论文标题
紧凑的量子后签名来自PKP，SD和RSD问题的知识证明证明
Compact Post-Quantum Signatures from Proofs of Knowledge leveraging Structure for the PKP, SD and RSD Problems
论文作者
论文摘要
[IKOS07]中引入的MPC在目前的头号已确立为设计有效的数字签名的重要范式。它已被利用在野餐方案[CDG+ 20]中，该方案达到了NIST PQC标准化过程的第三轮。它也已在[BEU20]中用于用辅助范式引入知识证明（POK）。这种构造允许设计较短的签名，但在使用剪切时会引起不可忽略的性能开销。在本文中，我们介绍了POK利用结构范式以及其相关的挑战空间放大技术。我们的新设计POK方法为POK与Helper One带来了一些改进。确实，我们通过利用所考虑的问题的基本结构来展示如何在这些结构中替代助手。这种方法不会遭受带有辅助范式的pok固有的性能高架，因此在安全性，签名尺寸和性能之间提供了不同的权衡。我们还提出了四个新的量子后签名方案。第一个是基于与综合征解码问题的新的POK。它依赖于[BGKM22]和[FJR21]的想法，并使用一种新技术来改善后者，该技术可以看作是在中间方法中进行相遇的剪切和选择。其他三个签名基于我们的新POK利用结构方法，因此说明了其多功能性。我们提供了与排列的内核问题（PKP），综合征解码（SD）问题和等级综合征解码（RSD）问题有关的新POK。实际上，这些POK会导致比现有的签名可比或更短的签名。确实，考虑到（公共密钥 +签名），我们的签名与PKP问题有关，低于9KB，低于15kb的签名，我们的签名与SD问题相关，低于7KB，对于与RSD问题有关的签名。
The MPC-in-the-head introduced in [IKOS07] has established itself as an important paradigm to design efficient digital signatures. It has been leveraged in the Picnic scheme [CDG+ 20] that reached the third round of the NIST PQC Standardization process. It has also been used in [Beu20] to introduce the Proof of Knowledge (PoK) with Helper paradigm. This construction permits to design shorter signatures but induces a non negligible performance overhead as it uses cut-and-choose. In this paper, we introduce the PoK leveraging structure paradigm along with its associated challenge space amplification technique. Our new approach to design PoK brings some improvements over the PoK with Helper one. Indeed, we show how one can substitute the Helper in these constructions by leveraging the underlying structure of the considered problem. This approach does not suffer from the performance overhead inherent to the PoK with Helper paradigm hence offers different trade-offs between security, signature sizes and performances. We also present four new post-quantum signature schemes. The first one is based on a new PoK with Helper for the Syndrome Decoding problem. It relies on ideas from [BGKM22] and [FJR21] and improve the latter using a new technique that can be seen as performing some cut-and-choose with a meet in the middle approach. The three other signatures are based on our new PoK leveraging structure approach and as such illustrate its versatility. We provide new PoK related to the Permuted Kernel Problem (PKP), Syndrome Decoding (SD) problem and Rank Syndrome Decoding (RSD) problem. In practice, these PoK lead to comparable or shorter signatures than existing ones. Indeed, considering (public key + signature), we get sizes below 9kB for our signature related to the PKP problem, below 15kB for our signature related to the SD problem and below 7kB for our signature related to the RSD problem.
