MiRitH

A MinRank in the Head Digital Signature Scheme

Introduction

MiRitH (from MinRank-in-the-Head) is a project in collaboration between the Technology Innovation Institute of Abu Dhabi (UAE) and the Politecnico di Torino (Italy).

MiRitH is a Digital Signature Scheme (DSS) whose security is based on the hardness of solving the MinRank problem. MiRitH has been submitted to the NIST Call for Additional Digital Signature Schemes for the Post-Quantum Cryptography Standardization Process (https://csrc.nist.gov/projects/pqc-dig-sig) . The scheme allows high flexibility in the parameters choice and several trade-offs between signature size and sign/verification time.

Scientific Background

Informally, the MinRank problem asks to find a non-trivial low-rank linear combination of some given matrices over a finite field. The construction of MiRitH starts from an MPC-in-the-Head (MPCitH) Zero-Knowledge Proof of Knowledge (ZKPoK) of a solution to the MinRank problem, which is then used to construct a 5-pass identification scheme, which in turn is converted into a non-interactive signature scheme via the Fiat-Shamir transform.

MiRitH is built on top of the MinRank-based signature scheme proposed by Adj, Rivera-Zamarripa, and Verbel [ARZV], which introduced a Multi-Party Computation (MPC) protocol P to verify solutions to the MinRank problem using the Kipnis--Shamir modeling and checking that a triple of shared matrices (Z, X, Y) satisfies Z = X.Y.

MiRitH introduces two optimizations over [ARZV], namely:

  1. It improves the protocol P by employing an optimization analogous to the one introduced by Kales and Zarevucha [KZ22, Section 2.5]. Note that this optimization is also used in [Fen22];
  2. It improves the protocol P by reducing the size of a random matrix used in the protocol, leveraging an optimization introduced by Feneuil [Fen22].

More details can be found in the technical specifications document.

Performance Overview

Version 1.0

As an example, for several variants of MiRitH, we report key/signature sizes and constant-time AVX2 implementation benchmarks on an 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz (Turbo Boost disabled). Other variants of the scheme and related performances can be found in the specifications document.

This numbers are dependent on the eXtended Keccak Code Package (XKCP) compiled with AVX2 enabled (https://github.com/XKCP/XKCP).

Set Variant Public key [bytes] Secret key [bytes] Signature (avg) [bytes] KeyGen[Clock Cycles] Sign [Clock Cycles] Verify [Clock Cycles]
Ia fast 129 16 7,661 109,128 8,904,1626 8,309,101
Ia short 129 16 5,665 109,128 77,911,848 78,181,045
Ib fast 144 16 8,800 201,971 8,322,639 7,822,115
Ib short 144 16 6,298 201,971 67,938,593 68,088,908
IIIa fast 205 24 16,668 251,654 23,438,882 19,142,362
IIIa short 205 24 12,423 251,654 199,753,944 178,080,288
IIIb fast 205 24 17,882 376,359 24,764,205 23,255,090
IIIb short 205 24 13,115 376,359 250,785,244 208,705,849
Va fast 253 32 29,568 506,581 37,349,137 36,863,070
Va short 253 32 21,763 506,581 316,823,994 315,372,936
Vb fast 274 32 31,980 695,762 39,828,244 38,710,077
Vb short 274 32 23,144 695,762 336,454,484 337,173,599

Submitters

Contacts