Криптография с нулевым следом

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

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

Разновидности Trace zero обладают лучшей производительностью скалярного умножения, чем эллиптические кривые. Это позволяет выполнять быструю арифметику в этих группах, что может ускорить вычисления в 3 раза по сравнению с эллиптическими кривыми и, следовательно, ускорить криптосистему.

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

Однако для представления элемента множества нулевого следа требуется больше битов по сравнению с элементами эллиптических или гиперэллиптических кривых. Другим недостатком является тот факт, что можно снизить безопасность TZV на ^{1/6 длины} бита, используя атаку покрытия _.

Математическое образование

Гиперэллиптическая кривая C рода g над простым полем , где q = p ⁿ ( p prime) нечетной характеристики, определяется как ${\displaystyle \mathbb {F} _{q}}$

${\displaystyle C:~y^{2}+h(x)y=f(x),}$

где f монична, deg( f ) = 2 g  + 1 и deg( h ) ≤ g. Кривая имеет по крайней мере одну -рациональную точку Вейерштрасса. ${\displaystyle \mathbb {F} _{q}}$

Якобианское многообразие C для всех конечных расширений изоморфно группе идеальных классов . С помощью представления Мамфорда можно представить элементы с помощью пары многочленов [u, v] , где u , v ∈ . ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$ ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle \operatorname {Cl} (C/\mathbb {F} _{q^{n}})}$ ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$ ${\displaystyle \mathbb {F} _{q^{n}}[x]}$

Эндоморфизм Фробениуса σ применяется к элементу [u, v] для возведения каждого коэффициента этого элемента в степень q : σ( [u, v] ) = [ u ^q (x), v ^q (x)]. Характеристический многочлен этого эндоморфизма имеет следующий вид: ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$

${\displaystyle \chi (T)=T^{2g}+a_{1}T^{2g-1}+\cdots +a_{g}T^{g}+\cdots +a_{1}q^{g-1}T+q^{g},}$

где _я в ${\displaystyle \mathbb {Z} }$

С помощью теоремы Хассе–Вейля можно получить групповой порядок любого поля расширения , используя комплексные корни τ _i уравнения χ( T ): ${\displaystyle \mathbb {F} _{q^{n}}}$

${\displaystyle |J_{C}(\mathbb {F} _{q^{n}})|=\prod _{i=1}^{2g}(1-\tau _{i}^{n})}$

Пусть D — элемент C , тогда можно определить эндоморфизм , так называемый след D : ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$ ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$

${\displaystyle \operatorname {Tr} (D)=\sum _{i=0}^{n-1}\sigma ^{i}(D)=D+\sigma (D)+\cdots +\sigma ^{n-1}(D)}$

На основе этого эндоморфизма можно свести якобиево многообразие к подгруппе G со свойством, что каждый элемент имеет нулевой след:

${\displaystyle G=\{D\in J_{C}(\mathbb {F} _{q^{n}})~|~{\text{Tr}}(D)={\textbf {0}}\},~~~({\textbf {0}}{\text{ neutral element in }}J_{C}(\mathbb {F} _{q^{n}})}$

G является ядром эндоморфизма следа, и, таким образом, G является группой, так называемым (под)многообразием нулевого следа (TZV) группы . ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$

Пересечение G и производится n -торсионными элементами . Если наибольший общий делитель, то пересечение пусто и можно вычислить групповой порядок G : ${\displaystyle J_{C}(\mathbb {F} _{q})}$ ${\displaystyle J_{C}(\mathbb {F} _{q})}$ ${\displaystyle \gcd(n,|J_{C}(\mathbb {F} _{q})|)=1}$

${\displaystyle |G|={\dfrac {|J_{C}(\mathbb {F} _{q^{n}})|}{|J_{C}(\mathbb {F} _{q})|}}={\dfrac {\prod _{i=1}^{2g}(1-\tau _{i}^{n})}{\prod _{i=1}^{2g}(1-\tau _{i})}}}$

Фактическая группа, используемая в криптографических приложениях, является подгруппой G ₀ группы G большого простого порядка l . Эта группа может быть самой G. ^{[1] [2]}

Существуют три различных случая криптографической значимости TZV: ^[3]

• г = 1, п = 3
• г = 1, п = 5
• г = 2, п = 3

Арифметика

Арифметика, используемая в группе TZV G _{0 ,} основана на арифметике для всей группы , Но можно использовать эндоморфизм Фробениуса σ для ускорения скалярного умножения. Это можно заархивировать, если G ₀ генерируется D порядка l, тогда σ(D) = sD , для некоторых целых чисел s . Для данных случаев TZV s можно вычислить следующим образом, где a _i берутся из характеристического многочлена эндоморфизма Фробениуса : ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$

• Для g = 1, n = 3: ${\displaystyle s={\dfrac {q-1}{1-a_{1}}}{\bmod {\ell }}}$
• Для g = 1, n = 5: ${\displaystyle s={\dfrac {q^{2}-q-a_{1}^{2}q+a_{1}q+1}{q-2a_{1}q+a_{1}^{3}-a_{1}^{2}+a_{1}-1}}{\bmod {\ell }}}$
• Для g = 2, n = 3: ${\displaystyle s=-{\dfrac {q^{2}-a_{2}+a_{1}}{a_{1}q-a_{2}+1}}{\bmod {\ell }}}$

Зная это, можно заменить любое скалярное умножение mD (|m| ≤ l/2) на:

${\displaystyle m_{0}D+m_{1}\sigma (D)+\cdots +m_{n-1}\sigma ^{n-1}(D),~~~~{\text{where }}m_{i}=O(\ell ^{1/(n-1)})=O(q^{g})}$

С помощью этого приема многократное скалярное произведение можно сократить примерно до 1/( n  − 1) -го ^числа удвоений, необходимых для вычисления mD , если подразумеваемые константы достаточно малы. ^{[3] [2]}

Безопасность

Стойкость криптографических систем на основе подмногообразий с нулевым следом по результатам работ ^{[2] [3]} сопоставима со стойкостью гиперэллиптических кривых низкого рода g' над , где p' ~ ( n  − 1)( g/g' ) для |G| ~128 бит. ${\displaystyle \mathbb {F} _{p'}}$

Для случаев, когда n = 3, g = 2 и n = 5, g = 1, можно снизить безопасность максимум на 6 бит, где |G| ~ 2 ²⁵⁶ , поскольку нельзя быть уверенным, что G содержится в якобиане кривой рода 6. Безопасность кривых рода 4 для подобных полей гораздо менее безопасна.

Атака прикрытия на криптосистему с нулевым следом

Атака, опубликованная в ^[4], показывает, что DLP в группах нулевого следа рода 2 над конечными полями характеристики, отличной от 2 или 3, и расширением поля степени 3 может быть преобразована в DLP в группе классов степени 0 с родом не более 6 над базовым полем. В этой новой группе классов DLP может быть атакована методами исчисления индексов. Это приводит к сокращению длины бита ^{на 1} / ₆ ^th .

Примечания

1. Фрей, Герхард ; Ланге, Таня (2005). «Математические основы криптографии с открытым ключом» (PDF) . Семинары и конгрессы . 11 : 41–73.
2. Ланге, Таня (2003). "Подмножество нулевых следов для криптосистем". Архив Cryptology ePrint .
3. Avanzi, Roberto M.; Cesena, Emanuele (2008). "Многообразия с нулевым следом над полями характеристики 2 для криптографических приложений" (PDF) . Алгебраическая геометрия и ее приложения : 188–215. doi :10.1142/9789812793430_0010. ISBN 978-981-279-342-3.
4. Дьем, Клаус; Шолтен, Джаспер. Атака на криптосистему с нулевым следом . CiteSeerX 10.1.1.295.9027 . 

Ссылки

• Винеке, Мальта; Паар, Кристоф (17 февраля 2008 г.). Криптография на разновидностях Trace-Zero (PDF) . Рурский университет в Бохуме.
• Сазерленд, Эндрю В. (2007). «101 полезное разнообразие с нулевыми следами». Массачусетский технологический институт.