Введение в современную криптографию



Pdf көрінісі
бет46/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   42   43   44   45   46   47   48   49   ...   249
Криптография Катц

ТЕОРЕМА 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 соответствует необходимым заявленным свойствам.


Достарыңызбен бөлісу:
1   ...   42   43   44   45   46   47   48   49   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет