Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ДОКАЗАТЕЛЬСТВО
| ТЕОРЕМА 3.11 Пусть (Enc, Dec) - это система шифрования с закрытым
ключом фиксированной длины A, которая обладает неразличимым шифровани- ем при наличии подслушивающей стороны. Тогда для любого ppt алгоритма A существует ppt алгоритм Ar, такой что для любого S {0, 1}A и любой функ- ции f : {0, 1}A → {0, 1}, существует пренебрежимо малая функция negl, такая что: где первая вероятность вычисляется по равномерному выбору k ∈ {0, 1}n и m ∈ S, произвольному A и произвольному Enc, а вторая вероятность вычисляется по равномерному выбору m∈ S и произвольному Ar . ДОКАЗАТЕЛЬСТВО (набросок) Тот факт, что (Enc, Dec) является надеж- ным с точки зрения EAV означает, что для любого S {0, 1}A не существует ppt противника, который мог бы отличить Enck (m) (для однородного m ∈ S) и Enck (1A ). Теперь рассмотрим вероятность того, что A успешно вычислит f 69 (m), получив Enck (m). Мы заявляем, что A должен успешно вычислить f (m), получив Enck (1A ), с примерно той же вероятностью; иначе, A может быть использован, чтобы различать Enck (m) и Enck (1A ). Дистинктор легко скон- струирован: равномерно выбираем m ∈ S и выводим m0 = m, m1 = 1A . После получения шифртекста c, представляющего собой зашифрованное m0 или m1, вызываем A(1n, c) и выводим 0 тогда и только тогда, когда A выводит f (m). Если A выводит f (m) после получения шифрования m с вероятностью, значительно отличающейся от вероятности вывода f (m) после получения шифрования 1A, тогда описанный дистинктор нарушает определение 3.9. Вышесказанное предполагает, что алгоритм Ar, не получающий c = Enck(m), еще может вычислять f (m) практически также, как это делает A: Ar(1n) выбирает унифицированный ключ k ∈ {0, 1}n, вызывает A по c ← Enck (1A ) и выводит все то же, что и A. Из вышесказанного имеем, что A выводит f (m), когда он работает как подпрограмма Ar с практически той же вероятностью, как когда он получает Enck (m). Таким образом, Ar соответствует необходимым заявленным свойствам. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|