Generalized Galbraith’s Test: Characterization and Applications to Anonymous IBE Schemes

Abstract

The main approaches currently used to construct identity-based encryption (IBE) schemes are based on bilinear mappings, quadratic residues and lattices. Among them, the most attractive approach is the one based on quadratic residues, due to the fact that the underlying security assumption is a well-understood hard problem. The first such IBE scheme was constructed by Cocks, and some of its deficiencies were addressed in subsequent works. In this paper, we focus on two constructions that address the anonymity problem inherent in Cocks’ scheme, and we tackle some of their incomplete theoretical claims. More precisely, we rigorously study Clear et al.’s and Zhao et al.’s schemes and give accurate probabilities of successful decryption and identity detection in the non-anonymized version of the schemes. Furthermore, in the case of Zhao et al.’s scheme, we give a proper description of the underlying security assumptions.

1. Introduction

From a desire to avoiding several issues (e.g., management of trust, public-key recovery) inherent to public-key cryptography, Shamir came up in 1984 with an interesting and novel concept: identity-based encryption [1]. In the IBE model, a user’s public key is simply derived from some of the user’s personal data such as their e-mail address, their phone number or even their personal address.

Unfortunately, the construction of a practical IBE scheme was postponed until 2001 when two such schemes were proposed. The first one was proposed by Boneh and Franklin [2] and is based on bilinear maps. Briefly, using a different approach, Cocks proposed a scheme based on quadratic residues [3]. Despite the simplicity of their idea, a disadvantage of the scheme is that it has a large ciphertext-to-plaintext ratio. More precisely, to encrypt one bit, we have to transmit two large integers.

As pointed out in [2], Cocks’ proposal does not provide anonymity in the sense of Bellare et al. [4]. Concretely, Galbraith devised a test that can distinguish which identity was used to create a given Cocks-like ciphertext. The test has been thoroughly analyzed in [5,6]. Despite this impediment, several schemes that achieve anonymity have been proposed in the literature [5,7,8,9,10,11].

In terms of ciphertext expansion, the most efficient anonymous proposal is the one described by Boneh, Gentry, and Hamburg [9]. However, encryption time is quartic in the security parameters and thus makes the scheme very inefficient. Two years later, Ateniese and Gasti [5] proposed a practical scheme that achieves anonymity. The scheme is universally anonymous; (i.e., the anonymization process is independent of encryption and requires only access to the user’s id). The scheme is further improved by Schipor [11]. By using a trial and error method, he manages to shrink the size of Ateniese and Gasti-type ciphertexts.

A xor-homomorphic variant, which is also universally anonymous, was proposed by Clear et al. [7,12]. By switching to polynomials, they where able to show that the scheme has an underlying algebraic structure. This structure was later studied and simplified by Joye [8]. As a consequence, he managed to improve both the speed and ciphertext expansion of Clear et al.’s IBE scheme. Using an earlier study [6], Nica and Ţiplea [13] reassessed Joye’s proposal and provide a simpler description of the scheme. By taking a different approach, Zhao et al. [10] managed to further speed up encryption. Unfortunately, their scheme have twice the ciphertext expansion compared to Joye’s scheme.

In this paper, we reevaluate some of the claims made by Clear et al. [7,12] and Zhao et al. [10] regarding their proposals. More precisely, we rigorously formulate and prove some of the claims made by these authors, thus providing the reader with a better understanding of the intrinsic algebraic structures in both schemes.

Structure of the Paper

We introduce notations and definitions used throughout the paper in Section 2. The extension of Galbraith’s test to polynomial rings is rigorously studied in Section 3. In Section 4 and Section 5, we apply our results to obtain precise characterizations of Clear et al.’s and Zhao et al.’s IBE schemes. We conclude with Section 6.

2. Preliminaries

2.1. Notations

Throughout the paper, $\lambda$ denotes a security parameter. Furthermore, the notation $\left|S\right|$ denotes the cardinality of a set S. The action of selecting a random element x from a sample space X is denoted by $x\stackrel{\$}{\leftarrow }X$, while $x\leftarrow y$ represents the assignment of value y to variable x. The probability of the event E happening is denoted by $Pr\left[E\right]$. The quotient of the integer division of a by n, assuming $n\ne 0$, is denoted $a\mathrm{div}n$.

The Jacobi symbol of an integer a modulo an integer n is represented by $J_n\left(a\right)$. We let $Q{R}_n$ and $QN{R}_n$ be the set of quadratic and, respectively, non-quadratic residues modulo n. Furthermore, $J_n$ denotes the sets of integers modulo n with Jacobi symbol 1.

2.2. Identity-Based Encryption

An IBE scheme consists of four probabilistic polynomial-time (PPT) algorithms: Setup, KeyGen, Enc and Dec. The first one takes as input a security parameter and outputs the system’s public parameters together with a master key. The KeyGen algorithm takes as input an identity $id$ together with the public parameters and the master key, and outputs a private key associated with the $id$. The Enc algorithm, starting with a message m, an identity $id$, and the public parameters, encrypts m into some ciphertext c (the encryption key is $id$ or some binary string derived from $id$). The last algorithm decrypts c into m by using the private key associated to $id$.

Definition 1

(Anonymity and Indistinguishability under Selective Identity and Chosen Plaintext Attacks—anon-ind-id-cpa). The anon-ind-id-cpa security of an IBE scheme $\mathcal{S}$ is formulated by means of the following game between a challenger C and an adversary A:

• Setup$\left(\lambda \right)$: The challenger C generates the public parameters $pp$ and sends them to adversary A while keeping the master key $msk$ to himself.
• Queries: The adversary issues a finite number of adaptive queries. A query can be one of the following types:
  • Private key query. When A requests a query for an identity, the challenger runs the KeyGen algorithm and returns the resulting private key to A.
  • Encryption query. Adversary A can issue only one query of this type. He sends C two pairs $(i{d}_0,m_0)$ and $(i{d}_1,m_1)$ consisting of two equal-length plaintexts $m_0$ and $m_1$ and two identities $i{d}_0$ and $i{d}_1$. The challenger flips a coin $b\in \{0,1\}$ and encrypts $m_b$ using $i{d}_b$. The resulting ciphertext c is sent to the adversary. The following restrictions are in place: private key queries for $i{d}_0$ and $i{d}_1$ must never be issued.
• Guess: In this phase, the adversary outputs a guess $b^{\prime }\in \{0,1\}$. He wins the game if $b^{\prime }=b$.

The advantage of an adversary A attacking an IBE scheme is defined as

$$\begin{array}{c}\hfill {\mathrm{IBEAdv}}_{A,\mathcal{S}}\left(\lambda \right)=|Pr[b=b^{\prime }]-1/2|\end{array}$$

where the probability is computed over the random bits used by C and A. An IBE scheme is anon-ind-id-cpa secure if, for any PPT adversary A, the advantage ${\mathrm{IBEAdv}}_{A,\mathcal{S}}\left(\lambda \right)$ is negligible. If we consider $i{d}_0=i{d}_1$ in the above game, we obtain the concept of ind-id-cpa security.

We further state the security assumption used to prove the security of the IBE schemes mentioned in this paper.

Definition 2

(Quadratic Residuosity—qr). Choose two large prime numbers $p,q\ge 2^{\lambda }$ and compute $n=pq$. Let A be a PPT algorithm that returns 1 on input $(x,n)$ if $x\in Q{R}_n$. We define

$$\begin{array}{cc}\hfill {ADV}_A^{\mathrm{QR}}\left(\lambda \right)& =\left|Pr[A(x,n)=1|x\stackrel{\$}{\leftarrow }Q{R}_n]-Pr[A(x,n)=1|x\stackrel{\$}{\leftarrow }{J}_n\setminus Q{R}_n]\right|.\hfill \end{array}$$

The Quadratic Residuosity assumption states that for any PPT algorithm A, the advantage ${ADV}_A^{\mathrm{QR}}\left(\lambda \right)$ is negligible.

3. Generalized Galbraith’s Test

According to [5,14], Galbraith developed a test that shows that Cocks’ scheme [3] is not anonymous. A straightforward generalization of Galbraith’s test to the ring ${\mathbb{Z}}_n\left[x\right]/(x^2-R)$ was introduced in [7,12]. More precisely, we define the generalized Galbraith test as

$$\begin{array}{c}\hfill G{T}_n(R,f_{0}x+f_1)=J_n(f_1^2-f_0^{2}R),\end{array}$$

where $R\in J_n$ and $f_{0}x+f_1\in Z_n\left[x\right]/(x^2-R)$.

The authors of [7,12] briefly describe some aspects of the generalized version of the test, but some of their claims were not rigorously formulated and/or proved. More precisely, they assume that $f_0,f_1\in {\mathbb{Z}}_n^{\ast }$ and this is not always the case (since we are working with polynomials from $Z_n\left[x\right]/(x^2-R)$ and not $Z_n^{\ast }\left[x\right]/(x^2-R)$). Note that when $f_0,f_1\in {\mathbb{Z}}_n^{\ast }$, the generalized Galbraith test is identical to the original Galbraith test.

In this limited scenario, Clear et al. prove that their scheme is anonymous by reducing their security proof to some result from [5,6]. Although is not explicitly mentioned in [7,12], using the results from [5,6] we can also compute the probability of success of Galbraith’s test when we choose to use Clear et al.’s IBE scheme without implementing the anonymization technique.

The generalized Galbraith test is also used in [10] to show that their scheme is not anonymous. Although the authors also assume that $f_0,f_1\in {\mathbb{Z}}_n^{\ast }$, they do not compute the test’s success probability for their IBE scheme, and in this case the probability cannot be derived from [5,6].

Motivated by these applications, we further study the generalized Galbraith test without any restrictions. More precisely, our goals are to better understand the behavior of the test and to develop the exact success probabilities for the test against Clear et al.’s and Zhao et al.’s non-anonymized IBE schemes.

Let p and q be two primes and $n=pq$ be their product. In this section, we study the cardinalities of the following sets:

$$\begin{array}{cc}\hfill P_p^{\ell }\left(R\right)& =\{f_{0}x+f_1\in {\mathbb{Z}}_p\left[x\right]/(x^2-R)\mid J_p(f_1^2-f_0^{2}R)=\ell \}\hfill \\ \hfill P_n^0\left(R\right)& =\{f_{0}x+f_1\in {\mathbb{Z}}_n\left[x\right]/(x^2-R)\mid J_n(f_1^2-f_0^{2}R)=0\}\hfill \\ \hfill P_n^{{\ell }_1,{\ell }_2}\left(R\right)& =\{f_{0}x+f_1\in {\mathbb{Z}}_n\left[x\right]/(x^2-R)\mid J_p(f_1^2-f_0^{2}R)={\ell }_1,J_q(f_1^2-f_0^{2}R)={\ell }_2\},\hfill \end{array}$$

where $\ell \in \{-1,0,1\}$ and ${\ell }_1,{\ell }_2\in \{-1,1\}$.

Before stating our results, we first present a lemma from [6] that further helps us compute our desired cardinalities.

Lemma 1

([6]). Let $p>2$ be a prime, $k=p\mathrm{div}4$, and $R\in {\mathbb{Z}}_p^{\ast }$. Then,

$$\begin{array}{c}\hfill |Q{R}_p(a+Q{R}_p)|=\left\{\begin{array}{cc}k-1,\hfill & ifp=4k+1andR\in Q{R}_p\hfill \\ k,\hfill & ifp=4k+1andR\in QN{R}_p,orp=4k+3.\hfill \end{array}\right.\end{array}$$

Now let us compute the cardinality of $P_p^{\ell }$.

Lemma 2.

The following statements are true

1. 

If $R\in QN{R}_p$ then $|P_p^0\left(R\right)|=1$, else $|P_p^0\left(R\right)|=2p-1$.

2. 

If $R\in QN{R}_p$ then $|P_p^1\left(R\right)|=(p^2-1)/2$, else $|P_p^1{\left(R\right)|=(p-1)}^2/2$.

3. 

If $R\in QN{R}_p$ then $|P_p^{-1}\left(R\right)|=(p^2-1)/2$, else $|P_p^{-1}{\left(R\right)|=(p-1)}^2/2$.

Proof. 

To prove the first statement, we simply have to count the elements that satisfy $f_1^2\equiv f_0^{2}Rmodp$. If $R\in QN{R}_p$, our single option is $f_0=f_1=0$. Otherwise, for each non-zero value of $f_0^2$ we have two distinct $f_1$ values. Hence, we obtain $2(p-1)$ possibilities.

Now, we will prove the second statement. When $f_0,f_1\not\equiv 0modp$, we can rewrite $f_1^2-f_0^{2}R$ as $c^2-R$, where $c\equiv f_0^{-1}{f}_{1}modp$. Using 1, we obtain that the number of possibilities is

$$\begin{array}{c}\hfill \left\{\begin{array}{cc}k-1,\hfill & \mathrm{if}p=4k+1\mathrm{and}R\in Q{R}_p\hfill \\ k,\hfill & \mathrm{if}p=4k+1\mathrm{and}R\in QN{R}_p,\mathrm{or}p=4k+3.\hfill \end{array}\right.\end{array}$$

When $f_0\equiv 0modp$, we obtain that $J_p\left(f_1^2\right)=1$ and this is true only if $f_1\not\equiv 0modp$. Hence, we obtain $p-1$ possibilities.

In the case $f_1\equiv 0modp$, we obtain that $J_p(-f_0^{2}R)=1$, and thus $f_0\not\equiv 0modp$. When $-R\in Q{R}_p$, we obtain $p-1$ possibilities, and when $-R\in QN{R}_p$, we have none.

Adding all the possibilities we obtain

$$\begin{array}{c}\hfill \left\{\begin{array}{cc}(p-1)[(p-5)/2+2]={(p-1)}^2/2\hfill & \mathrm{if}p=4k+1\mathrm{and}R\in Q{R}_p\hfill \\ (p-1)[(p-1)/2+1]=(p^2-1)/2\hfill & \mathrm{if}p=4k+1\mathrm{and}R\in QN{R}_p\hfill \\ (p-1)[(p-3)/2+1]={(p-1)}^2/2\hfill & \mathrm{if}p=4k+3\mathrm{and}R\in Q{R}_p\hfill \\ (p-1)[(p-3)/2+2]=(p^2-1)/2\hfill & \mathrm{if}p=4k+3\mathrm{and}R\in QN{R}_p\hfill \end{array}\right.\end{array}$$

The last statement is obtained by subtracting the cardinalities of $P_p^0\left(R\right)$ and $P_p^1\left(R\right)$ from $|\mathbb{Z}\left[x\right]/(x^2-R)|$. □

Using the Chinese remainder theorem, we obtain the following cardinalities.

Corollary 1.

The following statements are true

1. 

If $R\in J_n\setminus Q{R}_n$ then $|P_n^0\left(R\right)|=p^2+q^2-1$, else $|P_n^0\left(R\right)|=(2p-1)q^2+(2q-1)$${(p-1)}^2$.

2. 

If $R\in J_n\setminus Q{R}_n$ then $|P_n^{{\ell }_1,{\ell }_2}\left(R\right)|=(p^2-1)(q^2-1)/4$, else $|P_n^{{\ell }_1,{\ell }_2}{\left(R\right)|=(p-1)}^2{(q-1)}^2/4$.

Let $h\left(x\right)$ be a polynomial such that $G{T}_n(R,h\left(x\right))=-1$ and $A\subseteq {\mathbb{Z}}_n\left[x\right]/(x^2-R)$ a set of polynomials. We further define the set

$$\begin{array}{c}\hfill T_n(R,h\left(x\right),A)=\{h\left(x\right)·f\left(x\right)\mid f\left(x\right)\in A\}.\end{array}$$

Lemma 3.

The following identity holds $|T_p(R,h\left(x\right),A)|=|A|$.

Proof. 

If $R\in QN{R}_p$, then the polynomial $x^2-R$ is irreducible. Hence, ${\mathbb{Z}}_p\left[x\right]/(x^2-R)$ is a field. Therefore, $h\left(x\right)$ only permutes the set A.

When $R\in Q{R}_p$, we distinguish two cases. When $h{\left(x\right)}^{-1}$ exists, then we again have a permutation of the set. Otherwise, $h\left(x\right)$ has the form $h\left(x\right)=t(x\pm r)$, for a $t\in {\mathbb{Z}}_p^{\ast }$. However, in this case we obtain that ${\left(tr\right)}^2-t^{2}R=0$, and this contradicts our assumption (i.e., $G{T}_n(R,h\left(x\right))=-1$). Hence, $h{\left(x\right)}^{-1}$ always exists. □

Corollary 2.

The following identity holds $|T_n(R,h\left(x\right),A)|=|A|$.

We further present a lemma that states that the generalized Galbraith test is “multiplicative”. This lemma stays at the base of the anonymization technique described in [7,12].

Lemma 4

([7,12]). Let $e\left(x\right)\equiv f\left(x\right)·g\left(x\right)mod{x}^2-R$. Then $G{T}_n(R,e\left(x\right))=G{T}_n(R,f\left(x\right))·G{T}_n(R,g\left(x\right))$.

4. Clear et al. IBE Scheme

4.1. Scheme Description

Clear et al. [12] were the first to study the algebraic structure of Cocks’ ciphertexts. A more in-depth study of the underlying structure can be found in [6,8,13]. As a result of Clear et al.’s study, the authors managed to describe a partially homomorphic IBE scheme [12], and later they improve the scheme such that is also anonymous [7].

We further present a slightly improved version of Clear et al.’s IBE scheme. We start by presenting the non-anonymized version.

• Setup$\left(\lambda \right)$: Given a security parameter $\lambda$, generate two primes $p,q>2^{\lambda }$ and compute their product $n=pq$. The public parameters are $pp=\{n,u,H,H^{\prime }\}$ and the master secret key is $msk=\{p,q\}$, where $u\in {\mathbb{Z}}_n$ such that $J_p\left(u\right)=J_q\left(u\right)=-1$, $H:{\{0,1\}}^{\ast }\to J_n$ and $H^{\prime }:{\{0,1\}}^{\ast }\to {\mathbb{Z}}_n\left(x\right)/(x^2-R)$ are two cryptographic hash functions. Note that $H^{\prime }$ must also satisfy the property that for any identity $id\in {\{0,1\}}^{\ast },R\leftarrow H\left(id\right)$ and $h\left(x\right)\leftarrow H^{\prime }\left(id\right)$, it holds that

  $$\begin{array}{c}\hfill G{T}_n(R,h\left(x\right))=G{T}_n(uR,h\left(x\right))=-1.\end{array}$$
• KeyGen$(pp,msk,id)$: Let $R=H\left(id\right)$. If $R\in Q{R}_n$, then compute $r\equiv R^{1/2}modn$. Otherwise, compute $r\equiv {\left(uR\right)}^{1/2}modn$. The private key is r.
• Enc$(pp,id,m)$: On inputting $pp$, an identity $id$ and a message $m\in \{-1,1\}$, compute the hash value $R=H\left(id\right)$ and randomly choose two polynomials $f\left(x\right),\overline{f}\left(x\right)$ of degree 1 from ${\mathbb{Z}}_n\left[x\right]$ such that $J_n\left(f_1\right)=J_n\left({\overline{f}}_1\right)=m$, where $f_1=f\left(0\right)$ and ${\overline{f}}_1=\overline{f}\left(0\right)$. Furthermore, calculate

  $$\begin{array}{c}\hfill g\left(x\right)\equiv f_1^{-1}·f{\left(x\right)}^{2}mod(x^2-R)\mathrm{and}\overline{g}\left(x\right)\equiv {\left({\overline{f}}_1\right)}^{-1}·\overline{f}{\left(x\right)}^{2}mod(x^2-uR).\end{array}$$
  Return the ciphertext $C=(g\left(x\right),\overline{g}\left(x\right))$.
• Dec$(r,C)$: On input $pp$, a secret key r and a ciphertext $C=(c\left(x\right),\overline{c}\left(x\right))$, compute

  $$\begin{array}{c}\hfill m^{\prime }=\left\{\begin{array}{cc}{J}_n\left(c\left(r\right)\right)\hfill & \mathrm{if}{r}^2\equiv H\left(id\right)modn;\hfill \\ J_n\left(\overline{c}\left(r\right)\right)\hfill & \mathrm{otherwise}.\hfill \end{array}\right.\end{array}$$

Correctness: The correctness of the decryption algorithm follows by noticing that when $r^2\equiv H\left(id\right)modn$, we have

$$\begin{array}{c}\hfill m^{\prime }=J_n\left(c\left(r\right)\right)=J_n(f_1^{-1}·f{\left(r\right)}^2)=J_n\left(f_1^{-1}\right)=m.\end{array}$$

When $r^2\equiv uH\left(id\right)modn$, we can proceed similarly.

Using the generalized Galbraith test, it can be shown that the scheme is not anonymous (see Section 4.3). Hence, we need to upgrade the scheme with an anonymization algorithm. We further describe the method as presented in [7,12]. Note that the Anon algorithm anonymizes the ciphertext, while the DeAnon reverses the process.

• Anon$(pp,id,C)$: Given the public parameters $pp$, an identity $id$ and a ciphertext $C=(c\left(x\right),\overline{c}\left(x\right)$), compute $R=H\left(id\right)$ and $h\left(x\right)=H^{\prime }\left(id\right)$. Furthermore, generate two random bits $v_1,v_2\in \{0,1\}$ and calculate

  $$\begin{array}{cc}\hfill g\left(x\right)& \equiv g\left(x\right)·h{\left(x\right)}^{v_1}mod(x^2-R)\hfill \\ \hfill \overline{g}\left(x\right)& \equiv \overline{g}\left(x\right)·h{\left(x\right)}^{v_2}mod(x^2-uR).\hfill \end{array}$$
  Return the anonymized ciphertext $C^{\prime }=(g\left(x\right),\overline{g}\left(x\right))$.
• DeAnon$(pp,id,C)$: On input $pp$, a secret key r, and a ciphertext $C=(c\left(x\right),\overline{c}\left(x\right))$, compute $R=H\left(id\right)$, $h\left(x\right)=H^{\prime }\left(id\right)$ and

  $$\begin{array}{cc}\hfill g\left(x\right)& \equiv g\left(x\right)·h{\left(x\right)}^{(1-w_1)/2}mod(x^2-R)\hfill \\ \hfill \overline{g}\left(x\right)& \equiv \overline{g}\left(x\right)·h{\left(x\right)}^{(1-w_2)/2}mod(x^2-uR),\hfill \end{array}$$

  where $w_1=G{T}_n(R,c\left(x\right))$ and $w_2=G{T}_n(R,\overline{c}\left(x\right))$. Return the non-anonymized ciphertext $C^{\prime }=(g\left(x\right),\overline{g}\left(x\right))$.

4.2. Previous Analysis

Let $f\left(x\right)=ax+b$, where $a\in {\mathbb{Z}}_n$ and $b\in {\mathbb{Z}}_n^{\ast }$. Note that $J_n\left(b\right)$ is our message. Then

$$\begin{array}{c}\hfill b^{-1}·f{\left(x\right)}^2\equiv b^{-1}·(a^2{R}^2+b^2+2abx)\equiv a^2{b}^{-1}{R}^2+b+2axmod{x}^2-R.\end{array}$$

In the IBE scheme presented in [12], the authors select random polynomials $f\left(x\right)$ until $G{T}_n(R,f\left(x\right))=1$. Furthermore, when proving the security of their scheme, they also impose an additional restriction, that $a^2{b}^{-1}{R}^2+b\in {\mathbb{Z}}_n^{\ast }$. In the updated version of the scheme [7], the authors simply generate polynomials until $a^2{b}^{-1}{R}^2+b\in {\mathbb{Z}}_n^{\ast }$. Using these restrictions, we can reduce the generalized version of Galbraith’s test to the original version. However, in reality, we should not be able to distinguish the polynomials generated by the IBE scheme from random polynomials from $\mathbb{Z}\left[x\right]/(x^2-R)$. For this reason, in our version, we removed the requirement $a^2{b}^{-1}{R}^2+b\in {\mathbb{Z}}_n^{\ast }$, and as we shall see next, we can prove that we cannot distinguish these polynomials from random ones.

4.3. New Analysis

We first study the cardinality of the set

$$\begin{array}{cc}\hfill D_n\left(R\right)& =\{b^{-1}{(ax+b)}^{2}mod{x}^2-R\mid a\in {\mathbb{Z}}_n,b\in {\mathbb{Z}}_n^{\ast }\},\hfill \end{array}$$

which contains the polynomials generated by the scheme presented in Section 4.1. Note that we further consider that $R\ne 0$. Otherwise, we can trivially recover b by computing $f\left(0\right)$.

Lemma 5.

If $R\in QN{R}_p$ then $|D_p\left(R\right)|=(p^2-1)/2$, otherwise $|D_p\left(R\right)|=(p-1)(p+3)/2$.

Proof. 

Rewriting $b^{-1}{(ax+b)}^2=d^{-1}{(cx+d)}^2$ we obtain

$$\begin{array}{cc}\hfill a^{2}dR+b^{2}d& \equiv c^{2}bR+d^{2}bmodp\hfill \\ \hfill 2abd& \equiv 2cdbmodp.\hfill \end{array}$$

From the second equation, we obtain $a\equiv cmodp$. Keeping this in mind, the first equation becomes $(d-b)(a^{2}R-bd)\equiv 0modp$. If $a\equiv 0modp$, then we obtain that $d\equiv bmodp$ since $b,d\in {\mathbb{Z}}_p^{\ast }$. Else, either $d\equiv bmodp$ or $d\equiv b^{-1}{a}^{2}Rmodp$.

We further consider $a\not\equiv 0modp$. If $R\in QN{R}_p$ then $b\not\equiv b^{-1}{a}^{2}Rmodp$; otherwise from $b\equiv \pm a{R}^{1/2}modp$, we obtain $b\equiv b^{-1}{a}^{2}Rmodp$. Therefore, if $R\in QN{R}_p$, we obtain that $|D_p\left(R\right)|=(p-1)(p-1)/2+p-1=(p-1)(p+1)/2$. Otherwise, we obtain $|D_p\left(R\right)|=[(p-3)/2+2](p-1)+p-1=(p-1)(p+3)/2$. □

Corollary 3.

If $R\in J_n\setminus Q{R}_n$, then $|D_n\left(R\right)|=(p^2-1)(q^2-1)/4$, and if $R\in Q{R}_n$, then $|D_n\left(R\right)|=(p-1)(p+3)(q-1)(q+3)/4$.

Now, we consider the set of ciphertexts that can be correctly decrypted

$$\begin{array}{cc}\hfill D_n^{\ast }\left(R\right)& =\{b^{-1}{(ax+b)}^{2}mod{x}^2-R\mid a\in {\mathbb{Z}}_n;b,ar+b\in {\mathbb{Z}}_n^{\ast }\}.\hfill \end{array}$$

Lemma 6.

When $R\in Q{R}_p$ we have $|D_p^{\ast }\left(R\right)|=(p^2-1)/2$.

Proof. 

From $ar+b\equiv 0modp$ we obtain $a\equiv -b{r}^{-1}modp$ since $r,b\in {\mathbb{Z}}_n^{\ast }$. Looking at the proof of Lemma 5, we observe that in the case $a\equiv 0modp$, the sets are not affected by the added restriction since $-b{r}^{-1}\not\equiv 0modp$. When $a\not\equiv 0modp$, the only case that is affected is $b\equiv -armodp$. Therefore, we obtain our desired result. □

Corollary 4.

If $R\in Q{R}_n$, then $|D_n^{\ast }\left(R\right)|=(p^2-1)(q^2-1)/4$.

Corollary 5.

The probability of correct decryption is $1-\mathcal{O}(1/n)$.

Proof. 

From Corollaries 3 and 4 we obtain that the probability is

$$\begin{array}{c}\hfill \frac{|D_n^{\ast }\left(R\right)|}{|D_n\left(R\right)|}=\frac{(p+1)(q+1)}{(p+3)(q+3)}\simeq 1-\mathcal{O}\left(\frac{1}{n}\right).\end{array}$$

 □

Now we will study ciphertexts with a given generalized Galbraith value. Thus, we define

$$\begin{array}{cc}\hfill D_p^{\ell }\left(R\right)& =\{f_{0}x+f_1\in D_p\left(R\right)\mid J_p(f_1^2-f_0^{2}R)=\ell \}\hfill \\ \hfill D_n^0\left(R\right)& =\{f_{0}x+f_1\in D_n\left(R\right)\mid J_n(f_1^2-f_0^{2}R)=0\}\hfill \\ \hfill D_n^1\left(R\right)& =\{f_{0}x+f_1\in D_n\left(R\right)\mid J_p(f_1^2-f_0^{2}R)=J_q(f_1^2-f_0^{2}R)=1\},\hfill \end{array}$$

where $\ell \in \{0,1\}$.

Lemma 7.

The following statements are true

1. 

If $R\in QN{R}_p$ then $|D_p^0\left(R\right)|=0$, else $|D_p^0\left(R\right)|=2(p-1)$.

2. 

If $R\in QN{R}_p$ then $|D_p^1\left(R\right)|=(p^2-1)/2$, else $|D_p^1{\left(R\right)|=(p-1)}^2/2$.

Proof. 

Since $f\in D_p^0\left(R\right)$, we have ${(a^2{b}^{-1}R+b)}^2-4a^{2}R\equiv 0modp$. This is equivalent with $a^2{b}^{-1}R-b\equiv 0modp$. If $R\in QN{R}_p$, then $D_p^0\left(R\right)=\varnothing$. Otherwise, we obtain $(ar-b)(ar+b)\equiv 0modp$. Thus, we can rewrite the set as $D_p^0\left(R\right)=\{2ar(x\pm r)\mid a\in {\mathbb{Z}}_p^{\ast }\}$.

We further count the distinct elements of $D_p^0\left(R\right)$. From $2a(x\pm r)\equiv 2c(x\pm r)mod{x}^2-R$, we obtain $a\equiv \pm cmodp$. From $2a(x+r)\equiv 2c(x-r)mod{x}^2-R$ we obtain $a(x+r)+c(-x+r)\equiv 0mod{x}^2-R$. Hence, we obtain $a=c=0$, which is impossible. Thus, the cardinality of $D_p^0\left(R\right)$ is $2(p-1)$.

The last statement results from observing that all the elements from $D_p\left(R\right)$ have the Jacobi symbol $J_p(f_1^2-f_0^{2}R)$ either 1 or 0 when $R\in Q{R}_p$. Hence, using 5, we obtain our result. □

Corollary 6.

The following statements are true

1. 

If $R\in J_n\setminus Q{R}_n$, then $|D_n^0\left(R\right)|=0$, else if $R\in Q{R}_n$ $|D_n^0\left(R\right)|=(p-1)(q-1)(p+q+2)$.

2. 

If $R\in J_n\setminus Q{R}_n$, then $|D_n^1\left(R\right)|=(p^2-1)(q^2-1)/4$, else if $R\in Q{R}_n$ $|D_n^1{\left(R\right)|=(p-1)}^2{(q-1)}^2/4$.

Now we can properly analyze the efficiency of the generalized Galbraith test.

Corollary 7.

The probability that a ciphertext $f\left(x\right)$ produced by the scheme from Section 4.1 has $G{T}_n(R,f\left(x\right))=1$ is $1-\mathcal{O}(1/n)$.

Proof. 

According to Corollaries 4 and 6 we have

$$\begin{array}{c}\hfill \frac{|D_n^1\left(R\right)|}{|D_n\left(R\right)|}=\left\{\begin{array}{cc}1\hfill & \mathrm{if}R\in J_n\setminus Q{R}_n\hfill \\ \frac{(p+1)(q+1)}{(p+3)(q+3)}\simeq 1+\mathcal{O}\left(\frac{1}{n}\right)\hfill & \mathrm{if}R\in Q{R}_n.\hfill \end{array}\right.\end{array}$$

 □

Corollary 8.

The generalized Galbraith test can detect ciphertexts produced by the scheme from Section 4.1 with a probability of $1/2+\mathcal{O}(1/n)$.

Proof. 

According to Corollaries 1 and 3, we have

$$\begin{array}{c}\hfill \frac{|D_n\left(R\right)|}{|P_n^{1,1}\left(R\right)\cup P_n^{-1,-1}\left(R\right)|}=\left\{\begin{array}{cc}1/2\hfill & \mathrm{if}R\in J_n\setminus Q{R}_n\hfill \\ \frac{(p+3)(q+3)}{2(p+1)(q+1)}\simeq \frac{1}{2}+\mathcal{O}\left(\frac{1}{n}\right)\hfill & \mathrm{if}R\in Q{R}_n.\hfill \end{array}\right.\end{array}$$

 □

Lemma 8.

The following equality holds $D_p^1\left(R\right)=P_p^{1,1}\left(R\right)$.

Proof. 

We will show that $P_p^{1,1}\left(R\right)\subseteq D_p^1\left(R\right)$ and $D_p^1\left(R\right)\subseteq P_p^{1,1}\left(R\right)$. Our second inclusion is trivial because $P_p^{1,1}\left(R\right)$ contains all possible 1-degree polynomials that have Jacobi symbol equal to 1. Now, let us focus on the first inclusion. We take a random $f=f_{0}x+f_1\in P_p^{1,1}\left(R\right)$, and we search for a pair $(a,b)\in {\mathbb{Z}}_p\times {\mathbb{Z}}_p^{\ast }$ such that $f_{0}x+f_1=b^{-1}{(ax+b)}^2=2ax+a^{2}R{b}^{-1}+b$. From this, we have $f_0\equiv 2amodp$ and $f_1\equiv a^{2}R{b}^{-1}+bmodp$. As a result, we can derive $a\equiv 2^{-1}{f}_{0}modp$ and $b^2-b{f}_1+4^{-1}{f}_0^{2}R\equiv 0modp$. Therefore, we obtain $\Delta =f_1^2-4·4^{-1}{f}_0^{2}R=f_1^2-f_0^{2}R$, which has the Jacobi symbol 1 according to the definition of $P_p^{1,1}\left(R\right)$.

Now let us assume that $b\equiv 0modp$. Then, we have $f_1\pm {(f_1^2-f_0^{2}R)}^{1/2}\equiv 0modp$. This implies that $f_0^{2}R\equiv 0modp$. Since $R\not\equiv 0modp$, we obtain that $f_0\equiv 0modp$ and implicitly $a\equiv 0modp$. However, when $a\equiv 0modp$, we can choose the other root $b\equiv f_{1}modp$, which is different from 0 since we cannot have both $f_0$ and $f_1$ equal to 0.

When $f_0\not\equiv 0modp$, we can choose b as either of the two roots ($\Delta \not\equiv 0modp$). Thus, we obtain that $f\in D_p^1\left(R\right)$. This concludes our proof. □

Corollary 9.

The following equality holds $D_n^1\left(R\right)=P_n^{1,1}\left(R\right)$.

Corollary 10.

Either $T_n(R,h\left(x\right),D_n^1\left(R\right))=P_n^{1,-1}\left(R\right)$ or $T_n(R,h\left(x\right),D_n^1\left(R\right))=P_n^{-1,1}\left(R\right)$ depending if either $G{T}_p(R,h\left(x\right))=1$ or $G{T}_q(R,h\left(x\right))=1$.

Proof. 

We assume without loss of generality that $G{T}_p(R,h\left(x\right))=1$. Using Corollary 9, we obtain the following equality $T_n(R,h\left(x\right),D_n^1\left(R\right))=T_n(R,h\left(x\right),P_n^{1,1}\left(R\right))$. Since $P_n^{1,-1}\left(R\right)$ contains all the polynomials $f\left(x\right)$ with $G{T}_n(R,f\left(x\right))=-1$ and the generalized Galbraith test is “multiplicative” (see Lemma 4), we have $T_n(R,h\left(x\right),P_n^{1,1}\left(R\right))\subseteq P_n^{1,-1}\left(R\right)$.

For the second inclusion, we use the fact that $h\left(x\right)$ has an inverse (see the proof of Lemma 3). Hence, $T_n(R,h{\left(x\right)}^{-1},P_n^{1,-1}\left(R\right))\subseteq P_n^{1,1}\left(R\right)$. This relation can be rewritten as $P_n^{1,-1}\left(R\right)\subseteq T_n(R,h\left(x\right),P_n^{1,1}\left(R\right))$. This concludes our proof. □

Remark 1.

Corollary 10 is also proven in [7] but using different techniques. We chose to reprove it since it follows directly from our analysis.

We further assume without loss of generality that $G{T}_p(R,h\left(x\right))=1$.

Corollary 11.

Let $P_n^{+,-}\left(R\right)=P_n^{1,1}\left(R\right)\cup P_n^{1,-1}\left(R\right)$ and ${\tilde{D}}_n\left(R\right)=D_n^1\left(R\right)\cup T_n(R,h\left(x\right),D_n^1\left(R\right))$. Then the distributions

$$\begin{array}{cc}\hfill X_n& =\{f\left(x\right)\mid f\left(x\right)\stackrel{\$}{\leftarrow }{\tilde{D}}_n\left(R\right)\}\hfill \\ \hfill Y_n& =\{f\left(x\right)\mid f\left(x\right)\stackrel{\$}{\leftarrow }{P}_n^{+,-}\left(R\right)\}\hfill \end{array}$$

are identical.

In order to prove that their anonymization technique is secure, Clear et al. first established a series of computational indistinguishability results. The one that we are interested in states that

$$\begin{array}{c}\hfill Z_n=\{G{T}_n(R,f\left(x\right))\mid f\left(x\right)\stackrel{\$}{\leftarrow }{\tilde{D}}_n\left(R\right)\}\end{array}$$

is computationally indistinguishable from the uniform distribution U on $\{-1,1\}$, under the qr assumption. In [6], the authors prove a stronger result: the two distributions are statistically indistinguishable. Since we removed Clear et al.’s restriction, we need to prove that the statistically indistinguishability still holds. Using the results developed in this subsection, we can prove exactly that.

Theorem 1.

The following distribution

$$\begin{array}{c}\hfill Z_n=\{G{T}_n(R,f\left(x\right))\mid f\left(x\right)\stackrel{\$}{\leftarrow }{\tilde{D}}_n\left(R\right)\}\end{array}$$

is statistically indistinguishable from the uniform distribution U on $\{-1,1\}$.

Proof. 

We will show that the statistical distance $\Delta (Z_n,U)$ between $Z_n$ and U is negligible, where

$$\begin{array}{c}\hfill \Delta (Z_n,U)=\frac{1}{2}\sum _{b\in \{-1,1\}}\mid Pr[Z_n=b]-Pr[U=b]\mid .\end{array}$$

Let ${\overline{D}}_n\left(R\right)=T_n(R,h\left(x\right),D_n\left(R\right))$ and ${\overline{D}}_n^1\left(R\right)=T_n(R,h\left(x\right),D_n^1\left(R\right))$. In order to compute $Pr[Z_n=b]$, we make use of Corollaries 1 and 2. Thus, taking into account that

$$\begin{array}{c}\hfill Pr[f\left(x\right)\in D_n\left(R\right)]=Pr[f\left(x\right)\in {\overline{D}}_n\left(R\right)]=1/2,\end{array}$$

and that $f\left(x\right)\stackrel{\$}{\leftarrow }{D}_n\left(R\right)\cup {\overline{D}}_n\left(R\right)$, we obtain

$$\begin{array}{cc}\hfill Pr[Z_n=1]& =Pr[G{T}_n(R,f\left(x\right))=1]\hfill \\ \hfill & =Pr[G{T}_n(R,f\left(x\right))=1\mid f\left(x\right)\in D_n\left(R\right)]·Pr[f\left(x\right)\in D_n\left(R\right)]\hfill \\ \hfill & +Pr[G{T}_n(R,f\left(x\right))=1\mid f\left(x\right)\in {\overline{D}}_n\left(R\right)]·Pr[f\left(x\right)\in {\overline{D}}_n\left(R\right)]\hfill \\ \hfill & =\frac{1}{2}·\frac{|D_n^1\left(R\right)|}{|{\tilde{D}}_n\left(R\right)|}+\frac{1}{2}·\frac{|{\overline{D}}_n^1\left(R\right)|}{|{\tilde{D}}_n\left(R\right)|}=\frac{|D_n^1\left(R\right)|}{|{\tilde{D}}_n\left(R\right)|}\hfill \\ \hfill & =\frac{1}{2}+\mathcal{O}\left(\frac{1}{n}\right).\hfill \end{array}$$

In a similar way, one can obtain

$$\begin{array}{cc}\hfill Pr[Z_n=-1]& =\frac{1}{2}+\mathcal{O}\left(\frac{1}{n}\right).\hfill \end{array}$$

Now, the statistical distance $\Delta (Z_n,U)$ becomes

$$\begin{array}{c}\hfill \Delta (X_n,U)=\frac{1}{2}\left(\left|\frac{1}{2}+\mathcal{O}\left(\frac{1}{n}\right)-\frac{1}{2}\right|+\left|\frac{1}{2}+\mathcal{O}\left(\frac{1}{n}\right)-\frac{1}{2}\right|\right)=\mathcal{O}\left(\frac{1}{n}\right).\end{array}$$

Since n is exponentially large in the security parameter $\lambda$, the statistical distance is negligible. □

5. Zhao et al. IBE Scheme

5.1. Scheme Description

In [10], the authors introduce two IBE schemes that work with polynomials modulo n, where n is the product of two primes p, q chosen such that $p\equiv -qmod4$. Zhao et al. prove the security of their schemes under the strong qr assumption (which is basically the qr assumption with the restriction that $p\equiv -qmod4$).

Starting from their first scheme, we devised a new scheme from which we removed the necessity of choosing $p\equiv -qmod4$. In this case, the proof from [10] can be easily adapted to obtain that our scheme is secure under the qr assumption.

• Setup$\left(\lambda \right)$: Given a security parameter $\lambda$, generate two primes $p,q>2^{\lambda }$ and compute their product $n=pq$. Randomly generate two integers $u,y\in \mathbb{Z}$ such that $J_p\left(u\right)=J_q\left(u\right)=-1$ and $J_p\left(y\right)=-J_q\left(y\right)$. The public parameters are $pp=\{n,u,y,H\}$, where $H:{\{0,1\}}^{\ast }\to J_n$ is a cryptographic hash function. The master secret key is $msk=\{p,q\}$.
• KeyGen$(pp,msk,id)$: Let $R=H\left(id\right)$. If $R\in Q{R}_n$, then compute $r\equiv R^{1/2}modn$. Otherwise, compute $r={\left(uR\right)}^{1/2}modn$. The private key is r.
• Enc$(pp,id,m)$: On inputting $pp$, an identity $id$ and a message $m\in \{0,1\}$, compute the hash value $R=H\left(id\right)$ and randomly choose two polynomials $f\left(x\right),\overline{f}\left(x\right)$ of degree 1 from ${\mathbb{Z}}_n\left[x\right]$. Furthermore, calculate

  $$\begin{array}{c}\hfill g\left(x\right)=f{\left(x\right)}^{2}mod(x^2-R)\mathrm{and}\overline{g}\left(x\right)=\overline{f}{\left(x\right)}^{2}mod(x^2-uR).\end{array}$$
  Return the ciphertext $C=(y^m·g\left(x\right),y^m·\overline{g}\left(x\right))$.
• Dec$(pp,r,C)$: On input $pp$, a secret key r and a ciphertext $C=(c\left(x\right),\overline{c}\left(x\right))$, compute

  $$\begin{array}{c}\hfill m^{\prime }=\left\{\begin{array}{cc}{J}_n\left(c\left(r\right)\right)\hfill & \mathrm{if}{r}^2\equiv H\left(id\right)modn;\hfill \\ J_n\left(\overline{c}\left(r\right)\right)\hfill & \mathrm{otherwise}.\hfill \end{array}\right.\end{array}$$

Correctness: The correctness of the decryption algorithm follows by noticing that when $r^2\equiv H\left(id\right)modn$, we have

$$\begin{array}{c}\hfill m^{\prime }=J_n\left(c\left(r\right)\right)=J_n(y^m·f{\left(r\right)}^2)={[J_p\left(y\right)·J_q\left(y\right)]}^m={[-J_p{\left(y\right)}^2]}^m={(-1)}^m,\end{array}$$

and thus we can recover the message m. When $r^2\equiv uH\left(id\right)modn$, we can proceed similarly.

Although this proposal is not anonymous (see Section 5.3), it can be made as such by using the same anonymization technique as in Section 4.1.

5.2. Previous Work

When $p\equiv -qmod4$ and $y=-1$, we obtain the scheme described in [10]. Note that in this case we can choose $h\left(x\right)=x$ since $G{T}_n(R,x·c\left(x\right))=-G{T}_n(R,c\left(x\right))$. When analyzing the scheme, the authors do not prove the success probability of decryption and of the generalized Galbraith test against their first proposal. Furthermore, when computing the size of the ciphertext space, Zhao et al. managed to prove that it is at least $(p-1)(p-3)(q-1)(q-3)/16$ (see the next section for the exact size). Two other aspects that are not rigorously stated are: the two complexity assumptions used to prove the anonymity of their second scheme and their argument that leads to the necessity of these two assumptions.

5.3. New Analysis

We start with studying the cardinality of the following sets:

$$\begin{array}{cc}\hfill C_{n,0}\left(R\right)& =\{{(ax+b)}^{2}mod{x}^2-R\mid a,b\in {\mathbb{Z}}_n\},\hfill \\ \hfill C_{n,1}\left(R\right)& =\{y{(ax+b)}^{2}mod{x}^2-R\mid a,b\in {\mathbb{Z}}_n\},\hfill \end{array}$$

which contain the polynomials generated by the scheme presented in Section 5.1. Note that we further consider that $R\ne 0$. Otherwise, we can trivially recover m by computing $J_n\left(g\left(0\right)\right)=J_n\left(y^m{b}^2\right)=J_n\left(y^m\right)={(-1)}^m$.

Lemma 9.

Let $R\in Q{R}_p$. If $J_p\left(y\right)=-1$ then $C_{p,0}\left(R\right)\cap C_{p,1}\left(R\right)=\left\{0\right\}$; else we have $C_{p,0}\left(R\right)=C_{p,1}\left(R\right)$. We also have $|C_{p,0}\left(R\right)|=|C_{p,1}{\left(R\right)|=(p+1)}^2/4$.

Proof. 

Let $J_p\left(y\right)=-1$. We first prove that the sets $C_{p,0}\left(R\right)\cap C_{p,1}\left(R\right)=\left\{0\right\}$. Let $f\left(x\right)\in C_{p,0}\left(R\right)\cap C_{p,1}\left(R\right)$. Then $f\left(x\right)\equiv {(ax+b)}^{2}mod{x}^2-R$ and $f\left(x\right)\equiv y{(cx+d)}^{2}mod{x}^2-R$ for $a,b,c,d\in {\mathbb{Z}}_p$. This is identical with

$$\begin{array}{cc}\hfill a^{2}R+b^2& \equiv y(c^{2}R+d^2)modp\hfill \\ \hfill 2ab& \equiv 2cdymodp\hfill \end{array}$$

which is equivalent with

$$\begin{array}{cc}\hfill {(ar+b)}^2& \equiv y{(cr+d)}^{2}modp\hfill \\ \hfill {(ar-b)}^2& \equiv y{(cr-d)}^{2}modp.\hfill \end{array}$$

If $a,b,c,d\ne 0$, from any of the equations we obtain that $y\in Q{R}_p$. Therefore, we obtain a contradiction, and thus $a=b=c=d=0$.

When $J_p\left(y\right)=1$, we have

$$\begin{array}{c}\hfill f\left(x\right)\equiv y{(ax+b)}^2\equiv u^2{(ax+b)}^2\equiv {(uax+ub)}^{2}mod{x}^2-R,\end{array}$$

where $u^2\equiv ymodp$. Hence, if $f\left(x\right)\in C_{p,1}\left(R\right)$, then $f\left(x\right)\in C_{p,0}\left(R\right)$. Similarly, we obtain that $f\left(x\right)\in C_{p,0}\left(R\right)$ then $f\left(x\right)\in C_{p,1}\left(R\right)$. Therefore, $C_{p,0}\left(R\right)=C_{p,1}\left(R\right)$.

Let $f_1\left(x\right)={(a_{1}x+b_1)}^2,f_2\left(x\right)={(a_{2}x+b_2)}^2\in C_{p,0}\left(R\right)$. If $f_1\left(x\right)\equiv f_2\left(x\right)mod{x}^2-R$, then $f_1{\left(x\right)}^{1/2}\equiv \pm f_2{\left(x\right)}^{1/2}mod{x}^2-R$. Thus, $(a_1\mp a_2)x+(b_1\mp b_2)\equiv 0mod{x}^2-R$. Therefore, we have $a_1\equiv \pm a_{2}modp$ and $b_1\equiv \pm b_{2}modp$. Note that for $a_1\ne 0$, we always have $a_1\not\equiv -a_{1}modp$, and thus we obtain two numbers that reach the same value when squared, and similarly for $b_1$. Hence, we obtain that $|C_{p,0}{\left(R\right)|=[(p-1)/2+1]}^2={(p+1)}^2/4$. Similarly, we obtain $|C_{p,1}{\left(R\right)|=(p+1)}^2/4$. □

Corollary 12.

Let $R\in Q{R}_n$. We assume without loss of generality that $J_p\left(y\right)=1$. Then $|C_{n,0}\left(R\right)|=|C_{n,1}{\left(R\right)|=(p+1)}^2{(q+1)}^2/16$. Furthermore, $|C_{n,0}\left(R\right)\cap C_{n,1}{\left(R\right)|=(p+1)}^2/4$ and $|C_{n,0}\left(R\right)\cup C_{n,1}{\left(R\right)|=(p+1)}^2{(q+1)}^2/8-{(p+1)}^2/4$.

Lemma 10.

Let $R\in QN{R}_p$. Then we have $|C_{p,0}\left(R\right)|=(p^2+1)/2$ and $C_{p,0}\left(R\right)=C_{p,1}\left(R\right)$.

Proof. 

Since $R\in QN{R}_p$, then $\mathbb{Z}\left[x\right]/(x^2-R)$ is a field. Let $f_1\left(x\right)={(a_{1}x+b_1)}^2\ne 0,f_2\left(x\right)={(a_{2}x+b_2)}^2\ne 0\in C_{p,0}\left(R\right)$. If $f_1\left(x\right)\equiv f_2\left(x\right)mod{x}^2-R$, then ${\left(f_1\left(x\right)f_2{\left(x\right)}^{-1}\right)}^2\equiv 1mod{x}^2-R$. Thus, $f_1\left(x\right)f_2{\left(x\right)}^{-1}\equiv \pm 1mod{x}^2-R$, which is equivalent with $f_1\left(x\right)\equiv \pm f_2\left(x\right)mod{x}^2-R$. Hence, $|C_{p,0}\left(R\right)|=(p^2+1)/2$.

Let $f\left(x\right)\in C_{p,0}\left(R\right)\cap C_{p,1}\left(R\right)$. Then $f\left(x\right)\equiv g{\left(x\right)}^{2}mod{x}^2-R$ and $f\left(x\right)\equiv yh{\left(x\right)}^{2}mod{x}^2-R$ for $g\left(x\right),h\left(x\right)\in {\mathbb{Z}}_p\left[x\right]/(x^2-R)\setminus \left\{0\right\}$. This is equivalent with

$$\begin{array}{c}\hfill y\equiv {\left(g\left(x\right)h{\left(x\right)}^{-1}\right)}^2\equiv {(v+wx)}^2\equiv v^2+w^{2}R+2vwxmod{x}^2-R\end{array}$$

which translates into

$$\begin{array}{cc}\hfill v^2+w^{2}R& \equiv ymodp\hfill \\ \hfill 2vwx& \equiv 0modp\hfill \end{array}$$

We either have $v=0$ or $w=0$. Hence, either $w^2\equiv y{R}^{-1}modp$ or $v^2\equiv ymodp$. If $J_p\left(y\right)=-1$, then the second equality lead to a contradiction and hence $v=0$ and $w\equiv {\left(y{R}^{-1}\right)}^{1/2}modp$. This leads to $g\left(x\right)h{\left(x\right)}^{-1}\equiv {\left(y{R}^{-1}\right)}^{1/2}xmod{x}^2-R$. Hence, we obtain that $C_{p,0}\left(R\right)=C_{p,1}\left(R\right)$. If $J_p\left(y\right)=1$, then the first equality leads to a contradiction, and thus $v\equiv y^{1/2}modp$ and $w=0$. This leads to $g\left(x\right)h{\left(x\right)}^{-1}\equiv y^{1/2}mod{x}^2-R$. Therefore, we obtain our desired result. □

Corollary 13.

Let $R\in J_n\setminus Q{R}_n$. Then $C_{n,0}\left(R\right)=C_{n,1}\left(R\right)$ and $|C_{n,0}\left(R\right)|=(p^2+1)(q^2+1)/4$.

Now, we consider the sets of ciphertexts that can be correctly decrypted

$$\begin{array}{cc}\hfill C_{n,0}^{\ast }\left(R\right)& =\{{(ax+b)}^{2}mod{x}^2-R\mid a,b\in {\mathbb{Z}}_n;ar+b\in {\mathbb{Z}}_n^{\ast }\},\hfill \\ \hfill C_{n,1}^{\ast }\left(R\right)& =\{y{(ax+b)}^{2}mod{x}^2-R\mid a,b\in {\mathbb{Z}}_n;ar+b\in {\mathbb{Z}}_n^{\ast }\}.\hfill \end{array}$$

Lemma 11.

Let $R\in Q{R}_p$. If $J_p\left(y\right)=-1$ then $C_{p,0}^{\ast }\left(R\right)\cap C_{p,1}^{\ast }\left(R\right)=\varnothing$; else we have $C_{p,0}^{\ast }\left(R\right)=C_{p,1}^{\ast }\left(R\right)$. We also have $|C_{p,0}^{\ast }\left(R\right)|=|C_{p,1}^{\ast }\left(R\right)|=(p^2-1)/4$.

Proof. 

We first note that if $a=b=0$, then $ax+b\notin {\mathbb{Z}}_n^{\ast }$. Using Lemma 9, we obtain the first statement.

Now, we want to see how many of these pairs collapse to the same polynomial value. Similarly to the proof of Lemma 9, from $f_1\left(x\right)\equiv f_2\left(x\right)mod{x}^2-R$, we obtain $a_1\equiv \pm a_{2}modp$ and $b_1\equiv \pm b_{2}modp$. These numbers must also satisfy the restriction $b_1\not\equiv -a_{1}rmodp$.

We first consider the case $a_1=a_2=0$. Since we have $b_1\equiv a_{1}r+b_1\in {\mathbb{Z}}_p^{\ast }$, then there are $(p-1)/2$ non-collapsing values for $b_1$. On the other hand, if $a_1\ne 0$, then for $a_1$ we are able to find $(p-1)/2$ different non-collapsing values and for $b_1$ we are able to find $2+(p-3)/2=(p+1)/2$ non-collapsing values. (we have to count the pairs $(a_1,0)$ and $(a_1,a_{1}r)$) Hence, there will be $(p-1)(p+1)/4$ such polynomials in $C_{p,0}^{\ast }\left(R\right)$. Similarly, we obtain that $|C_{p,1}^{\ast }\left(R\right)|=(p^2-1)/4$. □

Corollary 14.

Let $R\in Q{R}_n$. Then $|C_{n,0}^{\ast }\left(R\right)|=|C_{n,1}^{\ast }\left(R\right)|=(p^2-1)(q^2-1)/16$. Furthermore, $C_{n,0}^{\ast }\left(R\right)\cap C_{n,1}^{\ast }\left(R\right)=\varnothing$ and $|C_{n,0}^{\ast }\left(R\right)\cup C_{n,1}^{\ast }\left(R\right)|=(p^2-1)(q^2-1)/8$.

Corollary 15.

The probability of correct decryption is $1+\mathcal{O}(1/n^2)$.

Proof. 

From Corollaries 12 and 14, we obtain that the probability is

$$\begin{array}{c}\hfill \frac{|C_{n,0}^{\ast }\left(R\right)\cup C_{n,1}^{\ast }\left(R\right)|}{|C_{n,0}\left(R\right)\cup C_{n,1}\left(R\right)|}=\frac{(p^2-1)(q^2-1)}{{(p+1)}^2{(q+1)}^2-8\delta }\simeq 1+\mathcal{O}\left(\frac{1}{n^2}\right),\end{array}$$

where $\delta \in \{{(p+1)}^2/4,{(q+1)}^2/4\}$. □

Now we will study ciphertexts with a given generalized Galbraith value. Thus, we define

$$\begin{array}{cc}\hfill C_p^{\ell }\left(R\right)& =\{f_{0}x+f_1\in C_{p,0}\left(R\right)\cup C_{p,1}\left(R\right)\mid J_p(f_1^2-f_0^{2}R)=\ell \},\hfill \\ \hfill C_n^0\left(R\right)& =\{f_{0}x+f_1\in C_{n,0}\left(R\right)\cup C_{n,1}\left(R\right)\mid J_n(f_1^2-f_0^{2}R)=0\},\hfill \\ \hfill C_n^1\left(R\right)& =\{f_{0}x+f_1\in C_{n,0}\left(R\right)\cup C_{n,1}\left(R\right)\mid J_p(f_1^2-f_0^{2}R)=J_q(f_1^2-f_0^{2}R)=\ell \},\hfill \end{array}$$

where $\ell \in \{0,1\}$.

Lemma 12.

The following statements are true

1. 

If $R\in QN{R}_p$ then $|C_p^0\left(R\right)|=1$; else

$$\begin{array}{c}\hfill |C_p^0\left(R\right)|=\left\{\begin{array}{cc}p\hfill & \mathrm{if}{J}_p\left(y\right)=1,\hfill \\ 2p-1\hfill & \mathrm{if}{J}_p\left(y\right)=-1.\hfill \end{array}\right.\end{array}$$

2. 

If $R\in QN{R}_p$ then $|C_p^1\left(R\right)|=(p^2-1)/2$, else

$$\begin{array}{c}\hfill |C_p^1\left(R\right)|=\left\{\begin{array}{cc}{(p-1)}^2/4\hfill & \mathrm{if}{J}_p\left(y\right)=1,\hfill \\ {(p-1)}^2/2\hfill & \mathrm{if}{J}_p\left(y\right)=-1.\hfill \end{array}\right.\end{array}$$

Proof. 

Let $f=y^m{(ax+b)}^2=y^m(a^{2}R+b^2+2abx)$, where $m\in \{0,1\}$. We observe that $J_n(f_1^2-f_0^{2}R)=J_n({(a^{2}R+b^2)}^2-4a^2{b}^{2}R)$. Hence, the Jacobi symbol is independent of y.

Since $f\in C_p^0\left(R\right)$ we have ${(a^{2}R+b^2)}^2-4a^2{b}^{2}R\equiv 0modp$. This is equivalent with $a^{2}R-b^2\equiv 0modp$. If $R\in QN{R}_p$, then $C_p^0\left(R\right)=\left\{0\right\}$. Otherwise, we obtain $(ar-b)(ar+b)\equiv 0modp$. Thus, we can rewrite the set as $C_p^0\left(R\right)=\{2a^{2}r{y}^m(\pm x+r)\mid a\in {\mathbb{Z}}_p;m\in \{0,1\}\}$. Let

$$\begin{array}{cc}\hfill C_{p,0}^0\left(R\right)& =\{2a^{2}r(\pm x+r)\mid a\in {\mathbb{Z}}_p\},\hfill \\ \hfill C_{p,1}^0\left(R\right)& =\{2a^{2}ry(\pm x+r)\mid a\in {\mathbb{Z}}_p\}.\hfill \end{array}$$

We further count the distinct elements of $C_{p,0}^0\left(R\right)$. From $2a^{2}r(\pm x+r)\equiv 2c^{2}r(\pm x+r)mod{x}^2-R$ we obtain $a\equiv \pm cmodp$. From the relation $2a^{2}r(x+r)\equiv 2c^{2}r(-x+r)mod{x}^2-R$ we obtain $a^2(x+r)+c^2(x-r)\equiv 0mod{x}^2-R$. Hence, we obtain $a=c=0$. Thus, the cardinality of $C_{p,1}^0\left(R\right)$ is p.

Now let us consider the intersection of $C_{p,0}^0\left(R\right)$ and $C_{p,1}^0\left(R\right)$. From $2a^{2}r(\pm x+r)\equiv 2y{c}^{2}r(\pm x+r)mod{x}^2-R$ we obtain $a\equiv \pm ycmodp$ if $J_p\left(y\right)=1$ and $a=c=0$ otherwise. Hence, $C_{p,0}^0\left(R\right)=C_{p,1}^0\left(R\right)$, if $J_p\left(y\right)=1$ and $C_{p,0}^0\left(R\right)\cap C_{p,1}^0\left(R\right)=\left\{0\right\}$ otherwise.

The last statement results from observing that all the elements from $C_{p,0}\left(R\right)\cup C_{p,1}\left(R\right)$ have the Jacobi symbol $J_p(f_1^2-f_0^{2}R)$ either 1 or 0. Hence, using Lemma 9, we obtain our result. □

Corollary 16.

We assume without loss of generality that $J_p\left(y\right)=1$. Then the following statements are true

1. 

If $R\in J_n\setminus Q{R}_n$ then $|C_n^0\left(R\right)|=(p^2+q^2)/2$, else if $R\in Q{R}_n$$|C_n^0{\left(R\right)|=(pq+1)(p+q)/2-(p+1)}^2/4$.

2. 

If $R\in J_n\setminus Q{R}_n$ then $|C_n^1\left(R\right)|=(p^2-1)(q^2-1)/4$, else if $R\in Q{R}_n$$|C_n^1{\left(R\right)|=(p-1)}^2{(q-1)}^2/8$.

Corollary 17.

The probability that a ciphertext $f\left(x\right)$ produced by the scheme from Section 5.1 has $G{T}_n(R,f\left(x\right))=1$ is $1+\mathcal{O}(1/n^2)$.

Proof. 

According to Corollaries 12, 13 and 16 we have

$$\begin{array}{c}\hfill \frac{|C_n^1\left(R\right)|}{|C_{n,0}\left(R\right)\cup C_{n,1}\left(R\right)|}=\left\{\begin{array}{cc}\frac{(p^2-1)(q^2-1)}{(p^2+1)(q^2+1)}\simeq 1+\mathcal{O}\left(\frac{1}{n^2}\right)\hfill & \mathrm{if}R\in J_n\setminus Q{R}_n\hfill \\ \frac{{(p-1)}^2{(q-1)}^2}{{(p+1)}^2{(q+1)}^2-8\delta }\simeq 1+\mathcal{O}\left(\frac{1}{n^2}\right)\hfill & \mathrm{if}R\in Q{R}_n,\hfill \end{array}\right.\end{array}$$

where $\delta \in \{{(p+1)}^2/4,{(q+1)}^2/4\}$. □

Corollary 18.

The generalized Galbraith test can detect ciphertexts produced by the scheme from Section 5.1 with a probability of $1/2+\mathcal{O}(1/n^2)$ if $R\in J_n\setminus Q{R}_n$ and $1/4+\mathcal{O}(1/n^2)$ if $R\in Q{R}_n$.

Proof. 

According to Corollaries 1, 12 and 13 we have

$$\begin{array}{c}\hfill \frac{|C_n\left(R\right)|}{|P_n^{1,1}\left(R\right)\cup P_n^{-1,-1}\left(R\right)|}=\left\{\begin{array}{cc}\frac{(p^2+1)(q^2+1)}{2(p^2-1)(q^2-1)}\simeq \frac{1}{2}+\mathcal{O}\left(\frac{1}{n^2}\right)\hfill & \mathrm{if}R\in J_n\setminus Q{R}_n\hfill \\ \frac{{(p+1)}^2{(q+1)}^2-8\delta }{4{(p-1)}^2{(q-1)}^2}\simeq \frac{1}{4}+O\left(\frac{1}{n^2}\right)\hfill & \mathrm{if}R\in Q{R}_n,\hfill \end{array}\right.\end{array}$$

where $\delta \in \{{(p+1)}^2/4,{(q+1)}^2/4\}$. □

Using our results, we further redo the analysis from [10] and present the exact assumptions used to prove that the IBE scheme from Section 5.1 can be anonymized using the technique described in Section 4.1.

Let $P_n^{+}\left(R\right)=P_n^{1,1}\left(R\right)\cup P_n^{-1,-1}\left(R\right)$ and $C_n\left(R\right)=C_{n,0}\left(R\right)\cup C_{n,1}\left(R\right)$. According to Corollaries 1, 12 and 13, we have that $|P_n^{+}\left(R\right)\times P_n^{+}\left(uR\right)|=\mathcal{O}\left(p^2{q}^2\right)$ and $|C_n\left(R\right)\times C_n\left(uR\right)|=\mathcal{O}(3p^2{q}^2/8-\delta )$, where $\delta \in \{p^2/4,q^2/4\}$. Since p and q are large primes, we can make the following computational assumption

Assumption 1.

For an identity $id$, the set $P_n^{+}\left(R\right)\times P_n^{+}\left(uR\right)$ is computationally indistinguishable from the ciphertext space when $v_1=v_2=0$ (i.e., $C_n\left(R\right)\times C_n\left(uR\right)$).

Let $P_n^{-}\left(R\right)=P_n^{1,-1}\left(R\right)\cup P_n^{-1,1}\left(R\right)$. According to Corollaries 1, 2, 12 and 13, we have that $|P_n^{-}\left(R\right)\times P_n^{-}\left(uR\right)|=\mathcal{O}\left(p^2{q}^2\right)$ and

$$\begin{array}{cc}\hfill |T_n(R,h\left(x\right),C_n\left(R\right))\times T_n(uR,h\left(x\right),C_n\left(uR\right))|& =|C_n\left(R\right)\times C_n\left(uR\right)|\hfill \\ \hfill & =\mathcal{O}(3p^2{q}^2/8-\delta ),\hfill \end{array}$$

where $\delta \in \{p^2/4,q^2/4\}$. Since p and q are large primes, we can make the following computational assumption:

Assumption 2.

For an identity $id$, the set $P_n^{+}\left(R\right)\times P_n^{-}\left(uR\right)$ is computationally indistinguishable from the ciphertext space when $v_1=v_2=1$ (i.e., $T_n(R,h\left(x\right),C_n\left(R\right))\times T_n(uR,h\left(x\right),C_n\left(uR\right))$).

6. Conclusions

In this paper, we reevaluated the extension of Galbraith’s test to the polynomial ring ${\mathbb{Z}}_n\left[x\right]/(x^2-R)$. By studying its exact behaviour, we were able to perform a deeper and a more rigorous analysis of Clear et al.’s and Zhao et al.’s IBE schemes. Therefore, we offer the reader a better understanding of these two schemes. To be more specific, we obtained a precise value for the probability of a successful decryption, the exact efficiency of the generalized Galbraith test, and, in the case of Zhao et al.’s IBE scheme, a thorough description of the underlying security assumptions.

Future Work

In [15], the authors introduce an analog of Galbraith’s test for higher residues. We believe that a more in-depth study of this test can lead to a simpler description of it and can also help researchers to devise an anonymizing technique that renders this test ineffective.