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

Нормированной DDT-таблицей функции F будем называть таблицу, в ячейке (a, b) которой записано количество решений уравнения

F(x) 0 F(x 0 a) 0 F (a) 0 F(0) = b.

Нормированной LAT-таблицей функции F будем называть LAT-таблицу функции F без линейной части.

Теорема 3. Если функции F и G EA-эквивалентны и в нормированной DDT (ХАТ)-таблице функции F есть совпадающие строки, то в нормированной DDT (LAT)-таблице функции G также есть совпадающие строки.

ЛИТЕРАТУРА

1. Biham E. and Shamir A. Differential cryptanalysis of DES-like cryptosystems //J. Cryptology. 1991. V.4. Iss. 1. P. 3-72.

2. Matsui M. and Yamagishi A. A new method for known plaintext attack of FEAL cipher // EUROCRYPT'1992. LNCS. 1992. V.658. P. 81-91.

3. Carlet C. Vectorial Boolean functions for cryptography // Boolean Models and Methods in Mathematics, Computer Science, and Engineering / eds. Y. Crama and P. Hammer. Cambridge: Cambridge University Press, 2010. P. 398-470.

УДК 519.7 DOI 10.17223/2226308X/12/19

РЕКУРРЕНТНЫЕ ФОРМУЛЫ ДЛЯ ЧИСЛА k-ЭЛАСТИЧНЫХ И КОРРЕЛЯЦИОННО-ИММУННЫХ ДВОИЧНЫХ ОТОБРАЖЕНИЙ

К. Н. Панков

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

Ключевые слова: веса подфункций, спектральные коэффициенты, рекуррентные формулы, устойчивые вектор-функции, эластичные вектор-функции, корреляционно-иммунные функции.

Системы распределённого реестра, основанные на блокчейн-технологии, являются одной из сквозных цифровых технологий программы «Цифровая экономика Российской Федерации». В последние годы различные аспекты данной технологии стали предметом пристального изучения исследователей и разработчиков программного обеспечения. Одной из многообещающих возможностей её применения являются системы хранения важных данных, включая персональные. Однако применение норм российского и европейского законодательства, занимающегося правовым регулированием персональных данных, приводит на практике к противоречию с самой концепцией блокчейн-систем, которые предполагают неизменность данных. В информационных системах (ИС) с реестром с ограничениями на добавление информации (согласно терминологии [1]), к примеру, задача удаления персональных данных может решаться изменением всей цепочки данных («forking»), в открытых же ИС с реестром наиболее

многообещающим способом решения этой задачи может служить шифрование каждого блока персональной информации на своём ключе и удаление ключа, который хранится за пределами цепочки данных, при поступлении запроса на удаление [2]. В работе [3] этот метод разобран достаточно подробно и связан с задачей оценки числа (n, m, к)-устойчивых и корреляционно-иммунных двоичных отображений, используемых в качестве комбинирующих в поточных системах шифрования.

Обозначим через Vn множество двоичных векторов размерности n. Корреляционная иммунность и эластичность (или (n, m, к)-устойчивость) двоичного отображения / (а) = (/ (а), /2 (а),..., /т (а)) : Vn ^ Vm, согласно [4], сводится к обладанию этими свойствами всеми ненулевыми линейными комбинациями координатных функций / (а), называемыми в [5] компонентными функциями или компонентами. Свойства компонент могут быть, в частности, выражены в терминах весов их подфункций (в обозначениях [6]):

w/ (/) = (Фт ( j ), / )t:1im

Здесь / = (/,...,/т); 11/11 —вес булевой функции /1; |J | —мощность множества J = {ji,... , j|/1} С {1,... ,m}; I = {¿i,... ,«|/|} С {1,... ,n}; фт (J) —двоичный вектор длины m, у которого в ji,..., j|j1 координатах стоят единицы, а в остальных нули (согласно [7], фт (J) называется индикаторным вектором множества J); (a,b) = = a1b1 ф ... ф anbn — скалярное произведение векторов а и b из Vm; (фт (J), /— подфункция компоненты (фт (J) , /) отображения /, получаемая, если у аргумента компоненты (фт (J) , /) значения координат с номерами ¿1,... , ¿|/1 положить равными единице.

Для компоненты (фт (J) , /) можно определить спектральный коэффициент Фурье — Уолша — Адамара

А/(/) = F/ (/) = 1 Е (-lfm(/)'/)(x)x- '''xvi = 2n-1 - || (фт( J), / )(x) ф (Фп(!),*)|| ,

где (Фп(1 ),x) = xil ф ... ф . Согласно [8], AJ(/) называется коэффициентом статистической структуры компоненты ^m(J),/).

В [9] доказаны формулы однозначной связи wJ с коэффициентами статистической структуры

LC/ LCI

называемые тождеством Саркара (можно назвать тождеством Денисова — Саркара). Рассмотрим для произвольной функции / из множества Вт вектор весов подфункций

Wk

и вектор коэффициентов статистической структуры

Ak

k / n

длины N = N (n, m, k) = (2m - 1) £

s=0 \

Многие свойства двоичных отображений зависят от того, чему равен вектор, состоящий из определённых выше характеристик всех компонент или их части. Поэтому задача нахождения мощности множества функций с фиксированным начальным

вектором весов подфункций или коэффициентов статистической структуры является важной. В настоящее время имеются только асимптотические оценки, полученные в [10-14].

Рассмотрим класс функций из Бгп

jrri n

WT (*) = Wnm (zj : 0 = J С {1,... , m}; I С {1,... , n}; |11 ^ fc) = {/ e Bnm : wj (f) = 2n-|/1-1 - zj, 0 = J С {1,... , m}; I C{1,...,n}; |11 ^ fc}

чьи первые (в лексикографическом порядке) веса подфункций Wk (f) = W G равны

W = (w/ (f) = 2n-|/1-1 - z/ (f): I C{1,...,n}; 0 = J c{1,...,m}; |I | ^ k) .

Теорема 1. Пусть n,m G N, k G {1,... ,n — l}, тогда

|Wram (z)| = |Wram (z/ : I C{1,...,n}; 0 = J c{1,...,m}; |I | ^ k) | = = E W-1 (z/u{„} : 0 = J C{1,...,m} ; I c{1,...,n — 1} ; |I | ^ k) x

z/u{n} ^Z:0=JC{1,...,m},

/C{1,...,n-1},|J|=k

x|F-i (z/ — z/u{n} : 0 = J C{1,...,m} ; I c{1,...,n — 1} ; |I | ^ k) | .

В теореме 1 суммирование на самом деле происходит не по всем z/u{n} G Z, а только по z/u{n} G {— 2n-k-2, — 2n-k"2 + 1,..., 2n-k-2}.

Обозначим через Sm (Д) класс функций из Bm, обладающих следующим начальным вектором коэффициентов статистической структуры:

Д = (Д/ (f) : 0 = J C {1,...,m}; I c{1,...,n}; |I | ^ k) .

Используя тождества Денисова — Саркара, можно доказать Теорема 2. Пусть n,m G N, k G {1,... , n — 1}, тогда

sm

E

Д/и{п>^:

0=J C{1,...,m}, / C{1,...,n-1},|/|=fc

/ aJ_ д J \

sm-^ J — 2 Ju{n> : 0 = J С {1,... , m} ; I С{1,...,п - 1} ; |11 ^ fcj

x

X

AJ + AJ

Sm-П J 2 JU{n} : 0 = J С {1,... , m} ; I С{1,...,п - 1} ; |11 ^ fc

В теореме 2 суммирование также происходит только по тем AjU{n}, что лежат в множестве {-2n-1, -2n-1 + 1,..., 2n-1}.

Определение 1. Отображение f из множества BT всех m-мерных двоичных функций от n переменных называется k-эластичным ((n,m, к)-устойчивым), если для любых I, J, 0 = J С {1,... , m}, I С {1,... , n}, |11 ^ k, выполняется AJ (f) = 0.

Обозначим R (n, m, k) множество всех k-эластичных двоичных отображений из BT

Следствие 1. В условиях теорем 1 и 2 верно |R(n, m, k)| = £ |{/ G Bm-1 : А/(/) = 0 : I С {1,... , n - 1} , |I | < k;

A(/'J )e{-2n-fc-2'''.'2n-fc-2}: 0=J С{1'.'.'т}' / С{1'.'.'П-1}'|/|=k

А/ (/) = 2kA (I, J) : I С {1,... , n - 1} , |I| = k; 0 = J С {1,... , m}}1 x

x | {h G Bn-1 : A/ (h) = 0 : I С {1,... , n - 1} , |I| < k; A/ (h) = -2k A (I, J) : I С {1,... ,n - 1} , |I | = k; 0 = J С {1,... ,m}}| .

В работе [3] следствие 1 доказано как отдельный результат, причём в формулировке допущена опечатка.

Определение 2. Отображение / из множества Вт всех m-мерных двоичных функций от n переменных называется корреляционно-иммунны{м порядка k, если дл}я любого J, 0 = J С {1,... , m}, существует такая величина r/ G {-2n-k-1,... , 2n-k-1j, что для любого I, I С {1,..., n}, |I| ^ k, выполняется w/ (/) = 2n-|/1-1 + r/2k-|/|.

Определение 2 эквивалентно тому, что для любых I, J, 0 = J С {1,... ,m}, I С С {1,... , n}, 1 ^ |I| ^ k, выполняется A/ (/) = 0.

Обозначим через K

Следствие 2. В условиях теорем 1 и 2 верно

2-n-k-l

|K(m,n,k)| = £ £ |{/ G Вт-1 : A0(/) = 2k-1s;

s=-2-n-k-1 A(/'/ )g{-2n—k—1'.'.'2n—k—1}:0=/ С{1'.'.'т}'

/С{1'.'.'П-1}'|/|=k

A/ (/) = 0 : I С {1,... , n - 1} , |I| < k; A/ (/) = 2k-1A (I, J) : I С {1,... , n - 1} , |I | = k; 0 = J С {1,...,m}}| x

x 1 {h G Bn-1 : A0 (h) = 2k-1s; A/ (h) = 0 : I С {1,... , n - 1} , |I| < k; A/ (h) = -2k-1A (I, J) : I С {1,... , n - 1} , |I| = k; 0 = J С {1,... , m}} | .

Полученные рекуррентные формулы позволяют вычислять точные значения мощностей множеств R (t, m, k) и K (t, m, k) для t > n при фиксированных значениях переменных m и k, предварительно экспериментально находя распределение мощности множеств (A) соответствующего вида.

ЛИТЕРАТУРА

1. МР 26.4.001-2018 «Термины и определения в области технологий цепной записи данных (блокчейн) и распределенных реестров». https://tc26.ru/standarts/ metodicheskie-rekomendatsii/

2. Michels D. Here's how GDPR and the blockchain can coexist. https://thenextweb.com/ syndication/2018/07/26/gdpr-blockchain-cryptocurrency/

3. 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.

4. Логачев О. А., Сальников А. А., Смышляев С. В., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2012.

5. 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.

6. Панков К. Н. Оценки скорости сходимости в предельных теоремах для совместных распределений части характеристик случайных двоичных отображений // Прикладная дискретная математика. 2012. №4. С. 14-30.

7. Сачков В. Н. Курс комбинаторного анализа. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2013, 336 с.

8. Словарь криптографических терминов. М.: МЦНМО, 2016. 94 с.

9. Денисов О. В. Локальная предельная теорема для распределения части спектра случайной двоичной функции // Дискретная математика. 2000. №1. С. 82-95.

10. Панков К. Н. Уточнённые асимптотические оценки для числа (n, m, к)-устойчивых двоичных отображений // Прикладная дискретная математика. Приложение. 2017. № 10. С. 4649.

11. Панков К. Н. Уточнённые асимптотические оценки для числа корреляционно-иммунных двоичных функций и отображений // Прикладная дискретная математика. Приложение. 2018. №11. С. 49-52.

12. 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.

13. Панков К. Н. Асимптотические оценки для чисел двоичных отображений с заданными криптографическими свойствами // Математические вопросы криптографии. 2014. №4. С. 73-97.

14. Панков К. Н. Улучшенные асимптотические оценки для числа корреляционно-иммунных и k-эластичных двоичных вектор-функций // Дискретная математика. 2018. №2. С. 73-98.

15. Денисов О. В. Асимптотическая формула для числа корреляционно-иммунных порядка k булевых функций // Дискретная математика. 1991. №2. С. 25-46.

УДК 519.7 DOI 10.17223/2226308X/12/20

О КОМПОНЕНТАХ НЕКОТОРЫХ КЛАССОВ ОБРАТИМЫХ ВЕКТОРНЫХ БУЛЕВЫХ ФУНКЦИЙ1

И. А. Панкратова

В классе обратимых векторных булевых функций от n переменных, координатные функции которых существенно зависят от всех переменных, рассматриваются подклассы Kn и Kn, функции в которых получены с помощью n независимых транспозиций из тождественной подстановки и из подстановки, каждая координатная функция которой существенно зависит от одной переменной, соответственно. Приводятся некоторые свойства компонент функций из этих классов.

Ключевые слова: векторная булева функция, обратимые функции, нелинейность векторной булевой функции, компонентная алгебраическая иммунность.

Для n G N рассмотрим обратимые векторные булевы функции F = (/1... /n) на Fn, такие, что координатные функции / : Fn ^ F2, i = 1,... , n, существенно зависят от всех n переменных. В [1] предложен алгоритм 1 построения некоторой такой функции, который состоит в следующем: стартуя с тождественной подстановки G : Fn ^ Fn, на i-м шаге, i = 1,... , n, выбираем два соседних по i-й координате и не выбранных на предыдущих шагах вектора a,b G Fn и меняем местами значения G(a) и G(b).

1 Работа поддержана грантом РФФИ, проект №17-01-00354.