Tel Aviv University 10/1/2012 Introduction to Modern Cryptography (0368.3049) – Ex. 5 Submission in pairs on 24/1/2013, 11am 5 bonus points will be given to printed submissions. 1. Commitments. Consider the following Commitment scheme: • Public Parameters: primes p, q where p = 2q + 1, and two elements g1, g2 ? Z * p of order q. (I.e., g1, g2 are generators of a q-order subgroup G of Z * p . • To commit to s ? Zq, Alice chooses r ? Zq and sends C = g s 1 g r 2 (mod p). • To open the commitment Alice publishes (s, r) • To check the commitment Bob verifies that the values (C ' , s' , r' ) satisfy C ' = g s ' 1 g r ' 2 (mod p) In the following assume that the discrete-Log problem in G is hard (cannot be solved in polynomial time). Assume that Alice and Bob are both limited to polynomial-time computation. (a) Does Bob learn something before Alice opens the commitment? What if Bob is computationally unbounded? (b) Can Alice change the value s without being caught after the committing phase? What if Alice is computationally unbounded? We say that the public-parameters are good if: (1) p and q are large primes (at least 512 bits long), (2) p = 2q + 1, and (3) the elements g1, g2 ? Z * p are of order q. (c) Say that one of the parties chose the parameters. How can the other party verify that the parameters are good? (d) Say that Alice chooses good parameters. Can she cheat in the protocol? (e) Say that Bob chooses good parameters. Can he cheat in the protocol? (f) Suggest a way to let one of the parties choose the parameters while keeping the protocol secure. 2. Zero Knowledge (exam question). Let N = pq for some large primes p, q that are chosen at random. Let e be a prime number such that gcd(e, f(N)) = 1. Alice and Bob sharing a number y ? N and Alice wants to prove to Bob that she knows that e’th root of y, without reviling that root. The following protocol has been suggested: Common input: y, N, e. Alice’s input: x ? Z * N such that x e = y (mod N). Protocol: 1. Alice chooses r ? Z * N and sends a = r e (mod N). 1 2. Bob chooses b ? {1, . . . , e - 1} and sends b. 3. Alice computes c = rxb (mod N) and sends c. 4. Bob is convinced iff c e = ayb (mod N). (a) Assuming that the players are honest, what is the probability that Bob is convinced? (b) Prove that if Bob is honest, then he learns nothing from the protocol. Namely, describe an efficient simulator S that sample a triplet (a, b, c) that distributes the same as a real triplet in the protocol. (c) Assume that Alice makes a mistake, and uses x ' that is not the e’th root of y. It is possible that Bob can still be convinced? (d) Prove that if Bob knows some integer ? that is co-prime to e and an element z = x ? (mod N) then x can be computed efficiently. Hint: use the element y = x e (mod N). (e) Alice and Bob ran the protocol twice. The first time they got the triplet (a, b, c) and the second time (a ' , b' , c' ) where a = a ' and b ?= b ' . In both cases bob was convinced. Show that in this case Bob can compute x. Hint: Use the previous sub-question and define ? = b - b ' . Explain how to compute z and why ? is co-prime to e. (f) Alice and Bob uses this protocol for e = 3. In this case, can honest Bob can learn anything about x with probability greater then 1/4? Can Alice cheats Bob with probability greater then 1/4? 3. Fun with Secret Sharing. When planning a system of a nuclear missile launch we would like to make sure that a single lunatic will not be able to launch a missile. We would prefer that two lunatics will not be able to do so, as well. We would like that at least three out of five colonels will be crazy enough to permit a launch. It was decided to use an (3, 5) Shamir’s secret sharing where five colonels receive shares of the launch password S. Three colonels Alice, Bob and Carol are sitting inside the bunker when a launch order is received directly from the prime-minister (who is the only single lunatic authorized to order a launch). Two of the colonels reveal their true shares, but the third, who is interested in stopping the launch, reveals a false share. Therefore when the three colonels reconstruct the secret they get a false secret S ' . (a) Prove that given the three shares an honest colonel cannot discover which of the other two is to blame for the failed launch. (b) It turns out that the above launch order was an exercise designed to test the missile launch system. As Alice, Bob and Carol reconstructed a false secret a military police investigator (who has no knowledge of S) arrives at the base and interrogates all five colonels. Explain how can the investigator find the guilty colonel. (c) Propose a modification of the system to prevent this kind of cheating. Your suggestion should ensure that each coalition of less than three colonels will have no information on the secret. 2