On the set of derivatives of a boolean bent function.pdf В работе продолжено исследование множества булевых бент-функций. Известно, что бент-функции [1] интересны для криптографических приложений [2]; актуальными в данной области остаются вопросы о числе бент-функций и способах их построения. «Много» или «мало» бент-функций? Этим вопросом озадачиваются многие исследователи. Если исходить из предположения, что бент-функций много и они разнообразны, то разнообразными должны быть и их производные. Так ли это на самом деле? При малом числе переменных мы исследуем этот вопрос. Производной булевой функции / от n переменных по направлению у е Fn называется функция /(x) = /(x) + /(x + y). Напомним, что булева функция / от чётного числа переменных n называется бент-функцией, если её производная по любому ненулевому направлению y уравновешена, т. е. / одинаково часто принимает значения 0 и 1. Хорошо известно, что степень бент-функции не превосходит n/2. Заметим, что булева функция g является производной некоторой булевой функции / тогда и только тогда, когда найдётся ненулевой вектор у, такой, что g(x) + + g(x + у) = 0 для всех x. Напомним также, что если функция / отлична от константы, то степень её производной по любому ненулевому направлению меньше степени /. Несложно доказать, что свойство быть производной некоторой бент-функции сохраняется при аффинном преобразовании, а именно: если булева функция g - производная некоторой бент-функции, то функция g(Ax + b) + А также обладает этим свойством, где A - невырожденная n х n-матрица, b - произвольный вектор, А - константа из F2. В работе исследуется следующая гипотеза: любая уравновешенная булева функция g от n переменных степени не выше n/2 - 1, такая, что g(x) = g(x + у) для всех x при некотором у, является производной некоторой бент-функции от n переменных. На основе аффинной классификации булевых функций от малого числа переменных проверено, что при n = 4, 6 и в ряде случаев при n = 8 гипотеза верна; проверка продолжается.

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