Алгебраически вырожденные приближения булевых функций PDF

Автори:А.Н. Алексейчук, С.Н. Конюшок

А.Н. Алексейчук, С.Н. Конюшок

УДК 519.7

Алгебраически вырожденные приближения булевых функций / Алексейчук А.Н., Конюшок С.Н. // Кибернетика и системный анализ.

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

Библиогр.: 12 назв.

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

УДК 519.7

Алгебраїчновиродженінаближеннябулевихфункцій/ ОлексійчукА.М., КонюшокС.М. // Кібернетикаісистемнийаналіз.

Досліджуються властивості -вимірних наближень булевих функцій. Одним з основних результатів є теорема про будову -вимірних функцій степеня , що знаходяться на відстані не біля , , від заданої булевої функциі  змінних, , . Ця теорема суттєво підсилює раніше відомий результат П. Гопалана та дозволяє помітно підвищити ефективність запропонованого їм алгоритму побудови усіх зазначених -вимірних булевих функцій.

Бібліогр.: 12 назв.

Первые результаты о корреляционных свойствах алгебраически вырожденных булевых функций относятся к 70-м годам прошлого века [3]. В последнее время интерес к исследованию этих функций обусловлен задачами криптоанализа и теории кодирования. Отметим работы [6 – 8], в которых описан ряд атак на генераторы гаммы поточных шифров, функции усложнения которых являются алгебраически вырожденными или близки к таковым.

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

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

Задача нахождения всех функций , находящихся от заданной функции  на расстоянии не более , , является более трудной. Существенный вклад в ее решение сделан в работе [2], посвященной изучению -мерных приближений функций от  переменных над произвольным конечным полем. Одним из основных результатов этой работы является теорема, описывающая строение -мерных функций степени не выше  над полем , находящихся от заданной функции  на расстоянии не более , где  – минимальное расстояние кода Рида-Маллера , ,  (см. [2], п. 4). В настоящей статье доказана теорема, существенно усиливающая этот результат для случая булевых функций. Получен также  ряд утверждений о свойствах -мерных приближений булевых функций, дополняющих и уточняющих отдельные результаты работ [5, 9].

References

1. Gopalan, P. Testing Fourier dimensionality and sparsity / P. Gopalan, R. O’Donnel, A. Servedio, A. Shpilka, K. Wimmer // SIAM J. on Computing. 2011. V. 40(4). P. 1075–1100.

2.Gopalan, P. A Fourier-analytic approach to Reed-Muller decoding / P. Gopalan // Annual IEEE Symp. on Foundation in Computer Science. – FOCS 2010, Proceedings. Berlin. Springer-Verlag. 2010. P. 685–694.

3. Lechner, R. L. Harmonic analysis of switching functions / R. L. Lechner // Recent Developments in Switching Theory. New-York. Academic Press. 1971. P. 122–228.

4. Dawson, E. Construction of correlation immune Boolean functions / E. Dawson, C.K. Wu // Information and Communication Security, Proceedings. Berlin. Springer-Verlag. 1997. P. 170–180.

5. Алексеев, Е. К. О некоторых мерах нелинейности булевых функций / Е. К. Алексеев // Прикладная дискретная математика. 2011. № 2(12). С. 5–16.

6. Daemen, J. Resynchronization weaknesses in synchronous stream ciphers / J. Daemen, R. Govaerts, J. Vandewalle // Advances in Cryptology – EUROCRYPT’93, Proceedings. Berlin. Springer-Verlag. 1993. P. 159–167.

7. Golić, J. On the resynchronization attack / J. Golić, G. Morgari // Fast Software Encryption. – FSE’03, Proceedings. Berlin. Springer-Verlag. 2003. P. 100–110.

8. Алексеев, Е. К. Об атаке на фильтрующий генератор с функцией усложнения, близкой к алгебраически вырожденной / Е. К. Алексеев // Сборник статей молодых ученых факультета МВК МГУ, 2011. В. 8. С. 114–123.

9. Canteaut, A. On the correlations between a combining function and function of fewer variables / A. Canteaut // The 2002 IEEE Information Theory Workshop, Proceedings. Berlin. Springer-Verlag. 2002. P.78–81.

10. Алексейчук, А. Н. Усовершенствованный тест k-мерности для булевых функций / А.Н.Алексейчук, С. Н. Конюшок // Кибернетика и системный анализ. 2013. T. 49. № 2. С. 27–35.

11.Alekseychuk, A. N. Fast algorithm for reconstruction of high-probable low-dimensional approximations for Boolean functions / A. N. Alekseychuk, S. N. Konyushok // Modern Stochastics: Theory and Applications III, Proceedings. Kyiv. Taras Shevchenko National University. 2012. P. 32.

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

 

 

Сайт видання:http://www.kibernetika.org/