On connection between affine splitting of a Boolean function and its algebraic, combinatorial and cryptographic properti.pdf Понятие сужения булевой функции активно используется как в синтезе, так и в анализе криптографических функций. В качестве основных причин исследований этого понятия можно назвать следующие: - анализ свойств булева отображения удобно проводить, используя семейство сужений этого отображения на специальным образом подобранное множество областей; - существует тесная связь свойств сужений и исходного булева отображения (в том числе и наследование свойств). В работе исследованы свойства сужений бент-функций и аффинно-расщепляемых функций. Бент-функцию можно определить как функцию, которая плохо аппроксимируется аффинными функциями. В блочных и поточных шифрах бент-функции и их векторные аналоги используются для синтеза криптографических отображений, устойчивых к ряду методов криптографического анализа. Свойство аффинной рас-щепляемости по некоторому подпространству [1] говорит о том, что сужение булевой функции на любой сдвиг этого подпространства совпадает с некоторой аффинной функцией. Если криптографическая функция является аффинно-расщепляемой, то задача её исследования заметно упрощается. Поэтому исследование сужений именно бент-функций и аффинно-расщепляемых функций, а также вопрос о том, может ли бент-функция быть аффинно-расщепляемой, представляет особый интерес. В работе рассматриются такие параметры булевых функций, как нелинейность, алгебраическая степень, спектр Уолша - Адамара, нормальность, слабая нормальность. Получены следующие результаты. 1) Доказано соотношение, связывающее величины квадратов коэффициентов неполного преобразования Уолша - Адамара функции на смежных классах по подпространству с квадратами коэффициентов Уолша - Адамара исходной функции (сформулировано в [2]). Теорема 1. Пусть f - булева функция от n переменных, L - подпространство Vn размерности d, u Е Тогда 2n-d , ч 2 1 Е ( Е (-i)f(x)®) = ^ Е Wf2(y), где v1,... , v2n-d -представители смежных классов {L ф v : v Е Vn}. 2) Доказано равенство значений коэффициентов неполного преобразования Уол-ша - Адамара бент-функции и дуальной к ней функции на нулевом наборе. Теорема 2. Пусть f - бент-функция, L - самодуальное подпространство. Тогда (x) = ^(-l)f(x). 3) Доказано, что если бент-функция нормальна (слабо нормальна), то и дуальная ей функция нормальна (слабо нормальна). Булеву функцию f от n переменных будем называть нормальной (слабо нормальной), если существует плоскость п = L ф u размерности n/2, такая, что f является константой (аффинной) на этой плоскости. 4) Получена верхняя оценка алгебраической степени аффинно-расщепляемой функции. Теорема 3. Пусть f - аффинно-расщепляемая по подпространству L функция от n переменных, dimL = r. Тогда deg(f) ^ n - r + l. 5) Доказано, что свойство аффинной расщепляемости инвариантно относительно полной аффинной группы. 6) Получены достаточные условия аффинной расщепляемости дуальной бент-функции. Теорема 4. Пусть f - бент-функция от n = 2k переменных и f - аффинно-рас-щепляемая по подпространству L С Vn, dim L = k. Если для полных систем представителей смежных классов {u1 ф L,... , u2 ф L} и {v1 ф Lx,... , v2 ф L±} выполнены условия f«i®L(x) = (С ,х)ф С Е v* ф Lx, ег Е {0, l}, i = 1,..., 2k, то дуальная бент-функция f аффинно-расщепляема по подпространству L^. 7) Получена верхняя оценка нелинейности булевой функции, обладающей нетривиальным пространством Lf линейных трансляторов (структур). Теорема 5. Пусть булева функция f от n переменных имеет линейную структуру и dim Lf = r. Тогда nl(f) ^ 2n-1 - 2(n_r)/2_1.

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