Post-Quantum Cryptography

ISBN-13: 9783540884026 / Angielski / Miękka / 2008 / 248 str.

Johannes Buchmann

Opis

Threedecadesagopublic-keycryptosystemsmadea revolutionarybreakthrough in cryptography. They have developed into an indispensable part of our m- ern communication system. In practical applications RSA, DSA, ECDSA, and similar public key cryptosystems are commonly used. Their security depends on assumptions about the di?culty of certain problems in number theory, such as the Integer Prime Factorization Problem or the Discrete Logarithm Problem. However, in 1994 Peter Shor showed that quantum computers could break any public-key cryptosystembased on these hard number theory problems. This means that if a reasonably powerful quantum computer could be built, it would put essentially all modern communication into peril. In 2001, Isaac Chuang and NeilGershenfeldimplemented Shor'salgorithmona7-qubitquantumcomputer. In 2007 a 16-qubit quantum computer was demonstrated by a start-up company with the prediction that a 512-qubit or even a 1024-qubit quantum computer would become available in 2008. Some physicists predicted that within the next 10 to 20 years quantum computers will be built that are su?ciently powerful to implement Shor's ideas and to break all existing public key schemes. Thus we need to look ahead to a future of quantum computers, and we need to prepare the cryptographic world for that future.

Spis treści

A New Efficient Threshold Ring Signature Scheme Based on Coding Theory.- Square-Vinegar Signature Scheme.- Attacking and Defending the McEliece Cryptosystem.- McEliece Cryptosystem Implementation: Theory and Practice.- Merkle Tree Traversal Revisited.- Explicit Hard Instances of the Shortest Vector Problem.- Practical-Sized Instances of Multivariate PKCs: Rainbow, TTS, and ?IC-Derivatives.- Digital Signatures Out of Second-Preimage Resistant Hash Functions.- Cryptanalysis of Rational Multivariate Public Key Cryptosystems.- Syndrome Based Collision Resistant Hashing.- Nonlinear Piece In Hand Perturbation Vector Method for Enhancing Security of Multivariate Public Key Cryptosystems.- On the Power of Quantum Encryption Keys.- Secure PRNGs from Specialized Polynomial Maps over Any .- MXL2: Solving Polynomial Equations over GF(2) Using an Improved Mutant Strategy.- Side Channels in the McEliece PKC.

O autorze

Johannes A. Buchmann is Professor of Computer Science and Mathematics at the Technical University of Darmstadt, and an Associate Editor of the Journal of Cryptology. In 1985, he received a Feodor Lynen Fellowship of the Alexander von Humboldt Foundation. He has also received the most prestigious award in science in Germany, the Leibniz Award of the German Science Foundation (Deutsche Forschungsgemeinschaft).

Blurb

This book constitutes the refereed proceedings of the Second International Workshop on Post-Quantum Cryptography, PQCrypto 2008, held in Cincinnati, OH, USA, in October 2008.

The 15 revised full papers presented were carefully reviewed and selected from numerous submissions. Quantum computers are predicted to break existing public key cryptosystems within the next decade. Post-quantum cryptography is a new fast developing area, where public key schemes are studied that could resist these emerging attacks. The papers present four families of public key cryptosystems that have the potential to resist quantum computers: the code-based public key cryptosystems, the hash-based public key cryptosystems, the lattice-based public key cryptosystems and the multivariate public key cryptosystems.