Abstract: Post-Quantum Cryptography
In an August 2015 announcement, the Information Assurance Directorate of the US National Security Agency announced plans to begin a transition from the existing “Suite B” cryptography to quantum-resistant algorithms. Since Peter Shor of AT&T Bell Laboratories first published an efficient quantum algorithm for factoring in 1994, we have known that when a general-purpose quantum computer of sufficient size is built then all our commonly-used public-key cryptographic algorithms will be broken. Recent progress in the physics and engineering of quantum computation is changing our assumptions about the feasibility of building a cryptographically-relevant quantum computer, and while there are still technical challenges to address, the best estimates today are that such a machine could become feasible in as little as 10-15 years. Given our experience with past cryptographic algorithm transitions, this time horizon means that we need to start today the process of identifying hard problems that are quantum resistant, developing efficient cryptographic algorithms based on those problems, standardizing these algorithms and deploying them broadly, and deprecating our existing public-key cryptosystems.
In this talk I will discuss recent advances in quantum computing, the potential impact on public-key cryptographic algorithms and protocols widely used today, the upcoming US NIST “competition” for quantum-resistant algorithms and related standardization activities, and some quantum-resistant public-key algorithms currently under development.
Brian LaMacchia is a Microsoft Corporation Distinguished Engineer and heads the Security and Cryptography team within Microsoft Research (MSR). His team’s main project at present is the development of quantum-resistant public-key cryptographic algorithms and protocols. Brian is also a founding member of the Microsoft Cryptography Review Board and consults on security and cryptography architectures, protocols and implementations across the company. Before moving into MSR in 2009, Brian was the Architect for cryptography in Windows Security, Development Lead for .NET Framework Security and Program Manager for core cryptography in Windows 2000. Prior to joining Microsoft, Brian was a member of the Public Policy Research Group at AT&T Labs—Research. In addition to his responsibilities at Microsoft, Brian is an Adjunct Associate Professor in the School of Informatics and Computing at Indiana University-Bloomington and an Affiliate Faculty member of the Department of Computer Science and Engineering at the University of Washington. Brian also currently serves as Treasurer of the International Association for Cryptologic Research (IACR) and is Past President of the Board of Directors of the Seattle International Film Festival (SIFF). Brian received S.B., S.M., and Ph.D. degrees in Electrical Engineering and Computer Science from MIT in 1990, 1991, and 1996, respectively.