ОПРЕДЕЛЕНИЕ 3.19 Система шифрования с закрытым ключом Π = (Gen,
Enc, Dec) обладает неразличимым многократным шифрованием при наличии под-
слушивающей стороны, если для всех вероятностных полиномиально-временных
противников A существует такая пренебрежимо малая функция negl, что
где вероятность вычисляется по случайности, используемой A, и случайности,
используемой в эксперименте.
Любая система шифрования, обладающая неразличимостью многократного
шифрования при наличии подслушивающей стороны, очевидно, также соот-
ветствует определению 3.8, поскольку эксперимент PrivKeav соответствует
особому случаю PrivKmult, где противник выводит два списка, в каждом из ко-
торых содержится только одно сообщение. Фактически, наше новое определе-
ние строго сильнее определения 3.8, как это показано далее.
ПРЕДПОЛОЖЕНИЕ 3.20 Существует система шифрования с закрытым клю-
чом, обладающая неразличимостью при наличии подслушивающей стороны, но раз-
личимая при многократном шифровании при наличии подслушивающей стороны.
ДОКАЗАТЕЛЬСТВО Нам не нужно долго искать пример системы шифрования,
соответствующей предположению. Шифр Вернама совершенно надежен, а также об-
ладает неразличимым шифрованием при наличии подслушивающей стороны. Мы
покажем, что он не надежен в смысле определения 3.19. (Мы уже обсудили эту атаку
в главе 2. Здесь же мы просто проанализируем атаку с учетом определения 3.19.)
Точнее, рассмотрим следующего противника A, атакующего систему (в смыс-
ле, определенном экспериментом PrivKmult): A выводит M˙ 0 = (0A, 0A) и
M1 = (0A, 1A ). (Первый содержит два одинаковых открытых текста, второй два
разных сообщения.) Пусть C˙= (c1, c2) - это список шифртекстов, полученных A.
Если c1 = c2, тогда A выводит br = 0; иначе, A выводит br = 1. Теперь мы анализи-
руем вероятность того, что br = b. Важно то, что шифр Вернама детерминирован,
таким образом, шифрование одного и того же сообщения (с помощью одного и
того же ключа) приводит к появлению одного и того же шифртекста. Итак, если b
= 0, тогда c1 = c2, и A в этом случае выводит 0. С другой стороны, если b = 1, тогда
каждый раз зашифровывается другое сообщение; следовательно, c1 ƒ= c2, и A вы-
водит 1. Делаем вывод, что A правильно выводит br = b с вероятностью 1, таким
образом, система шифрования не является надежной с учетом определения 3.19.
_____________________________________________________________
4
.В разделе 3.6.1 мы увидим, что если система шифрования отслеживает состояние, тогда возмож-
но надежно зашифровать несколько сообщений даже в случае детерминированного шифрования.
|