Многовариантная криптография - Multivariate cryptography

Многовариантная криптография общий термин для асимметричных криптографический примитивы на основе многомерные полиномы через конечное поле ${ displaystyle F}$ . В некоторых случаях эти многочлены могут быть определены как на основании, так и на расширении. поле. Если полиномы имеют степень два, мы говорим о многомерном квадратики. Решение систем многомерных полиномиальные уравнения доказано, что это НП-полный.^[1] Вот почему эти схемы часто считаются хорошими кандидатами на постквантовая криптография. Многовариантная криптография оказалась очень продуктивной с точки зрения дизайна и криптоанализа. В целом ситуация стала более стабильной, и самые сильные схемы выдержали испытание временем. Принято считать, что многомерная криптография оказалась более успешной как подход к построению схемы подписи в первую очередь потому, что многомерные схемы обеспечивают самую короткую сигнатуру среди постквантовых алгоритмов.

История

Цутому Мацумото и Хидеки Имаи (1988 ) представили свою так называемую схему C * на Еврокрипт конференция. Хотя C * был взломан Жаком Патареном (1995 ), общий принцип Мацумото и Имаи вдохновил поколение улучшенных предложений. В более поздних работах "Скрытые мономиальные криптосистемы" были разработаны (На французском) Жак Патарен. Он основан на поле земли и пристройки. "Уравнения скрытого поля "(HFE), разработанный Патариным в 1996 году, остается популярной многомерной схемой сегодня [P96]. Безопасность HFE была тщательно исследована, начиная с прямого Основа Грёбнера атака [FJ03, GJS06], атаки с восстановлением ключа (Кипнис и Шамир 1999 ) [BFP13] и другие. Обычная версия HFE считается практически неработающей в том смысле, что безопасные параметры приводят к непрактичной схеме. Однако некоторые простые варианты HFE, такие как минус вариант и вариант уксуса позволяют усилить базовый HFE против всех известных атак.

Помимо HFE, Патарин разработал и другие схемы. В 1997 году он представил «Сбалансированное масло и уксус», а в 1999 году - «Несбалансированное масло и уксус ”В сотрудничестве с Авиадом Кипнисом и Луи Губеном (Кипнис, Патарен и Губен 1995 ).

Строительство

Multivariate Quadratics включает в себя открытый и закрытый ключи. Закрытый ключ состоит из двух аффинных преобразований, S и T, и легко инвертируемого квадратичного отображения. ${ displaystyle P ' двоеточие F ^ {m} rightarrow F ^ {n}}$ . Обозначим ${ Displaystyle п раз п}$ матрица аффинный эндоморфизмы ${ displaystyle S двоеточие F ^ {n} rightarrow F ^ {n}}$ к ${ displaystyle M_ {S}}$ а вектор сдвига на ${ displaystyle v_ {S} in F ^ {n}}$ и аналогично для ${ displaystyle T двоеточие F ^ {m} rightarrow F ^ {m}}$ . Другими словами,

${ Displaystyle S (x) = M_ {S} x + v_ {S}}$ и
${ Displaystyle Т (у) = М_ {Т} у '+ v_ {Т}}$ .

Тройка ${ displaystyle (S ^ {- 1}, {P '} ^ {- 1}, T ^ {- 1})}$ это закрытый ключ, также известный как люк. Открытый ключ - это состав ${ Displaystyle P = S circ P ' circ T}$ которое по предположению трудно инвертировать, не зная о лазейке.

Подпись

Подписи генерируются с использованием закрытого ключа и проверяются с использованием открытого ключа следующим образом. Сообщение хешированный к вектору в ${ displaystyle y in F ^ {n}}$ через известную хеш-функцию. Подпись

{ Displaystyle х = P ^ {- 1} (y) = T ^ {- 1} left ({P '} ^ {- 1} left (S ^ {- 1} (y) right) right )}

.

Получатель подписанного документа должен иметь открытый ключ P. Он вычисляет хеш ${ displaystyle y}$ и проверяет, что подпись ${ displaystyle x}$ выполняет ${ Displaystyle P (x) = y}$ .

Приложения

Несбалансированное масло и уксус
Уравнения скрытого поля
SFLASH - пользователем НЕССИ
Радуга
TTS
КВАРЦ
QUAD (шифр)
Четыре схемы многомерной криптографической подписи (GeMMS, LUOV, Rainbow и MQDSS) прошли во второй раунд постквантового конкурса NIST: см. Слайд 12 отчета ^[2].

внешняя ссылка

[1] Шифрование и подпись открытого ключа HFE
[2] HFEBoost

[1] Гарей, Майкл Р. (1979). Компьютеры и сложность: руководство по теории NP-полноты. Джонсон, Дэвид С., 1945-. Сан-Франциско: W.H. Фримен. ISBN 0-7167-1044-7. OCLC 4195125.

[2] Муди, Дастин. «Второй раунд процесса стандартизации NIST PQC». NIST. Получено 11 октября 2020.

[1]

[2]