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



Pdf көрінісі
бет95/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   91   92   93   94   95   96   97   98   ...   249
Криптография Катц

ДОКАЗАТЕЛЬСТВО Как и в предыдущих случаях использования псевдослучай-
ных функций, это доказательство следует парадигме, в которой сначала анализируется 
устойчивость схемы, используя действительно случайную функцию, а затем рассма-
тривается результат замены действительно случайной функции на псевдослучайную.
Пусть A – вероятностный полиномиально-временной противник. Рассмотри код 
аутентификации сообщения Π˜ = (G˜en, M˜ac, V˜rfy), который равен Π = (Mac, Vrfy) 
из Конструкции 4.5, за исключением того, что в нем используется действительно слу-
чайная функция f вместо псевдослучайной функции Fk . То есть, G˜en(1n) выбирает 
равномерную функцию f ∈ Funcn, и M˜ac вычисляет тэг, так как Mac принимает то, 
что вместо Fk используется f . Из этого непосредственно следует, что
Pr[Mac-forgeA,Π(n) = 1]≤2−n
(4.1)
потому что для любого сообщения m ∉ Q, значение t = f (m) равномерно рас-
пределено в {0, 1}n с точки зрения противника A.
Мы покажем, что существует пренебрежимо малая функция negl , такая что
соединив это уравнение с Уравнением (4.1), получаем
Pr[Mac-forgeA,Π(n) = 1] ≤ 2−n + negl(n), что и требовалось доказать.
Чтобы доказать Уравнение (4.2), построим дистинктор полиномиального времени 
D , которому дан оракульный доступ к некоторой функции, и который имеет своей 
целью определить, является ли эта функция псевдослучайной (т.е. равной Fk для 
единообразного k ∈{0, 1}n) или случайной (т.е. равной f для единообразной f ∈ Funcn). 
Для этого D имитирует эксперимент аутентификации сообщения для A и проверяет, 
сможет ли A выдать действующий тэг для «нового» сообщения. В этом случае, D уга-


132
дывает, что его оракул является псевдослучайной функцией. В противном случае, D 
угадывает, что его оракул является случайной функцией. Более подробно:
Дистинктор D:
D получает вход 1n и доступ к оракулу O : {0, 1}n → {0, 1}n, и работает сле-
дующим образом:
1. Запустить A(1n). Каждый раз, когда A посылает запрос его оракулу КАСа 
для сообщения m (т.е. когда A запрашивает тэг для сообщения m), ответить на 
запрос следующим образом:
Послать запрос O с m и получить ответ t; вернуть A ответ t .
2. Когда A выдает (m, t) в конце своей работы, делать следующее:
(a) Послать запрос O с m и получить ответ tˆ.
(b) Если (1) tˆ = t и (2) A никогда не посылал своему оракулу КАСа запрос для m, то выдать 
1; в противном случае выдать 0. Очевидно, что D работает в полиномиальном времени.
Заметим, что если оракул дистинктора Dявляется псевдослучайной функци-
ей, то вид A , когда он запускается дистинктором D как субрутина, распределен 
идентично виду A в эксперименте Mac-forgeA,Π(n). Кроме того, D выдает 1, 
именно когда Mac-forgeA,Π(n) = 1. Следовательно,
где k ∈ {0, 1}n выбирается равномерно. Если оракул D — это случайная 
функция, то вид A , когда он запускается дистинктором D как субрутина, рас-
пределен идентично виду в эксперименте Mac-forgeA,Π(n) и сноваD выдает 1 
именно тогда, когда Mac-forgeA,Π(n)=1A,Π˜. Таким образом,
где f ∈Funcn выбирается равномерно.
Так как F — псевдослучайная функция, и D работает в полиномиальном 
времени, то существует пренебрежимо малая функция negl , такая что:
Из этого следует Уравнение (4.2), что и требовалось доказать.
___________________________________________________________
³Если использовать псевдослучайную функцию, которая принимает на входе данные произ-
вольной длины, Конструкция 4.5 может быть использована для построения КАС для сообщений 
произвольной длины. Таким же образом, псевдослучайная функция


133


Достарыңызбен бөлісу:
1   ...   91   92   93   94   95   96   97   98   ...   249




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

    Басты бет