ШВИДКІ АЛГОРИТМИ ПОБУДОВИ 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##
Опубліковано
Номер
Розділ
Ліцензія
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:- Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
- Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
- Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
