陳勇，魯龍，曾晟珂，何明星

（西華大學(xué)計算機(jī)與軟件工程學(xué)院，四川 成都 610039）

適用于多方協(xié)議的可否認(rèn)認(rèn)證

陳勇，魯龍，曾晟珂，何明星

（西華大學(xué)計算機(jī)與軟件工程學(xué)院，四川 成都 610039）

可否認(rèn)認(rèn)證不僅可以像數(shù)字簽名那樣實現(xiàn)消息認(rèn)證，且非公開可驗證性使其可以滿足許多簽名不能滿足的需求，如隱私保護(hù)等。研究了如何在多方協(xié)議中實現(xiàn)完全可否認(rèn)認(rèn)證，利用承諾方案提出了一個適用于多方協(xié)議的可否認(rèn)認(rèn)證。該方案作為一種一般化的方法，能夠為大多數(shù)多方協(xié)議實現(xiàn)可否認(rèn)認(rèn)證，如可否認(rèn)的群密鑰協(xié)商協(xié)議等，形式化了方案的敵手模型并嚴(yán)格證明了方案的安全性，為研究可否認(rèn)認(rèn)證提供了一種新思路。

可否認(rèn)認(rèn)證；多方協(xié)議；承諾；安全性

1　引言

數(shù)字簽名作為密碼學(xué)的一種基本原語，其不可偽造性以及不可否認(rèn)性受到學(xué)術(shù)界的廣泛關(guān)注。由于簽名過程的不可抵賴性，數(shù)字簽名算法不適用于保護(hù)用戶隱私的認(rèn)證。為了保護(hù)認(rèn)證過程中用戶的隱私，可否認(rèn)認(rèn)證的概念被提出?？煞裾J(rèn)認(rèn)證協(xié)議在保證消息認(rèn)證性的同時，其認(rèn)證副本并不能證明協(xié)議的參與者參與了認(rèn)證，即不具有公開驗證性，這在電子購物、互聯(lián)網(wǎng)會議等方面有廣泛的應(yīng)用前景。

1998年，Dwork等［1］首次正式提出可否認(rèn)認(rèn)證的概念，并利用時間約束機(jī)制實現(xiàn)了并發(fā)環(huán)境中的可否認(rèn)認(rèn)證。之后一系列的可否認(rèn)協(xié)議被提出［2～4］。交互式的認(rèn)證主要面臨并發(fā)會話攻擊。認(rèn)證的可否認(rèn)性要在并發(fā)環(huán)境中成立，一般采用時間約束機(jī)制［1］，然而，這種假設(shè)太強(qiáng)。通過使用Pass在文獻(xiàn)［5］中提出的非編程預(yù)言機(jī)，Jiang等［6］提出一個不使用時間約束的在并發(fā)環(huán)境中完全可否認(rèn)的認(rèn)證協(xié)議。Raimondo等在文獻(xiàn)［7］中利用明文可意識性（plaintext awareness）證明了SKEME協(xié)議滿足完全可否認(rèn)性。Jiang［8］利用“時限加密”，在可認(rèn)證的密鑰交換協(xié)議中實現(xiàn)了可否認(rèn)性。

為了提高認(rèn)證協(xié)議的效率，很多學(xué)者關(guān)注認(rèn)證協(xié)議的交互輪數(shù)，提出了一系列非交互式可否認(rèn)的認(rèn)證協(xié)議［9～11］。由于非交互性，這些協(xié)議自然滿足并發(fā)環(huán)境，但卻僅實現(xiàn)“半可否認(rèn)性”［5］。例如，Susilo在文獻(xiàn)［9］中利用 Chameleon Hash函數(shù)實現(xiàn)認(rèn)證的可否認(rèn)性，在文獻(xiàn)［9］方案中，參與方只能否認(rèn)通信的內(nèi)容，卻不能否認(rèn)其參與了認(rèn)證。Li等［11］也提出了一種非交互式的、基于身份的可否認(rèn)認(rèn)證協(xié)議。該協(xié)議也僅達(dá)到了半可否認(rèn)性，因為只有消息接收方才能仿真發(fā)送方發(fā)的認(rèn)證副本。即對于某次認(rèn)證副本，發(fā)送方和接收方中至少有一方不能否認(rèn)參與了認(rèn)證?？梢?，非交互式的可否認(rèn)認(rèn)證雖然認(rèn)證效率較高，但是應(yīng)用限制大。

在這些方案中，研究者研究的模型大多都是一對一的，即一對消息的發(fā)送者與接收者。在一些實際應(yīng)用中，協(xié)議需要多方用戶的參與。在多方協(xié)議中引入可否認(rèn)認(rèn)證有以下研究工作。2002年，Naor［12］將可否認(rèn)認(rèn)證與環(huán)簽名的特性相結(jié)合，提出了可否認(rèn)的環(huán)認(rèn)證，消息的接收者能夠確認(rèn)消息確實來自環(huán)中的成員，但不能確認(rèn)具體是哪一個成員，同時，第三方卻不能確認(rèn)消息來自于環(huán)成員。另一個將可否認(rèn)認(rèn)證引入到多方環(huán)境的協(xié)議是可否認(rèn)的群密鑰協(xié)商協(xié)議，可否認(rèn)的群密鑰協(xié)商協(xié)議是指多個參與者通過協(xié)商得到一個共同的會話密鑰，在協(xié)商結(jié)束后，任何實體都不能證明協(xié)商的參與者曾經(jīng)參與了協(xié)議。2006年，Bohli等［13］利用Schnorr簽名算法［14］首次提出一個可否認(rèn)的群密鑰協(xié)商協(xié)議，并在Random模型中證明協(xié)議的安全性。2010年，Zhang等［15］改進(jìn)了文獻(xiàn)［14］中方案的通信效率，且安全性證明不需要隨機(jī)預(yù)言機(jī)；2010年，Zhang等［16］給出一個構(gòu)造可否認(rèn)群密鑰協(xié)商協(xié)議的一般構(gòu)造方法，該方法可以將無認(rèn)證的群密鑰協(xié)商協(xié)議轉(zhuǎn)化成可否認(rèn)的群密鑰協(xié)商協(xié)議。2014年，Steinwandt等［17］提出一個構(gòu)造器可以將一個普通的兩輪次的群密鑰協(xié)商協(xié)議轉(zhuǎn)化為一個三輪次的可否認(rèn)的群密鑰協(xié)商協(xié)議。2016年，Chen等［18］利用DB協(xié)議［19］提出一個可否認(rèn)的群密鑰協(xié)商協(xié)議，進(jìn)一步改進(jìn)了協(xié)議的通信效率。

目前，雖然已有一系列關(guān)于可否認(rèn)的群密鑰協(xié)商協(xié)議的研究，但其可否認(rèn)性都依賴于最終的會話密鑰協(xié)商，無法簡單地將其擴(kuò)展到普通的多方協(xié)議，如非對稱的群密鑰協(xié)商協(xié)議［20］等。因此，本文旨在通過秘密承諾［23］的思想設(shè)計一個適用于廣播信道（如ad hoc網(wǎng)絡(luò)等）中多方協(xié)議的可否認(rèn)認(rèn)證方案（MDA， deniable authentication for multi-party protocol）。與以往的多方可否認(rèn)認(rèn)證（如可否認(rèn)的群密鑰協(xié)商）方案不同，本文方案不再關(guān)心消息的具體內(nèi)容，因此，具有很好的擴(kuò)展性。另外，本文定義了MDA方案的敵手模型，并對方案的安全性給出了證明。

2　基礎(chǔ)知識

2.1困難性問題

本文的安全性主要是基于判定性 Diffie-Hellman（DDH）假設(shè)。令G為階是素數(shù)q的乘法群，g是群G的生成元。

2.2多方計算協(xié)議

在只存在被動敵手的公共信道上，給出多方協(xié)議［21］的一般定義。令P1， …， Pn表示信道中的n個對等用戶，q表示系統(tǒng)的安全參數(shù)。假設(shè)協(xié)議共執(zhí)行l(wèi)個輪次，則多方協(xié)議的基本通信模型如下。

1）參與方Pi選擇xi作為自己的輸入，同時選擇一個隨機(jī)值ri。

2）令t=1，參與方Pi依次執(zhí)行以下步驟，直到t≥l。

① Pi產(chǎn)生消息其中，表示在本輪次將要發(fā)送給參與方的消息。

③令t=t+1。

3）參與方Pi產(chǎn)生輸出oi。

在只存在被動敵手的情況下，多方協(xié)議只需滿足私密性，即當(dāng)存在敵手監(jiān)聽整個信道時，參與方Pi所產(chǎn)生的輸出oi只能被它自己所了解。然而，當(dāng)信道中存在主動敵手時，主動敵手可以插入、刪除、篡改任何消息。此時，協(xié)議不僅需要滿足私密性，還必須滿足認(rèn)證性。

私密性：參與方Pi產(chǎn)生的輸出oi只能被參與方自己所了解，而對于任何第三方來說，oi在參數(shù)空間內(nèi)是均勻分布的。

認(rèn)證性：在多項式時間內(nèi)，任何敵手都不能以不可忽略的概率偽裝成其他誠實參與方參與并完成協(xié)議。

最常見的多方協(xié)議的例子便是群密鑰協(xié)商協(xié)議。

2.3字符串承諾方案

承諾方案作為一種基礎(chǔ)性密碼工具，常被用在構(gòu)造零知識證明［22］或可否認(rèn)認(rèn)證中。在承諾方案中，承諾者將承諾值和秘密值綁定在一起，承諾結(jié)束后，承諾者打開秘密值并驗證。安全的承諾方案必須滿足私密性和綁定性。字符串承諾方案［22］一般由以下幾個算法組成。

1）初始化階段Gen（1）k：可信方運行初始化算法生成系統(tǒng)參數(shù)（p，g，h）。

私密性：在承諾值被打開之前，承諾值保持私密性。

3　模型

3.1相關(guān)符號

首先，給出方案所用的主要符號，如表1所示。

表1　相關(guān)概念

3.2系統(tǒng)模型

本方案的基本思想是：在協(xié)議開始初，參與者承諾一個消息認(rèn)證碼密鑰；然后，參與者利用私鑰對消息認(rèn)證碼密鑰進(jìn)行簽名；接著，參與者利用消息認(rèn)證碼密鑰對多方協(xié)議的通信進(jìn)行認(rèn)證，這里需要認(rèn)證編碼函數(shù)MAC；在協(xié)議結(jié)束后，參與者公開自己的消息認(rèn)證碼密鑰，其他參與者驗證多方協(xié)議消息的合法性。

因此，MDA方案包括6個算法，下面對各個算法進(jìn)行介紹。

t進(jìn)行認(rèn)證。

需要注意的是，Communicate階段不需要在Commit階段和Authenticate階段之后，可以在這2個階段之前或之間。為了達(dá)到較高的通信效率，Communicate階段一般與Commit階段和Authenticate階段同時進(jìn)行。

3.3 安全模型

MDA方案使每個用戶確信收到的消息的確來自誠實用戶，且發(fā)送者對消息的認(rèn)證是可否認(rèn)的，因此，其安全性包括完整性、健壯性、可否認(rèn)性。

1） 完整性。如果所有的參與者都誠實地執(zhí)行協(xié)議，則jPpid∈接受消息tim來自用戶iP。

2） 健壯性。方案的健壯性意味著任何用戶都不能偽裝成誠實用戶iP對消息tim進(jìn)行認(rèn)證。接下來，通過一個游戲來定義方案的健壯性。

初始化階段：挑戰(zhàn)者X運行Setup（1）k生成系統(tǒng)參數(shù)，并將公開的系統(tǒng)參數(shù)發(fā)送給敵手A。

訓(xùn)練階段：挑戰(zhàn)者X回答敵手A的一系列查詢。

3） 可否認(rèn)性。方案的可否認(rèn)性是指協(xié)議的通信副本可以由敵手獨自構(gòu)造出來。即存在一個僅了解敵手知識的模擬者，不能訪問用戶的私鑰，除非用戶被腐蝕，構(gòu)造的通信副本的分布與真實通信的分布是一致的。正式地說，用表示模擬者模擬的通信副本，用表示真實執(zhí)行過程的副本，令?表示某個多項式時間的區(qū)分者，給出以下可否認(rèn)的定義。如果對于任何的敵手 A和所有的區(qū)分者?，總存在一個模擬者，使則認(rèn)為協(xié)議是滿足可否認(rèn)的。

4　協(xié)議的實現(xiàn)

本節(jié)給出MDA方案的具體實現(xiàn)，方案的靈感來源于文獻(xiàn)［1］的零知識證明。下面給出方案的詳細(xì)過程。

Setup：k為系統(tǒng)的安全參數(shù)；G是一個階為素數(shù)q的乘法群；g是群G的生成元；H是一個密碼學(xué)散列函數(shù)

5　安全性證明

本節(jié)對方案的安全性進(jìn)行證明，很容易理解方案是滿足完整性的，所以，接下來分別證明方案的可否認(rèn)性和健壯性。

5.1可否認(rèn)性

MDA方案的可否認(rèn)性使參與者可以否認(rèn)曾經(jīng)參與了多方協(xié)議消息的認(rèn)證，即參與者可以否認(rèn)曾參與了多方協(xié)議。本文通過構(gòu)造一個模擬者∑，在不允許模擬者∑訪問未腐蝕用戶私鑰的情況下，顯示模擬者生成的通信副本與真實執(zhí)行過程的通信副本不可區(qū)分，從而證明方案是滿足可否認(rèn)性的。

定理1MDA方案滿足可否認(rèn)性，如果H是一個隨機(jī)預(yù)言機(jī)。

證明構(gòu)造模擬者∑，它的輸入僅包括用戶公鑰等公共參數(shù)以及被腐蝕用戶的私鑰。用表示破壞方案可否認(rèn)性的敵手。在模擬過程中，模擬者必須回答敵手的一系列詢問，如Commit、Authenticate、Communicate、Open以及Corrupt。用表示在模擬過程中的通信副本，用表示真實協(xié)議的執(zhí)行副本?？煞裾J(rèn)性顯示對于任何敵手和所有的區(qū)分者?，都存在一個模擬者，使和是不可區(qū)分的。

Open（i,l1）：模擬者∑公開承諾值，即廣播消息

顯然，模擬者∑能夠在不引起任何區(qū)別的情況下成功地回答敵手的所有查詢，所以，該方案實現(xiàn)了可否認(rèn)性。

5.2健壯性

方案的健壯性是指任何敵手，在不了解用戶iP私鑰的前提下，都不能偽裝成用戶Pi參與協(xié)議。本文顯示，如果一個敵手能夠破壞方案的健壯性，則該敵手一定能以不可忽略的概率解決DDH困難性問題。

定理2如果DDH困難性假設(shè)成立，且消息認(rèn)證編碼函數(shù)（）MAC?是安全的，H是一個隨機(jī)預(yù)言機(jī)，那么方案是滿足健壯性的。

證明用A表示攻擊方案健壯性的敵手，如果A能以不可忽略的概率攻破方案的健壯性，則挑戰(zhàn)者X就可以利用敵手A來解決DDH困難性問題。挑戰(zhàn)者X被給出實例，判斷與是否相等。

接下來，說明挑戰(zhàn)者X如何利用敵手A來解決困難性問題。

接下來，敵手開始進(jìn)行游戲，首先是訓(xùn)練階段，具體如下。

H查詢：挑戰(zhàn)者X維持一個初始化為空的列表listH。當(dāng)輸入消息mi時，挑戰(zhàn)者X檢查listH里是否存在（mi，θi）。如果存在，則返回θi；否則，挑戰(zhàn)者 X隨機(jī)地選擇θi，同時將（mi，θi）存入到listH中并返回θi。

經(jīng)過一系統(tǒng)的訓(xùn)練之后，敵手A提交挑戰(zhàn)查詢，挑戰(zhàn)部分如下。

6　結(jié)束語

本文提出了一個適用于多方協(xié)議的可否認(rèn)認(rèn)證方案，MDA協(xié)議可以有效地防止敵手對通信的消息進(jìn)行修改或插入，從而冒充合法用戶去欺騙其他誠實用戶。同時，區(qū)別于數(shù)字簽名的不可否認(rèn)性，即公開可驗證性，可否認(rèn)協(xié)議的通信副本不能證明用戶曾經(jīng)參與了協(xié)議，有效地保護(hù)了參與者的隱私。本文在前人的基礎(chǔ)上，形式化了方案的敵手模型，并證明了方案滿足可否認(rèn)性和健壯性。相比于可否認(rèn)的群密鑰協(xié)商協(xié)議等具體方案，本文方案具有很好的擴(kuò)展性，能夠被應(yīng)用到多數(shù)多方協(xié)議中實現(xiàn)可否認(rèn)認(rèn)證。

［1］DWORK C， NAOR M， SAHAI A. Concurrent zero-knowledge［J］. Journal of the ACM， 2004， 51（6）：851-98.

［2］DENG X， LEE C H， ZHU H. Deniable authentication protocols［J］. IEEE Computers and Digital Techniques， 2001， 148（2）：101-104.

［3］LEE W B， WU C C， TSAUR W J. A novel deniable authentication protocol using generalized ElGamal signature scheme［J］. Information Sciences， 2007， 177（6）：1376-1381.

［4］KAR J. ID-based deniable authentication protocol based on diffie-hellman problem on elliptic curve［J］. International Journal of Network Security， 2013， 15（5）：357-364.

［5］PASS R. On deniability in the common reference string and random oracle model［C］//Advances in Cryptology， Berlin. c2003：316-337.

［6］JIANG S. Deniable authentication on the Internet［M］. Berlin：Springer， 2008：298-312.

［7］RAIMONDO M D， GENNARO R， KRAWCZYK H. Deniable authentication and key exchange［C］//ACM Conference on Computer and Communications Security. c2006：400-409.

［8］JIANG S. Timed encryption with application to deniable key exchange［J］. Theoretical Computer Science， 2014（560）： 172-189.

［9］SUSILO W， MU Y. Deniable ring authentication revisited［C］// Applied Cryptography and Network Security， Berlin. c2004：149-163.

［10］WANG L， ZHANG G， MA C. ID-based deniable ring authentication with constant-size signature［J］. Frontiers of Computer Science in China， 2008， 2（1）：106-12

［11］LI F， XIONG P， JIN C. Identity-based deniable authentication for ad hoc networks［J］.Computing， 2014，96（9）： 843-853.

［12］NAOR M. Deniable ring authentication［C］//Advances in Cryptology， Berlin. c2002：481-498.

［13］BOHLI J M， STEINWANDT R. Deniable group key agreement［C］//Progress in Cryptology， Berlin. c2006：298-311.

［14］SCHNORR C P. Efficient identification and signatures for smart cards［C］//Advances in Cryptology， Berlin. c1989：239-252.

［15］ZHANG Y， WANG K， LI B. A deniable group key establishment protocol in the standard model［C］//Information Security， Practice and Experience， Berlin. c2010： 308-323.

［16］張雅哲， 徐海霞， 李寶. 可否認(rèn)群密鑰協(xié)商協(xié)議的一般化構(gòu)造方式［J］. 通信學(xué)報， 2011，32（3）：143-149. ZHANG Y Z， XU H X， LI B. But denied group key agreement protocol way of generalized structure［J］. Journal of Communications， 2011， 32（3）： 143-149.

［17］STEINWANDT R， CORONA A S. Scalable attribute-based group key establishment： from passive to active and deniable［J］. Applicable Algebra in Engineering， Communication and Computing， 2014，25（1/2）：1-20.

［18］陳勇， 何明星， 曾晟珂， 等. 兩輪次的可否認(rèn)的群密鑰協(xié)商協(xié)議［J］.密碼學(xué)報， 2016，3（2）：137-146. CHEN Y， HE M X， ZENG S K， et al. Two rounds of deniable group key agreement protocol［J］. Journal of Password， 2016， 3（2）：137-146.

［19］DUTTA R， BARUA R. Provably secure constant round contribu-tory group key agreement in dynamic setting［J］. IEEE Transactions on Information Theory， 2008， 54（5）：2007-2025.

［20］CHEN Y， HE M， ZENG S， et al. Universally composable asymmetric group key agreement protocol［C］//The 10th International Conference on Information， Communications and Signal Processing（ICICS）， IEEE. c2015.

［21］CANETTI R. Security and composition of multiparty cryptographic protocols［J］. Journal of Cryptology， 2000， 13（1）：143-202.

［22］FEIGE U， FIAT A， SHAMIR A. Zero-knowledge proofs of identity［J］. Journal of Cryptology， 1988， 1（2）：77-94.

［23］CHAUM D， HEIJST E V， PFITZMANN B. Cryptographically strong undeniable signatures， unconditionally secure for the signer［C］//The 11th Annual International Cryptology Conference on Advances in Cryptology. c1991：470-484.

Deniable authentication for multi-party protocol

CHEN Yong， LU Long， ZENG Sheng-ke， HE Ming-xing

（School of Computer and Software Engineering， Xihua University， Chengdu 610039， China）

Deniable authentication can authenticate messages like digital signatures， and its non-public verification can meet many requirements that cannot be met by signatures， such as privacy preservation. How to achieve deniable authentication with multi-party protocol was the study aim. A deniable authentication for multi-party protocol using string commitment scheme was proposed. As a generic method， it can pass the most of protocol to deniable protocol， such as the deniable group key agreement protocol. The adversarial model was formalized and the security was proved strictly. The research content provide a new idea for studying deniable authentication.

deniable authentication， multi-party protocol， commitment， security

TP393

A

10.11959/j.issn.2096-109x.2016.00059

2015-04-17；

2015-05-25；通信作者：陳勇，chenyong.sclz@gmail.com

國家自然科學(xué)基金資助項目（No.61402376， No.U1433130）；四川省高校重點實驗室開放課題基金資助項目（No.SZJJ2014-078）；國家科技支撐計劃基金資助項目（No.2011BAH26B04）；教育部春暉計劃基金資助項目（No.Z2014045）

Foundation Items： The National Natural Science Foundation of China （No.61402376， No.U1433130）， The Open Research Foundation of Key Laboratory of Colleges and Universities in Sichuan Province （No.SZJJ2014-078）， National Science and Technology Support Program （No.2011BAH26B04）， Chunhui Project of the Ministry of Education of China （No.Z2014045）

陳勇（1991-），男，四川閬中人，西華大學(xué)碩士生，主要研究方向為密碼與信息安全。

魯龍（1989-），男，山東臨沭人，西華大學(xué)碩士生，主要研究方向為密碼與信息安全。

曾晟珂（1982-），女，四川成都人，博士，西華大學(xué)講師，主要研究方向為密碼與信息安全。

何明星（1964-），男，四川巴中人，博士，西華大學(xué)教授，主要研究方向為密碼與信息安全。