Di mana Cacat dalam Metode Blum-Feldman-Micali

Blum, Micali, dan Feldman (BFM) mengajukan model baru (kriptografi), di mana semua pihak (jujur ​​atau bermusuhan) memiliki akses ke beberapa string. Tali diasumsikan dipilih berdasarkan beberapa distribusi (biasanya, distribusi seragam) oleh pihak yang dipercaya. Ini disebut string referensi , dan model ini dinamai model string referensi umum (CSR).

Model ini memungkinkan kami untuk melakukan banyak protokol interaktif yang menarik secara non-interaktif , menggantikan permintaan dengan bit dari string referensi. Secara khusus, bukti nol-pengetahuan untuk bahasa NP dapat dilakukan secara non-interaktif, sehingga menimbulkan gagasan pengetahuan nol non-interaktif (NIZK).

NIZK memiliki banyak aplikasi, seperti menyediakan metode untuk mewujudkan cryptosystem kunci publik yang aman terhadap serangan ciphertext (adaptif) yang dipilih .

BFM pertama kali membuktikan adanya versi teorema tunggal NIZK untuk setiap bahasa NP ; yang, diberikan referensi tali dan bahasa L ∈ N P , satu dapat membuktikan hanya satu teorema tunggal bentuk x ∈ L . Selain itu, panjang teorema dibatasi pada | ρ | . Jika pepatah mencoba untuk menggunakan kembali beberapa bit ρ dalam bukti kemudian, ada bahaya kebocoran pengetahuan (dan bukti tidak akan lagi menjadi NIZK).$\rho$$L \in \bf{NP}$$x \in L$$|\rho|$$\rho$

Untuk mengatasinya, BFM menggunakan versi multi-teorema berdasarkan NIZK-teorema tunggal. Untuk tujuan ini, mereka menggunakan generator pseudo-acak untuk memperluas , dan kemudian menggunakan bit yang diperluas. Ada beberapa detail lain juga, tetapi saya tidak akan menggali.$\rho$

Feige, Lapidot, dan Shamir (dalam catatan kaki pertama pada halaman pertama makalah mereka) menyatakan:

Metode yang disarankan dalam BFM untuk mengatasi kesulitan ini ditemukan cacat.

( Kesulitan mengacu pada memperoleh bukti multi-teorema daripada yang satu-teorema.)

Di mana letak cacat BFM?

Saya belum membaca detail protokol mereka yang cacat, tetapi saya sudah mendengarnya beberapa kali. Kesan saya adalah bahwa kesalahan mereka adalah bagaimana mereka menggunakan benih PRG. Protokol mereka menempatkan pseudorandom generator (PRG) seed dalam string referensi umum, dan mereka berusaha untuk berargumen bahwa keamanan PRG memaksa beberapa properti statistik dari output PRG untuk bertahan bahkan dengan seed yang dikenal. Meskipun dimungkinkan untuk melakukan ini dengan cara yang sehat (skema tanda tangan Hohenberger dan Waters di sini dan di sini muncul dalam pikiran), ada yang salah dalam argumen mereka.