Xiao-Massey 定理: 歷史背景、學(xué)術(shù)影響和原創(chuàng)性*

張衛(wèi)國(guó)

西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室, 西安 710071

1 Xiao-Massey 定理的歷史背景與命題本質(zhì)

第二次世界大戰(zhàn)后, 數(shù)字電路技術(shù)在工程中逐漸被廣泛應(yīng)用, 流密碼的發(fā)展也逐漸從機(jī)械密碼時(shí)代過渡到數(shù)字電路密碼時(shí)代. 上世紀(jì)五十年代至七十年代, 是移位寄存器序列(shift register sequence) 理論蓬勃發(fā)展的時(shí)期, 有關(guān)線性移位寄存器(linear feedback shift register, LFSR) 的理論成果逐漸成熟[1–3].同一時(shí)期, 編碼理論和技術(shù)也得到較為充分的發(fā)展[4,5]. 在上世紀(jì)六十年代后期, Berlekamp[4,6]在BCH碼的譯碼方案中給出一種從校驗(yàn)子找出錯(cuò)位多項(xiàng)式的迭代算法, 這種算法的實(shí)質(zhì)是運(yùn)用歸納法確定一系列LFSR 的結(jié)構(gòu). Massey[7]也獨(dú)立地給出同一算法,解決了LFSR 的綜合問題. 所謂LFSR 的綜合,是指對(duì)一個(gè)給定的二元周期序列, 找出產(chǎn)生該序列的最少級(jí)數(shù)的LFSR. 后人稱這一算法為Berlekamp-Massey算法(BM 算法). BM 算法的提出, 對(duì)流密碼的發(fā)展產(chǎn)生了深遠(yuǎn)影響, 它提示人們用于加解密的二元序列應(yīng)該具有較高的線性復(fù)雜度[8]; 后來又進(jìn)一步考慮了序列線性復(fù)雜度的穩(wěn)定性問題, 引入序列的重量復(fù)雜度和球體復(fù)雜度等度量指標(biāo)[9–11].

在生成偽隨機(jī)序列的方式中, 利用非線性移位寄存器(nonlinear feedback shift register, NFSR) 生成序列是非常吸引人的方式, 可以實(shí)現(xiàn)具有優(yōu)良隨機(jī)性質(zhì)(包括高線性復(fù)雜度) 的序列的生成. 遺憾的是, 時(shí)至今日對(duì)這種生成序列的方式的研究仍不成熟. BM 算法問世之后, 人們對(duì)生成“復(fù)雜” (不止是高線性復(fù)雜度) 序列的流密碼系統(tǒng)的研究走向了另一方向.

上世紀(jì)七十年代初, Groth[12]在一個(gè)LFSR 生成的序列中置入乘法運(yùn)算, 這實(shí)際上是給序列生成器加入了非線性邏輯結(jié)構(gòu). 這種非線性前饋(feedforward) 結(jié)構(gòu)和NFSR 結(jié)構(gòu)有本質(zhì)的不同, 所生成的序列不再反饋到移位寄存器參與下一次非線性運(yùn)算. 非線性前饋結(jié)構(gòu)的引入對(duì)于提高生成序列的線性復(fù)雜度有明顯效果[13]. 經(jīng)過十多年的發(fā)展, 逐漸形成了一系列基于LFSR 的非線性序列生成器[8,14–18]. 非線性組合模式和非線性濾波(前饋) 模式這兩種非線性序列生成器成為最經(jīng)典的流密碼體制, 見圖1. 在圖1 中,f:→F2是一個(gè)n元布爾函數(shù).f的性質(zhì)直接影響系統(tǒng)的安全性, 它應(yīng)是一個(gè)非線性布爾函數(shù). 系統(tǒng)經(jīng)由f所生成的序列一般稱為非線性序列.

圖1 非線性組合模式和非線性濾波模式的流密碼系統(tǒng)Figure 1 Stream cipher for nonlinear combination mode and nonlinear filter mode

與此同時(shí), 對(duì)非線性序列的分析理論也逐漸成熟[8,10,11,13,19–27]. 對(duì)多個(gè)LFSR 序列進(jìn)行布爾組合的方式最早由Golomb[28]提出, 但當(dāng)時(shí)的目的并不是為了密碼應(yīng)用, 而是為了測(cè)距需要[29].

假設(shè)圖1 a) 中第i個(gè)LFSR 的級(jí)數(shù)為ri,i=1,2,··· ,n, 這n個(gè)LFSR 的初始狀態(tài)和線性反饋系數(shù)共同構(gòu)成密碼系統(tǒng)的密鑰. 為了最大化生成序列的周期, 線性反饋系數(shù)一般選擇本原多項(xiàng)式對(duì)應(yīng)的系數(shù)以生成周期為2ri-1 的m序列. 同時(shí), LFSR 初始狀態(tài)避免取全零. 用Ri=φ(2ri-1)/ri表示F2上ri次本原多項(xiàng)式的個(gè)數(shù), 其中φ(n) 是Euler 函數(shù), 定義為與正整數(shù)n互素且不大于n的正整數(shù)的個(gè)數(shù). 該系統(tǒng)可能的密鑰總量為其中P(A) 表示事件A發(fā)生的概率. 設(shè)上述n個(gè)序列經(jīng)由f后所生成的密鑰流序列(z(k)) =z(1),z(2),z(3),···是由獨(dú)立同分布的隨機(jī)變量z所產(chǎn)生, 并有

上面討論的分別征服攻擊只考慮了單個(gè)LFSR 所產(chǎn)生的序列與密文序列的相關(guān)性, 這一攻擊當(dāng)然可以進(jìn)一步考慮多個(gè)LFSR 的輸出序列進(jìn)行疊加(模2 加法運(yùn)算) 后所得到的序列與密文序列的相關(guān)性. 這就引出Siegenthaler 對(duì)t階相關(guān)免疫函數(shù)的定義[39]. 設(shè)X=(x1,x2,··· ,xn), 其中x1,x2,··· ,xn是n個(gè)獨(dú)立同分布二元隨機(jī)變量. 設(shè)Bn是所有n元布爾函數(shù)的集合. 若f(X)∈Bn和x1,x2,··· ,xn中的任意t個(gè)變量都是統(tǒng)計(jì)獨(dú)立的, 則稱f(X) 是t階相關(guān)免疫函數(shù). Siegenthaler 在文獻(xiàn)[39] 中還給出一種t階相關(guān)免疫函數(shù)的遞歸構(gòu)造方法, 并給出t階相關(guān)免疫函數(shù)代數(shù)次數(shù)的上界. Siegenthaler[32]還曾給出抵抗分別征服攻擊的組合部件的設(shè)計(jì)方案, 但并沒有產(chǎn)生多大影響. Siegenthaler 的貢獻(xiàn)在于他基于Blaser 和Heinzmann 的思想給出分別征服攻擊的統(tǒng)計(jì)模型, 并定義了布爾函數(shù)的相關(guān)免疫性. 他給出的相關(guān)免疫函數(shù)的遞歸構(gòu)造法, 雖然可以保證每一步得到的函數(shù)都是t階相關(guān)免疫, 但函數(shù)的非線性度很差.Siegenthaler 對(duì)相關(guān)免疫性的定義看起來嚴(yán)謹(jǐn)清晰, 但對(duì)函數(shù)設(shè)計(jì)和分析的指導(dǎo)意義較弱.

上世紀(jì)八十年代中期, 肖國(guó)鎮(zhèn)提出“線性統(tǒng)計(jì)獨(dú)立” (linear statistical independence) 的概念, 并用頻譜方法對(duì)非線性生成器進(jìn)行相關(guān)分析, 刻畫了線性統(tǒng)計(jì)獨(dú)立函數(shù)的頻譜特征.

線性統(tǒng)計(jì)獨(dú)立概念的提出動(dòng)機(jī)是為了研究圖1 中流密碼系統(tǒng)產(chǎn)生的密文序列與系統(tǒng)中一個(gè)或多個(gè)LFSR 所產(chǎn)生的序列的線性統(tǒng)計(jì)關(guān)聯(lián)性. 下面我們先描述一下線性統(tǒng)計(jì)獨(dú)立的概念.

定義1 設(shè)f是關(guān)于隨機(jī)變量x1,x2,··· ,xn的n元布爾函數(shù), 并設(shè)1≤t ≤n-1,ν ∈F2,aj ∈F2,j=1,2,··· ,t. 若任取t個(gè)隨機(jī)變?cè)獂i1,xi2,··· ,xit, 1≤i1＜i2＜···＜it ≤n, 恒有

其中線性組合運(yùn)算是在F2上進(jìn)行的, 且t是具有上述性質(zhì)的最大正整數(shù), 則稱f是t階線性統(tǒng)計(jì)獨(dú)立的.否則, 若對(duì)任意t, 1≤t ≤n-1,f都不是線性統(tǒng)計(jì)獨(dú)立的, 則稱f為完全線性相關(guān)的.

下面的定理由肖國(guó)鎮(zhèn)于1985 年6 月在第23 屆ISIT 國(guó)際會(huì)議的報(bào)告“The spectrum method in correlation analysis of non-linear generator” 中給出[40].

定理1f ∈Bn是t階線性統(tǒng)計(jì)獨(dú)立函數(shù)的當(dāng)且僅當(dāng)對(duì)Fn2中滿足1≤wt(α)≤t的α, 都有Sf(α)=0, 其中Sf(α) 是f在點(diǎn)α的Fourier 變換, 定義為:

這一成果是流密碼發(fā)展史上最重要的成果之一, 開創(chuàng)性地用布爾函數(shù)的頻譜特征簡(jiǎn)潔地刻畫出布爾函數(shù)為t階線性統(tǒng)計(jì)獨(dú)立(t階相關(guān)免疫) 的充要條件. 這一成果開辟了流密碼研究的新領(lǐng)域, 對(duì)密碼函數(shù)的設(shè)計(jì)和分析產(chǎn)生了深遠(yuǎn)影響.

肖國(guó)鎮(zhèn)在ISIT ’85 宣讀的研究成果引起國(guó)際同行的極大興趣. 很多學(xué)者就這些成果提出自己的觀點(diǎn)和建議, 這些學(xué)者主要有Massey、Siegenthaler、Duella、Golomb 等, 其中以Massey 提供的修改建議最具建設(shè)性. 1985 年8 月, 肖國(guó)鎮(zhèn)與Massey 共同署名將論文提交至IEEE Transactions on Information Theory (TIT) 評(píng)審. 這一論文的最終版本中沒有使用“線性相關(guān)獨(dú)立” 這一概念, 而是使用了“相關(guān)免疫” 這一概念. 1988 年5 月, 論文以“A spectral characterization of correlation-immune combining functions” 為題目正式發(fā)表[41].

這一論文中特別值得一提的是論文首頁(yè)的引理, 后人稱之為Xiao-Massey 引理[38,42]. 有了這一引理,就建立起從相關(guān)免疫這一概念到Xiao-Massey 定理的橋梁. 同時(shí), 這一引理既給出了概率統(tǒng)計(jì)上的一個(gè)重要結(jié)論, 也為密碼分析技術(shù)提供了指引.

引理1 (Xiao-Massey 引理) 離散隨機(jī)變量Z和t個(gè)相互獨(dú)立的二元隨機(jī)變量Y1,Y2,··· ,Yt都是相互獨(dú)立的, 當(dāng)且僅當(dāng)Z和c1Y1+c2Y2+···+ctYt是相互獨(dú)立的, 其中(c1,c2,··· ,ct)∈.

引理1 的證明可參閱文獻(xiàn)[42,43]. 由這一引理比較容易地推出Xiao-Massey 定理. 文獻(xiàn)[41] 中還有一些其他結(jié)論, 這里不再介紹.

彈性函數(shù)的提出時(shí)間稍晚于相關(guān)免疫函數(shù), 最早由Chor 等人提出[44], 是一種多輸出布爾函數(shù)→Fm2, 用F表示.F的m個(gè)分量函數(shù)的任意非零線性組合都是平衡的相關(guān)免疫函數(shù). 由于平衡性是密碼函數(shù)設(shè)計(jì)時(shí)總要考慮的, 人們所設(shè)計(jì)的(多輸出) 相關(guān)免疫函數(shù)一般都是彈性函數(shù). 線性統(tǒng)計(jì)獨(dú)立、相關(guān)免疫、彈性, 這些概念是在同一時(shí)期被獨(dú)立提出的, 它們的定義都是從概率統(tǒng)計(jì)的觀點(diǎn)給出的. Xiao-Massey定理用代數(shù)的觀點(diǎn)從頻譜的角度給出這些定義的等價(jià)描述.

設(shè)α ∈Fn2,f ∈Bn.f在α點(diǎn)的Walsh 變換定義為

借助關(guān)系(-1)f(X)=1-2f(X), 可得到Sf(α) 和Wf(α) 的關(guān)系:

由(4) 式可以看出, 在α/=0n的前提下,Wf(α)=0 當(dāng)且僅當(dāng)Sf(α)=0. 同時(shí), 注意到f是平衡布爾函數(shù)當(dāng)且僅當(dāng)Wf(0n)=0. 因而, Xiao-Massey 定理如今也常被描述成如下定理.

定理2f ∈Bn是t階彈性布爾函數(shù)的當(dāng)且僅當(dāng)對(duì)Fn2中滿足0≤wt(α)≤t的α, 都有Wf(α)=0.

2 Xiao-Massey 定理的學(xué)術(shù)價(jià)值和學(xué)術(shù)影響

本節(jié)分析整理Xiao-Massey 定理的被引用情況, 進(jìn)一步闡述其學(xué)術(shù)價(jià)值和學(xué)術(shù)影響.

(1) Xiao-Massey 定理對(duì)相關(guān)免疫(彈性) 函數(shù)的刻畫簡(jiǎn)潔而深刻, 已成為研究密碼函數(shù)的奠基性定理. 該定理的提出使頻譜理論方法從此成為研究密碼函數(shù)的最重要的代數(shù)工具之一.

從上世紀(jì)八十年代中期至今, Xiao-Massey 定理被國(guó)內(nèi)外同行廣泛引用, 深遠(yuǎn)地影響著流密碼理論的發(fā)展. 密碼學(xué)家Rueppel[45]最早在Crypto ’85 引用了Xiao-Massey 定理, 并把這一定理寫進(jìn)他在1986年出版的著名專著《Analysis and Design of Stream Ciphers》中[8]. Pichler[46]在Eurocrypt ’86 用Walsh-Fourier 分析方法實(shí)現(xiàn)了具有相關(guān)免疫性的開關(guān)函數(shù)的設(shè)計(jì), Mund 等人[47]在Eurocrypt ’87 利用頻譜方法研究了DES 體制中的S 盒, Forrié[48]在Crypto’88 用布爾函數(shù)的頻譜特征給出其滿足SAC的充要條件, Preneel 等人[49]在Eurocrypt ’90 利用布爾函數(shù)的Walsh 變換和自相關(guān)函數(shù)的關(guān)系研究了函數(shù)的擴(kuò)散特征. 劉育人是較早注意到Xiao-Massey 定理的中國(guó)臺(tái)灣學(xué)者, 1988 年他在文獻(xiàn)[50] 中用頻譜方法研究了非線性移位寄存器及其線性等價(jià)系統(tǒng)問題. 更多引用Xiao-Massey 定理的文獻(xiàn)可參閱[51—194].

(2) Xiao-Massey 定理在布爾函數(shù)多密碼指標(biāo)折中優(yōu)化中具有重要價(jià)值, 在構(gòu)造高非線性度的相關(guān)免疫(彈性) 函數(shù)這一研究課題中扮演了“方向盤” 的作用, 指導(dǎo)了一大批優(yōu)秀密碼函數(shù)構(gòu)造方法的提出.

Meier 和Staffelbach[195]在Eurocrypt’89 從頻譜的角度給出了非線性度的計(jì)算公式,借助Parseval恒等式和Xiao-Massey 定理, 初步明確了非線性度和相關(guān)免疫性(彈性) 之間存在制約關(guān)系. 由于彈性和非線性度都可通過計(jì)算布爾函數(shù)的頻譜得到, Xiao-Massey 定理在高非線性度彈性函數(shù)設(shè)計(jì)這一課題中扮演著舉足輕重的角色. 基于Xiao-Massey 定理和頻譜分析方法, 一大批便于確定彈性階和非線性度的密碼函數(shù)構(gòu)造方法被提出, 可參閱文獻(xiàn)[196—304].

(3) Xiao-Massey 引理和Xiao-Massey 定理對(duì)密碼分析的價(jià)值.

1989 年, Meier 和Staffelbach[38]在Journal of Cryptology 發(fā)表論文“Fast correlation attacks on certain stream ciphers”, 提出針對(duì)流密碼系統(tǒng)的快速相關(guān)攻擊. 在該文中用Xiao-Massey 引理解釋攻擊在特定情況下的可行性. Maurer 和Massey[305]在Crypto ’89 用Xiao-Massey 引理解釋了偽隨機(jī)序列中的完全局部隨機(jī)性中的安全性問題. Xiao-Massey 引理也被Goli?[306]在Eurocrypt ’92 用來研究帶記憶非線性組合器相關(guān)性質(zhì), 進(jìn)而考慮了多種非線性組合模式下的安全問題[307]. Heys[308]定義了對(duì)線性分析(m,n)-免疫的概念, 基于Xiao-Massey 引理給出分組密碼系統(tǒng)對(duì)線性分析(m,n)-免疫的充要條件.更多相關(guān)引用文獻(xiàn)可參閱[309—330].

(4) Xiao-Massey 定理的發(fā)展以及在其他領(lǐng)域的應(yīng)用.

Forré[331]從條件熵的角度考慮了S 盒輸入和輸出之間的“垂直獨(dú)立”, 不同輸出之間的“水平” 獨(dú)立.把肖國(guó)鎮(zhèn)提出的“線性統(tǒng)計(jì)獨(dú)立” 推廣到非線性函數(shù)之間的統(tǒng)計(jì)獨(dú)立.

馮登國(guó)[332]用廣義一階Walsh 譜刻畫了多輸出相關(guān)免疫函數(shù)的特征, 用Chrestenson 譜刻畫了剩余類環(huán)上的多值邏輯相關(guān)免疫函數(shù)的特征, 用離散Fourier 譜刻畫了有限域上的相關(guān)免疫函數(shù)的特征, 系統(tǒng)全面地發(fā)展了Xiao-Massey 定理.

Stinson[333,334]從正交陣列的角度刻畫了彈性函數(shù)的特征, 進(jìn)而在1995 年和Gopalakrishnan 進(jìn)一步從相伴矩陣、Fourier 變換、正交陣列等角度刻畫了非二元相關(guān)免疫和彈性函數(shù)的特征[335]. 后來,Xiao-Massey 定理又在Abel 群和復(fù)數(shù)域上被推廣[336,337].

Xiao-Massey 定理以充要條件的形式刻畫了相關(guān)免疫(彈性) 函數(shù)的頻譜特征, 確定了哪些點(diǎn)的譜值必定為0. 但是, 由Xiao-Massey 定理并不知道那些非零譜值有何特征. 2000 年, 人們發(fā)現(xiàn)t階相關(guān)免疫(彈性) 函數(shù)f ∈Bn的頻譜必定被2t+1(2t+2) 整除[338–340]. 這一結(jié)論是t階相關(guān)免疫(彈性) 函數(shù)頻譜特征的進(jìn)一步刻畫, 是對(duì)Xiao-Massey 定理的發(fā)展.

Lacharme[341,342]從布爾函數(shù)角度研究了真隨機(jī)數(shù)生成器的校正器的分析和設(shè)計(jì)問題, 給出t階校正器的頻譜特征. 對(duì)單輸出布爾函數(shù)f ∈Bn而言, 它是t階校正器的充要條件是

結(jié)合Xiao-Massey 定理可知, 任意t階彈性函數(shù)必定是t階校正器, 反之不然.

Xiao-Massey 定理還在下面研究課題中發(fā)揮著作用: 二元(雙極) 序列的量子糾纏態(tài)相關(guān)指標(biāo)的度量[343]、決策(投票) 規(guī)則的敏感性指標(biāo)度量[344]、欺騙免疫秘密共享方案的設(shè)計(jì)[345]、抗病毒行為檢測(cè)策略模型[346]等.

關(guān)于Xiao-Massey 定理的意義和作用, 讀者還可參閱文獻(xiàn)[347].

3 “Golomb 不變量” 的歷史背景和概念本質(zhì)

“相關(guān)免疫函數(shù)的頻譜化特征定理” 這一研究成果在國(guó)際上公認(rèn)首創(chuàng)屬于肖國(guó)鎮(zhèn)和Massey, 并稱之為“Xiao-Massey 定理”. 但是,在2018 年第4 期TIT 紀(jì)念Solomon W.Golomb 的?？蠀s有觀點(diǎn)認(rèn)為這一成果的首創(chuàng)應(yīng)屬Golomb, 過度解讀了Golomb 提出的“不變量”(invariant)的概念, 見文獻(xiàn)[348,Section VIII]. 受這一錯(cuò)誤觀點(diǎn)的影響,在2021 年出版的專著“Boolean Functions for Cryptography and Coding Theory”[349]中又把“Xiao-Massey 定理” 誤稱為“Golomb-Xiao-Massey characterization”. 這一研究成果的歸屬問題在肖國(guó)鎮(zhèn)、Massey、Golomb 三位學(xué)者都在世時(shí)沒有爭(zhēng)議, 近年來在這一問題上出現(xiàn)的錯(cuò)誤觀點(diǎn)既不符合學(xué)術(shù)事實(shí), 也不符合三位學(xué)者生前達(dá)成的共識(shí).

每一個(gè)概念或定理的產(chǎn)生, 都不是憑空而來的, 都有其特定的歷史背景. 下面我們通過梳理Golomb提出“不變量” 的歷史背景, 揭示其概念本質(zhì). 這一概念本質(zhì)上描述了在特定等價(jià)關(guān)系下不同布爾函數(shù)具有某種共同的頻譜特征, 它既不等同于相關(guān)免疫這一概念, 更沒有揭示Xiao-Massey 定理所描述的規(guī)律.

1938 年, Shannon 發(fā)表了重要論文“A symbolic analysis of relay and switching circuits”[350], 闡述了他在1937 年提交的碩士論文中的主要工作. 他創(chuàng)造性地在布爾代數(shù)[351,352]和開關(guān)電路之間建立了關(guān)聯(lián), 實(shí)現(xiàn)了從布爾邏輯到電路功能的轉(zhuǎn)化, 創(chuàng)建了開關(guān)電路理論. Shannon 把開關(guān)電路理論中的問題分為兩類: “分析問題” (analysis problem) 和“綜合問題” (synthesis problem). 分析問題是對(duì)確定的開關(guān)電路分析其性質(zhì)功能, 綜合問題是尋找具有特定性質(zhì)功能的電路. 前者是相對(duì)容易的問題, 而后者是非常困難的問題[353–356]. 這一時(shí)期, 一系列開關(guān)電路的分析和綜合問題被轉(zhuǎn)化為數(shù)學(xué)問題進(jìn)行研究[357–367]. 到了上世紀(jì)七十年代中期, 由開關(guān)電路的綜合問題逐漸發(fā)展出電子設(shè)計(jì)自動(dòng)化(electronic design automation,EDA) 技術(shù). 綜合問題的困難之處在于如何以最低的代價(jià)實(shí)現(xiàn)電路功能, 同時(shí)考慮電路的功耗、速度等因素. 早期的綜合問題主要考慮如何用相對(duì)簡(jiǎn)單的方式實(shí)現(xiàn)具有特定功能的電路. 1949 年, Shannon 又進(jìn)一步發(fā)展了開關(guān)電路綜合問題的理論和方法[353]. Shannon 指出變?cè)獋€(gè)數(shù)相對(duì)較大的n元布爾函數(shù)絕大多數(shù)實(shí)現(xiàn)起來都是相當(dāng)復(fù)雜的. 另一方面, 現(xiàn)實(shí)中使用的n個(gè)變?cè)碾娐范际欠浅：?jiǎn)單的. 對(duì)產(chǎn)生這個(gè)“矛盾” 的原因, Shannon 是這樣解釋的: 電路設(shè)計(jì)實(shí)踐中使用的布爾函數(shù)不是隨機(jī)選擇的. 為了有助于在實(shí)現(xiàn)電路功能時(shí)能選擇到結(jié)構(gòu)相對(duì)簡(jiǎn)單的布爾函數(shù), Shannon 給出兩種函數(shù)關(guān)系(functional relation), 一種叫函數(shù)可分關(guān)系(functional separability),另一種是特殊情形下的群不變關(guān)系(group invariance). 對(duì)前一種函數(shù)關(guān)系, 這里不作介紹. 后一種函數(shù)關(guān)系是指函數(shù)f ∈Bn滿足如下群不變性質(zhì): 對(duì)任意xi,ai ∈F2,0≤i ≤n, 總有

其中(i1,i2,··· ,in) 是(1,2,··· ,n) 的置換. 需要說明的是, Shannon 當(dāng)時(shí)研究的布爾函數(shù)中的乘法運(yùn)算規(guī)則與普通乘法規(guī)則相同, 而加法運(yùn)算規(guī)則為: 0+0=0, 0+1=1, 1+0=1, 1+1=1, 這并不影響討論的結(jié)果. (5)式中等號(hào)左右兩邊變?cè)淖儞Q關(guān)系是兩種運(yùn)算復(fù)合而成的: 一種是對(duì)(x1,x2,··· ,xn) 進(jìn)行置換運(yùn)算, 另一種是對(duì)x1,x2,···,xn中的k個(gè)變?cè)M(jìn)行取反運(yùn)算, 0≤k ≤n. 復(fù)合后的運(yùn)算共有2nn!種可能, 構(gòu)成一個(gè)群G.

1953 年, Slepian[368]把Shannon 在(5)式中給出的群不變關(guān)系推廣到兩個(gè)不同函數(shù)之間, 定義了一種等價(jià)關(guān)系. 設(shè)f1,f2∈Bn. 稱f1和f2是等價(jià)的, 若對(duì)任意xi,ai ∈F2, 0≤i ≤n, 總有

其中(i1,i2,··· ,in) 是(1,2,··· ,n) 的置換. 這一等價(jià)關(guān)系把n元布爾函數(shù)劃分為Nn個(gè)等價(jià)類, Slepian利用群論相關(guān)方法和結(jié)論[369,370]計(jì)算了Nn的數(shù)量. 同一等價(jià)類中的布爾函數(shù)被設(shè)計(jì)成電路后看作是功能等價(jià)的電路, 而Nn的值代表功能不等價(jià)電路的數(shù)量. 在這個(gè)意義上, 對(duì)等價(jià)類進(jìn)行計(jì)數(shù)是有現(xiàn)實(shí)意義的. 注意到, Golomb 在1958 年也撰寫了一篇研究等價(jià)類計(jì)數(shù)的技術(shù)報(bào)告[371].

1959 年, Golomb[365,372]又進(jìn)一步推廣了(6)式中Slepian 所定義的等價(jià)關(guān)系: 對(duì)b ∈F2, 若對(duì)任意xi,ai ∈F2, 0≤i ≤n, 總有其中(i1,i2,··· ,in) 是(1,2,··· ,n) 的置換, 則稱f1∈Bn和f2∈Bn是等價(jià)的. 這可以看作是一種更廣義的群不變關(guān)系. 由這一等價(jià)關(guān)系把n元布爾函數(shù)劃分的等價(jià)類數(shù)量可以參考Slepian 的計(jì)算方法得到. 等價(jià)類的具體數(shù)量對(duì)我們下面的討論并不重要. 假設(shè)等價(jià)類的數(shù)量是ν, 并把ν個(gè)等價(jià)類記為E1,E2,··· ,Eν. 可知,E1∪E2∪···∪Eν=Fn2且Ei ∩Ej=?, 1≤i ＜j ≤ν.

Golomb 發(fā)現(xiàn), 對(duì)同一等價(jià)類Ei中的所有布爾函數(shù)而言, 它們具有共同的“不變量” (invariant).Golomb 具體地描述了0 階和1 階不變量的定義, 并以2 階不變量為例定義了高階不變量. 為了清晰地闡釋不變量的實(shí)質(zhì), 下面用一種較為簡(jiǎn)潔的方式來一般性地描述t階不變量.

設(shè)0≤t ≤n.t階不變量的一般性定義描述如下: 設(shè)f ∈Ei, 1≤i ≤ν. 對(duì)α ∈Fn2, 定義Rα=max{cα,2n-cα}, 其中

顯然, 2n-1≤Rα ≤2n. 設(shè)多重集

我們從頻譜角度分析一下, 對(duì)同一等價(jià)類Ei中的布爾函數(shù)而言, 為什么它們會(huì)有相同的t階不變量?在Golomb 給出的這一等價(jià)關(guān)系下,f ∈Bn所屬等價(jià)類中的任一函數(shù)g ∈Bn和f都是擴(kuò)展仿射等價(jià)的(extended affine equivalent), 并滿足g(X)=f(XA+α)+b, 其中α=(a1,a2,··· ,an)∈Fn2,b ∈F2,A是把n階單位陣的列向量進(jìn)行某一置換得到. 可得

Golomb 發(fā)現(xiàn)不變量的歷史背景還與他在上世紀(jì)五十年代后期在噴氣推進(jìn)實(shí)驗(yàn)室(Jet Propulsion Laboratory, JPL) 的工作經(jīng)歷密切相關(guān). 這一時(shí)期, Golomb 和他的同事們?cè)谛请H測(cè)距系統(tǒng)設(shè)計(jì)方面做了一系列前沿性工作[29]. 星際測(cè)距要求所使用的偽隨機(jī)序列具有很大的周期且便于實(shí)現(xiàn)測(cè)距. Golomb[28]建議對(duì)周期兩兩互素的分量序列進(jìn)行非線性布爾組合, 用以生成周期為分量序列周期之積的長(zhǎng)周期組合序列. Easterling[373]按這一建議建立了布爾組合運(yùn)作模式. 最終Golomb 和他的同事們實(shí)現(xiàn)了地球到金星的測(cè)距[373–376].

在Golomb 和他的同事們的上述工作中, 為了實(shí)現(xiàn)測(cè)距, 需要把分量序列從組合序列中區(qū)分出來, 這可通過計(jì)算組合序列和分量序列的互相關(guān)值來實(shí)現(xiàn)[29]. 這就解釋了(7)式中Golomb 為什么要用一個(gè)非線性布爾函數(shù)f和一個(gè)線性函數(shù)α·X進(jìn)行疊加的工程背景. 在工程實(shí)踐中, 每個(gè)分量序列對(duì)應(yīng)于某個(gè)變?cè)獂i, 這相當(dāng)于只考慮了α重量為1 時(shí)的情形. 事實(shí)上, 考慮wt(α)≥2 時(shí)的情形對(duì)測(cè)距而言也無必要.為了區(qū)分分量序列和組合序列, 需要它們的互相關(guān)值盡可能大. 這和肖國(guó)鎮(zhèn)[40]提出的1 階線性統(tǒng)計(jì)獨(dú)立(1 階情形) 和Siegenthaler[39]提出的相關(guān)免疫性(1 階情形) 對(duì)函數(shù)f的頻譜的要求是“相反的”. 在文獻(xiàn)[41, Section V] 中, 稱這兩個(gè)方面的問題是“對(duì)偶的(dual)”.

肖國(guó)鎮(zhèn)和Massey 于1988 年發(fā)表在TIT 上的論文[41]是在1985 年8 月投稿, 1986 年6 月定稿.在論文定稿之前, Golomb 已和肖國(guó)鎮(zhèn)、Massey 進(jìn)行過深入的交流, 比較正式的一次交流反映在1986 年3 月Golomb 給他們的私人通信中[377](文獻(xiàn)[41] 的引用文獻(xiàn)[5]). 他們交流的結(jié)果體現(xiàn)在文獻(xiàn)[41] 第V部分的評(píng)注中.

結(jié)合文獻(xiàn)[41, Section V] 中的評(píng)注和我們前面的討論, 可以作如下總結(jié):

(1) Golomb 定義的不變量是一個(gè)概念, 而Xiao-Massey 定理是一個(gè)命題.

(2) Golomb 定義的不變量本質(zhì)上是刻畫了某種群不變關(guān)系下所劃分的等價(jià)類中布爾函數(shù)的頻譜特征(具有排序后的不變性), 它和相關(guān)免疫是兩個(gè)不同的概念.

(3) 相關(guān)免疫函數(shù)的定義是從概率統(tǒng)計(jì)的角度被描述的. Xiao-Massey 定理從頻譜觀點(diǎn)把一個(gè)概率統(tǒng)計(jì)概念等價(jià)地轉(zhuǎn)化為代數(shù)方式的描述, 二者之間的“橋梁” 在文獻(xiàn)[41] 中是通過“Xiao-Massey引理” 建立起來的. Golomb 所定義的不變量只是一個(gè)與Walsh 變換相關(guān)的純粹代數(shù)概念.

(4) Golomb 給出的計(jì)算不變量的方法(算法)本質(zhì)上是一種頻譜計(jì)算, 后人借助不變量這個(gè)概念去重新闡述Xiao-Massey 定理這個(gè)命題是一種“后知后覺”.

(5) Golomb 和他的同事們?cè)贘PL 所做的測(cè)距方面的工作對(duì)組合函數(shù)的要求與1 階相關(guān)免疫函數(shù)對(duì)組合函數(shù)的要求恰恰相反. 前者要求經(jīng)過組合函數(shù)所生成的非線性序列與每一LFSR 序列高度相關(guān), 而后者要求二者之間的相關(guān)值為0[29,41,378]. 由于時(shí)代背景和工程背景不同, Golomb 并沒有刻畫出1 階相關(guān)免疫函數(shù)的頻譜特征, 高階不變量也只是停留在概念層面.

4 結(jié)束語

上世紀(jì)五十年代以來, 信息論領(lǐng)域涌現(xiàn)了許多了不起的人物. 他們用數(shù)學(xué)的觀點(diǎn)看待工程中的問題,從工程實(shí)踐中抽象出數(shù)學(xué)問題, 又把數(shù)學(xué)理論巧妙地應(yīng)用于工程實(shí)踐. 他們對(duì)世界嚴(yán)肅而嚴(yán)謹(jǐn)?shù)乃伎? 把我們對(duì)世界的認(rèn)知帶入高度理性的層面. 本文中提到的肖國(guó)鎮(zhèn)、Massey、Golomb 三位學(xué)者無疑都是他們那個(gè)時(shí)代的杰出代表.

今年正值肖國(guó)鎮(zhèn)教授逝世六周年, 以此文作為紀(jì)念. 同時(shí), 也以此文紀(jì)念肖國(guó)鎮(zhèn)教授和James L.Massey、Solomon W. Golomb 之間的友誼.

致謝

作者就本文第3 節(jié)的觀點(diǎn)和法國(guó)巴黎第8 大學(xué)的學(xué)者Claude Carlet 進(jìn)行了有價(jià)值的學(xué)術(shù)討論.