Cryptology ePrint Archive: Report 2017/680

SOFIA: MQ-based signatures in the QROM

Ming-Shing Chen and Andreas Hülsing and Joost Rijneveld and 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.

Category / Keywords: Post-quantum cryptography, multivariate cryptography, $5$-pass identification schemes, QROM, Unruh's transform, vectorized implementation

Date: received 7 Jul 2017, last revised 9 Jul 2017

Contact author: authors-sofia at joostrijneveld nl

Available format(s): PDF | BibTeX Citation

Version: 20170718:150037 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]