Classes of boolean functions with limited complexity.pdf Во многих шифрсистемах используются булевы функции. Если функция является ключом, как, например, в [1, 2], то она должна зависеть от большого числа переменных. Поскольку длина вектора значений булевой функции от n переменных равна 2n и формула (в любом базисе) произвольной функции имеет ту же длину (порядка 2n), представляют интерес классы функций, которые зависят от большого числа переменных, но имеют короткое задание. В связи с этим возникают следующие задачи: подсчёт количества функций в классе; разработка теста на принадлежность функции классу; разработка алгоритма доопределения частичной функции до функции из заданного класса. Обозначим P2(n) множество всех булевых функций от n переменных; будем рассматривать следующие классы функций в P2(n) и называть их классами ограниченной сложности: - Cn,k - с заданным (равным k) числом существенных переменных; - - с ограниченным (не больше k) числом существенных переменных; - Dn,k - заданной степени (deg / = k); - - ограниченной степени (deg / ^ k); - Ln,k - с заданной (равной k) длиной алгебраической нормальной формы (АНФ); - - с ограниченной (не больше k) длиной АНФ; - - имеющие бесповторную АНФ (каждая переменная входит в АНФ не более одного раза). В таблице приведены мощности этих классов, здесь Sk - количество функций от k переменных, существенно зависящих от всех своих переменных (последовательk /k\\ к_г ность A000371 из [3]), Sk = 1)4 . ) 22 г; Bk - число Белла, или количество всех i=0 \\ij неупорядоченных разбиений k-элементного множества (последовательность A000110 k /ДА из [3]), задаваемое рекуррентной формулой B0 = 1, Bk+1 = У] I )Bj. i=A v Класс Мощность Cn,k (!) Sk k k / ! \\ E |cn,i| = £ J Si i=0 i=0 V 1 J Dn,k 25„Ksi) 2.5(n) Ln,k (; / Ln,^k E (2"/ i=0 V 1 ) NRn 2Bn+i Принадлежность функции f классу ограниченной сложности определяется свойствами её АНФ, например, deg f равна длине самого длинного слагаемого в АНФ; количество существенных переменных - количеству переменных, входящих в АНФ. АНФ, в свою очередь, строится с помощью преобразования Мёбиуса ^ : P2(n) ^ P2 (n) [4]: f (x) =0 g(a)xa, g = Mf), g(a) = 0 f (x). (1) Для g = ^(f) обозначим |a1,..., ar} множество всех векторов, на которых g(a^) = 1, i = 1,...,r; единичным компонентам в а^ соответствуют переменные, входящие в i-е слагаемое АНФ функции /. Через w(x) (w(f)) обозначим вес булева вектора x ( k \\ (функции f). Тогда t = w I \\/ аП - количество существенных переменных функции f; d = max w(a^) -её степень. Получаем следующие тесты принадлежности функции f i=1,...,r классам ограниченной сложности: - если t = k, то f Е Cn,k; если t ^ k, то f Е Cn,^k; - если d = k, то f Е Dn k; если d ^ k, то f Е ; - если w(g) = k, то f Е Ln,k; если w(g) ^ k, то f Е . Чуть сложнее проверяется принадлежность функции классу NRn. Составим матрицу A размера r х n, строками которой являются векторы а^, i = 1,...,r. Тогда f Е NRn, если и только если веса всех столбцов матрицы A не больше 1; другими словами, f Е NRn, если и только если какой-либо столбец матрицы A содержит хотя бы две единицы. Соответствующая проверка выполняется в алгоритме 1. Задача доопределения функции до функции из заданного класса C С P2(n) ставится так: частично определённая функция f Е P2(n) задана множествами M0 = {x Е ЖП : f (x) = 0} и M1 = {x Е ЖП : f (x) = 1}, M0 П M1 = 0; найти все такие функции g Е C, что g(x) = f (x) для всех x Е M0 U M1. Рассмотрим случай C = . АНФ функции f Е обладает следующим свойством: g(x) = 0 для всех x, таких, что w(x) > k, где g = ^(f). Обозначим вектор значений функции f как b = Алгоритм 1. Тест на принадлежность функции / классу Вход: Функция / 6 P2(n); матрица A со строками |а1,..., ar}. 1: x := а1. 2: Для i = 2,... , r 3: y := x ф a. 4: Если x&y = 0, то выход, ответ: / 6 NRn. 5: x := y. 6: Ответ: / 6 . = (b0b1... b2n-1), bi = /(i) (здесь мы не различаем число в диапазоне от 0 до 2n - 1 и его представление в виде булева вектора длины n). В самом общем виде (если M0 = M1 = 0) решение задачи состоит в следующем: для каждого x, такого, что w(x) > k, в соответствии с формулой (1) составляем уравнение ф Ьг = 0. Обозначим матрицу полученной системы линейных однородных уравнений (СЛОУ) Bn,k. Все решения получившейся СЛОУ Bn,k b = 0 (2) являются векторами значений функций из . Для поиска доопределений частично заданной функции (если M0 = 0 или M1 = 0) решаем ту же систему относительно переменных множества {Ьг : i 6 M0 U M1}, объявив константами 0 и 1 переменные Ьг с номерами из множеств M0 и M1 соответственно. Таким образом, СЛОУ (2) преобразуется к системе уже не обязательно однородных уравнений.

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