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 email 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 noninteractive identitybased 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 DiffieHellman (BDH) assumption.
1. Introduction
D
eniable authentication protocol plays an important role in practice and it is very useful in some special scenarios such as email 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 fullycooperate 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 cooperates fully. That is because even if there is full cooperation 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 networksniffing 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 zeroknowledge. However, the protocol requires a timing constraint, and the proof of knowledge is timeconsuming
[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 personinmiddle (PIM) attack. In 2005, Cao et al.
[6]
proposed an efficient noninteractive identitybased 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 identitybased 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 identitybased noninteractive 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 identitybased 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 identitybased deniable authentication protocols.
The concept of identitybased 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 email address, name, telephone number and so on. The certificate is not necessary in an IBC system. However, the first practical identitybased encryption scheme was proposed until 2001 by Boneh and Franklin in
[14]
using Weil pairing. In an identitybased 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 identitybased 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 identitybased 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) Nondegeneracy: 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 DiffieHellman 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
), identitybased deniable authenticated encryption (
IBDAE
) algorithm and identitybased 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
P_{pub}
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
S_{ID}
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
S_{S}
, the identities of a sender and receiver
ID_{S}
and
ID_{R}
, and outputs an IBDAE authenticator
δ
=IBDAE (
m
,
S_{S}
,
ID_{S}
,
ID_{R}
).
IBDAD
is a deterministic decryption and verification algorithm run by a receiver that takes as input an IBDAE authenticator
δ
, a receiver’s private key
S_{R}
, the identity
ID_{R}
of a receiver and outputs the recovered message
m
from IBDAD (
δ
,
S_{R}
,
ID_{R}
) 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
,
S_{S}
,
ID_{S}
,
ID_{R}
), then we must have
m
= IBDAD (
δ
,
S_{R}
,
ID_{R}
) 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 (INDIBDAECCA2). 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
S_{ID}
and sends it to the adversary Α.
② In a deniable authenticated encryption query, Α selects a sender’s identity
ID_{i}
, a receiver’s identity
ID_{j}
, a plaintext
m
and sends them to the challenger Χ. Χ first runs
Extract
algorithm to obtain the private key
S_{i}
corresponding to
ID_{i}
and then sends the result of
δ
=IBDAE (
m
,
S_{i}
,
ID_{i}
,
ID_{j}
) to Α.
③ In a deniable authenticated decryption query, the adversary Α submits an IBDAE authenticator
δ
and a receiver’s identity
ID_{j}
to Χ, then Χ runs
Extract
algorithm to obtain the receiver’s private key
S_{j}
. After that, Χ sends the result of IBDAD (
δ
, S
_{j}
,
ID_{j}
) to Α.
Challenge: Once Α decides that Phase 1 is over, he/she outputs two plaintexts
m
_{0}
,
m
_{1}
with equal length, and two identities
ID_{S}
,
ID_{R}
that haven’t made key extraction queries. Then Α sends them to the challenger Χ. Χ randomly chooses a bit
k
∈{0,1}, computes
δ
= IBDAE (
m_{k}, S_{S}, ID_{S}, ID_{R}
), 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
ID_{S}
and
ID_{R}
. 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 (DAIBDAECMA). 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
ID_{S}
and
ID_{R}
. Φ wins the game if the following three conditions hold:
①
δ
^{*}
is a valid IBDAE authenticator with identities
ID_{S}
and
ID_{R}
, it means that the result of IBDAD (
δ
^{*}
,
S_{R}, ID_{R}
) doesn’t be an error symbol ▲.
② Φ has not made key extraction queries on identities
ID_{S}
and
ID_{R}
.
③ Φ has not made a deniable authenticated encryption query with a message
m^{*}
and identities
ID_{S}
,
ID_{R}
.
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
ID_{S}
and
ID_{R}
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
≥
2^{k}
) 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
in which
l_{m}
denotes the length of message and
l_{ID}
denotes the length of an identity string. The PKG randomly chooses a master secret key
and computes
P_{pub}
=
sP
. PKG publishes the system parameters
param
={
G
_{1}
,
G
_{2}
,
P
,
P_{pub}
,
ê
,
q
,
l_{m}
,
l_{ID}
,
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
S_{ID}
=
sQ_{ID}
, where
Q_{ID}
=
H
(
ID
) is the public key of the identity
ID
. Then PKG sends the private key
S_{ID}
to the user via a security channel. Throughout this paper, we assume that the public/private key pairs of the sender and receiver are (
Q_{S}, S_{S}
) and (
Q_{R}, S_{R}
), respectively.
IBDAE
: Given a message
m
, a sender’s private key
S_{S}
, the identities of a sender and receiver
ID_{S}
and
ID_{R}
, this algorithm works as follows.

(1) Chooserandomly, computeU=rQSandT=ê(SS,QR)r.

(2) ComputeC=H1(T)⊕(mDS).

(3) Computeh=H2(mIDSIDR,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
S_{R}
and identity
ID_{R}
as follows.

(1) Compute (mIDS)=H1(ê(U,SR))⊕Cto recover plaintext and sender’s identitymIDS.

(2) Computeh=H2(mIDSIDR,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))⊕(mIDS).

②h=H2(mIDSIDR,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
and computes
U
_{1}
=
r
_{1}
Q_{S}
, 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 INDIBDAECCA2 game with advantage
ε
within time
t
for a security parameter
k
and consults at most
q_{H}
queries to oracles
H
,
q_{Hi}
queries to oracles
H_{i}
(
i
=1,2),
q_{k}
key extraction queries,
q_{E}
DAE queries and
q_{D}
DAD queries. Then there exists an algorithm Χ that can solve the BDH problem in time
t
+
O
(
q_{E}
+
q_{D}
)
T_{e}
(
T_{e}
denotes the computation time of bilinear map) with advantage
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
P_{pub}
=
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,…,
q_{H}
}. 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
ID_{i}
(
i
∈{1,2,…,
q_{H}
} and
i
≠
N
_{1}
,
N
_{2}
) given by Α, Χ first looks up the list
L
and checks if the value of
H
(
ID_{i}
) was previously defined. If it was, the previous defined value will be the result of this query. Otherwise, Χ chooses a random number
, inserts the 2 tuples (
ID_{i}
,
n_{i}
) into
L
, and returns
H
(
ID_{i}
)=
n_{i}P
as the result of this query.
(2)
H_{1}
queries: For a query of
H
_{1}
(
T_{i}
), Χ first looks up list
L
_{1}
, and checks if there exists a previous defined value of
H
_{1}
(
T_{i}
). 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 (
T_{i}
,
H
_{1}
^{i}
) into list
L
_{1}
. Then he/she sets
H
_{1}
(
T_{i}
)=
H
_{1}
^{i}
as the result of this query.
(3)
H_{2}
queries: For a query of
H
_{2}
(
m_{i}

ID_{i}

ID_{j}
,
U_{i}
), Χ first checks if the value of (
m_{i}

ID_{i}

ID_{j}
,
U_{i}
) 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
as the answer of the query and inserts the tuples (
m_{i}

ID_{i}

ID_{j}
,
U_{i}
,
h_{i}
) into list
L
_{2}
.
(4) Key extraction queries: Α submits an identity
ID_{i}
to Χ, Χ fails and terminates if
i
=
N
_{1}
or
i
=
N
_{2}
. Otherwise, Χ first looks up the list
L
to obtain the value
n_{i}
where
H
(
ID_{i}
)=
n_{i}P
, computes the corresponding private key
S_{i}
=
n_{i}P_{pub}
and sends it to the adversary Α. The probability of fail in key extraction queries is at most 2/
q_{H}
(5) Deniable authenticated encryption queries: Α submits a sender’s identity
ID_{i}
, a receiver’s identity
ID_{j}
and a plaintext
m
to Χ. If
i
≠
N
_{1}
,
N
_{2}
, Χ first obtains the private key
S_{i}
=
n_{i}P_{pub}
, runs
IBDAE
algorithm and sends the result
δ
=IBDAE (
m, S_{i}, ID_{i}, ID_{j}
) to Α. If
i
=
N
_{1}
or
i
=
N
_{2}
, but
j
≠
N
_{1}
,
N
_{2}
, Χ obtains the private key
S_{j}=n_{j}P_{pub}
, then he/she chooses
and computes
U
=
rQ_{i}
,
C
=
H
_{1}
(
ê
(
U,S_{j}
))⊕(
m

ID_{i}
). After that, Χ runs the
H
_{2}
simulation algorithm to obtain
h
, then computes
V
=
ê
(
U
+
hQ_{i},S_{j}
) 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
,
and and sets
U
=
rP

hQ_{i}
,
W
=
rP_{pub}
, at the same time he defines
H
_{2}
(
m

ID_{i}

ID_{j}
,
U
)=
h
and inserts the tuple (
m

ID_{i}

ID_{j}
,
U
,
h
) into list
L
_{2}
. After that, Χ computes
V
=
ê
(
W,Q_{j}
). Besides, Χ chooses a random value
C
∈{0,1}
^{lm+lID}
and computes
H
_{1}
(
T
)=
C
⊕(
m

ID_{i}
),
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
.
(6) Deniable authenticated decryption queries: Α submits an IBDAE authenticator
δ
=(
U,C,V
) and a receiver’s identity
ID_{j}
to Χ. If
j
≠
N
_{1}
and
j
≠
N
_{2}
, Χ obtains the receiver’s private key
S_{j}
=
n_{j}P_{pub}
, computes
T_{j}
=
ê
(
U,S_{j}
) and runs the
H
_{1}
simulation algorithm to obtain
H
_{1}
(
T_{j}
). After that, Χ computes (
m

ID_{i}
)=
H
_{1}
(
T_{j}
)⊕
C
to recover
m

ID_{i}
, runs the
H
_{2}
simulation algorithm to obtain
h
=
H
_{2}
(
m

ID_{i}

ID_{j}
,
U
), and then computes
V
_{1}
=
ê
(
U
+
hQ_{i}
,
S_{j}
). Χ 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
ID_{j}
. The probability of fail in this situation is at most
q_{D}
/2
^{k}
.
Challenge: Once Α decides that Phase 1 is over, he outputs two plaintexts
m
_{0}
,
m
_{1}
with equal length, and two identities
ID_{S}
,
ID_{R}
that didn’t make key extraction query. Χ fails if Α consults Χ for
H
(
ID_{S}
) or
H
(
ID_{R}
) during the game. However, if
ID_{S}
and
ID_{R}
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
T_{S}
∈
G
_{2}
randomly and computes
U
=
raP
. Then Χ runs the
H
_{1}
simulation algorithm to obtain
H
_{1}
(
T_{S}
) and computes
C
=
H
_{1}
(
T_{S}
)⊕(
m_{γ}

ID_{S}
) where
γ
∈0,1 was chosen by Χ randomly.
(2) Χ runs the
H
_{2}
simulation algorithm to obtain
h
=
H
_{2}
(
m_{γ}

ID_{S}

ID_{R}
,
U
) and computes
V
=(
T_{S}
)
^{r1(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
ID_{S}
and
ID_{R}
, meanwhile he can’t make deniable authenticated decryption query on the challenge
δ
either.
Guess: Finally, Α outputs a bit
γ'
∈{0,1}. If
γ'
=
γ
, X outputs (
T_{S}
)
^{r1}
=
ê
(
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 INDIBDAECCA2 game. The value of Adv(Χ) is calculated as follows.
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 DAIBDAECMA game with advantage
ε
≥5(
q_{E}
+1)(
q_{E}
+
q_{H2}
)
q_{H}
/(2
^{k}
1) within time
t
for a security parameter
k
and consult at most
q_{H}
queries to oracles
H
,
q_{Hi}
queries to oracles
H_{i}
(
i
=1,2),
q_{K}
Kqkey extraction queries,
q_{E}
DAE queries and
q_{D}
DAD queries. Then there exists an algorithm Χ that can solve BDH problem within an expected time
t'
≤60343
q
_{H2}
q_{H}
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
P_{pub}
=
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
ID_{S}
and
ID_{R}
. 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 (
ID_{S}
,
ID_{R}
,
C
^{*}
,
h
^{*}
,
V
^{*}
) and (
ID_{S}
,
ID_{R}
,
C
^{*}
,
h
_{1}
^{*}
,
V
_{1}
^{*}
) where
h
^{*}
≠
h
_{1}
^{*}
with the same
U
^{*}
. Χ solves the BDH problem by computing
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 chosenidentity attack
[16]
, if Φ succeeds in time
t
with probability
ε
≥5(
q_{E}
+1)(
q_{E}
+
q_{H2}
)
q_{H}
/(2
^{k}
1), then Χ can solve the BDH problem in expected time
t'
≤60343
q
_{H2}
q_{H}
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,
bits, 
m
=160 bits, 
ID
=160 bits and hash value =160 bits. The total communication size of Cao et al.
[6]
is
bits, the total communication size of Chou et al.
[7]
is
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 identitybased 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
Communication Size
For noninteractive deniable authentication protocol, we should consider the weakenkey compromise impersonation
[17]
(WKCI) instead of KCI attack. In a WKCI attack, the compromising longterm 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 longterm private key is compromised. In our presented scheme, the adversary can masquerade a sender with identity
ID_{s}
and generate a valid DAE authenticator
δ
as follows when the private key of a receiver
S_{R}
is compromised.

(1) Choose a random numberand computeU=rQS.

(2)C=H1(ê(U,SR))⊕(mIDS).

(3)h=H2(mIDSIDR,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
S_{S}
is compromised, our scheme is also secure against WKCI 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
S_{R}
. Besides, he/she knows nothing about
r
from
U
=
rQ_{S}
under the assumption of DLP, so it is impossible for him/her to obtain the value
T
=
ê
(
S_{S},Q_{R}
)
^{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

ID_{S}

ID_{R}
,
U
) and
V
=
ê
(
U
+
hQ_{S}
,
S_{R}
) even if he/she possesses the longterm private key
S_{s}
. After our analysis, we find that Li et al.’s scheme is secure against WKCI attack, but Cao et al.’s scheme is insecurity against WKCI 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
The group order
q
is some prime factor of (
p
+1) and
q
is 160 bits long.
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 noninteractive 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 UniversityHakodate, 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.
Deng X.
,
Lee C. H.
,
Zhu H.
2001
“Deniable authentication protocols,”
IEEE ProceedingsComputers and Digital Techniques
148
(2)
101 
104
DOI : 10.1049/ipcdt:20010207
Dwork C.
,
Naor M.
,
Sahai A.
“Concurrent zeroknowledge,”
in Proc. of the thirtieth annual ACM symposium on Theory of computing
1998
409 
418
Ibrahim M. H.
2009
“Receiverdeniable publickey 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 IDbased 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 IDBased deniable authentication protocol on pairings,”
IACR Cryptology ePrint Archive
Lim M. H.
,
Lee S.
,
Park Y.
“An enhanced IDbased 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 IDBased 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
“Identitybased deniable authentication protocol,”
Electronics Letters
41
(5)
241 
242
DOI : 10.1049/el:20047017
Shamir A.
“Identitybased cryptosystems and signature schemes,”
in Proc. of CRYPTO 84 on Advances in cryptology
1985
47 
53
Boneh D.
,
Franklin M.
“Identitybased 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 identitybased signature from gap DiffieHellman 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 identitybased restricted deniable authentication protocol,”
IEEE International Symposium on Parallel and Distributed Processing with Applications
2009
474 
478
http://crypto.stanford.edu/pbc/