5.3 Основнї критерії розповсюдження помилок

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

5.3.1 Булева функція задовольняє строгий лавинний критерій, якщо- рівноймовірна функція для всіх допустимих.

складається з похідних , де.

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

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

Можна показати, що якщо функція задовільняє , то вона задовільняє, де.

5.3.3 В критерії , за визначенням, у підфункцій допускається модифікація видудовільного, але тільки одного з аргументів.

Модифікація декількох аргументів розглядається в так званому критерії розповсюдження степеня(Propagation Criterion).

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

складається зі всіх похідних ,.

У випадку, коли відомо, що рівноймовірна для конкретного вектора, говорять, щозадовольняє критерій розповсюдженнястепенявідносно вектора.

5.3.4 Загальний випадок відповідає формулюванню критерія розповсюдження степеня , порядку.

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

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

5.4 Практичні приклади

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

Один з них: . Похіднуми вже обчислили як приклад похідноїу Таб. 5.1. Кількість одиниць у векторі значень функціїдорівнює 12, а не 8, таким чином, одна з похідних не є рівноймовірною іне задовілняє.

Критерій . Нехай, тобто фіксуються 2 змінні.

Розглянемо підфункцію для,(табл. 5.2) і застосуємо до неї критерій(табл. 5.3).

Маємо випробувати вектори з вагою одиниця. Нехай ,.

Таблиця 5.3 Критерій для підфункції від двох змінних

			,	,
0	0	0	0 0	0 0
0	1	0	0 1	0 1
1	0	0	1 0	1 0
1	1	1	0 0	1 1

Похідні іє рівноймовірними, тому треба продовжити обчислення для інших підфункцій.

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

Критерій розповсюдження ,.

Для цього критерія довільна похідна має бути рівноймовірною.

Ми обчислили при,і знайшли, що вектор значень цієї функції містить 10 одиниць (табл 5.1), тобто,не задовільняє.

Критерій розповсюдження степеня, порядку.

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

Ми вже знаємо, що не задовільняє, тому існують похідні, які не є рівноймовірними, звідки випливає що серед множини похіднихне всі рівноймовірні, томуне задовільняє.

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

Визначення (критерій 1). Функція є кореляційно імунною порядка порядка, тоді і тільки тоді, коли для будь-якої сукупностіномерівзміннихі для будь-яких наборіввиконується рівність.

Визначення (критерій 2).

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

.

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

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

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

Необхідно обчислити для трьох варіантів, та чотирьох варіантів.

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

Таблиця 6.1 Корені рівняння

0	0	0	0	0	0	0
0	0	1	1
0	1	0	0	0	1	0
0	1	1	0	0	1	1
1	0	0	1
1	0	1	0	1	0	1
1	1	0	1
1	1	1	1

Далі фіксуємо перший варіант для позицій підаргумента: та підраховуемо скільки в цих позиціях зустрічається пар , потім - скількі пар , і так далі. Аналогічно працюємо з позиціями підаргументу та.

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

Таблиця 6.2 Обчислення кореляційних коефіціентів

	1	2	1
	2	1	1
	1	0	1			0
	0	1	1		0

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

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

13