Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ДОКАЗАТЕЛЬСТВО
| ОПРЕДЕЛЕНИЕ 2.3 Система шифрования (Gen, Enc, Dec) с пространством
сообщения M является совершенно секретной, если для каждого распределе- ния вероятности по M, каждое сообщение m ∈ M и каждый шифртекст c ∈ C, для которых Pr[C = c] > 0: Pr[M = m | C = c] = Pr[M = m]. (Условие Pr[C = c] > 0 является техническим и необходимым для предотвра- щения зависимости от события с нулевой вероятностью.) Теперь мы дадим равноценную формулировку совершенной стойкости. Не- формально, для настоящей формулировки необходимо, чтобы распределение вероятности шифртекста не зависело от открытого текста, т.е . для любых двух сообщений m, mr ∈ M распределение шифртекста при зашифрованном m должно быть тождественно распределению шифртекста при зашифрованном mr. Формально, для каждого m, mr ∈ M и каждого c ∈ C Pr[EncK (m) = c] = Pr[EncK (mr) = c] (2.1) (где вероятности основываются на выборе из K и любой случайности Enc). Из указанного следует, что шифртекст не содержит информации об открытом тек- сте и что невозможно отличить шифрование m от шифрования mr, поскольку в каждом случае распределения по шифртексту совпадают. ЛЕММА 2.4 Система шифрования (Gen, Enc, Dec) с пространством со- общения M является совершенно секретной тогда и только тогда, когда урав- нение (2.1) верно для каждого m, mr ∈ M и каждого c ∈ C. ДОКАЗАТЕЛЬСТВО Покажем , что если заданное условие верно, то си- стема совершенно секретна (обратную импликацию рассмотрим в Упражнении 2.4). Зафиксируем распределение по M, сообщению m и шифртексту c, для ко- торого Pr[C = c] > 0. Если Pr[M = m] = 0, тогда мы обычно имеем: Pr[M = m | C = c] = 0 = Pr[M = m]. 39 Итак, допустим, Pr[M = m] > 0. Сначала отметим, Pr[C = c | M = m] = Pr[EncK (M ) = c | M = m] = Pr[EncK (m) = c], где первое равенство вытекает из определения случайной переменной C, а вто- рое - из поставленного нами условия, что M равно m. Зададим δс def Pr[EncK (m) = c] = Pr[C = c | M = m] . Если условие леммы верно, тогда для каж- дого m' ∈ M мы имеем Pr[EncK (m') = c] = Pr[C = c | M = m'] = δc. Используя теорему Байеса (см. Приложение A.3), мы имеем: где суммирование проводится по m' ∈ M при Pr[M = m'] ≠ 0. Мы приходим к выводу, что для каждого m ∈ M и c ∈ C, для которых Pr[C = c] > 0, верно, что Pr[M = m | C = c] = Pr[M = m], следовательно, система абсолютно секретна. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|