«Четвертая международная научная конференция по проблемам безопасности и противодействия терроризму Московский государственный университет им. М. В. Ломоносова, 30–31 октября 2008 г. Том 2 Материалы Седьмой ...»

Таким образом, для оценки практической стойкости БШ I относительно перечисленных методов криптоанализа требуется получить аналитические верхние границы параметров (7), (8) и (9).

3. Введем ряд дополнительных обозначений. Для любых u, v Vt обозначим u + v сумму по модулю 2t двоичных целых чисел, соответствующих векторам u и v; символом (u, v) обозначим бит переноса в t-й разряд при сложении чисел u и v в кольце Z.

18 А. Н. Алексейчук, Л. В. Ковальчук, Л. В. Скрыпник, А. С. Шевцов где (u, v) — символ Кронекера. Положим также Напомним, что вес вектора x = (x0,..., xp1), где xj GF(2t), j 0, p 1, определяется по формуле wt(x) = # j 0, p 1 : xj = 0, а индекс ветвления (branch number) обратимой матрицы M — по формуле [7] Следующая теорема устанавливает верхние оценки параметров (7), (8).

Теорема 1. Пусть I — r-раундовый БШ, описываемый соотношениями (1) – (6), r = 2r + 1. Тогда справедливы неравенства где и определяются по формулам (10), а BM — по формуле (11).

Отметим, что в доказательстве теоремы 1 существенно используются результаты, изложенные в [3, 4], а также тот факт, что при выполнении условий (1) – (6) I является обобщенным марковским шифром [4] относительно каждой из операций, +. Численные расчеты значений (10) для шифра «Калина-128» показывают, что = 0, 031250, = 0, 0421770.

Отсюда на основании (12) (при r = 5, BM = 9 [1]) вытекают оценки EDP() 2230, ELP() 2212, свидетельствующие о том, что рассматриваемый БШ является практически стойким относительно разностного и линейного методов криптоанализа.

Оценки практической стойкости блочного шифра «Калина»...

4. Приведем оценки параметра (9), справедливые при некоторых ограничениях на матрицу A. Запишем эту матрицу в блочном виде: A = = (Aij) i,j0,p1, где Aij — матрица порядка t; аналогично представим векторы и : = ( 0,..., p1), = ( 0,..., p1) где, Vt, j 0, p 1.

Для любого i 0, p 1 обозначим Ci (A) (Si (A)) подпространство векторного пространства Vt, порожденное столбцами матриц Aij (строками матриц Aji) по всем j = i. Введем также следующие обозначения:

где B — произвольная булева матрица порядка t, u, v Vt, j 0, p 1.

Теорема 2. Пусть матрица A = (Aij) i,j0,p1 удовлетворяет условию Тогда для любых, Vn справедливы неравенства Кроме того, если Aij = 0 для любых i = j, то последняя оценка достигается, если Aii = 0, i = i = 0 для всех i maxu,vV8 (B, u, v) для s-блоков si шифра «Калина-128» и нескольких десятков случайно сгенерированных ненулевых (8 8)-матриц B показывает, что эти значения не превоходят 0, 004. Отсюда на основании (14), (15) вытекают аналогичные оценки параметра (9), справедливые для любой матрицы A, удовлетворяющей условию (13) и содержащей любую из сгенерированных подматриц на главной диагонали.

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

20 А. Н. Алексейчук, Л. В. Ковальчук, Л. В. Скрыпник, А. С. Шевцов Литература [1] Горбенко I. Д., Долгов В. I., Олiйников Р. В., Руженцев В. I., Михайленко М. С., Горбенко Ю. I., Тоцький О. С., Казьмiна С. В. Перспективний блоковий симетричний шифр «Калина» — основнi положення та специфiкацi // Прикладная радиоэлектроника, 2007, т. 6, № 2, с. 195–208.

[2] Wagner D. Towards a unifying view of block cipher cryptanalysis // Proceedings of FSE’04, Springer-Verlag, 2004, p. 116–135.

[3] Alekseychuk A. N., Kovalchuk L. V. Upper bounds of maximum values of average dierential and linear characteristic probabilities of Feistel cipher with adder modulo 2m // Theory of Stohastic Processes, 2006, v. 12(28), № 1, 2, p. 20–32.

[4] Ковальчук Л. В. Обобщенные марковские шифры: построение оценки практической стойкости относительно дифференциального криптоанализа // Математика и безопасность информационных технологий. Материалы конференции в МГУ 25–27 октября 2006 г., М.: МЦНМО, 2007, с. 295–299.

[5] Vaudenay S. On the security of CS-cipher // Proceedings of FSE’99, Springer-Verlag, 1999, p. 260–274.

[6] Courtois N. T. Feistel schemes and bi-linear cryptanalysis // Proceedings of CRYPTO’04, Springer-Verlag, 2004, p. 23–40.

[7] Daemen J. Cipher and hash function design strategies based on linear and dierential cryptanalysis. Doctoral dissertation, 1995.

Алгоритмы построения матричных В докладе описываются два новых алгоритма построения матричных приближений Паде для рядов по отрицательным степеням переменной.

При решении задачи факторизации целых чисел возникает необходимость решать систему линейных однородных разреженных уравнений над полем F = GF(2). Ранее (см. [1]) в докладах автора было показано как эту задачу свести к построению матричных приближений формальных рядов с матричными коэффициентами по отрицательным степеням переменной. Основная часть алгоритма — это процедура построения следующего приближения при помощи предыдущих. Для получения решения исходной линейной системы необходимо построить приближения с невырожденными старшими коэффициентами. Рассмотрим несколько последовательных приближений Паде:

где — формальная переменная, греческими буквами обозначены матрицы из F(n n), большими латинскими — матричные полиномы из F(n n) [], степени которых не превосходят их номеров. Считаем, что коэффициенты разложений справа — независимые случайные матрицы.

Пусть Q (1) = 0n, P (1) = In, Q (0) = In, P (0) = 0, где In, 0n — соответственно единичная и нулевая матрицы. Был предложен алгоритм построения очередного приближения Паде при помощи модифицированных предыдущих. Было доказано, что приближение с номером r + 1 может быть построено при помощи приближений с номерами r, r 1,..., r t, если некоторые величины, характеризующие вырожденность старших коэффициентов предыдущих приближений 1, 2,..., t удовлетворяют следующим неравенствам:

Обозначим Идея следующей теоремы предложена А. М. Зубковым.

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

Доказательство использует несколько известных оценок распределения коранга случайных квадратных матриц [2]:

В докладе предложен ещё один алгоритм построения таких приближений.

Литература [1] Черепнев М. А. Блочный алгоритм типа Ланцоша решения разреженных систем линейных уравнений // Дискрет. матем. 2008. Т. 20, № 1. С. 145–150.

[2] Алексейчук А. Н. Неасимптотические оценки распределения вероятностей ранга случайной матрицы над конечным полем // Дискрет. матем. 2007. Т. 19, О числе отрезков заданного ранга В работе [1] получено точное значение числа последовательностей длины n (n-последовательностей) заданного ранга (под рангом понимается степень минимального многочлена отрезка) над конечным полем. В работе представленной данным сообщением исследуются вопросы связанные с вычислением значения числа n-последовательностей заданного ранга над кольцом вычетов ZN, N = pm1... pmt, p1,..., pt — различные простые числа.

В силу изоморфизма кольца ZN внешней прямой сумме примарных колец вычетов Zpmi, i = 1, t, изучение ранга n-последовательности un ZN естественным образом сводится к изучению ранга ее компонент над примарным кольцом Zpm.

Для дальнейшего изложения нам потребуется краткое описание алгоритма Берлекемпа—Месси нахождения минимального многочлена последовательности. Мы будем использовать разработанную В. Л. Куракиным версию алгоритма для конечных колец с единицей, которую можно найти, например, в [2].

Определение 1. Элементы a, b Zpm называются ассоциированными, если существует обратимый элемент v Zm, такой что a = vb.

Отношение ассоциированности, заданное в соответствии с определением 1, разбивает множество элементов кольца на непересекающиеся классы K0, K1,..., Km1. При этом будем считать, что классу K0 принадлежат обратимые элементы кольца, а остальным классам — делители нуля.

Обозначим wi = |Ki |, i = 0, m 1 — мощность соответствующего класса, а число элементов в кольце через R = pm. Будем также считать, что класс Ki, i = 1, m 1, содержит элементы с индексом нильпотентности равным Алгоритм Берлекемпа—Месси заполняет для каждого i = 0, m таблицу, соответствующую классу Ki (см. табл. 1, где ai Ki). На s-й строке этой таблицы находятся отрезок и многочлен, с помощью которого данный отрезок получается из первого отрезка. Кроме этого заполняется таб

Работа выполнена при поддержке гранта Президента РФ НШ 4.2008.10.

лица, содержащая идеалы Is (k), s = 0, 1,..., k = 0, n s 1 (см. табл. 2).

Идеал Is (k) порожден элементами v такими, что на шаге l < s появился отрезок, в начале которого было k нулей, а на k + 1 месте находился элемент v.

Алгоритм заключается в следующем. На s-м шаге отрезок в текущей таблице сдвигается на один элемент влево (умножается на x), и, если первый ненулевой элемент принадлежит соответствующему идеалу, то данный элемент может быть обнулен с помощью всех отрезков полученных на предыдущих этапах алгоритма во всех таблицах. После обработки всех таблиц подправляется таблица идеалов: в соответствующие идеалы добавляются первые ненулевые элементы получившихся отрезков. Алгоритм заканчивает работу, когда в первой таблице появляется нулевой отрезок.

Всюду далее считаем, что алгоритм закончил работу на шаге r 0, n.

Справедливы следующие леммы.

Лемма 1. Если построенный в результате работы алгоритма Берлекемпа—Месси идеал Ir1 (k) порожден элементом a, то идеал Ir1 (k 1) также порожден этим элементом.

Лемма 2. Ir1 (r) = 0.

Из последней леммы следует, что если ранг последовательности un равен r, то ненулевыми являются идеалы Ir1 (0),..., Ir1 (r 1).

Определение 2. i-м подрангом последовательности un будем называть величину О числе отрезков заданного ранга над кольцом вычетов Следствие 1. r0 r1... rm1 = r.

Далее для простоты изложения будем записывать (r0, r1,..., rm1) (un) в случае, если последовательность un имеет подранги r0, r1,..., rm1.

Заметим, что если мы рассмотрим все (n + 1)-последовательности un a, a Zpm, то в результате работы алгоритма Берлекемпа—Месси на r-том шаге для последовательнсотей такого вида в первой таблице получатся pm (n + 1 r)-последовательностей вида 0,..., 0, b, b Zpm.

Утверждение 1. Пусть n-последовательность un имеет подранги (r0, r1,..., rm1) (un). Тогда 1) если r0 r1... rm1 [(n + 1) /2], то (n + 1)-последовательность un a имеет подранги 2) если r0... ri1 [(n + 1) /2] < ri... rm1, то (n + 1)-последовательность un a имеет подранги 3) если [(n + 1) /2] < r0 r2... rm1, то (n + 1)-последовательность un a имеет подранги (r0, r1,..., rm1) (un).

Данное утверждение описывает определяющие соотношения для ранга n-последовательности при увеличении ее длины и позволяет получить выражения для точного числа последовательностей заданного ранга. Покажем на примере кольца Zp2 методику расчета указанных величин. Обозначим через Nn (r0, r1) число n-последовательностей длины имеющих подранги r0, r1. Положим Nn (r0, n + 1) = 0.

Следствие 2. Если n четно, то Nn (r0, r1) = 0, r1 > n/2, n r1 < r0 < < r1. Если же n нечетно, то Nn (r0, r1) = 0, r1 > [n/2] + 1, n r1 < r0 < < r1.

Следствие 3. При n > 1 число (n + 1)-последовательностей, имеющих подранги r0, r1, удовлетворяет следующим равенствам.

1. Пусть n + 1 нечетно. Тогда 2. Пусть n + 1 четно. Тогда Здесь w0 и w1 — определенные ранее мощности классов ассоциированных элементов.

Лемма 3.

О числе отрезков заданного ранга над кольцом вычетов Следствие 4.

Nn (r0, r1) = w1 (w1 + 1) 2n2r1 2r0 N2r0 (r0, r0), r1 > [n/2], r0 n r1 ;

Следствие 5. Nn (r, r) = R2n2r w0 (w1 + 1) 2rn1, r n/2.

Утверждение 2. Число Nn (r) n-последовательностей ранга r над кольцом Zp2 равно 1, если r = 0, если r w1 R2n2r+1 + (w1 + 1) 2n2r+1 + R2n2r (w1 + 1) 2rn1 R2 (w1 + 1) если r > n/2.

Литература [1] Niederreiter H. The linear complexity prole and the jump complexity of keystream sequences, I. Proceedings of Eurocrypt’90, Lecture notes in Comput.

Sci., vol. 473, Springer, Berlin, 1991, p. 174–188.

[2] Куракин В. Л. Алгоритм Берлекемпа—Месси над конечными кольцами, модулями и бимодулями // Дискретная математика. 1998. Т. 10, № 4. С. 3–34.

Эквивалентные подпространства кода Рида—Маллера и множество открытых ключей криптосистемы Мак-Элиса—Сидельникова Кодовая криптосистема Мак-Элиса—одна из старейших криптосистем с открытым ключом. Она была предложена в 1978 году Р. Дж. Мак-Элисом [1]. В. М. Сидельников в работе [2] рассматривал криптосистему Мак-Элиса, построенную на основе двоичных кодов Рида—Маллера RM(r, m). В. М. Сидельников, проведя криптоанализ такого варианта криптосистемы Мак-Элиса, пришёл к выводу, что на сегодняшний день модификация криптосистемы Мак-Элиса, построенная на кодах Рида—Маллера, не обеспечивает необходимого уровня стойкости. В той же работе [2] автор предлагает усиленный вариант криптосистемы на основе кодов Рида—Маллера — криптосистему Мак-Элиса—Сидельникова.

Опишем устройство криптосистемы Мак-Элиса—Сидельникова. Пусть R — (k n)-порождающая матрица кода Рида—Маллера RM(r, m). Будем полагать, что матрица R состоит из векторов значений всех мономов от m переменных степени нелинейности, не выше r. К тому же, если перенумеровать сверху строки матрицы R, в строке с номером 2 i k стоит вектор значений монома xi1 xi2... xit, где ij (1 j t) — номера позиций, в которых стоит единица в двоичном разложении числа i 1, а в строке с номером 1 — вектор из всех единиц. Секретным ключом криптосистемы является кортеж Здесь H1, H2,..., Hu — невырожденные (k k)-матрицы над полем F2 = = {0, 1}, которые выбираются случайно и равновероятно из множества GLk (F2) всех двоичных невырожденных (k k)-матриц над полем F2. Матрица — перестановочная (u · n u · n)-матрица.

Открытым ключом криптосистемы Мак-Элиса—Сидельникова является матрица где символом обозначена конкатенация матриц по столбцам. Алгоритмы шифрования и расшифрования подробно описаны в [2].

Эквивалентные подпространства кода Рида—Маллера...

Группу автоморфизмов кода Рида—Маллера RM(r, m) будем обозначать символом Aut(RM(r, m)). Рассмотрим некоторую перестановку P из группы автоморфизмов кода Рида—Маллера RM(r, m). Построим по ней i «длинных» перестановок P [i] Sun следующим образом: P [i] (j) = = P(I). Другими слова перестановка P [i] в i-том блоке совпадает с перестановкой P, а во всех остальных блоках — совпадает с единичной перестановкой. Группой расширенных автоморфизмов Au (RM(r, m)) кода Рида—Маллера RM(r, m) назовём множество всех возможных произведений описанных перестановок P [i] для всех возможных 1 i u и всех возможных перестановок P из группы автоморфизмов кода Рида—Маллера.

Два секретных ключа (H1, H2,..., Hu, ) и (H1, H2,..., Hu, ) назовём эквивалентными, если соответствующие им открытые ключи совпадают, то есть выполняется соотношение Всё множество секретных ключей разбивается на классы эквивалентности и число классов эквивалентности совпадает с числом открытых ключей. Класс эквивалентности с представителем (H1,..., Hu, ) будем обозначать так: [(H1,..., Hu, )].

Рассмотрим множество G (H1, H2,..., Hu), состоящее из перестановок Sun, для которых существуют невырожденные двоичные матрицы H1, H2,..., Hu такие, что (H1 R H2 R... Hu R) = (H1 R H2 R... Hu R).

Справедлива следующая теорема.

Теорема 1. Класс эквивалентности [(H1, H2,..., Hu, )] состоит из ключей вида где g принадлежит множеству G (H1, H2,..., Hu) и Тем самым вопрос изучения эквивалентных секретных ключей сводится к описанию множеств G (H1,..., Hu).

Наиболее просто устроено множество G (E,..., E). Следующее утверждение в немного другом виде было получено Г. А. Карпуниным [4].

Теорема 2. Множество G (E,..., E) состоит из перестановок вида · P, где такова, что а P — перестановка из группы Au (RM(r, m)).

Также в случае произвольного u справедлива следующая теорема.

Теорема 3. Пусть для невырожденных матриц D1, D2,..., Du существуют такие перестановки Pi (1 i n) из Sn, что Обозначим через P1 [1], P2 [2],..., Pu [u] перестановки из Au (RM(r, m)) соответствующие перестановкам P1, P2..., Pu. И пусть H — любая невырожденная матрица. Тогда С учетом теоремы 1 теорема 3 дает описание нетривиального подмножества множества открытых ключей криптосистемы Мак-Элиса—Сидельникова в случае u = 2.

Обратимся к вопросу изучения множества G (H1, H2), то есть к изучению множества в случае двух блоков (u = 2).

Для случая u = 2 задача поиска эквивалентных ключей криптосистемы Мак-Элиса—Сидельникова основывается на изучении множеств G (E, H).

В случае когда матрица H задаёт автоморфизм кода RM(r, m) описание множества G (E, H) даёт теорема 3. Интересно получить описание этого множества в случае каких-то других матриц H.

Для некоторого вектора = ( 1,..., n), i = 1, рассмотрим матрицу T i вида Первый случай — i = 1. Справедлива теорема.

Теорема 4. Пусть i = 1. Тогда Здесь символом e1 обозначен вектор, у которого на первом месте стоит 1, а на всех остальных местах — 0.

Перейдём теперь к изучению случая i > 1. Следует отметить, что в дальнейшем рассматриваются коды Рида—Маллера RM(r, m) с r > 1, так как Эквивалентные подпространства кода Рида—Маллера...

в случае r = 1 полное описание множества открытых ключей для двух блоков получено Г. А. Карпуниным [4]. При изучении эквивалентных ключей в случае i > 1 возникает необходимость в исследовании эквивалентности некоторых специальных (k 1)-мерных подпространств кода Рида—Маллера RM(r, m). Это объясняется тем, что справедливо следующее утверждение.

Утверждение 1. Пусть R — порождающая матрица кода Рида—Маллера RM(r, m), r > 1. И пусть перестановка с некоторыми невырожденными двоичными матрицами X, Y является решением уравнения то есть G (E, T i ). Тогда найдутся две перестановки Sun и P = R Sn такие, что = P и (R R) = (R R).

Здесь R — матрица, получающаяся из матрицы R выкидыванием i-той строки.

Утверждение 1 сводит задачу изучения пространства эквивалентных ключей криптосистемы Мак-Элиса—Сидельникова, в случае r > 1, к изучении таких перестановок, что R — (k 1)-мерный подкод кода Рида—Маллера RM(r, m).

Для подкода R введём ещё одно множество перестановок I(R) Иными словами множество I(R) состоит из перестановок, которые не изменяют кодовые слова кода R.

Теорема 5. Пусть 2r m, t > 0. Тогда любая перестановка, для которой существует подпространство P кода Рида—Маллера такое, что может быть представлена в виде произведения — аффинная перестановка, а принадлежит группе I(R).

где Используя теорему 5 можно получить описание множества G (E, T i ) для i > 1.

Итак, справедлива следующая теорема 6.

Теорема 6. Пусть RM(r, m) — код Рида—Маллера такой, что 2r m, i — натуральное число, большее единицы, H — любая невырожденная двоичная матрица, — произвольный двоичный вектор, у которого в координате с номером i стоит единица. Тогда множество G H, HT i содержит те и только те перестановки, которые могут быть представлены в виде R), R — автоморфизмы кода Рида—Маллера RM(r, m), а для перестановки выполняются следующие два условия:

1) если R — ((k 1) n)-матрица, получающаяся выкидыванием строки с номером i из матрицы R, то 2) если ri — строка матрицы R с номером i, то Литература [1] McEliece R. J. A public-key cryptosystem based on algebraic coding theory // DSN Prog. Rep., Jet Prop. Lab., California Inst. Technol., Pasadena, CA, January 1978, p. 114–116.

[2] Сидельников В. М. Открытое шифрование на основе двоичных кодов Рида—Маллера // Дискретная математика. 1994. Т. 6, вып. 3. С. 3–20.

[3] Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Связь, 1979.

[4] Карпунин Г. А. О ключевом пространстве криптосистемы Мак-Элиса на основе двоичных кодов Рида—Маллера // Дискретная математика. 2004. Т. 16, вып. 2. С. 79–84.

Неравенства для ортогональных массивов 1. Введение Ортогональным массивом с N строками, n факторами, над алфавитом из s символов силы m называется таблица N n с элементами из алфавита, в которой при выборе любых m столбцов, любая из sm комбинаций символов в этих столбцах встречается среди строк одинаковое число раз. Для ортогональных массивов принято краткое обозначение OA(N, n, s, m). При этом пустые массивы не рассматриваются. Если все строки массива различны, то он называется простым. Ортогональным массивам целиком посвящена монография [4].

Ортогональные массивы тесно связаны с корреляционно-иммунными функциями. Под корреляционно-иммунной булевой функцией порядка m понимается булева функция, у которой доля единичных значений не меняется при подстановке констант вместо любых m переменных. Набор аргументов, на которых корреляционно-иммунная функция порядка m принимает единичные значения, образует ортогональный массив силы m.

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

Уравновешенные корреляционно-иммунные функции порядка m называются m-устойчивыми. Подробнее о корреляционно-иммунных функциях можно прочитать в [2].

Представляет интерес вопрос, при каких соотношениях между n и m существуют неуравновешенные неконстантные корреляционно-иммунные функции порядка m от n переменных. Примеры таких функций при m = Работа выполнена при поддержке гранта Президента РФ (проект НШ 4470.2008.1) и программы фундаментальных исследований ОМН РАН «Алгебраические и комбинаторные методы математической кибернетики» (проект «Синтез и сложность управляющих систем»).

= 2n/3 1 хорошо известны. В работе [3] Д. Г. Фон дер Флаасс доказал, что при m (2n 2) /3 любая неконстантная корреляционно-иммунная функция порядка m от n переменных является уравновешенной. Данная статья обобщает этот факт на случай не обязательно простых ортогональных массивов.

2. Основной результат Теорема. Если m (2n 2) /3, то для OA(N, n, 2, m) выполнено N 2n1. А если при этом N = 2n1, то ортогональный массив является простым.

Доказательство. Для F2 обозначим x = 2n 1, где n — число строк ортогонального массива, совпадающих с. Предположим, что 0 < < N 2n1. Тогда Применим к набору чисел {x } преобразование Уолша:

для которого справедлива формула обращения [1]:

Возведем теперь выражение x через W в квадрат. Получим где Поскольку ортогональный массив имеет силу m, то W = 0 при 0 < | | m.

| | > m мы получаем Кроме того (используем формулу обращения для (3) и определение x ), Неравенства для ортогональных массивов большой силы Рассмотрим теперь величину у произведения векторов x и x2, поэтому аналогично выражению (4), перемножая формулы (2) и (3), получим равенство Второе слагаемое равно 0, поскольку W = 0, а в третьем слагаемом можно подставить выражение (5) для. Если, кроме того, вычесть x, то (7) преобразуется к виду Оценим сомножители. Поскольку W0 0, то и W0 /2n 0. Из (6) и (1) получаем 0 2n W0 /2n, откуда 30 (2/2n)W0 2n 0. Таким образом, (x x ) 0. С другой стороны, x x 0, поскольку x может принимать лишь значения 1, 1, 3,.... Отсюда получаем, что x3 x = для всех, то есть x = ±1 и, как следствие, массив является простым.

Кроме того, получаем, что либо W0 = 0, либо 30 (2/2n)W0 2n = 0.

В первом случае ортогональный массив содержит n = (x + 1) /2 = = W0 /2 + 2n1 = 2n1 строк, что удовлетворяет заключению теоремы. Во втором случае 0 = 2n и |W0 | = 2n, что противоречит неравенствам (1).

Литература [1] Логачёв О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптографии. М.: МЦНМО, 2004.

[2] Таранников Ю. В. О корреляционно-иммунных и устойчивых булевых функциях // Математические вопросы кибернетики. Вып. 11. М.: Физматлит, 2002.

С. 91–148.

[3] Fon-Der-Flaass D. G. A bound on correlation immunity // Siberian Electronic Mathematical Reports (http://semr.math.nsc.ru/). 2007. V. 4. P. 133–135.

[4] Hedayat A. S., Sloane N. J. A., Stufken J. Orthogonal arrays: theory and applications. New York: Springer-Verlag, 1999.

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

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

По всей видимости, для этих классов систем вообще не существует полиномиальных алгоритмов решения, но современное состояние математики позволяет доказывать такого рода результаты только при условии справедливости гипотезы P = NP. При этом используется теория NP-полных задач [4].

В работе рассматриваются классы систем булевых уравнений с ограничениями на выбор функций и без ограничений на выбор неизвестных [7] (классы систем вида [F] NC). В зарубежной литературе изложение ведется в терминах булевых формул, при этом задача распознавания совместности указанных систем уравнений называется «Constraint satisfaction problems» [18]. Если F — набор булевых функций, то эта задача обозначается SAT(F) (задача SAT(F) эквивалентна рассматриваемой далее задаче SAT([F] NC)). В ряде работ слабо отрицательные булевы функции называются хорновскими функциями, а слабо положительные булевы функции — антихорновскими функциями.

Среди зарубежных работ по рассматриваемой тематике следует выделить обзор [18] и монографию [21], поскольку в них приведены все основные результаты, полученные в англоязычной литературе до 2001 года. Новые продвижения даны в обзоре [22]. Среди отечественных работ по данной тематике основными являются, по-видимому, следующие статьи: [7, 6, 9]. Часть исследований в рассматриваемой области осуществлена в рамках НИР, проводимых Академией криптографии Российской Федерации.

Введем некоторые обозначения и определения.

• N — множество натуральных чисел, N0 = N {0};

• Bn — n-мерное пространство булевых векторов, n N0.

Определение 1 ([34]). Булева функция f(x1,..., xk) называется 1) 0-выполнимой, если f(0,..., 0) = 1;

2) 1-выполнимой, если f(1,..., 1) = 1;

3) мультиаффинной, если существует представление функции f в виде конъюнкции аффинных функций:

4) биюнктивной, если существует представление f в виде 2-КНФ:

5) слабо положительной, если существует представление f в виде следующей КНФ:

6) слабо отрицательной, если существует представление f в виде следующей КНФ:

7) 2-монотонной, если f представима в виде ДНФ одного из трех видов: xi1... xip, xj1... xjq, xi1... xip xj1... xjq, {i1,..., ip } Множество всех функций соответственно классов 1–7 обозначим 0-S, 1-S, A, Bi, WP, WN, 2-M. Формулы (1), (2), (3), (4), соответственно, для функций классов A, Bi, WP, WN будем называть приведенными представлениями. Множество A Bi, представляющее собой множество мультаффинных функций, являющихся произведениями аффинных функций от не более чем 2-х переменных, обозначим через 2-A.

Определение 2 ([7]). Пусть F = {fj (x1,..., xkj) | j J} — некоторый набор булевых функций, X = {xi | i N}. Символом [F] NC обозначим класс всевозможных систем уравнений, каждое уравнение которых имеет следующую структуру: правая часть равна 1, левая часть есть функция из набора F, переменные выбираются из множества X; другие ограничения на системы класса [F] NC не накладываются. Так, если F = {fj (x1,..., xk) | j = = 1,..., d} — конечный набор булевых функций, то системы класса [F] NC имеют вид:

где m N, fsi F, xsij X, i = 1, 2,..., m, j = 1, 2,..., k.

Классы систем уравнений вида [F] NC будем называть классами систем булевых уравнений с ограничениями на выбор функций и без ограничений на выбор неизвестных. При этом набор функций F будем называть порождающим набором функций для класса систем [F] NC.

Пусть R — некоторый класс систем булевых уравнений, S — система уравнений из класса R, sol(S) — множество решений системы S, len(S) — длина записи системы S. Определим две задачи, связанные с решением систем уравнений.

Определение 3. 1. Задача SAT(R) распознавания совместности систем класса R.

УСЛОВИЕ. Задана система S R.

ВОПРОС. Верно ли, что | sol(S)| > 0?

2. Задача ENU(R) определения числа решений систем класса R.

УСЛОВИЕ. Задана система S R.

ВОПРОС. Какова мощность множества sol(S)?

Определение 4 ([7]). Класс систем уравнений R назовем полиномиально решаемым, если 1) задача SAT(R) полиномиальна;

2) существуют алгоритм A и полином p(n) такие, что для всякой совместной системы S R алгоритм A последовательно, без повторений находит все решения системы S, причем сложность получения первого и каждого очередного t-ого решения, после получения (t 1)-го решения, не более p(len(S));

3) в ходе работы алгоритму A требуется память не более p(len(S)).

Заметим, что во всех зарубежных работах порождающий набор F считается конечным. При этом не требуется накладывать ограничения на вид записи функций набора F. В работах [7, 8] рассматривается, в том числе, случай бесконечного порождающего набора F.

Если набор функций F бесконечен, то считается, что функции набора F записаны или соответствующими приведенными представлениями, или многочленами Жегалкина, или ДНФ Объединяя результаты теоремы разделимости для задач SAT([F] NC) [34], теоремы разделимости для задач SAT([F] NC) при исключении тривиальных решений, все координаты которых равны между собой [7] (в работе [18] приведен аналог этой теоремы для случая конечного порождающего набора F), теоремы разделимости для задач ENU([F] NC) [5, 7] (в работе [19] доказан аналог этой теоремы для случая конечного порождающего набора F), и результаты о полиномиально решаемых классах систем булевых уравнений [7], получаем следующую общую картину, раскрывающую сложность решения систем уравнений из классов вида [F] NC.

Если все функции порождающего набора F являются мультиаффинными: F A (системы класса [F] NC равносильны системам линейных уравнений), то задачи SAT([F] NC) и ENU([F] NC) полиномиальны, класс систем уравнений [F] NC является полиномиально решаемым.

В случае, когда F A, но выполняется хотя бы одно из включений F Bi, F WP, F WN, возникают следующие интересные соотношения:

задача SAT([F] NC) полиномиальна, класс систем уравнений [F] NC является полиномиально решаемым, а задача ENU([F] NC) является #P-полной (труднорешаемой).

Если же F A, F Bi, F WP, F WN, то задача выяснения существования нетривиальных решений систем класса [F] NC является NP-полной, задача определения числа решений — #P-полная, класс систем уравнений [F] NC не является полиномиально решаемым (в предположении P = = NP).

Из приведенных результатов следует также следующий факт: в предположении P = NP множество полиномиально решаемых классов систем булевых уравнений вида [F] NC исчерпывается случаем выполнения хотя бы одного из включений В статье [29] изучается так называемая обратная задача к задаче распознавания совместности систем вида [F] NC. На языке классов систем булевых уравнений с ограничениями на выбор функций и без ограничений на выбор неизвестных результаты работы выглядят следующим образом.

Определим обратную задачу к задаче выполнимость (эту задачу обозначим INVSAT([F] NC)).

УСЛОВИЕ. Дано натуральное число n и множество M Bn.

ВОПРОС. Найдется ли система уравнений из класса [F] NC такая, что множество ее решений равно M?

Теорема 1 (Теорема разделимости для задачи INVSAT([F] NC), [29]). Если для набора функций F выполняется хотя бы одно из включений (5), то задача INVSAT([F] NC) имеет полиномиальную сложность, в противном случае эта задача является coNP-полной.

Рассмотрим задачу «Выполнимость с кванторами» [23]. Пусть имеется класс систем [F] NC, S — некоторая система из этого класса, а формула f(x1,..., xk) есть произведение формул левой части системы S. Рассмотрим выражение где Qi — кванторы, Qi {, }, i = 1,..., k. В формуле (6) все переменные являются связанными и ставится вопрос: формула (6) является истиной или ложью? Эту задачу обозначим QSAT([F] NC).

Теорема 2 (Теорема разделимости для задачи QSAT([F] NC), [23]).

Если для конечного набора функций F выполняется хотя бы одно из включений (5), тогда задача QSAT([F] NC) является полиномиальной.

В случае, когда не выполняется ни одно из включений (5), задача QSAT([F] NC) является PSPACE-полной.

Рассмотрим теперь задачу выполнимости в оптимизационной постановке. В работах [21, 30, 28, 22] рассмотрено понятие задачи оптимизации и класса NP проблем оптимизации (NPO). Класс полиномиально решаемых задач из NPO обозначается через PO. К классу проблем оптимизации относятся задачи:

• MAXSAT([F] NC) — задача нахождения вектора, выполняющего максимальное количество уравнений системы;

• MINSAT([F] NC) — задача нахождения вектора, минимизирующего количество не выполненных уравнений системы (данная задача эквивалентна задаче MAXSAT([F] NC) в случае, когда обе эти задачи полиномиальны, но отличается от нее при приближенном решении);

• MAXONES([F] NC) — задача нахождения решения системы максимального веса;

• MINONES([F] NC) — задача нахождения решения системы минимального веса.

Данные задачи могут быть сформулированы и во «взвешенном» варианте. В этом случае каждому уравнению для задач MAXSAT и MINSAT, либо каждой координате решения для задач MAXONES и MINONES приписывается неотрицательный «вес» и задача решается относительно суммарного «веса». В этом случае задачи обозначаются Weighted MAXSAT([F] NC), Weighted MINSAT([F] NC), Weighted MAXONES([F] NC) и Weighted MINONES([F] NC). В случае, когда какой-либо результат верен как для не взвешенного, так и для взвешенного варианта задачи, слово Weighted будем писать в скобках, например (Weighted) MAXSAT([F] NC), следуя вышеназванным работам.

Замечание. В работах [21, 28, 30], а также ряде других работ, оптимизационные задачи обозначаются как (Weighted) MAXSAT(F), (Weighted) MINSAT(F), (Weighted) MAXONES(F) и (Weighted) MINONES(F), что имеет тот же смысл, что и во введенных нами обозначениях.

Для задач оптимизации рассматриваются возможности приближенного решения задачи, то есть нахождения решения, в некотором смысле близкого к оптимальному. Введем понятие приближения для алгоритма решения задачи выполнимости в оптимизационной постановке (одной из четырех, указанных выше), которое согласуется с определением из работы [21].

Пусть S [F] NC — система уравнений от k неизвестных, m(S, x) — значение целевой функции (то есть соответствующей суммы весов уравнений либо неизвестных) на наборе значений x Bk, OPT(S) — оптимальное значение целевой функции m(S, x).

Определение 5 ([21]). Приближенный алгоритм A для решения NPO-задачи {(Weighted) MAXSAT([F] NC), (Weighted) MINSAT([F] NC), (Weighted) MAXONES([F] NC), (Weighted) MINONES([F] NC)} имеет аппроксимацию R(n), если для каждой системы S от k неизвестных, длина записи которой равна n, он находит вектор x Bk, удовлетворяющее соотношению:

Если полиномиальный алгоритм A имеет аппроксимацию 1, то он находит оптимальное решение. В этом случае он решает NPO-задачу с полиномиальной сложностью и задача оказывается в классе PO. В предположении PneNP для NP-полных задач таких алгоритмов не существует, однако для многих из них есть алгоритмы с приближением 1 + для любого > 0. В зависимости от того, какого вида функцию R(n) в (7) можно выбрать, выделяется ряд классов задач оптимизации. Если существует такое C > 0, что R(n) = C, то задача лежит в классе APX. Если R(n), то задача лежит в классе log-APX, а если R(n) ограничено полиномом от n то задача лежит в классе poly-APX.

Для задач оптимизации определяются два основных типа сводимости:

A-сводимость и AP-сводимость [21], в соответствии с которыми определяются понятия полноты. Данные сводимости определяют соответствия между системами из разных классов и устанавливают связь между значениями целевых функций. В соответствии с введенными понятиями в [21, 22] определяются понятия APX-полноты, log-APX-полноты и poly-APX-полноты.

В указанных работах сформулирована теорема разделимости для задачи (Weighted) MAXSAT([F] NC), в соответствии с которой эта задача либо полиномиальна, либо APX-полна, причем полиномиальность этой задачи исчерпывается случаем, когда выполняется одно из включений: F 0-S, F 1-S, F 2-M.

Классификация сложности для задачи (Weighted) MAXONES([F] NC) имеет более сложную структуру: задача (Weighted) MAXONES([F] NC) может быть полиномиальной, APX-полной, poly-APX-полной, разрешимой, но не аппроксимируемой, либо неразрешимой. В частности, если выполняется одно из включений F 1-S, F WP, F 2-A, то задача (Weighted) MAXONES([F] NC) — полиномиальна. Эта же задача APX-полна для F A, poly-APX-полна для случая F WN или F Bi.

Если же F 0-S, то задача поиска выполняющего вектора полиномиальна, но задача поиска решения положительного веса уже NP-трудна. Наконец, во всех остальных случаях задача поиска любого выполняющего решения для (Weighted) MAXONES([F] NC) NP-трудна. В тех же работах [21, 22] получена полная классификация сложности задач минимизации (Weighted) MINSAT([F] NC) и (Weighted) MINONES([F] NC).

Одной из важных подзадач проблемы Weighted MAXSAT([F] NC), является задача решения систем булевых уравнений с искаженной правой частью, в которой фактически необходимо найти вектор с максимальным суммарным весом выполняемых уравнений. Понятие систем уравнений с искаженной правой частью и некоторые методы их решения рассмотрены в работах [2, 3].

Ряд работ посвящен исследованию свойств булевых функций, порождающих полиномиально решаемые классы систем уравнений [F] NC — изучению мультиаффинных, биюнктивных, слабо положительных и слабо отрицательных булевых функций. В работах [34, 6] получены критерии мультиаффинности, биюнктивности, слабой положительности и слабой отрицательности булевых функций.

В [9] оценивается сложность задач распознавания мультиаффинности, биюнктивности, слабой положительности и слабой отрицательности при различных заданиях булевых функций, эти результаты важны при использовании отмеченных выше теорем разделимости (некоторые подобные результаты содержатся в монографии [21]). В работе [7] получены оценки числа мультиаффинных и биюнктивных функций, а в [1] получена оценка числа слабо отрицательных функций.

Свойства биюнктивных функций изучены также в работах [11, 13, 14].

В работе [13] показано, что задача минимизации 2-КНФ, представляТеоретико-сложностной подход...

ющей биюнктивную функцию является полиномиальной, в то время как в общем случае эта задача является труднорешаемой. Построен полиномиальный алгоритм минимизации 2-КНФ, представляющей биюнктивную функцию, описаны все минимальные 2-КНФ. В работе [14] исследована сложность распознавания эквивалентности биюнктивных функций, заданных своими 2-КНФ, относительно некоторых групп. Показано, что данная задача полиномиально эквивалентна задаче распознавания изоморфизма графов в случае симметрической группы и группы Джевонса и полиномиальна в случае группы сдвигов, рассмотрен ряд свойств групп инерции биюнктивных функций в данных группах. В статье [11] рассмотрена задача описания биюнктивных функций, инвариантных относительно заданной перестановки переменных. Задача полностью решена для полноцикловой подстановки.

Активно исследуются свойства слабо положительных и слабо отрицательных функций [15, 16, 24, 26, 31, 35]).

В работе [10] изучаются булевы функции, которые одновременно принадлежат двум или более классам из A, Bi, WP, WN. Асимптотическая формула для числа функций одного из возникающих подклассов булевых функций получена в работе [12].

В работах [17, 33] рассмотрена, в частности, следующая задача: имеются два набора функций F1 и F2, спрашивается — порождают они одинаковые классы систем уравнений [F1 ] NC, [F2 ] NC или разные?

В работах [22, 32] сформулированы открытые проблемы в рассматриваемой области. В частности, является открытым вопрос о NP-трудности APX-полных задач MAXSAT.

Литература [1] Алексеев В. Б. О числе семейств подмножеств, замкнутых относительно пересечения // Дискретная математика, 1989, т. 1, вып. 2, с. 129–136.

[2] Балакин Г. В. Введение в теорию случайных систем уравнений // Труды по дискретной математике, 1997, т. 1, с. 1–18.

[3] Балакин Г. В. Алгоритм нахождения множества наименьшей мощности, содержащего истинное решение с заданной вероятностью // Труды по дискретной математике, 2003, т. 7, с. 7–21.

[4] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.

Пер. с англ. // М.: Мир, 1982, 416 с.

[5] Горшков С. П. О сложности нахождения числа выполняющих наборов значений переменных в задаче «Обобщенная выполнимость» // Материалы девятой Всесоюзной конференции по математической логике, 1988, с. 38.

[6] Гизунов С. А., Носов В. А. О классификации всех булевых функций четырех переменных по классам Шефера // Обозрение прикладной и промышленной математики. Серия «Дискретная математика», 1995, т. 2, вып. 3, с. 440–467.

[7] Горшков С. П. Применение теории NP-полных задач для оценки сложности решения систем булевых уравнений // Обозрение прикладной и промышленной математики. Серия «Дискретная математика», 1995, т. 2, вып. 3, с. 325–398.

[8] Горшков С. П. О сложности задачи нахождения числа решений систем булевых уравнений // Дискретная математика, 1996, т. 8, вып. 1, с. 72–85.

[9] Горшков С. П. О сложности распознавания мультиаффинности, биюнктивности, слабой положительности и слабой отрицательности булевых функций // Обозрение прикладной и промышленной математики. Серия «Дискретная математика», 1997, т. 4, вып. 2, с. 216–237.

[10] Горшков С. П. О пересечении классов мультиаффинных, биюнктивных, слабо положительных и слабо отрицательных булевых функций // Обозрение прикладной и промышленной математики. Серия «Дискретная математика», 1997, т. 4, вып. 2, с. 238–259.

[11] Ролдугин П. В., Тарасов А. В. О числе биюнктивных функций, инвариантных относительно данной подстановки // Дискретная математика, 2002, т. 14, вып. 3, с. 23–41.

[12] Сачков В. Н. Разбиения с поглощениями и противоречивые разбиения множеств // Труды по дискретной математике, 2001, т. 4, с. 201–222.

[13] Тарасов А. В. О свойствах функций, представимых в виде 2-КНФ // Дискретная математика, 2001, т. 13, вып. 4, с. 99–115.

[14] Тарасов А. В. Некоторые свойства групп инерции булевых биюнктивных функций и индуктивный метод генерации таких функций // Дискретная математика, 2002, т. 14, вып. 2, с. 34–47.

[15] Arvind V., Biswas S. An O(n2) algorithm for the satisability problem of a subset of propositional sentences in CNF that includes all Horn sentences // Information Processing Letters, 1987, v. 24, no. 1, p. 67–69.

[16] Angluin D., Frazier M., Pitt L. Learning conjunctions of Horn clauses // Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990, p. 186–192.

[17] Bohler E., Hemaspaandra E., Reith S., Vollmer H. Equivalence problems for Boolean constraint satisfaction // Preprint, Reihe Institut fur Informatik Universitat Wurzburg, 2001, № 282, 16 p.

[18] Creignou N., Hermann M. Complexity of constraint satisfaction problems // Survey Document for CP 2001 Tutorial, 2001, 33 p.

[19] Creignou N., Hermann J. Complexity of generalized satisability counting problems // Information and Computation, 1996, v. 125, no. 1, p. 1–12.

[20] Creignou N., Hebrard J. On generating all satisfying truth assignments of a generalized CNF-formula // Theoretical Informatics and Applications, 1997, v. 31, no. 6, p. 499–511.

[21] Creignou N., Khanna S., Sudan M. Complexity classications of Boolean constraint satisfaction problems // SIAM Monographs on Discrete Mathematics and Applications, SIAM, Philadelphia, 2001, 106 p.

[22] Creignou N. Boolean CSP // Universite de la Mediterranee, 2006, 82 p.

[23] Dalmau V. Some dichotomy theorems on quantied Boolean formulas // Technical Report LSI-97-43-R, Departament LSI, Universitat Politecnica de Catalunya, 1997, 23 p.

[24] Dowling W. F., Gallier J. H. Linear-time algorithms for testing the satisability of propositional Horn formulae // J. Logic Programming, 1984, no. 3, p. 267–284.

[25] Furer M., Kasiviswanathan S. P. Algorithms for counting 2-SAT solutions and colouring with applications // Electronic colloquium on computational complexity, 2007.

[26] Hammer P., Kogan A. Horn functions and their DNFs // Information Processing Letters, 1992, v. 44, no. 1, p. 23–29.

[27] Jonnson D., Yannakakis M., Papadimitriou C. On generating all maximal independent sets // Information Processing Letters, 1988, v. 27, no. 3, p. 119–123.

[28] Kolaitis G. Constraint satisfaction, databases and logic // 2004, p. 1587–1595.

[29] Kavvadias D., Sideri M. The inverse satisability problem // SIAM J. on Computing, 1998, v. 28, no. 3, p. 152–163.

[30] Khanna S., Sudan M., Trevisan L., Williamson D. The approximability of constraint satisfaction problems // SIAM J. on Computing, 2001, v. 30, no. 6, p. 1863–1920.

[31] Minoux M. LTUR: a simplied linear-time unit resolution algorithm for Horn formulae and computer implementation // Information Processing Letters, 1988, v. 29, no. 1, p. 1–12.

[32] Open Problems List. Arising from MathsCSP, Workshop, Oxford, March 2006, Version 0.3, April 2006.

[33] Reith S. Generalized satisability problems // Dissertation zur Erlangung des naturwissenschaftlichen Doktorgrades der Bayerischen Julius-Maximilians-Universitat Wurzburg, 2001, 103 p.

[34] Schaefer T. Complexity of satisability problems // Proceedings of the 10th Annual ACM Symposium on theory of computing machinery, 1978, p. 216–226.

[35] Yamasaki S., Doshita S. The satisability problem for a class consisting of Horn sentences and non-Horn sentences in proportional logic // Information and Control, 1983, v. 59, no. 1–3, p. 1–12.

Линейный алгоритм, определяющий по вектору значений булевой функции, задается ли она полиномом фиксированной степени Каждая булева функция однозначно задается полиномом по mod 2.

Степенью булевой функции называется степень задающего ее полинома.

В криптографии важную роль играют булевы функции фиксированных степеней, например, степени 1 или 2.

Пусть булева функция записана вектором своих значений с N = 2n координатами, где n — число переменных функции. Известно, что по вектору значений булевой функции ее полином можно найти со сложностью O(N log N) [1]. Поэтому при отыскании алгоритмов, распознающих свойства полиномов булевых функций по их векторам значений, имеет смысл рассматривать только алгоритмы, имеющие меньшую по порядку сложность.

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

Пусть B = {0, 1}, V n — множество векторов длины n с координатами из множества B. Булевой функцией назовем отображение Множество всех булевых функций, зависящих от n переменных, обозначим как Fn.

Монотонной элементарной конъюнкцией назовем произведение попарно различных переменных без отрицаний. Рангом монотонной элементарной конъюнкции назовем число ее переменных. Будем считать 1 вырожденной монотонной элементарной конъюнкцией ранга 0. Каждую булеву функцию однозначно можно записать полиномом вида l Xi, где Xi — попарно различные монотонные элементарные конъюнкции, суммирование ведется по mod 2. Степенью полинома называется наибольший ранг его слагаемых.

Работа выполнена при поддержке РФФИ, гранты 06-01-00438 и 07-01-00444.

Линейный алгоритм, определяющий по вектору значений...

Будем говорить, что функция f(x1,..., xn) принадлежит классу Cm, m = 0, 1, 2,..., если она задается полиномом степени не выше m. Очевидно, что класс C0 содержит только константы 0 и 1, класс C1 совпадает с классом L линейных функций.

Назовем производной функции f(x1,..., xn) по переменной xi функцию fxi (x1,..., xn), равную f(x1,..., xi1, 0, xi+1,..., xn) f(x1,..., xi1, 1, xi+1,..., xn).

Теорема 1. Функция f(x1,..., xn) принадлежит классу Cm, m 1, тогда и только тогда, когда для каждой переменной xi, i = 1,..., n, функция fxi (x1,..., xn) принадлежит классу Cm1.

Доказательство. Следует из определения производной и однозначности представления булевой функции полиномом.

Пусть булева функция f(x1,..., xn) задана вектором f своих значений на наборах, перечисленных в лексикографическом порядке. Число координат вектора f равно N = 2n.

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

Теорема 2. Существует алгоритм, который по вектору f со сложностью O(N) определяет, является ли функция f(x1,..., xn) линейной, и в случае положительного ответа строит ее полином.

Доказательство. Рассмотрим следующий алгоритм.

fi (xi,..., xn) := f(x1,..., xn);

p(x1,..., xn) := f(0,..., 0).

Начало цикла.

1. Строим производную fi xi (xi,..., xn): делим вектор fi пополам и суммируем покоординатно. При этом будет затрачено 2ni+1 операций.

• fxi (xi,..., xn) 0, то p(x1,..., xn) оставляем без изменения;

• иначе — алгоритм заканчивает работу и ответ «Функция нелинейна».

3. i := i + 1, fi (xi,..., xn) = fi1 (0, xi,..., xn),. Для построения вектора fi требуется 2ni+1 операций.

• i > n, то алгоритм заканчивает работу, ответ «Функция линейна»

Корректность предложенного алгоритма следует из теоремы 1.

Подсчитаем сложность алгоритма. Она равна Теорема 3. Пусть задано число m 1. Существует алгоритм, который по вектору f со сложностью O(N) определяет, принадлежит ли функция f(x1,..., xn) классу Cm, и в случае положительного ответа строит ее полином.

Доказательство. Построим требуемый алгоритм Am индуктивно.

Базис индукции. Пусть m = 1. Тогда в качестве алгоритма A1 рассмотрим алгоритм, описанный в теореме 2. Его сложность равна 2 · 2n.

Индуктивный переход. Пусть алгоритм уже Am1 построен и его сложность равна cm1 · 2n, где cm1 — некоторая константа. Рассмотрим в качестве алгоритма Am следующий:

fi (xi,..., xn) := f(x1,..., xn);

P(x1,..., xn) := f(0,..., 0).

Начало цикла.

1. Строим производную fi xi (xi,..., xn): делим вектор fi пополам и суммируем покоординатно. При этом будет затрачено 2ni+1 операций.

2. При помощи алгоритма Am1 проверяем, принадлежит ли функция • иначе — алгоритм заканчивает работу и ответ «Функция не принадлежит классу Cm ».

Линейный алгоритм, определяющий по вектору значений...

На шаге 2 мы затратим cm1 · 2ni+1 операций.

3. i := i + 1, fi (xi,..., xn) = fi1 (0, xi,..., xn). Для построения вектора • i > n, то алгоритм заканчивает работу, ответ «Функция принадлежит классу Cm » и ее полином записан в P(x1,..., xn);

• иначе — переход на начало цикла.

Корректность предложенного алгоритма следует из теоремы 1.

Подсчитаем сложность алгоритма. Она равна где cm — некоторая константа. Таким образом, cm = 2 · (cm1 + 1), c1 = 2.

Нетрудно подсчитать, что cm = 2 · 2m. Следовательно, сложность алгоритма равна (2 · 2m) · 2n = O(N), так как число m — фиксировано.

Литература [1] Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. М.: ФИЗМАТЛИТ, 2004.

О метриках, изометричных относительно 1. Введение Одной из актуальных задач в криптографии является проблема приближения функций функциями из заданного класса, в частности, аппроксимация двоичных функций линейными и мономиальными функциями. При этом естественно возникающий вопрос состоит в том, каким образом измерить расстояние между функций. Если класс функций «хорош» относительно одной меры, то будет ли он также хорош относительно другой? Обычно в качестве такой меры между булевыми функциями используется метрика Хемминга. В работе [1], посвященной аппроксимации функций над произвольным полем GF(2l), в качестве основного параметра, характеризующего степень близости функции и её статистического аналога, используется функция «согласия». Эта функция отличается нормировкой, от введённой в работе [2] функции «близость». Кроме того, она не является метрикой.

Представляют интерес свойства функций относительно различных метрик.

В частности, исследование свойств аффинных функций и бент-функций (как функций максимально далёких от множества аффинных функций).

В данной работе исследуются метрики, группа изометрий которых содержит группу сдвигов. К таким метрикам относится и метрика Хемминга.

В качестве примера показано существование метрик в этом множества, относительно которых аффинные функции находятся на разном расстоянии друг от друга. Кроме того, приведены такие метрики, что функции, максимально далекие от аффинных функций относительно метрики Хемминга, не все являются такими относительно метрик из рассматриваемого класса.

Обозначения: N0 — множество натуральных чисел с нулем, n N0, n 2; Vt — векторное пространство t-мерных двоичных векторов; t — метрика Хемминга на Vt ; Fn — множество всех двоичных функций от n переменных; : Vn Z2n — (естественное) взаимно однозначное соотРабота выполнена при поддержке гранта Президента РФ НШ 4.2008.10.

О метриках, изометричных относительно группы сдвигов = (0,..., 0, 1, 0,..., 0), j {1, t}; a, b = a, a + 1,..., b, a < b; i(t) = { Vt | | = i}, i {1, t}; Fn = {f : Vn {0, 1}}; AFn — множество всех аффинных функций из Fn ; BFn — множество всех бент-функций из Fn ;

Если размерность t пространства Vt понятна из контекста, то у метрики t, множества i(t) и вектора j,t символ «t» будем опускать.

2. Свойства метрик, изометричных относительно группы сдвигов Для описания связей между классами метрик удобны понятия подметрики и надметрики данной метрики. Отметим, что понятие подметрики метрики Хемминга предложено Б. А. Погореловым [3], а все групповые подметрики метрики Хемминга описаны в работе [4]. Пусть |X| = n и — метрика на множестве X.

Определение 1. Метрика : X X N0, удовлетворяющая для любых,,, X свойствам:

называется подметрикой метрики.

Определение 2. Метрика : X X N0, удовлетворяющая для любых,,, X свойствам:

называется надметрикой метрики.

Очевидно, что метрика является подметрикой метрики. Обозначим через M+ множество всех метрик на Vn, группа изометрий которых содержит группу сдвигов, и имеющих вид Очевидно, что для таких метрик справедливо равенство (, + ) = = (, + ) для всех,, Vn. Произвольная метрика M+ од- n нозначно задаётся множествами Aj () = а любая (d + 1)-значная метрика M+ может быть представлена в виде где {A1 (),..., Ad ()} — некоторое разбиение Vn \ {0}.

Назовём максимальной метрикой множества M M+, если не сущеn ствует у метрики надметрики из множества M, отличной от метрики.

Опишем все максимальные метрики множества M+, являющиеся надn метриками метрики Хемминга. Для этого приведём индуктивный способ построения некоторых метрик.

Обозначим Vn,i = j j {1, n} \ {i}, i {1, n}.

Лемма 1. Пусть n 3, d 2, r — произвольное число из {1, n} и — произвольная (d + 1)-значная метрика из M+, — произn вольный ненулевой вектор из Vn \ Vn,r. Тогда функция : Vn Vn N0, заданная условиями является 2(d + 1)-значной метрикой.

Лемма 1 позволяет описать все максимальные метрики множества M+. n Для произвольных t, t 1, линейно независимых векторов 1,..., t из Vn обозначим Vn ( 1,..., t) = 1,..., t. Ясно, что Vn ( 1,..., t) Vt.

Утверждение 1. При n 2 каждому упорядоченному набору ( 1,..., n) линейно независимых векторов из Vn соответствует максимальная 2n -значная метрика n,( 1,..., n) множества M+, задан- n ная условиями:

О метриках, изометричных относительно группы сдвигов если если + Vn ( 1,..., t1, t), 2 t n. Кроме того, любая максимальная метрика множества M+ совпадает с метрикой n, 1,..., n для некоторого набора ( 1,..., n) Vn, а число максимальных метрик множества Mn равно (2 1) (2 2)... 2n 2n1.

Опишем максимальные метрики множества M+, являющиеся надметn риками метрики Хемминга.

Следствие 1. Пусть выполнены условия утверждения 1, а упорядоченный набор ( 1,..., n) линейно независимых векторов из множества M+, являющаяся надметрикой метрики Хемминга. Чисn ло таких максимальных 2n -значных надметрик метрики Хемминга равно Приведём одно свойство, позволяющее сводить исследование всех максимальных метрик множества M+ к одной.

Утверждение 2. Пусть ( 1,..., n), (1,..., n) — два различных базиса пространства Vn и GLn, : i i для всех i 1, n.

Пусть также 2 d 2n 1 и 1,..., n — (d + 1)-значная подметрика максимальной метрики n, 1,..., n множества M+. Тогда функция 1,...,n : Vn Vn N0, заданная условием является (d + 1)-значной подметрикой метрики n,1,...,n. Кроме того, Aj2 (1,...,n ) = (Aj2 ( 1,..., n)), Aj1 (n,1,...,n ) = (Aj1 (n, 1,..., n)) для всех Таким образом, каждой подметрике метрики n, 1,..., n однозначно соответствует подметрика метрики n,1,...,n. Кроме того, все максимальные метрики множества M+ линейно эквивалентны. Перечислим все (n + 1)-значные подметрики максимальных метрик множества M+ линейно эквивалентные метрики Хемминга и являющиеся подметриками надметрик метрики Хемминга.

Следствие 2. Пусть 1,..., n — базис пространства Vn таков, N0, заданная условием является (n + 1)-значной подметрикой 2n -значной надметрики n, 1,..., n метрики Хемминга.

3. Свойства аффинных и бент-функций относительно метрик множества M+ Приведём примеры метрик из множества M+, относительно которых аффинные функции находятся на разном расстоянии.

Для произвольных функций f2, f1 Fn обозначим через f2 + f1 функцию из Fn, заданную условием (f2 + f1) ( ) = f2 ( ) + f1 ( ) для всех Vn.

Обозначим также f = f(0),..., f(1) вектор значений функции f Fn.

Утверждение 3. Пусть m = 2n, r 1, m задана равенством (f1, f2) = Тогда расстояние между аффинными функциями f1, f2 AFn равно Утверждение 4. Пусть m = 2n и a1, a2 — произвольные аффинные функции, ai 0, 1, i {1, 2}. Пусть также базис 1,..., m пространства Vm таков, что О метриках, изометричных относительно группы сдвигов Fn 1, m задана равенством Тогда существуют аффинные функции f1, f2 AFn, для которых Приведём некоторые (2n + 1)-значные подметрики максимальных метрик множества M+, которые «разделяют» множество бент-функций.

B = {f BFn | Hr (f)}, где V2n, r = 2n1 2n/21.

Утверждение 5. Пусть Тогда dAF () = 1 и dAF () < dAF () для любых функций f1 B, f B (2).

Литература [1] Кузьмин А. С., Нечаев А. А., Шишкин В. А. Бент- и гипербент-функции над конечным полем // Труды по дискретной математике. 2007. Т. 10. С. 97–122.

[2] Солодовников В. И. Бент-функции из конечной абелевой группы // Дискретая математика. 2002. Т. 14, № 1. С. 99–113.

[3] Погорелов Б. А. Подметрики метрики Хемминга и теорема А. А. Маркова // Труды по дискретной математике. 2006. Т. 9.

[4] Погорелов Б. А., Пудовкина М. А. Подметрики Хемминга и их группы изометрий // Труды по дискретной математике. 2008. Т. 11.

О некоторых свойствах совершенно уравновешенных булевых функций 1. Основные определения и обозначения Пусть F2 — поле Галуа из двух элементов, Vn = Fn — пространство наборов длины n N над полем F2. Будем обозначать через Fn — множество булевых функций от n переменных {x1, x2,..., xn }. Крайними переменными функции f Fn будем называть x1 и xn. Через n будем обозначать подмножество функций из Fn, существенно зависящих от обеих крайних переменных. Пусть m N. Рассмотрим систему булевых уравнений:

Обозначим для f Fn через f отображение из Vm+n1 в Vm вида:

f (x1, x2,..., xm+n1) = Определение 1 ([1]). Булева функция f Fn называется совершенно уравновешенной, если соотношение выполняется для любого m N и любого y Vm. Множество совершенно уравновешенных функций из Fn обозначим PBn.

Замечание 1. Легко видеть (см. [1]), что если функция линейна хотя бы по одной из крайних переменных, то она является совершенно уравновешенной. Обозначим множество функций из Fn, линейных по первой переменной, Ln, а множество функций из Fn, линейных по последней переменной, Rn.

2. Предварительные результаты Отметим преобразования множества Fn, оставляющие инвариантным множество PBn (см. [1]):

— последовательность случайных векторов с распределением для любых (a1,..., am+n1) Vm+n1. Случайный вектор Ym = f (Xm) распределен равномерно для любого m N тогда и только тогда, когда f — совершенно уравновешенная функция.

Теорема 2 ([1]). Булева функция f Fn является совершенно уравновешенной тогда и только тогда, когда не существует двух двоичных последовательностей таких, что Для пары натуральных чисел m, k рассмотрим отображение m,k из Fm Fk в Fm+k1 вида где f(x1,..., xm+k1) = g [h] (x1,..., xm+k1) = Для этой конструкции справедливо следующее утверждение.

Теорема 3 ([3]). Пусть g Fm, h Fk. Функция f = g [h] Fm+k совершенно уравновешена тогда и только тогда, когда функции g и h совершенно уравновешены.

Утверждение теоремы 3 позволяет строить булевы функции из PBn, не входящие в классы Ln и Rn.

Для любой f n обозначим f (x1,..., xN) f(xN n, xN n1,..., xN 1), где = ( 1,..., n) — набор неотрицательных целых чисел, такой, что 1 = = 0, i {1,..., n 1} i+1 > i, N = n + 1. Далее будем рассматривать только такие наборы, определяющие точки входа в фильтрующем генераторе.

О некоторых свойствах совершенно уравновешенных...

В работе [4] Голичем было сформулировано и доказано (в одну сторону) следующее утверждение о совершенно уравновешенных булевых функциях:

Теорема 4 ([4]). Пусть на вход кодирующего устройства с функцией f поступает случайная последовательность, биты которой независимы и принимают значения 0 и 1 с вероятностями 1/2. Тогда выходная последовательность кодирующего устройства обладает тем же свойством при любом выборе набора тогда, когда f линейна по крайней существенной переменной.

Утверждение теоремы 4 является тривиальным следствием теоремы и замечания 1. В работе [4] было также высказано предположение, что утверждение теоремы 4 верно и в обратную сторону («и только тогда»), однако доказательства предложено не было. Воспользуемся аппаратом совершенно уравновешенных функций, переформулируем и докажем предположенное утверждение.

3. Основные результаты Теорема 5. Для любой функции n \ (Ln Rn) существует набор такой, что f PBN.

Доказательство. Здесь приведем доказательство, предполагающее, что f не зависит ни от одной переменной линейно.

Выберем набор следующим образом: 1 = 0, i {1,..., n 1} i+1 > > 2 i, и докажем разрешимость следующей системы:

Все равенства, в которые не входит явным образом xN 1 и zN 1 выполняются автоматически, остается разрешить следующую систему:

Каждое из уравнений этой системы имеет решение ввиду того, что f не зависит линейно ни от одного из своих аргументов. Покажем, что любые два уравнения этой системы — j-е и l-е — независимы. Требуется показать:

Очевидно, достаточно показать, что i {1,..., n 1} j i k i Таким образом, верны неравенства (9), а значит, система (8) состоит из n независимых уравнений, каждое из которых разрешимо. Поэтому системы (8) и, соответственно, (7) совместны, что, по теореме 2, означает f PBN, что и требовалось доказать.

Здесь приведено доказательство для случая функции, не зависящей линейно ни от одного аргумента. Для общего случая доказательство принципиально такое же — мы выбираем набор определенного вида, а затем по теореме 2 доказываем отсутствие совершенной уравновешенности f — но оно намного больше по объему из-за необходимости особым образом учитывать линейные переменные функции f.

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

Определение 2 ([5]). Булева функция f Fn называется функцией с правым барьером длины b, если система уравнений О некоторых свойствах совершенно уравновешенных...

имеет решение, а система f(yb, yb+1,..., yb+n1) = f(zb, zb+1,..., zb+n1), решений не имеет.

Булева функция f Fn называется функцией с левым барьером длины b, если f 2 (x1,..., xn) f(xn,..., x1) является функцией с правым барьером длины b.

Булева функция f Fn имеет барьер, если она имеет правый или левый барьер, или оба сразу. При этом длиной барьера функции называется соответственно длина правого барьера, левого барьера, или меньшая из длин барьеров.

Теорема 6. Наличие барьера у функции является достаточным, но не необходимым условием соверщенной уравновешенности функции.

Доказательство. Если у функции есть правый или левый барьер, то непосредственно из определения барьера, а также теоремы 2 вытекает совершенная уравновешенность функции.

Покажем, что существуют совершенно уравновешенные функции без барьера. Для этого рассмотрим функцию где g(x1, x2, x3) = x1 x2 x3 x2 x3, g 2 (x1, x2, x3) g(x3, x2, x1). Функция g имеет левый барьер длины k = 1, следовательно, g, g 2 PB3. Используя утверждение теоремы 3, получим: f PB 5. Чтобы доказать отсутствие барьеров у функции f, рассмотрим две пары последовательностей:

... (0, 0, 1, 1, 1, 1, 1, 0, ) (0, 0, 1, 1, 1, 1, 1, 0, ) (0, 0, 1, 1, 1, 1, 1, 0, )0, 0, 0, 1, 0,... (1, 1, 1, 0, 0, 0, 1, 1, ) (1, 1, 1, 0, 0, 0, 1, 1, ) (1, 1, 1, 0, 0, 0, 1, 1, )0, 1, 0, 1, 0, Для любого наперед заданного k > 0 продолжим пару (12) до длины большей k + 3, воспользовавшись ее периодичностью. Затем, подставив её в системы уравнений (10) и (11), убеждаемся, что обе системы совместны, то есть, никакое k не удовлетворяет определению 2, — следовательно, у функции f нет правого барьера. Аналогично, воспользовавшись парой (13), убедимся в отсутствии у f левого барьера. Следовательно, f PB5 является функцией без барьера.

Анализируя системы (10) и (11) из определения барьера, можно доказать следующее утверждение, позволяющее классифицировать функции с правым (левым) барьером:

Теорема 7 ([5]). Пусть f Fn — функция с правым (левым) барьером длины b, b < n, а g Fnb — произвольная функция. Тогда функция h(x1,..., xn) = f(x1,..., xn) g(x1,..., xnb) (соответственно, h(x1,..., xn) = f(x1,..., xn) g(xb+1..., xn)) тоже является функцией с правым (левым) барьером длины b.

Длина барьера — величина, определенным образом характеризующая обратимость отображения f, порожденного совершенно уравновешенной функцией f. Из общих соображений понятно, что в множестве PB n наибольший интерес представляют функции с большой длиной барьера, а также функции без барьера.

При доказательстве теоремы 6 мы доказали, что взятая нами композиция функций g 2 [g] является функцией без барьера. Можно показать, что g не имеет правого барьера, а g 2 не имеет левого барьера. Возникает вопрос: а всегда ли предложенный способ композиции функций g [h] сохраняет наличие и отсутствие правых и левых барьеров? Ответ на этот вопрос дает следующая теорема.

Теорема 8. Пусть h Fk, g Fm, f = g [h], а длины правых (левых) барьеров функций h, g, f равны, соответственно b, c, d. Тогда выполнено соотношение max{b, c} d b + c 1, где оба неравенства могут обращаться, а могут не обращаться в равенства. Обозначим основные идеи доказательства. Неравенства d b и d b + c 1 как для случая конечных b, c, d, так и в случае, если какие-то из функций не имеют барьеров, доказываются с помощью анализа систем, которые получаются из (10), (11) подстановкой вместо аргументов функции g значений функции h на соответствующих наборах. По полученным системам и определяются неравенства относительно b и b + c 1, накладываемые на d. Чтобы доказать неравенство d c, мы пользуемся 1 Здесь мы формально считаем функцию без правого (левого) барьера функцией с правым (левым) барьером равным +.

О некоторых свойствах совершенно уравновешенных...

леммой 1, доказательство которой опирается только на определение совершенно уравновешенной функции.

Лемма 1. Если f PBn, то для любого натурального u, для любых наборов z0, z1 Vu существуют натуральное число r и наборы x, y Vr+n1, z Vru такие, что выполнена система Для завершения доказательства теоремы 8 рассматриваются функции с правыми барьерами длины b = c = 3. Несложно проверить непосредственно, что у функций f2 [f2 ], f1 [f1 ] и f1 [f2 ] длины правых барьеров равны d = 3,d = 4,d = 5 соответственно. Во всех случаях max{b, c} = = 3, b + c 1 = 5, то есть d принимает все три возможных значения между max{b, c} и b + c 1, что и завершает доказательство теоремы.

Приведем пример способа построения совершенно уравновешенных функций без правого барьера:

Лемма 2. Функции вида f = x1 xm xm +1... xm1 h1 (xm1 +1, xm1 +2,..., xmk ) где hi — элементарные мономы, а k — нечетное, являются совершенно уравновешенными функциями без правого барьера.

Доказательство. Все такие функции линейны по первой переменной, поэтому, как следует из замечания 1, они являются совершенно уравновешенными. Докажем, что у них отсутствует правый барьер. Возьмем произвольную функцию f указанного вида. Для любого сколь угодно большого b рассмотрим следующую пару последовательностей:

Подставляя эту пару последовательностей в систему из определения 2, получим, что у f нет правого барьера длины b или меньше. Это верно для сколь угодно большого b, поэтому у f нет правого барьера.

Теперь с помощью леммы 2 и теоремы 8 мы можем описать крупный класс совершенно уравновешенных функций без барьера.

Теорема 9. Пусть f1, f2 имеют вид (14) или получены из функций вида (14) с помощью преобразования Тогда функции вида f1 [f2 2 ] и f1 2 [f2 ] являются совершенно уравновешенными функциями без барьера.

Функции, полученные с помощью теоремы 9, обладают всеми положительными криптографическими качествами совершенно уравновешенных булевых функций, в частности, фильтрующие генераторы с такими функциями устойчивы к оптимальной корреляционной атаке Андерсона [6]. При этом у них отсутствует нежелательное для фильтрующей функции свойство барьера конечной длины, которое позволяет эффективно находить прообраз f. Поэтому к фильтрующим генераторам с такими функциями неприменима инверсионная атака Голича [4], как и всякая другая атака, использующая наличие у фильтрующей функции барьера конечной длины.

Литература [1] Сумароков С. Н. Запреты двоичных функций и обратимость для одного класса кодирующих устройств // Обозрение прикладной и промышленной математики.

1994. Т. 1, вып. 1. С. 33–55.