О свойствах корреляционно-иммунных функций с высокой нелинейностью тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи УДК 511.361+511.9+512.64

БОТЕВ Антон Алексеевич

О СВОЙСТВАХ КОРРЕЛЯЦИОННО-ИММУННЫХ ФУНКЦИЙ С ВЫСОКОЙ НЕЛИНЕЙНОСТЬЮ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

Москва 2005

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

Научный руководитель: кандидат физико-математических

наук Ю.В. Таранников

Официальные оппоненты: доктор физико-математических наук,

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

Ведущая организация: Институт математики

им С.Л. Соболева СО РАН

Защита диссертации состоится 18 на заседании диссертационного государственном университете им. ГСП-2, Москва, Ленинские горы, МГУ, ауд. 14-08.

ноября 2005 г. в 16 часов 15 минут совета Д.501.001.84 в Московском М.В. Ломоносова по адресу: 119992, Механико-математический факультет

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

Автореферат разослан 18 октября 2005 г.

Ученый секретарь диссертационного совета Д.501.001.84 в МГУ, профессор

В. Н. Чубариков

Zoom Ys

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

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

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

Многие потоковые шифры состоят из линейной части, которая порождает последовательность с большим периодом, обычно состоящей из одного или нескольких регистров сдвига с линейной обратной связью (linear feedback shift registers, LFSR), и нелинейной булевой функции f, комбинирующей линейные выходы LFSR. Исследования устойчивости данного шифра к различным криптографическим атакам в основном сводятся к исследованию различных свойств комбинирующей функции /. Так, для того, чтобы противостоять атаке БерлекэмпагМэс-си1, разнообразным типам корреляционных (первоначальная статья Т. Зи-генталера2; в этой же работе впервые появился термин корреляционно-иммунная порядка т функция; см. также статью Канто и Траббья3) и линейных (первоначальная статья Матцуи и Ямагиши4; см. также статью Юхансона и Йонсона5) атак, а также алгебраической атаке®, функция по возможности должна удовлетворять следующим критериям:

1. Уравновешенность. Булева функция должна выдавать нули и единицы с одинаковой вероятностью.

2. Хорошая корреляционная иммунность (порядка т). Выход булевой функции должен быть статистически независим от комбинации любых т

lBerlecamp Е. R. Algebraic Coding Theory. New York, St. Louis, San Francisko, Toronto, London, Sydney: McGrow-ffill, 1968; MasaeyJ. L. Shift-Register syntesis and BCH decoding. // IEEE Trans, on Inform. Theory. 1969. IT-17. P. 464-466.

2SiegentalerT. Correlation-immunity of Nonlinear Combinig Functions for Cryptography Applications 11 IEEE Trans, on Inform. Theory. 1984. IT-30. No. 5. P. 776-780.

3CanteautA., ТгаЬЫа M. Improved fast correlation attacks using Parity-check equations of weight 4 and 5. // Proceedings of Advances in Cryptology - EUROCRYPT'OO. Lect. Notes in Сотр. Sci. Springer, 2000. V. 1807. P. 537-588.

4MatsuiM., Yamagishi A. A new method for known plaintext attack of FEAL cypher. 11 Proceedings of Advances in Cryptology - EUROCRYPT'92. Lect. Notes in Сотр. Sci. Springer, 1994. V. 950. P. 366-375.

5 Johansson Т., JonssonF. Fast correlation attacks through reconstruction of linear polynomials // Proceedings of Advances in Cryptology - Crypto 2000. Lect. Notes in Сотр. Sci. Springer, 2000. V. 1880. P. 300-315.

6Courtois N., Meier W. Algebraic attacks on stream ciphers with linear feedback // Proceedings of Advances in Cryptology - EURQCRYPT'03. Lect. Notes in Сотр. Sci. Springer,

2003. V. 2656. P. 345-357.

РОС. НАЦИОНАЛА БИБЛИОТЕКА

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

3. Хорошая нелинейность. Булева функция должна находиться на достаточно большом расстоянии от любой аффинной функции.

4. Высокая алгебраическая степень.

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

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

Критерии, налагаемые на комбинирующую функцию, зачастую конфликтуют друг с другом, выяснению их взаимоотношений посвящена обширная литература. Не существует функции, которая была бы оптимальна по всем перечисленным параметрам (например, имеет место известное неравенство Зигенталера7, утверждающее, что корреляционно-иммунная порядка m функция от п переменных не может иметь алгебраическую степень большую, чем п — т). Речь идет скорее о том, чтобы оптимизировать их в совокупности, учитывая при этом, что какие-то параметры являются более важными (нелинейность, корреляционная иммунность), какие-то менее важными. Кроме того, иногда появляются новые атаки на потоковые шифры (из последних стоит особо выделить алгебраическую атаку8). Так, Майер, Пасалич и Карле9 показали, что, например, функции одного из классов Майораны-Макфарланда, имеющие высокую устойчивость, асимптотически наилучшую нелинейность и оптимальную алгебраическую степень, имеют при этом достаточно низкую алгебраическую иммунность и не могут противостоять алгебраическим атакам. С этой точки зрения серьезный интерес представляет из себя построение-большого количества функций, удовлетворительных по уже существующим критериям, с тем, чтобы часть из них использовать против этих вновь появляющихся атак.

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

7Siegentaler T. Op. cit.

* Courtois N., Meier W. Op. cit.

9Meier W., PasalicE., Carlet C. Algebraic attack and decomposition of Boolean functions

// Proceedings of Advances in Cryptology - EURPCRYPT'04. Lect. Notes in Comp. Sei.

Springer, 2004. V. 3027. P. 474-491.

m оптимизируются другие криптографически важные параметры. В частности, в работах Зенга и Занга10, Саркара и Майтры11 и Таранникова12 одновременно и независимо друг от друга было доказано, что нелинейность nl(f) для фиксированных п и т не больше, чем 2"~' — 2т (для уравновешенных функций nl(f) < 2n_1 — 2m+1). В работе Зенга и Занга13, кроме того, доказано, что если О.бп — 0.4 < т < п — 2, то nl(f) < 2"-1 - 2m+1. Далее, Федоровой и Таранниковым14 показано, что данная граница нелинейности может достигаться при ¡¿щп + 0(log2n) < т <п- 2, =

0.5902... Этот результат в настоящий момент является наилучшим.

В исследованиях существенным образом используется коэффициент Уолша — дискретный аналог коэффициента Фурье. В частности, очень важна величина Х/(0) — коэффициент Уолша от нулевого вектора. Во всех рассматриваемых работах о Х/(0) было известно только то, что этот коэффициент делится на 2m+1 (в случае, если / — m-устойчивая функция, то на 2т+2). Исследование более общего случая (т.е. Х/Ф) = 2т+г( mod 2m+<+1) для произвольного г) ранее не проводилось. В настоящей работе этот случай исследован.

Важной и довольно мощной атакой на потоковые шифры является алгебраическая атака, предложенная Куртуа и Майером15. Алгебраическая атака раскрывает секретный ключ путем решения системы уравнений, зависящих от многих переменных. Данные системы уравнений описывают соотношения между битами ключа/состояния и выходными битами комбинирующей функции. Если найдено такое соотношение низкой степени, алгебраические атаки очень эффективны16. В первоначальной статье17 показано, что указанные соотношения низкой степени и,

10Zheng Y., ZhangХ.-М. Improved upper bound on nonlinearity of high order correlation immune functions // Selected Areas in Cryptography: SAC 2000. Lect. Notes in Сотр. Sci. Springer, 2000. V. 2012. P. 264-274.

nSarkarP., MaitraS. Nonlinearity bounds and constructions of resilient Boolean functions // Advanced in Cryptography: Crypto 2000. Lect. Notes in Сотр. Sci. Springer, 2000. V. 1880. P. 515-532.

nTarannikovYu. On resilient Boolean functions with maximal possible nonlinearity // Proceedings of Indocrypt 2000. Lect. Notes in Сотр. Sci. Springer, 2000. V. 1977. P. 19-30.

13 Zheng Y., Zhang X.-M. Op. cit.

14 Fedorvva M., Tarannikov Y. V. On the constructing of highly nonlinear resilient Boolean functions by means of special matrices // Proceedings of Indocrypt 2001. Lect. Notes in Сотр. Sci. Springer, 2001. V. 2247. P. 254-266.

liCourtoisN., Meier W. Op. cit.

19Courtois N. Fast algebraic attacks on stream ciphers with linear feedback // Proceedings of Advances in Cryptology - Crypto 2003. Lect. Notes in Сотр. Sci. Springer, 2003. V. 2729. P. 176-194.

17CourtoisN., Meier W. Op. cit.

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

Куртуа и Майер18 предложили три разновидности такого рода атак. Майер, Пасалич и Карле19 свели эти три вида к двум и предложили новый термин — алгебраическая иммунность. Алгебраическая иммунность функции /, или AI(f) — это наименьшая степень аннигилятора либо самой функции, либо ее дополнения. Если алгебраическая иммунность достаточно высока, то алгебраическим атакам можно успешно противостоять.

Для нужд криптографии требуются функции с возможно большей алгебраической иммунностью. Майер, Пасалич и Карле20 получили оценку алгебраической иммунности сверху - для функции с п входами она не превышает \п/2]. В 2005 г. Далаи, Гупта и Майтра21 нашли семейство функций с максимальной алгебраической иммунностью, и, кроме того, указали последовательность функций с растущей алгебраической иммунностью. Однако с точки зрения нелинейности эти функции не являются оптимальными, их превосходят, например, функции, разработанные Таранниковым22, оптимальные по всем параметрам, кроме, возможно, параметров недавно появившейся алгебраической иммунности. В настоящей работе показано, что для последовательности функций, введенных Таранниковым, последовательность их алгебраических иммун-ностей возрастает, хотя и не так значительно, как для последовательности функций Далаи и соавторов, сославшихся в своей последней работе23

18 Courtois N., Meier W. Op. cit.

19Meier W., Pasdic E., CarletC. Op. cit.

20 Meier W., PasalicE., CarletC. Op. cit.

21 Dalai D. K., Gupta К. С., Maitra S. Cryptographically significant Boolean functions: construction and analysis in terms of algebraic immunity // To be published in Proceedings of FSE'2005.

27 Tarannikov Yu. Op. cit.

23DalaiD. K., GuptaK. C., Maitra S. Basic theory in construction of Boolean functions with maximum possible annihilator immunity // http://eprint.iacr.org/2005/229. 20

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

Цель работы.

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

Научная новизна работы.

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

— Исследован наиболее общий случай неуравновешенных корреляционно-иммунных порядка m функций (х/(0) = 2m+'( mod 2m+i+1), г > 0), даны новые наилучшие оценки на границу достижимости максимальной нелинейности для них; получен качественный результат, состоящий в том, что при больших m максимальная нелинейность неуравновешенных корреляционно-иммунных функций порядка m меньше максимальной нелинейности m-устойчивых функций.

— С точки зрения алгебраической иммунности исследовано большое количество функций, являющихся оптимальными по всем прочим криптографически значимым параметрам. Показано, что с ростом количества входов для данных функций алгебраическая иммунность этих функций растет со скоростью не менее, чем fi(i/n), где п - количество входов функции.

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

Методы исследования.

В работе используются методы и результаты комбинаторного анализа и классического математического анализа.

pp.

24 Meier W., Рasdic Е., CarletC. Op. cit.

Теоретическая и практическая ценность.

Диссертация носит теоретический характер. Ее результаты могут быть использованы в теории криптографических свойств булевых функций, при разработке и анализе потоковых шифров. Они могут быть полезны специалистам Московского Государственного Университета им. М. В. Ломоносова, Института математики им. С. Л. Соболева СО РАН, Института прикладной математики и кибернетики им. М. В. Келдыша, Института проблем передачи информации, Института криптографии, связи и информатики академии ФСБ России.

Апробация работы.

Результаты настоящей диссертации докладывались автором на семинаре механико-математического факультета МГУ "Булевы функции в криптологии" под руководством О.А.Логачева, Ю.В.Таранникова, а также на следующих международных конференциях:

"Синтез и сложность управляющих систем XIF' (Пенза, 15-21 октября 2001),

"Asiacrypt 2001" (Gold Coast, Australia, 9-13 December 2001),

"Синтез и сложность управляющих систем XV" (Новосибирск, 18-23 октября 2004),

"Дискретные модели в теории управляющих систем VI" (Москва, 711 декабря 2004).

Публикации.

Результаты диссертации опубликованы в 7 работах, список которых приводится в конце автореферата ([1-7]).

Структура и объем работы.

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

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ.

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

Глава 1 посвящена изучению корреляционно-иммунных степени т неуравновешенных функций.

В разделе 1.1 даются вспомогательные для главы 1 определения и результаты. Преобразованием Уолша булевой функции над 1?% называется целочисленная функция над определяемая следующим образом:

где < и, х > - скалярное произведение в пространстве Fg. Для каждого и € F£ значение Х/(и) называется коэффициентом Уолша.

В разделе 1.2 исследуется возможность существования неуравновешенной корреляционно-иммунной функции с определенным набором коэффициентов Уолша, а именно Х/(0) = 2m+1( mod 2т+2). Далее можно следующим образом ввести величины ж%: для любого набора и из Fj* с весом i значение х}{и) сравнимо по модулю 2т+2 с 7г, ■ 2m+1, где 7Г, = 0 или 1. Необходимым условием существования корреляционно-иммунной порядка т функции над F" будет Хл=о (") ^ 4"-m_1. С помощью некоторых вспомогательных лемм доказывается следующая теорема.

Теорема 1. Для корреляционно-иммунной порядка т функции над при х/(0) = 2m+1( mod 2т+2) для любого г > 0 верно следующее равенство:

при i = 0 верно равенство щ — 1.

Далее при помощи этой теоремы устанавливается бесконечное число пар (m,n) таких, что для них выполняется необходимое условие существования корреляционно-иммунной порядка то функции над F":

Утверждение 1. Корреляционно-иммунные порядка m функции над

при Х/Ф) = 2т+1( mod 2т+2) могут существовать при (т,п) = (2', 2l+1 + 1) и при (m, п) = (21 + 1,2Í+1 + 2).

В разделе 1.3 доказана следующая теорема, улучшающая оценку Зенга и Занга26:

Теорема 2. Пусть / - неуравновешенная корреляционно-иммунная функция на F£, у которой %/(0) = 2m+1 (mod 2m+2). Тогда при п > 12 порядок корреляционной иммунности удовлетворяет неравенству то < ±n + £ log2 п + сь где а = % log2 (f е8/9) - 1.

25Zheng Y., ZhangX.-M. Op. cit.

xeij*

( mod 2);

Следствием этой теоремы будет

Следствие. Пусть f - неуравновешенная корреляционно-иммунная функция на • Если т > \п + \ log2 п + с\, где С\ - константа, определенная в предыдущей теореме, то верны оценки для нелинейности функции ni(/) < 2n_1 - 2т+1, и ее веса wt(/) < 2n~l - 2m+1.

В разделе 1.4 эти результаты распространены на общий случай.

Теорема 3. Пусть f - неуравновешенная корреляционно-иммунная функция на F?, у которой х/(0) = 2m+i (mod 2m+i+1). Тогда при п > N(i) порядок корреляционной иммунности удовлетворяет неравенству т < \п + ^ log2 n + Ejll bg2 (\ + Í)+ С2, где с2 = | log2 (fe8/9) - i.

Следствие. Пусть f - неуравновешенная корреляционно-иммунная функция на F2". ¿/ели m > ¿n + ^у1 log2 n + ]C}=i log2 Q + + с2, где с2 - константа, определенная в предыдущей теореме, то верны оценки для нелинейности функции nl(/) < 2n_1 - 2m+i, и ее веса wt(/) < 2n_1 - 2m+i.

Учитывая тот результат, что верхняя граница нелинейности может достигаться при [„g ^+1^+0(log2 п) <т < п—2, видно, что при больших т максимальная нелинейность неуравновешенных корреляционно-иммунных функций ниже максимальной нелинейности m-устойчивых функций (которая равна 2n_1 - 2m+1).

Результаты раздела 1.4 можно считать основными результатами главы 1.

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

В разделе 2.1 даются вспомогательные для главы 2 определения и результаты.

В разделе 2.2 объясняется устройство m-устойчивых функций с максимальной нелинейностью, предложенных Таранниковым26. В диссертации для удобства они названы Т\%п и Т2,„. Из двух начальных гп-устойчивых функций Дп и Дп, зависящих от п переменных и имеющих максимально возможную нелинейность 2n_1 — 2m+1 (в диссертации для удобства они названы Ti¡n+3k и Т2,„+з*, семейство функций названо Т), через к итераций получаются две (т + 2&)-устойчивые функции /i,n+3fc и Дп+зл с максимально возможной нелинейностью 2п+3к~1 — 2m+2k+l. В данном разделе рассматриваются функции, отличающиеся

26 Tarannikov Yu. Ор. cit.

от функций, предложенных Таранниковым, наличием дополнительных линейных слагаемых (для удобства они названы 1Р\,п+гк и /Рг.п+з*), и для них с помощью нескольких вспомогательных лемм доказывается следующая теорема и ее важное следствие.

Теорема 4. Пусть степень каждого из минимальных аннигиляторов (аннигиляторов наименьшей степени) функций IPo,n,IPi,n и их дополнений не превышает к, и из этих аннигиляторов хотя бы один ненулевой. Тогда по крайней мере через к итераций степень хотя бы одного аннигилятора среди аннигиляторов получившихся функций IРо,п+гк, IР\,п+ък u uz дополнений будет строго большей, чем к.

Следствие. Для функций IP порядок минимальной степени аннигилятора не может быть меньше, чем й(у/п), где п - количество входов, или п - степень функции. Другими словами, для функций IP верна оценка AI{IP) = П(у/тГ).

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

Лемма 1. Пусть функция f не зависит от переменных Xi, Х2, ■ ■ ■, £jt. Тогда

a)AI(f) < Л/(/ + X! + ■ • • + xk) < AI(f) +1,

b) минимальные степени аннигиляторов для функций f + xН-----hXk

и f + х! + ••• +Xfc + 1 совпадают. Более того,

c) множество аннигиляторов наименьшей степени для функций f + Xi + ■ ■ ■ + Xk и f + х! + •■• +Xfc + l разбиваются на пары, такие, что в каждой паре старшие члены аннигиляторов функции f + Х\ + ■ ■ ■ + Xk и f + x 1 Н-----Ь Хк совпадают.

Следствие. Для функций Т верна оценка А1(Т) = где п -

количество входов, или п - степень функции.

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

Теорема 5. Пусть имеется функция f, составленная конкатенацией функций /о, /i,..., /у-i одинаковой размерности. Пусть, кроме того, аннигилятор функции f обозначается cj, аннигиляторы функций /, обозначаются Тогда если k = таXi{deg(gi)}, то

1) deg(g') > к, причем

2) для того, чтобы deg(gr) не превышала к, необходимо выполнение условия deg(дг + gj) < к - 1, 0 < i,j < 2П - 1.

В разделе 2.5 объясняется устройство m-устойчивых функций высокой нелинейности Пасалича-Майтры-Юхансона-Саркара27, основанных на конструкции Таранникова28. Конструкция отличается от конструкций Т и IP только способом построения двух функций от п+3 переменных из двух функций от п переменных, обозначена как РМ J S, и для нее получены результаты, аналогичные результатам раздела 2.2 и раздела 2.3.

Теорема 6. Пусть степень каждого из минимальных аннигиляторов функций РМ J So, п-PMJSitTl и их дополнений не превышает к, и из этих аннигиляторов хотя бы один ненулевой. Тогда по крайней мере через к итераций степень хотя бы одного аннигилятора среди аннигиляторов получившихся функций PMJSo,n+3k) РM JS\:n+ik и tix дополнений будет строго большей, чем к.

Следствие. Для функций PMJS верна оценка AI(PMJS) — Щ^/п), где п - количество входов, или п - степень функции.

В разделе 2.6 полученная техника используется для анализа рекурсивной конструкции бент-функций (функций, достигающих максимально возможной нелинейности), основанной на пионерской статье Ротхауза29. Аналогично предыдущим разделам, из двух бент-функций от 2п переменных, Яцп и R2,in, с помощью определеной техники строятся две другие бент-функции от 2п + 2 переменных, R\,2n+2 и #2,2п+2- Если при этом обозначить аннигиляторы функций /?1,2п, Я%2п, #1,2п + 1 и i?2,2n + 1 как д2п,1, 924,2, 92п,\ и р2п,2 соответственно, то можно сформулировать главный результат раздела:

Теорема 7. Если для двух функций из семейства R существуют аннигиляторы 92п,\> 52л,2> 92n,i ^ 92п, 2, удовлетворяющие равенствам

deg(c/2n,i + <?2n,i) <к- 2,

27PasalicE., MaitraS., Johansson Т., Sarkar P., New construction of resilient and correlation immune Boolean functions achieving upper bound on nonlinearity // Workshop on Coding and Cryptography: WCC' 2001. Paris, Electronic Notes in Discreet Mathematics, New York: Elsevier Science, 2001. V. 6.

28 Tarannikov Yu. Op. cit.

29 Rothaus О. S. On "Bent"Functions // Journal of Combinatorial Theory (A). 1976. V. 20. No. 3. P. 300-305.

deg(p2n+2,2 + hn+2,2) <k- 2,

<?2n,I = gin,2

U

?2n,l = <?2n,2,

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

Наконец, в заключительном для главы 2 разделе 2.7 "мощност-ной" результат Майера-Пасалича-Карле30, касающийся вероятности того, что уравновешенная булева функция над F" имеет алгебраическую иммунность не более, чем d, распространяется с уравновешенных функций на произвольные булевы функции.

Теорема 8. Пусть dn - последовательность натуральных чисел,

таких, что dn < цп, где = + - 1 + - lj « 0.22. Тогда

для произвольных функций от п переменных Pb{AI(f) < dn} —> 0, п —► 00.

Основными результатами главы следует считать основные результаты разделов 2.3 - 2.5.

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

В разделе 3.1 даются предварительные для главы 3 сведения. Булева функция / = f(x\,...,хп) зависит от пары своих переменных (xi,xj) квазилинейно, если для любых двух наборов а/ и х" длины п, различающихся только в г-й и j-й компонентах, справедливо f(x') ф /(х").

Пара (х1,х]) в этом случае называется парой квазилинейных переменных

_

30 Meier W., Pas alie Е., CarletC. Op. cit.

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

Теорема 9. Пусть /П)о и /„д - две т-устойчивые функции от п переменных с нелинейностью не меньше, чем N0 каждая, причем существуют две переменные, от которых /„_о зависит линейно, а /„д квазилинейно. Тогда следующие функции /п+з,о и /„+3,1 от п + 3 переменных будут (т + 2)-устойчивыми, иметь нелинейность не меньше, чем 2П+1 + 4ЛГ0 каждая, и зависеть от некоторой пары переменных линейно и квазилинейно соответственно:

/п+3,0 = Хп+\(/П10 + /пД + <?п, о) + Хп+2 + Хп+3 + Ип,0,

/п+3,1 = Яп+1 + Хп+2(/п,0 + /п,1 + <?пд) + Ж„+з(/п,0 + /п,1 + Оп,\ + 1) + Л„Д,

где Ип,о и Л„д - это любая из функций До, /п,ь Л,о + 1, Лд + 1, а <7«,о и сг„д равны 0 или 1.

Поскольку /п+з,о и Д+зд снова удовлетворяют условиям этой теоремы, пользуясь указанными в ней формулами, можно построить следующую рекурсивную конструкцию {ВС):

/г»+3(1+1),0 = Яп+Зг+1 (/п+3г,0 + /п+3г,1 + <7п+3«,о) + ^п+Зг+2 + ^п+3»+3 + ^п+З^О,

/п+3(г+1),1 — Яп+31+1 + ^п+31+г(/п+31,0 + /п+ЗгД + <7п+3гд)+ ^п+3г+з(/п+3»,0 + /п+3!,1 + Сп+3»Д + 1) + Л„+3,-д.

Для предлженных функций верно очень важное следствие теоремы 9.

Следствие. Если первоначальные т-устойчивые функции от тг переменных /п,о и Дд в условиях теоремы 9 имеют максимально возможную для данных тип нелинейность 2"~1 — 2т+1, то и все функции, получающиеся из них последовательным применением формул (ВС), имеют максимально возможную для новых показателей корреляционной иммунности и количества переменных нелинейность.

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

Теорема 10. Пусть степень каждого из минимальных аннигиляторов функций BCotn, ВС\А и их дополнений не превышает к, и из этих аннигиляторов хотя бы один ненулевой. Тогда по крайней мере через к итераций степень хотя бы одного аннигилятора среди аннигиляторов получившихся функций BC(¡¡n+zki BC\tn+3k и их дополнений будет строго большей, чем к.

Следствие. Для функций ВС верна оценка А1(ВС) = П(у/п), где п - количество входов, или п - степень функции.

Автор выражает глубокую благодарность своему научному руководителю кандидату физико-математических наук Ю.В. Таранникову за постановку задач и постоянное внимание к работе.

РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИИ.

1. БотевА.А. О соотношении между корреляционной иммунностью, нелинейностью и весом для неуравновешенных булевых функций. // Математические вопросы кибернетики. Вып. И. М., Физматлит, 2002. С. 149-162.

2. БотевА.А. Об алгебраической иммунности одной рекурсивно заг данной последовательности корреляционно-иммунных функций. // Маг тер налы XV международной школы-семинара "Синтез и сложность управляющих систем "(Новосибирск, 18-23 октября 2004 г.). Новосибирск: издательство института математики СО РАН, 2004. С. 8-12.

3. БотевА.А. О взаимосвязи корреляционной иммунности и нелинейности для неуравновешенных булевых функций // Материалы XII международной школы-семинара "Синтез и сложность управляющих систем "(Пенза, 15-21 октября 2001 г.). М.: издательство центра прикладных исследований при механико-математическом факультете МГУ, 2001. С. 58-63.

4. Ботев А. А. Новые соотношения между корреляционной иммунностью, нелинейностью и весом для неуравновешенных булевых функций. // Материалы V молодежной научной школы по дискретной математике и ее приложениям (Москва, 12-17 ноября 2001 г.). М.: издательство центра прикладных исследований при механико-математическом факультете МГУ, 2002. С. 20-26.

5. Ботев А. А. Об алгебраической иммунности рекурсивных конструкций нелинейных фильтров. // Научные и методологические проблемы

информационной безопасности. Материалы конференции в МГУ (28-29 октября 2004 г.). М.: МЦНМО, 2005. С. 131-135.

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

7. TarannikovYu., KorolevP., BotevA. Autocorrelation coefficients and correlation immunity of Boolean functions. // Proceedings of Asiacrypt 2001. Lect. Notes in Сотр. Sci. Springer, 2001. V. 2248. P. 460-479. (БотевА.А. доказал ряд теорем из главы 1).

Издательство ЦПИ при механико-математическом факультете МГУ им. М.В. Ломоносова. Подписано в печать 5 Ю, 05 Формат 60x90 1/16. Усл. печ. л. 10

Тираж 100 экз. Заказ ¡3

< \

»18702

РНБ Русский фонд

2006-4 15889

1. Ботев А. А., О соотношении между корреляционной иммунностью, нелинейностью и весом для неуравновешенных булевых функций, Математические вопросы кибернетики, Вып. 11, М., Физматлит, 2002, с. 149-162.

2. Ботев А. А., Об алгебраической иммунности рекурсивных конструкций нелинейных фильтров, Материалы III общероссийской конференцииМатематика и безопасность информационных технологий"(МаБИТ-04), Москва, 28-29 октября 2004 г., М.: МЦНМО, 2005. С. 131-135.

3. Ю. В. Таранников. Числовые характеристики булевых функций. В сб.: Дискретная математика и ее приложения, Сборник лекций, ч. 1, с. 129144, Москва, 2001.

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

5. Ю. В. Таранников, Д. П. Кириенко. Спектральный анализ коррелляционно-иммунных функций высокого порядка. В сб.: Материалы XI Межгосударственной школы-семинара "Синтез и сложность управляющих систем", ч. 2, с. 177-189, Москва, 2001.

6. В. Феллер. Введение в теорию вероятностей и ее приложения, т. 1, с. 7073, М., "Мир", 1984.

7. Carlet C., On the algebraic thickness and non-normality of Boolean functions, Proceedings of 2003 IEEE Information Theory Workshop, Paris, France March 31-April 4, 2003.

8. Camion P, Carlet C., Charpin P., Sendrier N., On correlation-immune functions, Advanced in Cryptology: Eurocrypt'91, Brighton, UK, April 8-11, 1991, Proceedings, Lecture Notes in Computer Science, V. 547, pp. 86-100, Springer-Verlag, 1991.

9. Courtois N., Meier W., Algebraic attacks on stream ciphers with linear feedback, Advanced in Cryptology: Eurocrypt 2003, Warsaw, Poland, May 4-8, 2003, Proceedings, Lecture Notes in Computer Science, V. 2656, pp. 345-357, Springer-Verlag, 2003.

10. Dalai D.K., Gupta K.C., Maitra S., Results on algebraic immunity for crypto-graphically significant Boolean functions, Indocrypt 2004, Chennai (Madras),1.dia, December 20-22, Proceedings, Lecture Notes in Computer Science, to appear.

11. Dillon J.F., Elementary Hadamard Difference Sets, Ph. D. thesis, University of Maryland, USA, 1974.

12. Meier W., Pasalic E., Carlet C., Algebraic attack and decomposition of Boolean functions, Proceedings of Eurocrypt 2004, Interlaken, Switzerland, May 2-6, 2004, Lecture Notes in Computer Science, V. 3027, pp. 474-491, Springer-Verlag, 2004.

13. Pasalic E., Degree optimized resilient Boolean functions from Maiorana-McFarland class, in 9-th IMA Conference on Cryptography and Coding, 2003.

14. Rothaus O.S., On "bent"functions, Journal of Combinatorial Theory, Series A, Vol. 20 (1976), pp. 300-305.

15. Sarkar P., Maitra S., Nonlinearity bounds and constructions of resilient boolean functions, In Advanced in Cryptology: Crypto 2000, Proceedings, Lecture Notes in Computer Science, V. 1880, 2000, pp. 515-532.

16. Siegenthaler Т., Decrypting a Class of Stream Ciphers Using Ciphertext Only, IEEE Transactions on Computer, V. C-34, No 1, Jan. 1985, pp. 81-85.

17. Tarannikov Yu., On resilient Boolean functions with maximal possible non-linearity, Proceedings of Indocrypt 2000, Calcutta, India, December 10-13, 2000, Lecture Notes in Computer Science, V. 1977, pp. 19-30, Springer-Verlag, 2000.

18. Guo-Zhen Xiao, Massey J., A spectral characterization of correlation-immune combining functions, IEEE Transactions on Information Theory, V. 34, No 3, May 1988, pp. 569-571.