Computing a bit of security.

Computing a bit of security

It sounds like a children's game: proving that you know a particular password without having to give away any hint of what the actual password is. Yet such a scheme is at the heart of several recently proposed methods for keeping information--whether in the form of an access code, identification number or message -- secret during transactions involving computers. Successfully implemented, these methods would make computer operations such as transferring funds, signing contracts and sending and receiving sensitive information more secure. Neither eavesdropper nor receiver would be able to hijack enough information to masquerade as the sender.

The methods involve a mathematical concept that goes by the name of "zero-knowledge" or "minimum-disclosure" proof. Most schemes involving zero-knowledge proofs are interactive (SN: 8/30/86, p.140). The idea is to set up a dialogue between the "prover" (for example, a bank-card bearer who would like to prove that he can legitimately withdraw a certain sum of money) and the "verifier" (say, a bank). The verification process works if the prover's identity is tied to a mathematical statement for which the prover but not the verifier or a potential eavesdropper has a proof.

One such identification method, proposed by Uriel Feige, Amos fiat and Adi Shamir of the Weizmann Institute of Science in Rehovot, Israel, depends on the observation that while it's relatively easy to determine whether a number is prime (divisible only by itself and 1), finding the factors of a large composite number is difficult and time-consuming (SN: 3/30/85, p.202). By following the mathematical procedure built into the Shamir scheme, the prover uses his knowledge of the prime factors of a large number to persuade a verifier, who knows the number but can't factor it, that his "signature" is valid.

"The result is striking," comments computer scientist Susan Landau of Wesleyan University in Middletown, Conn., in this month's NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY. "Smart" identification cards containing a computer chip could be programmed to conduct the protocol, she says. However, without further safeguards, card theft would be a problem.

The Shamir method, like many other digital signature and identification schemes, may also fail if a third party, unknown to the prover and verifier, surreptitiously acts as a go-between, transferring information between the prover and verifier. "It's the problem of active eavesdropping," says Fiat, who is presently at the University of California at Berkeley. The eavesdropper may be not only listening in but also making changes in the conversation.

In attempts to overcome such problems and to speed up verification, researchers have been exploring variations of the basic zero-knowledge method. At last week's meeting in Atlanta of the American Mathematical Society, one group proposed a protocol that allows the prover to give away some information for the sake of efficiency. In this scheme, as described by Claude Crepeau of the Massachusetts Institute of Technology, information is represented as blocks, each with a value of 0 or 1. The prover, depending on the verifier's request, can reveal either the value of a block or that two blocks have the same value (without giving away the value). This idea can be converted quite readily into a practical mathematical procedure and computer protocol.

In another variation, Manuel Blum of the University of California at Berkeley and MIT's Silvio Micali recently found a way to make zero-knowledge proofs noninteractive. With their method, the prover can publish the fact that a theorem is true without revealing the proof and without the active participation of a verifier.