Guilhem Castagnos

Fabien Laguillaumie

Ida Tucker

Threshold Linearly Homomorphic Encryption

Keywords: Class groups of quadratic fields, Linearly homomorphic encryption, Threshold cryptography

come

Introduction

Encryption protocols are the core of any communication architecture. They provide confidentiality, defined in terms of semantic security or indistinguishability of encryptions by Goldwasser and Micali [START_REF] Goldwasser | Probabilistic encryption[END_REF]. On top of this security property, many applications require an "algebraic" property of the encryption scheme, in the sense that an operation on the ciphertexts translates into an operation on the underlying plaintexts. An encryption protocol possessing this property is said to be homomorphic. While fully homomorphic encryption schemes allow any operation to be evaluated on ciphertexts, protocols that only allow linear transformations are also very useful and significantly more efficient.

The first linearly homomorphic encryption appears in Goldwasser and Micali's seminal work [START_REF] Goldwasser | Probabilistic encryption[END_REF]. Then a line of factoring based schemes was developed, culminating with Paillier's scheme [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF] which was then 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.

An alternative was proposed by Castagnos and Laguillaumie using class groups of quadratic fields in [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF]. This allows to work with the additive group Z/qZ as a message space where q is an odd prime, whereas Paillier and Damgård and Jurik' schemes work modulo N s where N is an RSA integer. The case of message space Z/q s Z for an odd prime q, and more generally that of Z/N Z with N = q si i for odd primes q i , were sketched in the conclusion of [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF]. This was further analyzed in [START_REF] Das | Improved efficiency of a linearly homomorphic cryptosystem[END_REF] which gives a detailed construction and implementation. As a consequence, the Castagnos-Laguillaumie scheme allows to construct message spaces of any odd order N (with known factorization). There is a restriction however: many cryptographic applications and proofs require that this order N be relatively prime to the order of the underlying class group. This can only be ensured with high probability if each prime q i dividing N is large enough to make 1/q i negligible. Hence only relatively large values of odd integers N are possible in practice. The case of message spaces defined modulo 2 k were left open in these works.

Another elegant work, by Benhamouda, Herranz, Joye, Libert [START_REF] Benhamouda | Efficient cryptosystems from 2 k -th power residue symbols[END_REF] (refining a scheme by Joye and Libert [START_REF] Joye | Efficient cryptosystems from 2 k -th power residue symbols[END_REF]), generalizes the Goldwasser-Micali cryptosystem using 2 k -th power residue symbols, and produces efficient protocols in terms of bandwidth and speed (for both encryption and decryption). It is proven secure under the quadratic residuosity assumption for RSA moduli N = pq, where the primes p and q have a special form. The message space of their scheme is the additive group Z/2 k Z, which is a very interesting feature, especially for the purpose of multi-party computation. Indeed, it has been used by Catalano, Di Raimondo, Fiore and Giacomelli [START_REF] Catalano | MonZ 2 k a: Fast maliciously secure two party computation on Z 2 k . PKC[END_REF] to design a new 2-party protocol for secure computation over the ring Z/2 k Z. Their work follows a new line of secure computation modulo 2 k , initiated by Cramer, Damgård, Escudero, Scholl, and Xing in [START_REF] Cramer | SPD Z 2 k : Efficient MPC mod 2 k for dishonest majority[END_REF] who introduced a new information theoretic MAC that allows to authenticate messages in the ring Z/2 k Z to achieve security against malicious adversaries. This choice is driven by the fact that modern CPU computations are performed in such a ring, and it allows protocol designers to directly apply optimizations that are often expensive to emulate modulo p or N .

On the other hand, several multi-party computation protocols, starting with the pioneering work of Cramer, Damgård and Nielsen [START_REF] Cramer | Multiparty computation from threshold homomorphic encryption[END_REF], rely on threshold linearly homomorphic encryption. A (t, n)-threshold public key encryption (TPKE) scheme allows n parties to share the decryption key so that if t of them collaborate, they can decrypt ciphertexts, whereas t -1 users learn nothing about the underlying plaintext. Katz and Yung proposed a threshold variant of Goldwasser-Micali in [START_REF] Katz | Threshold cryptosystems based on factoring[END_REF], but this does not extend to a message space of order 2 k . Furthermore, it is an open problem to devise an efficient threshold variant of Benhamouda, Herranz, Joye, Libert's scheme. In a nutshell, This scheme uses an RSA integer N = pq where p ≡ 1 (mod 2 k ). A ciphertext for m ∈ Z/2 k Z is c = y m x 2 k ∈ Z/N Z for a random x, and a public y, which is a fixed non quadratic residue, with Jacobi Symbol 1. Decryption is done modulo p, by removing the 2 k -th power using an exponentiation to the power (p -1)/2 k and then finding m thanks to an easy discrete logarithm computation using Pohlig-Hellman's algorithm in the subgroup of (Z/pZ) × of order 2 k . As a result, lots of operations are done modulo the secret prime p, which prevents an efficient adaptation in a multiparty setting.

A solution would be to design an Elgamal version of this scheme, that fits the CL framework [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF] of a DDH group with an easy DL subgroup. In this framework, one works with a cyclic group G isomorphic to H ×F where H and F are subgroups of G of respective unknown order s and known order q, with q and s co-prime. The group H consists of q-th powers, and in F discrete logarithms are easy to compute. This makes it possible to encode messages m ∈ Z/qZ in f m where f is a generator of F . Then f m is hidden by a random q-th power.

To make Benhamouda et al's scheme fit the CL framework, the idea would be to use two primes p, q ≡ 1 (mod 2 k ) and encode the message in the exponent of an element f ∈ (Z/N Z) × of order 2 k both modulo p and q. A ciphertext for m could then be of the form (g r , f m pk r ), with pk = g sk . During decryption, after recovering f m , the discrete logarithm computation could then be done modulo the public N , and only one exponentiation would have to be distributed among the parties. However, this simple solution has some drawbacks due to the fact that this element f must be public and seems hard to generate without knowing the factorization. As a consequence, such a variant would rely on ad hoc security assumptions that include this element f . Moreover, it would be less efficient than the scheme that we propose in this work, at least in terms of bandwidth. Devising a variant without a trusted dealer would also be very complicated. So this question remains open: Is it possible to design an efficient threshold linearly homomorphic encryption with message space Z/2 k Z ?

Our contributions. In this work, we first propose a new linearly homomorphic encryption (LHE) scheme with message space of order 2 k that solves the aforementioned issues (Section 4). This LHE has an Elgamal structure as it follows the CL framework, with an element f of order 2 k that is used to encrypt the messages in the exponent. We emphasize that this element can be generated from public parameters. Thanks to its Elgamal shape, it can be converted into the first threshold linearly homomorphic encryption with message space Z/2 k Z. The part of the decryption which involves the secret key uses an exponentiation to that secret key in a group of unknown order. We use linear integer secret sharing schemes (LISS), introduced in [START_REF] Damgård | Linear integer secret sharing and distributed exponentiation[END_REF], to share the secret key over the integers. This allows to set up a scheme allowing any access structure for the decryption policy and in particular a threshold decryption (Section 5).

Furthermore, we suggest how to add robustness and a distributed setup to our scheme. We also sketch several application domains: multiparty computation, homomorphic secret sharing and lossy trapdoor functions (Section 6).

The security of our schemes relies on a hard subgroup membership (HSM) assumption, which is a natural adaptation of the assumption used in the CL framework. One could also design a variant based on the DDH assumption.

The setup of our schemes is flexible and allows to encrypt messages modulo 2 k for any integer k, and in particular natural choices such as k = 1, 32, 64, 128 or even larger values. We show that our schemes are efficient by reporting timings from an implementation in SageMath.

Technical Overview and Challenges. Our construction uses class groups of imaginary quadratic fields like the encryption schemes modulo an odd prime q of [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF][START_REF] Tucker | Functional encryption and distributed signatures based on projective hash functions, the benefit of class groups[END_REF]. One of the challenges is to stay within the CL framework, while working modulo a power of 2. As we will see, plugging q = 2 k does not work.

In the original framework, a class group with a cyclic subgroup of order q is generated. This is done by considering two class groups, Cl(∆ K ) with discriminant ∆ K = -pq and Cl(∆) with discriminant -pq 3 . In this case, there is a surjection from Cl(∆) to Cl(∆ K ), and the kernel of which is precisely the required subgroup of order q.

However, as usual in number theory, moving from an odd prime q to 2 or 2 k is not an easy task. Firstly, setting q = 2 k in the construction above does not always give a cyclic subgroup of order 2 k . Further difficulties arise from the fact that in class groups, knowing the factorization of the discriminant allows to compute square roots, and decide if elements are squares. And as we will see, this allows to completely break a scheme which uses an Elgamal in the exponent with a subgroup of order 2 k .

We solve this issue by constructing a discriminant from an RSA integer N of unknown factorization. But other technical reasons make the choice of this discriminant tricky, and lead to arithmetic conditions on the primes composing N (which have no negative impact in practice). We thus have to delve into the genus theory associated to class groups of quadratic fields, introduced by Gauss, to select discriminants that make it possible to securely work with the group of squares of cardinality 2 k s where s is odd (Section 3). Indeed, we need to carefully handle the fact that some genera can leak information on discrete logarithms. Controlling the 2-Sylow subgroup of Cl(∆ K ) and expliciting the shape of the kernel of the surjection from Cl(∆) to Cl(∆ K ) when the conductor is equal to 2 k allows to find a element f of the group of squares of order 2 k which does not depend on the factorization of N .

Relying on the factorization assumption implies slightly larger elements (compared to the original CL scheme), but the timings that we provide in Table 2 of Section 4.3 from a non-optimized implementation of our protocol with Sage-Math, show that the scheme is actually very efficient.

Background

Threshold public key encryption

In a threshold PKE (TPKE) scheme, the decryption key is divided into a number of key shares which are distributed to multiple decryption servers, according to a certain access structure. To decrypt a message, each server creates its own decryption share, and these shares can be publicly combined to result in a full decryption.

Definition 1. A monotone access structure on {1, . . . , n} is a non-empty collection A ⊆ {1, . . . , n} such that ∅ / ∈ A, and such that for all A ∈ A, and all sets B such that A ⊆ B ⊆ {1, . . . , n} it holds that B ∈ A. For a positive integer t < n, the threshold-t access structure T t,n is the collection of sets A ⊆ [n] for which |A| > t. The sets in A are called qualified, whereas the sets outside A which should not be able to obtain any information about the secret are called forbidden.

Definition 2 (Threshold PKE). Let P = {P 1 , . . . , P n } be a set of parties and let A be an access structure. A threshold PKE scheme for a message space M and access structure A is a tuple of PPT algorithms TPKE = (Setup, Encrypt, PartDec, FinalDec) with the following syntax.

Setup(1 λ , A) → (pp, ek, sk) Takes as input a security parameter 1 λ and an access structure A. It outputs public parameters pp, an encryption key ek, and a vector of n secret-key shares sk = (sk 1 , . . . , sk n ). Party P i is given the share sk i that allows deriving decryption shares for any ciphertext. Encrypt(ek, m) → c On input the encryption key ek and a plaintext m ∈ M, outputs a ciphertext ct. PartDec(pp, sk i , ct) → µ i ∪ ⊥ Takes as input the public parameters pp, a secretkey share sk i , and a ciphertext ct. It outputs a partial decryption share µ i . FinalDec(pp, {µ i } i∈S ) → m ∪ ⊥ Given pp and a subset S ⊂ {1, . . . , n} with decryption shares {µ i } i∈S , this algorithm outputs either a plaintext m or ⊥.

We require a TPKE scheme to satisfy the following correctness, and security requirements.

Definition 3 (Decryption correctness). We say that a TPKE scheme for an access structure A satisfies decryption correctness if for all λ, and all qualified sets S, the following holds. For (pp, ek, sk

) ← Setup(1 λ , A), ct ← Encrypt(ek, m), µ i ← PartDec(pp, sk i , ct) for i ∈ S, Pr[FinalDec(pp, {µ i } i∈S ) = m] = 1 -negl(λ).
Definition 4 (following [START_REF] Fouque | Sharing decryption in the context of voting or lotteries[END_REF]) is a classical extension of semantic security for an encryption scheme to the threshold case. The attacker actively (but nonadaptively) corrupts a set S of servers outside A, gets their secret keys, and can ask for partial decryptions of ciphertexts for which he already knows the corresponding plaintext. The idea is that partial decryptions give no information about the private keys of non-corrupted users.

Definition 4 (T-ind-cpa-security). We say a TPKE scheme for an access structure A is adaptive chosen plaintext (T-ind-cpa) secure if for any large enough λ ∈ N, and any PPT adversary A the experiments Expt A,TPKE,0 and Expt A,TPKE,1 of Fig. 1 Linearly Homomorphic Threshold Encryption. This primitive is particularly useful for applications to multi-party computation. Informally, evaluations should be correct, meaning that decryption should lead to the correct plaintext message m 1 + m 2 (resp. αm).

Linear integer secret sharing

In the threshold setting for groups of unknown orders, key generation schemes share the secret decryption key using the linear integer secret sharing (LISS) primitive of Damgård and Thorbek [START_REF] Damgård | Linear integer secret sharing and distributed exponentiation[END_REF], which is similar to linear secret sharing schemes except that it works over Z. They show that any integer span program (ISP) as defined in [START_REF] Cramer | Optimal black-box secret sharing over arbitrary Abelian groups[END_REF] can be used to build a secure LISS scheme. Roughly speaking, an ISP is specified by a matrix with integer entries, and these entries are used as coefficients in the linear combinations that produce the shares from secret and randomness. They also show that any LISS scheme can be used to build a distributed exponentiation protocol, which is what we will use in our threshold decryption.

Goal. Let P = {1, . . . , n} denote the n shareholders and D the dealer. Let A be a monotone access structure on P . The dealer D wants to share a secret s in a publicly known interval [-2 l , 2 l ] with the shareholders, such that any set A ∈ A can reconstruct s, but any set A / ∈ A gets no (or negligible) information on s.

Distributing the secret. To this end, D uses a distribution matrix M ∈ Z d×e and a distribution vector ρ = (s, ρ 2 , . . . , ρ e ) ⊤ , where s is the secret, and the ρ i 's are integers sampled uniformly at random in [-2 l0+λ , 2 l0+λ ] for 2 ≤ i ≤ e, where l 0 is a constant that is part of the description of the scheme.

The dealer D computes a vector s ∈ Z d of share units as:

s = (s 1 , . . . , s d ) ⊤ = M • ρ.
Let ψ : {1, . . . , d} → P be a surjective function. Shareholder ψ(i) is given the i-th share unit, and is said to own the i-th row in M. For a set of shareholders A ⊂ P , M A ∈ Z da×e denotes the restriction of M to the rows jointly owned by A, while d A denotes the number of these rows.

Likewise, s A ∈ Z d A denotes the restriction of s ∈ Z d to the coordinates jointly owned by the parties in A. Shareholder j's share consists of s ψ -1 (j) ∈ Z dj , so that it receives d j = |ψ -1 (j)| out of the d = n j=1 d j share units. The expansion rate µ = d/n is the average number of share units per player.

To construct LISS schemes, Damgård and Thorbek [START_REF] Damgård | Linear integer secret sharing and distributed exponentiation[END_REF] used integer span programs [START_REF] Cramer | Optimal black-box secret sharing over arbitrary Abelian groups[END_REF], which were originally used to construct black-box secret sharing which does not extend shares in the ring of integers.

Definition 6 (Integer Span Program (ISP) [START_REF] Cramer | Optimal black-box secret sharing over arbitrary Abelian groups[END_REF]). The tuple M = (M, ψ, ϵ) is called an integer span program (ISP), if M ∈ Z d×e and the d rows of M are labeled by a surjective function ψ : {1, . . . , d} → {1, . . . , n}. Finally, ϵ = (1, 0, . . . , 0) ⊤ ∈ Z e is called the target vector. The size of M is the number of rows d of M. Definition 7. Let A be a monotone access structure and let M = (M, ψ, ϵ) be an ISP. Then M is an ISP for A if for all A ⊂ {1, . . . , n} the following conditions hold:

-If A ∈ A, there is a reconstruction vector λ ∈ Z d A such that λ ⊤ • M = ϵ ⊤ . -If A / ∈ A, there exists κ = (κ 1 , . . . , κ e ) ⊤ ∈ Z e such that M A • κ = 0 ∈ Z d , and κ ⊤ • ϵ = 1.
The vector κ is called a sweeping vector for A. We also define

κ max = max A / ∈A (∥κ∥ ∞ ).
In other words, the rows owned by a qualified set must include the target vector in their span, while for a forbidden set, there must exist a sweeping vector which is orthogonal to all rows of the set, but has inner product 1 with the target vector. We also say that M computes A.

Damgård and Thorbek [START_REF] Damgård | Linear integer secret sharing and distributed exponentiation[END_REF] showed that from an ISP M = (M, ψ, ϵ) which computes the access structure A, a statistically private LISS scheme for A can be obtained with M as the share generating matrix and l 0 = l + ⌈log 2 (κ max (e -1))⌉ + 1, where l is the length of the secret.

Then LISS can be obtained from Cramer-Fehr [START_REF] Cramer | Optimal black-box secret sharing over arbitrary Abelian groups[END_REF] or Benaloh-Leichter [START_REF] Benaloh | Generalized secret sharing and monotone functions[END_REF]. Although this later case was designed to work over finite groups, Damgård and Thorbek generalized it to share integers using access structures consisting of any monotone Boolean formula. Thanks to results of Valiant [START_REF] Valiant | Short monotone formulae for the majority function[END_REF], LISS schemes can therefore be constructed for any threshold access structure. From a monotone Boolean function f , Damgård and Thorbek's technique from Benaloh-Leichter results allows binary share distribution matrices in {0, 1} d×e such that d, e = O(size(f )) and which have at most depth(f ) + 1 non-zero entries, so that each share unit has magnitude O(2 l0+λ depth(f )). Valiant's results, improved by [START_REF] Hoory | Monotone circuits for the majority function[END_REF] gives a monotone formula of size O(n 1+ √ 2 ) and depth O(log n) for the majority function (from which any threshold-t function can be built). This reduces the average share size to O(n

√ 2 (l 0 + λ + log log(n))) bits. Lemma 1 ([53, Lemma 3.1]). Let l 0 = l +⌈log 2 (κ max (e-1))⌉+1. Consider a secret to be shared, s ∈ [-2 l , 2 l ],
and ρ randomly sampled from [-2 l0+λ , 2 l0+λ ] e conditionally on ⟨ρ, ϵ⟩ = s, then the LISS scheme derived from M is private. For any arbitrary s, s ′ ∈ [-2 l , 2 l ] and any forbidden set of shareholders

A ∈ [n], the two distributions {s A = M A • ρ | ρ ← U ([-2 l0+λ , 2 l0+λ ] e ) s.t. ⟨ρ, ϵ⟩ = s}, and {s ′ A = M A • ρ | ρ ← U ([-2 l0+λ , 2 l0+λ ] e ) s.t. ⟨ρ, ϵ⟩ = s ′ } are 2 -λ close.

Class Groups

Class Groups. Given a non square integer ∆ < 0, ∆ ≡ 0, 1 (mod 4), called discriminant, the imaginary quadratic order of discriminant ∆,

denoted O ∆ is the ring Z[(∆ + √ ∆)/2].
The associated class group Cl(∆) is defined as the quotient of the group of invertible fractional ideals of O ∆ by the subgroup of principal ideals. Precise definitions of these objects can be found in e.g., [START_REF] Buchmann | Binary Quadratic Forms: An Algorithmic Approach[END_REF].

In a nutshell, the class group Cl(∆) is a finite Abelian group, with an efficiently computable group law and a compact representation of elements. Elements are classes of ideals, with a unique reduced representative. The order of Cl(∆), the class number, denoted h(∆) is close to |∆|.

Historically, with the works of Lagrange and Gauss, the class group Cl(∆) was defined using the language of positive definite binary quadratic forms of discriminant ∆. Let a, b, c ∈ Z such that a > 0 and ∆ = b 2 -4ac, we will denote for short f := (a, b, c) the positive definite binary quadratic form over the integers, f (X, Y ) = aX 2 + bXY + cY 2 . Such a form is said to be primitive if a, b and c are relatively prime. In the following, we will just call "forms" the primitive positive definite binary quadratic forms over the integers. Two forms f and g are said to equivalent if g(X, Y ) = f (AX + BY, CX + DY ) for integers A, B, C, D such that AD -BC = 1. [START_REF] Dobson | Trustless unknown-order groups[END_REF] an elegant method to reduce this representation to 3/4 log 2 (|∆|) bits.

The class group

Computations in Cl(∆) can be performed with a reduction algorithm for forms, devised by Lagrange (which corresponds to lattice reduction in dimension 2), and Gauss' composition of forms (which corresponds to product of ideals). More recently, efficient algorithms have been proposed for practical implementation by Shanks (cf. [START_REF] Jacobson | Computational aspects of nucomp[END_REF]). The neutral element of Cl(∆) is the class of the (reduced) principal form: (1, b, (b -∆)/4) where b = ∆ mod 2.

Class Group-based Cryptography. Class group cryptography dates back to the late 80s with the first key exchange in the class group of ideals of maximal orders of imaginary quadratic fields, and related protocols that can be found in Buchmann and Williams' work [START_REF] Buchmann | A key-exchange system based on imaginary quadratic fields[END_REF] or McCurley's [START_REF] Mccurley | Cryptographic key distribution and computation in class groups[END_REF]. After several years, a family of class group based cryptosystems, NICE, was designed using class groups of non-maximal orders [START_REF] Paulus | A new public-key cryptosystem over a quadratic order with quadratic decryption time[END_REF]. The area remained dormant for another decade until a serious cryptanalysis of this whole family of NICE cryptosystems was proposed [START_REF] Castagnos | On the security of cryptosystems with quadratic decryption: The nicest cryptanalysis[END_REF]. Since then, there has actually been a high regain of interest in class groups to design new advanced cryptosystems, especially for secure multi-party computation. Built upon Castagnos and Laguillaumie's linearly homomorphic encryption scheme (CL) [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF], projective hash functions relying on class groups allowed to design efficient inner product functional encryption [START_REF] Castagnos | Practical fully secure unrestricted inner product functional encryption modulo p[END_REF], 2-party and fully-threshold 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].

The main 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. For instance, [START_REF] Thyagarajan | Efficient cca timed commitments in class groups[END_REF] presented a scalable distributed randomness generator with enhanced security and transparent setup that relies on a variant of the CL encryption scheme. The verifiable random functions from [START_REF] Wesolowski | Efficient verifiable delay functions[END_REF] take advantage of an exponentiation in a group of unknown order without trusted setup, as well as accumulators in [START_REF] Lipmaa | Secure accumulators from euclidean rings without trusted setup[END_REF], and succinct noninteractive arguments of knowledge in [START_REF] Bünz | Transparent SNARKs from DARK compilers[END_REF][START_REF] Lai | Subvector commitments with application to succinct arguments[END_REF].

Another advantage is that the underlying algorithmic problems are harder that equivalent problems in (Z/N Z) × or (Z/pZ) × . Indeed, the current best known algorithms to solve the discrete logarithm problem in the class group of ideals of order of imaginary quadratic fields, or to compute the class number have a sub-exponential complexity of complexity L |∆| (1/2, o(1)) (cf. [START_REF] Biasse | Security estimates for quadratic field based cryptosystems[END_REF]). This means that elements in the class group are asymptotically smaller, and this actually matters in practice for a given security parameter. For example, a 112-bit (resp. 256-bit) security determinant will be of size 1348 bits (resp. 5971 bits), while an RSA modulus will be of size 2048 bits (resp. 15360 bits).

Genus Theory, Squares and Square Roots. We now give a quick introduction on genus theory and properties of squares of the class group. A comprehensive exposition of the subject with a historical perspective can be found in [START_REF] Cox | Primes of the Form x 2 + ny 2 : Fermat, Class Field Theory, and Complex Multiplication[END_REF]. The theory of quadratic forms was originally motivated by the representation problem: given m ∈ Z and a quadratic form f , are there integers (x, y) ∈ Z 2 such that f (x, y) = m? A first remark is that all the forms in an equivalent class represent the same numbers. Genus theory aims at characterizing primes represented by quadratic forms of a fixed discriminant ∆. A genus consists of classes of forms that represent the same classes of numbers in (Z/∆Z) × . Genera are related to squares of the class group: Gauss proved that the genus of the principal form, the principal genus, corresponds to the subgroup of squares in the class group Cl(∆). Moreover, genera can be identified by values of some characters.

Before going into more details, let us make a parallel with the well-known properties of squares in (Z/N Z) × where N = pq is an RSA integer. Given x ∈ (Z/N Z) × , there are 4 possible values for the Legendre symbols ((x/p), (x/q)) which gives a partition in 4 sets of (Z/N Z) × . One could speak of 4 "genera". The value (1, 1) corresponds to squares of (Z/N Z) which is the "genus" of 1. Given the factorization of N , one can thus identify the "genus" of an element x. But without it, one can only compute the Jacobi symbol of x. Given an element x of Jacobi symbol 1, the quadratic residuosity problem asks to decide if x is in the principal genus with symbol (1, 1) or in the genus with symbol (-1, -1) without knowing the factorization of N .

For a class group Cl(∆), the situation is similar: there are 2 µ-1 genera, where µ is related to the number of odd primes factor of the discriminant. One can define µ "assigned characters", whose joint values determine the genus (the product of all characters is always one, so we indeed have 2 µ-1 genera). The characters are for the majority Legendre symbols with respect to the odd prime factors of the discriminant. Let us describe in more details the setting that we will use to define our cryptosystem, where ∆ = -8N and N = pq is an RSA integer. In this case, where ∆ = 0 mod 4 and 2N = 2 mod 4 (see [START_REF] Cox | Primes of the Form x 2 + ny 2 : Fermat, Class Field Theory, and Complex Multiplication[END_REF]Prop. 3.11,Th. 3.15]), it holds that µ = 3, and there are 4 genera. If f is a quadratic form, the first two assigned characters are respectively

χ p (f ) := a p and χ q (f ) := a q
where a is any integer represented by f , respectively prime to p, prime to q. The third one, is

χ 8 (f ) := (-1) (a 2 -1)/8 or χ -8 := χ -4 • χ 8 (f ) := (-1) (a-1)/2 • (-1) (a 2 -1)/8 ,
depending if N ≡ 3 mod 4 or N ≡ 1 mod 4, where a is any odd integer represented by f . The genus of the class of a form f is thus identified by (χ p (f ), χ q (f ), χ 8 (f )) or (χ p (f ), χ q (f ), χ -8 (f )) depending on N modulo 4. The subgroup of squares of Cl(∆) is the subgroup of forms of genus with symbol (1, 1, 1), the three other genera have symbols (-1, -1, 1), (-1, 1, -1), (1, -1, -1).

Given the complete factorization of ∆ (thus of N ), one can identify in polynomial time the genus of an element of the class group (see also [START_REF] Lagarias | Worst-case complexity bounds for algorithms in the theory of integral quadratic forms[END_REF]Theorem 6.3]). Without it, only χ 8 or χ -8 and the Jacobi symbol relative to N , i.e., the product χ p • χ q can be computed.

The situation of elements of order ⩽ 2 of the class group is similar. In the general case, there are also 2 µ-1 such elements and there are classes of forms (a, 0, c), (a, a, c) and (a, b, a) [START_REF] Cox | Primes of the Form x 2 + ny 2 : Fermat, Class Field Theory, and Complex Multiplication[END_REF]Lemma 3.10,Prop. 3.11]). As a result, finding these elements is equivalent to factoring the discriminant. For example, the discriminant of the form (a, 0, c) is -4ac.

Computing square roots can also be done efficiently given the factorization of the discriminant [START_REF] Lagarias | Worst-case complexity bounds for algorithms in the theory of integral quadratic forms[END_REF]Theorem 6.10]. The algorithm, due to Gauss, uses reduction of ternary forms, and the factorization of ∆ is needed to extract square roots modulo ∆.

Two Classgroups. Starting with the NICE family of cryptosystems, the idea of using the relationship between two class groups has enabled many developments. Let us first consider ∆ K a fundamental negative discriminant: this means that either ∆ K ≡ 1 (mod 4) and ∆ K is square-free or ∆ K = 4m where m is squarefree and m ≡ 2, 3 (mod 4). This discriminant defines the maximal order O ∆ K of the quadratic field Q( √ ∆ K ). Now let us consider a non fundamental discriminant ∆ ℓ := ∆ K ℓ 2 where ℓ is called a conductor. Then, there exists a surjective map

φ ℓ : Cl(∆ ℓ ) → Cl(∆ K ), moreover, for ∆ K < -4, the kernel of this surjection is isomorphic to (O ∆ K /ℓO ∆ K ) × / (Z/ℓZ) × .
This isomorphism is used in [START_REF] Cox | Primes of the Form x 2 + ny 2 : Fermat, Class Field Theory, and Complex Multiplication[END_REF]Theorem 7.24] to establish that for ∆ K < -4,

h(O ∆ ℓ ) = h(O ∆ K ) • ℓ • p|ℓ 1 - ∆ K p 1 p . ( 1
)
3 A Class Group with a Cyclic Subgroup of order 2 k

In this section, we show how to generate a class group Cl(∆) that contains a cyclic subgroup of order 2 k , inspired by the CL cryptosystem of [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF], that builds a subgroup of order a prime q by using eq. 1 with a conductor ℓ = q, and a fundamental discriminant ∆ K divisible by q. Unfortunately, the situation is not as simple as setting ℓ = 2 k : as usual, working with 2 instead of an odd prime induces a lot of technicalities.

Choice for ∆ K

Let us begin with the generation of the fundamental discriminant ∆ K . Firstly, as we shall see in Subsection 3.4, we cannot reach any security in our applications if computing square roots in the class group is easy. As mentioned in Subsection 2.3 this means ∆ K must be hard to factor. As a consequence we will construct a discriminant ∆ K from an RSA integer, N = pq, which is a first difference with the CL encryption.

Secondly, we will need to work with a subgroup of Cl(∆) of odd order. This subgroup will be isomorphic to the subgroup of squares of Cl(∆ K ). The subgroup of squares has cardinality ŝ := h(∆)/2 µ-1 where 2 µ-1 is the number of elements of order ⩽ 2. If we ensure that the 2-Sylow of Cl(∆) is restricted to the elements of order ⩽ 2, then the subgroup of squares will correspond to the odd-part and ŝ will be odd as required. This is done by ensuring that elements of order 2 are not squares, thereby imposing conditions on the prime factors of ∆ K .

Several choices are possible to construct ∆ K from N . In order for the conditions on the prime p and q to be the less restrictive possible, we choose to work with a fundamental discriminant ∆ K := -8N . The next lemma gives the conditions that ensures that the 2-Sylow is restricted to elements of order 2.

Lemma 2. Consider two distinct odd primes p and q of same bit-size, with values modulo 8 and Legendre symbols chosen according to Table 1. Let N = pq, and consider the fundamental discriminant

∆ k = -8N . Then the 2-Sylow subgroup of Cl(∆ K ) is isomorphic to Z/2Z × Z/2Z. p mod 8 q mod 8 (p/q) (q/p) 1 3 -1 -1 1 5 -1 -1 3 1 -1 -1 3 5 * 3 7 -1 1 5 1 -1 -1 5 3 * 5 5 * 5 7 -1 -1 7 3 1 -1 7 5 -1 -1
Table 1. Choices of (p, q) such that the 2-Sylow of Cl(-8pq) is isomorphic to Z/2Z × Z/2Z. The star * means that there is no restriction on the values (p/q) and (p/q).

Proof. If N = pq, and ∆ k = -8N , as seen in Subsection 2.3, µ = 3, so there are 2 3-1 -1 = 3 elements of order 2 in Cl(∆ K ). Looking at forms of the type (a, 0, c) of discriminant -4ac = -8N , we find the following ones :

f 2 := (2, 0, N ); f p := (p, 0, 2q); f q := (q, 0, 2p).
By hypothesis, N > 2, 2q > p and 2p > q so these three distinct forms are reduced, and their classes gives the 3 elements of order 2 of Cl(∆ k ).

We now compute the genus of f 2 , f p and f q . For this, we need the value of χ p , χ q and χ 8 or χ -8 depending of the value of N mod 4. Let us see in details the case of f 2 . We have χ p (f 2 ) = a p where a is an integer represented by f 2 prime to p. One can choose a = 2 = f 2 (1, 0). As a result

χ p (f 2 ) = 2 p = (-1) p 2 -1 8
, which gives 1 if p ≡ 1, 7 (mod 8), and -1 if p ≡ 3, 5 (mod 8). Likewise, χ q (f 2 ) = (2/q), whose value is determined by q (mod 8).

If N ≡ 3 (mod 4), to compute χ 8 (f 2 ) we need an odd integer represented by f 2 . We can choose f 2 (0, 1) = N . We then have

χ 8 (f 2 ) = (-1) N 2 -1 8
, and again this value depends only on N mod 8. If N ≡ 1 (mod 4), we can also take N to evaluate χ -8 (f 2 ), which also depends only on N mod 8.

For f p , we use f p (0, 1) = 2q to evaluate χ p (f p ) = 2 p • q p . We also have χ q (f p ) = p q using f p (1, 0) = p, and the value of χ 8 and χ -8 are also determined using p. The genus of f p can thus be determined by the values of p mod 8 and the Legendre symbols p q and q p . Note that by the law of quadratic reciprocity, these Legendre symbols are equal if p ≡ 1 (mod 4) or q ≡ 1 (mod 4) and p q = -q p if p ≡ q ≡ 3 (mod 4). The determination of the genus of f q is similar to the one of f p by exchanging the roles of q and p.

Now in order to have a 2-Sylow subgroup isomorphic to Z/2Z × Z/2Z, f p , f q and f 2 must all not be squares, which means that their genus must not have symbols (1, 1, 1). As shown above, this only depends on the values of p, q (mod 8) and of the relative Legendre symbols of p and q. By inspection of these values, we fill the Table 1 which gives all possibilities ensuring that f p , f q and f 2 are all not squares. ⊓ ⊔

Choice for ∆

We now want to construct a non fundamental discriminant such that Cl(∆) contains a cyclic subgroup of order 2 k by using eq. 1. We will therefore consider as conductor ℓ a power of 2. As ∆ K = -8N , we get ∆ K 2 = 0, and denoting, ∆ = ℓ 2 ∆ K , the class number h(∆) = ℓh(∆ K ), i.e, the kernel of the surjection φ ℓ has order ℓ.

If we set ℓ = 2 k , we thus get a subgroup of Cl(∆) of order 2 k , and one can prove that this subgroup is cyclic, in our case where ∆ K = -8N . Unfortunately, a similar computation to that of the proof of the next theorem shows that generators of this subgroup are not squares: the character χ -4 is equal to -1. This would break all our security assumptions, as the value of this character would leak the parity of discrete logarithms.

We thus set ℓ = 2 k+1 , and as a consequence, the kernel of φ ℓ has order 2 k+1 , and we can work in its cyclic subgroup of squares, of order 2 k . Note that other choices of ∆ K depending on N lead to similar constructions.

Theorem 1. Let ∆ K = -8N with N = pq as in Lemma 2. Let ∆ = 2 2k+2 • ∆ K , then the class of f := (2 2k , 2 k+1 , 1 + 8N ) is a square of order 2 k in Cl(∆).
Proof. Let ℓ = 2 k+1 be the conductor. The strategy of the proof is as follows: we use the fact that ker φ ℓ is isomorphic to

G ℓ := (O ∆ K /ℓO ∆ K ) × / (Z/ℓZ) × .
We will exhibit a system of representatives of this quotient group, and an element of order 2 k . As the isomorphism to ker φ ℓ is explicit, we will apply it to this element to get f of the same order 2 k in Cl(∆). Then a computation of the assigned characters will show that f is a square.

The first step is to establish a system of representatives of the group G ℓ . As

∆ K = 4m, with m := -2N , O ∆ K = Z + Z √ m ≡ Z[X]/(X 2 -m) and O ∆ K /ℓO ∆ K ≡ Z/ℓZ[X]/(X 2 -m).
First observe that when ℓ = 2, we have m ≡ 0 mod ℓ and the invertible elements of O ∆ K /2O ∆ K are therefore 1 and 1 + X. For k ⩾ 0, we will then have

(O ∆ K /ℓO ∆ K ) × = a + bX, (a, b) ∈ (Z/ℓZ) × × Z/ℓZ
To get the group G ℓ , we identify a + bX with ac + bcX for c ∈ (Z/ℓZ) × . We then have the system of representatives:

{1 + bX, b ∈ Z/ℓZ} .
Now we show that 1 + 2X is of order 2 k in this group (one could prove that 1+X is of order 2 k+1 and this group is cyclic, but considering 1+2X is sufficient for our applications). For this we first prove that for k ⩾ 2,

(1 + 2X) 2 k-1 = 1 + 2 k X + 2 k X 2 ∈ Z/2 k+1 Z[X]. (2)
This can been shown by induction: the equality is clear for k = 2. Now suppose, that there exists a polynomial Q, s.

t. (1 + 2X) 2 k-2 = 1 + 2 k-1 X + 2 k-1 X 2 + 2 k Q(X).
Squaring both sides, we indeed get that (1+2X)

2 k-1 = 1+2 k X +2 k X 2 modulo 2 k+1 , which proves eqn. 2.
As a result we get that for k ⩾ 2, (1 + 2X)

2 k-1 ≡ 1 + 2 k m + 2 k X which is equivalent to 1+(1+2 k ) -1 2 k X = 1+2 k X ̸ = 1 in the group G ℓ . But (1+2 k X) 2 = 1 which proves that 1 + 2X is of order 2 k for k ⩾ 2. It is straightforward to verify that 1 + 2X is also of order 2 k for k = 0, 1.
The next step is to map 1 + 2X in ker φ ℓ using the explicit isomorphism. This isomorphism consists in taking a representative α of the class of 1 + 2X in O ∆ K , to compute a basis of the ideal αO We then move this form to Cl(∆) following [39, Algorithm 2] as a is odd so prime to the conductor 2 k+1 . We get the form (1 + 8N, 2 k+4 N, 2 2k+3 N ). We then reduce this form, first by normalizing the b coefficient modulo 2a : 2 k+4 N -2 k+1 a = -2 k+1 , and computing the new value of c, we get 2 2k . As a result, this normalization gives the form (1 + 8N, -2 k+1 , 2 2k ) which is equivalent to the form f = (2 2k , 2 k+1 , 1+8N ). Note that this form is reduced if 2 2k < 1+8N which will be the case in our applications.

The final step of the proof is to prove that f is a square. In Cl(∆), the assigned characters are χ 8 , χ -4 , χ p , χ q . Using f (1, 0) = 2 2k which is a square, one gets that χ p (f ) = χ q (f ) = 1. Using the odd integer f (0, 1) = 1 + 8N , χ -4 (f ) = (-1) 4N = 1 and χ 8 (f ) = 1 as 1 + 8N ≡ 1 (mod 8).

⊓ ⊔

The Gen 2 k algorithm

We depict our group generator in Algorithm 1. We first select a fundamental discriminant ∆ K := -8N as in Lemma 2. This ensures that the 2-Sylow subgroup of Cl(∆ K ) has order 4 and h(∆ K ) = 4ŝ where ŝ is odd, and ŝ is the cardinality of the subgroup of squares of Cl(∆ K ).

Algorithm 1: Gen 2 k

Input: 1 λ Result: pp sample two random distinct η(λ)-bit primes p, q according to Table 1

N := pq ∆K := -8N ∆ := 2 2k+2 • ∆K f := (2 2k , 2 k+1 , 1 + 8N ) ∈ Cl(∆) sample r a random square of Cl(∆) h := r 2 k ∈ Cl(∆) compute s an upper bound h(∆K ) return pp := (f, h, s)
We then consider the class group Cl(∆) of the non maximal order of discriminant ∆ := 2 2k+2 • ∆ K as in Lemma 1. This setting ensures that the class of the form f := (2 2k , 2 k+1 , 1 + 8N ) generates a subgroup F of order 2 k of the group of squares of Cl(∆).

For the discriminant ∆, the parameter µ equals 4 and there are h [START_REF] Cox | Primes of the Form x 2 + ny 2 : Fermat, Class Field Theory, and Complex Multiplication[END_REF]Prop. 3.11]). We then consider h a random 2 k -power of a square of Cl(∆). By construction, the order of h, denoted s, is odd as it divides ŝ. We denote H the subgroup generated by h. Denoting G the cycling subgroup of the squares of Cl(∆) of order 2 k s, we have the isomorphism G ≃ F × H and F (resp. H) is the subgroup of 2 k -roots of unity of G (resp. the 2 k -th powers of G). Finally, we denote s a known upper bound for s: the order s is unknown in our generator, but s can be computed from an upper bound on the class number of Cl(∆ K ):

(∆)/2 µ-1 = 2 k+1 • h(∆ K )/8 = 2 k • ŝ squares in Cl(∆) (cf.
h(∆ K ) < 1 π log |∆ K | |∆ K |
, or obtain a slightly better bound using the analytic class number formula (cf [START_REF] Mccurley | Cryptographic key distribution and computation in class groups[END_REF]).

Size of p and q. The bitsize η(λ) of the primes p and q is chosen such that the best algorithms for factoring N := pq take 2 λ time. This ensures that computing s via the class number of Cl(∆ K ) takes more that 2 λ time as known algorithms for computing class numbers have worse complexities. In practice, for 112 bits (resp. 128 bits) of security, we take N of 2048 bits (resp. 3072 bits).

Assumptions

The semantic security of our linearly homomorphic encryption (and its threshold variant) relies on the following hard subgroup membership assumption, which is a natural extension of the HSM assumption underlying CL encryption [START_REF] Castagnos | Practical fully secure unrestricted inner product functional encryption modulo p[END_REF]. In a nutshell, in the group G, we assume that it is hard to distinguish elements of the subgroup H, the 2 k -th powers, from random elements. As we shall see, in our particular context, this assumption implies the factorization assumption. Definition 8 (HSM 2 k assumption). Let A be an adversary for the HSM 2 k problem, its advantage is defined as:

Adv HSM 2 k A (λ) := 2 • Pr[b = b * : pp := (f, h, s) $ ← -Gen 2 k (1 λ ), x ← D H , u $ ← -U ((Z/2 k Z) × ), b $ ← -{0, 1}, z 0 := h x f u , z 1 := h x , b * ← A(pp, z b )] -1
where D H is a distribution over the integers such that the distribution {h x , x ← D H } is at distance less than 2 -λ from the uniform distribution in H. The HSM 2 k assumption holds if for any probabilistic polynomial-time adversary A, its advantage is negligible.

Relations with factoring and computing the class number. Let ∆ K = -8N , as defined in Algo. 1. The class number n := h(∆ K ) is an integer multiple of s, the unknown order of h. So computing n allows to break the HSM 2 k assumption by checking if z n b = 1 or not. The knowledge of n also allows to find the elements of order 2 of Cl(∆ K ), and, as shown in the background section, these elements gives the factorisation of ∆ K and thus of N . So computing n allows to factor N .

Conversely, there is no known method of computing h(∆ K ) given the factorisation of N , and best algorithms for computing h(∆ K ) have worse complexities than algorithms to factor N . However, the factorization of N allows to break HSM 2 k . As already mentioned in Subsection 2.3, computing square roots and deciding if an element is a square in Cl(∆) is feasible in polynomial-time if the factorisation of the discriminant is available. The HSM 2 k problem asks to distinguish between an element of the form z 0 = h x f u for a random odd integer u and an element of the form z 1 = h x , for a random x. As h is a 2 k -th power of a square, it is a square, and at least one of its square roots is a square itself, even if k = 1. This is not the case for h x f u . By construction, f is a square whose square roots are not squares: if there exists a square a such that f = a 2 then a would be a square of order 2 k+1 , and we get a contradiction with the fact that the group of squares of Cl(∆) has order 2 k • ŝ where ŝ is odd. So to distinguish the two cases, one has to compute a square root of the challenge element, and by inspection, compute the genera of the forms, check whether there exists a square root that is a square (and in this case the attacker outputs b ⋆ = 1) or not (and in this case the attacker outputs b ⋆ = 0).

It can be shown that the factorization allows in fact to compute a partial discrete logarithm of any y = g x in the class group, i.e., the value x mod 2 k (and gives therefore a trapdoor to decrypt a ciphertext).

Class Number

HSM 2 k Factorization

Fig. 2. Relations between the algorithmic assumptions underlying our protocols 4 Linearly Homomorphic Encryption Scheme on Z/2 k Z

Description of the new encryption scheme

Let D H (resp. D G ) be a distribution over the integers, such that {x mod s :

x $ ← -D H } (resp. {x mod 2 k s : x $ ← -D G }) is δ-close to the uniform distribution in {1, . . . , s} (resp. {1, . . . , 2 k s}), where δ ≤ 2 -λ .
The distribution D G is only used in the security proof and the distribution D H can be instantiated by sampling x uniformly in {1, . . . s • 2 λ+2 } using the upper bound s on s (cf. [17, Appendix C]).

Our linearly homomorphic encryption scheme on Z/2 k Z is described in Figure 3, where the key generation algorithm takes as input the public parameters pp := (f, h, s) that come from the Gen 2 k algorithm. There is no condition on the value of k, typical values are 32, 64 or 128.

Correctness and Decryption

The correctness of the protocol comes from the fact

c 2 • c -sk 1 = f m • pk r • (h r ) -sk = f m • (h sk ) r • (h r ) -sk = f m .
To recover m from f m , one has to compute a discrete logarithm. In this case, this discrete logarithm computation is trivial since f generates a subgroup of order 2 k . Pohlig-Hellman algorithm makes it possible to recover m by extracting m bit by bit. The algorithm to retrieve the discrete logarithm is described in Fig. 4. It consists mainly of O(k 2 ) squaring in the class group. We now demonstrate that in game 3, the challenge bit b is perfectly hidden from A's view. Since G ≃ H ×F , the element c 1 = h r f u information theoretically fixes the value of (u mod 2 k ) and of (r mod s) from A's view. Furthermore A receives c 2 = f m b +u•sk pk r . Given c 1 and pk, the value of pk r is information theoretically fixed, hence an unbounded adversary could infer (m b +u•sk mod 2 k ).

Algorithm 7: Pohlig-Hellman

Input: pp, M ∈ F Result: m such that M = f m - m := 0; f := f 2 k-1 ; for i = 0 to k -1 do if (f -m M ) 2 k-1-i = f then m := m + 2 i ; end end return m
Since sk is sampled from D G , the distribution followed by (sk mod 2 k s) is at negligible distance δ ≤ 2 -λ of the uniform modulo 2 k s. Furthermore, since s and 2 k are co-prime, (sk mod 2 k ) is δ-close to the uniform modulo 2 k and is independent of (sk mod s). So even if pk = h sk fixes the value of (sk mod s), that of (sk mod 2

k ) remains δ-close to U (Z/2 k Z) from A's view. Finally since u is invertible modulo 2 k , (u • sk mod 2 k ) is also δ-close to U (Z/2 k Z), and perfectly masks m b . Therefore | Pr[S 2 ] -1/2| ≤ δ.
Combining the probability equations, we conclude the proof with the following inequality:

Adv ind-cpa A (λ) ≤ ϵ HSM 2 k + 3δ.

⊓ ⊔

We note that a DDH assumption can also be used in the group G similarly to [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF], which would lead to slightly different encryption scheme (using g = hf instead of h).

Circuit privacy for linear functions The ciphertexts of our encryption protocol guarantees circuit privacy, in the sense that ciphertexts obtained through the homomorphic evaluation process are indistinguishable from fresh encryptions of the resulting message. This property is very useful in multi-party computation (see [START_REF] Catalano | MonZ 2 k a: Fast maliciously secure two party computation on Z 2 k . PKC[END_REF][START_REF] Catalano | Using linearly-homomorphic encryption to evaluate degree-2 functions on encrypted data[END_REF] for instance). More precisely, the definition is as follows.

Definition 9 (Circuit privacy for linear functions). We say that a linearly homomorphic encryption LHE is private if there exists a probabilistic polynomialtime simulator Sim such that for any λ ∈ N, for any (pk, sk) ← KeyGen(λ, pp), any pair of messages m 1 , m 2 in the message space, and two ciphertexts c 1 and c 2 of m 1 and m 2 respectively, and any scalar α, the statistical distances between LHE.EvalAdd(pp, pk, c 1 , c 2 ) and Sim(1 λ , pp, pk, m 1 + m 2 ) and between LHE.EvalScal(pp, pk, c 1 , α) and Sim(1 λ , pp, pk, αm 1 ) are negligible. Theorem 3. The scheme of Fig. 3 is circuit private for linear functions.

Proof. For both pair of distributions, the simulator just encrypts the message it has as input (m 1 +m 2 or αm 1 ). The randomization applied during homomorphic evaluations (LHE.EvalAdd and LHE.EvalScal) ensures that the distributions are statistically close. ⊓ ⊔

Experiments

We have implemented our encryption protocol using Sagemath with calls to the PARI native C Library [START_REF][END_REF] for the operations in class groups. All benchmarks were done on a standard laptop (Intel Core i5-6267U @ 2.90GHz). Our experiments have been run for security levels of λ = 112 and 128 bits. The RSA modulus N has therefore respective sizes of 2048 bits and 3072 bits. The bit size of the ciphertexts is 2 × 3 4 (5 + 2k + ℓ N ) where ℓ N is the bit size of N . The crucial part of KeyGen, Encrypt and Decrypt are exponentiations in class groups where the exponent is upper bounded by s ≈ √ N . These timings show that even a straightforward implementation is practical, and an optimized C implementation of our system would drastically improve the running times.

5 Threshold Encryption on Z/2 k Z with Trusted Setup

A TPKE scheme from class groups

In this subsection we adapt the PKE scheme from the previous section to the threshold setting. The threshold decryption relies on the LISS construction from Damgård and Thorbek [START_REF] Damgård | Linear integer secret sharing and distributed exponentiation[END_REF] based on [START_REF] Benaloh | Generalized secret sharing and monotone functions[END_REF]. Let n be the number of servers, from the know x. Concretely, we simulate the contribution from P by

ct sj 1 (ct x 1 ) κ S R = ct sj +xκ S R 1 = ct s ′ j 1 .
After this partial decryption phase, A outputs his messages m 0 and m 1 which are forwarded to the ind-cpa challenger which answers with a challenge ciphertext c ⋆ of one of this two messages m b ⋆ , which is given to A. After another series of queries for partial decryptions, answered in the same way, A outputs a bit b, which is set as the output of the ind-cpa adversary.

To see that the simulation is correct, we see that the simulated shares are statistically indistinguishable from the real shares by the privacy of the LISS scheme. Second, honest parties always output the correct value ct x 1 , by correctness of the LISS scheme. Finally, given ct 1 , ct x 1 , the simulated contributions from honest parties are statistically indistinguishable, since the vector we use for the simulated sharing is ρ ′ = ρ + xκ S which is statistically close to a uniformly chosen sharing vector for x. The advantage of the ind-cpa attacker will therefore be that of the T-ind-cpa attacker.

⊓ ⊔

In terms of efficiency, the only difference between the thresold scheme and the encryption scheme of Section 4 is in the decryption algorithms (encryption is exactly the same). Therefore, the additional costs come from the LISS, and translate in an additional number of exponentiations in the class group. Exact numbers depend on the considered access structure. For a concrete example, taking the access structure construction for a 2-out-of-3 policy (cf [53, Example 3.4 p. 26]), the shares have roughly the same bitsize as the secret key and we get 2 exponentiations (in total) for PartDec and a negligible extra cost in FinalDec consisting of multiplication and inversion since the reconstruction vector has components in {-1, 0, 1}. As a result, PartDec takes twice the classical decryption time (or the same with parallelisation).

Extensions

Some extensions and improvements (in terms of security or functionality) are possible for our threshold encryption scheme: we suggest few of them.

-Robustness: It informally captures that no malicious adversary can prevent a honest majority from decrypting a valid ciphertext. It can be achieved in our context by using Σ-protocols proving equality of discrete logarithms in groups of unknown orders to prove the validity of decryption shares. -Removing the trusted dealer: It is one of the most interesting feature that can be achieved, especially compared to a potential Elgamal version of Benhamouda et al.'s scheme. It first requires to generate in a distributed manner an RSA modulus satisfying the needed congruences. Many efficient techniques can be employed, such as [START_REF] Chen | Diogenes: Lightweight scalable rsa modulus generation with a dishonest majority[END_REF], secure against any subset of maliciously colluding parties. The class group can then be computed publicly and the factorization ignored. To share the secret key without trusted dealer, it is possible to use verifiable linear integer secret sharing [START_REF] Thorbek | Linear Integer Secret Sharing[END_REF] and techniques from [START_REF] Gennaro | Secure distributed key generation for discrete-log based cryptosystems[END_REF] to distribute key generation for discrete-log based cryptosystems.

In addition, zero-knowledge arguments for several relations (well-formdness of a key or equality of discrete logarithms) in group of unknown orders will be needed and can be found in the literature [START_REF] Block | Time-and space-efficient arguments from groups of unknown order[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]. -CCA security: Using techniques of [START_REF] Devevey | Non-interactive CCA2secure threshold cryptosystems: Achieving adaptive security in the standard model without pairings[END_REF] for their chosen ciphertext secure threshold cryptosystems from the Decision Composite Residuosity (DCR) assumption, it should be possible to make our threshold encryption scheme CCA secure (even though we would be loosing the crucial homomorphic encryption), as well as adaptively secure (i.e., secure against an adversary who dynamically corrupts servers throughout the protocol), and non-interactive (i.e., decryption servers do not interact amongst themselves but rather contribute, each, a single message). Note that several building blocks need to be adapted: for example, a Trapdoor Σ-protocol showing that an element is a 2 k -th power. As shown at the end of Subsection 3.4, the factorization of the discriminant could be the trapdoor of such a protocol.

Applications

We here discuss future work, and provide intuition for some of the many applications we see to our scheme.

Secure multi-party computation

The goal here is to devise an MPC protocol (for dishonest majority) that works over Z/2 k Z, and provides better (bandwidth) efficiency than current solutions. The topic of malicious MPC for Z/2 k Z has drawn significant attention since 2018, when Cramer et al. revelled their SPDZ 2 k protocol [START_REF] Cramer | SPD Z 2 k : Efficient MPC mod 2 k for dishonest majority[END_REF] which aims at solving this issue.

Computations modulo 2 k , closely match what happens in a CPU, thereby allowing protocol designers to take advantage of tricks already known there. Typical examples being comparison operations and bitwise operations which seem to be easier modulo 2 k (and harder to emulate modulo p).

The solution from [START_REF] Cramer | SPD Z 2 k : Efficient MPC mod 2 k for dishonest majority[END_REF] follows a blueprint that is by now standard for many fast (maliciously) secure MPC protocols. The protocol phase is divided in two stages. An offline (slow) phase where some precomputation is done without knowing the actual inputs of the computation; and a very fast, information theoretic, phase which requires knowing the inputs and takes advantage of the data computed offline.

The offline stage consists, mainly, in creating sharings of many triplets of the form In SPDZ 2 k they use oblivious transfer, which is fast but expensive in terms of bandwidth consumption. One way of reducing bandwidth would be to rely on homomorphic encryption (and indeed the original SPDZ protocol uses somewhat homomorphic encryption for degree two polynomials to compute triplets). The issue is how to do this in the Z/2 k Z setting, since we don't know many homomorphic encryption schemes that cope well with this setting.

To our knowledge, two solutions exist to this problem, and both have issues. The first is a protocol due to Orsini et al. [START_REF] Orsini | Overdrive2k: Efficient secure MPC over Z 2 k from somewhat homomorphic encryption[END_REF], which presents significant efficiency gains with respect to [START_REF] Cramer | SPD Z 2 k : Efficient MPC mod 2 k for dishonest majority[END_REF], but remains very complex. The second, much simpler, is due to Catalano et al. [START_REF] Catalano | MonZ 2 k a: Fast maliciously secure two party computation on Z 2 k . PKC[END_REF]. Their protocol relies on the Joye-Libert encryption scheme, but has lower bandwidth gain and only works in the two party case. Indeed, though the Joye-Libert protocol allows for a message space of order 2 k , it is unclear how to enhance it with threshold decryption. Hence each player in the [START_REF] Catalano | MonZ 2 k a: Fast maliciously secure two party computation on Z 2 k . PKC[END_REF] protocol has their own public and secret key pair, and computing multiplications is performed via a protocol à la Gilboa [START_REF] Gilboa | Two party RSA key generation[END_REF] which entails a number of zero-knowledge proofs -hence the small gain in bandwidth consumption.

How does our scheme help? Our encryption scheme both allows for a message space of order 2 k , and for threshold decryption. Given both these properties, one can easily generate triplets as follows. Each player P i chooses a random a i , a random b i , encrypts them Encrypt pk (a i ), Encrypt pk (b i ) and broadcasts these values. Every player homomorphically adds the shares it sent and received to obtain encryptions Encrypt pk (a), Encrypt pk (b), where a = i a i , and b = i b i . Then, using a trick from Catalano et al. [START_REF] Catalano | Using linearly-homomorphic encryption to evaluate degree-2 functions on encrypted data[END_REF], every player can multiply the underlying plaintexts to obtain Encrypt pk (ab). Finally each player P i uses the partial decryption algorithm with its secret key sk i to obtain an additive share c i of ab.

Homomorphic secret sharing (HSS)

Homomorphic secret sharing is a form of secret sharing that allows parties to non-interactively perform computations on shared private inputs. HSS can be viewed as a distributed variant of homomorphic encryption: in HSS multiple parties are given a share of the inputs, and, without further interaction, they each perform (non interactively) homomorphic evaluations over these inputs to obtain a share of the desired output. HSS can be used instead of fully/somewhat homomorphic encryption in many scenarios, including low-communication MPC (e.g. [START_REF] Boyle | Group-based secure computation: Optimizing rounds, communication, and computation[END_REF]), private querying to remote databases (e.g. [START_REF] Boyle | Function secret sharing[END_REF]), methods of succinctly generating correlated randomness (e.g. [START_REF] Boyle | Efficient pseudorandom correlation generators: Silent OT extension and more[END_REF]), and more. Using our TPKE scheme, combined with recent techniques introduced by Orlandi et al [START_REF] Orlandi | The rise of paillier: Homomorphic secret sharing and public-key silent OT[END_REF], one should be able to devise the first HSS protocol that efficiently performs computations modulo 2 k , without requiring a correctness/efficiency trade-off, and without the need to restrict the size of the shared inputs.

Details. Based on the breakthrough work by Boyle et al. [START_REF] Boyle | Breaking the circuit size barrier for secure computation under DDH[END_REF], Fazio et al. [START_REF] Fazio | Homomorphic secret sharing from paillier encryption[END_REF] provided a blueprint to build an HSS scheme for an expressive class of programs 5 . Precisely, from the [START_REF] Boyle | Breaking the circuit size barrier for secure computation under DDH[END_REF] protocol, which was based on (circular secure) Elgamal encryption, [START_REF] Fazio | Homomorphic secret sharing from paillier encryption[END_REF] abstract the key ingredients required of an encryption scheme to build an HSS.

1. The encryption scheme must be both message and key (linearly) homomorphic over a finite quotient. 2. Given an encryption of a small integer w, and substractive secret sharings ⟨x⟩ and ⟨skx⟩ (where sk is the decryption key), there must be a non-interactive method for parties to compute multiplicative shares of the group element g xw , which lives in the ciphertext space of the encryption scheme. 3. A non-interactive technique to convert the multiplicative sharing of g xw into an additive sharing of xw which lives in the plaintext space of the encryption scheme.

Our TPKE scheme naturally satisfies item 1, as it is linearly homomorphic, and threshold decryption can provide us the aforementioned key homomorphic property.

Regarding item 2, we leverage the Elgamal-like structure of our TPKE. Consider a ciphertext (h r , f w pk r ) encrypting w, where pk = h msk . For each memory value x in the RMS program, the value of x and of skx are each held as an additive secret sharing across parties (let us denote P i 's shares ⟨x⟩ i and ⟨skx⟩ i ). P i 's computes its' multiplicative share of f wx as g i := (h r ) -⟨skx⟩i (f w pk) ⟨x⟩i . Item 3 has for long been the tricky part of the protocol. An ingenious distributed discrete logarithm (DDLog) protocol was first suggested by [START_REF] Boyle | Breaking the circuit size barrier for secure computation under DDH[END_REF]. In their protocol, to obtain substractive shares of z := xw, parties P 0 and P 1 , respectively owning shares g 0 , g 1 such that g 0 = g 1 g xw , agree upon some distinguished element g that is not too far away from g 0 , g 1 in terms of multiplications by g. If they find such a g, then party i can compute the distance of g i from g by brute force: by multiplying g by g repeatedly, and seeing how many multiplications it takes to get to g i . If g isn't too far away, this should not be too inefficient. The primary challenge is agreeing upon a common point g. [START_REF] Boyle | Breaking the circuit size barrier for secure computation under DDH[END_REF] had the parties first fix a set of random, distinguished points in the group; party i then finds the closest point in this set to g i . As long as both parties find the same point, this will lead to a correct share conversion. To make this process efficient, the distance d between successive points can't be too large, as running time will be O(d). But this induces an inherent ≈ 1/d probability of failure, in case a point lies between the original two shares and parties fail to agree. Furthermore, Dinur et al [START_REF] Dinur | An optimal distributed discrete log protocol with applications to homomorphic secret sharing[END_REF] showed that if one could do better than 1/d error probability in O( √ d) steps, the algorithm could be used to improve the cost of finding discrete logarithms in an interval, a well-studied problem which is believed to be hard.

In recent work, Orlandi et al [START_REF] Orlandi | The rise of paillier: Homomorphic secret sharing and public-key silent OT[END_REF] overcame this barrier by leveraging the easy discrete logarithm subgroup present in the Paillier framework. As we also have such a setup, we benefit from their technique, and parties can both agree on a distinguished point and efficiently find the distance of a multiplicative share from that point, without requiring a correctness/efficiency trade-off. The high level idea (applied to our group elements), is that both g 0 and g 1 can be seen as elements of the coset X g0 := {g 0 , g 0 f, . . . , g 0 f 2 k -1 }. If both parties agree on a point h in this set, then there exists z such that h = g 0 f z , and so P 0 can efficiently compute log F ( h • g -1 0 ) = z. Furthermore, since g 0 = g 1 f xw , P 1 can efficiently compute log F ( h • g -1 1 ) = z + xw. And it holds that z + xw -z = xw as desired. Now to agree on the point h the parties compute the smallest element from X g0 . This may be done using the surjection φ 2 k from Cl(∆) to the class group of the maximal order Cl(∆ K ). Finally, we note that in prior work, the size of the shared inputs had to be bounded, either for efficiency, as in [START_REF] Boyle | Breaking the circuit size barrier for secure computation under DDH[END_REF], or for correctness of computations in [START_REF] Orlandi | The rise of paillier: Homomorphic secret sharing and public-key silent OT[END_REF]. The upper bound in Orlandi et al's protocol ensures that no wrap around occurs modulo N . On the other hand, using our TPKE scheme with message space 2 k , we can set the order of the message space to be the modulus desired for practical computations, and potentially avoid such constraints.

Lossy trapdoor functions (LTDFs)

Lossy trapdoor functions, introduced by Peikert and Waters [START_REF] Peikert | Lossy trapdoor functions and their applications[END_REF], are families of functions where injective functions are computationally indistinguishable from lossy functions, which lose many bits of information about their input. Among many interesting applications, LTDFs are known to imply chosen-ciphertextsecure PKE [START_REF] Peikert | Lossy trapdoor functions and their applications[END_REF] or deterministic encryption [START_REF] Bellare | Deterministic and efficiently searchable encryption[END_REF] for instance.

Huge efficiency gains were obtained by Joye and Libert [START_REF] Joye | Efficient cryptosystems from 2 k -th power residue symbols[END_REF] over previous constructions from linearly homomorphic scheme, by leveraging the 2 k order of their message space in order to batch evaluation and process k-bit blocks of the input at once.

Applying both techniques to our linearly homomorphic PKE of Figure 3 would yield an efficient LTDF which supports evaluation over k-bit blocks at once. This allows for compact outputs of the functions. We note however that, due to the Elgamal-like structure of our underlying PKE, trapdoors and function descriptions would be larger than in the Joye-Libert LTDF: for inputs of size n, our trapdoors would require an extra n/k integers, while our function descriptions would require an extra n/k elements in H.

Fig. 1 .

 1 Fig. 1. Experiment Expt A,TPKE,b

Definition 5 .

 5 Consider a TPKE with message space (M, +). A linearly homomorphic TPKE scheme additionally has the following evaluation algorithms: EvalAdd(pp, c 1 , c 2 ) → c * Takes as input pp and two ciphertexts c 1 and c 2 , and outputs a new ciphertext c * which decrypts to m 1 + m 2 where each c i , i ∈ {1, 2} decrypts to m i . EvalScal(pp, c, α) → c * Takes as input pp, a ciphertexts c which decrypts to m, and a scalar α, and outputs a new ciphertext c * which decrypts to α • m.

2 Z

 2 Cl(∆) is isomorphic to the set of forms modulo this equivalence relation. In fact, it is more natural to work with forms for algorithmic purposes: the class of the form (a, b, c) corresponds to the class of the O ∆ -ideal aZ + -b+ √ ∆ . Moreover, 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. A reduced form satisfies a ⩽ |∆|/3. As a result, elements of Cl(∆) can be represented by (a, b) using log 2 (|∆|) bits. Dobson et al. recently proposed in

  ∆ K and then to move it to Cl(∆) by considering the class of the ideal αO ∆ K ∩ O ∆ . The element 1 + 2X corresponds to the quadratic integer α := 1 + 2 √ m = 1 + √ ∆ K . Following [10, Prop. 2.9], one writes α = x+y √ ∆ K 2 with x = y = 2. Then applying the Extended Euclidean algorithm on y = 2 and (x + y∆ K )/2 = 1 + ∆ K one gets κ = 1 -4N , λ = -1, µ = 1 s.t. κy +λ(x+y∆ K )/2 = µ. The ideal αO ∆ K then corresponds to the form (a, b, c) where a = N (α)/µ = 1 -∆ = 1 + 8N ; and b ≡ -κx -λ(x + y)∆ K /2 (mod 2a). One gets b ≡ -2 -8N ≡ 8N (mod 2a), and c = 2N .

Fig. 4 .

 4 Fig. 4. Pohlig-Hellman algorithm to compute log f (M )

  [a], [b], [ab], where a and b are random in Z/2 k Z. These triplets are used to speed up the online phase. The computations on the input data executed in the online phase require performing additions and multiplications. To add two shared secrets [x], [y], players simply add their shares non interactively. Multiplication is less straightforward. In order to compute [xy] quickly, given a (yet unused) triplet [a], [b], [ab], players proceed as follows. First jointly open [x]-[a] = c and [y]-[b] = d. Then, without further interaction, each player can compute: [xy] = cd + [a]d + [b]c + [ab]. Since the online phase is very fast (essentially the same for all protocols following this blueprint) the question is how to improve efficiency of the offline stage?

  are computationally indistinguishable. On input 1 λ , the adversary A chooses an access structure A. Set up: The challenger C runs (pp, ek, sk) ← Setup(1 λ , A) and sends pp, ek to A. Choose set: A outputs a set S such that S / ∈ A, and C sends the set of secret keys {sk i }i∈S to A. Partial decryption queries: A queries partial decryption on encryptions of plaintexts mj of his choice. For ct j = Encrypt(pp, ek, mj), it then gets PartDec(pp, ski, ctj) for i ̸ ∈ S Choose challenge: A outputs a pair of challenge messages m0, m1 ∈ M. Challenge: C computes ct b ← Encrypt(ek, m b ) and sends ct b to A. Partial decryption queries: Again, A queries partial decryption on encryptions of plaintexts mj of his choice : it gets ct j = Encrypt(pp, ek, mj) and PartDec(pp, ski, ctj) for i ̸ ∈ S Guess: A outputs a bit b ′ , which is the output of the experiment.

	Choose structure:

Restricted Multiplication Straight-line Programs. This class captures polynomialsize branching programs, which includes arbitrary logspace computations and NC1 circuits.

Acknowledgements. We thank Dario Catalano for helpful early discussions about these results and the anonymous reviewers for their comments in improving the work. This work was partially supported by the French ANR SANGRIA project (ANR-21-CE39-0006) and the French PEPR Cybersecurité SecureCompute project (ANR-22-PECY-0003). This work also recieved funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program under projects PICOCRYPT (grant agreement No. 101001283), and TERMINET (grant agreement No. 957406), by the Spanish Government under projects SCUM (ref. RTI2018-102043-B-I00), by the Madrid Regional Government under project BLOQUES (ref. S2018/TCS-4339), and by a grant from Nomadic Labs and the Tezos foundation.

Fig. 3. Linearly homomorphic encryption scheme with message space Z/2 k Z

Security of the encryption scheme

Semantic security Theorem 2. The scheme described in Figure 3 is semantically secure under chosen plaintext attacks (ind -cpa) if the HSM 2 k assumption holds.

Proof. The proof proceeds as a sequence of games, starting with the real ind-cpa experiment and ending in a game where the ciphertext statistically hides the random bit b chosen by the challenger. We denote S i the event 'adversary A outputs b = b * in Game i'.

In Game 1, instead of sampling sk from D H , it is sampled from D G . The rest of the experiment is unchanged, so the only difference from A's view is the distribution of pk := h sk . The distribution D H is chosen such that {h Our new threshold encryption protocol with message space of order 2 k is described in Fig. 5. We omit the EvalAdd and EvalScal algorithm that are exactly the same as the ones for our linearly homomorphic encryption scheme (Algorithms 5 and 6 of Fig. 3). Theorem 4. The scheme described in Fig. 5 achieves T-ind-cpa-security under the indcpa security of the non-threshold scheme of Fig. 3.

Proof. This theorem is a direct corollary of the privacy of the LISS and the ind-cpa of the non-threshold encryption scheme.

From an attacker against the T-ind-cpa-security A, we construct an attacker against the ind-cpa security of the basic scheme, which receives public parameters pp and a public key pk = h x for an unknown x.

After A chooses an access structure A, he is fed with pp and pk as ek. He chooses a set S outside A, and waits for the corresponding secret keys. They are simulated after the computation of a sharing of 0, i.e., the distribution vector is ρ = (0, ρ 1 , . . . , ρ d ) T and the shares are s = (s 1 , . . . , s d ) ⊤ = M•ρ, where M is the matrix corresponding to the access structure A. A receives the shares belonging to the servers in S. Now, A can query partial decryptions: he queries the oracle on plaintext m and server i. The message m is encrypted as ct = Encrypt(pp, ek, m) = (ct 1 , ct 2 ). We must simulate the contributions that this honest party i computes, namely

1 . This is done as in [START_REF] Damgård | Linear integer secret sharing and distributed exponentiation[END_REF] for the distribution of an exponentiation. Let κ S be the sweeping vector of Def. 7 for S. Now, let R be a row in the distribution matrix M belonging to the honest server P i and let s j be one component of the server's share we computed from this row. Had we used ρ ′ = ρ + xκ S instead of ρ, then the share component coming from R would have been s ′ j = (ρ + xκ S )R = s j + xκ S R instead. The observation is now that because we know ct x 1 and s, we can compute ct where dS := i∈S di and λj i := (λj 1 ,1, . . . , λ j 1 ,d j i ) ⊤ for all i = 1, . . . , t.

if M / ∈ F then return ⊥ end return log f (M ) using Algo. 7


Narimane Gassa

Machteld Boonstra

Beata Ondrusova1

Jana Svehlikova

Dana Brooks

Akil Narayan

Ali Salman Rababah

Peter Van Dam

Rob Macleod

Jess Tate

Nejib Zemzemi

Effect of Segmentation Uncertainty on the ECGI Inverse Problem Solution and Source Localization

Electrocardiographic Imaging (ECGI) is a promising tool to non-invasively map the electrical activity of the heart using body surface potentials (BSPs) and the patient specific anatomical data. One of the first steps of ECGI is the segmentation of the heart and torso geometries. In the clinical practice, the segmentation procedure is not fullyautomated yet and is in consequence operator-dependent. We expect that the inter-operator variation in cardiac segmentation would influence the ECGI solution. This effect remains however non quantified.

In the present work, we study the effect of segmentation variability on the ECGI estimation of the cardiac activity with 262 shape models generated from fifteen different segmentations. Therefore, we designed two test cases: with and without shape model uncertainty. Moreover, we used four cases for ectopic ventricular excitation and compared the ECGI results in terms of reconstructed activation times and excitation origins.

The preliminary results indicate that a small variation of the activation maps can be observed with a model uncertainty but no significant effect on the source localization is observed.

Introduction

The inverse problem in cardiac electrophysiology, also known as electrocardiographic imaging (ECGI), has been a research topic for decades as it may be a powerful tool for the treatment and diagnosis of cardiac arrhythmia.

ECGI non-invasively estimates electrical activity of the heart using body surface potential measurements obtained are combined with a specific CT/MRI based anatomical models and defined electrode positions. However, the problem is known to be ill-posed; the uncertainty of the mathematical model mainly due to the different hypotheses stated and its parameters generate modeling errors and uncertainty in the inverse solution.

Moreover, ECGI relies on image segmentation for geometry creation. Since the process is operator dependent, it also introduces more uncertainty into the solution as it has shown that the segmentation variability affects estimated ventricular potentials [START_REF] Tate | Effect of segmentation variation on ecg imaging[END_REF]. Despite the previously studies conducted on the statistical shape analysis of ventricular segmentation variability the effect of this variation on ECGI remains unexplored [START_REF] Tate | A cardiac shape model for segmentation uncertainty quantification[END_REF][START_REF] Tate | Uncertainty quantification of the effects of segmentation variability in ecgi[END_REF].

More sources of uncertainties likely affects the ECGI solutions including the position of the heart within the torso mainly affected by respiration or changes in body position.

Therefore, in this study, we focus on the effect of segmentation variability on ECGI estimations of cardiac activation.

Methods

Anatomical Data

Fifteen different cardiac segmentations from the same single subject CT-scans were created by different researchers within the consortium for ECG Imaging (CEI, ecg-imaging.org). Then, these segmentations were analyzed using ShapeWorks to study the variability in segmen-tation [START_REF] Cates | Shapeworks: particle-based shape correspondence and visualization software[END_REF]. Therefore, 1024 control points were obtained which were evenly distributed over the surface. From the derived statistical model, 262 cardiac shape models were obtained as previously described in [START_REF] Tate | A cardiac shape model for segmentation uncertainty quantification[END_REF]. Figure 1. Representative example of one cardiac shape model with the control points.

Forward problem

To study solely the effect of segmentation variability on the inverse problem, body surface potentials (BSP) were computed using all 262 cardiac models using one torso model with 120 electrodes [START_REF] Sundnes | Computing the electrical activity in the heart[END_REF]. Specifically, the monodomain model was used to simulate the electrical wave propagation. In each of the 262 cardiac model we used four stimulation protocols of ventricular focal excitation : left ventricular (LV), right ventricular (RV), left ventricular septum, and apex as shown in Figure 2. On the torso surface, the electrical potential is computed using the pseudo-ECG approximation and is described by a Laplace equation and satisfies

BSP(x, y, z) = 1 4π ΩH ∇V m .∇ 1 r(x, y, z) ,
where V m stands for the trans-membrane potential, Ω H the heart domain and r is the Euclidean distance between the electrode at position (x, y, z) and a point of the heart.

LV RV Septal Apex

Inverse problem : MFS

We used the simulated BSP to estimate the cardiac activation sequence using the Method of Fundamental Solutions (MFS). We approach the solution of the elliptic problem given by the Laplace equation by a linear combination of fundamental solutions of the differential operator which is, in our case, the Laplacian. These solutions will be located on a set of points called virtual source points y j , j = 1 . . . M over an auxiliary surface of ΩT located outside of the domain of interest Ω T as described in [START_REF] Wang | Application of the method of fundamental solutions to potential-based inverse electrocardiography[END_REF].

The potentials are expressed as u(x) = a 0 + M i=1 f (x, y j )a j , where x ∈ Ω T , y j are the virtual source points and a j , j = 1 . . . M are their corresponding coefficients. Here, f stands for the Laplace fundamental solution defined as f (r) = 1 4πr with r = |x -y| is the euclidean distance between two points x and y.

When using Dirichlet and Neumann conditions we obtain the linear system Ax = b, with A being the transfer matrix and:

x = (a 0 , a 1 , • • • , a M ) T b = (u x1 , • • • , u x N , 0, • • • , 0) T
To find the unknown coefficients (a i ∈ R M+1 ) and compute the potential on the heart, we solve the following least-square optimization problem with a Tikhonov regularization,

Ax -b 2 + λ Lx 2 , (1)
where L the regularization operator is an identity matrix for the zero-order Tikhonov and λ is the regularization parameter to be identified.

Data-analysis

In order to assess the error related to the geometry variability from the error related to the inverse problem method we designed two test cases, with and without model uncertainty. In the first test case (Test A), the BSP computed using the i th shape model (BSP i ) is used for the ECGI estimation only for the i th shape model. As the second test case (Test B), the BSP * generated using a reference cardiac shape model was used for the ECGI estimation for all 262 shape models.

For both test A and B and for each stimulation protocol, we computed 262 inverse solutions. Per solution, we calculated the corresponding activation times and the estimated site of initial activation. Afterwards, we computed the correspondence between the reconstructed and true activation maps by means of Pearson's correlation coefficients (CCs). Finally, we computed the Euclidean distance between the true pacing sites and the ECGI based earliest activation sites (EAS) obtained from the inverse solutions we denote as the Localization Error (LE).

Results

In Figure 3, the mean cardiac shape model with average activation times obtained from the ECGI based solutions from 262 shape models. The columns correspond to the true activation maps (left column in Figure 3) as used to compute BSP, the mean activation maps for test A (middle column) and test B (right column). The rows correspond to the four stimulation protocols.Visually, there are no significant difference between the true activation sequence and the ECGI estimation in case of LV, RV and apical pacing. In the case of septal paced beats, we observe from the representation of the average activation map that, for both tests A and B, zones of low activation times in the RV and LV cavities. This finding would eventually be evidenced in the lower coefficient correlations and source location accuracy. The box plots for spatial CCS of the activation maps for all models are provided in Figure 4. In the four stimulation protocols, we remark a small decrease of the CC values from 0.959 ± 0.006 (in Test A) to 0.950 ± 0.007 (in Test B) for LV paced beat, from 0.951 ± 0.014 to 0.943 ± 0.018 for RV paced beat,from 0.935 ± 0.014 to 0.911 ± 0.016 for apical paced beat and from 0.819 ± 0.045 to 0.797 ± 0.071 for septal paced beat.

From the obtained ATs we compute the earliest activa-

Discussion and Conclusion

With a focus on segmentation uncertainty, we used computed BSP with the same or a reference heart shape to estimate the activation sequence. In fact, we performed two tests A and B. In test A, we solved the inverse problem for each cardiac shape model given the corresponding BSP. In test B, we solved the inverse problem for the different shape models starting from one single BSP. Afterwards, we evaluated, for both tests A and B per stimulation protocol, the correlation coefficients between the reconstructed and true activation maps as well as the localization errors of the ectopic ventricular sites given the position of ECGI based excitation origins. The obtained results indicate that the segmentation uncertainty affected the resulting activation maps for all the stimulation sites but this was not observed on the source localization, particularly for the RV and Apex stimulation. This could be explained by the low variability across the 262 cardiac shape models of the chosen stimulation sites. In fact, an analysis of the computed BSPs for these cases shows the effect of the segmentation on the amplitude of the signals but rarely on the morphology which is more likely to affect the ECGI results.

As the results from Test A indicate, there remain additional sources of uncertainty which likely affects the ECGI estimations. During real-life BSP measurements, beatto-beat differences occur due to respiration. The respiratory directly affects the position of the heart within the torso and consequently the obtained BSP. Furthermore, as patient-specific images are however obtained at one respiratory state during CT/MRI imaging procedures; either end-respiratory or end-excretory. To partially reduce this error mathematical models have been proposed [START_REF] Bergquist | Reconstruction of cardiac position using body surface potentials[END_REF]. Another part of uncertainty is expected for the repolarization due the contraction of the heart as we only use the end of diastolic phase from the imaging for the segmentation.

In future work, we will extend our study to different stimulation sites in areas of the heart more affected by segmentation variability. As it has shown that the largest variation was found at the base of the heart we may observe that also earliest site of activation may be significantly affected by cardiac shape model differences if we specifi-cally assess stimulation protocols in these areas.

Figure 2 .

 2 Figure 2. Ventricular stimulation protocols.

Figure 3 .

 3 Figure 3. Comparison of activation times (from left to right): true activation times on the mean heart with green dots representing the average of the simulated excitation origin and reconstructed activation times on the average heart (test A & B) with red dots representing the average earliest activation sites calculated by MFS.

Figure 4 .Figure 5 .

 45 Figure 4. Correlation coefficients of the reconstructed activation maps in the four stimulations protocols.

Figure 6 .

 6 Figure 6. Box plots of the localization error of the pacing site using Euclidean distance.

Acknowledgements

This Project has received funding from the European Unions Horizon research and innovation programme under the Marie Skodowska-Curie grant agreement No. 860974 and by the French National Research Agency, grant references ANR-10-IAHU04-LIRYC and ANR-11-EQPX-0030. This project was supported by the National Institute of General Medical Sciences of the National Institutes of Health under grant numbers P41GM103545, R24GM136986, U24EB029012, U24EB029011, R01AR076120, and R01HL135568. Data used in this study was made available by Drs. John Sapp and Milan Horacek and their research collaboration with Dalhousie University. The authors would like to thank all who generously provided the segmentations used in this study.