Code-based signatures from new proofs of knowledge for the syndrome decoding problem

作     者：Bidoux, Loic Gaborit, Philippe Kulkarni, Mukul Mateu, Victor 

作者机构：Technol Innovat Inst Abu Dhabi U Arab Emirates Univ Limoges Limoges France 

出 版 物：《DESIGNS CODES AND CRYPTOGRAPHY》 (设计、编码与密码学)

年 卷 期：2023年第91卷第2期

页      面：497-544页

核心收录：

学科分类：07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

主　　题：Code-based cryptography Signature Proof of knowledge 

摘      要：In this paper, we study code-based signatures constructed from Proofs of Knowledge (PoK). This line of work can be traced back to Stern who introduced the first efficient PoK for the syndrome decoding problem in 1993 (Stern in A new identification scheme based on syndrome decoding. In: International cryptology conference (CRYPTO), 1993). Afterwards, 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 types of optimizations which are compatible with a given protocol. In particular, optimizations related to the possibility of using random seeds instead of long vectors have a great impact on the final signature length. Over the years, different variations were proposed to improve the Stern scheme such as the Veron scheme (with public key as a noisy codeword rather than a syndrome) (Veron in Appl Algebra Eng Commun Comput 8(1):57-69, 1997), the AGS scheme which is a 5-pass protocol with soundness error asymptotically equal to 1/2 (Aguilar et al. in A new zero-knowledge code based identification scheme with reduced communication. In: IEEE information theory workshop, 2011) and more recently the FJR approach which permits to decrease the soundness probability to 1/N but induces a performance overhead (Feneuil et al. in Shared permutation for syndrome decoding: new zero-knowledge protocol and code-based signature. Cryptology ePrint archive, report 2021/1576, 2021). 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. For instance, depending on the application one may prefer a 30% shorter signature at the cost of a ten times slower implementation rather than a longer signature but a faster implementation. The recent approaches which increase the cost of the implementation open the door to man