280
для любого i. Таким образом, если мы пытаемся использовать A(f (x), r) ⊕ A(f
(x), r ⊕ ei) в качестве оценки для xi, то все, что мы можем утвеждать - это то, что
эта оценка будет корректной с вероятностью не менее ε(n), которая не может
быть лучше, чем принять случайный прогноз! Мы не можем утверждать, что
инверсия результата дает хорошую оценку в любом случае.
Вместо этого, мы разработаем Ar так, чтобы он вычислял gl(x, r) и gl(x, r⊕ei) при вы-
зове A только один раз. Мы сделаем это, имея Ar, запустим A(x, r ⊕ ei), и имея Ar просто
“угадаем” само значение gl(x, r). Наивным способом сделать это, было бы выбрать не-
зависимые друг от друга r, как и ранее, и имея Ar, дать независимый прогноз gl(x, r) для
каждого значения r. Но тогда вероятность того, что все эти прогнозы правильные , что,
как мы увидим, необходимо, если Ar является выходом корректной инверсии, было бы
пренебрежимо малым, поскольку используется полиномиальное множество r.
Ключевое наблюдение настоящего доказательства состоит в том, что Ar может
генерировать
r парно-независимым способом, и делать свои прогнозы определен-
ным образом так, чтобы его прогнозы были правильными, с не пренебрежимо ма-
лой вероятностью. В частности, чтобы генерировать m значений r, мы имеем Ar ,
выбираем A = |log(m + 1)| независимо и равномерно распределенные строки s1, . . . ,
sA ∈ {0, 1}n. Затем, для каждого непустого подмножества I∈{1, . . . , A}, мы задаем
rI := ⊕i I si. Поскольку существуют 2A − 1 непустых подмножеств, это определяет
набор 2flog(m+1){ − 1 ≥ m строк. Каждая такая строка имеет равномерное распреде-
ление. Эти строки не являются независимыми, но они являются попарно независи-
мыми. Чтобы убедиться в этом, обратите внимание, что для каждых двух подмно-
жеств I ƒ= J существует индекс j ∈ I∩ J, такой что j ∉/ I ∩ J .
Без потери общности,
предположим j ƒ∩ I. Тогда значение sj является равномерным и независимым от
значения rI . Поскольку sj включено в исключающее ИЛИ (XOR), которое опре-
деляет rJ , это означает, что rJ также является равномерным и независимым от rI .
Теперь у нас есть два следующих важных замечания:
1. С учетом gl(x, s1), . . . , gl(x, sA ), можно вычислить gl(x, rI ) для каждого
подмножества I ∈ {1, . . . , A}. Это
потому, что gl(x, rI ) = gl(x, ⊕i I si) = ⊕gl(x, si).
2. Если Ar просто прогнозирует значения gl(x, s1), . . . , gl(x, sA ) выбирая
однородный бит для каждого, то все эти прогнозы будут корректными с вероят-
ностью 1/2A. Если m является полиномом в параметре безопасности n, то 1/2A
не пренебрежимо мало, и, таким образом, при не пренебрежимо малой вероят-
ности Ar корректно прогнозирует все значения gl(x, s1), . . . , gl(x, sA ).
Сочетание указанного выше дает способ получения m = poly(n) равномерных и по-
парно-независимых строк {rI }, наряду с корректными значениями для {gl(x, rI )} при не