張衛(wèi)國

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

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

第二次世界大戰(zhàn)后, 數(shù)字電路技術(shù)在工程中逐漸被廣泛應(yīng)用, 流密碼的發(fā)展也逐漸從機(jī)械密碼時代過渡到數(shù)字電路密碼時代. 上世紀(jì)五十年代至七十年代, 是移位寄存器序列(shift register sequence) 理論蓬勃發(fā)展的時期, 有關(guān)線性移位寄存器(linear feedback shift register, LFSR) 的理論成果逐漸成熟[1–3].同一時期, 編碼理論和技術(shù)也得到較為充分的發(fā)展[4,5]. 在上世紀(jì)六十年代后期, Berlekamp[4,6]在BCH碼的譯碼方案中給出一種從校驗(yàn)子找出錯位多項(xiàng)式的迭代算法, 這種算法的實(shí)質(zhì)是運(yùn)用歸納法確定一系列LFSR 的結(jié)構(gòu). Massey[7]也獨(dú)立地給出同一算法,解決了LFSR 的綜合問題. 所謂LFSR 的綜合,是指對一個給定的二元周期序列, 找出產(chǎn)生該序列的最少級數(shù)的LFSR. 后人稱這一算法為Berlekamp-Massey算法(BM 算法). BM 算法的提出, 對流密碼的發(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ù)雜度) 的序列的生成. 遺憾的是, 時至今日對這種生成序列的方式的研究仍不成熟. BM 算法問世之后, 人們對生成“復(fù)雜” (不止是高線性復(fù)雜度) 序列的流密碼系統(tǒng)的研究走向了另一方向.

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

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

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

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

上面討論的分別征服攻擊只考慮了單個LFSR 所產(chǎn)生的序列與密文序列的相關(guān)性, 這一攻擊當(dāng)然可以進(jìn)一步考慮多個LFSR 的輸出序列進(jìn)行疊加(模2 加法運(yùn)算) 后所得到的序列與密文序列的相關(guān)性. 這就引出Siegenthaler 對t階相關(guān)免疫函數(shù)的定義[39]. 設(shè)X=(x1,x2,··· ,xn), 其中x1,x2,··· ,xn是n個獨(dú)立同分布二元隨機(jī)變量. 設(shè)Bn是所有n元布爾函數(shù)的集合. 若f(X)∈Bn和x1,x2,··· ,xn中的任意t個變量都是統(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 對相關(guān)免疫性的定義看起來嚴(yán)謹(jǐn)清晰, 但對函數(shù)設(shè)計(jì)和分析的指導(dǎo)意義較弱.

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

線性統(tǒng)計(jì)獨(dú)立概念的提出動機(jī)是為了研究圖1 中流密碼系統(tǒng)產(chǎn)生的密文序列與系統(tǒng)中一個或多個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個隨機(jī)變元xi1,xi2,··· ,xit, 1≤i1＜i2＜···＜it ≤n, 恒有

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

下面的定理由肖國鎮(zhèn)于1985 年6 月在第23 屆ISIT 國際會議的報(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)對Fn2中滿足1≤wt(α)≤t的α, 都有Sf(α)=0, 其中Sf(α) 是f在點(diǎn)α的Fourier 變換, 定義為:

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

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

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

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

設(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. 同時, 注意到f是平衡布爾函數(shù)當(dāng)且僅當(dāng)Wf(0n)=0. 因而, Xiao-Massey 定理如今也常被描述成如下定理.

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

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

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

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

從上世紀(jì)八十年代中期至今, Xiao-Massey 定理被國內(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 定理的中國臺灣學(xué)者, 1988 年他在文獻(xiàn)[50] 中用頻譜方法研究了非線性移位寄存器及其線性等價系統(tǒng)問題. 更多引用Xiao-Massey 定理的文獻(xiàn)可參閱[51—194].

(2) Xiao-Massey 定理在布爾函數(shù)多密碼指標(biāo)折中優(yōu)化中具有重要價值, 在構(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 定理對密碼分析的價值.

1989 年, Meier 和Staffelbach[38]在Journal of Cryptology 發(fā)表論文“Fast correlation attacks on certain stream ciphers”, 提出針對流密碼系統(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]定義了對線性分析(m,n)-免疫的概念, 基于Xiao-Massey 引理給出分組密碼系統(tǒng)對線性分析(m,n)-免疫的充要條件.更多相關(guān)引用文獻(xiàn)可參閱[309—330].

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

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

馮登國[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)一步刻畫, 是對Xiao-Massey 定理的發(fā)展.

Lacharme[341,342]從布爾函數(shù)角度研究了真隨機(jī)數(shù)生成器的校正器的分析和設(shè)計(jì)問題, 給出t階校正器的頻譜特征. 對單輸出布爾函數(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]、抗病毒行為檢測策略模型[346]等.

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

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

“相關(guān)免疫函數(shù)的頻譜化特征定理” 這一研究成果在國際上公認(rèn)首創(chuàng)屬于肖國鎮(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]. 受這一錯誤觀點(diǎn)的影響,在2021 年出版的專著“Boolean Functions for Cryptography and Coding Theory”[349]中又把“Xiao-Massey 定理” 誤稱為“Golomb-Xiao-Massey characterization”. 這一研究成果的歸屬問題在肖國鎮(zhèn)、Massey、Golomb 三位學(xué)者都在世時沒有爭議, 近年來在這一問題上出現(xiàn)的錯誤觀點(diǎn)既不符合學(xué)術(shù)事實(shí), 也不符合三位學(xué)者生前達(dá)成的共識.

每一個概念或定理的產(chǎn)生, 都不是憑空而來的, 都有其特定的歷史背景. 下面我們通過梳理Golomb提出“不變量” 的歷史背景, 揭示其概念本質(zhì). 這一概念本質(zhì)上描述了在特定等價關(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). 分析問題是對確定的開關(guān)電路分析其性質(zhì)功能, 綜合問題是尋找具有特定性質(zhì)功能的電路. 前者是相對容易的問題, 而后者是非常困難的問題[353–356]. 這一時期, 一系列開關(guān)電路的分析和綜合問題被轉(zhuǎn)化為數(shù)學(xué)問題進(jìn)行研究[357–367]. 到了上世紀(jì)七十年代中期, 由開關(guān)電路的綜合問題逐漸發(fā)展出電子設(shè)計(jì)自動化(electronic design automation,EDA) 技術(shù). 綜合問題的困難之處在于如何以最低的代價實(shí)現(xiàn)電路功能, 同時考慮電路的功耗、速度等因素. 早期的綜合問題主要考慮如何用相對簡單的方式實(shí)現(xiàn)具有特定功能的電路. 1949 年, Shannon 又進(jìn)一步發(fā)展了開關(guān)電路綜合問題的理論和方法[353]. Shannon 指出變元個數(shù)相對較大的n元布爾函數(shù)絕大多數(shù)實(shí)現(xiàn)起來都是相當(dāng)復(fù)雜的. 另一方面, 現(xiàn)實(shí)中使用的n個變元的電路都是非常簡單的. 對產(chǎn)生這個“矛盾” 的原因, Shannon 是這樣解釋的: 電路設(shè)計(jì)實(shí)踐中使用的布爾函數(shù)不是隨機(jī)選擇的. 為了有助于在實(shí)現(xiàn)電路功能時能選擇到結(jié)構(gòu)相對簡單的布爾函數(shù), Shannon 給出兩種函數(shù)關(guān)系(functional relation), 一種叫函數(shù)可分關(guān)系(functional separability),另一種是特殊情形下的群不變關(guān)系(group invariance). 對前一種函數(shù)關(guān)系, 這里不作介紹. 后一種函數(shù)關(guān)系是指函數(shù)f ∈Bn滿足如下群不變性質(zhì): 對任意xi,ai ∈F2,0≤i ≤n, 總有

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

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

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

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

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

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

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

我們從頻譜角度分析一下, 對同一等價類Ei中的布爾函數(shù)而言, 為什么它們會有相同的t階不變量?在Golomb 給出的這一等價關(guān)系下,f ∈Bn所屬等價類中的任一函數(shù)g ∈Bn和f都是擴(kuò)展仿射等價的(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). 這一時期, Golomb 和他的同事們在星際測距系統(tǒng)設(shè)計(jì)方面做了一系列前沿性工作[29]. 星際測距要求所使用的偽隨機(jī)序列具有很大的周期且便于實(shí)現(xiàn)測距. Golomb[28]建議對周期兩兩互素的分量序列進(jìn)行非線性布爾組合, 用以生成周期為分量序列周期之積的長周期組合序列. Easterling[373]按這一建議建立了布爾組合運(yùn)作模式. 最終Golomb 和他的同事們實(shí)現(xiàn)了地球到金星的測距[373–376].

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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

致謝

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