Paper 2023/1666

MiRitH: Efficient Post-Quantum Signatures from MinRank in the Head

Gora Adj, Technology Innovation Institute
Stefano Barbero, Politecnico di Torino
Emanuele Bellini, Technology Innovation Institute
Andre Esser, Technology Innovation Institute
Luis Rivera-Zamarripa, Technology Innovation Institute
Carlo Sanna, Politecnico di Torino
Javier Verbel, Technology Innovation Institute
Floyd Zweydinger, Technology Innovation Institute

Since 2016’s NIST call for standardization of post-quantum cryptographic primitives, developing efficient post-quantum secure digital signature schemes has become a highly active area of research. The difficulty in constructing such schemes is evidenced by NIST reopening the call in 2022 for digital signature schemes, because of missing diversity in existing proposals. In this work, we introduce the new post-quantum digital signature scheme MiRitH. As direct successor of a scheme recently developed by Adj, Rivera-Zamarripa and Verbel (Africacrypt ’23), it is based on the hardness of the MinRank problem and follows the MPC-in-the-Head paradigm. We revisit the initial proposal, incorporate design-level improvements and provide more efficient parameter sets. We also provide the missing justification for the quantum security of all parameter sets following NIST metrics. In this context we design a novel Grover-amplified quantum search algorithm for solving the MinRank problem that outperforms a naive quantum brute-force search for the solution. MiRitH obtains signatures of size 5.7 kB for NIST category I security and therefore competes for the smallest signatures among any post-quantum signature following the MPCitH paradigm. At the same time MiRitH offers competitive signing and verification timings compared to the state of the art. To substantiate those claims we provide extensive implementations. This includes a reference implementation as well as optimized constant-time implementations for Intel processors (AVX2), and for the ARM (NEON) architecture. The speed-up of our optimized AVX2 implementation relies mostly on a redesign of the finite field arithmetic, improving over existing implementations as well as an improved memory management.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in TCHES 2024
Digital SignatureMinRankMPCitHPost-QuantumZKPoKQuantum Analysi
Contact author(s)
gora adj @ tii ae
stefano barbero @ polito it
emanuele bellini @ tii ae
andre esser @ tii ae
luis zamarripa @ tii ae
carlo sanna @ polito it
javier verbel @ tii ae
floyd zweydinger @ tii ae
2024-01-31: revised
2023-10-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gora Adj and Stefano Barbero and Emanuele Bellini and Andre Esser and Luis Rivera-Zamarripa and Carlo Sanna and Javier Verbel and Floyd Zweydinger},
      title = {{MiRitH}: Efficient Post-Quantum Signatures from {MinRank} in the Head},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1666},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.