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.1.0

As an example, for several variants of MiRitH, we report key/signature sizes and constant-time implementation benchmarks on the following platforms:

  • 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz (Turbo Boost disabled) using AVX2 instructions
  • Apple M1 Max chip with NEON instructions
  • Cortex M4 STM32F407G board

Other variants of the scheme and related performances can be found in the specifications document submitted to NIST, or in the updated ePrint article.

This numbers are dependent on the eXtended Keccak Code Package (XKCP) compiled with AVX2 enabled for the AVX2 implementation, see (https://github.com/XKCP/XKCP for more details).

Size AVX2 NEON Cortex M4 STM32F407G
Set Variant Bit security Secret key [bytes] Public key [bytes] Signature [bytes] Key Generation [MCycles] Signing Online (%) Signing Total [MCycles] Verification [MCycles] Key Generation [MCycles] Signing Online (%) Signing Total [MCycles] Verification [MCycles] Key Generation [MCycles] Signing Total [MCycles] Verification [MCycles]
Ia fast 144 16 129 7,877 0.109 28.02 5.19 4.72 0.083 23.75 3.33 2.92 1.18 87.5 84.8
Ia short 144 16 129 5,673 0.109 4.24 31.91 31.76 0.083 3.19 23.06 22.75 - - -
Ib fast 159 16 144 9,105 0.197 28.11 5.51 4.94 0.158 21.37 4.15 3.77 2.23 135 117
Ib short 159 16 144 6,309 0.197 4.4 31.4 31.47 0.158 3.57 24.14 23.79 - - -
IIIa fast 207 24 205 17,139 0.247 27.3 11.1 10.43 0.206 23.52 6.71 6.16 - - -
IIIa short 207 24 205 12,440 0.247 5.65 54.42 54.93 0.206 4.09 38.85 38.33 - - -
IIIb fast 232 24 205 18,459 0.373 27.29 12.67 12.34 0.315 22.91 7.27 6.99 - - -
IIIb short 232 24 205 13,136 0.373 6.02 56.07 56.53 0.315 4.25 39.83 39.4 - - -
Va fast 273 32 253 31,468 0.515 32.38 19.33 17.95 0.408 26.12 12.66 11.92 - - -
Va short 273 32 253 21,795 0.515 5.73 92.39 92.23 0.408 4.42 64.95 64.26 - - -
Vb fast 301 32 274 34,059 0.703 32.19 21.96 20.44 0.602 25.47 15.19 14.62 - - -
Vb short 301 32 274 23,182 0.703 5.72 103.53 103.47 0.602 4.42 76.55 76.44 - - -

Submitters

Contacts