Рекуррентные формулы для числа k-эластичных и корреляционно- иммунных двоичных отображений | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/19

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

Получены рекуррентные формулы для распределения части вектора весов подфункций и части вектора спектральных коэффициентов AJ линейных комбинаций координатных функций двоичного отображения из векторного пространства Vn двоичных n-мерных векторов в векторное пространство Vm. С помощью этих формул получены рекуррентные формулы для числа корреляционно-иммунных порядка k двоичных отображений и для числа k-эластичных двоичных отображений.

Recursion formulas for the number of (n,m, AO-resilient and correlation-immune boolean mappings.pdf Системы распределённого реестра, основанные на блокчейн-технологии, являются одной из сквозных цифровых технологий программы «Цифровая экономика Российской Федерации». В последние годы различные аспекты данной технологии стали предметом пристального изучения исследователей и разработчиков программного обеспечения. Одной из многообещающих возможностей её применения являются системы хранения важных данных, включая персональные. Однако применение норм российского и европейского законодательства, занимающегося правовым регулированием персональных данных, приводит на практике к противоречию с самой концепцией блокчейн-систем, которые предполагают неизменность данных. В информационных системах (ИС) с реестром с ограничениями на добавление информации (согласно терминологии [1]), к примеру, задача удаления персональных данных может решаться изменением всей цепочки данных («forking»), в открытых же ИС с реестром наиболее многообещающим способом решения этой задачи может служить шифрование каждого блока персональной информации на своём ключе и удаление ключа, который хранится за пределами цепочки данных, при поступлении запроса на удаление [2]. В работе [3] этот метод разобран достаточно подробно и связан с задачей оценки числа (n, m, к)-устойчивых и корреляционно-иммунных двоичных отображений, используемых в качестве комбинирующих в поточных системах шифрования. Обозначим через Vn множество двоичных векторов размерности n. Корреляционная иммунность и эластичность (или (n, m, к)-устойчивость) двоичного отображения f (а) = (fi (а), f2 (а),..., fm (а)) : Vn - VW, согласно [4], сводится к обладанию этими свойствами всеми ненулевыми линейными комбинациями координатных функций f (а), называемыми в [5] компонентными функциями или компонентами. Свойства компонент могут быть, в частности, выражены в терминах весов их подфункций (в обозначениях [6]): w/ (f) = (Vm (J), f )1;;:1im Здесь f = (f1;...,fm); ||f1| -вес булевой функции f1; |J| -мощность множества J = {j1,... , j|j|} С {1,... ,m}; I = {«1,... ,i|I|} С {1,... ,n}; Vm (J) -двоичный вектор длины m, у которого в j1,..., j|j| координатах стоят единицы, а в остальных нули (согласно [7], Vm (J) называется индикаторным вектором множества J); (a,b) = = a1b1 ф ... ф anbn - скалярное произведение векторов а и b из Vm; (Vm (J), f - подфункция компоненты (Vm (J) , f) отображения f, получаемая, если у аргумента компоненты (Vm (J) , f) значения координат с номерами i1,... , i|i| положить равными единице. Для компоненты (Vm (J) , f) можно определить спектральный коэффициент Фурье - Уолша - Адамара А/(f) = F/(f) = 1 £ (_1)Wm(J)'/Xx)®xn®'.'®Xim = 2n-1 - ||(Vm(J),f)(x) Ф (Vn(1),x)| , 2 xevn где (Vn(1 ),x) = Ф ... Ф . Согласно [8], AJ(f) называется коэффициентом статистической структуры компоненты (Vm(J),f). В [9] доказаны формулы однозначной связи wJ с коэффициентами статистической структуры AJ = £ (_1)|L| (2n-1 _ 2|L|wL), wJ _ 2Пн11-1 = 2-|I| £ (_1)|l|+1Al, LeI LeI называемые тождеством Саркара (можно назвать тождеством Денисова - Саркара). Рассмотрим для произвольной функции f из множества В7" вектор весов подфункций W k (f )= (w/ (f) : 0 = J С {1,...,m},1 С {1,... , n}, |11 ^ k) и вектор коэффициентов статистической структуры Ak (f) = (А/ (f) : 0 = J С {1,... ,m}, I С {1,..., n}, |11 ^ k) kn длины N = N (n, m, k) = (2m _ 1) £ s=0 \\ Многие свойства двоичных отображений зависят от того, чему равен вектор, состоящий из определённых выше характеристик всех компонент или их части. Поэтому задача нахождения мощности множества функций с фиксированным начальным вектором весов подфункций или коэффициентов статистической структуры является важной. В настоящее время имеются только асимптотические оценки, полученные в [10-14]. Рассмотрим класс функций из jm n Wm (z) = W™ (z/ : 0 = J С {1,... , m}; I С {1,... , n}; |11 ^ k) = {f Е Bm : w/ (f) = 2n-|/1-1 - z/, 0 = J С {1,... , m}; I c{1,...,n}; |11 ^ k} чьи первые (в лексикографическом порядке) веса подфункций Wk (f) = W Е равны W = (w/ (f) = 2n-|/1-1 - z/ (f): I С {1,... , n}; 0 = J c{1,...,m}; |11 ^ k) . Теорема 1. Пусть n,m Е N, k Е {1,... ,n - 1}, тогда |Wnm (z)| = |Wnm (z/ : I С {1,..., n}; 0 = J c{1,...,m}; |11 ^ k) | = = E Wnm-1 (z/u{n} : 0 = J С {1,... , m} ; I с{1,...,п - 1} ; |11 ^ k) х zJu{n} ^Z:0=/C{1,...,m}, JC{1,...,n-1},|J|=k x|Fnm-1 (z/ - z/u{n} : 0 = J c{1,...,m} ; I c{1,...,n - 1} ; |11 ^ k) | . В теореме 1 суммирование на самом деле происходит не по всем z/u{n} Е Z, а только по z/u{n} Е {-2n-k-2, - 2n-k"2 + 1,..., 2n-k-2}. Обозначим через Sm (А) класс функций из Bm, обладающих следующим начальным вектором коэффициентов статистической структуры: А = (А/ (f) : 0 = J С {1,...,m}; I c{1,...,n}; |11 ^ k) . Используя тождества Денисова - Саркара, можно доказать Теорема 2. Пусть n,m Е N, k Е {1,... , n - 1}, тогда sm (А) | = |sm (А/ : I c {1,... , n}; 0 = J С {1,... , m}; |11 ^ k) /a J_A J \\ sm-^ J - 2 Ju{n} : 0 = J C{1,...,m} ; I c{1,...,n - 1} ; |11 ^ kj Е x AIJu{n}^Z: 0=/c{1,...,m}, I C{1,...,n-1},|/|=k X AJ + AJ Sm-П 1 2 Iu{n} : 0 = J C{1,...,m} ; I c{1,...,n - 1} ; |11 ^ k В теореме 2 суммирование также происходит только по тем A/u{n}, что лежат в множестве {-2n-1, -2n-1 + 1,..., 2n-1}. Определение 1. Отображение f из множества Bm всех m-мерных двоичных функций от n переменных называется k-эластичным ((n,m, ^-устойчивым), если для любых I, J, 0 = J С {1,... , m}, I С {1,... , n}, |11 ^ k, выполняется А/ (f) = 0. Обозначим R (n, m, k) множество всех k-эластичных двоичных отображений из Bm. Следствие 1. В условиях теорем 1 и 2 верно |R(n, m, k)| = £ |{f G ВП-1 : А/(f) = 0 : I С {1,... , n _ 1} , |11 < k; A(I'J )e{-2n-k-2'.'.'2n-k-2}: 0=J C{1'''.'m}' I С{1'''.'П-1},|I |=k А/ (f) = 2kA (I, J) : I С {1,... , n _ 1} , |11 = k; 0 = J С {1,... , m}}1 x x | {h G ВП-1 : А/ (h) = 0 : I С {1,... , n _ 1} , |11 < k; А/ (h) = _2k A (I, J) : I С {1,... ,n _ 1} , |11 = k; 0 = J С {1,... ,m}}| . В работе [3] следствие 1 доказано как отдельный результат, причём в формулировке допущена опечатка. Определение 2. Отображение f из множества В7" всех m-мерных двоичных функций от n переменных называется корреляционно-иммунны{м порядка k, если дл}я любого J, 0 = J С {1,... , m}, существует такая величина rJ G j_2ra-k-1,... , 2ra-k-1j, что для любого I, I С {1,..., n}, |11 ^ k, выполняется wJ (f) = 2ra-|I|-1 + rJ2k-|I|. Определение 2 эквивалентно тому, что для любых I, J, 0 = J С {1,... ,m}, I С С {1,... , n}, 1 ^ |11 ^ k, выполняется AJ (f) = 0. Обозначим через K (n, m, k) множество всех корреляционно-иммунных порядка k двоичных отображений из В7". Из утверждения в [15] следует, что если f G K(n, m, k), то |f || = 0 = A0 (mod 2k) Следствие 2. В условиях теорем 1 и 2 верно 2-n-k-l |{ |K(m,n,k)| = £ £ |{f G Bm-1 :A0(f) = 2k-1s; s=-2-n-k-1 A(I'J)e{-2n-k-1'.'.'2n-k-1}:0=J e{1'''.'m}' IC{1'''''n-1}'|I |=k AJ (f) = 0 : I С {1,... , n _ 1} , |11 < k; AJ (f) = 2k-1A (I, J) : I С {1,... , n _ 1} , |11 = k; 0 = J С {1,...,m}}| x x 1 {h G Bm-1 : A0 (h) = 2k-1s; AJ (h) = 0 : I С {1,... , n _ 1} , |11 < k; AJ (h) = _2k-1A (I, J) : I С {1,... , n _ 1} , |11 = k; 0 = J С {1,... , m}} | . Полученные рекуррентные формулы позволяют вычислять точные значения мощностей множеств R (t, m, k) и K (t, m, k) для t > n при фиксированных значениях переменных m и k, предварительно экспериментально находя распределение мощности множеств (А) соответствующего вида.

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

веса подфункций, спектральные коэффициенты, рекуррентные формулы, устойчивые вектор-функции, эластичные вектор-функции, корреляционно-иммунные функции, weights of subfunctions, spectral coefficient, recursion formula, resilient vectorial Boolean function, correlation-immune function

Авторы

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

Ссылки

МР 26.4.001-2018 «Термины и определения в области технологий цепной записи данных (блокчейн) и распределенных реестров». https://tc26.ru/standarts/ metodicheskie-rekomendatsii/
Michels D. Here's how GDPR and the blockchain can coexist. https://thenextweb.com/ syndication/2018/07/26/gdpr-blockchain-cryptocurrency/
Pankov K. Enumeration of Boolean mapping with given cryptographic properties for personal data protection in blockchain data storage // Proc. 24th Conf. of Open Innovations Association FRUCT, Moscow, Russia, 2019. P. 300-306.
Логачев О. А., Сальников А. А., Смышляев С. В., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2012.
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. №4. С. 14-30.
Сачков В. Н. Курс комбинаторного анализа. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2013, 336 с.
Словарь криптографических терминов. М.: МЦНМО, 2016. 94 с.
Денисов О. В. Локальная предельная теорема для распределения части спектра случайной двоичной функции // Дискретная математика. 2000. №1. С. 82-95.
Панков К. Н. Уточнённые асимптотические оценки для числа (n, m, к)-устойчивых двоичных отображений // Прикладная дискретная математика. Приложение. 2017. № 10. С. 4649.
Панков К. Н. Уточнённые асимптотические оценки для числа корреляционно-иммунных двоичных функций и отображений // Прикладная дискретная математика. Приложение. 2018. №11. С. 49-52.
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.
Панков К. Н. Асимптотические оценки для чисел двоичных отображений с заданными криптографическими свойствами // Математические вопросы криптографии. 2014. №4. С. 73-97.
Панков К. Н. Улучшенные асимптотические оценки для числа корреляционно-иммунных и k-эластичных двоичных вектор-функций // Дискретная математика. 2018. №2. С. 73-98.
Денисов О. В. Асимптотическая формула для числа корреляционно-иммунных порядка k булевых функций // Дискретная математика. 1991. №2. С. 25-46.
 Рекуррентные формулы для числа k-эластичных и корреляционно- иммунных двоичных отображений | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/19

Рекуррентные формулы для числа k-эластичных и корреляционно- иммунных двоичных отображений | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/19