Quantum computers will break today's most popular public-key cryptographic systems, including RSA, DSA, and ECDSA. This book introduces the reader to the next generation of cryptographic algorithms, the systems that resist quantum-computer attacks: in particular, post-quantum public-key encryption systems and post-quantum public-key signature systems.

Leading experts have joined forces for the first time to explain the state of the art in quantum computing, hash-based cryptography, code-based cryptography, lattice-based cryptography, and multivariate cryptography. Mathematical foundations and implementation issues are included.

This book is an essential resource for students and researchers who want to contribute to the field of post-quantum cryptography.

Table of Contents

Introduction to post-quantum cryptography

Daniel J . Bernstein .

1 ls ctyptography dead?

2 A taste of post-quantum ctyptography

3 Challenges in post-quantum cryp tography

4 Comparison to quantum etyptography

Quantum computing

Sean Hallgren, Ulrich Vollmer

1 Classical etyptography and quantum computing

2 The oomputat.ional model

3 The quantum Fburier transform

4 The hidden subgroup problem

5 Search algorithms

6 Outlook

References

Hash-based Digital Signature Schemes

Johannes Buchmann, Erik Dahmen, Michael Szydlo

1 Hash based one- time s ignature s chemes

2 Merlde's tree authentication scheme

3 One- time key-pair generation using an PRNG

4 A uthenticat.ion path computation

5 'Iree chaining

6 Distributed signature generat.ion

7 Security of the Merkle Signatw,, Scheme

References

Code-based cryptography

Raphael Overbeck, Nicolas Sendrier

1 Introduction

3 The security of computing syndromes as one-way function

4 Codes and structures

6 Annex

References

Lattice-based Cryptography

Daniele Micciancio, Oded Regw

1 lntroductfon

2 Preliminaries

3 Finding Short Vectors in Random q-ary Lattices

4 Hash Functions

5 Public Key Encryption Schemes

6 Digital Signature Schemes

7 Other Cryptographic Primitives

8 Open Questions

References

Multivariate Public Key Cryptography

Jintai Ding, Bo-Yin Yang

1 Introductfon

2 The Basics of Multivariate PKCs

3 Examples of Multivariate PKCs

4 Basic Constructions and Variations

5 Standard Attacks

6 The Future

References

About the Authors

Daniel J. Bernstein is a research professor in the Department of Computer Science at the University of Illinois at Chicago. Professor Bernstein has received a U.S. National

Science Foundation CAREER award, a Cyber Trust award, three more U.S.government grants, and a Sloan Research Fellowship for his research in computational number theory, cryptography, and computer security. He is the author of several dozen papers and two of the Internet's most popular server software packages, djbdns and qmail.

Johannes A. Buchmann is a Professor of Computer Science and Mathematics at the Technische Universität Darmstadt and an associate editor of the Journal of Cryptology. He received the most prestigious award in science in Germany, the Leibniz Award of the German Science Foundation. He also received the Karl Heinz-Beckurts Award for technology transfer. He is a member of the German Academy of Science and Engieneering.

Erik Dahmen is a PhD student in Prof. Buchmann's research group at the Technische Universität Darmstadt. He received his diploma degree in Mathematics from the Technische Universität Darmstadt in 2006. Erik Dahmen is the author of various research papers on hash-based cryptography.