Система скрытых уравнений поля основана на многочленах над конечными полями разного размера, чтобы замаскировать связь между закрытым ключом и открытым ключом.[2]
HFE на самом деле является семейством, которое состоит из основных HFE и комбинаций версий HFE. Семейство криптосистем HFE основано на трудности поиска решений системы многомерных квадратных уравнений (так называемой задаче MQ[3]), поскольку она использует частные аффинные преобразования, чтобы скрыть расширение поля и частные полиномы. Скрытые уравнения поля также использовались для построения схем цифровой подписи, таких как Quartz and Sflash.[2][1]
Пусть — конечное поле размерности с характеристикой (обычно, но не обязательно ).
Пусть — расширение степени .
Пусть , и — элементы .
Пусть , и — целые.
Наконец, пусть — функция такая, что:
Тогда является многочленом от .
Пусть теперь будет базисом . Тогда выражение в базисе :
где — многочленов от переменных степени 2.
Это верно, так как для любого целого , является линейной функцией . Многочлены могут быть найдены путем выбора «представления» . Такое «представление» обычно задается выбором неприводимого многочлена степени над , поэтому мы можем задать с помощью . В этом случае возможно найти многочлены .
Следует заметить, что не всегда является перестановкой . Однако основой алгоритма HFE является следующая теорема.
Теорема: Пусть — конечное поле, причем с и «не слишком большими» (например, и ).Пусть — заданный многочлен от над полем со степенью «не слишком большой» (например, ).Пусть — элемент поля .Тогда всегда (на компьютере) можно найти все корни уравнения .
Каждое сообщение представлено значением , где — строка из элементов поля . Таким образом, если , то каждое сообщение представлено битами. Более того, иногда предполагается, что в представление сообщений была помещена некоторая избыточность .
Способ добавления избыточности в сообщениях (то есть способ получения из ).
Основная идея построения семейства систем скрытых уравнений поля в качестве многомерной криптосистемы заключается в построении секретного ключа, начиная с полинома с одним неизвестным над некоторым конечным полем .[2] Этот полином может быть инвертирован над , то есть может быть найдено любое решение уравнения , если оно существует. Преобразование секрета, также как и расшифровка или/и подпись, основано на этой инверсии.
Как было сказано выше, можно идентифицировать системой уравнений , используя фиксированный базис. Для того чтобы построить криптосистему, полином должен быть преобразован таким образом, чтобы публичная информация скрывала первоначальную структуру и предотвращала инверсию. Это достигается рассмотрением конечных полей в качестве векторного пространства над и выбором двух линейных аффинных преобразований и . Триплет формирует приватный ключ. Приватный полином определён на . Публичным ключом является полином .[2]
Скрытые уравнения поля имеют четыре основных модификации: +, -, v и f, и их можно комбинировать по-разному. Основной принцип заключается в следующем[2]:
Модификация «+» состоит из линейного комбинирования публичных уравнений с некоторыми случайными уравнениями.
Модификация «-» появился благодаря Ади-Шамиру и удаляет избыточность «» из публичных уравнений.
Модификация «f» состоит из фиксации некоторых входных переменных открытого ключа.
Модификация «v» определяется как сложная конструкция, такая что обратная функция может быть найдена только в том случае, если некоторые v переменных фиксированы. Эта идея принадлежит Жаку Патарину.
Две самые известные атаки на систему скрытых уравнений поля[4]:
Получение закрытого ключа (Шамир-Кипнис): ключевым моментом этой атаки является восстановление закрытого ключа как разреженных одномерных многочленов над полем расширений . Атака работает только для базовой системы скрытых уравнений поля и не работает для всех её вариаций.
Атака, основанная на алгоритме Грёбнера (разработана Жаном-Чарльзом Фужером): идея атаки заключается в использовании быстрого алгоритма для вычисления базиса Грёбнера системы полиномиальных уравнений. Фужер взломал HFE в рамках the HFE Challenge 1 за 96 часов в 2002 году. В 2003 году Фужер вместе с Жу работали над безопасностью HFE.