Fungsi satu arah sehubungan dengan berbagai batasan sumber daya

13

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 ( )?NTIME (n)

Saya baik-baik saja dengan kekerasan invertiblity kasus terburuk sehubungan dengan batas sumber daya di atas.

Mohammad Al-Turkistany
sumber
Pernahkah Anda melihat eprint.iacr.org/2013/001.pdf ? Topik makalah ini mungkin relevan atau tidak relevan bagi Anda, tetapi teknik-teknik dalam makalah ini (atau bahkan kutipan) dapat mengarah pada sesuatu yang bermanfaat.
Daniel Apon
Abstrak tidak membantu tetapi terima kasih atas bantuan Anda.
Mohammad Al-Turkistany
Oh well - saya harap jawaban baru itu. :)
Daniel Apon
Yap, Ya :)
Mohammad Al-Turkistany

Jawaban:

11

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(Sebuah1,...,Sebuahn,S): =(Sebuah1,...,Sebuahn,sayaSSebuahsayamod2n)

Manu
sumber
Terima kasih Emanuele. Ini menjawab kasus Logspace. Hanya untuk kelengkapan, Bisakah Anda daftar beberapa fungsi dalam jawaban Anda.
Mohammad Al-Turkistany
Saya telah menambahkan dua contoh.
Manu
Terima kasih banyak, Emanuele. Apakah ada wawasan yang menjelaskan kesulitan membalik fungsi-fungsi tersebut (dengan algoritma LOGSPACE)?
Mohammad Al-Turkistany