80
безопасности, который определяет длину зашифрованного сообщения.
Иными
словами, G˜en(1n) выводит унифицированный ключ k длиной A(n), и шифрова-
ние сообщения m∈ 2A(n) с использованием k∈{0, 1}A(n) является шифртекстом
c := k⊕m. (Расшифрование может осуществляться как обычно, но для нас это
сейчас не так важно.) Совершенная стойкость
шифра Вернама подразумевает
Чтобы проанализировать поведение D, проведем следующие основные на-
блюдения:
1. Если w равномерно выбрана из {0, 1}A(n), тогда вид A, когда он работа-
ет в качестве подпрограммы D, распределен идентично виду A в эксперимен-
те
. Это происходит
из-за того, что когда A запускается в качестве
подпрограммы D(w) в этом случае, A задается шифртекст c = w⊕mb, где w∈{0,
1}A(n) является однородной. Поскольку D выводит 1 точно тогда, когда A до-
бивается успеха в своем подслушивающем эксперименте, вследствие этого мы
имеем (см. уравнение (3.3))
(Индекс первой вероятности явно обозначает, что w выбирается равномерно
из {0, 1}A(n).)
2. Если w, напротив, генерируется выбором однородного k∈{0, 1}n и после-
дующим заданием w := tt(k), вид A, работающего в качестве подпрограммы D,
распределяется идентично виду A в эксперименте
. Это из-за того,
что A, работающему в качестве подпрограммы D, теперь задан шифртекст c =
w⊕mb, где w = tt(k) для однородного k∈{0, 1}n.
Таким образом,
Поскольку tt - псевдослучайный генератор (и D работает в полиномиальном
времени), мы знаем, что существует такая пренебрежимо малая функция negl, что
Используя уравнения (3.4) и (3.5), мы
видим, что
которая подразумевает
Поскольку A явля-
ется произвольным противником, это завершает доказательство того, что П об-
ладает неразличимым шифрованием при наличии подслушивающей стороны.
Легко запутаться в подробностях доказательства и задаваться вопросом, по-
лучилось ли что-нибудь в сравнении с шифром Вернама, не стоит забывать, что
81
шифр Вернама также шифрует A-битные сообщения с помощью операции XOR
по отношению к A-битным строкам! Смысл
конструкции, конечно, заключается в
том, что A-битные строки tt(k) могут быть
значительно длиннее секретного ключа
k. В частности, вышеупомянутая система позволяет зашифровать файл размером
1 Мб с помощью всего лишь 128-битного ключа. Полагаясь на вычислительную
стойкость, мы таким образом обошли невозможность теоремы 2.10, в которой ут-
верждается, что любая совершенно криптостойкая система шифрования должна
использовать ключ по
крайней мере такой же длины, что и сообщение.
Достарыңызбен бөлісу: