密碼格中行列式的若干定義及性質(zhì)比較研究

楊 軍，李 慶

(西南民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，四川 成都 610041)

量子理論用于密碼通信，將引起密碼技術(shù)的一場(chǎng)變革；受量子計(jì)算機(jī)攻擊，現(xiàn)有的公鑰密碼體制正面臨巨大挑戰(zhàn).美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院(NIST)和國(guó)際互聯(lián)網(wǎng)工程任務(wù)組(IETF)[1]目前把“寶”壓在制定“后量子時(shí)代密碼系統(tǒng)的新標(biāo)準(zhǔn)”上，而量子通信則是我國(guó)面向2030 年的重大科技項(xiàng)目[2].但是，后量子時(shí)代的密碼與量子計(jì)算的能力極限密切相關(guān)，其安全性目前還缺乏足夠的理論保證. 近年來，基于格、編碼和散列的密碼系統(tǒng)、多變?cè)艽a學(xué)、用誤差學(xué)習(xí)的環(huán)及群論密碼學(xué)等被公認(rèn)為最有前景的候選方案[3－5].

與量子密碼相比具有成本和兼容性優(yōu)勢(shì)的“抗量子計(jì)算攻擊的新型密碼”在十余年前密碼學(xué)界已著手研究.2002 至2018 年，加州大學(xué)Micciancio 和麻省理工學(xué)院Goldwasser[6]、特拉維夫大學(xué)Regev[7]、印度技術(shù)研究所Gupta[8]、清華大學(xué)王小云[9]、北京大學(xué)Wang[10]及武漢大學(xué)張煥國(guó)等人[11－12]從密碼視角較系統(tǒng)地研究了格問題的復(fù)雜性、基于格的密碼、基于格的認(rèn)證密鑰交換、格密碼的數(shù)學(xué)基礎(chǔ)、基于格的小整數(shù)解密鑰交換問題及抗量子計(jì)算密碼.

本文研究?jī)?nèi)容之一是證明比文獻(xiàn)[6]中斷言“對(duì)于滿秩整數(shù)格Λ ＝L (B)，B 是一個(gè)格基，其行列式det (Λ)＝det (B)是整數(shù).”稍強(qiáng)的一個(gè)結(jié)果.文獻(xiàn)[6]及[9，11]分別斷言:對(duì)于整數(shù)格及滿秩格Λ ＝L (B)，其行列式det (Λ)是一個(gè)格不變量，即不依賴于用于計(jì)算它的基B 的選擇.主研內(nèi)容之二是把上述結(jié)果推廣到任何實(shí)數(shù)格上.研究?jī)?nèi)容之三是指出并改進(jìn)若干文獻(xiàn)中幾個(gè)相關(guān)概念的描述小失誤案例.

1 格的預(yù)備知識(shí)

定義1[6]:令?m為m 維Euclid 空間.?m中的一個(gè)格是?m中n (≤m)個(gè)線性無關(guān)向量b1，…，bn的所有整數(shù)線性組合構(gòu)成的集合

整數(shù)n 及m 分別稱為此格的秩及維；當(dāng)m ＝n 時(shí)，稱其為滿秩格.向量組b1，…，bn序列稱為一個(gè)(格)基，且按慣例把它表示成一個(gè)基向量作為列的矩陣(簡(jiǎn)稱基陣)

利用矩陣乘法，(1)式可被改寫成另一更緊致的形式

其中，格向量Bx 是通常的矩陣－向量乘法.在全文，格點(diǎn)(即格向量Bx)按慣例均用列向量表示，而AT表示矩陣A 的轉(zhuǎn)置矩陣.

在(3)式中，我們特令B ＝In(n 階單位矩陣)，可得全整數(shù)格.當(dāng)基陣B∈?m×n是整數(shù)矩陣，?n的子格L B( )稱為整數(shù)格.

2 格行列式的若干定義及性質(zhì)的比較

Micciancio 和Goldwasser[6]提出了格行列式的原始定義和一個(gè)具體計(jì)算公式.

證明:一方面，因Λ 為滿秩格，故B 為方陣.再據(jù)(4)式及行列式的乘法定理，我們有

另一方面，又因Λ 為整數(shù)格，故B 為整數(shù)方陣；再據(jù)方陣的行列式定義，知:.另因B 是基陣，故.最后，將以上兩個(gè)結(jié)果代入(5)式，得到

我們證明過程的“一方面”同時(shí)也解釋了文[7，11]直接給出滿秩格的行列式定義的來歷和合理性.

注2:值得注意的是，定理1 中的“滿秩”雖不是必要條件，但也不是多余條件:若去掉“滿秩”，則格行列式不必為整數(shù)(甚至不是有理數(shù)). 我們構(gòu)造反例如下. 由整數(shù)基陣確定的整數(shù)格＝的秩n ＝1 <2 ＝維m，故L ( B)是非滿秩的.由(4)式，此時(shí)我們有

文獻(xiàn)[6]及[7，9]分別斷言:對(duì)于整數(shù)格及滿秩格Λ ＝，其行列式是一個(gè)格不變量.在前人工作的基礎(chǔ)上，我們把上述兩種情形下的結(jié)果統(tǒng)一推廣到任何實(shí)數(shù)格上.

定理2: ?m中任何一格Λ 的行列式是一個(gè)格不變量，即不依賴于用于計(jì)算它的基的選擇.

證明:令B，B′∈?m×n是Λ 的任何兩個(gè)等價(jià)基，即

根據(jù)(4)式，需證

引理1:幺模矩陣U∈?n×n(即，行列式＝ ±1 的整數(shù)矩陣)的逆陣也是幺模矩陣.

又因

引理2:格Λ 的兩個(gè)基B，B′∈?m×n等價(jià)的充要條件是存在一個(gè)幺模矩陣U∈?n×n，使得B′＝BU.

( ?) 設(shè)格Λ 的兩個(gè)基B 與B′是等價(jià)的.依基陣的按列分塊描述(2)式，令

把(10)式代入(11)式，利用矩陣乘法的結(jié)合律，得到

同時(shí)，因B 構(gòu)成? 上的線性空間span (B) ＝{ Bx:x∈?n}的一個(gè)基，利用同一線性空間的兩個(gè)基的過渡陣的唯一性[13]，從(12)式我們得到UV ＝In.兩端同取行列式，可得

由引理2 的必要性，存在幺模矩陣U∈?n×n，使得B′＝BU.于是，

最后，附帶指出并改進(jìn)若干文獻(xiàn)中幾個(gè)相關(guān)概念的描述小失誤.

注3:文獻(xiàn)[6]斷言:任何n 個(gè)線性無關(guān)的格向量的集合B′∈是作為向量空間的的一個(gè)基.我們認(rèn)為，鑒于∈與?是一般不能互換的邏輯關(guān)系(舉一可換特例:若集合A ＝x ∪ x{ }，則x ∈A 且x ?A.)，B′∈須改正為B′?

注4:文獻(xiàn)[8]定義4:由一個(gè)基陣B ∈?m×n生成的格L 被定義成， 其中Ba 是通常的矩陣－ 向量乘法. 我們認(rèn)為，集合與矩陣的記號(hào)不容混淆，上式與(3)式相比，必須改為＝

注5:文獻(xiàn)[11]斷言:(滿秩格的)行列式的值依賴于基的選擇，且與?n中格點(diǎn)密度的逆幾何相關(guān).翻譯應(yīng)改正為:(滿秩格的)行列式的值與基的選擇無關(guān)，且它在幾何上對(duì)應(yīng)于?n中格點(diǎn)的密度的逆.

注6:文獻(xiàn)[11 －12，14]定義(q 模格):給定正整數(shù)q，m，n 及矩陣可以得到一個(gè)由A 的行向量生成的q 模格:對(duì)應(yīng)于A 的行向量生成的編碼.我們認(rèn)為，兩部分均應(yīng)改為“由A 的列向量生成”或“由AT的行向量生成”.

注7:文獻(xiàn)[10]提出的“基于小整數(shù)解問題的格密鑰交換協(xié)議”關(guān)鍵應(yīng)用了下面的所謂“結(jié)合性”:對(duì)于所有(列)向量x ，y ∈?m， 恒有等式

成立，其中?是在q 模格中用于引入隨機(jī)擾動(dòng)向量的一個(gè)記號(hào)，使得yT?A 及A ?x 均是m 維的行向量及列向量； ( yT?A) · x 是 ( yT?A)與x 的內(nèi)積.此性質(zhì)與經(jīng)典DH 密鑰交換協(xié)議中的相似.

剖析如下.盡管(14)式本身從理論上可證，且用仿真軟件驗(yàn)證成功，但以上整體描述有三點(diǎn)失誤或不妥.第一，根據(jù)文獻(xiàn)[15 －16]，m 維Euclid 空間?m中兩個(gè)列向量x 與y(標(biāo)準(zhǔn))內(nèi)積定義為xTy，記為x · y 或?x ，y?；兩個(gè)行向量x 與y(標(biāo)準(zhǔn))內(nèi)積類似定義，但行向量與列向量之間無內(nèi)積定義. 因此，(14)式中的· x 是行向量與列向量x 的矩陣乘法運(yùn)算結(jié)果.

第二，用抽象代數(shù)語(yǔ)言講[17]，命S 是任何一個(gè)集合，下列映射

第三，在經(jīng)典Diffie－Hellman 密鑰交換協(xié)議中成立，原因是在生成元為g 的循環(huán)子群中，非負(fù)整數(shù)集對(duì)于普通乘法運(yùn)算的交換律演繹出群元素方冪的指數(shù)律.結(jié)合律與交換律是兩個(gè)不同的、獨(dú)立的算律，不能混為一談.揭示原作者的真正含義:二者的來歷不一，但在下文可見它們?cè)诿荑€交換協(xié)議中扮演的作用恰是相似的.

3 結(jié)論與展望

本文的工作有三.首先在前人工作的基礎(chǔ)上，證明了“滿秩整數(shù)格的行列式必為正整數(shù)”的較強(qiáng)結(jié)果(定理1).其次給出了“實(shí)數(shù)格的行列式是一個(gè)與基選擇無關(guān)的格不變量”的完整證明(定理2).最后指出若干國(guó)內(nèi)外信息安全專業(yè)流行教材及文獻(xiàn)中看似沖突，實(shí)則各有不足之處，并給出具體改進(jìn)建議.

盡管當(dāng)前格密碼學(xué)研究主要應(yīng)用滿秩格，但定理2 不僅本身具有一定的純粹數(shù)學(xué)意義，而且對(duì)于未來抗量子計(jì)算密碼學(xué)研究提供了一種潛在而更廣泛的新視角.事實(shí)上，Wang 等人[10]已經(jīng)率先研究:在秩n?維m 情形下基于秩虧損的q 模格，首次建立了一類高效實(shí)施的密鑰交換協(xié)議，且已提出抵抗“私鑰對(duì)攻擊”的形式化安全證明.但Mao 等人[14]已對(duì)其展開“共享密鑰攻擊”.對(duì)其展開“單方私鑰攻擊”是本文的未來工作之一.