2007 - Exercises X.
1. Let p be a prime and a a primitive element of Z*. Ivan is given b = aa
(mod p)
and he claims that he knows the discrete logarithm a of b (mod p). Ivan wants
to convince Jan of this fact but without revealing a to him.
Propose a zero-knowledge protocol for this problem. Show that it satisfies completeness,
soundness and zero-knowledge properties.
2. Alice and Bob want to find out whether they like each other.
* Alice has a bit x A such that x A = 1 if she likes Bob and x A = 0 otherwise.
* Similarly, Bob has a bit XB such that XB = 1 if he likes Alice and XB = 0
otherwise.
* Alice and Bob want to compute / = xA A XB*
To prevent possible embarrassment, they want to find out / without revealing
their true feelings.
A friend of Alice and Bob, Carol, proposes the following protocol:
(i) Carol generates two random and distinct primes p, q such that p = q =
3 (mod 4), a random quadratic non-residue y with Jacobi symbol 1 and
computes n = pq. Then she announces the pair (n,y).
(ii) Alice chooses a random ti^ 6 Z*, and sends w = uAyXA
(mod n) to Bob.
(iii) If XB = 0, then Bob chooses a random UB E Z* and computes z =
u2
B (mod n), otherwise he sets z = w. Then he sends z to Carol.
(iv) If z is a quadratic residue modulo n, then Carol announces 0, otherwise she
announces 1.
Answer the following questions.
(a) Show that the protocol is correct.
(b) Suppose that Alice knows what Bob sends to Carol. Show that Alice can
learn something about Bob's bit x B even if x A = 0.
(c) Propose a modification of the protocol so that it is still correct, but neither
Alice nor Bob can learn anything about the other's bit, if his or her own
bit is 0.
3. Show how to implement standard oblivious transfer using l-out-of-2 oblivious
transfer.
4. How can a group of people calculate their average age without anyone learning
the age of anyone else?
5. Alice and Bob want to buy a new car, but they cannot agree on a color of the
car. Alice wants peas-green colour, Bob prefers salmon-pink. However, Alice
and Bob are not in the same city and are communicating over the Internet only.
They have decided to toss a coin. Consider the following 4 ways to do it:
(1) Alice tosses a coin sends the result to Bob.
(2) Alice videotapes herself tossing a coin and sends the result and the video
to Bob.
(3) i. Alice generates two random and distinct primes p, q such that p = q =
3 (mod 4), chooses a random bit b and a random quadratic non-residue
y modulo n = pq.
ii. Alice chooses a random u E Z*, computes z = u2
(mod n) and sends
z' = zyb
(mod n) and n to Bob.
iii. Bob chooses a random bit b' and sends it to Alice,
iv. Alice reveals p and q and the result is b  b'.
(4) i. Alice generates two random and distinct primes p, q such that p = q =
3 (mod 4), chooses a random bit b and a random quadratic non-residue
y modulo n = pq.
ii. Alice chooses a random uA E Z*, computes zA = uA (mod n) and sends
z'A = ZAyb
(mod n), y and n to Bob.
iii. Bob chooses a random bit b' and a random uB E Z*, computes ZB =
tí^ (mod n) and sends z'B = Zßyb
(mod n) to Alice,
iv. Alice reveals p and g and the result is b  b'.
Answer the following questions and explain your reasoning.
(a) Show which of the protocols is resilient against cheating Alice?
(b) Show which of the protocols is resilient against cheating Bob?
6. Suppose that you have supernatural powers and you can control the local
weather. More precisely, suppose that you can make it rain or not rain on
the following day. How could you prove this to a suspicious scientist without
revealing your magical methods so that the scientist would be 99,9% sure about
it. How long would it take?
7. Bonus Design an unconditionally secure oblivious transfer protocol (standard
or l-out-of-2) which uses the following device. If such a scheme does not exist,
explain the reason.
Alice Bob
a ˇ b = x ffiy
The device has two inputs a, b and two outputs x, y.
a, b, x, y are bits, related as follows: a ˇ b = x  y.
Alice (Bob) owns the input a (b) and the output x (y).
Once Alice (Bob) inputs a (b), she (he) immediately obtains x (y).
Pr[x = 0 | a, b] = Pr[x = 1 | a, b] = Pr[y = 0 | a, b] = Pr[y = 1 | a, b] = \