Où est la faille dans la méthode de Blum-Feldman-Micali

Blum, Micali et Feldman (BFM) ont proposé un nouveau modèle (cryptographique), dans lequel toutes les parties (honnêtes ou contradictoires) ont accès à une chaîne. La chaîne est supposée être sélectionnée selon une certaine distribution (généralement une distribution uniforme) par une partie de confiance. Il est appelé la chaîne de référence , et le modèle est bien nommé le modèle de chaîne de référence commune (CSR).

Le modèle nous permet d'effectuer de nombreux protocoles interactifs intéressants de manière non interactive , en remplaçant les requêtes par des bits de la chaîne de référence. En particulier, les preuves de connaissance zéro pour tout langage NP peuvent être effectuées de manière non interactive, donnant naissance à la notion de connaissance zéro non interactive (NIZK).

NIZK a de nombreuses applications, telles que la fourniture d'une méthode pour réaliser des cryptosystèmes à clé publique protégés contre les attaques de texte chiffré choisi (adaptatif) .

BFM a d'abord prouvé l'existence d'une version à théorème unique de NIZK pour chaque langue NP ; qui est, selon une chaîne de référence et un langage L ∈ N P , on peut montrer qu'un seul théorème de la forme x ∈ L . De plus, la longueur du théorème est bornée dans | ρ | . Si le prouveur tente de réutiliser certains bits de ρ dans des preuves ultérieures, il y a un risque de fuite de connaissances (et la preuve ne sera plus NIZK).$\rho$$L \in \bf{NP}$$x \in L$$|\rho|$$\rho$

Pour y remédier, BFM a utilisé une version multi-théorème basée sur le seul théorème NIZK. À cette fin, ils ont utilisé un générateur pseudo-aléatoire pour développer , puis ont utilisé les bits développés. Il y a aussi d'autres détails, mais je ne vais pas creuser.$\rho$

Feige, Lapidot et Shamir (dans la première note de bas de page de la première page de leur article) ont déclaré:

La méthode suggérée dans BFM pour surmonter cette difficulté s'est révélée défectueuse.

(La difficulté consiste à obtenir des preuves multi-théorèmes plutôt que des preuves à théorème unique.)

Où se situe la faille BFM?

Je n'ai pas lu les détails de leur protocole défectueux, mais j'en ai entendu parler à plusieurs reprises. Mon impression était que leur erreur était dans la façon dont ils ont utilisé la graine PRG. Leur protocole place la graine du générateur pseudo-aléatoire (PRG) dans la chaîne de référence commune publique, et ils tentent de faire valoir que la sécurité PRG force une propriété statistique de la sortie PRG à tenir même avec une graine connue. Bien qu'il soit possible de le faire de manière saine (les schémas de signature de Hohenberger et Waters ici et ici viennent à l'esprit), quelque chose s'est mal passé dans leur argument.