Zero Knowledge In Our Quantum Future

Se han resaltado estos términos de búsqueda: interactive quantum science future
John Watrous: Zero Knowledge In Our Quantum Future

Strangely enough for an academic, Professor John Watrous envisions a world in which we know less about one another, not more. His research into the theory of zero-knowledge quantum cryptographic protocols holds the tantalizing promise of keeping two parties in perfect ignorance about one another, otherwise known as privacy.

Recently lured to Waterloo from the University of Calgary, where he held a Canada Research Chair in Quantum Computing, Professor Watrous states his reason for being here plainly: “The quantum computing effort that's happening here is like no other program in the world. It's a large collection of some of the best people in the world working intensively on quantum computing. Being a part of that is very compelling.”

Professor Watrous is a member of Waterloo's Institute for Quantum Computing, and has previously worked with IQC members Richard Cleve, Andris Ambainis, and Ashwin Nayak. He hopes to begin collaborating with other UW faculty members in the near future.

An affiliate member at The Perimeter Institute for Theoretical Physics, Professor Watrous goes there regularly to participate in seminars and discussions, and to work with collaborators including Daniel Gottesman.

Professor Watrous’s research centers on the emerging field of quantum information science, specifically the theory of quantum information and its applications to algorithms, complexity theory, and cryptography. He became interested in the strange, sometimes bizarre quantum world when, as a doctoral student studying computational number theory at the University of Wisconsin-Madison under Eric Bach, he learned about Shor's Algorithm for integer factoring on a quantum computer. In 1994 Peter Shor, a computer scientist at AT&T Labs, proved that a quantum computer would be capable of efficiently finding the factors of very large numbers—ones with several hundred digits for instance—which is a task believed to be intractable for ordinary computers. The discovery caused great excitement in computer science, and sent shockwaves throughout defense establishments worldwide, who realized that standard cryptographic schemes could be broken by quantum computers. Watrous began investigating quantum theory, and ran with it, with his supervisor's blessing.

After graduating in 1998, Watrous spent a postdoctoral year at the Laboratoire d'Informatique Theorique et Quantique at the Universite de Montreal. In 1999, he joined the faculty at the University of Calgary, where he held a Canada Research Chair in Quantum Computing. He has rapidly made a name for himself as one of the world's preeminent quantum computing theorists, and is a member of several of Canada's key quantum research groups. In addition to his memberships at the Institute for Quantum Computing and the Perimeter Institute, he is a Scholar in the Quantum Information Processing Group in the Canadian Institute for Advanced Research. Professor Watrous joined Waterloo's School of Computer Science in July, 2006.

According to quantum theory, learning information from a piece of quantum data inherently changes it. Furthermore, separated yet “entangled” particles exhibit useful correlations over vast distances. These characteristics have proved extremely useful for cryptographic purposes. Quantum cryptography guarantees secure communications since any attempt to intercept a package (say, of photons) sent between two users will disturb their quantum state and thus expose the observer. While practical quantum computers are a relatively distant goal, quantum cryptography can be implemented over short distances using today's technology, offering a far higher level of data security than is available using ordinary computers.

Much of Professor Watrous's recent work has focused on the theory of quantum cryptography. “Part of quantum cryptography deals with how quantum computers will affect different aspects of classical cryptography. For example, it is important to understand which cryptographic systems are safe against attacks by quantum computers and which are not. For practical reasons, the ideal situation is one where ordinary people who don't have quantum computers can still use cryptography that is secure against quantum computers.”

Indeed this is not the current situation, due to the fact that cryptosystems that are used in practice can be defeated with quantum computers using Shor's Algorithm. “Right now, when you order books from Amazon.com, say, your credit card number is encrypted, but if someone had a quantum computer, they could easily decrypt it and steal your credit card number.”

Recently, Professor Watrous did intriguing work relating to zero-knowledge, a key goal in both classical and quantum cryptography. In cryptography, a zero-knowledge proof or zero-knowledge protocol is an interactive method for one party to prove to another that a (usually mathematical) statement is true, without revealing anything other than the veracity of the statement. For example, one application is to implement a cryptographic system in which two people can interact, and one comes away convinced of the other person's identity, but nothing more, and therefore cannot steal it.

Although zero-knowledge has been studied in the classical realm for over 20 years, and many interesting zero-knowledge protocols have been proposed and proved secure against attacks by classical computers, there was been a major problem in merging this theory with quantum information. In fact, none of these protocols could be proved secure against attacks by quantum computers. That changed about a year ago when Professor Watrous developed a new technique for addressing this problem, and in the process proved that many of the known zero-knowledge protocols indeed are secure even against quantum computer attacks.

“For a long time we really didn't know which way it would go... it was conceivable that quantum information would simply forbid zero-knowledge protocols from existing in a quantum world. That turns out to be false, and now we can show that a wide range of zero-knowledge protocols are secure against quantum computer attacks. This is good news, in a practical sense, because ordinary people who don't have quantum computers still need to use cryptography—so at least in the case of zero-knowledge we know it is possible to do this in a way that would be secure even if a few people did have quantum computers.”

When he is not envisioning the nature of a perfectly paranoid brave new quantum world, Watrous occasionally toys with more prosaic alternate realities. “I have two young kids, so it's not like I'm really enjoying the nightlife much...” In addition to playing with his children, he likes to read and occasionally enjoys a good computer game.

2007 Jan 28
Campaign Waterloo

David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1

Tel: 519-888-4567 x33293
Fax: 519-885-1208