автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.19, диссертация на тему:Алгебраические, комбинаторные и криптографические свойства параметров аффинных ограничений булевых функций

Московский государственный университет имени М. В. Ломоносова

0034Б1747

На правах рукописи

Буряков Михаил Леонидович

Алгебраические, комбинаторные и криптографические свойства параметров аффинных ограничений булевых функций

Специальность 05.13.19 — методы и системы защиты информации, информационная безопасность

Автореферат диссертации на соискание ученой степени, кандидата физико-математических наук' 2

/Пг> ¿00'

У

Москва - 2009

003461747

Работа выполнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова.

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

кандидат физико-математических наук, старший научный сотрудник Логачев Олег Алексеевич.

доктор физико-математических наук, ведущий научный сотрудник Фомичев Владимир Михайлович (Институт проблем информатики РАН)

кандидат физико-математических наук, старший научный сотрудник Кузнецов Юрий Владимирович (НИИ системных исследований РАН).

ФГУП «НИИ Автоматики».

Защита диссертации состоится 25 февраля 2009 г. в 16:45 на заседании диссертационного совета Д 501.002.16 при Московском государственном университете имени М. В. Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д. 1, Московский государственный университет имени М. В. Ломоносова, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан «23» января 2009 г.

Ученый секретарь диссертационного совета доктор физико-математических наук ' Корнев А. А.

Общая характеристика работы

Актуальность темы. Обеспечение информационной безопасности является одной из важнейших государственных задач наряду с обеспечением обороноспособности страны, развитием экономики, образования и здравоохранения. Основополагающим документом, который регламентирует политику России в области информационной безопасности, является Доктрина информационной безопасности Российской Федерации1, утвержденная в сентябре 2000 года Президентом РФ. Секция Научного совета при Совете Безопасности РФ на основе Доктрины разработала Перечень приоритетных проблем научных исследований, связанных с информационной безопасностью2. Он включает в себя направления в областях развития общей теории обеспечения информационной безопасности и, в частности, защиты информации различными методами, в том числе с использованием криптографических механизмов, разработку методов и средств защиты в системах электронного документооборота, включая использование электронной цифровой подписи. Одним из наиболее важных направлений в Перечне является «разработка фундаментальных проблем теоретической криптографии и смежных с ней областей математики» (п. 54 Перечня).

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

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

Доктрина информационной безопасности Российской Федерации. В сб. «Научные и методологические проблемы информационной безопасности». Под ред. В. П. Шерстюка, сс. 149-197 — М.: МЦНМО, 2004.

2Приоритетные проблемы научных исследований в области информационной безопасности Российской Федерации. Математика и безопасность информационных технологий. Материалы конференции в МГУ 23-24 октября 2003 г., сс. 21-28 - М.: МЦНМО, 2004.

онирования различных дискретных устройств. Необходимость изучения и решения систем булевых уравнений возникает в ряде задач теории конечных автоматов, теории кодирования и криптологии. В частности, в криптологии это направление относится к синтезу и анализу традиционных криптографических систем с секретным ключом. В ходе такого исследования системы нелинейных булевых уравнений связывают элементы неизвестного ключа криптосистемы с известными данными. Основные криптографические примитивы, являющиеся источниками систем булевых уравнений в криптоанализе, — это комбинирующие генераторы (рис. 1) и фильтрующие генераторы (рис. 2) потоковых шифров (РСЛОС-г, г — 1,..., п, РСЛОС — регистры сдвига с линейными обратными связями; / — комбинирующая (фильтрующая) булева функция от п переменных; ^¿(у), г — 1,2,..., п, д(у) — полиномы обратных связей регистров сдвига), а также Б-боксы блоковых шифров и раундовые преобразования, используемые в хэш-функциях3.

zt — /

Рис. 1: комбинирующий генератор 9 (v) [

Рис. 2: фильтрующий генератор

Задача решения произвольной системы нелинейных булевых уравнений является -/VF-трудной. На настоящее время для решения подобных систем в общем случае не существует алгоритма со сложностью, по порядку меньше, чем где п — число неизвестных в системе. Вместе

'Menezea А., P. van Oorschot, Vanstone S. Handbook of applied cryptography. CRC Press Inc., 1997

si(v) I PCJIOC-l S2(v) I РСЛОС-2

. JO

S„(v) I PCJIOC-rt j——

PCJIOC

... X«

/

Zt — f fx' Ej ...

с тем, анализ конкретных систем уравнений для криптосистем с секретным ключом (при п ~ 100-200 и более) является актуальной научной проблемой.

В криптоанализе разработаны различные подходы к решению нелинейных систем булевых уравнений. В ряде случаев для нахождения решения системы используются теоретико-вероятностные, статистические, и теоретико-кодовые методы4,5,6'7. При другом подходе предлагается погружать систему уравнений в действительную область и находить ее решение с помощью соответствующей системы псевдобулевых неравенств'9. Кроме того, в случае использования итераций в процессе шифрования возможна линеаризация исходной криптографической задачи (например, нахождения ключа) с использованием определенных степеней итерируемого отображения, которые представляют собой аффинные отображения10. Рассматриваются алгебраические методы решения систем нелинейных булевых уравнений над конечными полями на основе базисов Гребнера11.

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

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

4Siegenthaler Т. Correlation-immunity of nonlinear combining Junctions for cryptographic applications. IEEE TVans. ou Information Theory V. IT-30.5, pp. 776-780, 1984.

5Meier W., Staffelbach O. Fast correlation attacks on certain stream ciphers. Journal of Cryptology V. 1, № 3, pp. 159-1762,1989.

6Chepyzhov V., Smeets B. On a fast correlation attacks on certain stream ciphers. Advances in Cryptology: EUROCRYPT'91, LNCS V. 547, pp. 176-185, Springer-Verlag, 1991.

7Chepyzhov V., Johansson Т., Smeets B. A simple algorithm for fast correlation attacks on stream ciphers. Advances in Cryptology: FSE'2000, LNCS V. 1978, pp. 181-195, Springer-Verfag, 2000.

8Г. В. Балакин, В. Г. Никонов. Методы сведения булевых уравнений к системам пороговых соотношений. Обозрение прикладной и промышленной математики., т. 1, вып. 3, сс. 389-401, 1994.

9К. К. Рыбников, А. С. Хохлушин. О взаимосвязях различных алгоритмических методов погружения множества решений системы булевых уравнений в действительную область. Вестник МГУЛ. Лесной вестник, № 5 (25), сс. 189-194, 2002.

10В. М. Фомичев. Дифференциация элементов в конечных группах и в автоматах по заданным признакам, определяющим криптографические свойства систем защиты информации. Диссертация на соискание учеиой степени доктора физико-математических наук, специальность 05.13.19, Москва, 2006.

uArs G., Faugfere J.-C., Imai H., Kawazoe M., Sugita M. Companion between XL and Grobner basis Algorithms. Advances in Cryptology: ASIACRYPT'04, LNCS V. 3329., pp. 338-353, Springer-Verlag, 2004.

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

В 2003 году была рассмотрена12 атака по открытому и шифрованному тексту на комбинирующий генератор (см. рис. 1) потокового шифра с угрозой вскрытия ключа и предложен метод реализации этой атаки. Этот метод основан на частичном опробировании ключей и использующий ранговый критерий отбраковки ложной части опробуемого ключа. При этом последовательно перебираются возможные начальные заполнения (ключи) определенной, специальным образом подобранной части регистров сдвига с линейными обратными связями PCJ10C-ir, г = 1,..., s. (см. рис. 1). Среди выходных последовательностей этих регистров находятся такты, задающие подходящие значения переменных х^,..., а?,-, булевой функции / и определяющие ее аффинные ограничения. Подходящие фиксации (значения переменных) совместно с известными элементами выходной последовательности в этих тактах определяют линейные системы уравнений, которые используются для нахождения начальных состояний опробуемых регистров.

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

Уровень аффинности (1а (/)) булевой функции / определяется как минимальное число фиксаций переменных этой функции, переводящих исходную функцию в аффинную функцию от меньшего числа переменных. Понятие частичного уровня аффинности (1а° (/)) определяет минимальное число нулевых фиксаций переменных булевой функции /, превращающих исходную функцию в аффинную. Обобщенный уровень аффинности (£а (/)) булевой функции / определяется как минимальная разность между числом переменных функции / и размерностью плоскости (смежного класса по подпространству), ограничение на которую

120. А. Логачев, А. А. Сальников, В. В Ященко. Корреляционная иммунность и реальная секретность, Математика и безопасность информационных технологий. Материалы конференции в МГУ 23-24 октября 2003 г., сс. 165-170 — М.: МЦНМО, 2004.

совпадает с аффинной функцией. Различные виды уровня аффинности связаны между собой соотношением

£а(/)<1а(/)^1а°(/)-

Естественным образом указанные выше параметры линеаризации могут быть распространены и на булевы отображения.

Уровень аффинности 1а (/) комбинирующей функции / (рис. 1) определяет (наряду с другими параметрами) трудоемкость описанного выше метода нахождения ключей.

Другим важным направлением исследований является изучение криптографических свойств булевых функций и связей между этими свойствами. Достаточное число математически содержательных соотношений между параметрами, описывающими различные (в том числе и конфликтующие) криптографические свойства, облегчает решение сложной оптимизационной задачи выбора булевых функций (отображений) при синтезе стойких криптосистем. Примерами могут служит изучение пар криптографических свойств «корреляционная иммунность-нелинейность»13,14, «корреляционная иммунность-алгебраическая иммунность»15, «нелинейность-алгебраическая иммунность»16,17, а также использование локальных аффинностей для изучения криптографических свойст булевых функций18,19,20'21.

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

"ю. В. Таранников. О корреляционно-иммунных и устойчивых булевых функциях. Математические вопросы кибернетики. Вып. 11, сс. 91-148 — М.: Физматлит, 2002.

14Sarkar P., Maitra S. Nonlinearity bounds and constructions of resilient Boolean functions, CRYPTO'2000, LNCS V. 18S0, pp. 515-532, Springer-Verlag, 2000.

15А. А. Ботев. О свойствах корреляционно-иммунных функций с высокой нелинейностью. Диссертация на соискание ученой степени кандидата физико-математических наук, Москва, 2005.

16Dalai D. К., Gupta К. С., Maitra S. Results on algebraic immunity for cryptographically significant Boolean functions. Progress in Cryptology: INDOCRYPT'04, LNCS V. 1880, pp. 92-106, Springer-Verlag, 2004.

17Lobanov M. Tight bounds between nonlinearity and algebraic immunity, Cryptology ePrint Archive, Report 2005/441, 2005.

18Clark W. E., Hou X. D., Mihailovs A. The affinity of permutations of a finite vector space. Finite Fields and Their Applications V. 13, Issue 1, pp. 80-112, 2007.

19Hou X. D. Affinity of permutations of Discrete Applied Mathematics archive, v. 154, Issue 2, pp. 313-325, 2006.

20Canteaut A., Daum M., Dobbertin H., Leander G. Finding nonnormal bent functions. Discrete Applied Mathematics archive, v. 154 , Issue 2, pp 202-218, 2006.

21Logachev O., Yashenko V., Denisenko M. Local affinity of Boolean mappings. Proceedings of NATO ASI "Boolean functions in cryptology and information sequrity", Moscow, 8-18 September, 2007.

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

Научная новизна. Все результаты диссертации являются новыми. Основные результаты диссертации следующие:

- найдены параметры линеаризации и их оценки для различных, в том числе криптографических, классов булевых функций;

- доказаны свойства параметров, характеризующие методы линеаризации булевых функций в целом;

- получены соотношения, связывающие параметры линеаризации с основными криптографическими свойствами булевых функций;

- доказаны верхние и нижние асимптотические оценки уровня аффинности для почти всех булевых функций, а также асимптотическое неравенство для уровня аффинности квадратичных булевых функций;

- доказана /УР-трудность задачи определения уровня аффинности булевых функций с ограничением на количество мономов.

Научная и практическая ценность. Работа носит теоретический характер. Установлены различные свойства аффинных ограничений (уровня аффинности) булевых функций. Доказаны соотношения между криптографическими параметрами булевых функций и параметрами их аффинных ограничений. Доказаны асимптотические оценки уровня аффинности.

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

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

Апробирование. Результаты диссертации неоднократно докладывались на семинаре по криптографии Института проблем информационной безопасности МГУ, на семинаре «Булевы функции в криптоло-гии» механико-математического факультета МГУ, на семинаре «Дискретная математика и математическая кибернетика» кафедры математической кибернетики факультета ВМК МГУ, на международном семинаре «Дискретная математика и ее приложения», на международных конференциях МАБИТ'05 (2005 г.) и «Boolean Functions in Cryptology and Information Security» (2007 г.).

Публикации по теме диссертации. По теме диссертации опубликовано 8 работ [1-8], 3 из которых — в печатных изданиях из перечня ВАК [1-3].

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, трех приложений и списка литературы, включающего 70 наименований. Объем работы 114 страниц.

Краткое содержание диссертации

Глава 1 посвящена исследованию уровня аффинности некоторых классов булевых функций.

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

В разделе 1.2 рассматриваются основные классы булевых функций и конструкции для построения булевых функций с заданными криптографическими характеристиками. Для конструкций суперпозиции булевых функций вида прямой суммы, конкатенации, конструкции вида д (х, у) = / (х ф у) и ряда других доказываются соотношения, определяющие их уровень аффиннности. Для бент-функций, построенных с помощью конструкции Майорана-Мак-Фарланда, доказывается следующее утверждение:

Теорема 1.5. Пусть п — 2т, Ф = (/1,...,/т) — взаимнооднозначное

отображение Ут на себя, к € Тт. Тогда для бент-фунщии

т

/(г) = /(х, у) = <х, Ф(у)> ф Л(у) = ф ®4Л(у) © /г(у),

г=1

г е Уп, х € Т^, у € Ут справедливо соотношение 1а (/) = т.

Кроме того, для устойчивых булевых функций, построенных с помощью конструкции Майорана-Мак-Фарланда, устанавливается соотношение (Теорема 1.6), связывающее уровень аффинности и размерность образа соответствующего пространства для отображения Ф: Т4_( —> :

1а (/) ^п-1.

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

Гт + 3"

1а (/К

2

где т — порядок устойчивости функции /.

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

Теорема 1.11. Для булевой функции f из 3-п соотношение 1а (/) = п—1 выполнено тогда и только тогда, когда

/ (^Ъ • • • > = ^^ XiXj ® »<.7

где £ — произвольная аффинная функция.

Эта теорема дает полное описание класса функций с максимально возможным уровнем аффинности.

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

(Предложения 1.7-1.10). Для подобных функций доказываются оценки уровня аффинности.

В разделе 1.5 рассматривается связь между спектральными характеристиками булевой функции (коэффициентами Уолша-Адамара) и уровнем аффинности. Доказывается утверждение

Теорема 1.12. Пусть / £ Тп. Тогда для коэффициентов Уолша-Адамара функции f выполняется неравенство

max|W/(u)| > 2п-1а^. ueV„

Глава 2 посвящена получению соотношений, связывающих уровень аффинности с основными криптографическими свойствами (параметрами) булевых функций.

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

• N/ < Т~1 - 2"-'^-! (Предложение 2.1);

• 1а (/) > к для бент-функции / е В2к (Предложение 2.2);

• 1а (/) > г для платовидной порядка 2г функции / G (Предложение 2.3).

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

Для неуравновешенных корреляционно-иммунных булевых функций, не являющихся константами, доказано (Теорема 2.1) неравенство

1а(/)>сог(/).

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

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

Теорема 2.3. Пусть f е sut(/) = m ^ n - 2, N/ = 271"1 - 2m+1. Тогда

1а(/) ^ n — m — 2.

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

Доказано утверждение (Теорема 2.4), выводящее неравенство между алгебраической иммунностью булевой функции и ее алгебраической иммунностью на какой-либо плоскости пространства Vn :

Теорема 2.4. Пусть f 6 L CVn — линейное подпространство Vn, а € К- Тогда

AI (/) ^ AI|£ea (f) + n~ dim L. Как следствие из этой теоремы, доказано неравенство (Следствие 2.2):

«Й&Ч. {*«<«) + *>■

0<>i<-<i)t<n,

откуда получено (Следствие 2.3), что для любой булевой функции / £

1а(/)>А1(/)-1.

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

В Предложении 2.4 показывается, что для любого п ^ 3, 2 ^ d ^ п, 1 < к < п — 2 существует функция /„^ € Ти такая, что deg (/) = d, la (/) = *.

Для симметрических булевых функций доказывается утверждение:

Теорема 2.5. Пусть f 6 Тп — симметрическая булева функция, deg(/) = d,d>l. Тогда

la(/) > п — d.

При рассмотрении лавинных характеристик булевых функций, доказано, что для любой функции / € Тп, удовлетворяющей SAC(t), 1а(/) ^ t (Предложение 2.5).

Доказано соотношение, связывающее уровень аффинности булевой функции и размерностью пространства линейных структур этой функции (Предложение 2.6):

1а (/) ^ n — dim L/ - 1. 10

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

А>Ш(/).

Глава 3 посвящена асимптотическим оценкам уровня аффинности для почти всех булевых функций.

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

Теорема 3.1. Пусть а € К, а > 1 — произвольная фиксированная константа. Тогда асимптотически при п —> оо для почти всех функции из Тп

£а (/) ^ п — а 1о§2 п.

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

Теорема 3.3. Пусть (р (п) — произвольная монотонная неограниченная функция, <р(п) > 0 для любого п; /3 £ М, /? > 1 — некоторая фиксированная константа. Тогда асимптотически при п —> оо для почти всех функций из

1а° (/) < тг - 1о§2 V ("■). здесь = 1 / е Тп \ Лп ■ 1еп* (/) < ^ ■ 1, 1еп* (/) — количество

I 4>р (п) J

нелинейных мономов в АНФ функции /.

Как следствие из этой теоремы выведена асимптотическая оценка частичного уровня аффинности для функций с ограничением на степень: асимптотически при п —» оо для почти всех функций / 6 таких, что (/) ^ д. (с1 фиксировано),

1а°(/)<^п + 11об21>3>

где (3 £ М, (3 > 1 — произвольная фиксированная константа, О^ —

Е?=о (")•

В разделе 3.3 рассмотрен вопрос об асимптотическом поведении уровня аффинности квадратичных булевых функций, доказано утверждение:

Теорема 3.4. Вероятность того, что для произвольной булевой функции / € deg (/) < 2

[М (n)J ^ 1а (/) ^ \М (п)], где М (п) = 2 (log2 п — log2 log2 п -f log2 §) , стремится к 1 при п —» оо.

Глава 4 посвящена алгоритмическим вопросам нахождения уровня аффинности.

В разделе 4.1 приводится алгоритм определения уровня аффинности булевых функций общего вида со сложностью 0(N3) (N = 2П).

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

В разделе 4.3 показана JVP-трудность задачи определения уровня аффинности булевых функций с ограничением на количество мономов в АНФ:

Теорема 4.4. Задана нахождения уровня аффинности булевой функции из Т,с (п) является NP-трудной. Здесь

!FC (тг) = {/ € Fn •' len (/) < сп, с = const} , где 1еп(/) — количество мономов в АНФ функции /.

Благодарности

Автор выражает глубокую благодарность своему научному руководителю кандидату физико-математических наук Логачеву Олегу Алексеевичу за постановку задачи, всестороннюю помощь и внимание к работе над диссертацией, а также всем сотрудникам кафедры математической кибернетики факультета ВМК МГУ имени Ломоносова за доброжелательное отношение и творческую атмосферу.

Публикации автора по теме диссертации

1. М. Л. Вуряков, О. А. Логачев. Об уровне аффинности булевых функций. Дискретная математика, том 17, вып. 4, 2005, сс. 98-107.

2. М. Л. Буряков. О связи уровня аффинности с криптографическими параметрами булевых функций. Дискретная математика, том 20, вып. 2, 2008, сс. 3-15.

3. М. Л. Буряков. Асимптотические оценки уровня аффинности для почти всех булевых функций. Дискретная математика, том 20, вып. 3, 2008, сс. 73-79.

4. М. Л. Буряков. Об уровне аффинности некоторых классов булевых функций. VI Международная конференция «Дискретные модели в теории управляющих систем. Москва, 7-11 декабря 2004 г. Труды. Сс.231-235, М.: Издательский отдел Факультета ВМиК МГУ им. М. В. Ломоносова, 2004.

5. М. Л. Буряков. О некоторых свойствах уровня аффинности комбинирующих булевых функций. Математика и безопасность информационных технологий. Материалы конференции в МГУ 28-29 октября 2004 г., сс. 136-141 - М.: МЦНМО, 2005.

6. М. Л. Буряков, О. А. Логачев. О распределении уровня аффинности на множестве булевых функций. Математика и безопасность информационных технологий. Материалы конференции в МГУ 2829 октября 2004 г., сс. 141-146 - М.: МЦНМО, 2005.

7. М. Л. Буряков. Об уровне аффинности комбинирующих булевых функций. Сборник тезисов лучших дипломных работ 2005 года, сс. 62-64 — М.: Издательский отдел Факультета ВМиК МГУ им. М. В. Ломоносова, 2005.

8. М. Л. Буряков. Об уровне аффинности симметрических булевых функций. Материалы IX Международного семинара «Дискретная математика и ее приложения», сс. 421-423 — М.: Издательство механико-математического факультета МГУ, 2007.

Издательство ЦПИ при механико-математическом факультете МГУ имени М.В.Ломоносова

Подписано в печать 20,04. 0§ Формат 60x90 1/16. Усл. печ. л. 1,0 Тираж {О О экз. Заказ 06

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета

Введение

1 Общие свойства уровня аффинности

1.1 Обозначения, определения и общие сведения.

1.2 Уровень аффинности некоторых классов булевых функций

1.3 Класс функций с максимально возможным уровнем аффинности

1.4 Уровень аффинности булевой функции и преобразование Мёбиуса

1.5 Уровень аффинности булевой функции и спектральные коэффициенты

2 Связь с криптографическими параметрами

2.1 Уровень аффинности и нелинейность.

2.2 Уровень аффинности и корреляционная иммунность

2.3 Уровень аффинности и алгебраическая иммунность.

2.4 Другие криптографические параметры.

3 Асимптотические оценки уровня аффинности

3.1 Нижняя асимптотическая оценка обобщённого уровня аффинности

3.2 Верхняя асимптотическая оценка частичного уровня аффинности для функций с заданной степенью

3.3 Асимптотическое значение уровня аффинности квадратичных булевых функций.

4 Алгоритмы определения уровня аффинности

4.1 Алгоритм определения уровня аффинности для булевых функций общего вида.

4.2 Алгоритм определения уровня аффинности для симметрических булевых функций.

4.3 Сложность задачи определения уровня аффинности.

Обеспечение информационной безопасности является одной из важнейших государственных задач наряду с обеспечением обороноспособности страны, развитием экономики, образования и здравоохранения. Основополагающим документом, регламентирующим политику России в области информационной безопасности, является Доктрина информационной безопасности Российской Федерации [ДИБ], утвержденная в сентябре 2000 года Президентом РФ. Секция Научного совета при Совете Безопасности РФ на основе Доктрины разработала Перечень приоритетных проблем научных исследований, связанных с информационной безопасностью [ППНИ]. Он включает в себя направления в областях развития общей теории обеспечения информационной безопасности и, в частности, защиты информации различными методами, в том числе с использованием криптографических механизмов, разработку методов и средств защиты в системах электронного документооборота включая использование электронной цифровой подписи. Одним из наиболее важных направлений в Перечне является «разработка фундаментальных проблем теоретической криптографии и смежных с ней областей математики» (п. 54 Перечня).

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

Разработка алгоритмов преодоления криптографической защиты основана на использовании математических моделей, адекватно описывающих процесс функционирования системы защиты. Математическая формализация работы криптосистем в процессе криптоанализа во многих случаях приводит к задачам решения уравнений в различных алгебраических системах. Системы нелинейных булевых уравнений являются одной из распространённых моделей описания функционирования различных дискретных устройств. Необходимость изучения и решения систем булевых уравнений возникает в ряде задач теории конечных автоматов, теории кодирования и криптологии. В частности, в криптологии это направление относится к синтезу и анализу традиционных криптографических систем с секретным ключом, где системы нелинейных булевых уравнений, связывают элементы неизвестного ключа криптосистемы с известными данными. Основные криптографические примитивы, являющиеся источниками систем булевых уравнений в криптоанализе, — это комбинирующие генераторы (см. рис. 1) и фильтрующие генераторы (см. рис. 2) потоковых шифров, а также s-боксы блоковых шифров. На этих рисунках: РСЛОС-г, г = 1,., п, PCJIOC — регистры сдвига с линейными обратными связями; / — комбинирующая (фильтрующая) булева функция от п переменных; gi{v), i = 1,2,., п, g(v) — полиномы обратных связей регистров сдвига.

Рис. 1: комбинирующий генератор

V) рслос х jt) -W xw\

V 1 Iх2 > ■ • •'Xn }

Рис. 2: фильтрующий генератор

Задача решения произвольной системы нелинейных булевых уравнений является iVP-трудной (см. [ГДж82]) и на данный момент для решения подобных систем в общем случае не известно алгоритма со сложностью, по порядку меньше, чем

2о(п) где п — число неизвестных в системе. Вместе с

Zt = f тем, анализ конкретных систем уравнений для криптосистем с секретным ключом (при п « 100-200 и более) является актуальной научной проблемой (см., например, [eSTREAM]).

В криптоанализе разработаны различные подходы к решению нелинейных систем булевых уравнений. В ряде случаев для нахождения решения системы используются теоретико-вероятностные, статистические методы (см. [Sieg84, MSt89]) и теоретико-кодовые методы (см. [ChJohSmOO]). В ряде случаев предлагается погружать систему уравнений в действительную область (см. [БН94, Нат68, Рыб02, РХ02]) и находить её решение системы с помощью соответствующей системы псевдобулевых неравенств. Кроме того, в случае использования итераций в процессе шифрования возможна линеаризация исходной криптографической задачи (например, определения ключа) с использованием определённых степеней итерируемого отображения, являющихся аффинными отображениями (см. [ФомОб, Фом08]).

В работах [КЛО'ШиОО, AFIKS04] рассматриваются алгебраические методы решения систем нелинейных булевых уравнений над конечными полями на основе базисов Грёбнера.

Наиболее эффективными, как показывает практика криптоанализа, являются методы, использующие линеаризацию исходной системы. Эти методы можно условно разбить на два класса. Первый класс составляют методы линеаризации нелинейной системы булевых уравнений с введением новых переменных, эффективным решением полученной линейной системы и нахождением решения (решений) исходной системы. В практике криптоанализа этот метод называют алгебраической атакой (algebraic attack). Подробную библиографию, относящуюся к этому методу, можно найти, например, в [Баев07].

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

Подфункцией данной булевой функции (см. [ЛСЯ04]) называют ограничение этой функции на некоторое подмножество её области определения (формальное определение нужного нам понятия подфункции будет дано позднее). Тесно связано с понятием подфункции булевой функции понятие частично определённой булевой функции. Использование в криптоанализе подфункции определило интерес исследователей к изучению совместных криптографических свойств булевых функции и их подфункций (см. [ССЬОЗ, DDL03, CDDL03, КЯщОО, КЯщ01, Куз02-1, Куз02-2, Саг92]), а также к наследованию свойств булевой функции её подфункциями (см., например, [ЛСЯ02]).

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

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

Понятие уровня аффинности (1а(/)) булевой функции / как минимальное число фиксаций переменных этой функции, переводящих исходную функцию в аффинную функцию от меньшего числа переменных, было введено в [ЛСЯОЗ-2]. Понятие частичного уровня аффинности (1а° (/)) было введено в [JIor05] и определяется как минимальное число нулевых фиксаций переменных булевой функции /, превращающих исходную функцию в аффинную. Понятие обобщённого уровня аффинности (£а(/)) булевой функции / определяется как минимальная разность между числом переменных функции / и размерностью плоскости (смежного класса по подпространству), ограничение на которую совпадает с аффинной функцией. Различные виды уровня аффинности связаны между собой естественным соотношением а(/)<1а(/)^1а°(/), которое используется для вывода ряда соотношений.

Естественным образом указанные выше параметры линеаризации могут быть распространены и на булевы отображения.

Понятие сильной £;-аффинности рассмотрено в [ЛСЯОЗ-2]. Аналогичное понятие линеаризационного множества, определяемое в других терминах, введено в [Тим05-1, Тим05-2].

Кратко сформулируем криптографическую задачу восстановления ключей комбинирующего генератора. Рассмотрим комбинирующий генератор (см. рис. 1), построенный с помощью п регистров сдвига 'с линейными обратными связями — РСЛОС-г, г — 1 ,.,п. Длины регистров будем обозначать ki, i — 1, .,п соответственно. Псевдослучайная последовательность получается с помощью комбинирующей булевой функции / , • • •, — / (х) от п переменных.

Будем считать, что полиномы обратных связей регистров сдвига gi(v), г = 1, 2,., п примитивны, и регистры порождают линейные реккурентные последовательности максимального периода 2ki — 1, г = 1,2,., п.

Обозначим для натурального числа n и фиксированного г,

1 о ( (1) (2) (N)\ Г (t)\N г — 1,2,.,п, Xj = ,х\ , .,х\ J — j i ~ последовательность длины N, вырабатываемую регистром сдвига с номером г, находившимся (!) (2) (кг)\ гр . в начальном состоянии ( х\ , х\ ,., х\ ). 1о есть, в такт t регистр с номером г вырабатывает элемент xf^ последовательности х;, а "комбинирующий генератор вырабатывает знак z^ = f ., Хп^ шифрующей последовательности z

Пусть известна последовательность z, выработанная комбинирующим генератором. Задача состоит в определении начальных состояний \ \ • • • ) ^ j \ х2 > • • • » ^ ) ■ • ■ ) (^п > З^п \ • • • } Хп ^ регистров, при которых была получена последовательность z. Другими словаГ ми, задача состоит в восстановлении последовательностей xi ., xn

В криптоанализе данная криптографическая задача соответствует атаке по открытому и шифрованному тексту на комбинирующий генератор потокового шифра с угрозой вскрытия ключа. В работе [ЛСЯОЗ-1] был предложен метод реализации данной атаки, основанный на частичном опробовании ключей и использующий ранговый критерий. При этом уровень аффинности 1а (/) комбинирующей функции / (см. рис. 1) определяет (наряду с другими параметрами) трудоёмкость этого метода.

Другим важным направлением исследований является изучение криптографических свойств булевых функций и связей между этими свойствами. Достаточное число математически содержательных соотношений между параметрами, описывающими различные (в том числе и конфликтующие) криптографические свойства, облегчает решение сложной оптимизационной задачи выбора булевых функций (отображений) при синтезе стойких криптосистем. Примерами могут служит изучение пар криптографических свойств «корреляционная иммунность-нелинейность» [Тар02, SM00-2], «корреляционная иммунность-алгебраическая иммунность» [Бот05], «нелинейность-алгебраическая иммунность» [DGM04, Lob05], а также использование локальных аффинностей для изучения криптографических свойств булевых функций [С1НМ07, НоиОб, CDDL06, LYashD07].

Целью данной диссертации является развитие математического аппарата для совершенствования методов анализа и синтеза криптосистем с секретным ключом.

Основные результаты работы состоят в следующем.

- найдены параметры линеаризации и их оценки для различных (в том числе криптографических) классов булевых функций;

- доказаны свойства параметров, характеризующие методы линеаризации булевых функций в целом;

- получены соотношения, связывающие параметры линеаризации с основными криптографическими свойствами булевых функций;

- доказаны верхние и нижние асимптотические оценки уровня аффинности для почти всех булевых функций;

- доказана ./VP-трудность задачи определения уровня аффинности булевых функций с ограничением на количество мономов.

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

Заключение

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

1. AFIKS04. Ars G., Faugere J-С., Imai H., Kawazoe M., Sugita M. Comparsion between XL and Grobner basis Algorithms. Advances in Cryptology: ASIACRYPT'04, LNCS V. 3329., pp. 338-353, Springer-Verlag, 2004.

2. CCChS91. Camion P., Carlet C., Charpin P., Sendrier N. On correlation immune functions. Crypto 1991, LNCS V. 576, pp. 86-100, Springer-Verlag, 1991.

3. CCh03. Canteaut A., Charpin P. Decomposing bent functions. IEEE Transactions on Information Theory, V. 49, № 8, pp. 2004-2009, 2003.

4. CDDL03. Canteaut A., Daum M., Dobbertin H., Leandr G. Normal and nonnormal bent functions. Proc. Int. Workshop on Coding and Cryptography — WCC'2003, Versailles, Mar. 2003, pp. 91-100.

5. CV05. Canteaut A., Videau M. Symmetric boolean functions. IEEE Transactions on Information Theory, V. 51, № 8, pp. 2791-2811, 2005.

6. CDDL06. Canteaut A., Daum М., Dobbertin Н., Leander G. Finding nonnormal bent functions. Discrete Applied Mathematics archive, v. 154 , Issue 2, pp 202-218, 2006.

7. Car92. Carlet C. Partially-bent functions. Proc. Crypto 92, pp. 280-291, Springer, 1992.

8. Car94. Carlet C. Two new classes of bent functions. Advances in Cryptology: EUROCRYPT'93, LNCS V. 765., pp. 77-101, Springer-Verlag, 1994.

9. Car02. Carlet C. A large class of cryptographic Boolean functions via a study of the Maiorana-McFarland constructions. Advances in Cryptology: CRYPTO'02, LNCS V. 2442., pp. 549-564, Springer-Verlag, 2002.

10. Car04. Carlet C. On the secondary constructions of resilient and bent functions. Progress in Computer Science and Applied Logic 23 (2004), pp. 3-28.

11. C1HM07. Clark W. E., Hou X. D., Mihailovs A. The affinity of permutations of a finite vector space. Finite Fields and Their Applications V. 13, Issue 1, pp. 80-112, 2007.

12. ChSm91. Chepyzhov V., Smeets B. On a fast correlation attacks on certain stream ciphers. Advances in Cryptology: EUROCRYPT'91, LNCS V. 547, pp. 176-185, Springer-Verlag, 1991.

13. ChJohSmOO. Chepyzhov V., Johansson Т., Smeets В. A simple algorithm for fast correlation attacks on stream ciphers. Advances in Cryptology: FSE'2000, LNCS V. 1978, pp. 181-195, Springer-Verlag, 2000.

14. CP02. Courtois N., Pieprzyk J. Cryptanalysis of block ciphers with overdefined systems of equations. Advances in Cryptology: ASIACRYPT'02, LNCS V. 2501, Springer-Verlag, 2002.

15. CP03. Courtois N, Patarin J. About the XL algorithm over GF(2). Cryptographers' Track RSA 2003, San Francisco, April 13-17 2003, LNCS V. 2612, Springer, 2003.

16. CM03. Courtois N., Meier W. Algebraic attacks on stream ciphers with linear feedback. Advances in Cryptology: EUROCRYPT'03, LNCS V. 2656, Springer-Verlag, 2003.

17. DGM04. Dalai D. K., Gupta К. C., Maitra S. Results on algebraic immunity for cryptographically significant Boolean functions. Progress in Cryptology: INDOCRYPT'04, LNCS V. 1880, pp. 92-106, Springer-Verlag, 2004.

18. Ham68. Hammer P. L. Boolean elements in combinatorial optimization. Combinatorial Programming: Methods and Applications, Dordrecht-Boston, 1968.

19. Mats93. Matsui M. Linear cryptanalysis method for DES cipher. Advanced in Cryptology: EUROCRYPT'93, LNCS V. 765, pp. 386-397, Springer-Verlag, 1993.

20. Mat76. Matula D. W. The Largest clique size in random graph. Technical Report CS 7608, Department of Computer Science, Southern Methodist University, 1976.

21. Meier04. Meier W., Pasalic E., Carlet C. Algebraic attacks and decomposition of Boolean fucntions. Advances in Cryptology: EUROCRYPT'04, LNCS V. 3027, Springer-Verlag, 2004.

22. MSt89. Meier W., Staffelbach O. Fast correlation attacks on certain stream ciphers. Journal of Cryptology V. 1, № 3, pp. 159-1762, 1989.

23. MOV97. Menezes A., P. van Oorschot, Vanstone S. Handbook of applied cryptography. CRC Press Inc., 1997

24. NESSIE. Проект разработки новых европейских схем шифрования, цифровой подписи и проверки целостности NESSIE, https: //www. cosic. esat.kuleuven.be/nessie/

25. Pas03. Pasalic E. Degree optimized resilient Boolean functions from Maiorana-McFarland class. Cryptography and Coding — 9th IMA International Conference, LNCS V. 2898, pp. 93-114, Springer-Verlag, 2003.

26. Roth76. Rothaus O. On bent function. J. Combin. Theory Ser. A, V. 20, pp. 300-305, 1976.

27. SM00-1. SarkarP., MaitraS. Construction of nonlinear Boolean functions with important cryptographic properties, EUROCRYPT'2000, LNCS V. 1807, pp. 488-511, Springer-Verlag, 2000.

28. SM00-2. Sarkar P., Maitra S. Nonlinearity bounds and constructions of resilient Boolean functions, CRYPTO'2000, LNCS V. 1880, pp. 515-532, Springer-Verlag, 2000.

29. Sieg84. Siegenthaler T. Correlation-immunity of nonlinear combining functions for cryptographic applications. IEEE Trans, on Information Theory V. IT-30.5, pp. 776-780, 1984.

30. ZZ99. Zheng Y., Zhang X. M. Plateaued functions. ICICS'99, LNCS V. 1726, pp. 284-300, Springer-Verlag, 1999.

31. Ал02. В. Б. Алексеев. Введение в теорию сложности алгоритмов (учебное пособие для студентов). — М.: Издательский отдел факультета ВМиК МГУ, 2002.

32. Баев07. В. В. Баев. Эффективные алгоритмы получения оценок алгебраической иммунности булевых функций. Диссертация на соискание учёной степени кандидата физико-математических наук, специальность 01.01.09, Москва, 2007.

33. БН94. Г. В. Балакин, В. Г. Никонов. Методы сведения булевых уравнений к системам пороговых соотношений. Обозрение прикладной и промышленной математики., т. 1, вып. 3, сс. 389-401, 1994.

34. Бот05. А. А. Ботев. О свойствах корреляционно-иммунных функций с высокой нелинейностью. Диссертация на соискание учёной степени кандидата физико-математических наук, специальность 01.01.09, Москва, 2005.

35. Бур05-1. М. Л. Буряков. О некоторых свойствах уровня аффинности комбинирующих булевых функций. Математика и безопасность информационных технологий. Материалы конференции в МГУ 28-29 октября 2004 г., сс. 136-141 М.: МЦНМО, 2005.

36. Бур05-2. М. Л. Буряков. Об уровне аффинности комбинирующих булевых функций. Сборник тезисов лучших дипломных работ 2005 года, сс. 62-64 — М.: Издательский отдел Факультета ВМиК МГУ им. М. В. Ломоносова, 2005.

37. Бур07. М. Л. Буряков. Об уровне аффинности симметрических булевых функций. Материалы IX Международного семинара «Дискретная математика и её приложения», сс. 421-423 — М.: Издательство механико-математического факультета МГУ, 2007.

38. Бур08-1. М. JL Буряков. О связи уровня аффинности с криптографическими параметрами булевых функций. Дискретная математика, том 20, вып. 2, 2008, сс. 3-15.

39. Бур08-2. М. JI. Буряков. Асимптотические оценки уровня аффинности для почти всех булевых функций. Дискретная математика, том 20, вып. 3, 2008, сс. 73-79.

40. БЛ05-1. М. JT. Буряков, О. А. Логачев. Об уровне аффинности булевых функций. Дискретная математика, том 17, вып. 4, 2005, сс. 98-107.

41. БЛ05-2. М. Л. Буряков, О. А. Логачев. О распределении уровня аффинности на множестве булевых функций. Математика и безопасность информационных технологий. Материалы конференции в МГУ 28-29 октября 2004 г., сс. 141-146 М.: МЦНМО, 2005.

42. ГДж82. М. Гэри, Д. Джонсон. Вычислительные машины и труднореша-емые задачи. — М.: Мир, 1982.

43. ДИБ. Доктрина информационной безопасности Российской Федерации. В сб. «Научные и методологические проблемы информационной безопасности». Под ред. В. П. Шерстюка, сс. 149-197 — М.: МЦНМО, 2004.

44. КЛО'ШиОО. Д. Кокс, Дж. Литтл, Д. О'Ши. Идеалы многообразия и алгоритмы. — М.: Мир, 2000.

45. Куз96. Ю. В. Кузнецов. Коды Рида-Маллера (обзор публикаций). Математические вопросы кибернетики, № 6, сс. 5-50 — М.: Наука, 1996.

46. КЯщОО. Ю. В. Кузнецов, В. В. Ященко. О частичных бент-функциях. Вестник МГУ. Сер. 1. Математика. Механика. № 5, сс. 3-6, 2000.

47. Лог05. О. А. Логачев. Нижняя границауровня аффинности для почти всех булевых функций. Дискретная математика,т. 20,вып. 4 — М.,2008.

48. ЛСЯ02. О. А. Логачев, А. А. Сальников, В. В Ященко. О наследовании свойств при сужении булевых функций, Дискретная математика, т. 14, вып. 2, сс. 9-19 — М., 2002.

49. ЛСЯОЗ-1. О. А. Логачев, А. А. Сальников, В. В Ященко. Корреляционная иммунность и реальная секретность, Математика и безопасность информационных технологий. Материалы конференции в МГУ 23-24 октября 2003 г., сс. 165-170 М.: МЦНМО, 2004.

50. ЛСЯОЗ-2. О. А. Логачев, А. А. Сальников, В. В Ященко. Комбинирующие k-аффинные функции, Математика и безопасность информационных технологий. Материалы конференции в МГУ 23-24 октября 2003 г., сс. 176-178 М.: МЦНМО, 2004.

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

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

53. ППНИ. Приоритетные проблемы научных исследований в области информационной безопасности Российской Федерации. Математика и безопасность информационных технологий. Материалы конференции в МГУ 23-24 октября 2003 г., сс. 21-28 М.: МЦНМО, 2004.

54. Рыб02. К. К. Рыбников. Оценка сложности некоторых схем метода разоделяющих плоскостей при решении систем булевых уравнений. Обозрение прикладной и промышленной математики, т. 9, вып. 2, сс. 442443, 2002.

55. РХ02. К. К. Рыбников, А. С. Хохлушин. О взаимосвязях различных алгоритмических методов погружения множества решений системы булевых уравнений в действительную область. Вестник МГУЛ. Лесной вестник, № 5 (25), сс. 189-194, 2002.

56. Тар02. Ю. В. Таранников. О корреляционно-иммунных и устойчивых булевых функциях. Математические вопросы кибернетики. Вып. 11, сс. 91-148 — М.: Физматлит, 2002.

57. Тим05-1. Н. Е. Тимошевская. О линеаризационных множествах. Проблемы теоретической кибернетики. Тезисы докладов XIV Международной конференции (Пенза, 23-28 мая 2005), с. 154 — М.: Издательство механико-математического факультета МГУ, 2005.

58. Тим05-2. Н. Е. Тимошевская. Задача о кратчайшем линеаризационном множестве. Вестник Томского государственного университета, № 14, август 2005 (приложение), сс. 79-83.

59. ШенбЗ. К. Шеннон. Синтез двухполюсных переключательных схем. Работы по теории информации и кибернетике, сс. 59-105 — М.: ИЛ, 1963.