Refined asymptotic estimates for the number of (n, m, k)-resilient boolean mappings.pdf Как известно, многие свойства двоичных отображений и определяемые ими классы вектор-функций исторически выделялись под влиянием задач разработки и анализа криптографических систем. К таким классам относятся и широко известные в математике и её приложениях (n, m, к)-устойчивые или, как их можно назвать в соответствии с [1], k-эластичные отображения. Такие вектор-функции используются, например, в поточных шифрсистемах в качестве комбинирующих функций, обладающих способностью противостоять корреляционному методу криптоанализа, так как их выход статистически не зависит от некоторых комбинаций входов. Обозначим через Vn множество двоичных векторов размерности n. В [2] доказано, что многие важные свойства двоичного отображения / (а) = (f1 (а) , /2 (а) ,...,/m (а)) : Vn ^ Vm, к которым относится и (n, m, k)-устойчивость, сводятся к обладанию этими свойствами всеми ненулевыми линейными комбинациями координатных функций / (а), называемыми в [3] компонентными функциями или компонентами. Свойства компонент могут быть, в частности, выражены в терминах их спектральных коэффициентов Фурье - Уолша - Адамара [4], или, иначе говоря, коэффициентов статистической структуры в соответствии с [5, с. 71]: FiJ (/) = А/ (/) = 2 Е (-1)(^(J)J)(x)®Wn(I= 2n-1 - (J), /) (x) 0 tyn (I) ,x)|| , 2 xeVn где / = (/1,...,/m); ||/1| -вес булевой функции /1; J = {j1,...,j|j|} С {1,...,m}; (J) -двоичный вектор длины m, у которого на j1,... , j|j| координатах стоят единицы, а на остальных нули. В терминологии [6] (J) называется индикаторным вектором множества J. Определение 1. Отображение / из множества B^ всех m-мерных двоичных функций от n переменных называется (n, m, k)-устойчивым, если для любых I, J, 0 = J С {1,... ,m}, I С {1,... ,n}, \1 \ ^ k, выполняется А/ (/) = 0. Пусть функция f выбирается случайно и равновероятно из множества B^. Рассмотрим для этой функции вектор коэффициентов статистической структуры Аk (f) = (А/ (f) : 0 = J С {1,... ,m}, I С {1,..., n}, |/1 ^ k) k /n\ длины N = N (n, m, k) = (2m - I. Для упрощения записи введём обозначения s=0 V V exp2 x = 2x, T = T (n, m, k) = ^ (£) (2™ - 1) + N (n, m, k) log^ . Теорема 1. Пусть при всех достаточно больших n для произвольного 0 < е < 1 выполняется k (5 + 2log2 n) + 5m ^ n (1 - е). Тогда для векторов a = (aJ : 0 = J С С {1,..., m}, / С {1,... , n}, |/1 ^ k) размерности N, координаты которых удовлетворяют сравнениям (см. [7]) £ (-1)|L|aL = 0 (mod2|/|) , Е (-1)|L|+|S|af = 0 (mod2|J|+|J|-1) , LC/ 0=SCJ,LC/ для любых 0 = J Е {1,... , m} и / Е {1,... , n} справедливо: P (Ak = a) =05 (a) exp (-2ne-1-log2 5) + + exp2 (-T (n,m,k))(exp(-21-n E E (a/)^ x V V 0=Je{1,...,m} /C{1,...,n},|/|

Скачать электронную версию публикации