В чем разница между классической криптографией и постквантовой криптографией?

10

Будет ли необходимость менять определения безопасности, если у нас будут квантовые компьютеры? Какие криптографические конструкции сломаются? Знаете ли вы опрос или статью, которая объясняет, что нужно будет изменить?

анонимное
источник
1
Вы можете найти эту статью, доступную через ACM, интересной; кажется, он отвечает на ваш вопрос или, по крайней мере, на его аспекты: dl.acm.org/… Если у вас нет доступа, он может быть доступен для скачивания через Интернет. В противном случае я могу прочитать его и попытаться кратко изложить основные моменты.
Patrick87
1
@ Patrick87: Для меня это платная система. Резюме будет оценено. :)
Ли Аунг Ип

Ответы:

6

Краткое содержание этой статьи дает (частичный) ответ.

Существует два вида традиционных криптографических методов с открытым ключом: методы, основанные на целочисленной факторизации, и методы, основанные на дискретном логарифме, включая методы на основе эллиптических кривых. Эти модели считаются сложными в классических моделях, но было показано, что ни одна из них не является сложной в квантовой модели.

Хотя Гровер разработал квантовый алгоритм, обеспечивающий квадратичное ускорение поиска, Беннет, Бернштейн, Брассард и Вазирани показали, что квантовая модель не может обеспечить экспоненциальное ускорение для задач поиска. Это предполагает, что алгоритмы симметричного шифрования, односторонние функции и криптографические хеши должны противостоять квантовым атакам. Таким образом, основное внимание должно быть уделено разработке безопасных методов с открытым ключом.

Подписи Лампорта могут обеспечить механизм одноразовой подписи, защищенный от квантовых атак. Проблемы решетки могут стать основой для методов с открытым ключом, которые устойчивы к квантовым атакам; в частности, задачи кратчайшего вектора и ближайшего вектора NP-Hard являются привлекательными. Как для классической, так и для квантовой моделей, эти проблемы считаются сложными для решеток большой размерности. NTRU семейство криптографических алгоритмов, на основе решетчатых проблем, может обеспечить практические средства достижения криптографии с открытым ключом , устойчивой к квантовым атакам. Другая проблема, которая может служить основой для безопасных методов с открытым ключом, - это проблема декодирования синдрома. Система шифрования McEliece основана на этой проблеме, и варианты могут обеспечить путь вперед.

Patrick87
источник
0

Я ни в коем случае не эксперт (или даже близко к этому) по теме, но из того, что я знаю:

Классическая криптография зависит от неразрешимости факторинга (или проблемы дискретного журнала). Однако факторинг, как полагают, не является NP-полным, и он действительно разрешим в полиномиальном времени квантовыми компьютерами. Таким образом, любая криптография, которая зависит от этих операций, будет взломана (это все виды криптографии, которые мне известны).

Квантовая криптография зависит от квантовой механики, и теоретически ее невозможно взломать. Это совсем не вопрос времени - он просто основан на случайности и на том факте, что состояние измеряется при измерении, поэтому без соответствующей информации ваш лучший выбор - просто «угадать» сообщение ... что бесполезно ,

user541686
источник