Zero-knowledge, a newly emerging area of complexity theory, is of great interest to cryptographers because it provides a basis for the construction of secure authentication protocols. Most zero-knowledge protocols are of little practical use, though, because the communication costs are prohibitively high. This paper is of exceptional interest as it is the first to present a zero-knowledge protocol in which the communication costs are low enough that it can be proposed for real-life applications. The computational costs are also several orders of magnitude lower than those of RSA-based schemes. The authors have recently obtained a patent on their results.

The authors present two variants of their scheme: an identification scheme and a signature scheme (the latter, however, is not zero-knowledge). The situation in both is analogous to a public key system in which the public key is the user’s ID and the private key is information derived from that ID by a trusted distribution center. The zero-knowledge protocol is used to convince an interrogator that the user knows the secret information related to his or her ID without giving the interrogator any further information about the secret. The only requirement on the ID is that it uniquely identify the participant. Thus, the signature scheme also solves the identity-based signature problem originally proposed by Shamir in 1984.

This paper is an extended abstract, so the proofs and background are not given in great detail. Enough information is provided, however, to give the reader an intuitive feeling for why the protocols are secure. A complete paper containing improved results is due to appear in the Journal of Cryptology shortly.