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

Issue

Vol. 17 No. 1 (2015)

Section

Articles

License

Authors who publish with this journal agree to the following terms:

  1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).