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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Шифрование

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

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

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

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

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

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

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

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

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

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

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

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

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

Скорость

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

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

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

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

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$ $\text{[math]}$ to $n$ $\text{[math]}$ 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-алгоритма возможно проводить атаку на открытый ключ. [4]

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

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

Примечания

JINTAI DING, DIETER SCHMIDT. Reuleaux Triangle (англ.). MULTIVARIABLE PUBLIC–KEY CRYPTOSYSTEMS.
H. Ong, C.-P. Schnorr and A. Shamir Efficient signature schemes based on polynomial equations. In CRYPTO, volume 196 of Lecture Notes in Computer Science // Springer : journal. — 1984, pages 37–46.
T. Matsumoto and H. Imai EPublic quadratic polynomial-tuples for efficient signature verifi- cation and message-encryption. In EUROCRYPT, volume 330 of Lecture Notes in Computer Science // Springer : journal. — 1988, pages 419–553
Albrecht Petzoldt. Selecting and Reducing Key Sizes for Multivariate Cryptography (англ.).
Jintai Ding, Jason Gower, and Deiter Schmidt Multivariate Public Key Cryptosystems // Springer : journal. — 2006.
Jintai Ding and Bo-Yin Yang. Multivariate Public Key Cryptography (англ.).
NESSIE. Reuleaux Triangle (англ.). NESSIE: New European Schemes for Signatures, Integrity, and Encryption. NESSIE project announces final selection of crypto algorithms. Information Society Technologies Programme of the European Commission (IST-1999-12324).
Introduction
Shuaiting Qiao, Wenbao Han, Yifa Li, and Luyao Jiao. Construction of Extended Multivariate Public Key Cryptosystems (англ.).
Lih-Chung Wang, Bo-Yin Yang, Yu-Hua Hu, and Feipei Lai. A Medium-Field Multivariate Public-Key Encryption Scheme (англ.).
Jacques Patarin, Louis Goubin, and Nicolas Courtois. Reuleaux Triangle (англ.). Improved Algorithms for Isomorphisms of Polynomials (1998). Springer.
Jacques Patarin. IHidden Field Equations (HFE) and Isomorphisms of Polynomials (IP): two new Families of Asymmetric Algorithms (англ.).
Takanori Yasuda, Xavier Dahan, Yun-Ju Huang, Tsuyoshi Takagi and Kouichi Sakurai1. MQ Challenge (англ.). MQ Challenge: Hardness Evaluation of Solving Multivariate Quadratic Problems.
I.-T. Chen, M.-S. Chen, T.-R. Chen, C.-M. Cheng, J. Ding, E. L.-H. Kuo, F. Y.-S. Lee and B.-Y. Yang SSE implementation of multivariate PKCs on modern x86 CPUs. In CHES, volume 5747 of Lecture Notes in Computer Science // Springer : journal. — 2009, pages 33–48
A. Bogdanov, T. Eisenbarth, A. Rupp and C. Wolf Time-area optimized public-key engines: MQ-cryptosystems as replacement for elliptic curves? // Springer : CHES, volume 5154 of Lecture Notes in Computer Science. — 2008, pages 45–61
J. Patarin, N. Courtois and L. Goubin Flash, a fast multivariate signature algorithm // Springer : In CT-RSA, volume 2020 of Lecture Notes in Computer Science. — 2001, pages 298–307
B. Preneel The NESSIE project: Towards new cryptographic algorithms // Swww.cryptonessie.org — 2000
Raymond Heindl. New Directions in Multivariate Public Key Cryptography (англ.).
Harriet Fell and Whitfield Diffie Analysis of a public key approach based on polynomial substitution. In Advances in cryptology—CRYPTO ’85 (Santa Barbara, Calif.) // Springer : journal. — 1986. — volume 218, pages 340–349.
T. Matsumoto and H. Imai Public quadratic polynomial-tuples for efficient signature verification and message encryption. In C. G. Guenther, editor, Advances in cryptology – EUROCRYPT ’88 // Springer : journal. — 1988. — volume 330, pages 419–453.
Jacques Patarin, Louis Goubin, and Nicolas Courtois C∗−+ and HM: variations around two schemes of T. Matsumoto and H. Imai. In K. Ohta and D. Pei,editors, ASIACRYPT’98 // Springer : journal. — 1998. — volume 1514, pages 35–50.

Ссылки

Multivariate Public Key Cryptography

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[jinss-1] JINTAI DING, DIETER SCHMIDT. Reuleaux Triangle (англ.). MULTIVARIABLE PUBLIC–KEY CRYPTOSYSTEMS.

[2] H. Ong, C.-P. Schnorr and A. Shamir Efficient signature schemes based on polynomial equations. In CRYPTO, volume 196 of Lecture Notes in Computer Science // Springer : journal. — 1984, pages 37–46.

[3] T. Matsumoto and H. Imai EPublic quadratic polynomial-tuples for efficient signature verifi- cation and message-encryption. In EUROCRYPT, volume 330 of Lecture Notes in Computer Science // Springer : journal. — 1988, pages 419–553

[XL-4] Albrecht Petzoldt. Selecting and Reducing Key Sizes for Multivariate Cryptography (англ.).

[автоссылка1-5] Jintai Ding, Jason Gower, and Deiter Schmidt Multivariate Public Key Cryptosystems // Springer : journal. — 2006.

[ding-6] Jintai Ding and Bo-Yin Yang. Multivariate Public Key Cryptography (англ.).

[nessie-7] NESSIE. Reuleaux Triangle (англ.). NESSIE: New European Schemes for Signatures, Integrity, and Encryption. NESSIE project announces final selection of crypto algorithms. Information Society Technologies Programme of the European Commission (IST-1999-12324).

[pq-8] Introduction

[aacqpatar-9] Shuaiting Qiao, Wenbao Han, Yifa Li, and Luyao Jiao. Construction of Extended Multivariate Public Key Cryptosystems (англ.).

[jins-10] Lih-Chung Wang, Bo-Yin Yang, Yu-Hua Hu, and Feipei Lai. A Medium-Field Multivariate Public-Key Encryption Scheme (англ.).

[acque-11] Jacques Patarin, Louis Goubin, and Nicolas Courtois. Reuleaux Triangle (англ.). Improved Algorithms for Isomorphisms of Polynomials (1998). Springer.

[acqpatar-12] Jacques Patarin. IHidden Field Equations (HFE) and Isomorphisms of Polynomials (IP): two new Families of Asymmetric Algorithms (англ.).

[kmoddl-13] Takanori Yasuda, Xavier Dahan, Yun-Ju Huang, Tsuyoshi Takagi and Kouichi Sakurai1. MQ Challenge (англ.). MQ Challenge: Hardness Evaluation of Solving Multivariate Quadratic Problems.

[14] I.-T. Chen, M.-S. Chen, T.-R. Chen, C.-M. Cheng, J. Ding, E. L.-H. Kuo, F. Y.-S. Lee and B.-Y. Yang SSE implementation of multivariate PKCs on modern x86 CPUs. In CHES, volume 5747 of Lecture Notes in Computer Science // Springer : journal. — 2009, pages 33–48

[15] A. Bogdanov, T. Eisenbarth, A. Rupp and C. Wolf Time-area optimized public-key engines: MQ-cryptosystems as replacement for elliptic curves? // Springer : CHES, volume 5154 of Lecture Notes in Computer Science. — 2008, pages 45–61

[16] J. Patarin, N. Courtois and L. Goubin Flash, a fast multivariate signature algorithm // Springer : In CT-RSA, volume 2020 of Lecture Notes in Computer Science. — 2001, pages 298–307

[17] B. Preneel The NESSIE project: Towards new cryptographic algorithms // Swww.cryptonessie.org — 2000

[raymond-18] Raymond Heindl. New Directions in Multivariate Public Key Cryptography (англ.).

[19] Harriet Fell and Whitfield Diffie Analysis of a public key approach based on polynomial substitution. In Advances in cryptology—CRYPTO ’85 (Santa Barbara, Calif.) // Springer : journal. — 1986. — volume 218, pages 340–349.

[20] T. Matsumoto and H. Imai Public quadratic polynomial-tuples for efficient signature verification and message encryption. In C. G. Guenther, editor, Advances in cryptology – EUROCRYPT ’88 // Springer : journal. — 1988. — volume 330, pages 419–453.

[21] Jacques Patarin, Louis Goubin, and Nicolas Courtois C∗−+ and HM: variations around two schemes of T. Matsumoto and H. Imai. In K. Ohta and D. Pei,editors, ASIACRYPT’98 // Springer : journal. — 1998. — volume 1514, pages 35–50.