Cryptography Reference
In-Depth Information
We now explain the meaning of the tracing game. A tracing game is an
interaction between two parties: the adversary and the tracer. The tracer has
at its disposal the encryption and the tracing key (resp. tk,ek) while the
adversary has a set of user keys, that is a subsequence of sk
1
,...,sk
n
. The
ultimate objective of the tracer is to identify one of the keys that the adversary
controls.
Next we set the general rules of engagement between the tracer and the
adversary that are determined by Q,R. The essence on the constraint that
we will place on the interaction is the following: as long as the tracer follows a
certain query distribution as defined in Q the adversary is obliged to formulate
its responses in a way that they will satisfy the predicate R with su
cient
probability.
More specifically the pair hA,Ti will be said to be σ-admissible according
to a tracing game hKeyDist,Q,Ri with a parameter t provided that A,T
follow the proper rules of engagement. More specifically, σ-admissible would
be a pair of interacting algorithms that when T sends some message to A that
follows a random variable of Q then A has to provide a response that satisfies
the predicate R. Formally we have the following definition.
Definition 3.13. Let hA,Ti be a pair of interacting algorithms (the adversary
and the tracer) and let hKeyDist,Q,Ri be a tracing game. Fix n ∈ N and a
C ⊆ [n]. We assume the following regarding the interaction of hA,Ti :
• Initialization. The tuple (tk,ek,sk
1
,...,sk
n
) ← KeyDist(1
n
) is sampled
and the adversary A is given input {sk
j
}
j∈C
while the tracer T is given
tk,ek.
• Round actions. A and T exchange messages in rounds until the tracer T
terminates. In the i-th round, T goes first transmitting a value q
i
and then
party A responds by a value a
i
. In case A produces no output at a certain
round i, the value a
i
is defined to be ⊥.
We say the pair hA,Ti is σ-admissible for the game hKeyDist,Q,Ri for
t-coalitions, where t ∈ N if for any n ∈ N,C ⊆ [n], in case q
i
is distributed
according to some member of Q it holds that for any C ⊆ [n] with |C|≤ t,
Prob[R(C,tk,ek,sk
1
,...,sk
n
,q
i
,a
i
) = 1] ≥ σ
where a
i
is the response of A to the query q
i
on input {sk
j
}
j∈C
. We denote
the random variable that is the output of the tracer T after interacting with A
by hA,Ti(tk,ek,sk
1
,...,sk
n
,C). We denote the maximum number of rounds
that take place before T terminates the protocol by r
hA,T i
.
The definition of σ-admissibility in plain words it says that as long as the
tracer T follows some of the specified valid moves in Q the party A has to
oblige and satisfy with its response the predicate R with probability σ. We
observe that the predicate R takes into account the total information that
is available to both players and thus it is not something that the tracer T
