Уравнения скрытого поля

Уравнения скрытых полей ( HFE ), также известные как функция-ловушка HFE , представляют собой с открытым ключом криптосистему , которая была представлена в Eurocrypt в 1996 году и предложена (на французском языке) Жаком Патареном после идеи системы Мацумото и Имаи. Он основан на полиномах над конечными полями. $\mathbb {F} _{q}$ разного размера, чтобы скрыть связь между закрытым ключом и открытым ключом . HFE на самом деле представляет собой семейство, состоящее из базового HFE и комбинаторных версий HFE. Семейство криптосистем HFE основано на сложности задачи поиска решений системы многомерных квадратных уравнений (так называемая проблема MQ), поскольку оно использует частные аффинные преобразования для сокрытия поля расширения и частных полиномов . Уравнения скрытого поля также использовались для построения схем цифровой подписи, например Quartz и Sflash. ^[1]

Математическая основа

Одно из основных понятий, позволяющих понять, как работают уравнения скрытых полей, — это увидеть, что для двух расширенных полей $\mathbb {F} _{q^{n}}$ $\mathbb {F} _{q^{m}}$ над тем же базовым полем $\mathbb {F} _{q}$ можно интерпретировать систему $m$ многомерные полиномы в $n$ переменные над $\mathbb {F} _{q}$ как функция $\mathbb {F} _{q^{n}}\to \mathbb {F} _{q^{m}}$ используя основу подходящую $\mathbb {F} _{q^{n}}$ над $\mathbb {F} _{q}$ . Почти во всех приложениях полиномы квадратичны, т. е. имеют степень 2. ^[2] Мы начнем с простейшего вида многочленов, а именно с мономов, и покажем, как они приводят к квадратичным системам уравнений.

Рассмотрим конечное поле $\mathbb {F} _{q}$ , где $q$ является степенью 2 и полем расширения $K$ . Позволять $0<h<q^{n}$ такой, что $h=q^{\theta }+1$ для некоторых $\theta$ и НОД $(h,q^{n}-1)=1$ . Условие НОД $(h,q^{n}-1)=1$ эквивалентно требованию, чтобы отображение $u\to u^{h}$ на $K$ один к одному, а его обратная карта - это карта $u\to u^{h'}$ где $h'$ является мультипликативным обратным $h\ {\bmod {q}}^{n}-1$ .

Возьмите случайный элемент $u\in \mathbb {F} _{q^{n}}$ . Определять $w\in \mathbb {F} _{q^{n}}$ к

w=u^{h}=u^{q^{\theta }}u\ \ \ \ (1)

Позволять $\beta _{1},...,\beta _{n}$ быть основой $K$ как $\mathbb {F} _{q}$ векторное пространство . Мы представляем $u$ относительно основы как $u=(u_{1},...,u_{n})$ и $w=(w_{1},...,w_{n})$ . Позволять $A^{(k)}={a_{ij}^{(k)}}$ быть матрицей линейного преобразования $u\to u^{q^{k}}$ по отношению к основе $\beta _{1},...,\beta _{n}$ , то есть такой, что

\beta _{i}^{q^{k}}=\sum _{j=1}^{n}a_{ij}^{k}\beta _{j},\ \ a_{ij}^{k}\in \mathbb {F} _{q}

для $1\leq i,k\leq n$ . Дополнительно запишите все произведения базисных элементов через базис, т.е.:

\beta _{i}\beta _{j}=\sum _{l=1}^{n}m_{ijl}\beta _{l},\ \ m_{ijl}\in \mathbb {F} _{q}

для каждого $1\leq i,j\leq n$ . Система $n$ уравнения, которое является явным в $w_{i}$ и квадратичный по $u_{j}$ можно получить, разложив (1) и приравняв нулю коэффициенты $\beta _{i}$ .

Выберите два секретных аффинных преобразования. $S$ и $T$ , т.е. два обратимых $n\times n$ матрицы $M_{S}=\{S_{ij}\}$ и $M_{T}=\{T_{ij}\}$ с записями в $\mathbb {F} _{q}$ и два вектора $v_{S}$ и $v_{T}$ длины $n$ над $\mathbb {F} _{q}$ и определить $x$ и $y$ с помощью:

u=Sx=M_{S}x+v_{S}\ \ \ \ w=Ty=M_{T}y+v_{T}\ \ \ \ (2)

Используя аффинные соотношения в (2) для замены $u_{j},w_{i}$ с $x_{k},y_{l}$ , система $n$ уравнения линейны по $y_{l}$ и степени 2 в $x_{k}$ . Применяя линейную алгебру, это даст $n$ явные уравнения, по одному на каждое $y_{l}$ как многочлены степени 2 от $x_{k}$ . ^[3]

Многомерная криптосистема

Основная идея использования семейства HFE в качестве многомерной криптосистемы состоит в том, чтобы построить секретный ключ, начиная с полиномиального числа. $P$ в одном неизвестном $x$ над некоторым конечным полем $\mathbb {F} _{q^{n}}$ (обычно значение $q=2$ используется). Этот многочлен можно легко обратить $\mathbb {F} _{q^{n}}$ , т. е. можно найти любые решения уравнения $P(x)=y$ когда такое решение существует. секретное преобразование: расшифровка и/или подпись На этой инверсии основано . Как объяснялось выше $P$ можно отождествить с системой $n$ уравнения $(p_{1},...,p_{n})$ используя фиксированную основу. Для построения криптосистемы полином нужен $(p_{1},...,p_{n})$ должна быть преобразована так, чтобы публичная информация скрывала исходную структуру и предотвращала инверсию. Это делается путем просмотра конечных полей $\mathbb {F} _{q^{n}}$ как векторное пространство над $\mathbb {F} _{q}$ и выбрав два линейных аффинных преобразования $S$ и $T$ . Тройка $(S,P,T)$ составляют закрытый ключ. Частный полином $P$ определяется более $\mathbb {F} _{q^{n}}$ . ^[1]^[4] Открытый ключ $(p_{1},...,p_{n})$ . Ниже приведена схема люка MQ. $(S,P,T)$ в HFE

{\text{input}}x\to x=(x_{1},...,x_{n}){\overset {{\text{secret}}:S}{\to }}x'{\overset {{\text{secret}}:P}{\to }}y'{\overset {{\text{secret}}:T}{\to }}{\text{output}}y

полином HFE

Частный полином $P$ со степенью $d$ над $\mathbb {F} _{q^{n}}$ является элементом $\mathbb {F} _{q^{n}}[x]$ . Если условия многочлена $P$ иметь не более чем квадратичные члены по $\mathbb {F} _{q}$ тогда публичный полином будет оставаться небольшим. ^[1] Дело в том, что $P$ состоит из мономов вида $x^{q^{s_{i}}+q^{t_{i}}}$ , т.е. с 2 степенями $q$ в показателе является базовой версией HFE , т.е. $P$ выбран как

P(x)=\sum c_{i}x^{q^{s_{i}}+q^{t_{i}}}

Степень $d$ многочлена также известен как параметр безопасности , и чем больше его значение, тем лучше для безопасности, поскольку результирующий набор квадратных уравнений напоминает случайно выбранный набор квадратных уравнений. С другой стороны большой $d$ замедляет расшифровку. С $P$ является полиномом степени не более $d$ обратная сторона $P$ , обозначенный $P^{-1}$ можно вычислить в $d^{2}(\ln d)^{O(1)}n^{2}\mathbb {F} _{q}$ операции. ^[5]

Шифрование и дешифрование

Открытый ключ предоставляется $n$ многомерные полиномы $(p_{1},...,p_{n})$ над $\mathbb {F} _{q}$ . Таким образом, необходимо передать сообщение $M$ от $\mathbb {F} _{q^{n}}\to \mathbb {F} _{q}^{n}$ для того, чтобы зашифровать его, т.е. мы предполагаем, что $M$ вектор $(x_{1},...,x_{n})\in \mathbb {F} _{q}^{n}$ . Чтобы зашифровать сообщение $M$ мы оцениваем каждый $p_{i}$ в $(x_{1},...,x_{n})$ . Зашифрованный текст $(p_{1}(x_{1},...,x_{n}),p_{2}(x_{1},...,x_{n}),...,p_{n}(x_{1},...,x_{n}))\in \mathbb {F} _{q}^{n}$ .

Чтобы понять расшифровку, давайте выразим шифрование в терминах $S,T,P$ . Обратите внимание, что они недоступны отправителю. Оценивая $p_{i}$ в сообщении мы сначала применяем $S$ , в результате чего $x'$ . В этот момент $x'$ переводится из $\mathbb {F} _{q^{n}}\to \mathbb {F} _{q^{n}}$ поэтому мы можем применить частный полином $P$ что закончилось $\mathbb {F} _{q^{n}}$ и этот результат обозначается $y'\in \mathbb {F} _{q^{n}}$ . Снова, $y'$ переносится в вектор $(y_{1}',...,y_{n}')$ и трансформация $T$ применяется и конечный результат $y\in \mathbb {F} _{q^{n}}$ производится из $(y_{1},...,y_{n})\in \mathbb {F} _{q}^{n}$ .

Чтобы расшифровать $y$ , описанные выше действия выполняются в обратном порядке. Это возможно, если закрытый ключ $(S,P,T)$ известно. Решающим шагом в расшифровке является не инверсия $S$ и $T$ а скорее вычисления решения $P(x')=y'$ . С $P$ не обязательно является биекцией, можно найти более одного решения этой инверсии (существует не более d различных решений $X'=(x_{1}',...,x_{d}')\in \mathbb {F} _{q^{n}}$ с $P$ является полиномом степени d). Избыточность обозначается как $r$ добавляется на первом шаге к сообщению $M$ чтобы выбрать правильный $M$ из набора решений $X'$ . ^[1]^[3]^[6] На диаграмме ниже показан базовый HFE для шифрования.

M{\overset {+r}{\to }}x{\overset {{\text{secret}}:S}{\to }}x'{\overset {{\text{secret}}:P}{\to }}y'{\overset {{\text{secret}}:T}{\to }}y

Варианты HFE

Уравнения скрытого поля имеют четыре основных варианта, а именно +,-,v и f , и их можно комбинировать по-разному. Основной принцип заключается в следующем:

01. Знак + представляет собой смешение линейности общедоступных уравнений с некоторыми случайными уравнениями.

02. Знак «-» принадлежит Ади Шамиру и предназначен для устранения избыточности «r» в общедоступных уравнениях.

03. Знак f состоит из фиксации некоторых

f

входные переменные открытого ключа.

04. Знак v определяется как конструкция, иногда довольно сложная, так что обратную функцию можно найти только в том случае, если некоторые v переменных, называемых переменными уксуса, фиксированы. Эта идея принадлежит Жаку Патарену.

Вышеописанные операции в некоторой степени сохраняют разрешимость функции с помощью люка.

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

С шифрованием ситуация лучше с HFE+, поскольку процесс расшифровки занимает столько же времени, однако в открытом ключе больше уравнений, чем переменных. ^[1]^[2]

HFE-атаки

Есть две известные атаки на HFE:

Восстановить закрытый ключ ( Шамир -Кипнис). Ключевым моментом этой атаки является восстановление закрытого ключа в виде разреженных одномерных полиномов по полю расширения. $\mathbb {F} _{q^{n}}$ . Атака работает только для базового HFE и не работает для всех его вариантов.

Быстрые базисы Грёбнера (Фожер): Идея атак Фожера заключается в использовании быстрого алгоритма для вычисления базиса Грёбнера системы полиномиальных уравнений. Фожер преодолел задачу HFE 1 за 96 часов в 2002 году, а в 2003 году Фожер и Жу вместе работали над безопасностью HFE. ^[1]

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж Кристофер Вольф и Барт Пренил, Асимметричная криптография: уравнения скрытого поля
^ Jump up to: ^а ^б Николя Т. Куртуа о криптосистемах с открытым ключом, использующих только многовариантную подпись
^ Jump up to: ^а ^б Илья Толи Скрытые полиномиальные криптосистемы
^ Жан-Шарль Фожер и Антуан Жу , Алгебраический криптоанализ криптосистем уравнений скрытого поля (HFE) с использованием базисов Грёбнера. Архивировано 11 ноября 2008 г. на Wayback Machine.
^ Николя Т. Куртуа, «Безопасность уравнений скрытого поля»
^ Жак Патарен, Уравнения скрытого поля (HFE) и изоморфный полином (IP): два новых семейства асимметричных алгоритмов

Николя Т. Куртуа, Магнус Даум и Патрик Фельке, О безопасности HFE, HFEv- и Quartz
Андрей Сидоренко, Уравнения скрытого поля, семинар EIDMA, 2004 г., Технологический университет Эйндховена.
Иво Г. Десмет, Криптография с открытым ключом-PKC 2003, ISBN 3-540-00324-X

[autogenerated2-1] Jump up to: ^а ^б ^с ^д ^и ^ж Кристофер Вольф и Барт Пренил, Асимметричная криптография: уравнения скрытого поля

[autogenerated1-2] Jump up to: ^а ^б Николя Т. Куртуа о криптосистемах с открытым ключом, использующих только многовариантную подпись

[autogenerated4-3] Jump up to: ^а ^б Илья Толи Скрытые полиномиальные криптосистемы

[autogenerated3-4] Жан-Шарль Фожер и Антуан Жу , Алгебраический криптоанализ криптосистем уравнений скрытого поля (HFE) с использованием базисов Грёбнера. Архивировано 11 ноября 2008 г. на Wayback Machine.

[5] Николя Т. Куртуа, «Безопасность уравнений скрытого поля»

[6] Жак Патарен, Уравнения скрытого поля (HFE) и изоморфный полином (IP): два новых семейства асимметричных алгоритмов

[1]

[2]

[3]

[4]

[5]

[6]