Identification

Crypto Corner Editors: Peter Gutmann, [email protected] David Naccache, [email protected] Charles C. Palmer, [email protected]

Authentication without Identification

L

et’s say our user, Alice, wants to read her favorite online magazine. The magazine only allows users who have valid subscriptions to access its Web site. One way to proceed would be for the magazine to first ask

Alice who she is, have her prove it, and then check that she’s an authorized user. We call this approach authentication by identification, and it solves the basic problem of guaranteeing access only to authorized users. However, as far as protecting Alice’s privacy is concerned, this approach isn’t very good: every transaction requires Alice to reveal her identity. Why is it a bad idea for Alice to give away her identity during every transaction? For one thing, she has absolutely no idea what the magazine will do with this information. Will it try to prove its popularity by publishing who read what article? Will it accidentally leak the transaction log? Suddenly, every person with a Web browser can discover that Alice likes George Clooney and is a Boston Red Sox fan. This might seem harmless, but what if she’s looking for a job and an avid New York Yankees fan happens to interview her? Alice would much rather read her magazine without leaving an electronic trail. Moreover, it isn’t in the magazine’s best interest to be liable if Alice doesn’t get the job with the Yankees fan. Because the magazine can’t reveal what it doesn’t know, it’s much better off if it isn’t aware of Alice’s reading habits. What if Alice uses an anonymized username rather than her real name? In some situations, it might be good

enough, but in general it isn’t. Even if we don’t know a person’s real name—just a history of their past transactions—this information could be sufficient to identify the person. Alice might disclose her zip code to get a weather report for her region and her date of birth to read her horoscope. Her other habits could reveal her gender. If the same username links all these transactions together, they’re sufficient to identify Alice. What we need is a method for Alice to convince the magazine that she has a subscription without disclosing who she is: authentication without identification. Before we can examine it in full detail, though, we must look more closely at how to implement authentication by identification.

Authentication by identification Recall the fundamental, and by now classical, notion of a digital signature scheme. A signature scheme consists of three algorithms: setup, sign, and verify. First, Alice runs the setup algorithm to generate a pair of keys, her public key and her secret key. She publishes the public key, and whenever she wants to sign a message, she runs the sign algorithm using her secret key. Anybody can check whether Alice signed a message (or a person who knows the se-

PUBLISHED BY THE IEEE COMPUTER SOCIETY

■

cret key corresponding to Alice’s public key) by running the verify algorithm. A digital signature scheme is secure if no one other than the signer herself can compute a signature on a new document that will verify under her public key. Suppose Alice gives the magazine her public key, PK, when she starts her subscription. The magazine stores (Alice, PK) in its list of subscribers, so every time Alice attempts to access the magazine, it will check that she’s on the list and then have her prove that she’s the owner of the PK. Can we eliminate the need for the magazine to store a (potentially very large) list of its subscribers? Yes—if the magazine also has a signing key pair, then it doesn’t have to store anything. When Alice subscribes, the magazine will sign her PK, resulting in a certificate, Cert. When Alice wants to access the magazine, she submits (PK, Cert) and then proves that she owns the PK. We thus get authentication by identification. Alice has many options to prove to the magazine that she owns the PK. The magazine can challenge Alice to sign a random message, for example. (There is a subtlety: how can we ensure that Alice hasn’t forwarded the challenge to Bob, asked Bob to answer it, and then claim she knows Bob’s secret key? I leave this issue for the reader to ponder.)

ANNA LYSYANSKAYA Brown University

Zero-knowledge proofs We can modify the approach I described earlier to help Alice convince the magazine that she is indeed a valid subscriber without giving away any information about her identity. In particular, Alice shouldn’t reveal her public key, PK, or her certificate, Cert. However, she needs to prove that she

1540-7993/07/$25.00 © 2007 IEEE

■

IEEE SECURITY & PRIVACY

69

Crypto Corner

Background information n a series of papers, David Chaum1 initiated the study of anonymous credentials. Stefan Brands2 gave a general suite of techniques for obtaining anonymous credentials with attributes and showing that attributes satisfy certain broad classes of relations. However, each credential could only be unlinkably shown once. Latanya Sweeney3 demonstrated that 87 percent of the US population is likely to be uniquely identifiable by zip code, gender, and birth date, so being able to link transactions completely destroys anonymity. Even after the initial feasibility results were obtained by using the GMW protocol4 along the lines

I

described in the main text,5 efficient algorithms were still lacking. In a series of papers, Jan Camenisch and Anna Lysyanskaya6,7 gave an efficient solution to anonymous credentials; in particular, they exhibited a signature scheme with efficient protocols. These protocols have since been implemented by IBM Zurich; the resulting system, called Idemix,8 is slated for open source release.

2. S. Brands, Rethinking Public-Key Infrastructures and Digital Certificates: Building in Privacy, MIT Press, 2000. 3. L. Sweeney, “Uniqueness of Simple Demographics in the US Population,” Carnegie Mellon Univ., School of Computer Science, Data Privacy Lab White Paper Series LIDAP-WP4, 2000. 4. O. Goldreich, S. Micali, and A. Wigderson, “Proofs that Yield Nothing but Their Validity and a Methodology of Cryptographic Protocol Design,” Proc. IEEE Foundations of Computer Science, IEEE CS Press, 1986, pp. 174–187. 5. A. Lysyanskaya et al., “Pseudonym Systems,” Proc. Selected Areas in Cryptography 1999, LNCS 1758, Springer-Verlag, 1999, pp. 184–199. 6. J. Camenisch and A. Lysyanskaya, “An Efficient System for Non-Transferable Anonymous Credentials,” Proc. Eurocrypt 2001, LNCS 2045, Springer-Verlag, 2001, pp. 93–118. 7. J. Camenisch and A. Lysyanskaya, “A Signature Scheme with Efficient Protocols,” Proc. Security in Comm. Networks 2002, LNCS 2576, SpringerVerlag, 2002, pp. 268–289. 8. J. Camenisch and E. van Herreweghen, “Design

References

and Implementation of the Idemix Anonymous

1. D. Chaum, “Security without Identification: Trans-

Credential System,” Proc. ACM Conf. on Com-

action Systems to Make Big Brother Obsolete,”

puter and Comm. Security, ACM Press, 2002, pp.

Comm. ACM, vol. 28, no. 10, 1985, pp. 1030–1044.

21–30.

knows a PK such that, one, this PK is signed by the magazine with a Cert, and two, she also knows the corresponding secret key. To do this, we use a powerful and beautiful cryptographic tool known as a zero-knowledge proof. It lets a prover convince a verifier that a statement is true, without revealing any information besides the fact that the statement is true. Oded Goldreich, Silvio Micali, and Avi Wigderson proved that every NP statement can be proved in zero knowledge (see the “Background information” sidebar). If a prover knows a satisfying assignment to a Boolean formula , for example, then he or she can convince the verifier that  is satisfiable without revealing the input values on which  evaluates to TRUE. This is known as the GMW protocol. Applying this to 70

IEEE SECURITY & PRIVACY

■

MAY/JUNE 2007

our situation, Alice uses a zeroknowledge proof to convince the magazine that she knows a piece of data with certain properties (here, a PK, its corresponding secret key, and a certificate on the PK) without revealing any information about this data. Let us go over the GMW protocol. Suppose a prover wants to convince a verifier that she knows how to three-color a particular graph, and that she can paint every vertex red, green, or blue so that no two vertices of the same color are adjacent. In this version of the protocol, the prover uses physical materials—paper, colored pens, and paper cups. This is a simplification for the sake of exposition—the actual GMW protocol uses cryptographic constructs instead. In private, the prover draws the graph on a piece of paper and colors

all the vertices. The prover has six options for how to three-color the graph: one is the original three-coloring, and the other five are derived by permuting the colors. The prover chooses a random one of the six options, colors the graph accordingly, and then hides the vertices underneath paper cups. Now the verifier enters the room: he chooses any two adjacent vertices and removes the cups. If the vertices are the same color, then the verifier knows the prover is lying; otherwise, the verifier is satisfied. If the prover knows a three-coloring of the graph, then the verifier will always be satisfied. But if the graph isn’t three-colorable, the verifier has a chance to catch the prover. The verifier and prover can repeat the protocol many times. In each repetition, the prover must first choose a random way to three-color the graph from the six known possibilities. If the prover is lying, the verifier is extremely likely to catch her in one of the repetitions, thus this protocol is a convincing proof. The reason why this protocol is a zero-knowledge proof is that the verifier learns no information about the graph’s three-coloring. Because the prover has six permutations of colors to choose from every time, the two colors that the verifier sees are chosen uniformly at random from the set of {red, green, blue}. Once the verifier knows which vertices he wants to examine, he might as well have picked the colors himself. Recall that determining whether a graph is three-colorable is an NPcomplete problem, so any NP statement can be represented as an instance of graph three-colorability. Because we can prove graph three-colorability using a zero-knowledge proof, we can prove any statement in NP using a zero-knowledge proof. Specifically, we can prove statements about public keys and digital certificates.

From theory to practice If we just plug the GMW result into

Crypto Corner

our application, it would take Alice a very long time to convince the magazine that she’s a subscriber. Reducing the instance at hand to an instance of three-colorability isn’t recommended in practice. Instead, we need a digital signature scheme designed with our specific application in mind. It must support efficient zero-knowledge proofs of knowledge of a secret key, a public key, and a certificate such that, one, the secret key corresponds to the public key, and two, the certificate is the magazine’s signature on the public key. Fortunately, the cryptographic research community has solved this problem and more. Not only can Alice gain access to the magazine without revealing her public key, she can even obtain a certificate on her public key without revealing that key, or indeed anything about her identity! Alice can present the magazine with a blinded version of her public key by using a zero-knowledge proof to con-

vince the magazine that she knows the corresponding secret key. Satisfied, the magazine gives Alice a Cert for her PK. During this process, the magazine learns neither the PK nor the Cert it made for Alice. She can anonymously obtain credentials from various organizations, and, when needed, prove that she possesses them, without revealing any other information. Using state-of-the-art techniques, the running time for these protocols is comparable to performing 10 to 20 RSA decryptions. Additionally, anonymous credentials can contain attributes (such as expiration dates), similar to standard certificates. Alice can thus efficiently demonstrate possession of a set of credentials whose attributes satisfy broad classes of relations—for example, she can prove that her credentials haven’t expired yet. Efficient techniques limit the number of times Alice can show her credential or how often she can show it within a certain time period—

should she exceed the allotted limit, she gets “caught.” This strikes a balance between privacy and accountability: once a user breaks the rules, she can be identified, but if she behaves properly, her privacy is protected.

any authentication transactions performed today require us to disclose more information than is strictly needed, just for verification purposes. Fortunately, modern cryptography provides us with a way to solve the verification problem without leaking unnecessary personal information. These techniques are fast, secure, and preserve privacy, so let’s use them!

M

Anna Lysyanskaya is an assistant professor of computer science at Brown University. Her research interests include cryptography, theoretical computer science, and computer security. Lysyanskaya has a PhD in computer science and electrical engineering from MIT. Contact her at [email protected].

www.computer.org/security/

■

IEEE SECURITY & PRIVACY

71