162
2n p вариантов для тега m0 (и вообще злоумышленник может угадать его с ве-
роятностью большей, чем 2−n); более того, даже будучи обусловленным значе-
нием тега для m0, должно быть 2n возможностей для тегаm1 (ии вообще злоу-
мышленник мог бы подделать тег на m1 с вероятность большей, чем 2−n). Так
как каждый ключ определяет теги для m0 и m1, это означает, что ключи должны
быть как минимум 2n × 2n . Мы сделаем это формальным ниже.
Пусть K обозначает пространство ключей (то есть набор всех возможных клю-
чей, которые могут быть выведены Gen). Для любого возможного тега t0, пусть
K(t0)
означает набор ключей, для которых t0 является верным тегом на m0; то
есть
K(t0) {k | Vrfyk (m0, t0) = 1}.
Для любого t0 мы должны иметь |K(t0)| ≤ 2−n • |K|. Иначе злоумышленник мо-
жет просто вывести (m0, t0) в качестве его подлог; это будет верный подлог с ве-
роятностью как минимум |K(t0)|/|K| > 2−n, что противоречит заявленной защите.
Рассмотрим теперь злоумышленника A , который запрашивает тег на сообще-
ние m0, получает в ответ тег t0, подбирает универсальный ключ k ∈ K(t0) и вы-
водит (m1, Mack (m1)) в качестве его подлога. Вероятность того, что A выведет
верный
подлог как минимум
При заявленой защите схемы вероятность того, что злоумышленник выведет вер-
ный подлог максимум 2−n. Таким образом, мы должны иметь |K| ≥ 22n. Так как все
ключи имеют одинаковую длину, каждый ключ должен иметь длину как минимум 2n.
Достарыңызбен бөлісу: