Secara informal, fungsi satu arah didefinisikan sehubungan dengan algoritma PTIME. Mereka dapat dihitung dalam waktu polinomial tetapi tidak dapat dibalik dalam waktu polinomial kasus-rata. Keberadaan fungsi tersebut merupakan masalah terbuka yang penting dalam ilmu komputer teoretis.
Saya tertarik pada fungsi satu arah (tidak harus untuk aplikasi kriptografi) yang ditentukan sehubungan dengan batas sumber daya yang berbeda. Batas sumber daya semacam itu bisa LOGSPACE atau nondeterminisme terbatas.
Apakah ada masalah kandidat (alami) yang bersifat satu arah sehubungan dengan algoritma LOGSPACE? Apakah ada masalah kandidat (alami) yang bersifat satu arah sehubungan dengan algoritma waktu linear nondeterministic ( )?
Saya baik-baik saja dengan kekerasan invertiblity kasus terburuk sehubungan dengan batas sumber daya di atas.
sumber
Jawaban:
Mengenai ruang-log: Beberapa fungsi kandidat satu arah dapat dihitung dalam ruang-log atau di bawah (dan seharusnya aman bahkan terhadap musuh waktu-ganda). Anda dapat menemukan beberapa petunjuk misalnya dalam Kriptografi di0 kertas NC 0 .
Dua contoh spesifik meliputi:
Penggandaan bilangan bulat (ada beberapa seluk-beluk untuk OWF standar, tetapi jika Anda hanya peduli pada kasus terburuk ini sudah cukup)
The Impagliazzo-Naor calon berdasarkan bagian-sum: .f( a1, . . . , an, S) : = ( a1, . . . , an, ∑saya ∈ SSebuahsayamod2n)
sumber