M2: Post-Quantum Public Key Algorithms

If quantum computers of sufficient size could be built, the currently deployed public key algorithms (e.g., RSA, elliptic curve, Diffie-Hellman) would be broken.  The world needs to develop replacement public key algorithms soon.  There are several families of post-quantum algorithms proposed.  This tutorial will be aimed at engineers rather than math grad students.  It will explain these types of algorithms intuitively, rather than combining the description with formalism and security proofs.

Prerequisites: There are no prerequisites other than intellectual curiosity, and a good night’s sleep in the recent past.

Text: There is no textbook, although the instructors have been working on a 3rd edition of their textbook “Network Security”, and the contents of this tutorial will appear as a chapter in that, although it will not have been published by the time ACSAC occurs.

Outline:    

1. Introduction (20 minutes)
   1. Why quantum matters (Grover's and Shor's)
   2. NIST's process for helping the world standardize some algorithms
   3. Why RSA does both signatures and encryption, whereas most post-quantum schemes only do one or the other
2. Hash-based signature schemes (30 minutes)
3. Code-based schemes (45 minutes)
4. Multivariate schemes (40 minutes)
5. Lattice-based schemes (45 minutes)

About the Instructors:

Charlie Kaufman, security architect for the Midrange group at Dell/EMC, has been involved with computer networking and security issues for over 25 years, and holds over 50 patents in those fields. At Microsoft, he was the security architect for Windows Azure - Microsoft's Public Cloud offering - where he was involved with all aspects of cloud security from design through responding to ongoing attacks. At Lotus, he was chief security architect for Lotus Notes and Domino and later the entire Lotus product suite. At Digital, he was the Security Architect for their networking group and later for Digital's UNIX offering.

He has contributed to a number of IETF standards efforts including IPsec, S/MIME, and DNSsec and served as a member of the Internet Architecture Board. He is co-author of the popular textbook "Network Security: Private Communication in a Public World" and served on the National Academy of Sciences expert panel that wrote the book "Trust In Cyberspace".

Dr. Radia Perlman is a Fellow at Dell EMC.  Her specialties include network routing protocols, and network security. She developed the technology for making network routing self-stabilizing, largely self-managing, and scalable.  She also invented the spanning tree algorithm, which transformed Ethernet from a technology that supported a few hundred nodes within a single building, to something that could support large networks.  She also has made contributions in network security, including scalable data expiration, distributed algorithms despite malicious participants, DDOS prevention techniques, and user authentication. She is the author of the textbook “Interconnections” (about network layers 2 and 3) and coauthor (with Charlie Kaufman) of “Network Security: Private Communication in a Public World”). She has been recognized with many industry honors including induction into the National Academy of Engineering, the Inventor Hall of Fame, and lifetime achievement awards from Usenix and SIGCOMM.  She has a PhD in computer science from MIT.