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

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

Система скрытых уравнений поля основана на многочленах над конечными полями ${\displaystyle K}$ разного размера, чтобы замаскировать связь между закрытым ключом и открытым ключом.^[2]

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

1. Пусть ${\displaystyle K}$ — конечное поле размерности ${\displaystyle q}$ с характеристикой ${\displaystyle p}$(обычно, но не обязательно ${\displaystyle p=q=2}$).
2. Пусть ${\displaystyle L_{N}}$ — расширение ${\displaystyle K}$ степени ${\displaystyle N}$.
3. Пусть ${\displaystyle \beta _{ij}}$, ${\displaystyle \alpha _{i}}$ и ${\displaystyle \mu _{0}}$ — элементы ${\displaystyle L_{N}}$.
4. Пусть ${\displaystyle \theta _{ij}}$, ${\displaystyle \varphi _{ij}}$ и ${\displaystyle \xi _{i}}$ — целые.
5. Наконец, пусть ${\displaystyle f}$ — функция такая, что:$${\displaystyle L_{N}\mapsto L_{N}}$$$${\displaystyle 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}}$$

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

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

$${\displaystyle f(x_{1},...,x_{N})=(p_{1}(x_{1},...,x_{N}),...,p_{N}(x_{1},...,x_{N}))}$$где ${\displaystyle p_{1},...,p_{N}}$ — ${\displaystyle N}$ многочленов от ${\displaystyle N}$ переменных степени 2.

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

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

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

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

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

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

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

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

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

$${\displaystyle M{\overset {+r}{\to }}x{\overset {{\text{секрет}}:S}{\to }}x'{\overset {{\text{секрет}}:P}{\to }}y'{\overset {{\text{секрет}}:T}{\to }}y}$$

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

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

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

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