Quantum algorithms and cryptography
Speaker:
Sean Hallgren, The Pennsylvania State University
Date and Time:
Monday, October 2, 2006 - 2:50pm to 3:40pm
Location:
Fields Institute, Room 230
Abstract:
An important goal in quantum computing is to determine which classical cryptosystems are secure in the presence of quantum computers. Shor showed that quantum computers can efficiently factor, and compute discrete logs over finite fields or elliptic curves, implying that quantum computers can break RSA and Diffie-Hellman. I will discuss this and its extension to number fields, resulting in quantum algorithms that can break the Buchmann-Williams key exchange protocol. I will also discuss which cryptosystems are currently secure against quantum computers.