Introduction

The fast expansion of smart devices and mobile networks makes location-based services (LBSs) an integral part of people’s daily lives. Users utilize LBSs to find points of interests, navigate the destination, and inquire public transportation etc. [1–6]. In all of these requested services, users need to disclose their location information to the location-based service provider (LBSP). Based on location information, LBSP is able to infer some sensitive information about users, such as preferences, social circles, and trajectories. For example, if a user frequently presents location request to the same hospital, the LBSP is able to deduce that the user may have a physical issue.

If the LBSP cooperates with a malicious adversary for pecuniary advantage, there will be significant loss of profits for users. For example, based on the location-based privacy information leaked by a user, a malicious adversary can infer a user’s home address or routine and then commit theft, which seriously threatens user’s personal and property safety. Therefore, protecting users’ location privacy is a major concern.

Authentication plays a very important role in the LBS [7–16]. Only authorized users can access the LBS. Typically, we utilize digital signature technology to achieve authentication. However, there is also non-repudiation in digital signature. That is, the sender cannot deny the message he/she signed. To resolve this issue, deniable authentication [17] is proposed which has two characteristics: (1) the receiver has the capability of identifying whether a given message is from the sender; (2) any third party is incapable of determining whether the given message is from the sender or the receiver even though the third party colludes with the receiver since the receiver is able to generate a probabilistically indistinguishable transcript from the sender. However, in privacy-preserving scenarios, the transmitted message needs to be encrypted to achieve confidentiality. Wu and Li [18] first presented an identity-based DAE scheme to achieve confidentiality as well as deniable authentication in an efficient approach.

1 Related work

Related notions, hybrid encryption, deniable authenticated encryption, and heterogeneous deniable authentication are introduced.

Hybrid encryption constitutes a key encapsulation mechanism (KEM) and a data encapsulation mechanism (DEM). The KEM encrypts a session key by a public key, whereas the DEM encrypts the real data by a session key. For large messages, hybrid encryption is the best choice. Cramer and Shoup [19] designed practical and provably secure hybrid KEM/DEM schemes. Abe et al. [20] put forward to a more efficient tag-KEM/DEM scheme. Then, many KEM/DEM schemes [21–28] have been proposed. These designs support both components modular design. Sahai et al. [29] put forward to a tag-KEM/DEM scheme by a non-interactive proof method. The proposed scheme can encrypt message with arbitrary length. Baek et al. [30] presented a stateful KEM-DEM scheme. It is highly effective by utilizing a state to produce the random parameters.

Deniable authentication encryption (DAE) is a cryptographic primitive which can accomplish concurrently public key encryption and deniable authentication. Its cost is lower than that needed by deniable authentication-then-encryption manner. The DAE can achieve deniable authentication and confidentiality simultaneously which is well adopted for privacy-protecting scenarios.

Li et al. [31] constructed a DAE scheme with formal security proof. They also constructed an email system based on the designed DAE scheme. Jin et al. [32] constructed a DAE scheme which can realize simultaneously deniable authentication, confidentiality, and ciphertext anonimity. Rasmussen and Gasti [33] proposed a DAE based on two encryption schemes with strong and weak properties. Recently, Huang et al. [34] constructed a DAE scheme for privacy protection with formal security proof. The above mentioned schemes are all in the PKI environment which has public key management problems, including distribution, storage, and revocation. To resolve this issue, a number of identity-based deniable authenticated encryption (IBDAE) schemes have been constructed. Wu and Li [18] constructed an IBDAE scheme which provided formal security proof. Li et al. [35] (denoted by LZJ) proposed an IBDAE scheme for e-mail system. In their scheme, they utilize tag-KEM/DEM hybrid encryption technology which is more suitable for actual applications. Jin and Zhao [36] designed an IBDAE scheme which admitted formal security proof. The aforementioned schemes have key escrow problems, i.e., a third party called private key generator (PKG) knows all user’s private key. To avoid this problem, a certificateless deniable authenticated encryption (CLDAE) scheme [37] has been designed. Recently, Chen et al. [38] proposed a certificateless hybrid KEM/DEM scheme. It separates two parts to provide better security and efficiency.

The aforementioned DAE schemes have a common feature, i.e., the entities of these schemes are all in the same cryptosystem. Such characteristic makes these schemes not well suitable for the LBS system. Li et al. [39] (denoted by LHO) designed two heterogeneous deniable authentication (HDA) schemes. Their designed schemes allowed batch verification to accelerate the authenticators’ verification. Jin et al. [40] constructed an HDA scheme. In their scheme, a sender in a CLC setting delivered a message to a receiver in an IBC setting. However, these schemes do not achieve confidentiality.

2 Problem formulation

2.1 System and security models

There are three entities in the HDAE as shown in Fig 1: a user, an LBSP, and a trusted third party PKG. The location information and the corresponding ciphertext are produced by the user, and the ciphertext are sent to the LBSP. The LBSP can identify the received ciphertext is from the user and generate a probabilistically indistinguishable ciphertext from the user. The PKG is mainly responsible for generating system parameters and LBSP’s private key.

Fig 1

System model.

To obtain the location-based service that supports privacy-preserving, in the proposed system model, the user sends the ciphertext of location-requested information to the LBSP. Then the LBSP decrypts the received ciphertext and checks whether the decrypted message is location-requested information or a failure symbol ⊥.

3 PI-HDAE

We describe security notions for the HDAE in this section. In the designed HDAE scheme, a sender in a PKI environment, while a receiver in an IBC environment. PI-HDAE is denoted by this kind of DAE as follows.

3.2 Security notions

We rewrite the notions [35] to meet our scheme. For confidentiality, the standard security concept, indistinguishability against adaptive chosen ciphertext attacks (IND-CCA2) is employed in our construction.

For IND-CCA2 security in a PI-HDAE scheme, it is assumed that this game below is between an adversary $$ \mathcal{F}$$ with its challenger $$ \mathcal{C}$$.

“IND-CCA2” game (Game-I):

Setup. $$ \mathcal{C}$$ performs Setup algorithm to get params, releases it to $$ \mathcal{F}$$ and saves s. $$ \mathcal{C}$$ also executes the PKI-KG algorithm to obtain a sender’s private/public key pair ($$ s{k}_s^{*}$$, $$ p{k}_s^{*}$$). Then it passes $$ p{k}_s^{*}$$ to $$ \mathcal{F}$$.

Phase 1. $$ \mathcal{F}$$ adaptively issues the queries below.

Key extraction queries: $$ \mathcal{F}$$ picks an identity ID. $$ \mathcal{C}$$ obtains the private key S_ID by running an IBC-KE algorithm and transmits it to $$ \mathcal{F}$$.

DAE queries: $$ \mathcal{F}$$ selects a receiver’s identity ID_r, and a message m. Then $$ \mathcal{C}$$ executes DAE(m, $$ s{k}_s^{*}$$, $$ p{k}_s^{*}$$, ID_r) and transmits the result σ to $$ \mathcal{F}$$.

DAD queries: $$ \mathcal{F}$$ selects a ciphertext σ, and a receiver’s identity ID_r. $$ \mathcal{C}$$ obtains $$ S_{I{D}_r}$$ by implementing key extraction algorithm. It then transmits σ = DAD(σ, $$ p{k}_s^{*}$$, ID_r, $$ S_{I{D}_r}$$) to $$ \mathcal{F}$$ (the resulting ⊥ indicates σ is invalid).

Challenge. $$ \mathcal{F}$$ determines when Phase 1 ends. $$ \mathcal{F}$$ creates a challenge identity $$ I{D}_r^{*}$$ and two messages (m₀, m₁). In phase 1, it does not support to request a key extraction query on $$ I{D}_r^{*}$$. $$ \mathcal{C}$$ randomly picks b ∈ {0, 1}, computes σ* = DAE(m_b, $$ s{k}_s^{*}$$, $$ p{k}_s^{*}$$, ID_r) and outputs σ* to $$ \mathcal{F}$$.

Phase 2. $$ \mathcal{F}$$ makes queries as in Phase 1 except it neither requests a key extraction query on identity $$ I{D}_r^{*}$$ nor executes a DAD query on (σ*, $$ p{k}_s^{*}$$, $$ I{D}_r^{*}$$).

Guess. $$ \mathcal{F}$$ returns b′, and it wins the game if b′ = b.

$$ \mathcal{F}$$’s advantage is

where Pr[b′ = b] expresses the probability.

Definition 1. A PI-HDAE scheme is IND-CCA2 secure if there is a probabilistic polynomial time (PPT) adversary $$ \mathcal{F}$$ wins “IND-CCA2” game with a negligible advantage.

In the aforementioned definition, $$ \mathcal{F}$$ is permitted to gain the sender’s private key $$ S_{I{D}_s}$$ [41]. Namely, the confidentiality is retained if the $$ S_{I{D}_s}$$ is compromised.

For deniable authentication, the security concept, deniable authentication against adaptive chosen message attacks (DA-CMA) is employed in our construction.

For DA-CMA in a PI-HDAE scheme, this game below is between $$ \mathcal{F}$$ and $$ \mathcal{C}$$.

“DA-CMA” game (Game-II):

Setup. This is identical to Game-I.

Attack. This is identical to Game-I.

Forgery. $$ \mathcal{F}$$ creates a pair (σ*,$$ I{D}_r^{*}$$). $$ \mathcal{F}$$ succeeds if the conditions below are satisfied:

DAD(σ*,$$ p{k}_s^{*}$$,$$ I{D}_r^{*}$$,$$ S_{I{D}_r}$$) = m*.

$$ \mathcal{F}$$ has not issued a key extraction query on $$ I{D}_r^{*}$$.

$$ \mathcal{F}$$ has not issued a DAE query on (m*, $$ I{D}_r^{*}$$).

$$ \mathcal{F}$$’s advantage is defined as the probability that it will win.

Definition 2. A PI-HDAE scheme is DA-CMA secure if there is a PPT adversary $$ \mathcal{F}$$ wins the “DA-CMA” game with a negligible advantage.

In the aforementioned definition, $$ \mathcal{F}$$ does not issue a key extraction query on the identity $$ I{D}_r^{*}$$. This is for deniability. In other words, the two parties involved communication are able to produce a transcript with indistinguishable probability.

3.3 Data Encapsulation Mechanism (DEM)

Two algorithms are included in a DEM.

Enc: Given 1^k, a message m, and a key K, this algorithm outputs a ciphertext c. It is denoted as c = Enc(K, m).

Dec: Given a key K, and a ciphertext c, this algorithm outputs a message m or ⊥.

For a DEM, the security concept, indistinguishability against passive attackers (IND-PA) is employed in our construction. The game below is between $$ \mathcal{A}$$ and $$ \mathcal{C}$$.

IND-PA game (Game-III):

Setup. $$ \mathcal{A}$$ transmits two messages (m₀, m₁).

Challenge. $$ \mathcal{C}$$ picks K, β ∈ {0, 1}, and outputs a challenge ciphertext c* = Enc(K, m_β) to $$ \mathcal{A}$$.

Guess. $$ \mathcal{A}$$ returns β′, and it will win the game if β′ = β.

$$ \mathcal{A}$$’s advantage is

where Pr[β′ = β] expresses the probability.

Definition 3. A DEM is DA-CPA secure if there is a PPT adversary $$ \mathcal{A}$$ wins “DA-CPA” game with a negligible advantage.

4 PI-HDATK

The security notions for heterogeneous deniable authenticated tag-KEM (HDATK) are given in this section. In the designed HDATK scheme, a sender belongs to a PKI setting, while a receiver belongs to an IBC setting. PI-HDATK is denoted by this kind of DATK scheme as follows.

4.2 Security notions

The confidentiality and deniable authentication should be satisfied for the PI-HDATK scheme. For IND-CCA2 security in a PI-HDATK scheme, it is assumed that this game below is between $$ \mathcal{F}$$ and $$ \mathcal{C}$$.

“IND-CCA2” game (Game-IV):

Setup. $$ \mathcal{C}$$ performs Setup algorithm, delivers params to $$ \mathcal{F}$$ and saves s. $$ \mathcal{C}$$ also executes PKI-KG algorithm to obtain a sender’s private/public key pair ($$ s{k}_s^{*}$$, $$ p{k}_s^{*}$$). Then it delivers $$ p{k}_s^{*}$$ to $$ \mathcal{F}$$.

Phase 1. $$ \mathcal{F}$$ adaptively issues queries below.

Key extraction queries: This is identical to Game-I.

Symmetric key generation queries: $$ \mathcal{F}$$ submits a receiver’s identity ID_r to $$ \mathcal{C}$$. $$ \mathcal{C}$$ then performs $$ (K,\omega )=Sym(s{k}_s^{*},p{k}_s^{*},I{D}_r)$$, stores the state information ω, and sends the key K to $$ \mathcal{F}$$.

Encapsulation queries: $$ \mathcal{F}$$ picks a tag τ. If ω is not matched, $$ \mathcal{C}$$ outputs ⊥. If matched, $$ \mathcal{C}$$ deletes the exist one and produces ϕ = Encap(ω, τ)

Decapsulation queries: $$ \mathcal{F}$$ picks an encapsulation ϕ, a receiver’s identity ID_r, and a tag τ. $$ \mathcal{C}$$ produces $$ S_{I{D}_r}$$ by performing key extraction algorithm. It outputs the result of Decap(ϕ, τ, $$ p{k}_s^{*}$$, ID_r, $$ S_{I{D}_r}$$) to $$ \mathcal{F}$$.

Challenge. $$ \mathcal{F}$$ determines when Phase 1 is over. $$ \mathcal{F}$$ then outputs a challenge identity $$ I{D}_r^{*}$$. In phase 1, it does not support to request a key extraction query on $$ I{D}_r^{*}$$. $$ \mathcal{C}$$ executes (K₁, ω*) = Sym($$ s{k}_s^{*}$$,$$ p{k}_s^{*}$$,$$ I{D}_r^{*}$$), picks b ∈ {0, 1}, $$ K_0\in {\mathcal{K}}_{\mathcal{P}\mathcal{I}-\mathcal{H}\mathcal{D}\mathcal{A}\mathcal{T}\mathcal{K}}$$, and passes K_b to $$ \mathcal{F}$$. when $$ \mathcal{F}$$ obtains K_b, it will issue the identical queries as before. $$ \mathcal{F}$$ then returns a tag τ*. $$ \mathcal{C}$$ calculates a challenge encapsulation ϕ* = Encap(ω*, τ*) and outputs it to $$ \mathcal{F}$$.

Phase 2. $$ \mathcal{F}$$ makes queries as in Phase 1 except it neither requests a key extraction query on identity $$ I{D}_r^{*}$$ nor executes a decapsulation query on (ϕ*, τ*, $$ p{k}_s^{*}$$, $$ I{D}_r^{*}$$).

Guess. $$ \mathcal{F}$$ returns b′, and it wins the game if b′ = b.

$$ \mathcal{F}$$’s advantage is

where Pr[b′ = b] expresses the probability.

Definition 4. A PI-HDATK scheme is IND-CCA2 secure if a PPT adversary $$ \mathcal{F}$$ wins “IND-CCA2” game with negligible advantage.

In the above definition, it is allowed that $$ \mathcal{F}$$ gets the sender’s secret key $$ S_{I{D}_s}$$. Namely, the confidentiality is maintained if $$ S_{I{D}_s}$$ is compromised.

For deniable authentication, the security concept, deniable authentication against adaptive chosen message attacks (DA-CMA) is employed in our design.

For DA-CMA security in a PI-HDATK scheme, it is assumed that this game below is played between $$ \mathcal{F}$$ with $$ \mathcal{C}$$.

“DA-CMA” game(Game-V):

Setup. This is identical to Game-III.

Attack. This is identical to Game-III.

Forgery. $$ \mathcal{F}$$ creates an element (ϕ*, τ*, $$ I{D}_r^{*}$$). $$ \mathcal{F}$$ succeeds if the contexts below are met:

DAD(σ*,$$ p{k}_s^{*}$$,$$ I{D}_r^{*}$$) = m*.

$$ \mathcal{F}$$ has not issued a key extraction query on $$ I{D}_r^{*}$$.

$$ \mathcal{F}$$ has not issued a DAE query on (m*, $$ I{D}_r^{*}$$).

$$ \mathcal{F}$$’s advantage is defined as the probability that it will win.

Definition 5. A PI-HDATK scheme is DA-CMA secure if a PPT adversary $$ \mathcal{F}$$ wins the “DA-CMA” game with a negligible advantage.

In the aforementioned definition, $$ \mathcal{F}$$ does not issue a key extraction query on $$ I{D}_r^{*}$$. This is for deniability. That is, the two parties involved communication are able to produce an indistinguishable transcript.

5 A hybrid PI-HDAE scheme

Fig 2 depicts a hybrid PI-HDAE scheme that constitutes a PI-HDATK and a DEM. In DEM part, the ciphertext is a tag. This construction provides simple description. Theorems 1 and 2 present the security consequences.

Fig 2

Construction of PI-HDAE from PI-HDATK and DEM.

Theorem 1. Let a hybrid PI-HDAE scheme constitute a PI-HDATK and a DEM which are IND-CCA2 and IND-CPA secure, respectively, PI-HDAE is IND-CCA2 secure. to be specific, we receive

Proof: See Appendix 1.

Theorem 2. Let a PI-HDAE constitutes a PI-HDATK and a DEM. If PI-HDATK is DA-CMA secure, PI-HDAE is also DA-CMA secure. to be specific, we receive

Proof: Refer to Appendix 2.

6 A PI-HDATK scheme

There are six algorithms to describe our proposed scheme. Fig 3 shows the main description. In DEM part, a tag is the ciphertext. This construction provides simple description and realizes better universal security.

Fig 3

The main contribution of PI-HDATK.

6.2 Our scheme

Setup. Given G₁, G₂, P, and e as in Subsection A of Section VII. Let k be a security parameter (q ≥ 2^k) and n be a a DEM’s key length. H₁, H₂, H₃ are three cryptographic hash functions, where H₁: {0, 1}* → G₁, H₂: {0, 1}* × G₁ × G₂ → {0, 1}ⁿ and $$ H_3:{\{0,1\}}^{*}\times G_1\times G_2\to {\mathbb{Z}}_q^{*}$$. The KGC randomly selects a master key $$ s\in {\mathbb{Z}}_q^{*}$$ and calculates P_pub = sP. The public params are (G₁, G₂, e, q, n, k, P, P_pub, H₁, H₂, H₃) and a master private key is s.

PKI-KG. A user belongs to a PKI setting elecets $$ x_i\in Z_q^{*}$$ randomly as its secret key sk_i, and calculates pk_i = sk_i P as its public key. Here, i = s denotes the sender, and pk_s = x_s P, sk_s = x_s denotes the sender’s public/private key pair.

IBC-KE. A user belongs to an IBC setting gives its identity ID to the PKG. The PKG calculates its private key SK_ID = sQ_ID(Q_ID = H₁(ID)) and securely transmits it to the user. Here, ID_r denotes the receiver, and pk_r = ID_r $$ s{k}_r=S_{I{D}_r}$$ denote the receiver’s public and private key.

Sym. Given a sender’s private/public key pair (sk_s, pk_s), and a receiver’s identity ID_r, the algorithm below is done.

Pick $$ r\in {\mathbb{Z}}_q^{*}$$.

Compute $$ t=e{(P_{pub},Q_{I{D}_r})}^r$$.

Calculate K = H₂(t, pk_s, ID_r).

Return K and ω = (r, t, sk_s, pk_s, ID_r).

Encap. Given a tag τ and the state information ω, the algorithm below is done.

Compute h = H₃(τ, t, pk_s, ID_r).

Compute S = (hsk_s + r)P_pub.

Compute $$ W=e(S,Q_{I{D}_r})$$.

Compute V = hpk_s.

Compute σ = (W, V).

Decap. Given a tag τ, an encapsulation σ, a sender’s public key pk_s, a receiver’s private key $$ S_{I{D}_r}$$, identity ID_r, the algorithm below is executed.

Compute $$ t=W/e(V,S_{I{D}_r})$$.

Compute h = H₃(τ, t, pk_s, ID_r).

If V = hpk_s, output K = H₂(t, pk_s, ID_r); if not, return the symbol ⊥.

The consistency of the designed HDATK scheme can be verified. Because $$ W=e(S,Q_{I{D}_r})$$, V = hpk_s, we can get

6.3 Security

Theorems 3 and 4 offer the security consequences for PI-HDATK.

Theorem 3. Under DBDH assumption, in ROM, $$ \mathcal{F}$$ wins the IND-CCA2 game with a non-negligible advantage ϵ_datk when issuing $$ q_{H_i}$$ queries to H_i (i = 1, 2, 3), q_ke key extraction queries, q_gsk generation symmetric key queries, q_ke key encapsulation queries, and q_kd key decapsulation queries in a time t, $$ \mathcal{C}$$ resolves DBDH problem with probability

within t′ ≤ t + O(q_gsk + q_ke + q_kd)t_p, in which t_p is one paring computation.

Proof: Refer to Appendix 3.

Theorem 4. Under BDH assumption, in ROM, $$ \mathcal{F}$$ has a non-negligible advantage $$ {ϵ}_{datk}\ge 10(q_{ke}+1)(q_{ke}+q_{H_3})q_{H_1}/(2^k-1)$$ winning the DA-CMA game when issuing $$ q_{H_i}$$ queries to H_i (i = 1, 2, 3), q_ke key extraction queries, q_gsk generation symmetric key queries, q_ke key encapsulation queries, and q_kd key decapsulation queries in a time t, $$ \mathcal{C}$$ resolves BDH problem in expected time $$ t\le 120686q_{H_3}{q}_{H_1}{2}^k/{ϵ}_{datk}(2^k-1)$$.

Proof: Refer to Appendix 4.

7 Performance

We conduct a main computational cost comparison of the construction with existing schemes LZJ [35] and HDA-I of LHO [39] listed in Table 1. The point multiplication in G₁, the exponentiation calculation in G₂, the addition calculations in G₁, and the pairing calculation in G₂ are denoted by PM, EC, AD, and PC, respectively. We ignore XOR, and hash function since they are trivial. In all computational cost, the PC evaluation is the most time-consuming. From Table 1, it shows that the computation overhead of our scheme is less than that of LZJ [35], but more than that of the HDA-I of LHO [39]. It is noted that LZJ [35] is not a heterogeneous DAE scheme which is not catered for the LBS and HDA-I of LHO [39] cannot achieve confidentiality.

Table 1

Performance comparison.

Schemes	Computational cost				Security		Heterogeneity
	PM	BP	AD	EP	DA-CMA	IND-CCA2
LZJ [35]	4	3	1	1	√	√	×
HDA-I of LHO [39]	3	2	1	0	×	√	√
Ours	3	3	0	1	√	√	√

An experiment is conducted on the PBC library with A pairing [49]. The A pairing is designed on an elliptic curve y² = x³ + x mod p for some prime p ≡ 3 mod 4. As needed, we set the order of G₁ is q and the library’s embedding degree to 2. Here, 80-bit, 112-bit, and 128-bit denotes three kinds of AES [50] key size security level, respectively. Table 2 shows the description for different security levels.

Table 2

Description for different security level.

Security level	Size of P	Size of q
80-bit	512	160
112-bit	1024	224
128-bit	1536	256

We implement the experiment on an Intel Pentium(R) with 2,048 MB of RAM (2,007.04 MB available) and Dual-Core processor running at 2.69 GHz. On this machine, a PM takes 15.927 ms, and an AD requires 0.065ms employing an ECC with q of 160 bits. A PC and an EC take 26.68 ms and 3.126 ms, respectively. LZJ [35] takes 146.939 ms, HDA-I of LHO [39] takes 101.206 ms, and our scheme takes 130.947 ms. Fig 4 depicts the comparative computational cost for LZJ [35], HDA-I of LHO [39], and our scheme. From Fig 4, we can see that the implementation results are consistent with the theoretical analysis.

Fig 4

Computational cost comparison.

For the communication cost, LZJ [35], HDA-I of LHO [39], and our scheme are |m| + |G₁| + |G₂|. They possess the identical communication cost. |x| is the size of x. For 80-bit security level, |p| = 512bits, |G₁| = 1024bits, |q| = 160bits. If the standard compression techniques are used, G₁ can be reduced to 65bytes. G₂ = 1024bits = 128bytes. Therefore, the communication cost of the three schemes is |m| + |G₁| + |G₂| = | m| + 65 + 128 = |m| + 193bytes. For 112-bit security level, |p| = 1024bits, |G₁| = 2048bits, |q| = 224bits. Using the standard compression technique, G₁ can be reduced to 129bytes. G₂ = 2048bits = 256bytes. Therefore, the communication cost of the three schemes is |m| + |G₁| + |G₂| = |m| + 129 + 256 = |m| + 385bytes. For 128-bit security level, |p| = 1536bits, |G₁| = 3072bits, |q| = 256bits. Using the standard compression technique, G₁ can be reduced to 193bytes. G₂ = 3072bits = 384bytes. Therefore, the communication cost of the three schemes is |m| + |G₁| + |G₂| = |m| + 193 + 384 = |m| + 577bytes. Fig 4 shows the communication cost at different security level. It shows that from Fig 5 the 80-bit security level is our best choice for the current computing condition.

Fig 5

Communication cost at different security level.

8 Application

Zeng et al. [51] presented a deniable ring authentication for protecting the LBS privacy. In their scheme, the user’s identity is anonymous to the LBSP and he/she can deny that he/she sends the requested location information to LBSP. However, the entities are all in the same environment and the requested location information is sent in plaintext. Any adversary can monitor or intercept this sensitive information. Therefore, to better resolve this issue, utilize our designed HDAE scheme in LBS systems to render the transmitted message in ciphertext. The specific communication process is as follows:

A user in a PKI environment wants to request the location-based service m from the service provider (SP) in an identity-based environment. It first executes the PKI-KG algorithm to produce its private/public key pair (sk_s, pk_s) and executes DAE(m, sk_s, pk_s, ID_r) to create a ciphertext σ. The user then passes the resulting σ to the SP. When the SP receive the LBS request, it first requests a private key $$ S_{I{D}_r}$$ from the PKG. Then it executes DAD($$ \sigma ,p{k}_s,I{D}_r,S_{I{D}_r}$$) to get the LBS request m. It cannot send the response of m to any third party, since the third party cannot ensure whether the LBS request m is from the user or the service provider, due to the fact that the service provider can generate the same LBS request m and ciphertext σ with indistinguishable probabilities.

9 Conclusion

In this paper, we designed a hybrid DAE scheme which comprises a PI-HDAE scheme and a DEM scheme. The entities are in a heterogeneous system where the sender belongs to the PKI environment, while the receiver belongs to the IBC environment. Our construction can achieve confidentiality and deniable authentication in a single logic step. We give a formal security proof in the ROM. Our performance results show that this construction is secure and efficient. Furthermore, we present an example and apply our design to LBS system for better service.

Appendix 1

Proof: Our proof strategy is shown below. The modified games Game₀, Game₁, Game₂ are defined in [52, 53]. The games’ difference lies in how the environment replies $$ \mathcal{F}$$’s queries. $$ \mathcal{F}$$ receives the challenge ciphretext σ* = (ϕ*, c*) that encrypts either m₀ or m₁ by its challenge oracle in the light of b utilizing symmetric key K*. K* is also used in the decapsulation ϕ* with pk_s and ID_r chosen by $$ \mathcal{F}$$. In Game_i (i = 0, 1, 2), it is supposed that S_i is the event δ′ = δ. $$ \mathcal{F}$$’s challenge oracle outputs δ and $$ \mathcal{F}$$ returns δ′. $$ \mathcal{F}$$’s random oracle and $$ \mathcal{F}$$’s oracle determines the probability.

The lemma from [54] is employed as follows.

Lemma 1. Let E, E′, and F be events defined on a probability space such that Pr[E∧¬F] = Pr[E′∧¬F]. Then, we get |Pr[E] − Pr[E′]| ≤ Pr[F].

Game₀: We execute key extraction algorithm to simulate adversary’s view in a real attack. Then we utilize the produced key to reply $$ \mathcal{F}$$’s queries. Thus, the adversary’s view is identical to it in a real attack. Hence, we find

Game₁: In this game, we only alter how the DAD oracle replies $$ \mathcal{F}$$’s queries. After the calling of the challenge DAE oracle, (ϕ, c), pk_s and ID_r are submitted to the DAD oracle. If $$ p{k}_s=p{k}_s^{*}$$, $$ I{D}_r=I{D}_r^{*}$$, ϕ = ϕ*, the DAD oracle does not employ the key K, and it utilizes the key K* to decapsulate c and passes the result to $$ \mathcal{F}$$.

This change does not affect $$ \mathcal{F}$$ and so

Lemma 2. The running time of a ppt algorithm $$ {\mathcal{C}}_1$$ is identical to that of $$ \mathcal{F}$$, so we have

Proof: The proof below gives how to design $$ {\mathcal{C}}_1$$ of the PI-HDATK to be against the IND-CCA2 attack.

The game is between $$ {\mathcal{C}}_1$$ and $$ \mathcal{F}$$ as follows.

Setup: $$ {\mathcal{C}}_1$$ passes the param to $$ \mathcal{F}$$. Additionally, it also passes the sender’s public key pk_s to $$ \mathcal{F}$$.

Phase 1: $$ \mathcal{F}$$ submits a receiver’s identity ID_j to $$ {\mathcal{C}}_1$$. $$ {\mathcal{C}}_1$$ executes a key extraction (KE) query to its own oracle and transmits the response to $$ \mathcal{F}$$. When $$ \mathcal{F}$$ executes an encryption query on m, and ID_j, $$ {\mathcal{C}}_1$$ works as follows.

Issue a symmetric key generation (SKG) query on ID_j to gain K.

Calculate c = DEM.Enc(K, m).

Issue a key encapsulation (KES) query on c to gain ϕ.

Return σ = (ϕ, c).

When $$ \mathcal{F}$$ executes a key decryption (KD) query on σ = (ϕ, c), and ID_j, $$ {\mathcal{C}}_1$$ works as follows.

Issue a KD query on (ϕ, c, ID_j) to get K.

If K = ⊥, abort.

Calculate m = DEM.Dec(K, c) and output m.

Challenge: $$ \mathcal{F}$$ produces a challenge identity ID_j and messages (m₀, m₁) with equal-lengths. $$ {\mathcal{C}}_1$$ works as follows.

Pass ID_j to its challenger to gain K_β for β ∈ {0, 1}.

Elect δ ∈ {0, 1}.

Compute c* = DEM.Enc(K_δ, m_δ).

Pass c* to its challenger to gain ϕ*.

Return σ* = (ϕ*, c*) to $$ \mathcal{F}$$.

Phase 2: $$ \mathcal{F}$$ issues queries just like in phase 1 except for requesting a KE query on ID_r and a KD query on σ* = (ϕ*, c*) to gain the corresponding message.

Guess: $$ \mathcal{F}$$ returns δ′. If δ′ = δ, $$ {\mathcal{C}}_1$$ returns b′ = 1 which means K_b is a genuine key; or else it returns b′ = 0 which means K_b is a random key.

When K_b is a genuine key, $$ \mathcal{F}$$ is performed just like it in Game₁. It means

Lemma 3. The running time of a ppt algorithm $$ {\mathcal{C}}_2$$ is identical to that of $$ \mathcal{F}$$, so

Proof: The proof below gives how to design $$ {\mathcal{C}}_2$$ of the PI-HDATK to be against the IND-PA attack. $$ \mathcal{F}$$ is run just like the manner in game Game₂. Before $$ \mathcal{F}$$ calls its challenge DAE query, we perform the key extraction algorithm to answer $$ \mathcal{F}$$’s query. When $$ \mathcal{F}$$ issues its challenge DAE query on identity $$ I{D}_r^{*}$$, and two messages (m₀, m₁), we just transfer (m₀, m₁) to $$ {\mathcal{C}}_2$$’s challenge encapsulation oracle to gain c*. We then issue a GSK query to have K* and issue a KES query to have ϕ*. We transmit (ϕ*, c*) to $$ \mathcal{F}$$ and drop K*.

Pr[S₂] is the probability that $$ {\mathcal{C}}_2$$ pinpoints the challenge encapsulation oracle’s hidden bits due to that $$ {\mathcal{C}}_2$$ returns whatever $$ \mathcal{F}$$ returns.

Appendix 2

Proof: $$ \mathcal{F}$$ attacks the PI-HDAE scheme with advantage $$ Ad{v}_{PI-HDAE}^{DA-CMA}\left(\mathcal{F}\right)$$. $$ \mathcal{C}$$ attacks DA-CMA for PI-HDATK with advantage at least $$ Ad{v}_{PI-HDAE}^{DA-CMA}\left(\mathcal{F}\right)$$. We issue $$ \mathcal{F}$$’s queries below.

Setup: $$ \mathcal{C}$$ passes the param to $$ \mathcal{F}$$. Additionally, $$ \mathcal{C}$$ also transmits pk_s to $$ \mathcal{F}$$.

Attack: When $$ \mathcal{F}$$ submits an ID_j to $$ \mathcal{C}$$, $$ \mathcal{C}$$ executes a KE query to its own oracles and passes the response to $$ \mathcal{F}$$. When $$ \mathcal{F}$$ performs a DAE query on m, and ID_j, $$ \mathcal{C}$$ issues the SKG query, KES query and KD query just like $$ {\mathcal{C}}_1$$ works in Lemma 2.

Fogery: $$ \mathcal{F}$$ outputs $$ (m^{*},{\sigma }^{*},I{D}_r^{*})$$, where σ* = (ϕ*, c*). $$ \mathcal{C}$$ returns $$ ({\tau }^{*},{\varphi }^{*},I{D}_r^{*})$$, where τ* = c*.

Visibly, this is a perfect proof. If $$ \mathcal{F}$$ wins the DA-CMA game for PI-HDAE, $$ \mathcal{C}$$ has the identical advantage to win the DA-CMA game for PI-HDATK.

Appendix 3

Proof: $$ \mathcal{C}$$ gets an input (P, aP, bP, cP) of DBDH problem and purposes to decide if θ = e(P, P)^abc. $$ \mathcal{C}$$ is a challenger and performs $$ \mathcal{F}$$ as a subroutine. $$ \mathcal{C}$$ responds to $$ \mathcal{F}$$’s queries on H₁, H₂ and H₃ and these answers are created randomly. $$ \mathcal{C}$$ reserves lists L₁, L₂ and L₃ to keep the answers. The assumptions are made as follows.

Before $$ \mathcal{F}$$ issues KE queries, GSK queries, KES queries and KD queries on identity ID, $$ \mathcal{F}$$ will first inquire H_ID.

A KES query’s encapsulation ciphertext will not be employed in a KD query.

Setup: $$ \mathcal{C}$$ transmits system parameters with P_pub = cP to $$ \mathcal{F}$$ in which c is unknown to $$ \mathcal{C}$$. Additionally, $$ \mathcal{C}$$ produces sender’s (sk_s, pk_s) and transmits public key pk_s to $$ \mathcal{F}$$.

Phase 1: $$ \mathcal{F}$$ issues queries as follows.

H₁ queries: $$ \mathcal{C}$$ picks $$ \gamma \in \{1,2,\dots ,q_{H_1}\}$$. $$ \mathcal{F}$$ requests H₁ queries on its choice identities. At the γ-th query, $$ \mathcal{C}$$ replies by H₁(ID_γ) = bP. At the j-th query with j ≠ γ, $$ \mathcal{C}$$ picks $$ w_j\in Z_q^{*}$$, adds (ID_j, w_j) in the list L₁ and responds H₁(ID_j) = w_j P.

H₂, H₃ queries: When $$ \mathcal{F}$$ issues hash value queries, $$ \mathcal{C}$$ checks whether the corresponding items are included in the lists. If yes, $$ \mathcal{F}$$ will get the same answer; otherwise, $$ \mathcal{F}$$ will get a random value. The value and query will be added in the list.

Key extraction queries: When $$ \mathcal{F}$$ issues key extraction queries on receiver’s identity ID_j. If ID_j = ID_γ, $$ \mathcal{C}$$ aborts. If not, L₁ must comprise (ID_j, w_j) (it implies $$ \mathcal{C}$$ has replied H₁(ID_j) = w_j P.) The private key cH₁(ID_j) = w_j cP = w_j P_pub is calculated by $$ \mathcal{C}$$ and transmitted to $$ \mathcal{F}$$.

Generation symmetric key queries: $$ \mathcal{F}$$ submits an ID_j to $$ \mathcal{C}$$. $$ \mathcal{C}$$ then executes (K, ω) = Sym(sk_s, pk_s, ID_j) and passes K to $$ \mathcal{F}$$. $$ \mathcal{C}$$ saves ω and overwrites the previous value.

Key encapsulation queries: $$ \mathcal{F}$$ creates τ. $$ \mathcal{C}$$ checks if ω already exists. If not, $$ \mathcal{C}$$ aborts. Or else, $$ \mathcal{C}$$ just executes ϕ = Encap(ω, τ) and transmits the encapsulation ciphertext ϕ to $$ \mathcal{F}$$.

Key decapsulation queries: $$ \mathcal{F}$$ sends the receiver’s identity ID_j, a tag τ, and an encapsulation ϕ. If ID_j = ID_γ, (ϕ, τ) is invalid. If $$ \mathcal{F}$$ requests H₃(t, τ, pk_s, ID_j), where $$ t=W/e(V,S_{I{D}_j})$$, $$ \mathcal{C}$$ replies h that coincides with V = hpk_s, it aborts. From $$ \mathcal{F}$$’s perspective, σ = (W, V) is valid. The probability is at most 1/2^k. If ID_j ≠ ID_γ, $$ \mathcal{C}$$ gains $$ S_{I{D}_j}$$ by performing the key extraction query. It then passes the result of $$ Decap(\sigma ,\tau ,S_{I{D}_j})$$ to $$ \mathcal{F}$$.

Challenge: $$ \mathcal{F}$$ determines when phase 1 is over. It generates a receiver’s challenge identity ID_r. If $$ \mathcal{F}$$ has issued a key extraction query on ID_γ, $$ \mathcal{C}$$ aborts. If $$ \mathcal{F}$$ does not pick ID_r = ID_γ as the target identity, it aborts too. $$ \mathcal{C}$$ picks W* ∈ G₂, sets V* = aP and computes t* = W*/θ (θ is DBDH problem’s candidate). Then $$ \mathcal{C}$$ issues H₂ query to look for K₁ = H₂(t*). $$ \mathcal{C}$$ randomly picks K₀, β ∈ (0, 1), and passes K_β to $$ \mathcal{F}$$. $$ \mathcal{F}$$ then passes τ* to $$ \mathcal{C}$$. Whereafter, $$ \mathcal{C}$$ transmits σ* = (W*, V*) to $$ \mathcal{F}$$.

Phase 2: $$ \mathcal{F}$$ issues queries as in phase 1 except that it has no ability to issue a KE query on ID_r and a KD query on (ϕ*, τ*) to gain the symmetric key.

Guess: $$ \mathcal{F}$$ outputs β′ for (K_β, ω*) = Sym(sk_s, pk_s, ID_r) and ϕ* = Encap(ω*, τ*) hold. If β′ = β, $$ \mathcal{C}$$ outputs 1 shows θ = e(P, P)^abc; If not, $$ \mathcal{C}$$ outputs 0 shows θ ≠ e(P, P)^abc.

Now we calculate $$ \mathcal{C}$$’s successful probability. If one of the events below is satisfied, $$ \mathcal{C}$$ will fail:

E₁ $$ \mathcal{F}$$ does not pick ID_γ as the receiver’s identity in challenge phase.

E₂ $$ \mathcal{F}$$ has issued a KE query on ID_γ.

E₃ $$ \mathcal{C}$$ terminates in a KD query due to it refuses a valid encapsulation.

We show that Pr[¬E₁] = 1/$$ q_{H_1}$$, and Pr[E₃] ≤ q_kd/2^k. Additionally, ¬E₁ means ¬E₂.

Because

p₁ = Pr[β′ = β∣(K_β, ω*) = Sym(pk_s, sk_s, ID_r)] and $$ \varphi *=Encap(\omega *,\tau *)=\frac{ϵ+1}{2}-\frac{q_{kd}}{2^k}$$

and

$$ p_0=\text{Pr}[{\beta }^{\prime }=i|\theta {\in }_R{G}_2]=\frac{1}{2}$$ for i = 0, 1,

We get

O(q_gsk + q_ke + q_kd) is $$ \mathcal{C}$$’s computation time that shows pairing computations in GSK queries, KE queries and KD queries.

Appendix 4

Proof: we have to let our design fit into the signature scheme described in [54], where the simulation step can be simulated in the absence of the sender’s private key (i.e., absence of the master private key). On this occasion, we need an approach to resolve the BDH problem.

First, we observe that the PI-HDATK scheme accords with the requested three-phase honest-verifier zero-knowledge identification protocol, where σ₁ = t is the commitment, h = H₃(τ, t, pk_s, ID_r) is the hash value, and σ₂ = W is the answer.

Second, a simulation step is shown and an approach of how to resolve the BDH problem is given. Given (P, aP, bP, cP) of BDH problem, $$ \mathcal{C}$$ needs to compute h = e(P, P)^abc. $$ \mathcal{C}$$ performs $$ \mathcal{F}$$ as a subroutine. $$ \mathcal{F}$$ consults $$ \mathcal{C}$$ to reply H₁, H₂, and H₃ and $$ \mathcal{C}$$ holds L₁, L₂, and L₃ to preserve the resulting responses. The process below is depicted.

Setup: $$ \mathcal{C}$$ calculates params with P_pub = cP and passes them to $$ \mathcal{F}$$. Additionally, $$ \mathcal{C}$$ also transmits pk_s = aP to $$ \mathcal{F}$$.

Attack: $$ \mathcal{F}$$ executes the following queries.

H₁ queries $$ \mathcal{C}$$ picks $$ \gamma \in \{1,2,\dots ,q_{H_1}\}$$. $$ \mathcal{F}$$ requests H₁ queries on its choice identities. At the γ-th query, $$ \mathcal{C}$$ replies by H₁(ID_γ) = bP. At the j-th query with j ≠ γ, $$ \mathcal{C}$$ picks $$ w_j\in Z_q^{*}$$, inserts (ID_j, w_j) in the list L₁ and responds H₁(ID_j) = w_j P.

H₂, H₃ queries, KE queries, GSK queries, KES queries, and KD queries are identical to them in Theorem 3.

Fogery: $$ \mathcal{F}$$ outputs a triple (σ*, τ*, ID_γ), where σ* = (W*, V*). We coalesce ID_γ and τ* into a “generalized” forged tag (ID_γ, τ*) to hide the identity-based aspect of the DA-CMA attack, and simulate the setting of an identity-less adaptive-CMA existential forgery. If $$ \mathcal{F}$$ is an efficient forger, then we have the capability to constitute a Las Vegas machine $$ {\mathcal{F}}^{\prime }$$ that outputs ((ID_γ, τ*), h*, σ*) and $$ ((I{D}_{\gamma },{\tau }^{*}),{\overline{h}}^{*},{\overline{\sigma }}^{*})$$ with $$ h^{*}\ne {\overline{h}}^{*}$$ and the same commitment t*. To resolve the BDH problem based on the machine $$ {\mathcal{F}}^{\prime }$$, we constitute a machine $$ {\mathcal{C}}^{\prime }$$ as follows.

$$ {\mathcal{C}}^{\prime }$$ performs $$ {\mathcal{F}}^{\prime }$$ to gain two distinct signatures ((ID_γ, τ*), h*, σ*) and ($$ (I{D}_{\gamma },{\tau }^{*}),{\overline{h}}^{*},{\overline{\sigma }}^{*}$$).

$$ {\mathcal{C}}^{\prime }$$ computes e(P, P)^abc as $$ {(W^{*}/{\overline{W}}^{*})}^{1/(h^{*}-{\overline{h}}^{*})}$$.

From the forking lemma [54] and the lemma on relationship between given-identity and chosen-identity attack [55], if $$ \mathcal{F}$$ succeeds with probability $$ {ϵ}_{datk}\ge 10(q_{ke}+1)(q_{ke}+q_{H_3})q_{H_1}/(2^k-1))$$ in time t, then $$ {\mathcal{C}}^{\prime }$$ resolves the BDH problem in expected time $$ t\le 120686q_{H_3}{q}_{H_1}{2}^k/{ϵ}_{datk}(2^k-1)$$.