Paper 2017/680

SOFIA: MQ-based signatures in the QROM

Ming-Shing Chen, Andreas Hülsing, Joost Rijneveld, Simona Samardjiska, and Peter Schwabe

Abstract

We propose SOFIA, the first MQ-based signature scheme provably secure in the quantum-accessible random oracle model (QROM). Our construction relies on an extended version of Unruh's transform for 5-pass identification schemes that we describe and prove secure both in the ROM and QROM. Based on a detailed security analysis, we provide concrete parameters for SOFIA that achieve 128 bit post-quantum security. The result is SOFIA-4-128 with parameters that are carefully optimized to minimize signature size and maximize performance. SOFIA-4-128 comes with an implementation targeting recent Intel processors with the AVX2 vector-instruction set; the implementation is fully protected against timing attacks.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Post-quantum cryptographymultivariate cryptography$5$-pass identification schemesQROMUnruh's transformvectorized implementation
Contact author(s)
authors-sofia @ joostrijneveld nl
History
2017-07-18: received
Short URL
https://ia.cr/2017/680
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/680,
      author = {Ming-Shing Chen and Andreas Hülsing and Joost Rijneveld and Simona Samardjiska and Peter Schwabe},
      title = {SOFIA: MQ-based signatures in the QROM},
      howpublished = {Cryptology ePrint Archive, Paper 2017/680},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/680}},
      url = {https://eprint.iacr.org/2017/680}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.