基于矩陣填充問題的五輪零知識身份認(rèn)證方案

王后珍，蔡鑫偉，郭巖，張煥國

（1.武漢大學(xué)國家網(wǎng)絡(luò)安全學(xué)院，湖北 武漢 430072；2.密碼科學(xué)技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，北京 100878）

1 引言

Goldwasser、Micali 等[1]給出了零知識身份認(rèn)證的定義，其含義是P試圖使V相信其掌握某個(gè)知識，或證明論斷的正確性，但在該過程中V或第三方無法獲得任何與知識相關(guān)的內(nèi)容。整個(gè)交互過程的關(guān)鍵即如何做到使V無法獲取與知識本身相關(guān)的任何信息。自從身份認(rèn)證協(xié)議概念提出后，先后涌現(xiàn)了大批零知識身份認(rèn)證協(xié)議，其中最具代表性協(xié)議包括FS 協(xié)議[2]、GQ 協(xié)議[3]以及Schnorr 協(xié)議[4]等。它們的安全性主要基于數(shù)論困難問題，如大整數(shù)因子分解問題（IFP,integer factorization problem）或有限域上的離散對數(shù)問題（DLP,discrete logarithm problem）。

Shor[5]在1994年設(shè)計(jì)了一種能夠以多項(xiàng)式時(shí)間復(fù)雜度求解IFP和DLP的量子專用算法，也就是說，一旦造出可實(shí)用的量子計(jì)算機(jī)，基于上述數(shù)學(xué)困難問題設(shè)計(jì)的密碼算法容易遭受攻擊。現(xiàn)今密碼學(xué)領(lǐng)域越來越重視抗量子計(jì)算密碼的研究與探索，而且一些國家或組織正在積極開展抗量子計(jì)算密碼算法的標(biāo)準(zhǔn)化工作[6]。

目前，已有的抗量子身份認(rèn)證密碼方案主要如下。1993 年美密會上，Stern[7]基于Syndrome Decoding 問題構(gòu)造的認(rèn)證密碼方案。后來，文獻(xiàn)[8-9]在Stern 方案的基礎(chǔ)上做了進(jìn)一步的優(yōu)化，減小了Stern 方案的公鑰尺寸，減少了交互過程中的數(shù)據(jù)傳遞量，并提升了協(xié)議的安全性。上述方案均是在有限域F2上設(shè)計(jì)的，而文獻(xiàn)[10]則將上述方案拓展到有限域Fq上（q為素?cái)?shù)）。2001 年亞密會上，Courtois[11]基于矩陣最小秩問題提出零知識認(rèn)證協(xié)議；2011 年美密會上，Sakumoto 和Shirai 等[12]基于MQ 問題成功設(shè)計(jì)出安全實(shí)用的零知識認(rèn)證協(xié)議。其他類似的方案有PKP 協(xié)議[13]、Chen 協(xié)議[14]、CLE 協(xié)議[15]、PPP 協(xié)議[16]、SC 協(xié)議[17]等。上述身份認(rèn)證協(xié)議單輪的欺騙概率主要介于1/2～3/4，因此，工程應(yīng)用中需要通過多輪迭代才能滿足實(shí)際期望的安全性。2019 年，Yang 等[18]基于格上困難問題構(gòu)造了一種欺騙概率可達(dá)到1/poly 的認(rèn)證協(xié)議，不需要多輪迭代。2021 年，文獻(xiàn)[19]借鑒Courtois方案的構(gòu)造方法、基于矩陣填充（MC,matrix completion）問題構(gòu)造了一種新型三輪零知識身份認(rèn)證密碼方案，相較于Courtois 方案，該方案在欺騙概率不變的情況下，減小了密鑰尺寸，并提升了協(xié)議的運(yùn)行效率。本文的主要工作如下。

1) 在文獻(xiàn)[19]中認(rèn)證協(xié)議的基礎(chǔ)上，進(jìn)一步將惡意證明者欺騙成功的概率由2/3 降至1/2，提出了基于低秩MC 問題的五輪零知識身份認(rèn)證方案。

2) 針對新設(shè)計(jì)的五輪零知識身份認(rèn)證協(xié)議，本文給出了其完備性、合理性以及零知識性的詳細(xì)證明，證明了方案的安全性。

3) 最后給出了本文方案同其他現(xiàn)有方案的參數(shù)比較，指出本文方案所具備的優(yōu)勢。

2 預(yù)備知識

這里特別說明，本文的零知識身份認(rèn)證密碼協(xié)議均在有限域Fq上進(jìn)行。其中，q=ph，h為正整數(shù)，p為素?cái)?shù)。

2.1 零知識身份認(rèn)證協(xié)議

在日常生活中經(jīng)常會遇到這樣的問題，一方P希望向另一方V證明他具備某種身份或知道某個(gè)知識，通常習(xí)慣稱P為證明者，稱V為驗(yàn)證者，這是基本的身份認(rèn)證的問題。但為了進(jìn)一步確保方案的安全性，人們希望該過程中V或第三方無法獲得任何與知識相關(guān)的內(nèi)容，也就是平時(shí)所說的零知識身份認(rèn)證方案。

當(dāng)方案分別滿足以下3 個(gè)性質(zhì)時(shí)，通常稱該零知識身份認(rèn)證方案是安全的。

完備性（completeness）。如果陳述為真，那么誠實(shí)的證明者在不違背交互協(xié)議的前提下，總能使誠實(shí)的驗(yàn)證者相信其確實(shí)擁有知識。

合理性（soundness）。如果陳述為假，那么惡意證明者幾乎無法通過身份驗(yàn)證，誠實(shí)的驗(yàn)證者以絕對優(yōu)勢的概率返回拒絕，即惡意證明者成功通過驗(yàn)證的概率是可忽略的。下面給出正式定義。

定義1對任意概率多項(xiàng)式時(shí)間（PPT,probabilistic polynomial time）算法、驗(yàn)證者P以及輸入x，存在提取器δ，如果有

其中，δs為欺騙概率，ε是不可忽略的，則提取器δ可在多項(xiàng)式時(shí)間內(nèi)獲得相應(yīng)有效信息，且通過驗(yàn)證。

對于合理性這一性質(zhì)有進(jìn)一步的延伸，也就是特殊合理性，此處本文也對特殊合理性做簡單說明。特殊合理性是指對于給定的公鑰pk，當(dāng)c1≠c2時(shí)，輸出相同初始信息I的2 個(gè)可接收記錄(I,c1,r1)和(I,c2,r2)是困難的。也就是說，對于任意的多項(xiàng)式時(shí)間敵手，其做出的響應(yīng)只能通過挑戰(zhàn)值中的一個(gè)。下面同樣給出特殊合理性的定義。

定義2如果能夠證明身份認(rèn)證協(xié)議具備特殊合理性，那么對算法A而言，只要是PPT 算法，如下概率便可忽略不計(jì)。

其中，(pk,sk)由密鑰算法生成，Rsp 表示對應(yīng)記錄驗(yàn)證者給出的判斷。

零知識性（zero-knowledge）。當(dāng)證明者真正擁有知識（私鑰）信息時(shí)，誠實(shí)驗(yàn)證者或攻擊者只要遵守協(xié)議運(yùn)行規(guī)則，無論采用什么方法，如何對交互過程中的傳輸數(shù)據(jù)進(jìn)行推導(dǎo)，均不能得到與知識本身相關(guān)的任何有效信息。下面給出對零知識性更規(guī)范定義。

定義3假如存在有效的模擬器U，對于驗(yàn)證者V和證明者P而言，以下二者是計(jì)算上不可區(qū)分的：

1) {P(sk),V(pk)}表示V和P在忠實(shí)執(zhí)行交互后V所得到的知識信息，其中，sk 為私鑰，pk 為公鑰；

2) {U(pk)}表示輸入為公鑰pk、算法U的輸出。則稱該身份識別協(xié)議是誠實(shí)驗(yàn)證者零知識的。

另外需要指出，如果上述二者的分布是相同的，那么稱該協(xié)議滿足完美零知識性。如無特殊說明，本文后續(xù)的協(xié)議均指計(jì)算不可區(qū)分。為方便描述，上述完備性和合理性定義中的陳述均指證明者擁有知識這一斷言。

2.2 相關(guān)NP 困難問題

下面分別簡單描述矩陣最小秩（MR,min rank）問題和矩陣填充問題。

文獻(xiàn)[20]較詳細(xì)地描述了矩陣秩相關(guān)問題求解算法，矩陣最小秩問題就是其中之一，其求解思路是構(gòu)造多變量非線性方程組，然后解方程組。另外，文獻(xiàn)[21]也對MR 問題進(jìn)行了詳細(xì)分析。下面首先給出MR 問題的正式定義。

定義4（最小秩問題）設(shè)M0,M1,…,Mm為有限域Fq上的m×n矩陣，尋找一個(gè)向量使矩陣∑αiM i?M0的秩滿足

與矩陣最小秩問題相似的另一個(gè)數(shù)學(xué)困難問題——矩陣填充是本文重點(diǎn)關(guān)注的。文獻(xiàn)[22-24]給出了矩陣填充問題是NP 困難問題的證明，特別地，低秩矩陣填充問題的可表述如下

定義5（低秩矩陣填充問題）隨機(jī)給定一個(gè)η×n維矩陣A=(aij)∈Fq且A的秩rank(A)=r，假如隨機(jī)去掉矩陣中的m個(gè)元素。現(xiàn)對這m個(gè)空缺位置進(jìn)行賦值，滿足賦值后矩陣A'的秩仍然等于r。

矩陣填充問題屬于NP 完全問題[18]。下節(jié)介紹該問題的求解方法。

2.3 MC 問題的常見求解算法

Harm 證明了MC 問題與MR 問題實(shí)際上是等價(jià)的[22]。這也就意味著最小秩問題的一些求解方法也可用于矩陣填充問題的求解[11]。假如隨機(jī)選取秩為r的η×n維矩陣M∈Fq，參數(shù)ω為常量（2≤ω<3）。此外，定義缺失矩陣元素個(gè)數(shù)參數(shù)m，滿足

那么目前低秩MC 問題常見的求解方法主要有以下幾點(diǎn)。

1) 暴力破解。對缺失的元素進(jìn)行窮舉賦值，其時(shí)間復(fù)雜度為q mrω。

2) 子矩陣求解方法。Coppersmith 等[25]首先提出這種求解方法，文獻(xiàn)[26]進(jìn)一步對該類求解方法進(jìn)行了論證，但只適用于r?n的情形。實(shí)際意義不大。

3) Shamir 和Kipnis[27]提出了r?n情形的另一種不同求解算法。其思想是將矩陣填充問題轉(zhuǎn)化為一個(gè)多變量二次方程組。文獻(xiàn)[28]對這種方法做了進(jìn)一步改進(jìn)，其時(shí)間復(fù)雜度為nO(r)。

4) 2000 年，Goubin 等[28]給出了一種稱之為內(nèi)核攻擊的求解算法。當(dāng)矩陣為方陣（n=η）時(shí)，該算法的時(shí)間復(fù)雜度約為。文獻(xiàn)[29]做了進(jìn)一步改進(jìn)，給出了通用求解算法，其算法的時(shí)間復(fù)雜度為

5) 內(nèi)核攻擊方法是MC 問題的最有效的求解方法。2008 年，F(xiàn)augere 等[30]對Kipnis 和Shamir的方法進(jìn)行了優(yōu)化改進(jìn)，其時(shí)間復(fù)雜度為。需要說明的是，本文構(gòu)造的零知識身份認(rèn)證協(xié)議，其安全參數(shù)規(guī)模（包括有限域、矩陣維數(shù)及秩等）的選取依據(jù)將主要按照這種內(nèi)核攻擊求解算法。

3 基于MC 問題的五輪身份認(rèn)證協(xié)議

本節(jié)給出五輪身份認(rèn)證協(xié)議的具體構(gòu)造。同之前的三輪方案[19]相比，增加了一次驗(yàn)證者和證明者之間的通信，增加的挑戰(zhàn)值k∈(0,q)，因此，單輪攻擊者欺騙概率降低至，顯然，當(dāng)q足夠大時(shí)，欺騙概率約等于1/2。

3.1 協(xié)議構(gòu)造

本文將該方案分為2 個(gè)階段。首先是密鑰生成階段，其次是交互認(rèn)證階段。下面分別對這2 個(gè)階段進(jìn)行詳述。

3.1.1 密鑰生成

選定系統(tǒng)參數(shù)η,n,r,m和Fq。首先，隨機(jī)選擇一個(gè)η×n維矩陣A=(aij)∈Fq，且矩陣A滿足秩rank(A)=r；然后，隨機(jī)從矩陣A中去掉m個(gè)元素，將缺失m個(gè)元素的不完整矩陣記作A?，并用(i1,j1),…,(im,jm)分別表示這m個(gè)元素在矩陣A中的元素位置，ik代表矩陣行，jk代表矩陣列。

綜上所述，該系統(tǒng)的公鑰包含：η,n,r,m,Fq和A?，私鑰為有序序列s，滿足s={s1,…,sm}，其中，sk=aikjk,1≤k≤m。密鑰生成過程即輸入滿足rank(A)=r的矩陣A，進(jìn)行上述操作后，輸出公私鑰對(pk,sk)=((η,n,r,m,A?),s)。

3.1.2 單輪交互方案

證明者隨機(jī)選擇2 個(gè)可逆矩陣P和Q，其中矩陣P和Q分別為η×η、n×n維的方陣，并隨機(jī)選取向量γ∈。證明者機(jī)將公鑰不完整矩陣A?隨機(jī)拆分為 2 個(gè)元素不完整矩陣之和，即滿足等式A?=+，“+”代表相同位置元素相加，這里與三輪身份認(rèn)證協(xié)議不同的是，本文指定元素有缺失的矩陣所有值位置均等于零，方便后續(xù)進(jìn)行驗(yàn)證。這里需要說明的是這種拆法是公開的，據(jù)此拆分方法驗(yàn)證者同樣可以得到殘缺矩陣和。

證明者接下來秘密地將私鑰s隨機(jī)拆成α和β，滿足分量β k=α k+sk,1≤k≤m；隨后將α的m個(gè)元素逐次填充到缺失元素處得到矩陣A1，同理，將γ的m個(gè)元素也填充到得到矩陣A2。為了后續(xù)計(jì)算驗(yàn)證以及參數(shù)傳遞，證明者在本地分別計(jì)算M1和M2。其中，完整矩陣M1將由s的m個(gè)元素依次填充到得到，完整矩陣M2將由元素0依次填充到得到，之后計(jì)算矩陣M，矩陣M=PM1Q+PM2Q，顯然矩陣M1和M2滿足M1+M2=A。

五輪協(xié)議交互過程如圖1 所示。

證明者和驗(yàn)證者共進(jìn)行5 次交互，整個(gè)交互過程及每輪交互中的傳遞參數(shù)的詳細(xì)描述如下。

1) 證明者先計(jì)算矩陣PA1Q和PA2Q，隨后計(jì)算相應(yīng)Hash 值，分別記作c1和c2，對應(yīng)關(guān)系如下。

然后證明者將{c1,c2}發(fā)送給驗(yàn)證者。

2) 驗(yàn)證者從有限域Fq中隨機(jī)選擇一個(gè)值k，并將其發(fā)送給證明者。

3) 證明者計(jì)算矩陣N=PTQ并發(fā)送給驗(yàn)證者，這里矩陣T是通過將γ+kα+ks的元素逐次填充到得到的。

4) 驗(yàn)證者隨機(jī)選擇b∈{0,1}作為挑戰(zhàn)值，并將b傳至證明者。

5) 證明者根據(jù)b值向驗(yàn)證者做出不同的應(yīng)答。

①如果b=0，則證明者將矩陣PA1Q、PM1Q、PM2Q和向量α發(fā)送至驗(yàn)證者，驗(yàn)證者收到后計(jì)算下述Hash 值

驗(yàn)證其與c1是否相等，并計(jì)算

然后驗(yàn)證相加后得到的矩陣PAQ的秩是否等于r。

② 如果b=1，證明者將向量β、矩陣P和矩陣Q發(fā)送給驗(yàn)證者，驗(yàn)證者首先驗(yàn)證P和Q是否為可逆矩陣，然后在本地計(jì)算下述Hash 值

逐次將β的元素填充到的空缺位置得到完整矩陣Y，驗(yàn)證c2和該Hash 值是否相等。

綜上所述，同文獻(xiàn)[19]設(shè)計(jì)的三輪交互協(xié)議相比，多出的一輪交互是驗(yàn)證者選擇k值并將其傳遞給證明者；而證明者收到k后，利用該值計(jì)算一個(gè)矩陣N作為回應(yīng)。k值也是能夠?qū)⑵垓_成功的概率降低到1/2 的關(guān)鍵。同時(shí)在參數(shù)生成時(shí)，五輪方案多了一個(gè)隨機(jī)向量γ，該向量在驗(yàn)證者驗(yàn)證Hash值的時(shí)候起到了掩蓋私鑰的關(guān)鍵作用，從而確保在完成驗(yàn)證時(shí)并沒有泄露私鑰。

3.2 安全性證明

下面討論本文身份認(rèn)證方案的3 個(gè)重要性質(zhì)，即完備性、合理性和零知識性。

3.2.1 完備性

定理1對于誠實(shí)的證明者而言，驗(yàn)證者可以檢驗(yàn)證明者的身份。

證明在證明者和驗(yàn)證者都是誠實(shí)的以及不違背交互協(xié)議的前提下，證明者因?yàn)橹浪借€s和在第二輪交互中驗(yàn)證者所選的k值，很明顯可以在每一輪詢問中計(jì)算出正確的c1和c2值，并返回給驗(yàn)證者相應(yīng)的信息，進(jìn)而證明其身份。即針對任何挑戰(zhàn)值b，證明者做出的應(yīng)答總能滿足以下條件。

1) 當(dāng)b=0時(shí)，有如下等式成立

2) 當(dāng)b=1 時(shí)，有如下等式成立

3)P、Q均為可逆矩陣。

上述矩陣N=PTQ中的T可由γ+kα+ks的元素逐次填充至得到，矩陣1A和Y則分別為逐次將α和β的元素填充到矩陣元素空缺處后得到的完整矩陣。對任意輪次的詢問，驗(yàn)證者都能正確檢驗(yàn)證明者的身份。綜上所述，驗(yàn)證者檢驗(yàn)證明者的概率ε=1，因此，該協(xié)議滿足完備性。證畢。

3.2.2 合理性

為了能夠成功欺騙驗(yàn)證者，惡意證明者P′需要做以下準(zhǔn)備，以應(yīng)對驗(yàn)證者可能發(fā)起的挑戰(zhàn)。同三輪方案不同的是，在傳遞過程中多了一個(gè)k值，如果P′猜到了正確的k值，那么便可以用k值來構(gòu)造相應(yīng)的c1和c2；如果P′未猜中對應(yīng)的k值，那么P′仍然可以猜測b的值來嘗試通過驗(yàn)證。將P′所做的準(zhǔn)備記為{t1,t2}。在t1中，P′猜測收到的挑戰(zhàn)值為b′=0，P′ 隨機(jī)生成秩為r的矩陣A′，故rank(PA′Q)=rank(A′)，即矩陣PA′Q的秩為r，從而正確計(jì)算c1，而c2可以任意選取。綜上所述，P′可以正確回答挑戰(zhàn)b=0；在準(zhǔn)備t2中，P′猜測收到的挑戰(zhàn)值為b′=1，P′隨機(jī)生成可逆矩陣P和Q，以及隨機(jī)選擇向量α*，而c1可以任意選取。由于惡意證明者并不擁有私鑰，因此其無法對2 個(gè)挑戰(zhàn)值均做出正確回應(yīng)。因此，在每輪交互過程中{t1,t2}成功的概率為

這里假設(shè)驗(yàn)證者選取的k值不能為0，否則后續(xù)的驗(yàn)證便沒有任何意義，所以上述等式中k′=k的概率為1/(q?1)。不過即使k值可以取0，當(dāng)q達(dá)到一定閾值時(shí)，k k′=的概率仍然可以達(dá)到約1/2，其結(jié)果是相同的。通常需要將該身份認(rèn)證協(xié)議重復(fù)w次，那么全部欺騙成功的概率為。如果惡意證明者P′可以響應(yīng)驗(yàn)證者所有b值的挑戰(zhàn)，則有如下定理。

定理2假如欺騙者能假冒證明者響應(yīng)所有k值而且能被誠實(shí)驗(yàn)證者相信，則存在多項(xiàng)式時(shí)間概率圖靈機(jī)能以不可忽略的概率，要么可以求解矩陣填充問題以恢復(fù)私鑰，要么可以找到給定哈希函數(shù)的一個(gè)碰撞。

綜上所述，證明者要么找到了一個(gè)給定Hash函數(shù)的碰撞，要么就有

即找到了矩陣填充問題的一個(gè)解。綜上所述，該協(xié)議滿足合理性。證畢。

3.2.3 零知識性

從圖1 可以看出，在驗(yàn)證者和證明者的交互過程中，首先不會造成私鑰s的泄露。當(dāng)挑戰(zhàn)b=0時(shí)，向量α是隨機(jī)的，PM1Q和PM2Q均為隨機(jī)矩陣，其相加后得到的PMQ為秩為r的隨機(jī)矩陣，不能獲得與矩陣M有關(guān)的任何信息，也就不能獲得與私鑰s有關(guān)的任何信息；當(dāng)挑戰(zhàn)b=1時(shí)，傳輸矩陣P和Q是隨機(jī)選取的，向量β也是隨機(jī)的，故并不會造成私鑰s泄露。下面給出下述定理的證明，從而指出協(xié)議滿足零知識性。

定理3在隨機(jī)預(yù)言機(jī)模型下該身份認(rèn)證協(xié)議（圖1）為零知識交互認(rèn)證協(xié)議。

如果想要證明這一點(diǎn)，需要構(gòu)造模擬器U，滿足其輸出結(jié)果與協(xié)議誠實(shí)執(zhí)行后輸出是計(jì)算不可區(qū)分的。下面設(shè)計(jì)一個(gè)模擬器U來獲取與真實(shí)文本計(jì)算不可區(qū)分的模擬文本，從而證明本文協(xié)議的零知識性。

證明假如模擬器U可以跟驗(yàn)證者進(jìn)行通信。

1)U隨機(jī)選取一個(gè)b′,b′∈{0,1}。

2)U隨機(jī)選取可逆矩陣P、Q以及向量α和γ，U逐次將α和γ的元素填充到Ai?得到完整矩陣,這里i∈{1,2}，且分別計(jì)算PAiQ。若b′=0，隨機(jī)選擇秩為r的矩陣A′，將其拆分為M1+M2，M=PM1Q+PM2Q，計(jì)算c1=H(α,M,PA1Q,PA2Q)，任取c2即可；如果b′=1，則隨機(jī)選擇向量σ來代替私鑰s，并計(jì)算c2=H(α+σ,P,Q,A2)，任取c1即可。

3)U隨機(jī)選擇一個(gè)非零值k∈Fq，并計(jì)算矩陣PTQ。若b=0，矩陣T可通過計(jì)算將PA2Q+kPM1Q得到，這里A2由將γ+kα的元素逐次填充到得到；如果b=1，矩陣T可通過將γ+kα+kσ的元素逐次填充到得到。

4) 模擬器U隨機(jī)選擇一個(gè)b∈{0,1}，若b≠b′，則直接返回步驟1)重新執(zhí)行；若b=b′，則記錄該輪交互過程。若b=b′=0，則U返回的信息{c1,c2,k,N,α,A′,PA1Q,PM1Q,PM2Q}是與真實(shí)值是計(jì)算不可區(qū)分的；若b=b′=1，則模擬器U返回的{c1,c2,k,N,P,Q,α+σ} 是與真實(shí)文本計(jì)算不可區(qū)分的。由于模擬器U可以同驗(yàn)證者進(jìn)行任意次數(shù)的通信，因此模擬器可以重啟整個(gè)認(rèn)證協(xié)議直到猜對b值為止。

綜上所述，該協(xié)議滿足零知識性。

4 性能分析及方案比較

對于本文設(shè)計(jì)的五輪零知識身份認(rèn)證方案，其安全性基于矩陣填充問題，所以根據(jù)2.3 節(jié)中的描述可知，當(dāng)選取11×11 維的矩陣時(shí)，本文五輪身份認(rèn)證協(xié)議具有80 bit 以上安全性，可以滿足目前實(shí)際應(yīng)用需求。因此本文身份認(rèn)證方案在實(shí)際應(yīng)用中推薦矩陣參數(shù)為有限域 F65521上的11 維方陣。

交互過程的前四輪較為簡單，可以看出傳遞的參數(shù)為2 個(gè)Hash 值以及k值和b值（其中k∈Fq，b∈{0,1}），以及矩陣N，所以只需要傳遞(2×160 +lbq+ηnlbq+1)bit，其中q為有限域的特征數(shù)。同樣，這里為了方便同其他方案做比較，故用于計(jì)算的Hash 值的長度為160 bit。

由上節(jié)中協(xié)議交互過程易知，當(dāng)b=0時(shí)，傳遞的數(shù)據(jù)為向量α以及其他3 個(gè)維數(shù)為η×n的矩陣，向量α有m個(gè)元素，共計(jì)為(3ηnlbq+mlbq)bit；當(dāng)b=1時(shí)，需傳遞矩陣P、Q以及向量β，共計(jì)(η2lbq+n2lbq+mlbq) bit，這里m為矩陣中缺失元素的個(gè)數(shù)。綜上所述，整個(gè)交互過程所需要的比特?cái)?shù)平均為

3.2.2 節(jié)中分析過，在q達(dá)到一定閾值時(shí)，單輪交互過程中的欺騙成功概率為1/2，所以如果想要達(dá)到10?6的安全性實(shí)際需求，通常至少需要交互20 輪以上。

表1 列舉了80 bit 安全性水平下，本文方案與其他方案的比較結(jié)果，其中MC（五輪）代表本文所提方案。很顯然，本文方案和MC（三輪）方案的公鑰尺寸較小。通過比較可得，本文方案在公私鑰以及參數(shù)尺寸并未發(fā)生變化的前提下，通過增加一輪交互，降低惡意證明者成功通過驗(yàn)證者身份認(rèn)證的概率至1/2。同時(shí)單輪方案的通信開銷雖然由于方案設(shè)計(jì)改變驗(yàn)證參數(shù)導(dǎo)致有所增加，但由于欺騙成功概率的降低，使達(dá)到相同安全性時(shí)交互輪次降低，故本文設(shè)計(jì)的五輪交互身份認(rèn)證方案與MC（三輪）方案相比，總的通信開銷相差不大，但進(jìn)一步提高了協(xié)議的安全性。

表1 參數(shù)比較

本文對幾種典型的身份認(rèn)證方案進(jìn)行了實(shí)驗(yàn)比較，實(shí)驗(yàn)結(jié)果如表2 所示，本文方案實(shí)現(xiàn)效率比Stern 方案[7]和文獻(xiàn)[19]方案要高，僅需4.6 ms。同時(shí)也不難發(fā)現(xiàn)，由于本文身份認(rèn)證協(xié)議需要執(zhí)行多輪，相較于基于數(shù)論困難問題設(shè)計(jì)的1 024 bit GQ 方案[3]和512 bit 的Schnorr 方案[4]，其實(shí)現(xiàn)效率略低一些，但在實(shí)際工程應(yīng)用中仍然在可接受的范圍，此外本文方案還具有抗量子計(jì)算攻擊的優(yōu)勢。

表2 實(shí)現(xiàn)效率比較

5 結(jié)束語

本文基于（低秩）矩陣填充問題提出了一種五輪身份認(rèn)證方案，相比已有的三輪方案，本文所提方案將單輪交互方案的欺騙成功概率從2/3 降低到1/2，并給出了欺騙概率的詳細(xì)分析及嚴(yán)格安全性證明。以10?6安全性為例，五輪方案只需要重復(fù)執(zhí)行20 次，而三輪方案需要執(zhí)行35 次。所提身份認(rèn)證方案具有很好的抗量子計(jì)算攻擊潛力。而且基于本文提出身份認(rèn)證方案，通過Fiat-Shamir密碼轉(zhuǎn)換技術(shù)，還可得到具有抗量子計(jì)算性質(zhì)的數(shù)字簽名方案[31-32]。

另外，能否在本文身份認(rèn)證協(xié)議的基礎(chǔ)上，優(yōu)化參數(shù)降低通信開銷，從而進(jìn)一步提高協(xié)議的執(zhí)行效率，值得進(jìn)一步研究。