Улучшенные асимптотические оценки для числа корреляционно- иммунных двоичных функций и отображений | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/15

Улучшенные асимптотические оценки для числа корреляционно- иммунных двоичных функций и отображений

Уточнена локальная предельная теорема для распределения части вектора весов подфункций линейных комбинаций координатных функций случайного двоичного отображения из векторного пространства Vn двоичных n-мерных векторов в векторное пространство VW. С помощью этой теоремы получена асимптотическая формула для |K (m, n, k)| - числа корреляционно-иммунных порядка k двоичных отображений в случае n ^ то, m е {2,3, 4} и k (5 + 21og2n) + 6m ^ n (Ц - 7') для произвольного 0 < Y < 5/18, k = O (n/ln n): log2 |K (m,n,k)| ~ m2n + ^n + 1 +log2 n - ^ (2m - 1) - m2m-1 - -(2m-1) (^ (n)+log2 /IЕ (n)) + (2-3m-2-1) Е (n). Найдена улучшенная асимптотическая оценка для |K (n, 1, k)| в случае n ^ то, n ln 2 k < ----е для произвольного 0 < е < ln2/4: ln n 4 log2 |K [n, 1, k] | ~ 2n - 1 ((n - k^^ - n) - k- - (¥ (n) + Е (n)log2 - 1) log2 ^

Improved asymptotic estimates for the number of correlation-immune boolean functions and mappings.pdf К классам вектор-функций, изучения которых требуют задачи криптографического синтеза и анализа, относятся, в частности, корреляционно-иммунные отображения. Такие отображения могут использоваться при реализации шифрсистем, предназначенных для защиты информации в закрытых и гибридных сетях распределённых реестров [1]. Обозначим через Vn множество двоичных векторов размерности n. В [2] доказано, что такое свойство двоичного отображения f (a)=(f1 (a), f2(a),... , fm(a)) : Vn ^ VW, как корреляционная иммунность, сводится к обладанию этим свойством всеми ненулевыми линейными комбинациями координатных функций f(a), называемыми в [3] компонентными функциями или компонентами. Свойства компонент могут быть выражены в терминах весов их подфункций (в обозначениях [4]): w/ (f ) = || ww (j ) ,f )t:1im где f = (f1,...,fm); ||f1| -вес булевой функции f1; |J| -мощность множества J = = j ,...,j|/|} С {1,...,m}; I = {ib... ,i|/|} С {1,...,n}; (J) -двоичный вектор длины m, у которого на j\,... , j/1 координатах стоят единицы, а на остальных нули (в [5] (J) называется индикаторным вектором множества J); (a, b) = a1b1 ф ... ф Ф anbn - скалярное произведение векторов a и b из VW; (J) , f) 1,'"'1i - подфункция компоненты (фт (J) , f) отображения f, получаемая, если у аргумента компоненты (фт (J) , f) значения координат с номерами i1,... , i\j\ положить равными единице. В силу однозначной связи wJ с коэффициентами статистической структуры, приведёнными в [6], их можно по аналогии назвать весовыми коэффициентами двоичного отображения. Из результатов работы [6] следует Определение 1. Отображение f из множества Вт всех m-мерных двоичных функций от n переменных называется корреляционно-иммунным порядка k, если для любого J, 0 = J С (1,... , m}, существует такая величина rJ G { - что для любого I С (1,... , n}, |I1 ^ k, выполняется wJ (f) = 2n-|/|-1 + rJ2k-|/'. Пусть функция f выбирается случайно и равновероятно из множества Вт. Рассмотрим для этой функции вектор весов подфункций W k (f )= (wJ (f) : 0 = J С (1,...,m},I С (1,...,n}, |I | ^ k) k fn\ длины N = N (n, m, k) = (2m - 1) E I ). Для упрощения записи введём следующие s=0 V SJ обозначения: exp2 x = 2x; E£ - математическое ожидание случайной величины £; T = T (n, m, k) = ^ Q (2m - 1) + N (n, m, k) log^ . Теорема 1. Пусть при всех достаточно больших n для произвольного 0

Ключевые слова

correlation-immune function, weights of subfunctions, random binary mapping, local limit theorem, корреляционно-иммунные функции, локальная предельная теорема, веса подфункций, случайное двоичное отображение

Авторы

ФИООрганизацияДополнительноE-mail
Панков Константин НиколаевичМосковский технический университет связи и информатикикандидат физико-математических наук, научный сотрудник отдела «Безопасность критической информационной инфраструктуры», начальник отдела аспирантурыk.n.pankov@gmail.com
Всего: 1

Ссылки

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
 Улучшенные асимптотические оценки для числа корреляционно- иммунных двоичных функций и отображений | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/15

Улучшенные асимптотические оценки для числа корреляционно- иммунных двоичных функций и отображений | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/15