Permutasi Satu Arah Hingga dengan Domain Tak Terbatas

Biarkan menjadi permutasi. Perhatikan bahwa sementara bertindak pada domain tanpa batas, deskripsinya mungkin terbatas. Menurut deskripsi , maksud saya adalah program yang menjelaskan fungsionalitas . (Seperti dalam kompleksitas Kolmogorov.) Lihat penjelasan di bawah ini. π $\pi \colon \{0,1\}^* \to \{0,1\}^*$$\pi$$\pi$

Misalnya, fungsi NOT adalah salah satu permutasi tersebut:

fungsi TIDAK (x)
    Biarkan y = x
    Untuk i = 1 hingga | x |
        Balikkan sedikit y
    kembalikan y

$\pi_k(\cdot)$ , didefinisikan di bawah, adalah kasus lain:

fungsi pi_k (x)
    return x + k (mod 2 ^ | x |)

Pertanyaan saya adalah tentang kelas permutasi khusus, yang disebut permutasi satu arah . Secara informal, ini adalah permutasi yang mudah dihitung, tetapi sulit untuk dibalik (untuk mesin ). Keberadaan permutasi satu arah semata-mata adalah masalah terbuka lama dalam teori kriptografi dan kompleksitas, namun dalam sisanya, kita akan menganggap bahwa mereka ada.$\rm{BPP}$

Sebagai contoh dari permutasi satu arah terkira, seseorang dapat mempertimbangkan RSA : Misalkan menjadi bilangan bulat Blum , dan misalkan . Permutasi satu arah didefinisikan oleh: .$n = pq$$e = 65537$$\pi_n(x) = x^e \bmod n$

Perhatikan bahwa RSA didefinisikan atas domain hingga . Bahkan, untuk mendapatkan permutasi domain tak terbatas, kita harus mempertimbangkan keluarga permutasi RSA , di mana adalah himpunan bilangan bulat Blum yang tak terbatas. Perhatikan bahwa adalah deskripsi keluarga, dan menurut definisi, itu tidak terbatas.$\mathbb{Z}_n$$\{\pi_n\}_{n\in D}$$D$$D$

Pertanyaan saya adalah (dengan asumsi adanya permutasi satu arah):

Apakah ada permutasi deskripsi -jalan satu arah hingga domain tak terbatas ?

Jawabannya mungkin bervariasi: Itu bisa positif, negatif, atau terbuka (baik positif , atau negatif ).

Latar Belakang

Pertanyaan muncul ketika saya membaca makalah ASIACRYPT 2009 . Di sana, penulis secara implisit (dan dalam konteks beberapa bukti) mengasumsikan bahwa permutasi satu arah seperti itu ada.

Saya akan senang jika ini memang masalahnya, meskipun saya tidak dapat menemukan bukti.

Makalah tentang membangun 1-1 Fungsi Satu Arah , oleh Goldreich, Levin dan Nisan menunjukkan bagaimana membangun panjang yang mempertahankan fungsi 1-1 dengan domain tanpa batas dan deskripsi terbatas. Kekerasan dalam membalikkan fungsi didasarkan pada asumsi populer, seperti kekerasan membalikkan RSA atau menemukan Logaritma Diskrit.

Konstruksi mereka adalah twist dari ide langsung mengkonversi keluarga, , dari fungsi satu arah menjadi fungsi satu arah dengan menetapkan mana adalah keacakan yang digunakan untuk memilih indeks dan adalah keacakan yang digunakan untuk memilih input (diberi indeks ).$\{f_i\}_i$$f(r,s) = f_i(x)$$r$$i$$s$$x$$i$

Masalah dengan ide di atas adalah bahwa belum tentu 1-1. Mereka mengubah masalah ini dengan sedikit memodifikasi dan berpendapat bahwa, dalam kondisi tertentu pada keluarga , konstruksi baru memang 1-1. Mereka kemudian melanjutkan untuk menunjukkan bahwa kondisi ini memuaskan oleh fungsi berbasis RSA / Discrete-log.$f(r,s)$$f(r,s)$$\{f_i\}_i$