Несбалансированная схема масла и уксуса

В криптографии несбалансированная схема масла и уксуса (УОВ) представляет собой модифицированную версию схемы масла и уксуса, разработанную Дж. Патарином. Оба являются цифровой подписи протоколами . Это формы многомерной криптографии . Безопасность этой схемы подписи основана на NP-сложной математической задаче. Для создания и проверки подписей необходимо решить минимальную систему квадратных уравнений. Решение $m$ уравнений с $n$ переменными NP-трудно. Хотя проблема проста, если $m$ либо намного больше, либо намного меньше $n$ , ^{[ 1 ]} Что важно для криптографических целей, проблема считается сложной в среднем случае, когда $m$ и $n$ почти равны, даже при использовании квантового компьютера . Схемы множественных сигнатур были разработаны на основе многомерных уравнений с целью достижения квантового сопротивления .

Существенным недостатком UOV является то, что размер ключа может быть большим. Обычно $n$ , количество переменных, выбирается равным удвоенному $m$ , количеству уравнений. Кодирование коэффициентов всех этих уравнений в ключе требует значительного пространства, по крайней мере 200 килобайт для системы, которая обеспечивала бы безопасность, сравнимую с алгоритмом цифровой подписи или алгоритмом цифровой подписи на основе эллиптической кривой .

Ключ подписи и проверки

Схема подписи имеет ключ подписи, который остается конфиденциальным, и ключ проверки, который публикуется. Например, в схемах подписи, основанных на RSA, оба ключа имеют экспоненту. В схеме УОВ, как и в любой другой схеме многовариантной подписи, ключи более сложные.

Математическая задача состоит в том, чтобы решить $m$ уравнения с $n$ переменные. Вся система уравнений является открытым ключом.

Чтобы использовать математическую задачу для криптографии, ее необходимо модифицировать. Вычисление $n$ переменным потребуется много ресурсов. Стандартный компьютер не способен вычислить это за приемлемое время. Поэтому в систему уравнений вставлен специальный люк. Этот люк является ключом для подписи. Он состоит из трёх частей: двух аффинных преобразований $T$ и $S$ и полиномиальный вектор ${\acute {P}}$ . Оба преобразования используются для преобразования элементов в определенных группах. $T$ трансформирует $y$ к $y_{1},y_{2},...,y_{n}$ . Вторая трансформация $S$ преобразует вектор переменной в действительную подпись.

Третий секретный элемент ${\acute {P}}$ предоставляет определенные инструменты для создания уравнений. Уравнения построены по правилам, известным только владельцу ключа подписи.

Создание подписи

Чтобы создать действительную подпись, необходимо решить следующую систему уравнений:

${\begin{aligned}y_{1}&=f_{1}(x_{1},\ldots ,x_{n})\\y_{2}&=f_{2}(x_{1},\ldots ,x_{n})\\&~\vdots \\y_{m}&=f_{m}(x_{1},\ldots ,x_{n})\\\end{aligned}}$

Здесь $y=(y_{1},y_{2},\ldots ,y_{m})$ это заданное сообщение, которое должно быть подписано. Действительная подпись $x=(x_{1},x_{2},\ldots ,x_{n})$ .

Чтобы подписать данный $y$ , сообщение сначала необходимо преобразовать, чтобы оно соответствовало системе уравнений. $T$ используется для «разделения» сообщения на приемлемые части $y_{1},y_{2},\ldots ,y_{m}$ . Затем необходимо построить уравнения. Каждое уравнение имеет одинаковую форму:

$y_{i}=\sum {\gamma _{ijk}a_{j}{\acute {a}}_{k}}+\sum {\lambda _{ijk}{\acute {a}}_{j}{\acute {a}}_{k}}+\sum {\xi _{ij}a_{j}}+\sum {{\acute {\xi }}_{ij}{\acute {a}}_{j}}+\delta _{i}$

Следующие шаги подписывают данное сообщение $y$ и результатом является действительная подпись $x$ .

Коэффициенты, $\gamma _{ijk},\lambda _{ijk},\xi _{ij},{\acute {\xi }}_{ij},\delta _{i}$ , должен выбираться тайно.
Переменные уксуса ( ${\acute {a}}_{j}$ ) выбираются случайным образом
Полученная система линейных уравнений решается относительно нефтяных переменных ( $a_{i}$ )

Переменные уксуса и масла создают предварительную сигнатуру $A=(a_{1},\ldots ,a_{n},{\acute {a}}_{1},\ldots ,{\acute {a}}_{v})$ . Окончательно $A$ преобразуется в результате частной трансформации $S$ дать действующую подпись $x=S^{-1}(A)$ .

Система уравнений становится линейной , если переменные уксуса фиксированы – ни одна переменная масла в уравнении не умножается на другую переменную масла. Поэтому переменные нефти можно легко вычислить, используя, например, алгоритм гауссовой редукции . Создание подписи само по себе является быстрым и простым в вычислительном отношении процессом.

Проверка подписи

Подпись передается партнеру по связи. Проверка подписи осуществляется с помощью открытого ключа, который представляет собой систему уравнений.

${\begin{aligned}y_{1}&={f_{1}}^{*}(x_{1},x_{2},\ldots ,x_{n})\\y_{2}&={f_{2}}^{*}(x_{1},x_{2},\ldots ,x_{n})\\&~\vdots \\y_{m}&={f_{m}}^{*}(x_{1},x_{2},\ldots ,x_{n})\\\end{aligned}}$

Эта система уравнений представляет собой слегка модифицированную версию системы, необходимой для создания подписи. Он модифицирован таким образом, что злоумышленник не может получить информацию о секретных коэффициентах и специальном форматировании переменных масла и уксуса. Для проверки подписи необходимо решить каждое уравнение открытого ключа. Входными данными является сама подпись. Если каждый результат $y_{i}$ равен соответствующей части исходного сообщения, то проверка прошла успешно.

Проблемы и преимущества

Основное преимущество состоит в том, что математическая задача, решаемая в алгоритме, является квантово-устойчивой. Когда будет построен квантовый компьютер, способный факторизовать большие составные числа с использованием алгоритма Шора , это сломает коммерческие схемы подписи, такие как RSA или Эль-Гамаль , которые полагаются на проблемы дискретного логарифма неразрешимость . UOV может оставаться в безопасности, поскольку не известно ни одного алгоритма, который дал бы квантовому компьютеру большое преимущество при решении многомерных систем уравнений.

Второе преимущество состоит в том, что операции, используемые в уравнениях, относительно просты. Подписи создаются и проверяются только путем сложения и умножения «маленьких» значений, что делает эту подпись пригодной для оборудования с низким уровнем ресурсов, например, в смарт-картах .

Недостатком является то, что UOV использует очень длинные ключи, а открытый ключ затрагивает всю систему $m$ уравнения, для которых может потребоваться несколько сотен килобайт . УОВ не получил широкого распространения. Хотя уже известно несколько методов атаки, их может появиться, если UOV станет широко использоваться. UOV еще не готов к коммерческому использованию, поскольку его безопасность требует дальнейшего изучения.

Криптосистема Rainbow основана на UOV и является одним из трех финалистов конкурса NIST на стандарт постквантовой цифровой подписи, хотя недавно были выявлены серьезные опасения относительно ее безопасности, предложенной в конкурсе NIST. Была обнаружена новая атака MinRank на Rainbow, которая снижает безопасность предлагаемой реализации Rainbow до уровня ниже требований, установленных NIST. ^{[ 2 ]} В 2022 году Бёлленс обнаружил новую атаку, которая за выходные восстанавливает закрытый ключ для набора параметров Rainbow L1. ^{[ 3 ]} Сам БПЛА эта атака не затрагивает.

Ссылки

^ Куртуа, Николя; и др. «Решение недоопределенных систем многомерных уравнений» (PDF) . Проверено 16 октября 2016 г.
^ Бёлленс, Уорд (2021). «Улучшенный криптоанализ UOV и Rainbow» . В Канто, Энн; Стандарт, Франсуа-Ксавье (ред.). Достижения в криптологии – EUROCRYPT 2021 . Конспекты лекций по информатике. Том. 12696. Чам: Springer International Publishing. стр. 348–373. дои : 10.1007/978-3-030-77870-5_13 . ISBN 978-3-030-77870-5 . S2CID 226200424 .
^ Бёлленс, Уорд (2022). «Расставание с радугой требует выходных на ноутбуке» . Архив электронной печати по криптологии .

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

[1] Куртуа, Николя; и др. «Решение недоопределенных систем многомерных уравнений» (PDF) . Проверено 16 октября 2016 г.

[2] Бёлленс, Уорд (2021). «Улучшенный криптоанализ UOV и Rainbow» . В Канто, Энн; Стандарт, Франсуа-Ксавье (ред.). Достижения в криптологии – EUROCRYPT 2021 . Конспекты лекций по информатике. Том. 12696. Чам: Springer International Publishing. стр. 348–373. дои : 10.1007/978-3-030-77870-5_13 . ISBN 978-3-030-77870-5 . S2CID 226200424 .

[3] Бёлленс, Уорд (2022). «Расставание с радугой требует выходных на ноутбуке» . Архив электронной печати по криптологии .

[ 1 ]

[ 2 ]

[ 3 ]