具有不可關(guān)聯(lián)性的承諾方案

馬 麗，竇家維，吳艷梅

(陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，陜西 西安 710119)

具有不可關(guān)聯(lián)性的承諾方案

馬 麗，竇家維，吳艷梅

(陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，陜西 西安 710119)

承諾方案是密碼學(xué)中的一個(gè)基本方案，在密碼學(xué)中的其他協(xié)議中有重要的應(yīng)用，比如：安全多方計(jì)算、加密方案、簽名方案、密鑰交換協(xié)議等。不可關(guān)聯(lián)的承諾方案是國際密碼學(xué)界的一個(gè)研究熱點(diǎn)，是實(shí)現(xiàn)電子拍賣的理論基礎(chǔ)，也是多方保密計(jì)算一個(gè)重要的模塊。不可關(guān)聯(lián)承諾方案在密碼學(xué)與實(shí)際應(yīng)用中有很多用途，目前的研究主要集中于提高不可關(guān)聯(lián)承諾方案的安全性、效率以及減弱困難性假設(shè)等方面。因此，提出了兩種不可關(guān)聯(lián)承諾方案，能有效地阻止關(guān)聯(lián)攻擊和復(fù)制攻擊，且與其他方案相比效率更高。兩種不可關(guān)聯(lián)承諾方案分別基于離散對(duì)數(shù)假設(shè)和哈希函數(shù)性質(zhì)的合理應(yīng)用，如果能成功實(shí)施關(guān)聯(lián)攻擊就能夠計(jì)算離散對(duì)數(shù)，計(jì)算離散對(duì)數(shù)在密碼學(xué)中是難解問題，隨后給出了詳細(xì)的安全性證明和效率分析。研究分析表明，不可關(guān)聯(lián)承諾方案運(yùn)用哈希函數(shù)作為承諾函數(shù)，效率以及安全性都比較高。

不可關(guān)聯(lián)承諾；離散對(duì)數(shù)假設(shè)；哈希函數(shù)；承諾函數(shù)

0 引 言

在保密拍賣中，拍賣方發(fā)布拍賣公告，公告拍賣商品的展示時(shí)間與拍賣截止時(shí)間。在拍賣截止時(shí)間之前，競(jìng)價(jià)者寫好自己的出價(jià)，裝入信封并密封。截止日期過后，拍賣者在約定的開標(biāo)時(shí)間，當(dāng)著所有競(jìng)價(jià)者的面打開信封，出價(jià)最高者獲得拍賣的商品。這是現(xiàn)實(shí)社會(huì)的拍賣過程。如果拍賣活動(dòng)在網(wǎng)上進(jìn)行，就成為網(wǎng)絡(luò)拍賣。無論現(xiàn)實(shí)拍賣還是網(wǎng)絡(luò)拍賣，都要保密進(jìn)行?，F(xiàn)實(shí)拍賣需要密封信封，密封信封的數(shù)字化對(duì)應(yīng)物就是數(shù)字承諾[1]。

承諾協(xié)議分為兩個(gè)階段，承諾階段和揭示承諾階段。在承諾階段，承諾者根據(jù)自己的價(jià)格v，選擇一個(gè)隨機(jī)數(shù)r，計(jì)算承諾函數(shù)c=c(v,r)并發(fā)送給接收者，相當(dāng)于把出價(jià)裝入密封信封。在這個(gè)階段，要求任意概率多項(xiàng)式時(shí)間的接收者都不能得到關(guān)于承諾值v的任何知識(shí)，即使接收者試圖進(jìn)行欺騙，也無法得到相應(yīng)知識(shí)，這個(gè)性質(zhì)稱其為隱藏性。在揭示承諾階段，承諾者向接收者提供隨機(jī)數(shù)r和自己的承諾值v，接收者計(jì)算承諾函數(shù)c'=c(v,r)，如果c=c'，原承諾有效，否則拒絕，這個(gè)階段相當(dāng)于當(dāng)面打開信封。在這個(gè)階段，要求任意概率多項(xiàng)式時(shí)間的承諾者無法找到v≠v',r≠r'使得c(v,r)=c(v',r')，這個(gè)性質(zhì)稱其為綁定性。

然而，一般的承諾協(xié)議具有可關(guān)聯(lián)性。假設(shè)Bob是關(guān)聯(lián)攻擊者，他不知道Alice的v，但可以利用Alice的c(v)得到c(v*)(v*=v+b)。如果這樣，在拍賣中Bob就可以用比Alice高一點(diǎn)的價(jià)格獲得拍賣商品，這是不公平的。為了克服關(guān)聯(lián)承諾造成的不公平，Dolev等提出了不可關(guān)聯(lián)承諾的概念[2]，并提出了一個(gè)著名的不可關(guān)聯(lián)承諾方案，其他學(xué)者也提出了一些不可關(guān)聯(lián)承諾方案[3-11]，但這些方案的效率都有待進(jìn)一步提高。

因此，基于離散對(duì)數(shù)假設(shè)和哈希函數(shù)的性質(zhì)，構(gòu)造了兩種不可關(guān)聯(lián)承諾方案。這兩種方案簡(jiǎn)單易行，安全性和效率都很高，計(jì)算復(fù)雜性和通信復(fù)雜性很低，可以作為其他密碼學(xué)協(xié)議的模塊并廣泛應(yīng)用于其他實(shí)際安全問題中。

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

1.1 難解問題

現(xiàn)代密碼學(xué)的安全性基于某些困難問題假設(shè)。難解問題是這樣一些問題，經(jīng)過長時(shí)間研究，人們沒有找到這些問題的多項(xiàng)式時(shí)間算法或概率多項(xiàng)式時(shí)間算法，但也不能證明這些問題不存在多項(xiàng)式時(shí)間算法或者概率多項(xiàng)式時(shí)間算法。密碼系統(tǒng)的設(shè)計(jì)要使得攻擊者在不知道有關(guān)機(jī)密信息時(shí)，對(duì)密碼系統(tǒng)實(shí)施成功攻擊，必須要解某個(gè)難題。密碼學(xué)中的困難性問題主要有因子分解、離散對(duì)數(shù)、判斷n次剩余類問題[12]。

1.2 離散對(duì)數(shù)假設(shè)

αx≡βmodp

(1)

(2)

1.3 數(shù)字承諾方案

要理解數(shù)字承諾方案，需要理解兩個(gè)概念：安全性或隱藏性(secrecy or hiding)和歧義性(ambiguity)。

安全性：接收者即使任意偏離協(xié)議，也不能區(qū)分對(duì)于v的承諾c=c(v,r)和對(duì)于v'的承諾c'=c(v',r')，安全性保護(hù)承諾者的利益。

定義1[13]：數(shù)字承諾方案是概率多項(xiàng)式承諾者與接收者之間的一個(gè)交互協(xié)議，其中承諾者的輸入為v，協(xié)議同時(shí)滿足安全性和無歧義性。

1.4 基于離散對(duì)數(shù)假設(shè)的數(shù)字承諾方案

基于離散對(duì)數(shù)假設(shè)的數(shù)字承諾方案由Pedersen提出[14]，承諾協(xié)議如下：

揭示承諾：承諾者將v,r發(fā)送給接收者，接收者驗(yàn)證下述等式是否成立：

如果等式成立，承諾有效；否則無效。

(4)

Bob看到了承諾者揭示的承諾值(v,r)后，他可以將(v+b,r+m)作為他的承諾值進(jìn)行揭示，沒有人有理由懷疑他的承諾。如果攻擊者Bob這樣做，對(duì)于Alice是非常不公平的。為克服此承諾方案的可關(guān)聯(lián)問題，防止關(guān)聯(lián)攻擊，Dolev等提出了不可關(guān)聯(lián)承諾的概念[2]。

1.5 不可關(guān)聯(lián)承諾

有趣關(guān)系(interesting relation)：如果一個(gè)關(guān)系R?M×M是多項(xiàng)式時(shí)間可計(jì)算的非自反關(guān)系，則這個(gè)關(guān)系是有趣的。

不可關(guān)聯(lián)承諾：假設(shè)攻擊者知道v的承諾c=c(v,r)，仍然不能計(jì)算v*的承諾c*=c(v*,r')((v,v*)∈R)，則這個(gè)承諾稱為不可關(guān)聯(lián)承諾。

不可關(guān)聯(lián)承諾有如下兩種：

(1)關(guān)于承諾的不可關(guān)聯(lián)。

一個(gè)具有多項(xiàng)式計(jì)算能力的攻擊者知道關(guān)于v的承諾c=c(v,r)，只要能做出一個(gè)關(guān)于v*的承諾((v,v*)∈R)，不管他是否能夠成功地揭示這個(gè)承諾，都認(rèn)為關(guān)聯(lián)成功。

一個(gè)承諾方案是關(guān)于承諾可關(guān)聯(lián)的，如果一個(gè)多項(xiàng)式計(jì)算能力的攻擊者能夠在這種意義下關(guān)聯(lián)成功。若任何具有多項(xiàng)式能力的攻擊者都不能在這種意義下關(guān)聯(lián)成功，就稱承諾方案是關(guān)于承諾不可關(guān)聯(lián)的。

(2)關(guān)于揭示的不可關(guān)聯(lián)。

一個(gè)具有多項(xiàng)式計(jì)算能力的攻擊者知道關(guān)于v的承諾c=c(v,r)，能夠做出一個(gè)c*=c(v*,r')((v,v*)∈R)，且能夠在揭示階段成功地揭示該承諾，才算關(guān)聯(lián)成功。一個(gè)承諾方案是關(guān)于揭示可關(guān)聯(lián)的，如果一個(gè)多項(xiàng)式計(jì)算能力的攻擊者在這種意義下關(guān)聯(lián)成功。若任何具有多項(xiàng)式能力的攻擊者都不能在這種意義下關(guān)聯(lián)成功，稱承諾方案是關(guān)于揭示的不可關(guān)聯(lián)。

如果一個(gè)承諾方案是關(guān)于承諾不可關(guān)聯(lián)的，那么它也一定是關(guān)于揭示不可關(guān)聯(lián)的。

1.6 Fischlin提出的不可關(guān)聯(lián)承諾方案

Fischlin提出了一個(gè)著名的不可關(guān)聯(lián)承諾方案[15]，該方案的思想是對(duì)協(xié)議1進(jìn)行改進(jìn)，要求承諾者在做出承諾之后，再用零知識(shí)證明的方法向接收者證明他確實(shí)知道他的承諾值。如果是真正的承諾者就容易證明，而攻擊者就無法完成零知識(shí)證明過程，因而無法完成承諾。協(xié)議如下：

1)承諾階段。

將M,A,S發(fā)送給接收者。

(2)接收者選擇b∈Zp，并將b發(fā)送給承諾者。

2)揭示承諾階段。

(1)承諾者計(jì)算:

將a,u,r,y,z,v發(fā)送給接收者。

(2)接收者計(jì)算:

c≡a+bmodp

(3)接收者驗(yàn)證:

若相等，則接受承諾；否則拒絕承諾。

協(xié)議1具有可關(guān)聯(lián)性，可能導(dǎo)致拍賣失敗，造成經(jīng)濟(jì)損失。協(xié)議2中用附加零知識(shí)證明的方法解決了協(xié)議1中存在的關(guān)聯(lián)性問題，但是零知識(shí)證明的計(jì)算復(fù)雜性和通信復(fù)雜性都較高，因而效率較低。為提高不可關(guān)聯(lián)承諾的效率，設(shè)計(jì)了兩種不可關(guān)聯(lián)承諾方案。

2 兩種不可關(guān)聯(lián)承諾方案

2.1 基于離散對(duì)數(shù)的方案

協(xié)議3：基于離散對(duì)數(shù)的承諾方案。

c(v)=(c1,c2,c3)=(gxmodp,gymodp,xv+2yamodp)

將c發(fā)送給接收者作為對(duì)v的承諾。

揭示承諾階段：承諾者把x,y發(fā)給接收者，接收者驗(yàn)證:

(gxmodp,gymodp,xv+2yamodp)=(c1,c2,c3)

如果成立，則接受承諾；否則拒絕承諾。

直覺上，承諾者承諾的值是x的一個(gè)指數(shù)，攻擊者要想做出一個(gè)關(guān)于v+b的承諾，需要給c3乘以xb，這就必須知道x。要知道x，就必須求解離散對(duì)數(shù)。但求離散對(duì)數(shù)是困難的，所以該方案是不可關(guān)聯(lián)的。關(guān)于不可關(guān)聯(lián)性，有定理如下：

定理1：協(xié)議3構(gòu)成一個(gè)承諾方案且是關(guān)于揭示不可關(guān)聯(lián)的。

要證明協(xié)議3構(gòu)成一個(gè)數(shù)字承諾方案，需要下面的引理。

證明:首先證明安全性，假設(shè)對(duì)于v的承諾是：

(c1,c2,c3)=(gxmodp,gymodp,x(v+2)yamodp)

對(duì)于v'的承諾是：

當(dāng)Carol揭示承諾時(shí)，需要揭示s,t,v+1的值，就可以利用s,t,v計(jì)算α。

因?yàn)?/p>

所以

在這個(gè)方程中s,t,y,v都是已知的，都可以從方程中消除，最后得到一個(gè)xv+2modp≡u(píng)。利用費(fèi)馬小定理可以很容易求出x=umodp。而根據(jù)離散對(duì)數(shù)假設(shè)，這是不可能的。所以方案是關(guān)于揭示不可關(guān)聯(lián)的。事實(shí)上，這個(gè)方案也是關(guān)于承諾不可關(guān)聯(lián)的。遺憾的是，目前還不能把它標(biāo)準(zhǔn)歸約到離散對(duì)數(shù)問題。

協(xié)議4:拍賣協(xié)議。

發(fā)送給拍賣者作為自己的秘密出價(jià)。

2.2 基于Pedersen的數(shù)字承諾方案的改進(jìn)

協(xié)議設(shè)計(jì)：協(xié)議2是在協(xié)議1的基礎(chǔ)上增加零知識(shí)證明過程來阻止可能的關(guān)聯(lián)攻擊，注意到不用零知識(shí)證明的方法也可以阻止關(guān)聯(lián)攻擊，設(shè)計(jì)了一個(gè)基于單向散列函數(shù)的不可關(guān)聯(lián)承諾協(xié)議，就是在協(xié)議1的基礎(chǔ)上添加單向散列函數(shù)，同時(shí)將單向散列函數(shù)值作為承諾的一部分，使得承諾方案具有不可關(guān)聯(lián)性。具體協(xié)議如下：

c2=c2(v,r)=hash(v‖r)

并將(c1,c2)發(fā)送給接收者。

揭示承諾階段：承諾者發(fā)送(v,r)給接收者，接收者驗(yàn)證下述等式是否成立：

c2=c2(v,r)=hash(v‖r)

如果等式成立，則接受承諾值v；否則拒絕承諾值。

協(xié)議的正確性：

協(xié)議1是著名的承諾方案，文獻(xiàn)[10]已經(jīng)證明它確實(shí)構(gòu)成一個(gè)承諾方案。這里只證明增加單向散列函數(shù)確實(shí)能夠阻止關(guān)聯(lián)攻擊。

關(guān)聯(lián)攻擊者在看到(c1,c2)后，要想做出對(duì)v+b的承諾，必須選擇一個(gè)m,并計(jì)算：

c2=hash(x||r)

作為對(duì)x的承諾，把(c1,c2)給攻擊者。攻擊者得到(x+b,r+m)，就可以得到x。但根據(jù)離散對(duì)數(shù)假設(shè)，這是不可能的。

3 性能分析

Fischlin等提出了協(xié)議2，主要利用零知識(shí)證明的方法，使得承諾方案具有不可關(guān)聯(lián)性；分別利用離散對(duì)數(shù)和和哈希函數(shù)的性質(zhì)提出了兩種不可關(guān)聯(lián)性的承諾方案；這里對(duì)協(xié)議2和兩種不可關(guān)聯(lián)承諾方案的計(jì)算復(fù)雜性和通信復(fù)雜性進(jìn)行分析。

3.1 計(jì)算復(fù)雜性

在利用公鑰密碼系統(tǒng)構(gòu)建的協(xié)議中，模指數(shù)運(yùn)算的次數(shù)是決定協(xié)議效率的主要因素，因此協(xié)議的計(jì)算復(fù)雜性常常用模指數(shù)運(yùn)算的次數(shù)衡量。一個(gè)協(xié)議需要的模指數(shù)運(yùn)算次數(shù)越多，其計(jì)算復(fù)雜性越高，效率就越低。對(duì)這三種協(xié)議的計(jì)算復(fù)雜性，主要分析其模指數(shù)運(yùn)算，而忽略計(jì)算復(fù)雜度低得多的模加法運(yùn)算、單向散列函數(shù)運(yùn)算等。協(xié)議2需要進(jìn)行12次模指數(shù)運(yùn)算，而協(xié)議3需要6次，協(xié)議5需要進(jìn)行2次。

3．2 通信復(fù)雜性

協(xié)議的通信復(fù)雜性是傳遞數(shù)據(jù)的次數(shù)與傳送數(shù)據(jù)的比特?cái)?shù)。傳遞的次數(shù)越多，則協(xié)議的通信復(fù)雜性越高。傳遞的比特越多，通信復(fù)雜性也越高。協(xié)議2中，通過3次傳遞完成了承諾和承諾的揭示過程，需要傳送的比特?cái)?shù)為10lgp。協(xié)議3中，通過2次傳遞完成了數(shù)據(jù)的承諾與承諾揭示，需要傳送的比特?cái)?shù)為2lgp。協(xié)議5中，通過2次傳遞完成了數(shù)據(jù)的承諾與承諾揭示，傳遞的比特?cái)?shù)為lgp。(單向散列函數(shù)值的比特?cái)?shù)通常比lgp的比特?cái)?shù)少得多，因此可以忽略)

3.3 協(xié)議對(duì)比

計(jì)算復(fù)雜性與通信復(fù)雜性的全面比較見表1。表中計(jì)算復(fù)雜性指模指數(shù)運(yùn)算的次數(shù)，通信復(fù)雜性指通信次數(shù)與傳遞數(shù)據(jù)的比特?cái)?shù)。

表1 三種不可關(guān)聯(lián)性承諾的性能分析

4 結(jié)束語

由于不可關(guān)聯(lián)承諾方案有很多實(shí)際應(yīng)用，提出了兩種新的不可關(guān)聯(lián)承諾方案。協(xié)議3是基于離散對(duì)數(shù)直接構(gòu)造的方案，具有不可關(guān)聯(lián)性；協(xié)議5運(yùn)用哈希函數(shù)，將Pedersen的基于離散對(duì)數(shù)假設(shè)的關(guān)聯(lián)承諾方案改進(jìn)為一個(gè)不可關(guān)聯(lián)性承諾方案，并且提高了安全性。承諾方案的關(guān)鍵問題是如何找到簡(jiǎn)單的承諾函數(shù)。因此，如何找到簡(jiǎn)單的承諾函數(shù)并設(shè)計(jì)高效的承諾方案，是今后主要的研究方向。

[1] Hofheinz D,Quade J M.Universally composable commitments using random oracles[M]//Theory of cryptography.Berlin:Springer,2004:58-76.

[2] Dolev D,Dwork C,Naor M.Nonmalleable cryptography[J].SIAM Review,2003,45(4):727-784.

[3] Dachman-Soled D,Malkin T,Raykova M,et al.Adaptive and concurrent secure computation from new adaptive,non-malleable commitments[C]//Advances in cryptology-ASIACRYPT 2013.[s.l.]:[s.n.],2013:316-336.

[4] Abdalla M,Benhamouda F,Blazy O,et al.SPHF-friendly non-interactive commitments[C]//Advances in cryptology-ASIACRYPT 2013.[s.l.]:[s.n.],2013:214-234.

[5] Li Shundong,Wang Daoshun,Dai Yiqi,et al.New method for constructing non-malleable commitment schemes[J].Chinese Journal of Electronics,2008,17(4):583-588.

[6] Ishai Y, Kushilevitz E, Ostrovsky R.Sufficient conditions for collision-resistant hashing[M]//Theory of cryptography.Berlin:Springer,2005:445-456.

[7] Haitner I, Nguyen M H, Ong S J,et al.Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function[J].SIAM Journal on Computing,2009,39(3):1153-1218.

[8] Brenner H,Goyal V,Richelson S,et al.Fast non-malleable commitments[C]//Proceedings of the 22nd ACM SIGSAC conference on computer and communications security.[s.l.]:ACM,2015:1048-1057.

[9] Pass R.Unprovable security of perfect NIZK and non-interactive non-malleable commitments[M]//Theory of cryptography.Berlin:Springer,2013:334-354.

[10] Naor M.Bit commitment using pseudorandomness[J].Journal of Cryptology,1991,4(2):151-158.

[11] Goldreich O. Foundations of cryptography:basic tools[M].London:Cambridge University Press,2001.

[12] 李順東,王道順.現(xiàn)代密碼學(xué)[M].北京:科學(xué)出版社,2009.

[13] Paillier P.Public-key cryptosystems based on composite degree residuosity classes[C]//Advances in cryptology-EUROCRYPT’99.[s.l.]:[s.n.],1999:223-238.

[14] Pedersen T P.Non-interactive and information-theoretic secure verifiable secret sharing[C]//Advances in cryptology-CRYPTO’91.[s.l.]:[s.n.],1992:129-140.

[15] Fischlin M,Fischlin R.Efficient non-malleable commitment schemes[C]//Advances in cryptology-CRYPTO 2000.[s.l.]:[s.n.],2000:413-431.

Non-malleable Commitment Schemes

MA Li,DOU Jia-wei,WU Yan-mei

(College of Mathematics and Information Science,Shaanxi Normal University,Xi’an 710119,China)

Commitment scheme is a basic scheme in cryptography and has been important application in other agreements of cryptography like secure multi-party computation,encryption scheme,signature scheme,key exchange protocols and so on.Non-malleable commitment scheme is one focus in the international cryptographic community and the theoretical basis of electronic auction,which is also an important building block of secure multi-party computation and has important applications in cryptography and practice.At present,most studies focus on improving the security and the efficiency of non-malleable commitment schemes and less difficulty hypothesis,etc.So,two non-malleable commitment schemes are proposed which can efficiently prevent malleable attack and copy attack.These non-malleable commitment schemes are constructed based on discrete logarithm assumption and one-way hash function.If adversary can successfully attack the scheme,it can compute the discrete logarithm.The computing discrete logarithm in cryptography is a hard problem,and its security proving and efficiencies analysis are given.Study analysis shows that non associated commitment scheme using hash function as a commitment function,efficiency and security are relatively high.

non-malleable commitment;discrete logarithm assumption;hash function;commitment function

2016-06-07

2016-09-15 網(wǎng)絡(luò)出版時(shí)間：2017-03-07

國家自然科學(xué)基金資助項(xiàng)目(61272435)

馬 麗(1983-)，女，碩士研究生，研究方向?yàn)槊艽a學(xué)與信息安全；竇家維，副教授，碩士生導(dǎo)師，研究方向?yàn)槊艽a學(xué)與信息安全。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170307.0922.070.html

TP301

A

1673-629X(2017)05-0108-05

10.3969/j.issn.1673-629X.2017.05.023