Czy istnieje kandydat na postkwantowe jednokierunkowe działanie grupowe?

9

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 za,bh(za)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.)


źródło

Odpowiedzi:

4

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 O działa na nią idealna grupa klasowa O. Tajny klucz jest zasadniczo opisem izogenezy poprzez jej ideał jądra i działanie elementu grupy[za] przyjmuje krzywą mi do kodomain wspomnianej izogeny:

([za],mi)mi/za=mi/αzakerα.
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.

rrrrrrr
źródło