Статическая задачa Диффи-Хеллмана для эллиптических кривых над расширенными полями

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:31, 10 декабря 2015.
On the Static Diffie-Hellman Problem on Elliptic Curves over Extension Fields
AC2010 17.PNG
Авторы Robert Granger[@: 1]
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал


Аннотация. Мы показали, что для любой эллиптической кривой , если у злоумышленника есть доступ к оракулу, решающему задачу Диффи-Хеллмана (Статическая DHP), тогда выполняя запросов к оракулу статической DHP на фазе начальной инициализации, для фиксированных и злоумышленник может вычислить любое дальнейшее решение статистической DHP за эвристическое время . Предложенный нами метод к тому же решает DHP с задержкой цели, определённую Фриманом, и соответственно, может быть расширен до алгоритмов способных разрешить DLP с задержкой цели, дополнительной DHP и дополнительной DLP, изученных Коблицом и Менезесом в контексте якобиан гиперэллиптических кривых малого рода. Также утверждается, что для любой группы, в которой можно эффективно применить индекс вычисления, вышеуказанные задачи будут связаны соответствующими отношениями, разрешение которых будет всегда проще, чем для случая DLP. Хотя практически наш алгоритм уменьшает безопасность только при очень малых n для эллиптических кривых определённых над и предложенных Голбрайтом, Лином и Скоттом на EUROCRYPT 2009, его также можно применять для любого протокола, где пользователь выступает в роли прокси оракула Статистической DHP, либо для протоколов безопасность которых основывается на любой из вышеуказанных задач.

Введение

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

К примеру, в 2004 Браун и Галлант изучили статистическую задачу Диффи-Хеллмана (Статистическая DHP), в которой участник повторно использует одно и то же секретное значение Диффи-Хеллмана для нескольких ключевых соглашений [1]. Авторы доказали, что если установка взаимосвязи DLP для статического секрета является трудной задачей, то аналогично будет и для Статической DHP. Однако, при таком упрощении, естественно, получается алгоритм для решения DLP при том, что у злоумышленника есть доступ к Статическому оракулу DHP. В протоколах [2], [3] и [4], к примеру, пользователю в свою очередь вверяется роль прокси оракула статической DHP, что таким образом приводит к уязвимости данных систем к такой атаке. В наилучшем случае (с точки зрения злоумышленника) можно легко вычислить статический секрет Диффи-Хеллмана в группе порядка при помощи только запросов оракула статической DHP и групповых операций [1]. Для криптографически реализуемых эллиптических кривых, то есть тех, для которых универсальные атаки полностью изучены, этот результат сильно зависит от времени, требующемся для вычисления дискретных логарифмов, а именно . Таким образом, разрешение Статической DHP в данном случае остаётся сложной задачей, и тоже время мы имеем меньшую сложность, чем у наилучших DHP алгоритмов.

Коблиц и Менезес показали некоторые другие задачи, предоставив нашему вниманию очевидное схожее разделение[прим. 1] для DLP, в контексте якобиан гиперэллиптических кривых малого рода [5]; а именно, DHP с задержкой цели [6], DLP с задержкой цели [7], дополнительной DHP [8] и дополнительной DLP [9], [10]. Для каждой из этих задач используются запросы оракула, которые и создают эти разделения. К примеру, для DHP с задержкой цели можно непосредственно применить алгоритм Брауна-Галланта, поскольку действия злоумышленника позволяют получить доступ к оракулу статической DHP на стадии инициализации.

В 2006 Чеон получил аналог алгоритма Брауна-Галланта, когда требуемая информация была представлена в виде Стойкой Задачи Диффи-Хеллмана (Стойкая DHP) [11]. Чеон расширил эту атаку до использования делителей и , также как и в алгоритма Брауна-Галланта, в действительности оба алгоритма можно рассматривать как частные случаи известного преобразования DLP в DHP, предложенного Боером, Маурером, Вулфом и др. (см. [12] для подробного описания), но при ограниченном доступе к DHP оракулу. Что характерно, алгоритм взлома Чеона Стойкого DHP не заключается в выявлении каких-либо слабостей протоколов, так как сокращения доказательств безопасности лишь показывает выбор ложной направленности действий, то есть авторы показали, что взлом системы позволяет решить Стойкую DHP, но не наоборот. Следовательно, если найден алгоритм, который эффективно решает стойкую DHP, то, посколько все доказательства безопасности, составляющие общую стойкость, не предоставляют более какие-либо гарантии по безопасности, схожий подход не будет результативным для какой-либо другой взаимосвязанной системы. Для случая с подписью Бонеха-Боена [13], основывающейся на стойкой DHP аналогичным образом, Джао и Йошида задали сокращение обратного характера, таким образом усилив стойкость доказательства безопасности для этих подписей и в тоже время предоставив реализуемую атаку на схему со сложностью , если , то допускается выполнение запросов подписи [14]. Этот результат подразумевает под собой то, что если можно установить равенство между заданным протоколом и задачей представляющей вероятное разделение стойкости для DLP, тогда для некоторых моделей атак значение параметра безопасности, представляемое этими аргументами, будет, вероятнее всего, меньше, чем изначальное у DLP.

Аналогичным образом для задачи RSA, в 2007 Джоукс, Накаче и Том показали, что при помощи первоначального субэкспоненциального доступа к корню оракула, злоумышленник может впоследствии вычислить этот корень для любого элемента со сложностью меньшей чем требуется для факторизации модуля [15]. Этот алгоритм затем был модифицирован для решения статических DHP с оракулом в конечных полях [16] с аналогичными улучшениями эффективности, демонстрирующими вероятное разделение стойкости в данном случае.

Естественно, возникает вопрос, поможет ли первоначальный доступ к статическому DHP оракулу решать последующие значения статический DHP быстрее, чем в случае с DLP, в контексте эллиптических кривых? Как упоминалось ранее, в наилучшем случае алгоритму Брауна-Галланта-Чеона требуется запросов оракула и групп операций. Однако, для эллиптических кривых определённых над расширенными полями мы получили алгоритм, которому для фиксированного и требуется запросов оракула, и который имеет эвристическую временную сложность . Из сравнения нашего алгоритма с лучшим из ныне известных DLP алгоритмов для этих кривых со сложностью [17] следует, что предложенный нами вариант будет работать быстрее на значение, взятое в квадратный корень, чем DLP при увеличении . Отметим, что для n = 2 наша сложность будет такой же, как и для наиболее благоприятного случая сложности алгоритма Брауна-Галланта-Чеона, но применимо к эллиптическим кривым над , и не только к тем, у которых соответствующие делители будут при , наш результат будет лучшим. Также мы представили эвристический субэкспоненциальный алгоритм статической DHP с оракулом для эллиптических кривых над специальным семейством расширенных полей.

Предложенный нами метод можно, соответственно, расширить для представления алгоритмов, решающих четыре задачи, исследованные Коблицом и Менезесом в [5]. В данной работе было установлено, что отношения между стойкостью этих задач не оказались такими как прежде предполагалось (см. [18],[19]]). Мы исправили некоторую часть анализа и определили, что в контексте любой группы, в которой индекс исчисления является эффективным, то есть тем, которым реализуется в конечном счёте наилучший алгоритм для решения заданных задач – что включает в себя якобианы гиперэллиптических кривых и эллиптические кривые над расширенными полями – вышеупомянутые задачи действительно имеют соответствующие отношения, причём всегда более простые чем для случая DLP (это утверждение естественно применимо только по отношению к текущему состоянию вопроса по алгоритмам с индексом исчисления). Однако, основное заключение [5], а именно, возможность оценки какие конкретно гарантии безопасности обеспечиваются доказательствами безопасности при интерактивной работе алгоритма или при наличии сложных входных значений является сложной задачей, при этом выполнимо.

В связи с тем, что неявная константа по отношению к сложности нашего алгоритма растёт очень быстро по , практическая реализация возможно только для малых значений , а именно, = 2, 3 или 4 (и других при условии что делится на 2, 3 или 4). Однако, исходя из временной оценки, вытекающей из реализации компонентов атаки, безопасность, обеспечиваемая эллиптическими кривыми определёнными над и предложенными Голбрайтом, Лином и Скоттом на EUROCRYPT 2009, будет значительно меньшей, если эти кривые будут использоваться в протоколе где пользователь выступает в роли прокси оракула статической DHP, или если они используются в протоколах, безопасность которых основывается на задачах рассмотренных в [5].

Независимо от данной работы, Джукс и Витсе [20] представили аналогичную основу алгоритма, показанного здесь, для статической DHP с оракулом, а именно, Эвристический Результат 1. Хотя Джукс и Витсе не рассмотрели наш основной факторизационный метод сокращения, приводящий к получению Эвристического Результата 2, их основная идея лучше относительно метода Гаудри нахождения отношения – который используется в данной работе – позволяя находить соотношения для эллиптических кривых над полями расширения пятой степени, которые на текущий момент нецелесообразно применять для метода Гаудри.

Одной из целей нашей работы была оценка воздействия алгоритмов представленных здесь по отношению к статической DHP с оракулом для известных групп 3 и 4 Оукли, которые являются частью набора IPSEC протоколов [21] (см. параграф 4 и 5), и которые определены над полями расширения пятой степени с характеристическим значением 2. Отметим, из наших результатов, насколько проще происходит нахождение отношений для характеристического значения 2, чем для большого простого характеристического значения, автор данной работы связался с авторами [20] для того, чтобы применить их идею для этих кривых. Используя результаты этой работы и [20], мы недавно опубликовали экспериментальную проверку возможного решения статической DHP с оракулом на 152-битной группе 3 кривой [7] над полем , которую уже давно полагают слабой с точки зрения стойкости, но которая в тоже время, до текущего момента, могла противостоять многим атакам [22],[23],[24], [25].

Последующий материал организован следующим образом. В пункте 2 мы опишем статическую DHP. В пункте 3 мы обоснуем нашу главную идею, представим наш основной алгоритм, и проанализируем его основные асимптотические варианты. Затем в разделе 4 мы выявим кривые, представленные в различных работах, к которым успешно применима наша атака. В пункте 5 мы дадим полный обзор нашей экспериментальной реализации 128-битного уровня безопасности для расширенных степеней = 2, 3, 4 и 5, над большим простым полем и полем с характеристическим значением 2, оценивая из воздействие на вышеуказанные кривые и кривую группы 3 Оукли. В 6 пункте мы представим алгоритмы для трёх других задач, имеющих место в криптографических протоколах, и проанализируем их воздействие, а также сделаем некоторые заключительные замечания по этому поводу.

Статическая задача Диффи-Хеллмана

Пусть есть циклическая группа простого порядка , а это фиксированный генератор . Классическая задача Диффи-Хеллмана в может быть сформулирована следующим образом[26]:

Задача 1. (DHP): Для заданного и случайного и , найдем .

Процесс согласования ключей Диффи-Хеллмана (DH) между двумя участниками происходит таким образом, что Алиса выбирает случайное секретное значение и вычисляет , а Боб выбирает в свою очередь случайное секретное значение и вычисляет , затем оба участника обмениваются этими значениями. После получения каждой из сторон вычисляется общий секрет путём возведения группового элемента другого участника в степень, эквивалентную значению своего секрета. Основное условие безопасности процесса согласования ключа DH заключается в том, чтобы DHP была достаточно стойкой. Если Алиса по какой-либо причине неоднократно использует то же секретное значение, скажем , то результирующий набор вариаций задачи DHP сформирует малое подмножество всех возможных случаев будущих значений DHP, и таким образом окончательно нельзя утвердительно сказать, что эти получающиеся решения задачи будут достаточно стойкими, даже при том условии что изначально DHP обладала требуемой стойкостью. Эта задача должна быть рассмотрена как статическая DHP , которую мы определим следующим образом:

Задача 2. (Статическая DHP ): Для заданного и , и случайного , найдем .

Заметим, что в данной ситуации возникает необходимость не только наличия эффективной методики в процессе многостороннего DH согласования ключа – Алисе необходимо только вычислить единожды и затем повторно использовать это значение для многостороннего согласования ключей, – но к тому же и применения шифрования Эль-Гамаля [2], поиска ключа Форда-Калиски [3], а также неоспоримой подписи Чаум-Ван Антверпена [4]. Как указывалось в параграфе 1, Браун и Галлант показали, что если соответствующая DHP является стойкой, то таковой же является и статическая DHP [1]. Однако в трёх вышеупомянутых протоколах один из участников структуры системы выступает в роли статического DHP оракула, таким образом преобразуя сокращение Брауна-Галланта в вероятную атаку.

Как и в [1] определим оракул для решения статической DHP следующим образом:

TemplateDifinitionIcon.svg Определение «Определение 1»
(Статический DHP оракул). Пусть будет циклической группой простого порядка , записанной аддитивно. Для фиксированного базового элемента и фиксированного элемента пусть будет таким, что . Тогда статический DHP оракул (относительно ) вычисляет функцию определённую как:
.

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

Алгоритм статической DHP с оракулом для Алгоритм статической DHP с оракулом для E ( F q n ) {\displaystyle \mathrm {E} (\mathbb {F} {q^{n}})}

В данном разделе мы детально изложили и представили наш алгоритм для решения статической DHP с оракулом в заданном контексте.

Ключевое наблюдение в [15] заключается в том, что если можно определить подходящую «базу факторизации» в рассматриваемой группе, то есть относительно небольшое подмножество элементов группы, для которых не малая доля всех элементов группы «факторизуется», через групповые операции, тогда возможно решить статическую DHP с входным значением переменного группового элемента, учитывая, что известны действия статического DHP оракула только для факторизованных основных элементов. Это следует из утверждения, что если в аддитивно записанной группе мы имеем , c в некоторой базовой факторизации , тогда

.

Отметим, что если переменный групповой элемент не представим для базовой факторизации, то при добавлении случайного элемента (или любой его линейной комбинации) к и проверке возможности представления, можно получить элемент , факторизуемый над , позволяющий решить изначальную статическую DHP. Поэтому хорошая базовая факторизация, при которой не малая доля всех элементов группы представима, совместно с процессом рандомизации, позволяет решить статическую DHP для переменных групповых элементов. Заметим, что для статической DHP с оракулом не требуется знание для того, чтобы вычислить умножение на переменный элемент , то есть тем самым можно решить статическую DHP без решения соответствующей DHP. Это связано с тем, что требуемая информация выявляется через запросы оракула статической DHP, что в свою очередь позволяет проще решить DHP, используя вышеуказанную методику, чем это будет в случае с , для которой нет такой информации. Эта идея является основной в работах [16] и [5].

Когда является мультипликативной группой конечного поля, задача заключающаяся в том, как лучше всего построить факторизационную базу и как представить переменные элементы над этой факторизационной базой, подробно описана в [27],[28],[16]. Для конечных полей существует соответствующее понятие размерности элементов или эквивалентной нормы, заданной либо абсолютным значением элемента для простых полей, или степенью элемента для расширенных полей, либо комбинацией обоих в зависимости от используемого алгоритма для генерации мультипликативных отношений. Данная норма подразумевает под собой понятие гладкости для группы и таких элементов, при этом малая норма создаёт больше групповых элементов, чем большая, из чего следует, что наилучшим выбором для факторизационной базы будет случай с нормой имеющей некую ограниченность.

В контексте эллиптических кривых над простыми полями, неприменимо ни понятие нормы, что позволяет произвести выбор факторизационной базы, которая будет генерировать в свою очередь большую долю групповых элементов, чем в любом другом случае, ни способ выборки факторизованных элементов. Именно эта проблема и мешает созданию соответствующего алгоритма индексного исчисления для расчёта дискретных логарифмов таких кривых [прим. 2], из-за чего они являются столь предпочтительными с точки зрения безопасности.

Для эллиптических кривых над расширенными полями всё обстоит по-другому. Для методики «Вейла» [29],[23],[30] была успешно доказана возможность решения, а также ослабления стойкости DHP в некоторых случаях, что связано с отображением в общую большую группу, которая хоть и обладает соответствующей факторизационной базой, но не даёт возможности произвести необходимые статические DHP запросы на прообразы элементов факторизационной базы, поскольку в общем случае данные прообразы не существуют. Но тем не менее существует некое понятие ослабления стойкости для данных эллиптических кривых, нашедшее отражение в работе Гаудри [17].


Суть метода Гаудри

Идя по стопам Самаева [31] и изучая его актуальную идею, в 2004[прим. 3] Гаудри показал как определить применимую факторизационную базу для , для которой элементы могут быть «факторизованы», или точнее говоря разложены, что приводит к получению алгоритма индексного исчисления для расчёта логарифмов над этими кривыми [17]. Для фиксированного и , алгоритм имеет эвристическую сложность , что в свою очередь быстрее, чем сложность его аналога представленного Пролардом . Начнём пожалуй с записи суммарного значения полиномов Самаева [31].

TemplateDifinitionIcon.svg Определение «Определение 2»
Для пусть будет эллиптической кривой определённой над уравнением . Суммарное значение полиномов из будет определяться следующей повторным вычислением, с начальными значениями для и , заданных , и
,

а для и ,

.

Хоть определение может показаться неявным, Самаев привёл вышеуказанную формулировку посредством утверждения, что удовлетворяет следующему свойству, которое соотносит и по закону сложения.

TemplateTheoremIcon.svg Теорема Теорема 1
(Самаев [31]). Пусть E есть эллиптическая кривая над полем и это n-ый суммарный полином. Пусть будут элементами алгебраического замыкания из . Значит тогда и только тогда, когда существует n-кортеж элементов в таких, что для всех является точкой на и
.
Доказательство

Без доказательства.

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

.

В силу симметрии можно эвристически предположить, что для набора точек , и и при нахождении разделённых точек (приблизительный размер базовой факторизации) есть возможность получения их логарифмов относительно P путём исключения распределённой линейной алгебры, сложность которой . Нахождение логарифма переменного группового элемента таким образом становиться более лёгкой задачей. Поэтому, если нахождение малых корней (1) возможно, то для фиксированных и этот алгоритм будет работать быстрее, чем алгоритм Полларда.

К несчастью, нахождение таких малых корней не менее чем для двух переменных [32] является довольно сложной задачей. Основной идеей Гаудри было исследовать эллиптические кривые над , при этом, если используется база факторизации состоящая из точек с абсциссой в базовом поле , то предполагаемое поле, определяющее кривую, будет , а ограничение Вейла скалярного уравнения (1) из к преобразует алгебраическую систему уравнений в систему с неизвестными над , которая в свою очередь практически всегда будет нулевой размерности и разрешима с помощью теории исключения [17]. Отметим, что благодаря вышеуказанному способу элементы базы факторизации не сформируют подгруппу. Используя «изменение двойного большого простого значения» [33] это приводит к DHP алгоритму со сложностью . Теперь мы готовы представить вашему вниманию основополагающую версию нашего алгоритма, в которой мы детально показали как работает метод ограничения Вейла.

Основной алгоритм статической DHP с оракулом

Пусть это эллиптическая кривая, поле определения которой есть . Определим базовую факторизацию как у Гаудри [17] и получим:

.

По эвристическим соображениям ожидается, что , см. [17]. Для каждого мы можем произвести запрос оракула к статическому DHP оракулу для того, чтобы . Для переменной точки , нашей целью будет найти . Запишем как сумму элементов из , то есть:

.

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

. (2)

Отметим, что выражение в левой части уравнения (2) включает в себя определённые коэффициенты кривой , абсцисс , все из которых находятся в . Установим полиномиальный базис для расширения . Для каждого из коэффициентов степени должны равняться нулю. Так как каждая из абсцисс находится в , уравнение (2) определяет различные уравнения с неизвестными над , которые решаются через вычисление базиса Грёбнера, см. пункт 3.3. Если решение системы (2), тогда необходимо вычислить все возможных комбинаций при соответствующих координатах для того, чтобы найти нужную комбинацию сумма которой будет . Затем решение для статической DHP при находится из:

,

где все значения справа уже известны посредством запросов оракула для .

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

,

откуда следует, что

,

где опять же все значения справа уже известны. Следовательно наш пример статической DHP решен.

Более детальные рассуждения по данному вопросу

Сперва оговоримся, что вышеуказанный алгоритм и его обсуждения здесь полностью являются эвристическими; однако, мы полагаем, что алгоритм и сложность можно вполне строго определить используя результаты Диема [34] [35], что можно увидеть в пункте 3.4.

Уточним ещё один момент – который является основополагающим для сложности данного алгоритма – он заключается в том, что по сравнению с DLP здесь нет исключения линейной алгебры, так как ищется только одно соотношение. Таким образом, когда стадия инициализации запросов оракула завершена, сложность алгоритма зависит от задачи, вычисляющей одно отношение. В следствие чего мы как раз проанализируем её. Для суммарные полиномы Семаева симметричны и будут со степенью для каждой переменной. Следовательно уравнение (2) будет со степенью для каждой переменной. Для того чтобы значительно упростить систему, необходимо выразить в виде элементарных симметричных функций с переменными . Исходя из этого получим систему уравнений из неизвестных , каждая из которых опять таки будет в степени, ограниченной для каждой переменной. Для того чтобы решить эту систему, мы выполним расчёт базиса Грёбнера. На практике наши эксперименты (см. параграф 5) показали, что базис Грёбнера, так называемое лексикографическое упорядочение, всегда удовлетворяет лемме формы [36] , [37], то есть представляется в следующем виде:

, (3)

где одномерный полином в для каждого . В общем случае, степень одномерного полинома в , который мы получили, будет и действительно, в наших экспериментах это подтверждается. Сложность алгоритма Фаугере F4 [38] при вычислении такого базиса будет не меньше

Поскольку идёт двойное возведение в степень , то алгоритм практически реализуем только для очень малых значений . Однако для фиксированного и полином будет рассчитываться при . Для определения наличия корней системы , выполняется линейная факторизация одномерного полинома , используя вычисление наибольшего общего делителя с последующим использованием алгоритма Кантора-Цассенхауза и заменой каждого корня в - , для того, чтобы найти . Для каждого такого вектора из корни необходимо проверить, будет ли возможность разбиения многочлена

(4)

над . Если такая возможность есть, то эти корни будут точками абсцисс в , и будет существовать линейная комбинация

(5)

с , сумма которых равна . Этот шаг также полиномиален в .

В среднем необходимо выполнение таких разложений для того, чтобы найти необходимое отношение. Поэтому сложность нашего основного алгоритма статической DHP для фиксированного и будет полиномиальна в . Это даёт нам следующий эвристический результат.

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

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

Балансировка стоимости фаз Настройки и Ознакомления

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

,

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

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

Отметим, что нет возможности (и необходимости) для рассмотрения так называемых больших простых значений, то есть тех, абсцисса которых лежит в , но не в , поскольку нету шага линейного алгебраического исключения для простого отношения. Если мы сравним вышеуказанную сложность с полученной Гаудри для DLP, а именно , которая использует удвоенные большие простые значения, то увидим, что наш алгоритм для решения статической DHP на квадратный корень быстрее с увеличением . Интуитивно, это различие в сложности вызвано отсутствием шага линейной алгебры в решении статической DHP. Заметим, что Дием предложил более строгий алгоритм, который в сущности эквивалентен алгоритму Гаудри описанному выше [34], который для фиксированного решает DLP для любой эллиптической кривой над за доказанное соответствующее время . Мы полагаем, что этого можно избежать, если суметь преобразовать два эвристических результата в теорему, но это не является целью данной работы, и поэтому мы не исследуем данный вопрос здесь. Отметим, что на практике ограничивающим фактором являются не разложения, а запросы оракула, так как они обычно производятся на одном сервере, тогда как выполнение разложений можно легко распределить. Таким образом можно сократить число таких запросов в пределах необходимой границы за счёт необходимости выполнения большего количества разложений. Такой компромисс легко оптимизируется, в зависимости от вычислительных возможностей, но тем не менее требует экспоненциального количества запросов оракула, для фиксированного и . Теперь мы рассмотрим как и когда количество запросов оракула можно сделать субэкспоненциальным при данной размерности группы.

Субэкспоненциальный алгоритм статической DHP с оракулом

Дием также доказал следующий результат [35]. При и полагая, что , DLP над любой эллиптической кривой можно решить за соответствующее время . Таким образом, для семейства конечных полей, DLP любой эллиптической кривой можно решить используя соответствующий алгоритм субэкспоненциального индексного исчисления.

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

Потенциально уязвимые кривые

На EUROCRYPT 2009 Голбрайт, Лин и Скотт предложили использовать специальные эллиптические кривые над и [39], которые обладают эффективно вычислимыми гомоморфизмами, что позволяет реализовать более эффективную версию метода умножения точек Галланта-Ламберта-Ванстоуна [8]. Помимо того, что метод ускорения бита Полларда применим к данным кривым, они также подвержены атакам GHS [23] и Гаудри [17], в связи с чем сделаны соответствующие рекомендации к их применению. В частности, для кривых над быстрее всего будет реализация атаки Полларда, и таким образом эти кривые как правило обеспечивают должный уровень безопасности. Для кривых над полем , относительно последних атак, рекомендуют для достижения 128-битной безопасности использовать 80-битные простые значения, а не 60-битные, хотя известно, что это довольно опрометчивый выбор так как алгоритму Гаудри требуется ресурсоёмкие вычисления, и поэтому будут использоваться меньшие простые значения. Та же самая ситуация и с методом точечного умножения GLS Ханкерсона, Карабина и Менезеса над бинарным полем вида [40]. Что касается нашей атаки, единственной потенциальной слабостью в данном случае будут соответствующие кривые над согласно атаке Брауна-Галланта-Чеона. В наилучшем случае (с точки зрения злоумышленника) порядок группы должен делиться на целое значение , тогда секретное значение d статической DHP можно вычислить за время . Такое состояние легко избежать, если на него обратить внимание. Для кривых рассмотренных в [40] метод Виела проанализирован и показано, что доля восприимчивых к нему кривых незначительна, и его можно доказуемо избежать при дальнейших вычислениях.

Для кривых над наша атака будет иметь сложность , что значительно быстрее атаки Гаудри на DLP, сложность которой . Опять же, полагая, что точки разложения могут быть выполнены эффективно, кривые над расширенными полями степени 4 также уязвимы.

Также вызывают интерес определённые кривые, которые до текущего момента рассматривались как часть протокола разделения ключа Оакли, часть IPSEC. Ими являются группы 3 и 4 [21], в которых эллиптические кривые определены над полями и , которые были целью для многих атак, реализуемых с помощью метода Веила [[22],[23],[24],[25]], с момента их создания.

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

Мы реализовали наш алгоритм статической DHP с оракулом, используя систему вычислительной алгебры MAGMA [41] (V2.16-5), которая работает на Intel Xeon 3.16GHz с 32G памяти. При этом было рассмотрено два набора кривых. Первый набор состоит из четырёх случайно выбранных кривых простого порядка, каждая из которых длинной 256 бит, для полей формы и см. пункт 5.1 и 5.2. Эти кривые выбирались для того, чтобы измерить насколько уязвимы кривые, представленные в [39], относительно нашего алгоритма. Также мы представили оценки решения DLP на этих кривых используя актуальные на данный момент алгоритмы Полларда. Второй же набор состоит из четырёх случайно выбранных кривых порядка с в качестве длинны равной 256 над бинарными полями , для и , а должно быть наиболее приближенным к 256. Причина реализации атаки именно на эти кривые была двоякой: во-первых, оценить безопасность кривых представленных в [40] и, во-вторых, сравнить эффективность атаки для случая простого поля с оценкой предположительно трудно взламываемой статической DHP с оракулом на кривых Оакли, которые мы показали в пункте 5.3.

Хотя наша реализация в MAGMA не совсем оптимальна, нашей целью в данном случае было выявить доказательство теоретической реализации и дать действительную оценку тому, что может произойти на практике. Наши результаты раскрывают верхнюю границу для требуемого времени на решение статической DHP с оракулом для каждого из случаев. С учётом оптимизированной низкоуровневой реализации наша атака может выполняться значительно быстрее, чем в примерах приведённых для работы [7].

Большое простое характеристическое значение

Для каждого и используем кривые вида

,

где и случайно выбранные элементы из , такие, что # является простым и имеет длину 256 бит. Для мы вычислили симметричные полиномы суммы соответственно, и все экспериментальные вычисления были произведены за 2 часа. Для вычисления , нам, ко всеобщему удивлению, не хватило памяти, из-за чего пришлось независимо получать симметрические значения двух полиномов, которые в последствие использовались в результирующем вычислении для уменьшения количества значений, и заменять на частично симметричную версию . Можно выделять элементарные симметрические полиномы из этих двух независимых наборов надлежащим образом, рекомбинируя их. Однако, результирующий вычислительный базис Грёбнера окончательно исчерпал выделенную память таким образом сделав невозможным вычисления экспериментов. Без точного представления о том, сколько потребуется памяти вычислительному базису Грёбнера мы считаем нецелесообразным нахождение отношений для кривых над этими полями в настоящее время. Отметим, однако, что для простых базисных полей, использование расширенных полей пятой степени на данный момент, насколько нам известно, не нашло отражения в криптографической литературе по эллиптическим кривым. Поэтому в Таблицу 1 были включены лишь результаты для .

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

Таблица 1. Данные тестирования и разделения точек для эллиптических кривых над расширенными полями. Время показано в секундах.

# # T(GB) T (Корней)
2 128 13 5 0.001 0.009
3 85.3 439 43 0.029 0.027
4 64 54777 1100 5363 3.68

В соответствии с пунктом 3.3, последний из них включает в себя факторизацию полинома первой степени и затем заменяет корни на оставшиеся полиномы в уравнении (3). Это следует из рассинхронизации факторизации (уравнение (4)) и затем вычисления верной линейной комбинации базовых элементов факторизации как суммы (уравнение (5)).

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

Для в силу более значительных затрат на вычисление, мы показали время только для одного точечного входного значения; заметим, что входная система для вычисления базиса Грёбнера всегда будет одинаковой формы, но с разными коэффициентами, и следовательно, можно ожидать что эта часть вычислений будет в общем случае последовательна. Что касается времени нахождения корня, три этапа описанных выше занимают 3.68 сек, 0.00 сек и 0.04 сек соответственно, и таким образом, определяя основной влияющий на затраты по времени этап начальной факторизации, который необходим в любом случае, будут ли входные значения разбиваться или нет. Из чего следует, что средней оценкой по времени равномерно выбранных входных точек будет сек, поскольку одна точка разбивается с вероятностью .

Верхние границы на время атаки

Из данных в Таблице 1 и времени, требующемся для вычисления скалярного умножения, можно рассчитать верхнюю границу требуемого времени для выполнения атаки в пункте 3.4. Установка , и минимизация являются балансировкой двух этапов данной атаки, а именно, этапа посылки запросов оракулом, и этапа нахождения отношения. Мы не учитываем затраты на построение базовой факторизации, так как в ней участвует только лишь малое число операций поля и символьных вычислений Лежандра. Более точное формулировка 3.4 приводит нас к следующему уравнению:

,

где T(scalar) определяет среднее значение требуемых ресурсов на скалярное умножение. В нашей реализации последнее значение будет приблизительно 0.008 сек, 0.011 сек и 0.012 сек для кривых определённых над , соответственно.

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


Таблица 2. Оценка времени атаки для нашей реализации. Время приведено в секундах.

n Наше время атаки Вр. атаки Полларда
2 0.6701 (2/3)
3 0.7645 (3/4)
4 0.8730 (4/5)

Оценка атаки Полларда по времени выявляется как групповых операций, где затраты на групповую операцию определяются с помощью T(scalar) указанного выше, предполагающего взаимодействие алгоритмов удвоения и сложения. Мы также рассмотрели возможное увеличение быстродействия путём выполнения случайных преобразований над точками эквивалентного класса [42] [43], где набор таких точек для заданной точки считается эквивалентным, а есть гомоморфизм из [39]. Эти результаты для трёх выбранных кривых выявили идентичное значение параметра безопасности.

Для метода Полларда, однако, в данных условиях не был найден наилучший асимптотический DLP алгоритм. В данном основном индексном исчислении можно найти отношения с линейной алгеброй и затратами . Предполагая, что затраты на разделение довольно малы, можно уменьшить размер базовой факторизации для балансировки затрат на два этапа до , что соответствует методу Харли. В добавление хочется отметить, что здесь используются единичные и удвоенные большие простые переменные [[44],[33]], что приводит к сложностям и , соответственно.

Наша реализация позволяет определить верхние границы времени атаки для каждого из этих подходов, и, следовательно, показывает какого размера следует выбирать для обеспечения 128-битной безопасности, для каждого , в условиях нашей атаки. Этот уровень безопасности будет соответствовать значению требуемого времени для вычисления базовых операций группы. Отметим, что в случае с удвоенными большими простыми переменными, в наиболее актуальном примере когда число требуемых отношений будет . Для нашей же реализации разделения, время для этапа генерации отношений равно , что в свою очередь сопоставимо с методом Полларда. Следовательно, для этого уровня безопасности, значение 64 бита будет достаточным. Однако, в оптимизированной реализации время разделения можно увеличить, при этом необходимо увеличить и соответственно для компенсации. Более того, для баланса двух этапов данного алгоритма необходимо незначительно, но всё же увеличить размер базы факторизации. Это означает, что хотя наша реализация и позволяет оценить верхнюю границу времени атаки, но то, как выбрать приемлемый размер для обеспечения требуемой безопасности эллиптических кривых над расширенными полями остаётся открытым вопросом.

Характеристическое значение 2

Для каждого и используем кривые вида

,

где случайно выбранный элемент такой, что # является умноженным на четыре простым значением длинны 256. Отметим, что (6) есть форма кривых Оакли [21]. Также заметим, что базовые поля в каждом случае не обязательно будут обладать простой расширенной степенью над . Поскольку нашей целью было сравнение эффективности характеристического значения для полей заданного размера с аналогичными, но уже для меньшей расширенной степени, мы не учитывали любую возможную слабую сторону относительно метода Веила для данных примеров кривых. Для этих кривых суммарные полиномы, на удивление, просты, что делает их вычисление лёгкой задачей, что не скажешь в случае с простыми базовыми полями. Можно заметить, что результатом будет размер , а их симметричные значения будут меньше, чем до этого, что способствует более быстрому вычислению базиса Грёбнера для . Как в случае для простых базовых полей, для также имела место нехватка памяти для вычисления разделения использующегося в методе Гаудри. Однако, как было сказано в параграфе 1 и утверждалось в [7], можно попытаться записать случайную точку на кривой как сумму четырёх факторизационных базисных элемента [20] для того, чтобы выявить требуемое разделение, что приводит к уменьшению вероятности от до . Как и в методе разделения Гаудри, данный метод быстрее при характеристическом значении 2 чем при характеристическом значении в виде большого простого числа. Таким образом для группы 3 кривой Оакли актуальна статическая DHP задача с оракулом. Но можно ли это расширить до использования для Группы 4 кривой Оакли остаётся неизвестным и требует дальнейшего исследования. Для время требуемое для скалярного умножения будет 0.014 сек. Таблица 3 детально показывает результаты метода разделения Гаудри, а последнем столбце приведены для сравнения результаты из [7] для кривой Групы 3 Оакли.

Таблица 3. Данные исследования разделения точек эллиптической кривой над бинарными расширенными полями и оценка времени атаки. Время приводится в секундах.

# # Время GB Время для нахожд. корней Время атаки
2 129 5 3 0.000 0.008 0.6672 (2/3)
3 86 24 6 0.005 0.008 0.7572 (3/4)
4 65 729 39 247 0.88 0.8575 (4/5)
5 52 148300 638 N/A N/A N/A N/A
5 31 729 39 0.021 (полное время) 30/31

Отметим, что не смотря на меньшее значение для бинарных полей – из-за более быстрого разделения – время атаки всё равно значительно выше, потому что взяты поля с размерами 258 и 260 бит, в отличие от 256 бит. В следствие того, что время для скалярного умножения очень похоже на случай с простыми полями (для нашей реализации), схоже и время для метода Полларда, а следовательно, кривые в [40] также можно рассматривать как уязвимые к нашей атаке.

Другие криптографически соответствующие предположения

Наш предложенный алгоритм статической DHP с оракулом также решает DHP с задержкой цели, определённую Фриманом [6], что в свою очередь можно перефразировать: процессу решения даётся начальный доступ к статическому оракулу DHP для получения элемента ; когда статический оракул DHP больше не требуется, процесс решения задаёт случайный элемент и затем решает DHP для входного значения , а именно находит выход .

Коблиц и Менезес изучали эту задачу в контексте Якобиан гиперэллиптических кривых малого рода [5], а также некоторые другие задачи, такие как DLP с задержкой цели, дополнительной DHP и дополнительной DLP. В случае для DLP с задержкой цели не предоставляется доступ к статическому оракулу DHP, а даётся доступ к оракулу дискретного логарифма, иначе, в противном случае, задача сводиться к решению DHP с задержкой цели. Для дополнительной DHP и дополнительной DLP процедура решения сталкивается с оракулом выводящем случайные элементы группы, также как и в случае DHP оракула или DLP оракула, соответственно. Однако в этот раз необходимо выбрать целое и решить вариантов статической DHP или DLP, но использовать статический DHP или DLP оракул при этом можно только раз.

Дополнительная DHP впервые была сформулирована в [45], в то время как дополнительная DLP впервые была сформулирована в [9] и [10]. Используя Якобианы гиперэллиптических кривых малого рода, как примеры групп, Коблиц и Менезес установили, что составляющие каждой из двух пар одинаковых задач - DLP с задержкой цели и DHP с задержкой цели, а также дополнительной DLP и дополнительной DHP – должны быть различны. В частности, очень вероятно, что не существует сокращения между DLP с задержкой цели и DHP с задержкой цели, так как в некоторых группах первая проще представима чем вторая, в то время как в других возможно и обратное, аналогично и для дополнительных задач. Однако, их анализ DHP с задержкой цели и дополнительной DHP содержит незначительное допущение, поскольку они рассматривают только алгоритм Брауна-Галланта-Чеона, и не берут в расчёт методы индексного исчисления, которые впоследствии используют для изучения соответствующих версий DLP. Выполняя это для Якобиан гиперэллиптических кривых рода можно заметить, что сложности для задач с задержкой цели идентичны, и тоже самое для дополнительных задач.

В действительности, беря основной алгоритм статической DHP представленной в разделе 3.2, можно увидеть, что заменяя запросы оракула статической DHP на запросы оракула DLP, получается тот же алгоритм и следовательно, для других задач с задержкой цели ситуация будет аналогичной. Тоже самое и для любого изменения размера базовой факторизации, оно будет приводить к алгоритмам одинаковой сложности; запросы оракула по своей сути не относятся к структуре алгоритма непосредственно, таким образом понятно, что для любой группы, в которой есть возможность идентифицировать и использовать базовую факторизацию для генерации отношений, DLP с задержкой цели и DHP с задержкой цели будут иметь одинаковые сложности, всякий раз когда этот метод наиболее действенен для решения этих задач. Исключения возникают, например, когда к более быстрому алгоритму применяется только одна задача, как в случае с алгоритмом Брауна-Галланта-Чеона для DHP с задержкой цели, при эллиптической кривой над , порядок группы которой делятся на целое значение размером .

Для разновидностей дополнительных задач, в данном контексте мы получаем следующий простой алгоритм. Выбираем такую же базовую факторизацию, что и в пункте 3.2, и выполняем запросов оракула статической DHP к её элементам. Затем для каждого из полученных элементов, решаем соответствующую задачу также как и раньше. Единственным отличием от дополнительной задачи и задачи с задержкой цели будет то, что для дополнительных задач мы должны подобрать таких элементов, а для задачи с задержкой цели только один. Если выполнить анализ из пункта 3.4 ещё раз, то можно выявить, что оптимальный размер будет при заданном , в точности как и указывалось в пункте 4.5 [5]. Как и раньше, любой оракул можно применить для заданного отношения и таким образом дополнительная DLP и дополнительная DHP имеют одинаковые сложности, и опять таки, это будет всякий раз, когда этот метод наиболее действенен для решения этих задач.

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

Благодарности

Автор хотел бы поблагодарить Стивена Голбрайта и Альфреда Менезеса за их полезные наставления на ранней стадии создания данной статьи, а также рецензентов за их ценные предложения.


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

  1. Claude Shannon Institute, School of Computing, Dublin City University, Glasnevin, Dublin 9, Ireland E-mail: rgranger@computing.dcu.ie

Примечание

  1. Мы используем слово "очевидный", поскольку эти разделения существуют только относительно текущего понимания соответствующих проблем, которые, конечно, могут измениться
  2. Конечно, существуют такие атаки, которые применимы лишь к незначительному меньшинству кривых, хотя они и хорошо изучены и их легко избежать, но для данного случая, криптографии на основе спаривания, которая основана на кривых, ими можно воспользоваться
  3. Алгоритм Гаудри был первоначально размещён на препринт сервере IACR в 2004 году (номер журнала 2004/073), но не был опубликован до 2009 года

Литература

  1. 1,0 1,1 1,2 1,3 Brown, D.R.L., Gallant, R.P.: The Static Diffie-Hellman Problem, Cryptology ePrint Archive, Report 2004/306 (2004)
  2. 2,0 2,1 El Gamal, T.: A public-key cryptosystem and a signature scheme based on discrete logarithms. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (1985)
  3. 3,0 3,1 Ford, W., Kaliski, B.: Server-assisted generation of a strong secret from a password. In: 9th International Workshop on Enabling Technologies, WET ICE 2000, IEEE Press, Los Alamitos (2000)
  4. 4,0 4,1 Chaum, D., van Antwerpen, H.: Undeniable signatures. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 212–217. Springer, Heidelberg (1990)
  5. 5,0 5,1 5,2 5,3 5,4 5,5 5,6 Koblitz, N., Menezes, A.J.: Another look at non-standard discrete log and Diffie-Hellman problems. Journal of Mathematical Cryptology 2(4), 311–326 (2008)
  6. 6,0 6,1 Freeman, D.: Pairing-based identification schemes, technical report HPL-2005-154, Hewlett-Packard Laboratories (2005)
  7. 7,0 7,1 7,2 7,3 7,4 Granger, R., Joux, A., Vitse, V.: New timings for oracle-assisted SDHP on the IPSEC Oakley ‘Well Known Group’ 3 curve. Web announcement on Number Theory List (July 8th, 2010), http://listserv.nodak.edu/archives/nmbrthry.html
  8. 8,0 8,1 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, Heidelberg (2001)
  9. 9,0 9,1 Bellare, M., Namprempre, C., Pointcheval, D., Semanko, M.: The one-more-RSAinversion problems and the security of Chaum’s blind signature scheme. Journal of Cryptology 16, 185–215 (2003)
  10. 10,0 10,1 Bellare, M., Palacio, A.: GQ and Schnorr identification schemes: proofs of security against impersonation under active and concurrent attacks. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 149–162. Springer, Heidelberg (2002)
  11. Cheon, J.: Security analysis of the Strong Diffie-Hellman problem. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 1–11. Springer, Heidelberg (2006)
  12. Maurer, U.M., Wolf, S.: The Diffie-Hellman Protocol. Designs, Codes, and Cryptography 19, 147–171 (2000)
  13. Boneh, D., Boyen, X.: Short signatures without random oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 56–73. Springer, Heidelberg (2004)
  14. Jao, D., Yoshida, K.: Boneh-Boyen Signatures and the Strong Diffie-Hellman Problem. In: Shacham, H., Waters, B. (eds.) Pairing-Based Cryptography – Pairing 2009. LNCS, vol. 5671, pp. 1–16. Springer, Heidelberg (2009)
  15. 15,0 15,1 Joux, A., Naccache, D., Thom.e, E.: When e-th roots become easier than factoring. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 13–28. Springer, Heidelberg (2007)
  16. 16,0 16,1 16,2 Joux, A., Lercier, R., Naccache, D., Thom.e, E.: Oracle-Assisted Static Diffie-Hellman Is Easier Than Discrete Logarithms. In: Parker, M.G. (ed.) Cryptography and Coding. LNCS, vol. 5921, pp. 351–367. Springer, Heidelberg (2009)
  17. 17,0 17,1 17,2 17,3 17,4 17,5 17,6 Gaudry, P.: Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem. Journal of Symbolic Computation 44, 1690–1702 (2009)
  18. Koblitz, N., Menezes, A.J.: Intractable problems in cryptography. In: Proceedings of the 9th International Conference on Finite Fields and Their Applications. AMS, Providence
  19. Koblitz, N., Menezes, A.J.: The brave new world of bodacious assumptions in cryptography. Notices of the AMS 57, 357–365 (2010)
  20. 20,0 20,1 20,2 20,3 Joux, A., Vitse, V.: Elliptic Curve Discrete Logarithm Problem over Small Degree Extension Fields. Application to the static Diffie-Hellman problem on E(Fq5), Cryptology ePrint Archive, Report 2010/157 (2010)
  21. 21,0 21,1 21,2 IETF, The Oakley Key Determination Protocol, IETF RFC 2412 (November 1998)
  22. 22,0 22,1 Smart, N.P.: How Secure are Elliptic Curves over Composite Extension Fields? In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 30–39. Springer, Heidelberg (2001)
  23. 23,0 23,1 23,2 23,3 Gaudry, P., Hess, F., Smart, N.P.: Constructive and destructive facets of Weil descent on elliptic curves. Journal of Cryptology 15, 19–46 (2002)
  24. 24,0 24,1 Galbraith, S.D., Hess, F., Smart, N.P.: Extending the GHS Weil Descent Attack. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 29–44. Springer, Heidelberg (2002)
  25. 25,0 25,1 Menezes, A., Teske, E., Weng, A.: Weak Fields for ECC. In: Okamoto, T. (ed.) CT-RSA 2004. LNCS, vol. 2964, pp. 366–386. Springer, Heidelberg (2004)
  26. W. Diffie and M.E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory 22 (6), pp. 644-654, 1976.
  27. Joux, A., Lercier, R., Smart, N.P., Vercauteren, F.: The Number Field Sieve in the Medium Prime Case. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 326–344. Springer, Heidelberg (2006)
  28. Joux, A., Lercier, R.: The Function Field Sieve in the Medium Prime Case. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 254–270. Springer, Heidelberg (2006) 302 R. Granger
  29. Frey, G.: How to disguise an elliptic curve, Talk at Waterloo Workshop on the ECDLP (1998), http://cacr.math.uwaterloo.ca/conferences/1998/ecc98/slides.html
  30. Hess, F.: The GHS Attack Revisited. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 374–387. Springer, Heidelberg (2003)
  31. 31,0 31,1 31,2 Semaev, I.: Summation Polynomials and the discrete logarithm problem on elliptic curves, Cryptology ePrint Archive, Report 2004/031 (2004)
  32. Coppersmith, D.: Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 178–189. Springer, Heidelberg (1996)
  33. 33,0 33,1 Gaudry, P., Thom.e, E., Th.eriault, N., Diem, C.: A Double Large Prime Variation for Small Genus Hyperelliptic Index Calculus. Math. Comp. 76(257), 475–492 (2007)
  34. 34,0 34,1 Diem, C.: On the discrete logarithm problem in class groups of curves. Mathematics of Computation (to appear)
  35. 35,0 35,1 Diem, C.: On the discrete logarithm problem in elliptic curves (2009) (preprint)
  36. Gianni, P., Mora, T.: Algebraic solution of systems of polynomial equation using Gr.obner bases. In: Huguet, L., Poli, A. (eds.) AAECC 1987. LNCS, vol. 356, pp. 247–257. Springer, Heidelberg (1989)
  37. Lakshman, Y.N.: On the complexity of computing Gr.obner bases for zerodimensional ideals. Ph. D.Thesis, RPI, Troy (1990)
  38. Faug`ere, J.C.: A new efficient algorithm for computing Gr.obner bases (F4). Journal of Pure and Applied Algebra 139(1-3), 61–88 (1999)
  39. 39,0 39,1 39,2 Galbraith, S.D., Lin, X., Scott, M.: Endomorphisms for Faster Elliptic Curve Cryptography on a Large Class of Curves. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 518–535. Springer, Heidelberg (2010)
  40. 40,0 40,1 40,2 40,3 D. Hankerson, K. Karabina and A.J. Menezes, Analyzing the Galbraith-Lin-Scott point multiplication method for elliptic curves over binary fields, IEEE-Transactions on Computers, 58, 1411-1420, 2009.
  41. Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system I: The user language. J. Symbolic Comput., 24(3-4), 235–265 (1997)
  42. I. Duursma, P. Gaudry and F. Morain. Speeding up the Discrete Log Computation on Curves with Automorphisms, Advances in Cryptology - ASIACRYPT99, LNCS 1716, pp. 103-121, Springer-Verlag, 1999.
  43. M.J. Wiener and R.J. Zuccherato. Faster Attacks on Elliptic Curve Cryptosystems, Selected Areas in Cryptography - SAC 1998, LNCS 1556, pp. 190-200, SpringerVerlag, 1998.
  44. Th.eriault, N.: Index calculus attack for hyperelliptic curves of small genus. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 75–92. Springer, Heidelberg (2003)
  45. A. Boldyreva, Efficient threshold signatures, multisignatures and blind signatures based on the gap-Diffie-Hellman-group signature scheme, PKC 2003, LNCS 2567, pp. 31-46, Springer-Verlag, 2003.