Wo ist der Fehler in der Methode von Blum-Feldman-Micali?

Blum, Micali und Feldman (BFM) haben ein neues (kryptografisches) Modell vorgestellt, bei dem alle Parteien (ehrlich oder kontrovers) Zugriff auf eine Zeichenfolge haben. Es wird davon ausgegangen, dass die Zeichenfolge gemäß einer Verteilung (normalerweise einer gleichmäßigen Verteilung) von einer vertrauenswürdigen Partei ausgewählt wird. Es wird als Referenzzeichenfolge bezeichnet , und das Modell wird treffend als CSR-Modell ( Common Reference String ) bezeichnet.

Das Modell ermöglicht es uns, viele interessante interaktive Protokolle nicht interaktiv auszuführen und Abfragen durch Bits aus der Referenzzeichenfolge zu ersetzen. Insbesondere Zero-Knowledge - Beweise für jede NP Sprache können nicht interaktiv durchgeführt werden, was zu dem Begriff des nicht-interaktiven Zero-Knowledge (NIZK).

NIZK bietet eine Vielzahl von Anwendungen, beispielsweise eine Methode zur Realisierung von Kryptosystemen mit öffentlichem Schlüssel, die vor (adaptiven) Angriffen mit Chiffretext geschützt sind .

BFM hat zuerst die Existenz einer Einzelsatzversion von NIZK für jede NP- Sprache bewiesen ; das heißt, wenn eine Referenzzeichenfolge und eine Sprache , kann man nur einen einzigen Satz der Form beweisen . Außerdem ist die Länge des Satzes in. Wenn der Prüfer versucht, einige Teile von in späteren Beweisen wiederzuverwenden , besteht die Gefahr von Wissenslecks (und der Beweis ist nicht mehr NIZK).$\rho$$L \in \bf{NP}$$x \in L$$|\rho|$$\rho$

Um dies zu beheben, verwendete BFM eine Multisatzversion, die auf dem Einzelsatz NIZK basiert. Zu diesem Zweck verwendeten sie einen Pseudozufallsgenerator, um zu erweitern , und verwendeten dann die erweiterten Bits. Es gibt noch einige andere Details, aber ich werde nicht näher darauf eingehen.$\rho$

Feige, Lapidot und Shamir (in der ersten Fußnote auf der ersten Seite ihres Papiers) erklärten:

Die in BFM vorgeschlagene Methode zur Überwindung dieser Schwierigkeit erwies sich als mangelhaft.

(Die Schwierigkeit bezieht sich eher auf das Erhalten von Beweisen mit mehreren Theoremen als auf Beweise mit einem einzigen Theorem.)

Wo liegt der BFM-Mangel?

Ich habe die Details ihres fehlerhaften Protokolls nicht gelesen, aber ich habe mehrmals davon gehört. Mein Eindruck war, dass ihr Fehler darin lag, wie sie das PRG-Saatgut verwendeten. In ihrem Protokoll wird der Startwert des Pseudozufallsgenerators (PRG) in die öffentliche gemeinsame Referenzzeichenfolge eingefügt, und sie versuchen zu argumentieren, dass die PRG-Sicherheit eine statistische Eigenschaft der PRG-Ausgabe erzwingt, die auch bei einem bekannten Startwert erhalten bleibt. Es ist zwar möglich, dies auf vernünftige Weise zu tun (die Unterschriftenschemata von Hohenberger und Waters hier und hier fallen mir ein), aber in ihrer Argumentation ist etwas schief gelaufen.