On the complexity of discrete logarithm problem in a finite cyclic group with the efficient inversion.pdf Приведём постановки задач. Определение 1. Задача дискретного логарифмирования. Дано: группа G = (P), Q G G. Найти: n G {0,..., |G| - 1}, такое, что Q = nP. Определение 2. Задача дискретного логарифмирования в интервале. Дано: группа G = (P), Q G G, N G N, 2|N, N < |G| - 1, Q = nP для некоторого (неизвестного) n G { - N/2,..., N/2}. Найти: n. В настоящее время в общем случае одним из наиболее эффективным алгоритмом решения задачи дискретного логарифмирования в интервале является алгоритм Год-ри - Шоста [1]. Основная его идея может быть сформулирована следующим образом. Сначала выбираются так называемые «домашнее» (tame) и «дикое» (wild) множества: T = {-N/2,..., N/2}, W = {-N/2 + n,..., N/2 + n}. Затем параллельно вычисляются псевдослучайные последовательности хгР, хг G T, i =1, 2,...; (1) Q + Zj P, (n + Zj) G W, j = 1, 2,... (2) до тех пор, пока в них не найдутся два одинаковых элемента хк P = Q + ziP, (3) откуда находим n = хк - Zj. Средняя трудоёмкость алгоритма Годри - Шоста и его различных модификаций, измеряемая количеством групповых операций в G, равна по порядку величины среднему значению количества элементов последовательностей, вычисляемых до появления совпадающих элементов, в предположении, что значения n, х^ и Zj выбираются случайно равновероятно и независимо из соответствующих множеств. Это среднее значение может быть получено с использованием результата [2], являющегося обобщением парадокса дней рождения. Предположим теперь, что группа G обладает эффективно вычислимой операцией р взятия обратного элемента, т. е. время, необходимое для вычисления обратного элемента, существенно меньше времени, необходимого для выполнения одной групповой операции. Тогда группа G распадается на непересекающиеся классы эквивалентности (орбиты) относительно действия р, и подобно тому, как это делается в работе [3] для классической задачи дискретного логарифмирования, можно ускорить алгоритм, если искать не совпадающие элементы последовательностей (1) и (2), а совпадающие классы эквивалентности этих элементов. Действительно, в этом случае вместо равенства (3) имеем равенство рв(хЛ P) = Q + ZjP для некоторого s, откуда Q = ((-1Гхк - Zj)P, т. е. n = (-1)5хк - Zj. Примером такой группы c эффективным инвертированием является группа точек эллиптической кривой У2 = х3 + Ах + B над конечным простым полем из p > 3 элементов. Действительно, р(х,У) = (х, -у), т.е. p^P) = -aP и класс эквивалентности точки aP относительно действия группы (р) состоит из aP и p^P). Каждому такому классу эквивалентности соответствует множество {а, -а}. В [4] для этого случая предложена соответствующая модификация алгоритма Год-ри - Шоста, имеющая при N ^ то трудоёмкость (1,36 + o(1))\/N групповых операций. В настоящей работе конструктивно доказывается возможность дальнейшего улучшения оценки средней трудоёмкости решения задачи дискретного логарифмирования в интервале для группы с эффективным инвертированием. Основной результат может быть сформулирован в виде следующей теоремы. Теорема 1. Пусть G - циклическая группа с эффективным инвертированием, пусть также 2|N. Тогда для любого e > 0 существует такой алгоритм решения задачи дискретного логарифмирования в интервале в группе G, что при случайном равновероятном выборе n его средняя трудоёмкость не превосходит (1 + enN/2 + O£(N1/4) групповых операций, где N ^ те. Здесь запись O£ означает, что константа под символом O зависит от е. Подробное изложение представленных результатов можно найти в [5].

Скачать электронную версию публикации