UOV

05.03.2021

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

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

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

Процедура создания подписи

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

y 1 = f 1 ( x 1 , … , x n ) y 2 = f 2 ( x 1 , … , x n )   ⋮ y m = f m ( x 1 , … , x n ) {displaystyle {egin{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 , … , y m ) {displaystyle y=(y_{1},y_{2},ldots ,y_{m})} это сообщение, которое необходимо подписать. Действительной подписью здесь будет вектор x = ( x 1 , x 2 , … , x n ) {displaystyle x=(x_{1},x_{2},ldots ,x_{n})} , полученный при решении данной системы уравнений.

Чтобы подписать исходное сообщение y {displaystyle y} его нужно преобразовать таким образом, чтобы оно удовлетворяло системе уравнений. Для этого как раз и используется преобразование T {displaystyle T} необходимое для «разбиения» сообщения на фрагменты, которые обозначены как y 1 , y 2 , … , y m {displaystyle y_{1},y_{2},ldots ,y_{m}} . После этого строится система уравнений, где каждое уравнение системы должно быть записано в виде:

y i = ∑ γ i j k a j a ´ k + ∑ λ i j k a ´ j a ´ k + ∑ ξ i j a j + ∑ ξ ´ i j a ´ j + δ i {displaystyle 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 {displaystyle y} получения действительной подписи x {displaystyle x} необходимо выполнить следующие шаги:

  • Коэффициенты γ i j k , λ i j k , ξ i j , ξ ´ i j , δ i {displaystyle gamma _{ijk},lambda _{ijk},xi _{ij},{acute {xi }}_{ij},delta _{i}} должны быть выбраны секретными
  • «Уксусные» переменные ( a ´ u {displaystyle {acute {a}}_{u}} ) выбираются случайным образом
  • Конечная система уравнений решается относительно неизвестных «масляных» переменных ( a i {displaystyle a_{i}} )
  • С помощью найденных переменных масла и уксуса ( a i {displaystyle a_{i}} ) и ( a ´ u {displaystyle {acute {a}}_{u}} ) строится предварительная подпись A = ( a 1 , … , a n , a ´ 1 , … , a ´ u ) {displaystyle A=(a_{1},ldots ,a_{n},{acute {a}}_{1},ldots ,{acute {a}}_{u})} . Наконец, A {displaystyle A} при помощи секретного биективного афинного преобразования S {displaystyle S} преобразуется действительную подпись x = S − 1 ( A ) {displaystyle x=S^{-1}(A)} .

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

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

    ∀ i {displaystyle forall i} 1 ⩽ i ⩽ n {displaystyle 1leqslant ileqslant n} y i = P i ( x 1 , x 2 , … , x n + u ) {displaystyle y_{i}={P_{i}}(x_{1},x_{2},ldots ,x_{n+u})}

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

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

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

    y 1 = P 1 ∗ ( x 1 , x 2 , … , x n ) y 2 = P 2 ∗ ( x 1 , x 2 , … , x n )   ⋮ y m = P m ∗ ( x 1 , x 2 , … , x n ) {displaystyle {egin{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 {displaystyle n} и u {displaystyle u}

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

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

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

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

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

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