An Efficient Variant of Boneh-Gentry-Hamburg’s Identity-Based Encryption Without Pairing

Abstract

Boneh, Gentry and Hamburg presented an encryption system known as BasicIBE without incorporating pairings. This system has short ciphertext size but this comes at the cost of less time-efficient encryption/decryption algorithms in which their processing time increases drastically with the message length. Moreover, the private key size is $l$ elements in $\mathbb {Z}_{N}$, where $N$ is a Blum integer and $l$ is the message length. In this paper, we optimize this system in two steps. First, we decrease the private key length from $l$ elements in $\mathbb {Z}_{N}$ to only one element. Second, we present two efficient variants of the BasicIBE in terms of ciphertext length and encryption/decryption speed. The ciphertext is as short as the BasicIBE, but with more time-efficient algorithms which do not depend on the message length. The proposed system is very time efficient compared to other IBE systems and it is as secure as the BasicIBE system.

1 Introduction

In 1985, Shamir [12] presented the notion of identity-based encryption (IBE) in which the user’s identity represents his public key and consequently, no public key certificate is required. Shamir successfully managed to design an identity-based signature based on the RSA algorithm but he was unable to design an IBE because sharing an RSA modulus between different users makes RSA insecure [12]. The design of a provable secure IBE remained an open problem for sixteen years until Boneh and Franklin [4] proposed a provably secure IBE in the random oracle model based on bilinear maps. Subsequently, there has been a rapid development in IBE based on bilinear maps, such as [2, 3, 10, 13].

However, all the previously mentioned IBEs are based on pairing operations. According to MIRACL benchmarks, a 512-bit Tate pairing takes 20 ms while a 1024-bit prime modular exponentiation takes 8.80 ms. The pairing computations are expensive compared to normal operations. The costly pairing computation limits it from being used in wide applications, specially when time and power consumptions are a major concern such as in limited wireless sensor networks. Hence, the seek for a scheme that does not rely on pairings is desirable.

Another approach to design IBEs is based on the quadratic residuosity (QR) assumption. The first IBE based on this approach is due to Cocks [6]. This system is IND-ID-CPA secure in the random oracle model. It is time-efficient compared to pairing-based IBEs, but it produces a long ciphertext of two elements in $\mathbb {Z}_{N}$ for every bit in the message.

The design of efficient IBEs without pairings was an open problem until Boneh, Gentry and Hamburg [5] presented two space-efficient systems (BasicIBE and AnonIBE) in which the ciphertext is reduced from $2l$ elements to only one element in $\mathbb {Z}_{N}$. As in Cocks’ IBE, the security of BasicIBE is based on the QR assumption in the random oracle model. Although the concrete instantiation of BasicIBE is highly space-efficient, this comes at the cost of less time-efficient encryption/decryption algorithms. To encrypt an $l$-bit message, BasicIBE solves $l+1$ equations in the form $Rx^{2}+Sy^{2}\equiv 1\pmod N$ for known values of $R,S$ and $N$ [5]. Solving such an equation requires a ‘solubility certificate’ and obtaining these certificates requires the generation of primes [6–8]. The obtained certificates can be used to solve $Rx^{2}+Sy^{2}\equiv 1\pmod N$ efficiently using the Cremona-Rusin algorithm [8]. The prime generation is a time-consuming process and it is the bottleneck in the BGH systems. Moreover, the decryption key is $l$ elements in $\mathbb {Z}_{N}$ because the identity $ID$ is hashed to a different value to encrypt each bit. AnonIBE is based on BasicIBE and it is Anon-IND-ID-CPA secure in the standard model under the interactive quadratic residuosity (IQR) assumption [5]. Moreover, the ciphertext length is reduced to one element in $\mathbb {Z}_{N}$ plus $l+1$ bits.

Jhanwar and Barua [11] made some significant observations on the BGH systems (for solving equations in the form $Rx^{2}+Sy^{2}\equiv 1\pmod N$) and proposed a trade-off system that reduces the private key length but increases the ciphertext length. They found that by knowing the value of $S\pmod N$, one can find a random solution to the equation $Rx^{2}+Sy^{2}\equiv 1\pmod N$ using only one inversion in $\mathbb {Z}_{N}$. The sender solves only $2\sqrt{l}$ equations in the form $Rx^{2}+Sy^{2}\equiv 1\pmod N$ using only $2\sqrt{l}$ inversions in $\mathbb {Z}_{N}$ and thus, no prime generation is required. This increases the encryption/decryption speed dramatically. The private key is only one element in $\mathbb {Z}_{N}$. However, this system produces a large ciphertext of $2\sqrt{l}$ elements in $\mathbb {Z}_{N}$.

Our Contribution. In this paper, we first present some definitions and review Basic IBE. After that, we optimise BasicIBE in two steps. First, we prove that hashing the identity $ID$ to a different value to encrypt each bit is as secure as hashing the identity once to encrypt the whole message and therefore, the private key length is reduced to one element in $\mathbb {Z}_{N}$. Then, we present a variant of BasicIBE (V-BasicIBE) which is both time- and space- efficient. Moreover, we prove that V-BasicIBE is as secure as BasicIBE. Although the proposed variant has the same ciphertext length as BasicIBE, it only solves two equations in the form $Rx^{2}+Sy^{2}\equiv 1\pmod N$ regardless of the message length. We also present another version of V-BasicIBE with a time-space trade-off. For V-BasicIBE, with only the cost of one more element in $\mathbb {Z}_{N}$, the sender can find a solution to $Rx^{2}+Sy^{2}\equiv 1\pmod N$ using only one inversion in $\mathbb {Z}_{N}$ and the receiver does not have to solve any of these equations. The proposed variant is time- and power-efficient compared to other IBE systems. It does not use expensive-computational operations such as pairing like Boneh-Boyen or Boneh-Franklin IBEs [2, 4] or even a prime modular exponentiation such as RSA. Table 1 compares all systems in this paper, where V2-BasicIBE is the proposed systems with the trade-off applied. In this table, the symbol $m$ represents prime modular exponentiation while $e$ and $p$ represents pairing operation and prime generation respectively. $l$ represents the message length. The symbols $G$ and $G_{T}$ represents an element in two groups $G$ and $G_{T}$ such that $e:G\times G\rightarrow G_{T}$.

Table 1. Comparison between various IBEs and the proposed IBEs

2 Definitions

2.1 IND-ID-CPA

The IND-ID-CPA security model of an IBE is described as a game between an adversary $\mathcal {A}$ and a challenger $\mathcal {C}$ [4, 12]. This game is as follows:

• Setup($\lambda$): $\mathcal {C}$ generates the public parameters $(PP)$ and sends them to $\mathcal {A}$ and keeps the master secret ($MSK$) to himself.

• Query Phase: In this phase, $\mathcal {A}$ sends private key queries to $\mathcal {C}$ for identities $ID_{s}$ of his choice. These queries are adaptive based on previous queries.

• Challenge: Satisfied with private key queries, $\mathcal {A}$ sends to $\mathcal {C}$ two messages $m_{1}$ and $m_{2}$ for an identity $ID^{*}$. $\mathcal {C}$ tosses a coin $b\in [0, 1]$ randomly and encrypts $m_{b}$ using $ID^{*}$. Note that $ID^{*}$ must not be queried in the query phase.

• Guess: $\mathcal {A}$ outputs $\overline{b}\in [0, 1]$. $\mathcal {A}$ wins the game if $b=\overline{b}$.

The advantage of $\mathcal {A}$ to attack a system $\xi$ and win this game is:

$$IBEAdv_{\mathcal {A},\xi }(\lambda )=|pr[\overline{b}=b]-\tfrac{1}{2}|.$$

If $\mathcal {A}$ submits two pairs of $(ID_{0},m_{0})$ and $(ID_{1},m_{1})$ in the challenge phase, then this game is called the ANON-IND-ID-CPA security model. The advantage of the adversary winning this game is the same as above.

2.2 QR Assumption and Jacobi Symbols

For a positive integer $N$, define the following set:

$$J(N)=[a\in \mathbb {Z}_{N}:\left( \frac{a}{N}\right) =1],$$

where $\left( \frac{a}{N}\right)$ is the Jacobi symbol of $a$ w.r.t $N$ [5]. The Quadratic Residue set $QR(N)$ is defined as follows

$$QR(N)=[a\in \mathbb {Z}_{N}:gcd(a,N)=1\wedge x^{2}\equiv a\pmod N \text { has a solution].}$$

Definition 1

Quadratic Residuosity Assumption: Let RSAgen($\lambda$) be a probabilistic polynomial time (PPT) algorithm. This algorithm generates two equal size primes $p,q$. The QR assumption holds for RSAgen if it cannot distinguish between the following two distributions for all PPT algorithms $\mathcal {A}$ [5].

$$P_{QR}(\lambda ):{(N,V)(p,q)\leftarrow RSAgen(\lambda ), N=pq, V\in _{R}QR(N)},$$

$$P_{NQR}(\lambda ):{(N,V)(p,q)\leftarrow RSAgen(\lambda ), N=pq, V\in _{R}J(N)\setminus QR(N)}.$$

In other words, the advantage of $\mathcal {A}$ against QR assumption $QRAdv_{\mathcal {A},RSAgen(\lambda )}=$

$$|\Pr [(N,V)\leftarrow P_{QR}(\lambda ): \mathcal {A}(N,V)=1]|-|\Pr [(N,V)\leftarrow P_{NQR}(\lambda ): \mathcal {A}(N,V)=1]|$$

is negligible. i.e. $\mathcal {A}$ cannot distinguish between elements in $J(N)\setminus QR(N)$ and elements in $QR(N)$.

3 Review of the BasicIBE System [5]

BasicIBE encrypts an $l$-bit message $m$ using a square $S \equiv s^{2}\pmod N$ where $s\in _{R} \mathbb {Z_{N}}$, the user’s identity $ID$ and a pair of Jacobi symbols for each bit. It first hashes $ID$ to different values $H(ID,i)=u^{a}R_{i}=r_{i}^{2}$ where $a\in \{0,1\}$, $u\in J(N)\setminus QR(N)$ and $i$ is the bit index. Then it solves the equations $R_{i}x^{2}_{i}+Sy^{2}_{i}\equiv 1\pmod N$ and $uR_{i}\overline{x}^{2}_{i}+S\overline{y}^{2}_{i}\equiv 1\pmod N$ to get $(x_{i},y_{i},\overline{x}_{i},\overline{y}_{i})$. The ciphertext is $(S,c,\overline{c})$ where $c\leftarrow [c_{1},c_{2},c_{3},..., c_{l}]$, $c_{i}=m\cdot \left( \frac{2+2y_{i}s}{N}\right)$ and $\overline{c}\leftarrow [\overline{c}_{1},\overline{c}_{2},\overline{c}_{3},..., \overline{c}_{l}]$, $\overline{c}_{i}=m\cdot \left( \frac{2+2\overline{y}_{i}s}{N}\right)$. To decrypt, one needs to know the square-root of $R_{i}$ or $uR_{i}$. If $R_{i}=r_{i}^{2}$, the message is $m_{i}=c_{i}\cdot \left( \frac{1+x_{i}r_{i}}{N}\right)$ and if $uR_{i}=r_{i}^{2}$, the message is $m_{i}=\overline{c}_{i}\cdot \left( \frac{1+\overline{x}_{i}r_{i}}{N}\right)$.

4 Optimization of BasicIBE

4.1 Optimization of the Private Key Length

As shown above, the BasicIBE system hashes the identity $ID$ to different values $H(ID,i)=u^{a}R_{i}=r_{i}^{2}, a\in \{0,1\}$. This has a negative impact on the system. First, the private key length is larger than the message by a factor of $\mathbb {Z}_{N}$ which consumes bandwidth and memory. Second, the Private Key Generator (PKG) must generate $n$ private keys of $l$ elements in $\mathbb {Z}_{N}$ where $n$ is the number of users in the whole system. This overloads the PKG. Third, this not suitable for encrypting variable messages length.

In this section, we prove that hashing the identity $ID$ to different values $R_{i}=H(ID,i)$ does not have a positive impact on the security of BasicIBE. Solving the equations $Rx^{2}_{i}+Sy^{2}_{i}\equiv 1\pmod N$ is exactly equivalent to solving the equations $R_{i}x^{2}_{i}+Sy^{2}_{i}\equiv 1\pmod N$. Consequently, there is no need for generating a long private key of $l$ elements in $\mathbb {Z_{N}}$.

Theorem 1

Hashing the identity $ID$ to a different value to encrypt each bit is as secure as hashing the identity once to encrypt the whole message.

Proof

Jhanwar and Barua [1] showed that there is $N-1$ solutions for the equation $Rx^{2}+Sy^{2}\equiv 1\pmod N$ if $S,R\in QR(N)$. The solution $(x,y)$ for that equation is in the form:

$$\begin{aligned} \left( \frac{-2st}{R+St^{2}},\frac{R-St^{2}}{s(R+St^{2})}\right) \nonumber \end{aligned}$$

for some $t\in \mathbb {Z}^{*}_{N}$ such that $R+St^{2}\in \mathbb {Z}^{*}_{N}$.

$$\begin{aligned}&Rx_{i}^{2}+Sy_{i}^{2}=R\left( \frac{-2st}{R+St^{2}}\right) ^{2}+Sy_{i}^{2}\ =\left( \frac{4SR}{({R+St^{2}})^{2}}\right) t^{2}+Sy_{i}^{2} =R_{i}\overline{x}_{i}^{2}+Sy_{i}^{2}\\&where \;\;R_{i}=t^{2}\;\; and \;\; \overline{x}_{i}=\frac{-2sr}{R+St^{2}}. \end{aligned}$$

Since $t$ is random in $\mathbb {Z}^{*}_{N}$, $R_{i}$ looks mathematically random exactly as $R_{i}=H(ID,i)$. $\quad \square$

4.2 V-BasicIBE

In this section, we explain how to implement a variant of BasicIBE (V-BasicIBE) that is both time and space efficient. Like any other IBE, V-BasicIBE consists of four algorithms; Setup, KeyGen, Encrypt and Decrypt.

• Setup($\lambda$): Using RSAgen($\lambda$), generate ($p$,$q$), calculate the modulus $N \leftarrow pq$, choose $u\in J(N)\setminus QR(N)$, and choose a hash function $H:ID\rightarrow J(N)$. The public parameters $PP$ are [$N,u,H$]. The master secret MSK parameters are $p,q$ and a secret key $K$ for a pseudorandom function $F_{K}:ID\rightarrow [0,1,2,3]$.

• KeyGen($MSK,ID,l$): Calculate $R\leftarrow H(ID)\in J(N)$ and $w\leftarrow F_{K}(ID)\in \{0,1,2,3\}$. Choose $a\in \{0,1\}$ such that $u^{a}R\in QR(N)$. Let $[z_{0},z_{1},z_{2},z_{3}]$ be the four square roots of $u^{a}R\in \mathbb {Z}_{N}$, then $r\leftarrow z_{w}$.

• Encrypt($id,m$): To encrypt a message $m\in \{-1,1\}^{l}$, V-BasicIBE calculates $[x_{i},y_{i},\overline{x}_{i},\overline{y}_{i}]$, $i\in [0,l-1]$ such that these variables satisfy the following equations:

  $$\begin{aligned}{}[x_{i},y_{i}]\leftarrow Rx_{i}^{2}+S^{j}y_{i}^{2}\equiv 1\pmod N \; , \; [\overline{x}_{i},\overline{y}_{i}]\leftarrow uR\overline{x}_{i}^{2}+S^{j}\overline{y}_{i}^{2}\equiv 1\pmod N \end{aligned}$$

  for an odd number $j=2i+1$. To solve these equations, we review a product formula presented by Boneh, Gentry and Hamburg [5].

  Lemma 1. For $i=1,2$ let $(x_{i},y_{i})$ be a solution to $R_{i}x^{2}+Sy^{2}\equiv 1\pmod N$ . Then $(x_{3},y_{3})$ is a solution to

  $$\begin{aligned} R_{1}R_{2}x^{2}\,+\,Sy^{2}\,\equiv 1\pmod N, \end{aligned}$$

  where $x_{3}=\frac{x_{1}x_{2}}{Sy_{1}y_{2}+1}$ and $y_{3}=\frac{y_{1}+y_{2}}{Sy_{1}y_{2}+1}$.

  Proof. By directly substituting the values of $x_{3}$ and $y_{3}$ in the equation $R_{1}R_{2}x^{2}\,+\,Sy^{2}\,\equiv 1\pmod N$.

  Jhanwar and Barua [11] presented a variant of Lemma 1 to implement their system. This lemma states that:

  Lemma 2. For $i=1,2$ let $(x_{i},y_{i})$ be a solution to $Rx^{2}+S_{i}y^{2}\equiv 1\pmod N$ . Then $(x_{3},y_{3})$ is a solution to

  $$\begin{aligned} Rx^{2}\,+\,S_{1}S_{2}y^{2}\,\equiv 1\pmod N, \end{aligned}$$

  where $x_{3}=\frac{x_{1}+x_{2}}{Rx_{1}x_{2}+1}$ and $y_{3}=\frac{y_{1}y_{2}}{Rx_{1}x_{2}+1}$

  Proof. Same as Lemma 1.

  To solve these equations, BasicIBE calculates $[x_{0},y_{0}]$ and then uses Lemma 2 to find $[{x}_{i},{y}_{i}]$ as follows.

  $$\begin{aligned} \hat{x}=\frac{2x_{0}}{Rx_{0}^{2}+1} \; , \; \hat{y}=\frac{y^{2}_{0}}{Rx_{0}^{2}+1}, \;\; x_{i}=\frac{\hat{x}+x_{i-1}}{R\hat{x}x_{i-1}+1} \; , \; y_{i}=\frac{\hat{y}y_{i-1}}{R\hat{x}x_{i-1}+1}, \end{aligned}$$

  where $[\hat{x},\hat{y}]$ is a solution to $R\hat{x}^{2}+S^{2}\hat{y}^{2}\equiv 1\pmod N$. Similarly, $[\overline{x}_{i},\overline{y}_{i}]$ are generated as shown above.

  The message $m \leftarrow [m_{0}, m_{1}, ..., m_{l-1}]$ is encrypted using the following formula:

  $$\begin{aligned} c_{i}\leftarrow m_{i} \cdot \left( \frac{2y_{i}s^{j}+2}{N}\right) \; , \; \overline{c}_{i}\leftarrow m_{i} \cdot \left( \frac{2\overline{y}_{i}s^{j}+2}{N}\right) . \end{aligned}$$

  The ciphertext is $C\leftarrow (S,c,\overline{c})$.

• Decrypt($C,r$): The message can be retrieved from the ciphertext as follows.

  $$\begin{aligned} &m_{i}\leftarrow c_{i} \cdot \left( \frac{x_{i}r+1}{N}\right) \;\; \;\; \text{ if } \;\; r^{2}=R \;\; \text{ and } \;\;m_{i} \leftarrow \overline{c}_{i} \cdot \left( \frac{\overline{x}_{i}r+1}{N}\right) \;\; \;\; \text{ if } \;\; r^{2}=uR. \end{aligned}$$

  Correctness: As in [5], it is easy to prove that:

  $$\begin{aligned}&(x_{i}r+1)\cdot (2y_{i}s^{j}+2)=2x_{i}ry_{i}s^{j}+2x_{i}r+2y_{i}s^{j}+2+(Rx_{i}^{2}+S^{j}y_{i}^{2}-1)\\&\qquad \qquad \qquad \qquad =(x_{i}r+y_{i}s^{j}+1)^{2},\\&\left( \frac{x_{i}r+1}{N}\right) \cdot \left( \frac{2y_{i}s^{j}+2}{N}\right) =1, \;\; \left( \frac{x_{i}r+1}{N}\right) =\left( \frac{2y_{i}s^{j}+2}{N}\right) . \end{aligned}$$

4.3 V-BasicIBE Security

Theorem 2

Suppose the quadratic residuosity assumption holds for RSAgen and $F$ is a secure PRF. Then the proposed V-BasicIBE is IND-ID-CPA secure based on the QR assumption when H is modelled as a random oracle. In particular, suppose $\mathcal {A}$ is an efficient IND-ID-CPA adversary, then there exist efficient algorithms $B_{1}, B_{2}$ whose running time is the same as that of $\mathcal {A}$ such that:

$$\begin{aligned} IBEAdv_{\mathcal {A},V-BasicIBE}(\lambda )\le 2QRAdv_{B_{2},RSAgen}(\lambda )+PRFAdv_{B_{1},F}(\lambda ). \end{aligned}$$

We first introduce Lemma 3 [5].

Lemma 3

Let $N=pq$ be an RSA modulus, $S_{i},R\in J(N)$. Then

• 1-When $R\in J(N)\setminus QR(N)$, $S_{i}\in QR(N)$, the Jacobi symbols $\left( \frac{g(s_{i})}{N}\right)$ for any function $g$ are uniformly distributed in $\{\pm 1\}$, where $s_{i}$ is a random variable uniformly chosen among the four square roots of $S_{i}$ modulo $N$ and $g(s_{i})g(-s_{i})R\in QR(N)$ for all the four values of $s_{i}$.

• 2-When $S_{i}\in J(N)\setminus QR(N)$, $R\in QR(N)$, the Jacobi symbols $\left( \frac{f(r)}{N}\right)$ for any function $f$ are uniformly distributed in $\{\pm 1\}$, where $r$ is a random variable uniformly chosen among the four square roots of $R$ modulo $N$ and $f(r)f(-r)S_{i} \in QR(N)$ for all the four values of $r$.

• 3-When $S_{i}, R\in QR(N)$, the Jacobi symbols $\left( \frac{g(s_{i})}{N}\right)$ and $\left( \frac{f(r)}{N}\right)$ are constant, i.e. the same for all four values of $r$ and $s_{i}$.

Proof

Let $s_{i},\overline{s}_{i}$ be the four square roots of $S_{i}\in QR(N)$ such that $\overline{s}_{i}=s_{i}\pmod p$ and $\overline{s}_{i}=-s_{i}\pmod q$, then the four square roots of $S_{i}$ are $\{\pm \overline{s}_{i},\pm s_{i}\}$. We can assume the same for $R\in QR(N)$ and the four square roots are $\{\pm \overline{r},\pm r\}$, where $\overline{r}=r\pmod p$ and $\overline{r}=-r\pmod q$.

Case 1

$$\begin{aligned} &\left( \frac{g(s)g(-s)R}{N}\right) =\left( \frac{g(s)g(-s)R}{p}\right) =\left( \frac{g(s)g(-s)R}{q}\right) =1.\\ & \left( \frac{R}{p}\right) =\left( \frac{R}{q}\right) =-1,\nonumber \\ & \left( \frac{g(s)g(-s)}{p}\right) =\left( \frac{g(s)g(-s)}{q}\right) =-1,\nonumber \\ & \left( \frac{g(s)}{p}\right) =-\left( \frac{g(-s)}{p}\right) \;\; and\;\; \left( \frac{g(s)}{q}\right) =-\left( \frac{g(-s)}{q}\right) ,\\ & \left( \frac{g(s)}{N}\right) =\left( \frac{g(-s)}{N}\right) .\\ & \left( \frac{g(\overline{s})}{p}\right) =\left( \frac{g(s)}{p}\right) .\\ & \left( \frac{g(\overline{s})}{q}\right) =\left( \frac{g(-s)}{q}\right) =-\left( \frac{g(s)}{q}\right) ,\\ & \left( \frac{g(\overline{s})}{p}\right) \left( \frac{g(\overline{s})}{q}\right) =-\left( \frac{g(s)}{p}\right) \left( \frac{g(s)}{q}\right) \nonumber ,\\ & \left( \frac{g(\overline{s})}{N}\right) =-\left( \frac{g(s)}{N}\right) ,\\ & \left( \frac{g(\overline{s})}{N}\right) =\left( \frac{g(-\overline{s})}{N}\right) =-\left( \frac{g(s)}{N}\right) =-\left( \frac{g(-s)}{N}\right) . \end{aligned}$$

That means that among the four Jacobi symbols $\left( \frac{g(\overline{a})}{N}\right) ,\left( \frac{g(-\overline{a})}{N}\right) , \left( \frac{g(a)}{N}\right) ,$ $\left( \frac{g(-a)}{N}\right)$ two are $+1$ and two are $-1$. Case 2 and Case 3 can be proven similarly to Case 1.

 

• Security Proof. We define a sequence of games and let $W_{i}$ represents the winning of the $i_{th}$ game by the adversary $\mathcal {A}$. These games are defined as follows.

  • Game-0. This game is the usual adversarial game.

  • Game-1. This game replaces the PRF $F$ with a truly random function.

  • Game-2. This game explains how to simulate the hash function $H$.

  • Game-3. This game sets $u\in QR(N)$.

  • Game-4. This game explains how to respond to an encryption query from $\mathcal {A}$.

  • Game-5. This game sets $R\in J(N)\setminus QR(N)$.

  • Game-6. This game sets $S_{i}=s^{2}_{i}$ for each bit.

  • Game-7 replaces the message $m$ with a random number $z$.

• Game-0. This is the usual adversarial game for defining the IND-ID-CPA security of IBE protocols. The challenger picks the random oracle $H: ID\rightarrow J(N)$ at random from the set of all such functions in the $Setup$ algorithm and allows $\mathcal {A}$ to query $H$ at arbitrary points. Thus, we have

  $$\begin{aligned} |\Pr [W_{0}]-\frac{1}{2}|=IBEAdv_{\mathcal {A}, V-BasicIBE}(\lambda ). \end{aligned}$$

• Game-1. This is the same as Game-0, with the following change. In $Setup$ algorithm, instead of using a PRF $F$ to respond to $\mathcal {A}$’s private key queries, we use a truly random function $f :ID\rightarrow \{0, 1, 2, 3\}$. If $F$ is a secure PRF, $\mathcal {A}$ will not notice the difference between Game-0 and Game-1. In particular, there exists an algorithm $B_{1}$ (whose running time is about the same as that of $\mathcal {A}$) such that

  $$\begin{aligned} |\Pr [W_{1}]-\Pr [W_{0}]|=PRFAdv_{B_{1},F}(\lambda ). \end{aligned}$$

• Game-2. $(N,u,H)$ are the public parameters $PP$ given to $\mathcal {A}$ in the previous game where $u$ is uniform in $J(N)\setminus QR(N)$ and the random oracle $H$ is a random function $H: ID\rightarrow J(N)$. We make the following change in the random oracle $H$ in this game. The challenger responds to a query to $H(ID)$ by picking $a\in _{R}\{0,1\}$ and $v\in _{R}\mathbb {Z}_{N}$ and setting $H(ID)=u^{a}v^{2}$. Thus the challenger implements a random function $H: ID\rightarrow J(N)$ as in the previous game. The challenger responds to a private key query as follows.

  Suppose $R=H(ID)=u^{a}v^{2}$ for some $a\in _{R}\{0,1\}$ and $v\in _{R}\mathbb {Z}_{N}$. The challenger responds to a private key query for $ID$ by setting either $R^{\frac{1}{2}} = v$ (when $a = 0$) or $(uR)^{\frac{1}{2}} = uv$ (when $a = 1$). Since $v$ is uniform in $\mathbb {Z}_{N}$ this will produce a square root of $R$ or $uR$ which is also uniform among the four square roots, as in the previous game. Thus, $\mathcal {A}$’s views in Game-1 and Game-2 are identical and therefore,

  $$\begin{aligned} |\Pr [W_{1}]=\Pr [W_{2}]|. \end{aligned}$$

• Game-3. In this game, the challenger chooses $u$ uniformly in $QR(N)$ instead of $J(N)\setminus QR(N)$. Since this is the only change between Game-2 and Game-3, $\mathcal {A}$ will not notice the difference assuming that the QR assumption holds for RSAgen. In particular, there exists an algorithm $B_{2}$ (whose running time is about the same as that of $\mathcal {A}$) such that:

  $$\begin{aligned} |\Pr [W_{3}]-\Pr [W_{2}]| = QRAdv_{B_{2},RSAgen}(\lambda ). \end{aligned}$$

• Game-4. We describe below in detail how, in this game, the challenger responds to an encryption query from $\mathcal {A}$.

  • He chooses $R\in QR(N)$ and sets $H(ID)=R$. (*)

  • He chooses $s\in _{R}\mathbb {Z}_{N}$ and computes $S^{j}=s^{2j}$ for an odd value $j$.

  • He sets $c\leftarrow Encrypt(PP,ID,m_{b})$.

  • He sends $(S,c)$ to $\mathcal {A}$.

• Game-5. In this game, we make a change in the challenge phase. We replace the line (*) in Game-4 with the following:

  • He chooses $R\in J(N)\setminus QR(N)$ and sets $H(ID)=R$.

  Since the only difference between Game-5 and Game-4 is that $R\in J(N)\setminus QR(N)$ in Game-5 instead of $R\in QR(N)$ in Game-4, $\mathcal {A}$ will not notice the difference assuming that the QR assumption holds for RSAgen. In particular, there exists an algorithm $B_{2}$ (whose running time is about the same as that of $\mathcal {A}$) such that:

  $$\begin{aligned} |\Pr [W_{5}]-\Pr [W_{4}]| = QRAdv_{B_{2},RSAgen}(\lambda ). \end{aligned}$$

• Game-6: In this game, we encrypt the message by choosing $s_{i}\in \mathbb {Z}_{N}$ independently and randomly for each bit. In other words, we replace the Jacobi symbols $\left( \frac{2y_{i}s^{j}+2}{N}\right)$ and $\left( \frac{2\overline{y}_{i}s^{j}+2}{N}\right)$ with the Jacobi symbols $\left( \frac{2y_{i}s_{i}+2}{N}\right)$ and $\left( \frac{2\overline{y}_{i}s_{i}+2}{N}\right)$ respectively i.e. $c_{i}=m_{i}\cdot \left( \frac{2y_{i}s_{i}+2}{N}\right)$ and $\overline{c}_{i}=m_{i}\cdot \left( \frac{2\overline{y}_{i}s_{i}+2}{N}\right)$. To prove that Game-6 is indistinguishable from Game-5, we present the following Theorem.

  Theorem 3. The distribution of the Jacobi symbols $\left( \frac{2y_{i}s^{j}+2}{N}\right)$ is indistinguishable from the distribution the Jacobi symbols $\left( \frac{2y_{i}s_{i}+2}{N}\right)$.

  The proof of this theorem is based on the work of Damgard [9]. He proved that the Jacobi sequences are indistinguishable from random. i.e. if an adversary knows the value of $\left( \frac{a}{N}\right)$, it is a hard problem to find $\left( \frac{a+1}{N}\right)$ for an unknown value $a$. Although the values of $a$ and $a+1$ are highly correlated and dependent, that does not mean that their Jacobi symbols are correlated. We now present a formal proof for the above theorem.

  Proof. Damgard proved that the following is a hard problem [9].

  Lemma 4. Let J be the Jacobi sequence modulo N with a starting point a and length P(k), for a security parameter k and polynomial P. Given J, find $\left( \frac{a+P(k)+1}{N}\right)$.

  This means that, knowing $\left( \frac{a}{N}\right) ,\left( \frac{a+1}{N}\right) ,\left( \frac{a+2}{N}\right) ,...,\left( \frac{a+a_{1}}{N}\right) ,...,\left( \frac{a+a_{2}}{N}\right) ,...,\left( \frac{a+P}{N}\right)$, it is a hard problem to find $\left( \frac{a+P+1}{N}\right)$.

  We first choose $a$ and $P$ such that $a+P+1=2y_{i}s^{j}+2$, then we can write the above sequence in two different forms:

  $$\begin{aligned} \left( \frac{a}{N}\right) ,\left( \frac{a+1}{N}\right) ,\left( \frac{a+2}{N}\right) ,...,\left( \frac{2y_{i_{1}}s^{j_{1}}+2}{N}\right) ,...,\left( \frac{2y_{i_{2}}s^{j_{2}}+2}{N}\right) ,...,\left( \frac{a+P}{N}\right) \end{aligned}$$

  where $a_{1}=2y_{i_{1}}s^{j_{1}}+2-a$, $a_{2}=2y_{i_{2}}s^{j_{2}}+2-a$, and $j_{1}<j_{2}<j.$

  $$\begin{aligned} \left( \frac{a}{N}\right) ,\left( \frac{a+1}{N}\right) ,\left( \frac{a+2}{N}\right) ,...,\left( \frac{2y_{i_{1}}s_{j_{1}}+2}{N}\right) ,...,\left( \frac{2y_{i_{2}}s_{j_{2}}+2}{N}\right) ,...,\left( \frac{a+P}{N}\right) \end{aligned}$$

  where $a_{1}=2y_{i_{1}}s_{j_{1}}+2-a$, $a_{2}=2y_{i_{2}}s_{j_{2}}+2-a.$

  Since $\mathbb {Z}_{N}$ is an additive group, the values of $a_{1}, a_{2}$ and $P$ exist in both sequences for any value $y$ or $s$ which means that both sequences represent the Damgard hard problem. Moreover, guessing the Jacobi symbol $\left( \frac{2y_{i}s^{j}+2}{N}\right)$ from the sequence $\left( \frac{2y_{i}s+2}{N}\right)$, $\left( \frac{2y_{i}s^{2}+2}{N}\right)$,...,$\left( \frac{2y_{i}s^{j-1}+2}{N}\right)$ is as hard as guessing the same Jacobi symbol from the sequence $\left( \frac{2y_{i}s_{1}+2}{N}\right)$,$\left( \frac{2y_{i}s_{2}+2}{N}\right)$,...,$\left( \frac{2y_{i}s_{j}+2}{N}\right)$. The same holds for $\left( \frac{2\overline{y}_{i}s^{j}+2}{N}\right)$ and $\left( \frac{2\overline{y}_{i}s_{i}+2}{N}\right)$. $\square$

  Based on Theorem 3, $\mathcal {A}$ will not be able to distinguish between Game-5 and Game-6. i.e.

  $$\begin{aligned} |\Pr [W_{6}]=\Pr [W_{5}]|. \end{aligned}$$

• Game-7: In this game, we replace the message $m^{(b)}$ by a random string $z\in _{R}\{-1,1\}^{l}$ i.e., $c_{i}=z_{i}\cdot \left( \frac{2y_{i}s_{i}+2}{N}\right)$ and $\overline{c}_{i}=z_{i}\cdot \left( \frac{2\overline{y}_{i}s_{i}+2}{N}\right)$. We first prove that $(2y_{i}s_{i}+2)(-2y_{i}s_{i}+2)R\in QR(N)$.

  Proof. Let $g(s_{i})=(2y_{i}s_{i}+2)$, then we have

  $$\begin{aligned} &g(s_{i})g(-s_{i})R=4(y_{i}s_{i}+1)(-y_{i}s_{i}+1)R\nonumber ,\\ &g(s_{i})g(-s_{i})R=4(1-(y_{i}s_{i})^{2})R\nonumber ,\\ &g(s_{i})g(-s_{i})R=4(Rx^{2}_{i})R=(2Rx_{i})^{2} \in QR(N)\nonumber . \end{aligned}$$

  Similarly, we can prove that $(2\overline{y}_{i}s_{i}+2)(-2\overline{y}_{i}s_{i}+2)uR\in QR(N)$.

  Since $s_{i}\in QR(N)$, $R\in J(N)\setminus QR(N)$, $(2y_{i}s_{i}+2)(-2y_{i}s_{i}+2)R\in QR(N)$ and $(2\overline{y}_{i}s_{i}+2)(-2\overline{y}_{i}s_{i}+2)uR\in QR(N)$ then Case 1 in Lemma 3 can be applied and the distribution of the Jacobi symbols $\left( \frac{2y_{i}s_{i}+2}{N}\right)$ and $\left( \frac{2\overline{y}_{i}s_{i}+2}{N}\right)$ are random in $\{\pm 1\}$. Thus, $\mathcal {A}$ will not be able to distinguish between Game-6 and Game-7. i.e.

  $$\begin{aligned} |\Pr [W_{7}]=\Pr [W_{6}]|. \end{aligned}$$

• Clearly in Game-7 we have

  $$\begin{aligned} |\Pr [W_{7}]=\frac{1}{2}|. \end{aligned}$$

  Combining all the previous equations proves theorem.

5 Space-Time Tradeoff

In this section, we present a trade-off between the time and the ciphertext length of the proposed systems. For V-BasicIBE, instead of sending $S$ along with $c$ and $\overline{c}$ as the full ciphertext $C$, the sender sends $C=(x_{0},\overline{x}_{0},c,\overline{c})$. Thus, he can solve $Rx^{2}+Sy^{2}\equiv 1\pmod N$ using only one inversion in $\mathbb {Z}_{N}$. This results in high encryption speed. In the decryption, the receiver does not have to solve any equations and he can generate $x_{i}$ or $\overline{x}_{i}$ (based on if $r^{2}=R$ or $uR$) using Lemma 2. This, of course, comes at the cost of sending one more element in $\mathbb {Z}_{N}$.

6 Conclusion

This paper proposed a variant of BasicIBE. The proposed variant is more efficient (in terms of computation time) than previous IBE systems. We also proved that the proposed variant has the same security level as the BasicIBE system. Moreover, the proposed systems have only one element in the $\mathbb {Z}_{N}$ private key instead of $l$ elements in $\mathbb {Z}_{N}$ as in BasicIBE. We also produced a time-space trade-off variant that is both time- and space-efficient.