, Page 00001 The New York Times Archives

MATHEMATICIANS and cryptologists have discovered a way for people to prove that they possess secret information - from their credit card numbers to military access codes - without giving any of the information away.

This keenly paradoxical discovery has upset the traditional understanding of mathematical proof. Beyond that, however, it may also hold the power to transform the many aspects of modern life where processes of identification are subject to abuse, from everyday financial transactions to encounters between enemy aircraft.

Blending pure logic with computer technology, the researchers are developing an area of mathematics called zero-knowledge proof. Where a conventional proof conveys information, a zero-knowledge proof is meant to convey only the assurance that the information is in hand. The goal is to convince a second party without providing any of the knowledge that would allow him, or an eavesdropper, to convince a third party.

''You want to be able to prove some fact and not disclose why the fact is true,'' said Sylvio Micali of the Massachusetts Institute of Technology, one of the originators of the idea. ''You want to convince without giving more knowledge than is strictly necessary.'' Ideally, that is no knowledge at all.


Continue reading the main story

''Everybody has secret information that he needs to show to somebody to identify himself,'' said Adi Shamir of Israel's Weizmann Institute of Science. With zero-knowledge proofs, ''instead of giving away the secret, he proves he knows the secret,'' he said.

Dr. Shamir and two co-workers, Amos Fiat and Uriel Feige, have designed a way to use zero-knowledge proof cheaply and quickly in electronic chips that could be implanted, for example, in credit cards. Credit cards using chips, ''smart cards,'' are already in development, but a smart card using zero-knowledge proof could identify the cardholder to a merchant without giving the merchant the knowledge - the card number - that would let him make illicit purchases or forge a new card.

''I can go to a Mafia-owned store a million successive times and they still will not be able to misrepresent themselves as me,'' Dr. Shamir said. Because this invention also affects military uses of identification procedures, the United States recently imposed a secrecy order on it; the order was quickly rescinded amid an outcry from American mathematicians. [ Page C3 ] The fundamental mathematical ideas of zero-knowledge proof that underlie the invention are firmly in the public domain, and many researchers are pursuing other applications.

The essence of zero-knowledge proof lies in an interactive exchange of information between the ''prover'' and the ''verifier.'' That is a break with the traditional practice of simply writing a proof down, once and for all - or simply revealing one's password.

''What I find most exciting is that the whole notion of what constitutes a mathematical proof is broadening,'' said Manuel Blum of the University of California at Berkeley, who has played a central role in making such proofs workable. ''This interactive exchange has never existed before. In Euclid the proofs are written down - from Euclid to us - just one way.''

The other new element is a role for chance. In effect, the verifier asks a series of questions, choosing the questions by some electronic equivalent of flipping a coin.

Suppose, for example, the prover has a bafflingly complex maze the size of New York City. She points to two locations - Times Square and Shea Stadium - and asserts that she knows paths through the maze connecting them. How can she convince a verifier without actually showing him how to get from one point to the other? Process of Interrogation

She picks a third point on a path -say, the Brooklyn Promenade - and offers to reveal either the path from Times Square to the promenade or the path from the promenade to the stadium. The verifier flips a coin and chooses one half-path or the other. If she is lying, he already has a 50 percent chance of catching her.

Now she picks yet another point -Rikers Island - and they repeat the process of interrogation. The verifier checks either the path from Times Square to Rikers or from Rikers to the stadium. Again, if the prover is lying, she has a 50 percent chance of being caught.

''Eventually you are convinced, because of my willingness to show you either of two halves,'' Dr. Shamir said. ''You chose which half you wanted to see.''

The verifier can repeat the process as long as he likes. After 300 inquiries, the chance that she is lying has fallen to one part in 2#3#0#0, more than the number of atoms in the universe.

This example is not quite a zero-knowledge proof, however. Even though the verifier never actually sees a full path, the many fragments of paths can eventually enable him to piece together an understanding of the maze.

A more precise example involves a collection of lines joined at nodes, which mathematicians call a graph. A well-known problem is to ask whether it is possible to paint the nodes of a certain graph, using just three different colors, so that no line has the same color at both ends.

To construct a large graph that can be colored this way is easy. But the reverse problem, to find a way of coloring a given graph, has been shown to be very hard - a member of a class of problems that cannot be solved in a reasonable amount of time. The difficulty of the problem rises rapidly as the graph becomes bigger. Practical Applications

Dr. Micali and other experts in the field, who include Shafi Goldwasser, Charles Rackoff, Oded Goldreich and Avi Wigderson, have shown that graph colorings - and all other problems in the same hard class - can be proved in ways that convey zero knowledge of the proof.

Similar problems of pure mathematics are used electronically in the practical applications. Instead of a credit-card number, a user may have a computer chip containing, in effect, a unique, complicated graph and its coloring. A verifying computer knows the graph associated with each user, but does not know how to color it.

For practical applications, the mathematics of graph coloring are too slow. But using techniques of number theory, researchers have come up with zero-knowledge proofs that adapt well to electronic circuitry. Dr. Shamir's device carries out the whole back-and-forth exchange in less than one second.

''It's about 100 times faster,'' he said. ''If you had to wait 100 seconds for a smart card to prove its identity, no one would use such a scheme.''

Most important to many applications is that the technology of zero-knowledge proof so effectively separates the ability to generate a proof from the ability to verify it. Protecting Aircraft Signals

That addresses a security problem that arises in the most sensitive areas. For example, ''friend or foe'' recognition signals used by military aircraft can, in theory, be intercepted electronically or analyzed from captured aircraft. A system based on zero-knowledge proof would be impervious to both threats, mathematicians suggest.

The same applies to emergency destruct signals sent in encoded form from ground controllers to missiles. By separating the ability to generate an identification from the ability to verify the identification, a system would remain secure even when missiles with their electronics were captured and examined.

''There are going to be thousands of those boxes in missiles to verify those instructions, and it's going to be very difficult to keep the secrecy of the verification device,'' said one researcher. ''It's going to be much easier to keep the secrecy of the instruction-generation device that's going to be stored in the basement of the White House.''

As the technology advances, however, the less apocalyptic applications will come first. Some mathematicians speculate about automated procedures for signing contracts or communicating orders to stockbrokers. Signing Onto Computers

It may even be possible for users to dispense with the electronics. Dr. Blum is designing a procedure for signing onto computer systems that would remove the possibility of intercepting a password. He envisions users being presented with a string of about 10 letters, and typing a response of the same length - but a different response every time.

In effect, the sequence of letters is like a sequence of 10 questions to the user, and the ''password'' is actually a procedure for changing some letters to others. For the system to work, the procedure has to be so easy that no calculation will be involved.

''But somebody who's watching you won't be helped a bit,'' Dr. Blum said, ''because when he tries to log on as you, he'll be asked different questions.''

Continue reading the main story