Konsekuensi OWF untuk Kompleksitas

Sudah diketahui bahwa keberadaan fungsi satu arah diperlukan dan cukup untuk banyak kriptografi (tanda tangan digital, generator pseudorandom, enkripsi kunci pribadi, dll.). Pertanyaan saya adalah: Apa konsekuensi teori-kompleksitas dari keberadaan fungsi satu arah? Misalnya, OWF menyiratkan bahwa , , dan . Apakah ada konsekuensi lain yang diketahui? Secara khusus, apakah OWF menyiratkan bahwa hierarki polinom tidak terbatas? $\mathsf{NP}\ne\mathsf{P}$ $\mathsf{BPP}=\mathsf{P}$ $\mathsf{CZK}=\mathsf{IP}$

Saya berharap untuk lebih memahami hubungan antara kasus terburuk dan kekerasan rata-rata. Saya juga tertarik dengan hasil yang terjadi sebaliknya (yaitu kompleksitas-teori hasil yang akan menyiratkan OWF).

cc.complexity-theory reference-request complexity-classes cr.crypto-security one-way-function Thomas
sumber

Sudahkah Anda memeriksa literatur tentang dunia Impagliazzo?

Kaveh

@ MohammadAl-Turkistany jadi menyiratkan . Namun itu tidak mengesampingkan keruntuhan: itu masih konsisten dengan .

P \neq N P

$\mathsf{P} \neq \mathsf{NP}$

P \neq P H

$\mathsf{P} \neq \mathsf{PH}$

N P = P H

$\mathsf{NP} = \mathsf{PH}$

Sasho Nikolov

Thomas, ada beberapa lowerbound kriptografis untuk pembelajaran PAC yang efisien. Saya percaya mereka diisyaratkan dalam makalah lima dunia Impagliazzo

Sasho Nikolov

Saya tidak berpikir keberadaan OWF (sesuai dengan definisi standar mereka) menyiratkan . Untuk derandomisasi semacam itu, kita membutuhkan generator pseudorandom dengan bentangan eksponensial dan OWF tidak cocok untuk tujuan tersebut.

P = B P P

$P=BPP$

Mahdi Cheraghchi

@MarzioDeBiasi: jika OWF ada untuk jenis "kompleksitas struktural" dari OWFs (fungsi komputable injeksi waktu-poli tanpa invers waktu-poli). Jenis OWF yang diperlukan untuk kripto, seperti dalam pertanyaan, tampak sedikit lebih kuat (membutuhkan non-invertibilitas oleh musuh secara acak atau tidak seragam pada input kasus rata-rata).

P \neq U P

$P \neq UP$

Joshua Grochow

Jawaban:

Ini adalah respons yang terlambat.

Pertama, untuk memperbaiki apa yang Anda tulis: pseudorandomness Kriptografi (yang diperoleh dari OWF) tidak memiliki cukup peregangan untuk derandomisasi kelas kompleksitas komputasi yang didefinisikan secara alami. Dalam sebuah makalah lama (awal tahun 80-an) Andrew Yao menunjukkan derandomisasi waktu subeksponensial untuk RP dll menggunakan objek-objek ini (btw, ini langsung), tetapi tidak ada derandomisasi yang lebih kuat yang diketahui. Perhatikan, bahwa dalam hal menipu kekuatan, kriptografi PRG lebih kuat daripada yang Anda butuhkan untuk derandomisasi tetapi pada saat yang sama dalam hal peregangannya lebih lemah daripada analog kompleksitas-teoritikalnya yang khas (ini mengikuti urutan kuantifikasi dalam definisi PRGs).

Seperti yang Sasho Nikolov sebutkan ada banyak contoh dalam pembelajaran PAC. Lihatlah makalah yang sangat awal oleh Kearns dan Valiant tentang ketidakmungkinan belajar rumus dan automata (ikuti di google scholar referensi dari sana). Juga, ada konsekuensi dalam kompleksitas bukti melalui interpolasi - lihat juga karya-karya awal oleh Jan Krajicek dan Pavel Pudlak. Namun, saya tidak yakin apakah Anda menganggap ini sebagai implikasi teoretis kompleksitas (tapi saya tahu).

- Periklis

pengguna17164
sumber

Faktorisasi bilangan bulat secara luas dianggap sebagai kandidat terbaik untuk fungsi satu arah dan itu ada dalam TFNP. Dari abstrak makalah ini, Apakah Hirarki Polinomial Runtuh jika Fungsi yang Tidak Terbalik? , ini memberikan hasil negatif yang relatif dengan membangun oracle di mana fungsi TFNP dapat dihitung secara efisien tetapi hierarki waktu polinomial tidak terbatas. Namun, hasilnya tidak persis apa yang Anda cari.

Mohammad Al-Turkistany
sumber