158
вычислительной стойкостью, то есть, где предполагаются ограничение на время
работы. Вспоминая результаты Главы 2, правильно будет спросить, возможно ли
применение аутентификации сообщений в случае присутствия неограниченного
злоумышленника. В данном разделе мы покажем, при каких условиях достигает-
ся информационно-теоретическая (как альтернатива расчетной) защита.
Первое наблюдение заключается в том, что невозможно достигнуть «идеальной» за-
щиты в этом контексте: а именно, мы не можем надеяться получить код аутентифика-
ции сообщений, для которого вероятность того, что злоумышленник выведет верный
тег на ранее неаутентифицированное сообщение, составит 0. Причина в том, что зло-
умышленник может просто гадать верный тег t
на любом сообщении, и его догадка
будет правильной с вероятностью (как минимум) 1/2|t|, где |t| означает длину тег схемы.
Вышеописанный пример говорит нам о том, чего мы можем надеяться добить-
ся: MAC с тегами длиной |t|, где вероятность подлога максимум 1/2|t| даже для не-
ограниченных злоумышленников.
Мы увидим, что этого вполне можно достичь,
но только при условии ограничений того, сколько сообщений аутентифицированы
честными участниками. Для начала мы определяем информационно-теоретиче-
скую защиту для кодов аутентификации сообщений.
Начальной точкой должно
быть проведение эксперимента Mac-forgeАП(n) который используется чтобы опре-
делить безопасность для вычислительно защищенного MAC (сравните с Опре-
лелением 4.2), но чтобы сбросить параметр защиты n , и потребовать о том, что
Pr[Mac-forgeАП(n)= 1] должен быть «маленьким» для всех злоумышленников A
(и не только злоумышленников, работающих в полиномиальном времени). Как
было сказано выше (и как будет формально доказано в Разделе 4.6.2), однако, такое
определение недостижимо. Вернее, информационно-теоретическая защита может
быть достигнута только, если мы наложим некоторое ограничение на количество
аутентифицированных сообщений честными сторонами. Мы
здесь рассмотрим
наиболее простое условие, когда стороны аутентифицируют всего лишь одно со-
общение. Назовем это одноразовой аутентификацией сообщений. Следующий экс-
перимент изменяет Mac-forge (n) на основании вышепоказаного описания:
Достарыңызбен бөлісу: