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

96
В качестве первого шага, в таких доказательствах обычно рассматривается гипо-
тетическая версия конструкции, в которой псевдослучайная функция заменена на 
случайную. Затем утверждается, используя доказательство от противного, что эта 
модификация не влияет значительным образом на вероятность успешной атаки. 
Тогда у нас остается схема, использующая абсолютно случайную функцию. Таким 
образом, оставшаяся часть доказательства обычно основывается на анализе теории 
вероятностей и не зависит ни от каких вычислительных утверждений. Мы еще не-
сколько раз используем этот шаблон для доказательсв в этой и следующей главах.
КОНСТРУКЦИЯ 3.30
Пусть F — псевдослучайная функция. Определим шифровальную схему с за-
крытым ключом для сообщений длины n следующим образом:
• Gen: для входа 1n, выбери и выведи kn∈0, 1}.
• Enc: для входа — ключа k∈{0, 1}n и сообщения m∈{0, 1}n , выбери
равномерную r∈{0,1}n и выведи шифртекст c := (r, Fk(r)⊕m).
•Dec: для входа — ключа k∈{0, 1} и шифртекста c = (r, s), выведи сообщение с 
открытым текстом m := Fk (r)⊕s.
Шифровальная схема из любой псевдослучайной функции, защищенная от АВОТ.
ТЕОРЕМА 3.31 Если F — псевдослучайная функция, то Конструкция 3.30 
является шифровальной схемой с закрытым ключом, защищенной от АВОТ, 
для сообщений длины n.
ДОКАЗАТЕЛЬСТВО Пусть Π˜ = (G˜en, E˜nc, D˜ec) — шифровальная схема, 
абсолютно идентичная схеме Π = (Gen, Enc, Dec) из Конструкции 3.30, за ис-
ключением того, что вместо функции Fk используется случайная функция f.
То есть, G˜en(1n) выбирает равномерную функцию f∈ Funcn, и E˜nc шифрует 
точто так же, как Enc, только вместо Fk используется f. (Эта модифицированная 
шифровальная схема неэффективна. Но мы все же можем определить ее как 
гипотетическую шифровальную схему для доказательства.)
Зафиксируем произвольного ppt-противника A, и пусть q(n) будет максималь-
ным значением из числа запросов, которые посылает A(1n) своему шифроваль-
ному оракулу. (Заметим, что q должен иметь полиномиальное максимальное 
значение.) В качестве первой ступени доказательства, мы покажем, что суще-
ствует пренебрежимо малая функция negl , такая что
Используем доказательство от противного. Используем A , чтобы построить 
дистинктор D для псевдослучайной функции F . Дистинктор D получает ора-
кульный доступ к некоторой функции O, и его задача состоит в том, чтобы опре-
делить, является ли эта функция «псевдослучайной» (т.е. равной Fk для равно-
мерной k∈{0, 1}n) или «случайной» (т.е. равной f для равномерной f∈Funcn). 

97
Для этого, D эмулирует эксперимент PrivKcpa для A, как описано ниже, и на-
блюдает, справится ли A. Если A справляется, то D заключает, что его оракул 
является псевдослучайной функцией, тогда как если A не справляется, то D 
заключает, что его оракул является случайной функцией. Более подробно:

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

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