Problem: People want to use the Internet without having their habits documented or their personal data stolen. But they need to prove they’re authorized to access bank accounts or subscription sites, processes that usually involve revealing their identities.
Solution: Anna Lysyanskaya, an assistant professor of computer science, has developed a practical way for people to securely log in to websites without providing any identifying information. Her approach relies on “zero-knowledge proofs.” Say you want to browse a newspaper’s archives in total privacy. With zero-knowledge proofs, you subscribe using a pseudonym and receive digitally signed credentials. When you access the paper’s site, your computer sends encrypted versions of the pseudonym and credentials. The archive can’t decrypt this information; instead, it tests it for characteristics that valid data must have. (A certain field has to contain a specific number of digits, for example.) If the credentials are fake, some attribute will be wrong, and the site will be able to tell.
Zero-knowledge proofs have been around for a while, but they’ve required too much computing power to be practical. Collaborating with Jan Camenisch of the IBM Zürich Research Laboratory, Lysyanskaya developed algorithms that make both generating and testing credentials much more efficient. IBM is incorporating these algorithms into its Idemix anonymous-credential systems.