自适应多方非否认协议

李磊 王育民

西安电子科技大学综合业务网国家重点实验室 陕西 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.