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

Кратко эти способы как раз и можно охарактеризовать как «операторно-табличные». Построение устойчивых функций с максимально возможной нелинейностью, к сожалению, не решает задачу построения булевых функций с удовлетворительными криптографическими характеристиками. В частности, одной из нежелательных особенностей является наличие у построенной булевой функции значительного числа переменных, от которых она зависит линейно, и как следствие, с появляющимися в этом случае возможностями линеаризации соответствующих криптографических задач. Как показывают имеющиеся результаты, устойчивые функции с максимальными возможными значениями нелинейности, полученные известными в настоящее время способами, как правило, имеют переменные, от которых они зависят линейно. В [3] введено понятие профиля нелинейности булевой функции, то есть последовательности, r-й членкоторой равен степени нелинейности r-го порядка nlr (f), равной расстоянию функции f до класса функций, чья алгебраическая степень не превосходит r. В [27] получена нижняя оценка для параметра nlr (f) для функции f с AI (f) = k: и обсуждаются вопросы, связанные с применением данной характеристики булевой функции к криптоанализу. В [2] применен новый подход к получению нижних оценок параметра nlr (f). Доказана теорема, следствием из которой является оценка. Для случая r = 2 эта оценка улучшена. Доказано, что для функции f сAI (f) = k выполнено неравенство:

Более того, показано, что эта оценка достижима. Заключение

Как видно из результатов, представленных в настоящей работе, кор-реляционно-иммунные и устойчивые булевы функции и отображения являются хорошо известным математическим объектом, тесно связанным с комбинаторикой, теорией кодов, криптологией и некоторыми другими областями математики. Этот объект активно исследуется большим количеством математиков. Ежегодно публикуются десятки статей и тезисов, посвящённых изучению различных свойств корреляционно-иммунных булевых функций и отображений (причём не только уравновешенных — [2]).С точки зрения криптографических приложений естественно наиболее привлекательными являются уравновешенные функции, обладающие и другими важными криптографическими свойствами такими, как нелинейность. Верхние границы для нелинейности произвольной корреляци-онно-иммунной функции и устойчивой функции были получены в работе [3]. Эти оценки используют лишь порядок устойчивости булевой функции. В работе [4] при построении верхней оценки для нелинейности булевой функции была использована также и её алгебраическая степень. Для с-регулярных булевых функций получена верхняя оценка для её нелинейности получена с использованием аппарата покрывающих последовательностей. Наличие у булевой функции определённого количества линейных переменных оценивается как её потенциальная криптографическая слабость.

Интересным с этой точки зрения является выяснение вопроса о числе (либо об оценке числа) линейных переменных в алгебраической нормальной форме некоторых классов устойчивых функций высокого порядка. Автокорреляционные (или дифференциальные) характеристики корреляционно-иммунных и устойчивых булевых функций, которые считаются важнейшими криптографическими характеристиками наряду с нелинейностью, в известном смысле находятся в противоречии с корреляционной иммунностью. Неравенство Зигенталлера позволяет дать очевидную верхнюю оценкудля числа m-устойчивых функций из. Представляются интересными также вопросы вычисления мощностей (либо их оценка) различных классов корреляционно-иммунных и устойчивых функций. В [5] рассмотрена модифицированная задача о радиусе покрытия кода RM (r, т). Радиус покрытия определяется как максимальное расстояние между т-устойчивыми функциями изи кодом RM (r, т).

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

Список литературы

Логачёв О.А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии

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

11. М.: Физматлит, 2002. С. 149−162.Sarkar P. M aitra S. N onlinearity Bounds and Constructions of Resilient Boolean Functions with Important Cryptographic Properties // In Proceedings of Advances in Cryptology: CRYPTO'2000.

L ect. N otes in Comp. S ci. N ew York: Springer-Verlag, 2000.

V. 1880. P. 515—532.CarletС. O

n the Coset Weight Divisibility and Nonlinearity of Resilient and Correlation Immune Functions // Sequences and Their Applications: S£7i4'2001, Discrete Mathematics and Theoretical Computer Science. N ewYork: Springer-Verlag, 2001. P. 131 — 144. Kurosawa К., Iwata Т., Yoshiwara T. N ew covering radius of Reed—Muller codes for / -resilient functions // S/4C'2001.

L ect. N otesinComp. S pringer-Verlag, 2001.

S ci. № 2259, P. 75−86.Courtois N., Meier W. A

lgebraic Attacks on Stream Ciphers with Linear Feedback // Proceedings of Eurocrypt 2003, LectureNotes in Computer Sciences. 2003. V. 2656. P. 345 — 359. Courtois N. F ast Algebraic Attacks on Stream Ciphers with Linear Feedback // Proceedings of Crypto 2003, Lecture Notes inComputer Sciences.

2003. V. 2729. P. 176 — 194. Meier W., Pasalic E., Carlet C.

A lgebraic Attacks and Decomposition of Boolean Functions // Proceedings of Eurocrypt2004, Lecture Notes in Computer Sciences. 2004. V.

3027. P. 474 — 491. Meier W., Pasalic E., Carlet C. A lgebraic Attacks and Decomposition of Boolean Functions // Proceedings of Eurocrypt2004, Lecture Notes in Computer Sciences. 2004. V. 3027.

P. 474 — 491.