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 = r ^{2} mod n` to

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 _{0} =
r` when

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

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.

-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)

[ search CSE | CSE | bsy's home page | links | webster | MRQE | google | yahoo | citeseer | pgp certserver | openpgp certserver | geourl's meatspace ]

bsy+www@bennetyee.org, last updated

email bsy.