Saya telah membaca di beberapa makalah bahwa keberadaan fungsi satu arah diyakini secara luas. Adakah yang bisa menjelaskan mengapa ini terjadi? Argumen apa yang kita miliki untuk mendukung keberadaan fungsi satu arah?
25
Saya telah membaca di beberapa makalah bahwa keberadaan fungsi satu arah diyakini secara luas. Adakah yang bisa menjelaskan mengapa ini terjadi? Argumen apa yang kita miliki untuk mendukung keberadaan fungsi satu arah?
Jawaban:
Berikut adalah argumen bahwa fungsi satu arah harus sulit dibalik. Misalkan ada kelas masalah 3-SAT dengan solusi yang ditanam yang sulit untuk dipecahkan. Pertimbangkan peta berikut:
di mana adalah setiap string bit, adalah string bit (Anda bisa menggunakannya untuk menabur generator angka acak, atau Anda dapat meminta sebanyak bit acak yang Anda butuhkan) dan adalah masalah -SAT dengan sebagai solusi yang ditanam, di mana generator angka acak menentukan dengan tepat masalah -SAT yang Anda pilih. Untuk membalikkan fungsi satu arah ini, Anda perlu menyelesaikan masalah -SAT dengan solusi yang ditanam.r s k x k kx r s k x k k
Argumen ini menunjukkan bahwa membalik fungsi satu arah sama sulitnya dengan memecahkan masalah -SAT dengan solusi yang ditanam. Dan karena -SAT adalah masalah NP-complete, jika Anda bisa mencari cara untuk membangun instances keras dengan solusi yang ditanam untuk setiap masalah NP, Anda dapat menanam solusi dalam formula -SAT.k kk k k
Belum terbukti bahwa mungkin untuk menemukan kelas masalah NP-lengkap dengan solusi yang ditanam yang sama sulitnya dengan masalah NP-lengkap sewenang-wenang (dan bahkan jika ini benar, itu akan sangat sulit untuk dibuktikan) , tapi orang pasti tahu cara menanam solusi dalam masalah -SAT dengan cara yang saat ini tidak ada yang tahu bagaimana menyelesaikannya.k
TAMBAH: Saya sekarang menyadari bahwa koneksi ini sudah diberikan (lebih terinci) di Abadi, Allender, Broder, Feigenbaum, dan Hemachandra ; mereka menunjukkan bahwa fungsi satu arah dapat memberikan contoh keras SAT yang dipecahkan, dan sebaliknya.
Menempatkannya dalam bahasa yang lebih informal, tidak adanya fungsi satu arah menunjukkan bahwa teka-teki yang benar-benar keras tidak dapat ada. Jika ada jenis puzzle di mana seseorang dapat membuat puzzle dan solusinya secara algoritmik, maka ada juga algoritma waktu polinomial untuk menemukan solusi bagi puzzle tersebut. Ini tampaknya sangat kontra-intuitif bagi saya. Tentu saja, celah polinom bisa ada; mungkin itu terjadi bahwa jika membuat puzzle mengambil langkah , maka memecahkannya mungkin mengambil langkah . Namun, intuisi saya mengatakan bahwa harus ada kesenjangan superpolinomial. O ( n 3 )n O(n3)
sumber
Saya akan memberikan jawaban singkat: Adanya masalah yang tampaknya sulit, seperti FAKTOR atau LOG DISKRET membuat ahli teori percaya bahwa OWF ada. Secara khusus, mereka mencoba selama beberapa dekade (sejak 1970-an) untuk menemukan algoritma (waktu polinomial-waktu) yang efisien untuk masalah-masalah seperti itu, tetapi tidak ada upaya yang berhasil. Alasan ini sangat mirip dengan mengapa kebanyakan peneliti percaya bahwa P ≠ NP.
sumber
Argumen Sasho bergantung pada masalah P = NP abadi yang saat ini tidak ada konsensus.
Namun, jika kita mengikuti kriptanalisis C. Shannon dari pad sekali pakai, dideklasifikasi pada tahun 1947, yaitu: tidak ada algoritma enkripsi yang aman secara matematis selain pad sekali pakai. Argumennya didasarkan pada gagasan bahwa, jika kita memiliki urutan angka yang benar-benar acak dan untuk beberapa urutan untuk mengenkripsi, , kami mengenkripsi sebagai berikut :r1,r2,r3,…,rn s1,s2,s3,…,sn
Jika urutannya benar-benar acak, kami akan mencoba untuk menghitung dan hasilnya kemudian adalah bahwa semua urutan dapat dilengkapi.f−1(ri,si)
Kita bisa meniru hasil Shannon untuk fungsi satu arah.
Fungsinya adalah peta dan kebalikannya fungsi adalah peta .f:Z/nZ×Z/nZ→Z/nZ f:Z/nZ→Z/nZ×Z/nZ
Tangkapannya adalah bahwa kita tidak tahu apakah ada angka yang benar-benar acak karena pertanyaannya setara dengan komentar Einstein tentang "Tuhan tidak memainkan dadu".
Namun, untuk semua tujuan, generator bilangan acak berdasarkan proses fisik dianggap cukup acak oleh para ahli.
Ini mengatakan, saat kita mencoba untuk membalikkan , yaitu, angka acak tidak lagi rahasia, pembalikan itu sepele.(ci,ri)
Selain itu, fungsi satu arah ini tidak memiliki sifat yang bagus dari fungsi hashing yang paling aman secara kriptografis seperti resistensi tabrakan. Selain itu, kami memiliki situasi yang . Ini berarti bahwa nilai yang sama mendapat hash ke dua nilai yang berbeda. Dan adalah hal biasa.s k f ( r i , s i ) = f ( r j , s j )f(ri,sk)≠f(rj,sk) sk f(ri,si)=f(rj,sj)
sumber
Apakah semudah menyarankan misalnya fungsi Sine?
Karena untuk input dan output yang diberikan input dapat ditingkatkan atau diturunkan 360 derajat (atau 2 pi jika Anda ke radian) itu banyak-ke-satu, jadi Anda tidak pernah bisa yakin input mana yang Anda miliki?
Katakan padaku jika aku salah paham pertanyaannya.
sumber