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

Многие потоковые шифры состоят из линейной части, порождающей последовательность с большим периодом, обычно состоящей из одного или нескольких регистров сдвига с линейной обратной связью (linear feedback shift registers, LFSR), и нелинейной комбинирующей функции /, которая порождает выходную последовательность по данным линейным входам. Исследования криптографической устойчивости таких шифров большей частью сводятся к исследованию нелинейной функции /, в частности, к исследованию этой функции с точки зрения того, удовлетворяет или не удовлетворяет она некоторым критериям, необходимым для того, чтоб успешно противостоять различным криптографическим атакам.

Для того, чтобы противостоять этим атакам (таким, как атакам Берлекэм-па-Мэсси, различным типам корреляционных и линейных атак [47, 38, 20] и алгебраической атаке (см. [26])), функция должна удовлетворять следующим критериям:

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

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

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

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

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

Также важными критериями являются низкая автокорреляция, простая схемная реализация и т. д.

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

Настоящая работа посвящена взаимосвязи алгебраической иммунности и нелинейности различных порядков.

Пусть / является булевой функцией над .Кр. Известно, что / единственным образом представляется полиномом. Степенью булевой функции называется длина самого длинного слагаемого в ее полиноме (количество переменных в этом слагаемом). Булева функция д над ^ называется аннигилятором булевой функции / над Р2П, если /д = 0. Очевидно, что аннигиляторы / образуют линейное подпространство в пространстве всех булевых функций от п переменных.

Определение 1 Алгебраической иммунностью А1(/) булевой функции / над ^ называется степень булевой функции д над, где д не равная тождественно нулю функция с минимальной степенью, такая что $д = 0 или (/ + 1) д = 0.

Известно [26, 42], что для любой / над выполнено.

AI (f)< if" !- (1).

В [29] доказано, что доля уравновешенных функций / от п переменных, для которых выполнены неравенства ^ — Inn < AI (f) < стремится к единице при п —> оо. То есть алгебраическая иммунность почти всех уравновешенных булевых функций от п переменных имеет асимптотический порядок п/2 — максимально возможный.

Алгебраическая иммунность — это способность противостоять разного рода алгебраическим атакам на регистры сдвига с линейной обратной связью (linear feedback shift registers, LFSR). Эти атаки впервые были предложены в [26]. Они раскрывают секретный ключ путем решения системы уравнений, зависящих от многих переменных. Данные системы уравнений описывают соотношения между битами ключа/состояния и выходными битами / (комбинирующей функции для LFSR). Если найдено такое соотношение низкой степени, алгебраические атаки очень эффективны ([28]).

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

В [26] предложено три разновидности такого рода атак. В [42] авторы сводят эти три вида к двум и вводят новый термин — алгебраическая иммунность. Авторы доказывают, что если алгебраическая иммунность достаточно высока, то алгебраическим атакам можно успешно противостоять.

Ранее важными критериями для комбинирующих функций в LFSR признавались высокая алгебраическая степень, высокий порядок корреляционной иммунности (устойчивости) и большое расстояние до множества аффинных функций (высокая нелинейность), чтобы успешно противостоять атакам Берлекэмпа-Мэсси и различным типам корреляционных и линейных атак [38, 20], а также достаточно большое расстояние до полиномов невысоких степеней (нелинейность r-тых порядков).

Требование высокой алгебраической иммунности может конфликтовать с требованиями удовлетворения остальным критериям. В [42] авторы показали, что, например, функции класса Майораны-Макфарланда, имеющие высокую устойчивость, высокую нелинейность (асимптотически порядка 2n1) и оптимальную алгебраическую степень ([33, 18, 23, 46], — имеют при этом достаточно низкую алгебраическую иммунность и не могут противостоять алгебраическим атакам.

Весом wt (x) набора х из называется число единиц в х. Расстояние между булевыми функциями f и /2 определяется как d{f. /2) =| {х Е .F21 j h (x) ^ f2(x)} .

Определение 2 Нелинейностью г-го порядка nlr (f) булевой функции f над называется min deg (Z).

Нелинейностью nl (f) функции / называется расстояние между / и множеством аффинных функций, т. е. нелинейность первого порядка.

Отметим, что на языке теории кодирования нелинейность r-го порядка d (fj). функции — это расстояние функции до ЯМ (г, п) кода Рида-Маллера г-го порядка.

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

С точки зрения криптоанализа от булевой функции, используемой в качестве фильтра в потоковом шифре, надо требовать не только достаточно высокой нелинейности первого порядка, но и высокой нелинейности других порядков. В этом можно убедиться по работам [27, 35, 37, 40, 41, 45].

Настоящая работа посвящена проблеме оценки снизу нелинейности г-го порядка функции через значение ее алгебраической иммунности.

Получение таких оценок дает не только информацию о взаимосвязи этих двух свойств, но важно еще и по следующей причине. Если вопросы связанные с нелинейностью п1(/) = Ы^) достаточно хорошо изучены и существует аппарат коэффициентов Уолша, который позволяет ее вычислять, то с нелинейностью более высоких порядков все обстоит заметно хуже. Про п1г (/) при г > 2 мало что известно. Стоит упомянуть наилучшую, как нам известно, на этот момент верхнюю оценку из [24], которая имеет асимптотический вид: пЦЛ < 2П-1 — + у/2)г~22п'2 + 0(пг2). а.

Доказана также достаточно сильная нижняя оценка [25], которая, правда, тоже носит асимптотический характер и поэтому ничего не дает для оценки нелинейности г-го порядка при г > 1 для конкретных функций.

Эффективных алгоритмов подсчета нелинейности порядков выше первого тоже, насколько автору известно, пока не предложено. Интересный алгоритм и его модификации, предложенные в [34, 36, 39], работают только при г = 2 и п < 13.

В свете выше изложенного, получение как можно более сильных нижних оценок нелинейности г-го порядка через значение алгебраической иммунности приобретает особую важность. Отметим, что в [11, 12, 42, 30] был предложен целый ряд алгоритмов подсчета алгебраической иммунности, а в [16, 17, 21, 31] построено несколько семейств функций, имеющих максимально возможную алгебраическую иммунность .

В работе [32] был доказан результат, эквивалентный следующей оценке на нелинейность г-ого порядка:

Позже в [1] автором была доказана нижняя оценка нелинейности (г=1) функции через значение ее алгебраической иммунности:

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

Еще позднее К. Карле в [22] обобщил доказанную автором оценку (3) на случай других г:

Отметим, что ни одна из двух приведенных выше оценок (2) и (4) для нелинейности г-ого порядка не влечет другую.

2).

3).

В работах [43] и [3] была доказана следующая оценка.

А1(Л-г-1 /. А1(/)-г-1 / ч е (:)+ Е (п7. (5) г=0 4 7 г=АГ (/)-2г 4 У более сильная, чем (2) и (4).

В работе [2] была доказана точная оценка для нелинейности второго порядка: п- 2 г — 1 г=0 4 ' г=0 J У / которая достигается при всех допустимых значениях параметров.

В 2008 году автором [5] получена новая оценка нелинейности г-го порядка при г > 2, которая сильней всех ранее известных оценок: АГ (/)—г—1, ч А1(Л-г-1, х АГ (Я-г-2 nfe (/)> Е («) — Е < п / n V.

1 / 1 / U ' ' /.

Е I + Е Т)+а Е i—П N / И ГС f Г)&bdquo- / Л ГС О- 1 п — г — 2 г г=0 4 ' i=AI (f)—2r 4 ' г—Л/(/)—2r—1.

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

Во второй главе проблема получения как можно более сильных нижних оценок нелинейности r-го порядка через значение алгебраической иммунности функции полностью сводится к задаче определения размерности некоторых подпространств Bk (h) = {д{хi,., жп)| deg (g) < /с, deg (gh) < Теорема 1 Пусть f (xi,., хп) имеет AI (f) = к, тогда nlr (f) > min dim (Bk-i (g)). deg (g).

Кроме того, при к < существует функция /о, А/(/0) = к, для которой nlr (fo) = min dim (Bk-i (g)). deg (g).

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

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

В четвертой главе получена оценка на нелинейность второго порядка которая тоже достигается при всех допустимых значениях параметров. Эти результаты удалось получить благодаря сведению проблемы нахождения min dim (Bk~i{g)) из теоремы 1 к задаче комбинаторного подсчета deg{g).

Пятая глава посвящена получению оценки которая при г > 3 является рекордной на настоящий момент.

На страницах 49−51 шестой главы можно найти сравнение оценки 6 с оценками (7) и (5) для конкретных п, и АГ (/) и г = 2.

На страницах 52−57 шестой главы можно найти сравнение оценок (7) и (5) для конкретных п, АГ (/) и г > 3.

Результаты автора по теме диссертации опубликованы в работах [1]—[10].

6).

AI (f)—r—l.

1. М. С. Лобанов. Точное соотношение между нелинейностью и алгебраической иммунностью // Дискретная математика. — 2006. — Т. 18, вып. 3. — С. 152−159.

2. М. С. Лобанов. Точные соотношения между нелинейностью и алгебраической иммунностью // Дискретный анализ и исследование операций. 2008. — Т. 15, вып. 5. — С. 47−60.

3. М. С. Лобанов. Неулучшаемая оценка нелинейности функции через значение алгебраической иммунности // Материалы II международной конференции по проблемам безопасности и противодействия терроризму (МГУ, 25−26 октября 2006). М.: МЦНМО, 2007. — С. 210−217.

4. M.Lobanov. Tight bound between nonlinearity and algebraic immunity. Cryptology ePrint archive (http://eprint.iacr.org/), Report 2005/437.

5. M.Lobanov. Tight bounds between algebraic immunity and nonlinearities of high orders. Cryptology ePrint archive (http://eprint.iacr.org/), Report 2007/444.

6. B. B Баев. Некоторые нижние оценки на алгебраическую иммунность функций, заданных своими след-формами // Пробл. передачи информ. 2008. — Т. 44, вып. 3. — С. 81−104.

7. В. В Баев. Усовершенствованный алгоритм поиска аннигиляторов низкой степени для многочлена Жегалкина // Дискретная математика. — 2007. Т. 19, вып. 4. — С. 132−138.

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

9. Ю. В. Таранников, Д. П. Кириенко. Спектральный анализ коррелляционно-иммунных функций высокого порядка // Материалы XI Межгосударственной школы-семинара «Синтез и сложность управляющих систем». — Москва, 2001. — Ч. 2. — С.177−189.

10. F. Armknecht, M.Krause. Constructing singleand multi-output boolean functions with maximal algebraic immunity // International conference on automata, language and programing 2006. — LNCS 4052, Springer, 2006.— Part II. P. 180−191.

11. A. Braeken, B.Preneel. On the algebraic immunity of symmetric boolean functions // Indocrypt 2005. LNCS 3797, Springer, 2005. — P. 35−48.

12. P. Camion, C. Carlet, P. Charpin, N.Sendrier. On correlation-immune functions // Eurocrypt'91 (Brighton, UK, April 8−11, 1991). — Springer-Verlag, 1991. P. 86−100.

13. A. Canteaut. Open problems related to algebraic attacks on stream ciphers // International Workshop (WCC 2005) (Bergen, March 14−18, 2005) —Berlin/Heidelberg: Springer Verl., 2005. — P. 120−134. (Lecture Notes in Computer ScienceVol. 3969).

14. A. Canteaut, M.Trabbia. Improved fast correlation attacks using Parity-check equations of weight 4 and 5 // Eurocrypt 2000 (Bruges, Belgium, May 14−18, 2000). — Springer-Verlag, 2000. — P. 573−588. (Lecture Notes in Computer ScienceVol. 1807).

15. C.Carle. A method of construction of balanced functions with optimum algebraic immunity / / Cryptology ePrint archive, http://eprint.iacr.org/2006/149.

16. C.Carlet. On the higher order nonlinearities of algebraic immune functions // CRYPTO 2006. Berlin/Heidelberg: Springer, 2006. — P. 584−601. (Lecture Notes in Computer ScienceVol.4117).

17. C. Carlet, S.Mesnager. Improving the upper bounds on the covering radii of binary Reed-Muller codes // IEEE Transactions on Information Theory, 2006.

18. G. Cohen, I. Honkala, S. Litsyn, A.Lobstein. Covering codes. North-Holland, 1997.

19. N. Courtois and W.Meier. Algebraic attacks on stream ciphers with linear feedback // Anvances in cryptology, EUROCRYPT 2003. — Berlin/Heidelberg: Springer Verl., 2003. — P. 345−359. (Lecture Notes in Computer ScienceVol. 2656).

20. N.Courtois. Higher order corralation attacks, XL algorithm and cryptanalysis of Toyocrypt // Proceedings of ICISC 2002. LNCS 2587. — P. 182−199.

21. F.Didier. A new bound on the block error probability after decoding over the erasure channel // IEEE Trans, on Information Theory, vol. IT-52, e 10, 2006.

22. F. Didier, J.P.Tillich. Computing the algebraic immunity efficiently // Fast softwware encryption 2006, LNCS 4047, 2006. P. 359−374.

23. D.K.Dalai, S.Maitra. Balanced Boolean functions with (more than) maximum algebraic immunity / / Cryptology ePrint archive, http://eprint.iacr.org/2006/434.

24. D.K.Dalai, K.C.Gupta and S.Maitra. Results on Algebraic Immunity for Cryptographically Significant Boolean Functions // Indocrypt 2004 (Chen-nai, India, December 20−22, 2004) — Berlin/Heidelberg: Springer Verl., 2004. P. 92−106.

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

26. I. Dumer, G. Kabatiansky, C.Tavernier. List decoding of Reed-Muller codes up to the Johnson bound with almost linear complexity // Proceedings of ISIT 2006. Seattle, USA.

27. J.Golic. Fast low order approximation of cryptographic funtions // Proceedings of EUROCRYPT'96. LNCS 1070, 1996. — P.268−282.

28. R.Fourquet. Une FFT adaptee au decodage par liste dans les codes de Reed-Muller d’ordres 1 et 2 // Master-thesis of the University of Paris VIII, Thales communication, Bois Colombes, 2006.

29. T. Iwata, K.Kurosawa. Probabilistic higher order differential attack and higher order bent function // Proceedings of ASIACRYPT'99. — LNCS 1716, 1999. P.62−74.

30. G. Kabatiansky, C.Tavernier. List decoding of second order Reed-Muller codes //In Proc. 8th Intern. Simp. Comm. Theory and Applications (Ambelside, UK, july 2005).

31. L.R.Knudsen, M.J.B.Robshaw. Non-linear approximations in linear crypt-analysis // Proceedings of EUROCRYPT'96. LNCS 1070, 1996. — P. 224 236.

32. U.M.Maurer. New approaches to the design of self-synchronizing stream ciphers // Proceedings of EUROCRYPT'91. LNCS 547, 1991. — P. 458−471.

33. W. Meier, E. Pasalic and C.Carlet. Algebraic attacks and decomposition of Boolean functions // Advances in Cryptology — EUROCRYPT 2004. — Berlin/Heidelberg: Springer Verl., 2004. — P. 474−491. (Lecture Notes in Computer ScienceVol. 3027).

34. S.Mesnager. Improving the lower bound on the higher order nonlinearity of Boolean functions with prescribed algebraic immunity. Cryptology ePrint archive (http://eprint.iacr.org/), Report 2007/117.

35. F.J.McWilliams, N.J.A.Sloane. The Theory of Error Correcring Codes. New York: North-Holland, 1977. 760 p.

36. W.Millan. Low order approximation of cipher functions // Cryptographic Policy and Algorithms. LNCS 1029, 1996. — P. 144−155.

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

38. T.Siegenthaler. Decrypting a Class of Stream Ciphers Using Ciphertext Only // IEEE Transactions on Computer. — V. C-34, No 1, Jan. 1985. — P. 81−85.