Vidéo pédagogique

5.5. Stern’s Zero-Knowledge Identification Scheme

Réalisation : 5 mai 2015 Mise en ligne : 5 mai 2015
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
  • audio 1 audio 2 audio 3

In this session, we aregoing to have a look at Stern’s Zero-Knowledge Identification Scheme. So, what is aZero-Knowledge Identification Scheme? An identification schemeallows a prover to prove his identity to a verifier. And the Zero-KnowledgeProtocol is an interactive protocol where one provesthe knowledge of something, without revealing any informationon this knowledge, on this element. So, Stern’s IdentificationScheme was invented in 1993 and security relies on thesyndrome decoding problem. Contrary to McEliece orthe CFS signature, it uses a random binary matrix which meansthat there is no trap inside it. Like otheridentification schemes, it can also be converted into a signaturescheme. The system parameters are a public binary matrix Hof size r * n and a weight w. Each user in the systemthat wants to be able to prove his identity picks a secretbinary vector e of length n and weight w, which can beseen as an error pattern, and computes thesyndrome of this vector e. This syndrome is publishedand is a kind of a public key. The identificationprotocol: the verifier knows the public key s and the proverhas to prove that he knows e such that s = H * e. And this has to be done withoutleaving any information about e. The identification schemeinvolves a prover and a verifier. The prover picks arandom vector y and a random permutation of theelements from 1 to n, σ. Then, it computes threecommitments c0, c1, c2 which are hashes are different elements thathe knows, depending of σ, y and e. And he sends these commitmentsto the verifier who stores them. Then, the verifier picks arandom value in 0, 1 or 2 and sends it to the prover. Depending on the value of b, theanswer of the prover will be different. If b = 0, the prover willreveal elements that allow the verifier to verifycommitments c1 and c2. These elements are thepermutation σ(y) and the permutation of the error vector σ(e).

Langue :
Conditions d'utilisation
Ces ressources de cours sont, sauf mention contraire, diffusées sous Licence Creative Commons. L’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications à l’œuvre originale.
Citer cette ressource:
Inria. (2015, 5 mai). 5.5. Stern’s Zero-Knowledge Identification Scheme. [Vidéo]. Canal-U. (Consultée le 20 mai 2022)

Dans la même collection

Avec les mêmes intervenants

Sur le même thème