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

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

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

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

Основная идеяПравить

Функция $f$$f$ Править

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

    
   $$f:x\mapsto <!--\; \mapsto \; -->\underset{i,j}{\sum <!--\; \sum \; -->}{\mathrm{\beta <!--\; \beta \; -->}}_{ij}{x}^{q^{{\mathrm{\theta <!--\; \theta \; -->}}_{ij}}+q^{{\mathrm{\phi <!--\; \phi \; -->}}_{ij}}}+\underset{i}{\sum <!--\; \sum \; -->}{\mathrm{\alpha <!--\; \alpha \; -->}}_i{x}^{q^{{\mathrm{\xi <!--\; \xi \; -->}}_i}}+{\mathrm{\mu <!--\; \mu \; -->}}_0$$

    

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

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

$$f(x_1,...,x_N)=(p_1(x_1,...,x_N),...,p_N(x_1,...,x_N))$$

 

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

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

Инверсия $f$$f$ Править

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

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

ШифрованиеПравить

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

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

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

Шифрование $x$$x$ Править

Cекретная частьПравить

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

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

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

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

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

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

 

Расширения HFEПравить

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

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

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

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

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