Квантовый алгоритм для решения задачи дискретного логарифмирования: различия между версиями

'''Задача 1 (Дискретное логарифмирование)'''

В ходе своих революционных исследований Шор [9] предложил эффективный квантовый алгоритм для поиска дискретного логарифма в любой группе G; его алгоритм работает за время, полиномиальное относительно размера входных данных в битах.

Алгоритм Шора [9] для решения задачи дискретного логарифмирования использует эффективную квантовую процедуру для реализации унитарного преобразования, известного как квантовое преобразование Фурье. Его исходный алгоритм давал эффективную процедуру выполнения ''квантового преобразования Фурье'' только над группами вида <math>\mathbb{Z}_r</math>, где r – «гладкое» целое число; тем не менее, он показал, что этого достаточно для решения задачи дискретного логарифмирования в общем случае. В данной статье приводится более современное описание алгоритма Шора. В частности, используется результат Хейлз и Холлгрена [5], который показывает, что квантовое преобразование Фурье над любой конечной циклической группой <math>\mathbb{Z}_r</math> может быть эффективно аппроксимировано с обратно-экспоненциальной точностью.

Описание алгоритма приведено ниже. Предполагается знакомство с квантовой нотацией. Достаточное представление о квантовых вычислениях можно найти в книге Нильсена и Чуаня [8]. Пусть <math>(G, a, b, \bar{r})</math> – экземпляр задачи дискретного логарифмирования, где <math>\bar{r}</math> – заданная верхняя граница на порядок a в G. То есть существует положительное целое число <math>r \le \bar{r}</math>, такое, что <math>a^r = 1</math>. Используя эффективный квантовый алгоритм поиска порядка, также разработанный Шором [9], можно предположить, что порядок a в G известен и представляет собой наименьшее положительное целое число r, удовлетворяющее <math>a^r = 1</math>. Время выполнения алгоритма Шора для поиска порядка составляет <math>O((log \; \bar{r})^3)</math>. Пусть <math>\epsilon > 0</math>. Алгоритм дискретного логарифмирования работает на трех регистрах, из которых первые два имеют длину по t кубитов, где <math>t := O(log \; r + log(1 / \epsilon))</math>, а третий регистр достаточно велик, чтобы хранить элемент G. Пусть U обозначает унитарное преобразование <math>U: |x \rangle |y \rangle |z \rangle \mapsto |x |rangle |y \rangle |z \bigoplus (b^x \; a^y) \rangle</math>, где <math>\bigoplus</math> обозначает побитовое исключающее ИЛИ. Если имеется доступ к обратимому оракулу для групповых операций в G, U может быть реализовано обратимо за время <math>O(t^3)</math> путем многократного возведения в квадрат.

Заметим, что <math>\{ | \hat{l} \rangle \}_{0 \le l \le r - 1}</math> образует ортонормальный базис <math>\mathbb{C} [ \langle a \rangle ]</math>, где <math>\langle a \rangle</math> – подгруппа, порожденная a в G и изоморфная <math>\mathbb{Z}_r</math>, а <math>\mathbb{C} [ \langle a \rangle ]</math> обозначает гильбертово пространство функций от <math>\langle a \rangle</math> над полем комплексных чисел.

'''Алгоритм 1 (Дискретное логарифмирование)'''

Дано: элементы <math>a, b \in G</math>, квантовая схема для U, порядок r для a в G.

Требуется: найти с постоянной вероятностью дискретный логарифм s от b по основанию a в G.

   (d) <math> \mapsto r^{-1/2} \sum_{l = 0}^{r - 1} |sl mod r \rangle |l \rangle |\hat{l} \rangle</math>

   (e) <math> \mapsto</math> (sl mod r, l)

   3. Пусть <math>k_1, k_2</math> - целые числа, такие, что <math>k_1 l_1 + k_2 l_2 = 1</math>. Вывести <math>s = k_1(sl_1) + k_2(sl_2) mod r</math>.

Применение <math>QFT_{\mathbb{Z}_r}</math> к первым двум регистрам дает состояние вышеприведенного алгоритма на шаге 1(d). Измерение первых двух регистров дает (sl mod r, l) для равномерно распределенного l, <math>0 \le l \le r - 1</math> на шаге 1(e). С помощью элементарной теории чисел можно показать, что если целые числа <math>l_1, l_2</math> равномерно и независимо выбраны в интервале между 0 и l-1, то они будут совпадать с постоянной вероятностью. В этом случае найдутся целые числа <math>k_1, k_2</math> такие, что <math>k_1 l_1 + k_2 l_2 = 1</math>, что приведет к нахождению дискретного логарифма s на шаге 3 алгоритма с постоянной вероятностью. Поскольку фактически можно применить только <math>\epsilon</math>-приближенную версию <math>QFT_{\mathbb{Z}_r}</math>, можно задать <math>\epsilon</math> достаточно малой константой, и это все равно даст правильный дискретный логарифм s на шаге 3 алгоритма с постоянной вероятностью. Вероятность успеха алгоритма Шора для задачи дискретного логарифма можно увеличить по крайней мере до 3/4, повторив его постоянное число раз.

Идеи, лежащие в основе алгоритма Шора для дискретного логарифмирования, могут быть обобщены для получения эффективного квантового алгоритма для поиска скрытых подгрупп в абелевых группах (краткий обзор см. в [1]). Оказывается, что нахождение дискретного логарифма b по основанию a в G сводится к задаче поиска скрытой подгруппы в группе <math>\mathbb{Z}_r \times \mathbb{Z}_r</math>, где r – порядок ''a'' в G. Помимо задачи дискретного логарифмирования, другие криптографически важные функции, такие как факторизация целых чисел, нахождение порядка перестановок, а также нахождение эквивалентных относительно сдвига многочленов над конечными полями, могут быть сведены к случаям нахождения скрытой подгруппы в абелевых группах.

Предполагаемая неразрешимость задачи дискретного логарифмирования лежит в основе нескольких криптографических алгоритмов и протоколов. Первый пример криптографии с открытым ключом, а именно обмен ключами с помощью протокола Диффи-Хеллмана [2], использует дискретные логарифмы, обычно в группе <math>\mathbb{Z}^*_p</math> для простого числа p. Безопасность алгоритма цифровой подписи, являющегося национальным стандартом США (подробности и ссылки см. в [7]), зависит от предполагаемой неразрешимости задачи дискретного логарифмирования в <math>\mathbb{Z}^*_p</math>, где p – простое число. Криптосистема Эль-Гамаля с открытым ключом [3] и ее производные используют дискретные логарифмы в соответствующим образом выбранных подгруппах <math>\mathbb{Z}^*_p</math>, где p – простое число. Более поздние варианты применения включают криптографию на эллиптических кривых [ ], где группа состоит из группы точек эллиптической кривой над конечным полем.