Квантові комп'ютери зламають будь-який шифр: у США створили новий алгоритм, але є нюанс

Науковець-комп'ютерник із Нью-Йоркського університету Одед Регев придумав алгоритм, який прискорить кількість кубітів, необхідних квантовому комп'ютеру для злому будь-якого шифрування. Про це пише портал Singularity Hub.

Широко відомо, що однією з можливостей квантових комп'ютерів може стати злом будь-якого шифрування за лічені хвилини або години. Ще в 1994 році Пітер Шор з Массачусетського технологічного інституту розробив спосіб визначити, які прості числа потрібно перемножити, щоб отримати певне число — це проблема, відома як факторинг простих чисел. Для великих чисел це неймовірно складна проблема, яка швидко стає нерозв'язною на звичайних комп'ютерах, тому її було використано як основу для популярної схеми шифрування RSA на алгоритмі Шора.

Але, використовуючи переваги квантових явищ, таких як суперпозиція і заплутаність, можна розв'язувати ці проблеми навіть для неймовірно великих чисел. Цей факт викликав неабияку паніку серед експертів з безпеки, не в останню чергу тому, що сьогодні хакери та шпигуни можуть зібрати зашифровані дані, а потім просто дочекатися розробки достатньо потужних квантових комп'ютерів, щоб зламати їх. І хоча стандарти постквантового шифрування вже розроблено, їх впровадження в мережі може зайняти багато років.

Хоча, зараз, для наявних квантових комп'ютерів це все одно відносно довге завдання. Річ у тім, що більшість реалізацій шифрування RSA покладаються на ключі завдовжки щонайменше 2048 біт, що еквівалентно числу довжиною 617 цифр. Дослідники Fujitsu нещодавно підрахували, що повністю відмовостійкому квантовому комп'ютеру з 10 000 кубітами знадобиться 104 дні, щоб зламати таке велике число.

Важливо

Загадковий 4D-метаматеріал допоможе розвитку квантових обчислень: що придумали вчені

Однак новий алгоритм Одеда Регева, описаний в опублікованій роботі, потенційно може істотно знизити ці вимоги. Вчений істотно переробив алгоритм Шора, так що тепер можна знайти прості множники числа, використовуючи набагато менше логічних кроків. Виконання операцій у квантовому комп'ютері передбачає створення невеликих схем із кількох кубітів, відомих як вентилі, які виконують прості логічні операції.

У вихідному алгоритмі Шора кількість елементів, необхідних для факторизації числа, дорівнює квадрату числа біт, що використовуються для його подання, яке позначається як n2. Підхід Регева потребуватиме всього n1,5 вентилів, оскільки він шукає прості множники, виконуючи менші множення багатьох чисел, а не дуже великі множення одного числа. Це також зменшує кількість елементів, необхідних шляхом використання класичного алгоритму для подальшого опрацювання вихідних даних.

У статті Регев підрахував, що для 2048-бітного числа це може скоротити кількість необхідних вентилів на два-три порядки. Якщо це правда, це може дозволити набагато меншим квантовим комп'ютерам зламати шифрування RSA.

Однак існують практичні обмеження. Для початку Регев зазначає, що алгоритм Шора виграє від безлічі оптимізацій, розроблених протягом багатьох років, які зменшують кількість кубітів, необхідних для його запуску. Наразі незрозуміло, чи будуть ці оптимізації працювати за нового підходу.

Але в ідеї вже з'явилися і критики. Наприклад, Мартін Екеро, дослідник квантових обчислень шведського уряду, каже, що алгоритму Регева, схоже, потрібна квантова пам'ять для зберігання проміжних значень. Забезпечення такої пам'яті потребуватиме додаткових кубітів і з'їсть усі наявні в неї обчислювальні переваги.

Проте нове дослідження є своєчасним нагадуванням про те, що, коли йдеться про загрозу для шифрування з боку квантових обчислень, цілі постійно змінюються, і потрібен терміновий перехід до постквантових схем, які знову унеможливлять злом.

Раніше Фокус писав, що найточніший у світі квантовий комп'ютер на підході. Особливі "квазічастинки" під назвою еніони зможуть передавати й обробляти інформацію, не руйнуючись від найменшого впливу навколишнього середовища.