Квантовый алгоритм для решения задачи дискретного логарифмирования
Ключевые слова и синонимы
Логарифмы в группах
Постановка задачи
Пусть даны положительные действительные числа [math]\displaystyle{ a \ne 1, b }[/math]. Логарифмом b по основанию a называется единственное действительное число s, такое, что [math]\displaystyle{ b = a^s }[/math]. Понятие дискретного логарифма является расширением этого понятия на общие группы.
Задача 1 (дискретное логарифмирование)
Дано: группа G; [math]\displaystyle{ a, b \in G }[/math], такие, что [math]\displaystyle{ b = a^s }[/math] для некоторого целого положительного числа s.
Требуется: найти наименьшее положительное целое число s, удовлетворяющее условию [math]\displaystyle{ b = a^s }[/math], также известное как дискретный логарифм b по основанию a в G.
Обычный логарифм соответствует дискретному логарифму над группой положительных вещественных чисел при операции умножения. Наиболее распространенным случаем задачи о дискретном логарифме является группа [math]\displaystyle{ G = \mathbb{Z}^*_p }[/math], мультипликативная группа целых чисел от 1 до p - 1 по модулю p, где p – простое число. Еще один важный случай имеет место, когда группа G является группой точек эллиптической кривой над конечным полем.
Основные результаты
Задача поиска дискретного логарифма в [math]\displaystyle{ \mathbb{Z}^*_p }[/math], где p – простое число, а также в группе точек эллиптической кривой над конечным полем считается неразрешимой для рандомизированных классических компьютеров. Дело в том, что любому (возможно, рандомизированному) алгоритму для решения этой задачи на классическом компьютере потребуется время, суперполиномиальное относительно количества бит, необходимых для описания входных значений. Лучшим классическим алгоритмом для нахождения дискретных логарифмов в [math]\displaystyle{ \mathbb{Z}^*_p }[/math], где p – простое число, является адаптация Гордоном [4] метода решета числового поля, которая выполняется за время [math]\displaystyle{ exp(O((log \; p)^{1/3}(log \; log \; p)^{2/3})) }[/math].
В ходе своих революционных исследований Шор [9] предложил эффективный квантовый алгоритм для поиска дискретного логарифма в любой группе G; этот алгоритм работает за время, полиномиальное относительно размера входных данных в битах.
Результат 1 [9]. Существует квантовый алгоритм, решающий задачу дискретного логарифмирования в любой группе G на n-битных входных данных за время [math]\displaystyle{ O(n^3) }[/math] с вероятностью не менее 3/4.
Описание алгоритма для решения задачи дискретного логарифмирования
Алгоритм Шора [9] для решения задачи дискретного логарифмирования использует эффективную квантовую процедуру для реализации унитарного преобразования, известного как квантовое преобразование Фурье. Изначально его алгоритм давал эффективную процедуру выполнения квантового преобразования Фурье только над группами вида [math]\displaystyle{ \mathbb{Z}_r }[/math], где r – «гладкое» целое число; тем не менее, он показал, что этого достаточно для решения задачи дискретного логарифмирования в общем случае. В данной статье приводится более современное описание алгоритма Шора. В частности, используется результат Хейлз и Холлгрена [5], который показывает, что квантовое преобразование Фурье над любой конечной циклической группой [math]\displaystyle{ \mathbb{Z}_r }[/math] может быть эффективно аппроксимировано с обратно-экспоненциальной точностью.
Описание алгоритма приведено ниже. Предполагается знакомство с квантовой нотацией. Достаточное представление о квантовых вычислениях можно найти в книге Нильсена и Чуаня [8]. Пусть [math]\displaystyle{ (G, a, b, \bar{r}) }[/math] – экземпляр задачи дискретного логарифмирования, где [math]\displaystyle{ \bar{r} }[/math] – заданная верхняя граница на порядок [math]\displaystyle{ a }[/math] в G. То есть существует положительное целое число [math]\displaystyle{ r \le \bar{r} }[/math], такое, что [math]\displaystyle{ a^r = 1 }[/math]. Используя эффективный квантовый алгоритм поиска порядка, также разработанный Шором [9], можно предположить, что порядок [math]\displaystyle{ a }[/math] в G известен и представляет собой наименьшее положительное целое число r, удовлетворяющее условию [math]\displaystyle{ a^r = 1 }[/math]. Время выполнения алгоритма Шора для поиска порядка составляет [math]\displaystyle{ O((log \; \bar{r})^3) }[/math]. Пусть [math]\displaystyle{ \epsilon \gt 0 }[/math]. Алгоритм дискретного логарифмирования работает на трех регистрах, из которых первые два имеют длину по t кубитов, где [math]\displaystyle{ t := O(log \; r + log(1 / \epsilon)) }[/math], а третий регистр достаточно велик, чтобы хранить элемент G. Обозначим за U унитарное преобразование [math]\displaystyle{ U: |x \rangle |y \rangle |z \rangle \mapsto |x \rangle |y \rangle |z \bigoplus (b^x \; a^y) \rangle }[/math], где [math]\displaystyle{ \bigoplus }[/math] обозначает побитовое исключающее ИЛИ. Если имеется доступ к обратимому оракулу для групповых операций в G, U может быть реализовано обратимо за время [math]\displaystyle{ O(t^3) }[/math] путем многократного возведения в квадрат.
Обозначим за [math]\displaystyle{ \mathbb{C} [\mathbb{Z}_r] }[/math] гильбертово пространство функций от [math]\displaystyle{ \mathbb{Z}_r }[/math] над полем комплексных чисел. Вычислительный базис [math]\displaystyle{ \mathbb{C} [\mathbb{Z}_r] }[/math] состоит из дельта-функций [math]\displaystyle{ \{ |l \rangle \}_{0 \le l \le r - 1} }[/math], где [math]\displaystyle{ | \rangle }[/math] – функция, которая обращает элемент [math]\displaystyle{ l }[/math] в 1, а остальные элементы [math]\displaystyle{ \mathbb{Z}_r }[/math] в 0. Обозначим за [math]\displaystyle{ QFT_{\mathbb{Z}_r} }[/math] квантовое преобразование Фурье над циклической группой [math]\displaystyle{ \mathbb{Z}_r }[/math], определенное как следующий унитарный оператор над [math]\displaystyle{ \mathbb{C} [\mathbb{Z}_r] }[/math]:
[math]\displaystyle{ QFT_{\mathbb{Z}_r} : |x \rangle \mapsto r^{-1/2} \sum_{y \in \mathbb{Z}_r} e^{-2 \pi i x y/r} |y \rangle. }[/math]
Он может быть реализован за квантовое время [math]\displaystyle{ O(t \; log(t/ \epsilon) + log^2(1/ \epsilon)) }[/math] с точностью до ошибки [math]\displaystyle{ \epsilon }[/math] с использованием одного t-кубитного регистра [5]. Заметим, что для любого [math]\displaystyle{ k \in \mathbb{Z}_r }[/math] оператор [math]\displaystyle{ QFT_{\mathbb{Z}_r} }[/math] преобразует состояние [math]\displaystyle{ r^{-1/2} \sum_{x \in \mathbb{Z}_r} e^{2 \pi i k x/r} |x \rangle }[/math] в состояние [math]\displaystyle{ |k \rangle }[/math]. Для любого целого числа [math]\displaystyle{ l, 0 \le l \le r - 1 }[/math], определим
(1) [math]\displaystyle{ \; \; | \hat{l} \rangle := r^{-1/2} \sum_{k = 0}^{r - 1} e^{-2 \pi i l k/r} |a^k \rangle. }[/math]
Заметим, что [math]\displaystyle{ \{ | \hat{l} \rangle \}_{0 \le l \le r - 1} }[/math] образует ортонормальный базис [math]\displaystyle{ \mathbb{C} [ \langle a \rangle ] }[/math], где [math]\displaystyle{ \langle a \rangle }[/math] – подгруппа, порожденная [math]\displaystyle{ a }[/math] в G и изоморфная [math]\displaystyle{ \mathbb{Z}_r }[/math], а [math]\displaystyle{ \mathbb{C} [ \langle a \rangle ] }[/math] обозначает гильбертово пространство функций от [math]\displaystyle{ \langle a \rangle }[/math] над полем комплексных чисел.
Алгоритм 1 (дискретное логарифмирование)
Дано: элементы [math]\displaystyle{ a, b \in G }[/math], квантовая схема для U, порядок r для [math]\displaystyle{ a }[/math] в G.
Требуется: найти с постоянной вероятностью дискретный логарифм s от b по основанию [math]\displaystyle{ a }[/math] в G.
Время выполнения: суммарно [math]\displaystyle{ O(t^3) }[/math] базовых вентильных операций, включая четыре вызова [math]\displaystyle{ QFT_{\mathbb{Z}_r} }[/math] и один вызов U.
Процедура: 1. Повторить шаги (a)–(e) дважды, получив [math]\displaystyle{ (sl_1 }[/math] mod r, [math]\displaystyle{ l_1) }[/math] и [math]\displaystyle{ (sl_2 }[/math] mod r, [math]\displaystyle{ l_2) }[/math]. (a) [math]\displaystyle{ |0 \rangle |0 \rangle |0 \rangle }[/math] Инициализация; (b) [math]\displaystyle{ \mapsto r^{-1} \sum_{x, y \in \mathbb{Z}_r} |x \rangle |y \rangle |0 \rangle }[/math] Применить [math]\displaystyle{ QFT_{\mathbb{Z}_r} }[/math] к первым двум регистрам; (c) [math]\displaystyle{ \mapsto r^{-1} \sum_{x, y \in \mathbb{Z}_r} |x \rangle |y \rangle |b^x a^y \rangle }[/math] Применить U (d) [math]\displaystyle{ \mapsto r^{-1/2} \sum_{l = 0}^{r - 1} |sl \; mod \; r \rangle |l \rangle |\hat{l} \rangle }[/math] Применить [math]\displaystyle{ QFT_{\mathbb{Z}_r} }[/math] к первым двум регистрам; (e) [math]\displaystyle{ \mapsto (sl \; mod \; r, l) }[/math] Измерить первые два регистра; 2. Если [math]\displaystyle{ l_1 }[/math] не совпадает с [math]\displaystyle{ l_2 }[/math], прервать вычисление. 3. Пусть [math]\displaystyle{ k_1, k_2 }[/math] – целые числа, такие, что [math]\displaystyle{ k_1 l_1 + k_2 l_2 = 1 }[/math]. Вывести [math]\displaystyle{ s = k_1(sl_1) + k_2(sl_2) mod \; r }[/math].
Работа алгоритма поясняется ниже. Из равенства (1) легко увидеть, что [math]\displaystyle{ |b^x a^y \rangle = r^{-1/2} \sum_{l = 0}^{r - 1} e^{2 \pi i l (sx + y)/r} | \hat{l} \rangle }[/math].
Таким образом, состояние приведенного выше алгоритма на шаге 1(c) можно записать как [math]\displaystyle{ r^{-1} \sum_{x, y \in \mathbb{Z}_r} |x \rangle |y \rangle |b^x a^y \rangle = r^{-3/2} \sum_{l = 0}^{r - 1} \sum_{x, y \in \mathbb{Z}_r} e^{2 \pi i l (sx + y)/r} |x \rangle |y \rangle | \hat{l} \rangle = r^{-3/2} \sum_{l = 0}^{r - 1} \Bigg[ \sum_{x \in \mathbb{Z}_r} e^{2 \pi i s l x/r} \Bigg] \cdot \Bigg[\sum_{y \in \mathbb{Z}_r} e^{2 \pi i l y/r} \Bigg] | \hat{l} \rangle }[/math].
Применение [math]\displaystyle{ QFT_{\mathbb{Z}_r} }[/math] к первым двум регистрам дает состояние вышеприведенного алгоритма на шаге 1(d). Измерение первых двух регистров дает [math]\displaystyle{ (sl \; mod \; r, l }[/math]) для равномерно распределенного [math]\displaystyle{ l, 0 \le l \le r - 1 }[/math] на шаге 1(e). С помощью элементарной теории чисел можно показать, что если целые числа [math]\displaystyle{ l_1, l_2 }[/math] равномерно и независимо выбраны в интервале между 0 и [math]\displaystyle{ l - 1 }[/math], то они будут совпадать с постоянной вероятностью. В этом случае найдутся целые числа [math]\displaystyle{ k_1, k_2 }[/math] такие, что [math]\displaystyle{ k_1 l_1 + k_2 l_2 = 1 }[/math], что приведет к нахождению дискретного логарифма s на шаге 3 алгоритма с постоянной вероятностью. Поскольку фактически можно применить только [math]\displaystyle{ \epsilon }[/math]-приближенную версию [math]\displaystyle{ QFT_{\mathbb{Z}_r} }[/math], можно задать [math]\displaystyle{ \epsilon }[/math] достаточно малой константой, и это все равно даст правильный дискретный логарифм s на шаге 3 алгоритма с постоянной вероятностью. Вероятность успеха алгоритма Шора для задачи дискретного логарифмирования можно увеличить по крайней мере до 3/4, повторив его постоянное число раз.
Обобщения алгоритма для решения задачи дискретного логарифмирования
Задача о дискретном логарифмировании является частным случаем более общей задачи, называемой задачей о скрытой подгруппе [8].
Идеи, лежащие в основе алгоритма Шора для дискретного логарифмирования, могут быть обобщены для получения эффективного квантового алгоритма для поиска скрытых подгрупп в абелевых группах (краткий обзор см. в [1]). Оказывается, что нахождение дискретного логарифма [math]\displaystyle{ b }[/math] по основанию [math]\displaystyle{ a }[/math] в G сводится к задаче поиска скрытой подгруппы в группе [math]\displaystyle{ \mathbb{Z}_r \times \mathbb{Z}_r }[/math], где r – порядок [math]\displaystyle{ a }[/math] в G. Помимо задачи дискретного логарифмирования, другие криптографически важные функции, такие как факторизация целых чисел, нахождение порядка перестановок, нахождение эквивалентных относительно сдвига многочленов над конечными полями, могут быть сведены к случаям нахождения скрытой подгруппы в абелевых группах.
Применение
Предполагаемая неразрешимость задачи дискретного логарифмирования лежит в основе нескольких криптографических алгоритмов и протоколов. Первый пример криптографии с открытым ключом, а именно обмен ключами с помощью протокола Диффи-Хеллмана [2], использует дискретные логарифмы, обычно в группе [math]\displaystyle{ \mathbb{Z}^*_p }[/math] для простого числа p. Безопасность алгоритма цифровой подписи, являющегося национальным стандартом США (подробности и ссылки см. в [7]), зависит от предполагаемой неразрешимости задачи дискретного логарифмирования в [math]\displaystyle{ \mathbb{Z}^*_p }[/math], где p – простое число. Криптосистема Эль-Гамаля с открытым ключом [3] и ее производные используют дискретные логарифмы в соответствующим образом выбранных подгруппах [math]\displaystyle{ \mathbb{Z}^*_p }[/math], где p – простое число. Более поздние варианты применения включают криптографию на эллиптических кривых [6], где группа состоит из группы точек эллиптической кривой над конечным полем.
См. также
Литература
1. Brassard, G., Hayer, P.: An exact quantum polynomial-time algorithm for Simon's problem. In: Proceedings of the 5th Israeli Symposium on Theory of Computing and Systems, pp. 12-23, Ramat-Gan, 17-19 June 1997
2. Diffie, W., Hellman, M.: New directions in cryptography. IEEE Trans. Inf. Theor. 22,644-654 (1976)
3. ElGamal, T.: A public-key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theor. 31 (4), 469-472(1985)
4. Gordon, D.: Discrete logarithms in GF(p) using the number field sieve. SIAM J. Discret. Math. 6(1), 124-139 (1993)
5. Hales, L., Hallgren, S.: An improved quantum Fourier transform algorithm and applications. In: Proceedings of the 41 st Annual IEEE Symposium on Foundations of Computer Science, pp. 515-525 (2000)
6. Hankerson, D., Menezes, A., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer, New York (2004)
7. Menezes, A., van Oorschot, P., Vanstone, S.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1997)
8. Nielsen, M., Chuang, I.: Quantum computation and quantum information. Cambridge University Press, Cambridge (2000)
9. Shor, P.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5),1484-1509(1997)