Спосіб побудови високонелінійних збалансованих булевих функцій

Спосіб побудови високонелінійних збалансованих булевих функцій, який заснований на виконанні конкатенації булевих функцій, отриманих шляхом модифікації бент-функцій, результатом якої є криптографічно стійка функція, в якому процедуру конкатенації двох булевих функцій над V2k+1, де k > 1 виконують згідно з виразом X2, ,X2k+i) - отримана високонелінійна збалансована булева функція над \6к+і, а процедуру конкатенації двох булевих функцій над \6к+і, де к> 1, виконують згідно з виразом д(Хі, (Хз, Х2, Хз ,X2k)-f(X3, ,X2k) © (Xi Ф Х2 Ф 1) h ,Х2К+і) де f(x3, , x2k) - бент-функція над V 2k 2, h (x3, , x2k) - неконстантна афінна функція над \6к2, д(хі, Х2, хз , Х2к) - отримана високонелінійна збалансована булева функція над \6к, який відрізняється тим, що дозволяє будувати високонелінійні збалансовані булеві функції з низькими часовими витратами та високою непередбачуваністю вихідних значень функцій завдяки виконанню процедури конкатенації двох булевих функцій за допомогою нових виразів д(хі, х 2 , ,x 2 k + i)=f(x 2 , ,x 2 k + i) © h(x 2 , ,x 2k+ i) (xi Є 1), ДЄ f(X2, ,X2k+l) - бЄНТ-фуНКЦІЯ НЭД V2k, h (X2, ,X2k+l) неконстантна афінна функція над \^k g(xi, Запропонований винахід відноситься до автоматики й обчислювальної техніки і може бути використаний, зокрема, у системах криптографічного захисту інформації Відомий спосіб побудови високонелінійних збалансованих булевих функцій (див В Preneel, R Govaerts, and J Vandewalle, "Boolean functions satisfying higher order propagation criteria" in Lecture Notes in Computer Science 547, Advances in Cryplology Proc Eurocrypt'91, 1991, pp 141-152 Berlin Sprmger-Venag), заснований на конкатенації булевих функцій Для виконання побудови використовується булева функція f над заданим векторним простором Vn При цьому побудова складається з наступних двох етапів вибору нелінійної функції f, яка має нульові значеня в спектрі Уолша, результатом якого є проміжна булева функція, додавання потрібної лінійної функції h над Vn, результатом якого є високонелінійна збалансована булева функція, яка має гарні характеристики розповсюдження Наведений аналог потребує багато часу для побудови криптографічне стійких булевих функцій за рахунок необхідності знаходження нелінійних функцій з нульовими значеннями в їхньому спектрі Уолша та пошуку необхідної лінійної функції h, яка може бути знайдена шляхом повного перебору над всіма ЛІНІЙНИМИ функціями над Vn Найбільш близьким по сукупності ознак до запропонованого способу є спосіб побудови високонелінійних збалансованих булевих функцій (див J Sebeny, X -М Zhang and Y Zheng, "Nonlmeanty and Propagation Characteristics of Balanced Boolean Functions", Information and Computation, Vol 119, №1, pp 1-13, 1995), заснований на конкатенації булевих функцій Побудова складається з виконання конкатенації двох булевих функцій, отриманих шляхом модифікації бент функції, результатом якої є проміжна булева функція, та виконання афінних перетворень координат проміжної булевої функції, результатом якої є високонелінійна збалансована булева функція з гарними характеристики розповсюдження Процедура виконання конкатенації двох булевих функцій над \6к+і, де к> 1, отриманих шляхом модифікації бейт функції, описується наступним виразом ю СО О> Ю 59735 g(xi,x2, x2k+i)= ,х 2к+1 )) = = Х1ФТ(Х2, ,*2к + 1). де f(X2, X2k-м ) - бент (функція над V2k, g(xi,x 2 , Х2к+ 1) - отримана високонелінійна 4 збалансована булева функція над V2k+1 Процедура виконання конкатенації двох булевих функцій над \^к де к > 1 , отриманих шляхом модифікації бент функції, описується наступним виразом 0x 1 x 2 f(x 3 ..* 2 k )=x 1 ex 2 ef(X3...x 2 k ), де f(x 3 ,...,x 2 k) -бент функція над V 2k 2, д(хі,Х2,хз Х2к) - отримана високонелінійна збалансована булева функція над \^к Процедура виконання афінних перетворень координат проміжної булевої функції д(х) описується формулою д*(х) = д(хА), Де д*(х) - функція, обчислена з д(х) шляхом ЛІНІЙНОГО перетворення ВХІДНИХ координат, А - невироджена матриця, така що а.А=р з базисами Ві={а. J=1, ,2k+1}, =1, ,2к+1}наУ 2 к + ітаВі={а ] | J=1, ,2k}, =1, ,2k} над V2k Функція, обчислена над на \6к+і, є збалансованою, має не ЛІНІЙНІСТЬ N g > 2 2 к -2 к та задовольняє критерію розповсюдження відносно всіх ненульових векторів, окрім Уф (1,0, 0) Функція, обчисле на над на V2k є збалансованою, має не ЛІНІЙНІСТЬ Ng > 2 2 k 1 - 2 k та задовольняє критерію розповсюдження відносно всіх ненульових векторів, окрім трьох векторів у1 =(1,0, 0), у 2-(0,І, 0), g(x1,x2,...x2k+1) = x1f(x2, = x1f(x2, Уз = У і Ф ї 2 = 0 Д ,0) При реалізації технічного рішення, прийнятого за прототип, потрібно багато часу для побудови криптографічно стійких булевих функцій за рахунок необхідності виконання афінних перетворень координат проміжної булевої функції, крім того, ВИХІДНІ дані функції є ЛІНІЙНО залежними від хі над V2k+1 та від х-і, Х2 над \6к, що істотно знижує непередбачуваність цих вихідних даних В основу винаходу поставлена задача створити спосіб побудови високонелінійних збалансованих булевих функцій, який дозволив би будувати високонелінійні збалансовані булеві функції з низькими часовими витратами та високою непередбачуваністю вихідних значень функцій завдяки виконанню процедури конкатенації двох булевих функцій за допомогою нових виразів Такий технічний результат може бути отриманий, якщо у способі побудови високонеяїнійних збалансованих булевих функцій, заснованому на виконанні конкатенації булевих функцій, отриманих шляхом модифікації бент функцій, результатом якої є криптографічне стійка функція, згідно з винаходом, процедуру конкатенації двох булевих функцій над V2k+1, де k > 1, виконують згідно з виразом , x 2 k + 1 ) 0 (10x.|)(f(x 2 , ,x2k+1)0f(x2, ,x2k+1)0h(x2, 0 x 1 h ( x 2 . . . x 2 k + 1 ) = f(x2, ,x2k+1)( 2 k+i )) = ,x2k+1)0h(x2, ,x2k+1)0x1(x2, де f(x 2 , ,x 2 k + 1 ) - бент функція над V2k, h(x 2 , ,x2k+-|) - неконстантна афінна функція над V2k, g(x-|,x2, ,x2k+-|) - отримана високонелінійна збалансована булева функція над \6к+і, а процедуру конкатенації двох булевих функцій над \^к де к > 1, виконують згідно з виразом Де f(x 3 ,...,x 2 k ) бент функція над V 2k 2, h (хз,...,х 2 к ) - неконстантна афінна функція над V2k2, д(хі,Х2,хз Х2к) - отримана високонелінійна збалансована булева функція над \^к Функція g над V2k+1 є збалансованою функцією, задовольняє критерію розповсюдження відносно всіх ненульових векторів У є V2k+1 за винятком вектора у, обумовленого видом обраної афінної функції, та має не ЛІНІЙНІСТЬ Ng > 2 -2 Функція g над V2k є збалансованою функцією, задовольняє критерію розповсюдження відносно всіх ненульових векторів У є V2k+1, за винятком трьох ненульових ВеКТОріВ у і, у 2, у з = у і Ф у 2 ОбуМОВЛЄНИХ видом обраної афінної функції, та має нелінійність Ng>22k2-2k Таким чином, виконання процедури конкатенації двох булевих функцій за допомогою запро 59735 понованих виразів дозволяє скоротити час, потрібний для побудови високонелініиних збалансованих булевих функцій, щонайменше в 2 рази, та підвищити непередбачуваність вихідних значень функцій Спосіб побудови високонелініиних збалансованих булевих функцій над V2k+1 може бути реалізований таким чином Виконується побудова бент функції f ( x 2 , ,X2k+i) н а Д ^ 2 k т а рахується КІЛЬКІСТЬ "0" та " 1 " в и ВИХІДНІЙ ПОСЛІДОВНОСТІ Далі виконується побудова випадкової не константної афінної функції h (Х2, , Х2к+і) над \6і