Том 15, номер 6, 2008 г., Стр. 34-47
УДК 517.7, 519.1
М. С. Лобанов
Точные соотношения между нелинейностью и алгебраической иммунностью
Аннотация:
Усилены некоторые нижние оценки нелинейности высоких порядков булевой функции через значения её алгебраической иммунности и получены новые точные оценки. Доказана универсальная точная нижняя оценка, позволяющая сводить проблему оценки нелинейности высоких порядков к проблеме поиска размерности некоторых линейных подпространств в пространстве булевых функций. Как простое следствие этого результата получены все ранее известные оценки в этой области. Для бесповторных полиномов поиск размерности упомянутых выше линейных подпространств в пространстве булевых функций сведён к простому комбинаторному анализу. Для булевой функции доказана точная нижняя оценка её нелинейности второго порядка через значение алгебраической иммунности.
Ключевые слова: потоковый шифр, нелинейный фильтр, алгебраическая атака, булева функция, алгебраическая иммунность, степень булевой функции, нелинейность, нелинейность высокого порядка, аннигилятор.
Лобанов Михаил Сергеевич 1
1. Московский государственный университет им. М. В. Ломоносова,
Воробьёвы горы, 119992 Москва, Россия
е-mail: misha_msu@mail.ru
Статья поступила 7 апреля 2008 г.
