自適應多方非否認協議

李磊 王育民

西安電子科技大學綜合業務網國家重點實驗室 陜西 710071

0 引言

非否認協議廣泛應用于電子商務、認證電子郵件等領域。自 Zhou等人提出的公平的不可否認協議起，非否認協議得到了深入而廣泛的研究。最初非否認協議的研究僅限于對雙方非否認協議的研究，隨著研究的深入，多方非否認協議成為研究的熱點。多方非否認協議通常指有一個發送方多個接收方的非否認協議，根據發送的消息不同，可分為發送相同消息的多方非否認協議MPNR_S協議)和發送不同消息的多方非否認協議(MPNR_D協議)。

1 自適應多方非否認協議

協議由exchange、abort和recovery三個子協議組成。在參與方都誠實和信道可靠的情況下，只需使用exchange子協議就可以完成信息交換，但在參與方不誠實或其它異常情況下，需要運行輔助的子協議，來保證協議公平。

1.1 基本假定和符號說明

協議采用自由加密假定，即一個密文只能用一種方式看待。此外，協議假定可信第三方與協議參與者之間使用彈性信道，而除TTP外的協議參與者之間的信道為不可靠信道。協議中的發送者、所有接收者集合和可信第三方分別使用O、R和T代表。A→B代表用戶A向用戶B單播一個消息，A?S代表用戶A向集合S中的用戶廣播一個消息。使用uA代表用戶A的公鑰，vA代表用戶A的私鑰，{m}k代表用密鑰k對m加密，h(m)代表抗碰撞攻擊的單向哈希函數，ES(m) 代表用群加密機制對m加密，只有集合S中的用戶才能解密。

為了能夠自適應相同消息和不同消息的情況，協議設計集合Gi代表接收相同消息的接收者集合，使用N代表接收者的數量，I代表需要發送的不同消息的數量。

1.2 初始化集合Gi

初始化集合Gi的作用是將接收者按照待接收消息不同分別劃入集合Gi。過程如下：

其中，mi代表第i個不同的消息，mRj代表接收者Rj待接收的消息。初始化過程逐個考查接收者待接收的消息，將接收相同消息的接收者加入集合Gi中。最后形成I個集合，每個集合中的接收者接收相同的消息。

顯然當I=1時，所有接收者都在同一個集合中，協議退化為 MPNR_S協議；當I=N時，所有集合Gi中，都只有一個接收者，協議退化為MPNR_D協議。

1.3 exchange子協議

1.O?Gi:l,O,Gi,T,{mi}ki,EGi(ni),h(k),{l,k}uT,EOOi. i∈{1,I}

2.Ri→O:l,O,EORi.

3.O?R':l,ER'(k).

其中，ni是O為每個接收者集合選擇的隨機數，ki=k⊕ni是加密mi的密鑰，k由O選擇，l=h(O,R,T,{m1}k1,{m2}k2...,k)是 協 議 運 行 的 惟 一 標 識 符 ，EOOi={l,{l,k}uT,h({mi}ki),h(k),h(ni)}vO是 發 方 證 據 ，EORi={l,{l,k}uT,h({mi}ki),h(k),h(ni)}vRi是Ri的接收方證據，R'代表成功向O發送了正確的EORi的接收者集合。

1.4 abort子協議

發送exchange子協議消息1一段時間后，如果O沒有收到來自Ri的EORi，則將Ri加入集合R''，發起abort子協議，向可信第三方要求與R''內的接收者終止協議。

1.O→T:l,O,R'',T,h({mi}ki,h(k),Abortreq

2.T: FOR all Ri∈R''IF(Ri∈R''R)THENretrievesEORi;ELSEaddRiintoR''A;

3.T→O:l,R''A,allretrievedEORi,Abortcon

其中，R''R代表在TTP收到abort請求之前，已經通過recovery子協議，從可信第三方處獲得了k的接收者集合，R''A代表經過可信第三方確認的，終止協議的接收者集合。Abortreq={l,R''}vO代表O向可信第三方發送的終止協議請求，Abortcon={l,R'',R''A,Abortreq}vT代表可信第三方向O確認與R''A中的接收者終止協議。

1.5 recovery子協議

通過exchange子協議，iR如果沒有收到來自O的密鑰k或收到的k不正確，則可以發起recovery子協議，要求可信第三方協助完成協議。

1.Ri→T:l,O,Ri,T,h({mi}k),h(k),

{l,k}uT,EOOi,EORi,RecovRiT: IF (Ri∈R''A)THEN

2.T→Ri:l,Abortreq,AbortRi

ELSEaddRiintoR''R;

2'.T→Ri:l,{k}uRi

其中RecovRi={l,{l,k}uT}vRi代表Ri向可信第三方發出的recovery請求，AbortRi={l,Ri,EORi,Abortreq}vT代表可信第三方通知Ri協議已經終止的證據。

2 協議分析

2.1 不可否認性

發方不可否認：如果O否認曾經向Ri發送消息mi，則Ri可以出示證據NRO=(l,T,mi,ni,k,EOOi)，通過 l,T,mi,ni,k驗證EOOi={l,{l,k}uT,h({mi}ki),h(k),h(ni)}vO，即可證明O確實曾經向Ri發送消息mi。

收方不可否認：如果Ri否認收到了來自O的消息mi，則O可以出示證據NRR=(l,T,mi,ni,k,EORi)，通過l,T,mi,ni,k驗證EORi={l,{l,k}uT,h({mi}ki),h(k),h(ni)}vRi，此時，如果Ri不能出示AbortRi，即可證明Ri確實收到了mi，但如果Ri出示了AbortRi，則說明O在收到EORi后，沒有把k發給Ri，而搶先要求可信第三方終止了與Ri的協議，因此，應判定Ri沒有收到mi。

2.2 公平性

在協議參與方都誠實的情況下，顯然協議會按照exchange子協議運行，即使信道不可靠，也可以由about子協議和recovery子協議彌補，由此前對于協議的描述可知，協議運行只有兩種結果：①O獲得NRR且Ri獲得NRO；②O沒有獲得EORi且Ri沒有獲得k。兩種結果下，協議都公平。

如果O不誠實，則O希望獲得NRR，但不提供k給Ri。如果O偽造 exchange子協議的消息 1，顯然得不到有效的EORi。如果O偽造exchange子協議的消息3或者不發送消息3， Ri可以通過可信第三方獲得k或者AbortRi，都不影響協議公平性。

如果Ri不誠實，則Ri希望不提供正確的EORi給O，轉而從可信第三方得到k。不論Ri發送錯誤的EORi給O或者不發送EORi給O，O都會要求可信第三方終止與Ri的協議，abort子協議運行的結果只有兩個：①O獲得Abortcon，稍后可信第三方僅將AbortRi發送給Ri；②Ri已經獲得k，O從可信第三方處獲得EORi。由于在Ri的recovery請求中包含了與EORi內容相同的EOOi，因此， Ri不可能通過欺騙可信第三方而使O獲得偽造的EORi。abort子協議運行的兩種結果，都不影響協議公平性。

3 與其它協議的比較

非否認協議的效率分析中，通常把公鑰運算量、通信量以及可信第三方資源占用量作為考查的重要指標。由于通過exchange子協議正常完成交換的用戶數遠大于使用abort子協議和recovery子協議的用戶數，因此本文對效率的分析僅考慮exchange子協議。本文協議與一個MPNR_S協議和一個MPNR_D協議的比較如下。

3.1 與MPNR_S協議比較

在發送I個消息給N個接收者時，MPNR_S協議需運行I個實例，每個實例發送一個消息，而本文協議僅需運行一次，可信第三方也僅需存儲一次協議狀態。MPNR_S協議的每個實例都需要使用一個k加密消息，本文協議僅需使用一個k，但需要為每個消息選擇in并加密。MPNR_S協議每個實例需要廣播發送消息一次，廣播發送密鑰一次，I個實例需要2I次廣播，而本文協議依次廣播I個消息，但只需1次廣播發送密鑰。具體比較如表1所示。

表1 與MPNR_S協議比較

與MPNR_S協議相比，本文協議以增加一次公鑰運算的較小代價，減少了 1I- 次廣播通信量，并且大大降低了可信第三方的資源占用量。

3.2 與MPNR_D協議比較

在發送I個消息給N個接收者時，雖然 MPNR_D協議和本文協議都只需運行一次，但 MPNR_D協議需要為每個接收者計算 EOOi，選擇 ni并加密，而本文協議僅需為每個集合 Gi進行這些公鑰運算。MPNR_D協議需要依次單播消息給所有接收者，而本文協議需要依次廣播消息給 Gi，對EORi和密鑰的發送，兩協議都需要N次單播和一次廣播。具體比較如表2所示。

表2 與MPNR_D協議比較

與 MPNR_D協議相比，本文協議減少了2N-I次的公鑰運算，增加了I次廣播，減少了N次廣播。

4 結論

通過將接收相同消息的接收者劃入集合Gi，然后依次向Gi廣播發送消息的方法，本文提出了一個自適應多方非否認協議。協議在 1I=時退化為MPNR_S協議，在I N= 時退化為MPNR_D協議。在1IN＜＜時，與MPNR_S協議和MPNR_D協議相比，本文協議在公鑰運算量、通信量以及可信第三方資源占用量等方面，效率均有提高。

[1] ZHOU J,GOLLMANN D.A fair non-repudiation protocol[C]//in Proceedings of the 1996 IEEE Symposium on Security and Privacy.Oakland.1996.

[2] KREMER S,MARKOWITCH O.A multi-party non-repudiation protoco[C]//in 15th International Conference on Information Security. Beijing.China.IFIP World Computer Congress.2000.

[3] MARKOWITCH O,KREMER S.A Multi-party Optimistic Non-repudiation Protocol[C]//in Information Security and Cryptology - ICISC 2000:Third International Conference. Seoul,Korea:Spinger-Verlag.2001.

[4] FERRER-GOMILA J L,PAYERAS-CAPELL M,and HUGUETROTGER L.A Realistic Protocol for Multi-party Certified Electronic Mail[C]//in Proceedings of Information Security Conference.Sao Paulo:Springer.2002.

[5] ZHOU J,ONIEVA J,and LOPEZ J.Optimized multi-party certified email protocols[J].Information Management and Computer Security.2005.

[6] WANG H,WANG R.Improvement of a multi-party certified email protocol[J].Chinese Journal of Electronics.2007.

[7] 李磊,楊加喜,王育民.支持透明離線TTP的多方非否認協議[J]吉林大學學報(工學版).2009.

[8] ONIEVA J,ZHOU J,CARBONELL M,et al.a multi-party non-repudiation protocol for exchange of different messages[C]// in 18th IFIP International Information Security Conference.Athens.Greece.2003.

[9] ONIEVA J A,ZHOU J,and LOPEZ J.Non-repudiation protocols for multiple entities[J].Computer Communications. 2004.