О некоторых свойствах конструкции бент-функций с помощью подпространств произвольной размерности | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/12

О некоторых свойствах конструкции бент-функций с помощью подпространств произвольной размерности

Рассматриваются свойства конструкции f ® Indi, где f - бент-функция от 2k переменных, а L - аффинное подпространство, при определённых условиях порождающей бент-функции. Предложены необходимые и достаточные условия увеличения и уменьшения на 1 размерности подпространства L, при которых порождаемая функция тоже будет бент-функцией. Доказано, что если функция f (xi,... ,X2k) Ф x2fc+iX2fc+2 ф Indu является бент-функцией для некоторого аффинного подпространства U, то и f Ф IndL является бент-функцией для некоторого L размерности dim U - 1 или dim U - 2. Приведён пример бент-функции от 10 переменных, по которой конструкция порождает бент-функции только при dimL е {9,10}.

Properties of a bent function construction by a subspace of an arbitrary dimension.pdf Бент-функции - булевы функции от чётного числа переменных, обладающие максимально возможной нелинейностью. Они представляют интерес в первую очередь для криптографии. Понятие бент-функции предложено О. Ротхаусом [1]. Подробную информацию об этом классе булевых функций можно найти в [2, 3]. Введем необходимые обозначения. Отображение вида f : F^ ^ F2 называется булевой функцией от n переменных. Пусть (ж, y) = x1y1 ф ... ф xnyn, где ж, y е F£. Обозначим через Inds характеристическую булеву функцию множества S С Fn и через B2k - множество всех бент-функций от 2k переменных. В работе исследуются свойства конструкции бент-функций по заданной бент-функ-ции f е B2k и аффинному подпространству L С F2k, порождающей бент-функции вида f фIndL. Необходимое и достаточное условие принадлежности f фIndL множеству бент-функций B2k доказано К. Карле [4]. Заметим, что при dim L < k функция f ф IndL не может являться бент-функцией, а при dim L ^ 2k - 1 конструкция тривиальна и порождает бент-функцию вне зависимости от выбранной бент-функции f и аффинного подпространства L. Пусть f е B2k и для некоторого аффинного подпространства L С F2k справедливо f ф IndL е B2k. Рассмотрим случаи, в которых можно построить бент-функцию по надпространству или подпространству L. Теорема 1. Пусть f е B2k и f фIndL е B2k, где L С F2k - аффинное подпространство. Пусть а е F^. Тогда f ф IndLU(affiL) е B2k если и только если f ф IndaeL е B2k. Отметим, что в одну сторону утверждение теоремы легко следует, например, из критерия, доказанного в [4]. Следствие 1. Пусть f е B2k и f ф IndL е B2k, где L С F2k - аффинное подпространство размерности 2k - 2. Тогда f ф IndaffiL е B2k при любом а е F2k. Теорема 2. Пусть f е B2k и f ф IndL е B2k, где L С F2k - аффинное подпространство. Пусть а е F^ и La = {ж е L : (а, ж) = 0}. Тогда f ф IndLa е B2k, если и только если для всех y е F^ справедливо | (-1)f(x)®| = | (-1)f(x)®(x,y®a>|. xGL xGL Замечание 1. При dim L = k + 1 всегда найдётся такое а, при котором dim La = k и выполнено равенство из условия теоремы 2. Отметим, что у некоторых бент-функций существуют подпространства, которые нельзя «расширить» согласно теореме 1 и «сузить» согласно теореме 2. Например, такие подпространства есть у мономиальных бент-функций Касами от 8 переменных с показателем 57. Заметим также, что по некоторым бент-функциям рассматриваемая конструкция порождает бент-функции только в тривиальных случаях. Утверждение 1. Существует бент-функция f Е Bi0, для которой f ф IndL Е Bi0 для любого аффинного подпространства L С F^0 размерности меньшей чем 9. Утверждение 1 справедливо для функции, найденной в [5]. Известно, что если f Е B2k, то и f (x\,..., x2k) фx2k+ix2k+2 Е B2k+2. Более того, в [6] доказано, что для f Е B2k существует аффинное подпространство L С F2k размерности k, такое, что f фIndL Е B2k, если и только если существует аффинное подпространство U С F2k+2 размерности k + 1, такое, что f (xi,..., x2k) ф x2k+ix2k+2 ф Ind^ Е B2k+2. Обобщим этот результат на подпространства произвольной размерности. Лемма 1. Пусть f Е B2k и f фIndL Е B2k для некоторого аффинного подпространства L С F;f. Тогда для бент-функции g(xb ... , x2k+2) = f (xi,... ,x2k) ф x2k+ix2k+2 справедливы следующие свойства: 1) g(x) ф IndL Е B2k+2, где L' = {(x',a, 0) : x' Е L,a Е F2}, т.е. dim L' = dim L + 1; 2) g(x^IndL// Е B2k+2, где L'' = {(x',a,b) : x' Е L,a,b Е F2}, т.е. dimL'' = dimL+2. Теорема 3. Пусть для бент-функции g(xi,... , x2k+2) = f (xi,..., x2k) фx2k+ix2k+2 верно g ф Ind^ Е B2k+2, где U С F2k+2 - аффинное подпространство. Тогда существует аффинное подпространство L С F2k размерности dim U - 1 или dim U - 2, для которого верно f ф IndL Е B2k. Следствие 2. Пусть для f Е B2k и любого аффинного подпространства L С F2k, такого, что dimL Е {k, k + 1,... , k + t - 1}, t Е N, справедливо f ф IndL Е B2k. Тогда для бент-функции g(xi, . . . ,x2k+2n) = f (xi, . . . ,x2k) ф x2k+ix2k+2 ф ... ф x2k+2n-ix2k+2n, П Е N, и любого аффинного подпространства L' С F2k+2n, такого, что dim L' Е {k + n, k + n +1, ..., k + n + t - 1}, справедливо g ф Ind^ Е B2k+2n. Следствие 3. Существует бент-функция f от 2k переменных, 2k ^ 10, такая, что для любого аффинного подпространства L С F2k, dimL ^ k + 3, справедливо f ф IndL Е B2k.

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

affinity, subspaces, bent functions, Boolean functions, аффинность, бент-функции, подпространства, булевы функции

Авторы

ФИООрганизацияДополнительноE-mail
Коломеец Николай АлександровичИнститут математики им. С. Л. Соболева СО РАНкандидат физико-математических наук, научный сотрудникkolomeec@math.nsc.ru
Всего: 1

Ссылки

Canteaut A, DaumM., Dobbertin H., and Leander G. Finding nonnormal bent functions // Discr. Appl. Math. V. 154. No. 2. P. 202-218.
Leander G. and McGuire G. Construction of bent functions from near-bent functions // J. Combin. Theory. Ser.A. 2009. V. 116. No.4. P.960-970.
Carlet C. Two new classes of bent functions // LNCS. 1994. V. 765. P. 77-101.
Tokareva N. N. Bent Functions, Results and Applications to Cryptography. Acad. Press. Elsevier, 2015.
Логачев О. А., Сальников А. А., Смышляев С. В., Ященко В. В. Булевы функции в теории кодирования и криптологии. 2-е изд. М.: МЦНМО, 2012. 584с.
Rothaus O. On bent functions // J. Combin. Theory. Ser.A. 1976. V.20. No.3. P. 300-305.
 О некоторых свойствах конструкции бент-функций с помощью подпространств произвольной размерности | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/12

О некоторых свойствах конструкции бент-функций с помощью подпространств произвольной размерности | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/12