Квантовая криптография: новый математический фундамент безопасности

Математика современных шифров: NP-задачи

Современные шифры держатся на математике. Их основа — так называемые NP-задачи (non-deterministic polynomial time). Это задачи, для которых:
– найти решение очень трудно,
– но проверить готовый ответ легко.

Классический пример: разложить огромное число на простые множители. Решение почти безнадёжное, а проверка занимает мгновения. На этом и строится интернет-безопасность. Но если однажды кто-то найдёт быстрый алгоритм для таких задач, вся система рухнет.

Квантовая физика как новая основа криптографии

Казалось, другого фундамента нет. Но в последние годы внимание криптографов повернулось к квантовой физике. В ней нашлись новые «строительные блоки», которые могут заменить классические основы.

В 2023 году криптографы Дакшита Курана и Кабир Томар сделали шаг вперёд. Они предложили концепцию «однонаправленных головоломок» (quantum one-way puzzles). Это квантовые аналоги однонаправленных функций (one-way functions — функций, которые легко вычислить, но почти невозможно обратить). Такие структуры создают замки и ключи: замки прочные, ключи существуют, но открыть ими замок напрямую почти невозможно. Парадокс? Да. Но именно из этого парадокса можно собрать целый набор протоколов шифрования.

Перманент матрицы и квантовая криптография

Дальше — ещё интереснее. Учёные показали, что эти головоломки можно связать с одной из самых трудных задач линейной алгебры — вычислением перманента матрицы.
Перманент (в отличие от знакомого определителя) вычисляется похожей формулой по всем перестановкам, но без чередования знаков. Для больших матриц его нахождение считается одной из самых сложных задач: проверить правильность ответа почти так же трудно, как его найти.

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

Квантовая криптография против классических шифров: крепость вместо башни на песке

Пока это теория. Но она меняет сам взгляд на безопасность. Если классическая криптография похожа на башню, построенную на песке NP-задач, то квантовая обещает возвести крепость на камне.

В будущем эта крепость может стать основой всего цифрового мира — от переписки до финансовых транзакций. И всё это — благодаря новой математике, которая соединяет глубины алгебры с законами квантовой механики.

✨ Вопрос лишь в том, кто первый построит реальный замок на этом фундаменте.