Квантовый компьютер бесполезен для поиска коллизий хеш-функций

Множества задач, допускающих решение на квантовом компьютере и на классическом, совпадают. Весь смысл применения квантового компьютера заключается в том, что некоторые задачи он способен решить значительно быстрее. В блоге Kudelski Security эксперт под псевдонимом JP пояснил, почему, по его мнению, квантовые компьютеры бесполезны для нахождения коллизий хеш-функций.

Квантовые алгоритмы эффективно решают проблемы факторинга и дискретных логарифмов. На классических компьютерах такие задачи решить достаточно сложно, поэтому криптосистема RSA и алгоритм Диффи-Хеллмана считаются надежными. Все используемые на сегодняшний день криптографические схемы подписи, надежность которых основана на факторинге и вычислении дискретного логарифма, могут быть взломаны при помощи квантового компьютера, однако пока таких машин не существует. Даже если квантовый компьютер будет построен, он окажется бесполезен для поиска коллизий хеш-функций (H) или подбора пар определенных сообщений (M1, M2), таких как H(M1)=H(M2). Таким образом, квантовые компьютеры не могут взломать схемы, надежность которых основана на сложности нахождения коллизий, например, SPHINCS или XMSS.

Эксперт приводит ряд ключевых техник, используемых данными схемами: одноразовые схемы подписей, дерево хешей (дерево Меркла) и многоразовые схемы подписей.

Одноразовые алгоритмы позволяют получать устойчивые к взлому подписи даже в случае неимоверного увеличения вычислительной мощности компьютера (например, при использовании квантового компьютера).

Самая большая проблема одноразовых схем подписей - передача открытого ключа. Ральф Меркл (Ralph Charles Merkle) предложил криптосистему, где один открытый ключ можно использовать для множества сообщений. Схема подписи Меркла объединяет в себе схему одноразовой подписи (либо Лампорта, либо Винтерница) с деревом Меркла, что позволяет подписать одним ключом несколько сообщений, не создавая риск для их безопасности.

Дерево Меркла представляет собой математическую структуру, хеширующую различные наборы данных в один компактный хеш: корень Меркла. Базовая идея схемы достаточно проста - это обычное дерево (структура данных), в узлах которого находятся хеши, полученные по данным дочерних узлов. При использовании хеш-дерева верификаторам подписей потребуется хранить только корень хеша (обычно его размер составляет 256 бит), вместо всех открытых ключей, отмечает эксперт.