Спаривание Вейля

Спаривание Вейля — это билинейное отображение, определённое на точках эллиптической кривой над конечным полем, которое сопоставляет двум точкам кривой элемент мультипликативной группы некоторого расширения поля. Является одним из фундаментальных понятий в арифметической геометрии и теории чисел, а также нашло важное практическое применение в криптографии, в частности, в системах на основе спариваний (pairing-based cryptography).

История

Концепция спаривания Вейля была введена французским математиком Андре Вейлем в 1940-х годах в контексте его работ по эллиптическим кривым и абелевым многообразиям. Первоначально спаривание использовалось как инструмент для доказательства гипотезы Римана для кривых над конечными полями (часть доказательства гипотезы Вейля). В течение десятилетий оно оставалось чисто теоретическим объектом алгебраической геометрии.

В 1993 году Альфред Менезес, Т. Окамото и Скотт Ванстон предложили использовать спаривание Вейля для атаки на дискретный логарифм на эллиптических кривых (MOV-атака), что показало его практическую значимость в криптоанализе. Позднее, в начале 2000-х годов, Дэн Боне и Мэттью Франклин (2001) разработали первую практическую схему идентификации на основе спаривания, а затем — первую полностью функциональную систему шифрования на основе идентичности (Identity-Based Encryption, IBE). Эти работы положили начало бурному развитию криптографии на спариваниях.

Определение и основные свойства

Пусть \(E\) — эллиптическая кривая, определённая над конечным полем \(\mathbb{F}_q\). Пусть \(n\) — натуральное число, взаимно простое с характеристикой поля \(q\). Обозначим через \(E[n]\) множество точек кручения порядка \(n\) на кривой \(E\) (над алгебраическим замыканием поля \(\mathbb{F}_q\)). Спаривание Вейля — это отображение:

\[ e_n: E[n] \times E[n] \to \mu_n \]

где \(\mu_n\) — группа корней из единицы степени \(n\) в некотором расширении поля \(\mathbb{F}_q\).

Основные свойства спаривания Вейля:

• Билинейность: Для любых точек \(P, Q, R \in E[n]\) выполняется:
• \(e_n(P+Q, R) = e_n(P, R) \cdot e_n(Q, R)\)
• \(e_n(P, Q+R) = e_n(P, Q) \cdot e_n(P, R)\)
• Альтернированность: \(e_n(P, P) = 1\) для любой точки \(P \in E[n]\).
• Невырожденность: Для любой ненулевой точки \(P \in E[n]\) существует точка \(Q \in E[n]\) такая, что \(e_n(P, Q) \neq 1\). Иными словами, отображение не является тривиальным.
• Совместимость с расширением поля: Если \(P \in E(\mathbb{F}_q)\) (точка определена над исходным полем), то значение спаривания \(e_n(P, Q)\) лежит в мультипликативной группе некоторого расширения поля \(\mathbb{F}_{q^k}\), где \(k\) — степень вложения (embedding degree).

Степень вложения \(k\) — это наименьшее натуральное число такое, что \(n\) делит \(q^k - 1\). Именно от неё зависит, насколько быстро можно вычислить спаривание и насколько оно эффективно для криптографических приложений.

Вычисление спаривания Вейля

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

Алгоритм Миллера позволяет вычислить значение спаривания Вейля за \(O(\log n)\) операций на эллиптической кривой. Он основан на построении так называемой функции Миллера \(f_{n,P}\), дивизор которой равен \(n(P) - n(\mathcal{O})\), где \(\mathcal{O}\) — бесконечно удалённая точка (нейтральный элемент группы кривой). Значение спаривания Вейля \(e_n(P, Q)\) выражается через отношение значений этой функции в точках, связанных с \(Q\).

Алгоритм Миллера является основой для вычисления всех современных типов спариваний (включая спаривание Тейта и его оптимизированные варианты).

Применение в криптографии

Спаривание Вейля и его модификации (спаривание Тейта, спаривание Ате, оптимальное спаривание) стали ключевым инструментом в так называемой криптографии на спариваниях (pairing-based cryptography). Основные области применения:

• Криптосистемы на основе идентичности (IBE): Позволяют использовать в качестве открытого ключа любую строку (например, адрес электронной почты). Первая практическая схема IBE была предложена Боне и Франклином в 2001 году.
• Короткие подписи: Схемы подписей, длина которых значительно меньше, чем у традиционных (например, подписи Боне-Лин-Шахама).
• Протоколы обмена ключами с тремя участниками: Протокол Жу-Ли-Ма (Joux) позволяет трём сторонам установить общий секретный ключ за один раунд обмена.
• Групповые подписи и кольцевые подписи: Обеспечивают анонимность и верификацию в групповых сценариях.
• Схемы аутентификации и шифрования с нулевым разглашением: Используются для доказательства знания секрета без его раскрытия.

Криптоанализ и MOV-атака

Спаривание Вейля также используется для атаки на дискретный логарифм на эллиптических кривых (MOV-атака). Если степень вложения \(k\) мала (например, \(k=1\) или \(k=2\)), то задачу дискретного логарифма на эллиптической кривой можно свести к аналогичной задаче в мультипликативной группе расширения поля \(\mathbb{F}_{q^k}\), где известны более эффективные алгоритмы (например, индекс-исчисление). Поэтому для криптографических систем, не основанных на спариваниях, выбирают кривые с большой степенью вложения (обычно \(k > 20\)), чтобы избежать такой атаки.

Классификация спариваний

В современной криптографии используются несколько типов спариваний, которые являются модификациями спаривания Вейля:

• Спаривание Тейта: Более эффективное для вычислений, чем спаривание Вейля, особенно при использовании алгоритма Миллера. Часто используется в практических реализациях.
• Спаривание Ате (Ate pairing): Оптимизированная версия спаривания Тейта для кривых с большим порядком вложения. Позволяет сократить количество итераций алгоритма Миллера.
• Оптимальное спаривание (Optimal pairing): Дальнейшая оптимизация, позволяющая достичь минимально возможного количества итераций для данного типа кривой.
• Спаривание Вейля-Тейта: Обобщение, объединяющее свойства обоих.

Интересные факты

• Спаривание Вейля является частным случаем спаривания на абелевых многообразиях, определённого Вейлем.
• Теорема о том, что спаривание Вейля невырождено, эквивалентна утверждению, что группа точек кручения \(E[n]\) является прямым произведением двух циклических групп порядка \(n\).
• В криптографии на спариваниях часто используются суперсингулярные эллиптические кривые (кривые с малым значением степени вложения \(k\)), которые, наоборот, уязвимы для MOV-атаки в контексте обычных криптосистем.

Критика и ограничения

Основным ограничением спаривания Вейля с точки зрения криптографии является его вычислительная сложность. Хотя алгоритм Миллера значительно ускоряет вычисления, операции спаривания всё ещё на несколько порядков медленнее, чем стандартные операции на эллиптической кривой (сложение точек, умножение на скаляр). Это накладывает ограничения на производительность систем, использующих спаривания, особенно на устройствах с ограниченными ресурсами (например, смарт-карты, IoT-устройства).

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

Источники

1. Silverman, J. H. (2009). The Arithmetic of Elliptic Curves (2nd ed.). Springer.
2. Boneh, D., & Franklin, M. (2001). Identity-Based Encryption from the Weil Pairing. Advances in Cryptology — CRYPTO 2001.
3. Menezes, A., Okamoto, T., & Vanstone, S. A. (1993). Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transactions on Information Theory.
4. Miller, V. S. (1986). Use of elliptic curves in cryptography. Advances in Cryptology — CRYPTO '85.
5. Joux, A. (2004). A one round protocol for tripartite Diffie–Hellman. Journal of Cryptology.
6. Galbraith, S. D., Paterson, K. G., & Smart, N. P. (2008). Pairings for cryptographers. Discrete Applied Mathematics.
7. Washington, L. C. (2008). Elliptic Curves: Number Theory and Cryptography (2nd ed.). CRC Press.