Post-quantum cryptography

Motivation:
Introduction
Quantum computing
Cryptography:
Hash-based
Code-based
Lattice-based
MQ

Hash-based public-key cryptography

One-time signatures

1979. Leslie Lamport. "Constructing digital signatures from a one way function." Technical Report SRI-CSL-98, SRI International Computer Science Laboratory.

1992. Jurjen N. Bos, David Chaum. "Provably unforgeable signatures." Pages 1–14 in: Ernest F. Brickell (editor). Advances in cryptology—CRYPTO '92. 12th annual international cryptology conference, Santa Barbara, California, USA, August 16–20, 1992, proceedings. Lecture Notes in Computer Science 740. Springer. ISBN 978-3-540-65069-0.

1994. Daniel Bleichenbacher, Ueli M. Maurer. "Directed acyclic graphs, one-way functions and digital signatures." Pages 75–82 in: Yvo Desmedt (editor). Advances in cryptology—CRYPTO '94. 14th annual international cryptology conference, Santa Barbara, California, USA, August 21–25, 1994, proceedings. Lecture Notes in Computer Science 839. Springer. ISBN 3-540-58333-5.

1996. Daniel Bleichenbacher, Ueli M. Maurer. "On the efficiency of one-time digital signatures." Pages 145–158 in: Kwangjo Kim, Tsutomu Matsumoto (editors). Advances in cryptology—ASIACRYPT '96: international conference on the theory and applications of cryptology and information security, Kyongju, Korea, November 3–7, 1996, proceedings. Lecture Notes in Computer Science 1163. Springer. ISBN 3-540-61872-4. MR 98g:94001.

1996. Daniel Bleichenbacher, Ueli M. Maurer. "Optimal tree-based one-time digital signature schemes." Pages 363–374 in: Claude Puech, Rüdiger Reischuk (editors). STACS 96, 13th annual symposium on theoretical aspects of computer science, Grenoble, France, February 22–24, 1996, proceedings. Lecture Notes in Computer Science 1046. Springer. ISBN 3-540-60922-9.

2001. Adrian Perrig. "The BiBa one-time signature and broadcast authentication protocol." Pages 28–37 in: CCS 2001, proceedings of the 8th ACM conference on computer and communications security, November 6–8, 2001, Philadelphia, Pennsylvania, USA. ACM Press.

2002. Michael Mitzenmacher, Adrian Perrig. "Bounds and improvements for BiBa signature schemes." Harvard Computer Science Technical Report TR-02-02. http://www.eecs.harvard.edu/~michaelm/NEWWORK/papers.html.

2002. Leonid Reyzin, Natan Reyzin. "Better than BiBa: short one-time signatures with fast signing and verifying." Pages 144–153 in: Lynn Margaret Batten, Jennifer Seberry (editors). Information security and privacy, 7th Australian conference, ACISP 2002, Melbourne, Australia, July 3–5, 2002, proceedings. Lecture Notes in Computer Science 2834. Springer. ISBN 3-540-43861-0.

2004. Josef Pieprzyk, Huaxiong Wang, Chaoping Xing. "Multiple-time signature schemes against adaptive chosen message attacks." Pages 88–100 in: Mitsuru Matsui, Robert J. Zuccherato (editors). Selected areas in cryptography, 10th annual international workshop, SAC 2003, Ottawa, Canada, August 14–15, 2003, revised papers. Lecture Notes in Computer Science 3006. Springer. ISBN 3-540-21370-8.

Merkle trees

1982. Ralph C. Merkle. "Secrecy, authentication, and public key systems." UMI Research Press. Previous version: 1979. Ph.D. thesis, Stanford University.

1987. Ralph C. Merkle. "A digital signature based on a conventional encryption function." Pages 369–378 in: Carl Pomerance (editor). Advances in cryptology—CRYPTO '87. Proceedings of the Conference on the Theory and Applications of Cryptographic Techniques held at the University of California, Santa Barbara, California, August 16–20, 1987. Lecture Notes in Computer Science 293. Springer. ISBN 3-540-18796-0. MR 89b:68005.

1990. Ralph C. Merkle. "A certified digital signature." Pages 218–238 in: Gilles Brassard (editor). Advances in Cryptology—Crypto '89, 9th annual international cryptology conference, Santa Barbara, California, USA, August 20–24, 1989, proceedings. Lecture Notes in Computer Science 435. Springer. ISBN 3-540-97317-6.

2002. Don Coppersmith, Markus Jakobsson. "Almost optimal hash sequence traversal." http://www.informatics.indiana.edu/markus/papers/AOhash.pdf. Pages 102–119 in: Matt Blaze (editor). Financial Cryptography, 6th international conference, FC 2002, Southampton, Bermuda, March 11–14, 2002, revised papers. Lecture Notes in Computer Science 2357. Springer. ISBN 978-3-540-00646-6.

2002. Helger Lipmaa. "On optimal hash tree traversal for interval time-stamping." www.tcs.hut.fi/~helger/papers/lip02a/. Pages 357–371 in: Agnes Hui Chan, Virgil Gligor (editors). Information security, 5th international conference, ISC 2002, Sao Paulo, Brazil, September 30–October 2, 2002, proceedings. Lecture Notes in Computer Science 2433. Springer. ISBN 978-3-540-44270-7.

2003. Markus Jakobsson, Frank Thomson Leighton, Silvio Micali, Michael Szydlo. "Fractal Merkle tree representation and traversal." Pages 314–326 in: Marc Joye (editor). Topics in cryptology—CT-RSA 2003, the cryptographers' track at the RSA conference 2003, San Francisco, CA, USA, April 13–17, 2003, proceedings. Lecture Notes in Computer Science 2612. Springer. ISBN 3-540-00847-0.

2004. Michael Szydlo. "Merkle tree traversal in log space and time." Pages 541–554 in: Christian Cachin, Jan Camenisch (editors). Advances in cryptology—EUROCRYPT 2004, international conference on the theory and applications of cryptographic techniques, Interlaken, Switzerland, May 2–6, 2004, proceedings. Lecture Notes in Computer Science 3027. Springer. ISBN 3-540-21935-8.

2005. Dalit Naor, Amir Shenhav, Avishai Wool. "One-time signatures revisited: have they become practical?" http://eprint.iacr.org/2005/442.

2007. Piotr Berman, Marek Karpinski, Yakov Nekrich. "Optimal trade-off for Merkle tree traversal." Theoretical Computer Science 372, 26–36.

2008. J. Buchmann, Erik Dahmen, M. Schneider. "Merkle tree traversal revisited." Pages 63–77 in: Johannes Buchmann, Jintai Ding (editors). Post-quantum cryptography, second international workshop, PQCrypto 2008, Cincinnati, OH, USA, October 17–19, 2008, proceedings. Lecture Notes in Computer Science 5299, Springer.

Variations and proofs

1989. Moni Naor, Moti Yung. "Universal one-way hash functions and their cryptographic applications." Pages 33–43 in: Proceedings of the 21st annual ACM symposium on theory of computing, May 14–17, 1989, Seattle, Washington, USA. ACM Press.

1990. John Rompel. "One-way functions are necessary and sufficient for secure signatures." Pages 387–394 in: Proceedings of the 22nd annual ACM symposium on theory of computing, May 13–17, 1990, Baltimore, Maryland, USA. ACM Press.

1999. Pankaj Rohatgi. "A compact and fast hybrid signature scheme for multicast packet authentication." Pages 93–100 in: CCS '99, proceedings of the 6th ACM conference on computer and communications security, November 1–4, 1999, Singapore. ACM Press.

2002. Tal Malkin, Daniele Micciancio, Sara K. Miner. "Efficient generic forward-secure signatures with an unbounded number of time periods." Pages 400–417 in: Lars R. Knudsen (editor). Advances in cryptology—EUROCRYPT 2002, international conference on the theory and applications of cryptographic techniques, Amsterdam, the Netherlands, April 28–May 2, 2002, proceedings. Lecture Notes in Computer Science 2332. Springer. ISBN 3-540-43553-0.

2005. Carlos Coronado. "On the security and efficiency of the Merkle signature scheme." http://eprint.iacr.org/2005/192.

2005. Jonathan Katz, Chiu-Yuen Koo. "On constructing universal one-way hash functions from arbitrary one-way functions." http://eprint.iacr.org/2005/328.

2006. Johannes Buchmann, Luis Carlos Coronado Garcia, Erik Dahmen, Martin Döring, Elena Klintsevich. "CMSS—an improved Merkle signature scheme." Pages 349–363 in: Rana Barua, Tanja Lange (editors). Progress in Cryptology—INDOCRYPT 2006, 7th international conference on cryptology in India, Kolkata, India, December 11–13, 2006, proceedings. Lecture Notes in Computer Science 4329. Springer. ISBN 3-540-49767-6.

2007. Johannes Buchmann, Erik Dahmen, Elena Klintsevich, Katsuyuki Okeya, Camille Vuillaume. "Merkle signatures with virtually unlimited signature capacity." Pages 31–45 in: Jonathan Katz, Moti Yung (editors). Applied Cryptography and Network Security, 5th international conference, ACNS 2007, Zhuhai, China, June 5–8, 2007, proceedings. Lecture Notes in Computer Science 4521. Springer. ISBN 978-3-540-72737-8.

2008. Erik Dahmen, Katsuyuki Okeya, Tsuyoshi Takagi, Camille Vuillaume. "Digital signatures out of second-preimage resistant hash functions." Pages 109–123 in: Johannes Buchmann, Jintai Ding (editors). Post-quantum cryptography, second international workshop, PQCrypto 2008, Cincinnati, OH, USA, October 17–19, 2008, proceedings. Lecture Notes in Computer Science 5299, Springer.

Surveys

2005. C. Dods, Nigel P. Smart, Martijn Stam. "Hash based digital signature schemes." Pages 96–115 in: Nigel P. Smart (editor). Cryptography and coding, 10th IMA international conference, Cirencester, UK, December 19–21, 2005, proceedings. Lecture Notes in Computer Science 3796. Springer. ISBN 3-540-30276-X. MR 2006m:94081.

2009. Johannes Buchmann, Erik Dahmen, Michael Szydlo. "Hash-based digital signature schemes." Pages 35–93 in: Daniel J. Bernstein, Johannes Buchmann, Erik Dahmen (editors). Post-quantum cryptography. Springer, Berlin. ISBN 978-3-540-88701-0.

Version

This is version 2008.11.30 of the hash.html web page.