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.
翻译:在本文中,我们研究了根据知识证明(PoK)构建的基于代码的签名。这行工作可以追溯到Stern, Stern在1993年引入了第一个有效的综合解码问题PoK。之后,提出了不同的变通办法,以减少签名规模。在实践中,获得一个较小的签名规模取决于两个主要考虑因素的相互作用:(一) 基本的协议及其正确性差错,以及(二) 符合特定协议的优化类型。多年来,提出了不同的变通办法来改进斯特恩计划,例如Veron计划(公共钥匙是一个响亮的代码而不是一个综合的),AGS计划是一个五通制协议,其概率在瞬间等于1/2,而最近的FJR计划则可以减少。总体而言,各种交易期限取决于两者之间的权衡:方案本身、可能的优化和实施工作的成本。最近提出的增加执行成本的方法为许多不同的交易类型提供了一种不同的版本。在F2计划中,我们最终提出了三种新的交易计划,而后又提出了另一种不同的交易安排。在F2计划中,我们又提出了另一种不同的交易计划,在F计划中提出了一种新的选择。