Спаривание Тейта

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

Определение

Пусть \(E\) — эллиптическая кривая, определённая над конечным полем \(\mathbb{F}_q\), где \(q = p^m\) — степень простого числа \(p\). Пусть \(r\) — простое число, делящее порядок группы точек кривой \(E(\mathbb{F}_q)\), причём \(r\) не делит \(q\). Обозначим через \(k\) наименьшее целое число, такое что \(r \mid (q^k - 1)\); это число называется степенью вложения (embedding degree). Спаривание Тейта определяется как отображение:

\[ t_r: E(\mathbb{F}_{q^k})[r] \times E(\mathbb{F}_{q^k})/rE(\mathbb{F}_{q^k}) \to \mathbb{F}_{q^k}^/(\mathbb{F}_{q^k}^)^r, \]

где \(E(\mathbb{F}_{q^k})[r]\) — группа \(r\)-кручения (точки порядка \(r\)), а \(\mathbb{F}_{q^k}^\) — мультипликативная группа расширения поля. На практике спаривание Тейта часто нормализуют, возводя результат в степень \((q^k - 1)/r\), чтобы получить однозначно определённый элемент в \(\mathbb{F}_{q^k}^\).

Свойства

Спаривание Тейта обладает следующими ключевыми свойствами:

• Билинейность: Для любых точек \(P \in E(\mathbb{F}_{q^k})[r]\) и \(Q_1, Q_2 \in E(\mathbb{F}_{q^k})\) выполняется:

\[ t_r(P, Q_1 + Q_2) = t_r(P, Q_1) \cdot t_r(P, Q_2), \] \[ t_r(P_1 + P_2, Q) = t_r(P_1, Q) \cdot t_r(P_2, Q). \]

• Невырожденность: Для любого ненулевого \(P\) существует \(Q\) такой, что \(t_r(P, Q) \neq 1\).
• Вычислимость: Существуют эффективные алгоритмы (например, алгоритм Миллера) для вычисления спаривания за полиномиальное время.

Вычисление: алгоритм Миллера

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

\[ t_r(P, Q) = f_{r,P}(Q)^{(q^k - 1)/r}. \]

Алгоритм Миллера работает за \(O(\log r)\) арифметических операций в поле \(\mathbb{F}_{q^k}\), что делает его пригодным для практического использования.

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

Спаривание Тейта, наряду со спариванием Вейля, является основой для криптографических систем на основе спариваний. Основные области применения:

Трёхсторонний протокол Диффи — Хеллмана

Спаривание позволяет двум сторонам установить общий ключ без необходимости прямого обмена ключами, используя однократное взаимодействие. Протокол, предложенный Антуаном Жу (Antoine Joux) в 2000 году, использует билинейность для согласования ключа между тремя участниками.

Криптосистема Боне — Франклина

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

Короткие подписи

Спаривание Тейта позволяет создавать подписи малой длины (например, схема Боне — Линн — Шахама, BLS). Подпись представляет собой одну точку на эллиптической кривой, что даёт значительный выигрыш в размере по сравнению с традиционными схемами (RSA, DSA).

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

Спаривание Тейта и спаривание Вейля — два наиболее распространённых билинейных отображения на эллиптических кривых. Основные различия:

На практике спаривание Тейта предпочтительнее из-за более высокой скорости вычислений, особенно при использовании оптимальных вариаций (оптимальное спаривание Тейта).

Криптографическая стойкость

Безопасность протоколов на основе спаривания Тейта опирается на сложность задачи дискретного логарифмирования в мультипликативной группе поля \(\mathbb{F}_{q^k}\) и на эллиптической кривой. Для обеспечения стойкости необходимо выбирать параметры, при которых степень вложения \(k\) достаточно велика (обычно \(k \geq 12\) для 128-битного уровня безопасности), чтобы предотвратить атаки с помощью решета числового поля. Современные стандарты (например, NIST) рекомендуют кривые с малым \(k\) (например, BN-кривые с \(k=12\) или BLS-кривые с \(k=24\)).

Ограничения и критика

• Уязвимость для квантовых атак: Как и все криптосистемы на основе дискретного логарифмирования, спаривание Тейта уязвимо для атак с использованием квантового компьютера (алгоритм Шора). Это стимулирует разработку постквантовых криптосистем.
• Сложность реализации: Корректная реализация спаривания требует точного выбора параметров кривой и поля, а также защиты от атак по побочным каналам (side-channel attacks).
• Патентные ограничения: Некоторые алгоритмы на основе спаривания (например, IBE Боне — Франклина) были запатентованы, что ограничивало их распространение до истечения сроков патентов.

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

• Джон Тейт ввёл спаривание в 1958 году в работе «WC-groups over p-adic fields», но его криптографическое значение было осознано лишь спустя 40 лет.
• Спаривание Тейта является частным случаем более общего понятия спаривания Тейта — Шафаревича, используемого в теории Ивасавы.
• В 2002 году Виктор Миллер получил премию Гёделя за разработку алгоритма, названного его именем, который лежит в основе вычисления спариваний.

Источники

• J. Tate, «WC-groups over p-adic fields», Séminaire Bourbaki, 1958.
• V. Miller, «Short Programs for Functions on Curves», 1986.
• A. Joux, «A One Round Protocol for Tripartite Diffie–Hellman», 2000.
• D. Boneh, M. Franklin, «Identity-Based Encryption from the Weil Pairing», 2001.
• D. Boneh, B. Lynn, H. Shacham, «Short Signatures from the Weil Pairing», 2001.
• I. Blake, G. Seroussi, N. Smart, «Advances in Elliptic Curve Cryptography», Cambridge University Press, 2005.