Advantages of Logarithmic Signatures in the Implementation of Crypto Primitives

Yevhen Kotukh; Hennadii Khalimov

Автор(и)

Євген Котух Національний технічний університет «Дніпровська політехніка»
https://orcid.org/0000-0003-4997-620X
Геннадій Халімов Харківський національний університет радіоелектроніки
https://orcid.org/0000-0002-2054-9186

Ключові слова:

складні обчислювальні задачі, криптографія, квантова криптографія, логарифмічні підписи

Анотація

Складні обчислювальні задачі, або "важкі проблеми" для кратності, - це широкий термін, що охоплює проблеми, які вимагають значної кількості ресурсів для вирішення. Криптографія використовує їх, установлюючи еквівалентність між безпекою схеми та нерозв'язністю складної задачі. Два важких завдання широко використовуються в криптографії з відкритим ключем: розкладання цілих чисел та проблема дискретного логарифму. У 1994 році Шор показав, що ці класичні складні проблеми можна легко вирішити на великому квантовому комп'ютері. Квантовостійкі криптосистеми на основі решіток та інших пост-квантових кандидатів також використовують складні обчислювальні задачі. Ми позичимося вважати, що будь-який алгоритм, який має властивості регулярності в структурованих даних, буде зламаний квантовим комп'ютером. Властивості суперпозиції та квантової заплутаності дозволяють виконувати обчислення на всіх станах реєстра кубітів одночасно. Ця властивість моделює повний набір станів класичного комп'ютера. Наявність регулярності у обчислювальних даних алгоритму, наприклад, періодичність (резонанси частоти) в алгебраїчних структурах (кільцях, групах, решітках і т.д.), потенційно може бути відфільтрована деяким алгоритмом з складністю менше, ніж у алгоритму Гровера. У статті ми пропонуємо змінити підхід до проектування криптосистем. Ми замінюємо концепцію проблеми, яка складно вирішується, на проблему з багатьма еквівалентними рішеннями без регулярностей, коли всі рішення однаково ймовірні. У цьому випадку квантова криптоаналітика зводиться до схеми Гровера з експоненційною складністю реалізації. Ми поставимо лінійні рівняння щодо невідомих, для яких ми використовуємо значення логарифмічних підписів. Кількість рівнянь для секретних значень логарифмічних підписів менше їх кількості. Це призводить до неповної системи лінійних рівнянь щодо невідомих та неможливості їх вирішення за поліноміальний час.

Завантажити

Дані для завантаження поки недоступні.

Посилання

Peter W. Shor. Algorithms for quantum computation: Discrete log-arithms and factoring. In 35th FOCS, pages 124–134. IEEE Comput-er Society Press, November 1994

SS Magliveras , “A cryptosystem from logarithmic signatures of finite groups,” in Proceedings of the 29th Midwest Symposium on Circuits and Systems, pp. 972–975, Elsevier Publishing, Amsterdam, The Netherlands, 1986.

SS Magliveras and ND Memon, “ Algebraic properties of cryp-tosystem PGM,” Journal of Cryptology, vol.5, no.3, pp.167–183, 1992.

A. Caranti and F. Dalla Volta, “The round functions of cryptosys-tem PGM generate the symmetric group,” Designs, Codes and Cryp-tography, vol.38, no.1, pp.147–155, 2006.

S. S. Magliveras , P. Svaba , T. van Trung , and P. Zajac, “On the security of a realization of cryptosystem MST3”, Tatra Mountains Mathematical Publications, vol.41, pp.65– 78, 2008.

P. Svaba and T. van Trung, “Public key cryptosystem MST3 crypt-analysis and realization”, Journal of Mathematical Cryptology, vol. 4, no. 3, pp. 271–315, 2010.

Gennady Khalimov, Yevgen Kotukh, Oleksandr Sievierinov , Svitlana Khalimova , Sang-Yoon Chang, Yaroslav Balytskyi , Strong Encryption Based on the small Ree groups International Conference “Problems of Infocommunications. Science and Technology” (PIC S&T′2022) October 10 – 12, 2022 Kyiv – Kharkiv.