Свойства БФ 2023

1. Криптографические свойства булевых функций

Свойства и способы
построения

2. Булевы функции

2
Определения и обозначения
2 – поле Галуа {0,1}
Vn – ( 2)n - n-мерное векторной пространство над 2
wt(x) – Вес Хэмминга вектора x Vn
f: Vn 2 - булева функция n аргументов
n – множество всех булевых функций от n аргументов
wt(f) = #{x Vn | f(x) = 1} – вес булевой функции
dist(f,g) = wt(f g) – расстояние между булевыми функциями
Представление булевых функций:
1. Полином Жегалкина
n
f x1,..., xn c0 ci xi cij xi x j ... c12...n x1...xn
i 1
1 i j n
2. Алгебраическая нормальная форма
f x1 ,..., xn
1 ,..., n Vn
g f 1,..., n x1 1 ...xn n
Алгебраическая степень f – число переменных в самом длинном терме
представления.
: Vn Vm – булево отображение, = {f1(x), …fm(x)}, x Vn
n,m – множество булевых отображений из Vn в Vm

3. Булевы функции

3
Свойства булевых функций и отображений
Сбалансированность
Нелинейность
Корреляционная иммунность
Упругость/устойчивость
Лавинные критерии
Критерии распространения
Алгебраическая иммунность

4. Сбалансированность

4
Сбалансированность
1. Сбалансированность
Определение. Отображение n,m (m n) сбалансировано, если
v Vm #{u Vn | (u) = v} = 2n – m
Если m=1, то отображение является булевой функцией f, которая
сбалансирована, если
wt(f)=2n-1
Каждое сбалансированное отображение сюръективно, не существует
нетривиальной булевой функции g m, такой что u Vn g(f1(u),…,fm(u)) =
0, т.е. f1,…,fm алгебраически независимы
Поэтому для отображения n,m алгебраическая независимость
координатных функций f1,…,fm
является необходимым условием
сбалансированности.

5. Нелинейность

5
Нелинейность
Базовые определения
Определение 1. Множество аффинных функций n n определяется как
множество функций с deg f 1:
n = {f n | deg f 1}
Полином Жегалкина произвольной аффинной функции f имеет вид:
f(x1,…,xn) = a1x1 … anxn b
Определение 2. Преобразованием Уолша-Адамара булевой функции f
называется целая функция над Vn:
W f u exp f x ( 1)
x Vn
x,u
1
f x x,u
x Vn
Определение 3. Расстоянием от булевой функции f n до множества
M n называется величина
dist ( f , M ) min dist f , g
g M

6. Нелинейность (продолжение)

6
Нелинейность (продолжение)
Определение 4. Степенью нелинейности Nf булевой функции f n
называется расстояние от функции до множества всех аффинных функций n.
Определение 5. Степенью нелинейности N булева отображения n,m
называется следующее значение:
Nc f ... c f
c V ,c 0
N min
m
1 1
m m
Производная по направлению (Da) не должна обращать б.ф. в линейную
функцию.
Неформальное описание нелинейности:
1) «Функция с хорошей нелинейностью» далека от множества аффинных
функций в смысле какой-либо метрики.
2) «Функция с хорошей не линейностью» должна выражаться полиномом
как можно более высокой степени.
3) «Функция с хорошей нелинейностью» не должна линейно зависеть ни от
одной из своих переменных и не должна приобретать такую зависимость
после какой-либо линейной замены переменной. Это свойство формулируют
так: функция не должна иметь ненулевых линейных структур.

7. Корреляционная иммунность

7
Корреляционная иммунность
Определение 1. Взаимная информация двух случайных переменных X и Z определяется
как
I X , Z Pr X u, Z v log 2
u U v V
Pr X u, Z v
Pr X u Pr Z v
Определение 2. Булева функция f n имеет корреляционный иммунитет
порядка m, 0< m n, если
1 i1 i2 ... im n, I X i1...im , Z 0, где
X i1...im X i1 ,..., X im and Z f X 1,..., X n
Имеют место следующие свойства:
Булева функция f n корреляционно иммунная порядка m, 0< m n, если и
только если выполняется одно из следующих утверждений:
wt f
1 ,...,am
1. 1 i1 i2 ... im n, a j F2 , j 1...m, wt fi a,...,
im
1
2m
2. u Vn ,1 wt u m, W f u 0
Для булевой функции f n корреляционный иммунитет m и
алгебраическая степень d связаны неравенством: m + d n

8.

Корреляционная иммунность (продолжение)
Неформальное описание корреляционной иммунности:
1) Влияние какой либо переменной в булевой функции на ее значение
должно быть равнозначно по отношению к другим переменным;
2) Фиксация какой-либо переменной не должна давать информацию о
«роли» этой переменной в алгебраической нормальной форме;
3) Фиксация какой-либо переменной не должна приводить к
инвертированию всех значений функции;

9. Упругость/устойчивость

9
Упругость/устойчивость
Определение 4.1. Пусть = (f1,…,fm) n,m - отображение, где1 m n, и
x = (x1,…,xn)
1. называется несмещенным по отношению к фиксированному
подмножеству T={j1,…,jt} из{1,…n} если (a1,…,at) Vt отображение
,....,at
aj1,...,
j f1 x ,..., f m x |x j a1 ,..., x j at
1
t
1
t
сбалансировано.
2. называется (n,m,t)-упругим если оно несмещенное по отношению к
любому подмножеству T из{1,…,n}, такому что|T| = t.
Неформальное описание устойчивости:
1) Б.ф. устойчива, если все ее подфункции сбалансированы;
2) Из количества устойчивых подфункции (количества фиксаций
переменных) определяется степень устойчивости.

10. Лавинные критерии

10
Лавинные критерии
Базовые определения
Определение 1. Производной булевой функции f n по направлению u Vn
(u 0) называется функция
Du f x f x u f x
Определение 2. Производной булевой функции f n по направлению
подпространства L Vn называется функция
DL f x f x u
u L
Свойства производных.
1. L Vn, f n, u L
DLf(x) = DLf(x u)
2. L Vn, f,g n
DL(f g) = DLf DLg
3. f n, u, v, x Vn
Du v f(x) = Du f(x) Dv f(x u)
4. Du f 0 f const
5. Du f const f n

11. Лавинные критерии (продолжение)

11
Лавинные критерии (продолжение)
Определение 3. Кросс-корреляцией (взаимной корреляцией) булевых функций
f,g n называется целочисленная функция
f x g x u
f , g u 1
x Vn
Определение 4. Автокорреляцией булевой функции f n называется
целочисленная функция
f u 1
f x f x u
x Vn
Свойства корреляционных функций
1. f,g n , u Vn
f,g(u) = g,f (u)
2. f n, u Vn
f,f(u) = f (u)
f u WDu f 0
3. f n, u Vn
Определение 5. Функции f и g называются совершенно некоррелированными,
если ∆f,g (u) = 0 для любого u.

12. Лавинные критерии (продолжение)

12
Лавинные критерии (продолжение)
Определение 6. = (f1,…,fm) n,m удовлетворяет лавинному критерию, если
i,1 i n, wt x x ei m 2n 1
x Vn
Определение 7. = (f1,…,fm) n,m удовлетворяет строгому лавинному
критерию (SAC), если ∆Ф (u) = 0 для всех u, таких, что wt(u) = 1.
Или: функция f удовлетворяет строгому лавинному критерию, если её
производные по всем направлениям веса 1 уравновешены
В случае m = 1 строгий лавинный критерий эквивалентен лавинному
критерию.
Неформальное описание:
1) Б.ф. не имеет линейных и фиктивных переменных;
2) При изменении 1-го бита в x значение f (x) изменится для x = 00 и x = 10;
2-го бита для x = 00 и x = 01. Т.е. изменения с будут накапливаться и
влиять на следующие биты.

13. Критерии распространения

13
Критерии распространения
Определение 5.7. Булева функция f n удовлетворяет критерию
распространения в направлении a Vn если f(a) = 0 (или, эквивалентно, если
Daf сбалансировано).
Определение 5.8. Булева функция f n удовлетворяет
распространения степени (обозначается PC(k)), если
критерию
a Vn ,1 wt a k f a 0
PC(1) эквивалентен SAC, и если f является функцией с максимальной
нелинейностью (n четно), то f удовлетворяет PC(n).
Развитие данного подхода привело к следующему определению:
Определение 5.9. Булева функция f n удовлетворяет строгому лавинному
критерию порядка t, 1 t n – 2 (обозначается SAC(t)), если
,...,at
1 j1 ... jt n, a a1,..., at Vt подфункция f ja1,...,
j
1
t
удовлетворяет SAC.
Следующие утверждения имеют место: Пусть f n , n > 2. Тогда
1. Если f удовлетворяет SAC(n – 2), то deg f = 2.
2. Если f удовлетворяет SAC(t), 0 t n – 2, то deg f n – t – 1.

14. Критерии распространения

14
Критерии распространения
Определение 5.10. Булева функция f n удовлетворяет
распространения степени k и порядка t (PC(k,t)), если
критерию
,...,at
1 j1 ... jt n, a a1,..., at Vt подфункция f ja1,...,
j удовлетворяет PC(k).
1
t
Определение 5.11. 1) булева функция f n удовлетворяет расширенному
критерию распространения степени k и порядка 0 (EPC(k,0) если a Vn,
1 wt(a) k, Daf сбалансирована;
2) удовлетворяет расширенному критерию распространения степени k и
порядка t > 0 (EPC(k,t)), если a Vn, 1 wt(a) k, Daf является t-упругой.
Имеют место следующие свойства ( f n):
1. если f удовлетворяет EPC(k,t), k + t n, то f удовлетворяет PC(k,t);
2. если f удовлетворяет PC(k,0) или PC(k,1) то f удовлетворяет EPC(k,0)
или EPC(k,1) соответственно;
3. если f удовлетворяет PC(1,t), то f удовлетворяет EPC(1,t)

15. Алгебраическая иммунность

15
Алгебраическая иммунность
Определение 6.1. Аннулирующим множеством AN(f) булевой функции f n
называется множество
AN f g F n | f g 0
Любая g AN(f) называется аннулятором f.
Определение 6.2. Алгебраическим иммунитетом AIn(f) булевой функции f n
называется минимальная степень всех ненулевых аннуляторов f или f 1.
Поскольку f(f 1) = 0, AIn(f) deg f. Также можно показать, что AIn(f) n/2 .