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

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

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

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

Функция ${\displaystyle f}$

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 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 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 M}$

В поле ${\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}$ .

Шифрование ${\displaystyle x}$

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

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}}$ . Этот полином может быть инвертирован над ${\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})}$ .

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

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

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

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

Примечания

Ссылки