The 1993 Stern authentication protocol is a code-based zero-knowledge protocol with cheating probability equal to 2/3 based on the syndrome decoding problem which permits to obtain a proof of knowledge of a small weight vector. This protocol was improved a few years later by V\'eron, who proposed a variation of the scheme based on the general syndrome decoding problem which leads to better results in term of communication. A few years later, the AGS protocol introduced a variation of the V\'eron protocol based on quasi-cyclic matrices. The AGS protocol permits to obtain an asymptotic cheating probability of 1/2 and a strong improvement in term of communications. In the present paper we propose two new contributions. First, a Quasi-Cyclic Stern proof of knowledge construction which constitutes an adaptation of the AGS scheme in a syndrome decoding context. The main interest of this adaptation is that at the difference of the regular (non quasi-cyclic) case, the Quasi-Cyclic Stern protocol is better in terms of communication than its V\'eron counterpart (the AGS protocol, which can be seen as a Quasi-Cyclic V\'eron protocol). The difference comes from the fact that a seed related optimization is better for QC-Stern than for QC-V\'eron. Secondly, we also propose a general new optimization to handle random seeds in this type of protocol. Overall, the two new optimizations we propose permit to gain about 17.5% in the length of communication compared to the previous best approach for this type of protocols. Such optimizations are of great matter in the ongoing context where a new signature call for proposals has been announced by the NIST and for which such zero-knowledge approaches are a real alternative, as it was shown in the first signature call for proposals of the NIST.
翻译:1993 Stern 认证协议是一种基于代码的零知识协议,欺骗概率等于2/3,其依据是综合解码问题,它允许获得对小量矢量的知识证明。几年后,V\'eron改进了这一协议。V\'eron提议根据总体综合解码问题对该计划进行修改,从而在通信方面产生更好的效果。几年后,AGS协议引入了基于准周期矩阵的V\'eron协议的变异。AGS协议允许获得一次/2的失灵欺骗概率和通信期的大幅改进。在本文件中,我们提出了两项新的贡献。首先,V\'eron 协议的变异性证明构成AGS系统在综合解码背景下的变换。这一调整的主要利益是,常规(非准周期)案的变异性(Qasi-C)处理的变异性协议在通信中比V\'eron的变异性概率的变异性(AGS-Q-Qrent 协议的变异性协议)要好得多。这个变异性协议的变异性协议的变种在现在的变异性协议中展示了。