Paper 2023/1719

MQ on my Mind: Post-Quantum Signatures from the Non-Structured Multivariate Quadratic Problem

Ryad Benadjila, CryptoExperts (France)
Thibauld Feneuil, CryptoExperts (France), Sorbonne University
Matthieu Rivain, CryptoExperts (France)
Abstract

This paper presents MQ on my Mind (MQOM), a digital signature scheme based on the difficulty of solving multivariate systems of quadratic equations (MQ problem). MQOM has been submitted to the NIST call for additional post-quantum signature schemes. MQOM relies on the MPC-in-the-Head (MPCitH) paradigm to build a zero-knowledge proof of knowledge (ZK-PoK) for MQ which is then turned into a signature scheme through the Fiat-Shamir heuristic. The underlying MQ problem is non-structured in the sense that the system of quadratic equations defining an instance is drawn uniformly at random. This is one of the hardest and most studied problems from multivariate cryptography which hence constitutes a conservative choice to build candidate post-quantum cryptosystems. For the efficient application of the MPCitH paradigm, we design a specific MPC protocol to verify the solution of an MQ instance. Compared to other multivariate signature schemes based on non-structured MQ instances, MQOM achieves the shortest signatures (6.3-7.8 KB) while keeping very short public keys (few dozen of bytes). Other multivariate signature schemes are based on structured MQ problems (less conservative) which either have large public keys (e.g. UOV) or use recently proposed variants of these MQ problems (e.g. MAYO).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. EuroS&P 2024
Keywords
post-quantum signatureMPC-in-the-Headmultivariate cryptography
Contact author(s)
ryad benadjila @ cryptoexperts com
thibauld feneuil @ cryptoexperts com
matthieu rivain @ cryptoexperts com
History
2024-05-16: revised
2023-11-06: received
See all versions
Short URL
https://ia.cr/2023/1719
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1719,
      author = {Ryad Benadjila and Thibauld Feneuil and Matthieu Rivain},
      title = {{MQ} on my Mind: Post-Quantum Signatures from the Non-Structured Multivariate Quadratic Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1719},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1719}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.