Simple proof for the strong regularity of the cayley graph of bent function.pdf Бент-функции возникают в ряде криптографических приложений и широко исследуются. В частности, очень важной является задача описания бент-функций в алгебраических и комбинаторных терминах [1]. Пусть f — булева функция от n переменных. Через supp(f) обозначим её носитель, т. е. множество всех двоичных векторов длины n, на которых функция f принимает значение 1. Рассмотрим граф Кэли Gf = G(Zn, supp(f)) булевой функции f. Вершинами графа являются все векторы длины n. Две вершины x, y соединяются ребром, если вектор x фy принадлежит множеству supp(f). Граф G называется сильно регулярным с параметрами (v, k, А,р), если он содержит v вершин, степень каждой вершины равна k и для любых двух вершин x, y число общих смежных им вершин равно А или р в зависимости от того, соединены вершины x, y ребром или нет. Булева функция f от чётного числа переменных n называется бент-функцией, если ее производная по любому ненулевому направлению y уравновешена, т.е. выполняется (—1)f(x+y) = 0. xezr; В 2001г. А. Бернаскони, Б. Коденотти и Дж. Ван-дер-Кам [2, 3] получили следующий результат, позволивший охарактеризовать множество бент-функций в терминах сильно регулярных графов. Теорема 1. Булева функция f является бент-функцией тогда и только тогда, когда граф Gf является сильно регулярным, причем А = р. Доказательство было получено с помощью спектральной техники при исследовании графов, ассоциированных с булевыми функциями. Бент-функции при этом составили частный случай булевых функций с тремя различными спектральными коэффициентами. Недостатком такого доказательства служит его объёмность и малая наглядность: остаётся трудным объяснить по существу, почему же графы Кэли бент-функций (и только они) обладают таким примечательным свойством, как сильная регулярность. В связи с этим результат было трудно включить, например, в учебный курс. В данной работе получено простое доказательство теоремы 1, непосредственно опирающееся на свойства бент-функций. Явно определены параметры сильно регулярных графов, соответствующих бент-функциям. Теорема 1 вытекает из следующих утверждений, доказательства которых теперь могут войти в любой учебный курс. Утверждение 1. Граф Кэли Gf бент-функции f от n переменных сильно регулярный с параметрами (2n, 2n-1 ± 2(n/2)-1, А = р = 2n-2 ± 2(n/2)-1). Знаки «±» считаются согласованными, т. е. одинаковыми в обоих случаях. Утверждение 2. Пусть G — сильно регулярный граф на 2n вершинах, n ^ 2, такой, что Л = ^ > 0. Тогда он имеет параметры из утверждения 1.

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