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

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

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

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

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

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

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

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

НОВЫЕ СТАТЬИ

Chrome и Firefox защитят от государственного spyware?
Владимир Смирнов 22 Августа 08:59
БАКОТЕК открывает представительство в Азербайджане
По материалам БАКОТЕК 20 Августа 11:19
Мировые расходы на ИКТ будут стабильно расти
Владимир Смирнов 20 Августа 09:36