5.1 Підфункції та похідні булевіх функцій

Криптографічна практика показує, що булеві функції, що використовуються для побудови генераторів гами, крім рівноймовірності й високої нелінійності, повинні мати ряд більш тонких властивостей, які послаблюють зв’язки між виходами функцій ускладнення і послідовностями відповідних аргументів. Наявність таких властивостей у булевої функції перевіряється за допомогою, так званих критеріїв розповсюдження та кореляційної імунності.

Для формулювання відповідних визначень використовуються поняття підфункції булевої функції та її похідної.

Назвемо похідною булевої функції за напрямком,, функцію виду.

Введемо також позначення , при обмеженні.

Вектори , що задовільняють (у відповідному контексті) деяке обмеження будемо називати допустимими, наприклад,для.

Підфункцією булевої функції , що отримана фіксацієюзмінних на місцяхза допомогою вектора, називається функція, яка визначається рядками таблиці, для яких,,.

Аргументами функції є аргументи з номерами, що не належать множині, а значеннядорівнює.

Якщо функція задана аналітично, то при фіксації змінних частина змінних заміняється на деякі числа, що дає нову функцію від меншої кількості змінних.

5.2 Приклади

Запишемо булеву функцію у табличному виді, та обчислимо її похіднідляіпри,. Тобто, ми обчислимо не всі похідні другого порядку, а деякі.

Таблиця 5.1 Похідні булевих функцій

№
0	0	0	0	0	0	1	1	1	1
1	0	0	0	1	0	1	1	1	1
2	0	0	1	0	0	1	1	1	1
3	0	0	1	1	0	1	1	1	1
4	0	1	0	0	1	0	1	0	1
5	0	1	0	1	1	0	1	1	0
6	0	1	1	0	1	0	1	0	1
7	0	1	1	1	1	0	1	1	0
8	1	0	0	0	0	1	1	0	0
9	1	0	0	1	1	0	1	1	0
A	1	0	1	0	0	0	0	1	1
B	1	0	1	1	1	1	0	0	1
C	1	1	0	0	1	0	1	0	1
D	1	1	0	1	0	1	1	1	1
E	1	1	1	0	0	0	0	0	0
F	1	1	1	1	1	1	0	1	0

Підфункції від двох змінних при.

Оскількі розмірність аргументу підфункцій (тобто, після фіксації) дорівнює 2, то кількість змінних, що фіксуються дорівнює. Таким чином, умовакоректна. Якщоне було би задано, то слід було б вибирати чотири векторидля всіх значень .

Таблиця 5.2 Підфункції, що отримані з при

№					, ,
0	0	0	0	0	0
1	0	0	0	1	0
8	1	0	0	0	0
9	1	0	0	1	1
№					, ,
2	0	0	1	0	0
3	0	0	1	1	0
A	1	0	1	0	0
B	1	0	1	1	1
№					, ,
4	0	1	0	0	1
5	0	1	0	1	1
С	1	1	0	0	1
В	1	1	0	1	0
№					, ,
6	0	1	1	0	1
7	0	1	1	1	1
E	1	1	1	0	0
F	1	1	1	1	1

Вивчення властивостей булевих функцій з метою побудови криптосхем блокових шифрів, привело до ідеї строгого лавинного критерію (Strict Avalanche Criterion, ).

Подібні критерії відображають властивість непередбачуваності поведінки функції при однаковій модифікації (невідомих) аргументів.

Це означає, що при заміні (у наслідок помилки), скажимо, на, відповідні координати векторів значень функційіне співпадатимуть у половині випадків.

Або, наприклад, мінімальне відхилення від істинного значення аргументу призведе до максимально швидкого, як кажуть, лавинного розповсюдження помилок у рекурентній послідовності.