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.

⊕