Гибридный аргумент (криптография)

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

История

Гибридные аргументы возникли в работах Эндрю Яо в ​​1982 году и Шафи Голдвассера и Сильвио Микали в 1983 году.

Формальное описание

Формально, чтобы показать, что два распределения D ₁ и D ₂ вычислительно неразличимы, мы можем определить последовательность гибридных распределений D ₁ := H ₀ , H ₁ , ..., H _t =: D ₂ , где t является полиномиальным по безопасности. параметр н . Определим преимущество любого вероятностно-эффективного (полиномиально ограниченного по времени) алгоритма A как

${\mathsf {Adv}}_{H_{i},H_{i+1}}^{\mathsf {dist}}(\mathbf {A} ):=\left|\Pr[x{\stackrel {\$}{\gets }}H_{i}:\mathbf {A} (x)=1]-\Pr[x{\stackrel {\$}{\gets }}H_{i+1}:\mathbf {A} (x)=1]\right|,$

где символ доллара ($) означает, что мы выбираем элемент из распределения случайным образом.

Из неравенства треугольника ясно, что для любого вероятностного алгоритма с полиномиальным A временем

${\mathsf {Adv}}_{D_{1},D_{2}}^{\mathsf {dist}}(\mathbf {A} )\leq \sum _{i=0}^{t-1}{\mathsf {Adv}}_{H_{i},H_{i+1}}^{\mathsf {dist}}(\mathbf {A} ).$

Таким образом, должны существовать некоторые k st 0 ⩽ k < t(n) и

${\mathsf {Adv}}_{H_{k},H_{k+1}}^{\mathsf {dist}}(\mathbf {A} )\geq {\mathsf {Adv}}_{D_{1},D_{2}}^{\mathsf {dist}}(\mathbf {A} )/t(n).$

Поскольку t полиномиально ограничено, для любого такого алгоритма A имеет пренебрежимо малую функцию преимущества между распределениями Hi _{мы можем показать, что он} и Hi _{, если +1} для каждого i , то есть

$\epsilon (n)\geq {\mathsf {Adv}}_{H_{k},H_{k+1}}^{\mathsf {dist}}(\mathbf {A} )\geq {\mathsf {Adv}}_{D_{1},D_{2}}^{\mathsf {dist}}(\mathbf {A} )/t(n),$

тогда сразу следует, что его преимущество в различении распределений D ₁ = H ₀ и D ₂ = H _t также должно быть незначительным. Этот факт порождает гибридный аргумент: достаточно найти такую ​​последовательность гибридных распределений и показать, что каждая пара из них вычислительно неотличима.

Приложения

Гибридный аргумент широко используется в криптографии. Вот некоторые простые доказательства с использованием гибридных аргументов:

• Если невозможно эффективно предсказать следующий бит вывода некоторого генератора чисел, то этот генератор является генератором псевдослучайных чисел (PRG).
• Мы можем безопасно расширить PRG с 1-битным выходом до PRG с n -битным выходом.

См. также

• Интерактивная система доказательств
• Универсальная компоновка

Ссылки

• Додис, Евгений. «Введение в лекцию по криптографии, 5 примечаний» (PDF) . Архивировано из оригинала (PDF) 25 декабря 2014 г.
• Пас, Рафаэль. «Курс криптографии» (PDF) .
• Фишлин, Марк; Миттельбах, Арно. «Обзор гибридного аргумента» (PDF) .