Sur les preuves interactives et la connaissance zéro: un guide

Travail en commun avec Sebastian Gajek

Que pouvez-vous attendre de la lecture

  • Compréhension de base des propriétés des systèmes de preuve, y compris zéro connaissance, solidité et exhaustivité, et donc des propriétés fondamentales de zkSNARKs, zkSTARKs ou zkNIZKs
  • Le paradigme de la simulation, l’indiscernabilité informatique et l’extraction de témoins
  • Le protocole de Schnoor, y compris les preuves incontestables de solidité, de zéro connaissance et d’exhaustivité
Photo accréditée à Volkan Olmez
Les preuves interactives sont des concepts essentiels de la notion même de calcul vérifiable - un outil cryptographique puissant pour assurer l'intégrité de calcul des exécutions de contrats, programmes ou bases de données intelligents. Plus important encore, la théorie des preuves interactives ouvre la voie à des preuves non interactives à zéro connaissance (NIZK), à des arguments de connaissance succincts et non interactifs (SNARK) ou à des arguments de connaissance transparents succincts (STARK). Dans cet article, nous décrivons la théorie fondamentale sur laquelle reposent les systèmes de preuve interactifs et espérons faciliter l’entrée des nouveaux venus dans le domaine très excitant et prometteur des SNARK et des STARK.

1. Introduction

Les systèmes de preuve ont récemment suscité un vif intérêt dans le contexte de l'évaluation de l'intégrité du calcul. Par exemple, ils peuvent aider à mettre en place un auditeur «cryptographique» pour certifier qu'une fonction mathématique, telle qu'une requête de recherche sur une base de données, a bien été calculée, ce qui implique l'exactitude de la sortie à la lumière d'un propriétaire de base de données potentiellement malveillant. La connaissance zéro est une propriété merveilleuse des systèmes de preuve pour garantir la confidentialité du calcul. Il permet de vérifier le calcul sur le jeu de données sans révéler aucune information partielle sur les données. Dans ce contexte, les systèmes à connaissance zéro trouvent des applications apportées dans des domaines sensibles à la confidentialité, tels que l'identification anonyme, les requêtes d'appartenance à une base de données ou les paiements en chaîne.

1.1 Qu'est-ce qu'un système de preuve?

Dans la théorie de la complexité calculatoire, un système de preuve interactif est une machine abstraite qui modélise le calcul sous forme d'échange de messages entre deux parties. Les parties, connues sous les noms de prouveur P et de vérificateur V, interagissent en échangeant des messages afin de déterminer si une déclaration est correcte.

Le prouveur est tout-puissant et possède des ressources de calcul illimitées, mais ne peut être approuvé, alors que le vérificateur dispose d’une puissance de calcul limitée. Les messages sont envoyés entre le vérificateur et le prouveur jusqu'à ce que le vérificateur puisse valider ou falsifier une déclaration. Tous les systèmes de preuve interactifs ont deux propriétés principales:

Complétude: si l'affirmation est vraie, le vérificateur honnête (c'est-à-dire qui suit correctement le protocole) peut en être convaincu par un prouveur honnête.

Bien-fondé: si la déclaration est fausse, aucun vérificateur tricheur / malveillant ne pourra convaincre le vérificateur honnête que c'est vrai, sauf avec une probabilité négligeable.

En d'autres termes, la propriété de solidité affirme que la procédure de vérification de la preuve ne peut être trompée en acceptant de fausses déclarations. Ainsi, la justesse traduit la capacité du vérificateur à se protéger contre la conviction que de fausses déclarations (peu importe ce que fait le prouveur pour le duper). Par ailleurs, l’exhaustivité rend compte de la capacité d’un prouveur de convaincre le vérificateur de déclarations vraies (appartenant à un ensemble prédéterminé de déclarations vraies). Notez que les deux propriétés sont essentielles à la notion même de système de preuve.

1.2 Protection de la vie privée par la connaissance zéro

Les systèmes de preuve (interactifs) à connaissance nulle ont la propriété supplémentaire remarquable de ne rien produire au-delà de la validité de l'assertion. Notez cependant que la propriété n’a de sens que si le prouveur a des informations secrètes - en zk-jargon appelé témoin - et veut que le vérificateur n’apprenne aucune information partielle à ce sujet. Par conséquent, la troisième propriété magique des systèmes de preuve peut être résumée comme suit:

Connaissance zéro: si l'affirmation est vraie, aucun vérificateur de la fraude n'apprend rien de plus que ce fait.

Dans la littérature à connaissance zéro, il existe un exemple canonique pour expliquer la propriété. Dans cet exemple, il y a une grotte dont le chemin se divise en deux. Ces deux chemins sont reliés par une porte qui ne peut être ouverte qu'avec un mot secret. Une personne, appelée Alice, veut prouver à une autre personne, Bob, qu'elle connaît le mot secret sans le trahir. Pour cela, les deux parties se placent d'abord à l'entrée de la grotte. Ensuite, Alice entre et suit l'un des deux chemins - ce qui lui revient. Bob ne peut pas dire depuis l'entrée quel chemin Alice a choisi.

La caverne d'Ali Baba dans la connaissance zéro

Ensuite, Bob entre dans la grotte et court à la fourche. Il choisit l'un des deux chemins et l'appelle dans la grotte. La tâche d’Alice consiste à emprunter ce chemin qui mène à Bob. Si elle réussit, elle sera un peu plus près du but de prouver à Bob qu'elle connaît le mot secret.

Si Alice a choisi le chemin choisi par Bob, elle n'a pas besoin du mot secret. Seulement si elle choisit le chemin opposé, elle doit passer la porte pour emprunter le bon chemin. Cela signifie qu'une Alice malicieuse, qui ignore le mot secret, ne peut convaincre Bob qu'à 50% en une seule exécution de ce protocole. (C'est pourquoi Alice et Bob doivent répéter le protocole afin de réduire la probabilité d'erreur de cohérence.) Le protocole est une preuve de connaissance zéro car, peu importe le nombre de fois qu'Alice et Bob répètent le processus, Alice, si elle connaît le mot secret, sera toujours suivez le chemin choisi par Bob. Pendant ce temps, Bob n’apprend rien sur le secret [1].

1.3 L'application canonique: schémas d'identification

Les systèmes d'identification ont été l'une des premières applications des systèmes de preuve interactifs à zéro connaissance. Dans un schéma d'identification, une partie, appelée le prouveur Alice, a pour objectif de convaincre une autre partie, le vérificateur Bob, qu'il s'agit d'une partie en particulier. Ce processus d'authentification d'entité est un ingrédient permettant de fournir à la partie un service particulier, tel que l'accès aux derniers épisodes de Games of Thrones, car le fournisseur de contenu a identifié la partie en tant que membre premium. À cette fin, la partie est en possession d'un témoin secret, tel qu'une clé cryptographique ou un mot de passe, dont aucune autre partie, y compris le fournisseur de contenu, n'est au courant. Illustrons maintenant les trois propriétés de l’affaire en continu de Games of Thrones.

  • La complétude garantit que si Alice est un abonné premium, elle aura accès au contenu premium.
  • Solidité garantit qu'aucune autre partie ne peut prétendre être Alice et accéder au contenu premium.
  • Zero-Knowledge garantit qu'aucune autre partie, y compris le fournisseur de contenu, n'apprend le témoin secret et ne peut se faire passer pour Alice lors de futures identifications. La notion de connaissance zéro implique que la preuve d'identité est non transférable.

Au bas des schémas d'identification se trouve l'idée qu'Alice connait un secret (directement lié à son identité) et prouve à Bob la connaissance du secret. Pour empêcher un Bob malveillant de se faire passer pour Alice à l'avenir, attendez-vous du protocole que Bob n'apprenne aucune information partielle sur le secret d'Alice. Inversement, une partie imitant Alice ne doit pas produire de preuve valide ni accéder aux flux GoT.

2. Définitions formelles: le diable est dans les détails

Alors que les propriétés d'un système de preuve peuvent sembler intuitives, définir la complétude, la validité ou la connaissance nulle d'une manière rigoureuse et mathématiquement correcte a pris des décennies à la communauté des chercheurs. Afin de formaliser les propriétés, nous aurons besoin d'un modèle de calcul pour exprimer ce qu'est une interaction entre deux dispositifs informatiques. En cryptographie, le choix préféré est donné aux machines de Turing, du nom du «père» de l'informatique, Alan Turing.

2.1 Machine de Turing interactive

Une machine de Turing interactive (ITM) est une machine de Turing à plusieurs bandes (déterministe) (voir Figure 1). Les bandes sont une bande d'entrée en lecture seule, une bande aléatoire en lecture seule, une bande de travail en lecture et en écriture, une bande de sortie en écriture seule, une paire de bandes de communication et une bande de commutation en lecture et en écriture composée une seule cellule. Une bande de communication est en lecture seule et l'autre en écriture. Chaque ITM est associé à un seul bit, appelé son identité. Un ITM est dit actif dans une configuration si le contenu de sa bande de commutation est égal à l’identité de la machine. Sinon, la machine est dite au ralenti. Lorsqu’il est inactif, l’état de la machine, l’emplacement de ses têtes sur les différentes bandes et le contenu des bandes inscriptibles de l’ITM ne sont pas modifiés.

Figure 1: Illustration de deux machines de turing interactives.

Le contenu de la bande d'entrée est appelé entrée, le contenu de la bande aléatoire est appelé entrée aléatoire et le contenu de la bande de sortie à la fin est appelé sortie. Le contenu écrit sur la bande de communication en écriture seule pendant une période (de temps) au cours de laquelle la machine est active est appelé le message envoyé à cette période. De même, le contenu lu sur la bande de communication en lecture seule pendant une période active est appelé le message reçu (à cette période). (Sans perte de généralité, les mouvements de la machine sur les deux bandes de communication ne se font que dans un sens, par exemple de gauche à droite.)

Vous pouvez maintenant appeler la machine de turing interactive M interactive le prouveur P et M₂ le vérificateur V, respectivement. Comme les humains, les machines doivent comprendre un langage L pour pouvoir interagir correctement. Nous n’avons pas l’intention de plonger ici profondément dans la théorie des langues et sa complexité. Tout ce que nous devons savoir, c'est que la déclaration que le prouveur P veut prouver doit être codée - dans un sens très général - dans une langue particulière. Avec (x, w) ∈ L et (x, w) L, nous exprimons un énoncé de preuve correct / incorrect ou, en d'autres termes, la paire (x, w) est un membre du langage L. Typiquement, la valeur x est publique et connu à la fois du prouveur et du vérificateur et le paramètre w (appelé le témoin) est privé et connu du prouveur uniquement.

Formellement, un langage L est défini comme un ensemble (éventuellement infini) de chaînes sur un alphabet fini et est formé selon un ensemble spécifique de règles. Par exemple, une langue L sur l'alphabet Σ = {0, 1, 2, -, =} peut avoir la grammaire suivante:

  • Toute chaîne non vide qui ne contient pas “-” ou “=” et ne commence pas par “0” est en L
  • Une chaîne contenant "=" est dans L si et seulement s'il y a exactement un "=" et sépare deux chaînes valides de L

Selon ces règles, la chaîne “2–1 = 1” est en L, mais pas “= 21 = 0-”. Lors de la phase d'établissement d'un protocole de communication, les parties en interaction s'accordent souvent sur un langage spécifique avec des règles spécifiques.

2.2 Systèmes de preuve interactifs

Une paire de machines de turing interactives (P, V) est appelée un système de preuve interactif pour le langage L si la machine V est en temps polynomial et que les deux conditions suivantes sont remplies:

  • Complétude: Pour tous (x, w) dans le langage L, la probabilité qu’un prouveur P puisse convaincre le vérificateur honnête V est significative. C'est,
(X, w) ∈ L: Pr [P (x, w), V (x)⟩ = 1] ≤ 1 - négligé
  • Intégrité (version faible, également appelée Unforgeability): pour tous (x, w) et non dans le langage L, la probabilité qu’un vérificateur de fraude P puisse convaincre un vérificateur honnête V est négligeable. C'est,
(X, w) ∉ L: Pr [⟨P '(x), V (x) = 1] ≤ négligé
  • Caractère spécial (version forte ou connaissance de l'extractabilité des connaissances):

Pour chaque (x, w) du langage L, il existe un algorithme polynomial E (l'extracteur) tel que le témoin w puisse être extrait de conversations valides avec le prouveur P et le vérificateur V. C'est-à-dire

(X, w) ∈ L, E: Pr [E⟨P (x, w), V (x) = w] ≤ 1 - négligé

La solidité vient en deux saveurs. La notion plus faible de soundess capture un peu l’intuition d’une propriété d’impuabilité. En fait, les systèmes de preuve et les signatures numériques ont beaucoup en commun. Grâce à la transformation Fiat-Shamir, il est possible de transformer une classe de protocoles connus sous le nom de protocoles Sigma en signatures numériques. Nous discutons de la technique dans un prochain article. La notion la plus forte est souvent appelée propriété d'extraction de témoin. Les protocoles satisfaisant la propriété sont appelés preuves de connaissance. Essentiellement, l'existence de l'extracteur encadre de manière algorithmique l'idée de connaissance informatique. Supposons que le prouveur P connaisse le témoin w. Ensuite, elle doit avoir utilisé le témoin lors de l'exécution du protocole (et l'a donc codé d'une manière ou d'une autre dans les messages de protocole) pour réussir à convaincre le vérificateur. Supposons donc que nous ayons un ange magique, l'extracteur, surveillant l'arrière de P et attestant de l'utilisation du témoin dans l'exécution du protocole. Clairement, cela donnerait une preuve solide de la connaissance du témoin. Dans le monde informatique, les anges n'existent malheureusement pas. P et V sont plutôt des machines de Turing et l’extracteur E. Pour capturer l’intuition de «regarder le dos de P», nous laissons l’extracteur calculer le témoin à partir de l’observation de l’interaction du prouveur P et du vérificateur V. En d’autres termes, si vous pouvez extraire le témoin de P, il doit y avoir été. Ce qu'il faut souligner ici, c'est qu'une simple écoute passive de l'interaction ne laisse filtrer aucune information partielle sur le témoin. Sinon, le vérificateur V apprend le témoin w et le protocole ne satisfait pratiquement aucune forme de connaissance zéro. L'extracteur E (par opposition au vérificateur) a donc un pouvoir supplémentaire! Dans l'exemple à venir ci-dessous, nous verrons que la puissance supplémentaire est la capacité de rembobiner le prouveur P. Le rembobinage est une technique qui reflète l'idée de base des programmes: On peut exécuter un programme plusieurs fois (pensez à appeler une fonction) et afficher le résultat final. résultat déterministe, si l’on contrôle les bandes / entrées aléatoires du programme. Pour l’avenir, rembobiner le prouveur P (en particulier, exécuter le protocole de Schnorr à deux reprises tout en le rembobinant dans un état particulier avant la deuxième exécution) suffit déjà à rassembler toutes les informations pertinentes pour l’extraction de témoin. Notez à nouveau que pour que le protocole satisfasse à la connaissance zéro, le vérificateur doit manquer de cette puissance supplémentaire.

  • Connaissance zéro: Pour chaque (x, w) du langage L, il existe pour tous les vérificateurs un simulateur S tel qu'aucun différenciateur polynomial D ne puisse distinguer une exécution du protocole simulé de celle d'une interaction réelle entre le prouveur P et vérificateur V. C'est-à-dire,
(X, w) L, V S: Pr [D⟨P (x, w), V (x)⟩ = 1] - Pr [D⟨S (x) = 1] ≤ négl

Nous devons d’abord rappeler la notion même d’indiscernabilité informatique pour comprendre le mécanisme de simulation. L’indiscernabilité est un concept puissant dans de nombreux domaines de l’informatique. Il est formalisé par un algorithme décisionnel efficacement calculable, le différenciateur D, qui en entrée doit saisir une chaîne échantillonnée dans l'un des deux ensembles, en fonction de son choix. Considérons, pour faciliter l’exposition, l’expérience mentale suivante. Supposons qu'un homme et une machine simulant l'homme soient cachés derrière un rideau dans un théâtre et que le public interagisse avec l'un ou l'autre à travers le rideau. Après une longue conversation, si le public ne peut pas distinguer l'humain de la machine (disons que nous avions une décision à 50:50), nous conclurions que la machine est «aussi bonne que» ou «sonne / se comporte / se comporte comme» l'humain.

Considérons maintenant le cas où nous comparons l'interaction du prouveur P et du vérificateur V avec l'exécution qu'un simulateur S produit avec la mise en garde suivante. Dans l'interaction réelle entre le prouveur et le vérificateur, P utilise explicitement son témoin w alors que le simulateur S ne reçoit que l'information publique x. Malgré le désavantage informationnel, supposons que le simulateur produise une transcription qui "ressemble" à une interaction entre le prouveur et le vérificateur (voir la figure 2).

Figure 2: Illustration de la notion de connaissance zéro.

Ensuite, le transcript de protocole réel doit contenir autant d'informations que le transcript simulé. Notez que ça doit être comme ça. Sinon, les exécutions pouvaient être distinguées. Par construction, cependant, la transcription simulée est une connaissance zéro: elle ne laisse filtrer aucune information partielle sur le témoin w. En fait, le simulateur ne peut divulguer aucune information car il n’est pas en possession du témoin. La conclusion doit être que la transcription réelle du protocole ne contient aucune information sur le témoin, car la transcription simulée est indiscernable, elle est aussi bonne que la vraie. Par conséquent, le véritable protocole est la connaissance zéro.

3. Le protocole de Schnorr, aussi appelé le système de vérification de connaissances nulles «Honest Verifier Honest Verifier»

Une des preuves de connaissances les plus simples et les plus utilisées, la preuve de la connaissance d'un logarithme discret, est due à Claus P. Schnorr. C'était un mathématicien et cryptographe allemand. Son protocole a trois tours et est défini sur un groupe cyclique G d'ordre q avec le générateur g. Afin de prouver en connaissance zéro le langage L = {(x, w): x = gʷ} où le témoin w est l'exposant de journal discret difficile à calculer, le prouveur interagit avec le vérificateur, comme illustré à la figure 3.

3.1 Spécification du système de preuve

Figure 3: Protocole de Schnorr. Notez qu'il existe plusieurs variantes du protocole. Nous préférons choisir la version du protocole où le challenge e est échantillonné à partir de {0, .., q-1}.

Installer:

  • Le prouveur P a une entrée secrète w et une entrée publique x = gʷ.
  • Le vérificateur V n'a qu'une entrée publique x = gʷ.
  • P et V ont en commun les paramètres de groupe public g et q.

Protocole:

  1. Le prouveur P génère un élément de groupe aléatoire h et échantillonne un entier aléatoire r. Elle envoie la valeur aléatoire a = gʳ au vérificateur V.
  2. Le vérificateur V choisit une épreuve aléatoire e ∈ {0, .. q-1} et l’envoie au prouveur P.
  3. Prover P répond au défi avec la réponse z = r + ew.
  4. Le vérificateur V accepte la réponse (et est donc convaincu de la preuve), si et seulement si gᶻ est égal à axᵉ.

3.2 Analyse de sécurité

Nous analysons maintenant le système de preuve Schnorr et affirmons qu’il répond aux propriétés ci-dessus.

La complétude est montrée par une reformulation simple d'équivalence:

R, e: gᶻ = gʳ⁺ᵉʷ = gʳ (gʷ) = axᵉ

La figure 4 montre la validité spéciale en construisant l’extracteur E qui calcule le témoin correct w et rompt ainsi l’hypothèse du journal discret (c’est-à-dire qu’il est supposé être un problème de calcul difficile à calculer pour le témoin w donné x = gʷ), propriété de solidité faible. En d'autres termes, nous réduisons la validité du protocole au problème de journal discret à l'aide de l'extracteur E.

Figure 4: Illustration du déroulement de la simulation pendant la démonstration pour une solidité particulière.

Pour que l'extraction fonctionne, E exécute deux instances du prouveur, notées P et P *. Pendant la simulation, l'extracteur agit en tant que vérificateur V pour les deux instances et calcule le témoin à l'aide de la stratégie suivante:

  1. L'extracteur E alimente la première instance de prouveur P avec l'entrée publique x = gʷ (et les pièces aléatoires r pour paramétrer ses bandes aléatoires) et attend de recevoir le premier message de prouveur a = gʳ.
  2. L'extracteur E choisit un bit aléatoire e ∈ {0, .. q-1}, envoie e au prouveur P et attend la réponse z = r + ew.
  3. Maintenant, il rembobine le prouveur P à l’étape 2. (Techniquement, l’extracteur invoque une seconde instance de prouveur P * avec une entrée identique (x, r). Le fait que nous invoquons le prouveur avec le même caractère aléatoire r permet de s’assurer qu’il fait la même chose ) choix que P a fait pour le premier message a. Par conséquent, nous avons rembobiné P.)
  4. L’extracteur E choisit un autre e ’, l’envoie à P * et attend de recevoir la réponse z’ = r + e’w.
  5. Enfin, le témoin w est extrait en calculant les différences des paires défi-réponse.
(z-z ') / (e-e') = ((r + ew) - (r + e'w)) / (e-e ') = (e-e') / (e-e ') · W = w

Connaissance zéro: Un protocole est considéré comme une connaissance zéro si, pour tout vérificateur V, il existe un simulateur pouvant créer des conversations avec la même distribution que les conversations entre le prouveur et le vérificateur. Nous soulignons que le protocole de Schnorr (comme spécifié ci-dessus) n’est PAS une connaissance nulle. La raison réside dans l'impossibilité de construire un simulateur pour tous les vérificateurs: la simulation est un échec pour les vérificateurs malveillants avec des choix imprévisibles de message e. Cependant, pour que la simulation soit exécutée, le simulateur doit deviner le défi à l'avance. Compte tenu de l'espace d'échantillonnage exponentiel de e, les chances que cet événement se produise sont négligeables.

Le protocole de Schnorr répond toutefois à une notion plus faible de la vie privée appelée connaissance zéro du vérificateur honnête. Dans ce modèle, le vérificateur suit aveuglément l'exécution du protocole et ne s'écarte pas de la spécification de protocole ci-dessus. Avec cette simplification, le simulateur n'a plus besoin d'anticiper un comportement arbitraire et donc difficile à prévoir du vérificateur. Au lieu de cela, le simulateur peut maintenant simuler un choix aléatoire du message de défi e à l’avance, car, par hypothèse, un vérificateur honnête se comporterait exactement de la sorte. Il est même possible de prendre une valeur donnée e puis de générer une conversation où e apparaît comme un défi. En d’autres termes, le simulateur n’a pas à insister sur le choix de e lui-même, il peut prendre une valeur e en entrée. Cela renforce la simulation, car elle montre une connaissance nulle en présence de vérificateurs altérés de manière statique. Pour voir cela, nous construisons le simulateur S à partir de l'entrée publique x = gʷ de la manière suivante:

  1. Le simulateur S choisit z de manière uniforme et aléatoire et le défi que le vérificateur honnête V publiera.
  2. Le simulateur S calcule le message initial du prouveur sous la forme a = gᶻ / xᵉ. En outre, il simule le message de défi du vérificateur avec e.
  3. Enfin, le simulateur S simule le troisième message z.

En analysant la simulation, nous voyons que le simulateur S crée une interaction valide entre le prouveur et le vérificateur. Le vérificateur accepte les messages de protocole simulés car il affirme que

a · xᵉ = (gᶻ / xᵉ) · xᵉ = gᶻ

La simulation (a, e, z) a exactement la même distribution de probabilité que les conversations réelles entre le prouveur honnête et le vérificateur honnête. (Bien qu'il reste à le prouver.)

4. Conclusion et perspectives sur les protocoles Sigma et NIZK

On pourrait soutenir que la connaissance zéro du vérificateur honnête n’est pas une propriété utile, puisqu’il n’a pas de sens en pratique de supposer qu’un vérificateur est honnête. Le problème, cependant, est que les protocoles avec cette propriété plus faible peuvent souvent être utilisés comme blocs de construction dans des constructions qui sont effectivement protégées contre la fraude active, comme nous le verrons. Les protocoles qui ont la même structure en trois mouvements (engagement, défi, réponse), comme le protocole de Schnorr, sont appelés protocoles Σ. Des protocoles Sigma efficaces existent pour prouver diverses déclarations, telles que celles relatives aux logarithmes discrets. En outre, grâce à la transformation Fiat-Shamir, ils peuvent être efficacement transformés en preuves non interactives de connaissances sans connaissances (NIZK).

Nous prévoyons d’écrire sur le Sigma-Protocols, la transformation de Fiat-Shamir, avec quelques exemples concrets de constructions NIZK dans le prochain article. Restez à l'écoute!

Lectures complémentaires

La théorie des systèmes de preuve interactifs est de loin plus élaborée que ce que nous avons traité dans cet article. Voici une liste d'articles que nous vous recommandons d'approfondir dans ce domaine passionnant.

  • Claus P. Schnorr: Génération de signature efficace pour les cartes à puce. Journal of Cryptology, 4 (3): 239-252, 1991.
  • Mihir Bellare et Oded Goldreich: Sur la définition des preuves de la connaissance. Crypto’92.
  • Oded Goldreich: Fondements de la cryptographie - Outils de base. Cambridge University Press, 2001.