【非交互式零知識證明】（下）

1.交互式零知識證明（續(xù)）

交互式零知識證明的一般模型如下：

（1）證明者和驗(yàn)證者共享一個公共輸入，證明者可能擁有某個秘密輸入；
（2）如果驗(yàn)證者認(rèn)可證明者的響應(yīng)，則輸出Accept，否則輸出Reject。
經(jīng)典交互式零知識證明除了應(yīng)用在NP問題中，還可以應(yīng)用在身份鑒別協(xié)議和Sigma協(xié)議簇中。

1.身份鑒別協(xié)議

在一個安全的身份認(rèn)證協(xié)議中，要保證用戶身份識別的安全性，身份鑒別協(xié)議至少要滿足以下條件：
1）證明者P能夠向驗(yàn)證者V證明他的確是P（P向V證明自己有P的私鑰）。
2）在證明者P向驗(yàn)證者V證明他的身份后，驗(yàn)證者V沒有獲得任何有用的信息（V不能模仿P向第三方證明他是P ）。
下面介紹三種經(jīng)典的身份鑒別協(xié)議：

1）Feige-Fiat-Shamir身份鑒別協(xié)議

☆簡化版本

過程圖如下：

①系統(tǒng)初始化

首先信任中心TA選擇并公布一個RSA型模數(shù)n=p·q，并對素數(shù)p和q保密，然后對于參與者，每一個參與者P選擇一個與n互素的秘密值s，其中1≤s≤n-1，并計算v=s²(mod n)，并向TA注冊v為其公鑰。

②鑒別協(xié)議流程

1）證明者選擇一個隨機(jī)數(shù)r，1≤r≤n-1，計算并發(fā)送x=r²(mod n)給V。

2）驗(yàn)證者隨機(jī)選擇一個比特值α∈_R{0,1}，并將α發(fā)送給證明者。

3）證明者根據(jù)α做出不同的響應(yīng)：

若α=0，令y=r;若α=1，令y=r·s(mod n)。

4）驗(yàn)證者驗(yàn)證等式y(tǒng)²=x·v^α(mod n)。如果等式不成立或者y=0，驗(yàn)證者不接受證明。否則，進(jìn)行下一輪證明。驗(yàn)證者執(zhí)行上述證明過程t輪后，且均未拒絕，則驗(yàn)證者接受證明者的證明，即相信它的身份（很簡單，可以在紙上自己推一下）。

性質(zhì)分析

1.完備性：如果證明者知道秘密值s，他對于不同的α都可以做出正確的響應(yīng)。顯然，誠實(shí)驗(yàn)證者接收的概率為1.

2.可靠性：如果證明者不知道秘密值s，那么他只能夠以1/2的概率欺騙驗(yàn)證者。執(zhí)行t輪后，欺騙概率下降到2^-t.

3.零知識性：協(xié)議交互過程中泄露的信息有：x=r²(mod n),y=r或y=r·s(mod n)，即(x,y)。模擬器的模擬方式：隨機(jī)選擇y，并令x=y²（當(dāng)α=0時）或x=y²/v(當(dāng)α=1時)。模擬器產(chǎn)生的(x,y)和真實(shí)交互的(x,y)是計算不可區(qū)分的。

這里的計算不可區(qū)分性這個概念不是很好懂，我查閱了很多資料，我理解的計算不可區(qū)分和統(tǒng)計不可區(qū)分大致就是：如果挑戰(zhàn)者的能力是無限的，無限能力的挑戰(zhàn)者都不能挑戰(zhàn)成功那么他就是統(tǒng)計不可區(qū)分；如果挑戰(zhàn)者的能力是多項(xiàng)式的，多項(xiàng)式能力的挑戰(zhàn)者不能挑戰(zhàn)成功那么他就是計算不可區(qū)分的（一般情況下，我們認(rèn)為超過多項(xiàng)式時間復(fù)雜度的算法計算機(jī)就沒法處理了）。

☆完整版本

系統(tǒng)初始化（一次性）

首先信任中心TA選擇并公布一個RSA型模數(shù)n=p·q，并對素數(shù)p和q保密，然后對于參與者，每一個參與者選擇k個與n互素的秘密值s₁,s₂,…,s_k，1≤s_i≤n-1，并計算v_i=s_i²（mod n)，并向TA注冊（v₁,v₂,…v_k）為其公鑰。

鑒別協(xié)議流程：

1）證明者選擇一個隨機(jī)數(shù)??，1 ≤r≤n-1，計算并發(fā)送x=r²(mod n) 給V。

2）驗(yàn)證者隨機(jī)選擇??個比特值α向量=(α₁，α₂，…，α_k)并將??發(fā)送給P。

3）P計算
$$y=r?\prod _{i=1}^k{S_j}^{a_i}(modn)$$
，

并將??發(fā)送給V。

4）V驗(yàn)證等式
$$\prod _{i=1}^k{S_j}^{a_i}(modn)$$
如果等式不成立或者y=0，V不接受證明。否則，進(jìn)行下一輪證明。

驗(yàn)證者V執(zhí)行上述證明過程 ??輪 后，且均未拒絕，則驗(yàn)證者接受證明者P的證明，即相信他的身份。

（與簡化版本推導(dǎo)的過程類似）

性質(zhì)分析

1.完備性：顯然，誠實(shí)驗(yàn)證者接收的概率為1.

2.可靠性：如果證明者不知道秘密值s，那么他只能以1/2^k的概率欺騙驗(yàn)證者。執(zhí)行t輪后，欺騙概率下降到2^-kt。

3.零知識性：同樣地，與簡化版本一致，交互數(shù)據(jù)元組(x,y)可以被模擬器模擬，達(dá)到了計算不可區(qū)分性。

總結(jié)

1.安全假設(shè)

無論是簡化版本還是完整版本，協(xié)議的安全性依賴于未知分解的大合數(shù)的模平方根求解難題。這個問題等價于大合數(shù)分解困難問題。

2.參數(shù)選擇

以完整版本為例，k·t（簡化版本中k=1）需要足夠大，才能夠保證非誠實(shí)證明者欺騙成功的概率幾乎可忽略。同時，n的分解困難性也是安全性考慮之一。

3.安全平衡

每增加一輪協(xié)議，計算量和通信量均上升，但安全性越高。因此，需要在保證足夠安全的前提下，減少協(xié)議重復(fù)輪數(shù)t，提升效率。

2）Guillo-Quisquater身份鑒別協(xié)議

Guillo和Quisquater給出了一個身份鑒別方案，這個協(xié)議需要可信第三方參與、三輪交互、利用RSA公鑰密碼體制。

過程如下圖：

①系統(tǒng)初始化

1）信任中心TA選擇并公布一個RSA型模數(shù)??=?????，并對素數(shù)??和??保密。令φ=(p-1)(q-1) ，選取??使得gcd（??, ?? ）=1，計算??=1/e ?????? ?? ，公開(??, ??)。

2）用戶P選取唯一性身份I_P ，通過哈希函數(shù)變換得到哈希值J_P=H(I_P), TA給A分配密鑰S_P=I_P^-d (mod n) 。

②鑒別協(xié)議流程

1）P產(chǎn)生隨機(jī)數(shù)??，1≤??≤??-1，計算??=r(e) ?????? ?? ， 并將 I_P , ?? 發(fā)送給V；

2）V選取隨機(jī)數(shù)??，1 ≤ ?? ≤??，將??發(fā)送給P。

3）P計算y=S^u_Pmod n，并將y發(fā)送給V。

4）V計算J_P=H(I_P),并驗(yàn)證J^U_A·y^emod n不為0且等于??。如果成立，則此輪接收證明；否則，輸出拒絕。

**完備性：**顯然，誠實(shí)驗(yàn)證者接收的概率為1。

**可靠性：**如果證明者不知道秘密值??_p ，那么他只能夠以1/??的概率欺騙驗(yàn)證者。執(zhí)行??輪后，欺騙概率下降到e^-t。

**零知識性：**可被模擬器模擬，達(dá)到計算不可區(qū)分性。 如果??比較大時，每輪的錯誤概率就會很低，那么需要重復(fù)執(zhí)行的輪數(shù)??就可以很小，甚至為1。

2.非交互式零知識證明

? 采用Hash函數(shù)的方法來把一個交互式的證明系統(tǒng)變成非交互式的方法被稱為Fiat-Shamir變換，它由密碼學(xué)老前輩Amos Fiat和Adi Shamir兩人在1986年提出。

? Fiat-Shamir變換，又叫Fiat-Shamir Heurisitc（啟發(fā)式），或者Fiat-Shamir Paradigm（范式）。是Fiat和Shamir在1986年提出的一個變換，其特點(diǎn)是可以將交互式零知識證明轉(zhuǎn)換為非交互式零知識證明。這樣就通過減少通信步驟而提高了通信的效率。
? 菲亞特-沙米爾（Fiat-Shamir）啟發(fā)式算法允許將交互步驟替換為非交互隨機(jī)數(shù)預(yù)言機(jī)（Random oracle）。隨機(jī)數(shù)預(yù)言機(jī)，即隨機(jī)數(shù)函數(shù)，是一種針對任意輸入得到的輸出之間是項(xiàng)目獨(dú)立切均勻分布的函數(shù)。理想的隨機(jī)數(shù)預(yù)言機(jī)并不存在，在實(shí)現(xiàn)中，經(jīng)常采用密碼學(xué)哈希函數(shù)作為隨機(jī)數(shù)預(yù)言機(jī)。

? 以Schonor協(xié)議為例，交互式零知識證明的過程如下：

假設(shè)Alice 擁有一個秘密數(shù)字a，我們把這個數(shù)字當(dāng)做私鑰: sk，然后把它映射到橢圓曲線群上的一個點(diǎn) aG*，（簡寫為 aG），這個點(diǎn)我們把它當(dāng)做公鑰: PK。（Schnorr 協(xié)議充分利用了有限域和循環(huán)群之間單向映射，實(shí)現(xiàn)了簡潔的零知識證明安全協(xié)議）Alice 要向 Bob 證明她擁有 PK 對應(yīng)的私鑰 sk，那么如何證明呢。

? 第一步：為了保證零知識，Alice 需要先產(chǎn)生一個隨機(jī)數(shù)r，這個隨機(jī)數(shù)是用來保護(hù)私鑰無法被 Bob 抽取出來，會映射到橢圓曲線群上的點(diǎn)rG上，記為R發(fā)送給Bob；

? 第二步：Bob 要提供一個隨機(jī)數(shù)進(jìn)行挑戰(zhàn)，把它稱為 c；

第三步：Alice 根據(jù)挑戰(zhàn)數(shù)計算 z = r + a * c，然后把 z 發(fā)給 Bob，Bob通過式子進(jìn)行檢驗(yàn)：zG ?= R + cPK*；

? 由于z=r+csk，等式兩邊添加相同的生成元可得：zG= rG + c(aG)=cPK+R。就可以驗(yàn)證Alice確實(shí)擁有私鑰sk*，但是驗(yàn)證者Bob并不能得到私鑰sk的值，因此這個過程是零知識的，并且是交互式的。

? 由于橢圓曲線上的離散對數(shù)問題，知道R和G的情況下通過R=rG解出r是不可能的，所以保證了r的私密性。由這個問題也可以推廣到一般問題，假如證明者對于驗(yàn)證者第一次提出的問題，回答正確的話，驗(yàn)證者就有p的概率相信證明者自己的命題，第二次p+p2，…，第n次達(dá)到1-pⁿ的時候，當(dāng)n越來越大，這個概率的值就越接近1。

? 所以零知識證明是也一種基于概率的驗(yàn)證方式，驗(yàn)證者基于一定的隨機(jī)性向證明者提出問題，如果證明者都能給出正確回答，則說明證明者大概率擁有他所聲稱的“知識”。零知識證明也并不是數(shù)學(xué)意義上的證明，因?yàn)樗嬖谛「怕实恼`差，欺騙的證明者有可能通過虛假的陳訴騙過驗(yàn)證者。換句話說，零知識證明是概率證明而不是確定性證明（但是也存在技術(shù)能將誤差降低到可以忽略的值）。

? 上面的整個過程是在證明者和驗(yàn)證者在私有安全通道中執(zhí)行的。這是由于協(xié)議存在交互過程，只對參與交互的驗(yàn)證者有效，其他不參與交互的驗(yàn)證者，無法判斷整個過程是否存在串通的舞弊行為，一旦兩個驗(yàn)證者相互串通，交換自己得到的值，便可以推出私鑰。因此，是無法公開驗(yàn)證的。所以在交互式Schnorr協(xié)議中存在的私鑰泄露問題，使得算法無法在公開的環(huán)境下使用?？梢詫⒃嫉慕换ナ絽f(xié)議通過Fiat-Shamir變換變成非交互式零知識證明來解決這個問題：

回顧一下交互式Schnorr 協(xié)議的第二步，Bob 需要給出一個隨機(jī)的挑戰(zhàn)數(shù) c，這是為了防止Alice造假，這里我們可以讓 Alice 用*c = Hash(PK, R)*這個式子來計算這個挑戰(zhàn)數(shù)， 其中 R 是 Alice 發(fā)給 Bob 的橢圓曲線點(diǎn)，PK 是公鑰。

這個式子達(dá)到了兩個目的：

（1）Alice 在產(chǎn)生承諾 R 之前，沒有辦法預(yù)測 c，即使 c 最終是 Alice 生成的。

（2）c 是通過 Hash 函數(shù)計算的，會均勻分布在一個整數(shù)域內(nèi)，可以作為一個隨機(jī)數(shù)。

Hash 函數(shù)是單向的，這樣一來，雖然 c 是 Alice 計算的，但是 Alice 并沒有能力實(shí)現(xiàn)通過挑選 c 來作弊。因?yàn)橹灰?Alice 一產(chǎn)生 R， c 就相當(dāng)于固定下來了。

這樣，就把三步Schnorr協(xié)議合并為一步。Alice可直接發(fā)送*（R，z），因?yàn)锽ob擁有Alice的公鑰PK*，于是Bob可自行計算出c。然后驗(yàn)證zG?=R+cPK。

利用 Hash 函數(shù)，把三步 Schnorr 協(xié)議合并為了一步。Alice 可以直接發(fā)送：(R, c, z)這個三元組。又因?yàn)?Bob 擁有 PK，于是 Bob 可以自行計算出 c，于是 Alice 可以只發(fā)送 (R, z) 這個二元組即可。

總體步驟如下：
·Alice：均勻隨機(jī)選擇r，并依次計算 R=rG c=Hash(R,PK) z=r+csk

·Alice：生成證明*(R,z)*

·Bob(或者任意一個驗(yàn)證者)：計算e=Hash(PK,R)

·Bob(或者任意一個驗(yàn)證者)：驗(yàn)證zG?==R+cPK

可以看到這個過程，與交互式證明的過程相比減少了重復(fù)的挑戰(zhàn)和回應(yīng)過程，證明者只需要發(fā)送一次數(shù)據(jù)供驗(yàn)證者驗(yàn)證。去掉交互過程，證明者直接公開驗(yàn)證所需的數(shù)據(jù)。

ps：寫的比較潦草，懇請各位小可愛批評指正！
文章來源地址http://www.zghlxwxcb.cn/news/detail-757985.html

到了這里，關(guān)于【非交互式零知識證明】（下）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！