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

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

2011-11-07

arxiv.org/abs/1111.1644v1

Computer Science

Cryptography and Security

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

A new zero-knowledge code based identification scheme with reduced communication does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A new zero-knowledge code based identification scheme with reduced communication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A new zero-knowledge code based identification scheme with reduced communication will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-692890