Нетривиальное шифрование с закрытым ключом предполагает одно-

300
чом, поскольку их можно построить, не используя псевдослучайный генератор. 
Кроме того, можно строить совершенно секретные схемы шифрования (см. главу 
2), до тех пор, пока открытый текст не длиннее, чем ключ. Таким образом, дока-
зательство того, что безопасное шифрование с закрытым ключом подразумевает 
использование односторонних функций, требует большей тщательности.
ПРЕДПОЛОЖЕНИЕ 7.29 Если существует схема шифрования с закры-
тым ключом, безопасная с точки зрения расширенной проверки приложения 
(EAV), которая шифрует сообщения в два раза длиннее ее ключа, то существу-
ет и односторонняя функция.
ДОКАЗАТЕЛЬСТВО Пусть Π = (Enc, Dec) – схема шифрования с закрытым 
ключом, которая имеет неотличимые шифровки в присутствии перехватчика и 
шифрует сообщения длиной 2n, ключ имеет длину n. (Для простоты, предполо-
жим, что ключ выбран равномерно). Допустим, что когда используется n-битный 
ключ, Enc использует не более A(n) случайных битов. Обозначим шифрование 
сообщения m, использующее ключ k и степень случайности r by Enck(m; r).
Определим следующую функцию f :
f (k, m, r) 
Enc (m; r) || m,
где |k| = n, |m| = 2n и |r| = A(n). Покажем, что f является односторонней функци-
ей. Очевидно, что ее можно эффективно вычислить; покажем, что ее трудно 
инвертировать. Допуская, что A – произвольный ppt алгоритм, покажем, что 
Pr[InvertA,f (n) = 1] пренебрежимо мало (см. определение 7.1).
Рассмотрим следующего вероятностного полиномиально-временного оппо-
нента Ar, атакующего схему шифрования с закрытым ключом Π (т.е., в экспе-
рименте 
Оппонент Ar(1n)
1. Выберем равномерное m0, m1 ← {0, 1}2n и выведем его. Примем в ответ 
на вызов зашифрованный текст c.
2. Запустим A(c || m0), чтобы получить (kr, mr, rr). Если f (kr, mr, rr) = c || m0, 
выведем 0; в противном случае выведем 1.
Теперь проанализируем поведение Ar. Когда c является шифровкой m0, то 
c»m0 распределено равномерно как f (k, m0, r) равномерных k, m0 и r. Поэтому, 
A выводит действительную инверсию c»m0 (и, следовательно, Ar выводит 0) с 
вероятностью точно равной Pr[InvertA,f (n) = 1].
С другой стороны, когда c является шифровкой m1, то c не зависит от m0. 
Для любого фиксированного значения вызванного шифрованного текста c,
существует не более 2n возможных сообщений (по одному для каждого воз-
можного ключа), которому c может соответствовать. Поскольку m0 является 

301
равномерной 2n-битной строкой, что означает, что вероятность того, что суще-
ствует некий ключ k, для которого Deck (c) = m0 составляет не более 2n/22n = 
2−n. Это дает верхнюю границу по вероятности, с которой A может вывести 
действительную инверсию c|| m0 при f, и, следовательно верхнюю границу по 
вероятности, с которой Ar выводит 0 в этом случае.
Сопоставив все указанное выше, имеем:
Безопасность Π означает, что Pr[ 
= 1]. ≤ 1/2+negl(n) для некоторой 
пренебрежимо малой функции negl. Это, в свою очередь, подразумевает, что 
Pr[InvertA,f (n) = 1] пренебрежимо мало; это завершает доказательство того, что 
f является односторонней.

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

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