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

Скрытые уравнения поля (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}$, $\varphi _{ij}$ и $\xi _{i}$ — целые.
5. Наконец, пусть $f$ — функция такая, что:
   $$L_{N}\mapsto L_{N}$$
   $$f:x\mapsto \sum _{i,j}{\beta _{ij}x^{q^{\theta _{ij}}+q^{\varphi _{ij}}}}+\sum _{i}{\alpha _{i}x^{q^{\xi _{i}}}}+\mu _{0}$$

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

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

$$f(x_{1},...,x_{N})=(p_{1}(x_{1},...,x_{N}),...,p_{N}(x_{1},...,x_{N}))$$

где $p_{1},...,p_{N}$ — $N$ многочленов от $N$ переменных степени 2.

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

Инверсия $f$

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

Теорема: Пусть $L_{N}$ — конечное поле, причем $\mid {L_{N}}\mid =q^{n}$ с $q$ и $n$ «не слишком большими» (например, $q\leq {64}$ и $n\leq {1024}$). Пусть $f(x)$ — заданный многочлен от $x$ над полем $L_{N}$ со степенью $d$ «не слишком большой» (например, $d\leq {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},...,p_{n})$ размерности $n$ над полем $K$.
3. Способ добавления избыточности $r$ в сообщениях (то есть способ получения $x$ из $M$).

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

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

$$M{\overset {+r}{\to }}x{\overset {{\text{секрет}}:S}{\to }}x'{\overset {{\text{секрет}}:P}{\to }}y'{\overset {{\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.