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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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}}}$; где ${\displaystyle f_{i}\in \mathbb {F} [x_{1},\ldots ,x_{n}]}$ — многочлен второй степени.

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

Шифрование

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Изоморфизм многочленов.^[12]

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

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

• Скорость

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

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

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

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

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

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

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

XL алгоритм

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

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

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

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

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

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