*Инфрмационно-теоретические MAC

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) на основании вышепоказаного описания:

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

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