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

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

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

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

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

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

ЧИТАТЬ МАТЕРИАЛ

Комментарии:

НОВЫЕ СТАТЬИ

Microsoft «убьет» Windows 7 в начале 2020
Владимир Смирнов Вчера 09:10
Amazon занялась квантовыми вычислениями
Владимир Смирнов 4 Декабря 09:34