2014Лекція 4 булеві функції та відображення

4.1 Визначення та основні властивості булевих функцій

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

Під булевим відображенням будемо розуміти відображення () скінченномірних векторних просторів над полем.

Булевою функцією називається булеве відображення виду .

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

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

Представлення функції у вигляді т.зв. полінома Жегалкіна

називається алгебраїчною нормальною формою (АНФ). Степінь полінома Жегалкіна називається степенем нелінійності функції і позначається.

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

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

Приклад: .

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

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

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

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

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

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

Відстанню Хемінга від булевої функції до заданої множини функційназивається значення.

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

						№ блока	:
0	0	0	1	0	1	1	0	0
0	0	1	1	1	0	1	0	1
0	1	0	0	0	0	2	0	0
0	1	1	1	0	1	2	0	1
1	0	0	0	1	1	1	1	0
1	0	1	1	0	1	1	1	1
1	1	0	0	1	1	2	1	0
1	1	1	1	1	0	2	1	1

; ,.

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

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

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

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

Доведення: ,.

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