Использование классов эквивалентности для ускоренного решения задачи дискретного логарифмирования в коротком интервале

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 11:27, 22 ноября 2015.
Using Equivalence Classes to Accelerate Solving the Discrete Logarithm
DLP.jpg
Авторы Steven D. Galbraith[@: 1]
Raminder S. Ruprai[@: 2]
Опубликован 2010 г.
Сайт Public Key Cryptography 2010
Перевели Борис Степанов
Год перевода 2015 г.
Скачать оригинал
Аннотация. ρ-метод Поларда помогает решить задачу дискретного логарифмирования (далее ЗДЛ) в интервале размера N с ожидаемым оперативным временем эвристического среднего случая приблизительно равным групповых операций. Хорошо известно, что производительность ρ-метода Поларда может быть увеличена при использовании классов эквивалентности (таких как орбиты точек эффективно рассчитанного гомоморфизма групп), но такие идеи не используются для ЗДЛ в интервале. Действительно, выглядит невозможным применить стандартный ρ-метод совместно с классами эквивалентности.
Основной результат работы сводится к алгоритму, построенному на работах Годри и Шоста и ведущему к решению ЗДЛ в интервале размера N в эвристически среднем случае, когда ожидаемое оперативное время близко к групповых операций для групп с быстрой инверсией. На практике алгоритм не настолько быстр из-за обычных проблем с псевдослучайным блужданием, таких как бесплодные циклы. В дополнение, мы приводим результаты экспериментов.


Ключевые слова: задача дискретного логарифмирования (DLP, ЗЛП), эллиптические кривые, карта отрицаний, эффективно рассчитываемые группы гомоморфизма.

Введение

Задача дискретного логарифмирования (ЗДЛ) в интервале выглядит следующим образом: Дано в группе и в результате чего для некоторых (где N меньше, чем порядок g), вычислить n. Эта проблема возникает естественным путем в ряде контекстов, например, в ЗДЛ с с-бит экспонентами (c-DLSE) [1] [2] [3], при дешифровании по схеме гомоморфного шифрования Бонэ – Го - Нессима [4], при подсчете точек на кривых или в абелевом многообразии над конечными полями [5], при анализе задачи Диффи-Хеллмана [6] [7], при атаках по побочным каналам или атакам по малым подгруппам. [8] [9]

ЗДЛ в интервале может быть решена при помощи алгоритма больших и малых шагов по меньшей мере в групповых операциях (или при незначительных доработках с оперативным временем среднего случая равным групповых операций). Но для этого метода также требуется групповых элементов памяти.

Поллард [10] разработал алгоритм кенгуру имея в виду именно это приложение. Используя отмеченные точки, ван Ооршот и Винер [11] (также см Поллард [12]) достигают ожидаемой сложности эвристического среднего случая в существенных групповых операциях и при небольшой памяти. Мы обобщаем этот алгоритм в дополнении А. Заметьте, что этот алгоритм имеет вероятность успеха равную 1, как и все алгоритмы в этой работе. Эти алгоритмы также могут быть распараллелены с линейным ускорением. Для сравнения, ρ-метод Полларда [10] имеет эвристическое ожидаемое оперативное время oопераций, если имеет порядок . Все сложные утверждения в этой работе полагаются на эвристические допущения; для более полного анализа метода кенгуру обращайтесь к работам Монтенегро и Тетали [13]. Годри и Шост [5] (основываясь на более ранней работе Годри и Харлея [14]) предложили другой подход к решению этой задачи, представив анализ в стиле «парадокса дня рождения». В то время как их парадокс не настолько быстр, как парадокс Ооршота и Винера, он легко распараллеливается и, что важно, нет необходимости знать количество клиентов или процессоров перед тем как алгоритм запущен в действие. Распараллеливание алгоритма Годри-Шоста дает линейное ускорение, и это также относится ко всем алгоритмам в данной работе. Для краткости мы сводим все интервалы операционного времени к примеру последовательности. Среднее ожидаемое операционное время их алгоритма равняется групповых операций на серийном компьютере (алгоритм Годри и Харлея [14] менее рационален). Мы представляем этот алгоритм и напоминаем анализ его сложности в Разделе 2.

Галлант, Ламберт и Ванстоун [15] а также Винер и Дзукератто [16] показали, что ρ-метод Полларда может быть использован с классами эквивалентности (орбитами групповых элементов при быстро рассчитываемом групповом гомоморфизме), чтобы достигнуть постоянного ускорения в некоторых группах. В частности, для эллиптических кривых ρ-алгоритм может быть ускорен фактором при использовании класса эквивалентности , где это элемент группы (которые чаще записывается как в случае эллиптических кривых). На практике, интервалы оперативного времени недостаточно хороши, так как алгоритмы используют псевдослучайные блуждания (в частности, блуждания могут попасть в короткие циклы и таким образом никогда не попасть в отмеченную точку; такие циклы называются «бесплодными» и были проанализированы Дуурсма, Годри и Морейном[17], а также Босом, Клейнюнгом и Ленстрой [18]). Выглядит невозможным комбинировать стандартный ρ-метод с классами эквивалентов в обычном аспекте в Разделе 19.6.3 [19] заявлено, что это может быть сделано, но не предоставлено никаких деталей, и это выглядит просто ошибкой). Поэтому, необходимо рассмотреть другие алгоритмы. Более естественным выглядит то, что что для частного случая ЗДЛ даже в интервале длиной , можно установить и затем решить, что , где . Если дискретный логарифм u лежит в интервале значит класс эквивалентности соответствует паре элементов группы в рассматриваемой области. Совсем недавно Поллард [25] разработал два новых варианта метода кенгуру, который предполагает инверсию только одного или двух элементов группы. Третий и четвертый вариант «кенгуру» имеют эвристические интервалы оперативного времени приблизительно и групповых операций соответственно. Более детальное описание алгоритмов будет опубликовано в предстоящей совместной работе.

В разделах 3 и 4 мы показываем, как ускорить метод Годри-Шоста в группах с быстрой инверсией (таких как эллиптические кривые, торы, LUC и XTR). Здесь быстрая инверсия означает, что расчет для любого в группе намного быстрее, чем операции с общими группами. Мы также представляем дальнейшее ускорение, модифицируя область поиска. Наш основной результат – это метод решения ЗДЛ на интервале примерно в групповых операций. Результат получен при использовании нового варианта «парадокса дня рождения», который разработан в [20]. Теоретический анализ алгоритма допускает, что он применяется с использованием действительного случайного блуждания. На практике алгоритм реализуется с использованием псевдослучайного блуждания, при котором проявляется ряд нежелательных последствий – в частности, существование «бесплодных циклов». В Разделе 5 мы представляем экспериментальные результаты, которые дают лучшее представление о фактических показателях на практике (хотя имеются предпосылки, что эти данные могут быть улучшены).

Наш алгоритм, как и в случае с работой Годри-Шоста, требует небольшой памяти и может быть очень легко распараллелен с линейным ускорением. В Приложении В мы показывали, как ускорить работу алгоритма Годри-Шоста для многомерной ЗДЛ, используя классы эквивалентов. Подробный анализ алгоритмов в Приложении В все еще остается открытым вопросом.

Алгоритм Годри-Шоста

Для того, чтобы представить систему обозначений и основные идеи, нам необходимо вспомнить алгоритм Годри-Шоста [5]. Принцип его работы такой же, как и у алгоритма «кенгуру» Полларда в формулировке Ван Ооршота и Винера [11]. Пусть и являются частными случаями ЗДЛ, которые мы намереваемся решить, для некоторого числа . Мы запускаем большое количество псевдослучайных блужданий (возможно распределенных среди большого количества процессоров. Половина блужданий становится «укрощенными блужданиями», и это означает, что каждый элемент блуждания – , где a известная целая. Другая половина представлена «дикими блужданиями», и это значит, что каждый элемент – , где число также известно. Как и полагается, для этого субъекта исследования мы визуализируем группу в аспекте ‘шаг экспоненты’. Если быть точнее, определяем ‘укрощенное множество’

(где под мы подразумеваем ) и ‘дикое множество’

Хотя и имеют один и тот же размер, -это отображение , и, конечно, мы не знаем значения n. «Укрощенное блуждание» - это последовательность точек , где , а «дикое блуждание» это последовательность точек , где . Каждое блуждание продолжается до тех пор, пока отмеченная точка не будет достигнута. Эта отмеченная точка затем хранится на сервере вместе с соответствующим экспонентой и флагом, указывающим, какой был тип блуждания. Эти данные аналогичны множеству «ловушке» базового метода «кенгуру» Полларда [10] [12]. Когда в одну и ту же отмеченную точку приходят два блуждания различного типа, мы имеем столкновение «укрощенного» и «дикого» блужданий» , и это помогает решить ЗДЛ. Следует отметить, что действие алгоритма продолжается до решения ЗДЛ. Таким образом вероятность успешности равна 1.

Основное отличие алгоритма Годри-Шоста от алгоритма «кенгуру» в том, что при достижении отмеченной точки Годри и Шост возобновляют блуждание от случайной стартовой точки в определенном ряду, в то время как алгоритм «кенгуру» продолжает работать. Теоретический анализ также отличается: Годри и Шост используют вариант «парадокса дня рождения», в то время как Ван Ооршот и Винер используют различные вероятностные аргументы. (См. Приложение А).


Теоретический анализ

Давайте вспомним подробный анализ идеализированной версии (т.е., предпочитая использование действительного случайного блуждания, псевдослучайному блужданию) алгоритма Годри-Шоста [5]. Годри и Шост используют другой вариант «парадокса дня рождения», который мы назовем «парадоксом дня рождения со столкновением «укрощенный-дикий».

TemplateTheoremIcon.svg Теорема Теорема 1
Осуществляя случайную единообразную выборку из множества размера , с замещением, и попеременно записывая элементы, выбранные в двух различных множествах с последующим ожидаемым количеством выборов, которые необходимо сделать полностью до того, как у нас будет пересечение множеств, получаем .
Доказательство
Доказательства этой теоремы можно найти у Селиванова [21] или в [22] (что получается в качестве вывода из результатов работ Нишимуры и Сибуя [23]).


Для упрощения мы опустим компоненту во всех последовательных интервалах оперативного времени. Поскольку «укрощенные» точки лежат в , а «дикие» точки находятся в , столкновение между «укрощенными» и «дикими» точками может случится только в . Мы называем такое столкновение «укрощенное-дикое», и это аналогично пересечению множеств в Теореме 1, таким образом мы применяем Теорему 1 в случае, когда .


Рис. 1. Пересечение множеств и . Множества и представлены черными горизонтальными полосками, и затенение между ними показывает длину пересечения. В первом случае , а во втором -


Рисунок 1 показывает два случая . В первом случае для , таким образом, (в среднем случае). Во втором случае для , таким образом, (в худшем случае).

TemplateTheoremIcon.svg Теорема Теорема 2 (Годри-Шоста [5])
Пусть система обозначений останется, как было выше. Если из элементов осуществляется случайная единообразная выборка с попеременным замещением элементов из множеств T и W , то, ожидается, что число всех выборок, сверх всех частных случаев задачи, до возникновения коллизий «укрощенный-дикий», составляет .
Доказательство
Оперативное время алгоритма Годри-Шоста зависит от частного случая задачи , но, по законам симметрии, мы можем быть ограничены случаем . Мы записываем это как , где .

Пусть . Согласно Теореме 1 ожидается, что нам необходимо сделать выборку элементов (половину от каждого типа) от , чтобы определить столкновение. Для того, чтобы выбрать элементов в , когда единообразная выборка из предусматривает выбор

.

Этот же аргумент применим и к . Таким образом ожидаемое оперативное время алгоритма равняется групповых операций. Отметим, что это ожидаемое значение оперативного времени, всех выборов из случайных блужданий, для конкретного условия задачи. Среднее значение всех этих частных случаев задачи можно выразить как

.

Этот результат был приведен к с использованием меньших областей определения для и в [8].


Псевдослучайные блуждания и практические рекомендации

Годри и Шост представляют сведения в Теореме 2, но они также рассматривают практическое применение алгоритма. Во-первых, чтобы сократить память, нет необходимости записывать каждый элемент после выборки при псевдослучайном блуждании, а вместо этого надо использовать отмеченные точки. Если мы будем считать, что вероятность того, что элемент группы является отмеченной точкой, когда длина блужданий в среднем равна , то нам потребуется памяти примерно групповых элементов.

Во-вторых, необходимо использовать псевдослучайное блуждание, которое происходит достаточно близко к случайной единообразной выборке, к которой все еще применим парадокс «дня рождения со столкновением «укрощенный-дикий». Годри и Шост, как и в случае метода «кенгуру», говорят, что 32 подмножества и использование псевдослучайного блуждания, где каждый шаг – это умножение текущего элемента группы на , где это фиксированное малое положительное число, если текущий элемент группы лежит в i-м блоке разбиения. Наши алгоритмы будут непременно иметь случайные блуждания, когда шаги делаются в «поперечном» направлении, поскольку элемент группы как представитель класса эквивалентности может быть его обратной величиной, и шаг вправо от обратного элемента группы, то же самое, что и шаг влево от изначального элемента. Следовательно, хотя мы берем и каждый шаг умножается на , на практике блуждания выглядят, как прыжки . Отметим, что под мы подразумеваем числа и называем это средней абсолютной величиной шага. Для анализа следует вспомнить следующий исход (что средняя абсолютная величина шага в блуждании равна ).

TemplateLemmaIcon.svg Лемма «Лемма 1 ( Кофман, Флажолет, Флатто и Хофри [24]).»
Допустим что есть симметрическое случайное блуждание, которое начинается в начале координат и совершает шаги единообразно, распределившись в , тогда ожидаемая максимальная амплитуда равна
.


Среднее расстояние, покрываемое случайным блужданием из его начальной точки до момента, когда она достигнет отмеченной точки равняется . Для получения хороших случайных блужданий важно, чтобы это значение было достаточно велико, и каждое блуждание могло покрыть приемлемую относительную пропорцию в укрощенном или диком множестве. Если нет, то иначе блуждания остаются очень близко к их начальной точке, и вероятность столкновения двух блужданий очень мала. С другой стороны, когда велико, тогда имеется хорошая возможность того, что псевдослучайные блуждания иногда выйдут за пределы или . Шаги за пределы области исследования не могут быть включены в наш вероятностный анализ, и, таким образом, они сделаны «впустую». Чтобы уменьшить количество этих пустых шагов, необходимо начать блуждания внутри подмножества, образованного и . Более детальное описание того, как это сделать, дано в [25].

Мы же отсюда утверждаем следующий эвристический результат. Фактор принимает в расчет отрицательную «попытку» псевдослучайного блуждания вести себя как случайное блуждание, в частности, из-за воздействий на границы областей исследований.

TemplateLemmaIcon.svg Лемма «Эвристическое утверждение 1.»
Среднее ожидаемое оперативное время для алгоритма Годри-Шоста решения ЗДЛ в интервале размера равно групповых операций для некоторых малых величин >0


Мы отмечаем, что вывод Эвристического правила 1Эвристического правила 2 позже) весьма бессодержателен (например, разве результат = 1 “малая величина”?). Нам бы хотелось иметь возможность заместить на . Это может быть справедливо для Эвристического правила 1, но это выглядит неподходящим для Эвристического правила 2. Несомненно мы чувствуем, что может быть меньше, чем как в Правиле 1, так и в Правиле 2.

Стандартный алгоритм Годри-Шоста, следовательно, не так быстр, как версия ван Ооршота и Винера метода “Кенгуру» Полларда. Тем не менее, мы собираемся усовершенствовать их подход к группам с быстрой инверсией, чтоб получить более быстродействующий метод, чем какие-либо известные методы, основанные на методе «Кенгуру».

Классы эквивалентности

Следуя работе Галланта, Ламберта и Ванстоуна [15] а также Винера и Цуккерато [16] выглядит естественным рассматривать псевдослучайные блуждания на множестве классов эквивалентности. Для ЗДЛ в интервале это только дает видимость улучшения, когда класс эквивалентности является множеством групповых элементов, все дискретные логарифмы которых находятся в интервале. Группы с быстрой инверсией – неплохие кандидаты для этого.

Необходимо иметь возможность вычислять «уникальных представителей» класса эквивалентности так, чтобы можно было определить детерминированное псевдослучайное блуждание по классам эквивалентности. Например, рассмотрим группу точек на эллиптической кривой над полем с конечным числом элементов , где это нечетное простое число. Если допустим, что тогда число обратное это просто . Теперь нам необходимо правило, чтобы определить уникального представителя для каждого класса эквивалентности . В этом случае простое правило гласит: используйте y-координату как целое число и позвольте уникальному представителю быть . Тогда псевдослучайное блуждание определяется с использованием уникального представителя класса эквивалентности.

Если мы обозначаем элементы группы по их дискретным логарифмам и упорядочиваем их в интервале , тогда два элемента в классе эквивалентности равноудалены от центра интервала. Шаг вправо для одного представителя класса эквивалентности соответствует шагу влево для другого. Следовательно, при использовании классов эквивалентности нет возможности избежать «поперечных» блужданий. Это существенная причина, по которой стандартный метод «кенгуру» не может быть использован с классами эквивалентности.

Важным вопросом является то, что имеется опасность возникновения в блужданиях малых циклов. Этот феномен был отмечен Галлантом, Ламбертом и Ванстоуном [15], а также Виннером и Цуккерато [16]. Это может стать причиной того, что псевдослучайные блуждания никогда не достигнут выделенной точки. Метод, который позволяет обойти эту проблему называется «сжатием цикла», и его описание можно найти у Галланта, Ламберта и Ванстоуна [[15], Раздел 6]. Детальный анализ этих вопросов был представлен Босом, Клейнюнгом и Ленстрой [18].

Естественно будет попытаться применить алгоритм Годри-Шоста на классах эквивалентности, чтобы решить ЗДЛ в интервале размера .

Алгоритм Годри-Шоста на классах эквивалентности

Мы дали только краткий обзор метода, поскольку наша основная цель – это дальнейшее совершенствование его основной идеи. Вспомним, что мы намереваемся решить , где . Мы допускаем, что вычисление для любого в группе намного быстрее, чем операция с обычной группой.

При естественном подходе мы осуществляем естественные блуждания в множествах классов эквивалентности, соответствующих «укрощенным и диким» множествам стандартного метода Годри-Шоста. Другими словами, рационально сделать следующие определения.

TemplateDifinitionIcon.svg Определение «Определение 1.»
Сформулируем «укрощенное и дикое» множества как выражения
.


Отметим, что .

Как и прежде, наше основное внимание на . Когда мы имеем , а когда большая величина, то составляет только половину размера . Тем не менее, здесь проявляется тонкость, которой не было в предыдущем случае: когда и , имеется только один путь возникновения класса эквивалентности , но, когда малая величина, может быть два пути. Точнее говоря, предположим, что , тогда класс эквивалентности может возникнуть из и из (например, если тогда и таковы, что . Этот феномен означает, что алгоритм Годри-Шоста прослеживается в «диком» множестве неравномерно, и это значит, что мы не можем применить Теорему 1, чтобы определить ожидаемое оперативное время алгоритма. Более подробно мы объясним эти моменты в следующим разделе.

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

Новый алгоритм

Теперь мы представляем алгоритм для задачи дискретного логарифма в интервале для групп с эффективной инверсией. Как обычно, пусть и заданы так, что и . Основная идея в том, чтобы использовать алгоритм Годри-Шоста на множестве классов эквивалентности. Дальнейшее ускорение придается определением того, что «дикое» множество , в некотором смысле, меньше, чем «укрощенное» множество.

TemplateDifinitionIcon.svg Определение «Определение 2.»
Сформулируем «укрощенное и дикое множество» (в качестве множеств классов эквивалентности) как

где, как обычно .

В этом случае алгоритм становится быстродействующим. Можно производить выборку из и , используя псевдослучайные блуждания, которые хорошо определены в классах эквивалентности. Когда блуждание достигает отмеченной точки, мы сохраняем представителя классов эквивалентности, его дискретный логарифм (или дискретный логарифм элемента группы, поделенный на ), и «тип» блуждания. Когда тот же самый класс эквивалентов бывает достигнут блужданиями обоих типов, тогда дискретный логарифм считается решенным.

Для понимания алгоритма необходимо рассмотреть «основную область» для множеств. Другими словами, мы рассматриваем множества, которые точно соответствует множеству класса эквивалентности. Основная область для это ; ясно, что каждая пара соответствует точно одному значению . Один выбор основной области для is . Тем не менее, чтобы визуализировать мы действительно хотим, чтобы основная область для состояла только из положительных значений, и это не тот случай, когда . Следовательно, когда , мы отмечаем, что множество точно соответствует мультимножеству

Когда , единообразная выборка из соответствует единообразной выборке из мульти-множества , которая в свою очередь соответствует выборке с вероятностью для и вероятностью для . Мы описываем это утверждением, что в «диком» множестве существует «удвоенная плотность» блужданий.


Рис. 2. Множество показано в верхней части диаграммы в виде длинной черной полосы. Множества даны для значений и , где диагональные линии означают одинарную плотность, а перекрестная штриховка означает удвоенную плотность (т.е. повторение в мультимножестве)


Чтобы показать сложность алгоритма нам необходимо обобщение Теоремы 1. Это вариант парадокса дня рождения, который соответствует цветным шарикам и неоднородным вероятностям. Такой исход доказан в [20].


TemplateTheoremIcon.svg Теорема Теорема 3
Пусть и . Предположим, что мы имеем неограниченное количество шариков двух цветов (красных и синих) и урн. Мы попеременно выбираем шары каждого цвета и кладем их в случайные урны. Красные шары приписаны к урнам единообразно и независимо. Синие шары приписаны к урнам независимо со следующими вероятностями: урны используются с вероятностью , урны используются с вероятностью , и корзины используются с вероятностью 0. Тогда ожидаемое количество предписаний, которые необходимо сделать в целом, до того, как мы получим корзину, содержащую два шара одного цвета равно .
Доказательство
Обратимся к [20] для доказательства. Хотя относительно легко убедиться, что результат окажется справедливым: возможность того, что красный и синий шар попадут в одну и ту же урну равна
что примерно то же самое, что и вероятность, в случае, когда красные и синие шары распределены равномерно. Одним из значительных отличий от стандартного парадокса дня рождения «укрощенный-дикий» становится появление повышенного шанса для двух или более синих шаров быть помещенными в одну и ту же урну (и это имеет эффект снижения вероятности столкновения шаров различного цвета). Таким образом, Теорема 3 не выглядит тем, что она - незамедлительное последствие результатов в [23],[21].


TemplateTheoremIcon.svg Теорема Теорема 4
Если из элементов сделана единообразная случайная выборка с попеременным замещением из множеств и из Определения 2, то ожидание всех частных случаев задачи, для определенного числа выборов перед столкновением «укрощенный-дикий» описывается формулой
.
Доказательство
Пусть для . Благодаря симметрии нам нужно только рассмотреть положительную половину интервала экспонентов. Как мы видели, когда мы имеем и мы производим выборку в единообразно из укрощенных элементов и неединообразно из «диких» элементов. С другой стороны, когда тогда и в и в производится единообразная выборка, но в этом случае – строгое подмножество и в общем случае. Поэтому анализ разбивается на два случая.

В случае, когда , по Теореме 3 (принимая, что R имеет размер фундаментальной области для , которое равно ), ожидаемое количество групповых операций до получения столкновения равно .

В случае, когда можно увидеть, что (здесь под мы подразумеваем количество классов эквивалентности в пересечении) и мы оказываемся в ситуации очень похожей на ту, которую мы получаем при доказательстве Теоремы 2. Нам необходимо сделать выборку точек в (половина из них «укрощенные», а другая половина – «дикие»). Поскольку мы ожидаем, что сделаем выборку

Групповых элементов всего.

Теперь мы выводим среднее из всех частных случаев задачи, чтобы получить оперативное время для среднего случая.

.


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

TemplateLemmaIcon.svg Лемма «Эвристическое утверждение 2.»
Наш алгоритм решения ЗДЛ в интервале размера в группе с быстрой инверсией имеет ожидаемое операционное время среднего случая приблизительно равное групповых операций для некоторых малых величин > 0.


Как упоминалось ранее, мы считаем, что может быть взят меньшим, чем и наши экспериментальные результаты предполагают, что это справедливо.

Это стало значительным усовершенствованием стандартного алгоритма Годри-Шоста (Эвристическое утверждение 2), и был усовершенствован метод «кенгуру» Полларда с эвристическим оперативным временем равным групповых операций [26].

Экспериментальные результаты

Мы применили усовершенствованный алгоритм Годри-Шоста, используя классы эквивалентности для решения ЗДЛ в интервале, работая с пакетом программного обеспечения Magma. Используемой группой была группа точек на следующей эллиптической кривой

над

Где . Группа точек имеет кардинальное число

.

Мы выбрали различные размеры интервалов и провели ряд экспериментов на этих интервалах. Каждый эксперимент предполагал единообразный случайный выбор и решение ЗДЛ для . Мы сосчитали количество произведенных групповых операций и вывели среднее по итоговому количеству попыток. Не разрешалось запускать блуждания в пределах расстояния от края любого из множеств (приближенно это равно половине размера ожидаемого максимального расстояния, преодолеваемого блужданием).

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

Для обнаружения малых циклов мы сохранили 30 предыдущих групповых элементов в блуждании в случае, когда (соответственно, групповых элементов для ). Каждый новый шаг в блуждании был сравнен с предыдущими (соответственно, ) посещенных групповых элементов. Мы использовали детерминированный метод для «выпрыгивания» из цикла (используя прыжок определенной длины из других прыжков, используемых в псевдослучайном блуждании) так, что псевдослучайное блуждание в целом оставалось детерминированным. Стоимость поиска во множестве предыдущих групповых элементов не включена в наши экспериментальные результаты, но наш расчет групповых операций не исключает «пустые» шаги из цикла.

Мы прекратили блуждания, которые происходили во время шагов без прибытия в отмеченную точку (обычная рекомендация предусматривает шагов; см [11] ). Это предоставит нам время, немного отклоняющееся от оптимального оперативного времени.


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


Для улучшения этих экспериментальных результатов имеется много возможностей. Во-первых, [18] для управления циклами должны привести к улучшению работы над экспериментами усовершенствовали алгортм Годри-Шоста на классах эквивалентности. Во-вторых, отношения между значениями и возможно не оптимальны. Третье, можно получить лучшие результаты, не прибегая к использованию одного и того же количества «укрощенных» блужданий и «диких» блужданий или к незначительному изменению размеров областей «укрощенных и диких» блужданий.

Заключение

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

Приложение A. Краткая информация о методе «Кенгуру» Полларда

Сначала мы вспомним метод «Кенгуру» Полларда, в котором используются отмеченные точки так, как описано Ооршотом и Винером [11], а также Поллардом [12]. Система символов: Нам даны и и нам необходимо найти такие как .

Также, как и -метод, метод «кенгуру» полагается на псевдослучайные блуждания, хотя шаги в блуждании «кенгуру» соответствуют известным малым отрезкам в экспоненте (другими словами кенгуру делают небольшие прыжки). Укрощенный кенгуру стартует в середине интервала (т.е. на ) и прыгает вправо. Дикий кенгуру стартует из группы элементов и прыгает вправо, используя то же самое псевдослучайное блуждание. На серийном компьютере могут попеременно прыгать и укрощенные и дикие кенгуру. Время от времени укрощенный или дикий кенгуру приземляется на отмеченный элемент группы и это сохраняется в отсортированном списке, двоичном дереве или хешированной таблице вместе с его дискретным логарифмом (если кенгуру «укрощенный») или дискретным логарифмом (если кенгуру «дикий»). В тот момент, когда один и тот же элемент группы посещен разными кенгуру ЗДЛ считается решенной.

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

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

Приложение B. Двухмерные задачи

Можно рассмотреть и многомерные ЗДЛ: Дано и границы , чтобы вычислить такие, что и , где . Мы называем целое число измерением. Размер области решений составляет . Эта проблема возникает в ряде приложений. Например, Годри и Шост [5] используют алгоритм для решения двухмерных ЗДЛ в точке, рассчитывая на гиперэллиптические кривые второго типа.

Двухмерная ЗДЛ также возникает, если кто-либо пытается анализировать безопасность криптографии эллиптических кривых, используя метод Галланта-Ламберта-Ванстоуна (GLV [27]. В этом методе наблюдается эффективно просчитываемый групповой гомоморфизм и можно вычислить для и , как , где . Имеется алгоритм для вычисления пары из , но более естественно выбрать напрямую. Есть соблазн выбрать и немного меньшими, чем , и непрерывная величина, до которой это может быть сделано без потери безопасности, зависит от трудности двухмерной ЗДЛ. Годри и Шост не дают точного значения для оперативного времени этого алгоритма, но мы имеем следующее эвристическое утверждение под обычной аксиомой (см [25] для дальнейшего детального рассмотрения этого результата и усовершенствование константы от до ).


TemplateLemmaIcon.svg Лемма «Эвристическое утверждение 3.»
Алгоритм Годри-Шоста [5] решает двухмерную ЗДЛ за групповых операций для незначительных величин > 0.


Приложение B1. Решение с использованием классов эквивалентности

В группах с эффективно рассчитываемым обратным элементом (таких как группы интереса метода Годри-Шоста и метода GLV) можно рассматривать классы эквивалентов как мы делали в одномерных случаях. Для большей точности, пусть выражение

будет множеством класса эквивалентности точек в области имеющей центр 0. Для таких, что мы рассматриваем множество


Анализ алгоритма снова требует визуализации множеств через фундаментальную область. Поскольку карта образована поворотом на 180 градусов, естественной фундаментальной областью становится полуплоскость . Поэтому можно определить фундаментальную область для как

Отметим, что . Фундаментальная область для , которая содержится в может быть легко определена, но заметим, что как и в Разделе 4 это может быть мульти-множество и мы снова можем оказаться в случае неединообразной выборки в . Действительно, когда и есть этот случай и область, с удвоенной плотностью имеет площадь . Когда или в этом случае распределение по единообразно, но обычно больше не содержится в . В этих случаях варьируется в пределах и .

Мы рассматриваем алгоритм, в котором выбираются элементы из и единообразно и случайно, с выборкой элементов с отношением (то есть, вдвое больше прирученных блужданий, чем диких блужданий, поскольку прирученные блуждания вдвое больше, чем дикие блуждания).

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

Приложение B2. Более обширные классы эквивалентности в методе GLV

Теперь мы принимаем, что и что двухмерная исследуемая ЗДЛ выражена формулой с . Снова запишем . Поскольку известен по основанию достаточно вычислить и . Часто вместе с методом GLV [12] гомоморфизм удовлетворяет равенству . Это случается, например, со стандартной кривой над с . Это также включает гомоморфизм, используемый Галбрайтом, Лином и Скоттом [7]. В этой постановке проблемы можно рассмотреть классы эквивалентов размера 4.

Если , тогда 4 точки соответствуют парам экспонент

Таким образом, действие соответствует повороту на 90 градусов.

Выглядит естественным применить алгоритм Годри-Шоста к этим классам эквивалентов. Берем множества и аналогичные тем, что имеются в Разделе B1. Нахождение подходящей фундаментальной области для симметрии при повороте несложно (например, возьмем . Теперь можно определить, что некоторые области «дикого» множества имеют плотность, возведенную в квадрат (так же, как и одинарную и сдвоенную плотности).

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

Контакты авторов материала

  1. Mathematics Department, Auckland University, Auckland, New Zealand, E-mail: [1]
  2. Mathematics Department, Royal Holloway University of London, Egham, Surrey TW20 0EX, UK, E-mail: [2]

Выражение признательности

Мы благодарим анонимных рецензентов PKC 2010 и ASIACRYPT 2009 за ряд очень полезных комментариев.

Литература

  1. Gennaro, R.: An Improved Pseudo-random Generator Based on Discrete Log. In Bellare, M., ed.: CRYPTO 2000. LNCS, vol. 1880, pp. 469–481. Springer-Verlag (2000)
  2. Patel, S., Sundaram, G.: An Efficient Discrete Log Pseudo Random Generator. In Krawczyk, H., ed.: CRYPTO 1998. LNCS, vol. 1462, pp. 304–317. Springer-Verlag (1998)
  3. van Oorschot, P.C., Wiener, M.J.: On Diffie-Hellman Key Agreement with Short Exp onents. In Maurer, U., ed.: EUROCRYPT 1996. LNCS, vol. 1070, pp. 332–343. Springer-Verlag (1996)
  4. Boneh, D., Goh, E.J., Nissim, K.: Evaluating 2-DNF formulas on ciphertexts. In Kilian, J., ed.: TCC 2005. LNCS, vol. 3378, pp. 325–341. Springer (2005)
  5. 5,0 5,1 5,2 5,3 5,4 5,5 5,6 Gaudry, P., Schost, E.: A low-memory parallel version of Matsuo, Chao and Tsujii’s algorithm. In Buell, D.A., ed.: Proceedings of Algorithm Number Theory Symposium - ANTS VI. LNCS, vol. 3076, pp. 208–222. Springer-Verlag (2004)
  6. Cheon, J.H.: Security Analysis of the Strong Diffie-Hellman Problem. In Vaudenay, S., ed.: EUROCRYPT 2006. LNCS, vol. 4004, pp. 1–11, Springer-Verlag (2006)
  7. Jao, D., Yoshida, K.: Boneh-Boyen signatures and the Strong Diffie-Hellman problem. In Shacham, H., Waters, B., eds.: Pairing 2009. LNCS, vol. 5671, pp. 1–16. Springer-Verlag (2009)
  8. Gopalakrishnan, K., Th´eriault, N., Yao, C.Z.: Solving Discrete Logarithms from Partial Knowledge of the Key. In Srinathan, K., Rangan, C.P., Yung, M., eds.: INDOCRYPT 2007. LNCS, vol. 4859, pp. 224–237. Springer-Verlag (2007)
  9. Lim, C.H., Lee, P.J.: A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup. In Kaliski Jr., B.S., ed.: CRYPTO 1997. LNCS, vol. 1294, pp. 249–263. Springer-Verlag (1997)
  10. 10,0 10,1 10,2 Pollard, J.M.: Monte Carlo Methods for Index Computation mod p. Mathematics of Computation 32(143), 918–924 (1978)
  11. 11,0 11,1 11,2 11,3 van Oorschot, P.C., Wiener, M.J.: Parallel collision Search with Cryptanalytic Applications. Journal of Cryptology 12, 1–28 (1999)
  12. 12,0 12,1 12,2 Pollard, J.M.: Kangaroos, Monopoly and Discrete Logarithms. Journal of Cryptology 13, 437–447 (2000)
  13. Montenegro, R., Tetali, P.: How long does it take to catch a wild kangaroo? In: 41st ACM Symposium on Theory of Computing. (2009)
  14. 14,0 14,1 Gaudry, P., Harley, R.: Counting Points on Hyperelliptic Curves over Finite Fields. In Bosma, W., ed.: Proceedings of Algorithm Number Theory Symposium - ANTS IV. LNCS, vol. 1838, pp. 313–332. Springer-Verlag (2000)
  15. 15,0 15,1 15,2 15,3 Gallant, R., Lamb ert, R., Vanstone, S.: Improving the Parallelized Pollard Lamb da Search on Binary Anomalous Curves. Mathematics of Computation 69, 1699–1705 (2000)
  16. 16,0 16,1 16,2 Wiener, M.J., Zuccerato, R.J.: Faster Attacks on Elliptic Curve Cryptosystems. In Tavares, S.E., Meijer, H., eds.: Selected Areas in Cryptography. LNCS, vol. 1556, pp. 190–200. Springer-Verlag (1998)
  17. Duursma, I.M., Gaudry, P., Morain, F.: Sp eeding up the discrete log computation on curves with automorphisms. In Lam, K.Y., Okamoto E., Xing, C. ed.: ASIACRYPT 1999. LNCS, vol. 1716, pp. 103–121. Springer-Verlag (1999)
  18. 18,0 18,1 18,2 Bos, J.W., Kleinjung, T., Lenstra, A.K.: On the use of the negation map in the Pollard Rho metho d. preprint (2010)
  19. Cohen, H., Frey, G.: Handb o ok of Elliptic and Hyp erelliptic Curve Cryptography. Discrete Mathematics and its Applications. Chapman & Hall/CRC (2005)
  20. 20,0 20,1 20,2 Galbraith, S.D., Holmes, M.: A non-uniform birthday problem with applications to discrete logarithms. In preparation (2010)
  21. 21,0 21,1 Selivanov, B.I.: On waiting time in the scheme of random allocation of coloured particles. Discrete Math. Appl. 5(1), 73–82 (1995)
  22. Ruprai, R.S.: An improvement to the Gaudry-Schost algorithm for multidimensional discrete logarithm problems and applications. PhD Thesis, Royal Holloway, University of London (2010)
  23. 23,0 23,1 Nishimura, K., Sibuya, M.: Probability to meet in the middle. Journal of Cryptology 2, 13–22 (1990)
  24. Cofman, E.G., Fla jolet, P., Flatto, L., Hofri, M.: The Maximum of a Random Walk and its Application to Rectangle Packing. Technical rep ort, INRIA (1997)
  25. 25,0 25,1 Galbraith, S.D., Ruprai, R.S.: An improvement to the Gaudry-Schost algorithm for multidimensional discrete logarithm problems. In Parker, M.G., ed.: Cryptography and Co ding, 12th IMA International Conference. LNCS, vol. 5921, pp. 368–382. Springer (2009)
  26. Galbraith, S.D., Pollard, J.M., Ruprai, R.S.: Improving kangaro o and GaudrySchost metho ds for solving the DLP in an interval. In preparation (2010)
  27. Gallant, R.P., Lambert, R.J., Vanstone, S.A.: Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms. In Kilian, J., ed.: CRYPTO 2001. LNCS vol. 2139, pp. 190–200. Springer-Verlag (2001)