Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Алгоритм инверсии Ar. Теперь мы дадим полное описание алгоритма Ar,
который принимает входные данные 1n, y и пытается вычислить инверсию y. Алгоритм действует следующим образом: 1. Зададим A := |log(2n/ε(n)2 + 1)|. 2. Выберем равномерные, независимые s1, . . . , sA ∈ {0, 1}n и σ1, . . . , σA ∈ {0, 1}. 3. Для любого непустого подмножества I ∈ {1, . . . , A}, вычислим rI := ⊕i ∈ I si и σI := ⊕i ∈ I σi. 4. Для i = 1, . . . , n выполним: (a) Для каждого непустого подмножества I ∈ {1, . . . , A}, зададим (b) Зададим xi := majorityI {xI } (т.е., берем бит, который появляется большую часть времени на предыдущем этапе). 5. Выводим x = x1 • • • xn. Остается вычислить вероятность того, что Ar выводит x ∈ f −1(y). Как и в до- казательстве предположения 7.14, сосредоточимся только на n как в утверждении 7.18 и предположим, что y = f (xˆ) для некоторого xˆ∈ Sn. Каждое σi представляет собой «прогноз» для значения gl(xˆ, si). Как отмечалось ранее, с не пренебрежимо малой вероятностью все эти прогнозы являются корректными; покажем, что об- условленный этим результатом Ar выводит x = xˆ с вероятностью не менее 1/2. Предположим, что σi = gl(xˆ, si) для всех i. Тогда σI = gl(xˆ, rI ) для всех I. Зафик- сируем индекс i ∈ {1, . . . , n} и рассмотрим вероятность того, что Ar получает корректное значение xi = xˆi. Для любого непустого I имеем A(y, rI ⊕ ei) = gl(xˆ, rI ⊕ ei) с вероят- ностью не менее 1 + ε(n)/2 на основании выбора r; это следует из того, что xˆ∈ Sn и rI ⊕ ei распределены равномерно. Таким образом, для любого непустого подмножества I имеем Pr[xI = xˆi] ≥ 1/2+ ε(n)/2. Кроме того, {xI }I1,...,A являются попарно-независимы- ми, поскольку {rI }I∈{1,...,A}(и поэтому {rI ⊕ ei}I∈{1,...,A}) являются попарно, незави- симыми. Поскольку xi определяется как значение, которое появляется большую часть времени среди {xI }I1,...,A , можно применить предположение A.13, чтобы получить 282 Указанное выше, справедливо для всех i, таким образом, мы можем видеть, что вероятность того, что xi ƒ= xˆi для some i составляет не более 1/2. То есть, xi = xˆi для всех i (и, следовательно x = xˆ) с вероятностью не менее 1/2. Сопоставим все изложенное: Пусть n будет как в утверждении 7.18 и y = f (xˆ). С вероятностью не менее ε(n)/2, имеем xˆ ∈ Sn. Все эти прогнозы σi являются корректными с вероятностью не менее для достаточно большого n. При выполнении обоих указанных выше условий, Ar выводит x = xˆ с вероятностью не менее 1/2. Общая вероятность, при кото- рой Ar инвертирует свои входные данные составляет, таким образом, не менее ε(n)3/20n = 1/(20 np(n)3) для бесконечного множества n. Поскольку 20 np(n)3 – полином от n, это доказывает предположение 7.17. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|