О связях между некоторыми параметрами совершенно уравновешенных булевых функций | ПДМ. 2013. № 2(20).

О связях между некоторыми параметрами совершенно уравновешенных булевых функций

Для класса совершенно уравновешенных булевых функций с барьером доказываются соотношения, связывающие между собой определённые параметры таких функций. В частности, получены общие результаты о свойствах полиномов функций с барьером, позволяющие установить новые оценки числа инверсионных функций для произвольной функции с барьером.

Connections between some parameters of perfectly balanced Boolean functions.pdf Введение Для обеспечения у используемых в криптографических целях кодирующих устройств, построенных на основе регистра сдвига и булевой функции усложнения [1-3], свойства сохранения равномерного распределения преобразуемой двоичной последовательности функции усложнения выбираются из множества совершенно уравновешенных булевых функций [2, 4, 5]. Среди таких функций особое место занимают функции с барьером [2, 6], обладающие также положительным свойством отсутствия предсказывания [2, 7]. Для функций с барьером в работе [7] введены целочисленные параметры, определённым образом характеризующие отображения, реализуемые кодирующими устройствами с такими функциями при фиксированном начале входной последовательности. Настоящая работа посвящена вопросам о соотношениях между параметрами функций с барьером. В частности, доказано утверждение об определённых свойствах полиномиальных представлений таких функций — вопрос, результаты по которому ранее отсутствовали, за исключением частных и тривиальных. Полученные результаты позволяют расширить область применимости утверждения о числе инверсионных функций, полученного в работе [8]. Данное утверждение представляет собой решение открытого вопроса, поставленного в работе Х. Лэя и Дж. Месси [9], и содержит выражение, позволяющее вычислить число инверсионных функций по трём параметрам функции: числу переменных, длине барьера и параметру eR, описанному в [7]. С использованием полученных результатов возможно эффективное (с полиномиальной относительно длины входа сложностью) нахождение по полиномиальному представлению булевой функции нетривиальных оценок на eR и, следовательно, на число инверсионных функций. 1. Определения и предварительные результаты Будем использовать следующие обозначения. Множество двоичных наборов длины n будем обозначать через Vn = {0, l}n, множество булевых функций n переменных— через Fn. Для всяких n, l G N, f G Fn будем через f обозначать следующее отображение из V^+n-1 в V: /г(x1,x2, . . . ,xi+n-1) = (f(x1, . . . ,xn),f(x2, . . . ,xn+1), . . . ,f(xi, . . . ,xi+n-1)). Отображение f описывает преобразование, производимое l тактами работы кодирующего устройства, которое построено подсоединением входов реализующей булеву функцию f схемы к ячейкам двоичного регистра сдвига [1, 4]. Для всяких n, l,p G N, p ^ l + n — 1, f G Fn и любого набора (x1, x2,..., Xp) G Vp будем через fR':1pt:2, ',Xp" обозначать следующее отображение из Vl+n-1-p в V: fR,l1,p 2, , р) (x1, x2, . . . , xl+n-1-p) = fl(Xb X2, . . . , ^^ xb . . . , xг+n-1-p), и через fLJl1pX2,''',:Ep) — следующее отображение из Vl+n-1-p в Vl: /L^p 2, , p) (x1, x2, . . . ,xl+n-1-p) = fl(x1, x2, . . . , xг+n-1-p, X2, . . . ,Xp). Отображение fR^i1pC2,'",Xp) описывает преобразование, производимое l тактами работы кодирующего устройства с функцией усложнения f на двоичных последовательностях с фиксированным началом (X1, X2,... , Xp). Приведём понятия совершенно уравновешенной булевой функции, а также барьера булевой функции. Определение 1 [6]. Булева функция f G Fn называется совершенно уравновешенной, если соотношение |fm1(y)| = 2n-1 выполняется для любого m G N и любого y G V^. Множество совершенно уравновешенных функций из Fn будем обозначать PBn. Определение 2 [6]. Булева функция f G Fn называется функцией с правым барьером длины b, b G N, если система уравнений fb (X1,X2, . . . , Xb'+n-1) = fb' (Z1,Z2, . . . +n-1), X1 z1 , . . . , xn-1 zn-1, xn 0, zn 1 имеет решение при всяком b' G N, таком, что b' ^ b — 1, а система уравнений fb(x1,X2, . . . , Xb+n-1) = fb(z1,Z2, . . . , Zb+n-1), X1 Z1 , . . . , Xn— 1 zn-1, xn 0, zn 1 решений не имеет. Булева функция f G Fn называется функцией с левым барьером длины b, если f (x1, x2,... , xn) = f (xn, xn-1,... , x1) является функцией с правым барьером длины b. Булева функция f G Fn имеет барьер, если она имеет правый или левый барьер, или оба сразу. При этом длиной барьера функции называется соответственно длина правого барьера, левого барьера или меньшая из длин барьеров. Длины правого и левого барьера булевой функции f будем обозначать через bR и bj соответственно. Наличие правого (левого) барьера длины 1, как нетрудно заметить, означает линейность функции по последнему (первому) аргументу. Очевидным является тот факт, что для фиксированного c проверка неравенства bR ^ c по полиному функции, содержащему N мономов, требует порядка (2N + 1)c операций. Для этого требуется лишь перемножить (пользуясь только полиномиальным представлением функций) выражения вида / (ж^, xi+1,... , xi+ra_i) ф ф/(zj, zi+1,... , zi+n-1) ф 1 для i = 1, 2,..., c, затем в полученное полиномиальное представление подставить x1 = z1,... ,жп-1 = zn-1, xn = 0, zn =1, привести подобные и сравнить полученное выражение с нулём — при равенстве, очевидно, функция имеет правый барьер длины не более c. В работе [7] доказан ряд утверждений о свойствах прообразов выходных наборов относительно отображений /r,i,p и /r,i,p в случае наличия у функции / правого или левого барьера. Теорема 1 [7]. Для каждой функции / Е с правым барьером можно определить величину eR Е {0,1, 2,...,bR — 1}, eR ^ n — 1, такую, что для любых p ^ n — 1, l ^ bR + p — n, (X1, X2,..., Xp) Е и любого набора (yb y2,..., У) Е Im /R^p 2,''',Xp)) выполняется равенство „R 2eR. /R,l«p)_1(y1,y2,...,yi) Теорема 2 [7]. Для каждой функции / Е с левым барьером можно определить величину eR Е {0,1, 2,...,bR — 1}, eR ^ n — 1, такую, что для любых p ^ n — 1, l ^ bR + p — n, (X1, X2,..., Xp) Е Vp и любого набора (y1, y2,..., yj) Е Im /RXlpX2,'",Xp)) 2e/. выполняется равенство /йг,---,Хр)_ (y1,y2,...,yi) Следствие 1 [7]. Для любой функции / Е Fn, имеющей правый (левый) барьер, любых l ^ bR — 1 (l ^ bR — 1) и x Е Vn_1 верно равенство |lm(/R,1,n_1) | = 21-eR (|lm(/R,i,n_1)| = 21-е/). Лемма 1 [7]. Если у некоторой / Е есть правый (левый) барьер, то eR = 0 (соответственно, eR = 0) тогда и только тогда, когда bR =1 (bR = 1). Лемма 2 [7]. Пусть /(x1, ж2,... , xn) Е имеет правый (левый) барьер. Тогда eR = bR — 1 (соответственно, eR = bR — 1) тогда и только тогда, когда функция / не зависит существенно от переменных xn_bR+2,xn_bR+3,... ,xn и линейна по переменной xn_bR+1 (не зависит существенно от переменных x1, x2,... , xb/_ 1 и линейна по переменной xbL ). В работе [9] введено понятие инверсионной функции, которое в терминах функций с правым барьером может быть определено следующим образом. Определение 3. Пусть / Е имеет правый барьер. Тогда булева функция / Е FbR+n_ 1 является инверсионной для функции /, если для всякого набора (x1,x2, ... ,xbR+n_1) Е VbR+n_1 выполняется равенство ■/"^ъ . . . , xn_1, /(x1, x2, . . . , xn) , . . . , /(xbR , xbR+1, . . . , xbR+n_1)) = xn. Исследования понятия инверсионной функции проводились в работах [10, 11]. Тем не менее оставался открытым поставленный в конце работы [9] вопрос о числе инверсионных функций для фиксированной функции с правым барьером. Из доказанных в работах [7, 8] свойств функций без предсказывания вытекает следующая теорема. Теорема 3 [8]. Если f G Fn имеет правый барьер, то для f существует в точности 2b/+n-1f 1-2—eR 2 инверсионных функций. Несмотря на полученное утверждение о числе инверсионных функций, при вычислении данной величины в случае представления функции полиномом существует серьёзная проблема. В отличие от параметров n и bR, для нахождения значения параметра eR (или для проверки неравенства eR ^ с для фиксированного с) по полиномиальному представлению нет известных алгоритмов полиномиальной относительно длины входа сложности. То есть нахождение числа инверсионных функций для булевой функции от n переменных, представленной полиномом длины O(n), требует порядка 2n операций. Таким образом, актуальна задача нахождения соотношений между параметром eR и легко вычислимыми по полиному параметрами функций, которые позволят строить эффективные алгоритмы для получения нетривиальных оценок eR (а значит, и нетривиальных оценок числа инверсионных функций) по полиному функции f. При дальнейших построениях будет использован известный критерий равенства алгебраической степени булевой функции числу её переменных. Лемма 3 [2]. Пусть f G Fn. Функция f имеет алгебраическую степень n тогда и только тогда, когда её вес нечётен. 2. Основные результаты Обозначим для произвольной функции f G Fn через tR наибольшее целое t', такое, что в полиноме функции f присутствует моном, который содержит все переменные xn, xn-1,... , xn-t'+1, через tj — наибольшее целое t'', такое, что в полиноме функции f присутствует моном, который содержит все переменные x1, x2,... , xt«. Теорема 4. Пусть функция f G Fn имеет правый барьер, bR ^ 2. Тогда выполняется соотношение eR + tR ^ bR — 1. Доказательство. Если tR = 0, то утверждение непосредственно следует из теоремы 1, поэтому далее предполагаем tR ^ 1. Так как функция f имеет барьер, то она совершенно уравновешена, а следовательно, и уравновешена, откуда по лемме 3 получаем tR ^ n — 1. Введём обозначение t = min{tR ,bR — 1} и рассмотрим набор (а*,а2,... , an-t) G Vn-t, такой, что функция f'(xn-t+1, xn-t+2,..., xn) = = f (а1, а2,..., an_t, xn-t+1, xn-t+2,..., xn) имеет алгебраическую степень t. n- Пусть а* = (0,0,... , 0,а1,а2,... , яП-4). Рассмотрим отображение fR*bR-1 n-1. Оно представимо в следующем виде: fR,bR -1 ,n-1 (xn, xn+1,. . . , xbR+n-2) = = ^g(1) (xn), g(2) (xn, xn+1) , . . . , g(t) (xn, xn+1, . . . , xn+t-1) . . . , g(b/ 1) (xn, xn+1, . . . , Xn+bR-2)^ Заметим, что функция g(t) в точности равна функции f'. Введя для функции g(t) фиктивные переменные в количестве bR — 1 — t, перейдём к рассмотрению g(x1 ,X2, . . . ,XbR-1) = g(t)(x1,X2, . . . ,Xt). С одной стороны, wt(g) = 2bR-1-t • wt(g(t)). Так как g(t) = f' имеет алгебраическую степень t, то в соответствии с леммой 3 значение wt(g(t)) нечётно, поэтому wt(g) не 0bR-t делится на 2 f - . С другой стороны, как следует из теоремы 1, 1 wt(y)= |ГЧ1)| = /x* R,bf_1,ra_1 Е У1,У2'...'Уг-1' yt+1 ,...,ybR_1e{0,1> (У1,У2,...,У*_Ъ 1,yt+1,...,ybR_1) --C-2eR где C — некоторое целое положительное число. Таким образом, 2f не делится на ь, откуда получаем eR ^ bR — t — 1. Если t = min{tR,bR — 1} = bR — 1, то получим eR ^ 0, то есть, с учётом леммы 1, bR = 1, что противоречит условию. Таким образом, t = tR и eR ^ bR — tR — 1, что завершает доказательство теоремы. ■ Данное утверждение означает, что при наличии в полиномиальном представлении булевой функции n переменных монома, содержащего одновременно переменные xn, xn_1,... , xn_t+1 (то есть при tR ^ t), выполнено eR ^ bR — 1 — t, что, с учётом теоре- R f 1 t+1-Ь 12 2bR+nмы 3, означает, что данная функция имеет не более 2 функций. Замечание 1. Заметим, что неравенство eR + tR ^ bR — 1 может обращаться, а может и не обращаться в равенство. Например, для функции /(1)(x1,x2,x3,x4) = = x3 фx2x4 фx1 x2x4 верно, что bRw = 3, eR(1) = 1, tRw = 1, то есть eRw + tR(1) = bRw — 1; для функции /(2)(x1, x2, x3, x4, x5) = x4 ф x1x5 ф x1x2x3x5 верно, что bR(2) = 4, eR(2) = 1, tR(2) = 1 , то есть eR(2) + tR(2) < bR(2) — 1. Абсолютно аналогично теореме 4 доказывается следующее утверждение. Теорема 5. Пусть функция / Е имеет левый барьер, bR ^ 2. Тогда выполняется соотношение eR + tR ^ bR — 1. Следствие 2. Пусть функция / Е имеет правый барьер, 2 ^ bR ^ n. Тогда в полиноме функции /(x1 ,x2,...,xn) нет мономов, содержащих одновременно переменные xn, xn_1, x инверсионных ra_bR+2. Доказательство. Как следует из теоремы 1 и леммы 1, для функции / верно eR ^ 1. По теореме 4 верно eR+tR ^ bR — 1, откуда tR ^ bR — 2, то есть в полиноме функции /(x1,x2,... ,xn) не может быть мономов, содержащих одновременно переменные xra, xra_1, . . . , xra_bR+2. ® Для произвольной функции / Е с правым барьером длины 3 с помощью следствия 2 можно получить, что в разложении /(x1, x2,... , xn) = /(oo)(x1, x2,... , xn_2) ф фXn_l/(01)(Xl,X2, . . . ,x„_2) фx„/(10)(x1,x2, . . . , x„_2) фx„xn_1/(11) (x1, x2, . . . , x„_2) функция /(и) тождественно равна нулю. Таким образом, полученное в работе [6] необходимое условие барьера длины 3 является тривиальным частным следствием полученного общего утверждения. Следствие 3. Пусть функция / Е имеет левый барьер, 2 ^ bR ^ n. Тогда в полиноме функции /(x1, x2,... , xn) нет мономов, содержащих одновременно переменные x1 , x2 , . . . , xbL _1 . Теорема 6. Пусть n ^ 2. Если для некоторой функции / Е Fn, отличной от x1 и x1 ф 1, верно bR ^ n, то eR ^ bR — 3. Доказательство. Будем доказывать индукцией по n. В случае n ^ 2 утверждение очевидно, так как все функции из F2 с правым барьером длины 2 — это функции x1 и x1 ф 1, а функций двух переменных с барьером большей длины не существует. Пусть n ^ 3. Предположим противное: существует функция f G Fn, не равная x1 и x1 ф 1, такая, что bR ^ n, eR ^ bR — 2. При этом, с учётом теоремы 1 и леммы 2, eR ^ n — 1, eR < bR — 1, поэтому необходимо рассмотреть только такие функции f, что bR = n, eR = bR — 2 = n — 2. Если при этом f не зависит существенно от xn, то для функции f'(x1, x2,... , xn-1) = f (x1, x2,... , xn-1, 0), f' G , n' = n — 1, верно bR —1 = n' - 2 и противоречие следует из предположения индукции. Пусть теперь f существенно зависит от xn. В соответствии с теоремой 4 tR ^ (bR — 1) — (bR — 2) = 1. Таким образом: 1) для всякого набора констант (а1, а2,..., an-2) G V^-2 функция f (а1, а2,..., an-2, xn-1,xn) либо линейна по xn, либо не зависит существенно от xn; 2) существует набор констант (а1, а2,... , a^-2) G Vn-2, такой, что функция f (а1, а2, ..., а^-2, xn-1, xn) существенно зависит от xn. Отсюда следует, что функция f (а1, а2,... , 2,xn-1,xn) линейна по переменной bR R R n', e xn, а значит, функции f (а1, а2,... , «П-2, 0, xn) и f (а , an_2,1, xn) также линейны 12 по xn. При этом, так как bR = n и eR = n — 2, то, по следствию 1 Т™ I J"K>a2>...>°) 1Ш \ J R,n— 1,n- 1 2 Im l fR,n- 1,n- 1 С учётом линейной зависимости первых компонент значений векторных отображеn—2,0) ,(ai,a|,...,a;-2,1) и fRn_ 1n_ 1 от переменной xn имеем ний fR,n-1,n- 1 Tm I /а1,а2,...,аП—2,° Im I fR,1,n- 1 Tm I i*(al ,a2 ,...,an —2,1) Im I fR,1,n- 1 2 Из равенств (1) и (2) получаем Tty1 / ,(a|,a3,...,an —2,dl,d2) Im I j R,n-2,n-1 (3) 1 для любых d1, d2 G {0,1}. Из (3) следует, что при всяких d1, d2 G {0,1} после фиксации начальных n — 1 переменных отображения fn-2 значениями а2, а3,... , а^2, d1, d2 получаем постоянный вектор: fn-2(a2, «з,..., an_2, d1, d2, x1, x2,... ,xn-2) = (qd1,d2, ^2; q?i,22) G K-2. Следо вательно, при произвольной фиксации первых двух переменных d1 и d2 функция f обращается в константную: f (d1, d2, x1, x2,... , xn-2) = on-?. Следовательно, f зависит существенно только от первых двух переменных, что противоречит существенной зависимости от последней переменной. Полученное противоречие завершает доказательство утверждения. ■ Теорема 7. Пусть n ^ 2. Если для некоторой функции f G Fn, отличной от xn и xn ф 1, верно bR ^ n, то eR ^ bR — 3.

Ключевые слова

совершенно уравновешенные функции, функции с барьером, криптография, perfectly balanced functions, functions with barriers, cryptography

Авторы

ФИООрганизацияДополнительноE-mail
Смышляев Станислав ВитальевичМосковский государственный университет им. М. В. Ломоносовакандидат физико-математических наукsmyshsv@gmail.com
Всего: 1

Ссылки

Preparata F. P. Convolutional transformations of binary sequences: Boolean functions and their resynchronizing properties // IEEE Trans. Electron. Comput. 1966. V. 15. No. 6. P. 898-909.
Логачев О. А., Сальников А. А, Смышляев С. В., Ященко В. В. Булевы функции в теории кодирования и криптологии. 2-е изд. М.: МЦНМО, 2012.
Colic J. Dj. On the security of nonlinear filter generators // LNCS. 1996. V. 1039. P. 173-188.
Сумароков С. Н. Запреты двоичных функций и обратимость для одного класса кодирующих устройств // Обозрение прикладной и промышленной математики. 1994. Т. 1. Вып. 1. С. 33-55.
Smyshlyaev S. V. Perfectly balanced Boolean functions and Golic conjecture //J. Cryptology. 2012. No. 25(3). P. 464-483.
Логачев О. А., Смышляев С. В., Ященко В. В. Новые методы изучения совершенно уравновешенных булевых функций // Дискретная математика. 2009. Т. 21. Вып. 2. С. 51-74.
Смышляев С. В. Булевы функции без предсказывания // Дискретная математика. 2011. Т. 23. Вып. 1. С. 102-118.
Смышляев С. В. О свойствах булевых функций без предсказывания // Материалы Шестой Междунар. науч. конф. по проблемам безопасности и противодействия терроризму (МГУ им. М.В. Ломоносова, Москва, 11-12 ноября 2010). М.: МЦНМО, 2011. С. 47-56.
Lai X. and Massey J. Some connections between scramblers and invertible automata // Proc. 1988 Beijing Int. Workshop on Info. Theory. Beijing, China, July 4-8, 1988. P. DI-5.1-DI-5.5.
Смышляев С. В. О преобразовании двоичных последовательностей с помощью совершенно уравновешенных булевых функций // Материалы Пятой Междунар. науч. конф. по проблемам безопасности и противодействия терроризму (МГУ им. М.В. Ломоносова, Москва, 29-30 октябр
Смышляев С. В. О криптографических слабостях некоторых классов преобразований двоичных последовательностей // Прикладная дискретная математика. 2010. №1(7). С. 5-15.
 О связях между некоторыми параметрами совершенно уравновешенных булевых функций | ПДМ. 2013. № 2(20).

О связях между некоторыми параметрами совершенно уравновешенных булевых функций | ПДМ. 2013. № 2(20).

Полнотекстовая версия