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

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