*Семантическая криптостойкость

67
Мы начнем с того, что покажем, что неразличимость означает, что шифртекст 
не допускает утечки никакой информации об отдельных битах открытого тек-
ста. Формально скажем, что система шифрования (Enc, Dec) является надеж-
ной с точки зрения EAV (тогда вспомним, когда алгоритм Gen опускается, ключ 
представляет собой однородную n-битную строку), а m ∈ {0, 1}A однородным.
Тогда докажем, что для любого индекса i, невозможно угадать mi по Enck (m) 
(где, в этом разделе, mi обозначает i-тый бит m) с вероятностью больше, чем 1/2.
ТЕОРЕМА 3.10 Пусть Π = (Enc, Dec) - это система шифрования с закрытым 
ключом фиксированной длины A, которая обладает неразличимым шифровани-
ем при наличии подслушивающей стороны. Тогда для всех ppt противников A и 
любых i ∈ {1, ..., A}, существует пренебрежимо малая функция negl, такая что1
где вероятность вычисляется по однородным m ∈ {0, 1}A и k ∈ {0, 1}n, произ-
вольному A и произвольному Enc. 
ДОКАЗАТЕЛЬСТВО  Смысл доказательства данной теоремы заключается в том, 
что если возможно угадать i-тый бит m по Enck (m), тогда также возможно различить 
шифрования двух сообщений m0 и m1, чьи i-тые биты различаются. Формализуем 
это используя доказательство от противного, в котором мы покажем, как использовать 
любого эффективного противника A для создания такого эффективного противника 
Ar, что если A нарушает понятие безопасности по теореме для П, тогда Ar нарушает 
определение неразличимости для П. (См. Раздел 3.3.2.) Поскольку П обладает нераз-
личимым шифрованием, то она также должна быть надежной по теореме.
Зафиксируем произвольного ppt противника A и i ∈ {1, ..., A}. Пусть I0 ∈{0, 
1}A - это множество всех строк, чей i-тый бит равен 0, и пусть I1 ∈ {0, 1}A - это 
множество всех строк, чей i-тый бит равен 1. Мы имеем
Сконструируем следующего противника-перехватчика Ar:
Противник Ar:
1. Выбирает однородные m0 ∈ I0 и m1 ∈ I1. Выводит m0, m1. 
2. После изучения шифртекста c вызывает A(1n, c). Если A выводит 0, выво-
дить br = 0; иначе, выводить br = 1.
Ar работает в полиномиальном времени, так как A работает в полиномиаль-
ном времени.
По определению эксперимента
(n) имеем, что Ar добивается успеха 
тогда и только тогда, когда A выводит b при получении Enck (mb). Таким образом,

68
По гипотезе о том, что (Enc, Dec) обладает неразличимым шифрованием при 
наличии подслушивающей стороны, то существует пренебрежимо малая функ-
ция negl, такая что 
(n)=1]≤ 1 + negl(n). Мы приходим к выводу, что
завершая доказательство. 
Затем мы заявляем, что неразличимость, грубо говоря, означает, что ни один 
ppt перехватчик не может узнать никакой функции открытого текста из данного 
шифртекста вне зависимости от распределения отправляемых сообщений. Это 
предполагает мысль о том, что никакая информация об открытом тексте не про-
сочится из получившегося шифртекста. Однако это требование не так просто 
определить формально. Чтобы это понять, обратите внимание на то, что даже в 
вышеупомянутом случае, легко вычислить i-тый бит m, если m равномерно вы-
бирается из, скажем, множества всех строк, чей i-тый бит равен 0 (по сравнению 
с равномерно выбранным из {0, 1}A). Таким образом, мы хотим сказать, что если 
существует противник, который с некоторой вероятностью правильно вычисляет 
f (m), когда задан Enck (m), тогда существует противник, который может с той же 
вероятностью правильно вычислить f (m), не имея заданного шифртекста совсем 
(а только зная распределение m). В дальнейшем мы сосредоточимся на случаях, 
когда m равномерно выбирается из множества S {0, 1}A. 

жүктеу/скачать 6.4 Mb.

Достарыңызбен бөлісу: