1 Introduction

The idea of Identity based encryption scheme (IBE) was formulated by shamir in the early 1980s. Shamir’s original motivation was to simplify certificate management in email systems. The intuitive flexibility and convenience of using an arbitrary string as a public key made many practical applications of IBE quickly apparent. An IBE scheme is an asymmetric system wherein the public key is effectively replaced by a user’s publicly available identity information or any arbitrary string which derived from the user’s identity. It enables any pair of users to communicate securely without exchanging public or private keys and without keeping any key directories. The service of a third party which we called private key generator (PKG) is needed whose sole purpose is to generate private key for the user. The private key is computed using the PKG’s master-key and the identity of the user, and it’s very useful in the field of cloud computing Shen et al. 2015; Wang et al. 2017b; Xu et al. 2018.

Since the presentation of the idea from Shamir, several IBE schemes have emerged in the literature, based on various hard problems, for example in Desmedt and Quisquater 1986; Tanaka 1987. Unfortunately, most of the proposed schemes are impractical or insecure. However, it was not until 2001 that the Boneh–Franklin scheme Boneh and Franklin 2001 introduced the first working IBE system building on the progress in elliptic curves with bilinear pairings. Its publication was quickly gave rise to a number of follow-up works Waters 2005; Canetti et al. 2007; Li et al. 2015; Pan et al. 2016. Specifically, the system is based on bilinear maps between groups realized through the Weil pairing or Tate pairing, while the computational cost of the multiply and exponent operation using pairing is slowly and inefficiency in implementation.

Soon after the Boneh–Franklin scheme, a totally different approach was put forward by Cocks (2001) who introduced an elegant IBE scheme based on the standard quadratic residuosity (QR) problem. Cocks IBE scheme only requires elementary mathematics, encryption merely involves a couple of operations modulo an RSA modulus and the evaluation of Jacobi symbols. Its security rests on the standard quadratic residuosity assumption in the random oracle model. Cocks IBE, however, encrypts the message bit by bit and thus it is considered very bandwidth consuming. Despite its simplicity, Cocks’ scheme received less attention from the research community, compared to the pairing-based constructions.

1.1 Related works

A long standing open problem since Cocks (2001) is the construction of a space efficient IBE system without pairings. From efficiency considerations, and that motivates us to find alternative constructions.

Since Cocks’ pioneering work, there has been a flurry of variants, aiming at dealing with the issue of bandwidth or offering extra properties. At FOCS’07, Boneh et al. (2007) made the first successful attempt to propose a space-efficient IBE scheme relied on the theory of ternary quadratic forms. Both use a RSA composite and while the Cocks scheme utilizes this concept in a bitwise encryption algorithm which encrypts each bit individually, thus expanding an \(\ell\)-bit plaintext to a ciphertext of size \(2\ell \log _{2}N\), the latter scheme would only expand it to about a size of \(\ell +\log _{2}N\). Unfortunately, this scheme has short ciphertexts but rather large private keys, and both the encryption and decryption algorithms require non-trivial computational effort, observably slower than the Cocks system.

Subsequently, Cocks’ cryptosystem was extended by Boneh et al. (2013) with multiple bit encryption. This scheme was shown to be secure under a modified higher power residuosity assumption (which generalizes the quadratic residuosity assumption). As explained in Boneh et al. 2013, these schemes are however less efficient, bandwidth-wise, than the original Cocks scheme. While it is currently inefficient, it shows that a generalization is possible, which may be able to be made efficient in the future.

Note that in 2009, Paterson and Srinivasan also proposed an IBE scheme from another direction, based on factorization assumption and discrete logarithm related assumptions simultaneously. It is reasonable both in space and in time-consuming, but the private key extracting algorithm is inefficient. Moreover, Meshram (2015) made a further improvement on the same intractable assumption, Thus, the scheme is in practice limited to the number of private key extraction queries. Other generalizations and extensions of the Cocks IBE scheme can be found in Ateniese and Gasti 2009; Clear et al. 2014.That is worth mentioning, an entirely different approach to IBE, based on lattices, was introduced by Gentry et al. (2008). Their IBE scheme enjoys efficient encryption and decryption, but has large public parameters and private keys. It also remains to be seen how parameters should be selected in practice for this scheme in order to attain a given level of security. Very recently, Döttling and Garg (2017) gave a beautiful construction of IBE using new primitives called chameleon encryption or one-time signatures with encryption.

1.2 Our contributions

In this study, we deal with the problem of constructing an IBE scheme without pairings, from Paillier’s original scheme based on composite residuosity problem Paillier 1999, which is efficient and practical while meets a strong security requirement. Then we transform the basic scheme into enhanced one by applying the technique in Fujisaki and Okamoto 1999 to design a mediated IBE scheme secure against more powerful attacks (CCA). It should be noted that, our basic scheme is additively homomorphic and anonymous. In particular, it can now be used in applications where computing over ciphertexts is required. Typical applications include electronic voting, auction systems, private information retrieval, or cloud computing Liu et al. 2015; Chen et al. 2016; Wang et al. 2017a.

1.3 Outline of the paper

The rest of this paper is organized as follows: Some preliminaries such as basic facts, definitions and security models are given in next section. In Sect. 3, we present our proposed new efficient identity-based encryption scheme. Section 4 gives the security analysis as well as security proof. In Sect. 5, the enhanced scheme against chosen-ciphertext attacks is presented. The comparison of the previous ralated scheme is discussed in Sect. 6. Finally, some concluding remarks are made in Sect. 7.

2 Preliminaries

The Paillier encryption scheme Paillier 1999 is a probabilistic public key algorithm. The problem of computing N-th residue classes is believed to be computationally difficult. The decisional composite residuosity assumption is the intractability hypothesis upon which this cryptosystem is based.

In this section, we briefly describe some useful background knowledge. We first review the mathematical primitive that plays on central role in the previous scheme.

2.1 Definitions and notations

Let N be a positive integer, we write \(\mathbb {Z}_{N}\) for the ring of residue classes modulo N, and \(\mathbb {Z}_{N}^{*}\) for its multiplicative group. As usual, we say that a function f from the natural numbers to the non-negative real numbers is negligible if for every positive polynomial there is an N such that for all integers \(n>N\) it holds that \(f(n)<1/poly(n)\). We typically denote an arbitrary negligible function by negl(n). The probabilistic polynomial time is abbreviated as PPT.

2.2 Paillier encryption scheme

Let \(N= pq\) be a safe-prime modulus, i.e. p and q are large primes of the form \(p= 2p^{\prime }+1\) and \(q= 2q^{\prime }+1\), where \(p^{\prime }\) and \(q^{\prime }\) are also different primes. We will denote by \(\varphi (N)\) Euler’s totient function and by \(\lambda (N)\) Carmichael’s function on N, i.e. \(\varphi (N)= (p-1)(q-1)\) and \(\lambda (N)= lcm(p-1, q-1)\), respectively. From now, we adopt \(\lambda\) instead of \(\lambda (N)\) for visual comfort. And that \(gcd(p-1, q-1)=2\), which yields \(\varphi (N)= 2\lambda\). Let \(N=pq\) be a modulus chosen as above and \(g\in \mathbb {Z}_{N^{2}}^{*}\). It is shown that the integer-valued function \(\varepsilon _{g}\) defined as follows:

$$\begin{aligned} \mathbb {Z}_{N} \times \mathbb {Z}_{N}^{*} \longrightarrow \mathbb {Z}_{N^{2}}^{*} \end{aligned}$$

with

$$\begin{aligned} \varepsilon _{g}(x, y)=g^{x}y^{N}\pmod {N^{2}} \end{aligned}$$

is a bijection if \(ord(g)= \alpha N\), where \(\alpha \ge 1\). Then given \(\forall \omega \in \mathbb {Z}_{N^{2}}^{*}\), the unique \(x \in \mathbb {Z}_{N}\) for which there exists some \(y \in \mathbb {Z}_{N}^{*}\) such that \(\omega = \varepsilon _{g}(x, y)\) is called the N-residuosity class of \(\omega\) relative to g, denoted by g. Accordingly, the message is recovered by means of computing

$$\begin{aligned} m= \frac{L({c}^{\lambda }~mod~{N^{2}})}{L(g^{\lambda }~mod~{N^{2}})}\pmod {N} \end{aligned}$$

One can observe that the set \(\mathbb {S}= \{u< N^{2}| u \equiv 1\pmod {N}\}\), over which the function L such that \(\forall u \in \mathbb {S}\), \(L(x)=\frac{x-1}{N}\) is clearly well-defined.

Lemma 1

The Carmichael’s theorem implies that \(\forall g \in \mathbb {Z}_{N^{2}}^{*},\) we have

$$\begin{aligned} \left\{ \begin{array}{ll} g^{\lambda } \equiv 1 &\quad ({\rm mod}\, {N}) \\ g^{N\cdot \lambda }\equiv 1 &\quad ({\rm mod}\,{N^{2}}) \end{array}\right. \end{aligned}$$
(1)

Proof

Since \(\varphi (p)= (p-1)\), \(\varphi (q)= (q-1)\). \(gcd(p-1, q-1)=2\) as well as \(\varphi (N)= 2\lambda\), which yelds \(\varphi (p), \varphi (q) |\lambda\). So we have

$$\begin{aligned} \left\{ \begin{array}{ll} g^{\lambda } \equiv 1\pmod {p} & \\ & \\ g^{\lambda }\equiv 1\pmod {q} & \end{array}\right. \end{aligned}$$

From Chinese Remainder Theorem, implies \(g^{\lambda } \equiv 1\pmod {N}\). Futhermore, Carmichael function \(\lambda (N^{2})=N\cdot \lambda\), hence

$$\begin{aligned} g^{N\cdot \lambda }\equiv 1\pmod {N^{2}} \end{aligned}$$

\(\square\)

2.3 Identity-based encryption model

A general study of the definition and security model of Identity Based Encryption has been driven from Boneh and Franklin (2001), we therefore refer the reader to this paper for more detail, concluding with a complete hierarchy.

3 A new identity-based encryption scheme

Motivated by Paillier 1999; Cramer and Shoup 2002; Bresson et al. 2003, we construct a new efficient IBE scheme without pairings.

For decreasing the decryption complexity, the ciphertext space was restricted to subgroup \(\langle g \rangle\) of \(\mathbb {Z}_{N^{2}}^{*}\) in the original Paillier scheme (see Paillier (1999), section 6). Accordingly, we define \(\mathbb {G}=\{x \in \mathbb {Z}_{N^{2}}^{*} ~| x \equiv {y^{2}} ~mod{N^2}, \exists y \in \mathbb {Z}_{N^{2}}\}\) is the cyclic subgroup of quadratic residues modulo \(N^{2}\). For the order of group \(\mathbb {G}\), denotes \(ord(\mathbb {G})\), so we have

$$\begin{aligned} ord(\mathbb {G}) = \frac{{\varphi ({N^2})}}{4} = \frac{{N \cdot \varphi (N)}}{4} = \frac{{N \cdot \lambda }}{2} \end{aligned}$$
(2)

If one denotes by \(\nu\) the inverse of 2 modulo N, according to Lemma 1, it can get the following corollaries:

Corollary 1

In the cyclic group\(\mathbb {Z}_{N^{2}}^{*}\), every element of orderN, can be rewritten as the form\(\alpha = (1 + kN)\), where\(k \in \{1, 2, \cdots, N \}\).

Corollary 2

The elements of orderNin\(\mathbb {Z}_{N^{2}}^{*}\), also belong to the cyclic subgroup of quadratic residues modulo\(N^{2}\), i.e. \(\alpha \in \mathbb {G}\)which is\(2\nu \equiv 1 \bmod {N}\)

$$\begin{aligned} \alpha = 1+kN =(1+ \nu kN)^{2} \pmod {N^{2}} \end{aligned}$$

Corollary 3

For every element\(s \in \mathbb {G}\), there exists\(\varepsilon \in \mathbb {Z_{N}}\), i.e.

$$\begin{aligned} s^{\frac{\lambda }{2}}=\big (1+\varepsilon \cdot N \big )\pmod {N^{2}} \end{aligned}$$

Proof

Note that, from eq. 2, \(ord(\mathbb {G}) = \frac{{N \cdot \lambda }}{2}\), in the cyclic group \(\mathbb {G}\) we have

$$\begin{aligned} {s^{\frac{{\lambda \cdot N}}{2}}} = 1\pmod {N^2} \end{aligned}$$

that is

$$\begin{aligned} (s^{\frac{\lambda }{2}})^{N} = 1\pmod {N^2} \end{aligned}$$

with eq. 1, there exists \(\varepsilon \in \mathbb {Z_{N}}\), i.e.

$$\begin{aligned} s^{\frac{\lambda }{2}} = \big (1+\varepsilon \cdot N \big ) \pmod {N^2} \end{aligned}$$

\(\square\)

3.1 The intractable problems over \(\mathbb {Z}_{N^{2}}^{*}\)

In this subsection, we will follow the presentation of Paillier (1999). It defined the Partial Discrete Logarithm, abbreviated as PDL. Given g and \(h\equiv g^{x} \bmod {N^{2}}\), computing x is infeasible.

Assumption 1

(PDL) For any probabilistic polynomial time algorithm \(\mathcal {A}\), there exists a negligible function negl(n) such that

$$\begin{aligned} Adv_{\mathcal {A}}^{PDL}=Pr\Big [(\mathcal {A}(g,h,N=x)\wedge (h\equiv g^{x}\bmod {N^{2}})\Big ]\le negl(n) \end{aligned}$$

Assumption 2

(DDH) Given \(N=pq\), \(X= {g^x}\bmod {N^2}\), \(Y= {g^y}\bmod {N^2}\) and \(Z= {g^z}\bmod {N^2}\), to decide whether \(z= xy \bmod (ord(\mathbb {G}))\) or not. For any probabilistic polynomial time algorithm \(\mathcal {A}\), there exists a negligible function negl(n) such that

$$\begin{aligned} Adv_\mathcal {A}^{DDH} = \Big | Pr[\mathcal {A}(N, g, X, Y, g^{xy}) = 1] - Pr[\mathcal {A}(N, g, X, Y, Z) = 1] \Big | \le negl(n) \end{aligned}$$

For modulo \(N^{2}\), it can be compute \(Z(\bmod N)\) in line with \(Z(\bmod N^{2})\), similarly with the well known CDH problem, the Modified computatial Diffie–Hellman problem, denotes MDH assumption.

Assumption 3

(MDH) Given \(N=pq\), \(X= {g^x}\bmod {N^2}\), \(Y= {g^y}\bmod {N^2}\) and \(z= g^{xy}\bmod {N}\), to compute \(Z= g^{xy}\bmod {N^{2}}\). For any probabilistic polynomial time algorithm \(\mathcal {A}\), there exists a negligible function negl(n) such that

$$\begin{aligned} Adv_\mathcal {A}^{MDH}=Pr\Big [\mathcal {A}(N, g, X, Y, z\bmod ~N) = Z\bmod {N^2}\Big ]\le negl(n) \end{aligned}$$

With the following theorem we make explicit the relation existing between the PDL problem and MDH problem.

Theorem 1

If the PDL assumption is tenable then so is the MDH assumption.

Proof

Assume that the MDH problem can be easily solved, there exists a probabilistic polynomial time algorithm \(\mathcal {B}\) requre the result \(Z= g^{xy}(\bmod {~N^{2}})\), where it is given as input a random MDH three-tuple (X, Y, z). Then we can construct an PPT algorithm \(\mathcal {A}\) that attempts to solve PDL problem using algorithm \(\mathcal {B}\) as a subroutine.

Consider the PDL problem, that is given as input a value \(h\equiv g^{x} (\bmod ~{N^{2}})\) and tries to compute x. Since \(x \in \big [1, ord(\mathbb {G}) \big ]\), there exists \(x_{1}, x_{2} \in \mathbb {Z}_{N}\), i.e. \(x=x_{1} + x_{2}N\). That is to say, \(\mathcal {A}\) try to find \(x_{1}, x_{2}\) with \(h\equiv g^{x_{1} + x_{2}N} (\bmod {N^{2}})\).

For convenience, let g is a generator of cyclic group \(\mathbb {G}\), then \(ord(g) = \frac{{N \cdot \lambda }}{2}\). So a quadratic residue \(c \in \mathbb {G}\) can be generated by g, there is \(r_{1} \in \mathbb {Z}_{\lambda }\) as well as \(r_{2} \in \mathbb {Z}_{N}\) that the equality \(c\equiv g^{r_{1} + \lambda r_{2}} (~\bmod {N^{2}})\) holds. Therefore

$$\begin{aligned} ord\big (g^{\lambda }\big )&= \dfrac{ord(g)}{\big (\lambda ,ord(g)\big )}=\dfrac{\frac{\lambda \cdot N}{2}}{(\lambda ,~\frac{\lambda \cdot N}{2})}=N \end{aligned}$$

Recall the Corollary 3, let \(\varepsilon = 1\), we have

$$\begin{aligned} g^{\lambda }= (1+N) \pmod {N^{2}} \end{aligned}$$

The algorithm \(\mathcal {A}\) call the algorithm \(\mathcal {B}\) and make use of any values it outputs. Let \(X= h\), \(Y= c\) and \(z= X^{r_{1}}(\bmod ~{N})\), that is (X, Y, z) regard as input instantiation, plugged into algorithm \(\mathcal {A}\). Now

$$\begin{aligned} Y&= g^{r_{1} + \lambda r_{2}}=g^{r_{1}} \cdot g^{\lambda r_{2}}\\&= g^{r_{1}}\cdot (1 + N)^{r_{2}}\\&= g^{r_{1}}\cdot \big (1 + N\cdot r_{2}\big ) \pmod {N^{2}} \end{aligned}$$

Suppose \(t= \varepsilon ^{-1}(\bmod ~{N})\), then

$$\begin{aligned} Y&= g^{r_{1}}\big (1+\varepsilon \varepsilon ^{-1}Nr_{2}\big )\\&= g^{r_{1}}\big (1 + \varepsilon tNr_{2}\big )\\&= g^{r_{1}}\big (1 + \varepsilon N\big )^{tr_{2}}\\&= g^{\big (r_{1} + \dfrac{\lambda tr_{2}}{2}\big )} \pmod {N^{2}} \end{aligned}$$

When \(\mathcal {A}\) is given instance (X, Y, z), it can obtain the result \(Z^{*}\) from \(\mathcal {B}\),

$$\begin{aligned} Z^{*} = {g^{\big ({x_1} + {x_2}N\big )\big ({r_1} + \dfrac{{\lambda t{r_2}}}{2}\big )}} \pmod {N^{2}} \end{aligned}$$

Since

$$\begin{aligned}&\big ({x_1} + {x_2}N\big )\big ({r_1} + \dfrac{{\lambda t{r_2}}}{2}\big )\\&= (x_{1}+x_{2}N)r_{1}+\dfrac{\lambda tx_{1}r_{2}}{2}+\dfrac{\lambda Ntx_{2}r_{2}}{2} \end{aligned}$$

For \(ord(g)=\dfrac{{N\lambda }}{2}\), therefore

$$\begin{aligned} Z^{*}&= X^{r_{1}}\cdot \big (g^{\frac{\lambda }{2}}\big )^{tx_{1}r_{2}}\\&= X^{r_{1}}\cdot \big (1+\varepsilon N\big )^{tx_{1}r_{2}}\\&= X^{r_{1}}\cdot \big (1+x_{1}r_{2}N\big ) \pmod {N^{2}} \end{aligned}$$

It follows that \(\dfrac{Z^{*}}{X^{r_{1}}}=\big (1+x_{1}r_{2}N\big ) \pmod {N^{2}}\).

To sum up, along with N is known, \(x_{1},x_{2}, r_{2}\in \mathbb {Z}_{N}\). Hence, algorithm \(\mathcal {A}\) can compute \(x_{1}\), \(x_{2}\) with non-negligible probability, it shows that the PPT algorithm \(\mathcal {A}\) can solve PDL problem. This would contradict Assumption 1, and thus cannot happen. \(\square\)

3.2 Description of the proposed scheme

In this section, we proposed an Identity Based Encryption scheme based on intractable Partial Discrete Logarithm (DLP) problem and Modified computatial Diffie–Hellman (MDH) problem over \(\mathbb {Z}_{N^{2}}^{*}\). Our basic IBE scheme is defined to be a four-tuple of algorithms, (Setup, Extract, Encrypt, Decrypt) are constructed as follows.

  1. 1.

    Setup: PKG run the algorithm on input the security parameter \(1^{\kappa }\):

    • It generates the safe-prime modulus \(N=pq\), i.e. p and q are large primes of the form \(p= 2p^{\prime }+1\) and \(q= 2q^{\prime }+1\).

    • Choose a secure cryptographic hash function \(\mathcal {H}:~{\left\{ {0, 1} \right\} ^*} \rightarrow \mathbb {Z}_{N^{2}}^{*}\).

  2. 2.

    Extract: For a given string \(ID \in {\left\{ {0, 1} \right\} ^{*}}\), the algorithm does:

    • Compute hash function \(a= \mathcal {H}(ID)\), let \(s= a^{2} \pmod {N^{2}}\).

    • Pick a random \(d\in [1, ord(\mathbb {G})]\) and set \(h= s^{d} \pmod {N^{2}}\).

    • Send the private decrypt key d to user.

    • The public parameters \(\{ N, \mathcal {H}, h\}\), and keep the msk \(\{ p, q\}\) secret.

  3. 3.

    Encrypt: When sending an encrypted message \(m \in \mathbb {Z}_{N}\) to a user with identity information ID,

    • Compute hash function \(a= \mathcal {H}(ID)\), let \(s= a^{2} \pmod {N^{2}}\).

    • Pick a random \(r \in \mathbb {Z}_{N^{2}}\), send the ciphertext \(\mathcal {C} = ({c_1}, {c_2})\) where

      $$\begin{aligned} c_{1}&=s^{r} \pmod {N^{2}} \\ c_{2}&=(1+N)^{m}\cdot h^{r}\pmod {N^{2}} \end{aligned}$$
  4. 4.

    Decrypt: To decrypt ciphertext \(\mathcal {C} = ({c_1},~{c_2})\), with decrypt key d the recipient outputs plaintext

    $$\begin{aligned} m = \dfrac{\Big (c_{2} \cdot c_{1}^{-d} - 1\Big )(\bmod {~N^{2}})}{N} \end{aligned}$$

Correctness: Assuming the ciphertext is well-formed for ID, according to the Binomial Expansion \((a+b)^{n} = \sum \limits _{i = 0}^{n} {C_{n}^{i}\cdot a^{n-i}\cdot b^{i}}\), we have

$$\begin{aligned} {(1 + N)^m}&= C_m^0 \cdot {N^0} + C_m^1 \cdot {N^1} + \cdots + C_m^{m - 1} \cdot {N^{m - 1}}+C_m^{m} \cdot {N^{m}}\\&= (1 + mN)\pmod {N^2} \end{aligned}$$

Then

$$\begin{aligned} \dfrac{\Big (c_{2} \cdot c_{1}^{-d} - 1\Big )\bmod ~N^{2}}{N}&= \dfrac{(1 + N)^{m}\cdot h^{r}\cdot (s^{r})^{-d} - 1}{N} \\&=\dfrac{(1 + mN)(s^{d})^{r}(s^{r})^{-d} - 1}{N}\\&= m \end{aligned}$$

Hence, it is easy to check that the decryption algorithm correctly recovers the plaintext m.

4 Security analysis

We now ready to study the security of our basic scheme. From Boneh and Franklin 2001, we do consider two security models that will be applied to our scheme. That is ID-OWE security and IND-ID-CPA security, respectively. In the following proving process, the idea is similarly to Boneh and Franklin 2001. Firstly, define a general PKE scheme associated with our scheme. Moreover, we prove that the attack on IBE scheme can be turned into the general PKE scheme. The idea behind the proof is that the adversary conducts private key extraction queries about ID do not increase more success advantage on the attack. Finally, our IBE scheme is proven security under reasonable assumption indirectly.

Theorem 2

Our proposed IBE scheme is IND-OWE security under the modified computatial Diffie–Hellman (MDH) assumption.

Motivated by Boneh and Franklin 2001; Huang et al. 2017, we formalize this via a proof by reduction, to prove this theorem we need to construct a general PKE scheme \(\mathcal {S}\) as follows.

Definition 1

(General PKE) The general PKE is constructed by \(\mathcal {S}= (\mathcal {K}, \mathcal {E}, \mathcal {D})\).

  • KeyGen \(\mathcal {K}\) Input security parameter \(1^{\kappa }\), algorithm \(\mathcal {K}\) generates the safe-prime modulus \(N=pq\), i.e. p and q are large primes of the form \(p= 2p^{\prime }+1\) and \(q= 2q^{\prime }+1\). Pick a random \(s, d \in \mathbb {Z}_{N^{2}}\) and set \(h= s^{d} \pmod {N^{2}}\). The public key is (N, s, h) and the private key is (p, q, d), respectively.

  • Encrypt \(\mathcal {E}\) Given the message \(m \in \mathbb {Z}_{N}\), pick a random \(r \in \mathbb {Z}_{N^{2}}\), send the ciphertext \(\mathcal {C} = ({c_1}, {c_2})\) where

    $$\begin{aligned} c_{1}&=s^{r} \pmod {N^{2}} \\ c_{2}&=(1+N)^{m}\cdot h^{r}\pmod {N^{2}} \end{aligned}$$

  • Decrypt \(\mathcal {D}\) The user can decrypt ciphertext \(\mathcal {C} = ({c_1}, {c_2})\) using the private key d as follows,

    $$\begin{aligned} m = \dfrac{\Big (c_{2} \cdot c_{1}^{-d} - 1\Big )(\bmod {~N^{2}})}{N} \end{aligned}$$

Lemma 2

Suppose \(\mathcal {B}\) be an ID-OWE adversary that has non-negligible advantage \(\epsilon\) aganist the proposed IBE scheme. Let the secure cryptographic hash function \(\mathcal {H}:~{\left\{ {0, 1} \right\} ^*} \rightarrow \mathbb {Z}_{N^{2}}^{*}\) be an random oracle, and \(\mathcal {B}\) makes at most \(q_{E}\) private key extraction queries. Then there exists a PPT adversary \(\mathcal {A}\) succeeds in breaking the scheme \(\mathcal {S}\) with at least \(\Big (1 - \dfrac{{{q_E}^2}}{{N(p - 1)(q - 1)}}\Big )\cdot \dfrac{\epsilon }{{{q_E}}}\) probability.

Proof

Firstly, the challenger runs the system parameters about general PKE scheme \(\mathcal {S}\), where the public key is (N, s, h) and the private key is (p, q, d), respectively. Pick a random message m, to generate the ciphertext \(\mathcal {C} = ({c_1}, {c_2})\).

Given adversary \(\mathcal {A}\) the public key (N, s, h) and the challenge ciphertext \(\mathcal {C} = ({c_1}, {c_2})\), \(\mathcal {A}\) attempts to recover the message m under ciphertext \(\mathcal {C}\). Moreover, the adversary \(\mathcal {A}\) employs the given parameters to simulate for \(\mathcal {B}\) an instance of the IBE scheme and then adversary \(\mathcal {A}\) interacts with \(\mathcal {B}\) as follows:

  • \(\mathcal {H}\) queries: The adversary \(\mathcal {A}\) acts as the simulator, random oracle, to respond to the ID queries of adversary \(\mathcal {B}\). Suppose \(\mathcal {B}\) does not make the same queries. In addition, it has conducted \(\mathcal {H}(ID)\) queries before the private key extraction queries for ID. To answer the queries, the adversary \(\mathcal {A}\) (simulator) creates a list of the queried \(ID_{i}\) and the output result \(\mathcal {H}(ID_{i})\). If the next queries have already appears on the list, then \(\mathcal {A}\) replies with the recorded hash value \(\mathcal {H}(ID_{i})\), if not, outputs a random value. \(\mathcal {A}\) maintains the above list, and the list is initially empty.

  • Responds: When given the \(\mathcal {H}\) queries, the adversary \(\mathcal {A}\) randomly chooses \(a_{i} \in Z_{N^{2}}^{*}\), return \(a_{i}=\mathcal {H}(ID)\) to the adversary \(\mathcal {B}\). And obtain \(s_{i}= a_{i}^{2}~(\bmod ~N^{2})\). To respond the private key extraction queries queries, the adversary \(\mathcal {A}\) randomly chooses \(d_{i} \in Z_{N^{2}}^{*}\), computes \(h_{i}= s_{i}^{d_{i}}~(\bmod ~N^{2})\).

From the constructions of our IBE scheme and the general PKE scheme \(\mathcal {S}\), we observe that \(h_{i}\) is the valid ciphertext as the challenge to the adversary \(\mathcal {B}\). With \(q_{E}\) queries and \(\left| Z_{N^{2}}^{*} \right| = N(p-1)(q-1)\), then the success probability of every query is \(1-\dfrac{{{q_E}}}{{N(p - 1)(q - 1)}}\). That is, \(\mathcal {B}\) makes \(q_{E}\) queries,

$$\begin{aligned} \Big (1-\dfrac{{{q_E}}}{{N(p - 1)(q - 1)}}\Big )^{q_{E}} \ge \Big (1 - \dfrac{{{q_E}^2}}{{N(p - 1)(q - 1)}}\Big ) \end{aligned}$$

Hence, the probability of the adversary \(\mathcal {A}\) succeeds in breaking the scheme \(\mathcal {S}\) with at least

$$\begin{aligned} \Big (1 - \dfrac{{{q_E}^2}}{{N(p - 1)(q - 1)}}\Big )\cdot \dfrac{\epsilon }{{{q_E}}} \end{aligned}$$

\(\square\)

The above lemma shows that the ID-OWE security about the proposed basic IBE scheme rely on the OWE security of PKE scheme \(\mathcal {S}\). Next, we show that scheme \(\mathcal {S}\) is OWE security if the Assumption 3 holds.

Lemma 3

The general PKE scheme \(\mathcal {S}\) is OWE security under the modified computatial Diffie–Hellman (MDH) assumption.

Proof

If the OWE adversary \(\mathcal {B}\) succeeds in breaking the scheme \(\mathcal {S}\) within probabilistic polynomial time, then the MDH problem can be easily solved by adversary \(\mathcal {A}\).

Given the instance of MDH problem (N, g, X, Y, z), where \(N=pq\), \(X= {g^x}\bmod {N^2}\), \(Y= {g^y}\bmod {N^2}\) and \(z= g^{xy}\bmod {N}\). the goal of \(\mathcal {A}\) is to compute \(Z= g^{xy}\bmod {N^{2}}\). The adversary \(\mathcal {A}\) works as follows:

  • \(\mathcal {A}\) picks a random message m, exploit the given parameters to construct the valid ciphertext \(\mathcal {C} = ({c_1}, {c_2})\).

  • Simulate for \(\mathcal {B}\) the public key of scheme \(\mathcal {S}\), i.e. the triple (N, s, Y) be.

  • Let \(c_{1}=X\), \(c_{2}= z\cdot (1 + N)^{m}\pmod {N^{2}}\).

  • Call the adversary \(\mathcal {B}\) for attacking the scheme \(\mathcal {S}\) , input ciphertext \(\mathcal {C}\), obtain the output M.

  • \(\mathcal {A}\) computes \(Z= z\cdot \Big (1 + (m-M)N\Big ) \pmod {N^{2}}\).

From the construction of scheme \(\mathcal {S}\) (Definition 1), we have

$$\begin{aligned} c_{2}&= Z\big (1+N\big )^{M} \\&= Z+(Z\bmod ~N)MN \\&= (Z+zMN) \pmod {N^{2}} \end{aligned}$$
(3)

Moreover, by \(\mathcal {C} = ({c_1}, {c_2})\), obviously,

$$\begin{aligned} &z\cdot (1+N)^{m}\pmod {N^{2}} \\&\quad = z\big (1+mN\big ) \\&\quad = (Z+zMN) \pmod {N^{2}} \end{aligned}$$
(4)

From the above two Eqs. (3, 4), the solution for MDH problem is

$$\begin{aligned} Z= z\cdot \Big (1+(m-M)N\Big ) \pmod {N^{2}} \end{aligned}$$

This would contradict Assumption 3, and this cannot happen. Thus the general PKE scheme \(\mathcal {S}\) is OWE security. \(\square\)

To conclude, by Eqs. 2 and 3, our proposed basic IBE scheme is IND-OWE security under the modified computatial Diffie–Hellman (MDH) assumption, hence Theorem 2 is proved by reduction.

Next, we show that our proposed basic IBE scheme is IND-ID-CPA security.

Theorem 3

The proposed basic IBE scheme is IND-ID-CPA security if the DDH assumption holds.

Proof

The following is analogous to Theorem 2 and is proved in the same way, i.e. the adversary conducts private key extraction queries about ID do not increase more success advantage on the attack. Then we show that scheme \(\mathcal {S}\) is IND-CPA security if the Assumption 2 holds.

Concretely, suppose that there is an IND-CPA adversary \(\mathcal {B}\) has non-negligible advantage \(\epsilon\) against the proposed IBE scheme, we can construct a probabilistic polynomial time algorithm \(\mathcal {A}\), with help of the adversary \(\mathcal {B}\), which can solve the decisional Diffie–Hellman problem (DDH) over \(Z_{N^{2}}^{*}\).

Given the instance of DDH problem quadruple (g, X, Y, Z), where \(X= {g^x}\bmod {N^2}\), \(Y= {g^y}\bmod {N^2}\) and \(Z= g^{z}\bmod {N^2}\). the goal of \(\mathcal {A}\) is to decide whether \(z= xy \bmod (ord(\mathbb {G}))\) or not. The adversary \(\mathcal {A}\) works as follows:

  • \(\mathcal {A}\) sets the public key (N, s, h), where \(h= X = {s^x}\pmod {N^2}\).

  • \(\mathcal {A}\) tosses a coin \(i \in \{0, 1\}\) randomly and encrypt \(m_{i}\) to return to \(\mathcal {B}\).

  • \(\mathcal {A}\) exploits the given parameters to construct the ciphertext \(\mathcal {C} = ({c_1}, {c_2})\).

$$\begin{aligned} c_{1}&=s^{y} \pmod {N^{2}} \\ c_{2}&=(1+N)^{m_{i}}\cdot s^{z}\pmod {N^{2}} \end{aligned}$$

Obviously, if \(z= xy \bmod (ord(\mathbb {G}))\), the above ciphertext \(\mathcal {C} = ({c_1}, {c_2})\) is valid for \(m_{i}\), thus the adversary \(\mathcal {A}\) can obtain the successful attack from adversary \(\mathcal {B}.\)

Otherwise, if \(z \ne xy \bmod (ord(\mathbb {G})),\) there exists \(\gamma \in \left[ 1, ord(\mathbb {G})\right]\) that the formula \(z=xy+\gamma\) holds. From \(ord(\mathbb {G})= \dfrac{{N \cdot \lambda }}{2},\) we infer

$$\begin{aligned} \gamma = \gamma _{1}+\dfrac{\lambda \cdot \gamma _{2}}{2} \end{aligned}$$

where \(\gamma _{1}, \gamma _{2} \in \mathbb {Z}_{N}.\) According to corollary 3

$$\begin{aligned} s^{\frac{\lambda }{2}}&=(1 +\varepsilon N)\pmod {N^{2}} \\ (1 + N)^{m}&= (1 + mN)\pmod {N^2} \end{aligned}$$

Hence, we have

$$\begin{aligned} c_{2}&= (1+N)^{m_{i}}\cdot s^{xy+\gamma } \\&= \big (1+Nm_{i}\big )\cdot s^{xy} \cdot s^{\gamma _{1}} \cdot s^{\frac{\lambda \cdot \gamma _{2}}{2}}\\&= \big (1+Nm_{i}\big )\cdot s^{xy+\gamma _{1}}\cdot \big (1+\varepsilon N\big )^{\gamma _{2}}\\&= \Big (1+(m_{i}+\varepsilon \gamma _{2})N\Big ) \pmod {N^{2}} \end{aligned}$$

For the above formula we observe that \(m_{i}\) is hidden behind \(\varepsilon \gamma _{2}\), hence the adversary is impossible to distinguish between encryptions of messages \(m_{0}\) and \(m_{1}\). If not, the adversary can solve the decisional Diffie–Hellman problem (DDH) over \(Z_{N^{2}}^{*}\). To conclude, the proposed IBE scheme is IND-ID-CPA security if the DDH assumption holds. \(\square\)

4.1 Properties

In this section, we study the properties of the basic IBE scheme. Concretely, these are called additively homomorphic and anonymity, respectively.

Proposition 1

(Additively Homomorphic) Observe that, the proposed basic IBE scheme is additively homomorphic, i.e.

$$\begin{aligned} Dec \Big (Enc(m_{1})\cdot Enc(m_{2})\Big ) = m_{1}+m_{2} \end{aligned}$$

Proof

Choose \(r_{1}, r_{2} \in \mathbb {Z}_{N^{2}}\) at random, on input plaintext \(m_{1}\), \(m_{2}\), and output the ciphertext \(\mathcal {C}_{1}\), \(\mathcal {C}_{2}\). For \(\mathcal {C}_{1}\cdot \mathcal {C}_{2}\)

$$\begin{aligned} c_{1}&= s^{r_{1}+r_{2}} \pmod {N^{2}} \\ c_{2}&= (1+N)^{m_{1}+m_{2}}\cdot h^{r_{1}+r_{2}}\pmod {N^{2}} \end{aligned}$$

therefore

$$\begin{aligned} \dfrac{\Big (c_{2} \cdot c_{1}^{-d} - 1\Big )\bmod ~N^{2}}{N}&= \dfrac{(1 + N)^{m_{1}+m_{2}}\cdot h^{r_{1}+r_{2}}\cdot (s^{r_{1}+r_{2}})^{-d} - 1}{N} \\&=\dfrac{\big (1 + (m_{1}+m_{2})N\big )(s^{d})^{r_{1}+r_{2}}(s^{r_{1}+r_{2}})^{-d} - 1}{N}\\&=\dfrac{{1 + \big (m_{1}+m_{2}\big )N - 1}}{N}\\&=m_{1}+m_{2} \end{aligned}$$

\(\square\)

Remark 1

Because of the homomorphic properties, the proposed IBE scheme, however, is malleable and therefore does not protect against adaptive chosen-ciphertext attacks (IND-CCA). Usually in cryptography the notion of malleability is not seen as an advantage, but under certain applications such as secure electronic voting and threshold cryptosystems, this property may indeed be necessary. In the next section, we will present a enhanced IBE scheme with chosen ciphertext security.

Proposition 2

(Anonymity) The proposed basic IBE scheme is anonymous, that is, the adversary cannot determine the identity under which an encryption is computed.

The concept of anonymity (key-privacy) was first introduced by Bellare et al. (2001), subsequently, Boneh et al. (2001) extended the notion for Identity Based Encryption.

Notice that the above ciphertext \(\mathcal {C}\) has two parts, namely

$$\begin{aligned} c_{1}&=s^{r} \pmod {N^{2}} \\ c_{2}&=(1+N)^{m}\cdot h^{r}\pmod {N^{2}} \end{aligned}$$

Obviously, from the Partial Discrete Logarithm problem (Assumption 1) is intractable, any adversary cannot distinguish the receiver (i.e. ID) of a message, and more precisely, if an adversary who has two keys \(pk_{1},\)\(pk_{2}\) can not distinguish with which of these keys the message was encrypted. This property guarantee that the malicious adversaries are unable to acquire the intended recipient’s ID from the intercepted ciphertext, thus they cannot issue extract queries, i.e. unable to possess the decryption secret key \(sk_{ID}= d\).

5 Enhanced cryptosystems

The notion of security against an adaptive chosen-ciphertext attack (IND-CCA) was introduced by Rackoff and Simon (1992) as the property that a cryptosystem must have to resist active adversaries. It has been shown Boneh and Franklin 2001; Boneh and Katz 2005 that the stronger security notion for IBE is indistinguishability against adaptive chosen ID and adaptive chosen ciphertext attacks (IND-ID-CCA).

In Fujisaki and Okamoto 1999 Fujisaki–Okamoto (FO) put forward a method to transform a cryptosystem with IND-CPA security into one with IND-CCA security. They used a security hash function which was modeled as a random oracle in the security analysis. Moreover, Boneh and Franklin (2001) had shown such conversion instantiation. Here, we employ the general FO conversion technique to upgrade the basic IBE scheme to a scheme with IND-ID-CCA security.

  1. 1.

    Setup: As in the basic IBE scheme state. The only difference is we select a secure cryptographic hash function \(\mathcal {H}_{1} : \mathbb {Z}_{N^{2}}\rightarrow \left\{ 0, 1\right\} ^{\ell }\times \left\{ 0, 1\right\} ^{\kappa }\) additionally, where \(\ell\) is the length of the message to be encrypted.

  2. 2.

    Extract: This phase is the same as the basic scheme.

  3. 3.

    Encrypt: To encrypt the message \(m \in \left\{ 0, 1\right\} ^{\ell }\) to a user with identity ID do the following:

    • Compute hash function \(a= \mathcal {H}(ID)\), let \(s= a^{2} \pmod {N^{2}}\).

    • Pick a random \(\sigma \in \left\{ 0, 1\right\} ^{\kappa }\), compute \(r=\mathcal {H}(m~\Vert ~\sigma )\).

    • Send the ciphertext \(\mathcal {C} = ({c_1}, {c_2})\) where

      $$\begin{aligned} c_{1}&= s^{r} \pmod {N^{2}} \\ c_{2}&= \mathcal {H}_{1}(h^{r}\bmod ~N^{2})\oplus (m~\Vert ~\sigma ) \end{aligned}$$
  4. 4.

    Decrypt: To decrypt ciphertext \(\mathcal {C} = ({c_1}, {c_2})\) using the decrypt key d under ID.

    • Compute \((m~\Vert ~\sigma )=c_{2}\oplus \mathcal {H}_{1}(c_{1}^{d}\bmod ~N^{2})\).

    • Verify whether \(c_{1}= s^{\mathcal {H}_{1}(m~\Vert ~\sigma )} \pmod {N^{2}}\) and output m if so. Otherwise, reject the ciphertext.

We say that the IND-ID-CCA security proof which is based on Fujisaki and Okamoto 1999 and our basic IBE scheme. Without going into details, we make the following theorem:

Theorem 4

The proposed enhanced IBE scheme is IND-ID-CCA if the DDH assumption holds.

6 Comparison

To the best of our knowledge, recent research on the construction of IBE scheme without pairings proceeds in the following main directions: quadratic residuosity problem Cocks 2001; Boneh et al. 2007, higher power residuosity problem Boneh et al. 2013, discrete logarithm problem Paterson and Srinivasan 2009; Meshram 2015. In this section we compare our basic IBE scheme with them.

Firstly, the procedure for key generation is efficient due to the random input, the encryption process requires 2 modular exponetiation and only require 1 in the decryption process. Moreover, the size of ciphertext is acceptable. Finally, our proposed basic IBE scheme have the properties of additively homomorphic and anonymity. The following table shows the comparison result (Table 1).

Table 1 Comparison of IBE schemes without Pairings
Full size table

7 Conclusion

In this paper, we present a new efficient Identity-Based Encryption scheme without pairings, based on composite residuosity related problem, which may impel us to construct IBE scheme from a new direction.

Unfortunately, our scheme is provably secure under the random oracle. There is some doubt concerning the meaning of a proof of security in the random oracle model. As Canetti et al. (2004) shown, there exist cryptosystems that are provably secure in the random oracle, but insecure when the random oracle is instantiated with any hash function. Future work in attempting to modify our scheme which proven security in the stand model may also be an interesting problem. Finally, if we consider the IBE construction of Döttling and Garg (2017), maybe the chameleon function can also be instantiated by our assumption. It is beyond the scope of this paper, yet interested readers are referred to Döttling and Garg 2017 for a detailed description. However, in the current work we have not addressed the problem, and leave it for future.