IV054 Coding, Cryptography and Cryptographic Protocols
2008 ­ Exercises X.
1. Consider the group Z
p such that p = 2q + 1 where p, q are primes. Let g  Z
p.
Show that g is a quadratic residue modulo p if and only if gq
 1 (mod p).
2. Consider the following 1-out-of-2 oblivious transfer scheme which uses the RSA
cryptosystem.
(1) The sender has two secrets m0, m1. He generates RSA keys: n, e and d,
and picks two random messages x0 and x1.
The sender transmits n, e, x0, and x1 to the receiver.
(2) The receiver chooses a random message k, encrypts k with e, and adds xb,
b  {0, 1}, to the encryption of k (modulo n).
The receiver sends the result q to the sender.
(3) The sender computes k0 to be the decryption of q - x0 and similarly k1 to
be the decryption of q - x1, and sends r0 = m0 + k0 and r1 = m1 + k1 to
the receiver.
Show that the receiver can compute mb, but cannot compute m1-b and that the
sender cannot learn b.
3. Consider the following coin flipping protocol:
(1) Bob generates a Blum integer n (ie. an integer n = pq, where p  q 
3 (mod 4) are distinct primes), a random x  N with gcd(x, n) = 1, and
computes x0  x2
(mod n) and x1  x2
0 (mod n). He sends n and x1 to
Alice.
(2) Alice guesses the parity of x and sends her guess to Bob.
(3) Bob sends x and x0 to Alice.
(4) Alice checks that both x0  x2
(mod n) and x1  x2
0 (mod n). Therefore,
Alice can determine if the guess is correct.
Show that Bob can cheat if n is not a Blum integer.
4. Alice needs to prove to Bob that she knows some secret quadratic non-residue
x  Z
n. The parties decide to use for this the zero-knowledge protocol for
quadratic residuosity (see lecture notes) with the modification that Bob accepts
if and only if he would reject in the residuosity protocol.
(a) Write the modified protocol explicitly.
(b) Is it a zero-knowledge protocol? Justify your answer.
5. Given p = 31, q = 23 and y = 220 perform the coin flipping by telephone
protocol (Protocol 2 from lecture). Show details.
6. Consider the following protocol for proving quadratic non-residuosity of x modulo
n:
(1) Victor randomly chooses a number r  Z
n and a bit b and sends to Peggy
y  r2
xb
(mod n).
(2) Peggy sends to Victor c = 0 if and only if there is z such that z2

y (mod n), otherwise she sends c = 1.
(3) Victor accepts if and only if c = b.
(a) Is this protocol an interactive proof system?
(b) Is it a zero-knowledge protocol?
Justify your answers.