FAST ALGORITHMS FOR CONSTRUCTING k - DIMENSIONAL APPROXIMATIONS OF BOOLEAN FUNCTIONS

Authors

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

DOI:

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

Keywords:

stream cipher, non-linear cryptanalysis, correlation attack, k -dimensional Boolean function, fast algorithm, finding approximations of Boolean functions

Abstract

Finding Boolean functions’ approximations in certainclasses of functions with a simple structure, is a traditionaltask in symmetric cryptography. In particular, correlationattacks on stream ciphers need to find approximations ofn -variable Boolean functions by k -dimensional functions,i.e., the functions, which are affine equivalent tofunctions of k  n variables. Main result of this paper isan algorithm for constructing a list of all k -dimensionalfunctions of degree at most d at relative distance notmore than 2 (1) dfrom a given Boolean function of nvariables, defined by the truth table, 1 d  k  n , (0,1) . The proposed algorithm is more efficient thanthe best previously known (in some cases – to 1000 timesand more) and can be used in practice while studying thecorrelation properties of stream cipher’ complicatingfunctions.

Author Biographies

Антон Миколайович Олексійчук, NTUU «KPI»

Doctor of Technical Science, Professor of Institute of Special Communication and Information Security

Сергій Миколайович Конюшок, NTUU «KPI»

Candidate of Technical Science, docent, vice-head of Institute of Special Communication and Information Security

Артем Юрійович Сторожук, NTUU «KPI»

post-graduate student of Institute of Special Communication  and Information Security

References

. Алексеев Е.К. О некоторых мерах нелинейности булевых функций / Е. К. Алексеев // Прикладная дискретная математика. 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.

Downloads

Published

2015-06-03

How to Cite

Олексійчук, А. М., Конюшок, С. М., & Сторожук, А. Ю. (2015). FAST ALGORITHMS FOR CONSTRUCTING k - DIMENSIONAL APPROXIMATIONS OF BOOLEAN FUNCTIONS. Ukrainian Information Security Research Journal, 17(1), 43–52. https://doi.org/10.18372/2410-7840.17.8322

Issue

Vol. 17 No. 1 (2015)

Section

Articles

License

The scientific journal adheres to the principles of Open Access and provides free, immediate, and permanent access to all published materials without financial, technical, or legal barriers for readers.

All articles are published in Open Access under the Creative Commons Attribution 4.0 International (CC BY 4.0) license.

Copyright

Authors who publish their works in the journal:

  • retain the copyright to their publications;

  • grant the journal the right of first publication of the article;

  • agree to the distribution of their materials under the CC BY 4.0 license;

  • have the right to reuse, archive, and distribute their works (including in institutional and subject repositories), provided that proper reference is made to the original publication in the journal.