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