Будет ли необходимость менять определения безопасности, если у нас будут квантовые компьютеры? Какие криптографические конструкции сломаются? Знаете ли вы опрос или статью, которая объясняет, что нужно будет изменить?
10
Будет ли необходимость менять определения безопасности, если у нас будут квантовые компьютеры? Какие криптографические конструкции сломаются? Знаете ли вы опрос или статью, которая объясняет, что нужно будет изменить?
Ответы:
Краткое содержание этой статьи дает (частичный) ответ.
Существует два вида традиционных криптографических методов с открытым ключом: методы, основанные на целочисленной факторизации, и методы, основанные на дискретном логарифме, включая методы на основе эллиптических кривых. Эти модели считаются сложными в классических моделях, но было показано, что ни одна из них не является сложной в квантовой модели.
Хотя Гровер разработал квантовый алгоритм, обеспечивающий квадратичное ускорение поиска, Беннет, Бернштейн, Брассард и Вазирани показали, что квантовая модель не может обеспечить экспоненциальное ускорение для задач поиска. Это предполагает, что алгоритмы симметричного шифрования, односторонние функции и криптографические хеши должны противостоять квантовым атакам. Таким образом, основное внимание должно быть уделено разработке безопасных методов с открытым ключом.
Подписи Лампорта могут обеспечить механизм одноразовой подписи, защищенный от квантовых атак. Проблемы решетки могут стать основой для методов с открытым ключом, которые устойчивы к квантовым атакам; в частности, задачи кратчайшего вектора и ближайшего вектора NP-Hard являются привлекательными. Как для классической, так и для квантовой моделей, эти проблемы считаются сложными для решеток большой размерности. NTRU семейство криптографических алгоритмов, на основе решетчатых проблем, может обеспечить практические средства достижения криптографии с открытым ключом , устойчивой к квантовым атакам. Другая проблема, которая может служить основой для безопасных методов с открытым ключом, - это проблема декодирования синдрома. Система шифрования McEliece основана на этой проблеме, и варианты могут обеспечить путь вперед.
источник
Я ни в коем случае не эксперт (или даже близко к этому) по теме, но из того, что я знаю:
Классическая криптография зависит от неразрешимости факторинга (или проблемы дискретного журнала). Однако факторинг, как полагают, не является NP-полным, и он действительно разрешим в полиномиальном времени квантовыми компьютерами. Таким образом, любая криптография, которая зависит от этих операций, будет взломана (это все виды криптографии, которые мне известны).
Квантовая криптография зависит от квантовой механики, и теоретически ее невозможно взломать. Это совсем не вопрос времени - он просто основан на случайности и на том факте, что состояние измеряется при измерении, поэтому без соответствующей информации ваш лучший выбор - просто «угадать» сообщение ... что бесполезно ,
источник