Advanced
An Efficient Identity-Based Deniable Authenticated Encryption Scheme
An Efficient Identity-Based Deniable Authenticated Encryption Scheme
KSII Transactions on Internet and Information Systems (TIIS). 2015. May, 9(5): 1904-1919
Copyright © 2015, Korean Society For Internet Information
  • Received : January 07, 2015
  • Accepted : May 03, 2015
  • Published : May 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Weifeng Wu
Fagen Li

Abstract
Deniable authentication protocol allows a sender to deny his/her involvement after the protocol run and a receiver can identify the true source of a given message. Meanwhile, the receiver has no ability to convince any third party of the fact that the message was sent by the specific sender. However, most of the proposed protocols didn’t achieve confidentiality of the transmitted message. But, in some special application scenarios such as e-mail system, electronic voting and Internet negotiations, not only the property of deniable authentication but also message confidentiality are needed. To settle this problem, in this paper, we present a non-interactive identity-based deniable authenticated encryption (IBDAE) scheme using pairings. We give the security model and formal proof of the presented IBDAE scheme in the random oracle model under bilinear Diffie-Hellman (BDH) assumption.
Keywords
1. Introduction
D eniable authentication protocol plays an important role in practice and it is very useful in some special scenarios such as e-mail system, electronic bidding, electronic voting and negotiations over the Internet [1] . Compared with traditional authentication protocol, it has the following two characters: (1) The protocol principals can deny their involvement after the protocol run and the intended receiver can verify the source of a given message. (2) However, the intended receiver cannot convince any third party of the fact that the message was sent by the specific sender, even if fully-cooperate with the third party. Consider the following application scenario.
Electronic voting system: In an electronic voting system, let V be a voter and T be a tallying authority. When V submits his/her ballot m to T, he/she should send m together with the authenticator of m to T, so that T can make sure this ballot really comes from V but not from anyone else. Suppose a third party F compels V to elect a predetermined candidate but V does not want to do so. When V submits his/her ballot m to T in this situation, it is desirable for V to assure that T has no ability to prove the true source of the ballot m to F even if T and F co-operates fully. That is because even if there is full co-operation between T and F, F may also be skeptical of the evidence provided by T. Thus, F cannot force the voter V to elect the candidate predetermined by him/her. And in this way the property of fairness which is very important for electronic voting system is achieved perfectly. Therefore, such a deniable authentication protocol is needed to protect the voter V from coercion in electronic voting system.
However, in some cases, the content of the transmitted message (such as the content of ballot in electronic voting system) in a deniable authentication protocol should only be shared between the sender and intended receiver, any other third party should not have the ability to obtain the transmitted transcripts. That is, we should provide confidentiality to protect confidential data and sensitive information from eavesdropping and network-sniffing attack. We call a cryptographic scheme that achieves simultaneously confidentiality and deniable authentication deniable authenticated encryption (DAE) scheme.
- 1.1 Related Work
Several deniable authentication protocols have been proposed over the past few years. In 1998, Dwork et al. [2] first proposed a deniable authentication protocol based on zero-knowledge. However, the protocol requires a timing constraint, and the proof of knowledge is time-consuming [3] . Later, Aumann and Rabin [4] proposed another scheme based on factoring which needs a public directory trusted by the two communication parties. In 2001, Deng et al. [1] proposed two deniable authentication protocol based on factoring and discrete logarithm problem, respectively, under the communication model defined by Aumann and Rabin in 1998. However, in 2006, Zhu et al. [5] proved that both of the protocols were vulnerable to the person-in-middle (PIM) attack. In 2005, Cao et al. [6] proposed an efficient non-interactive identity-based deniable authentication protocol from pairings. What’s more, the scheme achieves confidentiality by employing a symmetric encryption algorithm. However, in 2006, Chou et al. [7] pointed out that Cao et al.’s scheme suffered from key compromise impersonation (KCI) attack. Then Chou et al. presented a new identity-based deniable authentication protocol from pairings, and claimed that the protocol is secure. But in 2007, Lim et al. [8] proved that Chou et al.’s scheme remains insecure due to the vulnerability to the KCI attack. Moreover, they presented an enhanced scheme. But later in 2008, they found that their enhanced scheme suffered from the insider KCI attack and key replicating attack, and then they repaired the secure flaw in [9] . Unfortunately, in 2011, Tian et al. [10] pointed out that the repaired protocol by Lim et al. was still not secure under a special KCI attack. Besides, in 2005, Shi and Li [11] proposed an identity-based non-interactive deniable authentication protocol in which a signature scheme is needed. And this results in less efficient than scheme in [6] . In 2013, Li et al. [12] proposed an efficient identity-based deniable authentication protocol for ad hoc networks. What’s more, they gave the security model and formal proof of their protocol, and claimed that their protocol met the requirements of batch verification and was faster than all known identity-based deniable authentication protocols.
The concept of identity-based cryptography (IBC) was first introduced by Shamir [13] in 1984, and the original motivation of IBC was to simplify certificate management. In IBC systems, every user’s public keys can be obtained from their public information such as e-mail address, name, telephone number and so on. The certificate is not necessary in an IBC system. However, the first practical identity-based encryption scheme was proposed until 2001 by Boneh and Franklin in [14] using Weil pairing. In an identity-based system, a trusted private key generator (PKG) is required to generate the private key corresponding to some public key of a user, and then PKG sends the private key to the user via a secure channel. However, as we know, most of the existed identity-based deniable authentication protocols transmit the message in plaintext form over an insecure public network which does not meet our requirements in practice. During the schemes mentioned above, only scheme in [6] achieved message confidentiality along with deniable authentication. It is desirable to design a new kind of protocol that achieves both properties of deniable authentication and confidentiality simultaneously within one logical step. Motivated by the advantages of IBC, in this paper, we present an IBDAE scheme with pairings that can meet the requirements in practice.
- 1.2 Contribution
In this paper, we first define a security model for IBDAE scheme and then present an IBDAE scheme using bilinear pairings. Next, we give the formal proof of our scheme in the random oracle model under the BDH assumption. After that, we compare the performance of our IBDAE scheme with the other three identity-based deniable authentication protocols. Generally speaking, our IBDAE scheme achieves the following three properties simultaneously:
Confidentiality: This property assures that only the intended receiver can share the transmitted message with the sender, any third person has no ability to gain the transmitted transcripts.
Deniability: The sender of the protocol can later deny the authorship of the transmitted message and even deny having taken part in the communication run. At the same time, the intended receiver can identify the true source of a given message, but he/she cannot prove this fact to any other third party.
Authentication: This property assures that the protocol principal is actually the person he/she claims to be, rather than another third person or an adversary.
- 1.3 Organization
This paper is organized as follows. In Section 2, we introduce the preliminary work that will be used later in this paper. In Section 3, we define the security model of IBDAE, and our scheme is presented in Section 4. In Section 5, we provide the security proof of the proposed scheme and compare its performance with other schemes. Finally, we draw the conclusions in Section 6.
2. Preliminaries
In this section, we simply review the basic concept and some properties of bilinear pairings.
Let G 1 be a cyclic additive group generated by P , whose order is a prime q , and G 2 be a cyclic multiplicative group of the same order q . A bilinear pairings is a map ê : G 1 × G 1 G 2 , which satisfies the following three properties:
  • (1) Bilinear:ê(aP, bQ)=ê(P, Q)abfor allP, Q∈G1.
  • (2) Non-degeneracy: There existsP, Q∈G1such thatê(P, Q)≠1.
  • (3) Computability: There is an efficient algorithm to computeê(P, Q) for allP, Q∈G1.
A bilinear pairings that satisfies the three properties above is said to be an admissible bilinear pairings, and the modified Weil pairing or Tate pairing are admissible maps of this kind. There is a more concrete description in [14] . The security of our IBDAE scheme relies on the following two related mathematical problems in G 1 .
  • (1) Discrete Logarithm Problem (DLP): GivenP, Q∈G1, find an integera, such thatQ=aP, whenever such an integer exists.
  • (2)Bilinear Diffie-Hellman Problem (BDHP): GivenP, aP, bP, cP∈G1, computes ê(P, P)abc∈G2, where
3. Formal Model for IBDAE
- 3.1 Syntax
A generic IBDAE scheme consists of four algorithms: system setup ( Setup ) algorithm, key extraction algorithm ( Extract ), identity-based deniable authenticated encryption ( IBDAE ) algorithm and identity-based deniable authenticated decryption ( IBDAD ) algorithm. Now, we describe these algorithms as follows.
Setup is a probabilistic algorithm run by PKG that takes as input a security parameter k , and outputs the system parameters param , a master public key Ppub and a master secret key s , In this paper, we simplify the input of other algorithms by assuming that the system parameters param are public, thus we do not need to contain them in other algorithms.
Extract is a key extraction algorithm run by PKG that takes as input an identity ID and the master secret key s and outputs the private key SID corresponding to ID . Then PKG transmits this private key to the user of identity ID via a secure channel.
IBDAE is a probabilistic algorithm run by a sender that takes as input a message m , a sender’s private key SS , the identities of a sender and receiver IDS and IDR , and outputs an IBDAE authenticator δ =IBDAE ( m , SS , IDS , IDR ).
IBDAD is a deterministic decryption and verification algorithm run by a receiver that takes as input an IBDAE authenticator δ , a receiver’s private key SR , the identity IDR of a receiver and outputs the recovered message m from IBDAD ( δ , SR , IDR ) if δ is a valid IBDAE authenticator of m between the sender and receiver. Otherwise, an error symbol ▲will be output.
The algorithms above must have the following consistency requirements. If δ =IBDAE ( m , SS , IDS , IDR ), then we must have m = IBDAD ( δ , SR , IDR ) holds.
- 3.2 Security Model
(1) Confidentiality of IBDAE: The security notion of confidentiality of an IBDAE scheme is called ciphertext indistinguishability against adaptive chosen ciphertext attacks (IND-IBDAE-CCA2). Here, we consider the following game played between a challenger Χ and an adversary Α.
Initial: Χ runs Setup algorithm that takes as input a security parameter k and sends the system parameters param to Α, while keeps the master secret key s secret.
Phase 1: Α performs a polynomial bounded number of key extraction queries, deniable authenticated encryption queries and deniable authenticated decryption queries in an adaptive way as follows.
① In a key extraction query, Α submits an identity ID to Χ, then Χ runs Extract algorithm to obtain the corresponding private key SID and sends it to the adversary Α.
② In a deniable authenticated encryption query, Α selects a sender’s identity IDi , a receiver’s identity IDj , a plaintext m and sends them to the challenger Χ. Χ first runs Extract algorithm to obtain the private key Si corresponding to IDi and then sends the result of δ =IBDAE ( m , Si , IDi , IDj ) to Α.
③ In a deniable authenticated decryption query, the adversary Α submits an IBDAE authenticator δ and a receiver’s identity IDj to Χ, then Χ runs Extract algorithm to obtain the receiver’s private key Sj . After that, Χ sends the result of IBDAD ( δ , S j , IDj ) to Α.
Challenge: Once Α decides that Phase 1 is over, he/she outputs two plaintexts m 0 , m 1 with equal length, and two identities IDS , IDR that haven’t made key extraction queries. Then Α sends them to the challenger Χ. Χ randomly chooses a bit k ∈{0,1}, computes δ = IBDAE ( mk, SS, IDS, IDR ), and sends δ to Α as his challenge.
Phase 2: Α can issue more polynomial bounded queries like Phase 1, but in this phase, Α can not make key extraction queries on identities IDS and IDR . Meanwhile he can’t make IBDAD queries on his challenge δ either.
Guess: Finally, Α outputs a bit k 1 ∈{0,1}. If k 1 = k , we say Α wins the game.
We define the advantage of Α as the probability |Pr[ k 1 = k ]-1/2|.
(2) Unforgeability of IBDAE: We borrow the concept of unforgeability against adaptive chosen messages attacks in digital signature to define this security notion. However, the security notion in IBDAE scheme is essentially different from that in a digital signature scheme. That is because only the sender with correct private key has the ability to generate a valid signature in digital signature, while in an IBDAE scheme, both the sender and the receiver have ability to generate a valid IBDAE authenticator. We call this security notion deniable authentication against adaptive chosen messages attacks (DA-IBDAE-CMA). Here, we consider the following game played between a challenger Χ and an adversary Φ.
Initial: Χ runs Setup algorithm that takes as input a security parameter k and sends the system parameters param to Φ, while keeps the master secret key s secret.
Attack: Φ performs a polynomial bounded number of key extraction queries, deniable authenticated encryption queries and deniable authenticated decryption queries as Phase 1 in the model of confidentiality above.
Forgery: Φ outputs an IBDAE authenticator δ * and two identities IDS and IDR . Φ wins the game if the following three conditions hold:
δ * is a valid IBDAE authenticator with identities IDS and IDR , it means that the result of IBDAD ( δ * , SR, IDR ) doesn’t be an error symbol ▲.
② Φ has not made key extraction queries on identities IDS and IDR .
③ Φ has not made a deniable authenticated encryption query with a message m* and identities IDS , IDR .
We define the advantage of Φ as the probability that it wins in the game. In order to achieve the property of deniability in an IBDAE scheme, we require that Φ should not have made key extraction queries on both identities IDS and IDR in the second step of the three conditions. It is because the receiver can also generate a valid IBDAE authenticator.
4. Proposed IBDAE Scheme
In this section, we give the precise algorithms of our IBDAE scheme with bilinear pairings. Our scheme consists of the following four algorithms.
Setup : Suppose k is a secure parameter, G 1 is a cyclic additive group generated by P and G 2 is a cyclic multiplicative group, both groups have the same prime order q ( q 2k ) and the discrete logarithm problems in both G 1 and G 2 are hard when k≥160. A bilinear map is ê : G 1 × G 1 G 2 . Let H , H 1 , H 2 be three security cryptographic hash functions where H :{0,1}*→ G 1 , H 1 : G 2 →{0,1} lm+lID and
PPT Slide
Lager Image
in which lm denotes the length of message and lID denotes the length of an identity string. The PKG randomly chooses a master secret key
PPT Slide
Lager Image
and computes Ppub = sP . PKG publishes the system parameters param ={ G 1 , G 2 , P , Ppub , ê , q , lm , lID , H , H 1 , H 2 }, while keeps the master secret key s secret.
Extract : Given an identity ID , PKG computes the private key corresponding to ID as SID = sQID , where QID = H ( ID ) is the public key of the identity ID . Then PKG sends the private key SID to the user via a security channel. Throughout this paper, we assume that the public/private key pairs of the sender and receiver are ( QS, SS ) and ( QR, SR ), respectively.
IBDAE : Given a message m , a sender’s private key SS , the identities of a sender and receiver IDS and IDR , this algorithm works as follows.
  • (1) Chooserandomly, computeU=rQSandT=ê(SS,QR)r.
  • (2) ComputeC=H1(T)⊕(m||DS).
  • (3) Computeh=H2(m||IDS||IDR,U).
  • (4) ComputeV=ê((r+h)SS,QR).
Then the sender sends the IBDAE authenticator δ =( U,C,V ) to the receiver.
IBDAD : After receiving the IBDAE authenticator δ =( U,C,V ), the receiver performs IBDAD algorithm with his/her private key SR and identity IDR as follows.
  • (1) Compute (m||IDS)=H1(ê(U,SR))⊕Cto recover plaintext and sender’s identitym||IDS.
  • (2) Computeh=H2(m||IDS||IDR,U).
  • (3) Check ifV=ê(U+hQS,SR) holds. If yes, accept the recovered messagem, otherwise, this algorithm outputs an error symbol ▲.
5. Analysis of Scheme
- 5.1 Security
The consistency of our scheme is obvious, so we mainly analyze the deniability, confidentiality and deniable authentication of our scheme in this section.
- 5.1.1 Deniability
Proof: Our scheme achieves the property of deniability since the receiver can also generate a valid IBDAE authenticator that indistinguishable from that of a sender for the following reasons.
(1) After receiving the IBDAE authenticator δ =( U,C,V ) from a sender, the receiver can obtain the recovered message m by running IBDAD algorithm. Then he/she performs the processes as follows.
  • ①C1=H1(ê(U,SR))⊕(m||IDS).
  • ②h=H2(m||IDS||IDR,U).
  • ③V1=ê(U+hQS,SR).
It’s obvious that even if for the same message m , δ 1 =( U , C 1 , V 1 ) is indistinguishable from δ =( U,C,V ) for any third party.
(2) The receiver can also chooses a random number
PPT Slide
Lager Image
and computes U 1 = r 1 QS , then performs as (1) above. The output of this situation will be δ 1 =( U 1 , C 1 , V 1 ) which also indistinguishable from δ =( U,C,V ).
- 5.1.2 Confidentiality
Theorem 1 In random oracle model, if there exists an adversary Α that wins IND-IBDAE-CCA2 game with advantage ε within time t for a security parameter k and consults at most qH queries to oracles H , qHi queries to oracles Hi ( i =1,2), qk key extraction queries, qE DAE queries and qD DAD queries. Then there exists an algorithm Χ that can solve the BDH problem in time t + O ( qE + qD ) Te ( Te denotes the computation time of bilinear map) with advantage
PPT Slide
Lager Image
Proof: We can prove the confidentiality of our scheme via the game defined in section three. If there is an adversary Α that can break the scheme, we can use Α to build a new algorithm Χ to solve the BDH problem. Next we show how Χ solves the BDH problem which means Χ takes as input ( P,aP,bP,cP ) and outputs ê (P,P) abc by interacting with Α. In the following game, Χ acts as the challenger of Α. Α will consult Χ for the answers of the random oracles H , H 1 and H 2 . To track the queries of H , H 1 and H 2 , Χ maintains three lists L , L 1 , L 2 to store the answers respectively. The three lists are all empty at first. We describe the processes as follows.
Initial: Χ runs Setup algorithm that takes as input a security parameter k and sends the system parameters param in which Ppub = cP ( c plays as the master secret key and Χ knows nothing about c ) to Α.
Phase 1: Α performs a polynomial bounded number of the following queries.
(1) H queries: At first, the challenger Χ chooses two different numbers N 1 , N 2 ∈{1,2,…, qH }. At the N 1 -th query of H , Χ answers H ( ID N1 )= aP , while at the N 2 -th query of H , Χ answers H ( ID N2 )= bP . For an identity IDi ( i ∈{1,2,…, qH } and i N 1 , N 2 ) given by Α, Χ first looks up the list L and checks if the value of H ( IDi ) was previously defined. If it was, the previous defined value will be the result of this query. Otherwise, Χ chooses a random number
PPT Slide
Lager Image
, inserts the 2- tuples ( IDi , ni ) into L , and returns H ( IDi )= niP as the result of this query.
(2) H1 queries: For a query of H 1 ( Ti ), Χ first looks up list L 1 , and checks if there exists a previous defined value of H 1 ( Ti ). If it was, the existed value will be returned as the result of this query. Otherwise, Χ selects a random value H 1 i ∈{0,1} lm+lID and inserts 2- tuples ( Ti , H 1 i ) into list L 1 . Then he/she sets H 1 ( Ti )= H 1 i as the result of this query.
(3) H2 queries: For a query of H 2 ( mi || IDi || IDj , Ui ), Χ first checks if the value of ( mi || IDi || IDj , Ui ) was previously defined in list L 2 . If it was, the previous defined value will be returned as the result of the query. Otherwise, Χ returns a random number
PPT Slide
Lager Image
as the answer of the query and inserts the tuples ( mi || IDi || IDj , Ui , hi ) into list L 2 .
(4) Key extraction queries: Α submits an identity IDi to Χ, Χ fails and terminates if i = N 1 or i = N 2 . Otherwise, Χ first looks up the list L to obtain the value ni where H ( IDi )= niP , computes the corresponding private key Si = niPpub and sends it to the adversary Α. The probability of fail in key extraction queries is at most 2/ qH
(5) Deniable authenticated encryption queries: Α submits a sender’s identity IDi , a receiver’s identity IDj and a plaintext m to Χ. If i N 1 , N 2 , Χ first obtains the private key Si = niPpub , runs IBDAE algorithm and sends the result δ =IBDAE ( m, Si, IDi, IDj ) to Α. If i = N 1 or i = N 2 , but j N 1 , N 2 , Χ obtains the private key Sj=njPpub , then he/she chooses
PPT Slide
Lager Image
and computes U = rQi , C = H 1 ( ê ( U,Sj ))⊕( m || IDi ). After that, Χ runs the H 2 simulation algorithm to obtain h , then computes V = ê ( U + hQi,Sj ) At last, Χ sends δ =( U,C,V ) to Α. However, if i = N 1 and j = N 2 (or j = N 1 and i = N 2 ), Χ chooses r ,
PPT Slide
Lager Image
and and sets U = rP - hQi , W = rPpub , at the same time he defines H 2 ( m || IDi || IDj , U )= h and inserts the tuple ( m || IDi || IDj , U , h ) into list L 2 . After that, Χ computes V = ê ( W,Qj ). Besides, Χ chooses a random value C ∈{0,1} lm+lID and computes H 1 ( T )= C ⊕( m || IDi ),
PPT Slide
Lager Image
At the same time, Χ inserts the 2- tuples ( T , H 1 ( T )) into list L 1 . Finally, Χ sends δ =( U,C,V ) to Α. Χ fails and terminates if the values of H 1 , H 2 are already defined. And the probability of fail in this phase is at most
PPT Slide
Lager Image
.
(6) Deniable authenticated decryption queries: Α submits an IBDAE authenticator δ =( U,C,V ) and a receiver’s identity IDj to Χ. If j N 1 and j N 2 , Χ obtains the receiver’s private key Sj = njPpub , computes Tj = ê ( U,Sj ) and runs the H 1 simulation algorithm to obtain H 1 ( Tj ). After that, Χ computes ( m || IDi )= H 1 ( Tj )⊕ C to recover m || IDi , runs the H 2 simulation algorithm to obtain h = H 2 ( m || IDi || IDj , U ), and then computes V 1 = ê ( U + hQi , Sj ). Χ sends the recovered message m to Α if V 1 = V holds. Otherwise Χ tells Α that the IBDAE authenticator is invalid and returns an error symbol ▲ to Α. However, if j = N 1 or j = N 2 , Χ will always tell the adversary Α that the IBDAE authenticator is invalid as Χ can’t compute the private key of IDj . The probability of fail in this situation is at most qD /2 k .
Challenge: Once Α decides that Phase 1 is over, he outputs two plaintexts m 0 , m 1 with equal length, and two identities IDS , IDR that didn’t make key extraction query. Χ fails if Α consults Χ for H ( IDS ) or H ( IDR ) during the game. However, if IDS and IDR are not identities ID N1 and ID N2 ( S N 1 , R N 2 or S N 2 , R N 1 ), Χ fails either. To compute the IBDAE authenticator, Χ performs as follows.
(1) Χ chooses
PPT Slide
Lager Image
TS G 2 randomly and computes U = raP . Then Χ runs the H 1 simulation algorithm to obtain H 1 ( TS ) and computes C = H 1 ( TS )⊕( mγ || IDS ) where γ ∈0,1 was chosen by Χ randomly.
(2) Χ runs the H 2 simulation algorithm to obtain h = H 2 ( mγ || IDS || IDR , U ) and computes V =( TS ) r-1(r+h) . Finally, Χ sends the IBDAE authenticator δ =(U,C,V) to the adversary Α as his challenge.
Phase 2: Α can issue more polynomial bounded queries like Phase 1, but Α can not make key extraction queries on identities IDS and IDR , meanwhile he can’t make deniable authenticated decryption query on the challenge δ either.
Guess: Finally, Α outputs a bit γ' ∈{0,1}. If γ' = γ , X outputs ( TS ) r-1 = ê ( P,P ) abc .
To calculate the value of Adv(Χ), we take into consideration all the probabilities that Χ does not fail in the simulation above, the probability that the two challenged identities chosen by Α are ID N1 and ID N2 and the probability that Α wins the IND-IBDAE-CCA2 game. The value of Adv(Χ) is calculated as follows.
PPT Slide
Lager Image
Thus, Χ solves the BDH problem under the help of Α. However, as we assume that the BDH problem is hard and there is no efficient algorithm to solve the BDH problem at present, therefore, the adversary Α doesn’t actually exist and the confidentiality of our scheme is proved.
- 5.1.3 Deniable Authentication
Theorem 2 In random oracle model, if there is an adversary Φ can win the DA-IBDAE-CMA game with advantage ε ≥5( qE +1)( qE + qH2 ) qH /(2 k -1) within time t for a security parameter k and consult at most qH queries to oracles H , qHi queries to oracles Hi ( i =1,2), qK Kqkey extraction queries, qE DAE queries and qD DAD queries. Then there exists an algorithm Χ that can solve BDH problem within an expected time t' ≤60343 q H2 qH 2 k t / ε (2 k -1).
Proof: We prove the deniable authentication of our scheme via the game defined in section three that played between a challenger Χ and an adversary Φ. If there exists an adversary Φ that can break the scheme, we can use Φ to build a new algorithm Χ to solve BDH problem. Just like the proof of confidentiality above, Χ maintains three lists L , L 1 , L 2 to store the answers of the random oracles H , H 1 and H 2 during the game, respectively. The processes of the game are described as follows.
Initial: Χ runs Setup algorithm that takes as input a security parameter k and sends the system parameters param in which Ppub = cP ( c plays as the master secret key and Χ knows nothing about c ) to Φ.
Attack: Φ performs a polynomial bounded number of H queries, H 1 queries, H 2 queries, key extraction queries, deniable authenticated encryption queries and deniable authenticated decryption queries like those in Phase 1 of the proof of confidentiality above.
Forgery: Φ outputs an IBDAE authenticator δ * =( U * , C * , V * ) and two identities IDS and IDR . From the forking lemma [15] , if Φ is an efficient forger during the interaction above, we can construct a Las Vegas machine Φ 1 that outputs two results ( IDS , IDR , C * , h * , V * ) and ( IDS , IDR , C * , h 1 * , V 1 * ) where h * h 1 * with the same U * . Χ solves the BDH problem by computing
PPT Slide
Lager Image
when S = N 1 and R = N 2 (or R = N 1 and S = N 2 ) in the game above.
Now we consider the advantage of Χ. From the forking lemma [15] and the lemma on the relationship between given identity attack and chosen-identity attack [16] , if Φ succeeds in time t with probability ε ≥5( qE +1)( qE + qH2 ) qH /(2 k -1), then Χ can solve the BDH problem in expected time t' ≤60343 q H2 qH 2 k t / ε (2 k -1). However, since we assume that the BDH problem is hard and there is no efficient algorithm to solve the BDH problem at present, there doesn’t actually exist such an adversary Φ. Thus we prove the deniable authentication of our scheme.
- 5.2 Analysis of Performance
In this section, we compare the performance of our scheme with those in [6 , 7] and [12] . With regard to the major computational cost, we can see more details from Table 1 , and we denote by AD the point addition in G 1 , PM the point multiplication in G 1 , EXP the exponentiation in G 2 , P the pairing computation, CS the computational cost of the sender and CR the computational cost of the receiver in the table. The other operations are omitted for they are trivial. Besides, we assume that | G 1 |=1024 bits, | G 2 |=1024 bits,
PPT Slide
Lager Image
bits, | m |=160 bits, | ID |=160 bits and hash value =160 bits. The total communication size of Cao et al. [6] is
PPT Slide
Lager Image
bits, the total communication size of Chou et al. [7] is
PPT Slide
Lager Image
bits and both the communication sizes of Li et al. [12] and ours are | ID |+| G 1 |+| m |+| G 2 |=2368 bits. We can refer to Fig.1 for the comparison of the communication size. The presented scheme in this paper has a little higher communication cost for the IBDAE authenticator contains an element in G 2 . Although the scheme of Cao et al. [6] achieves confidentiality by employing a symmetric encryption algorithm, it suffers from the problem of key distribution in symmetric cryptography before a communication setups. However, our scheme overcomes this weakness by using identity-based encryption algorithm. Meanwhile, the schemes of Chou et al. [7] and Li et al. [12] transmit message in an unencrypted form which may cause a big security flaw in practice.
Performance Comparison
PPT Slide
Lager Image
Performance Comparison
PPT Slide
Lager Image
Communication Size
For non-interactive deniable authentication protocol, we should consider the weaken-key compromise impersonation [17] (W-KCI) instead of KCI attack. In a W-KCI attack, the compromising long-term private key of a receiver can make an adversary have the ability to masquerade other users to cheat the receiver, however, the adversary cannot masquerade other users to cheat a sender when the sender’s long-term private key is compromised. In our presented scheme, the adversary can masquerade a sender with identity IDs and generate a valid DAE authenticator δ as follows when the private key of a receiver SR is compromised.
  • (1) Choose a random numberand computeU=rQS.
  • (2)C=H1(ê(U,SR))⊕(m||IDS).
  • (3)h=H2(m||IDS||IDR,U).
  • (4)V=ê(U+hQS,SR).
Thus the adversary can cheat the receiver while the receiver cannot detect this attack. However, even if the private key of the sender SS is compromised, our scheme is also secure against W-KCI attack for the following two reasons: (1) When the adversary received a DAE authenticator δ from the sender, he/she cannot recover the plaintext m from δ for he/she doesn't know any information about SR . Besides, he/she knows nothing about r from U = rQS under the assumption of DLP, so it is impossible for him/her to obtain the value T = ê ( SS,QR ) r from U which means the adversary cannot recover m . (2) As the adversary knows nothing about the recovered plaintext m, he/she has no ability to compute h = H 2 ( m || IDS || IDR , U ) and V = ê ( U + hQS , SR ) even if he/she possesses the long-term private key Ss . After our analysis, we find that Li et al.’s scheme is secure against W-KCI attack, but Cao et al.’s scheme is insecurity against W-KCI and the interactive scheme of Chou et al. [7] is insecurity against KCI either.
We implement the four schemes using Type A pairing in PBC library [18] and obtain the precise computational cost that described in Fig. 2 . Type A pairing is constructed on the curve y 2 x 3 + x (mod p ) for some prime p ≡3 mod 4. The embedding degree is 2. G 1 is a group of points on the curve over a base field F p and G 2 is a subgroup of finite field
PPT Slide
Lager Image
The group order q is some prime factor of ( p +1) and q is 160 bits long.
PPT Slide
Lager Image
Major Computational Cost
From Fig. 2 we know that: CS is 43.174ms and CR is 43.369ms in [6] ; CS is 134.33ms and CR is 112.288ms in [7] ; CS is 43.937ms and CR is 33.021ms in [12] , CS is 69.957ms and CR is 55.026ms in our scheme. The implement environment is: Pentium(R) Dual E5500 @2.80GHz of processor, memory of 2GB and OS with Microsoft Windows XP. Generally speaking, our scheme achieves all properties list in Table 1 with an admissible computational cost and communication size.
6. Conclusion
In this paper, we present a non-interactive IBDAE scheme from bilinear pairings. We defined a formal security model of the IBDAE scheme and gave the security proof under the BDH assumption in the random oracle model. Our scheme can not only achieve the property of deniable authentication but also obtain the property of confidentiality. So it is suitable for some special application scenarios that need the requirement of message confidentiality while deniable authentication.
BIO
Weifeng Wu received his B.S. degree in College of Science from Henan Agricultural University, Zhengzhou, P.R. China, in 2008. Now, he is studying in School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, P.R. China, for M.S. degree. His current research interests include computer science and cryptography.
Fagen Li received his B.S. degree from Luoyang Institute of Technology, Luoyang, P.R. China, in 2001, M.S. degree from Hebei University of Technology, Tianjin, P.R. China, in 2004, and Ph.D. degree in Cryptography from Xidian University, Xi'an, P.R. China, in 2007. From 2008 to 2009, he was a postdoctoral fellow in Future University-Hakodate, Hokkaido, Japan, which is supported by the Japan Society for the Promotion of Science. He worked as a research fellow in the Institute of Mathematics for Industry, Kyushu University, Fukuoka, Japan from 2010 to 2012. He is now an associate professor in the School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, P.R. China. His recent research interests include cryptography and network security. He has published more than 70 papers in the international journals and conferences.
References
Deng X. , Lee C. H. , Zhu H. 2001 “Deniable authentication protocols,” IEEE Proceedings-Computers and Digital Techniques 148 (2) 101 - 104    DOI : 10.1049/ip-cdt:20010207
Dwork C. , Naor M. , Sahai A. “Concurrent zero-knowledge,” in Proc. of the thirtieth annual ACM symposium on Theory of computing 1998 409 - 418
Ibrahim M. H. 2009 “Receiver-deniable public-key encryption,” International Journal of Network Security 8 (2) 159 - 165
Aumann Y. , Rabin M. O. “Efficient Deniable Authentication of Long Messages Int,” in Proc. of Conf. on Theoretical Computer Science in honour of Professor Manuel Blums 60th birthday 1998 20 - 24
Zhu R. W. , Wong D. S. , Lee C. H. 2006 “Cryptanalysis of a suite of deniable authentication protocols,” IEEE Communications Letters 10 (6) 504 - 506    DOI : 10.1109/LCOMM.2006.1638630
Cao T. , Lin D. , Xue R. “An efficient ID-based deniable authentication protocol from pairings,” in Proc. of 19th International Conference on Advanced Information Networking and Applications 2005 388 - 391
Chou J. S. , Chen Y. , Huang J. C. 2006 “An ID-Based deniable authentication protocol on pairings,” IACR Cryptology ePrint Archive
Lim M. H. , Lee S. , Park Y. “An enhanced ID-based deniable authentication protocol on pairings,” in Proc. of International Conference on Computational Science and Its Applications 2007 1008 - 1017
Lim M. H. , Lee S. , Lee H. “Cryptanalysis on improved Chou et al.’s ID-Based deniable authentication protocol,” IEEE International Conference on Information Science and Security 2008 87 - 93
Tian H. , Chen X. , Ding Y. 2009 “Analysis of two types deniable authentication protocols,” International Journal of Network Security 9 (3) 242 - 246
Shi Y. , Li J. 2005 “Identity-based deniable authentication protocol,” Electronics Letters 41 (5) 241 - 242    DOI : 10.1049/el:20047017
Li F. , Xiong P. , Jin C. 2014 “Identity-based deniable authentication for ad hoc networks,” Computing 96 (9) 843 - 853    DOI : 10.1007/s00607-013-0321-5
Shamir A. “Identity-based cryptosystems and signature schemes,” in Proc. of CRYPTO 84 on Advances in cryptology 1985 47 - 53
Boneh D. , Franklin M. “Identity-based encryption from the Weil pairing,” 21st Annual International Cryptology Conference on Advances in Cryptology—CRYPTO 2001 2001 213 - 229
Pointcheval D. , Stern J. 2000 “Security arguments for digital signatures and blind signatures,” Journal of cryptology 13 (3) 361 - 396    DOI : 10.1007/s001450010003
Choon J. C. , Cheon J. H. “An identity-based signature from gap Diffie-Hellman groups,” in Proc. of 6th International Workshop on Practice and Theory in Public Key Cryptography 2002 18 - 30
Fan C. , Zhou S. , Li F. “An identity-based restricted deniable authentication protocol,” IEEE International Symposium on Parallel and Distributed Processing with Applications 2009 474 - 478
http://crypto.stanford.edu/pbc/