79
ДОКАЗАТЕЛЬСТВО Пусть Π обозначает конструкцию 3.17. Покажем, что
Π соответствует определению 3.8: покажем, что для любого вероятностного по-
линомиально-временного противника A существует такая пренебрежимо малая
функция negl, что
Интуиция
подсказывает, что если П использует
равномерную последователь-
ность вместо псевдослучайной последовательности tt(k), тогда получившаяся си-
стема должна быть идентична системе шифрования Вернама, и A не должен быть
в состоянии правильно угадать, какое сообщение было зашифровано, с вероятно-
стью выше, чем 1/2. Таким образом, если уравнение (3.2) не верно, тогда A должен в
неявной форме различать выходные данные tt и по-настоящему случайные строки.
Мы явным образом докажем это методом от противного, именно, показав, как ис-
пользовать A для конструирования эффективного дистинктора D, такой что способ-
ность D различать выходные данные tt и равномерную строку будет напрямую свя-
зана со способностью A определять, какое именно сообщение было зашифровано
системой Π. Надежность tt тогда подразумевает надежность Π.
Пусть A - это произвольный ppt противник. Мы конструируем дистинктор D,
который на входе берет строку w и целью которого является определить, была
ли строка w выбрана равномерно (т. е. w - это «случайная строка») или w была
сгенерирована с помощью унифицированного k и вычислена w := tt(k) (т. е. w
- это «псевдослучайная строка»).
Мы конструируем D так, чтобы имитировал
эксперимент с подслушивающей стороной для A, как описано ниже, и наблю-
дал, добьется A успеха или нет. Если A справляется, тогда D угадывает, что w
должна быть псевдослучайной строкой, а если A не справляется, тогда D угады-
вает, что w является случайной строкой. Более подробно:
Достарыңызбен бөлісу: