Скрытые уравнения поля

Скрытые уравнения поля (HFE, анг. Hidden Field Equations) — разновидность криптографической системы с открытым ключом, которая является частью многомерной криптографии. Также известна как односторонняя функция с потайным входом HFE. Данная система является обобщением системы Матцумото-Имаи и впервые была представлена Жаком Патарином в 1996 году на конференции Eurocrypt.

Система скрытых уравнений поля основана на многочленах над конечными полями $K$ разного размера, чтобы замаскировать связь между закрытым ключом и открытым ключом.

HFE на самом деле является семейством, которое состоит из основных HFE и комбинаций версий HFE. Семейство криптосистем HFE основано на трудности поиска решений системы многомерных квадратных уравнений (так называемой задаче MQ), поскольку она использует частные аффинные преобразования, чтобы скрыть расширение поля и частные полиномы. Скрытые уравнения поля также использовались для построения схем цифровой подписи, таких как Quartz and Sflash.

Основная идея

Функция $f$

1. Пусть $K$ — конечное поле размерности $q$ с характеристикой $p$(обычно, но не обязательно $p=q=2$).
2. Пусть $L_N$ — расширение $K$ степени $N$.
3. Пусть ${\beta }_{ij}$, ${\alpha }_i$ и ${\mu }_0$ — элементы $L_N$.
4. Пусть ${\theta }_{ij}$, ${\phi }_{ij}$ и ${\xi }_i$ — целые.
5. Наконец, пусть $f$ — функция такая, что:$$L_N\mapsto L_N$$$$f:x\mapsto \sum _{i,j}{\beta }_{ij}{x}^{q^{{\theta }_{ij}}+q^{{\phi }_{ij}}}+\sum _i{\alpha }_i{x}^{q^{{\xi }_i}}+{\mu }_0$$

Тогда $f$ является многочленом от $x$.

Пусть теперь $B$ будет базисом $L_N$. Тогда выражение $f$ в базисе $B$ :

$$f(x_1,\mathrm{...},x_N)=(p_1(x_1,\mathrm{...},x_N),\mathrm{...},p_N(x_1,\mathrm{...},x_N))$$где $p_1,\mathrm{...},p_N$ — $N$ многочленов от $N$ переменных степени 2.

Это верно, так как для любого целого $\lambda$, $x\mapsto x^{q^{\lambda }}$ является линейной функцией $L_N\mapsto L_N$. Многочлены $p_1,\mathrm{...},p_N$ могут быть найдены путем выбора «представления» $L_N$. Такое «представление» обычно задается выбором неприводимого многочлена $i_N(X)$ степени $N$ над $K$, поэтому мы можем задать $L_N$ с помощью $K[X]/(i_N(X))$. В этом случае возможно найти многочлены $p_1,\mathrm{...},p_N$.

Инверсия $f$

Следует заметить, что $f$ не всегда является перестановкой $L_N$ . Однако основой алгоритма HFE является следующая теорема.

Теорема: Пусть $L_N$ — конечное поле, причем $\mid L_N\mid =q^n$ с $q$ и $n$ «не слишком большими» (например, $q\le 64$ и $n\le 1024$). Пусть $f(x)$ — заданный многочлен от $x$ над полем $L_N$ со степенью $d$ «не слишком большой» (например, $d\le 1024$). Пусть $a$ — элемент поля $L_N$. Тогда всегда (на компьютере) можно найти все корни уравнения $f(x)=a$.

Шифрование

Представление сообщения $M$

В поле $K$ количество публичных элементов $q=p^m$.

Каждое сообщение $M$ представлено значением $x$, где $x$ — строка из $n$ элементов поля $K$. Таким образом, если $p=2$, то каждое сообщение представлено $nm$ битами. Более того, иногда предполагается, что в представление $x$ сообщений была помещена некоторая избыточность $r$.

Шифрование $x$

Cекретная часть

1. Расширение $L_n$ поля $K$ степени $n$.
2. Функция $f$:$L_n\mapsto L_n$, которая была описана выше, с «не слишком большой» степенью $d$.
3. Два аффинных преобразования $S$ и $T$: $K^n\mapsto K^n$

Публичная часть

1. Поле $K$ c $q=p^m$ элементами и длина $n$.
2. $n$ многочленов $(p_1,\mathrm{...},p_n)$ размерности $n$ над полем $K$.
3. Способ добавления избыточности $r$ в сообщениях (то есть способ получения $x$ из $M$).

Основная идея построения семейства систем скрытых уравнений поля в качестве многомерной криптосистемы заключается в построении секретного ключа, начиная с полинома $P$ с одним неизвестным $x$ над некоторым конечным полем $L_N$. Этот полином может быть инвертирован над $L_N$, то есть может быть найдено любое решение уравнения $P(x)=y$, если оно существует. Преобразование секрета, также как и расшифровка или/и подпись, основано на этой инверсии.

Как было сказано выше, $P$ можно идентифицировать системой $n$ уравнений $(p_1,\mathrm{...},p_n)$, используя фиксированный базис. Для того чтобы построить криптосистему, полином $(p_1,\mathrm{...},p_n)$ должен быть преобразован таким образом, чтобы публичная информация скрывала первоначальную структуру и предотвращала инверсию. Это достигается рассмотрением конечных полей ${𝕃}_n$ в качестве векторного пространства над $𝕂$ и выбором двух линейных аффинных преобразований $S$ и $T$. Триплет $(S,P,T)$ формирует приватный ключ. Приватный полином $P$ определён на ${𝕃}_n$. Публичным ключом является полином $(p_1,\mathrm{...},p_n)$.

$$M\stackrel{+r}{\to }x\stackrel{\text{секрет}:S}{\to }{x}^{\prime }\stackrel{\text{секрет}:P}{\to }{y}^{\prime }\stackrel{\text{секрет}:T}{\to }y$$

Расширения HFE

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

1. Модификация «+» состоит из линейного комбинирования публичных уравнений с некоторыми случайными уравнениями.
2. Модификация «-» появился благодаря Ади-Шамиру и удаляет избыточность «$r$» из публичных уравнений.
3. Модификация «f» состоит из фиксации некоторых входных переменных $f$ открытого ключа.
4. Модификация «v» определяется как сложная конструкция, такая что обратная функция может быть найдена только в том случае, если некоторые v переменных фиксированы. Эта идея принадлежит Жаку Патарину.

Атаки на криптосистемы HFE

Две самые известные атаки на систему скрытых уравнений поля:

1. Получение закрытого ключа (Шамир-Кипнис): ключевым моментом этой атаки является восстановление закрытого ключа как разреженных одномерных многочленов над полем расширений $L_n$. Атака работает только для базовой системы скрытых уравнений поля и не работает для всех её вариаций.
2. Атака, основанная на алгоритме Грёбнера (разработана Жаном-Чарльзом Фужером): идея атаки заключается в использовании быстрого алгоритма для вычисления базиса Грёбнера системы полиномиальных уравнений. Фужер взломал HFE в рамках the HFE Challenge 1 за 96 часов в 2002 году. В 2003 году Фужер вместе с Жу работали над безопасностью HFE.