Cryptography Reference
In-Depth Information
is necessarily capable of computing by itself. In the coming section we will
formulate various tracing games that are resulting from interactions based on
multiuser encryption schemes.
We will also condider the following variations of the definition:
1. Stateful Tracing. Consider the set {Q h } h∈{0,1} , a collection of sets of
random variables. In this specification, for the adversary to oblige and
satisfy the R predicate we require the tracing queries of T to be consistent
with the history of previous queries. More specifically, we define, for any
i > 0, h = hq 1 ,...,q i−1 i to be the history of the queries posed by T (it is
empty if i = 1), the next query q i should be distributed according to some
member of Q h in order to impose the σ lower bound in the satisfaction of
the predicate R for A. Note that the predicate R will also take the history
of the queries into account while producing a result. Stateful tracing is
thus placing a further possible restriction on the tracer's side as it drops
any compliance requirements on the part of A when the tracer becomes
inconsistent with the query history.
2. Alfresco. When tracing alfresco the tracer needs to form every query he
makes to be computationally indistinguishable from members of Q (or
from Q h in case of stateful tracing) in the eyes of any user of the sys-
tem. More specifically, when the tracer has submitted h = hq 1 ,...,q i−1 i
queries, in the i-th round it must choose a query that is indistinguishable
from a member of Q (from a member of Q h in case of stateful tracing).
Note that this is a different type of restriction on the tracer T . Without
this restriction the tracer has the flexibility to provide queries to T that
are outside of Q; depending on the case this may carry substantial advan-
tages for the tracer that are stripped in the case of alfresco tracing. On
the plus side alfresco may allow the tracer to perform tracing while honest
participants are also listening to the tracing channel (without disrupting
their correct operation).
3. Tracing with Resetting. The adversary A is not allowed to maintain state
from one round to the next, i.e., in each round the tracer can “reset” the
adversary. This model weakens the adversary A as it is prohibited from
keeping knowledge of previous queries. This can be taken advantage of
by the tracer T . Alternatively, when the adversary maintains state across
rounds (i.e., the default in the definition above) we say we deal with
history-recording adversaries.
4. Abrupt adversaries. This is a strengthening of the adversarial model that
enables A to finish the game at a moment of its choosing. This means
that A may produce a special symbol as a response. Given such symbol
the tracer T is not allowed to submit any further queries. We note that
this is not in violation of the basic tenet of being admissible : A when it
forms a σ-admissible pair with the adversary is still supposed to satisfy
the R with probability at least σ. If A is abrupt though it may decide to
stop the tracing game with probability as high as 1 −σ if given a query
Search WWH ::




Custom Search