Paper 2017/936

A tight security reduction in the quantum random oracle model for code-based signature schemes

André Chailloux and Thomas Debris-Alazard

Abstract

Quantum secure signature schemes have a lot of attention recently, in particular because of the NIST call to standardize quantum safe cryptography. However, only few signature schemes can have concrete quantum security because of technical difficulties associated with the Quantum Random Oracle Model (QROM). In this paper, we show that code-based signature schemes based on the full domain hash paradigm can behave very well in the QROM i.e. that we can have tight security reductions. We also study quantum algorithms related to the underlying code-based assumption. Finally, we apply our reduction to a concrete example: the SURF signature scheme. We provide parameters for 128 bits of quantum security in the QROM and show that the obtained parameters are competitive compared to other similar quantum secure signature schemes.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Quantum Random OracleQuantum-Safe CryptographyCode-Based CryptographySignature SchemeQuantum Decoding Algorithm
Contact author(s)
thomas debris @ inria fr
andre chailloux @ inria fr
History
2017-09-27: revised
2017-09-27: received
See all versions
Short URL
https://ia.cr/2017/936
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/936,
      author = {André Chailloux and Thomas Debris-Alazard},
      title = {A tight security reduction in the quantum random oracle model for code-based signature schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2017/936},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/936}},
      url = {https://eprint.iacr.org/2017/936}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.