Нелінійність булевої функції

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

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

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

Однією з важливих характеристик булевої функції є її нелінійність.

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

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

У цьому випадку , , .

Для вивчення нелінійності та інших властивостей булевих функцій велике значення має перетворення Уолша-Адамара. Це перетворення діє на булевих функціях.

При перетворенні Уолша-Адамара элементи 0 и 1 поля розглядаються як звичайні цілі числа. Результатом перетворення функції є цілочислена функція , , що пов'язана з усіма векторами значень виду . Очевидно, у кожному подібному векторі одиниці відповідають місцям неспівпадінь правої частини з правою частиною відповідної лінійної функції .

Іншими словами, якщо на цих місцях замінити біти у векторі значень на протилежні, то перетвориться на .

Значенням є різниця між кількістю нулів та одиниць у векторі : , де проходить всю множину аргументів.

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

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

Співставимо вектору значень булевої функції вектор цілочисленої функції , в якому , тобто нулі замінимо на , а одиниці – на . Функція часто позначається як exp .

Очевидно, вираз можна розгля-дати як скалярний добуток векторів і : .

Ця рівність може служити визначенням перетвореня Уолша-Адамара.

Приклад.

Функції , і . . .

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

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

Дійсно, позначимо через через і відповідно кількість нулів та кількість одиниць у векторі . Позначимо також .

З системи , , випливає, що , а . Крім того, очевидно, .

Оскільки , то .

Покажемо тепер, що відстань від функції до множини виражається у виді .

Нехай , тоді .

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

Очевидно, що , тому кількість нулів у векторі дорівнює , а кількість одиниць - . Таким чином, , а і .

Множини і співпадають. Із точністю до позначень, можна вважати, що для функції , тому для функції .

Тоді і .

Таким чином, .

Повертаючись до перетворення Уолша-Адамара та враховуючи, що , , , , отримаємо .

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

Тобто, , , .

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

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

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

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

Знайдемо тепер оцінку , виходячи зі значення .

Відмітимо, що

.

Тут кожна внутрішня сума перетворюється в нуль при .

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

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

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

.

У випадку, коли , приймає максимальне значення . При цьому, оскільки є цілим числом, - обов'язково парне.

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

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

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

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

, де і .

Доведення є вправою на розуміння позначень та визначення нелінійності.

Дійсно, максимум у лівій частині рівності вибирає максимальне за модулем значення серед коефіціентів Уолша-Адамара функції . Це значення визначає нелінійність функції за формулою .

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

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

Рівність правої і лівої частини вказує на те, що , тому, за визначенням, функція - максимально нелінійна.

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

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

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

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

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

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

Подібні властивості називаються інваріантними відносно афінної заміни змінних.

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

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

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

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

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

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

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

Як важливий факт відмітимо те, що бент-функції не є рівноймовірними.

Дійсно, , , , тому .

Якщо - рівноймовірна, то , що неможливо.

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

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

Теорема 6.4. (Критерій Ротхауза).Булева функція від змінних максимально нелінійна тоді і тільки тоді, коли коли її похідна за довільним напрямком є рівноймовірною.

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