Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Дистинктор D
| ДОКАЗАТЕЛЬСТВО Как и в предыдущих случаях использования псевдослучай-
ных функций, это доказательство следует парадигме, в которой сначала анализируется устойчивость схемы, используя действительно случайную функцию, а затем рассма- тривается результат замены действительно случайной функции на псевдослучайную. Пусть 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 может быть использована для построения КАС для сообщений произвольной длины. Таким же образом, псевдослучайная функция |