Apakah ada kandidat untuk aksi kelompok satu arah pasca-kuantum?

Apakah ada keluarga aksi kelompok yang diketahui dengan elemen yang ditunjuk
dalam set yang sedang ditindaklanjuti, di mana diketahui cara efisien

$\:$ sampel (pada dasarnya seragam) dari kelompok, menghitung operasi terbalik,
$\:$ hitung operasi grup, dan hitung aksi grup

dan tidak ada algoritma kuantum efisien yang diketahui
untuk berhasil dengan probabilitas yang tidak dapat diabaikan di

$\:$ diberikan sebagai input indeks tindakan kelompok dan hasil
$\:$ elemen grup sampel yang bekerja pada elemen yang ditunjuk,
$\:$ temukan elemen grup yang tindakannya pada elemen yang ditunjuk adalah input kedua

?


Sejauh yang saya sadari, mereka menyediakan satu-satunya konstruksi yang diketahui dari komitmen menyembunyikan statistik non-interaktif di mana pengetahuan tentang pintu jebakan memungkinkan pengelompokan yang efisien dan tidak terdeteksi, properti yang berguna untuk protokol tanpa pengetahuan dan keamanan adaptif.

Setiap keluarga homomorfisme kelompok satu arah dengan tiga properti pertama (dari baris ketiga dan keempat dari posting ini) dapat dikonversi menjadi hal seperti itu dengan meminta domain bertindak pada codomain via $\: \langle a,b\rangle \mapsto h(a)\cdot b \:$, $\:$ dengan elemen identitas sebagai elemen yang dibedakan.

Versi terbatas dari skema komitmen Pedersen dapat diperoleh sebagai kasus khusus untuk menerapkan konversi di atas ke homomorfisme eksponensial grup, yang arah satu arahnya setara dengan kekerasan masalah logaritma diskrit, meskipun itu tidak sulit untuk algoritma kuantum. (Lihat algoritma Shor dan bagian halaman itu pada logaritma diskret.)

Ya , ada proposal lama untuk ini karena Couveignes , yang secara independen ditemukan kembali oleh Rostovtsev dan Stolbunov .

$\mathcal O$$\mathcal O$$[\mathfrak a]$$E$

$$([\mathfrak a], E) \longmapsto E/\mathfrak a = E/\bigcap_{\alpha\in\mathfrak a}\ker\alpha \text.$$ Catatan kuliah Luca De Feo . _{^{(Mereka juga mengandung lebih banyak latar belakang yang diperlukan untuk memahami konstruksi ini!)}}

Meskipun dimungkinkan untuk membalikkan tindakan kelompok dengan memecahkan contoh masalah pergeseran tersembunyi, sehingga menimbulkan serangan kuantum subeksponensial , sistem tetap tidak terputus untuk ukuran parameter yang cukup besar. Masalah yang jauh lebih besar adalah bahwa skema ini sangat lambat dalam praktiknya: Bahkan setelah upaya optimalisasi yang besar , satu perhitungan aksi kelompok masih membutuhkan waktu beberapa menit .

Masalah kinerja telah diatasi oleh proposal baru-baru ini yang disebut CSIDH dengan beralih ke kurva elips supersingular, yang secara drastis meningkatkan efisiensi sambil menjaga dasarnya struktur mendasar yang sama. Masih lambat relatif terhadap skema pra-kuantum yang sebanding, serta skema pasca-kuantum yang tak tertandingi, tetapi mungkin memiliki tempat di dunia pasca-kuantum karena fitur-fiturnya yang unik.