Printer Friendly

Identity-based Deniable Authenticated Encryption for E-voting Systems.

1. Introduction

Network communication has become an indispensable part of our daily lives. The security of network communication is a problem we have to consider. To achieve secure communication over the network, two basic security needs have to be considered: message confidentiality and message authentication. Message confidentiality typically means that a sender encrypts the message to be transmitted using the session key through symmetric cryptography; then, the session key is encrypted employing a receiver's public key; finally, the resulting ciphertext is sent with the encrypted symmetric key (ESK) to the receiver. The receiver decrypts ESK using his secret key, and then decrypts the resulting ciphertext using the session key. Message authentication is generally realized through digital signatures; however, the digital signature scheme is a non-repudiation scheme, and any independent third party can certify its validity, which is undesirable for applications where privacy is needed (such as e-voting systems). Therefore, deniable authentication was developed to protect the privacy of users.

Deniable authentication protocol (DAP) is designed to achieve two properties: (1) for a given message, only the prescribed receiver can determine its source; and (2) for any third party, the specified receiver is not capable of determining the provenience of a prescribed message. As such, DAPs are useful in many application scenarios that require privacy protection, such as electronic voting systems, e-tendering systems, and internet negotiations[1].

1.1 Related Work

Dwork et al.[2] developed the first DAP, which achieves concurrent zero-knowledge by pushing all use of timing into a constant round preprocessing phase. In 2013, Chen and Chou[3] proposed an ECC-based DAP. Their protocol, which is very efficient, used the Fiat-Shamir heuristic to realize full deniability. In 2014, Li et al.[4] constructed an identity-based (IB) DAP in an ad hoc network. Their protocol provides provable security in the random oracle model (ROM). Gambs et al.[5] designed a distance bounding scheme which defines and models prover anonymity. The anonymity can insure that the server is not capable of distinguishing prover manner from rancorous verifier manner. Shi et al.[6] constructed a quantum DAP without entanglement. Their protocol has greater qubit efficiency and consumes fewer quantum resources. In terms of security, their design meets all known security requirements of DAP. Dimitriou and Al-Ibrahim[7] designed a deniable-LBS (location-based services) scheme. This scheme can protect user location privacy even if its location is leaked to any third-party. Mandal et al.[8] designed an IBDAP without pairings. Their scheme admits provable security in ROM under the ECCDH (elliptic curve computational Diffie-Hellman) problem and is applicable for mobile devices with limited resources. Hong and Wang[9] proposed a DA scheme without pairings. Their scheme provides provable security in the standard model and achieves a low computational cost by implementing a precomputation technique. In 2017, Zeng et al.[10] constructed an encryption scheme with multi-receiver which achieved CCA2 security to support deniable ring authentication. This protocol achieves full deniability, requires only two communication rounds, and can be applied in LBS to protect vehicle privacy. Later, Zeng et al.[11] designed a DA with a ring signature that can hide sources. Their construction is based on the projective hash function, and the encryption scheme is not required to achieve CCA security. Recently, Li et al.[12] proposed two heterogeneous DA protocols that allow the sender and the receiver to be in different environments.

However, when we carefully examine the protocols listed above, we find that the messages are all transmitted in plaintext, and thus carry the risk of revealing the entities' private information. For confidentiality, messages should be kept secret. Harn and Ren[13] designed a fully deniable authentication protocol that is supported by the current PGP and S/MIME to offer deniability and message authentication. Lu et al.[14] proposed a DAP. Their protocol provides proof of security in the ROM and achieves their alleged security requirements. Later, to resist receiver spoofing attacks, Yoon et al.[15] designed an improved DAP. They claimed that their construction meets all security requirements. Nevertheless, Li and Takagi[16] clear that Yoon et al.'s scheme has a security breach, where the receiver is capable of proving the provenience of a prescribed message to any independent third-party. Subsequently, based on their proposed signcryption, Hwang and Sung[17] designed a DAP that achieves confidentiality, sender anonymity and protection. Harn et al.[18] proposed a 1-out-of-co DAP that can achieve full deniability. Later, Hwang et al.[19] constructed a non-interactive (NIA) DAP that supports both fair protection and anonymity. Li et al.[20] designed a DAE scheme. They provide an example of how to apply their proposed DAE scheme to e-mail systems.

Nevertheless, the above protocols must simplify the key management procedure, as they are all in a PKI environment. To eliminate various disadvantages brought by PKI, identity-based DAE (IBDAE) was proposed[21,22,23]. Wu et al.[21] proposed the first IBDAE protocol. They provide the proof of security of their scheme in the ROM. Later, Li et al.[22] presented an IBDAE protocol using a hybrid signcryption mechanism. They provide proof of security in the ROM and had better performance by comprehensive performance evaluation. Jin and Zhao[23] designed an IBDAE scheme. Their scheme shows high efficiency in the light of comprehensive performance evaluation. Recently, many related protocols[24,25,26,27] have been presented. Jin et al.[24] proposed a DAE scheme, and their construction is applicable for e-voting systems. Unger and Goldberg[25] proposed three deniable authenticated key exchange protocols. These three protocols can support forward secrecy against future quantum adversaries. Ahene et al.[26] proposed a DAE scheme in a certificateless setting. They provide concrete instantiation in e-voting systems. Jin and Zhao[27] devised an efficient ciphertext length (CL) aggregate DA protocol. Their protocol adopts aggregate verification, which expedites authenticator verification.

1.2 Motivation and Contribution

Signature-then-encryption schemes have disadvantages in terms of computational and communication costs. To solve these problems, Zheng[28] presented the concept of signcryption (SC). Nevertheless, the SC scheme is a non-repudiation scheme, which is undesirable, especially for some confidential occasions. In this paper, our goal is to design a scheme that satisfies the deniability. Motivated by the aforementioned studies, in this paper, we construct a novel IBDAE scheme that provides confidentiality and deniable authentication in one logical step. Our construction provides proof of security in the ROM under the DBDH and BDH assumptions and shows high efficiency in terms of performance analysis. Moreover, we provide an example that involves integrating our scheme into e-voting systems.

1.3 Organization of the Paper

Section 2 depicts preliminary work. We define the security model for IBDAE in Section 3, and the IBDAE scheme is designed in Section 4. In Section 5, we analyze the IBDAE scheme and discuss formal security in the ROM. Section 6 presents the results of the performance tests of our design. A secure e-voting system is constructed in Section 7, and the conclusions are provided in Section 8.

2. Preliminaries

This section discusses the basics of bilinear pairings.

Let [G.sub.1] and [G.sub.2] be a cycle additive group and a cycle multiplication group, respectively. [G.sub.1] is generated by P. [G.sub.1] and [G.sub.2] have the same prime order q. A bilinear pairing is a map e: [G.sub.1] x [G.sub.1] [right arrow] [G.sub.2], with the properties as below:

* Bilinearity: For all P, Q [member of] [G.sub.1], a, b [member of] [Z*.sub.q], e(aP, bQ) = [e(P, Q).sup.ab];

* Non-degeneracy: There exists P,Q [member of] [G.sub.1] such that e(P, Q) [not equal to] 1;

* Computability: There exists an efficient algorithm for computing e(P, Q) for all P, Q [member of] [G.sub.1].

The admissible maps of this type are the modified Weil pairing and the Tate pairing (Refs.[29,30] provide more information). The security of this scheme lies in the difficulty of the below problems.

Definition 2.1 According to the aforementioned basic definition of bilinear pairings, the DBDH problem in ([G.sub.1], [G.sub.2], e) is to determine whether h = [e(P, P)] given (P, aP, bP, cP) and an element h [member of] [G.sub.2].

Definition 2.2 According to the aforementioned basic definition of bilinear pairings, the BDH problem in ([G.sub.1], [G.sub.2], e) is to calculate h = [e(P, P)] given (P, aP, bP, cP) .

3. Formal Model for the IBDAE Protocol

This section presents the framework and the security concepts.

3.1 Framework

Four algorithms of the presented protocol is described as below.

Setup: Upon inputting a security parameter k, a public key generator (PKG) produces the public system parameters params and a master private key s. For simplicity, the following algorithms do not include params.

Extract: Upon inputting ID (an identity) and s, PKG calculates [S.sub.ID] (the corresponding private key) and outputs it securely to its owner.

DAE: Upon inputting a sender's private key [mathematical expression not reproducible], a message m, and a receiver's identity [ID.sub.r], the sender calculates [mathematical expression not reproducible] to obtain the ciphertext [sigma] .

DAD: Upon inputting a sender's identity [ID.sub.s], the ciphertext [sigma], and a receiver's private key [mathematical expression not reproducible], the receiver calculates [mathematical expression not reproducible], obtaining either the message m or [perpendicular to] when [sigma] is an invalid ciphertext.

For consistency, if [mathematical expression not reproducible], then [mathematical expression not reproducible] must also be true.

Fig. 1 presents the communication process in which the sender generates the ciphertext [sigma] for message m using his/her identity [ID.sub.s], private key [mathematical expression not reproducible], and the receiver's identity [ID.sub.r]. The receiver decrypts [sigma] using his/her identity [ID.sub.r] with the corresponding private key [mathematical expression not reproducible] and the sender's identity[ID.sub.s], resulting in either m or [perpendicular to]. Note that [mathematical expression not reproducible] and [mathematical expression not reproducible] are from the PKG.

3.2 Security Concepts

Our construction must achieve the desirable security requirements below:

* Confidentiality: any independent third party other than the entities involved cannot acquire any valuable advice related to the plaintext of a ciphertext;

* Deniable authentication: the receiver creates a deniable transcript that is probabilistically indistinguishable from the sender.

For confidentiality, the standard security concept used in our construction is the indistinguishability against adaptive chosen ciphertext attacks (IND-CCA2). For deniable authentication, the security concept used in our construction is the deniable authentication against adaptive chosen message attacks (DA-IBDAE-CMA) proposed in[4]. It is assumed that the following games (Definition 3.1 and Definition 3.2) are played between a challenger C and an adversary A .

Definition 3.1 An IBDAE scheme is IND-IBDAE-CCA2 secure when no adversary has a non-negligible advantage in the game below.

Setup: C executes Setup algorithm to create param and then transmit it to A.

Phase 1: A adaptively executes queries; any request may count on the responses to former queries.

* Extract: A elects an identity ID. C executes the Extract algorithm and transmits the corresponding private key [S.sub.ID] to A .

* DAE: A elects a message m and two identities [ID.sub.i], [ID.sub.j]. C first obtains the sender's private key [mathematical expression not reproducible] by implementing the Extract algorithm. Then, it transmits the result of [mathematical expression not reproducible] to A .

* DAD: A elects two identities [ID.sub.i] and [ID.sub.j], and a ciphertext [sigma]. C first obtains the sender's private key [mathematical expression not reproducible] by executing the Extract algorithm. Then, it transmits the result of [mathematical expression not reproducible] to A (if [sigma] is invalid, the result is [perpendicular to]).

Challenge: A determines when Phase 1 is over. Then, A outputs two challenged identities, [ID.sub.A] and [ID.sub.B], and two equal-length messages, [m.sub.0] and [m.sub.1]. It cannot request the private key of identities [ID.sub.A] or [ID.sub.B] in Phase 1. C elects a bit b [member of]{0,1}, calculates [mathematical expression not reproducible] and transmits [sigma] to A .

Phase 2: A requests queries as in Phase 1. In this phase, it cannot execute an Extract query on identities [ID.sub.A] or [ID.sub.B] nor can it execute a DAD query on ([sigma], [ID.sub.A], [S.sub.ID]B ) to possess the message m for[sigma] .

Guess: A outputs a guess b' and wins the game if b = b'.

The advantage of A is defined as Adv(A) =| 2P[b' = b] -1|, where P[b' = b] denotes the probability that b' = b.

Definition 3.2 An IBDAE scheme is DA-IBDAE-CMA secure when no adversary has a non-negligible advantage in the game below.

Setup: The procedure is the same as Setup in Definition 3.1.

Attack: A adaptively executes queries (any query counts on the responses to former queries). The allowed types of queries, such as Extract, DAE and DAD, are the same as those in Definition 3.1.

Forgery: A exports a pair identities [ID.sub.A] and [ID.sub.B] and a ciphertext [sigma], which never emerge in any Extract query in th e Attack phase. A wins the game if the result of [mathematical expression not reproducible] is not [perpendicular to].

The advantage of A is defined as the probability that it wins.

In the previous definition, the adversary is unallowed to perform an Extract query on identity [ID.sub.B], which is essential for realizing deniability. The sender and the receiver can create an indistinguishable transcript.

4. A New IBDAE Protocol

This section presents our construction.

Setup: Define [G.sub.1],[G.sub.2], e, k, and q as in Section 2. Let n, l be security parameters, [H.sub.1], [H.sub.2], and [H.sub.3] be three hash functions, i.e., [H.sub.1]: {0,1}* [right arrow][G.sub.1], [H.sub.2]:[G.sub.2][right arrow] [Z.sub.q] and [H.sub.3] : [{0,1}.sup.n] x [Z.sub.q][right arrow][{0,1}.sup.l], and E and D be symmetric encryption and decryption algorithms, respectively. PKG elects s [member of] [Z*.sub.q] and calculates []=sP. PKG publishes system parameters ([G.sub.1], [G.sub.2], n, l, e, P, q, [], [H.sub.1], [H.sub.2], [H.sub.3], E, D) but secretly retains s. The plaintexts must have a fixed bitlength of n where n + l < k [approximately equal to] [log.sup.q.sub.2].

Extract: On input an identity ID, the PKG calculates the user's public key [Q.sub.ID]=[H.sub.1] (ID) [member of] [G.sub.1] and the corresponding private key [S.sub.ID]=[sQ.sub.ID], which is sent to the owner securely.

DAE: Upon inputting a message m, a sender's private key [mathematical expression not reproducible], and a receiver's identity [ID.sub.r], the sender performs the following work.

* Select x [member of] [Z*.sub.q].

* Calculate [mathematical expression not reproducible]

* Calculate [k.sub.2] = [H.sub.2] ([tau]).

* Calculate [mathematical expression not reproducible].

* (Calculate) [mathematical expression not reproducible].

* Calculate [mathematical expression not reproducible].

* Output [sigma] = (r, V ).

DAD: Upon inputting a sender's identity [ID.sub.s], a ciphertext [sigma], and a receiver's private key [S.sub.ID], the receiver performs the procedure below.

* Calculate [mathematical expression not reproducible].

* Calculate [k.sub.2] = [H.sub.2] ([tau]).

* Calculate [mathematical expression not reproducible].

* Take m as the first n bits of m' if and only if (m, [H.sub.3] (m, [k.sub.2])) are the first n + l bits of m'.

5. Analysis of the Protocol

This section analyzes the presented protocol's consistency and security.

5.1 Consistency

We can certify the consistency of our construction by the equations below.

[mathematical expression not reproducible]

5.2 Security

We also certify that our design possesses deniability. A receiver with private key [mathematical expression not reproducible] creates a ciphertext that is probabilistically indistinguishable from a ciphertext created by a sender possessing [mathematical expression not reproducible]. To imitate the ciphertext, the receiver can perform the following steps.

* Select [] [member of] [Z*.sub.q] randomly.

* (Compute) [mathematical expression not reproducible] (.)

* Compute [[k.sub.2].bar] = [H.sub.2] ([[tau].bar]) .

* Calculate [mathematical expression not reproducible].

* Compute [mathematical expression not reproducible].

* Output is [[sigma].bar] = ([], []).

The generated ciphertext [[sigma].bar] = ([], []) is indistinguishable from [sigma] = (r, V) produced by the sender in Section 4. The sender randomly chooses a ciphertext [sigma]' = (r', V' ) from the sender's valid set of ciphertexts that are intended for the receiver. The probability [P.sub.r][[[sigma].bar]= [sigma]'] is 1/(q - 1) because [[sigma].bar] is chosen from [] [member of] [Z*.sub.q]. Likewise, the probability that [P.sub.r][[sigma] = [sigma]' ] is the same value, 1/(q - 1), because [sigma] is chosen from x [member of] [Z*.sub.q], i.e., they have the same probability distribution.

Next, we show that our design is provably secure. The two theorems below indicate that the design is secure with regard to both IND-IBDAE-CCA2 and DA-IBDAE-CMA.

Theorem 5.1 In the ROM, if A wins the game in Definition 3.1, with an advantage of [epsilon] within a time t by at most requesting [mathematical expression not reproducible] queries to oracle [H.sub.i](i = 1,2, 3), [q.sub.K] KE queries, [q.sub.E] DAE queries, and [q.sub.D] DAD queries, then C can settle the DBDH problem within a time of [mathematical expression not reproducible] with an advantage of

[mathematical expression not reproducible]

In which [T.sub.e] represents the calculation time of the bilinear pairing.

Proof. C acquires (P, aP, bP, cP) of the DBDH problem and attempts to determine whether h = [e(P,P)]. C is A 's challenger in the IND-IBDAE-CCA2 game. C consults A for a response to [H.sub.1], [H.sub.2], and [H.sub.3] which are randomly produced. C maintains three lists, [L.sub.1], [L.sub.2], and [L.sub.3], to save the response. A will request [H.sub.1] (ID) before ID is employed.

Setup: C runs Setup algorithm and sends []= cP to A. Note that C knows nothing about c, which serves as PKG's master private key.

Phase 1: A adaptively executes queries.

* [H.sub.1] queries: C randomly selects two index values i, [mathematical expression not reproducible]. A requests [H.sub.1] queries on identities it chooses. For query [H.sub.1], at the i-th, C returns [H.sub.1] ([ID.sub.i]) as aP; C returns [H.sub.1] ([ID.sub.j] ) as bP at the j-th. For queries [H.sub.1] ([ID.sub.[alpha]] ) with [alpha] [not equal to] i, j, C selects [d.sub.[alpha]] from [Z*.sub.q], stores ([ID.sub.[alpha]],[d.sub.[alpha]]) in list L1, and returns [H.sub.1] ([ID.sub.[alpha]]) = [d.sub.[alpha]]P .

* [H.sub.2] queries: For query [H.sub.2] ([g.sub.e]), C checks whether the value of [H.sub.2] is in the list. If so, it returns the same answer to A ; if not, C randomly picks a value [k.sub.2] [member of] [Z*.sub.q] as a response and stores ([g.sub.e], [k.sub.2]) in [L.sub.2].

* [H.sub.3] queries: For query [H.sub.3] (m, [k.sub.2]), C checks if the value of [H.sub.3] is in the list. If so, it transmits the same answer to A. If not, C returns value u [member of] [Z*.sub.q] as a response and stores (m, [k.sub.2], u) in list [L.sub.3].

* KE queries: When A submits an identity to C, if [ID.sub.[alpha]]=[ID.sub.i] or [ID.sub.[alpha]] = [ID.sub.j], C fails. If [ID.sub.[alpha]] [not equal to] [ID.sub.i], [ID.sub.j], the list [L.sub.1] must have ([ID.sub.[alpha]], [d.sub.[alpha]]) for some [d.sub.[alpha]] (indicating that C previously answered [H.sub.1] ([ID.sub.[alpha]])=[d.sub.[alpha]]P). The private key of [ID.sub.[alpha]] is [d.sub.[alpha]][] = [d.sub.[alpha]]cP. The failure probability in KE queries is at most [mathematical expression not reproducible].

* DAE queries: A can perform DAE queries on m, [ID.sub.[alpha]] and [ID.sub.[beta]].

(1). If [ID.sub.[alpha]] [not equal to] [ID.sub.i],[ID.sub.j], C first calculates the private key [mathematical expression not reproducible] by executing KE query algorithm; then, it performs the DAE(m, [mathematical expression not reproducible], [ID.sub.[beta]]) algorithm to answer the query.

(2). If [ID.sub.[alpha]]= [ID.sub.i] or [ID.sub.[alpha]] = [ID.sub.j], but [ID.sub.[beta]] [not equal to] [ID.sub.i],[ID.sub.j], C runs a simulation as follows. It obtains the private key [mathematical expression not reproducible] using the key extraction algorithm. Then, it selects the random elements (r, V) [member of] [Z*.sub.q] x [G.sub.2] and computes [mathematical expression not reproducible].

The simulation depends on whether list [L.sub.2] has a tuple of the form ([tau], *). When [L.sub.2] contains an entry ([tau], [k.sub.2]) and [L.sub.3] has an item (m, [k.sub.2], u), when the first n bits of [mathematical expression not reproducible] (r) can be distinguished from m, C selects another (r, V ) and repeats the procedure. When [L.sub.3] contains no entry for (m, [k.sub.2], u), C takes u = [mathematical expression not reproducible] (in which [[x].sub.i... j] symbolises the bit string between the i-th and j-th leftmost bits of x) and stores (m, [k.sub.2], u) in list [L.sub.3].

When no entry ([tau], *) exists in list [L.sub.2], C chooses a random [k.sub.2] [member of] [Z*.sub.q] It also selects a random u [member of] [{0,1).sup.l] to ensure that (m, *, u) is not in list [L.sub.3]. Then, it calculates m = m [parallel] u. When no item (m, [k.sub.2], u ) with u [not equal to] u is in list [L.sub.3], C stores ([tau], [k.sub.2]) and (m, [k.sub.2], u) in lists [k.sub.2] and [k.sub.3], respectively. Otherwise, C provides other alternative data (r, V) and repeats the procedure.

C updates lists [k.sub.2] and [k.sub.2] after it searches alternative data (r, V), and it returns (r, V) as the ciphertext. The procedure is repeated at most 2q[H.sub.3]. After each attempt, only one pairing is computed.

(3). When [ID.sub.[alpha]] = [ID.sub.i], [ID.sub.[beta]] = [ID.sub.j] or [ID.sub.[beta]] = [ID.sub.i], [ID.sub.[alpha]] = [ID.sub.j] C randomly selects x from [Z*.sub.q] and computes [tau] = e[([], [Q.sub.B]).sup.x] and [k.sub.2] = [H.sub.2] ([tau]) such that no ([tau], [k.sub.2]) exists in list [L.sub.2]. Then, C verifies whether list [L.sub.3] contains an item for (m, [tau], u). If not, C stores (m, [tau], u) in list [L.sub.3] and ([tau], [k.sub.2]) in list [L.sub.2]. Then, C computes [mathematical expression not reproducible] (m [parallel] u), selects V[member of] [G.sub.2] and transmits [sigma]=(r, V) to A. A would not know that [sigma] is an invalid ciphertext, but it requests the decryption of [sigma].

* DAD queries: A generates a ciphertext [sigma] for [ID.sub.[alpha]] and [ID.sub.[beta]]. When [ID.sub.[beta]] [not equal to] [ID.sub.i], [ID.sub.j], C can obtain [mathematical expression not reproducible] by running the KE algorithm and then running DAD( [sigma], [ID.sub.[alpha]], [mathematical expression not reproducible]. Otherwise, C fails. The failure probability is at the utmost [q.sub.D] / [2.sup.k] .

After the first stage, A selects two identities it wishes to challenge. The challenged identities are ([ID.sub.i], [ID.sub.j]) with a probability of at least [mathematical expression not reproducible] fails if A requests the private key of [ID.sub.i] or [ID.sub.j] in first stage because it is unable to answer the question. C also fails if A does not pick these two identities as the target identities.

Then, A creates two messages, [m.sub.0] and [m.sub.1] * C chooses a random bit b [member of] {0,1} and encrypts [m.sub.b] * It chooses r [member of] [Z*.sub.q] and V [member of] [G.sub.2] and computes [tau] = V[h.sup.r] (where h is C 's candidate for the DBDH problem) to receive [k.sub.2] = [H.sub.2] ([tau]) (according to [H.sub.2] simulation algorithm) and [u.sub.b] = [H.sub.3] ([m.sub.b], [k.sub.2]) (according to [H.sub.3] simulation algorithm). Then, it verifies whether [L.sub.3] already contains the entry ([m.sub.b], [k.sub.2], [u.sub.b]. If not, it stores ([m.sub.b], [k.sub.2], [u.sub.b]) in list [L.sub.3]; otherwise, it selects another (r,V) and repeats the procedure. After looking up admissible element (r,V), C sends the ciphertext [sigma] = (r,V) to A.

A then executes the second stage queries as in the first stage. When the simulation is over, it creates a bit b' as [mathematical expression not reproducible] from the standpoint of A. If b = b', C answers 1 because A has produced a valid [sigma] using its knowledge of h. Otherwise, C responds 0.

Now we consider C's probability of success. C does not successful if A requests the private key of [ID.sub.i] or [ID.sub.J] in the first stage. There are [mathematical expression not reproducible] options to pick ([ID.sub.i],[ID.sub.j]). Of these identities, at least one will never have made a KE query from A. A will not query Keygen( [ID.sub.i]) and Keygen( [ID.sub.j]) with a probability greater than [mathematical expression not reproducible] Further, A elects challenge identities ([ID.sub.i], [ID.sub.j]) with a exactly probability [mathematical expression not reproducible] and C settles its DBDH problem if A wins the IND-IBDAE-CCA game.

In the end, because [p.sub.1] = Pr[b ' = b | [sigma] = DAE([m.sub.b], [mathematical expression not reproducible], [ID.sub.j])] =[ [epsilon]+1/2 - [q.sub.D]/[2.sup.k]]

[p.sub.0] = Pr[b ' = i | h [member of] [G.sub.2]] = 1/2for i=0,1

we have

[mathematical expression not reproducible]

Note that the denominator is [mathematical expression not reproducible] rather than [mathematical expression not reproducible] because Adetermines the challenged identities after the first stage.

Theorem 5.2 In the ROM, if A wins the game of Definition 3.2 with an advantage of [mathematical expression not reproducible] within time t and by at most requesting [mathematical expression not reproducible] queries to [H.sub.i] (i = 1,2,3), [q.sub.K] KE queries, [q.sub.E] DAE queries, and [q.sub.D] DAD queries, then C settles the BDH problem in an expected time of [mathematical expression not reproducible].

Proof. To wield the forking algorithm[31], we have to prove how our design is applicable for the signature scheme described in[31]. In DAE imitate steps, the sender's private key fails (implying that the master private key fails). In this case, a method is needed to settle the BDH problem.

First, observe that the DAE of our design meets the requested three-phase honest-verifier zero-knowledge identification protocol, in which [[sigma].sub.1] = [k.sub.2] = [H.sub.2] (e[([], [Q.sub.B]).sup.x]) is the commitment, h = [H.sub.3] (m, [k.sub.2])is the hash value, and [[sigma].sub.2] = V is the answer.

Second, we give a concrete imitate step and show a method of settling the BDH problem. Upon inputting (P, aP, bP, cP) of the BDH problem, C is needed to calculate e[(P, P)]. C executes A as a subroutine. A consults C to answer [H.sub.1], [H.sub.2], and [H.sub.3] and C holds lists [L.sub.1], [L.sub.2], and [L.sub.3] to save the randomly generated responses. The [H.sub.1], [H.sub.2], [H.sub.3], DAE and DAD queries are requested in the way they are in the proof of Theorem 1.

Forgery: A outputs a triple ([sigma]*, [ID.sub.i], [ID.sub.j]), where [sigma]* = (r*, V*). We coalesce the identities [ID.sub.[theta]] = {[ID.sub.i], [ID.sub.j]} and the message m* into ([ID.sub.[theta]], m*) so that we can hide the IB aspect of the DA-IBDAE-CMA attacks and imitate an identity-less adaptive-CMA existential forgery.

If A is an attacker with adequate efficiency in the above interaction, we can create a Las Vegas machine A ' that returns two forgeries (([ID.sub.[theta]], m*), r*, V*) and (([ID.sub.[theta]], m*), [bar.r]*, [bar.V]*) with r* [not equal to] [bar.r]* and the same commitment x. To settle the BDH problem based on the machine A' derived from A, we construct a machine C' as follows.

* C' executes A' to acquire two distinct forgeries (([ID.sub.[theta]], m*), r*, V*) and (([ID.sub.[theta]], m*), [bar.r]*, [bar.V]*).

* C' calculates e[(P, P)] as [(V*/[bar.V]*).sup.-1]/([bar.r]* - r*).

The machine C' is our reduction of the BDH problem. If the success probability of A' is [mathematical expression not reproducible], while its running time is t, then C' can settle the BDH problem in an expected time [mathematical expression not reproducible]. Here, there is a change in the coefficient since the simulator has to bring forward two disparate identities.

6. A Secure E-voting Protocol

The construction is employed in an e-voting system (EVS). Here, we provide the example shown in Fig. 2. An electronic power corporate expects to select a general manager by having all employees vote. However, if the votes are sent as plaintext, the process would be insecure. Each employee is a voter who first runs [mathematical expression not reproducible] to gain the ciphertext. Then, the voter sends the ciphertext to the electronic power tally authority (TA). In this protocol, a PKG exists in the company in charge of registration. The PKG gives a secret key to each employee and to the TA. The employees can use their smart devices to transmit their ciphertexts to the TA. Finally, the TA runs [mathematical expression not reproducible] to obtain each message m. While the TA can know that the ciphertexts were sent by valid staff because the protocol owns the authentication, the TA cannot certify the sender's identity of the ciphertext to any trusted entity, as this design is deniable. Moreover, if the TA and a third party were to cooperate, the third party might suspect the truth of the ciphertext as provided by the TA because the TA can also generate valid ciphertexts. Thus, the third party cannot force an employee to select a particular candidate.

7. Performance

We will construct a detailed performance analysis of our design with the existing schemes[16, 17, 21, 22] listed in Table 1. We employ the point add (PA) calculation and the point multiplication (PM) calculation in [G.sub.1], the bilinear pairing (BP) calculation, the modular exponentiation (ME) calculation and the multiplication (MT) calculation in a finite field, and a certificate verification (CV) calculation (which generally costs approximately the same as two ME computations). Note that the ME calculation in a finite field (FF) is equivalent to a PM calculation in the elliptic curve cryptosystem (ECC) (i.e., ME=PM), and the MT calculation in a FF is equal to the PA calculation in ECC (i.e., MT=PA). The XOR, hash function, and add calculation in a FF are omitted because their computation speeds are sufficiently fast to be negligible. Additionally, let |[G.sub.1]| =160 bits, |m| = 160 bits, |p| = 512 bits, |cert| = 320 bits, |q| = 160 bits, hash value = 160 bits, and |[G.sub.2]| =1024 bits. Here, the key size (KS) is made up of both public key and private key size. As shown in Table 1, regarding KS and CL, our approach is highly efficient. Additionally, the scheme in [16] is interactive and lacks proof of security. Our design is in the ID-based setting. As such, our design avoids problems related to PKI.

We conduct an experiment on the PBC library. As needed, we set the library's embedding degree to 2. The experiment is executed on an Intel Pentium(R) Dual-Core processor running at 2.69 GHz, with 2,048 MB of RAM (2,007.04 MB available). On this machine, a PA computation and a PM computation require 0.065 ms and 15.927 ms using an ECC with 160 bits of q, respectively. A BP computation and a ME computation require 26.68 ms and 3.126 ms, respectively. DAE and DAD consume 95.562 ms and 95.562 ms in [16], 79.7 ms and 63.773 ms in [17], 88.34 ms and 42.672 ms in [21], and 101.206 ms and 58.534 ms in[22]. In our scheme, DAE and DAD consume 101.206 ms and 42.607 ms, respectively. [16, 17, 21, 22], the computational expense for DAE in our design is the same as that in [22] but slightly higher than those in [16, 17, 21] because it requires two pairings that belong to [G.sub.2]. Our design has the lowest computational expense for DAD, although we have one pairing computation. In terms of type, [16, 17] are in the PKI setting, while [21, 22] and our design are in an ID-based setting and avoid the problems in PKI. Fig. 4 shows the CL for [16, 17, 21, 22] and our scheme. Although our design must transmit V, which belongs to [G.sub.2], our protocol still has the smallest communication overhead.

8. Conclusion

In this paper, we construct a novel non-interactive IBDAE scheme that realizes deniable authentication and confidentiality in a logical single step. Our construction provides proof of security and is efficient in terms of performance analysis. In addition, we provide an example to show how our construction can be used in e-voting systems. As such, our design is applicable to privacy protection scenarios.


This work is supported by the Natural Science Foundation of Huai'an (Grant No.HAB201837), the Electric Power Company Technology Project of Jiangsu Province (Grant No.J2017123), the Natural Science Foundation of Jiangsu Province (Grant No.BK20161302), the National Key R & D Program of China (No. 2018YFB1004904), the Huai'an Science and Technology Project (No. HAC201705, No.HAB201803), the Key Project of JiangSu Provincial Department of Education (No.18KJA520001), the Six Talent Peaks Project in Jiangsu Province (XYDXXJS-011), and the Jiangsu 333 Engineering Research Funding Project (BRA2016454)..


[1] Y. Aumann and M. Rabin, "Authentication, enhanced security and error correcting codes," in Proc. of 20th Annual International Cryptology Conference, CRYPTO 1998, pp. 299-303, August 23-27, 1998. Article (CrossRef Link).

[2] C. Dwork, M. Naor and A. Sahai, "Concurrent zero-knowledge," in Proc. of the Thirtieth Annual ACM Symposium on the Theory of Computing Symposium on Theory of Computing (STOC '98), pp. 409-418, May 23-26, 1998. Article (CrossRef Link).

[3] Y. Chen and J. Chou, "ECC-Based Non-Interactive Deniable Authentication with Designated Verifier," IACR Cryptology ePrint Archive, pp. 783, 2013. Article (CrossRef Link).

[4] F. Li, P. Xiong and C. Jin, "Identity-Based Deniable Authentication for Ad Hoc Networks," Computing, vol. 96, no. 9, pp. 843-853, September, 2014. Article (CrossRef Link).

[5] S. Gambs, C. Onete and J. Robert, "Prover anonymous and deniable distance-bounding authentication," in Proc. of the 9th ACM symposium on Information, computer and communications security, pp. 501-506, June 4-6, 2014. Article (CrossRef Link).

[6] W. Shi, J. Zhang, Y. Zhou and Y. Yang, "A novel quantum deniable authentication protocol without entanglement," Quantum Information Processing, vol.14, no.6, pp. 2183-2193, January, 2015. Article (CrossRef Link).

[7] T. Dimitriou and N. Al-Ibrahim, "Denying Your Whereabouts: A Secure and Deniable Scheme for Location-Based Services," in Proc. of Cryptology and Network Security- 15th International Conference, pp. 713-718, November 14-16, 2016. Article (CrossRef Link).

[8] S. Mandal, S. Mohanty, and B. Majhi, "An ID-based Non-Interactive Deniable Authentication Protocol based on ECC," in Proc. of the 2017 the 7th International Conference on Communication and Network Security, pp. 48-52, November 24-26, 2017. Article (CrossRef Link).

[9] X. Hong and B. Wang, "A non-interactive deniable authentication scheme in the standard model," Journal of Electrical and Electronic Engineering, vol. 5, no. 2, pp. 80, December, 2017. Article (CrossRef Link).

[10] S. Zeng, Y. Chen, S. Tan and M. He, "Concurrently deniable ring authentication and its application to LBS in VANETs," Peer-to-Peer Networking and Applications, vol.10, no.4, pp. 844-856, January, 2017. Article (CrossRef Link).

[11] S. Zeng, Y. Mu, G. Yang and M. He, "Deniable Ring Authentication Based on Projective Hash Functions," in proc. of Provable Security- 11th International Conference, ProvSec 2017, pp. 127-143, October 23-25,2017. Article (CrossRef Link).

[12] F. Li, J. Hong and A. Omala, "Practical deniable authentication for pervasive computing environments," Wireless Networks, vol.24, no.1, pp. 139-149, January, 2018. Article (CrossRef Link).

[13] L. Harn and J. Ren, "Design of fully deniable authentication service for e-mail applications," Communications Letters, vol.12, no.3, pp. 219-221, January, 2008. Article (CrossRef Link).

[14] R. Lu, X. Lin, Z. Cao, L. Qin and X. Liang, " A simple deniable authentication protocol based on the Diffie-Hellman algorithm," International Journal of Computer Mathematics, vol.85, no.9, pp. 1315-1323, 2008. Article (CrossRef Link).

[15] E. Yoon, K. Yoo, S. Yeo and S. Lee, "Robust deniable authentication protocol," Wireless personal communications, vol. 55, no. 1, pp. 81-90, September, 2010. Article (CrossRef Link).

[16] F. Li and T. Takagi, "Cryptanalysis and Improvement of Robust Deniable Authentication Protocol," Wireless personal communications, vol. 69, no.4, pp. 1391-1398, January, 2013. Article (CrossRef Link).

[17] S. Hwang and Y. Sung, "Confidential deniable authentication using promised signcryption," Journal of Systems and Software, vol. 84, no. 10, pp. 1652-1659, January, 2011. Article (CrossRef Link).

[18] L. Harn, C. Lee, C. Lin, and C. Chang, "Fully deniable message authentication protocols preserving confidentiality," The Computer Journal, vol. 54, no. 10, pp. 1688-1699, January, 2011. Article (CrossRef Link).

[19] S. Hwang, Y. Sung and J. Chi, "Deniable Authentication Protocols with Confidentiality and Anonymous Fair Protections," in Proc. of the International Computer Symposium ICS 2012, pp. 41-51, December 12-14, 2013. Article (CrossRef Link).

[20] F. Li, D. Zhong and T. Takagi, "Efficient Deniably Authenticated Encryption and Its Application to E-Mail," IEEE Transactions on Information Forensics and Security, vol. 11, no. 11, pp. 2477-2486, November, 2016. Article (CrossRef Link).

[21] W. Wu and F. Li, "An Efficient Identity-Based Deniable Authenticated Encryption Scheme," KSII Transactions on Internet and Information Systems (TIIS), vol. 9, no. 5, pp. 1904-1919, January, 2015. Article (CrossRef Link).

[22] F. Li, Z. Zheng and C. Jin, "Identity-based deniable authenticated encryption and its application to e-mail system," Telecommunication Systems, vol. 62, no. 4, pp. 625-639, May, 2016. Article (CrossRef Link).

[23] C. Jin and J. Zhao, "Efficient and Short Identity-Based Deniable Authenticated Encryption," in proc. of International Conference on Cloud Computing and Security, pp. 244-255, June 17-18, 2017. Article (CrossRef Link).

[24] C. Jin, G. Chen, C. Yu and J. Zhao, "Deniable authenticated encryption for e-mail applications," International Journal of Computers and Applications, pp.1-10, May, 2018. Article (CrossRef Link).

[25] N. Unger and I. Goldberg, "Improved Strongly Deniable Authenticated Key Exchanges for Secure Messaging," in Proc. of Privacy Enhancing Technologies, 2018, pp.21-66, July 24-27, 2018. Article (CrossRef Link).

[26] E. Ahene, C. Jin and F. Li, "Certificateless deniably authenticated encryption and its application to e-voting system," Telecommunication Systems, pp. 1-18, 2018. Article (CrossRef Link).

[27] C. Jin and J. Zhao, "Certificateless aggregate deniable authentication protocol for ad hoc networks," International Journal of Electronic Security and Digital Forensics, vol. 10, no. 2, pp. 168-187, 2018. Article (CrossRef Link).

[28] Y. Zheng, "Digital signcryption or how to achieve cost (signature & encryption) << cost (signature) + cost(encryption)," in Proc. of Cryptology-CRYPTO'97, 17th Annual International Cryptology Conference, pp. 165-179, August 17-21, 1997. Article (CrossRef Link).

[29] J. Cha and J. Cheon, "An identity-based signature from gap Diffie-Hellman groups," in Proc. of Public Key Cryptography- PKC 2003, sixth International Workshop on Theory and Practice in Public Key Cryptography, pp. 18-30, January 6-8, 2003. Article (CrossRef Link).

[30] D. Boneh and M. Franklin, "Identity-based encryption from the weil pairing," in Proc. of Cryptology- CRYPTO 2001, 21st Annual International Cryptology Conference, pp. 213-229, August 19-23, 2001. Article (CrossRef Link).

[31] D. Pointcheval and J. Stern, "Security arguments for digital signatures and blind signatures," Journal of Cryptography, vol. 13, no. 3, pp. 61-396, 2003. Article (CrossRef Link).

Chunhua Jin received a B.S. degree from Northwestern Polytechnical University, Xi'an, P.R. China in 2007, an M.S. degree from Xidian University, Xi'an, P.R. China in 2011, and a Ph.D. degree in Cryptography from the University of Electronic Science and Technology of China, Chengdu, P.R. China in 2016. She is now a lecturer in the Faculty of Computer and Software Engineering, Huaiyin Institute of Technology, Huai'an, P.R. China. Her recent research interests include cryptography and network security.

Guanhua Chen received a B.S. degree from Xi'an University of Technology, Xi'an, P.R. China in 2006. He is now a graduate student in the Faculty of Computer and Software Engineering, Huaiyin Institute of Technology, Huai'an, P.R. China. His recent research interests include cryptography and network security.

Jianyang Zhao received an Ms.D. degree in power electronic engineering and a Ph.D. degree in test measurement techniques and instruments from the Nanjing University of Aeronautics and Astronautics. His current research interests are power quality monitoring and analysis, transient analysis, and power system equipment modeling and diagnoses.

Shangbing Gao received a BS degree in mathematics from the Northwestern Polytechnical University in 2003, a MS degree in applied mathematics from the Nanjing University of Information and Science and Technology in 2006, and a Ph.D. degree with the School of Computer Science and Technology, Nanjing University of Science and Technology (NUST). Since 2014, he has been an associate professor at Huaiyin Institute of Technology, China. His current research interests include pattern recognition and computer vision

Changhui Yu received a B.S. degree from Liaoning Normal University, Dalian, P.R. China in 1996, and an M.S. degree from Southeast University, Nanjing, P.R. China in 2009. She is now a teacher in the Faculty of Computer and Software Engineering, Huaiyin Institute of Technology, Huai'an, P.R. China. Her recent research interests include cryptography and network security.

Chunhua Jin (1), Guanhua Chen (1*), Jianyang Zhao (1), Shangbing Gao (1), Changhui Yu (1)

(1) Faculty of Computer & Software Engineering, Huaiyin Institute of Technology Huaian, 233003 - China


(*) Corresponding author: Guanhua Chen

Received December 4, 2017; revised April 3, 2018; revised September 28, 2018; accepted November 13, 2018; published June 30, 2019
Table 1. Performance comparison

Schemes    Computational cost   KS   CL            Interactive  Security
           DAE       DAD                           mode         proof

Li[16]     4ME+1CV   4ME+1CV    672   832+ |cert|  IA           No
           =6ME      =6ME             =1252
Hwang[17]  3ME+1MT   2ME+1MT+   672   992+ |cert|  NIA          Yes
           +1CV      1CV              =1312
           =5ME+1MT  =4ME+1MT
Wu[21]     2BP+1ME   2BP+1PA+1  320  1856          NIA          Yes
           +2PM      PM
Li[22]     2BP+1PA+  1BP+2PM    320  1536          NIA          Yes
Ours       2BP+3PM   1BP+1PM    320  1184          NIA          Yes

Schemes    Type

Li[16]     PKI
Hwang[17]  PKI
Wu[21]     ID
Li[22]     ID
Ours       ID
COPYRIGHT 2019 KSII, the Korean Society for Internet Information
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2019 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Jin, Chunhua; Chen, Guanhua; Zhao, Jianyang; Gao, Shangbing; Yu, Changhui
Publication:KSII Transactions on Internet and Information Systems
Date:Jun 1, 2019
Previous Article:An Efficient Anonymous Autithentication Scheme with Secure Communication in Intelligent Vehicular Ad-hoc Networks.
Next Article:Transitive Signature Schemes for Undirected Graphs from Lattices.

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters