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

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

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

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

Однако для представления элемента множества нулевых следов требуется больше битов по сравнению с элементами эллиптических или гиперэллиптических кривых. Еще одним недостатком является то, что можно снизить безопасность TZV ¹/₆^th длины бита с использованием атаки прикрытия.

Математический фон

А гиперэллиптическая кривая C рода грамм над простым полем ${displaystyle mathbb {F} _ {q}}$ куда q = п^п (п простое число) нечетной характеристики определяется как

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

куда ж моник, град (ж) = 2грамм + 1 и град (час) ≤ g. На кривой есть хотя бы один ${displaystyle mathbb {F} _ {q}}$ -рациональная Weierstraßpoint.

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

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

{displaystyle chi (T) = T ^ {2g} + a_ {1} T ^ {2g-1} + cdots + a_ {g} T ^ {g} + cdots + a_ {1} q ^ {g-1} Т + д ^ {г},}

где_я в ℤ

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

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

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

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

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

{displaystyle G = {Din J_ {C} (mathbb {F} _ {q ^ {n}}) ~ | ~ {ext {Tr}} (D) = {extbf {0}}}, ~~~ ({ extbf {0}} {ext {нейтральный элемент в}} J_ {C} (mathbb {F} _ {q ^ {n}})}

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

Пересечение грамм и ${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- au _ {i} ^ {n})} {prod _ {i = 1} ^ {2g} (1- au _ {i})} }}

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

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

грамм = 1, п = 3
грамм = 1, п = 5
грамм = 2, п = 3

Арифметика

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

За грамм = 1, п = 3: ${displaystyle s = {dfrac {q-1} {1-a_ {1}}} {mod {ell}}}$
За грамм = 1, п = 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}} {мод {ell}}}$
За грамм = 2, п = 3: ${displaystyle s = - {dfrac {q ^ {2} -a_ {2} + a_ {1}} {a_ {1} q-a_ {2} +1}} {mod {ell}}}$

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

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

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

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

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

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

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

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

Примечания

^ Фрей, Герхард; Ланге, Таня (2005). Математические основы криптографии с открытым ключом (PDF). Семинары и конгрессы. 11. С. 41–73.
^ ^а ^б ^c Ланге, Таня (2003). Подмножество Trace Zero для криптосистем.
^ ^а ^б ^c Avanzi, Roberto M .; Чезена, Эмануэль (2008). «Отслеживание нулевых многообразий над полями характеристики 2 для криптографических приложений» (PDF). Алгебраическая геометрия и ее приложения: 188–215.
^ Дием, Клаус; Шолтен, Джаспер. Атака на криптосистему Trace-Zero.