Пошук академічних текстів

Інформація × Реєстраційний номер 2124U000089, Матеріали видань та локальних репозитаріїв Категорія Стаття, Опубліковано, Рецензована стаття Назва роботи Переваги логарифмічних підписів у впровадженні криптографічних примітивів Автор Котух ЄвгенХалімов ГеннадійKotukh YevhenKhalimov Hennadii Дата публікації 14-06-2024 Постачальник інформації Дніпровський національний університет імені Олеся Гончара Першоджерело https://cims.fti.dp.ua/j/article/view/119 Видання Oles Honchar Dnipro National University Опис Складні обчислювальні задачі, або "важкі проблеми" для кратності, - це широкий термін, що охоплює проблеми, які вимагають значної кількості ресурсів для вирішення. Криптографія використовує їх, установлюючи еквівалентність між безпекою схеми та нерозв'язністю складної задачі. Два важких завдання широко використовуються в криптографії з відкритим ключем: розкладання цілих чисел та проблема дискретного логарифму. У 1994 році Шор показав, що ці класичні складні проблеми можна легко вирішити на великому квантовому комп'ютері. Квантовостійкі криптосистеми на основі решіток та інших пост-квантових кандидатів також використовують складні обчислювальні задачі. Ми позичимося вважати, що будь-який алгоритм, який має властивості регулярності в структурованих даних, буде зламаний квантовим комп'ютером. Властивості суперпозиції та квантової заплутаності дозволяють виконувати обчислення на всіх станах реєстра кубітів одночасно. Ця властивість моделює повний набір станів класичного комп'ютера. Наявність регулярності у обчислювальних даних алгоритму, наприклад, періодичність (резонанси частоти) в алгебраїчних структурах (кільцях, групах, решітках і т.д.), потенційно може бути відфільтрована деяким алгоритмом з складністю менше, ніж у алгоритму Гровера. У статті ми пропонуємо змінити підхід до проектування криптосистем. Ми замінюємо концепцію проблеми, яка складно вирішується, на проблему з багатьма еквівалентними рішеннями без регулярностей, коли всі рішення однаково ймовірні. У цьому випадку квантова криптоаналітика зводиться до схеми Гровера з експоненційною складністю реалізації. Ми поставимо лінійні рівняння щодо невідомих, для яких ми використовуємо значення логарифмічних підписів. Кількість рівнянь для секретних значень логарифмічних підписів менше їх кількості. Це призводить до неповної системи лінійних рівнянь щодо невідомих та неможливості їх вирішення за поліноміальний час. Додано в НРАТ 2024-07-30 Закрити