Statistical independence of general superposition of boolean functions.pdf Определение 1. Для любой булевой функции f (x), где x — переменные со значениями в Zn, и для любого подмножества U её аргументов будем говорить, что f (x) статистически не зависит от переменных множества U, если для любой её подфункции f'(x'), полученной фиксированием значений всех переменный в U, имеет место равенство Pr[f'(x') = 0] = Pr[f(x) = 0]. В [1] доказано, что если булева функция f1(x) статистически не зависит от некоторого подмножества своих аргументов, то это свойство сохраняется для произвольной суперпозиции g(f1(x), y). Для суперпозиции g(f1(x), f2(x), y) в [2] доказано более сложное достаточное условие сохранения статистической независимости: этим свойством, помимо fi и f2, должна обладать и их сумма f1 ф f2. В данной работе условие из [2] обобщается на случай произвольного числа внутренних функций суперпозиции. Утверждение 1. Пусть x,y,z — переменные со значениями в Zn, Zm и соответственно и для всех 1 ^ s ^ I и 1 ^ i1

Скачать электронную версию публикации