Improved asymptotic estimates for the number of correlation-immune boolean functions and mappings
For linear combinations of coordinate functions of a random Boolean mapping from the vectorspace Vn of all binary vectors of length n to the vectorspace Vm, the local limit theorem for the joint distribution of weights of some their subfunctions is improved. By means of this theorem, we have obtained an asymptotic formula for |K (n, m, k)| that is the number of correlation-immune of order k functions as n -> ro, m Е {2, 3, 4} and k (5 + 2log2n) + 6m ^ ^ n (5/18 - y') for any 0 <7' < 5/18, k = О (r^): ln n log2 |K (m, n, k) | ~ m2n + ln n n +1+log2п - k) (2™ - 1) - m.2'"-1- - (2™ - 1) ( ^ fn ) + logn/ ig ( s ) ) + (2 · 3m-2 - 1) E I п ^ /n k fn 0 \s Also, we have obtained improved asymptotic estimates for the number |K (n, 1, k) | as n /ln2 \ ln 2 -- ---e for any e, 0 < e < --: ln n 4 4 n -> 00, k < log2 |K [n, 1,k]|~ 2n - (n - k) n nk k п - 1 ) log2 л/ПТ2. + £ (n) log2 s=0 V s nk
Keywords
correlation-immune function,
weights of subfunctions,
random binary mapping,
local limit theorem,
корреляционно-иммунные функции,
локальная предельная теорема,
веса подфункций,
случайное двоичное отображениеAuthors
| Pankov K. N. | Moscow Technical University of Communication and Informatics | k.n.pankov@gmail.com |
Всего: 1
References
Canfield E. R., Gao Z., Greenhill C., et al. Asymptotic enumeration of correlation-immune Boolean functions // Cryptography and Communications. 2010. No. 1. P. 111-126. 10. Панков К. Н. Уточнённые асимптотические оценки для числа (n, m, к)-устойчивых двоичных отображений // Прикладная дискретная математика. Приложение. 2017. №10. С.46-49.
Панков К. Н. Асимптотические оценки для чисел двоичных отображений с заданными криптографическими свойствами // Математические вопросы криптографии. 2014. №4. С. 73-97.
Панков К. Н. Локальная предельная теорема для распределения части вектора весов подфункций компонент случайного двоичного отображения // Математические вопросы криптографии. 2014. №3. С. 49-80.
Денисов О. В. Локальная предельная теорема для распределения части спектра случайной двоичной функции // Дискретная математика. 2000. №1. С. 82-95.
Сачков В. Н. Курс комбинаторного анализа. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2013.
Панков К. Н. Оценки скорости сходимости в предельных теоремах для совместных распределений части характеристик случайных двоичных отображений // Прикладная дискретная математика. 2012. №4. С. 14-30.
Carlet C. Vectorial Boolean functions for cryptography // Boolean Models and Methods in Mathematics, Computer Science, and Engineering. Encyclopedia of Mathematics and its Applications. V. 134. N.Y.: Cambridge University Press, 2010. P. 398-472.
Логачев О. А., Сальников А. А, Смышляев С. В., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2012.
Развитие технологии распределенных реестров. Доклад для общественных консультаций. М.: Центральный банк Российской Федерации, 2017. http://www.cbr.ru/ analytics/ppc/Consultation_Paper_1712129(2).pdf
