Введение в современную криптографию
Сокращения - предмет обсуждения
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Сокращения - предмет обсуждения. Мы безусловно не доказываем, что кон-
струкция 3.17 криптографически надежна. Скорее, мы доказываем, что она крип- тографически надежна при допущении, что tt - псевдослучайный генератор. Такой подход сокращения надежности конструкции высокого уровня до примитива низ- кого уровня имеет ряд преимуществ (обсуждение в разделе 1.4.2). Первое преиму- щество заключается в том, что обычно легче спроектировать примитив низкого уровня, чем примитив высокого уровня; также обычно проще непосредственно проанализировать алгоритм tt с учетом определения низкого уровня, чем проана- лизировать более сложную систему Π с определением высокого уровня. Это не зна- чит, что спроектировать псевдослучайный генератор «легко». Это значит, что спро- ектировать его легче, чем собирать систему шифрования с нуля. (В данном случае система шифрования не выполняет ничего кроме операции исключающего ИЛИ в отношении выходных данных псевдослучайного генератора и сообщения, таким образом, это не совсем так. Однако мы рассмотрим более сложные конструкции, и в тех случаях возможность сокращения задач до простых имеет большое значение.) Другое преимущество заключается в том, что, один раз создав подходящий tt, мож- но использовать его в качестве компонента других различных систем. Конкретная криптостойкость. И хотя теорема 3.18 и ее доказательство являются асимптотическими, мы без труда можем адаптировать доказательство к условиям конкретной безопасности системы шифрования в отношении конкретной без- опасности tt. Зафиксируем некоторое значение n до конца данного обсуждения, пусть Π теперь обозначает конструкцию 3.17, использующую это значение n. До- пустим, tt является (t, ε)-псевдослучайным (для заданного значения n) в том смыс- ле, что для всех дистинктором D, работающих максимум t, мы имеем Pr[D(r) = 1] − Pr[D(tt(s)) = 1]. ≤ ε. (3.6) (Представьте, что t ≈ 280 and ε ≈ 2−60, хотя точные значения несущественны для на- шего обсуждения.) Мы заявляем, что Π является (t − c, ε)-надежной для некоторой (ма- лой) постоянной c в том смысле, что для всех A, работающих максимум t − c, мы имеем 82 (Обратите внимание, теперь выше приведены фиксированные числа, а не функции от n, поскольку мы больше не находимся в асимптотических условиях.) Чтобы понять это, допустим, A - это произвольный противник, работающий мак- симум t − c. Дистинктор D, сконструированный в доказательстве теоремы 3.18, помимо работы A имеет очень небольшие производительные издержки; задание c надлежащим образом обеспечивает работу D максимум t. Наше допущение о том, что конкретная надежность tt подразумевает уравнение (3.6); продолжая также, как и в доказательстве теоремы 3.18, мы получаем уравнение (3.7). жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|