UOV

В криптографии схема Unbalanced Oil and Vinegar  “Несбалансированная схема масла и уксуса” (Далее для удобства будем называть схемой UOV) представляет собой модифицированную версию стандартной схемы Oil and Vinegar  «Масла и уксуса», разработанной Дж. Патарином. Свое название схема получила ввиду использования двух типов переменных: "уксусных" и "масляных",формирующих открытый ключ. В самих уравнениях эти величины не перемножаются, т.е. не смешиваются подобно маслу и уксусу, используемых в кулинарии. Отсюда и пошло такое название. Обе эти схемы  являются схемами цифровой подписи. Они относятся к группе многомерной криптографии. Безопасность подписи данной схемы основана на решении  NP-полной задачи. Для создания и проверки подписей необходимо решить систему минимальных квадратичных уравнений. Решение $m$ уравнений с $n$ переменными является NP-трудной задачей, что означает, что проблему почти наверняка трудно эффективно решить в худшем случае, даже при использовании квантового компьютера. В то время как задача становится простой, если значение $m$ намного больше $n$ или намного меньше $n$,в среднем случае когда $m$ и  почти равны  проблема считается сложной, даже при использовании квантового компьютера. В результате был разработан ряд схем цифровых подписей на основе многомерных уравнений с целью достижения квантово-устойчивых сигнатур.

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

Математической задачей является решение   $m$ уравнений c $n$ Вся система уравнений сама по себе и является открытым ключом. Чтобы использовать такую задачу для применения в криптографии, ее необходимо было изменить. Для вычисления $n$ переменных требуется много ресурсов. Стандартный компьютер не может вычислить это за приемлемое время. Поэтому в систему уравнений вставляется так называемая односторонняя функция с потайным входом или Trapdoor, которая будет являться ключом подписи, состоящим  из трех частей: двух аффинных преобразований $T$ и $S$ и вектора полиномов $P$. Оба преобразования используются для разбиения элементов исходного сообщения на определенные группы. Афинное преобразование $T$ преобразует исходное сообщение $y$ в $y_{1},y_{2},...,y_{n}$. Второе преобразование $S$ преобразует вектор из переменных в действительную подпись. Третий секретный элемент $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$необходимо выполнить следующие шаги:

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

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

Таким образом, каждое значение $y_{i}$может быть записано как квадратичный полином $P_{i}$от неизвестных $x_{j}$, где $1\leqslant j\leqslant n+u$.

Поэтому система $n$ квадратичных уравнений $P$ будет являться открытым ключом. где:

$\forall i$ $1\leqslant i\leqslant n$ $y_{i}={P_{i}}(x_{1},x_{2},\ldots ,x_{n+u})$

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

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

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

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

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

Результаты по анализу на криптографическую стойкость

В данной таблице находятся основные результаты, полученные при попытках взлома схемы UOV при различных значениях $n$ и $u$

Пусть $K$= $F_{q}$конечное поле $q=p^{m}$ . Элементы $a_{1},\ldots ,a_{n}$ и ${\acute {a}}_{1},\ldots ,{\acute {a}}_{u}$- его элементы и $n+u=p$

"Сложностью сравнимой со случайным решением" означает что сложность взлома сопоставима с решением систем уравнений относительно перемененных $u$когда коэффиценты выбираются случайным образом

Степень	Вломано	Не взломано	Не взломано и сложность сравнима со случайным решением	Взломано, не смотря на то что сложность сравнима со случайным решением
2 ( для всех $p$)	$u\leqslant n$или $u\simeq n$	$2n\leqslant u\leqslant {\frac {n^{2}}{2}}$	${\frac {n^{2}}{2}}\leqslant u\leqslant n^{2}$	$u\geqslant n^{2}$
3 ( для $p=2$)	$u\leqslant (1+{\sqrt {3}})n$	$(1+{\sqrt {3}})n\leqslant u\leqslant {\frac {n^{3}}{6}}$	${\frac {n^{3}}{6}}\leqslant u\leqslant {\frac {n^{3}}{2}}$	$u\geqslant {\frac {n^{3}}{6}}$
3 ( для $p\neq 2$)	$u\leqslant n$или $u\simeq n$	$2n\leqslant u\leqslant {\frac {n^{2}}{2}}$	${\frac {n^{3}}{6}}\leqslant u\leqslant n^{4}$	$u\geqslant n^{4}$

Преимущества и недостатки схемы масла и уксуса

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

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

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

Ссылки

• Buchmann, Johannes; Coronado, Carlos; Doring, Martin; Engelbert, Daniela; Ludwig, Christoph; Overbeck, Raphael; Schmidt, Arthur; Vollmer, Ulrich; Weinmann, Ralf-Philipp: Post-Quantum Signatures, –, October 29. 2004
• Wolf, Christopher: Multivariate Quadratic Polynomials in Public Key Cryptography, DIAMANT/EIDMA symposium 2005
• Coron, Jean-Sebastien; de Weger, Benne: Hardness of the Main Computational Problems Used in Cryptography, ECRYPT D.AZTEC.6, March 14. 2007
• Faugère, Jean-Charles and Perret, Ludovic. On the security of UOV. Cryptology eprint archive. Report 2009/483. 2009
• Unbalanced Oil and Vinegar Signature Schemes - Louis Goubin