Gdzie jest usterka w metodzie Bluma-Feldmana-Micali

Blum, Micali i Feldman (BFM) przedstawiają nowy (kryptograficzny) model, w którym wszystkie strony (uczciwe lub przeciwne) mają dostęp do niektórych ciągów znaków. Zakłada się, że ciąg jest wybrany zgodnie z pewną dystrybucją (zwykle równomierną dystrybucją) przez zaufaną stronę. Nazywa się to ciągiem odniesienia , a model jest trafnie nazwany modelem wspólnego ciągu odniesienia (CSR).

Model pozwala nam wykonywać wiele interesujących interaktywnych protokołów w sposób nieinteraktywny , zastępując zapytania bitami z ciągu referencyjnego. W szczególności dowody zerowej wiedzy dla dowolnego języka NP mogą być przeprowadzane w sposób nieinteraktywny, co powoduje powstanie pojęcia nieinteraktywnej wiedzy zerowej (NIZK).

NIZK ma wiele aplikacji, takich jak zapewnienie metody realizacji kryptosystemów klucza publicznego zabezpieczonych przed (adaptacyjnymi) atakami wybranego tekstu zaszyfrowanego .

BFM po raz pierwszy udowodnił istnienie wersji NIZK o jednym twierdzeniu dla każdego języka NP ; to znaczy, biorąc pod uwagę ciąg odniesienia i język L ∈ N P , można wykazać tylko jednego twierdzenie postaci x ∈ L . Ponadto długość twierdzenia jest ograniczona | ρ | . Jeśli prover spróbuje ponownie wykorzystać fragmenty ρ w późniejszych dowodach, istnieje niebezpieczeństwo wycieku wiedzy (a dowodem nie będzie już NIZK).$\rho$$L \in \bf{NP}$$x \in L$$|\rho|$$\rho$

Aby temu zaradzić, BFM zastosował wersję z wieloma twierdzeniami opartymi na pojedynczym twierdzeniu NIZK. W tym celu użyli pseudolosowego generatora do rozwinięcia , a następnie użyli rozszerzonych bitów. Są też inne szczegóły, ale nie zamierzam się w to zagłębiać.$\rho$

Feige, Lapidot i Shamir (w pierwszym przypisie na pierwszej stronie swojego artykułu) stwierdzili:

Metoda zaproponowana w BFM w celu przezwyciężenia tej trudności okazała się wadliwa.

( Trudność dotyczy uzyskania dowodów na wiele twierdzeń, a nie na podstawie twierdzeń pojedynczych).

Gdzie leży wada BFM?

Nie przeczytałem szczegółów ich wadliwego protokołu, ale kilkakrotnie o nim słyszałem. Mam wrażenie, że ich błąd polegał na tym, jak użyli nasion PRG. Ich protokół umieszcza ziarno generatora pseudolosowego (PRG) w publicznym wspólnym ciągu referencyjnym i próbują argumentować, że zabezpieczenia PRG wymuszają utrzymanie pewnej statystycznej właściwości wyjścia PRG nawet przy znanym nasieniu. Chociaż można to zrobić w rozsądny sposób (przychodzą na myśl schematy Hohenbergera i Watersa tu i tutaj ), coś poszło nie tak w ich argumentacji.