Краткие явные формулы вычислительного спаривания для обычных кривых

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:51, 27 сентября 2015.
Faster Explicit Formulas for Computing Pairings over Ordinary Curves
Two-Output Secure Computation with Malicious Adversaries.png
Авторы Диего Ф. Аранья[@: 1],
Корая Карабина[@: 2],
Патрик Лонга[@: 3],
Кэтрин Х. Геботиц[@: 4] и
Хулио Лопез[@: 5]
Опубликован 2010 г.
Сайт Patrick Longa's webpage
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация. Мы описываем эффективные формулы вычисления пары для обыкновенных эллиптических кривых с простыми полями. Во-первых, мы обобщаем методы снижения, которые ранее применялись для квадратичных вычислений и для вычисления пар, в том числе арифметических. Во-вторых, мы вводим новую формулу сжатия квадратуры для круговых подгрупп и новую технику, чтобы избежать инверсий для возведений в степень, когда кривая параметризуется отрицательными числами. Методы демонстрируются в контексте парных вычислений для кривых Баррето-Наерига, в которых они имеют эффективные реализации, а также в сочетании с результатами других современных исследований. Полученные формулы снижают количество необходимых операций и, следовательно, время исполнения, улучшая реализацию криптографических пар на 28%-34% для нескольких 64-разрядных вычислительных платформ. В частности, наши методы позволяют вычислить пары для 2 миллионов циклов.


Ключевые слова: Эффективная реализация программного обеспечения, явные формулы, билинейные пары.

Введение

К производительности вычисления пар привлекается повышенный интерес научно-исследовательского сообщества, главным образом потому, что криптография спаривания позволяет эффективно решить несколько давних проблем, таких, как идентифицирующее шифрование [1][2], неинтерактивное доказательство с нулевым разглашением [3] и эффективные многосторонние согласования ключей [4]. В последнее время значительные улучшения по сравнению с 10 млн. циклами, представленными в [5] позволили вычислить спаривание при 128-битном уровне безопасности для 4,38 млн. циклов [6] и при использовании высокоскоростных векторных операций для 2,33 млн. циклов [7], когда работает быстрый множитель, доступный в 64-разрядной системе.

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

  • оптимальное спаривание Ate [8], вычисленное исключительно для поворотов [9] с упрощенной окончательной линией оценки [6] для подмножеств [10] Баррето-Наерига (BN) спаривания эллиптических кривых [11].
  • внедрение методов, описанных в [7] для квадратичных арифметических полей, показывает как сократить трудоемкую обработку и вызов функций.

С другой стороны, вводятся следующие новые методы:

  • Понятие сокращения, как правило, применяемое для арифметики в квадратичных вычислений в контексте спаривания, как описано в [12], обобщается до возводящей арифметики, выполняемой в вычислениях спаривания. В некотором смысле, это направление противоположно тому, которое принято другими авторами. Вместо того, чтобы кодировать арифметику для увеличения модульных сокращений [13][6], мы настаиваем на сокращении Монтгомери и концентрируемся на уменьшении вычислительных сокращений. Более того, для работы с трудозатратными высокоточными дополнениями добавлено ленивый сокращение, мы разрабатываем гибкую методологию, сохраняющую промежуточные значения для ограниченной редукции Монтгомери, и максимизирующую эффективность операции без проверки. Традиционная модель операций существенно расширяется с учетом модульных сокращений в индивидуальном порядке.
  • Формулы для удвоения и добавления точек в якобиан и однородные координаты тщательно оптимизируются за счет устранения нескольких пренебрежимых операций, которые являются трудозатратными для 64-битных платформ.
  • Вычисления окончательного возведения в степень улучшаются новым набором формул для возведения в квадрат и эффективной декомпрессии в круговых подгруппах, и арифметическим трюком для вычисления пар для кривых, параметризованных отрицательными целыми числами.

Описанные методы значительно уменьшают затраты, что позволяет нашему программному обеспечению вычислять спаривания для 2 млн. циклов и улучшить время затраты на 28%-34% для нескольких различных 64-разрядных вычислительных платформ. Хотя методы применяются для спаривания по BN кривым на 128-битном уровне безопасности, они могут быть легко расширены и на другие параметры с помощью различных кривых и более высоких уровней безопасности [14].

Эта статья организована следующим образом. В разделе 2 дается обзор алгоритма Миллера, используемого для вычисления оптимального спаривания Ate для BN кривых. В разделе 3 представлены обобщенные методы сокращения и их применение для улучшения производительности. Различные оптимизации для арифметики, в том числе применение сокращений, обсуждаются в разделе 4. Раздел 5 описывает наши усовершенствования конечного возведения в степень. Раздел 6 подводит итоги и Раздел 7 описывает наши высокоскоростных реализации программного обеспечения и сравнивает результаты с самыми быстрыми из известных ранее. В разделе 8 даны окончательные замечания.

Предварительные сведения

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

Баррето и Наеринг [11] описали параметризованные множества эллиптических кривых для простого поля простого порядка , где это любое целое число. Это множество является довольно большим и легко создаваемым [10], что обеспечивает множество параметров для выбора; и, при степени , хорошо подходит для вычисления асимметричной пары на 128-битном уровне безопасности [12]. Она допускает несколько оптимальных выводов [8] для различных вариантов спаривания Ate [15], таких как скорость R-схемы [16], оптимальные схемы [8] и χ-схемы [17].

Пусть будет подгруппой n точек из Е и имеет шестую степень для E, а не вторую и не третью в . Для создания преимуществ прямого тестирования и при сохранении производительности примерно такой же, мы ограничимся описанием вычислительного оптимального спаривания, определяемого как [6]:


где и является эндоморфизмом Фробениуса  ; группы , , определяются собственным пространством как , а в качестве прообраза для при изоморфизме ; группа будет подгруппой n единичных корней для  ; является нормированной функцией с и будут линиями, возникающими при добавлении и и их оценке в точке P.


Миллером [18][19] был предложен алгоритм, который поэтапно строит с помощью метода двойных добавлений. При обобщении вида алгоритма Миллера без знаменателя [20] для вычисления спариваний с набором параметров, предложенных в [10] для 128-битного уровня безопасности, мы получаем Алгоритм 1. Для BN кривой мы имеем . Для того чтобы учесть отрицательные r (строка 9 в алгоритме 1), требуется вычислить простые отрицания в и получить окончательную функцию Т для ; сложные инверсии в большом поле нужны для получения правильного значения спаривание вместо , получаемого в конце алгоритма. Сложные инверсии будут осуществляться позднее в Разделе 5 с помощью окончательного возведения в степень.

Kiaf 01.png

Арифметика возвышения расширенных полей

Алгоритм Миллера [18][19] использует арифметику в на стадии аккумуляции (строки 3,5,11,12 в алгоритме 1) и на стадии заключительного возведения в степень (строка 13 в том же алгоритме). Следовательно, для достижения высокой эффективности осуществления спаривания крайне важно выполнение арифметики для расширенных полей. В частности, в [21] рекомендуется представить через расширения с помощью неприводимых биномов. Соответственно, в наших целевых настройках мы представляем с использованием гибких возвышающих схем, использованных в [22][5][7][10] совместно с параметрами, предложенными в [10]:

  • , где
  • , где
  • , где
  • или

Мы можем конвертировать одно возвышение в другое путем простых перестановок порядка коэффициентов. Выбор ускоряет арифметику в , так как умножение на может быть рассчитано как простые вычитания [10].

Упрощение возвышающих полей

Концепция упрощения относится к [23] и используется во многих работах и для различных сценариев [24][25][12]. Лим и Хванг [24] показали, что умножение в , когда рассматривается как прямое расширение через неприводимые биномы , при , которые могут быть выполнены с k сокращениями по модулю p. Как правило, требуется либо сокращений, либо сокращений Каратцубы. Данное сокращение было впервые применено в контексте вычисления спариваний [12] для устранения сокращений . Если применить , то этот подход требует 2*6*3 = 36 сокращений по модулю p и 3*6*3 = 54 целочисленных умножений для выполнения одного умножения в , см. [12][5][7].

В этом разделе мы обобщим методику приведения для возвышающих полей построенных на неприводимых биномах [26]. Покажем, что умножение (и возведения в квадрат) в требует только k сокращений и по-прежнему основывается на различных арифметических оптимизациях, имеющихся в литературе, для уменьшения числа умножений в подполях. Например, при нашем подходе требуется 2•3•2=12 сокращений по модулю p и 54 целочисленных умножений с использованием для вычисления одного умножения в  ; или 12 сокращений по модулю p и 36 целочисленных операций умножения для вычисления одной квадратура в . Хотя более широкие обобщения этих методов подробно проанализированы в контексте умножений и редукций Монтгомери [27], которые обычно используются для спаривания обычных кривых. Мы приведем наши формулы для возвышающего построения в разделе 3.3. Для устранения неоднозначности, термин редукции по модулю p, всегда будет относится к модульному снижению для двойной точности чисел.

TemplateTheoremIcon.svg Теорема Теорема 1
Пусть и . Зададим в качестве расширения, где каждое из имеет степень 2 или 3, которое можно построить, используя вторую степень неприводимых биномов , или третью степень неприводимых биномов , соответственно. Полагая, что может быть выбрано так, что для всех , может быть вычислено без какого-либо сокращения по модулю p. Тогда умножение в можно вычислить с помощью целочисленных умножений и сокращения по модулю p для любого k.
Доказательство
Докажем это индукцией по . Базовым случаем будет и . То есть, , и у нас будет с . Для любого мы можем написать

что может быть вычислено для 3 целочисленных умножений и 2 сокращений по модулю p (обратим внимание, что мы игнорируем умножение для , по нашему предположению).

Далее, рассмотрим

где или . В первом случае, пусть и .

Тогда

(1)

что может быть вычислено 3 умножениями в , а именно и (опять таки, мы игнорируем умножение на ). По гипотезе индукции, каждое умножение в требует целочисленных умножений, и сокращений по модулю p. Кроме того, три сокращения по модулю p, при вычислении и могут быть сведены к двум сокращениям по модулю p (См. (1)). Таким образом, умножение в может быть вычислено с с целочисленными умножениями и сокращениями по модулю p.

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

Также легко обобщить процедуру выше, до любой формулы, кроме Каратцубы, включающей в себя только суммы (или вычитания) результатов из , с такими , как при возведение в квадрат или для Тчун-Хасановской асимметричной формулы [28].

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

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

Существуют некоторые ограничения при задержке сокращений. В частности, единичные операции (с операндами занимающими слов , где w это размер машинного текста) заменяются на двойными операциями (с операндами, занимающими 2n слов). Тем не менее, этот недостаток можно свести к минимуму с точки зрения скорости, выбрав размер поля меньший, чем границы для размеров текста, потому что этот метод моет быть использован более широко для оптимизации двойной арифметики.


Создание меньшего, чем текстовая граница, размера поля

Если модуль p выбирается так, что , где , а n это точное число слов, необходимых для представления р, т.е. , и w это размер машинного текста; затем может быть выполнено несколько последовательных дополнений без переноса в наиболее значимых словах (MSW) перед умножением формы , где , . В случае сокращения Монтгомери, ограничение задается верхней границей . Аналогично, при задержке сокращений, результат умножения без уменьшения имеет максимальное значение (предполагается, что ), а несколько последовательных двойных дополнений без переноса в MSW (и, в некоторых случаях, вычитаний без переноса) могут быть выполнены перед сокращением. При использовании снижения Монтгомери до дополнений могут быть выполнены без выполнения проверки.

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

В случае двойной арифметики, доступны различные оптимизационные альтернативы. Рассмотрим их в контексте арифметики Монтгомери. Во-первых, как сказано в [7], если , где c это результат двойного дополнения, тогда с может быть восстановлено с более простым одинарным вычитанием при (Заметим, что первая половина этого значения состоит из одних нулей). Во-вторых, доступны различные варианты для преобразования отрицательных чисел в положительные после двойного вычитания. В частности, рассмотрим вычисления , где и , что является рекуррентной операцией (например, когда ). Для этой операции, мы исследовали следующие варианты, которые могут быть интегрированы в вычисления, давая различные преимущества:


Вариант 1: , h небольшая целое число, .

Вариант 2: если , то .

Вариант 3:

Вариант 4: если , то .

В частности, варианты 2 и 4 требуют условной проверки, что делают их более сложными. Тем не менее, эти параметры могут быть полезны, когда отрицательные значения не могут быть исправлены другими вариантами, не нарушая верхней границы. Также отметим, что вариант 2 может использовать более простые одинарные вычитания для преобразования отрицательных значений в положительные. Варианты 1 и 3 являются особенно эффективными, поскольку они не требуют проверок. Более того, если l достаточно мало (и h максимально для варианта 1), тогда несколько следующих операций могут быть выполнены без проверки. Среди прочих, вариант 1, как правило, наиболее эффективен потому, что добавление требует меньше, чем двойной точности, если , где w это размер машинного текста.

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

Анализ для выбранных параметров

Для анализа мы используем , построенные с неприводимыми биномами, описанными в начале этого раздела. При работе с 128-битным уровнем безопасности, одинарные и двойные операции определяются операндами размера N = 256 и 2N = 512, соответственно. В нашем случае, и . Обозначения фиксируются следующим образом: (1) это операторы, не требующие проводить обработку или модульные сокращения границ; (2) являются операторами, производящими снижение результатов через осуществление обработки или модульных снижений; (3) индексы, используются в операторе для обозначения расширения степени; (4) обозначение используется для j-го элемента подполя для элемента расширенного поля  ; (5) t и T отвечают за одинарные и двойные числа или расширенные элементы поля, построенные на одинарных или двойных числах, соответственно. Точность операторов определяется точностью операнд и результата. Обратим внимание, что, как отмечалось выше, если после добавления , мы корректируем результат, вычисляя . Как и для вычитаний, мы ссылаемся на "вариант 2".

Следующие обозначения используются для трудозатрат операций: (1) m,s,a обозначают стоимость умножения, возведение в квадрат и сложения в , соответственно, (2) обозначают стоимость умножения, возведения в квадрат, сложения и инверсии в , соответственно; (3) обозначают стоимость нередуцированных умножений и возведений в квадрат, дающих двойные результаты, а также модульные снижения двойных целых чисел, соответственно, (4) обозначает стоимость нередуцированных умножения и возведения в квадрат, и модульные снижение двойной точности элементов в , соответственно. Далее в работе, если не указано иное, мы предполагаем, что дополнение двойной точности имеет стоимость 2а и в и , соответственно, что совпадает с практическими наблюдениями.

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

Kiaf 02.png

Теперь определим умножения в . Пусть будут такими, что . Требуемые операции для вычисления умножений в подробно описаны в алгоритме 3. В этом случае, и , где и . Во-первых, отметим, что модель повторяется для каждого . После умножения с использованием алгоритма 2 с вариантом , мы имеем и (шаг 1 из алгоритма 3). Выходы одинарных дополнений вида и находятся в диапазоне [0,2p] и, следовательно, не требуют проверок (пункты 2, 9 и 17 алгоритма 3).

Соответствующие умножения в с использованием алгоритма 2 с вариантом 2 дают результаты в диапазонах и (шаги 3, 10 и 18). Хотя , отметим, что и , поскольку .

Следовательно, при , двойные вычитания для вычисления с использованием алгоритма Каратцубы не требуют выполнения проверок (пункты 4 и 6, 11 и 13, 19 и 21). Для вычисления не требуется проводить проверку (для выходного диапазона ) и вычитания дают результат в диапазоне при использовании варианта 2 (пункты 5,12 и 20). Для вычисления , умноженного на , т.е. , включаются операции и , которые вычисляются с двойной точностью с использованием варианта 2 до получения диапазона (шаг 7). Аналогичным образом, окончательные дополнения с требуют варианта 2, чтобы получить выход в диапазоне (шаг 8). Для вычисления , рассчитывается как и , где требуется двойная точности вычитания с использованием варианта , чтобы получить результат в диапазоне (шаг 14) и кроме того требуется двойная точность, чтобы получить результат в диапазоне (шаг 15). Затем, и связываются с двойной точностью и дополнением с использованием варианта 2 для получения результатов в диапазоне (шаг 16). Результаты и требуют двойной точности с использованием варианта 2 (окончательный диапазон , шаг 22) и двойной точности без проверки (окончательный диапазон , шаг 23), соответственно. Модульные сокращения были отложены снова до последней строки .

Kiaf 03.png

Наконец, пусть будут такими, что . Алгоритм 4 детализует необходимые операции для вычисления умножения. В этом случае . На шаге 1, умножения дают выходы и в диапазоне с помощью алгоритма 3. Дополнения и являются одинарными, приведенными по модулю p, так что умножение в шаге 2 дает выход в диапазоне с помощью алгоритма 3. Затем, вычитания и используют двойные операции с вариантом 2 и в диапазоне , так что мы можем применить сокращение Монтгомери на шаге 5, чтобы получить результат по модулю p. Для , умножение на v, т. е. , где , включает в себя двойные операции и , все выполняемые с вариантом 2 для получения выходного диапазона (шаги 6-7). Заключительное дополнение использует двойную точность с вариантом 2 снова, так что мы можем применить сокращения Монтгомери на шаге 9 для получения результата по модулю p.

Отметим, что, применение данной техники с использованием описанной последовательности действий, приводит к уменьшению числа сокращений в с 3 до всего лишь 2, или числа общих модульных сокращения из 54 (или 36 для ) до k =12.

Kiaf 04.png

Как уже говорилось ранее, существуют ситуации, когда более эффективно выполнять сокращения сразу после умножения, а возведения в квадрат в последней строке арифметики. Проиллюстрируем это возведения в квадрат в . Как показано в алгоритме 5, в общей сложности требуется 2 сокращения в при выполнении умножений на шаге 4. Если применяется упрощенное сокращение, то число сокращений останется на уровне 2, а общая стоимость будет увеличена, так как некоторые операции потребуют двойной точности. Читатель должен заметить, что подход, предложенный в [10], где формулы из [28] используются для вычисления квадратур во внутреннем кубическом расширении , что экономит по сравнению с алгоритмом 5. Тем не менее, мы проверили такой подход для нескольких комбинаций формул, и он всегда медленнее, чем алгоритм 5 в связи с увеличением числа дополнений.

Kiaf 05.png

Подход Миллера

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

Костелло и соавт. [9, § 5] предложили использовать однородные координаты для выполнения полных арифметических расчетов кривых. Их формула для вычислительные удвоение точек и оценка линии стоит .

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

,

Это удвоенная формула дает стоимость в . Кроме того, если параметр выбран как и в [10], умножение на может быть выполнено с минимальным количеством сложений и вычитаний. Например, если зафиксировать , то . Соответственно, данное исполнение имеет стоимость (отметим, что расчеты для Е и приводятся для и вычисляется заранее):

,

Отметим, что на практике мы наблюдали, что . Следовательно, более эффективно вычислять непосредственно , чем использовать и . Если бы это было не так, то формулу можно было бы реализовать со стоимостью в


Примечательно, что метод, предложенный в разделе 3 для отсрочки сокращений может быть применен и к точечным расчетам для расширенного поля. Сокращения могут быть отложены до конца каждого умножение/возведения в квадрат в и затем далее они могут откладываться для тех сумм произведений, что позволяют уменьшить число сокращений. Существует не много мест, где эта техника может быть применена. например, удвоение формулы (2) требует 25 сокращений (3 на каждое умноженияе с использованием алгоритма Каратцубы, по 2 на возведения в квадрат и по 1 на умножения ). Во-первых, путем отсрочки сокращения внутри их число снижается до 2, с 22 сокращениями в общей сложности. Более того, сокращение, соответствующее и в (см. исполнение (3)) может дополнительно отложено, что устраняет необходимость двух сокращений. В общей сложности, число сокращений равно 20.

Подобные оптимизации могут быть применены к другим точечным/линейным формулам оценки (см. расширенную версию [29] для оптимизации для формул с помощью якобиана и однородных координат).

Для накопления линий оценок в переменную Миллера, представляется через и специальные умножения, стоимостью в . Во время первого исполнения цикла, возведение в квадрат в может быть устранено, так как переменная Миллера инициализируется как 1 (линия 1 алгоритма 1) и специальные умножения, стоимостью в , используется для умножения двух первых оценок, и дает в результате пересмотренный алгоритм 6. Эти редкие умножения используются также для двух финальных строк в шаге 10 алгоритма.

Заключительные возведения в степень

Самый быстрый способ для вычисления окончательного возведения в степень описывается в работе [29]. Значение преобразуется в , требующую сопряжения и инверсии; еще один простой показатель , который требует степени Фробениуса и умножения; а показатель может быть выполнен в круговой подгруппе . Для вычисления последней власти, можно написать показатели следующим образом [12]:

где

,

и вычислить отдельные степени дополнительными цепочками, требующими три последовательных возведения в степень по абсолютному значению параметра кривой , 13 умножений, 4 квадратуры, 4 р степени Фробениуса, степени Фробениуса и одной степени Фробениуса в Эти степени Фробениуса могут быть эффективно вычислены по формулам в [7]. В следующих разделах мы объясним, как избавиться от дорогих инверсии в , упомянутых в конце раздела 2; и как круговые структуры подгрупп позволяют быстрые и сжатые квадратуры и следовательно, быстрые возведения в степень по .


Удаление недостатков инверсии

Для алгоритма 1, оптимальное Ate спаривание при может быть вычислено как

с и . Лемма 1 позволяет заменить дорогую инверсию простыми сопряжениями без изменения результата. Это отражено в строке 9 алгоритма 6.

TemplateTheoremIcon.svg Теорема Лемма 1.
Спаривание может быть вычислено как при соответствующих g,h.
Доказательство
Распределяя степени для g,h в уравнении (4):


Вычисление u степеней в Вычисление u степеней в   G ϕ 0 ( F p 2 ) {\displaystyle ~G {\phi {0}}(F {p^{2}})}

с В работе [31] было показано, что можно сжать g до и сжатое представление для вычисляется как , где равны:

, ,

, ,

где и . Формула требует 4 умножений в . Учитывая технику сокращения из раздела 3.3, мы предлагаем другую формулу, которая немного быстрее и имеет стоимость в . Формула задается следующим образом:

, ,

, ,

где и  ; см. также расширенную версия [30] для правильности нашей формулы и явной реализации.

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

,

В частности, можно вычислить в три этапа:

1. Вычислить для , используя (6) и сохранить и .
2. Вычислить и .
3. Вычислить .

Шаг 1 требует 62 квадратуры в . Использование трюка Монтгомери [32] на шаге 2 требует . Шаг 3 требует 2 умножения в . Общая стоимость:

Формула Грейнджера-Скотта [33] для возведения в квадрат может быть реализована со стоимостью в , если упрошенные методы сокращения работают. При таком подходе возведение в степень требует:

Таким образом, формулы быстрого сжатия квадратур уменьшают на 33% число квадратур и на 30% количество дополнений в .

Kiaf 06.png

Вычислительные затраты

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

Таблица 1. Операционные затраты алгоритма Миллера. (†) В работе [7] эти дополнения расчитываются по-другому. Расходы на умножение и квадратуры в равны и , соответственно.

Kiaf 07.png

Для выбранных параметров и с представленными улучшениями, цикл Миллера в алгоритме 6 выполняет 64 удвоения точек и оценки линий, 6 дополнительных точек с оценкой линий (4 внутри цикла Миллера и еще 2 на заключительном этапе), 1 отрицание в для предварительного вычисления , 1 р степень Фробениуса, 1 степень Фробениуса и 2 отрицания в  ; 1 сопряжение, 1 умножение, 66 редких умножений, 2 более редких умножений и 63 квадратуры в . Стоимость цикла Миллера:

Окончательное возведение в степень выполняется в общей сложности за 1 инверсию, 4 сопряжения, 15 умножений, 3 u степени, 4 круговых квадратуры, 5 р степеней Фробениуса, степеней Фробениуса:

В таблице 2 приведены сравнение в первом приближении для нашей реализации и лучших реализаций доступных в литературе для оптимального Ate спаривания при 128-битном уровне безопасности в той же платформе. Для соответствующей работы, мы предполагаем, что упрощенное сокращение всегда используется в а затем каждое умножение или квадратура по существу вычисляет модульное сокращение (т.е. и ). Обратим внимание, что наши обобщения методов для целого спаривания сводит число модульных сокращение от ожидаемого в 7818 (если упрощенное сокращение использовалось только для арифметика), до 4662, избегая более 40% общих требуемых модульных сокращений. Число умножений также уменьшается на 13%, а ряд дополнений увеличивается на 26% за счет сокращения упрощенных компромиссов. Наши операционные затраты выше, чем у Перейры и соавт. [10]. Тем не менее, читатель должен отметить, что, когда мы рассматриваем реальную стоимость дополнений в , мы не можем использовать формулу квадратуры к [28] (см. раздел 3.3) и формулу удвоения точки с меньшим количеством умножений (См. раздел 4), с учетом значительного увеличения числа дополнений.

Таблица 2. Сравнение операционных затрат для различных реализаций оптимального спаривания Ate при 128-битном уровне безопасности

Kiaf 08.png

Результаты применения

Несколько реализаций подтверждают эффективность представленной схемы. Мы реализовали непосредственно следуя советам из [7] для оптимизации выполнения обработки и уменьшения трудозатрат. Были реализованы более сложные алгоритмы с использованием языка С совместно с компилятором GCC, использующем -03 уровень оптимизации. В таблице 3 представлены соответствующие времена в миллионах циклов. Основные исполнения используют однородные координаты и упрощенные исполнения . Быстрые вычисления в подгруппах в ускоряет базовое исполнение на 5% -7%, а в сочетании с обобщенными сокращениями базовую реализация улучшается на 18% -22%.


Таблица 3. Улучшения производительности при использовании новой арифметики в круговых подгруппах (раздел 5.2) и обобщенных сокращений (раздел 3.1) для нескольких 64-разрядных архитектур. Улучшения рассчитываются по отношению к базовому исполнению. Часы представлены в миллионах тактов.

Kiaf 09.png

Таблица 4 сравнивает нашу реализацию с соответствующими работами. Чтобы убедиться в том, что компьютеры с различными конфигурациями, но принадлежащие к одной микроархитектуре совместимы по производительности (как в случае с Core i5 и Core i7), программное обеспечение из [7] было протестировано и результаты были сравненены. Машины, эквивалентные по этому критерию, представлены в одном столбце. Отметим, что Phenom II не рассматривался в первоначальном исследовании, и что мы не смогли найти процессор Core 2 Duo работающий за теже времена, что в [7]. По этой причине, времена для этих двух архитектур были приняты независимо друг от друга, используя доступное программное обеспечение. Заметим, что базовая реализация в Таблице 3 последовательно превосходит алгоритм Бешо и соавт. для нашей реализации оптимального выбора параметров [10], в сочетании с оптимизированной арифметикой кривых в однородных координатах [9]. При снижениях и для круговых формул, спаривание становится быстрее, чем в лучшей из предыдущих результатов на 28% -34%. Результаты для длительного тестирования в сравнении с предыдущими работами для различных 64-разрядных процессоров мы приводим в нашей онлайн базе данных [34].

Таблица 4. Сравнение между реализациями для 64-битных архитектур. Времена представлены в тактах.

Kiaf 10.png

Заключение

В этой работе мы вновь обратились к вычислению оптимального спаривания по обычных кривых в простых полях. Некоторые новые методы были внедрены для вычисления спаривания, состоящие в основном в обобщении методов снижений для арифметики в  ; были предложены улучшения окончательного возведения в степень, состоящие из формулы для сжатого возведения в квадрат в круговых подгруппах и удалении учета отрицательных параметризаций кривой. Быстрая арифметика в круговых подгруппах улучшает производительность спаривания на 5% -7%, а обобщенные снижения в состоянии устранить 40% необходимых вычислений, улучшая производительность спаривания еще на 11% -17%. Введеные методы позволяют впервые вычислить спаривания для 2 млн. циклов на 64-битных платформах, давая улучшения в 28% -34%. Повышения производительности, как ожидается, будут выше, для встроенных архитектур, где соотношение между умножением и сложением, как правило, выше.

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

Мы хотели бы выразить нашу благодарность Альфреду Менезесу, Крейгу Костелло, Майклу Скотту, Пауло Баррето, Джоварно Перейре и Конрадо Гуве за полезные советы во время подготовки данной работы. Авторы благодарят Научно-исследовательский совет Канады (NSERC), центр в Онтарио (OCE), CNPq, CAPES и FAPESP для поддержку этой работы.

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

  1. University of Campinas, E-mail: dfaranha@ic.unicamp.br
  2. Certicom Research, E-mail: kkarabina@rim.com
  3. University of Waterloo, E-mail: plonga@uwaterloo.ca
  4. University of Waterloo, E-mail: cgebotys@uwaterloo.ca
  5. University of Campinas, E-mail: jlopez@ic.unicamp.br

Примечание

Литература

  1. Boneh, D., Franklin, M.K.: Identity-Based Encryption from the Weil Pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001)
  2. Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems Based on Pairing over Ellip- tic Curve. In: The 2001 Symposium on Cryptography and Information Security. IEICE, Oiso (2001) (in Japanese)
  3. Groth, J., Sahai, A.: Efficient Non-interactive Proof Systems for Bilinear Groups. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 415–432. Springer, Heidelberg (2008)
  4. Joux, A.: A One Round Protocol for Tripartite Diffie-Hellman. Journal of Cryptology 17(4), 263–276 (2004)
  5. 5,0 5,1 5,2 Hankerson, D., Menezes, A., Scott, M.: Identity-Based Cryptography, ch. 12, pp. 188–206. IOS Press, Amsterdam (2008)
  6. 6,0 6,1 6,2 6,3 Naehrig, M., Niederhagen, R., Schwabe, P.: New Software Speed Records for Cryptographic Pairings. In: Abdalla, M., Barreto, P.S.L.M. (eds.) LATINCRYPT 2010. LNCS, vol. 6212, pp. 109–123. Springer, Heidelberg (2010)
  7. 7,0 7,1 7,2 7,3 7,4 7,5 7,6 7,7 Beuchat, J.L., Díaz, J.E.G., Mitsunari, S., Okamoto, E., Rodríguez-Henríquez, F., Teruya, T.: High-speed software implementation of the optimal ate pairing over barreto–naehrig curves. In: Joye, M., Miyaji, A., Otsuka, A. (eds.) Pairing 2010. LNCS, vol. 6487, pp. 21–39. Springer, Heidelberg (2010)
  8. 8,0 8,1 8,2 Vercauteren, F.: Optimal pairings. IEEE Transactions on Information The- ory 56(1), 455–461 (2010)
  9. 9,0 9,1 Costello, C., Lange, T., Naehrig, M.: Faster Pairing Computations on Curves with High-Degree Twists. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 224–242. Springer, Heidelberg (2010)
  10. 10,0 10,1 10,2 10,3 10,4 10,5 10,6 Pereira, G.C.C.F., Simplício Jr, M.A., Naehrig, M., Barreto, P.S.L.M.: A Family of Implementation-Friendly BN Elliptic Curves. To appear in Journal of Systems and Software
  11. 11,0 11,1 Barreto, P.S.L.M., Naehrig, M.: Pairing-Friendly Elliptic Curves of Prime Order. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 319– 331. Springer, Heidelberg (2006)
  12. 12,0 12,1 12,2 12,3 12,4 Scott, M.: Implementing Cryptographic Pairings. In: Takagi, T., Okamoto, T., Okamoto, E., Okamoto, T. (eds.) Pairing 2007. LNCS, vol. 4575, pp. 197–207. Springer, Heidelberg (2007)
  13. Fan, J., Vercauteren, F., Verbauwhede, I.: Faster Fp-arithmetic for Cryptographic Pairings on Barreto-Naehrig Curves. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 240–253. Springer, Heidelberg (2009)
  14. Freeman, D., Scott, M., Teske, E.: A Taxonomy of Pairing-Friendly Elliptic Curves. Journal of Cryptology 23(2), 224–280 (2010)
  15. Hess, F., Smart, N.P., Vercauteren, F.: The Eta Pairing Revisited. IEEE Transactions on Information Theory 52, 4595–4602 (2006)
  16. Lee, E., Lee, H.-S., Park, C.-M.: Efficient and Generalized Pairing Computation on Abelian Varieties. IEEE Transactions on Information Theory 55(4), 1793–1803 (2009)
  17. Nogami, Y., Akane, M., Sakemi, Y., Kato, H., Morikawa, Y.: Integer Variable χ-Based Ate Pairing. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209, pp. 178–191. Springer, Heidelberg (2008)
  18. 18,0 18,1 Miller, V.: Uses of Elliptic Curves in Cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986)
  19. 19,0 19,1 Miller, V.S.: The Weil Pairing, and its Efficient Calculation. Journal of Cryptol- ogy 17(4), 235–261 (2004)
  20. Barreto, P.S.L.M., Kim, H.Y., Lynn, B., Scott, M.: Efficient Algorithms for Pairing- Based Cryptosystems. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 354–368. Springer, Heidelberg (2002)
  21. IEEE: P1363.3: Standard for Identity-Based Cryptographic Techniques using Pair- ings (2006), http://grouper.ieee.org/groups/1363/IBC/submissions/
  22. Devegili, A.J., Scott, M., Dahab, R.: Implementing Cryptographic Pairings over Barreto-Naehrig Curves. In: Takagi, T., Okamoto, T., Okamoto, E., Okamoto, T. (eds.) Pairing 2007. LNCS, vol. 4575, pp. 197–207. Springer, Heidelberg (2007)
  23. Weber, D., Denny, T.F.: The Solution of McCurley’s Discrete Log Challenge. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 458–471. Springer, Hei- delberg (1998)
  24. 24,0 24,1 Lim, C.H., Hwang, H.S.: Fast Implementation of Elliptic Curve Arithmetic in GF(pn). In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751, pp. 405–421. Springer, Heidelberg (2000)
  25. Avanzi, R.M.: Aspects of Hyperelliptic Curves over Large Prime Fields in Software Implementations. In: Joye, M., Quisquater, J.J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 148–162. Springer, Heidelberg (2004)
  26. Benger, N., Scott, M.: Constructing Tower Extensions of Finite Fields for Imple- mentation of Pairing-Based Cryptography. In: Hasan, M.A., Helleseth, T. (eds.) WAIFI 2010. LNCS, vol. 6087, pp. 180–195. Springer, Heidelberg (2010)
  27. Montgomery, P.L.: Modular Multiplication Without Trial Division. Mathematics of Computation 44(170), 519–521 (1985)
  28. 28,0 28,1 28,2 Chung, J., Hasan, M.: Asymmetric Squaring Formulae. In: 18th IEEE Symposium on Computer Arithmetic (ARITH-18 2007), pp. 113–122. IEEE Press, Los Alamitos (2007)
  29. Scott, M., Benger, N., Charlemagne, M., Perez, L.J.D., Kachisa, E.J.: On the Final Exponentiation for Calculating Pairings on Ordinary Elliptic Curves. In: Shacham, H., Waters, B. (eds.) Pairing 2009. LNCS, vol. 5671, pp. 78–88. Springer, Heidelberg (2009)
  30. Aranha, D.F., Karabina, K., Longa, P., Gebotys, C.H., López, J.: Faster Ex- plicit Formulas for Computing Pairings over Ordinary Curves. Cryptology ePrint Archive, Report 2010/526 (2010), http://eprint.iacr.org/
  31. Karabina, K.: Squaring in Cyclotomic Subgroups. Cryptology ePrint Archive, Re- port 2010/542 (2010), http://eprint.iacr.org/
  32. Montgomery, P.: Speeding the Pollard and Elliptic Curve Methods of Factorization. Mathematics of Computation 48, 243–264 (1987)
  33. Granger, R., Scott, M.: Faster Squaring in the Cyclotomic Subgroup of Sixth Degree Extensions. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 209–223. Springer, Heidelberg (2010)
  34. Longa, P.: Speed Benchmarks for Pairings over Ordinary Curves, http://www.patricklonga.bravehost.com/speed_pairing.html#speed