The MPC-in-the-Head (MPCitH) paradigm is widely used for building post-quantum signature schemes, as it provides a versatile way to design proofs of knowledge based on hard problems. Over the years, the MPCitH landscape has changed significantly, with the most recent improvements coming from VOLE-in-the-Head (VOLEitH) and Threshold-Computation-in-the-Head (TCitH). While a straightforward application of these frameworks already improve the existing MPCitH-based signatures, we show in this work that we can adapt the arithmetic constraints representing the underlying security assumptions (here called the modeling) to achieve smaller sizes using these new techniques. More precisely, we explore existing modelings for the rank syndrome decoding ( \(\textsf{RSD}\) ) and \(\textsf{MinRank}\) problems and we introduce a new modeling, named dual support decomposition, which achieves better sizes with the VOLEitH and TCitH frameworks by minimizing the size of the witnesses. While this modeling is naturally more efficient than the other ones for a large set of parameters, we show that it is possible to go even further and explore new areas of parameters. With these new modeling and parameters, we obtain low-size witnesses which drastically reduces the size of the “arithmetic part” of the signature. We apply the TCitH and VOLEitH frameworks to our new modeling for both \(\textsf{RSD}\) and \(\textsf{MinRank}\) and compare our results to the NIST candidates RYDE, MiRitH, and MIRA (MPCitH-based schemes from \(\textsf{RSD}\) and \(\textsf{MinRank}\) ). We also note that recent techniques optimizing the sizes of GGM trees are applicable to our schemes and further reduce the signature sizes by a few hundred bytes. We obtain signature sizes below 3.5 kB for 128 bits of security with \(N=256\) parties (a.k.a. leaves in the GGM trees) and going as low as \(\approx \) 2.8 kB with \(N=2048\) , for both \(\textsf{RSD}\) and \(\textsf{MinRank}\) . This represents an improvement of more than 2 kB compared to the original submissions to the 2023 NIST call for additional signatures.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Dual Support Decomposition in the Head: Shorter Signatures from Rank SD and MinRank

  • Loïc Bidoux,
  • Thibauld Feneuil,
  • Philippe Gaborit,
  • Romaric Neveu,
  • Matthieu Rivain

摘要

The MPC-in-the-Head (MPCitH) paradigm is widely used for building post-quantum signature schemes, as it provides a versatile way to design proofs of knowledge based on hard problems. Over the years, the MPCitH landscape has changed significantly, with the most recent improvements coming from VOLE-in-the-Head (VOLEitH) and Threshold-Computation-in-the-Head (TCitH). While a straightforward application of these frameworks already improve the existing MPCitH-based signatures, we show in this work that we can adapt the arithmetic constraints representing the underlying security assumptions (here called the modeling) to achieve smaller sizes using these new techniques. More precisely, we explore existing modelings for the rank syndrome decoding ( \(\textsf{RSD}\) ) and \(\textsf{MinRank}\) problems and we introduce a new modeling, named dual support decomposition, which achieves better sizes with the VOLEitH and TCitH frameworks by minimizing the size of the witnesses. While this modeling is naturally more efficient than the other ones for a large set of parameters, we show that it is possible to go even further and explore new areas of parameters. With these new modeling and parameters, we obtain low-size witnesses which drastically reduces the size of the “arithmetic part” of the signature. We apply the TCitH and VOLEitH frameworks to our new modeling for both \(\textsf{RSD}\) and \(\textsf{MinRank}\) and compare our results to the NIST candidates RYDE, MiRitH, and MIRA (MPCitH-based schemes from \(\textsf{RSD}\) and \(\textsf{MinRank}\) ). We also note that recent techniques optimizing the sizes of GGM trees are applicable to our schemes and further reduce the signature sizes by a few hundred bytes. We obtain signature sizes below 3.5 kB for 128 bits of security with \(N=256\) parties (a.k.a. leaves in the GGM trees) and going as low as \(\approx \) 2.8 kB with \(N=2048\) , for both \(\textsf{RSD}\) and \(\textsf{MinRank}\) . This represents an improvement of more than 2 kB compared to the original submissions to the 2023 NIST call for additional signatures.