论文标题
基于代码的签名来自新知识证明综合征解码问题
Code-based Signatures from New Proofs of Knowledge for the Syndrome Decoding Problem
论文作者
论文摘要
在本文中，我们研究了根据知识证明（POK）构建的基于代码的签名。这项工作可以追溯到Stern，后者在1993年引入了综合征解码问题的第一个有效的POK。之后，提出了不同的变化，以减少签名的大小。实际上，获得较小的签名大小取决于两个主要考虑因素的相互作用：（i）基础协议及其声音误差以及（ii）与给定协议兼容的优化类型。多年来，提出了不同的变体来改善诸如Veron方案（使用公共密钥A嘈杂的代码字，而不是综合征）的严格方案，AGS方案是一种5通用协议，其作弊概率在渐近上等于1/2，而最近允许FJR方法可以将作弊的可能性降低到1/N，但会降低1/N的作弊可能性。总体而言，签名的长度取决于：计划本身，可能的优化和实施成本之间的权衡。最近增加实施成本的方法为许多不同类型的权衡打开了大门。在本文中，我们提出了三个新计划和不同的权衡，这本身都很有趣，因为取决于潜在的未来优化，计划最终可能比另一个方案更有效。我们提出的所有计划都使用受信任的助手：第一个方案允许获得1/2的作弊概率，第二个方案允许降低1/N中的作弊概率，但采用与最近的FJR方案不同的方法，最后第三个方案提出了一个类似veron的FJR方案，公共密钥是一个noisy kepeew而不是Noisy Codeorord，而不是noisy syndrome。我们提供了一个广泛的比较表，其中列出了我们的计划与以前的比较表。
In this paper, we study code-based signatures constructed from Proof of Knowledge (PoK). This line of work can be traced back to Stern who introduces the first efficient PoK for the syndrome decoding problem in 1993. Afterward, different variations were proposed in order to reduce signature's size. In practice, obtaining a smaller signature size relies on the interaction of two main considerations: (i) the underlying protocol and its soundness error and (ii) the type of optimizations which are compatible with a given protocol. Over the years, different variations were proposed to improve the Stern scheme such as the Veron scheme (with public key a noisy codeword rather than a syndrome), the AGS scheme which is a 5-pass protocol with cheating probability asymptotically equal to 1/2 and more recently the FJR approach which permits to decrease the cheating probability to 1/N but induces a performance overhead. Overall the length of the signature depends on a trade-off between: the scheme in itself, the possible optimizations and the cost of the implementation. The recent approaches which increase the cost of the implementation opens the door to many different type of trade-offs. In this paper we propose three new schemes and different trade-offs, which are all interesting in themselves, since depending on potential future optimizations a scheme may eventually become more efficient than another. All the schemes we propose use a trusted helper: a first scheme permits to get a 1/2 cheating probability, a second scheme permits to decrease the cheating probability in 1/N but with a different approach than the recent FJR scheme and at last a third scheme propose a Veron-like adaptation of the FJR scheme in which the public key is a noisy codeword rather than a syndrome. We provide an extensive comparison table which lists various trade-offs between our schemes and previous ones.
