First, our assumptions. We're going to arithmetic modulo n, where n = pq, and p and q are primes. Factoring n is assumed to be intractible.
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 = r^2 mod n to V. Now, V choses a random bit b, and sends it to P. P replies with y = r s^b. To verify P's claim, V computes y^2 and compares it with x v^b.
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 y_1 = r s when b = 1 and y_2 = r when b = 0 means you also know s, since y_1/y_2 = 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 = t^2 / 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'' 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 chose s, and v is widely published. 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.
-bsy
-------------------- 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)
|
|
|
|
|
