Permutasi Satu Arah tanpa Trapdoor

Singkatnya: Dengan asumsi permutasi satu arah ada, dapatkah kita membangun yang tidak memiliki pintu jebakan?

Info lebih lanjut:

Permutasi satu arah adalah permutasi yang mudah dihitung, tetapi sulit untuk dibalik (lihat wiki tag fungsi satu arah untuk definisi yang lebih formal). Kami biasanya mempertimbangkan keluarga permutasi satu arah, , di mana setiap adalah permutasi satu arah, yang bekerja pada domain terbatas . Sebuah pintu jebakan satu arah permutasi didefinisikan seperti di atas, kecuali bahwa ada satu set pintu jebakan dan algoritma poli-waktu pembalik , sehingga untuk semua , , dan $\pi$ $\pi = \{\pi_n\}_{n \in \mathbb{N}}$ $\pi_n$ $D_n$ $\{t_n\}_{n \in \mathbb{N}}$ $I$ $n$ $|t_n| \le {\rm poly}(n)$ $I$ dapat membalikkan asalkan diberikan . $\pi_n$ $t_n$

Saya tahu permutasi satu arah yang dihasilkan sehingga tidak mungkin menemukan pintu jebakan (namun pintu jebakan ada). Contoh, berdasarkan asumsi RSA, diberikan di sini . Pertanyaannya adalah,

Apakah ada permutasi (keluarga) satu arah yang tidak memiliki pintu jebakan (set)?

Edit: (Lebih Banyak Formalisasi)

Asumsikan ada permutasi satu arah dengan domain (tak terbatas) . Yaitu, terdapat algoritma polinomial-waktu probabilistik (yang, pada input , menginduksi beberapa distribusi melalui ), sehingga untuk setiap musuh waktu-polinomial , setiap , dan semua bilangan bulat yang cukup besar : $\pi$ $D \subseteq \{0,1\}^*$ $\mathcal{D}$ $1^n$ $D_n=\\{0,1\\}^n \cap D$ $\mathcal{A}$ $c>0$ $n$

$\Pr[x \leftarrow \mathcal{D}(1^n) \colon \quad \mathcal{A}(\pi(x))=x]<n^{-c}$

(Peluang diambil dari lemparan koin internal dari $\mathcal{D}$ dan $\mathcal{A}$ .)

Pertanyaannya, adalah apakah kita dapat membangun permutasi satu arah , yang untuknya terdapat algoritme waktu polinomial probabilistik sedemikian rupa sehingga untuk setiap keluarga ukuran-rangkaian sirkuit , apa pun , dan semua bilangan bulat yang cukup besar : $\pi'$ $\mathcal{D}'$ $\mathcal{A}'=\{\mathcal{A}'_n\}_{n \in \mathbb{N}}$ $c>0$ $n$

$\Pr[x \leftarrow \mathcal{D}'(1^n) \colon \quad \mathcal{A}'_n(\pi'(x))=x]<n^{-c}$

(Peluang diambil dari lemparan koin internal dari , karena adalah deterministik.) $\mathcal{D}'$ $\mathcal{A}'$

cr.crypto-security one-way-function MS Dousti
sumber

Sepertinya Anda menginginkan OWP yang tetap satu arah bahkan ketika diberi jumlah polinomial saran. Ngomong-ngomong, kita biasanya tidak mendefinisikan keluarga OWP seperti itu - lihat Goldreich Vol 1, defs 2.4.4 dan 2.4.5.

David Cash

@ David: Ya, saya tahu itu bukan definisi yang biasa, tapi saya merasa definisi formal (yang muncul di buku Goldreich) terlalu panjang untuk diskusi ini.

MS Dousti

@ Sadq: Cukup adil, tapi saya pikir perubahan definisi akan signifikan di sini. Untuk apa nilainya, saya sudah mencoba memikirkan jenis keamanan yang sama (tidak ada pintu jebakan) sebelumnya. Sepertinya definisi yang baik adalah untuk memungkinkan pemrosesan indeks keluarga tanpa batas untuk menghasilkan saran sebelum percobaan inversi.

David Cash

@ David: lihat apakah bagian yang diedit memenuhi kebutuhan untuk formalisasi lebih lanjut.

MS Dousti

@Sadeq: Menentukan apakah permutasi pintu satu arah tersirat oleh permutasi satu arah atau tidak (meskipun itu bahkan tidak jelas apa artinya yang terakhir, karena keduanya bisa ada) adalah salah satu masalah terbuka terbesar dalam teori kriptografi . Impagliazzo dan Rudich ( cseweb.ucsd.edu/~russell/secret.ps ) membuktikan bahwa ini tidak dapat dicapai dengan menggunakan teknik black-box, dan teknik saat ini tidak diketahui memotong pemisahan mereka.

Alon Rosen

Jawaban:

Pertimbangkan kasus-kasus berikut:

1) Permutasi satu arah (OWP) ada tetapi permutasi pintu jebakan (TDP) tidak (yaitu kita berada dalam varian dunia " minicrypt " Impagliazzo ). Dalam hal ini Anda hanya mengambil OWP yang dijamin ada, dan Anda tahu itu tidak memiliki pintu jebakan.

2) Baik OWP dan TDP ada. Di sini Anda memiliki dua opsi:

(a) Setiap OWP memiliki algoritma pembuatan kunci G yang menampilkan deskripsi fungsi "publik" bersama dengan t pintu jebakan yang disampel. Dalam hal ini, pertimbangkan generasi kunci yang dimodifikasi yang hanya menghasilkan f. Ini memberi Anda OWP, dan terlebih lagi tidak layak untuk menemukan f (karena jika tidak, Anda memiliki cara yang efisien untuk membalikkan f). Ini juga berlaku untuk varian yang tidak seragam.

(B) Ada OWP f sehingga tidak ada algoritma G dapat menghasilkan f dan t sehingga t memungkinkan inversi f (x) untuk x acak. Dalam hal ini f adalah OWP yang tidak memiliki pintu jebakan.

Salah satu komentar di utas di atas tampaknya menunjukkan bahwa Anda mempertanyakan sebenarnya apakah keberadaan OWP diketahui menyiratkan keberadaan TDP. Ini telah ditunjukkan untuk tidak menahan konstruksi / pengurangan kotak hitam, dan terbuka secara umum (lihat komentar saya di utas di atas).

Alon Rosen
sumber

+1, terima kasih. David telah berusaha keras untuk menjawab, dan saya sangat berterima kasih kepadanya; tapi ini adalah yang jawaban apa yang ada dalam pikiran saya.

MS Dousti

Saya pikir pertanyaannya adalah: apakah (a) mungkin. Secara kriptografis, jika setiap OWP memiliki pintu jebakan, maka Anda tidak dapat mempercayai seseorang yang memberi Anda OWP untuk tidak juga mengetahui pintu jebakan. Tentu saja, Anda bisa mengambil OWP-nya dan menyusunnya dengan OWP Anda sendiri, yang hanya Anda yang tahu pintu jebakan, dan dapatkan OWP yang tidak ada satu pihak pun yang tahu pintu jebakan itu.

Peter Shor

@ Peter: Ya. Komposisi tampaknya melakukan pekerjaan itu. Pilihan lain adalah menggunakan transfer yang tidak diketahui (yang, jika (a) berlaku, diketahui ada - modulo beberapa subltleties kecil). Dengan menggunakan OT, para pemain dapat membangun protokol perhitungan 2-pihak yang aman yang memungkinkan salah satu dari mereka belajar tanpa mempelajari pintu jebakan dan yang lain tidak mempelajari apa pun. Tetapi solusi Anda memang lebih sederhana.

Alon Rosen

Saya tidak tahu tentang konstruksi dari asumsi umum, tetapi Anda bisa mendapatkan kandidat yang masuk akal untuk "permutasi satu arah tanpa pintu jebakan" dengan menggunakan modul disk log disko a prima . Artinya, biarkan menjadi primitif akar modulo , dan menentukan . Maka adalah permutasi pada bilangan bulat antara dan , dan umumnya diasumsikan satu arah. Untuk bagian "tanpa pintu jebakan", saya kira Anda perlu mendefinisikan dengan tepat apa artinya itu, tetapi sejauh yang saya tahu, kami tidak memiliki cara untuk mengatur semuanya untuk mengaktifkan inversi. (Jika kami melakukannya, itu akan memiliki semua jenis aplikasi keren (positif) dalam kriptografi!) $p$ $g$ $p$ $\pi(x) = g^x\!\mod p$ $\pi$ $1$ $p-1$

David Cash
sumber

+1. Terima kasih atas jawabannya. Anda mengasumsikan kekerasan log diskrit terhadap musuh yang tidak seragam. Pertanyaan saya adalah: Dengan asumsi hanya adanya permutasi satu arah, dapatkah kita membangun yang tidak memiliki pintu jebakan?

MS Dousti

@Sadeq: Bukankah keberadaan permutasi satu arah menyiratkan kekerasan log diskrit sejak P = NP?

Mohammad Alaggan

@Alaggan: Saya kira tidak. Mungkin itu terjadi bahwa ada permutasi satu arah, tetapi seseorang datang dengan algoritma yang efisien untuk membalik log diskrit.

MS Dousti

@Sadeq: Itu jika P = BQP! = NP.

Mohammad Alaggan

@ Sadq: Benar atau saya salah?

Mohammad Alaggan