Guilhem Castagnos
email: guilhem.castagnos@math.u-bordeaux.fr

Fabien Laguillaumie
email: fabien.laguillaumie@ens-lyon.fr

Linearly Homomorphic Encryption from DDH

Keywords: Linearly Homomorphic Encryption, Orders of Quadratic Fields, Diffie-Hellman Assumptions

We design a linearly homomorphic encryption scheme whose security relies on the hardness of the decisional Diffie-Hellman problem. Our approach requires some special features of the underlying group. In particular, its order is unknown and it contains a subgroup in which the discrete logarithm problem is tractable. Therefore, our instantiation holds in the class group of a non maximal order of an imaginary quadratic field. Its algebraic structure makes it possible to obtain such a linearly homomorphic scheme whose message space is the whole set of integers modulo a prime p and which supports an unbounded number of additions modulo p from the ciphertexts. A notable difference with previous works is that, for the first time, the security does not depend on the hardness of the factorization of integers. As a consequence, under some conditions, the prime p can be scaled to fit the application needs.

Introduction

Encryption protocols insure confidentiality during information transmission. They are the heart of any communication architecture. Their security has been formally defined for long, and many efficient encryption schemes fulfill the strongest security requirement, namely the indistinguishability of ciphertexts under an adaptive chosen message attack. Roughly speaking, it means that an attacker will learn not even a single bit of a message, given its encryption, even if he has access to a decryption oracle.

Paradoxically, a widely deployed kind of encryption scheme has an "algebraic" property which precludes it to reach this highest level of security. It is called homomorphic, because an operation on the ciphertexts translates into an operation on the underlying plaintexts. It is well-known that such protocols cannot reach the highest level of security, even though, this homomorphic property is actually very important for many applications, like e-voting for instance. Indeed, an additively homomorphic encryption makes it possible to obtain an encryption of the sum of all the ballots (which consists in 0 or 1 in the case of a 2-choice referendum for instance) from their encryption, so that a single decryption will reveal the result of the election, saving a lot of computational resources which would have been necessary to decrypt all the ciphertexts one by one. Linearly homomorphic encryption schemes have attracted a lot of attention because of their potential applications. A tremendous breakthrough related to homomorphic encryption was Gentry's theoretical construction of a fully homomorphic encryption scheme [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF], which actually allows to evaluate any function on messages given their ciphertexts.

Currently, no linearly homomorphic encryption scheme is secure under a discrete logarithm related assumption. This theoretical question has been open for thirty years. In this paper, we provide the first construction of such a scheme. Related Work. The story of homomorphic encryption begins with the first probabilistic encryption scheme, which was also homomorphic, by Goldwasser and Micali from [START_REF] Goldwasser | Probabilistic Encryption[END_REF], improved by Benaloh in his thesis [START_REF] Benaloh | Verifiable Secret-Ballot Elections[END_REF], then by Naccache and Stern in [START_REF] Naccache | A New Public Key Cryptosystem Based on Higher Residues[END_REF] and Okamoto and Uchiyama [START_REF] Okamoto | A New Public-Key Cryptosystem as Secure as Factoring[END_REF]. One of the most achieved system was actually designed by Paillier [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF]. Its semantic security relies on the decisional composite residuosity assumption. Paillier's scheme has then been generalized by Damgård and Jurik [START_REF] Damgård | A Generalisation, a Simplification and some Applications of Paillier's Probabilistic Public-Key System[END_REF], allowing to encrypt larger messages. This family of practical linearly homomorphic schemes is still growing with the recent work of Joye and Libert [START_REF] Joye | Efficient Cryptosystems from 2 k -th Power Residue Symbols[END_REF]. The security of these schemes is based on the problem of factoring RSA integers (including the elliptic curve variant of Paillier [START_REF] Galbraith | Elliptic Curve Paillier Schemes[END_REF]).

To design a linearly homomorphic encryption based on the Discrete Logarithm problem (DL), a folklore solution consists in encoding the message in the exponent of an Elgamal encryption, i.e., in encrypting m as (g r , h r g m ) where g is a generator of a cyclic group G = g and h = g x is the public key. Unfortunately, to decrypt, one has to recover m from g m and as the DL problem in G must be intractable, m has to be small enough to ensure a fast decryption. As a result, only a logarithmic number of additions is possible. There have been some attempts to reach a fully additive homomorphy based on the DL problem, with a variant of Elgamal modulo p 2 ( [START_REF] Chevallier-Mames | Encoding-free Elgamal Encryption without Random Oracles[END_REF]) or with messages encoded as a small smooth number ( [START_REF] Castagnos | Towards a DL-based Additively Homomorphic Encryption Scheme[END_REF]); both solutions still have a partial homomorphy. In [W+11], the map m → g m 0 mod p 0 is used with the plain Elgamal, where p 0 is a prime such that p 0 -1 is smooth and g 0 is a primitive root modulo p 0 . Unfortunately, although not clearly stated, this scheme only supports a limited number of additions, and it is not semantically secure as the set of encoded messages does not belong to a proper subgroup of (Z/pZ) × where the Decisional Diffie-Hellman assumption (DDH) holds.

A full solution has been proposed by Bresson et al. in [START_REF] Bresson | A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications[END_REF]. However, their scheme is not only based on the DL problem but also on the factorization problem. It is less efficient than [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF] but has an additional property: it has a double trapdoor. The idea is to use the same setting as Paillier: In (Z/N 2 Z) × , the DL problem in basis f = 1 + N is easy. Bresson et al. use an Elgamal encryption of the message m as (g r , f m • h r ) modulo N 2 , where N is an RSA integer.

To our knowledge, designing a linearly homomorphic scheme based on the sole hardness of the DL problem is an open problem, as stated in [START_REF] Chevallier-Mames | Encoding-free Elgamal Encryption without Random Oracles[END_REF]. Some other schemes allow more homomorphic operations, like [START_REF] Boneh | Evaluating 2-DNF Formulas on Ciphertexts[END_REF] or [START_REF] Castagnos | Homomorphic Encryption for Multiplications and Pairing Evaluation[END_REF]. As already mentioned, a fully homomorphic encryption (FHE) scheme appeared in 2009 [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF]. Its security relies on hard problems related to lattices. The latest developments of FHE [START_REF] Brakerski | Efficient Fully Homomorphic Encryption from (Standard) LWE[END_REF] are getting more and more efficient and might become operational soon for applications that need a complex treatment over ciphertexts. Meanwhile, for applications that need only to add ciphertexts, protocols that rely on "classical" algorithmic assumptions are still more competitive, in particular in terms of compactness.

Our Contributions. Our contribution has both a theoretical and a practical impact. On one hand, we propose a linearly homomorphic encryption scheme whose security relies on the hardness of the decisional Diffie-Hellman problem. In particular it is the first time that the security of such a scheme does not depend on the hardness of the factorization of integers. On the other hand, we provide an efficient implementation within some specific group, namely the class group of orders in imaginary quadratic fields.

The design of our scheme is somehow similar to the one of [START_REF] Bresson | A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications[END_REF]. We use a group G = g such that the DDH assumption holds in G and such that there exists a subgroup f of G where the DL problem is easy (called a DDH group with an easy DL subgroup). Then the core of the protocol is an Elgamal encryption of the message m as (g r , f m • h r ) for a random r. In our case, the message space will be (Z/pZ) * , where p is a prime. Compared to some other linearly homomorphic schemes, ours allows some flexibility as p can be chosen (with some restrictions) independently from the security parameter.

To reach this unnatural feature without involving the factorization problem, we had to use the particular algebraic structure of class groups of imaginary quadratic fields, which have some specificities which seem hard to find in other groups. We designed a method to compute a group of unknown3 order (to insure the hardness of a partial discrete logarithm assumption) which contains an easy DL subgroup (of known order). The interest of class group of orders in imaginary (or real) quadratic fields in cryptography decreased after critical attacks by Castagnos et al. [START_REF] Castagnos | On the Security of Cryptosystems with Quadratic Decryption: The Nicest Cryptanalysis[END_REF][START_REF] Castagnos | Factoring pq 2 with Quadratic Forms: Nice Cryptanalyses[END_REF] on some specific cryptosystems such as NICE [HPT99,PT00] and its real variant [START_REF] Jacobson | An Adaptation of the NICE Cryptosystem to Real Quadratic Orders[END_REF]. These attacks will not apply in our setting. Indeed, these attacks recover the secret key by exposing the factorization of the discriminant of the field, thanks to the structure of the kernel of the surjection between the class group of a non maximal order to the class group of the maximal order. In our case, the factorization of the discriminant will be public and we will use constructively the ideas of [START_REF] Castagnos | On the Security of Cryptosystems with Quadratic Decryption: The Nicest Cryptanalysis[END_REF]: the subgroup with an easy DL will be precisely the kernel of this surjection. The security of our scheme is proved to rely only on the hardness of the DDH problem in the class group of a non maximal order and on the hardness of computing class numbers. Several systems that adapt either Diffie-Hellman or Elgamal in class groups are already based on the DL problem and the DDH assumption in class groups of maximal order ([BW88,BDW90,SP05,BH01,BV07]) of discriminant ∆ K . The current best known algorithms to solve these problems have a sub-exponential complexity of complexity

L |∆ K | (1/2, o(1)) (cf. [BJS10]
). It means that the factorization problem (or the discrete logarithm problem in a finite field) can be solved asymptotically faster than the discrete logarithm in the class group. 4 Moreover, arithmetic operations in class groups are very efficient, since the reduction and composition of quadratic forms have a quadratic time complexity (and even quasi linear using fast arithmetic).

As a result, our scheme is very competitive. With a straightforward implementation and using an underlying arithmetics very favorable to [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF][START_REF] Bresson | A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications[END_REF], it compares very well with these linearly homomorphic protocols. With a similar level of security, it is faster than [START_REF] Bresson | A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications[END_REF] with a 2048 bits modulus, and the decryption process is faster than Paillier's for a 3072 bits modulus.

A very nice application of our protocol is that it can be used directly in Catalano and Fiore's linearly homomorphic encryption transformation to evaluate degree-2 computations on ciphertexts [START_REF] Catalano | Boosting Linearly-Homomorphic Encryption to Evaluate Degree-2 Functions on Encrypted Data[END_REF]. Their technique requires the message space to be a public ring in which it is possible to sample elements uniformly at random. Our scheme has this feature naturally, contrary to some of the other additively homomorphic schemes. It is therefore a very competitive candidate in 2-server delegation of computation over encrypted data (see [START_REF] Catalano | Boosting Linearly-Homomorphic Encryption to Evaluate Degree-2 Functions on Encrypted Data[END_REF] for more details).

The rest of the paper is organized as follows. In Section 2, we formalize the notion of DDH Group with an Easy DL Subgroup, give reductions between related problems and propose a generic construction of a linearly homomorphic encryption scheme which relies on such group, and prove its security. Sections 3 and 4 present our instantiation in class groups. We give benchmarks and comparisons before concluding. Background on linearly homomorphic encryption can be found in Appendix A. Background on class groups of imaginary quadratic fields and their use for DL based cryptography are given in Appendix B.

DDH Group with an Easy DL Subgroup

In this section, we introduce and formalize the concept of a group in which the decisional Diffie-Hellman problem is hard, whereas it contains a subgroup in which the discrete logarithm problem is easy. This problem has already been used to design cryptosystems, including, for instance, Bresson et al.'s encryption scheme [START_REF] Bresson | A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications[END_REF]. It will be adjusted to build our new encryption protocol.

Definitions and Reductions

Definition 1. We define a DDH group with an easy DL subgroup as a pair of algorithms (Gen, Solve). The Gen algorithm is a group generator which takes as input two parameters λ and µ and outputs a tuple (B, n, p, s, g, f, G, F ). The integers B, n, p and s are such that s is a λ-bit integer, p is a µ-bit integer, gcd(p, s) = 1, n = p • s and B is an upper bound for s. The set (G, •) is a cyclic group of order n generated by g, and F ⊂ G is the subgroup of G of order p and f is a generator of F . The upper bound B is chosen such that the distribution induced by {g r , r $ ← -{0, . . . , Bp -1}} is statistically indistinguishable from inant ∆ will be public or ∆ will be a prime, so we will not rely on the hardness of the factorization problem.

the uniform distribution on G. We assume that the canonical surjection π : G → G/F is efficiently computable from the description of G, H and p and that given an element h ∈ G/F one can efficiently lift h in G, i.e., compute an element h ∈ π -1 (h).

We suppose moreover that:

1. The DL problem is easy in F . The Solve algorithm is a deterministic polynomial time algorithm that solves the discrete logarithm problem in F :

Pr x = x : (B, n, p, s, g, f, G, F ) $ ← -Gen(1 λ , 1 µ ), x $ ← -Z/pZ, X = f x , x ← Solve(B, p, g, f, G, F, X) = 1
2. The DDH problem is hard in G even with access to the Solve algorithm:

Pr b = b : (B, n, p, s, g, f, G, F ) $ ← -Gen(1 λ , 1 µ ), x, y, z $ ← -Z/nZ, X = g x , Y = g y , b $ ← -{0, 1}, Z 0 = g z , Z 1 = g xy , b $ ← -A(B, p, g, f, G, F, X, Y, Z b , Solve(.)) - 1 2
is negligible for all probabilistic polynomial time attacker A.

The bound B for the order s in Definition 1 can be chosen as B = 2 2λ . Indeed, according to Lemma 4 in Appendix C, the statistical distance of {g r , r $ ← -{0, . . . , Bp-1}} to the uniform distribution is upper bounded by n/(4pB) = s/2 2λ+2 2 -λ-2 which a negligible function of λ.

It is fundamental to note that in this definition, the order n of the group G is not an input of the adversary or of the Solve algorithm: Only the bound Bp is implicitly given. Indeed, if n or s were efficiently computable from the description of G, a DDH group with an easy DL subgroup would not exist since it would be possible to partially compute discrete logarithms. More formally, let us define the following partial discrete logarithm problem initially introduced by Paillier in [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF], in the context of the group (Z/N 2 Z) × .

Definition 2 (Partial Discrete Logarithm (PDL) Problem). Let (Gen, Solve) be a DDH group with an easy DL subgroup. Let (B, n, p, s, g, f, G, F )

$ ← -Gen(1 λ , 1 µ ), x $ ← - Z/nZ, X = g x .
The Partial Discrete Logarithm Problem consists in computing x modulo p; given (B, p, g, f, G, F, X) and access to the Solve algorithm.

Lemma 1. Let (Gen, Solve) be a DDH group with an easy DL subgroup and let the tuple (B, n, p, s, g, f, G, F ) be an output of Gen(1 λ , 1 µ ). The knowledge of n makes the PDL problem easy.

Proof. If an adversary is given an instance (B, p, g, f, G, F, X) of the PDL problem, as well as n, he can compute s = n/p and then for all h ∈ G, h s lies in F . The adversary can run the Solve algorithm with g s as input to find α ∈ Z/pZ such that g s = f α . Note that α ≡ 0 (mod p) as g has order n. Thanks to another run of the Solve algorithm with X s as input, the adversary obtains β ∈ Z/pZ such that X s = g sx = f β . Eventually, he computes x ≡ βα -1 (mod p).

Lemma 2. Let G be a DDH group with an easy DL subgroup. The DDH problem in G reduces to the PDL problem.

Proof. Let (B, p, g, f, G, F, X, Y, Z) be an instance of the DDH problem in G. Three queries to the PDL oracle respectively on (B, p, g, f, G, F, X), (B, p, g, f, G, F, Y ) and (B, p, g, f, G, F, Z), gives the adversary x, y and z modulo p. His answer to the DDH instance will be 1 if and only if xy ≡ z (mod p). Indeed, if (X, Y, Z) is a true DDH triple then xy ≡ z (mod n) and he always finds the right answer. Conversely, if (X, Y, Z) is not a DDH triple, xy ≡ z (mod n), and then the adversary fails to correctly responds if xy ≡ z (mod p). But this happens with probability 1/p. As a result, we have sketched a probabilistic polynomial time adversary against DDH with a non negligible advantage equals to 1 2 (1 -1 p ).

Remark 1. Combining Lemmas 1 and 2 we get that as previously mentioned, with the notation of Definition 1, if n is easily computable from the description of G, then the DDH problem in G is easy so, G can not be a DDH group with an easy DL subgroup.

The following problem was introduced in [BCP03] in (Z/N 2 Z) × . It is a variant of the computational Diffie-Hellman problem, that we adapt to our general context.

Definition 3 (Lift Diffie-Hellman (LDH) Problem). Let (Gen, Solve) be a DDH group with an easy DL subgroup. Let (B, n, p, s, g, f, G, F ) $ ← -Gen(1 λ , 1 µ ). Let x, y $ ← - Z/nZ, X = g x ,
Y = g y and Z = g xy and π : G → G/F be the canonical surjection. The Lift Discrete Logarithm Problem consists in computing Z, given the tuple (B, p, g, f, G, F, X, Y, π(Z)) and access to the Solve algorithm.

In the following theorem we prove that this problem is equivalent to the PDL problem. Curiously only one implication was proved in [START_REF] Bresson | A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications[END_REF].

Theorem 1. In a DDH group with an easy DL subgroup, the LDH and PDL are equivalent.

Proof. In all the proof, we implicitly set s = n/p and α ∈ (Z/pZ) × such that g s = f α and denote β ≡ α -1 (mod p). Let us first prove that the PDL problem reduces to the LDH problem, which is a direct generalization of the proof of [BCP03, Theorem 10]. Let (B, p, g, f, G, F, X) be a PDL challenge and let denote X = g x where

x = x 1 + x 2 p with x 1 = x mod p. The adversary draws r 1 $ ← -{0, . . . , B -1}, r 2 $ ← -{0, . . . , p -1} and sets Y = g r 1 f r 2 . Note that Y = g r 1 +sβr 2 . Let us prove that the random variable Y is statistically indistinguishable from the uniform distribution in G.
The distance between Y and the uniform distribution in G is the same than the distance between Y = r 1 + sβr 2 mod n with r 1 uniformly drawn in {0, . . . , B -1} and r 2 independently uniformly drawn in {0, . . . , p -1} and the uniform distribution in {0, . . . , n -1}. Let y be an element of {0, . . . , n -1}, we denote y = y 1 + y 2 s with y 1 ∈ {0, . . . , s -1} and y 2 ∈ {0, . . . , p -1} the euclidean division of y by s. We have

Pr[Y = y] = Pr[Y = y 1 + y 2 s] = Pr[r 1 + sβr 2 ≡ y 1 + y 2 s (mod n)] = Pr[r 1 ≡ y 1 (mod s)] Pr[r 2 β ≡ y 2 (mod p)] = Pr[r 1 ≡ y 1 (mod s)]/p
as β ≡ 0 (mod p). Now let B = qs + r with 0 r < s be the euclidean division of B by s. We proceed as in the proof of Lemma 4 in Appendix C. For y 1 < r, Pr[r 1 ≡ y 1 (mod s)] = (q + 1)/B > 1 s and for y 1 r, Pr[r 1 ≡ y 1 (mod s)] = q/B 1 s . Eventually,

∆(X, Y ) = r q + 1 Bp - 1 n = r(s -r) Bn = r(n -pr) pBn r(n -r) pBn •
This last quantity is the statistical distance of {g r , r $ ← -{0, . . . , Bp -1}} to the uniform distribution in G which is suppose to be negligible. This proves that Y is statistically indistinguishable from the uniform distribution in G.

The adversary then compute Z = π(X r 1 ) = π(X r 1 +sβr 2 ) and queries the LDH oracle with (B, p, g, f, G, F, X, Y, Z ). The oracle provides with non negligible probability

Z = X r 1 +sβr 2 = X r 1 (g x ) sβr 2 = X r 1 g (x 1 +x 2 p)(sβr 2 ) = X r 1 g x 1 sβr 2 = X r 1 f x 1 r 2 .
Then, Z/X r 1 = f x 1 r 2 and running the Solve algorithm on this value gives x 1 r 2 (mod p) to the adversary from which he can get x 1 , the answer to the PDL instance. Now, let us prove that the LDH problem reduces to the PDL problem. Let us consider X = g x , Y = g y , Z = g xy for random x and y, such that the LDH challenge writes as (B, p, g, f, G, F, X, Y, Z = π(Z)). The adversary makes two queries to the PDL oracle relative to X and Y , from which he obtains x (mod p) and y (mod p). The adversary draws r 1 $ ← -{0, . . . B -1} and r 2 $ ← -{0, . . . , p -1} and sets U = g r 1 f r 2 , which is as before statistically indistinguishable from the uniform distribution in G. The adversary queries the PDL oracle with U , which gives r 1 + sβr 2 (mod p) as U = g r 1 +sβr 2 . From this answer, the adversary can compute sβ (mod p). From the definition of a DDH group with an easy DL subgroup, the adversary can compute Z ∈ π -1 (Z ). He then draws r $ ← -Z/pZ and computes V = f r Z . The random variable V is uniformly distributed in G. As π(V ) = Z = π(Z), there exists γ ∈ Z/pZ such that V = f γ Z = g sβγ+xy . From a last call to the PDL oracle, the adversary can get sβγ + xy (mod p) from which he can compute γ since gcd(sβ, p) = 1. Eventually, the adversary deduces Z from V = f γ Z.

We now further analyze the relations between the problems in G/F and G. We first give a lemma that shows that we can define a morphism in order to lift the elements from G/F to G.

Lemma 3. Let (B, n, p, s, g, f, G, F ) $ ← -Gen(1 λ , 1 µ ) where (Gen, Solve) is a DDH group with an easy DL subgroup. Denote π : G → G/F the canonical surjection. The map ψ : G/F → G s.t. h → h p , where h ∈ π -1 (h), is an effective injective morphism.
Proof. First ψ is well defined: if h

(1) , h

(2) ∈ π -1 (h) are two distinct pre-images of h then there exists an element f r ∈ F such that h

(1) = f r h (2) , and (h

(1) ) p = (h (2) ) p as F is of order p. Moreover it is easy to see that ψ is a morphism. Consider h in G/F such that ψ(h) = h p = 1 in G, with h ∈ π -1 (h). Applying π gives π(h ) p = h p = 1.
As G/F is of order s prime to p then h = 1, so the map is injective. Eventually, ψ is efficiently computable as computing h is easy by definition of a DDH group with an easy DL subgroup.

Theorem 2. Let (B, n, p, s, g, f, G, F ) $ ← -Gen(1 λ , 1 µ ) where (Gen, Solve) is a DDH group with an easy DL subgroup. The DL problem in G/F reduces to the DL problem in G.

Proof. Consider a DL problem instance in G/F : Let h = g x where g is a generator of G/F of order s and x $ ← -Z/sZ. The adversary chooses r, r $ ← -(Z/pZ) × and computes g = ψ(g)f r and h = ψ(h)f r where the map ψ is defined in Lemma 3. The element ψ(g) has order s as ψ is injective and f r has order p. As gcd(p, s) = 1, g has order ps and is a generator of G. Moreover, G can be viewed as the direct product

ψ(G/F ) × F . The element h is uniformly distributed in G/F , f r is uniformly distributed in F so h = ψ(h)f r is uniformly distributed in G.
As a consequence, an oracle for the DL problem in G gives x such that g x = h to the adversary with a non negligible advantage. He then has g x = ψ(g) x f rx = h = ψ(h)f r . By the uniqueness of the decomposition of an element of G in a product of an element of ψ(G/F ) and an element of F , and because ψ is injective, we must have g x = h and therefore x ≡ x (mod s).

Unfortunately, it seems unlikely that a similar reduction of the DDH problem in G/F to the DDH problem in G exists. Indeed, a DDH challenge in G/F can be lifted into ψ(G/F ) ⊂ G. But G = ψ(G/F ) × F , so the reduction has to fill the F -part to keep the DDH challenge's form. This seems impossible with a non-negligeable advantage.

Examples

Let G be the group of quadratic residues modulo N 2 where N = (2p + 1)(2q + 1) is the product of two safe primes. In this case, the order of G is N p q . The subgroup H of order N of G is generated by 1 + N , and since (1 + N ) k ≡ 1 + kN (mod N 2 ), the DL problem is easy in H (cf. [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF]). If the factorization of N is known, then DDH problem in G can not be hard (cf. Remark 1). This inspired [BCP03, Theorem 4] where the factorization acts as a second trapdoor to an Elgamal-like protocol in G. A generalization of this protocol is given in the next subsection. Now, let G be the group of quadratic residues modulo p 2 where p = 2p + 1 is a safe prime. In this case, the DL problem is easy in the subgroup of order p generated by 1 + p. The order of G is pp and it can not be hidden from the description of G (i.e., the integer p 2 ). As a result, the PDL and DDH problems are easy. In [START_REF] Chevallier-Mames | Encoding-free Elgamal Encryption without Random Oracles[END_REF], the partial logarithm of an element is called the class of an element. They define a variant of the DDH problem, namely the Decision Class Diffie-Hellman problem, which is believed to be intractable in such a group G. From that problem, [CPP06] derived a modification of Elgamal which, unfortunately, is partially homomorphic: it only supports the addition of a constant.

A Generic Linearly Homomorphic Encryption Scheme

From a DDH group with an easy DL subgroup, we can devise generically a linearly homomorphic encryption scheme. An Elgamal type scheme is used in G, with plaintext message m ∈ Z/pZ mapped to f m ∈ F . The resulted scheme is linearly homomorphic. Thanks to the Solve algorithm, the decryption does not need a complex DL computation. We depict this scheme in Fig. 1. Note that the outputs n and s of Gen are not used in the algorithms.

Algorithm KeyGen(1 λ ) 1. (B, n, p, s, g, f, G, F ) $ ← -Gen(1 λ , 1 µ ) 2. Pick a x $ ← -{0, . . . , Bp -1} and set h ← g x 3. Set pk ← (B, p, g, h, f ) and sk ← x. 4. Return (pk, sk) Algorithm Encrypt(1 λ , pk, m) 1. Pick r $ ← -{0, . . . , Bp -1} 2. Compute c1 ← g r 3. Compute c2 ← f m h r 4. Return (c1, c2)
a As n will be unknown in the sequel, x is picked at random in {0, . . . , Bp -1}

Algorithm Decrypt(1 λ , pk, sk, (c1, c2))

1. Compute M ← c2/c x 1 2. m ← Solve(p, g, f, G, F, M ) 3. Return m Algorithm EvalSum(1 λ , pk, (c1, c2), (c 1 , c 2 )) 1. Compute c 1 ← c1c 1 and c 2 ← c2c 2 2. Pick r $ ← -{0, . . . , Bp -1} 3. Return (c 1 g r , c 2 h r ) Algorithm EvalScal(1 λ , pk, (c1, c2), α) 1. Compute c 1 ← c α 1 and c 2 ← c α 2 2. Pick r $ ← -{0, . . . , Bp -1} 3. Return (c 1 g r , c 2 h r )

Fig. 1. A generic linearly homomorphic encryption scheme

Let us prove the homomorphic property of the scheme. Let us consider an output of the EvalSum algorithm on an input corresponding to encryptions of m and m . Due to Elgamal's multiplicativity, the first line of the decryption algorithm applied on this output gives M = f m f m = f m+m mod p as f as multiplicative order p. As a consequence, the decryption process indeed returns m+m mod p, and the EvalSum algorithm gives a random encryption of m+m (mod p) (in the sense that it has the same output distribution than the encryption algorithm on the input m + m (mod p)). The same argument works for the EvalScal algorithm, with any scalar α ∈ Z/pZ.

Security

The total break of our scheme (tb -cpa attack) consists in finding x from (B, p, g, g x , f ), i.e., in computing a discrete logarithm in G. From Theorem 2, this is harder than computing a discrete logarithm in G/F . Theorem 3. The scheme described in Fig. 1 is one-way under chosen plaintext attack (ow -cpa) if and only if the Lift Diffie-Hellman (LDH) problem is hard (so if and only if the partial discrete logarithm problem (PDL) is hard).

Proof. From the equivalence of Theorem 1, it suffices to prove the equivalence between the owcpa security and the hardness of the LDH problem. Let us consider (c 1 , c 2 ) = (g r , f m h r ), a ciphertext with the public key h = g x . Then as π(c 2 ) = π(h r ) = π(g xr ), the triplet (h, c 1 , π(c 2 )) is an LDH challenge. Given a LDH oracle, we obtain Z = g xr = h r and recover m by running Solve on c 2 /Z.

Conversely let (X, Y, Z ) = (g x , g y , π(Z)) be an LDH challenge with Z = g xy . From this triplet, one can set X as public key and construct the ciphertext (c 1 , c 2 ) = (Y, f r Z ) where Z ∈ π -1 (Z ) and r is a random element of Z/pZ. As π(c 2 ) = Z = π(Z), one as c 2 = f m Z for an element m ∈ Z/pZ. As a result, (c 1 , c 2 ) is a correct ciphertext of m, and a decryption oracle would respond m from which we can compute c 2 /f m and recover Z.

Theorem 4. The scheme described in Fig. 1 is semantically secure under chosen plaintext attacks (ind -cpa) if and only the decisional Diffie-Hellman problem is hard in G.

Proof. Let's construct a reduction R that solve the DDH assumption using an efficient indcpa adversary A. R takes as input a DDH instance (B, p, g, f, G, F, X, Y, Z) and sets pk = (B, p, g, X, f ). When A requests an encryption of one of his choice of challenge messages m 0 and m 1 , R flips a bit b encrypts m b as (Y, f m b Z) and sends this ciphertext as its answer to A. If Z was not a random element, this ciphertext would be indistinguishable from a true encryption of m b because of the choice of the bound B, and A will correctly answer with its (non-negligeable) advantage . Otherwise, the encryption is independent of the message and A's advantage to distinguish is 1/2. Therefore, the reduction returns one if and only A correctly guessed b and has advantage /2 to solve the DDH assumption.

A Linearly Homomorphic Encryption from DDH

We prove that, somewhat like in Paillier's encryption scheme [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF] within Z/N 2 Z, a subgroup with an easy discrete logarithm problem exists in class groups of imaginary quadratic fields, and it allows to design a new linearly homomorphic encryption scheme. We refer the reader to Appendix B for background on class groups of imaginary quadratic fields and their use in Discrete Logarithm based cryptography.

A Subgroup with an Easy DL Problem

The next proposition, inspired by [CL09, Theorem 2], establish the existence of a subgroup of a class group of an imaginary quadratic fields where the DL problem is easy.

Proposition 1. Let ∆ K be a fundamental discriminant with ∆ K ≡ 1 (mod 4) of the form ∆ K = -pq where p is an odd prime and q a non-negative integer prime to p such that q > 4p. Let f = (p 2 , p) be an ideal of O ∆p , the order of discriminant

∆ p = ∆ K p 2 . Denote by f = [f] the class of f in C(O ∆p ). For m ∈ {1, . . . , p-1}, Red(f m ) = (p 2 , L(m)p)
where L(m) is the odd integer in [-p, p] such that L(m) ≡ 1/m (mod p). Moreover, f is a generator of the subgroup of order p of C(O ∆p ).

Proof. We consider the surjection φp : C(O ∆p ) -→ C(O ∆ K ). From [CL09, Lemma 1] and [Cox99, Proposition 7.22 and Theorem 7.24], the kernel of φp is isomorphic to

(O ∆ K /pO ∆ K ) × /(Z/pZ) × . As p | ∆ K , the group (O ∆ K /pO ∆ K ) × is isomorphic to (F p [X]/(X 2 )) ×
. This group contains p(p -1) elements of the form a + b √ ∆ K where a ∈ (Z/pZ) × and b ∈ Z/pZ. Now let us consider the quotient group (O ∆ K /pO ∆ K ) × /(Z/pZ) × where [x] = [y] with x, y ∈ (O ∆ K /pO ∆ K ) × if and only if there exists λ ∈ (Z/pZ) × such that x = λy. This quotient is cyclic of order p and a system of representatives is [1] and [a + √ ∆ K ] where a is an element of (Z/pZ)

× . Let g = [1 + √ ∆ K ], one has g m = [1 + m √ ∆ K ] = [L(m) + √ ∆ K ] for all m ∈ {1, . . . , p -1} and g p = [1]. Let α m = L(m)+ √ ∆ K 2 ∈ O ∆ K . Then α m is a representative of the class g m . The ele- ment g m maps to the class [ϕ -1 p (α m O ∆ K )]
of the kernel of φp . From [BTW95, Proposition 2.9], one can see that α m O ∆ K = (N (α m ), -L(m) mod 2N (α m )) where the remainder is computed from the centered euclidean division. Now,

ϕ -1 p (α m O ∆ K ) = (N (α m ), -L(m)p mod 2N (α m )) . As N (α m ) = L(m) 2 -∆ K 4 and q > 4p, it follows that p 2 < N (α m ) and that -L(m)p mod 2N (α m ) = -L(m)p. As a consequence, this ideal ϕ -1 p (α m O ∆ K ) corresponds to the quadratic form L(m) 2 -∆ K 4 , -L(m)p, p 2 , of discriminant ∆ p . Moreover this form is equivalent to the form (p 2 , L(m)p, L(m) 2 -∆ K 4
) which corresponds to the ideal (p 2 , L(m)p). Eventually, this ideal of O ∆p is reduced as |L(m)p| < p 2 < |∆ p |/2, where the second inequality holds because q > 4p. Consequently, if f = (p 2 , p), then [f] generates the kernel of φp as

[f] = [ϕ -1 p (α 1 O ∆ K )]. Moreover, [f] m = [ϕ -1 (α m O ∆ K )] so Red([f] m ) = (p 2 , L(m)p), for m ∈ {1, . . . , p -1}.
We devise, in Fig. 2, a new DDH group with an easy DL subgroup in class groups of imaginary quadratic fields, by assuming the difficulty of the DDH problem. In the Gen algorithm, we first construct a fundamental discriminant ∆ K = -pq such that the 2-Sylow subgroup of C(∆ K ) is of order 2 (cf. Appendix B.3). Then, using [HJPT98, Subsection 3.1]'s method, we construct an ideal r of O ∆ K of norm r, where r is a prime satisfying ∆ K r = 1. We then assume, as in the previous implementations of Elgamal (cf. Appendix B.4) that the class [r 2 ] will be of order s, an integer of the same order of magnitude than the odd part, h(∆ K )/2. Due to our choice of p and q, pq is 2λ-bit integer, and as s is close to |∆ K | (cf. Appendix B.3), it will be a λ-bit integer.

If µ > 80, following the Cohen-Lenstra heuristics, the probability that p divides h(∆ K ) and s is negligible. Therefore, we can assume that gcd(p, h(∆ K )) = 1. We consider the non-maximal order O ∆p of discriminant p 2 ∆ K as in Proposition 1. The fact that λ µ + 2 ensures that q > 4p. As a result, the subgroup F generated by f gives an easy DL subgroup. The morphism φp defined in Appendix B.1 plays the role of the surjection π between C(O ∆p ) and C(O ∆p )/F C(O ∆ K ), which is computable in polynomial time, knowing p (cf. [HJPT98, Algorithm 3]). Moreover, still with the knowledge of p, it is possible to lift elements of C(O ∆ K ) in C(O ∆p ), using [HPT99, Algorithm 2]. We can then apply the injective morphism of Lemma 3 on [r 2 ] to get a class of C(∆ p ) with the same order s and multiply this class by f k where k $ ← -{1, p -1}. As gcd(p, s) = 1 the result, g is of order ps (this procedure to get an element of order ps was also used in the proof of Theorem 2). Note that g is still a square of C(∆ p ): as the map of Lemma 3 is a morphism, the lift of [r 2 ] gives a square of C(∆ p ). Moreover, F is a subgroup of the squares: f = (f 2 -1 mod p ) 2 as p is odd. As a consequence, g is a square as it is a product of two squares.

Eventually, we take B = |∆ K | 3/4 . According to Lemma 4 in Appendix C, the statistical distance of {g r , r $ ← -{0, . . . , Bp -1}} to the uniform distribution is upper bounded by ps/(4pB) = s/(4

|∆ K | 3/4 ). By Equation 1 in Appendix B.3 , this is less than log |∆ K | 4π |∆ K | 1/4 ∈ Õ(2 -λ/2
) which is a negligible function of λ. As a consequence, the distribution {g r , r $ ← -{0, . . . , Bp -1}} is statistically indistinguishable from the uniform distribution in G = g . In practice, for performance issue, one can take a better bound for B, for example B = 2 80 log(|∆ K |)|∆ K | 1/2 /(4π) , which makes the statistical distance less than 2 -80 .

Algorithm Gen(1 λ , 1 µ ) 1. Assume λ µ + 2 2. Pick p a random µ-bits prime and q a random (2λ-µ) prime such that pq ≡ -1 (mod 4) and (p/q) = -1.

The new protocol

The DDH group with an easy DL subgroup of Fig. 2 gives rise to a linearly homomorphic encryption scheme in quadratic fields, using the generic construction of Fig. 1. Compared to previous solutions based on a similar construction ([BCP03]), this scheme is only based on the difficulty of the discrete logarithm in G, and does not rely on the difficulty of factorization.

In practice, the best attack against the scheme consists in retrieving the private key, i.e., in computing a discrete logarithm. As said in Appendix B.3, the problems of computing discrete logarithm in C(O ∆ K ) and computing h(O ∆ K ) have similar complexity. Given oracle for both problems, one can compute discrete logarithm in C(O ∆p ) and totally break the scheme. Indeed, if s = h(O ∆ K ), given g and h = g x , we can compute φp (g) and φp (h) = φp (g) x mod s . The oracle for discrete logarithm in C(O ∆ K ) gives x mod s. Furthermore, as shown in Lemma 1, if s is known the PDL problem is easy, so one can compute x mod p and we get x as gcd(p, s) = 1 with the Chinese remainder theorem. Moreover, finding h(O ∆ K ) or the multiplicative order of g can be sufficient: knowing s = h(O ∆ K ) breaks the PDL problem (cf. Lemma 1) and the one wayness of the scheme by Theorem 3.

Extensions

Removing the Condition on the Relative Size of p and q

To have a polynomial Solve algorithm, we impose that q > 4p, in order that the reduced elements of f are the ideals of norm p 2 . If we want a large message space, for example 2048 bits (as for the cryptosystem of Paillier or the scheme of [START_REF] Bresson | A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications[END_REF] with a 2048 bit RSA integer), this means that p has 2048 bits, so |∆ p | = p 3 q > 4p 4 has more than 8194 bits and |∆ K | = pq > 4p 2 has more than 4098 bits. Therefore we loose our advantage over factoring based schemes, as we only need a discriminant ∆ K of 1348 bits to have the same security than a 2048 bit RSA integer (cf. Appendix B.3).

For example, suppose that we work with ∆ K = -p. In the order O ∆p of discriminant ∆ p = p 2 ∆ K = -p 3 , the ideals of norm p 2 are no longer reduced. However, we can still have a polynomial time algorithm to solve the discrete logarithm in f where f = [(p 2 , p)]. From the proof of Proposition 1, f still generate the subgroup of order p, and for k ∈ {1, . . . , p-1}, the class f k still contains a non reduced ideal (p 2 , L(k)p) where L(k) is defined as in Proposition 1. We can use the main result of [START_REF] Castagnos | On the Security of Cryptosystems with Quadratic Decryption: The Nicest Cryptanalysis[END_REF] constructively to find this non reduced ideal that will disclose the discrete logarithm k given the reduced element of the class f k . The idea is to lift this reduced element in a class group of a suborder where the ideals of norm p 2 are reduced. Let ∆ p 2 = p 4 ∆ K . For p > 4, we have p 2 < |∆ p 2 |/2 so the ideals of norm p 2 are reduced. We lift an element of O ∆p in O ∆ p 2 by computing [ϕ -1 p (•)] p on a representative ideal prime to p (we can use [HJPT98, Algorithm 1] to find an ideal prime to p in a given class). This map is injective, so applied on f we get a class f of order p in C(O ∆ p 2 ). Moreover, this class is in the kernel of the map φp 2 from C(O ∆ p 2 ) to C(O ∆ K ), and an easy generalization of Proposition 1 shows that the subgroup of

C(O ∆ p 2 ) generated by f is also generated by [(p 2 , p)]. As a result, if h = f x in C(O ∆p ), we have h = [ϕ -1 p ([h])] p = ([ϕ -1 p ([f ])] p ) x = f
x and x can be computed as x = y/z where y is the discrete logarithm of h in basis [(p 2 , p)] and y is the discrete logarithm of f in basis [(p 2 , p)]. Both logarithms can be computed as in

C(O ∆p ).
This variant can also work with ∆ K = -pq and q < 4p, so p can be chosen independently from the security level, with the restriction that p must have at least 80 bits.

A Faster Variant

We can change the KeyGen algorithm as follows: g is now in the class group of the maximal order (i. e., g is the class of r 2 ) and we set h = g x where x is the secret key and the computation is done in C(O ∆ K ). Let us denote by ψ : C(O ∆ K ) → C(O ∆p ) the injective morphism of Lemma 3, that computes [ϕ -1 p (•)] p on a representative ideal prime to p.

To encrypt m ∈ Z/pZ, we compute c 1 = g r and c 2 = f m ψ(h r ) in C(O ∆p ). To decrypt, we first compute c x 1 and lift it, by computing c 1 = ψ(c x 1 ) in C(O ∆p ). Then we retrieve f m = c 2 /c 1 . This variant can be viewed as a mix of an Elgamal cryptosystem in C(O ∆ K ) (lifted in C(O ∆p ) by applying ψ) and of a cryptosystem based on the subgroup decomposition problem using the direct product between ψ( g ) and f . The advantage of this variant is that ciphertexts are smaller (c

1 is in C(O ∆ K ) instead of C(O ∆p ))
and that computations are faster: encryption performs two exponentiations in C(O ∆ K ) instead of C(O ∆p ) and one lift (which computational cost is essentially the exponentiation to the power p). Decryption similarly involves one exponentiation in C(O ∆ K ) instead of C(O ∆p ) and a lift. However, the semantic security is now based on a non standard problem. Let g be a generator of a subgroup of C(O ∆ K ) of order s. After having chosen m, the adversary is asked to distinguished the following distributions :

{(g x , g y , ψ(g xy )), x, y $ ← -Z/sZ} and {(g x , g y , ψ(g xy )f m ), x, y $ ← -Z/sZ}. The total break is equivalent to the DL problem in C(O ∆ K ).
5 Performances and Comparisons.

We now compare the efficiency of our cryptosystem with some other linearly homomorphic encryptions schemes, namely the system of Paillier and the one from [START_REF] Bresson | A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications[END_REF]. The security of the Paillier cryptosystem is based on the factorization problem of RSA integers, while [START_REF] Bresson | A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications[END_REF] is based on both the factorization and the DL problems. For our scheme, the best attack consists in computing DL in C(O ∆ K ) or in computing h(O ∆ K ) and both problems have similar complexity.

As said in Appendix B.3, in [START_REF] Biasse | Security Estimates for Quadratic Field Based Cryptosystems[END_REF], the Discrete Logarithm problem with a discriminant ∆ K of 1348 (resp. 1828 bits) is estimated as hard as factoring a 2048 (resp. 3072 bits) RSA integer n. In Fig. 1, we give the timings in ms of the time to perform an encryption and decryption for the three schemes. Concerning Paillier, for encryption and decryption, the main operation is an exponentiation of the form x k mod n 2 where k has the same bit length as n. Concerning [START_REF] Bresson | A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications[END_REF], which has an Elgamal structure, two exponentiations of the form x k mod n 2 with k an integer of the same bit length as n 2 are used for encryption and one for decryption. Our scheme has also this structure with two exponentiations for encryption and one for decryption. Decryption also involves an inversion modulo p. The exponentiations are made in C(O ∆p ) with ∆ p = p 2 ∆ K . The size of the exponent is bounded by Bp where we have seen that B can be chosen roughly of the bit size of √ ∆ K plus 80 bits. For a same security level, our scheme is thus more efficient for a small p.

The timings where performed with Sage 6.3 on a standard laptop with a straightforward implementation. The exponentiation in class group uses a PARI/GP function (qfbnupow). We must stress that this function is far less optimized than the exponentiation in Z/nZ, so there is a huge bias in favor of BCP and Paillier. A more optimized implementation would give much better results for our system. Nevertheless, we see that for a 2048 bits modulus, our cryptosystem is already faster than the protocol from [START_REF] Bresson | A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications[END_REF]. Moreover, for stronger securities, our system will be faster, as asymptotically, the factorization algorithms have complexity L(1/3, •) whereas the algorithms for class groups of quadratic fields have complexity L(1/2, •). Moreover the multiplication modulo n and the composition of quadratic forms have both quasi linear complexity [START_REF] Schönhage | Fast reduction and composition of binary quadratic forms[END_REF]. As shown in Table 1, already with a 3072 bits modulus our cryptosystem is competitive: faster than Paillier for decryption. For a very high security level (7680 bits modulus), our system would be twice as fast as Paillier for encryption, for messages of 512 bits. We also give timings of our faster variant of Subsection 4.2. For a same security level, this variant becomes more interesting when the message space grows. In Table 1, we see that even with a naive implementation, our system is competitive for message space up to 256 bits (resp. 912 bits) for 2048 bits security (resp. for 3072 bits security).

Note that a medium size message space can be sufficient for applications. For example, our system may be used as in [START_REF] Cramer | A Secure and Optimally Efficient Multi-Authority Election Scheme[END_REF] to design a voting scheme. For a yes/no pool, a voter encrypts 0 (resp. 1) to vote no (resp. to vote yes). By combining all the ciphertexts, the election manager would get an encryption of the sum of the vote modulo p. Decryption allows to decide the result if the number of voters satisfies < p. So a 80-bit p is largely sufficient as 2 80 ≈ 10 24 . With Elgamal, in [START_REF] Cramer | A Secure and Optimally Efficient Multi-Authority Election Scheme[END_REF], the discrete logarithm in decryption involves a baby-step giant-step computation of time O( √ ) (so a very low number of voters can be handled) whereas a single inversion modulo p is needed for our scheme. For a multi-candidate election system with m candidates and voters, one votes for the i th candidate by encrypting i . The tally is decrypted with a decomposition in base , so we must have m < p. With a 256 bit integer p, we can have for example 2 16 voters and 16 candidates, which is the good order of magnitude for real life elections, for which there are around a thousand registered voters by polling stations.

Conclusion

We proposed the first linearly homomorphic encryption whose security relies on a sole Diffie-Hellman-like assumption. Our construction crucially uses the algebraic properties of the class group of a non maximal order of an imaginary quadratic field. They make it possible to avoid the factorization assumption and to have Z/pZ as the set of messages. Other improvements than those we presented are possible: we can gain efficiency using the Chinese Remainder Theorem using discriminant of the form ∆ K = -( n i=1 p i )q, and generalizing à la Damgård and Jurik (cf. [START_REF] Damgård | A Generalisation, a Simplification and some Applications of Paillier's Probabilistic Public-Key System[END_REF]), with discriminants of the form ∆ p t = p 2t ∆ K , with ∆ K = -pq and t 1 to enlarge the message space to Z/p t Z without losing the homomorphic property. A non-trivial adaptation may also be possible with

: I(O ∆ f , f ) → I(O ∆ K , f ), a → aO ∆ K is an isomorphism. This map induces a surjection φf : C(O ∆ f ) C(O ∆ K ).
In our settings, we will use a prime conductor f = p and consider ∆ p = p 2 ∆ K , for a fundamental discriminant ∆ K divisible by p. The order of the kernel of φp is then given by the classical analytic class number formula (see for instance [START_REF] Buchmann | Binary Quadratic Forms. An Algorithmic Approach[END_REF]):

h(O ∆p ) h(O ∆ K ) = p if ∆ K < -4.

B.2 Representation of the Classes

Working with ideals modulo the equivalence relation of the class group is essentially equivalent to work with binary quadratic forms modulo SL 2 (Z) (cf. Section 5.2 of [START_REF] Cohen | A Course in Computational Algebraic Number Theory[END_REF]). Every (primitive) ideal a of O ∆ can be written as a = aZ + -b+ √ ∆ 2 Z with a ∈ N and b ∈ Z such that b 2 ≡ ∆ (mod 4a), and denoted by (a, b) for short. The norm of such an ideal is then a. This notation also represents the binary quadratic form ax 2 + bxy + cy 2 with b 2 -4ac = ∆. This representation of the ideal is unique if the form is normal: -a < b a.

An ideal is reduced if it is normal, and a c, and b 0 for a = c. Note that in every class of O ∆ -ideals there exists exactly one reduced ideal. We note Red(a) the unique reduced ideal equivalent to an ideal a, or Red([a]) the unique reduced ideal in the class [a]. From the theory of quadratic forms, we can efficiently compute Red(a) given a. The algorithm, which is due to Gauss, is described in [Coh00, Algorithm 5.4.2 p. 243] and is called Red in this paper. In general, instead of working with classes, we will work with reduced ideals. The product of ideals is also efficiently computable with the composition of quadratic forms algorithm, see [Coh00, Algorithm 5.4.7 p. 243]. These two algorithms have quadratic complexity (and even quasi linear using fast arithmetic).

A crucial fact for our purpose is described in [Coh00, Lemma 5.3.4] and [BV07, Lemma 6.5.1]: a normal ideal a = (a, b) with |a| < |∆|/2 is reduced.

B.3 Class Number Computation and DL Problem

In 2000, Jacobson has described an index-calculus method to solve the discrete logarithm problem in class group of imaginary quadratic field of discriminant ∆ K [Jac00]. Various improvements have been proposed to this algorithm: In [START_REF] Biasse | Security Estimates for Quadratic Field Based Cryptosystems[END_REF], it is conjecture that a state of the art implementation has conjectured complexity L |∆ K | [1/2, o(1)] . Moreover, the best known algorithm to compute class numbers of fundamental discriminant are again index-calculus method with the same complexity.

In [START_REF] Hamdy | Security of Cryptosystems Based on Class Groups of Imaginary Quadratic Orders[END_REF], Hamdy and Möller discuss the selection of a discriminant ∆ K such that the discrete logarithm problem in C(O ∆ K ) is as hard as in finite fields: It is advised to construct a fundamental discriminant ∆ K and to minimize to 2-Sylow subgroup of the class group. In our case, by construction ∆ K will be the product of two odd primes. If we take ∆ K = -pq with p and q such that p ≡ -q (mod 4) then ∆ K is a fundamental discriminant. Moreover the 2-Sylow subgroup will be isomorphic to Z/2Z if we choose p and q such that (p/q) = (q/p) = -1 (cf. [Kap78, p. 598]). In that case, we will work with the odd part, which is the group of squares of C(O ∆ K ).

Following the Cohen-Lenstra heuristics, cf. [Coh00, Chapter 5.10.1], the probability that the odd part of the class group is cyclic is 97.757% and the probability that an odd prime r divides h(O ∆ K ) is approximately 1/r + 1/r 2 . As a result, we can not guarantee that the order of the odd part is not divisible by small primes. Nevertheless, as indicated in [START_REF] Hamdy | Security of Cryptosystems Based on Class Groups of Imaginary Quadratic Orders[END_REF], this does not lead to a weakness on the discrete logarithm problem, as there is no efficient algorithm to compute h(O ∆ K ) or odd multiples or factors of h(O ∆ K ), hence an adaptation of the Pohlig-Hellman Algorithm is not possible.

On average, h

(O ∆ K ) is in the order of |∆ K |, see [Coh00, Theorem 4.9.15 (Brauer- Siegel)]. Moreover (cf. [Coh00, p. 295]), h(∆ K ) < 1 π log |∆ K | |∆ K |. (1)
To conclude, following [START_REF] Hamdy | Security of Cryptosystems Based on Class Groups of Imaginary Quadratic Orders[END_REF], if ∆ K is taken large enough, generic methods to compute discrete logarithm such as Pollard λ-method are slower than the index-calculus algorithms. Thus, since index-calculus algorithms for solving the discrete logarithm problem are asymptotically much slower than index-calculus algorithms to solve the integer factorization problem, the discriminant can be taken smaller than RSA modulus. In [START_REF] Biasse | Security Estimates for Quadratic Field Based Cryptosystems[END_REF], the discrete logarithm problem with a discriminant of 1348 bits (resp. 1828 bits) is estimated as hard as factoring a 2048 bits (resp. 3072 bits) RSA integer.

B.4 Elgamal Cryptosystem Adaptations in Class Group

In [START_REF] Buchmann | A Key-Exchange System Based on Imaginary Quadratic Fields[END_REF], Buchmann and Williams proposed an adaptation of the Diffie-Hellman key exchange in imaginary quadratic fields and briefly described an adaptation of the Elgamal cryptosystem in the same setting. Efficient implementations of these cryptosystems are discussed in [BDW90,SP05,BH01] and [START_REF] Buchmann | Binary Quadratic Forms. An Algorithmic Approach[END_REF]. At a high level, the key generation process of these adaptations of Elgamal can be sketched as follows:

-Generate ∆ K a fundamental negative discriminant, such that |∆ K | is large enough to thwart the computation of discrete logarithm (cf. previous subsection) ; choose g a class of C(O ∆ K ) of even order (from the discussion of the previous subsection, the order of g will be close to h(∆ K ) ≈ |∆ K | with high probability) ;

21

the private key is x $ ← -{0, . . . , |∆ K | } and the public key is (g, h), where h = g x .

To implement Elgamal, it remains the problem of the embedding of a message. In [START_REF] Buchmann | A Key-Exchange System Based on Imaginary Quadratic Fields[END_REF], an integer m is encrypted as (g r , m + N (h r )) where N (h r ) denotes the norm of the reduced ideal of the class h r . As a result, the scheme is not based on the traditional DDH assumption.

Another solution is given in [SP05, Section 2]. An integer message m ≤ |∆|/2 is mapped to the class M of an ideal above p where p is the first prime with p > m such that ∆ is a quadratic residue modulo p. If d = m -p, the message m is encrypted as (g r , M h r , d): The distance d seems to be public, in order to recover m from M . This can be a problem for semantic security: the first stage adversary can choose two messages m 0 , m 1 such that d 0 = d 1 and easily win the indistinguishability game with probability one by recognizing the message thanks to the distance.

In [START_REF] Buchmann | A survey on IQ-cryptography, Public-Key Cryptography and Computational Number Theory[END_REF], a "hashed" version is used, a bit-string m is encrypted as (g r , m ⊕ H(h r )) where H is a cryptographic hash function. In [START_REF] Buchmann | Binary Quadratic Forms. An Algorithmic Approach[END_REF], an adaptation of DHIES is described.

An variant of the Elgamal cryptosystem in a non maximal order of discriminant ∆ q = q 2 ∆ K is presented in [START_REF] Hühnlein | A Cryptosystem Based on Non-Maximal Imaginary Quadratic Orders with Fast Decryption[END_REF]. A traditional setup of Elgamal is done in C(O ∆q ), h = g x . A ciphertext is (g r , mh r ) in C(O ∆q ) where m is an ideal of norm smaller than √ ∆ K /2. To decrypt, the ciphertext is moved in the maximal order with the trapdoor q where a traditional decryption is made to recover the message in C(O ∆ K ). Eventually, the message is lifted back in C(O ∆q ). This variant can be seen as an Elgamal with a CRT decryption procedure: its advantage is that most of the decryption computation is done in C(O ∆ K ) and ∆ K can be chosen relatively small (big enough such the factorization of ∆ q is intractable, the discrete logarithm problem can be easy in C(O ∆ K )). The problem of the embedding of the plaintext in an ideal is not addressed in this paper. A chosenciphertext attack against this cryptosystem has been proposed in [START_REF] Jaulmes | A NICE Cryptanalysis[END_REF].

In [START_REF] Kim | Public-key cryptosystems based on class semigroups of imaginary quadratic non-maximal orders[END_REF], an adaptation of the Diffie-Hellman key exchange and of the Elgamal cryptosystem are given using class semigroup of an imaginary non-maximal quadratic order. Unfortunately a cryptanalysis of this proposal has been presented in [START_REF] Jacobson | The Security of Cryptosystems Based on Class Semigroups of Imaginary Quadratic Non-maximal Orders[END_REF].

A final important remark on the adaptation of the Elgamal cryptosystem is that it is necessary to work in the group of squares, i. e., the principal genus. We didn't find this remark in previous works: in the whole class group, the DDH problem is easy. Indeed, it is well known that in (Z/pZ) × , one can compute Legendre symbols and defeats the DDH assumption. As a consequence, it is necessary to work in the group of squares. In a class group, for example if the discriminant ∆ = -k i=1 p i is odd and the p i are distinct primes numbers, we can associate to a class the value of the generic characters, the Legendre symbols (r, p i ) for i from 1 to k where r is an integer represented by the class (see [START_REF] Cox | Primes of the form x 2 + ny 2[END_REF] for details on genus theory). It is easy to see that the previous attack in (Z/pZ) × can be adapted in class groups with the computation of the generic characters. As a result, it is necessary to work in the group of squares, which is the principal genus (cf. [Cox99, Theorem 3.15]), i. e., the set of classes such that the generic characters all equal 1.

  Fig. 2. A new DDH Group with an Easy DL Subgroup

Table 1 .

 1 Efficiency Comparison of Linearly Homomorphic Encryption Schemes real quadratic fields. Experiments show that our protocol is competitive with existing ones.then O = Z + f ω K Z. The integer f is called the conductor of O. The discriminant of O is then ∆ f = f 2 ∆ K . Now, let O ∆ be an order of discriminant ∆ and a be a nonzero ideal of O ∆ , its norm is N(a) = |O ∆ /a|. A fractional ideal is a subset a ⊂ K such that da is an ideal of O ∆ for d ∈ N. A fractionalideal a is said to be invertible if there exists an another fractional ideal b such that ab = O ∆ . The ideal class group of O ∆ is C(O ∆ ) = I(O ∆ )/P (O ∆ ), where I(O ∆ ) is the group of invertible fractional ideals of O ∆ and P (O ∆ ) the subgroup consisting of principal ideals. Its cardinality is the class number of O ∆ denoted by h(O ∆ ). The group O ∆ of units in O ∆ is equal to {±1} for all ∆ < 0, except when ∆ is equal to -3 and -4 (O -3 and O -4 are respectively the group of sixth and fourth roots of unity) A nonzero ideal a of O ∆ , a is said to be prime to f if a + f O ∆ = O ∆ . We denote by I(O ∆ , f ) the subgroup of I(O ∆ ) of ideals prime to f . The map ϕ f

	Cryptosystem	Parameter	Message Space Encryption (ms) Decryption (ms)
	Paillier	2048 bits modulus	2048 bits	28	28
	BCP03	2048 bits modulus	2048 bits	107	54
	New Proposal	1348 bits ∆K	80 bits	93	49
	Variant Subsec. 4.2 1348 bits ∆K	80 bits	82	45
	Variant Subsec. 4.2 1348 bits ∆K	256 bits	105	68
	Paillier	3072 bits modulus	3072 bits	109	109
	BCP03	3072 bits modulus	3072 bits	427	214
	New Proposal	1828 bits ∆K	80 bits	179	91
	Variant Subsec. 4.2 1828 bits ∆K	80 bits	145	78
	Variant Subsec. 4.2 1828 bits ∆K	512 bits	226	159
	Variant Subsec. 4.2 1828 bits ∆K	912 bits	340	271

Using groups of unknown order in cryptography has already been done[START_REF] Brent | Public Key Cryptography with a Group of Unknown Order[END_REF][START_REF] Coron | ECC: Do We Need to Count? Proc. of Asiacrypt[END_REF][START_REF] Damgård | A Statistically-Hiding Integer Commitment Scheme Based on Groups with Hidden Order[END_REF]

Note that it is well known (see[START_REF] Hamdy | Security of Cryptosystems Based on Class Groups of Imaginary Quadratic Orders[END_REF] for instance) that computing the class number of a quadratic field of discriminant ∆ allows to factor ∆ . However for our scheme, the factorization of the discrim-

Acknowledgement: This work has been supported in part by ERC Starting Grant ERC-2013-StG-335086-LATTAC and by the financial support from the French State, managed by the French National Research Agency (ANR) in the frame of the "Investments for the future" Programme IdEx Bordeaux (ANR-10-IDEX-03-02), Cluster of excellence CPU.

A Public-key Encryption: Definitions

Encryption Scheme: Definition. Let λ be an integer. An encryption scheme is a tuple of algorithms Π = (KeyGen, Encrypt, Decrypt). The probabilistic polynomial-time key generation algorithm KeyGen takes a security parameter λ in unary as input and returns a pair (pk, sk) of public key and the matching secret key. The probabilistic polynomial-time encryption algorithm Encrypt takes a security parameter, a public key pk and a message m as inputs, and outputs a ciphertext c. The deterministic polynomial-time Decrypt decryption algorithm takes a security parameter, a secret key sk and a ciphertext c and returns either a message m or the symbol ⊥ which indicates the invalidity of the ciphertext. The scheme must be correct, which means that for all security parameters λ, and for all messages m, if (pk, sk) ← KeyGen(1 λ ) then Decrypt(1 λ , sk, Encrypt(1 λ , pk, m)) = m with probability (taken on all internal random coins and random choices).

Encryption Scheme: Security. The total break of an encryption scheme is declared if an attacker can recover the secret key from (at least) the public key. Therefore any probabilistic polynomial-time Turing machine B must have a success in recovering the public key arbitrarily small, where the success is defined, for an integer λ, as the probability Pr (pk, sk) ← Π.KeyGen(1 λ ) : B(pk) = sk .

The intuitive security notion expected from an encryption scheme is the one-wayness, which means that, given only the public data, an adversary cannot recover the message corresponding to a given ciphertext. More precisely, any probabilistic polynomialtime Turing machine A (the attacker ) has a success in inverting the encryption algorithm arbitrarily small, where the success is defined, for an integer λ, as the probability Pr (pk, sk) ← Π.KeyGen(1 λ ) :

The previous definition supposes that the attacker has no more information that the public key : the attacker is said to do a chosen-plaintext attack (since he can produce the ciphertext of message of his choice). If he has access to a decryption oracle, the attack is said be a chosen-ciphertext attack.

An encryption scheme must indeed reach a stronger notion of security : it must have semantic security (aka indistinguishability). This means that an attacker is computationally unable to distinguish between two messages, chosen by himself, which one has been encrypted, with a probability significantly better than one half. The indistinguishability game is formally defined as:

where the adversary A is modelled as a 2-stage PPTM (A 1 , A 2 ). The advantage of the attacker is then defined as

Linearly Homomorphic Encryption Let suppose that the set of plaintexts M (resp. the set of ciphertexts C) is equipped with an additive (resp. a multiplicative) group structure. An encryption scheme Π is said to be homomorphic if ∀λ ∈ N, ∀(pk, sk) ← KeyGen(1 λ ), ∀m 1 , m 2 ∈ M, if c 1 ← Encrypt(pk, m 1 ) and c 2 ← Encrypt(pk, m 2 ), then the product c 1 c 2 is a valid encryption of m 1 + m 2 . The exponentiation of a ciphertext c 1 to a power α is as well a valid encryption of αm 1 . The formal definition of a linearly homomorphic encryption includes two algorithms EvalSum and EvalScal that fulfills the corresponding correctness property. Of course, to achieve semantic security Π.Encrypt has to be probabilistic, but even though, the highest level of indistinguishability an homomorphic encryption scheme can achieve is indeed ind -cca1. As a matter of fact, an attacker will always win the cca2 game by querying, in the second phase, for instance c • Encrypt(pk, 0) to the decryption oracle: this one will answer with m b + 0 = m b .

B Background on Imaginary Quadratic Fields

B.1 Imaginary Quadratic Fields and Class Group

Let D < 0 be a squarefree integer and consider the quadratic imaginary field

C Uniform Sampling in a Cyclic Group

Let us first recall some well known facts on the statistical distance of two discrete random variables. Let X and Y two discrete random variables with values in Ω. The statistical distance between X and Y is defined as

So we can restrict to subsets A such that the difference is positive. Moreover, in order to maximize the difference, we can let

we have Proof. Let X the random variable with values in {0, . . . , n-1} with uniform distribution and Y defined by Y = (y mod n) where y is drawn in {0, . . . , B -1} with uniform distribution. Clearly, ∆(X, Y ) = ∆(X , Y ). Let B = qn + r with 0 r < n be the euclidean division of B by n. For c ∈ {0, . . . , r -1}, Pr[Y = c] = (q + 1)/B > 1 n as (q + 1)n > B. For c ∈ {r, . . . , n -1}, Pr[Y = c] = q/B 1/n. So for A = {0, . . . , r -1}, we have

Using the fact that q = B-r n , this simplifies to ∆(X, Y ) = r(n-r) nB . Moreover as r(n -r) n 2 /4, ∆(X, Y ) n 4B •