Cyril Bouvier
email: cyril.bouvier@lirmm.fr

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

Laurent Imbert
email: laurent.imbert@lirmm.fr

Fabien Laguillaumie
email: fabien.laguillaumie@lirmm.fr

I want to ride my BICYCL: BICYCL Implements CryptographY in CLass groups

Keywords: class group cryptography, quadratic form arithmetic, implementation library, linearly homomorphic encryption, multi-party computation

We introduce BICYCL an Open Source C++ library that implements arithmetic in the ideal class groups of imaginary quadratic fields, together with a set of cryptographic primitives based on class groups. It is available at https://gite.lirmm.fr/crypto/bicycl under GNU General Public License version 3 or any later version. BICYCL provides significant speed-ups on the implementation of the arithmetic of class groups. Concerning cryptographic applications, BICYCL is orders of magnitude faster than any previous pilot implementation of the CL linearly encryption scheme, making it faster than Paillier's encryption scheme at any security level. Linearly homomorphic encryption is the core of many multi-party computation protocols, sometimes involving a huge number of encryptions and homomorphic evaluations: class groupbased protocols become the best solution in terms of bandwidth and computational efficiency to rely upon.

Introduction

Class group cryptography was introduced in the late 80s by Buchmann and Williams [START_REF] Buchmann | A key-exchange system based on imaginary quadratic fields[END_REF][START_REF] Buchmann | A key exchange system based on real quadratic fields[END_REF] and concurrently by McCurley [START_REF] Mccurley | Cryptographic key distribution and computation in class groups[END_REF] through variants of the Diffie-Hellman key agreement [START_REF] Diffie | New directions in cryptography[END_REF] and their extensions to public-key cryptosystems using constructions similar to that of Elgamal [START_REF]A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF]. More specifically, Buchmann and Williams [START_REF] Buchmann | A key-exchange system based on imaginary quadratic fields[END_REF] suggested that the class group of ideals of maximal orders of imaginary quadratic fields may offer a better security than the multiplicative group of finite fields. Indeed, at the time, the best algorithms for computing discrete logarithms in class groups were exponential in the group order, whereas index calculus methods with subexponential complexity already existed for the equivalent problem in (multiplicative subgroups of) finite fields. The current best algorithms for computing the structure of the class group of a quadratic imaginary number field [START_REF] Jacobson | Computing discrete logarithms in quadratic orders[END_REF][START_REF] Biasse | Improvements in the computation of ideal class groups of imaginary quadratic number fields[END_REF][START_REF] Kleinjung | Quadratic sieving[END_REF] are all improvements of Hafner and McCurley's algorithm [START_REF] Hafner | A rigorous subexponential algorithm for computation of class groups[END_REF]. The costs of these algorithms increase with ∆, the discriminant of the number field. The current largest computation involved a 512 bits discriminant [START_REF] Beullens | CSI-FiSh: Efficient isogeny based signatures through class group computations[END_REF].

With a subexponential complexity of L 1/2 (|∆|), computing class groups is still asymptotically slower than factoring integers, whose complexity is L 1/3 (N ), where N is the integer to be factored. From a cryptographic perspective, it essentially means that any given security level may be achieved with shorter keys than those required by schemes based on integer factorization. Nevertheless, the arithmetic of class groups is quite intricate. Therefore, the associated cryptographic protocols are potentially slower than cryptosystems based on elliptic curves or those involving arithmetic modulo a prime number or an RSA modulus.

A nice attempt to improve the efficiency of cryptosystems based on class group was achieved by Hühnlein, Jacobson, Paulus and Takagi [START_REF] Hühnlein | A cryptosystem based on non-maximal imaginary quadratic orders with fast decryption[END_REF]. Unfortunately, a critical attack [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] against this family of cryptosystems consigned class group cryptography to oblivion. Over the last decade, class groups have regained a lot of interest thanks to their usefulness in designing advanced cryptosystems and secure multi-party computation protocols. In particular, ideas from the original attack [START_REF] Castagnos | On the security of cryptosystems with quadratic decryption: The nicest cryptanalysis[END_REF] were positively turned into the Castagnos -Laguillaumie (CL) linearly homomorphic encryption scheme (LHE) [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF] which involves a subgroup of a class group where discrete logarithms are easy to compute. CL is at the heart of a construction of projective hash functions, which in turn allows to design efficient inner-product functional encryption [START_REF] Castagnos | Practical fully secure unrestricted inner product functional encryption modulo p[END_REF], two-party and fullythreshold ECDSA signatures [START_REF] Castagnos | Two-party ECDSA from hash proof systems and efficient instantiations[END_REF][START_REF] Castagnos | Bandwidthefficient threshold EC-DSA[END_REF][START_REF] Yuen | Compact zero-knowledge proofs for threshold ECDSA with trustless setup[END_REF][START_REF] Deng | Promise Σ-protocol: How to construct efficient threshold ECDSA from encryptions based on class groups[END_REF], as well as coin mixing protocols [START_REF] Glaeser | Foundations of coin mixing services[END_REF].

A crucial advantage of class group cryptography is that it is well-suited when multi-party protocols require a one-time transparent (or public-coin) setup with minimal interaction among parties. In addition, it is also interesting for timereleased cryptography since protocols can take advantage of an exponentiation over a group of unknown order. For instance, [START_REF] Thyagarajan | Efficient CCA timed commitments in class groups[END_REF] presented secure timed commitments and a scalable distributed randomness generation with enhanced security, transparent setup, that relies on a variant of the CL encryption scheme. Besides, class group cryptography has recently led to many advanced protocols such as verifiable random functions without trusted setup [START_REF] Wesolowski | Efficient verifiable delay functions[END_REF], accumulators [START_REF] Lipmaa | Secure accumulators from Euclidean rings without trusted setup[END_REF][START_REF] Boneh | Batching techniques for accumulators with applications to IOPs and stateless blockchains[END_REF], encryption switching protocols [START_REF] Castagnos | Encryption switching protocols revisited: Switching modulo p[END_REF], efficient designated-verifier non-interactive zero-knowledge proofs of knowledge [START_REF] Chaidos | Efficient designated-verifier non-interactive zeroknowledge proofs of knowledge[END_REF], succinct non-interactive argument of knowledge [START_REF] Bünz | Transparent SNARKs from DARK compilers[END_REF][START_REF] Lai | Subvector commitments with application to succinct arguments[END_REF], homomorphic secret sharing and pseudorandom correlation functions for generating oblivious transfer [START_REF] Abram | An algebraic framework for silent preprocessing with trustless setup and active security[END_REF], range proofs [START_REF] Couteau | Efficient range proofs with transparent setup from bounded integer commitments[END_REF][START_REF] Couteau | Sharp: Short relaxed range proofs[END_REF] or vector commitments [START_REF] Attema | Vector commitments over rings and compressed σ-protocols[END_REF].

When available, the timings reported in these contributions come from vanilla implementations of the protocols, mainly relying on PARI/GP [START_REF][END_REF] functions for the arithmetic of class group. Very few dedicated libraries exist for class group cryptography: we can cite ZenGo-X's Class library written in Rust [START_REF] Zengo | Class: Rust library for building iqc[END_REF] (used to benchmark threshold ECDSA signatures), which makes calls to PARI/GP, Sayles' libqform library [START_REF] Sayles | libqform[END_REF], which is an optimized C library for ideal arithmetic in imaginary quadratic number fields but which does not implement any cryptographic protocols, and the implementation that won the Chia VDF compe-tition [START_REF] Rijmen | Chia verifiable delay function competition[END_REF] whose goal was to evaluate a VDF by performing successive squarings as fast as possible 3 .

In this paper, we introduce BICYCL, an optimized open source library that implements arithmetic in ideal class groups of imaginary quadratic fields together with class group-based cryptographic primitives and protocols. We show that our library outperforms any implementation that we were aware of, and demonstrate that class group cryptography can be more efficient than classical cryptography in certain cases, particularly for linearly homomorphic encryption. This is interesting for applications to multi-party computation as LHEs based on class groups offer at the same time: transparent setup, low bandwidth, efficient thresholdization due to their Elgamal structure, and now computational efficiency.

Our main contributions:

-From a theoretical point of view, we unify several frameworks to construct linearly homomorphic encryption schemes from [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF][START_REF] Castagnos | Threshold linearly homomorphic encryption on Z/2 k Z[END_REF], as well as compact (i.e., with shorter ciphertexts) and large message variants of these cryptosystems and provide the security proofs. -We optimize the implementation of the arithmetic of binary quadratic forms at a low level, namely the squaring (NUDUPL) and the composition (NU-COMP) of quadratic forms, by carefully implementing partial extended GCD variants. At a higher level, we also improve exponentiation in the class group arising from practical cryptographic applications, such as CL encryption which requires two fixed-basis exponentiations. -We explicit some isomorphisms involving some subgroups of the class groups (in particular those where computing discrete logarithms is easily ) that allow very fast exponentiations and discrete logarithm computations needed by the CL framework. More precisely, these explicit isomorphisms make it possible to avoid quadratic form arithmetic in these subgroups, allowing instead the use of more efficient arithmetic of quadratic integers. -We provide a suite of cryptographic protocols: not only we have implemented the CL encryption and its variants, but we also provide an implementation of Paillier and Camenisch-Shoup, that take benefit, when possible, from our improvements for CL, as well as a zero-knowledge proof of well-formedness of a CL ciphertext.

BICYCL is significantly faster than any previous pilot implementation of the CL protocol, improving encryption time by a factor 20, and decryption by a factor 5 compared to the first implementation [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF]. At the lower level, these significant speed-ups come from our implementation of the arithmetic of binary quadratic forms, namely the NUDUPL and NUCOMP algorithms. As an illustration, for 6000-bit discriminant, our version of NUDUPL is 15% faster than libqform [START_REF] Sayles | libqform[END_REF], which was the fastest implementation available that we were aware of, and 68% faster than PARI/GP that is probably the most widely used. The cryptographic schemes that we have implemented also benefit from tailored exponentiations in the class group, in particular when the base is fixed. In Section 6, we present more extensive comparisons with other libraries for the low level arithmetic primitives, as well as timings and comparisons with various LHE schemes. In particular, we show that for common applications, CL's encryption is faster than Paillier's at any security level. In addition, in multi-party computation protocols or when data are encrypted, homomorphic arithmetic modulo an RSA number is not well-suited if the message space is of order a prime q, and requires subtleties to deal with potential wraparounds or to hide the number of modular reductions modulo q during the process. On top of that, to reach adaptive security, range proofs must be added. CL provides a solution which is simpler and more efficient.

It is our intention to augment our library with other flavors of CL (like the DDH-f based variants, threshold decryption or Gaussian distributions for randomness sampling), as well as more complex cryptographic protocols that rely on class groups. It has been widely tested and can be used to implement class group cryptography, and more generally for computations in ideal class groups of imaginary binary quadratic fields.

Detailed Roadmap and Results:

In Section 2, we give some background on class groups of imaginary quadratic fields. In Section 3 we present a unified view of the CL framework for designing linearly homomorphic encryption schemes from groups of unknown order that contain a subgroup where the discrete logarithm problem is easy. We provide generic schemes and their security, in particular a generic compact variant that was previously only described in a particular case. In Section 4, we review instantiations of the CL framework within class groups with some improvements compared to previous works. In particular, we simplify the handling of large messages and apply the compact variant to more cases as implemented in our library. We also give a guide to select the best variant of CL if one wants a linearly encryption scheme homomorphic modulo an integer M of a certain bitsize without any particular property on the form of M . Then, we give specific theorems that explicitly describe the representation of elements of the subgroups where discrete logarithms are easy, giving the mathematical foundations of some optimizations of our implementation. In Section 5, we focus on specific points of the implementation. First, the speed up of the arithmetic of class groups, then we show how to combine some known exponentiation methods from the context of elliptic curves in order to obtain the highest speed-ups for the instantiations of CL in class groups. Finally, we give algorithms specific to the subgroup where discrete logarithms are easy, in particular we give important improvements when the order of this group is a power of a prime, and more generally when the order is large by showing that we can work with quadratic integers instead of quadratic forms. In the last section, Section 6, we give benchmarks of the implementation of several linearly homomorphic encryption schemes: two from the CL framework for class groups, homomorphic modulo a prime q and 2 k , and the Paillier and Camenisch-Shoup encryption, homomorphic modulo an RSA integer N . These benchmarks highlight the improvements previously mentioned.

We give here a high level overview of class groups of imaginary quadratic fields. See for instance [START_REF] Buchmann | Binary Quadratic Forms: An Algorithmic Approach[END_REF][START_REF] Cox | Primes of the Form x 2 + ny 2 : Fermat, Class Field Theory, and Complex Multiplication[END_REF] for a comprehensive treatment.

Quadratic Fields, Orders and Class Groups

Imaginary quadratic fields are extensions of degree 2 of Q that can be written as

K = Q( √ D)
where D < 0 is a square free integer. To such a field is attached an integer, called fundamental discriminant and denoted ∆ K , that is defined as

∆ K := D if D ≡ 1 (mod 4) and ∆ K := 4D otherwise.
The ring O ∆ K of algebraic integers in K, also called the maximal order, can be written as

Z[ω K ] where ω K = (∆ K + √ ∆ K )/2. One can define special subrings of O ∆ K , called orders, associated to a non fundamental discriminant ∆ ℓ := ℓ 2 ∆ K where ℓ is called a conductor. The order O ∆ ℓ of conductor ℓ is the ring Z[ℓω K ], it has index ℓ in O ∆ K .
To each discriminant ∆ (fundamental or not), one can associate a finite abelian group, called the ideal class group and denoted Cl(∆) defined as the quotient of the group of (invertible fractional) ideals of O ∆ by the subgroup of principal ideals. The order of this group is called the class number and denoted h(∆).

One has h(∆) close to |∆| in general and one can compute its number of bits in polynomial time using the analytic class number formula (cf [START_REF] Mccurley | Cryptographic key distribution and computation in class groups[END_REF]). However, the full value of h(∆) is only known to be computable from ∆ in sub-exponential time L 1/2 (|∆|). As a result, these groups have been extensively used in the past decade to implement cryptographic protocols based on groups of unknown order, as they can be generated with a public coin setup: It is sufficient to generate the integer ∆ to use these groups. This is in contrast to the group of invertible elements of Z/N Z for which one needs a trusted setup to generate an RSA integer N , in order to keep its factorization secret, and thus the order of the group unknown. Another feature used by cryptographic applications is that discrete logarithms in Cl(∆) are also hard to compute (again only subexponential time algorithms with complexity L 1/2 (|∆|) are known, see [START_REF] Biasse | Security estimates for quadratic field based cryptosystems[END_REF] for instance).

Elements and Group Law

Elements of Cl(∆) can be represented in a compact form. One can define a system of representatives of the classes with the notion of reduced ideals. Ideals are of the form aZ

+ -b+ √ ∆ 2
Z, where a, b ∈ N and a and b are smaller than |∆| when the ideal is reduced. As a result, one needs log 2 (|∆|) bits to represent an element of the class group and this can be reduced to 3/4 log 2 (|∆|) using a recent technique proposed in [START_REF] Dobson | Trustless unknown-order groups[END_REF]. Combined with the fact that the best known attacks against cryptographic problems in class groups are of complexity L 1/2 (|∆|) instead of L 1/3 (N ) for factoring based schemes, this leads to bandwidth improvement for cryptographic applications.

The group law corresponds to product of ideals followed by a reduction operation to find the unique reduced ideal of the class. In practice, the group law is computed using the language of positive definite binary quadratic forms. Let a, b, c be three relatively prime integers such that a > 0 and ∆ = b 2 -4ac, we will denote f := (a, b, c) the primitive positive definite binary quadratic form over the integers, f (X, Y ) = aX 2 + bXY + cY 2 of discriminant ∆. One can define an equivalence relation on forms from the action of SL 2 (Z). The class group Cl(∆) is actually isomorphic to the set of forms modulo this equivalence relation. Moreover there is an explicit correspondence between ideals and forms: the class of the form (a, b, c) corresponds to the ideal aZ

+ -b+ √ ∆ 2
Z. The definition of the unique representative of the class is more natural when working with forms: it is the reduced form (a, b, c), which satisfies -a < b ⩽ a, a ⩽ c and if a = c then b ⩾ 0.

The group law is implemented using Gauss' composition of forms and a reduction algorithm for forms devised by Lagrange. More efficient algorithms have been proposed by Shanks to compute the group law, NUCOMP and NUDUPL, where a partial reduction is applied during composition ( [START_REF] Shanks | On Gauss and composition I, II[END_REF]). Our library represents elements of the class group Cl(∆) as triplets of integers corresponding to reduced binary quadratic forms and implements Shank's algorithms (see Section 5).

Maps between Class Groups

We have seen that from a fundamental (square free) discriminant ∆ K , one can define a class group Cl(∆ K ) associated with the ring of integers O ∆ K . Moreover, from ∆ K one can define a non fundamental discriminant ∆ ℓ := ℓ 2 ∆ K and a class group Cl(∆ ℓ ) associated with the suborder O ∆ ℓ ⊂ O ∆ K . This inclusion of the orders actually translates into a relation on the class groups Cl(∆ f ) and Cl(∆ K ). First one defines a map on the level of the ideals. A nonzero ideal I of O ∆ ℓ is said to be prime to ℓ if I +f O ∆ ℓ = O ∆ ℓ . Then the map I → IO ∆ K is an isomorphism from the group of ideals of O ∆ ℓ prime to ℓ to the group of ideals of O ∆ K prime to ℓ. This map and the inverse map are explicit and can be computed efficiently knowing the conductor ℓ (see [START_REF] Hühnlein | A cryptosystem based on non-maximal imaginary quadratic orders with fast decryption[END_REF]Algo. 2,[START_REF] Attema | Vector commitments over rings and compressed σ-protocols[END_REF]). By passing to the quotient, we obtain a surjection φ ℓ : Cl(∆ ℓ ) ↠ Cl(∆ K ). Studying the kernel of this map, one obtains, for ∆ K < -4, ([26, Theorem 7.24]) the formula

h(O ∆ ℓ ) = h(O ∆ K ) • ℓ • p|ℓ 1 - ∆ K p 1 p .
The instantiation of the CL framework to design linearly homomorphic encryption schemes in class groups heavily relies on this formula and on the fact that the discrete logarithm problem can be easy in ker φ ℓ for appropriate choices of ∆ K and ℓ. We will see this in more details in Section 4 with a precise characterization of the elements of this kernel.

Squares and Square Roots

A last important property of class groups for cryptography concerns squares and square root computations. Knowing the factorization of the discriminant ∆, it is possible to determine in polynomial time if an element of Cl(∆) is a square and compute its square roots ( [START_REF] Lagarias | Worst-case complexity bounds for algorithms in the theory of integral quadratic forms[END_REF]). The situation is somewhat similar to Z/N Z for an RSA integer N = pq where one can compute the values of the Legendre symbol relative to p and q to determine if an element is a square. For class groups, genus theory defines various characters that play the role of these symbols, depending on the specific form of the discriminant. Genus theory is of crucial importance in the instantiation of the CL framework modulo 2 k . We refer the interested reader to [21, Subsection 2.3] for more details.

The CL Framework

In this section, we present the generic framework introduced in [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF] and refined in [START_REF] Tucker | Functional encryption and distributed signatures based on projective hash functions, the benefit of class groups[END_REF] to design linearly homomorphic encryption schemes.

Let M be an integer. In a nutshell, in the CL framework, a setup generates a large cyclic group G of unknown order that contains a subgroup F of order M where the discrete logarithm problem is easy. The index of that subgroup in the larger group is dictated by the security level. Moreover, G will be isomorphic to

F × H where H is the subgroup of G of M -th powers.
This construction makes it possible to instantiate various linearly homomorphic variants of the Elgamal cryptosystem where the plaintexts space is the additive group (Z/M Z, +). A public key is of the form pk = h sk where h is a generator of H and a ciphertext of a plaintext m is of the form (h r , f m pk r ) where f is a generator of F . As the discrete logarithm problem is easy in F , decryption à la Elgamal in the exponent can recover m without restriction on its size. The second component of the ciphertext uses the decomposition F × H: the plaintext is encoded as an element of F and masked by an element of H. As we shall see, the security of this scheme is based on the difficulty of an Hard Subgroup Membership problem: deciding if a random element of G is an element of H.

In previous works that expose a generic presentation of the CL framework, the plaintexts space was restricted to prime order groups. In this work, we expose the CL framework together with the design of a generic linearly homomorphic encryption scheme and its security, with minimal hypotheses on the integer M .

This allows to capture many more concrete instantiations based on class groups: for instance the CL-HSM q scheme introduced in [START_REF] Castagnos | Practical fully secure unrestricted inner product functional encryption modulo p[END_REF], homomorphic modulo an odd prime q, but also variants modulo q k and modulo a product of primes as analyzed in [START_REF] Das | Improved efficiency of a linearly homomorphic cryptosystem[END_REF], and the recent scheme of [START_REF] Castagnos | Threshold linearly homomorphic encryption on Z/2 k Z[END_REF] homomorphic modulo 2 k . As we shall see, this generalized framework is not limited to class groups. It also encompasses derivatives of the Paillier cryptosystem such as the Camenisch and Shoup's encryption scheme, homomorphic modulo an RSA integer N . In this case, G is a subgroup of (Z/N 2 Z) × , and the hard subgroup membership problem correspond to recognizing N -th powers, the problem defined by Paillier's Decisional Composite Residuosity assumption (DCR) from [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF] (see Remark 1 below for details).

Compared to the original exposition of the framework of [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF] based solely on the DDH assumption, we take advantage of the HSM assumption from [START_REF] Castagnos | Practical fully secure unrestricted inner product functional encryption modulo p[END_REF] which provides more efficient and versatile schemes (notably, these schemes are related to hash proof systems as exposed in [START_REF] Tucker | Functional encryption and distributed signatures based on projective hash functions, the benefit of class groups[END_REF]). Moreover, in the last subsection, we generalized to any message space, the so-called compact variant introduced in [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF] and analyzed in [START_REF] Thyagarajan | Efficient CCA timed commitments in class groups[END_REF] that produces more compact ciphertexts.

Generic definition and properties

Let us now introduce the algebraic structure and the properties required to build a CL scheme.

Definition 1 (Setup CL -Adapted from Def. 3.1 of [START_REF] Tucker | Functional encryption and distributed signatures based on projective hash functions, the benefit of class groups[END_REF]). Let λ be a security parameter and M be a positive integer. Let G be a commutative group of unknown order M • s, for some s that depends on λ, and which admits a cyclic subgroup F = ⟨f ⟩ of order M . We require gcd(M, s) = 1, although the index [ G : F ] = s should be hard to compute. Yet, we need to know an upper bound s ≥ s. Let h = x M for some random element x ∈ G.

A setup for the CL framework for M is a pair of algorithms (Gen CL , Solve DL ) such that:

-Gen CL takes as input 1 λ and outputs public parameters pp :

= (s, f, h, extra)
where extra encodes necessary information to efficiently compute in G, -Solve DL is a deterministic polynomial time algorithm for computing discrete logarithms in F .

The following proposition clarifies the structure of the group used for cryptographic purposes.

Proposition 1. Let g = f • h, and let G be the cyclic subgroup of G generated by g. Then, denoting H = {x M ; x ∈ G}, we have ⟨h⟩ = H and G ≃ F × H.

Proof. Let y ∈ H. We have y = (g α ) M = f αM • h αM = h αM since f has order M . Thus H ⊂ ⟨h⟩. Conversely, denoting s the order of h, β :≡ M -1 (mod s) and x := g β , one as x M = g βM = h βM = h, so h ∈ H and ⟨h⟩ = H. Finally, since the orders of f and h are coprime, we have G ≃ F × H.

⊓ ⊔

As said above, the encryption schemes that we present in the following sections exploit the cyclic subgroup G by hiding with a random element of H the plaintext messages encoded in F , using a technique à la Elgamal. However, contrary to the standard Elgamal scheme defined in a group of known prime order, in the instantiations of our framework the order of G will remain unknown (to anyone), and there will be no way to efficiently recognize valid encodings of elements of this cyclic group. This can be problematic for applications involving malicious participants (like CCA secure encryption schemes, zero knowledge proofs and multi-party computation). However, in general, elements of the group G will be easy to recognize, which will be sufficient for applications. For example, this permits to design an efficient zero knowledge argument of knowledge for ciphertexts well-formedness: the verifier will begin by checking that elements are in G, and it will then be possible to link the soundness of the argument with a computational assumption in G (cf. [15, Subsection 3.1]).

Assumption

The generic encryption scheme that follows the framework from Def. 1 relies on the hard subgroup membership assumption related to the direct product of Proposition 1: distinguishing between elements of H and arbitrary elements of G. In Definition 2, we give the formal definition of this generic assumption, called HSM CL,M , for any integer M . Note that this generalizes the HSM assumption from [START_REF] Castagnos | Practical fully secure unrestricted inner product functional encryption modulo p[END_REF], which was made for M = q, an odd prime (we take u [START_REF] Castagnos | Practical fully secure unrestricted inner product functional encryption modulo p[END_REF], but it infers a negligible difference 1/q as the bitsize of q is larger than the security parameter to ensure that q is prime to ŝ in concrete instantiations). This generic assumption also generalises the HSM 2 k assumption from [START_REF] Castagnos | Threshold linearly homomorphic encryption on Z/2 k Z[END_REF] made for M = 2 k . As said above, this is also a generalization of the DCR assumption (see Remark 1 below).

$ ← -(Z/qZ) × instead of u $ ← -(Z/qZ) in
Notation 1 (Distribution D H ) In the following, given a generator h of a cyclic group H, we will denote D H a distribution over the integers such that the distribution {h x , x ← D H } is at distance less than δ D H (λ) from the uniform distribution in H for some negligible function δ D H .

Knowing an upper bound s on the order of H, this distribution can be instantiated efficiently from a folded uniform distribution or from a folded discrete Gaussian distribution (see [54, Subsection 2.7.1]).

Definition 2 (HSM CL,M assumption). Let λ be a security parameter, M be a positive integer and Setup CL = (Gen CL , Solve DL ) be a setup for the CL framework for M . Let A be a PPT algorithm, its advantage for the HSM CL,M problem is defined as:

Adv HSM CL,M A (λ) := Pr b = b * : pp = (s, f, h, extra) ← Gen CL (1 λ ), x ← D H , u $ ← -(Z/M Z) × , b $ ← -{0, 1}, z 0 := f u h x , z 1 := h x , b * ← A(pp, z b , Solve DL (•)) -1/2
For a positive integer M , The HSM CL,M problem is δ HSM CL,M -hard for Setup CL if for all PPT algorithm A, its advantage Adv HSM CL,M A (λ) ⩽ δ HSM CL,M (λ). The HSM CL,M assumption holds for Setup CL if the HSM CL,M problem for Setup CL is δ HSM CL,M -hard and δ HSM CL,M is negligible.

Algorithm 1: KeyGen

Input: pp = (s, f, h, extra) generated by Gen CL Result: (pk, sk) - 1 sample sk $ ← -DH 2 pk := h sk 3 return (pk, sk) Algorithm 2: Encrypt Input: pp, pk, m ∈ Z/M Z Result: ciphertext (c1, c2) - 1 sample r $ ← -DH 2 c1 := h r 3 c2 := f m pk r 4 return (c1, c2) Algorithm 3: Decrypt Input: pp, sk, (c1, c2) Result: m ∈ Z/M Z - 1 a := c2 • c -sk 1 2 return Solve DL (pp, a) Algorithm 4: EvalAdd Input: pp, pk, (c1, c2), (c ′ 1 , c ′ 2 ) Result: ciphertext (c ′′ 1 , c ′′ 2 ) - 1 c ′′ 1 := c1 • c ′ 1 2 c ′′ 2 := c2 • c ′ 2 3 sample r $ ← -DH 4 return (c ′′ 1 • h r , c ′′ 2 • pk r ) Algorithm 5: EvalScal Input: pp, pk, (c1, c2), α Result: ciphertext (c ′ 1 , c ′ 2 ) - 1 c ′ 1 := c α 1 2 c ′ 2 := c α 2 3 sample r $ ← -DH 4 return (c ′ 1 • h r , c ′ 2 • pk r )
Fig. 1. Generic linearly homomorphic encryption scheme modulo M

LHE under HSM CL,M

We describe in Figure 1 the generic linearly homomorphic encryption scheme modulo M that follows from the CL framework, and prove its security in Theorem 2.

Theorem 2. Let Setup CL = (Gen CL , Solve DL ) be a setup for the CL framework for an integer M . The resulting linearly homomorphic encryption scheme modulo M of Figure 1 is indcpa under the HSM CL,M assumption for Setup CL .

Proof. Let A be an adversary against the indistinguishability of the scheme. We describe a sequence of indistinguishable games which starts from the ind-cpa experiment Game 0 and finishes with a game where the ciphertext statistically hides the challenge bit b ⋆ . In the following, we denote by S i the event "adversary

A outputs b = b ⋆ in Game i".
In the first game Game 1, the only modification is the distribution of secret key sk: It is sampled according to the distribution D G instead of D H .

The difference from A's view is therefore the distribution of pk = h sk . With the notation of Proposition 1, D G is a distribution over the integers such that the distribution {x mod M s : x ← D G } is δ D G -close to the uniform distribution in {1, . . . , M s}, where s is the order of H. Since s divides M s, sampling sk according to D G yields also a distribution δ D G -close to the uniform in {1, . . . , s}, and by the triangular inequality, we have

Pr[S 1 ] -Pr[S 0 ] ≤ 2δ D G .
In the second game Game 2, the challenge ciphertext is computed using the secret key. Namely, c 1 := h r and c 2 := f m b ⋆ c sk 1 where r ← D H . Though the challenge ciphertext is computed differently, its distribution is in fact unchanged as c sk

1 = h rsk = pk r . Hence, Pr[S 1 ] = Pr[S 2 ].
In the third game Game 3, an integer u is sampled uniformly at random in (Z/M Z) × and c 1 is computed as c 1 = f u h r . By reduction to the HSM CL,M assumption, we have

Pr[S 3 ] -Pr[S 2 ] ≤ δ HSM CL,M .
In Game 3, we have

c 2 = f m b ⋆ c sk 1 = f m b ⋆ +u•sk pk r .
From an information theoretic point of view, using the direct product of Proposition 1, the adversary learns m b ⋆ + u • sk mod M from c 2 . Moreover, it gets u mod M from c 1 , but only sk mod s from pk. Since sk is close to uniform modulo M s, and M and s are coprime, sk mod M is uniform and independent from sk mod s. Therefore, as u is invertible modulo M , u • sk acts as a perfect one time pad for the message m b ⋆ and we get

Pr[S 3 ] = 1 2 •
Combining the above probability equations concludes the proof. ⊓ ⊔ Remark 1. This generic construction of a linearly homomorphic encryption introduced to cover the CL family of cryptosystems actually also captures Camenisch and Shoup's encryption scheme from [START_REF] Camenisch | Practical verifiable encryption and decryption of discrete logarithms[END_REF] (a linearly homomorphic encryption can be obtained from their encryption protocol by removing the last component of the ciphertext, which brings non-malleability). It involves an RSA modulus N = pq, for two safe primes p and q, and the message space is Z/N Z (M = N with our notations). The group G is the subgroup of (Z/N 2 Z) × of squares, H is the subgroup of the N -th powers, and F is the subgroup of order N generated by 1 + N . In this case the HSM CL,M assumption corresponds to the Paillier's DCR assumption from [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]. We provide in our library an implementation of this encryption scheme (CamenischShoup class) and give comparison in Section 6. Our implementation benefits from all improvements of Section 5.2 that also apply to this setting.

A compact variant

The ciphertexts of the generic linearly homomorphic encryption scheme of Figure 1 use two elements of the group G. The element c 2 = f m pk r needs to be in G ⊂ G in order to use the direct product G ≃ F × H of Proposition 1. However, c 1 is an element of the subgroup H, and H is isomorphic to the quotient group G/F . Moreover, in all known implementations of the CL framework, this quotient group is isomorphic to a group whose elements can be represented with a more compact representation than the elements of G.

In this subsection, we present a compact variant of the scheme of Figure 1 that benefits from this observation. To this end, we first enrich the setup of Definition 1 in order to add some properties: We consider a group Γ and a surjection G → Γ of kernel F . These objects always exist by taking Γ = G/F and the canonical surjection, but we further require that Γ has an explicit and compact representation of elements.

These extra properties and this variant were originally proposed in [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF] for the specific M = q an odd prime, and presented as a fast variant. The security of this variant was then analyzed in [START_REF] Thyagarajan | Efficient CCA timed commitments in class groups[END_REF], still presented as a fast variant. However, if this variant used to be fast compared to an encryption scheme that follows the original CL framework based on the DDH assumption, it is no longer the case compared to optimized implementation of schemes based on the HSM CL,M assumptions, as suggested by our benchmarks of Section 6. But this variant is still interesting for applications where the bandwidth is a critical issue as it leads to schemes with only a slight computational overhead due to the exponentiation to the power M and significantly reduces the size of ciphertexts. As a consequence we prefer the term compact variant in this work.

Definition 3 (Setup CL C ). Let λ be a security parameter and M be a positive integer and Setup CL = (Gen CL , Solve DL ) a setup for the CL framework for M . Let Γ be a group and π : G → Γ be a surjective map with kernel F .

We say that Setup CL C is a setup for the compact CL framework, if we have the following additional properties:

one can compute in Γ in deterministic polynomial time; the representation of elements of Γ is more compact than the representation of elements of G; one can evaluate π in polynomial time; given an element ω ∈ Γ , one can efficiently lift it in G, i.e., compute an element ω ℓ ∈ π -1 (ω).

The algorithm Gen CL C still outputs pp := (s, f, h, extra), where extra encodes both the necessary information to efficiently compute in G and Γ . Proof. This is a generalization of the proof of [19, Lemma 3] that we include for completeness. First ψ is well defined: if ω (1) ℓ , ω

(2) ℓ ∈ π -1 (ω) are two distinct pre-images of ω then there exists an element x ∈ F such that ω

(1) ℓ = xω (2)
ℓ , and (ω

(1) ℓ ) M = (ω (2) ℓ ) M as F is of order M . Moreover it is easy to see that ψ is a morphism. Consider ω in Γ such that ψ(ω) = ω M ℓ = 1 in G, with ω ℓ ∈ π -1 (ω). Applying π gives π(ω ℓ ) M = ω M = 1 in Γ . Now
observe that Γ is of order ŝ (as G has order M • s and π is a surjection with kernel of order M ). Moreover, ŝ is prime to M so ω = 1 ∈ Γ , so the map is injective. Eventually, ψ is computable in polynomial time as composition of operations computable in polynomial time. Concerning the map ψ : Γ ≃ H: firstly the restriction of π to H is injective. Moreover, denoting s the order of h, s is prime to M so γ = π(h) M = π(h M ) generates a group Γ of the same order s. Moreover, as ψ(γ) = h M 2 ∈ H and ψ is injective, we get that ψ : Γ ≃ H.

⊓ ⊔

We describe in Figure 2 the compact variant of the scheme of Figure 1. The public key and the first element of the ciphertext are now elements of Γ instead of G. We then use the map ψ of Proposition 2 in order to generate the element of H that hides f m in the second element of the ciphertext. The unnatural choice of γ = π(h) M instead of π(h) is a generalization of a trick introduced in [START_REF] Thyagarajan | Efficient CCA timed commitments in class groups[END_REF] that makes the security proof go trough. Proof. We proceed with a sequence of games as in the proof of Theorem 2, starting with the ind-cpa experiment in Game 0.

In Game 1, the public key is computed as follows: first sample sk ′ $ ← -D H and set pk = π(h) sk ′ .

We still have pk = π(h) M sk = γ sk for some sk defined modulo s, the order of h, since gcd(s, M ) = 1. Moreover, sk and sk ′ follow the same distribution modulo s. Therefore, the distribution of the public key is unchanged,

Pr[S 0 ] = Pr[S 1 ].
In Game 2, we change the distribution of sk ′ : it is sampled from D G instead of D H . As in the first step of the proof of Theorem 2, one has

Pr[S 2 ] -Pr[S 1 ] ≤ 2δ D G .
In Game 3, we set z := h r ′ for r ′ $ ← -D H and compute the challenge ciphertext as follows:

c 1 = π(z) and c 2 = f m b ⋆ z sk ′ .
Again, there exists r such that

c 1 = π(h) r ′ = π(h) M r = γ r . Moreover, c 2 = f m b ⋆ h sk ′ r ′ . But ψ(pk r ) = ψ(π(h) sk ′ r ) = h sk ′ M r = h sk ′ r ′ = z sk ′ as M r ≡ r ′ Algorithm 6: KeyGen Input: pp = (s, f, h, extra) generated by Gen CL C Result: (pk, sk) - 1 γ := π(h) M ; append γ to pp 2 sample sk $ ← -DH 3 pk := γ sk 4 return (pk, sk) Algorithm 7: Encrypt Input: pp, pk, m ∈ Z/M Z Result: ciphertext (c1, c2) - 1 sample r $ ← -DH 2 c1 := γ r 3 c2 := f m ψ(pk r ) 4 return (c1, c2) Algorithm 8: Decrypt Input: pp, sk, (c1, c2) Result: m ∈ Z/M Z - 1 a := c2 • ψ(c -sk 1 ) 2 return Solve DL (pp, a) Algorithm 9: EvalAdd Input: pp, pk, (c1, c2), (c ′ 1 , c ′ 2 ) Result: ciphertext (c ′′ 1 , c ′′ 2 ) - 1 c ′′ 1 := c1 • c ′ 1 2 c ′′ 2 := c2 • c ′ 2 3 sample r $ ← -DH 4 return (c ′′ 1 • γ r , c ′′ 2 • ψ(pk r ))
Algorithm 10: EvalScal

Input: pp, pk, (c1, c2), α Result: ciphertext (c ′ 1 , c ′ 2 ) - 1 c ′ 1 := c α 1 2 c ′ 2 := c α 2 3 sample r $ ← -DH 4 return (c ′ 1 • γ r , c ′ 2 • ψ(pk r ))
Fig. 2. Generic compact linearly homomorphic encryption scheme modulo M (mod s). Therefore, c = (γ r , f m b ⋆ ψ(pk r )) is a genuine ciphertext of m b ⋆ for the public key pk with the correct distribution:

Pr[S 3 ] = Pr[S 2 ].
In Game 4, we now set z := f u h r ′ with u sampled uniformly at random in (Z/M Z) × . By reduction to the HSM CL,M assumption, we have

Pr[S 4 ] -Pr[S 3 ] ≤ δ HSM CL,M . In Game 4, we have c 2 = f m b ⋆ z sk ′ = f m b ⋆ +u•sk ′ h sk ′ r ′
and the only information on sk ′ known by the adversary is sk ′ modulo s (from pk). As in the last step of the proof of Theorem 2, one has sk ′ mod M uniform and as u is invertible modulo M , u • sk acts as a perfect one time pad for the message m b ⋆ and we get

Pr[S 4 ] = 1 2 •
Combining the above probability equations concludes the proof.

⊓ ⊔ 4 Instantiation in Class Groups

In this section, we present instantiations of the CL framework in class groups, for plaintexts spaces Z/M Z where M = 2 k and M = q k where q is an odd prime, of bitsize larger than the security parameter. The case 2 k was recently proposed in [START_REF] Castagnos | Threshold linearly homomorphic encryption on Z/2 k Z[END_REF]. For the case q k , the generator for k = 1 was originally proposed in [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF] and a generalization for k > 1 was only suggested in that work. This generalization was then developed in [START_REF] Das | Improved efficiency of a linearly homomorphic cryptosystem[END_REF]. These two works focused on the DDH version of the CL framework, whereas we are interested in schemes based on the HSM CL,M assumption. Moreover [START_REF] Das | Improved efficiency of a linearly homomorphic cryptosystem[END_REF] also consider the case of small odd primes q and product of different odd primes. We do not consider the case of small odd primes, as it is required that q is large in order to have q prime to the class number with overwhelming probability for the ind-cpa proof to go through when working with the HSM CL,M assumption. Note that this property is also needed in many security proofs of applications of the DDH variant. Products of odd primes could also be obtained in our setting, by using Chinese remaindering during the computation of the discrete logarithm for decryption. It may also be possible to consider cases of even numbers such as 2 k q but the generation process would be very technical for limited application interest.

In the next subsection we describe the generators for M = 2 k and M = q k already given in [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF][START_REF] Das | Improved efficiency of a linearly homomorphic cryptosystem[END_REF][START_REF] Castagnos | Threshold linearly homomorphic encryption on Z/2 k Z[END_REF] with some changes in order to follow the framework of the previous section. Moreover we unify the presentation of several variants. Firstly we show that these generators are all compatible with the compact variant of Subsection 3.4. This variant was previously only known to be compatible with size of the message space M = q. Secondly, we simplify the exposition by presenting generators independent of the size of M , where as previous works imposed condition on the size of M or treated differently the case of large M 's.

Then, in Subsections 4.2 and 4.3, we show that it is possible to optimize computations of exponentiations and discrete logarithms in the subgroup F . As we will see in Section 5, this gives speedup, particularly in the context of plaintexts spaces of orders q k and 2 k with large k's. This will also improve dramatically the computation of discrete logarithms in the case of large M 's.

Generators for the CL framework in class groups

Case M = q k Algorithm 11 implements the generator Gen CL for Setup CL for M = q k where q is an odd prime, of bitsize larger than the security parameter. We denote η(λ) the bitsize of a fundamental discriminant ∆ K such that the computation of the class number h(∆ K ) and computation of discrete logarithms in Cl(∆ K ) takes at least 2 λ operations (see Table 2 for concrete sizes). A bound B such that B ⩽ h(∆ K ) < 2B can be computed in polynomial time, under the Algorithm 11: Gen CL-HSM q k Input: 1 λ , k, q a µ bits prime with µ ⩾ λ Result: pp -1 if µ ≥ η(λ) then 2 p := 1 if q ≡ 3 (mod 4) or else take the smallest prime p such that pq ≡ 3 (mod 4) and q p = -1 3 else 4 sample p a random η(λ) -µ bits prime such that 5 pq ≡ 3 (mod 4) and q p = -1 6 end 7 ∆K := -pq, ∆ q k := q 2k ∆K and G := Cl(∆ q k ) 2 8 compute s an upper bound on the order of Γ := Cl(∆K ) 2 9 sample t in G and set h := t q k 10 f := (q 2k , q k , 1-∆ K

4

) in G 11 return pp := (s, f, h, extra := (∆K , q, k))

extended Riemann hypothesis, using the analytic class number formula (cf [START_REF] Mccurley | Cryptographic key distribution and computation in class groups[END_REF]). The bitsize of B is expected to be η(λ)/2.

The algorithm first computes a fundamental discriminant ∆ K = -q or ∆ K = -pq where p is another prime, with ∆ K ≡ 1 (mod 4) and ∆ K of bitsize at least η(λ). The additional requirement on the Legendre symbol ensures that the group of squares Γ := Cl(∆ K ) 2 has odd order ŝ, where ŝ = h(∆ K ) or h(∆ K )/2 depending if ∆ K = -q or ∆ K = -pq (see [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF]). From the Cohen-Lenstra heuristics, gcd(q, ŝ) = 1 with overwhelming probability as q is a µ-bit prime with µ ⩾ λ.

This computation of ∆ K is done in order to have ∆ K of the minimal size with the constraints that q|∆ K and ∆ K is large enough to meet the security level. Moreover, we do not set an upper bound on the plaintexts space size: For instance, for k = 1, [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF] supposed that q was not too large to ensure an easy computation of discrete logarithms in F , and proposed another process, called the "large message variant", for large q's. We here proposed a unified view of these two settings (see Subsection 4.3 for the consequences on the computation of discrete logarithms in F ).

We then denote G = Cl(∆ q k ) 2 the group of squares of Cl(∆ q k ). It has order ŝq k and gcd(q k , ŝ) = 1 with overwhelming probability. The subgroup F generated by f := (q 2k , q k , 1-∆ K

4

) has order q k (we prove this in Theorem 5 as this does not seem to have been formally proven elsewhere). This subgroup is the kernel of the surjection φ q k from Cl(∆ q k ) to Cl(∆ K ). Note that F is contained in Cl(∆ q k ) 2 as F has odd order.

The description of the polynomial time algorithm that computes discrete logarithms in F is deferred in Subsection 5.4: Algorithm 13. It contains several new optimizations to compute in F , introduced in the next subsections.

One can recognize elements of G as it is possible to recognize squares given the factorization of the discriminant. Note that Algorithm 11 is a public coin algorithm: we can publish the randomness used to generate the parameters.

Algorithm 11 also implements a generator for Setup CL C by setting Γ := Cl(∆ K ) 2 . Indeed, elements of Cl(∆ K ) 2 have shorter representations than those of Cl(∆ q k ) 2 : this saves 3/2 • k log 2 (q) bits using the compression of [START_REF] Dobson | Trustless unknown-order groups[END_REF]. The homomorphism φ q k between the two class groups can be restricted from Cl(∆ q k ) 2 to Cl(∆ K ) 2 and its kernel is still F , so it plays the role of the map π in Setup CL C . If ω ∈ Cl(∆ K ) 2 , one can find a pre-image by φ q k by computing [I ∩ O ∆ q k ] for I an ideal prime to q in the class ω. This can be done efficiently using [START_REF] Hühnlein | A cryptosystem based on non-maximal imaginary quadratic orders with fast decryption[END_REF]Algo. 2].

Case M = 2 k Algorithm 12 implements a generator for Setup CL for M = 2 k . This is the original algorithm proposed in [START_REF] Castagnos | Threshold linearly homomorphic encryption on Z/2 k Z[END_REF], with a restriction on the choice of the primes p and q to ease both exposition and implementation. The overall idea of the generator is similar to the case q k with the notable change that the factorization of ∆ K must be kept secret in order to prevent an adversary from computing square roots and recognizing squares, which would break the ind-cpa security of the encryption scheme. We thus choose primes p and q of bitsize η ′ (λ) where η ′ (λ) denotes the bitsize of N such that the best algorithms for factoring N := pq take 2 λ operations (again, see Table 2 for concrete sizes). As a result the coins of the algorithm can not be given to an adversary. The algorithm that computes discrete logarithms in F is similar to the q k case, as we will see in Subsection 5.4.

Algorithm 12: Gen CL-HSM 2 k

Input: 1 λ , k ⩾ 1 Result: pp -1 sample two random distinct η ′ (λ) bits primes p, q such that (p mod 8, q mod 8) ∈ {(3, 5), (5, 3)} 2 N := pq 3 ∆K := -8N , ∆ 2 k+1 := 2 2k+2 ∆K and G := Cl(∆ 2 k+1 ) 2 4 compute s an upper bound on the order Γ := Cl(∆K ) 2

sample t in G and set

h := t 2 k 6 f := (2 2k , 2 k+1 , 1 -∆K ) ∈ G 7 return pp := (s, f, h, extra := (∆K , k))
We now prove that this algorithm also implements a generator for Setup CL C , which was not shown in [START_REF] Castagnos | Threshold linearly homomorphic encryption on Z/2 k Z[END_REF]. The situation is however a little bit intricate compared to the case q k . We still consider for π the restriction of φ 2 k+1 from G := Cl(∆ 2 k+1 ) 2 to Γ := Cl(∆ K ) 2 . However the kernel of φ 2 k+1 is now larger than F , it is of order 2 k+1 and ker φ 2 k+1 ̸ ⊂ G. Actually, F = ker φ 2 k+1 ∩ G. If ω ∈ Cl(∆ K ) 2 , computing a pre-image ρ by φ 2 k+1 : ρ := [I ∩ O ∆ q k ] for I an ideal prime to 2 may give an element which is not in G, as φ -1

2 k+1 ({ω}) = x • ker φ 2 k+1 where x ∈ G.
This can be checked and solved thanks to genus theory (we refer the reader to [START_REF] Castagnos | Threshold linearly homomorphic encryption on Z/2 k Z[END_REF] for background on genus theory for this specific class group). As in the proof of [START_REF] Castagnos | Threshold linearly homomorphic encryption on Z/2 k Z[END_REF]Theorem 1], one can prove that the f = (2 2k+2 , 2 k+2 , 4-∆ K

4

) is in ker φ 2 k+1 \F (actually, this is a generator of ker φ 2 k+1 ). This element f has genus (1, 1, -1, 1) for the respective characters (χ p , χ q , χ -4 , χ 8 ). Moreover, elements of ker φ 2 k+1 \ F are in the same genus. Elements of F are squares, so their genus is (1, 1, 1, 1). Now let us see how to finish our lift. We have similarly half the elements of φ -1 2 k+1 ({ω}) in G, and half of genus (1, 1, -1, 1). Back to our element ρ, one can check the value of χ -4 efficiently without knowing the factorization of N . If this gives 1, ρ is a square and we are done. Otherwise, we multiply it by f in order to get a square. In both case, we have obtained an element of φ -1 2 k+1 ({ω}) which is a square, so an element of π -1 ({ω}).

Note that one can not recognize elements of G nor of Γ . The situation is similar to elements of Jacobi symbol 1 and squares of Z/N Z. Here we can only recognize if elements have genus (1, 1, 1, 1) or (-1, -1, 1, 1).

Concrete linearly homomorphic encryption schemes When using the generator Gen CL-HSM q k with the generic constructions of Figure 1 (resp. Figure 2), one gets an encryption scheme linearly homomorphic modulo q k for an odd prime q, denoted CL-HSM q k (resp. CL C -HSM q k for the compact variant). Likewise, the generator Gen CL-HSM 2 k gives a scheme homomorphic modulo 2 k , denoted CL-HSM 2 k (resp. CL C -HSM 2 k for the compact variant).

On the selection of the plaintext space size In most of the cases, the choice of the generator will be guided by the application, as a specific form of M will be needed. However, it might be the case that one needs a linearly encryption scheme homomorphic modulo an integer M of a certain bitsize ν, without any particular property on M .

We discuss here on the best choice of the generator in this context in order to optimize ciphertexts size. First, we summarize in Table 1, the bitsize of the ciphertexts for these schemes using the compression technique of [START_REF] Dobson | Trustless unknown-order groups[END_REF]. The different sizes of ciphertexts for the q k variants comes from the fact that when log(q) ⩽ η(λ), Algorithm 11 chooses a fundamental discriminant ∆ K of minimal size η(λ) to ensure security, where as when log(q) > η(λ), ∆ K will have approximately the same bitsize as q.

To optimize ciphertext expansion, for plaintexts of bitsize ν < λ, only the 2 k setting is possible. With CL C -HSM 2 k using k = ν, the expansion is:

3 2 η ′ (λ) ν + 6 ν + 3 2 • Scheme Size of plaintexts Size of ciphertexts Condition CL-HSM q k k log q 3 2 η(λ) + 3k log(q) λ ⩽ log(q) ⩽ η(λ) CL C -HSM q k k log q 3 2 η(λ) + 3 2 k log(q) λ ⩽ log(q) ⩽ η(λ) CL-HSM q k k log q (3k + 3 2 ) log(q) η(λ) < log(q) CL C -HSM q k k log q 3 2 (k + 1) log(q) η(λ) < log(q) CL-HSM 2 k k 3 2 η ′ (λ) + 3k + 15 2 - CL C -HSM 2 k k 3 2 η ′ (λ) + 3 2 k + 6 - Table 1.

Ciphertext sizes of class groups based schemes

For plaintexts of bitsize ν with λ ⩽ ν, CL C -HSM q k is the best choice. One can get a ciphertext expansion of 3 2

η(λ) ν + 3 2 •
This tends to 3/2 when the bitsize of messages tends to infinity, for a fixed level of security. The choice of q and k to meet this expansion depends on the value of ν. For λ ⩽ ν ⩽ η(λ), one can use any combination of the prime q and power k such that ν = k log q and log q > λ. Using k = 1 and a prime q of bitsize ν is thus the simplest choice in this case. For plaintexts of bitsize ν > η(λ), one has to choose the prime q and the integer k such that log q = ν/k ⩽ η(λ).

Note that as η ′ (λ) > η(λ), the 2 k setting is less interesting for large messages, in terms of compactness.

Explicit isomorphisms for ker φ

For CL-HSM q k , the cyclic group F of size M = q k in which the discrete logarithm should be easy is exactly the kernel of the surjective homomorphism φ q k from Cl(∆ q k ) to Cl(∆ K ). For CL-HSM 2 k , the cyclic group F is of size M = 2 k and is a subgroup of index 2 of the kernel of the surjective homomorphism φ 2 k+1 . To be able to compute discrete logarithms in F , we will show how to represent its elements in a manner that allows very fast computations. The main tool used in previous works to analyse these kernels is the fact that there exists an effective isomorphism with some quotient of the ring of integers. This is summarized in the following theorem. Theorem 4. Let ∆ K < -4 be a fundamental negative discriminant, ℓ be a positive integer and ∆ ℓ = ℓ 2 ∆ K . Then, the kernel of the surjective homomorphism

φ ℓ : Cl(∆ ℓ ) ↠ Cl(∆ K ) is isomorphic to G ℓ := (O ∆ K /ℓO ∆ K ) × / (Z/ℓZ) × .
Moreover, let α represent an equivalence class in G ℓ . Denote by (a, b, c) a form corresponding to the ideal αO ∆ K , where a is coprime to ℓ. Then the class of ker φ ℓ corresponding to α is the class of the (non-necessarily reduced) form (a, bℓ, cℓ 2 ).

Proof. See [START_REF] Cox | Primes of the Form x 2 + ny 2 : Fermat, Class Field Theory, and Complex Multiplication[END_REF]Prop. 7.20,Prop. 7.22,Th. 7.24] for the theoretical side. See [37, Prop. 2], [38, Algo. 1-3] and [8, Prop 2.9] for the computational side.

⊓ ⊔

We then apply this theorem to get a correspondence between the representation of elements of F in the q k setting with quadratic integers.

Theorem 5. Let k, q, ∆ K , ∆ q k , f and F be generated as in Algorithm 11. Then, the set {1 + t √ ∆ K | t = 0 or t odd in -q k < t < q k } has size q k and is a complete set of representatives of G q k . The explicit group isomorphism of Theorem 4 is given by

G q k → F 1 + t ∆ K → q 2j , uq j , u 2 -q 2(k-j) ∆ K 4 ,
where j = 0 and u = 1 for t = 0 and j = k -val q t and u = t q k-j -1 mod 2q j with centered remainder otherwise.

The generator f of F corresponds to 1 + √ ∆ K , its order is q k . Moreover, all the forms are reduced if and only if

q 2k ≤ 1-∆ K 4 .
Proof. The proof is similar to [19, Proposition 1] that proves the case k = 1.

For t = 0, the ideal generated by 1 is the maximal order O ∆ K . When lifted in O ∆ q k using [38, Algo. 2], it corresponds to the ideal Z +

q k + √ ∆ q k 2
Z. This ideal corresponds to the form (1, -q k , c) with c such that its discriminant is ∆ q k , which is equivalent to the reduced form (1, 1, (1 -∆ q k )/4).

Let t be an odd integer in -q k < t < q k . Using [8, Prop 2.9], we obtain that the ideal generated by 1+t

√ ∆ K 2 , an element equivalent to 1+t √ ∆ K in G q k , is aZ+ b+ √ ∆ q k 2
Z by setting a = 1-t 2 ∆ K 4 and b = t∆ K mod 2a with centered remainder. As a is coprime with q, we can use [START_REF] Hühnlein | A cryptosystem based on non-maximal imaginary quadratic orders with fast decryption[END_REF]Algo. 2] to lift it in O ∆ q k and we obtain the ideal aZ

+ bq k + √ ∆ q k 2 Z. It corresponds to the form ( 1-t 2 ∆ K 4 , -t∆ K q k , -q 2k ∆ K ).
Let u and v be the Bézout coefficients of the two coprime integers t q k-j and 2q j :

t q k-j u + 2q j v = 1.
We can always choose u such that -q j < u < q j . Finally, we apply the transformation matrix

2q j u -t q k-j v
of determinant 1 to the form and obtain (q 2j , q j u, u 2 -q 2(k-j) ∆ K

4

). The fact that the form f = (q 2k , q k , 1-∆ K

4

) corresponds to 1 + √ ∆ K comes from the case t = 1. We then prove that f is a generator of F . As the order of

F is q k , it is sufficient to prove that 1 + √ ∆ K q k-1 ̸ = 1.
We prove this by induction by showing that for i ⩾ 2,

1 + ∆ K q i-1 ≡ 1 + q i-1 ∆ K (mod q i ). For i = 2, 1 + √ ∆ K q = q j=0 q j √ ∆ K j .
As q|∆ K and q| q j for j = 1, . . . , q-1, we get 1 + √ ∆ K q ≡ 1 + q √ ∆ K (mod q 2 ). Now suppose that there exists a quadratic integer α such that 1

+ √ ∆ K q i-1 = 1 + q i-1 √ ∆ K + αq i = 1 + q i-1 ( √ ∆ K + αq).
We then rise this equality to the power q, and using again binomial expansion, one obtains 1

+ √ ∆ K q i ≡ 1 + q i √ ∆ K (mod q i+1
) as for j ⩾ 2, q j(i-1) ≡ 0 (mod q i+1 ) as i ⩾ 2.

⊓ ⊔

Now we use Theorem 4 to get a correspondence between the representation of elements of F in the 2 k setting with quadratic integers. Theorem 6. Let k, ∆ K , ∆ 2 k+1 , f and F be generated as in Algorithm 12. Then, the set

{1 + τ √ -2N | 0 ≤ τ < 2 k+1
} has size 2 k+1 and is a complete set of representatives of G 2 k+1 . We will consider the subset

{1 + τ √ -2N | 0 ≤ τ < 2 k+1 , τ even} = {1 + t √ ∆ K | 0 ≤ t < 2 k }.
The explicit group isomorphism of Theorem 4 restricted to this subset of representatives is given by

G 2 k+1 → F 1 + t ∆ K → 2 2j , u2 j+1 , u 2 -2 2(k-j) ∆ K ,
where j = 0 and u = 0 for t = 0 and j = k -val 2 t and u = t 2 k-j -1 mod 2 j with centered remainder for 0 < t < 2 k .

The generator f of F corresponds to 1 + √ ∆ K , its order is 2 k and it is a square. Note that all the forms are reduced if and only if 2 2k ≤ 1 -∆ K .

Proof. For t = 0, the ideal generated by 1 is the maximal order O ∆ K . When lifted in O ∆ 2 k+1 using [START_REF] Hühnlein | A cryptosystem based on non-maximal imaginary quadratic orders with fast decryption[END_REF]Algo. 2], it corresponds to the ideal Z +

2 k+1 + √ ∆ 2 k+1 2
Z. This ideal corresponds to the form (1, -2 k+1 , c) with c such that its discriminant is ∆ 2 k+1 , which is equivalent to the reduced form (1, 0, -

∆ 2 k+1 4
). Let t be an integer in 0 < t < 2 k . Using [8, Prop 2.9], we obtain that the ideal generated by 1 + t

√ ∆ K is aZ + b+ √ ∆ K 2
with a = 1 -t 2 ∆ K and b = t∆ K mod 2a with centered remainder. As a is odd, we can use [START_REF] Hühnlein | A cryptosystem based on non-maximal imaginary quadratic orders with fast decryption[END_REF]Algo. 2] to lift it in O ∆ 2 k+1 and we obtain the ideal aZ

+ b2 k+1 + √ ∆ 2 k+1 2
. It corresponds to the form (a, -b2 k+1 , c) with c such that the discriminant is ∆ 2 k+1 . It is equivalent to (1 -t 2 ∆ K , -t∆ K 2 k+1 , -2 2k ∆ K ). Let u and v be the Bézout coefficients of the two coprime integers t 2 k-j and 2 j : t 2 k-j u + 2 j v = 1. We can always choose u such that -2 j-1 < u < 2 j-1 . Finally, we apply the transformation matrix

2 j u -t 2 k-j v
of determinant 1 to the form and obtain (2 2j , 2 j+1 u, u 2 -2 2(k-j) ∆ K ).

The fact that the form f = (2 2k , 2 k+1 , 1 -∆ K ) corresponds to 1 + √ ∆ K comes from the case t = 1. The fact that it is a square of order 2 k was proven in [21, During decryption, one need to compute the discrete logarithm of a given element f t ∈ F in basis f . For more efficiency, we move the problem into G q k or G 2 k+1 . In these groups, the discrete logarithms can be easily computed with O(k) operations (see Subsection 5.4 for implementation details). However, in order to use this method we need to find the representative of f t as given in Theorems 5 and 6. This is direct if this representative is reduced (i.e, if q k or 2 k is small enough compared to |∆ K | as stated in the theorems). Otherwise, we use [START_REF] Hühnlein | Towards practical non-interactive public key cryptosystems using non-maximal imaginary quadratic orders[END_REF]Algo. 1] to invert the maps of Theorems 5 and 6. This last case corresponds to the large message variant of [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF]. In this work, the form f t was lifted in another non-maximal order, chosen to make some adaptation of the representative forms reduced. This involves an exponentiation to the power q k or 2 k . Our new method in this case is much faster. As a result, the distinction between the two cases becomes irrelevant from the user's point of view: the cost of computing the representative is completely negligible in both cases.

Algorithmic Perspective

In this section, we present some algorithmic aspects of our implementation in BICYCL of the arithmetic of class groups of imaginary quadratic fields and of the different cryptosystems described in the previous sections.

We first give some details of our implementation choices for the composition of quadratic forms and for exponentiation, from which can benefit any cryptographic protocols based on class groups. This can be found in the classes QFI and ClassGroup of BICYCL.

We then focus on the exponentiation and discrete logarithm computations in the subgroup F defined in Section 4 in the context of the CL encryption schemes.

Composition of quadratic forms

For the composition and reduction of quadratic forms, we implemented Shanks' NUCOMP algorithm [START_REF] Shanks | On Gauss and composition I, II[END_REF] (as well as NUDUPL for the computation of the square of a form). At the lowest level, our implementation makes extensive use of GMP's arithmetic functions [START_REF] Gmp | The GNU Multiple Precision Arithmetic Library[END_REF], with the exception of the partial extended GCD. Partial extended GCD is a core component of NUCOMP. It performs the same steps as a classical extended GCD but terminates once the computed remainders reach a given bound. In the context of NUCOMP and NUDUPL, a common choice for this bound is ∆ 1/4 . We implemented this function by modifying one of the extended GCD algorithms implemented in GMP: Lehmer's variant 4 . GMP implementation of Lehmer's variant uses the two most-significant words to approximate the successive quotients appearing in the extended GCD algorithm. We modify the algorithm to stop it once the remainders were below the targeted bound. The Flint library [START_REF] Hart | FLINT: Fast Library for Number Theory[END_REF] also implements the Lehmer's variant for its function xgcd partial but only uses the most-significant word to approximate the quotient. The PARI/GP library [START_REF][END_REF], in its function parteucl implementing the partial extended GCD, performs a full Euclidean division at each step.

In Figure 3, we compare our implementation of NUDUPL to the implementation found in Flint (via the add-on Antic library) and PARI/GP. We also compare our implementation to libqform [START_REF] Sayles | libqform[END_REF] which is the library used to implement several CL variants from [START_REF] Das | Improved efficiency of a linearly homomorphic cryptosystem[END_REF]. Finally, we compare to the implementation that won the Chia VDF competition [START_REF] Rijmen | Chia verifiable delay function competition[END_REF], whose goal was to perform successive NUDUPL as fast as possible. Our implementation improves all these libraries, for all cryptographic sizes of discriminant. Comparisons for NUCOMP gave very similar timings.

Exponentiations in the class group

The Encrypt and Decrypt Algorithms involve exponentiations of quadratic forms. For Encrypt, both h and pk are known in advance, which opens the door to various optimization strategies at the cost of some precomputations and extra storage. For Decrypt, one needs to compute and invert the form c sk 1 . Since c 1 is not known in advance, the above optimizations do not apply. In class groups, we note that inverting a form is virtually free5 . Thus, one can take advantage of signed-digit representations and the numerous algorithms developed in the context of elliptic curves. We detail the algorithms implemented in our library in the next paragraphs.

Encrypt -fixed-basis exponentiations: Recall that the Encrypt algorithm, described in Algorithm 2, outputs a pair (c 1 , c 2 ) with c 1 = h r and c 2 = f m pk r . The special, easier case of the computation of f m will be explain in Subsection 5.3. Let us focus on the other two exponentiations. Our code evaluates h r and pk r in parallel using the same algorithm6 , which mixes a variant of the width-2 comb method [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF] and Solinas' Joint Sparse Form (JSF) [START_REF] Solinas | Low-weight binary representations for pairs of integers[END_REF].

Let us assume that r is a 2n-bits integer. In the comb method, the scalar r is divided into w chunks of 2n/w bits each. The bits of r are then scanned w at a time. In our implementation, the 2n-bit scalar r is split in half (i.e. w = 2) so that r = r 0 + 2 n r 1 . Hence, we get h r = h r0 × h r1 n with h n = h 2 n . Since h is fixed, and the size of r is bounded, one can precompute h n offline. Hence, this reduces a 2n-bits exponentiation to an n-bits double-exponentiation which is implemented using Straus-Shamir's trick [START_REF] Straus | Addition chains of vectors (problem 5125)[END_REF]. Using minor extra-storage for h n , one can thus divide by 2 the number of calls to NUDUPL.

As already observed, one can take advantage of algorithms based on signeddigit representations. In particular, Solinas' Joint Sparse Form [START_REF] Solinas | Low-weight binary representations for pairs of integers[END_REF] allows to jointly rewrite the pair (r 0 , r 1 ) of n-bit exponents using digits in {-1, 0, 1} so that the double-exponentiation requires exactly n NUDUPL and n/2 NUCOMP on average. For computing

h r0 × h r1 n , each call to NUCOMP involve either h, h n , h × h n , h × h -1
n or their respective inverse. Note that there is no need to store both a form and its inverse.

Finally, since the cost of NUDUPL is almost identical to that of NUCOMP, it is advantageous to adapt to our context the variant of the comb method presented in [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]Algo 3.45], even for w = 2. This approach further divides the We have implemented several linearly homomorphic encryption schemes in our library BICYCL. First, the different linearly homomorphic encryption schemes based on class groups, which is the main purpose of this library, namely the schemes CL-HSM q k , CL-HSM 2 k and their compact variants (as CL HSMqk and CL HSM2k classes).

For comparisons, we have also implemented Paillier ( [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]) which is the most popular linearly homomorphic encryption scheme (Paillier class). As shown in Remark 1, the underlying LHE of Camenisch-Shoup encryption ( [START_REF] Camenisch | Practical verifiable encryption and decryption of discrete logarithms[END_REF]), based on the same security assumption than Paillier, can be viewed as an instantiation of our generic construction of Section 3. Moreover, several optimizations detailed in Subsection 5.2 for computing exponentiations can be applied to Camenisch-Shoup, as encryption also uses fixed-basis exponentiations, whereas this is not possible for Paillier. For fair comparison, we have therefore also implemented this scheme in BICYCL (CamenischShoup class).

In this section, we provide timings for CL-HSM q k , CL-HSM 2 k and compare to Paillier and Camenisch-Shoup. All timings are performed on a standard laptop (Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz). The results are averages over 100 operations.

Parameters sizes Table 2 gives the sizes of fundamental discriminants and RSA moduli for various security levels that we used in BICYCL (available in the RSA modulus bitsize and discriminant bitsize methods of the SecLevel class). These sizes come from the estimations done in [START_REF] Biasse | Security estimates for quadratic field based cryptosystems[END_REF], commonly used for implementation of class group based cryptography. Note that in particular, the discriminant ∆ K for CL-HSM 2 k is defined as -8N with N following the first column. The discriminants for CL-HSM q k are given by the second column. They are smaller than RSA moduli as the best algorithms to compute discrete logarithms in class groups are in L 1/2 instead of L 1/3 for factoring integers.

Comparisons of LHE schemes

We then give in Table 3 a comparison between four cryptosystems. For CL-HSM q k , we choose to give timings for the case k = 1, therefore denoted CL-HSM q , and q of bitsize twice the security parameter. This choice is driven by applications where the linearly encryption scheme is used to encrypt integers modulo the order of an elliptic curve, like in [START_REF] Castagnos | Two-party ECDSA from hash proof systems and efficient instantiations[END_REF]. For CL-HSM 2 k , we use k = 64 independently of the security level, as the main purpose of this scheme is to provide a threshold LHE homomorphic modulo 2 k compatible with applications to multi-party computations that closely match data manipulated by a CPU. where the bitsize of q is twice the security level and k = 64

This table shows substantial improvements for the schemes based on class groups compared to previous implementations. Thanks to our many improvements, at the level of group operations and at the level of exponentiations, our experiments show that the gain we have on the size of the parameters allows to compensate the additional cost of quadratic forms arithmetic compared to traditional arithmetic in Z/N Z.

For instance, when comparing CL-HSM q 's encryption with Paillier's encryption, CL-HSM q is faster for all security levels. This is in contrast with previous implementations like [START_REF] Castagnos | Two-party ECDSA from hash proof systems and efficient instantiations[END_REF] whose implementation was only faster than Paillier's encryption for large security parameters. In details, CL-HSM q 's encryption is 1.5 times faster for 112-bits security, 2.7 times faster for 128-bits security, 7 times faster for 192-bits security and 13.8 times faster for 256 bits security. Note that two threads are used to perform the two exponentiations in parallel during encryption for CL-HSM q k , CL-HSM 2 k and Camenisch-Shoup's encryption. This is useless for Paillier's encryption. Our implementation of Paillier gives similar encryption times than the one from Relic [START_REF] Aranha | RELIC is an Efficient LIbrary for Cryptography[END_REF].

Decryption of CL-HSM q is faster than Paillier's starting from 128 bits of security. Overall this shows that CL-HSM q is highly competitive compared to Paillier. optimizations for the exponentiations in Camenisch-Shoup make also this scheme faster than Paillier. However this is at the cost of very large ciphertexts (Camenisch-Shoup needs two elements of Z/N 2 Z against one for Paillier).

Concerning setup and key generation, once the class group is computed, key generation in CL-HSM q is the fastest, since it of a single exponentiation in the class group, whereas Paillier's key generation needs to generate large primes, and Camenisch-Shoup's consists of an exponentiation in a group that is significantly larger.

The CL-HSM 2 k scheme gives encryption timings that are globally intermediate between Camenisch-Shoup and Paillier and a worse decryption time. This is due to the fact that security is based on factoring, so we do not benefit from a small discriminant. However, timings are in the same order of magnitude compared to the other factoring based schemes.

Concerning ciphertext sizes, for 112-bits security and a q of 224 bits, ciphertexts for CL-HSM q are 1.5 (resp. 3) times shorter than Paillier's (resp. Camenisch-Shoup's). For 192-bits of security, the difference is of course much higher: ciphertexts for CL-HSM q are 2.3 (resp. 4.7) times shorter than Paillier's (resp. Camenisch-Shoup's). Note that the elements that are transmitted are compressed using the technique from [START_REF] Dobson | Trustless unknown-order groups[END_REF] (see Section 2) and the time of encryption (resp. decryption) includes compression (resp. decompression) which corresponds to less than 1% of the time.

Compact variants As shown in Table 1, with the compact variants we gain 3/2 log(q) bits for CL-HSM q and 3/2 k bits for CL-HSM 2 k on the size of the ciphertexts. Concretely, for the choices made in Table 3, this means that CL C -HSM q has ciphertexts of bitsizes 2358, 3125 or 5973 depending of the security level. For CL C -HSM 2 k , we get ciphertexts of 3174, 4710 or 11622 bits. This reduction on the size comes with an additional cost for computing the lift during encryption and decryption (essentially an exponentiation to the power M ). Our benchmark shows that depending on the security level CL C -HSM q adds 35% to 55% more time for encryption and 4% to 15% for decryption. So for applications where bandwidth is crucial but encryption time is less sensitive, this variant is adequate. For CL C -HSM 2 k the overheads are smaller as M = 2 k is also smaller: around 6% to 9% more time for encryption and 3% to 6% for decryption.

Comparisons with previous implementations for CL We run BICYCL on the same machine used for the benchmark of [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF] (which describe the original DDH variant of CL). Our experiments shows that the CL-HSM q implementation of BICYCL improves encryption time by a factor 20, and decryption by a factor 5. Compared to the timings announced in [START_REF] Das | Improved efficiency of a linearly homomorphic cryptosystem[END_REF] (still for the original DDH variant of CL) that were run on a machine with a slightly more powerful CPU, get an improvement of factor 7 for encryption and 2 for decryption 7 .

For CL-HSM 2 k , running BICYCL on the same machine used for the benchmark of [START_REF] Castagnos | Threshold linearly homomorphic encryption on Z/2 k Z[END_REF] shows that we improve the encryption time by a factor 9, and decryption by a factor 4.

Overall, these results show that we obtain improvements not only because of the improvement of the basic arithmetic has shown in Figure 3, but especially thanks to our tailored implementation of the exponentiations.

Proposition 2 .

 2 With the notation of Definitions 1 and 3, the mapψ : Γ → G s.t. ω → ω M ℓ , where ω ℓ ∈ π -1 (ω), is an injective morphism, computable in polynomial time. Let γ = π(h) M and Γ := ⟨γ⟩. With the notation of Proposition 1, ψ gives an isomorphism Γ ≃ H.

Theorem 3 .

 3 Let Setup CL C = (Gen CL C , Solve DL ) be a setup for the compact CL framework for an integer M . The resulting linearly homomorphic encryption scheme modulo M of Figure2is indcpa under the HSM CL,M assumption for Setup CL C .

Fig. 3 .

 3 Fig.3. Comparison for the NUDUPL operation for different libraries. All timings were computed using one thread of a Intel i7-8665U CPU at 1.90GHz. For each discriminant size, NUDUPL is executed 10000 times for 10 different random discriminants.

  Theorems 5 and 6 are used to speedup computation in the subgroup F . During encryption, one need to compute f m , where f is the generator of the group F and m in a non-negative integer less than M . This computation can be done without using quadratic forms.Instead one computes 1 + √ ∆ m in G q k (resp. G 2 k+1 ),then Theorem 5 (resp. Theorem 6) is used to get the form corresponding to this element. It will be the quadratic form corresponding to f m . Implementation details are given in Subsection 5.3.

	Theorem 1].	⊓ ⊔
	4.3 Computations in F

Table 2 .

 2 Security level, λ Size of RSA modulus N , η ′ (λ) Size of ∆K for CL-HSM q k , η(λ) Size in bits of N and ∆K for each security level.

	112	2048 bits	1348 bits
	128	3072 bits	1827 bits
	192	7680 bits	3598 bits
	256	15360 bits	5971 bits

Table 3 .

 3 Comparison between CL-HSMq, Paillier and Camenisch-Shoup and CL-HSM 2 k

	Sec. level		CL-HSMq	Paillier	Camenisch-Shoup CL-HSM 2 k
		ciphertext	2694 bits	4096 bits	8192 bits	3272 bits
		setup	0.300 s	-	0.051 s	0.571 s
	112	keygen	0.011 s	0.039 s	0.012 s	0.019 s
		encrypt	4.39 ms	6.57 ms	3.00 ms	7.78 ms
		decrypt	9.70 ms	6.56 ms	7.17 ms	17.7 ms
		ciphertext	3509 bits	6144 bits	12288 bits	4808 bits
		setup	0.586 s	-	0.178 s	1.78 s
	128	keygen	0.019 s	0.121 s	0.036s	0.044 s
		encrypt	7.68 ms	20.9 ms	8.62 ms	17.4 ms
		decrypt	17.8 ms	20.8 ms	21.8 ms	40.1 ms
		ciphertext	6549 bits	15360 bits	30720 bits	11720 bits
		setup	7.65 s	-	5.55 s	27.3 s
	192	keygen	0.072 s	5.63 s	0.374 s	0.319 s
		encrypt	28.2 ms	198 ms	108 ms	128 ms
		decrypt	67.3 ms	199 ms	205 ms	300 ms
		ciphertext	10493 bits	30720 bits	61440 bits	23240 bits
		setup	72.0 s	-	53.4 s	263 s
	256	keygen	0.216 s	79.6 s	2.25 s	1.77 s
		encrypt	84.9 ms	1169 ms	624 ms	691 ms
		decrypt	202 ms	1168 ms	1262 ms	1600 ms

https://github.com/Chia-Network/vdftrack1results

For more details on GMP implementation of Lehmer's variant, see GMP documentation https://gmplib.org/manual/Lehmer_0027s-Algorithm

[START_REF] Biasse | Improvements in the computation of ideal class groups of imaginary quadratic number fields[END_REF] If f = (a, b, c), then the inverse of the class of f is represented by (a, -b, c).

There does not seem to be an efficient way to exploit the fact that one raises both basis to the same power.

This comparison should be taken with caution: we did not have access to the source code of[START_REF] Das | Improved efficiency of a linearly homomorphic cryptosystem[END_REF] and could not run the benchmarks on the same machine.

Acknowledgements. We thank the anonymous reviewers for their comments in improving the exposition. This work was partially supported by the French ANR Project ANR-21-CE39-0006 SANGRIA and by the France 2030 ANR Project ANR-22-PECY-003 SecureCompute.

number of NUDUPL by 2, at the cost of (3 4 -1)/2 = 40 extra precomputed forms which can be computed with 36 calls to NUCOMP. These precomputed forms are obtained as products of forms in h ±1 , h ±1 n/2 , h ±1 n , h ±1 3n/2 , where h n/2 = h 2 (n/2) and h 3n/2 = h 2 3n/2 .

Decrypt -variable basis: The Decrypt algorithm, described in Algorithm 3, involves one exponentiation c -sk 1 where the exponent is the secret key. Contrary to the encryption algorithm, the base c 1 is not known in advance. Hence, the above techniques are not advantageous. Our implementation uses a left-to-right wNAF exponentiation with w = 7 which does not require to scan the bits of the exponents first for the NAF recoding (cf [START_REF] King | wNAF*, an efficient left-to-right signed digit recoding algorithm[END_REF]). Instead of a fixed size, one could opt for an adaptive strategy for the window width depending on the size of the discriminant. But we reckon that the gain should be very marginal.

Exponentiations in F

As described in Subsection 4.3, the computation of an exponentiation in F corresponds to computing an exponentiation of 1 + √ ∆ K in G M . Efficient exponentiations of quadratic integers can be done using Lucas sequences as

where U n (P, Q) and V n (P, Q) are the Lucas sequences of the first and second kind and Q is such that ∆ K = P 2 -4Q. Terms of Lucas sequences can be easily computed using the fact that

Note that we only need to compute 0 1

For CL-HSM q k , we use P = 1 and Q = 1-∆ K

4

. The values U n (P, Q) and V n (P, Q) are computed modulo q k by computing the power of the above matrix. Then, we compute t = U n (P, Q) (V n (P, Q))

-1 mod q k and obtain the representative 1 + t √ ∆ K (note that V n (P, Q) is guaranteed to be invertible modulo q k ). Then we can use Theorem 5 to find the corresponding form.

For CL-HSM 2 k , we use P = 2 and Q = 1 -∆ K . The values U n (P, Q) and V n (P, Q) are computed modulo 2 k by computing the power of the above matrix.

Then, we compute t = U n (P, Q) Vn(P,Q) 2 -1 mod 2 k and obtain the representative 1 + t √ ∆ K (note that Vn(P,Q) 2 is guaranteed to be odd). Then we can use Theorem 6 to find the corresponding form.

Note that in the case of CL-HSM q , it is even easier to compute t as we have 1 + √ ∆ K n ≡ 1 + n √ ∆ K in G q as q divides ∆ K , as originally remarked in [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF].

Discrete logarithms in F

The first step to efficiently compute discrete logarithms in F is to move the problem into G M as described in Section 4.3. It remains to compute the discrete logarithm of an element 1 + t √ ∆ K in basis 1 + √ ∆ K in that group. We first describe the case M = q k . Given 1 + t √ ∆ K we compute the digits m i in basis q of the unknown exponent m starting by the least significant one. At first look, the process is similar to Pohlig-Hellman method. However, contrary to this method, which would calculate at step i and exponentiation to the power q k-i for i = 1, . . . , k -1, our algorithm only uses an exponentiation to the power q at each step.

To obtain this more efficient method, we use the fact, noted at the end of the previous subsection, that m 0 ≡ t (mod q). Then, let i > 0 and assume that the values of m j , for 0 ≤ j < i, were already computed. We will consider 1 + t i √ ∆ K , defined as a representative of the element

we can compute m i as t i /q i mod q. This process is formalized in Algorithm 13.

Algorithm 13: Solve

The case M = 2 k is similar to the case M = q k : the bits of the unknown exponent m are computed one at a time. It is even simpler to implement as the exponentiation by m i is trivial to compute as m i can only be 0 or 1.