Визначення (критерій 2).
Функція називається кореляційно імунною порядку, якщо для будь-якої сукупності номерів змінних при довільних значеннях векторів виконується співвідношення
.
Ймовірності називаються кореляційними коефіціентами порядка функції .
З визначення випливає, що для аргумента , такого, що , ніяка підмножина з змінних не має особливостей, які дозволили би обмежити варіанти їхніх значень, виходячи з розподілу ймовірностей .
Можна довести, що функція є кореляційно імунною порядку тоді і тільки тоді, коли для її коефіціентів Уолша-Адамара виконується умова: : .
Також можна довести, що кореляційно імунна порядку функція від змінних, є кореляційно імунною довільного меншого порядку.
Таким чином, булевій функції відповідає деякий максимальний порядок її кореляційної імунності , який позначається через .
Раніше ми зауважили, що функції, які досягають максимального кореляційного імунітету степеня , є афінними.
Виявляється, якщо рівноймовірна і , то функція афінна.
Теорема 6.1 (Нерівність Зігенталера). Для довільної булевої функції від змінних виконується нерівність . Крім того, якщо - рівноймовірна і , то .
Для побудови булевих функцій, які задовільняють тим, чи іншим критеріям, існують відповідні методи.
Наприклад, доведено, що якщо функції , є кореляційно імунними порядку , то «скомбінована» з них функція від змінної також кореляційно імунна порядку .
Інший приклад. Якщо - максимально нелінійна функція від змінних, то функція виду від змінних задовільняє критерій і має високу нелінійність , що задовільняє нерівність: .
Треба зауважити, що не всі кореляційно імунні функції є рівноймовірними. Таким чином, є сенс звернутися до властивостей рівноймовірних кореляційно імунних функції.
Рівноймовірні, кореляційно імунні порядка функції називаються - стабільними.
Узагальненням - стабільних функцій є так звані стабільні відображення.
6.2 Стабільні булеві відображення
Визначення. Відображення , , називається - стабільним, якщо для довільних наборів , та довільних , відображення виду є рівноймовірним.
У позначенні основне навантаження несе параметр , оскільки він, подібно другому параметру для критерія , задає кількість фіксованих змінних у підфункціях координатних функцій і тим самим визначає розмірність їхніх аргументів: .
Параметри і показують, що відображає -вимірні вектори в -вимірні. Таким чином, при відображення є булевою функцією.
Трійка не може бути довільною. Дійсно, згідно із визначенням рівноймовірного булевого відображення, образ вектор-функции співпадає з і потужності прообразів елеменів з однакові. Оскільки потужність області визначення підфункції дорівнює , то кожний прообраз містить елементів, тобто, необхідно, щоб .
Стабільне відображення називається лінійним, якщо лінійні всі його функції-компоненти.
Теорема 6.2. Відображення , , , є -стабільним, тоді і тільки тоді, коли для довільного ненульового набора функція є -стабільною, тобто рівноймовірною, кореляційно імунною порядка функцією.
Для стабільних відображень існують підходи, щодо їх побудови зі стабільних відображень меншої розмірності. Крім того практичне значення має підхід, що дозволяє будувати стабільнї відображення з лінійних стабільних відображень, виходячи з наступного твердження.
Теорема 6.3. Нехай является -стабільним, а відображення, що здійснює перестановку простору .
Тоді відображення також -стабільне з нелінійністю .
Наведемо приклади -стабільних лінійних відображень.
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 |
На завершення, слід зауважити, що стабільні функції з максимальними значеннями нелінійності, які отримуються на основі поширених методів, як правило, мають змінні, за якими вони є лінійними.
Таким чином, криптографічно стійкі булеві функції мають задовільняти відповідним критеріям на основі розумного компромісу.