WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 | 2 ||

В данной работе предлагается аппроксимировать булевы функции от m переменных v1,..., vm функциями вида u, (v), где k любая перестановка на m переменных, параметры u Zm, k (k m/2) произвольны. Класс m всех таких аппроксимирующих функций может быть описан следующим образом. Пусть АНФ(f) алгебраическая нормальная форма функции f; пусть Act(f) подмножество максимальной мощности множества {1, 2,..., m/2} такое, что для любых различных элементов i, j из Act(f) одночлены v2i-1v2j-1, v2i-1v2j, v2iv2j-1, v2iv2j принадлежат множеству АНФ(f). Через = (f) обозначим любую перестановку m переменных такую, что |Act(f)| = max |Act(f)|, где по определению Sm f(·) = f((·)). Справедлива Теорема 8. Булева функция f Fm, степени не больше двух, такая что f(0) = 0, принадлежит классу m тогда и только тогда, когда f удовлетворяет условиям 1) для любых различных чисел i, j (1 i, j m/2) одночлены v2i-1v2j-1, v2i-1v2j, v2iv2j-1, v2iv2j одновременно принадлежат / не принадлежат АНФ(f);

2) множество АНФ(f) не содержит одночлены вида v2i-1v2i;

3) в точности одна из переменных v2i-1, v2i принадлежит АНФ(f) для каждого элемента i Act(f).

Из теоремы 8 следует, что множество аппроксимирующих функций состоит из 2m (т. е. всех) линейных функций и не более чем 2m(1+log m) квадратичных функций, что не ограничивает криптоаналитика в возможности их полного перебора.

Выбор таких функций для аппроксимации обусловлен наличием простых формул для вычисления расстояния Хэмминга от произвольной булевой функции f до класса Ak () функций u, (v) при k m,фиксированных параметрах и k:

(k) dist(f, Ak ()) = 2m-1 - max Wf ((v)), m,vZm а также свойствами таких функций, близкими к линейным.

Исследования носят теоретический характер. Предложены модификации алгоритмов 1 и 2 линейного криптоанализа Мацуи [19] для расширенного класса аппроксимирующих функций. Приведены формулы для вычисления абсолютных значений преобладаний и надежности алгоритмов. Показано, что использование k-бент-функций в качестве функций шифрования позволяет снижать максимальное абсолютное значение преобладания до его минимального значения, а следовательно максимально повышать стойкость шифра к данным квадратичным аппроксимациям.

key Пусть F : Zm Zm Zm функция шифрования блочного шиф2 2 ра; P, C и K открытый текст, шифротекст и ключ соответственно.

Пусть вещественное число (K) преобладание равенства a, (P ) b, (C) = d, (K), i j k key при фиксированном ключе K, где a, b Zm, d Zm, перестанов2 ки, Sm, Sm, целые числа i, j, k некоторым образом key выбранные параметры. Упомянутую выше роль k-бент-функций в блочном шифре отражает следующее утверждение.

Теорема 9. Пусть фиксирован ключ K. Если вектор b, перестановки, и параметр j, таковы что функция b, (F (-1(·), K)) : Zm Zm j 2 является (m/2)-бент-функцией, то справедливо равенство max |(K)| = min |(K)| = 2-(m/2)-1.

i,k,a,d, i,k,a,d, Приведены свойства аппроксимирующих функций u, (v), котоk рые могут быть использованы при согласовании нелинейных раундовых аппроксимаций в квадратичном криптоанализе. В заключение рассмотрены примеры четырехразрядных подстановок, рекомендованных для применения в узлах замены (S-блоках) алгоритмов ГОСТ 28147-89, DES, s3DES; с помощью компьютера показано, что для всех этих подстановок (кроме одной) существуют более вероятные (по сравнению с линейными) квадратичные соотношения специального вида на входные и выходные биты этих подстановок.

Результаты четвертой главы опубликованы в работах [35, 36, 38].

В пятой главе диссертации приводится доказательство Теоремы 1, формулировка которой дана в первой главе. Результаты главы опубликованы в работах [27, 28, 29].

Благодарности. Я искренне признательна своему научному руководителю Ю. Л. Васильеву (Институт математики им. С. Л. Соболева) за неизменную поддержку и постоянное внимание к данной работе. Моя самая глубокая благодарность А. А. Нечаеву (Московский государственный университет) и Л. А. Бассалыго (Институт проблем передачи информации им. А. А. Харкевича, Москва), проявившим неподдельный интерес к моей работе и высказавшим немало ценных замечаний и критики. Я очень благодарна сотрудникам института математики им. С. Л. Соболева: Д. С. Кротову за ценные замечания, позволившие существенно расширить множество кодов, для которых справедлива Теорема 1, и В. Н. Потапову, взявшему на себя труд прочитать рукопись и указавшему на целый ряд неточностей. Мне очень приятно выразить признательность профессору Патрику Сол (Национальный Центр Научных Исследований е CNRS, София Антиполис, Франция) за гостеприимство и увлекательную совместную работу в области бент-функций, благодаря которой удалось узнать много нового. С большим удовольствием я благодарю Лилию Будагян (Университет Бергена, Норвегия) за консультации по векторным бент-функциям, внимательное прочтение текста и замечания, которые трудно переоценить. Отдельную благодарность я приношу всем рецензентам печатных работ, обратившим мое внимание на многие существенные вопросы.

Список литературы [1] Буряков М. Л., Логачев О. А. Об уровне аффинности булевых функций // Дискретная математика. 2005. Т. 17, N 4. С. 98–107.

[2] Кротов Д. С. Z4-линейные совершенные коды // Дискрет. анализ и исслед. операций. Сер. 1. 2000. Т. 7, N 4. С. 78–(translated athttp://arxiv.org/abs/0710.0198).

[3] Логачев О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: Московский центр непрерывного математического образования, 2004.

[4] Нечаев А. А. Код Кердока в циклической форме // Дискретная математика. 1989. Т. 1, N 4. С. 123–139.

[5] Agievich S. V. On the representation of bent-functions by bentrectangles // Fifth Int. Petrozavodsk conf. on probabilistic methods in discrete mathematics (Petrozavodsk, Russia. June 1–6, 2000).

Proc. Boston: VSP, 2000. P. 121–135.

[6] Biham E., Shamir A. Differential cryptanalysis of DES-like cryptosystems // J. Cryptology. 1991. V. 4, N 1. P. 3–72.

[7] Carlet C. Boolean functions for cryptography and error correcting codes // Chapter of the monograph Boolean Methods and Models, Cambridge Univ. Press (P. Hammer, Y. Crama eds.), to appear. Prelim. version is available at www-rocq.inria.fr/secret/Claude.Carlet/chap-fcts-Bool.pdf.

[8] Carlet C. Vectorial Boolean functions for cryptography // Chapter of the monograph Boolean Methods and Models, Cambridge Univ. Press (P. Hammer, Y.

Crama eds.), to appear. Prelim. version is available at www-rocq.inria.fr/secret/Claude.Carlet/chap-vectorial-fcts.pdf.

[9] Carlet C., Klapper A. Upper bounds on the numbers of resilient functions and of bent functions // 23rd Symposium on Information Theory (Benelux, Belgium. May, 2002) Proc. 2002. P. 307-314. The full version will appear in Lecture Notes dedicated to Philippe Delsarte.

[10] Dillon J. F. A survey of bent functions // The NSA Technical J.

1972. Special Issue. P. 191–215.

[11] Dillon J. F. Elementary Hadamard difference sets // Ph. D. Thesis, Univ. of Maryland, 1974.

[12] Dobbertin H., Leander G. A survey of some recent results on bent functions // Sequences and their applications. – SETA 2004. Third Int. conference (Seul, Korea. October 24–28, 2004). Revised selected papers. Berlin: Springer, 2005. P. 1–29 (Lecture Notes in Comput.

Sci. V. 3486).

[13] Hammons A. R., Kumar P. V., Calderbank A. R., Sloane N. J.

A., Sol P. The Z4-linearity of Kerdock, Preparata, Goethals, and related codes // IEEE Trans. Inform. Theory. 1994. V. 40, N 2. P.

301–319.

[14] Kantor W. M. Codes, quadratic forms and finite geometries // Proceedings of Symposia in Applied Math. 1995. V. 50. P. 153–177.

[15] Kavut S., Maitra S., Yucel M. D. Search for Boolean functions with excellent profiles in the rotation symmetric class // IEEE Trans.

Inform. Theory. 2007. V. 53, N 5. P. 1743–1751.

[16] Kerdock A. M. A class of low-rate non-linear binary codes // Inform. Control. 1972. V. 20, N 2. P. 182–187.

[17] Knudsen L. R., Robshaw M. J. B. Non-linear approximation in linear cryptanalysis // Advances in Cryptology – EUROCRYPT’96.

Workshop on the theory and application of cryptographic techniques (Saragossa, Spain. May 12–16, 1996). Proc. SpringerVerlag. 1996. P. 224–236 (Lecture Notes in Comput. Sci. V. 1070).

[18] Krotov D. S. Z4-linear Hadamard and extended perfect codes // Proc. of the Int. Workshop on Coding and Cryptography (Paris, France. January 8–12, 2001). P. 329–334.

[19] Matsui M. Linear cryptanalysis method for DES cipher // Advances in Cryptology EUROCRYPT’93. Workshop on the theory and application of cryptographic techniques (Lofthus, Norway. May 23– 27, 1993). Proc. Berlin: Springer, 1994. P. 386–397 (Lecture Notes in Comput. Sci. V. 765).

[20] McFarland R. L. A family of difference sets in non-cyclic groups // J. Combin. Theory. Ser. A. 1973. V. 15, N 1. P. 1–10.

[21] Olsen J. D., Scholtz R. A., Welch L. R. Bent-function sequences // IEEE Trans. Inform. Theory. 1982. V. 28, N 6. P. 858–864.

[22] Riera C., Parker M.G. Generalised bent criteria for Boolean functions (I) // IEEE Trans. Inform. Theory 2006. V. 52, N 9.

P. 4142–4159.

[23] Rothaus O. On bent functions // J. Combin. Theory. Ser. A. 1976.

V. 20, N 3. P. 300–305.

[24] Schmidt K-U. Quaternary constant-amplitude codes for multicode CDMA // Available athttp://arxiv.org/abs/cs.IT/0611162.

[25] Sol P. A quaternary cyclic code, and a family of quadriphase sequences with low correlation properties // Third International Colloquium Coding Theory and Applications (Toulon, France.

November 2–4, 1988). Proc. Springer. 1989. P. 193–201 (Lecture Notes in Comput. Sci. V. 388).

Публикации автора по теме диссертации (доступны по адресуwww.math.nsc.ru/tokareva) [26] Токарева Н. Н. Иерархия классов бент-функций кратной нелинейности // Материалы VI молодежной научной школы по дискретной математике и ее приложениям (Москва, Россия. 16–апреля, 2007) Часть III, 2007. С. 5–11.

[27] Токарева Н. Н. О верхней оценке числа равномерно упакованных двоичных кодов // Материалы VI молодежной научной школы по дискретной математике и ее приложениям (Москва, Россия. 16–21 апреля, 2007) Часть III, 2007. С. 11–16.

[28] Tokareva N. N. An upper bound for the number of uniformly packed codes // IEEE International Symposium on Information Theory ISIT’2007. (Nice, France. June 24–29, 2007). Proc. 2007. P. 346–350.

[29] Токарева Н. Н. О верхней оценке числа равномерно упакованных двоичных кодов // Дискрет. анализ и исслед. операций.

Сер. 1. 2007. Т. 14, N 3. С. 90–97.

[30] Tokareva N. N. On k-bent functions // Вестник Томского госуниверситета. Приложение. 2007. N 23. С. 74–76.

[31] Токарева Н. Н. Бент-функции кратной нелинейности: k-бентфункции // Материалы российской конференции Математика в современном мире (Новосибирск, Россия. 17–21 сентября, 2007). С. 288–289.

[32] Токарева Н. Н. Бент-функции с более сильными свойствами нелинейности: k-бент-функции // Дискрет. анализ и исслед.

операций. Сер. 1. 2007. Т. 14, N 4. С. 76–102.

[33] Tokareva N. N. k-Bent functions and quadratic approximations in block ciphers // Proc. Fourth International Conference BFCA Boolean Functions: Cryptography and Applications (Copenhagen, Denmark, May 19–21, 2008). P. 132–148.

[34] Токарева Н. Н. k-Преобразование Уолша-Адамара в теории кодирования и криптографии // Материалы XV Международной конференции Проблемы теоретической кибернетики (Казань, Россия, 2–7 июня, 2008). С. 113–114.

[35] Tokareva N. N. k-Bent functions: from coding theory to cryptology // Proc. First IEEE International Conference SIBIRCON Computational Technologies in Electrical and Electronics Engineering (Novosibirsk, Russia, July 21–25, 2008). P. 36–40.

[36] Токарева Н. Н. О квадратичных аппроксимациях в блочных шифрах // Пробл. передачи информ. 2008. Т. 44, Вып. 3. С.

105–127.

[37] Токарева Н. Н. Описание k-бент-функций от четырех переменных // Дискр. анализ и исслед. операций. 2008. Т. 15, N 4. С.

74–83.

[38] Токарева Н. Н. Квадратичные аппроксимации специального вида для четырехразрядных подстановок в S-блоках // Прикладная дискретная математика. 2008. Т. 1, N 1. С. 50–54.

Токарева Наталья Николаевна Сильно нелинейные булевы функции:

бент-функции и их обобщения Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Подписано в печать 2 октября 2008 г. Формат 60x84 1/16.

Усл. печ. л. 1,4. Уч.-изд. л. 1,4.

Тираж 140 экз. Заказ N 173.

Отпечатано в ООО "Омега Принт" 630090 Новосибирск, пр. Лаврентьева, 6.

Pages:     | 1 | 2 ||






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»