Уравнения скрытого поля - Hidden Field Equations

Уравнения скрытых полей (HFE) , также известные как функция-лазейка HFE , представляют собой криптосистему с открытым ключом, которая была представлена на Eurocrypt в 1996 году и предложена (на французском языке) Жаком Патарином, следуя идее системы Мацумото и Имаи. Он основан на полиномах над конечными полями разного размера, чтобы замаскировать взаимосвязь между закрытым ключом и открытым ключом . Фактически, HFE - это семейство, состоящее из базовых HFE и комбинаторных версий HFE. Семейство криптосистем HFE основано на сложности проблемы поиска решений системы многомерных квадратных уравнений (так называемая проблема MQ), поскольку оно использует частные аффинные преобразования, чтобы скрыть поле расширения и частные многочлены . Уравнения скрытого поля также использовались для построения схем цифровой подписи, например Quartz и Sflash. ${\ displaystyle \ mathbb {F} _ {q}}$

Математический фон

Одним из центральных понятий , чтобы понять , как скрытое поле Уравнения работы видеть , что для двух полей расширения по сравнению с аналогичным базовым полем можно интерпретировать систему многомерных полиномов в переменных над как функции , используя подходящий базис из более чем . Почти во всех приложениях многочлены квадратичны, т. Е. Имеют степень 2. Мы начнем с простейшего вида многочленов, а именно с одночленов, и покажем, как они приводят к квадратным системам уравнений. ${\ Displaystyle \ mathbb {F} _ {д ^ {п}}}$ ${\ Displaystyle \ mathbb {F} _ {д ^ {м}}}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ displaystyle m}$ ${\ displaystyle n}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ Displaystyle \ mathbb {F} _ {д ^ {п}} \ to \ mathbb {F} _ {д ^ {м}}}$ ${\ Displaystyle \ mathbb {F} _ {д ^ {п}}}$ ${\ displaystyle \ mathbb {F} _ {q}}$

Рассмотрим конечное поле , где - степень двойки, и поле расширения . Пусть такое, что для некоторых и gcd . Условие gcd эквивалентно требованию, чтобы отображение on было взаимно однозначным, а его обратным было отображение, где - мультипликативное обратное . ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ displaystyle q}$ ${\ displaystyle K}$ ${\ Displaystyle 0 <ч <д ^ {п}}$ ${\ Displaystyle ч = д ^ {\ тета} +1}$ ${\ displaystyle \ theta}$ ${\ Displaystyle (ч, д ^ {п} -1) = 1}$ ${\ Displaystyle (ч, д ^ {п} -1) = 1}$ ${\ Displaystyle и \ к и ^ {ч}}$ ${\ displaystyle K}$ ${\ Displaystyle и \ к и ^ {ч '}}$ ${\ displaystyle h '}$ ${\ displaystyle h \ {\ bmod {q}} ^ {n} -1}$

Возьмите случайный элемент . Определить по ${\ Displaystyle и \ в \ mathbb {F} _ {д ^ {п}}}$ ${\ Displaystyle ш \ в \ mathbb {F} _ {д ^ {п}}}$

{\ Displaystyle ш = и ^ {ч} = и ^ {д ^ {\ тета}} и \ \ \ \ (1)}

Пусть быть основой в качестве векторного пространства . Представим относительно основания как и . Пусть - матрица линейного преобразования относительно базиса , т.е. такая, что ${\ displaystyle \ beta _ {1}, ..., \ beta _ {n}}$ ${\ displaystyle K}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ displaystyle u}$ ${\ displaystyle u = (u_ {1}, ..., u_ {n})}$ ${\ Displaystyle ш = (ш_ {1}, ..., ш_ {п})}$ ${\ Displaystyle А ^ {(к)} = {а_ {ij} ^ {(к)}}}$ ${\ Displaystyle и \ к и ^ {д ^ {к}}}$ ${\ displaystyle \ beta _ {1}, ..., \ beta _ {n}}$

{\ displaystyle \ beta _ {i} ^ {q ^ {k}} = \ sum _ {j = 1} ^ {n} a_ {ij} ^ {k} \ beta _ {j}, \ \ a_ {ij } ^ {k} \ in \ mathbb {F} _ {q}}

для . Кроме того, запишите все произведения базовых элементов в терминах основы, то есть: ${\ Displaystyle 1 \ Leq я, к \ Leq п}$

{\ displaystyle \ beta _ {i} \ beta _ {j} = \ sum _ {l = 1} ^ {n} m_ {ijl} \ beta _ {l}, \ \ m_ {ijl} \ in \ mathbb { F} _ {q}}

для каждого . Система уравнений, которая является явной по и квадратичной по, может быть получена расширением (1) и приравниванием к нулю коэффициентов при . ${\ Displaystyle 1 \ Leq я, J \ Leq п}$ ${\ displaystyle n}$ ${\ displaystyle w_ {i}}$ ${\ displaystyle u_ {j}}$ ${\ displaystyle \ beta _ {я}}$

Выберите два секретных аффинных преобразования и , то есть две обратимые матрицы и с записями в и двумя векторами и длины over и define и via: ${\ displaystyle S}$ ${\ displaystyle T}$ ${\ Displaystyle п \ раз п}$ ${\ Displaystyle M_ {S} = \ {S_ {ij} \}}$ ${\ Displaystyle M_ {T} = \ {T_ {ij} \}}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ displaystyle v_ {S}}$ ${\ displaystyle v_ {T}}$ ${\ displaystyle n}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ displaystyle x}$ ${\ displaystyle y}$

{\ Displaystyle и = Sx = M_ {S} x + v_ {S} \ \ \ \ w = Ty = M_ {T} y + v_ {T} \ \ \ \ (2)}

Используя аффинные соотношения в (2) , чтобы заменить с , система уравнений является линейной в и степени 2 в . Применяя линейную алгебру, он даст явные уравнения, по одному для каждого в виде многочленов степени 2 от . ${\ displaystyle u_ {j}, w_ {i}}$ ${\ displaystyle x_ {k}, y_ {l}}$ ${\ displaystyle n}$ ${\ displaystyle y_ {l}}$ ${\ displaystyle x_ {k}}$ ${\ displaystyle n}$ ${\ displaystyle y_ {l}}$ ${\ displaystyle x_ {k}}$

Многовариантная криптосистема

Основная идея семейства HFE, использующего это в качестве многомерной криптосистемы, состоит в том, чтобы построить секретный ключ, начиная с полинома от одного неизвестного над некоторым конечным полем (обычно используется значение ). Этот многочлен легко инвертируется , т.е. возможно найти любые решения уравнения, когда такое решение существует. Секретное преобразование, дешифрование и / или подпись основано на этой инверсии. Как объяснялось выше, можно отождествить с системой уравнений, использующей фиксированный базис. Для построения криптосистемы полином должен быть преобразована так , что общественная информация скрывает первоначальную структуру и предотвращает инверсию. Это делается путем просмотра конечных полей как векторного пространства над и выбирая два линейных аффинных преобразований и . Тройка составляет закрытый ключ. Частный полином определяется над . Открытый ключ - это . Ниже представлена схема MQ-люка в HFE. ${\ displaystyle P}$ ${\ displaystyle x}$ ${\ Displaystyle \ mathbb {F} _ {д ^ {п}}}$ ${\ displaystyle q = 2}$ ${\ Displaystyle \ mathbb {F} _ {д ^ {п}}}$ ${\ Displaystyle P (x) = y}$ ${\ displaystyle P}$ ${\ displaystyle n}$ ${\ displaystyle (p_ {1}, ..., p_ {n})}$ ${\ displaystyle (p_ {1}, ..., p_ {n})}$ ${\ Displaystyle \ mathbb {F} _ {д ^ {п}}}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ displaystyle S}$ ${\ displaystyle T}$ ${\ Displaystyle (S, P, T)}$ ${\ displaystyle P}$ ${\ Displaystyle \ mathbb {F} _ {д ^ {п}}}$ ${\ displaystyle (p_ {1}, ..., p_ {n})}$ ${\ Displaystyle (S, P, T)}$

{\ displaystyle {\ text {input}} x \ to x = (x_ {1}, ..., x_ {n}) {\ overset {{\ text {secret}}: S} {\ to}} x '{\ overset {{\ text {secret}}: P} {\ to}} y' {\ overset {{\ text {secret}}: T} {\ to}} {\ text {output}} y}

Полином HFE

Частный многочлен со степенью выше является элементом . Если члены полинома содержат не более квадратичных членов, тогда публичный полином останется малым. Случай, состоящий из одночленов вида , т.е. с двумя степенями в экспоненте, является базовой версией HFE , т.е. выбран как ${\ displaystyle P}$ ${\ displaystyle d}$ ${\ Displaystyle \ mathbb {F} _ {д ^ {п}}}$ ${\ Displaystyle \ mathbb {F} _ {д ^ {п}} [х]}$ ${\ displaystyle P}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ displaystyle P}$ ${\ displaystyle x ^ {q ^ {s_ {i}} + q ^ {t_ {i}}}}$ ${\ displaystyle q}$ ${\ displaystyle P}$

{\ Displaystyle P (x) = \ сумма c_ {i} x ^ {q ^ {s_ {i}} + q ^ {t_ {i}}}}

Степень от полинома также известна как параметр безопасности и большим его , тем лучше для безопасности значение , так как результирующий набор квадратных уравнений напоминает случайно выбранный набор квадратных уравнений. С другой стороны, большой размер замедляет расшифровку. Поскольку является многочленом степени, не более обратной к , обозначается, может быть вычислен в операциях. ${\ displaystyle d}$ ${\ displaystyle d}$ ${\ displaystyle P}$ ${\ displaystyle d}$ ${\ displaystyle P}$ ${\ Displaystyle P ^ {- 1}}$ ${\ displaystyle d ^ {2} (\ ln d) ^ {O (1)} n ^ {2} \ mathbb {F} _ {q}}$

Шифрование и дешифрование

Открытый ключ задается многомерными полиномами над . Таким образом , необходимо , чтобы передать сообщение от того , чтобы зашифровать его, т.е. мы предполагаем , что вектор . Чтобы зашифровать сообщение, мы оцениваем каждое по адресу . Зашифрованный текст есть . ${\ displaystyle n}$ ${\ displaystyle (p_ {1}, ..., p_ {n})}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ displaystyle M}$ ${\ displaystyle \ mathbb {F} _ {q ^ {n}} \ to \ mathbb {F} _ {q} ^ {n}}$ ${\ displaystyle M}$ ${\ displaystyle (x_ {1}, ..., x_ {n}) \ in \ mathbb {F} _ {q} ^ {n}}$ ${\ displaystyle M}$ ${\ displaystyle p_ {i}}$ ${\ displaystyle (x_ {1}, ..., x_ {n})}$ ${\ displaystyle (p_ {1} (x_ {1}, ..., x_ {n}), p_ {2} (x_ {1}, ..., x_ {n}), ..., p_ { n} (x_ {1}, ..., x_ {n})) \ in \ mathbb {F} _ {q} ^ {n}}$

Чтобы понять расшифровку, давайте выразим шифрование в терминах . Обратите внимание , что это не доступно отправителю. Оценивая в сообщении, мы сначала применяем , в результате чего . На этом этапе выполняется перенос из, чтобы мы могли применить закрытый многочлен, который закончился, и этот результат обозначен как . Еще раз, переносится в вектор и преобразование применяется и окончательный вывод производится из . ${\ Displaystyle S, T, P}$ ${\ displaystyle p_ {i}}$ ${\ displaystyle S}$ ${\ displaystyle x '}$ ${\ displaystyle x '}$ ${\ Displaystyle \ mathbb {F} _ {д ^ {п}} \ to \ mathbb {F} _ {д ^ {п}}}$ ${\ displaystyle P}$ ${\ Displaystyle \ mathbb {F} _ {д ^ {п}}}$ ${\ Displaystyle у '\ в \ mathbb {F} _ {д ^ {п}}}$ ${\ displaystyle y '}$ ${\ displaystyle (y_ {1} ', ..., y_ {n}')}$ ${\ displaystyle T}$ ${\ Displaystyle у \ в \ mathbb {F} _ {д ^ {п}}}$ ${\ displaystyle (y_ {1}, ..., y_ {n}) \ in \ mathbb {F} _ {q} ^ {n}}$

Для расшифровки вышеуказанные шаги выполняются в обратном порядке. Это возможно, если известен закрытый ключ . Решающий шаг в расшифровке не инверсия и а вычисления решения . Поскольку биекция не является обязательной, можно найти более одного решения этой инверсии (существует не более d различных решений, поскольку является многочленом степени d). Избыточность, обозначенная как , добавляется на первом шаге к сообщению , чтобы выбрать нужное из множества решений . На диаграмме ниже показан базовый HFE для шифрования. ${\ displaystyle y}$ ${\ Displaystyle (S, P, T)}$ ${\ displaystyle S}$ ${\ displaystyle T}$ ${\ Displaystyle P (x ') = y'}$ ${\ displaystyle P}$ ${\ displaystyle X '= (x_ {1}', ..., x_ {d} ') \ in \ mathbb {F} _ {q ^ {n}}}$ ${\ displaystyle P}$ ${\ displaystyle r}$ ${\ displaystyle M}$ ${\ displaystyle M}$ ${\ displaystyle X '}$

{\ displaystyle M {\ overset {+ r} {\ to}} x {\ overset {{\ text {secret}}: S} {\ to}} x '{\ overset {{\ text {secret}}: P} {\ to}} y '{\ overset {{\ text {secret}}: T} {\ to}} y}

Варианты HFE

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

01. Знак + представляет собой смешивание линейности общедоступных уравнений с некоторыми случайными уравнениями.

02. - знак из - за Ади Шамир и намерена удалить избыточность «г» из общественных уравнений.

03. Знак f состоит из фиксации некоторых входных переменных открытого ключа.

{\ displaystyle f}

04. Знак v определяется как конструкция и иногда довольно сложная, так что обратная функция может быть найдена, только если некоторые v переменных, называемых переменными уксуса, фиксированы. Эта идея принадлежит Жаку Патарену.

Приведенные выше операции в некоторой степени сохраняют лазейную разрешимость функции.

HFE- и HFEv очень полезны в схемах подписи, поскольку они предотвращают замедление генерации подписи, а также повышают общую безопасность HFE, тогда как для шифрования и HFE-, и HFEv приведут к довольно медленному процессу дешифрования, поэтому не может быть слишком много уравнений. удалено (HFE-) и не следует добавлять слишком много переменных (HFEv). И HFE- и HFEv были использованы для получения кварца.

Для шифрования ситуация лучше с HFE +, поскольку процесс дешифрования занимает такое же количество времени, однако открытый ключ имеет больше уравнений, чем переменных.

HFE атаки

Есть две известные атаки на HFE:

Восстановление закрытого ключа ( Шамир- Кипнис): ключевым моментом этой атаки является восстановление закрытого ключа в виде разреженных одномерных многочленов по полю расширения . Атака работает только для базового HFE и терпит неудачу для всех его вариаций. ${\ Displaystyle \ mathbb {F} _ {д ^ {п}}}$

Быстрые базисы Гребнера (Фогер): Идея атак Фогера заключается в использовании быстрого алгоритма для вычисления базиса Гребнера системы полиномиальных уравнений. Фогер преодолел задачу 1 HFE за 96 часов в 2002 году, а в 2003 году Фогер и Жу вместе работали над безопасностью HFE.

Languages

In other projects