Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
ПРЕДВАРИТЕЛЬНЫЕ УСЛОВИЯ:
а) Злоумышленник и оракул О действуют в заданной криптосистеме, состоящей из алгоритма шифрования ?, пространства исходных сообщений ЛЛ и пространства зашифрованных текстов С;
б) оракул О владеет фиксированным ключом шифрования ке.
1. Злоумышленник подбирает разные сообщения mo, mi б М. и посылает их оракулу О.
(* Сообщения то и mi называются подобранным исходным текстом (chosen plaintext messages). Злоумышленник пока находится на этапе поиска ("find-stage") сообшений то и mi. Разумеется, он готовит их таким образом, чтобы легко распознать результат их шифрования. *)
2. Если эти сообщения имеют разную длину, оракул О дополняет более короткое из них, чтобы их длины стали одинаковыми.
(* Например, для дополнения сообщений оракул может использовать фиктивную строку 0d, где d — разность между длинами сообщений. *) Оракул О подбрасывает идеальную монету 6 б [/{О,1} и выполняет следующую операцию шифрования
?fce(rao), если Ъ — О, ?fce(mi), если 6 = 1.
Оракул О посылает Злоумышленнику сообщение с* € С. (* Зашифрованное сообщение с* называется зашифрованным текстом оклика (challenge ciphertext). В теории доказуемой стойкости зашифрованный текст, сопровождаемый звездочкой, всегда считается окликом. *)
(* Следует помнить, что зашифрованный текст с* является случайной величиной, зависящей от двух случайных входных величин: идеальной монеты 6 и внутренней случайной операции алгоритма 8. *)
3. Получив зашифрованный текст с*, Злоумышленник должен угадать результат подбрасывания монеты, послав оракулу 0 или 1.
(* Теперь Злоумышленник находится на этапе осмысленного угадывания ("guess-stage" for an educated guess), пытаясь угадать результат жеребьевки, проведенной оракулом О. Ответы, отличающиеся от 0 и 1, не допускаются. *)
518
Часть V. Методы формального доказательства стойкости
нию 4.14 преимуществом называется разность между вероятностями, с которыми Злоумышленник может распознавать эксперименты ?*е(то) и ?ke(fni)-
Adv =| Prob[0 <— Злоумышленник^* - - ?ке(то))]— 14 2 1 J
— РгоЬ[0 *— ЗлоумЫШЛеННИк(с* = ^fceC^l))]!-
Вероятностное пространство должно содержать случайный выбор, сделанный! оракулом О и Злоумышленником, а также внутреннюю случайную операцию алгоритма шифрования. Отметим, что ответ Злоумышленника зависит не только от зашифрованного текста оклика с*, но и от двух подобранных исходных сообщений (m0, mi). Только поэтому его ответ можно считать результатом "осмысленного угадывания" ("educated guess"). Однако для простоты изложения мы не будем указывать исходные сообщения (mo, mi) во входной информации, поступающей к Злоумышленнику.
Следует заметить, что Злоумышленник имеет дополнительную возможность i для того, чтобы улучшить результаты своего угадывания: оракул О подбрасывает идеальную монету. Формула вычисления преимущества (14.2.1) не указывает явно на то, как Злоумышленник может воспользоваться этим фактом, хотя неявно известно, что каждая из вероятностей, входящих в формулу (14.2.1), никогда не превысит 5, например, вероятность события с* = ?ке(гпо) составляет ровно |. Необходимо явно указать, как именно Злоумышленник использует дополнительный ключ в формуле вычисления преимущества. Применяя условную вероятность (определение 3.3 из раздела 3.4.1) и замечая, что вероятность обоих результатов при подбрасывании идеальной монеты равна |, можно переписать формулу (14.2.1) в следующем виде.
Adv - i Prob[0 *— Злоумышленник^*) | с* = ?ke(j^o)]~
1 (14.2.2)
—- Prob[0 *— Злоумышленник(с*) | с* = ?keipii)\ ¦
По правилам игры Злоумышленнику не разрешается давать ответы, отличающиеся от 0 и 1, следовательно, неправильный ответ является событием, дополнительным по отношению к правильному ответу. Применяя свойство 5 (раздел 3.3), получаем следующую формулу.
Adv =
Иначе говоря,
i Prob[0 *— Злоумышленник^*) | с* = ?fce(mo)]— -^(1 — Prob[0 <— Злоумышленник^*) | с* = ?ke(jno)])
Prob[0 «— Злоумышленник^*) | с* = ?fce(mo)] = ^ ± Adv. (14.2.3)
Глава 14. Определения формальной и сильной стойкости криптосистем... 519
Формула (14.2.3) часто применяется для выражения преимущества алгоритма при угадывании результатов подбрасывания идеальной монеты (вероятность ^). Итак, если Adv = 0, то случайный ответ Злоумышленника имеет точно такое же распределение, как и результаты подбрасывания идеальной монеты. Однако следует учитывать, что преимущество всегда больше нуля. Очевидно, что формула (14.2.3) также справедлива, если в результатах жеребьевки все нули заменить единицами.
Из формулы (14.2.3) следует, что преимущество Злоумышленника никогда не превышает ^, поскольку вероятность всегда лежит в интервале [0,1]. Действительно, если оракул О шифрует оба исходных текста с вероятностью ^, преимущество Adv, заданное формулой (14.2.1), представляет собой разность вероятностей совместных событий и никогда не превышает |. Читатель может заметить, что формула (14.2.3) выглядит так, будто оракул О подбрасывает несимметричную монету, например, оракул с вероятностью \ шифрует сообщение то и с вероятностью \ — сообщение т\. Подсказка: замените число \ в формуле (14.2.2) соответствующими смещенными вероятностями и посмотрите, как изменится формула (14.2.3). Впоследствии будет показано, что преимущество Злоумышленника может превышать \, если оракул О подбрасывает несимметричную монету.
