Zero-Knowledge Reparation of the Véron and AGS Code-based Identification Schemes

Designing code-based signatures is both an important and challenging problem. A standard way to tackle it consists to use the Fiat-Shamir heuristic along with an identification scheme that is required to be zero-knowledge. The authors of [1] have highlighted an issue within the zero-knowledge proof of the Veron identification scheme [2]. It turns out that the zero-knowledge proof of the AGS protocol [3] is impacted in a similar way. In this paper, we present a masking technique that solves the aforementioned issue without inducing any performance penalty. We introduce the Masked Veron and Masked AGS protocols that both leverage this masking technique and provide their zero-knowledge proofs. In addition, we present a new technique improving the performances of signatures built from code-based identification schemes subject to the attack described in [4]. The Masked Veron and Masked AGS protocols feature all the existing performance improvements from the literature.