Fabrice Benhamouda
email: fabrice.benhamouda@ens.fr

Javier Herranz
email: javier.herranz@upc.edu

Marc Joye
email: marc.joye@technicolor.com

Benoît Libert
email: benoit.libert@ens-lyon.fr

Efficient Cryptosystems From 2 k -th Power Residue Symbols

Keywords: Public-key encryption, quadratic residuosity, Goldwasser-Micali cryptosystem, homomorphic encryption, standard model

highlighted the importance of randomizing the plaintext for public-key encryption and introduced the notion of semantic security. They also realized a cryptosystem meeting this security notion under the standard complexity assumption of deciding quadratic residuosity modulo a composite number. The Goldwasser-Micali cryptosystem is simple and elegant but is quite wasteful in bandwidth when encrypting large messages. A number of works followed to address this issue and proposed various modifications. This paper revisits the original Goldwasser-Micali cryptosystem using 2 k -th power residue symbols. The so-obtained cryptosystems appear as a very natural generalization for k ≥ 2 (the case k 1 corresponds exactly to the Goldwasser-Micali cryptosystem). Advantageously, they are efficient in both bandwidth and speed; in particular, they allow for fast decryption. Further, the cryptosystems described in this paper inherit the useful features of the original cryptosystem (like its homomorphic property) and are shown to be secure under a similar complexity assumption. As a prominent application, this paper describes an efficient lossy trapdoor function based thereon.

Introduction

Encryption is arguably one of the most fundamental cryptographic primitives. Although it seems an easy task to identify properties that a good encryption scheme must fulfill, it turns out that rigorously defining the right security notion is not trivial at all. Security is context sensitive. Merely requiring that the plaintext cannot be recovered from the ciphertext is not enough in most applications. One may require that the knowledge of some a priori information on the plaintext does not help the adversary to obtain any new information, that is, beyond what can be obtained from the a priori information. This intuition is formally captured by the notion of semantic security, introduced in a seminal paper by Goldwasser and Micali [GM84]. They also introduced the equivalent notion of indistinguishability of encryptions, which is usually easier to work with. Given the encryption A preliminary version of this paper appears in the proceedings of EUROCRYPT 2013. Part of this work was done while this author was with Technicolor, France.

of any two equal-length (distinct) plaintexts, an adversary should not be able to distinguish the corresponding ciphertexts.

Clearly, the latter notion is only achievable by probabilistic encryption schemes. One such cryptosystem was also presented in [GM84]. It achieves ciphertext indistinguishability under the Quadratic Residuosity (QR) assumption. Informally, this assumption says that it is infeasible to distinguish squares from non-squares in J N (i.e., the set of elements in Z * N whose Jacobi symbol is +1) where N pq is an RSA-type modulus of unknown factorization.

The Goldwasser-Micali cryptosystem is simple and elegant. The public key comprises an RSA modulus N pq and a non-square y ∈ J N while the private key is the secret factor p. The encryption of a bit m ∈ {0, 1} is given by c y m x 2 mod N for a random x ∈ Z * N . The message m is recovered using p, by checking whether c is a square: m 0 if so, and m 1 otherwise -observe that a non-square y ∈ J N is also a non-square modulo p. The encryption of a bitstring m (m k-1 , . . . , m 0 ) 2 , with m i ∈ {0, 1}, proceeds by forming the ciphertexts c i y m i x 2 mod N, for 0 ≤ i ≤ k -1. The scheme is computationally efficient but somewhat wasteful in bandwidth as k • log 2 N bits are needed to encrypt a k-bit message. Several proposals were made to address this issue.

A first attempt is due to Blum and Goldwasser [BG84]. They achieve a better ciphertext expansion: the ciphertext has the same length as the plaintext plus an integer of the size of the modulus. The scheme is proved semantically secure assuming the unpredictability of the output of the Blum-Blum-Shub's pseudo-random generator [BBS82, BBS86], which resides on the factorization hardness assumption. Details about this scheme can be found in [Gol04].

Another direction, put forward by Benaloh and Fischer [CF85,Ben87], is to use a k-bit prime r such that r | p -1, r 2 p -1 and r q -1. The scheme also requires y ∈ Z * N such that y φ(N)/r 1 (mod N), where φ(N) (p -1)(q -1) denotes Euler's totient function. A k-bit message m (with m < r) is encrypted as c y m x r mod N, where x ∈ R Z * N . It is recovered by searching over the entire message space, [0, r) ⊆ {0, 1} k , for the element m satisfying (y φ(N)/r ) m ≡ c φ(N)/r (mod N). The scheme is shown to be secure under the prime-residuosity assumption (which generalizes the quadratic residuosity assumption). With the Benaloh-Fischer cryptosystem, the ciphertext corresponding to a k-bit message is short but the decryption process is now demanding. In practice, the scheme is therefore limited to small values of k, say k < 40. The Benaloh-Fischer cryptosystem was subsequently extended by Naccache and Stern [NS98]. They observe that the decryption can be sped up by rather considering a product of small (odd) primes R i r i such that r i | φ(N) but r i 2 φ(N) for each prime r i . Given a ciphertext, the plaintext m is reconstructed from m i m mod r i through Chinese remaindering. The advantage is that each m i is searched in the subspace [0, r i ) instead of the entire message space. A variant of this technique was used by Groth [Gro05].

Other generalizations and extensions of the Goldwasser-Micali cryptosystem but without formal security analysis can be found in [ZMI88, KKOT90,PLW95]. In [MV04b,MV04a], Monnerat and Vaudenay developed applications using the more general theory of characters, specifically with characters of order ≤ 4. Related cryptosystems are described in [SW95,Sch98]. A different approach was proposed by Okamoto and Uchiyama [OU98], who suggested to use moduli of the form N p 2 q. This allows encrypting messages of size up to log 2 p bits. This was later extended by Paillier [Pai99] to the setting N p 2 q 2 ; see also [CGHGN01,DJN10].

A useful application of additive homomorphic encryption schemes resides in the construction of lossy trapdoor functions (or LTDFs in short). These functions, as introduced by Peikert and Waters [PW08], are function families wherein injective functions are computationally indistin-guishable from lossy functions, which lose many bits of information about their input. LTDFs have proved to be very powerful and versatile in the cryptographer's toolbox. They notably imply chosen-ciphertext-secure public-key encryption [PW08], deterministic encryption [BBO07, BFO08], as well as cryptosystems that retain some security in the absence of reliable randomness [BBN + 09] or in the presence of selective-opening adversaries [BHY09].

Our contributions

N H

C . We suggest an improvement of the original Goldwasser-Micali cryptosystem. It can be seen as a follow-up of the earlier works due to Benaloh and Fischer [CF85] and Naccache and Stern [NS98]. Before discussing it, we quote from [NS98]:

"Although the question of devising new public-key cryptosystems appears much more difficult . . . we feel that research in this direction is still in order simple yet efficient constructions may have been overlooked."

It is striking that the generalized cryptosystem in this paper was not already proposed because, as will become apparent (cf. Section 3), it turns out to be a very natural generalization. Our approach consists in considering n th -power residues modulo N with n 2 k (the Goldwasser-Micali system corresponds to the case k 1). This presents many advantages. First, the resulting cryptosystem is bandwidth-efficient. Only log 2 N bits are needed for encrypting a k-bit message in typical applications (e.g., using the KEM/DEM paradigm). Second, the decryption process is fast. Searches are no longer needed (not even in smaller subspaces) in the decryption algorithm as plaintext messages can be recovered bit by bit. Further, although asymptotically slower than in Paillier's cryptosystem, the decryption process turns out to achieve comparable performance for most practical values of k (e.g., k ≤ 128). As a last advantage, the underlying complexity assumptions are similar to that used by Goldwasser and Micali. The proposed cryptosystem is shown to be secure under the quadratic residuosity assumption for RSA moduli N pq such that p ≡ 1 (mod 2 k ) and q ≡ 3 (mod 4). When q 3 (mod 4), it assumes in addition the hardness of determining the Jacobi symbol of an element y ∈ Z * N given a pair (x, N) where x y 2 mod N. Although the proposed cryptosystem makes use of primes of special form, there are no known factoring algorithms taking advantage of that. Further, complexity-wise, the use of such special primes does not incur penalty with the latest prime generation algorithms. As will be seen, the time required to generate a random prime p ≡ 1 (mod 2 k ) is essentially the same as the time required to generate a random, form-free prime.

We also note that, similarly to the Goldwasser-Micali cryptosystem, our generalized cryptosystem enjoys an additive property known as homomorphic encryption. If c 1 and c 2 denote two ciphertexts corresponding to k-bit plaintexts m 1 and m 2 , respectively, then c 1 • c 2 (mod N) is an encryption of the message m 1 + m 2 (mod 2 k ). This reveals useful in several applications like voting schemes.

As another useful property, the new scheme inherits the selective opening security [DNRS03, BHY09] of the Goldwasser-Micali system (in the sense of a simulation-based definition given in [BHY09]). We actually prove its semantic security by showing that its public key is indistinguishable from a so-called lossy key for which encryptions reveal nothing about the encrypted message.

We thus believe our system to provide an interesting competitor to Paillier's cryptosystem for certain applications. As a salient example, we show that it provides a dramatically improved lossy trapdoor function.

N E

L T F . The initial LTDF realizations [PW08] were based on the Decisional Diffie-Hellman (DDH) and Learning-with-Error (LWE) [Reg09] assumptions. More efficient examples based on the Decisional Composite Residuosity (DCR) assumption were given in [BFO08, FGK + 10, FGK + 13] while Kiltz et al. [KOS10] showed that the RSA permutation provides a lossy function. Under the Quadratic Residuosity (QR) assumption, three distinct constructions were put forth in [HO12, FGK + 10, FGK + 13, Wee12]. Those of Freeman et al. [FGK + 10, FGK + 13] and of Wee [Wee12] must be used in combination with the results of Mol and Yilek [MY10] as they only lose single bits of information about the input. Hemenway and Ostrovsky [HO12] suggested a more efficient realization, of which Wee's framework [Wee12] is a generalization. While their QR-based LTDF has found applications in the design of deterministic encryption schemes [BS11], it is conceptually very similar to the Peikert-Waters matrix-based schemes and suffers from similarly large outputs and descriptions.

We show that our variant of the Goldwasser-Micali cryptosystem drastically improves the efficiency of the Hemenway-Ostrovsky LTDF. Specifically, it reduces both the length of the output and the description of the function. By appropriately selecting the parameters, we obtain evaluation keys and outputs consisting of a constant number of Z * N elements. We thus get a DDH/QR-based LTDF, whose efficiency is competitive with Paillier-based realizations [BFO08, FGK + 10, FGK + 13]. These improvements carry over to the deterministic encryption setting, when the Hemenway-Ostrovsky LTDF is used as a building block of the Brakerski-Segev system [BS11].

Outline of the paper

In the next section, we introduce some mathematical background and review some complexity assumptions. In Section 3, we present our generalized cryptosystem. We prove its security in Section 4. Section 5 discusses certain implementation aspects. In Section 6, we describe our new lossy trapdoor function. Finally, we conclude in Section 7.

Background

We review some useful background and fix the notation. In particular, we define the n-th power residue symbol. We refer the reader to [IR90, Sho10, Yan02] for further details on (quadratic) residuosity. More information about encryption schemes can be found in textbooks in cryptography; e.g. [Gol04,KL07].

General notation

The set of non-negative integers is denoted by N. For any integer N ≥ 2, Z N denotes the ring of integers modulo N, and Z * N denotes its group of units. The order of Z * N is φ(N), where φ is Euler's totient function.

For any positive integer N and any integer a, a mod N represents the smallest integer in the set {0, . . . , N -1} that is congruent to a modulo N. Furthermore, for any positive odd integer N and any integer a, a mods N represents the absolute smallest residue of a modulo N -note the "s" ending the "mod" operator. The complete set of absolute smallest residues is {-(N -1)/2, . . . , -1, 0, 1, . . . , (N -1)/2}.

n th -power residues

Let N ≥ 2 be an integer. For each integer n ≥ 2, we define (Z * N ) n {x n | x ∈ Z * N } as the set of n th -power residues modulo N. If the relation a x n has no solution in Z * N then a is called a n th -power non-residue modulo N.

Suppose that p is an odd prime. For any integer a with gcd(a, p) 1, it is easily verified that a is a n th -power residue modulo p if and only if a p-1 gcd(n,p-1) ≡ 1 (mod p) .

When n 2 (and so gcd(n, p -1) 2), this is known as Euler's criterion. It allows one to distinguish quadratic residues from quadratic non-residues. This defines the Legendre symbol:

a p      1 if a is a quadratic residue modulo p -1 if a is a quadratic non-residue modulo p .
There are several ways to generalize the Legendre symbol (see [Lem00]). In this paper, we consider the n-th power residue symbol for a divisor n of (p -1), as presented in [Yan02,Definition 1.6.21]. (-1)

p-1 n .

Quadratic residuosity

Let N pq be the product of two (odd) primes p and q. For an integer a co-prime to N, the Jacobi symbol is the product of the corresponding Legendre symbols, namely a N a p a q . This gives rise to the multiplicative group J N of integers whose Jacobi symbol is +1,

J N a ∈ Z * N | a N 1 . A relevant subset of J N is the set of quadratic residues modulo N, QR N a ∈ Z * N | a p a q
1 . The set of integers whose Jacobi symbol is -1 is denoted by J

N ; i.e., J N a ∈ Z * N | a N -1 Z * N \ J N .
The Quadratic Residuosity (QR) assumption says that, given a random element a ∈ J N , it is hard to decide whether a ∈ QR N if the prime factors of N are unknown. To emphasize that this should hold for RSA moduli N pq with p ≡ 1 (mod 2 k ) for some k ≥ 1, we refer to it as the k-QR assumption.

Formally, we have: Definition 2 (Quadratic Residuosity Assumption, k-QR). Let RSAGen be a probabilistic algorithm which, given a security parameter κ, outputs primes p and q such that p ≡ 1 (mod 2 k ), and their product N pq. The Quadratic Residuosity (k-QR) assumption asserts that the function Adv k-QR D (κ), defined as the distance

Pr[D (x, N) 1 | x R ← QR N ] -Pr[D (x, N) 1 | x R ← J N \ QR N ]
is negligible for any probabilistic polynomial-time distinguisher D; the probabilities are taken over the experiment of running (N, p, q) ← RSAGen(1 κ ) and choosing at random x ∈ QR N and x ∈ J N \ QR N .

We also introduce a new assumption. The new assumption, which we call the Squared Jacobi Symbol (SJS) assumption, posits the infeasibility of determining whether

y N 1 or -1 given (x, N)
where x y 2 mod N. Again, when the assumption is directed to RSA moduli N pq with p ≡ 1 (mod 2 k ), we write it k-SJS. Formally, we define: Definition 3 (Squared Jacobi Symbol Assumption, k-SJS). Let RSAGen be a probabilistic algorithm which, given a security parameter κ, outputs primes p and q such that p ≡ 1 (mod 2 k ), and their product N pq. The Squared Jacobi Symbol (k-SJS) assumption asserts that the function Adv k-SJS D (κ), defined as the distance

Pr[D (y 2 mod N, N) 1 | y R ← J N ] -Pr[D (y 2 mod N, N) 1 | y R ← J N ]
is negligible for any probabilistic polynomial-time distinguisher D; the probabilities are taken over the experiment of running (N, p, q) ← RSAGen(1 κ ) and choosing at random y ∈ J N and y ∈ J N .

When q ≡ 3 (mod 4), any element x ∈ QR N has four square roots: two of Jacobi symbol +1 and two of Jacobi symbol -1. In that case, as detailed in Section 3.3, the k-SJS assumption holds perfectly.

A New Public-Key Encryption Scheme

We generalize the Goldwasser-Micali cryptosystem so that it can efficiently support the encryption of larger messages while remaining additively homomorphic.

Description

The setting is basically the same as for the Goldwasser-Micali cryptosystem. The only additional requirement is that the prime p is chosen congruent to 1 modulo 2 k , where k denotes the bit-size of the messages being encrypted. The case k 1 (i.e., encryption of 1-bit messages) corresponds to the Goldwasser-Micali cryptosystem.

In more detail, our encryption scheme is the tuple (KeyGen, Encrypt, Decrypt) defined as follows.

KeyGen(1 κ ) Given a security parameter κ, KeyGen defines an integer k ≥ 1, randomly generates primes p and q such that p ≡ 1 (mod 2 k ), and sets N pq. It also picks a random y ∈ J N \ QR N .

The public and private keys are pk {N, y, k} and sk {p}, respectively. Encrypt(pk, m) Let M {0, 1} k . To encrypt a message m ∈ M (seen as an integer in {0, . . . , 2 k -1}), The correctness of the decryption is easily verified by observing that α y p 2 k has order 2 k as an element in Z * p . Indeed, letting n ord p (α) the order of α, we have n | 2 k since, by definition,

α ≡ y p-1 2 k (mod p). But n cannot be equal to 2 k for some k < k because α 2 k ≡ 1 (mod p) would imply y p-1 2 ≡ 1 (mod p), which contradicts the assumption that y ∈ J N \ QR N ⇐⇒ y p y q -1.
The decryption algorithm recovers the unique m ∈ {0, . . . , 2 k -1} such that α m ≡ z (mod p).

Furthermore, the scheme is homomorphic for the addition modulo 2

k : if c 1 y m 1 x 1 2 k and c 2 y m 2 x 2 2 k are ciphertexts of m 1 and m 2 respectively, then c 1 • c 2 y m 1 +m 2 (x 1 x 2 ) 2 k mod N is a ciphertext of m 1 + m 2 (mod 2 k ).

Fast decryption

At first glance, from the above description, it seems that the decryption process amounts to a search through the entire message space {0, 1} k , similarly to some earlier cryptosystems. But we can do better. One of the main advantages of the proposed cryptosystem is that it provides an efficient way to recover the message. Hence, it remains practical, even for large values of k. The decryption algorithm proceeds similarly to the Pohlig-Hellman algorithm [PH78].

The message m ∈ {0, 1} k is viewed as a k-bit integer given by its binary expansion

m k-1 i 0 m i 2 i , with m i ∈ {0, 1}. Given c y m x 2 k mod N, we have c p 2 i y m x 2 k p 2 i y i-1 j 0 m j 2 j p 2 i y p i-1 j 0 m j 2 j 2 i mods p since y m x 2 k y i-1 j 0 m j 2 j • y k-1 j i m j 2 j-i x 2 k-i 2 i , for 1 ≤ i ≤ k.
As a result, m can be recovered bit by bit using p, starting from the least significant bit. Implementation details are provided in Section 5.2.

Security analysis

We focus on semantic security. The case k 1 corresponds to the Goldwasser-Micali cryptosystem. Indeed, when k 1, the 2 k -th power residue symbol is then the classical Legendre symbol and the assumption p ≡ 1 (mod 2 k ) is trivially verified. The Goldwasser-Micali scheme has indistinguishable encryptions under the standard Quadratic Residuosity assumption. In the general case (i.e., k ≥ 1), we prove that the scheme provides indistinguishable encryptions (IND-CPA security) under the k-QR and k-SJS assumptions. More precisely: Theorem 1. Let κ denote the security parameter. For any IND-CPA adversary A against the scheme of Section 3.1, there exist a k-QR distinguisher D 1 and a k-SJS distinguisher D 2 with comparable running times and such that

Adv ind-cpa A (κ) ≤ 3 2 (k -1 3 ) • Adv k-QR D 1 (κ) + (k -1) • Adv k-SJS D 2 (κ) .
Proof. The proof is given in Section 4.

When k 1, the theorem reads Adv ind-cpa

A (κ) ≤ Adv QR D 1 (κ), as shown in [GM84]. We henceforth assume k ≥ 2. When k ≥ 2, the condition p ≡ 1 (mod 2 k ) implies p ≡ 1 (mod 4).
Depending on q, there are two possible sub-cases. If q ≡ 1 (mod 4) then -1 is a square modulo p and modulo q. The square roots of any element of QR N then all have the same Jacobi symbol modulo N. The hardness to distinguish among them is captured by the k-SJS assumption.

The sub-case q ≡ 3 (mod 4) is more interesting. We then have -1 N -1. As a consequence, by definition of the Jacobi symbol, it follows that

y 2 mod N | y ∈ J N y 2 mod N | y N -1 (-y) 2 mod N | -y N -1 y 2 mod N | - y N -1 y 2 mod N | y ∈ J N .
Since the two sets are identical, the k-SJS assumption holds perfectly when q ≡ 3 (mod 4). This in turn leads to the following corollary.

Corollary 1. When q ≡ 3 (mod 4), for any IND-CPA adversary A against the scheme of Section 3.1, there exists a k-QR distinguisher D with comparable running time and such that

Adv ind-cpa A (κ) ≤ 1 2 (3k -1) • Adv k-QR D (κ) .
Proof. First observe that the bound is valid for k 1. For k ≥ 2, the corollary follows by letting

D 1 D and plugging Adv k-SJS D 2 (κ) 0 in the bound of Theorem 1.
The bound in Corollary 1 can be slightly tightened by a more direct proof. We have:

Theorem 2. Let κ denote the security parameter. For any IND-CPA adversary A against the scheme of Section 3.1 with q ≡ 3 (mod 4), there exists a k-QR distinguisher D with comparable running time and such that Adv

ind-cpa A (κ) ≤ 1 2 (k + 1) • Adv k-QR D (κ) .
Proof. The proof is given in appendix.

Comparing the security bounds offered by Theorems 1 and 2, it turns out that RSA moduli N pq with p ≡ 1 (mod 2 k ) and q ≡ 3 (mod 4) should be preferred over RSA moduli with q ≡ 1 (mod 4). More importantly, selecting RSA moduli N pq with p ≡ 1 (mod 2 k ) and q ≡ 3 (mod 4)

presents the advantage that the security solely relies on a QR-based assumption (namely, the k-QR assumption).

Regarding the weaker notion of one-wayness, it is easy to see that one-wayness can be proved just under the k-QR assumption in all cases. Let B be an adversary which returns m when given c y m x 2 k mod N and N (with x R ← Z * N ). We construct a distinguisher D for the k-QR assumption as follows. It takes as input an RSA modulus N pq with p ≡ 1 (mod 2 k ) and an element w ∈ Z * N .

Its goal is to distinguish whether w ∈ QR N or w ∈ J N \ QR N . To do this, D simply picks a random x ∈ Z * N , sets c wx 2 mod N, and feeds B with (c, N). When the latter outputs a result m, D outputs the least significant bit of m. It is clear that if w ∈ QR N , c is a ciphertext of an even plaintext; otherwise, c is a ciphertext of an odd plaintext. Hence if B is a successful attacker against one-wayness, D is a successful distinguisher for k-QR.

Security Proof

Gap 2 k -residuosity assumption

The k-QR assumption states that, without knowing the factorization of N, random elements of QR N are computationally indistinguishable from random elements of J N \ QR N . Here, it will be convenient to consider a gap variant of the k-QR assumption. We chose the terminology "gap" (not to be confused with computational problems which have an easy decisional counterpart [OP01]) by analogy with certain lattice problems, where not every instance is a or instance since a gap exists between these.

Definition 4 (Gap 2 k -Residuosity Assumption, Gap 2 k -Res). Let RSAGen be a probabilistic algorithm which, given a security parameter κ, outputs primes p and q such that p ≡ 1 (mod 2 k ). The Gap 2 k -Residuosity problem in Z * N consists in distinguishing a uniform element of V 0 from a uniform element of V 1 given only N pq, where V 0 and V 1 are defined as follows:

V 0 x ∈ J N \ QR N and V 1 y 2 k mod N | y ∈ Z * N .
The Gap 2 k -Residuosity (Gap 2 k -Res) assumption posits that the advantage Adv

Gap 2 k -Res D (κ), defined as the distance Pr[D (x, k, N) 1 | x R ← V 0 ] -Pr[D (x, k, N) 1 | x R ← V 1 ]
is negligible for any probabilistic polynomial-time distinguisher D; the probabilities are taken over the experiment of running (N, p, q) ← RSAGen(1 κ ) and choosing

x R ← V 0 and x R ← V 1 .
The latter assumption was independently considered in [ABP13] by Abdalla, Ben Hamouda and Pointcheval who used it to provide tighter security proofs for forward-secure signatures.

Gap 2 k -Res is implied by k-QR and k-SJS

We now investigate the relationship between the Gap 2 k -Residuosity assumption and other more natural assumptions; namely, we will show that Gap 2 k -Res is implied by the k-QR and k-SJS assumptions.

For this proof, it is useful to introduce two intermediate assumptions: the "special" k-QR assumption and the "special" k-SJS assumption.

Definition 5 (Special Quadratic Residuosity Assumption, k-QR ). Let RSAGen be a probabilistic algorithm which, given a security parameter κ, outputs primes p and q such that p ≡ 1 (mod 2 k ), and their product N pq. The Special Quadratic Residuosity (k-QR ) assumption asserts that the function Adv k-QR D (κ), defined as the distance

Pr[D (x, N) 1 | x y 2 mod N, y R ← J N ] -Pr[D (x, N) 1 | x R ← J N \ QR N ]
is negligible for any probabilistic polynomial-time distinguisher D; the probabilities are taken over the experiment of running (N, p, q) ← RSAGen(1 κ ) and choosing at random y ∈ J N and x ∈ J N \ QR N .

Definition 6 (Special Squared Jacobi Symbol Assumption, k-SJS ). Let RSAGen be a probabilistic algorithm which, given a security parameter κ, outputs primes p and q such that p ≡ 1 (mod 2 k ), and their product N pq. The Special Squared Jacobi Symbol (k-SJS ) assumption asserts that the function Adv k-SJS D (κ), defined as the distance

Pr[D (y 2 mod N, N) 1 | y R ← J N \ QR N ] -Pr[D (y 2 mod N, N) 1 | y R ← J N ]
is negligible for any probabilistic polynomial-time distinguisher D; the probabilities are taken over the experiment of running (N, p, q) ← RSAGen(1 κ ) and choosing at random y ∈ J N \ QR N and y ∈ J N .

Lemma 1. Using the previous notation, we have k-QR + k-SJS ⇒ k-QR + k-SJS . More precisely, for any probabilistic polynomial-time distinguisher A against k-QR or k-SJS , A is also a distinguisher against k-QR or k-SJS and there exists a distinguisher B against k-QR with comparable running time, such that

Adv k-QR A (κ) ≤ Adv k-QR A (κ) + 1 2 Adv k-SJS A (κ) , Adv k-SJS A (κ) ≤ Adv k-SJS A (κ) + 1 2 Adv k-QR B (κ) .
Proof. Consider a probabilistic polynomial-time algorithm A taking as input N and x ∈ J N . For

x R ← J N , we let                1 Pr[A(x, N) 1 | x ∈ J N \ QR N ] 2 Pr[A(x, N) 1 | x y 2 ∈ QR N ∧ y ∈ J N \ QR N ] 2 Pr[A(x, N) 1 | x y 2 ∈ QR N ∧ y ∈ QR N ] 3 Pr[A(x, N) 1 | x y 2 ∈ QR N ∧ y ∈ J N ]
.

Against k-QR, k-SJS, k-QR , and k-SJS , its advantage is denoted

α 1 1 -1 respectively.
We have to show that if the k-QR and k-SJS assumptions hold then so do the k-QR and k-SJS assumptions. The k-QR and k-SJS assumptions imply that α 1 and α 2 are negligible. We also note that any significant difference between 2 and 2 would lead to a distinguisher against k-QR. We thus have | 2 -2 | ≤ Adv k-QR B (κ), with B an algorithm with running time comparable to that of A.

From the definitions of α 3 and α 4 , we can write

α 3 1 -1 2 ( 2 + 2 ) 1 -1 4 ( 2 + 2 ) -1 2 3 + 1 2 3 -1 4 ( 2 + 2 ) ≤ 1 -1 4 ( 2 + 2 ) -1 2 3 + 1 2 3 -1 4 ( 2 + 2 ) α 1 + 1 2 Adv k-QR B (κ)
and

α 4 2 -3 1 2 2 + 1 2 2 -3 + 1 2 2 -1 2 2 ≤ 1 2 ( 2 + 2 ) -3 + 1 2 ( 2 -2 ) ≤ α 2 + 1 2 α 1 .
The previous inequalities show that when α 1 and α 2 are negligible then so are α 3 and α 4 .

Theorem 3 (k-QR + k-SJS ⇒ Gap 2 k -Res).
For RSA moduli N pq with p ≡ 1 (mod 2 k ), the Gap 2 k -Res assumption holds if the k-QR assumption and the k-SJS assumption hold. More precisely, for any probabilistic polynomial-time distinguisher B against the former, there exist a k-QR distinguisher D 1 and a k-SJS distinguisher D 2 with comparable running times and for which

Adv Gap 2 k -Res B (κ) ≤ 3 2 (k -1 3 ) • Adv k-QR D 1 (κ) + (k -1) • Adv k-SJS D 2 (κ) .
Proof. To prove the result, we consider a sequence of distributions which will help us bridge the gap between the assumptions. More precisely, for 0 ≤ i ≤ k -1, we consider the subsets D i of J N

given by

D i y 2 i mod N | y ∈ J N \ QR N .
We also need other subsets which can be seen as the complement of D i in the set of 2 i -th residues that are not 2 i+1 -th residues:

D i y 2 i mod N | y ∈ J N .
Finally we define the subgroup of 2 k -th residues,

R k { y 2 k mod N | y ∈ Z * N }.
If we consider the sets V 0 and V 1 (presented in Definition 4), we have V 0 D 0 and V 1 R k . The proof will actually proceed by showing the computational indistinguishability of the (uniform) distributions induced by the corresponding subsets. Namely, unless either the k-QR assumption or the k-SJS assumption is false, we will prove

D 0 c ≈ D 1 c ≈ D 1 c ≈ D 2 c ≈ D 2 c ≈ • • • c ≈ D k-1 c ≈ D k-1 ,
where the c ≈ denotes computationally indistinguishable distributions. Finally, we also prove that D k-1 c ≈ R k unless the k-QR assumption is false.

Remark 1. Note that we abuse notation by using D i , D i , R k both for subsets and for the uniform distributions over them. Also, it is important to see that:

-if y ∈ R J N \ QR N then y 2 i ∈ R D i ; -if y ∈ R J N then y 2 i ∈ R D i ; -if y ∈ R Z * N then y 2 k ∈ R R k . C
1. If k-QR holds, for each i ∈ {1, . . . , k -1}, no probabilistic polynomial-time adversary can distinguish the distributions of D i-1 and D i .

Proof (of Claim 1). Let D be a distinguisher that can tell apart D i-1 and D i with non-negligible advantage ε. We show that D implies a k-QR distinguisher B 1,i with advantage ε for RSA moduli N pq with p ≡ 1 (mod 2 k ). Our distinguisher B 1,i takes as input an RSA modulus N pq with p ≡ 1 (mod 2 k ) and an element w ∈ Z * N which is drawn from one of the two distributions

dist 0 { y 2 mod N | y R ← J N } , dist 1 { y | y R ← J N \ QR N } .
Its task is to decide if w is in dist 0 or in dist 1 . To this end, B 1,i chooses a random element z R ← J N . It then defines x z 2 i w 2 i-1 mod N and feeds D with (x, i, N). When the distinguisher D halts, B 1,i outputs whatever D outputs.

-First assume that w y 2 ∈ dist 0 , for some y ∈ R J N . We have x (z y)

2 i mod N. Further, since z R ← J N , we have z y ∈ J N and thus x ∈ R D i . -Now assume that w ∈ R J N \ QR N . In this case, we clearly have x ∈ R D i-1 because x (z 2 w) 2 i-1 mod N and z 2 w ∈ J N \ QR N . C 2.
If k-SJS holds, for each i ∈ {1, . . . , k -1}, no probabilistic polynomial-time adversary can distinguish the distributions of D i and D i .

Proof (of Claim 2).

Let D be a distinguisher with non-negligible advantage ε between D i and D i . We show that D implies a k-SJS distinguisher B 2,i with advantage ε for RSA moduli N pq with p ≡ 1 (mod 2 k ). Given w ∈ Z * N which is drawn from one of the two distributions

dist 0 { y 2 mod N | y R ← J N \ QR N } , dist 1 { y 2 mod N | y R ← J N } ,
B 2,i constructs x w 2 i-1 mod N which is used to feed the distinguisher D. When the latter outputs a result, B 2,i produces the same output.

It is clear that, if w ∈ R dist 0 (resp. w ∈ R dist 1 ), then x ∈ R D i (resp. x ∈ R D i ). Hence, if D is a successful distinguisher, so is B 2,i . C 3. If k-QR holds, no probabilistic polynomial-time adversary can distinguish the distributions of D k-1 and R k .
Proof (of Claim 3). Let D be an algorithm that can distinguish D k-1 and R k with non-negligible advantage. We build a k-QR distinguisher B 3 out of D with the same advantage.

Algorithm B 3 takes as input N pq with p ≡ 1 (mod 2 k ) as well as an element w ∈ J N with the goal of deciding whether w ∈ QR N or w ∈ J N \ QR N . To do this, B 3 simply defines x w 2 k-1 mod N and feeds D with (x, k, N). When D halts and outputs b ∈ {0, 1}, B 3 outputs the same bit.

It is easy to see that, if w ∈ R QR N then w y 2 mod N for a random y ∈ R Z * N , and so

x (y 2 k mod N) ∈ R R k -see Remark 1. If w ∈ R J N \ QR N , we immediately have x ∈ R D k-1 .
To conclude the proof of the theorem, we remark that, if a probabilistic polynomial-time distinguisher B exists for the Gap 2 k -Res assumption (i.e., if

D 0 c ≈ R k ), then -either D k-1 c ≈ R k , contradicting k-QR (Claim 3); or -there exists 1 ≤ i ≤ k -1 such that D i c ≈ D i-1 or D i c ≈ D i .
The above arguments show that either situation would contradict the k-QR assumption (Claim 1) or the k-SJS assumption (Claim 2) -or by Lemma 1, the k-QR assumption or the k-SJS assumption.

More precisely, to get the bound given in Theorem 3, we consider B 2,i the adversary "B" defined in Lemma 1 when "A B 2,i ", and we define the distinguisher D 1 (resp. D 2 ) as follows: it picks

(α, i) R ← P 1 (resp. (α, i) R ← P 2 )
, where P 1 and P 2 are probability distributions defined as:

Pr (X,Y) R ←P 1 [(X, Y) (α, i)]          2 3k-1 if α 1 and i ∈ {1, . . . , k -1} 1 3k-1 if α 2 and i ∈ {1, . . . , k -1} 2 3k-1 if α 3 and Pr (X,Y) R ←P 2 [(X, Y) (α, i)]      1 3k-3 if α 1 and i ∈ {1, . . . , k -1} 2 3k-3 if α 2 and i ∈ {1, . . . , k -1} .
Then D 1 runs B 1,i when α 1, B 2,i when α 2, and B 3 when α 3, and outputs what this latter adversary outputs. Similarly, D 2 runs B α,i , and outputs what this latter adversary outputs.

Using Lemma 1, we have:

Adv Gap 2 k -Res B (κ) ≤ k-1 i 1 Adv k-QR B 1,i (κ) + k-1 i 1 Adv k-SJS B 2,i (κ) + Adv k-QR B 3 (κ) ≤ k-1 i 1 Adv k-QR B 1,i (κ) + 1 2 k-1 i 1 Adv k-QR B 2,i (κ) + Adv k-QR B 3 (κ) + 1 2 k-1 i 1 Adv k-SJS B 1,i (κ) + k-1 i 1 Adv k-SJS B 2,i (κ) 3k -1 2 Adv k-QR D 1 (κ) + 3k -3 2 Adv k-SJS D 2 (κ) .
In addition, we note that D 1 and D 2 have comparable running times to B.

We remark that the assumption p ≡ 1 (mod 2 k ) is never directly used in the proof. The assumption p ≡ 1 (mod 2 k ) is just needed for the correctness of our encryption scheme. The security proof actually holds for any kind of modulus N for which the QR and the SJS assumptions hold -the k-QR and the k-SJS assumptions are just the QR and the SJS assumptions for moduli N pq such that p ≡ 1 (mod 2 k ).

Semantic security

It is not hard to see that the semantic security of the scheme is equivalent to the Gap 2 k -Res assumption. From Theorem 3, we thus obtain the result announced in Theorem 1. Namely, for any IND-CPA adversary A, there exist a k-QR distinguisher D 1 and a k-SJS distinguisher D 2 such that

Adv ind-cpa A (κ) ≤ 3 2 (k -1 3 ) • Adv k-QR D 1 (κ) + (k -1) • Adv k-SJS D 2 (κ) .
Proof (of Theorem 1). The proof proceeds by simply changing the distribution of the public key.

Under the Gap 2 k -Res assumption, instead of picking y uniformly in J N \ QR N , we can choose it in the subgroup of 2 k -th residues without the adversary noticing. However, in this case, the ciphertext carries no information about the message and the IND-CPA security follows.

Interestingly, the security proof implicitly shows that, like the original Goldwasser-Micali system, our scheme is a lossy encryption scheme [BHY09] (i.e., it admits an alternative distribution of public keys for which encryptions statistically hide the plaintext), which provides security guarantees against selective-opening attacks [DNRS03]. Moreover, for a lossy key (y, N), there exists an efficient algorithm that opens a given ciphertext c to any arbitrary plaintext m (by using the factorization of N to find random coins that explain c as an encryption of m). It implies that our scheme satisfies the simulation-based definition [BHY09] of selective-opening security.

Implementation and Performance

We tackle here some implementation aspects. We explain how to select the parameters involved in the system set-up and key generation. We present fast decryption algorithms. Finally, we discuss the ciphertext expansion and give a comparison with previous schemes.

Parameter selection

The key generation (cf. Section 3.1) requires a prime p such that p ≡ 1 (mod 2 k ) for some k ≥ 1 and a random element y ∈ J N \ QR N , where N pq. The condition y ∈ J N \ QR N is equivalent to y p y q -1. Since a random nonzero element modulo p has a probability of exactly 1 2 of being a quadratic non-residue modulo p (and similarly modulo q), a suitable y is likely to be obtained after just a few trials. Efficient algorithms for generating a prime p lying in a prescribed interval [p min , p max ] can be found in [JPV00, JP06]. They can be adapted to accommodate the extra condition p ≡ 1 (mod 2 k ) without increasing the time complexity, as a random number congruent to 1 modulo 2 k in [p min , p max ] is prime with approximatively the same probability than a random odd number in [p min , p max ], thanks to Dirichlet's theorem. We describe such a variant below.

The goal is to produce a prime p 1 + 2 k r for some r ∈ [r min , r max ], where r min (p min -1)/2 k and r max

(p max -1)/2 k . Let Π 3 • 5 • 7 • • • ≤ r max -r min + 1 denote a product of small odd
primes. The algorithm will construct candidate primes that are automatically co-prime to Π. The first step is to generate a random unit υ ∈ Z * Π (for example using the efficient algorithm presented in [JP06, § 2.2]). Define ϑ 0 -1 2 k + r min mod Π. A candidate p is then formed as

p ← 1 + 2 k (r min + ϑ) for some ϑ ∈ R [0, r max -r min ] such that ϑ ≡ ϑ 0 + υ (mod Π)
and tested for primality. If candidate p is not prime, υ is updated as υ ← 2υ mod Π and the process is re-iterated. Since Π is odd, 2 ∈ Z * Π and thus υ remains in Z * Π after the updating step. Moreover,

reducing candidate p modulo Π, we get p ≡ 1 + 2 k (r min + ϑ) ≡ 1 + 2 k (r min + ϑ 0 + υ) ≡ 2 k υ (mod Π) and thus p ∈ Z * Π since υ ∈ Z * Π and 2 k ∈ Z * Π . Equivalently, p ∈ Z *
Π means that candidate p is such that gcd(p, p i ) 1 for all primes p i dividing Π (and p is also odd by construction).

A powerful LLL-based technique due to Coppersmith bounds the size of k to at most 1 2 log 2 p bits as, otherwise, the factors of N would be revealed [Cop97, Theorem 5]. Going beyond polynomial-time attacks, one should add an extra security margin to take into account exhaustive searches [Ngu09]. RSA moduli being balanced (i.e., 1 2 log 2 p 1 4 log 2 N), we so end up with the upper bound

k < 1 4 log 2 N -κ
where κ is the security parameter.

In practice, this restriction on k is not a limitation because, as described in the next section, long messages can be encrypted using the KEM/DEM paradigm. For example, using ECRYPT 2 recommendations [ECR12], for κ 128 bits of security, a symmetric key of k 128 bits has to be used for the KEM/DEM paradigm, and a 3248-bit modulus N has to be used to ensure factorization is hard. These parameters do not take into account the tightness of the reduction. If we take it into account, when q ≡ 3 (mod 4), according to Theorem 2, a factor (k + 1)/2 ≈ 64 2 6 is lost in the reduction. Assuming that the best way to solve the quadratic residuosity consists in factorizing the modulus N, a 3584-bit modulus has to be used, as this corresponds to (128 + 6) bits of security for factorization, according to [ECR12]. Note that the choice of parameters k 128 and |N | 2 3584 satisfies the relation k < 1 4 log 2 N -κ.

Optimized decryption algorithms

In its most basic version, the decryption requires O(k) full modular exponentiations in Z * p in order to compute higher power residue symbols. This section shows that a suitable pre-processing phase allows increasing the decryption speed.

The RSA modulus used in the proposed cryptosystem is of the form N pq with p ≡ 1 (mod 2 k ). Hence, we can write p 2 K p + 1 for some integer K ≥ k and some odd integer p . Now, given the public key pk {N, y, k}, consider the ciphertext c y m x 2 k mod N of message m k-1 i 0 m i 2 i with m i ∈ {0, 1}. If, for 1 ≤ j ≤ k, we define Λ j 2 K-j p then c Λ j ≡ y m x 2 k Λ j ≡ y m Λ j x 2 K+k-j p ≡ y m Λ j mod 2 K p ≡ y m Λ j mod 2 j Λ j ≡ y Λ j (m mod 2 j ) ≡ y Λ j (mj-12 j-1 +(m mod 2 j-1 )) ≡ y p-1 2 m j-1 y Λ j (m mod 2 j-1 )

≡ (-1) m j-1 y Λ j (m mod 2 j-1 ) (mod p) .

So, letting C c 2 K-k p mod p and Y y 2 K-k p mod p, the previous relation becomes

C Y m mod 2 j-1 2 k-j ≡
(-1) m j-1 (mod p). Starting at j 1 and iterating until j k, it yields a decryption algorithm producing one bit of plaintext m per iteration (i.e., bit m j-1 ).

To further speed-up the decryption, observing that Y y 2 K-k p mod p is independent of the ciphertext, its value -or better its inverse-can be pre-computed. The private key now consists of the pair (p, D) where D y -2 K-k p mod p. As one bit of plaintext m is correctly obtained per iteration, there is no need to fully recompute D m mod 2 j-1 mod p at iteration j. Rather, it can be obtained more efficiently from the value of the previous iteration as

D m mod 2 j-1 mod p      D m mod 2 j-2 mod p if m j-1 0 D m mod 2 j-2 D 2 j-1 mod p if m j-1 1 .
We thus obtain:

Algorithm 1 Decryption algorithm

Input: Ciphertext c, private key (p, D) with D y -(p-1)/2 k mod p, and public-key element k

Output: Plaintext m (m k-1 , . . . , m 0 ) 2 1: m ← 0; B ← 1; D ← D 2: C ← c (p-1)/2 k mod p 3: for j 1 to k -1 do 4: z ← C 2 k-j mod p 5: if (z 1) then m ← m + B; C ← C • D mod p 6: B ← 2B; D ← D 2 mod p 7: end for 8: if (C 1) then m ← m + B 9: return m
Variable m in the for-loop contains the lowest part of the plaintext m and variable B contains the successive powers of 2. Further, the for-loop is only performed until iteration k -1 to save a couple of operations. As a variant, we remark that D can be initialized to y -(p-1)/2 k mod p (Line 1 in Alg. 1) instead of being explicitly included in the private key.

As described, the for-loop in Alg. 1 on average involves k-1

j 1 (k -j) (k-1)k 2 modular squarings
for the successive evaluation of z, k-1 2 modular multiplications for the evaluation of C, and (k -1) modular squarings for updating D.

Remark 2. The decryption can even be made slightly faster. The condition z 1 is equivalent to z ≡ -1 (mod p). Instead of iteratively evaluating z ← C 2 k-j mod p for 1 ≤ j ≤ k -1, we can set z to C and successively square it, z ← z 2 mod p, until it becomes congruent to -1 (mod p). We then update C by multiplying it by the corresponding power of D and redo the process until C becomes equal to 1. On average, this halves the number of squarings for the successive evaluations of z. Furthermore, the modular squarings for updating D can be saved by pre-computing the different powers of D. This saves (k -1) modular squarings. The total number of operations in the for-loop then boils down to (k-1)k 4 squarings plus k-1 2 multiplications (on average), modulo p.

Ciphertext expansion

Hybrid encryption allows designing efficient asymmetric schemes, as suggested by Shoup in the ISO 18033-2 standard for public-key encryption [ISO06]. An asymmetric cryptosystem is used to encrypt a secret key that is then used to encrypt the actual message. This is the so-called KEM/DEM paradigm.

The next table compares the ciphertext expansion in the encryption of k-bit messages for different generalized Goldwasser-Micali cryptosystems. Only cryptosystems with a formal security analysis are considered. Further, the value of k is assumed to be relatively small (e.g., 128 or 256) as the "message" being encrypted is typically a symmetric key (for example a 128-or 256-bit AES key) in a KEM/DEM construction.

It appears that the Goldwasser-Micali cryptosystem has the highest ciphertext expansion but its semantic security relies on the standard quadratic residuosity assumption (i.e., RSA moduli

Goldwasser-Micali [GM84] Quadratic residuosity (QR) k • log 2 N Benaloh-Fisher [CF85]
Prime residuosity (PR)

k log 2 r • log 2 N Naccache-Stern [NS98] Prime residuosity (PR) log 2 N Okamoto-Uchiyama [OU98] p-subgroup log 2 N Paillier [Pai99]
N-th residuosity 2 log 2 N

This paper when q ≡ 1 (mod 4)

Quadratic residuosity (k-QR) + Squared Jacobi symbol (k-SJS) log 2 N
This paper when q ≡ 3 (mod 4)

Quadratic residuosity (k-QR) log 2 N N pq involves form-free primes). The ciphertext expansion of the Benaloh-Fischer cryptosystem is similar to that of the Naccache-Stern cryptosystem for small messages; i.e., when k ≤ log 2 r. For larger messages, the Naccache-Stern cryptosystem should be preferred. It also offers the further advantage of providing a faster decryption procedure. The same is true for the Okamoto-Uchiyama cryptosystem and the Paillier cryptosystem. These two latter cryptosystems are particularly suited to encrypt very large messages (i.e., up to 1 2 log 2 N bits for the Okamoto-Uchiyama cryptosystem and up to log 2 N bits for the Paillier cryptosystem).

The encryption scheme proposed in this paper has the same ciphertext expansion as in the Naccache-Stern cryptosystem. Moreover, its decryption algorithm is fast (no searches are needed), requires less memory, and the security relies on a quadratic residuosity assumption (i.e., k-QR) when q ≡ 3 (mod 4). When q ≡ 1 (mod 4), it additionally requires the k-SJS assumption.

More Efficient Lossy Trapdoor Functions from the k-Quadratic Residuosity Assumption

In this section, we show that our homomorphic cryptosystem allows constructing a lossy trapdoor function based on the k-QR, k-SJS and DDH assumptions (or on the k-QR and DDH assumptions) with much shorter outputs and keys than in previous QR-based or DDH-based examples.

In comparison with the function of Hemenway and Ostrovsky [HO12], for example, its output is k times smaller when working with a modulus N pq with p ≡ 1 (mod 2 k ). Moreover, the size of the evaluation key is decreased by a factor of O(k 2 ) while increasing the lossiness by more than k bits. Finally, our inversion trapdoor has constant size, whereas [HO12] uses a trapdoor of size O(n) to recover n-bit inputs. Our function also compares favorably with the QR-based function of Freeman et al. [FGK + 10, FGK + 13], which only loses a single bit.

In fact, by appropriately tuning our construction, we obtain the first lossy trapdoor function with short outputs, description and trapdoor that loses many input bits and relies on another assumption than Paillier's. Among known lossy trapdoor functions based on traditional number-theoretic assumptions [PW08, BFO08, FGK + 10, FGK + 13, KOS10, HO12, MY10], this appears as a rare efficiency tradeoff. To the best of our knowledge, it has only been achieved under the Composite Residuosity assumption [BFO08, FGK + 10, FGK + 13] so far.

Interestingly, our LTDF provides similar efficiency improvements to the QR-based deterministic encryption scheme of Brakerski and Segev [BS11], which also builds on the Hemenway-Ostrovsky LTDF. Note that the scheme of [BS11] is important in the deterministic encryption literature since it is one of the only known schemes providing security in the auxiliary input setting in the standard model.

Description and security analysis

We start by recalling the following definition.

Definition 7 ([PW08]

). Let κ ∈ N be a security parameter and n : N → N, : N → R be non-negative functions of κ. A collection of (n, )-lossy trapdoor functions (LTDF) is a tuple of efficient algorithms (InjGen, LossyGen, Eval, Invert) with the following specifications.

-Sampling an injective function: Given a security parameter κ, the randomized algorithm InjGen(1 κ ) outputs the index ek of an injective function of the family and an inversion trapdoor t.

-Sampling a lossy function: Given a security parameter κ, the probabilistic algorithm LossyGen(1 κ ) outputs the index ek of a lossy function.

-Evaluation: Given the index of a function ek -produced by either InjGen or LossyGenand an input

x ∈ {0, 1} n , the evaluation algorithm Eval outputs F ek (x) such that:

• If ek is an output of InjGen, then F ek (•) is an injective function.

• If ek was produced by LossyGen, then F ek (•) has image size 2 n-. In this case, the value nis called residual leakage.

-Inversion: For any pair (ek, t) produced by InjGen and any input x ∈ {0, 1} n , the inversion algorithm

Invert returns F -1 ek (t, F ek (x)) x.
-Security: The two ensembles {ek | (ek, t) ← InjGen(1 κ )} κ∈N and {ek | ek ← LossyGen(1 κ )} κ∈N are computationally indistinguishable.

Our construction goes as follows.

S

. Given a security parameter κ, let N N (κ) and k k(κ) be parameters determined by κ. Let also n n(κ) be the desired input length. Algorithm InjGen defines m n/k (we assume that k divides n for simplicity) and conducts the following steps.

1. Generate an N -bit RSA modulus N pq such that p 2 K p + 1 and q 2 L q + 1, for odd prime integers p, q, p , q and with K k and L ∈ {1, . . . , k}. Choose y R ← J N \ QR N at random.

For each

i ∈ {1, . . . , m}, pick h i in the subgroup of 2 k -residues, R k {w 2 k mod N | w ∈ Z *
N } (of order p q ), by setting h i g i 2 k mod N for a randomly chosen g i R ← Z * N . 3. Choose r 1 , . . . , r m R ← Z p q and compute a matrix Z Z i, j i, j∈{1,...,m} given by

Z y z 1,1 • h 1 r 1 mod N . . . . . . y z 1,m • h m r 1 mod N . . . . . . y z m,1 • h 1 r m mod N . . . . . . y z m,m • h m r m mod N
, where (z i, j ) i, j∈{1,...,m} denotes the identity matrix.

The evaluation key is ek N, (Z i, j ) i, j∈{1,...,m} and the trapdoor is t {p, y}.

S

. The process followed by LossyGen is identical to the above one but the matrix (z i, j ) i, j∈{1,...,m} is replaced by the all-zeroes m × m matrix.

E

. Given ek N, (Z i, j ) i, j∈{1,...,m} , algorithm Eval parses the input x ∈ {0, 1} n as a vector of k-bit blocks x (x 1 , . . . , x m ), with x i ∈ Z 2 k for each i. Then, it computes and returns ỹ (y 1 , . . . , y m ), with y j ∈ Z * N , where

ỹ m i 1 Z i,1 x i mod N, . . . , m i 1 Z i,m x i mod N y m i 1 z i,1 x i • h 1 m i 1 r i x i mod N, . . . , y m i 1 z i,m x i • h m m i 1 r i x i mod N .

I

. Given t {p, y} and ỹ (y 1 , . . . , y m ) ∈ Z m N , Invert applies the decryption algorithm of Section 3.2 to each y j , for j 1 to m. Observe that when (z i, j ) i, j∈{1,...,m} is the identity matrix,

y j p 2 k y p 2 k
x j mods p. From the resulting vector of plaintexts x

(x 1 , . . . , x m ) ∈ Z 2 k m , it recovers the input x ∈ {0, 1} n .
The Hemenway-Ostrovsky construction of [HO12] is slightly different in that, as in the DDHbased construction of Peikert and Waters [PW08], the evaluation key includes a vector of the form G (g r 1 , . . . , g r m ) T , where g ∈ QR N , and the trapdoor is t (log g (h 1 ), . . . , log g (h m )). In their scheme, the evaluation algorithm additionally computes m i 1 (g r i ) x i while the inversion algorithm does not use the factorization of N but rather performs a coordinate-wise ElGamal decryption. Here, explicitly using the factorization of N in the inversion algorithm makes it possible to process k-bit blocks at once. In addition, it allows for a very short inversion trapdoor: the inversion algorithm only needs y and the factorization of N.

We first recall the DDH assumption before giving the security theorem for our new construction.

Definition 8 (Decision Diffie-Hellman, DDH). Given a security parameter κ, let G g be a (multiplicatively written) group of order n. The Decision Diffie-Hellman (DDH) assumption for G asserts that the function Adv DDH D (κ), defined as the distance

Pr[D (g, g a , g b , g ab ) 1 | a, b R ← Z n ] -Pr[D (g, g a , g b , g c ) 1 | a, b, c R ← Z n ]
is negligible for any probabilistic polynomial-time distinguisher D; the probabilities are taken over the experiment of selecting at random a generator g of G and choosing at random a ∈ Z n , b ∈ Z n and c ∈ Z n .

Theorem 4. Let (κ) n(κ)log 2 (p q ). The above construction is a (n(κ), (κ)-LTDF if the Gap 2 k -Res assumption holds and if the DDH assumption holds in the subgroup R k of 2 k -th residues.

We recall that N pq, with p 2 K p + 1 and q 2 L q + 1. Therefore, we have:

n(κ) -log 2 (N/2 K+L ) < (κ) < n(κ) -log 2 (N/2 K+L ) + 1 .
Proof (of Theorem 4). We first prove that lossy functions are indistinguishable from injective functions. To this end, we consider a sequence of hybrid experiments. We first define an experiment Exp 0 which is an experiment where the key generation algorithm outputs the description of an injective function with the difference that y is chosen as a 2 k -th residue instead of being drawn as y R ← J N \QR N . Clearly, under the Gap 2 k -Res assumption, Exp 0 is computationally indistinguishable from an experiment where the adversary is given the description of an injective function. Note that although p q is used to generate the values r j , using the approximate value N/2 K+L instead of p q is statistically indistinguishable. Thus knowing the factorization of N is not necessary in these experiments, and the Gap 2 k -Res assumption can be applied.

Next, for each i ∈ {1, . . . , m} we define experiment Exp i as an experiment where y ∈ R R k and the key generation algorithm outputs a matrix (Z i, j ) i, j which encrypts a hybrid matrix (z i, j ) i, j

whose first i columns all contain zeroes whereas the last mi columns are those of the m × m identity matrix.

C

. If the DDH assumption holds in the subgroup R k of 2 k -th residues, for each i ∈ {1, . . . , m}, experiment Exp i is computationally indistinguishable from Experiment Exp i -1 .

Proof. The claim is proved in the same way as a similar claim about the DDH-based LTDF of Peikert and Waters [PW08]. Since y lives in the cyclic subgroup R k of 2 k -th residues, we are free to invoke the DDH assumption in R k . Concretely, given a DDH challenge (g, g a , g b , γ) ∈ (R k ) 4 , the goal is to distinguish if γ g ab or γ R ← R k . Let B be an adversary that can tell apart Exp i from Exp i -1 with advantage Combining this result with Theorem 3, the security of the new trapdoor function relies on the DDH assumption in the subgroup of 2 k -th residues and additionally either the combination of the k-QR and k-SJS assumptions (when L > 1) or the k-QR assumption alone (when L 1).

It is worth noting that, with N pq such that p ≡ 1 (mod 2 k ), a side effect of working in the subgroup R k (of order p q ) is an improved lossiness. Indeed, we lose nlog 2 (p q ) bits in comparison with nlog 2 φ(N) in [HO12]. Since φ(N) 2 K+L p q , this means we lose K + L more bits than by using the construction in [HO12], where K k, 1 ≤ L ≤ k.

The most interesting instantiations are:

-K L k: in which case we lose 2k more bits than [HO12] and the construction is secure under k-QR, k-SJS, and DDH in R k ; -K k and L 1: in which case we lose only k more bits than [HO12], but the k-SJS assumption is no more required.

An all-but-one trapdoor function

Using the techniques of Peikert and Waters [PW08], it is easy to construct an equally efficient all-but-one trapdoor function providing the same amount of lossiness as our lossy trapdoor function, under the same assumptions. A difference will be that, in order to enable inversion, the resulting all-but-one function will handle k/2 bits (instead of k) in each chunk.

First we recall the definition of an all-but-one trapdoor function. Let κ ∈ N be a security parameter and n : N → N, : N → R be non-negative functions of κ. A collection of (n, )-all-but-one trapdoor functions (ABO-TDF) is a tuple of efficient algorithms (BranchGen, ABOGen, Eval, Invert) with the following specifications.

-Sampling a branch: Given a security parameter κ, BranchGen is a randomized algorithm that outputs a branch b ∈ {0, 1} * of appropriate length.

-Sampling a function: ABOGen is a probabilistic algorithm that takes as input a security parameter κ and a branch b produced by BranchGen. It outputs the description ek of a function and a trapdoor t.

-Evaluation: For any branch b produced by BranchGen, any pair (ek, t) produced by ABOGen(1 κ , b ), any branch b and any input x ∈ {0, 1} n , the evaluation algorithm Eval outputs F b,ek (x) such that: Our ABO-TDF is described below. A difference with the Paillier-based construction of [FGK + 10] is that, when inverting the function, we must pay attention to the fact that the output of the function may contain encryptions of values which are not invertible modulo 2 k . In order to avoid the need to invert in Z 2 k , we perform the division over the integers. To this end, we have to adjust the parameter k so as to make sure that, for any branches b, b and any input block 1. Generate an N -bit RSA modulus N pq such that p 2 K p + 1 and q 2 L q + 1, for odd prime integers p, q, p , q , K k, and some L ∈ {1, . . . , k}. Choose y R ← J N \ QR N at random. 2. For each i ∈ {1, . . . , m}, pick h i in the subgroup R k (of order p q ), by setting h i g i

• If b b , then F b,ek (•) is an injective function; • If b b , then F b ,ek (
2 k mod N for a randomly chosen g i R ← Z * N . 3. Choose r 1 , . . . , r m R ← Z p q and compute a matrix Z Z i, j i, j∈{1,...,m} y -z 1,1 b • h 1 r 1 mod N . . . . . . y z 1,m • h m r 1 mod N . . . . . . y z m,1 • h 1 r m mod N . . . . . . y -z m,m b • h m r m mod N
, where z i, j i, j∈{1,...,m} is the identity matrix; i.e., Z i,i y -b h i r i mod N and Z i, j h j r i mod N if j i.

The evaluation key of the ABO function is ek N, (Z i, j ) i, j∈{1,...,m} , y and the trapdoor is t p.

E

. In order to evaluate the function on a branch b ∈ {0, 1} λ for the input x ∈ {0, 1} n using the evaluation key ek N, (Z i, j ) i, j∈{1,...,m} , y , algorithm Eval parses x ∈ {0, 1} n as a vector of λ-bit blocks x (x 1 , . . . , x m ), with x i ∈ Z 2 λ for each i. Then, it defines the matrix The correctness of the inversion algorithm stems from the fact that, since we have x i , b, b < 2 λ , it holds that |bb | • x i < 2 2λ 2 k for each i ∈ {1, . . . , m}, so that x i can be computed over the integers at step 3 of the inversion algorithm.

It is easy to prove that the description of the function computationally hides the underlying lossy branch if the k-QR and k-SJS assumptions hold (when L > 1) or if the k-QR assumption holds (when L 1), and if the DDH assumption holds in the subgroup R k (of order p q ). The proof is essentially identical to the proof of Theorem 4 and is omitted.

Application: Efficient CCA-secure encryption

By combining the lossy and all-but-one trapdoor function, a CCA-secure encryption scheme can be obtained using the construction of [PW08]. We argue now that m O(1) suffices for this purpose. Recall that the scheme of [PW08] combines a pairwise independent hash function H : {0, 1} n → {0, 1} τ , an (n, )-lossy function and an (n, )-all-but-one function such that + ≥ n + ν and τ ≥ ν -2 log 2 (1/ε), for some ν ∈ ω(log n) and where ε is the statistical distance in the modified Leftover Hash Lemma used in [DRS04]. If we choose ε ≈ 2 -κ and τ k in order to encrypt k-bit messages, we can set ν k + 2κ. Setting nlog 2 (p q ), the constraint + ≥ n + ν translates into n -2 log 2 (p q ) ≥ ν.

Since q 2 L q + 1 and p 2 k p + 1 in our trapdoor functions, if we set k 1 4 log 2 N -κ (cf. Section 5.1), we have log 2 (p q ) log 2 φ(N)k -L ≈ 4(k + κ)k -L 3k + 4κ -L, which yields n ≥ 4k + 6κ -L. If k > κ, it is sufficient to set n ≥ 10k. If we take into account the fact that our all-but-one function processes blocks of k/2 bits, we find that m 2n/k 20 suffices here, even for L 1. For larger values of L, an even smaller m would suffice.

As it turns out, when the Peikert-Waters construction [PW08, Section 4.3] of CCA-secure encryption is instantiated with our lossy and all-but-one trapdoor functions, it only requires a constant number of exponentiations while retaining constant-size public keys and ciphertexts.

With the exception of [HKS13] (which relies on a weaker assumption), to the best of our knowledge, it yields the only known CCA-secure QR-based cryptosystem combining the aforementioned efficiency properties. Up to now, the most efficient chosen-ciphertext-secure cryptosystem strictly based on the QR assumption was the one of Kiltz et al. [KPSY09], where O(κ) exponentiations are needed to encrypt and the public key contains O(κ) group elements. On the other hand, our construction requires more specific moduli than [KPSY09] and additionally appeals to the DDH assumption (and the k-SJS assumption, as well, if L > 1).

Conclusion

This paper introduced a new generalization of the Goldwasser-Micali cryptosystem. The so-obtained cryptosystems are shown to be secure under well-defined assumptions. Further, they enjoy a number of useful features including fast decryption, optimal ciphertext expansion, and homomorphic property. We believe that our proposal is the most natural yet efficient generalization of the Goldwasser-Micali cryptosystem. It keeps the nice attributes and properties of the original scheme while improving the overall performance.

When applied to the Peikert-Waters framework for building lossy trapdoor functions, it yields a practical construction based on quadratic-residuosity related and DDH assumptions, with companion deterministic encryption scheme and CCA-secure cryptosystem.

Definition 1 .

 1 Let p be an odd prime and let n ≥ 2 such that n | p -1. Then the symbol is called the n-th power residue symbol modulo p.It satisfies the following properties. Let a and b be two integers that are co-prime to p. Then:1. If a ≡ b (mod p)

Encrypt

  picks a random x ∈ Z * N and returns the ciphertext c y m x 2 k mod N. Decrypt(sk, c) Given c ∈ Z * N and the private key sk {p}, the algorithm first computes z c p 2 k and then finds m ∈ {0, . . . , 2 k -1} such that the relation fast decryption algorithm is detailed in Section 3.2.

-

  •) has image size 2 n-. In this case, the value nis called residual leakage. Inversion: For any b produced by BranchGen and any pair (ek, t) produced by ABOGen(1 κ , b ), any branch b b and any input x ∈ {0, 1} n , the inversion algorithm Invert returns F -1 b,ek (t, F b,ek (x)) x. -Security: For any distinct b, b ∈ {0, 1} * produced by BranchGen, the ensembles {ek | (ek, t) ← ABOGen(1 κ , b)} κ∈N and {ek | (ek, t) ← ABOGen(1 κ , b )} κ∈N are computationally indistinguishable.

  x, the product (bb ) • x will be smaller than 2 k . S . Given a security parameter κ ∈ N and a parameter λ λ(κ) determined by κ, the algorithm chooses b R ← {0, 1} λ . S . The function sampling algorithm takes as input a security parameter κ, parameters N (κ) and λ λ(κ) that are determined by κ, the desired input length n n(κ), and a branch b ∈ {0, 1} λ . It sets k 2λ and defines m n/λ (we assume that λ divides n for simplicity) and does the following.

  Z i,i mod N for each i, j ∈ {1, . . . , m}. Then, it computes and returnsỹ m i 1 (Z b i,1 ) x i mod N, . . . , m i 1 (Z b i,m ) x i mod N y (b-b )x 1 • h 1 m i 1 r i x i mod N, . . . , y (b-b )x m • h m m i 1 r i x i mod N .I . Given a description ek N, (Z i, j ) i, j∈{1,...,m} , y of the function, the trapdoor t p and the output ỹ (y 1 , . . . , y m ) ∈ Z m N , the function can be inverted for the branch b b by proceeding as follows. 1. Define the vector (w 1 , . . . , w m ) ∈ Z m N as (w 1 , . . . , w m ) (y 1 , . . . , y m ) if b > b (when the bitstrings b and b are interpreted as natural integers) and (w 1 , . . . , w m ) (y 1 -1 mod N, . . . , y m -1 mod N) if b < b . 2. For i 1 to m, apply the decryption algorithm of Section 3.2 to w i . 3. From the vector of plaintexts x (x 1 , . . . , x m ) ∈ Z m 2 λ obtained at Step 2, define x (x 1 , . . . , x m ) ∈ Z m 2 λ such that x i x i /|b -b | (the division being performed over Z), where |bb | bb if b > b and bb otherwise. 4. From x(x 1 , . . . , x m ), recover the original input x ∈ {0, 1} n by concatenating the binary representations the coordinates of x .

Table 1 .

 1 Ciphertext expansion in a typical encryption

	Encryption scheme	Assumption	Ciphertext size

This notion refers to an attack scenario where the adversary is given t encryptions of possibly correlated messages, opens t/2 out of these (and thereby obtains the messages and encryption coins) before attempting to harm the security of the remaining ciphertexts.

( 2 + 2 ) -1 2 3 , α 2 1 2 ( 2 + 2 ) -3 , α 3 1 -1 2 ( 2 + 2 ) , α 4 2 -3 ,

Acknowledgments

The authors are thankful to an anonymous referee for useful comments. The third author is also thankful to Antoine Joux for comments on an earlier version of this work.

The work of the second author is partially supported by project MTM 2013-41426-R of Spanish Ministry MINECO.

Adv

Exp(i ,i -1) B (κ) : Pr B y, (Z i, j ) i, j

1 | (y, (Z i, j ) i, j )

Our distinguisher D is defined as follows. The public key is generated by setting h i g a and h j g α j , with α j R ← Z p q for each j i . The evaluation key is generated by setting the entry (i , i ) of the matrix as Z i ,i y β γ for a random bit β R ← {0, 1}, while the rest of the i -th row is obtained by setting Z i , j (g b ) α j . The rest of rows of matrix (Z i, j ) i, j , different from the i -th one, are generated by choosing the exponents faithfully; namely for each i i : Z i, j h j r i for each j i, Z j, j h j r j for each j < i and Z j, j y • h j r j for each j > i , with r j R ← Z p q for each j i . Element y ∈ R k and matrix (Z i, j ) i, j are given to B, which returns its guess β on the running experiment. Distinguisher D outputs 1 if β β and 0 otherwise. Suppose first that γ g ab . Then it is clear that the evaluation key given to B is distributed as in Experiment Exp i when β 0 and as in Experiment Exp i -1 when β 1. Hence,

(κ), which should be negligible under the DDH assumption.

The proof now follows by remarking that, in lossy functions, the output is entirely determined by m i 1 r i x i mod p q , so that the image size is smaller than p q . The residual leakage is thus at most log 2 (p q ) bits.

A Proof of Theorem 2

As in the proof of Theorem 3, for 0 ≤ i ≤ k -1, we consider the subsets D i of J N given by

We start with a lemma that is useful to tighten the bound of Theorem 3 in the case q ≡ 3 (mod 4).

Lemma 2. Let N pq be the product of two large primes p and q where p ≡ 1 (mod 2 k ) for some k ≥ 1 and q ≡ 3 (mod 4). Then, for any w ∈ QR N , letting W

Proof. We assume that w is uniform over QR N . The case i k (which includes the case k 1) yields W w 2 k-1 with w ∈ QR N . It is then readily verified that W is uniform over R k with probability 1.

We henceforth suppose i ≤ k -1 and k ≥ 2. In particular, this implies p ≡ 1 (mod 4) and thus

-1 p 1. Denoting by ( ŵp , ŵq ) the CRT representation of a square root ŵ of w (i.e., ŵp ŵ mod p and ŵq w mod q), the four square roots of w modulo N are given by (± ŵp , ± ŵq ). Since -1 q -1, we can assume w.l.o.g. that ŵq q ŵp p , or equivalently that ŵ ∈ J N . If ŵ ∈ QR N the process can be re-iterated, and so on. More generally, we define t as the largest integer in {1, . . . , k -i} such that w ŵ2 t for some ŵ ∈ J N . We can so write W ŵ2 t+i-1 for some ŵ ∈ J N . It is worth noting that since t is the largest integer in the set {1, . . . , k -i} we can only have ŵ ∈ QR N when

Theorem 5. For RSA moduli N pq with p ≡ 1 (mod 2 k ) and q ≡ 3 (mod 4), the Gap 2 k -Residuosity Gap 2 k -Res assumption holds if the k-QR assumption holds. More precisely, for any probabilistic polynomial-time distinguisher B against the latter, there exists a k-QR distinguisher D with comparable running time and for which

Proof. Let B be an adversary against Gap 2 k -Res. We write:

The advantage of B against Gap 2 k -Res is given by Adv

We first construct k distinguishers B 1 , . . . , B k against k-QR as follows. B i takes as input an RSA modulus N pq, with p ≡ 1 (mod 2 k ) and q ≡ 3 (mod 4), and an element w ∈ J N . Its task is to decide whether w is uniform over J N \ QR N or uniform over QR N . To this end, B i chooses -If w is uniform over J N \ QR N , we clearly have that x is uniform over D i-1 . Therefore, in that case, B i outputs 1 with probability i-1 .

-If w is uniform over QR N , B outputs 1 with probability k j i 1 2 j-i+1 j + 1 2 k-i k , according to Lemma 2. Therefore, the (signed) advantage of B i in solving k-QR is

with β j 1 2 j for j ∈ {1, . . . , k -1} and β k 1 2 k-1 . Consider the following probability distribution P over {1, . . . , k}:

We now define an adversary D against k-QR as follows: D chooses a random element i R ← P and feeds B i with its k-QR challenge. The advantage of D is equal to

For j ∈ {1, . . . , k -1}, we have β j 1 2 j and thus

Likewise, since β k 1 2 k-1 , we have

Therefore, we get that the advantage of D satisfies Adv k-QR D (κ)

This concludes the proof by further noting that the running time of D is comparable to that of B.

Theorem 2 is now an application of Theorem 5, in a way similar to what was done in Section 4.3 for the general case.