Основы безопасности
Основы безопасности обеспечивают строгую математическую базу криптографии: точные определения того, что означает безопасность, предположения о сложности, на которых базируется безопасность, и редукции, доказывающие надежность схем.
Definition
Основы безопасности включают в себя концептуальные рамки, вычислительные предположения и методы доказательства, используемые для точного определения целей безопасности и строгого подтверждения того, что криптографические конструкции достигают этих целей.
Scope
Эта область охватывает теорию, которая превращает криптографию из искусства в науку: формальные определения безопасности и модели противника, предположения о вычислительной сложности, методология доказуемой безопасности, основанная на редукции, и центральная роль случайности и псевдослучайности. Она рассматривает, как определяется и демонстрируется «безопасность». Она исключает конкретные примитивы и протоколы, которые реализуют эти идеи, поскольку они рассматриваются в областях, ориентированных на криптографию.
Sub-topics
Core questions
- Что формально означает «безопасность» криптографической схемы?
- Как полномочия и цели противника фиксируются в точной модели?
- На каких недоказанных, но правдоподобных предположениях о сложности основывается безопасность?
- Как редукция доказывает, что взлом схемы решит сложную проблему?
- Почему случайность и псевдослучайность являются основополагающими для криптографии?
Key concepts
- определения безопасности
- модели противника
- семантическая безопасность и неразличимость
- предположения о вычислительной сложности
- редукции
- односторонние функции
- псевдослучайность
- пренебрежимо малая вероятность
- вычислительная против теоретико-информационной безопасности
Key theories
- Семантическая безопасность и неразличимость
- Голдвассер и Микали определили безопасность шифрования как семантическую безопасность — зашифрованный текст не раскрывает ничего вычислительно полезного о открытом тексте — что было показано эквивалентным неразличимости зашифрованного текста, заменив смутные интуиции точной, достижимой целью.
- Доказуемая безопасность путем редукции
- Схема доказывается безопасной путем редукции, показывающей, что любой эффективный противник, взламывающий ее, может быть превращен в алгоритм, решающий предполагаемо сложную проблему; таким образом, безопасность является условной относительно предположения, но строгой.
Clinical relevance
Фундаментальный подход является причиной, по которой современной криптографии можно доверять: вместо того чтобы надеяться, что схема выдержит атаку, разработчики доказывают, что ее взлом так же сложен, как хорошо изученная проблема, в рамках точно сформулированной модели противника. Эта методология лежит в основе заявлений о безопасности каждого стандартизированного примитива и протокола, определяет, какие схемы одобряются регулирующими органами и органами по стандартизации, и объясняет, почему специальные, недоказанные конструкции не рекомендуются.
Evidence & guidelines
Анализ доказуемой безопасности в настоящее время является обязательным при стандартизации криптографии (конкурсы NIST для AES, SHA-3 и постквантовых схем учитывали доказательства безопасности и редукции). Машинно-проверяемые доказательства (EasyCrypt) и стандартизированные модели (модель случайного оракула, стандартная модель) обеспечивают строгость, хотя дебаты относительно идеализированных предположений сохраняются. Конструкции, безопасность которых основана только на эвристиках, не рекомендуются.
History
Криптография стала строгой наукой в начале 1980-х годов, когда Голдвассер и Микали представили вероятностное шифрование и семантическую безопасность (1982–1984), дав первые точные определения и доказательства. Яо и Блюм-Микали формализовали псевдослучайность, и методология, основанная на редукции, распространилась в 1980-х и 1990-х годах, консолидировавшись в работе Голдрейха «Основы криптографии». Эта революция в определениях отличает современную криптографию от более раннего создания кодов.
Key figures
- Shafi Goldwasser
- Silvio Micali
- Oded Goldreich
- Andrew Yao
- Manuel Blum
Related topics
Seminal works
- goldwasser1984
- goldreich2001
- katz2020
Frequently asked questions
- Что на самом деле означает «доказуемо безопасный»?
- Это означает, что существует математическое доказательство того, что взлом схемы по крайней мере так же сложен, как решение некоторой проблемы, считающейся неразрешимой, в рамках заявленной модели противника. Это не является абсолютной гарантией: безопасность зависит от предположения о сложности и от того, насколько модель соответствует реальности.
- Почему вообще полагаться на недоказанные предположения о сложности?
- Большинство полезных криптографических систем не могут быть доказаны безопасными безусловно — это решило бы крупные открытые проблемы, такие как P против NP. Вместо этого безопасность сводится к небольшому набору давно изучаемых проблем (факторизация, дискретный логарифм, решетки), сложность которых подтверждается десятилетиями неудачных атак.