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

Date: 2015-10-07; view: 851.

ЛЕКЦІЯ 3 БУЛЕВІ ФУНКЦІЇ ТА ВІДОБРАЖЕННЯ

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

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

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

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

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

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

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

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

Приклад: .

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

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

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

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

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

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

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

							№ блока	:

; , .

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

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

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

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

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