Correlation-immune functions with optimal algebraic immunity.pdf Булевы функции являются основными компонентами симметричных шифров, их криптографические свойства обеспечивают стойкость шифра к различным видам криптоанализа. Например, в работе [1] рассмотрены связи корреляционной иммунности с другими свойствами булевых функций. В данной работе основным рассматриваемым свойством является алгебраическая иммунность, обеспечивающая стойкость шифра к алгебраическому криптоанализу, введённому Н. Куртуа в 2003 г. [2]. Корреляционная иммунность используется в качестве вспомогательного свойства для сокращения числа рассматриваемых функций и поиска закономерностей и интересных структур, так как накладывает ограничения на расположение носителя булевой функции в булевом кубе. Так как полный перебор множества всех булевых функций затруднён, наибольший интерес представляют подходы, при которых булевы функции с нужными свойствами находятся с помощью средств машинного обучения, таких, как генетические алгоритмы [3], или строятся, как, например, в [4]. В данной работе изучается способ построения булевых функций от большего числа переменных на основе функций от меньшего числа переменных с сохранением криптографических свойств исходных функций. Используется геометрическое представление булевой функции: носитель булевой функции рассматривается как подможество вершин булева куба соответствующей размерности. Любую булеву функцию можно единственным образом записать в алгебраической нормальной форме (АНФ, полином Жегалкина): ф a0, n ф ф ai1,...,ik xi1 k=1 i1,...,ik где при каждом k все индексы i1, . . . , ik различны и параметры a0, ai1,...,ik принимают значения 0 или 1. Носитель булевой функции - множество всех векторов, на которых функция принимает значение 1: suPP(f) = {x € Zn : f (x) = 1}. Булев куб -граф En, вершинами которого являются все двоичные векторы длины n, т. е. V = {(x1, . . . , xn) : xi € Z2}, а рёбрами соединяются только те векторы, расстояние Хэмминга между которыми равно единице. Число n называется размерностью булева куба. Весом Хэмминга wt(f) булевой функции f от п переменных называется число ненулевых координат её вектора значений. Гранью размерности k в булевом кубе En называется множество Га1 ,...,an -k i1,...,in - k {xi1 = a1, . . . , xin-k = an-k}. Булева функция f(x) от п переменных называется сбалансированной, если принимает каждое из значений 0 и 1 ровно 2n-1 раз [5]. Алгебраической иммунностью AI(f) булевой функции f от п переменных называется минимальное число d, такое, что существует не тождественно равная нулю булева функция g от п переменных степени d, для которой выполняется f • g = 0 или (f + 1)g = 0 [5]. Высокая алгебраическая иммунность обеспечивает стойкость шифра к алгебраическому криптоанализу. Известна оценка сверху алгебраической иммунности булевой функции от п переменных: AI(f) С Гп/2"| [2]. Булева функция f от п переменных называется корреляционно-иммунной порядка г, 1 С r С п, если для любой её подфункции f^’’"’^, полученной фиксацией r переменных, выполняется равенство .’ar ’ir wt(f) 2r Эквивалентное определение: булева функция f от п переменных является корреляционно-иммунной порядка п - k, 1 С k С п, если любой грани Г“1’'"’“п-к булева куба En размерности k принадлежит одинаковое число точек носителя функции f, а именно 2-(n-k)wt(f) точек. Так как корреляционно-иммунная порядка m булева функция является также корреляционно-иммунной порядка £ для всех £ < m [6], можем ввести обозначение для максимального порядка корреляционной иммунности: CI(f) = max{m G N : f - корреляционно-иммунная порядка m}. Пусть f - булева функция от п переменных. Геометрическим представлением булевой функции f назовём подграф булева куба En, индуцированный носителем функции f. Напомним, что два графа F и G называются изоморфными, если существует биекция на множествах их вершин, такая, что образы ^(и) и ^(v) в графе G смежны тогда и только тогда, когда смежны вершины u и v в графе F . Два подграфа G1 и G2 булева куба En, индуцированные носителями функций f1 и f2 соответственно, назовём изоморфными по метрическому вложению, если найдётся автоморфизм : En En булева куба En, под действием которого G1 переходит в G2. Напомним, что любой автоморфизм булева куба En как графа является изометрией En относительно расстояния Хэмминга. 1. Булевы функции от трёх переменных Для п = 3 получена полная классификация булевых функций с корреляционной иммунностью порядков 3, 2, 1. Всего существуют: - 2 функции порядка 3 - функции-константы; - 4 функции порядка 2 - функции-константы и функции-счётчики чётности; - 18 функций порядка 1. Из всех этих функций ни одна не имеет максимально возможного значения алгебраической иммунности (т. е. AI(f) < 2). 2. Булевы функции от четырёх переменных Исследуем пересечение множеств булевых функций от четырёх переменных с максимальной алгебраической иммунностью (равной 2) и с максимальным порядком корреляционной иммунности 1. Заметим, что среди функций от четырёх переменных с максимальной алгебраической иммунностью не существует функций с более высоким максимальным порядком корреляционной иммунности. В этом пересечении лежат 392 функции, среди которых функции веса 6 (96 функций), 8 (200 функций) и 10 (96 функций), при этом функции веса 6 совпадают с инверсиями функций веса 10. Ограничения на вес функций накладывают рассматриваемые характеристики: корреляционная иммунность требует чётного веса, а для того, чтобы алгебраическая иммунность имела максимальный показатель AI(f) = 2, необходимо, d n d n чтобы выполнялись следующие ограничения: wt(f) и wt(f ф 1) , i=0 i i=0 i где d = AI(f) - 1 = 1 , n = 4. Будем рассматривать только функции, которые принимают значение 1 на нулевом векторе: 36 функций веса 6, 100 функций веса 8, 60 функций веса 10. Мы можем это сделать, так как инвертирование функции не изменяет показатели её алгебраической и корреляционной иммунности. Заметим, что все функции разбиваются на классы сообразно своему геометрическому представлению (или виду АНФ). Переход от одной булевой функции к другой внутри класса осуществляется переобозначением переменных. Произведена классификация данных булевых функций и написана программа, с помощью которой на основе рассматриваемых 196 функций от четырёх переменных построены функции от шести переменных и проверена их алгебраическая и корреляционная иммунность. 2.1. Б у л е в ы ф у н к ц и и в е с а 6 с A I (f) = 2 , C I (f) = 1 Рассмотрим функции веса 6 с AI(f) = 2, CI(f) = 1 , принимающие значение 1 на нулевом векторе, и индуцированные их носителями подграфы булева куба E4 (рис. 1). Здесь и далее метками у тонких линий обозначены расстояния между несмежными вершинами графа. Подграфы данного вида симметричны относительно вертикальной оси, мы не различаем симметричные вершины. Рис. 1. Подграф из G6 Все подграфы, индуцированные носителями таких функций, изоморфны по вложению между собой. Обозначим данное множество индуцированных подграфов как G6. Утверждение 1. Булева функция f от четырёх переменных веса 6, принимающая значение 1 на нулевом векторе, имеет характеристики AI(f) = 2 и CI(f) = 1 , если и только если индуцированный её носителем подграф булева куба E4 изоморфен по вложению графу на рис. 1. От того, какой вершиной индуцированного носителем подграфа является нулевой вектор булева куба, зависит вид алгебраической нормальной формы функции f: 1) нулевой вектор - изолированная вершина (12 функций), пример АНФ: Х1Х2Хз ф Х1Х2Х4 ф Х1Х3Х4 ф Х2Х3Х4 ф XiХ3 ф Х2Х4 ф Х3Х4 ф Х4 ф Х3 ф Х2 ф Х1 ф 1; 2) нулевой вектор - вершина ai, i = 1, 2 (12 функций), пример АНФ: x1x2x3 ф x1x2x4 ф x1x3x4 ф x2x3x4 ф x3x4 ф x2x4 ф x4 ф x3 ф x2 ф 1; 3) нулевой вектор - вершина bi, i = 1, 2 (12 функций), пример АНФ: x1x2x3 ф x1x2x4 ф x1x3x4 ф x2x3x4 ф x3x4 ф x4 ф x3 ф x2 ф 1. 2.2. Б у л е в ы ф у н к ц и и в е с а 10 с A I (f) = 2 , C I (f) = 1 Подграфы булева куба, индуцированные носителями функций веса 10 с AI(f) = 2 и CI(f) = 1, принимающих значение 1 на нулевом векторе, также изоморфны по вложению между собой; обозначим множество таких подграфов как G10 (рис. 2). Утверждение 2. Булева функция f от четырёх переменных веса 10, принимающая значение 1 на нулевом векторе, имеет характеристики AI(f) = 2 и CI(f) = 1, если и только если индуцированный её носителем подграф булева куба E4 изоморфен по вложению графу на рис. 2. От того, какой вершиной индуцированного носителем подграфа является нулевой вектор булева куба, зависит вид алгебраической нормальной формы функции f : 1) нулевой вектор - вершина степени 1 (12 функций), пример АНФ: x1x2x3 ф x1x2x4 ф x1x3x4 ф x2x3x4 ф x1x2 ф x1x3 ф x2 ф x3 ф x4 ф 1; 2) нулевой вектор - вершина степени 2, равноудалённая от вершин степени 3 (12 функций), пример АНФ: x1x2x3 ф x1x2x4 ф x1x3x4 ф x2x3x4 ф x1x2 ф x1x4 ф x2x3 ф x3 ф x4 ф 1; 3) нулевой вектор - вершина степени 2, не равноудалённая от вершин степени 3 (24 функции), пример АНФ: Х1Х2Хз ф Х1Х2Х4 ф Х1Х3Х4 ф Х2Х3Х4 ф Х1Х2 ф Х1Х3 ф Х1Х4 ф Х2Х3 ф Х2Х4 ф Х3Х4ф ф x1 ф x 4 ф 1; 4) нулевой вектор - вершина степени 3 (12 функций), пример АНФ: Х1Х2Хз ф Х1Х2Х4 ф Х1ХзХ4 ф Х2ХзХ4 ф Х1Х2 ф Х1Хз ф Х1Х4 ф Х2Хз ф Х2Х4 ф Х4 ф 1. 2.3. Б у л е в ы ф у н к ц и и в е с а 8 с A I (f ) = 2 , C I (f ) = 1 Индуцированные носителями функций веса 8 с AI(f ) = 2, CI(f ) = 1 подграфы имеют четыре возможных вида, обозначим их Gi8, i = 1, 2, 3, 4 (рис. 3). Подграфы в каждом из Gi8 , i = 1, 2, 3, 4, изоморфны по вложению между собой. абвг Рис. 3. Подграфы из G8 Утверждение 3. Булева функция f от четырёх переменных веса 8, принимающая значение 1 на нулевом векторе, имеет характеристики AI(f ) = 2 и CI(f ) = 1, если и только если индуцированный её носителем подграф булева куба E4 изоморфен по вложению одному из графов на рис. 3. От того, какой вид имеет индуцированный носителем функции подграф и какой вершиной этого подграфа является нулевой вектор булева куба, зависит вид алгебраической нормальной формы функции f : 1. Два 2-пути и две изолированные вершины (рис. 3, а ): а) нулевой вектор - вершина степени 2 (6 функций), пример АНФ: Х1Х2 Ф Хз ф Х4 ф 1; б) нулевой вектор - вершина степени 1 (12 функций), пример АНФ: x1 x2 ф x2 ф x3 ф x4 ф 1; в) нулевой вектор - изолированная вершина (6 функций), пример АНФ: x3x4 ф x1 ф x2 ф x3 ф x4 ф 1. 2. Два 3-пути (рис. 3, б ): а) нулевой вектор - вершина степени 2 (24 функции), пример АНФ: x1 x2 ф x2x3 ф x3 ф x4 ф 1; б) нулевой вектор - вершина степени 1н (24 функции), пример АНФ: x1 x2 ф x3x4 ф x2 ф x3 ф x4 ф 1. 3. Две вершины степени 3 (рис. 3, в): а) нулевой вектор - вершина степени 3 (4 функции), пример АНФ: x1 x2 ф x1 x3 ф x2x3 ф x4 ф 1; б) нулевой вектор - вершина степени 1 (12 функций), пример АНФ: x2x3 ф x2x4 ф x3x4 ф x1 ф x2 ф x3 ф 1. 4. Цикл длины 8 (рис. 3, г), пример АНФ: x1 x2 ф x1 x4 ф x2x3 ф x3x4 ф x3 ф x4 ф 1. 3. Булевы функции от пяти переменных При n = 5 получен полный список булевых функций с максимальной алгебраической иммунностью (AI(f) = 3)-всего их 197765122. Из них 96 768 функций имеют корреляционную иммунность порядка 1. Функций с более высоким порядком корреляционной иммунности и с максимальной алгебраической иммунностью не существует. 4. Булевы функции от шести переменных Для перехода к функциям от шести переменных мы заменяем каждый вектор булева куба E4 на грань размерности 2. В таком случае, если вектор булева куба E4 принадлежал носителю исходной функции от четырёх переменных, существуют пять вариантов расположения точек носителя в новой грани размерности 2: - все векторы новой грани принадлежат носителю функции от шести переменных; - три вектора новой грани принадлежат носителю; - два вектора новой грани на расстоянии 1 друг от друга принадлежат носителю; - два вектора новой грани на расстоянии 2 друг от друга принадлежат носителю; - один вектор новой грани принадлежит носителю функции от шести переменных. Исследован способ построения, при котором все вершины, принадлежащие носителю, заменяются на грань одного и того же вида. При этом необходимо учитывать, что для сохранения максимального порядка корреляционной иммунности 1 необходимо, чтобы каждой грани булева куба E6 размерности 5 принадлежало одинаковое число точек носителя. С помощью программы мы проверили алгебраическую иммунность всех полученных функций от шести переменных и выяснили, что все варианты (с учётом ограничений, накладываемых корреляционной иммунностью) позволяют построить функцию от шести переменных с сохранением показателей алгебраической и корреляционной иммунности исходной булевой функции от четырёх переменных. Однако ни в одном случае не наблюдался рост алгебраической иммунности до максимально возможного показателя AI(f) = 3 для функций от шести переменных. Заключение В работе получена полная классификация булевых функций от трёх, четырёх и пяти переменных с максимальной алгебраической иммунностью и обладающих корреляционной иммунностью. Исследован способ построения булевых функций большей размерности на основе функций меньшей размерности с заданными свойствами с сохранением этих свойств. В дальнейшем планируется рассмотреть другие возможности построения функций от шести переменных на основе геометрического представления функций от четырёх переменных, добиться повышения показателя алгебраической иммунности.

Скачать электронную версию публикации