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.
Source code: Available on GitHub
Related talks:
SOFIA: MQ-based signatures in the QROM
2018-03-28 – PKC 2018 –
2018-02-01 – PQCRYPTO research retreat –
@inproceedings{CHRSS18, author = {Ming-Shing Chen and Andreas H\"ulsing and Joost Rijneveld and Simona Samardjiska and Peter Schwabe}, title = {SOFIA: MQ-based signatures in the QROM}, booktitle = {Public Key Cryptography -- {PKC 2018}}, year = {2018}, publisher = {Springer-Verlag Berlin Heidelberg}, series = {Lecture Notes in Computer Science}, volume = {10770}, editor = {Michel Abdalla and Ricardo Dahab}, pages = {3--33}, url = {https://eprint.iacr.org/2017/680}, }