First, our assumptions. We're going to do arithmetic modulo n, where n = pq, and p and q are primes. Factoring n is assumed to be intractable.
Rabin showed in [RabinFunc] that finding square roots modulo n is equivalent to factoring n. That is, if you have an algorithm that can find a square root of a number modulo n, then you can use that algorithm to factor n. Our zero-knowledge proof will consist of rounds of interaction which shows that the prover knows a square root of a published number, where we do not reveal any new information about the square root. It is known that there exists a square root to this number (public knowledge), i.e., it is a quadratic residue. The factors of the modulus n may be entirely secret. (U. Feige et al show a refinement in [FFS] which allows the published number to be a non-quadratic residue of a particular form as well, thus revealing less information; in either case, runs of the protocol itself reveals no new information.)
The prover, P, publishes the quadratic residue v for which P claims to know a root s.
When P wishes to prove its knowledge of s to the verifier, V, P runs several rounds of interaction. In each round, P choses a new random number r and sends x = r2 mod n to V. Now, V choses a random bit b, and sends it to P. P replies with y = r sb. To verify P's claim, V computes y2 and compares it with x vb.
Now, let's do the analysis. The first claim is that only P can successfully complete the protocol for both possible values of b. This is clear, since knowing y0 = r when b = 0 and y1 = r s when b = 1 means you also know s, since y1/y0 = s. The second claim is that an imposter P' who does not actually know s can succeed with a probability of exactly 1/2 each round: to see this, notice that if P' guesses correctly that b = 0, then it can just follow the protocol and succeed; on the other hand, if P' guesses that b = 1, P' can generate x by chosing a random number t and setting x = t2 / v. The response is y = t. The third claim is that no new information is released. To see this, consider what an eavesdropper E hears. In the case of the random bit b = 0, E sees a random numer r and its square x; in the case of b = 1, E sees the numbers rs and x = (rs)2/v. These are numbers that the eavesdropper could have generated in a closet. More precisely, a simulator S can run both sides of the protocol, and by using advanced information as to the value of the random bit (model is a poly-time TM with an auxiliary input tape of random bits), S can simulate the protocol without knowledge of s.
Each round of the proof shows that there is a 1/2 chance that a prover P'' (we don't know whether P'' is P or P') might not actually know s. Iterating 20 times gives a probability of less than 2-20 or .0000009536 that P'' does not actually know s.
Such zero-knowledge proofs can be used for authentication -- the value of v can be generated from a randomly chosen s, and v is widely published as the public authentication ``puzzle''. A successful zero-knowledge proof showing knowledge of s authenticates identity. In [StrongboxIn25th], Doug Tygar and I show how to obtain superexponential scaling in security modulo the factorization assumption, run the protocol in constant rounds while retaining the zero-knowledge property, and simultaneously perform key exchange.
Note that using only a zero-knowledge proof of identity over a communication channel such as that provided by TCP/IP does not suffice to provide a secure communication channel: an attacker who has access to a link in the Internet through which your packets all cross may wait until the authentication protocol completes, and then `hijacks' your connection. Furthermore, doing the obvious protocol piggy-backing to run zero-knowledge authentication at the same time as, say, anonymous Diffie-Hellman key exchange is subject to message tampering -- an attacker may substitute her/his own Diffie-Hellman values in your packets, using your zero-knowledge authentication as a subroutine. Care must be taken when composing two cryptograhic protocols to ensure that the needed security properties are retained.
-------------------- bibtex format bibliographic entries -------------------- @TechReport(RabinFunc, Author="Michael Rabin", Institution="Laboratory for Computer Science, Massachusetts Institute of Technology", Title="Digitalized Signatures and Public-Key Functions as Intractable as Factorization", Key="Rabin", Year=1979, Month="January", Number="MIT/LCS/TR-212") @InProceedings(FeigeFiatShamir, Key="Feige", Author="Uriel Feige and Amos Fiat and Adi Shamir", Title="Zero Knowledge Proofs of Identity", Year=1987, Pages="210-217", Booktitle="Proceedings of the 19th ACM Symp. on Theory of Computing", Month="May") @Inproceedings(StrongboxIn25th, Key="Tygar and Yee", Author="J. D. Tygar and Bennet S. Yee", Title="Strongbox: A System for Self Securing Programs", Organization = "ACM", Booktitle="CMU Computer Science: 25th Anniversary Commemorative", Year = 1991)
firstname.lastname@example.org, last updated