Введение в современную криптографию
Шаг t: Выберем универсальное значение для g(It), таким образом, определяя It+1 и Irt+1. Шаги t + 1 до A − 1
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Шаги A до 2A − 2
| Шаг t: Выберем универсальное значение для g(It), таким образом, определяя
It+1 и Irt+1. Шаги t + 1 до A − 1 (если t < A − 1): Выбираем, в свою очередь, универсаль- ные значения для каждого из g(It+1), g(It+2), . . . , g(IA−1), таким образом, опре- деляя It+2, It+3, . . . , IA . Шаги A до 2A − 2 (если t < A − 1): Выбираем, в свою очередь, универсальные значения для каждого из , таким образом, опре- деляя . Пусть Coll(k) будет фактом, что нетривиальная коллизия случается на шаге k. Тогда используя Предположение A.9. Для k < t, мы заявляем, в действительности, если не случилось никакой нетривиальной коллизии на шаге k − 1, значение g(Ik ) выбирает- ся единообразно на шаге k; нетривиальная коллизия случается, только если слечается так, что Ik+1 = g(Ik) ⊕ xk+1 равняется оному из {I1, . . . , Ik } (ко- торые все разные, поскольку Coll(k − 1) не случилась). Согласно такому же рассуждению, мы имеем (здесь два зна- чения It+1, Irt+1 для рассмотрения; обратите внимание, что они не могут рав- няться друг другу). Наконец, аргументируя, как и ранее, для k > t мы имеем 145 Уравнение (4.7), мы, таким образом, имеем Из Уравнения (4.6) мы получаем Pr[Coll] < q2A2 • 2−n = δ. Наконец, используя Уравнени (4.5) мы видим, что как и утверждалось. Мы теперь видим, что гладкость подразумевает теорему. Предположим, без потери обобщенности, что D всегда совершает q (разных) запросов, каждый из которых содержит максимум A блоков. D может выбиратьсвои запросы адап- тивно (то есть в зависимости от ответов на рпедыдущие запросы), но набор запросов D должен быть беспрефиксным. Дt ля разных X1, . . . , Xq ∈ ({0, 1}n)* и произвольных t1, . . . , tq ∈ {0, 1}n, определим, что α(X1, . . . , Xq ; t1, . . . , tq ) равно 1, если и только если D выводит 1, при запросах X1, . . . , Xq и полчении ответов t1, . . . , tq . (Если, скажем, D не делает запрос X1 как свой первый запрос, тогда α(X1, . . . ; . . .) = 0.) Допуская, что X˙ = (X1, . . . , Xq ) и ˙t = (t1, . . . , tq ), мы, таким образом, имеем где, выше, g выбирается единообразно из Funcn, а f выбирается единообразно из набора функций, преобразовывающих ({0, 1}n)* в {0, 1}n. Из этого следует Симметричный аргумент для того, когда D выводит 0, завершает доказательство. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|