ШВИДКІ АЛГОРИТМИ ПОБУДОВИ k -ВИМІРНИХ НАБЛИЖЕНЬ БУЛЕВИХ ФУНКЦІЙ

Автор(и)

  • Антон Миколайович Олексійчук НТУУ «КПІ»
  • Сергій Миколайович Конюшок НТУУ «КПІ»
  • Артем Юрійович Сторожук НТУУ «КПІ»

DOI:

https://doi.org/10.18372/2410-7840.17.8322

Ключові слова:

потоковий шифр, нелінійний криптоаналіз, кореляційна атака, k -вимірна булева функція, швидкий алгоритм, знаходження наближень булевих функцій,

Анотація

Знаходження наближень булевих функцій у певних класах функцій, що мають більш просту будову, є традиційноюзадачею симетричної криптографії. Зокрема, при побудові кореляційних атак на потокові шифри потрібно знаходи-ти наближення булевих функцій від n змінних k -вимірними функціями, тобто такими, що є афінно еквівалент-ними функціям від k  n змінних. Основним результатом статті є алгоритм побудови списку всіх k -вимірнихфункцій степеня не вище d , які знаходяться на відносній відстані не більше 2 (1 ) d    від булевої функції n змін-них, що задається вектором її значень, 1 d  k  n,  (0,1) . Запропонований алгоритм є більш ефективним упорівнянні з найкращим раніше відомим (у певних випадках – в 1000 та більше разів) і може бути застосований напрактиці при дослідженні кореляційних властивостей функцій ускладнення потокових шифрів.

Біографії авторів

Антон Миколайович Олексійчук, НТУУ «КПІ»

доктор технічних наук, професор Інституту спеціального зв’язку та захисту інформації

Сергій Миколайович Конюшок, НТУУ «КПІ»

кандидат технічних наук, доцент, заступник начальника Інституту спеціального зв’язку та захисту інформації

Артем Юрійович Сторожук, НТУУ «КПІ»

аспірант Інституту спеціального зв’язку та захисту інформації

Посилання

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

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

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

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

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

А.Н. Алексейчук, С.Н. Конюшок, А.Ю. Сторожук // Радиотехника. 2014. Вып. 176. С. 13 – 21.

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

. Сачков В.Н. Введение в комбинаторные методы дискретной математики / В.Н. Сачков. М.:МНЦНМО, 2004. 424 с.

. 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.

. Bshouty N. More efficient PAC-learning of DNF with membership queries under the uniform distribution / N. Bshouty, J. Jackson, C. Tamon // Proc. 12th Annual Conf. on Comput. Learning Theory, 1999. P. 286 – 295.

. 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.

. Carlet C. An infinite class of balanced functions with optimal algebraic immunity, good immunity to fast algebraic attacks, and good nonlinearity / C. Carlet, K. Feng // ASIACRYPT’08, Proceedings. Berlin. Springer-Verlag, 2008. P. 425–440.

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

. 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.

. 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.

. 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.

. 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.

. De Wolf R. A brief introduction to Fourier analysis on the Boolean cube / R. de Wolf // Theory of Comput. Library. 2008. № 1. P. 1– 20.

##submission.downloads##

Опубліковано

2015-06-03

Як цитувати

Олексійчук, А. М., Конюшок, С. М., & Сторожук, А. Ю. (2015). ШВИДКІ АЛГОРИТМИ ПОБУДОВИ k -ВИМІРНИХ НАБЛИЖЕНЬ БУЛЕВИХ ФУНКЦІЙ. Захист інформації, 17(1), 43–52. https://doi.org/10.18372/2410-7840.17.8322

Номер

Том 17 № 1 (2015)

Розділ

Статті

Ліцензія

Науковий журнал дотримується принципів відкритого доступу (Open Access) та забезпечує вільний, негайний і постійний доступ до всіх опублікованих матеріалів без фінансових, технічних або юридичних обмежень для читачів.

Усі статті публікуються у відкритому доступі відповідно до ліцензії Creative Commons Attribution 4.0 International (CC BY 4.0).

Авторські права

Автори, які публікують свої роботи в журналі:

  • зберігають за собою авторські права на свої публікації;

  • надають журналу право на перше опублікування статті;

  • погоджуються на поширення матеріалів за ліцензією CC BY 4.0;

  • мають право повторно використовувати, архівувати та поширювати свої роботи (у тому числі в інституційних та тематичних репозитаріях) за умови посилання на первинну публікацію в журналі.