ZERO KNOWLEDGE AND THE DEPARTMENT OF DEFENSE
Susan M. Landau · 1988
The game is simple and apparently paradoxical: Prove you know something— an ID number, an access code—without revealing even a single bit of the information itself. The importance is obvious: from credit card numbers to computer passwords, we are increasingly reliant on the secure electronic transmission of what are known as signatures. Yet how can one transmit a signature without potentially revealing to an eavesdropper—or an unethical vendor—all the information he needs in order to masquerade as the sender? Three Israeli computer scientists—Uriel Feige, Amos Fiat and Adi Shamir, of the Weizmann Institute—figured out how to play the game, called zero knowledge proofs of identity. They publicized their result at conferences, and they applied for U.S. patent protection. Ironically the United States said disclosure was detrimental to the national security, and imposed a secrecy order. The three Israelis sought relief, and, with intervention from powerful sources, they got it. Though no one will say for certain, it appears that the National Security Agency (NSA), the government decrypter of secrets, stepped in to help. What the research is, and why the NSA had reason to involve itself, is the story we present here. The technical part has its genesis in the work of Stephen Cook and Richard Karp of the early seventies. Our model of a computer is a RAM, a Random Access Machine. At issue is complexity: on a problem of input size m, how many steps does it take as a function of m to solve the problem? Certain problems are easy; by the obvious method, two m x m matrices can be multiplied in O(m 3) steps (although there are considerably more sophisticated algorithms which require only O(m2-376) steps). Other problems are less obvious. The crucial distinction comes between those problems with polynomial time solutions (the class P), and those which require more than polynomial time. The latter are considered, infeasible. What Cook did was to show that the question Is a boolean expression satisfiable? occupies a special place in the hierarchy of problems. It is solvable in polynomial time by a nondeterministic RAM1 (it is in NP, Nondeterministic Polynomial time), and it is as hard as any other problem in NP (it is complete). If satisfiabilit y has a polynomial time solution, so will any other problem in NP. Karp then showed that a number of combinatorial problems shared that characteristic, called NP-completeness, including kcolorability (can the vertices of a given undirected graph be colored with k colors so that no two adjacent vertices have the same color?), knapsack (given » finite set of integers «,, is there a subset which sums to an integer Kl), This article is the seventeenth in the series of Special Articles published in the Notices. The author, Susan Landau, is an assistant professor of computer science at Weslyan University. She received her Ph. D from M.I.T.; her thesis gave a polynomial time method for determining solvability by radicals. Her research interests include computational complexity and algebra.