Cryptography Reference
In-Depth Information
mined (essentially as a random value), but only one party (i.e., Party 1)
“can see” (i.e., knows) this value. Clearly, if both parties are honest
then they both output the same uniformly chosen bit, recovered in
Steps C3 and C4, respectively. Intuitively, each party can guarantee
that the outcome is uniformly distributed, and Party 1 can cause pre-
mature termination by improper execution of Step 3. Formally, we have
to show how the effect of every real-model adversary can be simulated
by an adequate ideal-model adversary (which is allowed premature ter-
mination). This is done in (67, Sec. 7.4.3.1).
7.4
Concurrent execution of protocols
The definitions and results surveyed so far refer to a setting in which,
at each time, only a single execution of a cryptographic protocol takes
place (or only one execution may be controlled by the adversary).
In contrast, in many distributed settings (e.g., the Internet), many
executions are taking place concurrently (and several of them may
be controlled by the same adversary). Furthermore, it is undesirable
(and sometimes even impossible) to coordinate these executions (so to
effectively enforce a single-execution setting). Still, the definitions and
results obtained in the single-execution setting serve as a good starting
point for the study of security in the setting of concurrent executions.
As in the case of stand-alone security, the notion of zero-knowledge
provides a good test case for the study of concurrent security. Indeed,
in order to demonstrate the security issues arising from concurrent
execution of protocols, we consider the concurrent execution of zero-
knowledge protocols. Specifically, we consider a party
P
holding a ran-
dom (or rather pseudorandom) function
f
:
n
,and
willing to participate in the following protocol (with respect to secu-
rity parameter
n
).
6
The other party, called
A
for adversary, is supposed
to send
P
a binary value
v
2
n
{
0
,
1
}
→{
0
,
1
}
∈{
1
,
2
}
specifying which of the following
cases to execute:
6
In fact, assuming that
P
shares a pseudorandom function
f
with his friends (as explained
in Section 3.3), the above protocol is an abstraction of a natural “mutual identification”
protocol. (The example is adapted from (71).)
