Games and Adversaries Sample Clauses

Games and Adversaries. We use elements of Xxxxxx’x random systems formalization [35, 36] with slightly different notation. × ⊂ An (X, Y)-system [36] takes inputs from X and generates outputs in Y which can depend probabilistically on all previous outputs. A game G from X to Y is a tuple (O, W) consisting of an (X, Y)-system O and a random variable W (X Y)+ which may depend on O, representing the “winning” transcripts. → { } → { } × ∪ { } × ∪ { } For example, key recovery of some keyed function Fk : XF YF could be modelled as follows. Let G : K 0 be an output oracle for the adversary, meaning when the adversary has a guess for the key, it queries G on that guess. Then O is defined as O(0, x) = Fk(x) and O(1, x) = G(x), with k chosen uniformly at random from K. Then O is a ( 0 XF 1 K, YF 0 )- system, and W is defined to be all transcripts containing a query of the form O(1, k) = 0. Note that this example illustrates how W need not be independent of O. We write O⟨t ⟩ to mean the event that (O(x1), O(x2),..., O(xA)) = (y1, y2,..., yA), (3) where t = ((x1, y1),..., (xA, yA)). Note that the order of the queries in the xxxx- script is important since O could be stateful. ∈ ⟨ ⟩ ∈ × × ∈ − An adversary A interacting with G = (O, W) is a (Y, X)-system, which produces a sequence of inputs (x1, x2,.. .) ∈ X+, where xi is generated using y1, y2,..., yi−1 with yj = O(xj) for j = 1,...,i 1; note that x1 is generated without any O-output. We let AO denote the sequence ((x1, y1), (x2, y2),.. .) (X Y)+, which is a random variable. We say that a transcript AO wins if AO W, and write A t for t = ((x1, y1), (x2, y2),..., (xq, yq)) (X Y)+ to denote the event that A produces xi as the ith oracle input when given (y1, y2,..., yi−1) as oracle outputs, for i = 1,..., q. Let q be a non-negative integer, then the advantage of an adversary A win- ning game G within q queries is G,q