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

Многомерная криптография — это общий термин для асимметричных криптографических примитивов, основанных на многомерных полиномах над конечным полем. $F$. В некоторых случаях эти полиномы могут быть определены как по основному, так и по расширенному полю . Если многочлены имеют степень два, мы говорим о многомерных квадратиках . решения систем многомерных полиномиальных уравнений Доказана NP-полнота . Вот почему эти схемы часто считаются хорошими кандидатами на постквантовую криптографию . Многомерная криптография оказалась очень продуктивной с точки зрения проектирования и криптоанализа . В целом ситуация сейчас более стабильна, и самые сильные схемы выдержали испытание временем. Принято считать, что многомерная криптография оказалась более успешной как подход к построению схем подписи прежде всего потому, что многомерные схемы обеспечивают самую короткую подпись среди постквантовых алгоритмов.

История

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

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

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

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

• $S(x)=M_{S}x+v_{S}$ и
• $T(y)=M_{T}y+v_{T}$.

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

Подпись

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

$x=P^{-1}(y)=T^{-1}\left({P'}^{-1}\left(S^{-1}(y)\right)\right)$.

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

Приложения

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

Ссылки

• [BFP13] Л. Беттале, Жан-Шарль Фожер и Л. Перре, Криптоанализ HFE, Multi-HFE и вариантов нечетных и четных характеристик. DCC'13
• [FJ03] Жан-Шарль Фожер и А. Жу, Алгебраический криптоанализ криптосистем уравнений скрытого поля (HFE) с использованием базисов Грёбнера. КРИПТО'03
• [GJS06] Л. Гранбулан, Антуан Жу, Ж. Стерн: Инвертирование HFE является квазиполиномиальным. КРИПТО'06.
• Кипнис, Авиад; Шамир, Ади (1999). «Криптоанализ криптосистемы с открытым ключом HFE путем релинеаризации». Достижения криптологии – КРИПТО' 99 . Берлин, Гейдельберг: Springer. дои : 10.1007/3-540-48405-1_2 . ISBN  978-3-540-66347-8 . ISSN   0302-9743 . МР   1729291 .
• Кипнис, Авиад; Патарен, Жак; Губен, Луи (1999). «Несбалансированные схемы подписи масла и уксуса» (PDF) . В Жаке Штерне (ред.). Достижения криптологии – КРИПТО' 99 . Еврокрипт'99. Спрингер. дои : 10.1007/3-540-48910-x_15 . ISBN  3-540-65889-0 . ISSN   0302-9743 . МР   1717470 .
• Мацумото, Цутому; Имаи, Хидеки (1988). «Публичные квадратичные полиномиальные кортежи для эффективной проверки подписи и шифрования сообщений». Конспекты лекций по информатике . Берлин, Гейдельберг: Springer. дои : 10.1007/3-540-45961-8_39 . ISBN  978-3-540-50251-7 . ISSN   0302-9743 . МР   0994679 .
• Патарин, Жак (1995). «Криптоанализ схемы открытых ключей Мацумото и Имаи Eurocrypt'88». Достижения в криптологии – CRYPT0' 95 . Конспекты лекций по информатике. Том. 963. Берлин, Гейдельберг: Springer. стр. 248–261. дои : 10.1007/3-540-44750-4_20 . ISBN  978-3-540-60221-7 . ISSN   0302-9743 . МР   1445572 .
• [P96] Жак Патарен, Уравнения скрытого поля (HFE) и изоморфизмы полиномов (IP): два новых семейства асимметричных алгоритмов (расширенная версия); Еврокрипт '96
• Кристофер Вольф и Барт Пренил , Таксономия схем с открытым ключом, основанная на проблеме многомерных квадратных уравнений; Текущая версия: 15 декабря 2005 г.
• Ан Брекен, Кристофер Вольф и Барт Пренил , Исследование безопасности несбалансированных схем подписи масла и уксуса, текущая версия: 6 августа 2005 г.
• Цзиньтай Дин, исследовательский проект: Криптоанализ по схеме многомерной подписи с открытым ключом Rainbow и TTS
• Жак Патарен, Николя Куртуа , Луи Губен, SFLASH, быстрая схема асимметричной подписи для недорогих смарт-карт. Примитивная спецификация и сопроводительная документация.
• Бо-Инь Ян, Чен-Моу Ченг, Бор-Ронг Чен и Цзюнь-Минг Чен, Реализация минимизированного многомерного PKC во встраиваемых системах с низким уровнем ресурсов, 2006 г.
• Бо-Инь Ян, Цзюнь-Мин Чен и Йен-Хун Чен, TTS: высокоскоростные подписи на недорогой смарт-карте, 2004 г.
• Николя Т. Куртуа , Короткие подписи, доказуемая безопасность, общие атаки и вычислительная безопасность многомерных полиномиальных схем, таких как HFE, Quartz и Sflash, 2005 г.
• Альфред Дж. Менезес, Пол К. ван Оршот и Скотт А. Ванстон, Справочник по прикладной криптографии, 1997 г.

Внешние ссылки

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