On decomposability of schur - hadamard product of the tensor products sum of reed - muller codes.pdf Кодовые криптосистемы типа Мак-Элиса рассматриваются в качестве альтернативы современным асимметричным криптосистемам, так как при выборе подходящего кода являются стойкими к атакам с помощью компьютера на основе квантовой модели вычисления [1]. Оригинальная система Мак-Элиса на кодах Гоппы в настоящее время считается стойкой, но высокая стойкость достигается за счёт ключа большого размера [2]. С целью уменьшения размера ключа предложены криптосистемы типа Мак-Элиса на других кодах. Но для некоторых широко известных кодов, таких, как обобщённые коды Рида - Соломона, двоичные коды Рида - Маллера, системы типа Мак-Элиса оказываются нестойкими и для компьютеров на основе классической модели Тьюринга [3-5]. Для усиления стойкости криптосистем в [6] предлагается использовать тензорное произведение кодов Рида - Маллера. В [7] исследуется класс кодов, обобщающий конструкцию тензорного произведения. Коды из этого класса представляют собой сумму нескольких тензорных произведений специального вида. Эти коды эффективно декодируются, поэтому на их основе можно построить криптосистему типа Мак-Элиса. Но для применения криптосистемы необходимо проанализировать её стойкость. При анализе стойкости кодовых криптосистем к атакам на ключ часто исследуются свойства произведения Шура - Адамара кодов, которые лежат в основе этих криптосистем [8]. В настоящей работе ставится задача исследования разложимости квадрата суммы специального вида двух тензорных произведений кодов Рида - Маллера. Напомним, что линейным [n, k]q-кодом C называется подпространство размерности k пространства Fn над полем Галуа Fq. Для кода C ортогональный к нему код будем обозначать C = {x G Fn : Vc G C ((x, c ) = 0}, где ( x, c) - скалярное произведение векторов. Для двух кодов C1,C2 С Fn произведение Шура - Адамара C1 * C2 определяется как линейная оболочка, натянутая на множество векторов {x * y : x G C1, y G C2}, где x * y = (x1y1,... , xnyn). При этом под квадратом кода C понимается код C2 = C*C [8]. Под внутренней суммой кодов C1 и C2 будем понимать код C1 + C2 = {x + y : x G C1, y G C2}, а под внешней (прямой) суммой кодов C С Fqn1 и D С F^2 - код C ф D = {(x, y) : x G C, y G D}, где (x, у) - конкатенация векторов x и y. Тензорное произведение кодов C и D обозначим C ф D [9]. В случае C = Fn получаем следующее равенство: Fni ф D = D ф ф D, n1 а в случае D = Fqn2 код C ф Fqn2 перестановочно эквивалентен коду Fn ф C = C ф ... ф C. n2 Код называется разложимым, если он перестановочно эквивалентен прямой сумме двух или более кодов ненулевой размерности [10]. Пусть RM(r, m) -двоичный код Рида - Маллера порядка r и длины 2m. Рассмотрим коды C1 = RM(r11, m1), C2 = RM(r21, m1), D1 = RM(r12, m2), D2 = RM(r22, m2), такие, что C2 С C1, D1 С D2. Код K = Ci ф Di + C2 ф D2 (1) является мажоритарно-декодируемым кодом [7]. Отметим, что C1 С C2, D2 С D1. В [11] доказано, что для произвольных кодов Vi, V2 С Fqn1, Wi, W2 С Fqn2 выполняется равенство (Vi ф Wi) * (V2 ф W2) = (Vi * V2) ф (Wi * W2). Отсюда получаем, что квадрат кода K имеет следующий вид: к2 = Ci ф d2 + (C i * C2) ф (Di * D2)+C2 ф d2. (2) Теорема 1. Пусть K - код вида (1). 1) Если mi - г1 - 1 > m1/2 и m2 - ф - 1 < m2/2, то K2 = F22 1 ф RM(2(m2 - r2 - 1), m2). 2) Если m1 - r2 - 1 < m1 /2 и m2 - r2 - 1 > m2/2, то K2 = RM(2(mi - r2i - 1), mi) ф F22m2. Теорема 2. Пусть K - код вида (1). Если выполняется хотя бы одно из условий: 1) m1 - rj - 1 > m1/2 и m2 - ф - 1 > m2/2, 2) 2m1 - (rj + r2) - 2 > m1 и 2m2 - (r2 + r2) - 2 > m2, 3) m1 - r2 - 1 Ф m1/2 и m2 - r2 - 1 > m2/2, то K2 =F Теорема 3. Пусть K - код вида (1), mi - r2 - 1 > m1/2, m2 - /7 - 1 > m2/2, m1- r11- 1 m2, то K2 = RM(r1 + r2 - m1 + 1,m1) ® RM(2r2 - m2 + 1,m2). В случаях, не рассмотренных в теоремах 1-3, то есть при 1 m1 2 m2 1 1 2 2 m1 - rx - 1 < - ,m2 - r2 - 1 < -, 2m1 - (rx + r2) - 2 < m1,2m2 - (r1 + r2) - 2 < m2, (3) представление (2) не удаётся упростить и сделать выводы о разложимости квадрата кода вида (1) в прямую сумму кодов Рида - Маллера. Но в этом случае можно оценить размерность кода (2) и проверить, возможно ли разложение этого кода в прямую сумму каких-либо кодов Рида - Маллера длины 2mi или 2m2. А именно, если размерность кода (2) не делится на 2m1 или 2m2, то этот код не разлагается в прямую сумму и не является перестановочно эквивалентным такому коду. Согласно результатам вычислений, для m1 = 2, . . . , 10 и m2 = 2, . . . , 10 общее количество кодов вида (1), удовлетворяющих условиям (3), равно 9025. При этом количество кодов, размерность которых делится на 2m1 или 2m2, равно 204. Это значит, что для случайно выбранного кода вида (1), удовлетворяющего условиям (3), с вероятностью более 0,97 его квадрат не разлагается в прямую сумму кодов Рида - Маллера длины 2mi или 2m2.

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