Cryptography Reference
In-Depth Information
n
, and sends it to
A
, which is supposed to reply with a pair of
n
-bit long strings,
denoted (
β, γ
). Party
P
checks whether or not
f
(
αβ
)=
γ
.In
case equality holds,
P
sends
A
some secret information (e.g.,
the secret-key corresponding to
P
's public-key).
For
v
=2: Party
A
is supposed to uniformly select
α
For
v
=1: Party
P
uniformly selects
α ∈{
0
,
1
}
n
,and
∈{
0
,
1
}
n
, and replies
sends it to
P
, which selects uniformly
β ∈{
0
,
1
}
with the pair (
β, f
(
αβ
)).
Observe that
P
's strategy (in each case) is zero-knowledge (even w.r.t
auxiliary-inputs as defined in Definition 4.1): Intuitively, if the adver-
sary
A
chooses the case
v
= 1, then it is infeasible for
A
to guess a
passing pair (
β, γ
) with respect to a random
α
selected by
P
.Thus,
except with negligible probability (when it may get secret informa-
tion),
A
does not obtain anything from the interaction. On the other
hand, if the adversary
A
chooses the case
v
= 2, then it obtains a pair
that is indistinguishable from a uniformly selected pair of
n
-bit long
strings (because
β
is selected uniformly by
P
,andforany
α
the value
f
(
αβ
) looks random to
A
). In contrast, if the adversary
A
can conduct
two concurrent executions with
P
, then it may learn the desired secret
information: In one session,
A
sends
v
= 1 while in the other it sends
v
= 2. Upon receiving
P
's message, denoted
α
, in the first session,
A
sends it as its own message in the second session, obtaining a pair
(
β, f
(
αβ
)) from
P
's execution of the second session. Now,
A
sends the
pair (
β, f
(
αβ
)) to the first session of
P
, this pair passes the check, and
so
A
obtains the desired secret.
An attack of the above type is called a
relay attack
: During such an
attack the adversary just invokes two executions of the protocol and
relays messages between them (without any modification). However,
in general, the adversary in a concurrent setting is not restricted to
relay attacks. For example, consider a minor modification to the above
protocol so that, in case
v
=2,party
P
replies with (say) the pair
(
β, f
(
αβ
)), where
α
=
α
1
|α|
, rather than with (
β, f
(
αβ
)). The modi-
fied strategy
P
is zero-knowledge and it also withstands a relay attack,
but it can be “abused” easily by a more general concurrent attack.
⊕
