Cryptography Reference
In-Depth Information
Protocol 17.2
A round in the Guillou-Quisquater authentication protocol.
A
B
( n, x )
( n, y )
r ∈ R Z n
t = r e (mod n )
t
c
←−
c ∈ R { 0 ,...,e− 1 }
s
−→
s ≡ rx c (mod n )
s e ?
ty c (mod n )
( accept or reject )
t = r e (mod n ). This value is sent to B. B, in turn, randomly selects a number
between 0 and e
rx c (mod n ) and
1 and challenges A with it. A computes s
sends s to B. B must now verify that s e
ty c (mod n ). Based on this verification,
he or she either accepts or rejects the proof of knowledge.
The protocol is complete, because
s e
( rx c ) e
r e ( x e ) c
ty c (mod n ) .
The protocol is sound, because an attacker can either guess s or prepare
himself or herself for one challenge c (before he or she sends out commitment t ).
In the first case, the success probability (i.e., the probability to correctly guess s )
is negligible for any reasonably sized n . In the second case, the attacker guesses
c , randomly selects s , computes t
s e y −c (m o d n ), and uses this value as
commitment. If B really used c as a challenge, then the attacker could respond with
s . B, in turn, could compute ty c
s e (mod n ) and accept the proof.
Of course, if the guess was wrong and B provides a different challenge, then the
attacker can only guess s .
One may wonder whether an attacker can prepare himself or herself for
different challenges to improve his or her odds. Let us assume that an attacker can
prepare himself or herself for two challenges c 1 and c 2 and sends a corresponding t
to B. In this case, the following pair of equivalences must hold:
s e y −c y c
s e
ty c 1 (mod n )
1
s e
ty c 2 (mod n )
2
Search WWH ::




Custom Search