不相交線性碼的一種新構造*

董雪雯, 孫玉娟

1.西安電子科技大學 綜合業(yè)務網(wǎng)理論及關鍵技術國家重點實驗室, 西安710071

2.密碼科學技術國家重點實驗室, 北京100878

1 引言

密碼函數(shù)包括單輸出布爾函數(shù)和多輸出布爾函數(shù), 是構成密碼算法的重要部件, 主要用于流密碼和分組密碼的設計.在流密碼和分組密碼體制中, 為了抵抗多年來相繼出現(xiàn)的各種攻擊方式, 一個密碼函數(shù)需要滿足以下指標: 高非線性度、平衡性、相關免疫性、高代數(shù)次數(shù)、最優(yōu)代數(shù)免疫度和良好自相關性質等等.然而密碼函數(shù)的各項指標之間存在相互制約, 如何實現(xiàn)這些指標的折中優(yōu)化是密碼函數(shù)設計中的重要難題.

Berlekamp-Massey 攻擊、相關攻擊是攻擊流密碼的重要方法, 抵抗Berlekamp-Massey 攻擊需要高非線性度, 抵抗相關攻擊需要高階相關免疫, 而高非線性度與高階相關免疫相互制約, 平衡的相關免疫函數(shù)通常稱為彈性函數(shù), 因此非線性度高的彈性密碼函數(shù)的設計是一個重要的研究課題.[n,k]線性碼是n維向量空間的k 維線性子空間, 在高非線性度彈性密碼函數(shù)的構造中起著重要作用[1–8].

2003年, Johansson 和Pasalic[2]首次利用不相交[n,k]線性碼構造具有高非線性度的多輸出彈性密碼函數(shù).為了得到不相交[n,k]線性碼, 他們采用的方法是計算機搜索.這種方法只在n 和k 都比較小時才是可行的.2004年, Niederreiter 和Xing[9]給出了基于代數(shù)函數(shù)域上的不相交線性碼的構造, 這種方法能找到的不相交線性碼數(shù)量很少.2005年, Charpin 和Pasalic[3]利用射影空間的基本理論構造了不相交線性碼, 利用這種不相交[n,k]線性碼也可以構造具有高非線性度的多輸出彈性密碼函數(shù), 這種構造不相交線性碼的方法只有在k 整除n 時才可行.2014年, 張衛(wèi)國和Pasalic[1]利用不相交線性碼構造了能達到嚴格幾乎最優(yōu)非線性度的彈性S 盒, 另外還利用不相交線性碼構造了PS 類bent 函數(shù)和完全非線性S 盒.該篇論文充分利用了不相交線性碼, 這提示我們不相交線性碼在密碼函數(shù)的構造中有重要價值.其中還給出了一種不相交線性碼的構造方法.這種方法生成的不相交[n,k]線性碼的個數(shù)為其中當k |n 時, N(n,k)達到了最優(yōu)值; 當kn 時, 所得不相交[n,k]線性碼的個數(shù)是目前已知最好的結果.在kn 時, 是否存在一種方法能生成更多的不相交[n,k]線性碼, 是值得進一步研究的問題.由于張衛(wèi)國和Pasalic[1]在構造不相交[n,k]線性碼時, 需要借助很多個不同次數(shù)的本原多項式來進行計算, 其個數(shù)與成正比.因此, 當n ?k 時, 計算量很大.本文提出了不相交[n,k]線性碼的一種新構造, 即使當n、k 很大或n ?k 時, 仍可以快速有效地得到大量不相交[n,k]線性碼.

在本文構造中, 當k | n 時, 只需要借助一個k 次本原多項式便可生成個不相交[n,k]線性碼, 其中也就是說此時生成不相交[n,k]線性碼的個數(shù)達到了最優(yōu).當kn時, 只需要借助一個k 次本原多項式和一個m 次本原多項式便可生成大量的不相交[n,k]線性碼, 其中此時生成不相交[n,k]線性碼的的個數(shù)與文獻[1]生成不相交[n,k]線性碼的個數(shù)相同.本文的構造在保證生成不相交[n,k]線性碼的個數(shù)與文獻[1]生成不相交[n,k]線性碼的個數(shù)相同的情況下, 很大程度上簡化了計算過程, 極大地減少了計算量.越大, 本文構造的優(yōu)勢越明顯.后文的結構如下: 第2 節(jié), 主要介紹了線性碼和不相交線性碼的相關基礎知識; 第3 節(jié), 描述了一種構造不相交線性碼的新方法, 并給出相關證明; 第4 節(jié), 對本文工作進行了總結.

2 基礎知識

定義1將GF(2)上的n 維向量空間記為Vn, Vn的k 維線性子空間Vk稱為[n,k]線性碼, 記為C(n,k).[n,k]線性碼共有2k個n 維向量.

定義2以[n,k]線性碼C 的基底向量構成的矩陣稱為該[n,k]線性碼的生成矩陣, 記為G(n,k).

定義3設{C0(n,k), C1(n,k), ··· , Ct(n,k)} 均為[n,k]線性碼, 如果Ci(n,k)∩Cj(n,k)={01×n}, 其中0i,jt, 且ij, 則稱Ci(n,k), Cj(n,k)互為不相交[n,k]線性碼.

引理1將不相交[n,k]線性碼的個數(shù)記為N(n,k), 則

引理2令k,m,v 均為正整數(shù),其中km,v =2m?1.α 是F2m 上的本原元,(1,α,α2,··· ,αm?1)是F2m/F2上的基.定義同構σ :F2m →為

其中F2m上的零元素映射成中的零向量.令

則矩陣(Ik,Mi)是一系列不相交[k +m,k]線性碼Ci(k +m,k)對應的生成矩陣Gi(k +m,k), 其中i = 0,1,2,··· ,v ?1.當矩陣(Ik,Mi)是一系列不相交[k+m,k]線性碼對應的生成矩陣時, 矩陣(A,Ik,B,Mi,C)也是一系列不相交線性碼對應的生成矩陣, 其中A, B, C 為任意k×j 的矩陣, j 為任意非負整數(shù).

證明:Ci1(k + m,k)的每個碼字是Gi1(k + m,k)的線性組合, Ci2(k + m,k)的每個碼字是Gi2(k+m,k)的線性組合.要證Ci1(k+m,k)與Ci2(k+m,k)互為不相交線性碼,則只要證Gi1(k+m,k)中任意一行都與Gi2(k+m,k)線性無關即可, 其中i1i2.很顯然, 當i1i2時, (Ik,Mi1)中任意一行都與(Ik,Mi2)線性無關.因此, 矩陣(Ik,Mi)是一系列不相交[k+m,k]線性碼對應的生成矩陣.

3 構造方案

構造1令n, k, m, v1, v2, u 均為正整數(shù), 且kn, n>2k, m=n ?uk, v1=2k?1, v2=2m?1,將k×k 的單位矩陣記為Ik, 將k×k 的零矩陣記為0k, 將k×m 的零矩陣記為0′.α 是F2k上的本原元,是F2k/F2上的基, β 是F2m 上的本原元,是F2m/F2上的基.分別定義同構π1:F2k→π2:F2m →為

其中F2k上的零元素映射成中的零向量, F2m 上的零元素映射成中的零向量.令

其中i=0,1,2,··· ,v1?1, j =0,1,2,··· ,v2?1.令As是一個k×k 的矩陣, 其中s=1,2,··· ,u;A′是一個k×m 的矩陣.[n,k]線性碼對應的生成矩陣G(n,k)是一個k×n 的矩陣, 表示為

我們分三大步構造這種不相交線性碼的生成矩陣,

? 第一步: 令A1=0k, (A2,··· ,Au,A′)=G(n ?k,k).其中, G(n ?k,k)為不相交[n ?k,k]線性碼.稱其為第I 類[n,k]線性碼, 共有w 個, 其中w 為不相交[n ?k,k]線性碼的個數(shù).

? 第二步: 令A1=Ik, A′=0′.而后將第二步分成u 小步完成, 稱其為第II 類[n,k]線性碼.

– 第2 步, 對于某一s1∈{2,3,··· ,u}, 令As1=Mi.對于任意ss1, 令As=0k.i 從0 遍

歷到v1?1.稱其為第II-2 類[n,k]線性碼, 共有個;

...

– 第r+1 步, 對于s1,s2,··· ,sr∈{2,3,··· ,u}, 令Ast= Mit, t =1,2,··· ,r, 當t1t2時,st1st2.對于任意sst, 令As= 0k, t = 1,2,··· ,r.對于任意it都從0 遍歷到v1?1.

其中r =0,1,2,··· ,u ?1.

...

– 第u 步, 對于st=2,3,··· ,u, 令Ast=Mit, t=1,2,··· ,u ?1, 當t1t2時, st1st2.同樣, 對于任意it都從0 遍歷到v1?1.稱其為第II-u 類[n,k]線性碼, 共有個.

? 第三步: 令A1= Ik, A′=而后將第三步分成u 小步完成, 稱其為第III 類[n,k]線性碼.這u 小步與第二大步里的u 小步相同, 分別稱其為第III-(r +1)類[n,k]線性碼, 其中r =0,1,2,··· ,u ?1.因為與0′的差別, 其中j 從0 遍歷到v2?1, 所以第三步生成的不相交線性碼共有

證明:因為G(n ?k,k)是一系列不相交[n ?k,k]線性碼的生成矩陣, 所以第I 類[n,k]線性碼是不相交線性碼.由引理2 可知, 第II-(r+1)類[n,k]線性碼是不相交線性碼, 其中r =1,2,··· ,u ?1.同理, 第III-(r+1)類[n,k]線性碼是不相交線性碼, 其中r = 1,2,··· ,u ?1.對于第二大步, 因為每一小步中, 值為Mi的As的個數(shù)都不同.所以對于任意第II-r1類不相交線性碼和任意第II-r2類不相交線性碼, 總存在第II-r1類不相交線性碼中Ast1= Mi, 而第II-r2類不相交線性碼中Ast1= 0k, 其中r1r2.因此第II 類[n,k]線性碼是不相交線性碼.同理, 第III 類[n,k]線性碼是不相交線性碼.因為在第I 類[n,k]線性碼中A1=0k, 而在第II 類[n,k]線性碼和第III 類[n,k]線性碼中A1=Ik, 所以第I 類與第II 類不相交, 第I 類與第III 類也不相交.在第II 類[n,k]線性碼中A′= 0′, 在第III 類[n,k]線性碼中A′=所以第II 類與第III 類不相交.因此, 用這種構造方法得到的[n,k]線性碼是不相交線性碼.

因為G(n ?k,k)也是由Ik, 0k, 0′, Mi,構成的.所以在整個構造過程中, 我們只需要Ik, 0k,0′, Mi,五種矩陣.其中借助一個k 次本原多項式和一個m 次本原多項式即可得到所有的Mi和在很大程度上簡化了計算過程, 減少了計算量.

定理1將構造1 生成[n,k]不相交線性碼的數(shù)量記為N1(n,k).N1(n,k)=1+n>k,且

證明:當n=2k+b, 0

其中Gl(k+b,k)=(Ik,0k×b), 則N1(2k+b,k)=1+2m, 此時符合定理.

假設當n=ak+b 時, 滿足N1(n,k)=1+

當n=(a+1)k+b 時,

即此時符合定理.

綜上, 得證.

例1由構造1 生成不相交[10,3]線性碼, 此時n = 10, k = 3, m = 4, v1= 7, v2= 15, u = 2,N1(n,k)= 145, w = 17, δ = 1.π1(α0)= (1,0,0), π1(α1)= (0,1,0), π1(α2)= (0,0,1), 可取本原多項式, p(x)= x3+x+1, 此時, π1(α3)= (1,1,0), π1(α4)= (0,1,1), π1(α5)= (1,1,1), π1(α6)= (1,0,1).π2(β0)= (1,0,0,0), π2(β1)= (0,1,0,0), π2(β2)= (0,0,1,0), π2(β3)= (0,0,0,1), 可取本原多項式p(x)= x4+ x + 1, 此時, π2(β4)= (1,1,0,0), π2(β5)= (0,1,1,0), π2(β6)= (0,0,1,1), π2(β7)=(1,1,0,1)等等, 這里不再一一列出.簡略地列出所生成的不相交[10,3]線性碼對應的生成矩陣Gl(10,3)為

例2由構造1 生成不相交[11,3]線性碼, 此時n = 11, k = 3, m = 5, v1= 7, v2= 31, u = 2,N1(n,k)= 289, w = 33, δ = 3.π1(α0), π1(α1), ···, π1(α6)同例1.π2(β0)= (1,0,0,0,0), π2(β1)=(0,1,0,0,0), π2(β2)= (0,0,1,0,0), π2(β3)= (0,0,0,1,0), π2(β4)= (0,0,0,0,1), 可取本原多項式p(x)=x5+x2+1.簡略地列出所生成的不相交[11,3]線性碼對應的生成矩陣Gl(11,3)為

例3由構造1 生成不相交[13,3]線性碼, 此時n = 13, k = 3, m = 4, v1= 7, v2= 15, u = 3,N1(n,k)= 1169, w = 145, δ = 1.π1(α0), π1(α1), ···, π1(α6)同例1.π2(β0), π2(β1), ···, π2(β14)同例1.簡略地列出所生成的不相交[13,3]線性碼對應的生成矩陣Gl(13,3)為

3.2 k |n

構造2k |n 是kn 的特殊情況, 即即在整個構造過程中, 我們只需要Ik, 0k, Mi三種矩陣, 只需要借助一個k 次本原多項式即可得到所有的Mi.這在更大程度上簡化了計算過程, 減少了計算量.此時, 還有更簡潔的構造過程.令As是一個k×k 的矩陣, 其中s=1,2,··· ,u+1.[n,k]線性碼對應的生成矩陣G(n,k)是一個k×n 的矩陣, 表示為

我們分兩大步構造這種不相交線性碼的生成矩陣,

? 第一步: 令A1= 0k, (A2,··· ,Au,Au+1)= G(n ?k,k), 其中G(n ?k,k)為不相交[n ?k,k]線性碼.稱其為第I 類[n,k]線性碼, 共有w 個, 其中w 為不相交[n ?k,k]線性碼的個數(shù).

? 第二步: 令A1=Ik.而后將第二步分成u+1 小步完成, 稱其為第II 類[n,k]線性碼.

– 第2 步, 對于某一s1∈{2,3,··· ,u+1}, 令As1=Mi.對于任意ss1, 令As=0k.i 從0遍歷到v1?1.稱其為第II-2 類[n,k]線性碼, 共有個;

...

– 第r+1 步, 對于s1,s2,··· ,sr∈{2,3,··· ,u+1}, 令Ast=Mit, t=1,2,··· ,r, 當t1t2時, st1st2.對于任意sst, 令As=0k, t=1,2,··· ,r.對于任意it都從0 遍歷到v1?1.稱其為第II-(r+1)類[n,k]線性碼, 共有個;

其中r =0,1,2,··· ,u.

...

– 第u+1 步, 對于st=2,3,··· ,u+1, 令Ast=Mit, t=1,2,··· ,u, 當t1t2時, st1st2.同樣, 對于任意it都從0 遍歷到v1?1.稱其為第II-(u+1)類[n,k]線性碼, 共有個.

證明:同理構造1, 第I 類[n,k]線性碼是不相交線性碼; 第II-(r+1)類[n,k]線性碼是不相交線性碼, 其中r =1,2,··· ,u; 第II 類[n,k]線性碼是不相交線性碼; 第I 類與第II 類不相交.因此, 用這種構造方法得到的[n,k]線性碼是不相交線性碼.

定理2將構造2 生成[n,k]不相交線性碼的數(shù)量記為且

證明:當n=2k 時, 按構造2 生成的不相交[n,k]線性碼對應的生成矩陣為

其中Gl(k,k)=Ik, 則N2(2k,k)=1+2k, 此時符合定理.

當n=(a+1)k 時,

即此時符合定理.

綜上, 得證.

例4用構造2 生成不相交[6,2]線性碼, 此時n = 6, k = 2, v = 3, u = 2, N2(n,k)= 21, w = 5,π1(α0)= (1,0), π1(α1)= (0,1), 可取本原多項式p(x)= x2+x+1, 此時, π1(α2)= (1,1).由構造2 生成的不相交[6,2]線性碼對應的生成矩陣Gl(6,2)見表1.

表1 不相交[6,2]線性碼對應的生成矩陣Table 1 G of disjoint [6,2]linear codes

例5用構造2 生成不相交[9,3]線性碼, 此時n = 9, k = 3, v = 7, u = 2, N2(n,k)= 73, w = 9.π1(α0), π1(α1), ···, π1(α6)同例1.簡略地列出所生成的不相交[9,3]線性碼對應的生成矩陣Gl(9,3)為

例6用構造2 生成不相交[12,3]線性碼, 此時n=12, k =3, v =7, u=3, N2(n,k)=585, w =73.π1(α0), π1(α1), ···, π1(α6)同例1.簡略地列出所生成的不相交[12,3]線性碼對應的生成矩陣Gl(12,3)為

4 總結

本文給出了不相交[n,k]線性碼的新構造.通過該構造生成的不相交線性碼的個數(shù)為目前已知最優(yōu).本文運用簡潔明了的劃分方式生成了一系列的不相交線性碼, 使得在k 整除n 和k 不整除n 兩種情況下生成不相交線性碼的計算量都比現(xiàn)有構造方法的計算量小.本文構造的不相交線性碼可以用于流密碼系統(tǒng)中具有高非線性度的多輸出彈性密碼函數(shù)的構造.我們給出了一部分本文構造所生成的不相交線性碼的個數(shù), 見表2.

表2 本文構造所生成的不相交[n,k]線性碼的個數(shù)Table 2 Number of disjoint [n,k]linear codes in proposed works