Введение
Криптосистема с открытым ключом Hidden Fields Equations (HFE), также известная как функция с ловушкой HFE, является криптосистемой с открытым ключом, представленной на Eurocrypt в 1996 году и предложенной Жаком Патарином, основываясь на идее системы Мацумото и Имай. Она базируется на многочленах над конечными полями различного размера для маскировки связи между секретным и открытым ключами. HFE фактически представляет собой семейство, состоящее из базовой HFE и комбинаторных вариантов HFE. Семейство криптосистем HFE основано на вычислительной сложности задачи поиска решений системы многомерных квадратных уравнений (так называемая проблема MQ), поскольку в нем используются секретные аффинные преобразования для сокрытия поля расширения и секретных многочленов. Уравнения скрытых полей также использовались для построения схем цифровой подписи, например, Quartz и Sflash.
Hidden Fields Equations (HFE), also known as HFE trapdoor function, is a public key cryptosystem which was introduced at Eurocrypt in 1996 and proposed by Jacques Patarin following the idea of the Matsumoto and Imai system. It is based on polynomials over finite fields of different size to disguise the relationship between the private key and public key. HFE is in fact a family which consists of basic HFE and combinatorial versions of HFE. The HFE family of cryptosystems is based on the hardness of the problem of finding solutions to a system of multivariate quadratic equations (the so called MQ problem) since it uses private affine transformations to hide the extension field and the private polynomials. Hidden Field Equations also have been used to construct digital signature schemes, e. g. Quartz and Sflash.
Математическая подготовка
Одним из центральных понятий для понимания работы уравнений скрытых полей является то, что для двух полей расширения над одним и тем же базовым полем можно интерпретировать систему многовариантных многочленов от переменных как функцию, используя подходящий базис из над . В подавляющем большинстве приложений многочлены являются квадратичными, то есть имеют степень 2. Начнем с простейшего вида многочленов, а именно мономов, и покажем, как они приводят к квадратичным системам уравнений. Рассмотрим конечное поле , где – степень 2, и поле расширения . Пусть , такое что для некоторых и НОД. Условие НОД эквивалентно требованию, чтобы отображение на было взаимно однозначным, а его обратное отображение – , где – мультипликативная обратная величина .
Возьмем случайный элемент. Определим следующим образом:
Пусть будет базисом над как векторное пространство размерности . Представим относительно базиса как , а пусть будет матрицей линейного преобразования относительно базиса , то есть такой, что
для . Кроме того, запишем все произведения базисных элементов через базис, то есть:
для каждого . Система уравнений, явно выраженная через и квадратичная по , может быть получена разложением (1) и приравниванием к нулю коэффициентов при .
Выберем два секретных аффинных преобразования и , то есть две невырожденные матрицы и с элементами из и два вектора и длины над , и определим и следующим образом:
Используя аффинные соотношения в (2) для замены на , система уравнений становится линейной по и квадратичной по . Применяя линейную алгебру, получим явные уравнения, по одному для каждого , как многочлены степени 2 относительно .
Многовариантная криптосистема
Основная идея семейства HFE, заключающаяся в использовании данной схемы как многовариантной криптосистемы, состоит в построении секретного ключа, начиная с многочлена от одной неизвестной над некоторым конечным полем (обычно используется значение ). Этот многочлен можно легко обратить в , то есть осуществимо найти любое решение уравнения, если такое решение существует. Секретное преобразование, будь то расшифровка или подпись, основано на этом обращении. Как было объяснено выше, можно представить как систему уравнений, используя фиксированный базис. Для построения криптосистемы многочлен необходимо преобразовать таким образом, чтобы публичная информация скрывала исходную структуру и препятствовала обращению. Это достигается путем рассмотрения конечных полей как векторного пространства над и выбором двух линейных аффинных преобразований и . Тройка образует секретный ключ. Приватный многочлен определен над . Публичный ключ приведен ниже. Ниже представлена диаграмма ловушки MQ в HFE.
Полином HFE
Частный многочлен со степенью над является элементом . Если члены многочлена содержат степени не выше второй над , то это позволит сохранить общественный многочлен малым.
Шифрование и расшифрование
Публичный ключ задается многомерными многочленами над полем 𝔽q. Таким образом, необходимо передать сообщение m из 𝔽q, чтобы зашифровать его, то есть мы предполагаем, что m является вектором. Для шифрования сообщения m мы вычисляем значение каждого многочлена fi в точке m. Шифротекст равен (f1(m), f2(m), ..., fn(m)).
To understand decryption let us express encryption in terms of Note that these are not available to the sender. By evaluating the at the message we first apply , resulting in At this point is transferred from so we can apply the private polynomial which is over and this result is denoted by Once again, is transferred to the vector and the transformation is applied and the final output is produced from
To decrypt , the above steps are done in reverse order. This is possible if the private key is known. The crucial step in the deciphering is not the inversion of and but rather the computations of the solution of Since is not necessary a bijection, one may find more than one solution to this inversion (there exist at most d different solutions since is a polynomial of degree d). The redundancy denoted as is added at the first step to the message in order to select the right from the set of solutions The diagram below shows the basic HFE for encryption.
Чтобы понять расшифровку, выразим шифрование через полиномы, которые известны только получателю. Вычисляя fi(m), мы сначала применяем преобразование T, в результате чего получаем T(m). В этой точке T(m) передается из 𝔽q, чтобы мы могли применить секретный полином h, который определен над 𝔽q, и этот результат обозначается h(T(m)). Снова, h(T(m)) передается в векторный вид, и применяется преобразование S, в результате чего получается конечный выход c = S(h(T(m))).
To understand decryption let us express encryption in terms of Note that these are not available to the sender. By evaluating the at the message we first apply , resulting in At this point is transferred from so we can apply the private polynomial which is over and this result is denoted by Once again, is transferred to the vector and the transformation is applied and the final output is produced from
To decrypt , the above steps are done in reverse order. This is possible if the private key is known. The crucial step in the deciphering is not the inversion of and but rather the computations of the solution of Since is not necessary a bijection, one may find more than one solution to this inversion (there exist at most d different solutions since is a polynomial of degree d). The redundancy denoted as is added at the first step to the message in order to select the right from the set of solutions The diagram below shows the basic HFE for encryption.
Для расшифровки c, вышеуказанные шаги выполняются в обратном порядке. Это возможно, если известен секретный ключ h. Ключевым шагом в расшифровке является не инверсия преобразований S и T, а вычисление решения уравнения S(h(x)) = c. Поскольку S не обязательно является биекцией, может существовать более одного решения этого уравнения (существует не более d различных решений, поскольку h – полином степени d). Избыточность, обозначаемая как r, добавляется на первом шаге к сообщению m, чтобы выбрать правильное решение x из множества возможных решений. На диаграмме ниже показана базовая схема HFE для шифрования.
To understand decryption let us express encryption in terms of Note that these are not available to the sender. By evaluating the at the message we first apply , resulting in At this point is transferred from so we can apply the private polynomial which is over and this result is denoted by Once again, is transferred to the vector and the transformation is applied and the final output is produced from
To decrypt , the above steps are done in reverse order. This is possible if the private key is known. The crucial step in the deciphering is not the inversion of and but rather the computations of the solution of Since is not necessary a bijection, one may find more than one solution to this inversion (there exist at most d different solutions since is a polynomial of degree d). The redundancy denoted as is added at the first step to the message in order to select the right from the set of solutions The diagram below shows the basic HFE for encryption.
Изменения HFE
Уравнения скрытого поля имеют четыре основных варианта, а именно +, , v и f, и их можно комбинировать различными способами. Основной принцип заключается в следующем:
01. Знак + состоит из линейного смешения публичных уравнений со случайными уравнениями. 02. Знак принадлежит Ади Шамиру и предназначен для удаления избыточности 'r' из публичных уравнений. 03. Знак f состоит из фиксации некоторых входных переменных открытого ключа. 04. Знак v определяется как конструкция, иногда довольно сложная, такая что обратная функция может быть найдена только если некоторые из переменных, называемых "уксусными" переменными, фиксированы. Эта идея принадлежит Жаку Патарину. Вышеуказанные операции в некоторой степени сохраняют свойство решаемости функции с "лазейкой". HFE и HFEv очень полезны в схемах цифровой подписи, поскольку они предотвращают замедление генерации подписи и повышают общую безопасность HFE. В то время как для шифрования HFE и HFEv приведут к довольно медленному процессу дешифрования, поэтому нельзя удалять слишком много уравнений (HFE) и добавлять слишком много переменных (HFEv). HFE и HFEv использовались для получения Quartz. Для шифрования ситуация лучше с HFE+, поскольку процесс дешифрования занимает то же время, однако открытый ключ содержит больше уравнений, чем переменных.