On Zero-Knowledge Identification Based on Q-ary Syndrome Decoding

Abstract

Cayrel.et.al at SAC 2010 proposed a zero-knowledge identification scheme based on syndrome decoding of q-ary codes. It is a 5-pass scheme with soundness error q/2(q-1). We propose an alternative to this scheme by generalizing (binary) Stern zero-knowledge identification from CRYPTO 1993 directly to q-ary setting. Our proposal is a 3-pass scheme with soundness error 2/3. We show that it is superior to Cayrel et al scheme in terms of communication cost for the case q = {3, 4}. A possible application for q-ary code-based identification schemes with small q is a proof of plaintext knowledge for code-based public key encryption.