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

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

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

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

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