Fungsi Satu Arah vs komitmen yang mengikat sempurna

10

Jika OWF ada, maka komitmen bit yang mengikat secara statistik adalah mungkin. [1]

Apakah diketahui bahwa jika OWF ada, maka komitmen bit yang mengikat dengan sempurna dimungkinkan?
Jika tidak, adakah pemisahan kotak hitam yang diketahui di antara mereka?


[1] http://en.wikipedia.org/wiki/Pseudorandom_generator_theorem dan
http://en.wikipedia.org/wiki/Commitment_scheme#Bit-commitment_from_a_pseudo-random_generator

Mohammad Al-Turkistany
sumber

Jawaban:

6

Dalam sebuah karya baru-baru ini dengan Rafael Pass, ditunjukkan bahwa tanpa asumsi kompleksitas ekstra dari Barak-Ong-Vadhan, komitmen noninteraktif tidak dapat didasarkan pada fungsi satu arah dengan cara kotak hitam. Bahkan, bahkan dengan asumsi-asumsi ekstra ini (ketika diformalkan sebagai semacam properti pemukul yang diasumsikan sebagai tambahan terhadap satu arah) masih ada pemisahan antara kotak hitam:

http://eprint.iacr.org/2012/523.pdf

(konstruksi Barak-Ong-Vadhan adalah non-kotak hitam).

Mohammad
sumber
3

Untuk jawaban positif untuk pertanyaan ini, di bawah beberapa asumsi kompleksitas-teoritik tambahan, lihat makalah "Derandomisasi dalam Kriptografi" oleh Barak, Ong, dan Vadhan.

pengguna686
sumber