Czy istnieje kandydat na postkwantowe jednokierunkowe działanie grupowe?

Czy istnieje znana rodzina działań grupowych z wyznaczonym elementem
w zestawie, na którym działa się, gdzie wiadomo, jak skutecznie

$\:$ próbkuj (zasadniczo jednolicie) z grup, oblicz operacje odwrotne,
$\:$ oblicz operacje grupowe i oblicz działania grupowe

i nie ma znanego wydajnego algorytmu kwantowego
do osiągnięcia sukcesu z nieistotnym prawdopodobieństwem w

$\:$ jako dane wejściowe podaje się indeks akcji grupowej i wynik
$\:$ próbkowany element grupy działający na wyznaczony element,
$\:$ znajdź element grupy, którego działanie na wyznaczonym elemencie jest drugim wejściem

?


O ile mi wiadomo, stanowią one jedyne znane konstrukcje nieinteraktywnych statystycznie ukrytych zobowiązań, w których znajomość zapadni umożliwia wydajne i niewykrywalne dwuznaczność, właściwość przydatną do protokołów zerowej wiedzy i bezpieczeństwa adaptacyjnego.

Każda rodzina jednokierunkowych homomorfizmów grupowych z pierwszymi trzema właściwościami (z trzeciego i czwartego wiersza tego postu) może zostać przekształcona w coś takiego, poprzez działanie domen na kodomeny za pośrednictwem $\: \langle a,b\rangle \mapsto h(a)\cdot b \:$, $\:$ z elementami tożsamości jako elementami wyróżniającymi.

Ograniczoną wersję schematu zobowiązań Pedersena można uzyskać jako szczególny przypadek zastosowania powyższej konwersji do wykładniczego homomorfizmu grupowego, którego jednokierunkowość jest równoważna z twardością problemu dyskretnego logarytmu, chociaż nie jest to trudne w przypadku algorytmów kwantowych. (Zobacz algorytm Shora i sekcję tej strony dotyczącą logarytmu dyskretnego.)

Tak , istnieje stara propozycja na ten temat ze względu na Couveignes , która została niezależnie odkryta na nowo przez Rostowcewa i Stolbunowa .

W obu przypadkach zestaw krzywych eliptycznych z pewnym wspólnym pierścieniem endomorficznym $\mathcal O$ działa na nią idealna grupa klasowa $\mathcal O$. Tajny klucz jest zasadniczo opisem izogenezy poprzez jej ideał jądra i działanie elementu grupy$[\mathfrak a]$ przyjmuje krzywą $E$ do kodomain wspomnianej izogeny:

$$([\mathfrak a], E) \longmapsto E/\mathfrak a = E/\bigcap_{\alpha\in\mathfrak a}\ker\alpha \text.$$ Istnieje przyjemna interpretacja tego działania na wykresach, opisana (na przykład) w rozdziale 14.1 notatek z wykładu Luca De Feo . _{^{(Zawierają również więcej tła niezbędnego do zrozumienia tej konstrukcji!)}}

Podczas gdy możliwe jest odwrócenie działania grupy poprzez rozwiązanie wystąpienia problemu ukrytej zmiany, co powoduje podwykładniczy atak kwantowy , system pozostaje nieprzerwany dla stosunkowo dużych rozmiarów parametrów. Znacznie większym problemem jest to, że schematy te są boleśnie powolne w praktyce: nawet po znacznych wysiłkach optymalizacyjnych jedno obliczenie działania grupowego nadal zajmuje kilka minut .

Kwestia wydajności została rozwiązana przez ostatnią propozycję o nazwie CSIDH , przechodząc do supersingularnych krzywych eliptycznych, co drastycznie poprawia wydajność przy jednoczesnym zachowaniu zasadniczo tej samej podstawowej struktury. Wciąż jest powolny w porównaniu do porównywalnych schematów przedkwantowych, a także nieporównywalnych schematów pokwantowych, ale może mieć swoje miejsce w świecie postkwantowym ze względu na swoje unikalne cechy.