Vectorial boolean functions on distance one from apn functions.pdf В работе исследуются метрические свойства класса векторных булевых функций, а именно APN-функций. Знание метрических свойств позволяет получать конструкции таких функций, а также сокращать перебор при поиске функций, обладающих определённым свойством. Например, метрические свойства класса бент-функций исследовались в работах [1, 2]. В 1994 г. K. Nyberg [3] было введено понятие дифференциально ^-равномерных векторных булевых функций (differentially ^-uniform). Векторная булева функция F : Zn ^ Zn называется дифференциально 6-равномерной, если при любом ненулевом векторе a E Zn и произвольном векторе b уравнение F(x) ф F(x ф a) = b имеет не более 6 решений, где 6 - целое число. Для векторной функции F и любого ненулевого вектора а определим множество B«(F) = {F(x) ф F(x ф а) : x E Zn}. Максимальная достижимая мощность множества Ba(F) равна 2n-1. В частности, если при любом ненулевом векторе а выполнено |Ba(F)| = 2n-1, то функция F является APN, а если выполнено |Ba(F)| ^ 2n-1 - 1, то дифференциально 4-равномерной. Минимальное 6, при котором функция является дифференциально 6-равномерной, назовём порядком дифференциальной равномерности. Расстоянием между векторными булевыми функциями F и G называется мощность множества {x E Zn : F(x) = G(x)}. Утверждение 1. Пусть F - APN-функция от n переменных. Тогда все функции на расстоянии один от F являются дифференциально 4-равномерными. Доказательство. Пусть F - APN-функция. Тогда при любом ненулевом векторе a E Zn выполнено равенство |Ba(F)| = 2n-1. Рассмотрим функцию G, совпадающую с F во всех точках, кроме некоторого x1 E Zn. Пусть Bo(G) = {G(x) ф G(x ф a) : x E Zn\{xb x1 Ф a}}. При любом ненулевом векторе a E Zn множество Ba(F) совпадает с Ba(G) и выполнено равенство |B^(G)| = 2n-1 -1. Заметим, что Ba(G) = Ba(G)U{G(x1 ^G^фa)}. Тогда для любого значения G(x1), в том числе отличного от F(x1), и при любом ненулевом a E Zn выполнено |Ba(G)| ^ ^ |Ba(G)| = 2n-1 - 1, т.е. функция G является дифференциально 4-равномерной. ■ Гипотеза. Пусть F - APN-функция от n переменных. Тогда все функции на расстоянии один от F являются дифференциально равномерными порядка 4. Другими словами, на расстоянии один от APN-функций не может быть других APN-функций, т. е. минимальное расстояние между APN-функциями не меньше двух. На расстоянии два APN-функции могут быть; например, функции F = = (0, 0,1, 2,1, 4, 2, 4) и G = (0,0,1, 2,1,4, 4, 2) отличаются двумя последними значениями и обе являются APN-функциями. Заметим, что гипотеза верна, если и только если существует a E Zn, для которого выполнено равенство |Ba(G)| = |Ba(G)|. Для этого требуется, чтобы сумма G(x1) ф ф G(x1 ф a) принадлежала множеству Ba(G).

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