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

Многомерная криптография или многомерная криптография открытого ключа  — это общий термин, описывающий асимметричные криптографические схемы, построенные на решениях уравнений, основанных на многомерных полиномах над конечным полем $\mathbb {F}$.

Безопасность многомерной криптографии основывается на предположении, что решения системы квадратичных многочленов над конечным полем $\mathbb {F}$, в общем случае, является NP-полной задачей в сильном смысле или просто NP-полной. Вот почему эти схемы часто считаются хорошими кандидатами для постквантовой криптографии.

История создания

Первая попытка построения криптографической схемы на основе многомерных квадратичных полиномов была сделана Онгом, Шнором и Шамиром , где они предлагали схему подписи, основанную на сложности решения уравнения:
$s_{1}^{2}+k*s_{2}^{2}=m(\mod n)$;

Однако безопасность этой схемы по-прежнему основана на сложности факторизации $n=p*q$ и поэтому эта схема неустойчива к атакам при помощи квантовых компьютеров. Разработка многомерных криптографических схем в современном смысле началась в 1988 году со схемы С* Системы Матцумото-Имаи.

Мацумото и Имаи использовали биективное отображение ${\mathcal {F}}$ над степенью $n$ полем расширения $\mathbb {E}$ из $GF(2)$ формы: ${\mathcal {F}}:\mathbb {E} \rightarrow \mathbb {E} ,{\mathcal {F}}(X)=X^{2^{\theta }+1}$.
Чтобы убедиться, что это преобразование обратимо, необходимо выбрать $\theta$ таким образом, что ${\text{НОД}}(2^{\theta }+1,2^{n}-1)=1$. Уравнение выше даёт, благодаря каноническому изоморфизму между $GF(2^{n})$ и векторным пространством $GF(2)^{n}$ систему многомерных квадратичных уравнений ${\mathcal {F}}$ на полем $GF(2)$, объясняется это Эндоморфизмом Фробениуса. Для того чтобы спрятать структуру ${\mathcal {F}}$ Мацумото и Имай использовали два аффинных преобразования ${\mathcal {S}}$ и ${\mathcal {T}}$. Таким образом, они представили открытый ключ в форме: ${\mathcal {P}}={\mathcal {S}}\circ {\mathcal {F}}\circ {\mathcal {T}}$.

Эта конструкция называемая биполярной. Она по-прежнему является стандартным методом построения многомерных криптосистем с открытым ключом.

Стандартная двухполярная конструкция

Многомерная криптография была активной областью исследований, однако, до сих пор отсутствуют многомерные схемы, такие как: протоколы обмена ключами и схемы подписи со специальными свойствами.

Актуальность и перспективы развития

Большинство криптосистем с открытым ключом, используемых на практике, основаны на целочисленной факторизации или дискретных логарифмах (в конечных полях или эллиптических кривых). Однако, эти системы страдают от двух недостатков.

1. Достижения в области теории чисел привели к снижению эффективности вычислений, поэтому размеры параметров должны быть увеличены в соответствии с требованиями безопасности.
2. Если можно построить достаточно большие квантовые компьютеры, алгоритм Шора сделает текущие системы полностью небезопасными. Поэтому важно искать альтернативные системы, которые способствуют эффективной и безопасной связи.

Многомерная криптография с открытым ключом — одна из возможных альтернатив нынешних реализаций алгоритмов шифрования с открытым ключом. В 2003 году система подписи Sflash стала окончательным выбором проекта NESSIE (Новые европейские схемы подписи, целостности и шифрования) . Первая книга о многомерной криптографии, написанная Дингом, Гауэром и Шмидтом, была опубликована в 2006 году . Существует также международный воркшоп, PQCrypto, который посвящен вопросам постквантовой криптографии, в том числе многомерной криптографии.

Основной алгоритм работы

Основной идеей стандартного построения многомерной криптографии является выбор системы ${\mathcal {F}}:\mathbb {F} ^{m}\rightarrow \mathbb {F} ^{n}$ (центральное преобразование) из $m$ многомерных квадратичных многочленов от $n$ переменных, которые могут быть легко инвертированы. После этого выбираются два случайных аффинных обратимых преобразования ${\mathcal {S}}:\mathbb {F} ^{m}\rightarrow \mathbb {F} ^{m}$ и ${\mathcal {T}}:\mathbb {F} ^{n}\rightarrow \mathbb {F} ^{m}$ для того, чтобы скрыть структуру центрального преобразования ${\mathcal {F}}$ в открытом ключе.

Открытый ключ криптосистемы — составное квадратичное преобразование ${\mathcal {P}}={\mathcal {S}}\circ {\mathcal {F}}\circ {\mathcal {T}}$, которое, как предполагается, вряд ли отличается от случайного и поэтому его трудно инвертировать.

Закрытый ключ состоит из ${\mathcal {S}}$, ${\mathcal {F}}$, ${\mathcal {T}}$ и следовательно, это позволяет инвертировать ${\mathcal {P}}$.

Построение публичного ключа

Пусть $\mathbb {F}$ — конечное поле. Публичный ключ алгоритмов многомерной криптографии — это полиномиальное отображение ${\mathcal {P}}:\mathbb {F} ^{n}\rightarrow \mathbb {F} ^{m}$

${\mathcal {P}}(x_{1},\ldots ,x_{n})={\begin{pmatrix}f_{1}(x_{1},\ldots ,x_{n})\\\vdots \\f_{m}(x_{1},\ldots ,x_{n})\end{pmatrix}}$; где $f_{i}\in \mathbb {F} [x_{1},\ldots ,x_{n}]$ — многочлен второй степени.

Для шифрования и дешифрования считаем, что $m\geq n$, для электронной подписи: $m\leq n$.

Шифрование

Чтобы зашифровать сообщение $\mathbf {z} \in \mathbb {F} ^{n}$ или $(x_{1},\ldots ,x_{n})\in \mathbb {F} ^{n}$ необходимо вычислить $\mathbf {h=} {\mathcal {P}}(\mathbf {z} )$. Шифротекст полученного сообщения $\mathbf {z}$ есть $\mathbf {h} \in \mathbb {F} ^{m}$ или $(y_{1},\ldots ,y_{m})={\mathcal {P}}(x_{1},\ldots ,x_{n})$.

Расшифрование

Что бы расшифровать шифротекст $\mathbf {h} \in \mathbb {F} ^{m}$ рекурсивно вычисляется: $\mathbf {x=} {\mathcal {S}}^{-1}(\mathbf {h} )$, $\mathbf {y=} {\mathcal {F}}^{-1}(\mathbf {x} )$ и $\mathbf {z=} {\mathcal {T}}^{-1}(\mathbf {y} )$.

$\mathbf {z} \in \mathbb {F} ^{n}$ — это открытый текст шифротекста $\mathbf {h}$. Так как $m\geq n$, то отображение из $\mathbf {z}$ в ${\mathcal {F}}$, а следовательно, и результирующий открытый текст являются уникальными.

Или другими словами, если дан шифротекст $(y_{1},\ldots ,y_{m})\in \mathbb {F} ^{m}$, необходимо найти $(x_{1},\ldots ,x_{n})\in \mathbb {F} ^{n}$ такой, что ${\mathcal {P}}(x_{1},\ldots ,x_{n})=(y_{1},\ldots ,y_{m})$. Обычно ${\mathcal {P}}$ является инъекцией в криптографических системах, поэтому дешифровка выполняется при помощи вычисления ${\mathcal {P}}^{-1}(y_{1},\ldots ,y_{n})$.

Цифровая подпись

Для того, что бы подписать документ $d$, используется хеш-функция ${\mathcal {H}}:\{0,1\}^{*}\rightarrow \mathbb {F} ^{m}$ для вычисления значения $\mathbf {h} ={\mathcal {H}}(d)\in \mathbb {F} ^{m}$.
Затем необходимо вычислить $\mathbf {x=} {\mathcal {S}}^{-1}(\mathbf {h} )$, $\mathbf {y=} {\mathcal {F}}^{-1}(\mathbf {x} )$ и $\mathbf {z=} {\mathcal {T}}^{-1}(\mathbf {y} )$. Здесь ${\mathcal {F}}^{-1}(\mathbf {x} )$ означает один, возможно, много прообраз $x$ для центрального отображения ${\mathcal {F}}$. Так как $n\geq m$, то такое отображение существует. Таким образом каждое сообщение может быть подписано.

Проверка цифровой подписи

Чтобы проверить подлинность документа, необходимо просто вычислить $\mathbf {h^{,}=} {\mathcal {P}}(\mathbf {z} )$ и значение хеш-функции $\mathbf {h} ={\mathcal {H}}(d)$ от документа. Если $\mathbf {h^{,}=h}$, то подпись принимается, в противном случае отклоняется.

Безопасность

Безопасность алгоритмов многомерной криптографии опирается на следующее:

• Сложность решения квадратичных многомерных систем уравнений над конечными полями.

Дана система ${\mathcal {P}}=(p^{1},\ldots ,p^{m})$ из $m$ нелинейных полиномиальных уравнений с переменными $x_{1},\ldots ,x_{n}$. Необходимо найти значения $\mathbf {x_{1}} ,\ldots ,\mathbf {x_{n}}$ такие, что $p^{1}(\mathbf {x_{1}} ,\ldots ,\mathbf {x_{n}} )=\ldots =p^{m}(\mathbf {x_{1}} ,\ldots ,\mathbf {x_{n}} )$.

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

• Изоморфизм многочленов.

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

Преимущества систем, построенных на алгоритмах многомерной криптографии

• Скорость

Системы, построенные на алгоритмах многомерной криптографии достаточно быстры, особенно для подписи документов. Есть много предпосылок, что они могут быть быстрее, чем классические криптографические схемы с открытыми ключами, например RSA.

• Скромные требования к вычислительным ресурсам

Математические операции, выполняемые многомерными схемами, обычно очень просты: большинству схем требуется только сложение и умножение по небольшим конечным полям. Поэтому многомерные схемы требуют скромных вычислительных ресурсов, что делает их привлекательными для использования на недорогих устройствах, таких как RFID чипы и смарт-карты, без необходимости наличия криптографического сопроцессора. Вариант схемы С*, называемый SFLASH, был предложен Европейской комиссией в качестве стандарта для схем подписи на недорогих устройствах.

В системе SFLASH используется конечное поле $\mathbb {F} ={\frac {Z_{2}[2]}{x^{7}+x+1}}$ также определяется отображение ${\mathcal {P^{-}}}:\mathbb {F} ^{67}\rightarrow \mathbb {F} ^{56}$. Обозначение ${\mathcal {P^{-}}}$ указывает, что $11$ уравнений были удалены из функции ${\mathcal {P}}$, которая построена следующим образом: ${\mathcal {P}}={\mathcal {L_{1}}}\circ {\mathcal {f}}\circ {\mathcal {L_{2}}}$. Здесь ${\mathcal {L_{1}}}$ и ${\mathcal {L_{2}}}$ — два обратимых линейных преобразования. Функция ${\mathcal {f^{-}}}$ имеет вид:${\mathcal {f^{-}}}(X)=X^{1+128^{33}}$. Таким образом, открытый ключ состоит из $56$ квадратичных полиномов c $67$ переменными коэффициентами в $\mathbb {F}$. Каждый квадратичный полином будет иметь $67*34+67+1$ коэффициентов. Для этого требуется $128,3$ КБ памяти, если каждый коэффициент хранится в одном байте, также его можно уменьшить до $112,3$ КБ, если использовать только $7$ бит для каждого коэффициента

Атаки на системы многомерной криптографии

Повторная линеаризация

Атака релинеризации направлена на решение переопределенных систем многомерных квадратичных уравнений. Пусть ${\mathcal {P}}$ - система из $m$ квадратичных уравнений по $n$ переменным $x_{1},\ldots ,x_{n}$. Основная идея заключается в введении новой переменной $x_{ij}$ для каждого квадратичного одночлена $x_{i}x_{j}$. Таким образом, получается система линейных уравнений, если число уравнений достаточно велико, можно использовать метод Гаусса. Нужно удостовериться, действительно ли полученное таким образом решение является решением квадратичного система, при условии, что $x_{ij}=x_{i}x_{j}\forall i,j\in \{1,\ldots ,n\}$. Для решения системы квадратичных уравнений по $n$ переменным этим методом необходимо $m\geq {\frac {(n+1)(n+2)}{2}}-1$ уравнений. Таким образом атака методом повторной линеаризации позволяет уменьшить количество неизвестных переменных в закрытом ключе т.е уменьшить его размерность.

XL алгоритм

Пусть $T_{D}^{n}$ — множество всех многочленов из $\mathbb {F} [x_{1},\ldots ,x_{n}]$ степени $\leq D$.

XL-алгоритм:
Входные данные: множество квадратичных многочленов ${\mathcal {F}}=\{f^{(1)},\ldots ,f^{(m)}\}$.
Выходные данные: вектор $\mathbf {x=} (x_{1},\ldots ,x_{n})$ такой, что $f^{(1)}(\mathbf {x} )=\ldots =f^{(m)}(\mathbf {x} )$.

• for $i=1$ to $n$ do
  • Фиксируется целое число $D>2$.
  • Формируются все многочлены:$h\cdot f^{(j)}$, где $h\in T_{D-2}^{n}$ и $j=1,\ldots ,m$.
  • Необходимо воспользоваться методом Гауса для уравнений, полученных на предыдущем шаге, чтобы сгенерировать одно уравнение, содержащее только $x_{i}$.
  • Если на предыдущем шаге получился, по крайней мере один одномерный многочлен от $x_{i}$, то его необходимо решить, например при помощи алгоритма Берлекэмпа.
  • Необходимо упростить уравнения $f^{(1)},\ldots ,f^{(m)}$ путем замены значения $x_{i}$.
• end for $\mathbf {x=} (x_{1},\ldots ,x_{n})$
• return $\mathbf {x=} (x_{1},\ldots ,x_{n})$

Атака при помощи XL-алгритма позволяет уменьшить размерность закрытого ключа при помощи сведения системы уравнений к инварианту в некоторой переменной. Таким образом при помощи XL-алгоритма возможно проводить атаку на открытый ключ.

Примеры многомерных криптосистем

1. Треугольные криптосистемы .
2. Системы Матцумото-Имаи .
3. Минус-Плюс обобщения системы Мацумото-Имаи .
4. Скрытые уравнения поля
5. Unbalanced Oil and Vinegar

Ссылки

1. [1] Multivariate Public Key Cryptography