CS 161 Computer SecurityFall 2008 Dawn Song Notes 6We will consider the following authentication scheme: the user selects a number N = P · Q product of twolarge primes, and a number y = x2mod N. The server is given N,y and to login the user must prove that sheknows x : x2= y mod N. Notice the similarity between this and the RSA encryption function — here we aresquaring instead of cubing (when e = 3 in RSA) to implement our hard to invert function. Indeed, it turnsout that computing square roots modulo N is provably as hard as factoring N.Before we can state the zero-knowledge protocol and establish its properties, we first state a few facts aboutnumbers which are perfect squares modulo N. Let us restrict our attention to numbers 0 ≤ a ≤ N − 1 whichare relatively prime to N (i.e. gcd(a,N) = 1; note that if the gcd is not 1 then it must be P or Q, so such a’sare rare and lucky choices that we will not consider). This set of numbers is denoted Z∗N. For example, forN = 15, we would consider the numbers Z∗15= {1,2,4,7,8,11, 13,14}. Among these numbers only 1 and 4are perfect squares. Each has four square roots, {1,4,11,14} and {2,7, 8, 13} respectively. The square rootscome in pairs, e.g. 13 = −2 mod 15 and 8 = −7 mod 15. In fact, for general N = P · Q, exactly one quarterof the elements of Z∗Nare perfect squares and every perfect square a mod N has four square roots+− x and+− y. Moreover, multiplying a square by a square gives another square, since x2· z2mod N = (xz)2mod N.The protocol:The prover knows x : x2= y mod N. She wishes to prove to the verifier that she knows such a value x.1. The prover picks a random value r mod N and computes s = r2mod N and sends s to the verifier.2. The verifier randomly flips a coin and sends the prover the coin flip.3. The prover sends either t = r mod N if the coin flip is head or t = rx mod N if the coin flip is tail.4. The verifier checks that the received number matches the challenge. In particular, if the coin flip is head,then t2= s mod N; if the coin flip is tail, then t2= sy mod N.Let us prove that this protocol provides a zero-knowledge proof of knowledge of a square root of y mod N.We will show that if the prover does not know a square root of y mod N then the honest verifier will catch hercheating with probability at least 1/2. This will establish that the protocol constitutes a proof of knowledge.And we will show that the verifier cannot extract any extra information from the prover no matter how hedeviates from protocol. To do so we will show that for every verifier (no matter how dishonest), there is asimulator that can recreate the verifier’s view (his conversation with the prover) without any knowledge of asquare root of y mod N. This will establish that the protocol is zero-knowledge.Knowledge extractor: (Optional reading)If the prover wishes not to be caught cheating, she must be able to answer both possible challenges of theverifier. We will argue that such a prover must know a square root of y mod N. For the purposes of theproof let us assume that there is a hypothetical knowledge extractor who can travel backward in time, andafter issuing the first challenge and receiving the answer, the knowledge extractor travels back in time andissues the second challenge. By our assumption the prover can answer both challenges and therefore theknowledge extractor receives u : u2= s mod N and v : v2= sy mod N. Now w = v/u mod N is a square rootof y mod N, since w2= v2/u2= sy/s = y mod N. Thus the knowledge extractor can obtain a square root ofy mod N, therefore establishing that the prover must have known a square root of y mod N. It is importantCS 161, Fall 2008, Notes 6 1to understand that the knowledge extractor is a hyothetical construct. The protocol requires that the proveronly answer if the verifier issues one of the two possible challenges. Also note that a dishonest prover cancheat with probability 1/2. This probability of cheating can be decreased to 1/2kby repeating the protocolk times.The Simulator: (Optional reading, out of scope)What is the verifier’s view of the protocol. Note that we are now assuming that the prover is honest and thatthe verifier is trying to trick the prover into revealing information beyond her knowledge of some squareroot of y mod N. Challenge I by the verifier is s a uniformly random perfect square modulo N. Let us showthat the second challenge sy mod N is also a uniformly random perfect square modulo N. To see this firstnotice that sy is a perfect square, since it is a product of two perfect squares. Also notice that multiplicationby y mod N is a permutation of the numbers modulo N. This is because all the numbers we are workingwith are relatively prime to N, and therefore we can divide by y mod N to show that if sy = s0y mod N thens = s0mod N. Thus multiplication by y is a one-to-one mapping from the set of perfect squares to itself,and is therefore a bijection. Thus if we pick s at random among the perfect squares, then sy mod N is alsouniformly random among the perfect squares modulo N.The simulator selects a random r mod N, and with probability 1/2 sends the verifier r2mod N and withprobability 1/2 sends the verifier r2/y mod N. If the verifier issues challenge I, then in the first case thesimulator responds with r mod N and otherwise rewinds the simulation and starts again. If the verifierissues challenge II, then in the second case, the simulator responds with r mod N, and otherwise it rewindsthe simulation and starts again. Since the simulator’s choice is independent of the choice of challenge issuedby the verifier, it follows that the simulation will succeed in satisying the verifier with probability at least 1/2.The verifier’s view is accurately recreated by the simulator, since it just consists of a challenge consisting ofa uniformly random perfect square modulo N, followed by a response from the prover consisting of a squareroot of this number.CS 161, Fall 2008, Notes 6
View Full Document
Unlocking...