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

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

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

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

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

Мацумото и Имаи использовали биективное отображение ${\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}}}$ .

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

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

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

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

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

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

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

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

Открытый ключ криптосистемы — составное квадратичное преобразование ${\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}$ .

Шифрование

Чтобы зашифровать сообщение ${\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})}$ .

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

Что бы расшифровать шифротекст ${\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}}}$ , а следовательно, и результирующий открытый текст являются уникальными.

Или другими словами, если дан шифротекст ${\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}$ , то такое отображение существует. Таким образом каждое сообщение может быть подписано.

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

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

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

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

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

Дана система ${\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-полной . Сложность решения этой задачи препятствует злоумышленику вычислить закрытый ключ , зная открытый ключ .

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

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

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

• Скорость

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

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

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

В системе SFLASH используется конечное поле ${\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}$ уравнений. Таким образом атака методом повторной линеаризации позволяет уменьшить количество неизвестных переменных в закрытом ключе т.е уменьшить его размерность.

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-алгоритма возможно проводить атаку на открытый ключ.

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

1. .
2. .
3. .
4. Скрытые уравнения поля

Примечания

Ссылки

1. Multivariate Public Key Cryptography