Есть ли кандидат на постквантовое одностороннее групповое действие?

9

Существует ли известное семейство групповых действий с назначенным элементом
в наборе, над которым выполняется действие, где известно, как эффективно

выборка (по существу, равномерно) из групп, вычисление обратных операций, вычисление групповых операций и вычисление групповых действий

и нет известного эффективного квантового алгоритма
для успеха с пренебрежимо малой вероятностью в

качестве входных данных указывается индекс действия группы и результат выборочный элемент группы, воздействующий на назначенный элемент, найти элемент группы, действие которого на назначенном элементе является вторым входом

?


Насколько мне известно, они предоставляют единственные известные конструкции неинтерактивных статистически скрывающих обязательств, в которых знание люка обеспечивает эффективную и необнаружимую двусмысленность, свойство, которое полезно для протоколов с нулевым знанием и адаптивной безопасности.

Любое семейство гомоморфизмов односторонней группы с первыми тремя свойствами (из третьей и четвертой строк этого поста) может быть преобразовано в такую ​​вещь, если домены действуют на кодомены через , с элементами идентичности как выделенные элементы.a,bh(a)b

Ограниченная версия схемы обязательств Педерсена может быть получена как частный случай применения указанного выше преобразования к групповому экспоненциальному гомоморфизму, односторонность которого эквивалентна сложности задачи дискретного логарифма, хотя это не сложно для квантовых алгоритмов. (См . Алгоритм Шора и раздел этой страницы о дискретном логарифме.)


источник

Ответы:

4

Да , есть старое предложение для этого из-за Кувейна , которое было независимо переоткрыто Ростовцевым и Столбуновым .

В обеих случаях множество эллиптических кривых с некоторыми общими кольцом эндоморфизмов действуют на идеал группы классов . Секретный ключ - это, по сути, описание изогении через идеал ядра, и действие группового элемента выводит кривую в кодомен указанной изогении: Есть хорошая интерпретация этого действия, которая описана (например) в разделе 14.1 лекционных заметок Луки Де Фео . (Они также содержат больше информации, необходимой для понимания этой конструкции!)OO[a]E

([a],E)E/a=E/αakerα.

Несмотря на то, что можно инвертировать групповое действие, решая проблему скрытого сдвига, приводя к субэкспоненциальной квантовой атаке , система остается неповрежденной для достаточно больших размеров параметров. Гораздо более серьезная проблема заключается в том, что на практике эти схемы мучительно медленны: даже после значительных усилий по оптимизации одно вычисление группового действия все еще занимает минуты .

Проблема производительности была решена недавним предложением под названием CSIDH путем перехода к суперсингулярным эллиптическим кривым, что значительно повышает эффективность при сохранении, по существу, той же базовой структуры. Он все еще медленный по сравнению с сопоставимыми доквантовыми схемами, а также несопоставимыми постквантовыми схемами, но может иметь место в постквантовом мире из-за его уникальных особенностей.

YYYYYYY
источник