Quasi-Cyclic Stern Proof of Knowledge

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.