Ressource pédagogique : 5.5. Stern’s Zero-Knowledge Identification Scheme

Informations pratiques sur cette ressource

Description de la ressource pédagogique

Description (résumé)

In this session, we are going to have a look at Stern’s Zero-Knowledge Identification Scheme. So, what is a Zero-Knowledge Identification Scheme? An identification scheme allows a prover to prove his identity to a verifier. And the Zero-Knowledge Protocol is an interactive protocol where one proves the knowledge of something, without revealing any information on this knowledge, on this element. So, Stern’s Identification Scheme was invented in 1993 and security relies on the syndrome decoding problem. Contrary to McEliece or the CFS signature, it uses a random binary matrix which means that there is no trap inside it. Like other identification schemes, it can also be converted into a signature scheme. The system parameters are a public binary matrix H of size r * n and a weight w. Each user in the system that wants to be able to prove his identity picks a secret binary vector e of length n and weight w, which can be seen as an error pattern, and computes the syndrome of this vector e. This syndrome is published and is a kind of a public key. The identification protocol: the verifier knows the public key s and the prover has to prove that he knows e such that s = H * e. And this has to be done without leaving any information about e. The identification scheme involves a prover and a verifier. The prover picks a random vector y and a random permutation of the elements from 1 to n, ?. Then, it computes three commitments c0, c1, c2 which are hashes are different elements that he knows, depending of ?, y and e. And he sends these commitments to the verifier who stores them. Then, the verifier picks a random value in 0, 1 or 2 and sends it to the prover. Depending on the value of b, the answer of the prover will be different. If b = 0, the prover will reveal elements that allow the verifier to verify commitments c1 and c2. These elements are the permutation ?(y) and the permutation of the error vector ?(e).

"Domaine(s)" et indice(s) Dewey

• Analyse numérique (518)
• Théorie de l'information (003.54)
• données dans les systèmes informatiques (005.7)
• cryptographie (652.8)
• Mathématiques (510)

Thème(s)