Apakah "Fungsi Satu Arah" memiliki aplikasi di luar crypto?

Fungsi adalah satu arah jika f dapat dihitung dengan algoritma waktu polinomial, tetapi untuk setiap algoritma waktu polinomial acak A ,$f \colon \{0, 1\}^* \to \{0, 1\}^*$$f$$A$

$\Pr[f(A(f(x))) = f(x)] < 1/p(n)$

untuk setiap polinomial dan cukup besar n , dengan anggapan bahwa x dipilih secara seragam dari { 0 , 1 } n . Probabilitas diambil alih pilihan x dan keacakan A .$p(n)$$n$$x$$\{ 0, 1 \}^n$$x$$A$

Jadi ... apakah "Fungsi Satu Arah" memiliki aplikasi di luar kriptografi? Jika ya, apakah mereka?

Fungsi satu arah muncul secara krusial dalam hasil bukti alam Razborov-Rudich. Saya tidak akan menganggap batas bawah sirkuit sebagai bagian dari "kriptografi", jadi mungkin ini sesuai dengan kriteria Anda.

Fungsi satu arah juga ditampilkan dalam beberapa diskusi di sekitar dugaan isomorfisme Berman-Hartmanis . Joseph dan Young menduga bahwa jika fungsi satu arah ada maka dugaan isomorfisme gagal (satu arah melawan musuh deterministik, bukan yang probabilistik, tetapi mudah-mudahan itu cukup dekat untuk keperluan pertanyaan ini). John Rogers memberikan dunia relativized di mana dugaan Joseph-Young gagal (yaitu, di mana fungsi satu arah ada tetapi dugaan isomorfisme berlaku). Tapi sejauh yang saya tahu dugaan JY masih merupakan salah satu bukti teknis utama yang membuat orang berpikir bahwa dugaan Isomorfisme itu salah (jika mereka memang berpikir demikian).

Inti dari gagasan Joseph and Young adalah bahwa jika adalah fungsi satu arah, maka f ( S A T ) adalah N P -complete tetapi "tidak boleh" bersifat isomorfik untuk SAT.$f$$f(SAT)$$NP$

Ya, tabel hash atau peta hash membutuhkan fungsi satu arah. Deteksi duplikat (lihat ini dan ini ) dapat dilakukan dengan sangat efisien menggunakan fungsi satu arah. Kedua kasus membutuhkan fungsi "baik" (dengan kemungkinan tabrakan rendah) sementara kekuatan kriptografi biasanya tidak diperlukan .

Ada banyak hasil "kekerasan kriptografi" (hanya Google frase ini) untuk masalah belajar. Ini adalah hasil kekerasan dengan asumsi bahwa fungsi satu arah ada.

Fungsi satu arah memiliki aplikasi di Kolmogorov Complexity:

$x$$y$

$K^q(x, y) = K^q(x) + K^q(y|x) + O(\log n)$$q$

Jika fungsi satu arah ada, maka simetri informasi waktu yang dibatasi polinomial adalah salah.

L. Longpre dan S. Mocas. Simetri informasi dan fungsi satu arah. Pemrosesan informasi Letters, 46 (2): 95 {100, 1993

L. Longpre dan O. Watanabe. Tentang simetri informasi dan polinomial time invvertibility. Informasi dan Komputasi, 121 (1): 14 {22, 1995