Что такое корреляционная иммунность функций?

В криптологии важное место занимают корреляционно-иммунные функции. У любой такой функции есть два параметра: число переменных — n и степень корреляционной иммунности — m. Криптологи, которые давали определение, сначала дали его на вероятностном языке: это функция, выход которой не коррелирует с совокупностью любых m входов. То есть если мы берем любые m входов функции от n переменных и подставляем любые константы — нули и единицы — вместо этих m входов, то получится какая-то подфункция — функция уже от n минус m переменных. Любая такая подфункция определена уже на 2(n-m) наборах. На комбинаторном языке такая функция является корреляционно-иммунной, если при подстановке любых m констант вместо любых n переменных вес функции будет одним и тем же. То есть доля наборов, для которых функция равна единице, при подстановке констант не изменится. В принципе любую информацию можно разложить на нули и единицы и какой-то функцией это описать, но в этом никакой науки нет. Весь вопрос в том, как с этой информацией дальше работать.

Рассмотрим функцию от трех булевых переменных. Ее можно рисовать с помощью обычного трехмерного кубика, в котором вершины — это как раз наборы. Каждая вершина представлена тремя параметрами, например ноль, ноль, ноль. То есть каждая вершина — это один набор. И на каждую вершину давайте ставить значение — нолик и единичку. Нолик — черное, а единичка — белое. Получается, что какие-то вершины мы делаем черными, а какие-то — белыми.

И вот, допустим, мы хотим построить функцию корреляционно иммунную порядка один. Это что означает? При подстановке одной константы у нас остается подфункция двух переменных, то есть из трехмерного кубика получаются двумерные квадраты. Мы как бы убираем одну степень свободы. И в любой грани тогда должно быть одинаковое число белых вершин: например, если одна вершина белая, а три остальные черные. И такая соответствующая функция — это корреляционно-иммунная функция порядка один от трех переменных.

С точки зрения криптографии особый интерес представляют случаи, когда нулей и единиц поровну, то есть функции уравновешенные, и можно генерировать псевдослучайные последовательности. Но корреляционно-иммунные функции порядка n были известны раньше в другой области как ортогональный массив. Это понятие ввел индийский математик Рао в 1947 году. Он был статистиком и в качестве мотивации для своих исследований приводил оптимизацию планирования эксперимента для дегустации сортов кофе.

Что же такое ортогональный массив? Это матрица с N столбцами и n строками, и в каждой ячейке есть какой-то символ из алфавита. И есть еще параметр мощности алфавита. Мы говорим про двоичный алфавит, и его мощность равна двум. Еще есть параметр t — сила массива, которая заключается в следующем: как бы мы ни зафиксировали любые t столбцов, любой поднабор длины t должен встречаться одинаковое число раз.

Если каждый столбец соответствует какому-то параметру, значит, строка соответствует комбинации параметров. И если мы хотим перебрать все возможные параметры, то есть провести эксперимент, может оказаться, что число вариантов будет слишком большим. Но если провести меньше экспериментов, какие-то комбинации параметров будут встречаться неодинаковое число раз. Так вот, нужно стремиться к тому, чтобы эти комбинации из t параметров встречались одинаковое число раз, а число строк было как можно меньшим.

И на самом деле такой массив (если в нем нет повторяющихся строк) эквивалентен корреляционно-иммунной функции. То есть если t равно m, строки не повторяются, а мощность алфавита равняется двум, то это просто эквивалентно корреляционно-иммунной функции порядка t от n переменных.

Уже существует наработанная теория построения таких массивов и получения нижних оценок числа строк в них, а статистика широко применяется для теории экспериментов. Но это еще и с теорией кодирования имеет связь. По строкам матрицы можно записывать все наборы из списка, который нужно кодировать. Получается матрица определенных размеров, и ее можно рассматривать как код. Но для этого вводится понятие расстояния между наборами: берут две строки и смотрят, в каком количестве разрядов они различаются. И как раз минимум этих расстояний по парам — это и есть свойство, которое необходимо для кодирования. Оно называется кодовым расстоянием.

Можно задать вопрос: а если эту матрицу нарисовать, взять просто код, ортогональным массивом какой силы он является? И оказывается, если код линейный, то нужно взять ортогональный к нему код, найти его кодовое расстояние и вычесть из него единицу — это максимальная сила массива. А если код линейный, мы знаем его распределение весов. Вес набора — это число ненулей в нем. Элемент Ai распределения весов кода — это число наборов кода, в которых ровно i ненулей. У ортогонального кода есть свое распределение весов (B0,… Bn). И оказывается, что даже если код нелинейный, то все равно из этого распределения весов можно найти силу массива по формальным формулам, через преобразования Мак-Вильямс или полиномы Кравчука.

По преобразованию весов (A0,… An) строится распределение весов ортогонального кода (B0,… Bn). B0 всегда равно единице, потому что ноль принадлежит ортогональному пространству. Потом идет сколько-то нулей, а первое ненулевое значение и будет максимальной корреляционной иммунностью и максимальной силой плюс один.

Пусть это значение имеет индекс m+1, значит, максимальная корреляционная иммунность равна m. И похожий подход можно применить и для нелинейных кодов.

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

Есть такая атака: разделяй и властвуй. Ее можно применить к поточному шифру, в котором выходы нескольких регистров сдвига подаются на входы комбинирующей булевой функции, выход которой будет давать псевдослучайную последовательность. Если функция обладает маленькой корреляционной иммунностью, противник фиксирует определенное число входов и перебирает варианты начальных значений ячеек внутри регистров, присоединенных к этим входам. И смотрит, когда появляется корреляция. Как только это происходит, он делает определенный вывод. Это позволяет находить секретный ключ по частям, если он как-то распределен. В обычной схеме есть несколько регистров сдвига, в каждом регистре своя псевдослучайная последовательность со своим секретным ключом, и они все подаются на вход булевой функции. И казалось бы, надо перебирать варианты во всех регистрах. Но если есть какая-то маленькая часть, которая коррелирует с выходом, то можно перебрать только в ней отдельно и по части угадать целое. Чтобы этого избежать, нужна корреляционная иммунность.