Об обратимости векторных булевых функций

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Теорема 1. Булева бент-функция f от чётного числа переменных n является самодуальной (анти-самодуальной) тогда и только тогда, когда при каждом фиксированном y G Fn для булевой функции Fy (x) = f (x) ф f (y) ф x • y справедливо wt (Fy) = 2n-1 — 2n/2−1 (соответственно 2n-1 + 2n/2−1).
ЛИТЕРАТУРА
1. Carlet C., Danielson L. E., Parker M. G., Sole P. Self dual bent functions // Int. J. Inform. Coding Theory. 2010. No. 1. P. 384−399.
2. Hou X. Classification of self dual quadratic bent functions // Des. Codes Cryptogr. 2012. V. 63. Iss.2. P. 183−198.
УДК 519.7 DOI 10. 17 223/2226308X/8/14
ОБ ОБРАТИМОСТИ ВЕКТОРНЫХ БУЛЕВЫХ ФУНКЦИЙ
И. А. Панкратова
Рассматривается класс Fn, m, k обратимых векторных булевых функций из Fn в F^, координатные функции которых существенно зависят от заданного числа k переменных. Доказано: 1) таких функций не существует при любом n = m и k = 2- 2) функции класса Fn, n, n-1 могут (не могут) быть построены из аффинных координатных функций при чётном (нечётном) n- 3) если Fn, m, k = 0, то и
Fn+1 = 0.
Ключевые слова: векторная булева функция, обратимые функции.
Задача построения обратимых векторных булевых функций возникает при создании многих криптосистем- в частности, такие функции используются в многораундо-вых симметричных блочных шифрах класса SIBCipher [1]. Для того чтобы значения функции можно было эффективно вычислять, часто вводится ограничение на количество существенных переменных у каждой координатной функции векторной функции.
Для n, m, k G Z обозначим через Fn, m, k класс функций F: Fn ^ Fm, где F = = (f1… fm), таких, что координатные функции fi: Fn ^ F2, i = 1,…, m, существенно зависят ровно от k переменных и функция F — инъекция (т.е. обратима).
В случае n = m (практически важном для построения многораундовых шифров) будем обозначать Fn, k = Fn, n, k.
Непосредственно проверяются следующие свойства:
1) если Fn, m, k = 0, то m ^ n-
2) если F G Tn, k, то F есть подстановка на Fn и все её координатные функции уравновешены-
3) если F = (f … fm) G Fn, m, k, то и F'- = (f … fi… fm) G Fn, m, k, i G {1,…, m}-
4) если Fn, m, k = 0, то Fn, t, k = 0 для любого t & gt- m-
5) если Fk, k = 0, то Fks, k = 0 для любого s & gt- 1.
Последнее свойство используется при построении шифров SIBCiphers семейства Люцифер [1]: ks переменных разбиваются на блоки по k переменных в каждом и «большая» раундовая функция набирается из s «маленьких» функций — подстановок на Fk.
Пример 1. Функция F: F^ ^ F2 с вектором значений (0 6 7 2 4 3 1 5) принадлежит множеству F3,3- её координатные функции f1 = x1 ф x2 ф x3, f2 = x1x2 ф
Ф x2x3 ф x2 ф x3, f3 = x1x3 ф x2x3 ф x2.
36
Прикладная дискретная математика. Приложение
Утверждение 1. = 0 для любого п ^ 2.
Доказательство. Предположим, ^ ега, 2. Тогда по свойству 2 все её координатные функции уравновешены, т. е. имеют вид хг фх^- фс для некоторых 1 ^ г & lt- ] ^ п, с е F2. Но в этом случае ^(х) = ^(х) для любого х е Fn, что невозможно для инъек-тивной функции. ¦
Заметим, что при т & gt- п уравновешенность координатных функций уже не обязательна и класс ^& quot-га, т,2 может быть не пуст.
Пример 2. Функция: F2 ^ F2 с вектором значений (0 5 4 2) принадлежит классу ^& quot-2,з, 2- её координатные функции / = XI ф х2, /2 = Х1Х2, /з = Х1Х2 ф х2.
Утверждение 2.
1) Если п чётное, то некоторая ^ ега, га-1 может быть построена из аффинных координатных функций.
2) Если п нечётное, то никакая ^ ега, га-1 не может быть построена из аффинных координатных функций.
Доказательство. Пусть F (хь…, xn) = (/… /n), /
0х, — Ф Сг, С е F2,
г = 1,…, п- а = (а1… ап) е Fn — произвольное значение. Ввиду свойства 3 без ограничения общности можно полагать, что все с равны нулю. Составим уравнение ^(х) = а, или в матричном виде Ах = а, где х и, а — вектор-столбцы, А — (п х п)-матрица:
A
1 0 1. .1 1
1 1 0. .1 1
1 1 1. .0 1
1 1 1. .1 0
Легко убедиться, что det A = (n — 1) mod 2 над полем F2, поэтому уравнение F (x) = a имеет решения для всех, а (что равносильно условию F G Fn, n-i), если и только если n чётно.
Для завершения доказательства п. 2 утверждения осталось заметить, что перестановка координатных функций не влияет на принадлежность функции F классу Fn, n- i- других способов выбора n различных аффинных функций, существенно зависящих от (n — 1) переменных каждая и от всех n переменных в совокупности (что, очевидно, необходимо для принадлежности функции F классу Fi), нет. в
Следствие 1. Fn, n-i = 0 для любого чётного n.
Утверждение 3. Если F")m-fc = 0, то Fra+i-m+i)fc = 0.
Доказательство. Пусть F (xi,…, xn) = (/i… /m) G Fra-m-k. Построим функцию G: Fn+i ^ Fm+i так: G (xi,…, x", xra+i) = (/i… /m g), где g (xi,…, xn, xn+i) = xra+i ф ф h (xi,…, xn), h — любая функция, существенно зависящая от (k — 1) переменных. Тогда G (ai,…, an, 0) = G (ai,…, an, 1) для любого ai… an G F^ ввиду линейности функции g по переменной xn+i- G (ai,…, an, c) = G (bi,…, bn, c) для любых ai… an = = bi… bn, c G F2 ввиду обратимости функции F. ¦
Из утверждения 3, свойства 4 и примеров 1 и 2 следует, что Fra т ^ п ^ 3 и Fra, m,2 = 0 для всех т & gt- п ^ 2.
, з = 0 для всех
ЛИТЕРАТУРА
1. Агибалов Г. П. SIBCiphers — симметричные итеративные блочные шифры из булевых функций с ключевыми аргументами // Прикладная дискретная математика. Приложение. 2014. № 7. С. 43−48.
УДК 519.7 DOI 10. 17 223/2226308X/8/15
ОБ АЛГЕБРАИЧЕСКОЙ ИММУННОСТИ ВЕКТОРНЫХ БУЛЕВЫХ ФУНКЦИЙ1
Д. П. Покрасенко
Исследуется компонентная алгебраическая иммунность векторных булевых функций. Доказана теорема о соответствии между максимальной компонентной алгебраической иммунностью и сбалансированностью функции. Получена связь между максимальной компонентной алгебраической иммунностью и матрицами специального вида. При малом числе переменных построены функции, имеющие максимальную компонентную алгебраическую иммунность.
Ключевые слова: векторная булева функция, компонентная алгебраическая иммунность.
В 2003 г. N. Courtois и W. Meier предложили алгебраический метод криптоанализа шифров [1]. В случае поточных шифров этот метод использует следующие слабости фильтрующей функции: наличие у неё аннигиляторов низкой степени и множителей, уменьшающих степень функции. В настоящее время данный вид криптоанализа является одним из наиболее перспективных и развивающихся- соответственно возникает вопрос о поиске функций, способных ему противостоять.
В 2004 г. W. Meier, E. Pasalic и C. Carlet в работе [2] ввели понятие алгебраической иммунности для булевых функций. Алгебраической иммунностью AI (/) булевой функции /: Fn ^ F2 называется такое минимальное число d, что существует булева функций g степени d, не тождественно равная нулю, для которой /g = 0 или (/ ф 1) g = 0. Для любой булевой функции выполняется Л1(/) ^ [n/2] и существуют функции, имеющие Л1(/) = [n/2]. Высокая алгебраическая иммунность позволяет противостоять алгебраическим атакам.
Понятие алгебраической иммунности различными способами было обобщено на векторный случай. Так, в работе [3] F. Armknecht и M. Krause, а также G. Ars и J. -C. Faugere в [4] рассмотрели алгебраическую иммунность S-блоков и ввели понятия базовой AI (F) и графической AIgr (F) алгебраической иммунности векторных булевых функций. При этом базовая алгебраическая иммунность больше 1 только при малых значениях m, поэтому данный параметр анализируется у S-блоков, которые используются в поточных шифрах. Графическая алгебраическая иммунность используется для изучения сопротивляемости алгебраическим атакам блочных шифров.
Следующее обобщение является одним из наиболее естественных с криптографической точки зрения. Компонентной алгебраической иммунностью AIcomp (F) векторной булевой функции F: Fn ^ F? называется минимальная алгебраическая иммунность компонентных функций b ¦ F (b G Fm, b = 0), т. е. AIcomp (F) = min{AI (b ¦ F): b G F?, b = 0}, где b ¦ F = bi/i ф … ф bm/m. Данное определение является наиболее универсальным, наличие высокой компонентной алгебраической иммунности S-блоков
1 Работа поддержана грантом РФФИ, проект № 15−31−20 635.

ПоказатьСвернуть
Заполнить форму текущей работой