IV054 Coding, Cryptography and Cryptographic Protocols
2012 - Exercises X.
1. Consider the coin-flipping by telephone protocol (Protocol 2 from the lecture). Let p = 19, q = 23
and y = 192. Show computation steps in detail.
2. The following thread appeared in the discussion group of IV054 after the notebook score statistics
in Information System had broken:
”Colleagues, I would like to know what is the average of points we have received for our assignments.”
How would you solve this problem if students do not want to individually reveal the number of
points they have received?
3. Let n = pq where p, q are primes. Propose an interactive proof system which allows Peggy to prove
to Victor that a ∈ Z∗
n is not a quadratic residue mod n. For both honest and dishonest Victor,
decide whether your protocol has the zero-knowledge property. Explain your reasoning.
4. Despite being very far from each other, Alice and Bob have decided to play poker. They have
invented the following protocol to deal cards:
(a) Let p = 2q + 1 where p, q are primes and let g be a generator of a subgroup of order q in Z∗
p.
(b) Alice has a public key yA = gxA
(mod p) and Bob has a public key yB = gxB
(mod p) where
xA, xB ∈ Zq.
(c) The cards are represented by a set {y1, . . . , y52} of mutually different quadratic residues mod
p known to both Alice and Bob.
(d) Alice for each i ∈ {1, . . . , 52} independently and randomly chooses ri from Zq and computes
a pair Ci = (gri
(mod p), yri
A yi (mod p)). Then she randomly permutes these pairs and sends
them to Bob.
(e) Bob randomly chooses five pairs from the received pairs (let us denote them C∗
1 , . . . , C∗
5 ) and
sends them to Alice. These pairs represent Alice’s cards.
(f) Bob randomly chooses five pairs from the remaining pairs (let us denote them
C1 = (z1,1, z1,2), . . . , C5 = (z5,1, z5,2)). For each i ∈ {1, . . . , 5} Bob independently and randomly
chooses ri, si from Zq, computes a triplet
Ci = (gri (mod p), zi,1gsi
(mod p), zi,2y
ri
B ysi
A (mod p))
and sends these triplets to Alice.
(g) For each received triplet Ci = (wi,1, wi,2, wi,3), where i ∈ {1, . . . , 5}, Alice computes a pair
CR
i = (wi,1,
wi,3
w
xA
i,2
(mod p)) and sends these pairs to Bob. These pairs represent Bob’s cards.
Prove that both Alice and Bob can compute which cards they have.
5. Does the 3-SAT problem have a zero-knowledge proof? Discuss.
6. Show how to construct a bit–commitment scheme from a cryptographically secure pseudo–random
generator G. Discuss the binding and hiding properties of your protocol.
7. Let m = pq be a modulus and let y be a quadratic non-residue modulo m. Consider the following
bit commitment scheme:
commit(r, b) = yb
r2
(mod m)
where r ∈ Z∗
m and b ∈ {0, 1}. Is the proposed scheme
(a) binding (computationally or perfectly)?
(b) hiding (computationally or perfectly)?