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

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