Bahasa apa yang telah berhasil secara kriptografi menggunakan pintu jebakan?

Pengamatan yang terkait dengan kriptografi asimetris adalah bahwa beberapa fungsi (diyakini) mudah dilakukan dalam satu arah tetapi sulit untuk dibalik. Selain itu, jika ada beberapa informasi 'pintu jebakan' yang memungkinkan operasi terbalik untuk dihitung dengan cepat maka masalahnya menjadi kandidat untuk skema kriptografi kunci publik.

Masalah pintu jebakan klasik, dibuat terkenal oleh RSA, termasuk masalah anjak piutang dan masalah log diskrit. Sekitar waktu yang sama ketika RSA diterbitkan, Rabin menemukan cryptosystem kunci publik didasarkan pada penemuan akar kuadrat diskrit (ini kemudian terbukti setidaknya sama sulitnya dengan anjak piutang).

Kandidat lain telah muncul selama bertahun-tahun. KNAPSACK (segera setelah RSA), Kurva Elliptic "Logaritma" dengan parameter tertentu, dan Masalah Dasar Terpendek Lattice adalah contoh masalah yang masalah pintu jebakannya digunakan dalam skema lain yang diterbitkan. Juga mudah untuk melihat bahwa masalah seperti itu harus berada di suatu tempat di NP.

Ini menguras pengetahuan saya tentang fungsi pintu jebakan. Tampaknya juga menguras daftar di Wikipedia juga.

Saya berharap bahwa kita bisa mendapatkan daftar bahasa wiki komunitas yang mengakui pintu jebakan dan literatur yang relevan. Daftar itu akan bermanfaat. Tuntutan kriptografi yang terus berkembang juga mengubah fungsi pintu jebakan yang dapat menjadi dasar dari sistem kriptografi. Ledakan penyimpanan pada komputer memungkinkan skema dengan ukuran tombol yang besar. Momok yang terus-menerus menjulang dari Quantum Computing membatalkan skema yang dapat dipatahkan dengan ramalan untuk menemukan subkelompok abelian tersembunyi. Cryptosystem Sepenuhnya Homomorfik Gentry hanya berfungsi karena kami telah menemukan fungsi pintu jebakan yang menghormati homomorfisme.

Saya terutama tertarik pada masalah yang tidak lengkap NP.

Penting untuk membedakan antara fungsi pintu jebakan dan enkripsi kunci publik. Sementara fungsi pintu jebakan memang menghasilkan skema enkripsi kunci-publik, beberapa kandidat yang Anda sebutkan hanya dikenal menyiratkan enkripsi kunci-publik dan tidak selalu memberi Anda fungsi pintu jebakan. Bahkan, Gertner, Malkin dan Reingold menunjukkan bahwa tidak ada konstruksi kotak hitam dari fungsi pintu jebakan dari "predikat pintu jebakan" (yang dapat dianggap sebagai skema enkripsi kunci publik satu-bit).

Contoh klasik dari fungsi pintu jebakan adalah fungsi RSA dan Rabin. Contoh klasik dari predikat pintu jebakan adalah menentukan Quadratic Residuosity modulo komposit, karena Goldwasser dan Micali. Konstruksi berbasis diskrit dan kisi yang Anda sebutkan menghasilkan enkripsi kunci publik secara langsung, tanpa melalui fungsi pintu jebakan.

Di bawah ini adalah daftar (tidak komprehensif) konstruksi skema enkripsi kunci publik, yang sebagian besar diketahui tidak melalui fungsi pintu jebakan.

• Cryptosystem kunci-publik El Gamal (termasuk varian kurva eliptik). Keamanan didasarkan pada asumsi Decisional Diffie Hellman. Tidak masuk ke fungsi pintu jebakan (tapi lihat item Peikert-Waters di bawah ini untuk fungsi pintu jebakan yang keamanannya didasarkan pada keamanan semantik El Gamal).

  [Taher El Gamal: Suatu Cryptosystem Kunci Publik dan Skema Tanda Tangan Berdasarkan Logaritma Diskrit. CRYPTO 1984: 10-18]

• Ajtai-Dwork, Regev. Keamanan didasarkan pada SVP unik dalam kisi-kisi. Tidak diketahui menyiratkan fungsi pintu jebakan.

  [Miklós Ajtai, Cynthia Dwork: Cryptosystem Public-Key dengan Kesetaraan Kasus Terburuk / Rata-Rata. STOC 1997: 284-293]

  [Oded Regev: Konstruksi kriptografi berbasis kisi baru. STOC 2003: 407-416]

• Regev, Peikert. Keamanan didasarkan pada kekerasan belajar dengan kesalahan (ini termasuk pengurangan dari SVP). Tidak diketahui menyiratkan fungsi pintu jebakan.

  [Oded Regev: Tentang kisi, belajar dengan kesalahan, kode linear acak, dan kriptografi. STOC 2005: 84-93]

  [Chris Peikert: Cryptosystem kunci publik dari masalah vektor terpendek terburuk: abstrak yang diperluas. STOC 2009: 333-342]

• Peikert, Perairan. Keamanan didasarkan pada Diffie Hellman keputusan dan pada masalah kisi. Dikenal menyiratkan fungsi trapdoor (melalui fungsi trapdoor lossy).

  [Chris Peikert, Brent Waters: Fungsi pintu jebakan yang hilang dan aplikasi mereka. STOC 2008: 187-196]

• Lyubashevsky, Palacio, Segev. Keamanan didasarkan pada Subset-Jumlah. Tidak diketahui menyiratkan fungsi pintu jebakan.

  [Vadim Lyubashevsky, Adriana Palacio, Gil Segev: Primitif Kriptografi Publik-Kunci Terbukti Aman sebagai Subset Sum. TCC 2010: 382-400]

• Stehlé, Steinfeld, Tanaka, Xagawa, dan Lyubashevsky, Peikert, Regev. Keamanan didasarkan pada kekerasan cincin LWE. Keuntungan dari semua ini dibandingkan proposal sebelumnya adalah ukuran kunci yang lebih kecil. Tidak diketahui menyiratkan fungsi pintu jebakan.

  [Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, Keita Xagawa: Enkripsi Kunci Publik yang Efisien Berdasarkan Kisi-Kisi Ideal. ASIACRYPT 2009: 617-635]

  [Vadim Lyubashevsky, Chris Peikert, Oded Regev: Tentang Kisi Ideal dan Belajar dengan Kesalahan atas Cincin. EUROCRYPT 2010: 1-23]