63
мализует это понятие и представляет собой первое из когда-либо предложенных
определений вычислительно надежного шифрования. Семантическая криптостой-
кость - сложно е понятие, с которым трудно работать. К счастью, существует равно-
сильное и
более простое определение,
называемое неразличимостью.
Определение неразличимости сформулировано по образцу альтернативного
определения совершенной криптостойкости (см. Определение 2.5). (Еще одна
причина того, почему определение неопределенности хорошо.)
Напомним, что
Определение 2.5 включает в себя эксперимент
, в котором противник
A выводит два сообщения m0 и m1, а затем получает одно из этих сообщений,
зашифрованное с помощью унифицированного ключа. В определении говорит-
ся, что система Π надежна, если ни один противник A не сможет определить,
какое из сообщений m0, m1 было зашифровано, с вероятностью, отличной от
1/2, которая
равносильна вероятности того, что A правильно угадает ответ.
А теперь перейдем к эксперименту
почти аналогичному (за ис-
ключением некоторых технических различий, указанных ниже) тому, что мы уже
проводили, однако, мы внесем два ключевых изменения в само определение:
1. Теперь мы рассматриваем только противников, работающих в
полиноми-
альном времени, хотя в определении 2.5 рассматривались даже противники с
неограниченным временем работы.
2. Теперь мы допускаем, что противник может определить зашифрованное
сообщение с
вероятностью пренебрежимо большей, чем 1/2.
Как уже было сказано в предыдущем разделе, упомянутые выше ослабления
являются ключевыми элементами вычислительной криптостойкости.
Что же касается других отличий, основным является то, что теперь мы пара-
метризуем эксперимент посредством параметра безопасности n. Тогда мы из-
меряем как время работы противника A, так и вероятность его успеха в качестве
функций по n. Запишем
(n), чтобы обозначить, что эксперимент про-
водится с учетом
параметра безопасности n, и
запишем
(n) = 1]
(3.1)
для обозначения вероятности того, что результатом эксперимента Pr
(n) является 1. Обратите внимание, что при фиксированных A, Π, уравнение
(3.1) является функцией по n.
Второе отличие эксперимента
заключается в том, что теперь нам
явно требуется, чтобы противник вывел два сообщения m0, m1
равной длины.
(В определении 2.5 это требование подразумевается, если пространство сооб-
щения M содержит только сообщения фиксированной длины, как это происхо-
дит при шифровании Вернама.) Это означает, что по умолчанию для надежного
64
шифрования на не требуется скрывать длину открытого текста. Мы вернемся к
этому моменту в конце данного раздела (также см. упражнения 3.2 и 3.3).
Достарыңызбен бөлісу: