Почти совершенно нелинейные функции: характеризация через подфункции и дифференциальная эквивалентность Городилова Анастасия Александровна

Лавинные характеристики

Нелинейностью булевой функции / от п переменных называется величина Nf, равная расстоянию Хэмминга от / до множества Ап всех аффинных функций от п переменных. Для (п,т)-функции F нелинейность определяется как минимальная из нелинейностей всех ее компонентных функций Fv, v = 0. Максимально нелинейной называется функция, нелинейность которой достигает максимально возможного значения. В случае четного числа переменных п максимальное значение нелинейности известно и равно 2й"1 - 2п12 1. Функции от четного числа переменных п, нелинейность которых равна 2n_1 — 2n/2_1 называются бент-функциями.

Векторная (п, п)-функция F называется дифференциально S-равномерной, если для любых а Є %, а = 0, и Ь Є F уравнение F(x) 0 F(x 0 а) = b имеет не более S решений, где S - целое число. Порядок дифференциальной равномерности F - минимальное S такое, что F является дифференциально -равномерной. Легко видеть, что минимально возможный порядок равен 2, поскольку если хо — решение уравнения F(x) ф F(x ф а) = Ь, то и хо фа также является решением. Почти совершенно нелинейная (APN-функция) - это функция порядка дифференциальной равномерности 2.

Блочный шифр преобразует блок открытого текста (сообщения) длины N в блок шифртекста также длины N с использованием некоторого секретного ключа. Процесс шифрования состоит из нескольких повторяющихся раундов, определяющихся, как правило, одинаковой раундовой функцией, зависящей от раун-дового подключа К І, вырабатываемого по специальному правилу из исходного ключа К.

Наиболее распространенные типы блочных шифров, SP-сетъ и сеть Фейсте-ля, схематично приведены на рис. 1.1 [20]. Обе эти схемы отражают в себе два принципа построения шифрующих преобразований, которые определил в своей работе Клод Шеннон, —рассеивание и перемешивание.

Приведем объяснение этих принципов по книге [5]: «Качественно можно сказать, что перемешивание усложняет восстановление взаимосвязи статистических и аналитических свойств открытого и шифрованного текстов, а рассеивание распространяет влияние одного знака открытого текста на большое число знаков шифртекста, что позволяет сгладить влияние статистических свойств открытого текста на свойства шифртекста». На примере SP-сети хорошо видно, что P-блок обеспечивает рассеивание, а набор небольших S-блоков —перемешивание. В то время как в качестве P-блока обычно выбирается линейная функция, S-блоки составляют нелинейные преобразования шифра.

По сути, S-блок-это векторная (п, т)-функция, причем значения пит небольшие, например 4, 6, 8 битов. Несмотря на столь небольшой размер, найти такой S-блок с «хорошими» криптографическими свойствами достаточно трудно. Для наглядности заметим, что всевозможных отображений из F в себя существует 22048, что в настоящее время не поддается полному перебору! При этом даже аналитические рассуждения пока не могут привести к ответу на некоторые важные для криптографических приложений вопросы. Например, неизвестно, существуют ли взаимно однозначные почти совершенно нелинейные отображения из F в себя при четных п 8, подробнее об этом сказано в раздел 1.13.

Приведем широко используемую модель поточного шифра — шифр гаммиро-вания [5]. В основе таких систем лежит метод «наложения» (например, сложение по модулю 2) ключевой последовательности (гаммы) на открытый текст (шифруемое сообщение). Из работ Клода Шеннона следует, что если ключ имеет такую же длину, как и сообщение, выбирается случайно и равновероятно и при этом используется только один раз, то данная система шифрования является абсолютно стойкой к атакам на основе шифртекста. Поскольку такая модель не применима для широкого распространения в силу того, что затруднительно генерировать такой же объем ключа, как и сообщения, а тем более его пе 22 редавать, перед разработчиками стоит задача получать из короткой случайной последовательности битов ключа некоторую длинную последовательность (гамму), которая будет близка к случайной. Заметим, что именно от свойств данной последовательности зависит криптографическая стойкость шифра.

Часто в качестве компонент поточного шифра используются регистры сдвига с обратной связью. Общая схема их работы приведена на рис. 1.2, где — булева функция от переменных, являющаяся функцией обратной связи [20].

Перед стартом работы происходит начальное заполнение состояния регистра некоторыми п битами. Далее на каждом такте работы вычисляется очередное значение а = /(жп_і,... ,хо), затем все биты регистра сдвигаются влево, при этом в крайний правый бит записывается значение а, а крайний левый бит становится очередным битом выходной последовательности U

Наибольшее распространение получили регистры сдвига с линейной обратной связью (LFSR), т.е. те, в которых / линейна, скажем, /(жп_і,... ,жо) = (с, ж), где с Є F . Заметим, что последовательность, порождаемая любым регистром с обратной связью, всегда периодическая. Легко видеть, что на самом деле любую периодическую последовательность можно породить LFSR подходящей длины. При этом линейной сложностью Си последовательности и называют минимальную длину LFSR, который ее порождает. Линейная сложность последовательности — это основной параметр, характеризующий сложность ее аналитического строения [5].

Напомним, что для генерации «хорошей» гаммы не используется лишь один LFSR. Действительно, если мы знаем функцию обратной связи f(x) = (с, ж), с Є %, то достаточно лишь п подряд идущих битов последовательности для того, чтобы восстановить начальное состояние регистра путем решения системы линейных уравнений. А начальное состояние, как правило, и является секретным ключом шифра.

Кроме того, известен более сильный результат, который позволяет найти линейную функцию обратной связи для любой периодической последовательности. Допустим, что мы перехватили достаточно длинный отрезок некоторой периодической последовательности. Тогда с помощью широко известного алгоритма Берлекэмпа — Месси можно за полиномиальное от длины конечной последовательности время найти закон рекурсии, ее порождающий, что эквивалентно нахождению линейного регистра, который вырабатывает данный отрезок последовательности. При этом если длина последовательности не меньше 2, где — ее линейная сложность, то найденный LFSR вырабатывает и всю бесконечную последовательность, отрезок которой нам известен.

С другой стороны, линейная сложность вырабатываемой последовательности должна быть высокой при почти любом начальном состоянии регистра — неизвестном ключе. В силу этого используют некоторые усложнения. Выделяют две основные модели генераторов, построенных на основе регистров сдвига с линейной обратной связью [20] (рис. 1.3).

Линеаризационные множества

По определению эквивалентности относительно группы сдвигов существуют такие c,d Є %, что G(x) = F(x(Bc)(Bd для всех х Є F . С учетом этого выпишем условие ( ): для всех ж, у, а Є F, а=0, нарушается хотя бы одно из равенств: F(x)(BF(x(Ba) = F(y0c)0 i0F(?/0c0a)0 i, /(х)ф/(хфа) = д(у)фд(уфа)-Заметим, что первое равенство всегда выполнено для любых х, у = х ф с, а = 0. Выберем три пары х, а и выпишем для функций fug условия: х = 0, а = а1, а1 = 0, /(0) 0 /(а1) = д(с) 0 д(с 0 а1) 0 1; ж = 0, а = а2, а2 = 0, а1, /(0) 0 /(а2) = д(с) 0 д(с 0 а2) 0 1; ж = а1, а = а1 0 а2, f(al) Д0,2) = #(с а1) #(с о2) 1 Если сложить по модулю 2 уравнения из первых двух условий и сравнить результат с третьим, то получим противоречие. Следовательно, таких / и д не существует для F и G, т. е. пара F и G не допустима. (1) Пусть для допустимой пары F и G существует в точности к пар буле вых функций fi, ді, і = 1,... ,к, при которых выполнены условия допустимости. Рассмотрим произвольную пару функций F и G , где F (x) = F(x ф с1) ф d1 и G (x) = G(x0с2) 0(і2 при с1, d1, с2,d2 Є F . Тогда непосредственной подстанов кой в условия ( ) и ( ) устанавливаем, что для F и G существуют соответ ствующие булевы функции f- и д[, где //(ж) = / (ж 0 с1) и д[(х) = ді(х ф с2), и при этом только они. Действительно, если существует некоторая пара / , д , не совпадающая для некоторого і с //, д {, то пара f(x) = f(x@c\), д(х) = д (х@со) не будет совпадать с некоторой парой среди fi, д,и і = 1,..., к, что противоречит максимальности выбора к. Следующее утверждение содержит эквивалентный критерий проверки допустимости пары двух APN-функций, не включающий в рассмотрение поиск соответствующих булевых функций.

Утверждение 6. Пара APN-фунщш F u G от п переменных допустима тогда и только тогда, когда для любого нечетного к, к 3, не существует такого набора векторов х\ у\ а\ і = 1,..., к, где аг = 0, что F(xl) 0 F(x% 0 аг) = G(y%) ф G(y% ф аг), і = 1..., к, и в обоих наборах хг, хг 0 а\ і = 1,..., к, и у1, у1 0 а\ і = 1,..., к, каждый вектор встречается четное число раз. Доказательство. По определению пара F и G допустима, если существуют бу левы функции /ид, при которых выполнены условия допустимости ( ). Рас смотрим систему линейных булевых уравнений от 2n+1 неизвестных fx = f(x), Qx = д(%), где х Є %, состоящую из уравнений fx 0 fx(S)a 0 ду 0 дуфа = 1 для всех тех ж, у, а, при которых F(x) 0 F(x 0 а) = G(y) 0 G(y 0 а). По построе нию пара допустима тогда и только тогда, когда совместна построенная система уравнений относительно значений функций / и д. По известной теореме Кро некера — Капелли система линейных уравнений совместна тогда и только тогда, когда ранг матрицы системы равен рангу расширенной матрицы. В данном слу чае совместность рассматриваемой системы эквивалентна тому, что не найдется к различных уравнений системы, таких, что их сумма по модулю два приводит к уравнению вида 0 = 1, что в свою очередь равносильно тому, что к нечетно, и каждая переменная, входящая в сумму данных уравнений, встречается четное число раз.

Замечание 2. Если пара APN-фунщий FuG допустима, то значения соответствующих булевых функций fug определяются как решение системы линейных уравнений, рассмотренной в доказательстве утверждения 6.

Для построения квадратичной APN-функции S от п + 1 переменных с помощью описанного выше метода в качестве двух исходных допустимых векторных функций F и G от п переменных необходимо брать квадратичные функции, которые в сумме дают аффинную функцию. Действительно, без ограничения общности можно рассматривать S(x, xn+i) = ({xn+i 0 l)F(x) 0 xn+iG(x), (xn+i 0 l)f(x) 0 xn+ig(x)).

Тогда по построению первые n координатных функций xn+\(F(x)G(x))F(x) определяют квадратичную функцию тогда и только тогда, когда F — квадратичная и F 0 G — аффинная, следовательно, G также является квадратичной функцией. Отметим, что данное условие не является достаточным, так как п +1 координатная функция S может не быть квадратичной функцией. Поскольку порядок дифференциальной равномерности инвариантен относительно прибавления аффинной функции, то в качестве F и G в этом случае следует рассматривать только функции одного порядка дифференциальной равномерности. Утверждение 7. Пусть F - квадратичная APN-функция, а L - произвольная линейная функция от п переменных. Пусть существуют в точности к различных ненулевых аг Є Щ, при которых Bai(F) = Bai(F 0 L). Тогда, если к 2п 1, то пара F, F 0 L не является допустимой.

Доказательство. Так как F - квадратичная APN-функция, то все ее производные аффинны, и, следовательно, множества Ba(F) = {F(x) ф F(x(Ba) \ х Є F } являются аффинными подпространствами размерности п — 1. Поскольку L — линейная функция, то Ba(F 0 L) = Ba(F) 0 L(a), где под сложением вектора и множества понимается сложение всех элементов множества с данным вектором. Тогда для каждого ненулевого вектора а множества Ba(F) и Ba{FL) либо совпадают, либо не пересекаются. Поскольку по условию для а1,..., ак множества совпадают, тогда для любого х найдутся такие векторы у1, ..., ук, что F{x) 0 F[x 0 а1) = F[yl) 0 F[yl 0 а1) 0 L(al), F(x) 0 F(x 0 ak) = F(yk) 0 F(yk 0 ak) 0 L(ak). Если к 2n_1, то среди 2k векторов y, y% 0 a, і = 1,..., к, найдутся два одинаковых, например, уі = уе = у (заметим, что уг ф уг 0 аг для любого і, так как а1 ф 0). Тогда F{x) 0 F{x 0 а-7 ) = F{y) 0 F{y 0 а-7 ) 0 Ь{а )} F[x) 0 F[x 0 о!) = F(y) 0 F(y 0 a?) 0 L(a), F(x 0 a-7 ) 0 F(x 0 a1) = F(y 0 a-7 ) 0 F(y 0 a1) 0 L(a-7 0 a ), где третье равенство получается путем сложения по модулю 2 первых двух. Таким образом, по утверждению 6 получаем, что пара F и F 0 L не является допустимой. Гипотеза 1. Для любой квадратичной APN-функции F существует линейная функция L такая, что пара F и F 0 L является допустимой. В качестве подтверждения гипотезы 1 при малом числе переменных вычислительно получено следующее утверждение.

Утверждение 8. Пусть Fh ..., Fk - представители всех классов эквивалентности относительно группы сдвигов APN-функций от 3-х переменных. Тогда для любой F{ существует в точности 35 функций F ,..., Fi35 таких, что пара F{ и F{. допустима и Ft Ftj - линейная функция для любого j = 1,... ,35. Аналогично для каждого представителя классов функций порядка дифференциальной равномерности 4 существует либо 0, либо 1, либо 2 допустимых представителей других классов, отличающихся на линейную функцию.

Вычислительные результаты

Необходимым условием принадлежности двух таких чисел одному циклотомическому классу является равенство длин групп подряд идущих 1. Следовательно, любые два числа в каждой из рассмотренных выше групп (Р 1,..., Р 1 и P +l)..., Pk l) принадлежат разным циклотомическим классам. Действительно, п — к ф к по условию леммы ип — кфі — к — 1 для всех i = ft + l,...,n — 1. (3), (4) Согласно рассуждениям выше о двоичных представлениях чисел Р%к единственный возможный случай, когда \С(Ргк)\ ф п, следующий: если длины групп подряд идущих 1 обе равны п/2 — 1. Если п нечетно, то этот случай невозможен. Если п четно, возможны следующие случаи: і = п — 1 при ft = п/2 — 1 и і = к — 1 при ft = п/2 + 1. В обоих случаях Р%к = 2п/2Р по модулю 2П — 1, что завершает доказательство. Лемма 2. Пусть — целое число, 1. Если четно, то gcd(2,±l) = 1; если нечетно, то gcd{2) ± 1) = 2.

Доказательство. Пусть gcd(2, ± 1) = d. Тогда 2 = xd и ± 1 = y i, где gcd(:r, у) = 1. Выражая из второго равенства и подставляя его в первое, получаем 2 = (=рж ± 2у) 1 Следовательно, единственно возможные случаи следующие: d = 1 или d = 2. Тогда если четное, то ± 1 нечетное и d = 1; иначе d = 2. 3.2.2 Основной результат об APN-функциях Голда

Для APN-функции Голда F известен [43] точный вид ассоциированной булевой функции 7F. Для полноты приведем данный факт с доказательством. Утверждение 12. [43] Пусть F : 2п -+ 2п - функция Голда F{x) = x2"+l, где gcd(k, п) = 1. Тогда 7іКа Щ = tr ( (a2 +1)_16) + tr(l) + 1 при а Ф 0 и 7 (0? Ь) = 0 для всех Ъ Є F2«. Доказательство. По определению 7Иа Ь) = 1 тогда и только тогда, когда а ф 0 и уравнение F(x) + F(IK + а) = Ь имеет решение. Рассмотрим данное уравнение для функции Голда: ж241 + (х + а)241 = Ъ, Л + жа2 = 6 + а2 +1 / аГ1 (a?) l, ж2 (а-1)2 + жа-1 = Ь(а241)-1 + 1 Если решение существует, то, подействовав функцией следа на обе части уравнения, получаем: tr (х2\аГ1)2к + ха 1 ) = 0 = tr a241)-1 + і) . Тогда 7-F(&5 Ъ) = tr (6(a2 +1)-1 + l) + 1 = tr ( (a2 +1)_1б) + tr(l) + 1. П Следующая теорема содержит основной результат об APN-функциях Голда.

Теорема 2. Пусть F - APN-фунщия Голда от п переменных, F{x) = x2"+l и gcd{k,n) = 1. Тогда выполнены следующие утверждения: (1) если п = At для некоторого t и к = п/2 ± 1, то существуют в точности 22п+п 2 различных аффинных функций А таких, что F и F+A дифференциально эквивалентны, при этом А{х) = a +A2 х + \х2 +5x2J, где а, А, 5 Є 2п, 5 = 52" , и j = к — 1 при к = п/2 + 1 и j = п — 1 при к = п/2 — 1; (2) иначе существуют в точности 22п различных аффинных функций А таких, что F и F + А дифференциально эквивалентны, при этом А{х) = а + А2 х + Хх2 , где а, А Є 2п. Доказательство. По утверждению 12 ассоциированная функция -iF для APN-функции Голда F имеет вид г)р{а)Ь) = tr ( (a2 +1)_16) + tr(l) + 1 при а Ф 0 и 7F(0, Ь) = 0 для всех О Є Jr 2 . Пусть Л : 2п — 2п — произвольная аффинная функция и L — ее линейная часть, Ь(ж) = А(х) + А(0). Тогда IF+L I Ь) = 7-F(a? + (а) ) = tr ( (a + ) (b + L(a) ) + tr(l) + 1 = tr ( (a + ) Щ + tr ( ((a + ) Ь(а) ) + tr(l) + 1. Таким образом, fF+L(a, Ь) = jF(a, Ь) + tr{{a2k+lylL{a) ) . Следовательно, F и F + А дифференциально эквивалентны тогда и только тогда, когда линейная часть L функции А удовлетворяет равенству tr ( (a2 +1) 1L(a) ) = 0 для всех а Є F2». Обозначим через N число таких аффинных функций.

Пусть А{х) = а + Х Г=о - — аффинная функция, где a, Si Є F2«, і = 0,..., п — 1. Тогда получаем цепочку равенств, выполненных для всех а Є F2»: п—1 п—1 tr ( (CL ) ±J \ CL ) І —— tr ( / 0 і CL 1 CL ) I —— / tr ( 0 і CL ) —— U. г=0 г=0

Последнее равенство представляет собой полиномиальное уравнение от переменных а степени не выше 2П — 1, которое имеет 2п решений. Следовательно, коэффициенты при всех мономах равны 0. Определим вид коэффициентов при каждом из мономов xd, d = 0,..., 2п — 1. Для этого рассмотрим циклотомиче-ские классы всех экспонент Р = 2% — 2к — 1, і = 0,... ,п — 1, для данного к. По лемме 1 (1,2) существуют только две экспоненты Р и Р, принадлежащие одному циклотомическому классу по модулю 2П — 1. Следовательно, So и Sk связаны соотношением So = (Sk)2 при всех п, так как Р = 2кР ( mod (2П — 1) ) . Далее рассмотрим несколько случаев.

Случай 1. Если п нечетно, то по лемме 1 (2,3) получаем Si = 0 при і ф 0, к. Таким образом, N = 22п, поскольку a, Sk могут быть произвольными элементами Jr 2 . Пусть п четно, п = 2. Рассмотрим два случая в зависимости от четности . Случай 2. Если нечетно, то gcd(n,n/2 ± 1) = 2 по лемме 2. Следовательно, случай к = п/2 ± 1 не рассматривается по условию теоремы. Тогда Si = 0 при і ф 0, к по лемме 1 (4). Аналогично случаю 1, N = 22п. Случай 3. Если четно, то по лемме 2 gcd(n, п/2 ± 1) = 1. — Если к ф п/2 ± 1, то по лемме 1 (4) имеем: Si = 0 при і ф 0,к. Тогда N = 22п. — Если к = п/2 + 1, то по лемме 1 (4) имеем: Si = 0 при і ф 0,fc - l,fc и Sk-i = (Sk-i)2" . Так как число элементов х Є F2», удовлетворяющих уравнению х = х2п/2 равно 2п12, получаем N = 22п+п12. — Если к = п/2 — 1, то по лемме 1 (4) имеем: Si = 0 при і ф О, /с, п — 1 и n_i = ( n_i)2 . Аналогично подслучаю выше, 7V = 22п+п/2. П

Теорема 2 показывает, что класс APN-функций Голда содержит квадратичные функции, классы дифференциальной эквивалентности которых шире, чем тривиальные {FCyd(x) = F(x + с) + d I с, d Є F } мощности 22п (напомним, что для квадратичной функции F верно Fc4 = F + Л , где Ad - аффинная функция для всех с, rf Є F). Действительно, мощность P F, где F(x) = х2п/ш+\ п = U, больше либо равна 22п+п/2 согласно теореме 2 (1). Кроме того, как установлено в разделе 3.3, эти функции являются единственными (кроме одной функции от 6 переменных) среди всех квадратичных APN-функций от 2,..., б переменных и всех известных квадратичных APN-функций от 7, 8 переменных, для которых существует больше, чем 22п, аффинных функций, сложение которых с исходной функцией сохраняет ассоциированную булеву функцию.

В данном разделе приводятся результаты о дифференциально эквивалентных APN-функциях, полученные с помощью компьютерных вычислений.

Таблица 3.2 содержит классификацию APN-функций относительно дифференциальной эквивалентности при малом числе переменных п = 2,3,4. Для данных размерностей видим, что дифференциальная эквивалентность двух функций влечет также их ЕА-эквивалентность.

Кратные производные булевых функций Касами

Легко видеть, что из определения Q А 1 — 2й . Понятие линейного спектра естественно возникает при изучении квадратичных APN-функций F, их конструкций и соответствующих им ассоциированных функций 7F. Отметим два конкретных направления исследований APN-функций, для которых представляет интерес линейный спектр. В разделе 2.3 данной работы описан подход для поиска итеративной конструкции APN-функций. В частности, для построения квадратичной APN-функции S от п +1 переменных с помощью данного метода в качестве двух исходных допустимых (см. определение 3, раздел 2.3) векторных APN-функций F и G от п переменных необходимо брать квадратичные функции, которые в сумме дают аффинную функцию, а именно, S(x,xn+i) = ( (жп+1 Ф l)F(x) ф xn+\G{x)) (хп+\ 0 l)f(x) 0 xn+\g{x) ) , где f,g — некоторые булевы функции от п переменных. Тогда по построению первые п координатных функций xn+\(F(x) 0 G(x)) 0 F(x) определяют квадратичную функцию тогда и только тогда, когда F — квадратичная и F 0 G — аффинная, следовательно, G также является квадратичной функцией. Тогда утверждение 7 в терминах данного раздела формулируется так: пара функций F и F 0 L не допустима, где F — квадратичная APN-функция и L — линейная функция, если к 2п 1. Следовательно, перед тем как проверять условия допустимости, полезно определить, а какие к могут быть. Другое направление связано с понятием дифференциально эквивалентных APN-функций. Функции F и G называются дифференциально эквивалентными (глава 3), если 7F = 1с Описание классов дифференциальной эквивалентности является актуальной открытой задачей, которая возникает у многих специалистов [42], поскольку ее решение может потенциально привести к новым конструкциям APN-функций. Тогда крайнее значение линейного спектра Л_х квадратичной APN-функции F отвечает за то, сколько существует дифференциально эквивалентных F функций, в сумме с F дающих линейную функцию.

Кроме того, по утверждению ниже линейный спектр является EA-инвариантом, следовательно, может быть использован для проверки неэквивалентности относительно EA-преобразования.

Утверждение 16. Линейный спектр квадратичной APN-функций инвариантен относительно ЕА-преобразования. Доказательство. Пусть G = А о F о А" 0 А, где F, G — квадратичные APN-функции от п переменных, А , А" — взаимно однозначные аффинные функции, А - аффинная функция. Тогда Ba(G) = А (ВАЧа)фАЧо) (F) ) 0 4/(0) 0 А{а) 0 А(0). Следовательно, для любой линейной функции L верно, что kFL = Щ, поскольку Ba(F) = Ba(F 0 L) тогда и только тогда, когда Ba(G) = Ba(G 0 L ), где L (x) = Л/(Ь(ж) ) 0 Af(0). Так как А — взаимно однозначная функция, то V пробегает все возможные линейные функции при переборе всех возможных линейных функций L. Таким образом, по определению линейного спектра AF = AG. Справедливо следующее утверждение о крайнем значении линейного спектра произвольной квадратичной APN-функции. Утверждение 17. Пусть F - квадратичная APN-функция от п переменных, п 1. Тогда Л1_1 2П. Доказательство. Рассмотрим Lc(x) = F(x) 0 F(x 0 с) 0 F(0) 0 F(c) для произвольного с Є F. Функции Lc линейны в силу квадратичности F, и при этом 7JF = 1FLC для любого с Є Щ. Кроме того, так как F - APN-функция и п 1, то все 2П функций Lc, с Є F , попарно различны. Следовательно, A.f„_i 2П. П По результатам раздела 3.2 можно сформулировать как следствие результат о крайнем значении APN-функций Голда. Следствие 2. Пусть : F2« - F2« - APN-функция Голда () = 2"\ где gcd(,) = 1. Тогда выполнены следующие утверждения: (1) fl = 2пЄп/Ч если = 4 для некоторого и = /2 ± 1; (2) _1 = 2П иначе.

Получена следующая теорема о нулевых значениях линейного спектра. Теорема 4. Дус/иь - квадратичная APN-функция от переменных, четно, 1. Тогда выполнены следующие утверждения: (1) f1 = 0 для всех четных , 0 2п — 2; (2) = 0 для всех 0 (2П — 1)/3.

Доказательство. Пусть (,) = ((), Є () Є 1. Напомним, что = { Є F і?() = } для любого Є F . По теореме 3 для любого Є F2 такого, что f непусто, размерность „ U {0}) четна. Следовательно, минимально возможная \„\ равна 3. Кроме того, если \„\ 3, то „ можно представить как объединение \„ /3 линейных подпространств „ i размерности 2 без нулевого вектора, = 1,..., \„ /3. Пусть U {0} — линейное подпространство размерности 2 либо совпада ющее с некоторым у, либо c { при \ \ 3. Заметим, что таких подпро странств в точности (2П — 1)/3. Тогда (р(),())\м = (, ())м — ли нейная функция, где - некоторый вектор. Следовательно, (Р(),())\м = 0 либо для всех трех векторов Є , либо только для одного. Так как число (2П — 1)/3 нечетно, то согласно (4.2) с учетом рассуждений выше получаем, что нечетно. Кроме того, поскольку для каждого хотя бы для одного Є выполнено (р(), ())м = 0, то f = 0 для всех 0 (2П — 1)/3. Замечание 3. Строго говоря, оценку пункта (2) теоремы 4 можно улучшить. Но для этого необходимо знать, каковы мощности FV для квадратичной функции . Пусть сначала = (2п — 1)/3, тогда по теореме 4(2) = 0 для всех 0 . Просматривая Є %, заменяем текущее число на — \FJ/3+2dim u _1 — 1 как только \ \ 3 для некоторого Є %, поскольку в доказательстве теоремы вместо подпространств {, = 1,..., \F /3, можно по аналогии рассмотреть все множество . Рассмотрев все возможные , получим итоговую оценку: f = 0 для всех 0 .

Замечание 4. Вычислительно найдены линейные спектры всех представителей классов ЕА-эквивалентности квадратичных APN-функций от переменных для = 3,4,5,6 (см. Таблицы 4.1, 4.2, 4.3, 4.4). Отметим, для этих размерностей классификация всех квадратичных APN-функций известна полностью [31,32, 58]. Представителей классов EA-эквивалентности можно найти в работе [31] (функция №13 в таблице 5 из [31] не является квадратичной). Вычисления для = 6 проводились на кластере НКС-30Т ССКЦ СО РАН. Отметим, что для = 5 спектры различных представителей попарно различны, а при = 6 существует два класса №3 и №10, спектры которых совпадают. Кроме того, оценка из утверждения 4 (2) с учетом замечания 3 является точной для рассмотренных . Замечание 3 реализуется лишь для одного класса при = 6: для функции №11 существует одно множество мощности 15.