Доказуемая безопасность и редукции

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

Definition

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

Scope

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

Core questions

• Как редукция преобразует атаку на схему в решение сложной проблемы?
• В чем разница между доказательствами, основанными на играх, и доказательствами, основанными на симуляции?
• Что означает «плотность» редукции для реальных параметров безопасности?
• Что такое модели случайного оракула и стандартная модель, и почему первая является спорной?
• Каковы ограничения и распространенные ловушки аргументов доказуемой безопасности?

Key concepts

• редукция безопасности
• доказательства, основанные на играх
• доказательства, основанные на симуляции
• плотные и неплотные редукции
• конкретная безопасность
• модель случайного оракула
• стандартная модель
• пренебрежимое преимущество
• предположение о сложности

Key theories

Методология редукционного доказательства

Чтобы доказать безопасность схемы, предполагается противник, который ее взламывает, и с использованием этого противника в качестве подпрограммы строится алгоритм, решающий основную сложную проблему — таким образом, успешная атака противоречила бы предположению о сложности.

Модель случайного оракула

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

Mechanisms

В редукции доказывающий предполагает гипотетического противника, который взламывает схему с не пренебрежимым преимуществом, и строит оболочку, которая встраивает экземпляр трудной проблемы в представление противника, запускает противника и использует его вывод для решения проблемы. Доказательства, основанные на играх, проходят через последовательность неразличимых игр от реальной схемы до той, где противник явно не может выиграть. Плотность редукции — сколько преимущества и времени выполнения теряется — определяет размеры ключей, необходимые для целевого уровня безопасности.

Clinical relevance

Доказуемая безопасность является стандартом, по которому криптографические схемы заслуживают доверия и стандартизации: AES, SHA-3 и постквантовые процессы NIST уделяли большое внимание доказательствам безопасности, а такие протоколы, как TLS 1.3, сопровождались редукционистскими и машинопроверяемыми анализами. Понимание редукций позволяет специалистам оценивать, что утверждение о безопасности гарантирует, а что нет, и выбирать параметры, учитывающие плотность редукции.

Evidence & guidelines

Современная практика отдает предпочтение доказательствам в стандартной модели, когда это возможно, и рассматривает доказательства случайного оракула как сильное эвристическое свидетельство, а не абсолютные гарантии. Инструментальные фреймворки (EasyCrypt, CryptoVerif) предоставляют машинопроверяемые доказательства. Конкретный (точный) анализ безопасности, который количественно определяет преимущество противника как функцию ресурсов, предпочтительнее чисто асимптотических утверждений для установки реальных параметров.

History

Редукционистская методология возникла с революцией в определениях в начале 1980-х годов и была систематизирована в 1990-х годах. Белларе и Рогавей представили модель случайного оракула (1993) для доказательства безопасности практических схем, а затем анализ «конкретной безопасности» для количественной оценки гарантий. Результат Канетти, Голдрейха и Халеви 1998 года, показывающий схемы, безопасные в модели случайного оракула, но небезопасные при инстанцировании, обострил дебаты об идеализированных моделях.

Key figures

• Mihir Bellare
• Phillip Rogaway
• Oded Goldreich
• Shafi Goldwasser
• Silvio Micali

Seminal works

• bellare1993
• katz2020
• goldreich2001

Frequently asked questions

Означает ли доказательство безопасности, что схему никогда нельзя взломать?

Нет. Доказательство показывает, что взлом схемы подразумевает решение предполагаемой сложной проблемы в рамках указанной модели. Если предположение неверно, модель нереалистична или реализация отклоняется от анализируемой схемы, атаки остаются возможными. Доказательства снижают, но не устраняют риск.

Почему модель случайного оракула считается спорной?

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