Представлені алгоритми обчислення наступних криптографічних характеристик вектора булевих функцій: порядку кореляційної імунної, нелінійності, компонентної алгебри імунної і показника диференціальної рівномірності. компоненти векторної булевої функції перебираються в порядку, що задається кодом Грея. Наводяться результати експериментів для випадкових векторних булевих функцій, підстановок і двох спеціальних класів Kn і Sn, k оборотних векторних булевих функцій від n змінних, координати яких істотно залежать від усіх і заданого числа k < n змінних відповідно. Доведені деякі властивості диференціальної рівномірності для функцій з класів Kn і Sn, k.

Анотація наукової статті з математики, автор наукової роботи - Кисельова Наталя Максимівна, Ліпатова Катерина Сергіївна, Панкратова Ірина Анатоліївна, Трифонова Єлизавета Євгеніївна


Algorithms for computing cryptographic characteristics of vectorial Boolean functions

There are presented algorithms for calculating the cryptographic characteristics of vectorial Boolean functions, such as the order of correlation immunity, nonlinearity, component algebraic immunity, and differential uniformity order. In these algorithms, the components of a vectorial Boolean function are enumerated according to the Gray code. Experimental results are given for random vectorial Boolean functions, permutations, and two known classes Kn and Sn, k of invertible vectorial Boolean functions in n variables with coordinates essentially depending on all variables and on k variables, k < n, respectively. Some properties of differential uniformity are theoretically proved for functions in Kn and Sn, k, namely, the differential uniformity order? F equals 2n for any F? Sn, k, and the inequality 2n 4 (n 1)? ? F? 2n 4 holds for any F? Kn.


Область наук:

  • Математика

  • Рік видавництва: 2019


    Журнал: Прикладна дискретна математика


    Наукова стаття на тему 'АЛГОРИТМИ ОБЧИСЛЕННЯ КРИПТОГРАФІЧНИХ ХАРАКТЕРИСТИК векторні булевих функцій'

    Текст наукової роботи на тему «АЛГОРИТМИ ОБЧИСЛЕННЯ КРИПТОГРАФІЧНИХ ХАРАКТЕРИСТИК векторні булевих функцій»

    ?2019 Обчислювальні методи в дискретної математики №46

    ОБЧИСЛЮВАЛЬНІ МЕТОДИ В дискретної математики

    519.7

    АЛГОРИТМИ ОБЧИСЛЕННЯ КРИПТОГРАФІЧНИХ ХАРАКТЕРИСТИК векторні Булевой ФУНКЦІЙ1

    Н. М. Кисельова, Е. С. Ліпатова, І. А. Панкратова, Е. Е. Трифонова

    Національний дослідницький Томський державний університет, Томськ,

    Росія

    Представлені алгоритми обчислення наступних криптографічних характеристик вектора булевих функцій: порядку кореляційної імунної, нелінійності, компонентної алгебри імунної і показника диференціальної рівномірності. Компоненти векторної булевої функції перебираються в порядку, що задається кодом Грея. Наводяться результати експериментів для випадкових векторних булевих функцій, підстановок і двох спеціальних класів Kn і Sn, k оборотних векторних булевих функцій від n змінних, координати яких істотно залежать від усіх і заданого числа k < n змінних відповідно. Доведені деякі властивості диференціальної рівномірності для функцій з класів Kn і Sn, k.

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

    DOI 10.17223 / 20710410/46/7

    ALGORITHMS FOR COMPUTING CRYPTOGRAPHIC CHARACTERISTICS OF VECTORIAL BOOLEAN FUNCTIONS

    N. M. Kiseleva, E. S. Lipatova, I. A. Pankratova, E. E. Trifonova National Research Tomsk State University, Tomsk, Russia

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її., Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її., Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.,

    Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    There are presented algorithms for calculating the cryptographic characteristics of vectorial Boolean functions, such as the order of correlation immunity, nonlinearity, component algebraic immunity, and differential uniformity order. In these algorithms, the components of a vectorial Boolean function are enumerated according to the Gray code. Experimental results are given for random vectorial Boolean functions, permutations, and two known classes Kn and Sn, k of invertible vectorial Boolean functions in n variables with coordinates essentially depending on all variables and on k variables, k < n, respectively. Some properties of differential uniformity are theoretically

    1 Робота підтримана грантом РФФД, проект №17-01-00354.

    proved for functions in Kn and Sn, k, namely, the differential uniformity order op equals 2n for any F e Sn, k, and the inequality 2n - 4 (n - 1) ^ op ^ 2n - 4 holds for any F e Kn.

    Keywords: vectorial Boolean function, nonlinearity, correlation immunity, component algebraic immunity, differential uniformity.

    Вступ

    Криптосистеми, стійкість яких заснована на складності рішення систем нелінійних рівнянь над кінцевим полем, є імовірно стійкими до квантовим атакам [1]. До цього класу, зокрема, відносяться криптосистеми з функціональними ключами, побудовані на векторних булевих функціях [2-4]. Для аналізу стійкості таких криптосистем, крім розробки спеціальних атак, потрібно досліджувати відомі криптографічні характеристики використовуваних функцій. У даній роботі наведені алгоритми обчислення таких характеристик, як порядок кореляційної імунної, нелінійність, компонентна алгебраїчна імунітет і показник диференціальної рівномірності. Алгоритми досить «прямолінійні» і, швидше за все, не є кращими за складністю, проте їх реалізація дозволила досліджувати характеристики функцій з різних класів і сформулювати ряд тверджень про властивості функцій цих класів. У п. 3 доведено кілька тверджень про диференціальної рівномірності підстановок, координатні функції яких істотно залежать від заданого числа змінних.

    Наведемо необхідні визначення [5 - 7]. Нехай дана векторна булева функція F = (fi ... fm): Fn ^ Fm.

    Компонентою функції F називається булева функція vF = vf ф ... ф vmfm, де v = vi ... vm e Fm \ {0m}; 0m - нульовий вектор довжини m.

    Порядком кореляційної імунної cor (F), нелинейностью N (F) і компонентної алгебри імунної AIcomp (F) векторної функції F називаються мінімальні порядок кореляційної імунної, нелінійність і алгебраїчна імунітет її компонент відповідно:

    cor (F) = min cor (vF), N (F) = min N (vF), AIcomp (F) = min AI (vF)

    v € Fm \ {0m} v € Fm \ {0m} v € Fm \ {0m}

    (Визначення відповідних характеристик для булевої функції см. В [8, с. 277 і визначення 2.50] і [5]).

    Для функції F і векторів a e Fn, b e Fm позначимо

    5p (a, b) = | {x e Fn: F (x) ф F (x ф a) = b} |.

    Показником диференціальної рівномірності функції F називається

    5p = max 5p (a, b).

    a = 0n, b

    Значення cor (F), N (F) і AIcomp (F) характеризують стійкість криптосистеми з функцією F в якості блоку перетворення до корреляционному, лінійному і алгебраическому методам криптоаналізу відповідно, і вони повинні бути великими. Зауважимо, що для всіх підстановок F: Fn ^ Fn має місце cor (F) = 0, оскільки для врівноважених функцій F: Fn ^ Fm вірно нерівність m ^ n - cor (F) [5].

    Показник пов'язаний зі здатністю шифру протистояти диференціального криптоаналізу в випадках, коли функція Г використовується в якості блоку заміни в ВЕБ-подібному шифрі [7] або (в загальному випадку) в довільному итеративном блоковому шифрі з адитивним раундовим ключем [9] -чем він менше, тим краще.

    1. Алгоритми обчислення криптографічних характеристик

    Для обчислення характеристик СОГ (Г), N (Г) і А1сотр (Г) за визначенням потрібно перебрати всі компоненти vF функції Г, v Е Fm \ {0т}. Щоб мінімізувати час обчислення компонент, будемо перебирати вектори V відповідно до кодом Грея - в цьому випадку «сусідні» значення V розрізняються рівно в одному двійковому розряді, а значить, чергова компонента функції Г виходить з попередньої додатком однієї координатної функції (алгоритм 1).

    Алгоритм 1. Перебір компонент векторної булевої функції

    Вхід: функція F = (fi ... fm): Fn ^ F ™ 1: Створити булеву функцію f: Fn ^ F2, f: = const 0, і вектор v0 Е Fm, v0: = 0m. 2: Для i = 1, ..., 2m - 1:

    3: Vj: = i ф (i ^ 1) // перетворення двійкового коду в код Грея; ^ -Операція зсуву вправо; i розглядається і як ціле число, і як логічний вектор довжини m. 4: Покласти k рівним номеру (єдиною) одиниці в векторі vi-l ф Vj; 5: f: = f ф fk // чергова компонента. 6: Обробка f.

    Згідно [5], порядок кореляційної імунної СОГ (Г) функції Г: Fn ^ Fm дорівнює якщо і тільки якщо: 1) (і) = 0 для всіх наборів і Е Fn ваги від 1 до? включно і всіх компонент vF і 2) (і) = 0 для деякого набору і ваги? + 1 і деякої компоненти vF, де (і) = ^ (-1) Ур (х) ФІХ - коефіцієнт перетворення Уолша - Адамара функції vF. Таким чином, для обчислення СОГ (Г) потрібно знайти ненульовий вектор і мінімальної ваги, на якому перетворення Уолша - Адамара хоча б однієї компоненти приймає нульове значення. Іншими словами, нам цікаві такі значення і, що (і) = 0 для всіх компонент. Тому, перебираючи компоненти vF, будемо «накопичувати» в одному масиві диз'юнкцію коефіцієнтів (і), і Е Fn (інтерпретуючи цілі числа як булеві вектори) і тільки потім проаналізуємо отриманий вектор (алгоритм 2).

    Алгоритм 2. Обчислення СОГ (Г)

    Вхід: функція Г: Fn ^ Fm. 1: Створити масив цілих чисел Д розміру 2П, обнулити всі його елементи. 2: Перебираємо компоненти vF, як в алгоритмі 1. 3: Для кожної компоненти:

    4: т: =; Д: = Д V т (поелементно) // крок 6 алгоритму 1.

    5: Для всіх г = 1, ..., п:

    6: Для всіх векторів і Е Fn ваги г:

    7: якщо Ді = 0, то вихід, відповідь: г - 1.

    8: Вихід, відповідь: п.

    Оцінимо складність алгоритму 2:

    - всього компонент (2m - 1), перехід до наступної компоненті (додавання поточної з координатної функцією) - O (2n) операцій, обчислення перетворення Уолша - Адамара за схемою Гріна - O (2nn) [8], поелементно диз'юнкція векторів - O ( 2n) операцій; разом складність кроків 2-4 становить O (2n + mn) операцій;

    - на кроках 5-7 в гіршому випадку (для функції-константи) доведеться перебрати 2n - 1 векторів.

    Таким чином, складність алгоритму 2 дорівнює O (2n + mn).

    Нелінійність N (F) функції F: F ^ ^ Fm теж можна обчислити з використанням перетворення Уолша - Адамара за такою формулою [5]:

    N (F) = 2n-1 - 1 max Wvf (u). (1)

    2 ueFn, veFm ​​\ {om}

    Отримуємо алгоритм 3 обчислення нелінійності.

    Алгоритм 3. Обчислення N (F)

    Вхід: функція F: ^ Fm 1: c: = 0.

    2: Перебираємо компоненти vF, як в алгоритмі 1. 3: Для кожної компоненти:

    4: w: = Wvf; d: = max | wj; якщо d > c, то c: = d. i = 0, ..., 2n-1

    Вихід: N (F) = 2n-1 - c / 2 (по формулі (1)).

    Складність алгоритму 3 дорівнює O (2ra + mn).

    Для опису алгоритму обчислення компонентної алгебри імунної Alcomp (F) введемо такі поняття [5]. Анігілятором підмножини A З F ^ називається будь-яка булева функція від n змінних, що не рівна тотожно 0 і приймаюча значення 0 на всіх наборах з A. алгебраїчних імунної безлічі A називається мінімальна з алгебраїчних ступенів Аннігілятор, що не рівних тотожне 0; позначається AI (A). Для булевої функції f від n змінних позначимо MJ = {x е F ^: f (x) = а}, а е {0,1}. тоді

    AIcomp (F) = min AI (vF) = min min (AI (M ° p), AI (MViF)). (2)

    Відповідно до (2) отримуємо алгоритм 4 обчислення компонентної алгебри імунної.

    Алгебраїчну імунітет безлічі A = {ai, ...,} З F ^ будемо шукати методом невизначених коефіцієнтів [10] (алгоритм 5). Для того щоб визначити, чи існує анігілятор безлічі A ступеня не вище d, побудуємо матрицю B (A, d), стовпці якої відповідають елементам множини A, рядки - всіляким мо-

    d fn

    номам m1, ..., mt від змінних x1, ..., xn ступенів від 0 до d, де t = ^; на пере-

    i = 0 V%)

    перетині рядка i та стовпця j запишемо значення mi (aj-). Якщо rangB (A, d) < t, то існує нетривіальна нульова лінійна комбінація рядків матриці: mil ф .. .®mis = 0k; тоді функція g (x) = mi1 (x) ф ... ф mis (x) - анігілятор безлічі A.

    Алгоритм 4. Обчислення А1сотр (Г)

    Вхід: функція Г: Fn ^ Fm. 1: з: = | ~ п / 2] // верхня межа А1сотр (Г) [10]. 2: Перебираємо компоненти vF, як в алгоритмі 1. 3: Для кожної компоненти:

    4: т0: = А1 (МУР); т1: = А1 (Му1р) // за алгоритмом 5; 5: з: = шт (с, т0, т1). Вихід: А1сотр (Г) = з.

    Алгоритм 5. Обчислення алгебри імунної безлічі

    Вхід: безліч A З Fn, | A | = K. 1: Якщо A = 0, то вихід, відповідь: AI (A) = 0. 2: Побудувати матрицю B = B (A, 1); d: = 1; t: = n +1. 3: Якщо rangB < t, то вихід, відповідь: AI (A) = d.

    4: d: = d +1; t: = t +; якщо t > k, то вихід, відповідь: AI (A) = d.

    5: Додати до матриці B рядки, відповідні Мономах ступеня d, перейти до п. 3.

    Складність алгоритму 5 при обчисленні рангу методом Гаусса становить 0 (к3 ^). Відзначимо, що при використанні цього алгоритму для обчислення А1сотр (Г) можна ввести додаткове обмеження на кроці 4 після збільшення «якщо d ^ [п / 2], то вихід, відповідь: А1 (А) = d». Складність алгоритму 4 дорівнює 0 (2т + 3 "п).

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

    Алгоритм 6. Обчислення показника Sf

    Вхід: функція F: Fn ^ Fm 1: Створити допоміжний масив цілих чисел DDT розміру 2m, обнулити всі його

    елементи. 2: S: = 0.

    3: Для всіх a Е F ^ \ {0n}: 4: Для всіх x Е F ^:

    b: = F (x) 0 F (x 0 a); DDT [b]: = DDT [b] + 1; 5: d: = max DDT [b]; якщо d > S, то S: = d.

    b&V?

    6: Обнулити масив DDT. Вихід: SF = S.

    Складність алгоритму 6 дорівнює 0 (2 га + тах (га'т)).

    2. Результати експериментів

    Всі алгоритми реалізовані на мові ляпас-Т [11] і досліджені в комп'ютерному експерименті на випадкових функціях, підстановках і двох спеціальних класах оборотних функцій, координати яких залежать від заданого числа змінних. Визначимо ці класи [12, 13].

    Для п € N п ^ 3, розглянемо клас функцій Кп, функції Р = (/ ... / п): ЩП ^ ЩП в якому виходять з тотожною підстановки Про на за допомогою п наступних незалежних транспозиція: вибираємо п непересічних множин Мг = { х (г), у (г)}, де вектори {х (г), у (г)} сусідні по г-й координаті, і вважаємо р (х (г)) = О (у (г)),

    п

    Р (у (г)) = О (х (г)), г = 1, ..., п; Р (х) = О (х) для всіх х Е У Мг. За побудовою, для

    будь-якого а = а1 ... ап € ЩП має місце

    г = 1

    ". . а * ф 1, якщо а € М ^

    Ма) = 4 (3)

    1аг інакше.

    Доведено [12], що всі координати функцій з Кп істотно залежать від усіх п змінних і п = 0 для всіх п ^ 3.

    Для до, п € N 3 ^ до ^ п, побудуємо функцію Р = (/ 1 ... / п): ЩП ^ ЩП так. Нехай Н = (до ... кк) -деяка функція з Кк. Покладемо / г (х1, ..., хп) = кг (х ^ ..., хк), г = 1, ..., к (змінні хк + 1, ..., хп у функцій / 1 ,. .., / к фіктивні), і / г = хГ ф ф ^ г (х1, ..., хГ-1) для г = до + 1, ..., п, де ^ до + 1, ... , - довільні функції, істотно залежать рівно від (до - 1) зі своїх змінних. Позначимо клас функцій, побудованих таким чином, через? П, к. В [13, твердження 3] доведено, що функції з? П, до є підстановками на ЩП; всі їх координати істотно залежать рівно від до змінних. Необхідність обмежувати кількість істотних змінних у координат векторних булевих функцій може виникнути, зокрема, при побудові криптосистем, де такі функції є ключами [2-4], а значить, потрібно вміти їх ефективно задавати і швидко обчислювати.

    Експерименти на функціях Р: ЩП ^ дали наступні результати.

    1) Порядок кореляційної імунної випадкової функції, як правило, дорівнює 0, рідко - 1.

    2) Для нелінійності:

    - при фіксованому п з ростом т значення N (Р) убуває; наприклад, при п = 5 середнє значення ^ р (Р) = 6,6 при t = 5 і ^ р (Р) ^ 2 при т ^ 18;

    - якщо Р: ЩП ^ ЩП - підстановка, то її нелінійність росте з ростом п, наближаючись до теоретичної верхній межі Nmax = 2п-1 - 2п / 2-1: від 47% при п = 5 до 93% при п = 12;

    - якщо Р € Кп, то N (Р) = 2 (доведено в [14]); звідси випливає, що N (Р) ^ 2п-к + 1 для Р €? п, к, оскільки перші до координат такої функції Р виходять додаванням (п - к) фіктивних змінних, кожна з яких збільшує нелінійність функції в два рази. В експериментах для функцій Р €? П, до завжди виконується N (Р) = 2п-к + 1, крім випадків до = 3 (завжди отримуємо 0) і до = 4 (отримуємо 0 або 2п-3).

    3) Для алгебраїчної імунної:

    - для випадкових підстановок Р майже завжди А1сотр (Р) = п / 2 (максимально можливе) при парному п і А1сотр (Р) = (п - 1) / 2 (на 1 менше максимально можливого) при непарному п; це узгоджується з результатами [15] для врівноважених булевих функцій /: для парного п ймовірність того, що мінімальна серед ступенів Аннігілятор безлічі М ^ дорівнює п / 2, близька до 1; для непарного п ця ступінь з більшою ймовірністю (0,711 проти 0,289) дорівнює (п - 1) / 2, ніж (п + 1) / 2 (максимально можливої);

    - якщо Г € Кп, то А1сотр (Г) = 2 (доведено в [14]); звідси випливає, що А1сотр (Г) ^ 2 для Г € ЗПК, оскільки додавання фіктивних змінних не впливає на алгебраїчну імунітет функції. В експериментах отримано: А1сотр (Г) = 1 для функцій Г € завжди при к = 3 і іноді при до ^ 4; Останнім - чим більше п і до, тим рідше (у більшості випадків

    А1сотр (Г) = 2).

    4) Для показника диференціальної рівномірності:

    - при п ^ т, як правило, 5р = 2п;

    - при фіксованому п з ростом т значення убуває;

    - якщо Г: Fn ^ Fn - підстановка, то її диференціальна рівномірність в середньому багато менше, ніж диференціальна рівномірність випадкової такої функції (без умови оборотності).

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

    3. Властивість диференціальної рівномірності функцій з класів Кп і Бп>до Для] € {1, ..., п} позначимо ej логічний вектор довжини п з єдиною 1 в] -й координаті.

    Твердження 1. Нехай Г € Кп, а = е ^ ф е »2 ф ... ф,] € {? 1, ...,% до}. тоді

    Е 5К (а, Ь) = < , до > , b = (bl ... bn) eFn: bj = 0 [0, к = 1.

    Доведення. запишемо:

    Е (а, Ь) = Е | {х € Fn: Г (х) ф Г (х ф а) = Ь} | =

    М ^ ь-М ^: ^ = 0 М ^ ь .. ^^ ??: ^ = 0

    = | {Х € Fn: / j (х) = / (х ф а)} |.

    Зауважимо, що х і хфа розрізняються в] -й координаті. Тоді з формули (3) випливає, що / j (х) = / j (хфа), якщо і тільки якщо рівно один з векторів х і хфа належить Mj, де Mj = {с, з ф ej} для деякого з € Якщо к = 1 і, отже, а = ej, то х і х ф а одночасно або належать, або не належать Mj. при до > 1 умова виконується для х € X = {с, з ф ej, з ф а, з ф ej ф а}; з огляду на те, що вага вектора а більше 1, всі вектори в X різні. |

    Твердження 2. Нехай Г € Кп, а = eil ф ei2 ф ... ф eifc, € {% 1, ...,}. тоді

    Е (а, Ь) = 4.

    М ^ ь-М ^ Ь, - = 1

    Доведення. Аналогічно доведенню твердження 1 отримаємо Е (а, Ь) = | {х € Fn: / (х) = / (х ф а)} |.

    b = (bl ... bn) eFn: bj = 1

    Оскільки] -е координати х і х ф а збігаються, з формули (3) випливає, що / (х) = = Л '(х ф а), якщо і тільки якщо рівно один з векторів х і х ф а належить Mj = = {с, з ф ej}. Ця умова виконується для х € X = {с, з ф ej, з ф а, з ф ej ф а}; з огляду на те, що а = ej, всі вектори в X різні. |

    З тверджень 1 і 2 випливає, що 5 ^ (а, Ь) ^ 4 для всіх Р € Кп і а = Ь; зважаючи на парності значень 5, р (а, Ь) це означає, що 5, р (а, Ь) € {0, 2, 4}.

    Затвердження 3. Нехай Р € Кп, а = е ^ 1 фе ^ 2 ф ... фе ^, Ь = (61 ... Іоп) € ^ і Ь, = 0 для всіх € {г1, ...,} . Тоді (а, Ь) = 0.

    Доведення. Позначимо X = {х € ^: V] € {г1, ...,} (/ (ж) = / (х ф а))}. Тоді для а і Ь в умови затвердження 5 ^ (а, Ь) = | Х | і для х € X повинна виконуватися умова: рівно один з векторів х і х ф а належить М ^,] =? 1, ...,. Оскільки безлічі М ^ не перетинаються, ця умова не може виконуватися при до > 2; випадок к = 1 розглянуто в утвердженні 1. Залишилося розглянути випадок к = 2.

    Нехай а = е ^ ф е ^ 2, = {с, з ф е ^}, М ^ 2 = ^ ф е ^ 2} і без обмеження спільності х € Мг1, х ф а € мг2. Якщо х = с, то х ф а = х ф е ^ ф е ^ 2; при х ф а = d отримуємо dфе ^ 2 = сфе ^ € Мг1, а якщо хфа = dфе ^ 2, то d = сфе ^ € М ^ 1; обидва висновки суперечать тому, що Мг1 П мг2 = 0. Випадок х = з ф е ^ 1 розглядається аналогічно. |

    Затвердження 4. Нехай Р € Кп, а € Е ^. Тоді 5, р (а, а) ^ 2п - 4п, якщо вага а більше 1, і (а, а) ^ 2п - 4 (п - 1) інакше.

    Доведення. З того, що Е (а, Ь) = 2п, слід

    ^ (А, а) = 2п - Е 5 ^ (а, Ь). (4)

    Нехай а = е ^ 1 ф е ^ 2 ф ... ф е ^. запишемо:

    п

    Е ^ (а, Ь) ^ Е Е ^ (а, Ь) = Е Е 5 ^ (а, Ь) + Е Е 5 ^ (а, Ь).

    Ь = а .7 = 1 а ^ еш ^ Ь, - = «, | ^ {п} ЬеК?: ^ = 0 ^ {? Ь ... ^} ЬеК?: ^ = 1

    у у у у

    ^ 2

    З твердження 1 випливає, що

    ] 4к, якщо до > 1,? 1 = <

    0, якщо к = 1,

    з утвердження 2 отримуємо 52 = 4 (п - к). тоді

    / 4п, якщо до > 1,

    Е ^ (а, Ь) (5)

    ь = а 14 (п - 1), якщо к = 1.

    З (4) і (5) випливає справедливість твердження 4. |

    Затвердження 5. Для будь-якої функції Р € Кп має місце

    2п - 4 (п - 1) ^ 5 ^ ^ 2п - 4.

    Доведення. Нижня межа слід безпосередньо з утвердження 4. З тверджень 1 і 2 отримуємо, що Е 5 ^ (а, Ь) ^ 4 для будь-якого ненульового а € ЕП, а

    Ь = а

    значить, 5 ^ (а, а) ^ 2п - 4. Тоді з того, що 5 ^ (а, Ь) ^ 4 для будь-яких а = Ь і нерівності 4 ^ 2п - 4, вірного при всіх п ^ 3, слід 5 ^ ^ 2п - 4. |

    Затвердження 6. Нехай С = (Д1 ... дп) €? П, до і до < п. Тоді 5с = 2п. Доведення. За побудовою, змінна хп є лінійної для функції дп і фіктивної для інших координат. Тоді С (х) ф С (х ф єп) = єп для всіх х € Еп, тобто 5с (єп, єп) = 2п, отже, 5с = 2п. |

    висновок

    Дослідження показали, що функції з класів Kn і Sn, k є криптографически слабкими: їх нелінійність та компонентна алгебраїчна імунітет малі, а показник диференціальної рівномірності близький (або дорівнює - для класу Sn, k) до максимального (т. Е. Гіршого) значенням 2n . До переваг таких функцій можна віднести можливість управляти кількістю істотних змінних у їх координат; для функцій класу Kn додатково - відсутність лінійних і фіктивних змінних у компонент, що не рівних координатами, і високий ступінь (n - 1) -максимально можлива для підстановок. Напрямки подальших досліджень:

    1) вивчення застосовності атак, які експлуатують зазначені слабкості функцій, до криптосистемам [2-4], як наслідок - оцінка стійкості цих криптосистем;

    2) вивчення композицій функцій з класів Kn і Sn, k між собою і з іншими функціями з метою нівелювання їхніх недоліків при збереженні позитивних властивостей;

    3) розробка нових алгоритмів генерації оборотних векторних булевих функцій з «хорошими» криптографічними характеристиками.

    Автори дякують Г. П. Агібалова за увагу до роботи і цінні зауваження.

    ЛІТЕРАТУРА

    1. Ding J. and Yang B. Y. Multivariate public key cryptography // Post-Quantum Cryptography / eds. D. J. Bernstein, J. Buchmann, and E. Dahmen. Berlin; Heidelberg: Springer, 2009. P. 193-241.

    2. Agibalov G.P. Substitution block ciphers with functional keys // Прикладна дискретна математика. 2017. №38. С. 57-65.

    3. Agibalov G. P. and Pankratova I. A. Asymmetric cryptosystems on Boolean functions // Прикладна дискретна математика. 2018. №40. С. 23-33.

    4. Agibalov G. P. ElGamal cryptosystems on Boolean functions // Прикладна дискретна математика. 2018. №42. С. 57-65.

    5. Carlet C. Vectorial Boolean Functions for Cryptography. Cambridge: Cambridge University Press, 2010. 93 p.

    6. Canteaut A. Lecture Notes on Cryptographic Boolean Functions. Paris: Inria, 2016. 48 p.

    7. Nyberg K. Differentially uniform mappings for cryptography // LNCS. 1994. V. 765. P. 55-64.

    8. Логачов О. А., Сальников А. А., Ященко В. В. Булеві функції в теорії кодування та криптології. М .: МЦНМО, 2004. 472 с.

    9. Агібалов Г. П. Елементи теорії диференціального криптоаналізу ітеративних блокових шифрів з адитивним раундовим ключем // Прикладна дискретна математика. 2008. №1 (1). С. 34-42.

    10. Meier W., Pasalic E., and Carlet C. Algebraic attacks and decomposition of Boolean functions // LNCS. 2004. V. 3027. P. 474-491.

    11. Агібалов Г. П., Липський В. Б., Панкратова І. А. Про криптографическом розширенні і його реалізації для російської мови програмування // Прикладна дискретна математика. 2013. №3 (21). С. 93-104.

    12. Pankratova I. A. Construction of invertible vectorial Boolean functions with coordinates depending on given number of variables // Матеріали Міжнар. науч. конгресу з інформатики: Інформаційні системи і технології. Республіка Білорусь, Мінськ, 24-27 жовт. 2016. Мінськ: БДУ, 2016. С. 519-521.

    13. Панкратова І. А. Про оборотності векторних булевих функцій // Прикладна дискретна математика. Додаток. 2015. №8. С. 35-37.

    14. Панкратова І. А. Властивості компонент деяких класів векторних булевих функцій // Прикладна дискретна математика. 2019. №44. С. 5-11.

    15. Canteaut A. Open problems related to algebraic attacks on stream ciphers // Proc. WCC'2005, Bergen, Norway, March 14-18, 2005. P. 120-134.

    REFERENCES

    1. Ding J. and Yang B. Y. Multivariate public key cryptography. Post-Quantum Cryptography (eds. D.J.Bernstein, J. Buchmann, and E. Dahmen). Berlin; Heidelberg, Springer, 2009 pp.193-241.

    2. Agibalov G. P. Substitution block ciphers with functional keys. Prikladnaya Diskretnaya Matematika 2017, no. 38, pp. 57-65.

    3. Agibalov G. P. and Pankratova I. A. Asymmetric cryptosystems on Boolean functions. Prikladnaya Diskretnaya Matematika, 2018, no. 40, pp. 23-33.

    4. Agibalov G. P. ElGamal cryptosystems on Boolean functions. Prikladnaya Diskretnaya Matematika, 2018, no. 42, pp. 57-65.

    5. Carlet C. Vectorial Boolean Functions for Cryptography. Cambridge: Cambridge University Press, 2010. 93 p.

    6. Canteaut A. Lecture Notes on Cryptographic Boolean Functions. Paris, Inria, 2016. 48 p.

    7. Nyberg K. Differentially uniform mappings for cryptography. LNCS, 1994, vol. 765, pp. 55-64.

    8. Logachev O. A., Sal'nikov A. A., and Yashchenko V. V. Bulevy funktsii v teorii kodirovaniya i kriptologii [Boolean Functions in Coding Theory and Cryptology]. Moscow, MCCME Publ., 2004, 472 p. (In Russian)

    9. Agibalov G. P. Elementy teorii differentsial'nogo kriptoanaliza iterativnykh blochnykh shifrov s additivnym raundovym klyuchom [Some theoretical aspects of differential cryptanalysis of the iterated block ciphers with additive round key]. Prikladnaya Diskretnaya Matematika, 2008, no. 1 (1), pp. 34-42. (In Russian)

    10. Meier W., Pasalic E., and Carlet C. Algebraic attacks and decomposition of Boolean functions. LNCS, 2004, vol.3027, pp. 474-491.

    11. Agibalov G. P., LipskiyV.B., And Pankratova I. A. O kriptograficheskom rasshirenii i ego realizatsii dlya russkogo yazyka programmirovaniya [Cryptographic extension and its implementation for Russian programming language]. Prikladnaya Diskretnaya Matematika, 2013, no. 3 (21), pp. 93-104. (In Russian)

    12. Pankratova I. A. Construction of invertible vectorial Boolean functions with coordinates depending on given number of variables. Proc. CSIST'16, Minsk, BSU Publ., 2016, pp.519-521.

    13. Pankratova I. A. Ob obratimosti vektornykh bulevykh funktsiy [On the invertibility of vector Boolean functions]. Prikladnaya Diskretnaya Matematika. Prilozhenie, 2015-го, no. 8, pp. 35-37. (In Russian)

    14. Pankratova I. A. Svoystva komponent nekotorykh klassov vektornykh bulevykh funktsiy [Properties of components for some classes of vectorial Boolean functions]. Prikladnaya Diskretnaya Matematika, 2019, no. 44, pp. 5-11. (In Russian)

    15. Canteaut A. Open problems related to algebraic attacks on stream ciphers. Proc. WCC'2005, Bergen, Norway, March 14-18, 2005, pp. 120-134.


    Ключові слова: ВЕКТОРНА булевих функцій /кореляційний імунної /НЕЛІНІЙНИЙ ВЕКТОРНОЇ булевих функцій /Компонентний алгебраїчних імунної /ПОКАЗНИК ДИФЕРЕНЦІАЛЬНОЇ рівномірно /VECTORIAL BOOLEAN FUNCTION /NONLINEARITY /CORRELATION IMMUNITY /COMPONENT ALGEBRAIC IMMUNITY /DIFFERENTIAL UNIFORMITY

    Завантажити оригінал статті:

    Завантажити