MiRitH (from __M__in__R__ank-__i__n-__t__he-__H__ead) 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.

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:

- 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];
- 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.

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

- 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