A new zero-knowledge code based identification scheme with reduced\n communication

Abstract

In this paper we present a new 5-pass identification scheme with asymptotic\ncheating probability 1/2 based on the syndrome decoding problem. Our protocol\nis related to the Stern identification scheme but has a reduced communication\ncost compared to previous code-based zero-knowledge schemes, moreover our\nscheme permits to obtain a very low size of public key and secret key. The\ncontribution of this paper is twofold, first we propose a variation on the\nStern authentication scheme which permits to decrease asymptotically the\ncheating probability to 1/2 rather than 2/3 (and very close to 1/2 in practice)\nbut with less communication. Our solution is based on deriving new challenges\nfrom the secret key through cyclic shifts of the initial public key syndrome; a\nnew proof of soundness for this case is given Secondly we propose a new way to\ndeal with hashed commitments in zero-knowledge schemes based on Stern's scheme,\nso that in terms of communication, on the average, only one hash value is sent\nrather than two or three. Overall our new scheme has the good features of\nhaving a zero-knowledge security proof based on well known hard problem of\ncoding theory, a small size of secret and public key (a few hundred bits), a\nsmall calculation complexity, for an overall communication cost of 19kb for\nauthentication (for a $2^{16}$ security) and a signature of size of 93kb\n(11.5kB) (for security $2^{80}$), an improvement of 40% compared to previous\nschemes based on coding theory.\n