Chloé Hébant

Duong Hieu Phan

David Pointcheval

Decentralized Evaluation of Quadratic Polynomials on Encrypted Data

Keywords: Decentralization, Fully Homormorphic Encryption, 2-DNF

Since the seminal paper on Fully Homomorphic Encryption (FHE) by Gentry in 2009, a lot of work and improvements have been proposed, with an amazing number of possible applications. It allows outsourcing any kind of computations on encrypted data, and thus without leaking any information to the provider who performs the computations. This is quite useful for many sensitive data (finance, medical, etc.). Unfortunately, FHE fails at providing some computation on private inputs to a third party, in cleartext: the user that can decrypt the result is able to decrypt the inputs. A classical approach to allow limited decryption power is distributed decryption. But none of the actual FHE schemes allows distributed decryption, at least with an efficient protocol. In this paper, we revisit the Boneh-Goh-Nissim (BGN) cryptosystem, and the Freeman's variant, that allow evaluation of quadratic polynomials, or any 2-DNF formula. Whereas the BGN scheme relies on integer factoring for the trapdoor in the composite-order group, and thus possesses one public/secret key only, the Freeman's scheme can handle multiple users with one general setup that just needs to define a pairing-based algebraic structure. We show that it can be efficiently decentralized, with an efficient distributed key generation algorithm, without any trusted dealer, but also efficient distributed decryption and distributed re-encryption, in a threshold setting. We then provide some applications of computations on encrypted data, without central authority.

Introduction

Decentralized Cryptography is one of the main directions of research in cryptography, especially in a concurrent environment of multi-user applications, where there is no way to trust any authority. Recently, the rise of blockchain's applications also witnessed the importance of decentralized applications. However, the blockchain mainly addresses the decentralized validation of transactions, but it does not help in decentralizing computations. For the computational purpose, though general solutions can be achieved via multi-party computation, reasonably efficient solutions only exist for a limited number of protocols, as decentralization usually adds constraints to the design of protocols: in broadcast encryption [FN94], the decentralized protocol in [PPS12] is much less efficient than the underlying original protocol [NNL01]; in attributebased encryption [SW05], the decentralized scheme [CC09] implies some constraints on the access control policy, that are removed in [LW11], but at the cost of the use of bilinear groups of composite order with 3 prime factors; etc.

Decentralized Computing over Encrypted Data. In the last decade, the most active research direction carries on computing over encrypted data, with the seminal papers on Fully Homomorphic Encryption (FHE) [Gen09] and on Functional Encryption (FE) [BSW11, GKP + 13, GGH + 13]. FE was generalized to the case of multi-user setting via the notion of multi-input/multiclient FE[GGG + 14, GGJS13, GKL + 13]. It is of practical interest to consider the decentralization for FHE and FE without need of trust in any authority. In FE, the question in the multi-client setting was recently addressed by Chotard et al. [CDG + 18] for the inner product function and then improved in [ABKW19, CSG + 18], where all the clients agree and contribute to generate the functional decryption keys, there is no need of central authority anymore. Note that, in FE, there are efficient solutions for quadratic functions [Gay16, BCFG17] but actually, only linear function evaluations can be decentralized as none of the methods to decentralize linear schemes c Springer 2019. seems to apply, and no new method has been proposed so far. We consider, in this paper, the practical case of decentralizing FHE in multi-user setting. However, the general solution for FHE is still not yet practical, as FHE decryption requires rounding operations that are hard to efficiently distribute. Thus we only consider decentralized evaluation of quadratic polynomials. Moreover, as only decentralized linear computation was possible before, this paper can improve the efficiency of multi-party computation scheme by allowing quadratic steps and thus, improve the number of interactions needed. To motivate our work, we focus on some real-life applications in the last section which only require evaluations of quadratic polynomials so that specific target users can get the result in clear, by running re-encryption in a distributed manner under the keys of the target users.

Technical Contribution

We design an efficient distributed evaluation for quadratic polynomials, with decentralized generation of the keys. proposed a nice solution for quadratic polynomials evaluation. However, their solution relies on a composite-order elliptic curve and thus on the hardness of the integer factoring. This possibly leads to a distributed solution, but that is highly inefficient. Indeed, no efficient multi-party generation of distributed RSA modulus is known, except for 2 parties. But even the recent construction [FLOP18], the most efficient up to now, is still quite inefficient as it relies on oblivious transfer in the semi-honest setting, and on an IND-CPA encryption scheme, coin-tossing, zero-knowledge and secure two-party computation protocols in the malicious setting. Catalano and Fiore [CF15] introduced an efficient technique to transform a linearly-homomorphic encryption into a scheme able to evaluate quadratic operations on ciphertexts. They are able to support decryption of a large plaintext space after the multiplication. However, as in Kawai et al. [KMH + 19] which used this technique to perform proxy re-encryption, they only consider a subclass of degree-2 polynomials where the number of additions of degree-2 terms is bounded by a constant. This is not enough for most of the applications and we do not try to decentralize these limited protocols.

Our Approach. Freeman [Fre10] proposed a conversion from composite-order groups to primeorder groups for the purpose of improving the efficiency. Interestingly, Freeman's conversion allows multi-user setting, since a common setup can handle several keys. But we additionally show it is well-suited for distributed evaluation of 2-DNF formulae. Actually, working in primeorder groups, we can avoid the bottleneck of a distributed generation of RSA moduli. However, it is not enough to have an efficient distributed setup. One also needs to distribute any use of the private keys in the construction: for decryption and re-encryption (see Section A.10). Unfortunately, the Freeman's generic description with projection matrices does not directly allow the design of a decentralized scheme, i.e., with efficient distributed (threshold) decryption without any trusted dealer. We thus specify particular projections, with well-chosen private and public keys. This leads to an efficient decentralized version with distributed private computations. Our main contribution is to prove that using particular projection matrices does not weaken the global construction.

Related Work. In a previous and independent work, Attrapadung et al. [AHM + 18] proposed an efficient two-level homomorphic encryption in prime-order groups. They put forward a new approach that avoids the Freeman's transformation from BGN encryption. Interestingly, our work shows this scheme falls into the Freeman's framework because their construction is similar to the simplified non-decentralized version of our scheme which is obtained from BGN via a Freeman transformation with a particular choice of projections. The concrete implementations in [AHM + 18] show that such a scheme is quite efficient, which applies to our construction, and even to the distributed construction as each server, for a partial decryption, essentially has to perform a decryption with its share. In another unpublished work [CPRT18], Culnane et al. considered a universally verifiable MPC protocol in which one of the two steps is to distribute the key generation in somewhat homomorphic cryptosystems. However, as we mentioned above, the Freeman's generic description with projection matrices, as considered in [CPRT18], does not lead to an efficient distributed decryption. In short, our result bridges the gap between the objective of decentralization as in [CPRT18] and the efficiency goal as in [AHM + 18].

Applications

Boneh, Goh, and Nissim proposed two main applications to secure evaluation of quadratic polynomials: private information retrieval schemes (PIR) and electronic voting protocols. However, the use of our decentralized scheme for electronic voting is much more preferable than the BGN scheme, as there is no way to trust any dealer in such a use-case. We propose two more applications that are related to the group testing and the consistency model in machine learning. Our applications are particularly useful in practice in a decentralized setting, as they deal with sensitive data. Interestingly, the use of distributed evaluation for quadratic polynomials in these applications is highly non-trivial and will be explained in the last section.

Preliminaries

Notations

We denote by x $ ← X the process of selecting x uniformly at random in the set X. Let Z p = Z/pZ be the ring of integers modulo p. For any group G, we denote by g the space generated by g ∈ G.

Bilinear Group Setting

A bilinear group generator G is an algorithm that takes as input a security parameter λ and outputs a tuple (G 1 , G 2 , G T , p, g 1 , g 2 , e) such that G 1 = g 1 and G 2 = g 2 are cyclic groups of prime order p (a λ-bit prime integer), and e : G 1 × G 2 → G T is an admissible pairing:

e is bilinear: for all a, b ∈ Z p , e(g a 1 , g b 2 ) = e(g 1 , g 2 ) ab ; e is efficiently computable (in polynomial-time in λ); e is non-degenerate: e(g 1 , g 2 ) = 1. Furthermore, the bilinear setting (G 1 , G 2 , G T , p, g 1 , g 2 , e) is said asymmetric when G 1 = G 2 . This will be our setting, while the BGN encryption scheme uses a symmetric setting, with composite-order groups.

Computational Assumption

Our security results rely on the Decisional Diffie-Hellman assumption: Definition 1. Let G = g be a cyclic group of prime order p. The advantage Adv ddh G (A) of an adversary A against the Decisional Diffie-Hellman (DDH) problem in G is defined by:

Pr A(g, g x , g y , g xy ) = 1|x, y $ ← Z p -Pr A(g, g x , g y , g z ) = 1|x, y, z $ ← Z p .
We say that the DDH problem in G is (t, ε)-hard if for any advantage A running within time t, its advantage Adv ddh G (A) is bounded by ε. We denote by Adv ddh G (t) the best advantage any adversary can get within time t.

Exp ind-cpa-b E (A) : param ← Setup(λ); (sk, pk) ← Keygen(param); (s, m0, m1) ← A(pk) C ← Encrypt(pk, m b ); b ← A(s, C); return b Figure 1. Experiment of IND-CPA

Security Notions

Let us now recall the semantic security, a.k.a. indistinguishability (or IND-CPA), for a public-key encryption scheme, according to the experiment presented in Figure 1, where the attack is in two steps, and so the adversary outputs a state s to resume the process in the second step.

Definition 2. Let E = (Setup, Keygen, Encrypt, Decrypt) be an encryption scheme. Let us denote Exp ind-cpa-b E (A) the experiment defined in Figure 1. The advantage Adv ind-cpa

E (A) of an ad- versary A against indistinguishability under chosen plaintext attacks (IND-CPA) is Pr[Exp ind-cpa-1 E (A) = 1] -Pr[Exp ind-cpa-0 E (A) = 1]. We say that an encryption scheme E is (t, ε) -IND-CPA if for any adversary A running within time t, its advantage Adv ind-cpa E (A) is bounded by ε.
We denote by Adv ind-cpa E (t) the best advantage any adversary A can get within time t.

Encryption for Quadratic Polynomial Evaluation

To evaluate 2-DNF formulae on encrypted data, Boneh-Goh-Nissim described a cryptosystem [BGN05] that supports additions, one multiplication layer, and additions. They used a bilinear map on a composite-order group and the secret key is the factorization of the order of the group. Unfortunately, composite-order groups require huge orders, since the factorization must be difficult, with costly pairing evaluations.

Freeman's Framework

In order to improve on the efficiency, Freeman in [Fre10, Section 5] proposed a system on primeorder groups, using a similar property of noise that can be removed, with the general definition of subgroup decision problem. Let us recall the Freeman's cryptosystem: Keygen(λ): Given a security parameter λ, it generates a description of three Abelian groups G, H, G T and a pairing e : G × H → G T . It also generates a description of two subgroups G 1 ⊂ G, H 1 ⊂ H and two homomorphisms π 1 , π 2 such that G 1 , H 1 are contained in the kernels of π 1 , π 2 respectively. It picks g $ ← G and h $ ← H, and outputs the public key pk = (G, H, g, h, G 1 , H 1 ) and the private key sk = (π 1 , π 2 ). Encrypt(pk, m): To encrypt a message m using public key pk, one picks g

1 $ ← G 1 and h 1 $ ← H 1 , and outputs the ciphertext (C A , C B ) = (g m • g 1 , h m • h 1 ) ∈ G × H. Decrypt(sk, C): Given C = (C A , C B ), output m ← log π 1 (g) (π 1 (C A )) (which should be the same as log π 2 (h) (π 2 (C B ))).
The Freeman's scheme is also additively homomorphic. Moroever, if an homomorphism π T exists such that, for all g ∈ G, h ∈ H, e(π 1 (g), π 2 (h)) = π T (e(g, h)), we can get, as above, a ciphertext in G T of the product of the two plaintexts, when multiplying the ciphertexts in G and H. The new encryption scheme in G T is still additively homomorphic, and allows evaluations of 2-DNF formulae.

Remark 3. We note that in the Freeman's cryptosystem, ciphertexts contain encryptions of m in both G and H to allow any kind of additions and multiplication. But one could focus on just one ciphertext when one knows the formula to be evaluated.

Optimized Version

In the Appendix A, we present the translation of the Freeman's approach with projection matrices. This indeed leads to a public-key encryption scheme that can evaluate quadratic polynomials in Z p , under the DDH assumption. However, because of the secret key that must be a projection matrix, the distributed generation, while possible (see Appendix A.10), is not as efficient as one can expect. We thus now propose a particular instantiation of projections, which allows very compact keys and ciphertexts. In addition, this will allow to generate keys in a distributed manner, without any trusted dealer. While in the generic transformation of Freeman, the secret key belongs to the whole projection matrix space, our particular instantiation of projections means that the secret key will belong to a proper sub-space of the projection matrix space. Indeed, it is possible to reduce by a factor two the size of the keys: for s ∈ {1, 2}, the secret key is just one scalar and the public key one group element in G s . For the keys, we will consider orthogonal projections on (1, x) , for any x ∈ Z p . Thus, sk s can simply be described by x ∈ Z p , which is enough to define the projection. The public key pk s can simply be described by g -x s ∈ G s , which is enough to define (g -x s , g s ), as (-x, 1) is a vector in the kernel of the projection, to add noise that the secret key will be able to remove.

More precisely, we can describe our optimized encryption schemes, for s ∈ {1, 2, T }, as E s : (Setup, Keygen s , Encrypt s , Decrypt s ) with a common Setup: Setup(λ): Given a security parameter λ, run and output

param = (G 1 , G 2 , G T , p, g 1 , g 2 , e) ← G(λ).
Keygen s (param): For s ∈ {1, 2}. Choose x s $ ← Z p and output the public key pk s = g -xs s and the private key sk s = x s . From (pk 1 , sk 1 ) ← Keygen 1 (param) and (pk 2 , sk 2 ) ← Keygen 2 (param), one can consider pk T = (pk 1 , pk 2 ) and sk T = (sk 1 , sk 2 ), which are associated public and private keys in G T . Encrypt s (pk s , m): For s ∈ {1, 2}, to encrypt a message m ∈ Z p using public key pk s , choose r $ ← Z p and output the ciphertext

C s = (c s,1 = g m s • pk r s , c s,2 = g r s ) ∈ G 2 s .
For s = T , to encrypt a message m ∈ Z p using public key pk T = (pk 1 , pk 2 ), choose r 11 , r 12 , r 21 , r 22 $ ← Z 4 p and output the ciphertext

C T =      c T,1 = e(g 1 , g 2 ) m • e(g 1 , pk 2 ) r 11 • e(pk 1 , g 2 ) r 21 , c T,2 = e(g 1 , g 2 ) r 11 • e(pk 1 , g 2 ) r 22 , c T,3 = e(g 1 , pk 2 ) r 12 • e(g 1 , g 2 ) r 21 , c T,4 = e(g 1 , g 2 ) r 12 +r 22      ∈ G 4 T Decrypt s (sk s , C s ): For s ∈ {1, 2}, given C s = (c s,1 , c s,2
) and the private key sk s , compute d = c s,1 •c sks s,2 and output the logarithm of d in basis g s . For s = T , given

C T = (c T,1 , c T,2 , c T,3 , c T,4 ) and sk T = (sk 1 , sk 2 ), compute d = c T,1 • c sk 2 T,2 • c sk 1 T,3 • c sk 1 •sk 2 T,4
and output the logarithm of d in basis e(g 1 , g 2 ).

In G 1 and G 2 , this is actually the classical ElGamal encryption. We essentially extend it to G T , to handle quadratic operations:

Add(C s , C s ) just consists of the component-wise product in G s ; Multiply(C 1 , C 2 ) for C 1 = (c 1,1 = g m 1 1 • pk r 1 1 , c 1,2 = g r 1 1 ) ∈ G 2 1 and C 2 = (c 2,1 = g m 2 2 • pk r 2 2 , c 2,2 = g r 2
2 ) ∈ G 2 2 , consists of the tensor product:

C T = (e(c 1,1 , c 2,1 ), e(c 1,1 , c 2,2 ), e(c 1,2 , c 2,1 ), e(c 1,2 , c 2,2 )) ∈ G 4
T Randomize s (pk s , C s ) is, as usual, the addition of a random ciphertext of 0 in the same group G s . For s ∈ {1, 2}: Given a ciphertext C s = (c s,1 , c s,2 ) with its public key pk s , it chooses r $ ← Z p and outputs (c s,1 • pk r s , c s,2 • g r s ); while for s = T , a public key pk T and a ciphertext (c T,1 , c T,2 , c T,3 , c T,4 ), it chooses r 11 , r 12 , r 21 , r 22 $ ← Z p and outputs (c T,1 • e(g 1 , pk 2 ) r 11 • e(pk 1 , g 2 ) r 21 , c T,2 •e(g 1 , g 2 ) r 11 •e(pk 1 , g 2 ) r 22 , c T,3 •e(g 1 , pk 2 ) r 12 •e(g 1 , g 2 ) r 21 , c T,4 •e(g 1 , g 2 ) r 12 +r 22 ).

Security Properties

Whereas the correctness directly comes from the correctness of the Freeman's construction, presented in the Appendix A, and verification is straightforward, the semantic security comes from the classical ElGamal encryption security, under the DDH assumptions, for the basic schemes in G 1 and G 2 : Theorem 4. For s ∈ {1, 2}, E s is IND-CPA under the DDH assumption in G s : for any adversary A running within time t, Adv ind-cpa

Es (A) ≤ 2 × Adv ddh Gs (t). Corollary 5. E T is IND-CPA under the DDH assumptions in G 1 or G 2 .
Proof. The semantic security for ciphertexts in G T comes from the fact that:

Encrypt T (pk T , m) = Multiply(Encrypt 1 (pk 1 , m), Encrypt 2 (pk 2 , 1)) = Multiply(Encrypt 1 (pk 1 , 1), Encrypt 2 (pk 2 , m)) Indeed, with this relation, each ciphertext in G 1 can be transformed into a ciphertext in G T (idem with a ciphertext in G 2 ). Let A be an adversary against IND-CPA of E T , in G T .
Game G 0 : In the first game, the simulator plays the role of the challenger in the experiment Exp ind-cpa-0

E T (A)
, where b = 0:

-param = (G 1 , G 2 , G T , p, g 1 , g 2 , e) ← Setup(λ) -(sk 1 , pk 1 ) ← Keygen 1 (param),(sk 2 , pk 2 ) ← Keygen 2 (param) -m 0 , m 1 ← A(param, (pk 1 , pk 2 )); C T = Encrypt T ((pk 1 , pk 2 ), m 0 ) -β ← A(param, (pk 1 , pk 2 ), C T ) We are interested in the event E: b = 1. By definition, Pr G 0 [E] = Pr Exp ind-cpa-0 E T (A) = 1 .
Game G 1 : The simulator interacts with a challenger in Exp ind-cpa-0 E 1 (A), where b = 0. It thus first receives param, pk 1 from that challenger, generates pk 2 by himself to provide (pk T = (pk 1 , pk 2 )) to the adversary. The latter sends back (m 0 , m 1 ) the simulators forwards to the challenger. It gets back

C 1 = Encrypt 1 (pk 1 , m 0 ). It can compute C T = Multiply(C 1 , Encrypt 2 (pk 2 , 1
)), to be sent to the adversary. This game is perfectly indistinguishable from the previous one:

Pr G 1 [E] = Pr G 0 [E]. Game G 2 : The simulator interacts with a challenger in Exp ind-cpa-1 E 1 (A), where b = 1: Pr G 2 [E] -Pr G 1 [E] ≤ Adv ind-cpa E 1 (t + 4 • t p + 4 • t e ),
where t p is the time for one pairing and t e the time for one exponentiation. Game G 3 : In this final game, the simulator plays the role of the challenger in Exp ind-cpa-1 E T (A), where b = 1. This game is perfectly indistinguishable from the previous one:

Pr G 3 [E] = Pr G 2 [E]. One can note, that in this last game, Pr G 3 [E] = Pr Exp ind-cpa-1 E T (A) = 1 , hence Adv ind-cpa E T (A) ≤ Adv ind-cpa E 1 (t + 4 • t p + 4 • t e ),
which concludes the proof, since it works exactly the same way for G 2 .

We stress that the security of E T only requires the DDH assumption in one of the two groups, and not the SXDH assumption (which means that the DDH assumption holds in both G 1 and G 2 ).

Decentralized Homomorphic Encryption

Our main motivation was a decentralized key generation and a distributed decryption in order to be able to compute on encrypted data so that nobody can decrypt intermediate values but the result can be provided in clear to a target user. We now show that our optimized construction allows both decentralized key generation without a trusted dealer and distributed decryption. They are both quite efficient. When a result should be available to a unique user, a classical technique called proxy re-encryption [BBS98] is to re-encrypt to this target user: this is a virtual decryption followed by encryption under the new key. We also show this is possible to do it in a distributed way, without any leakage of information.

Decentralized Key Generation

In fact, a classical decentralized t-out-of-n threshold secret sharing allows to generate the shares of a random element and it seems hard (if one expects efficiency) to use it to generate the shares of a structured matrix, such as projections required in the generic construction, because its elements are not independently random. In our specific construction, the secret keys in G 1 and G 2 are now one scalar and one can perform a classical t-out-of-n threshold secret sharing: each player i generates a random polynomial P i of degree t-1 in Z p [X], privately sends x i,j = P i (j) to player j, and publishes g -P i (0) s ; each player i then aggregates the values into sk i = j x j,i = P (i), for P = j P j , which leads to a share of x = P (0), and the public key is the product of all the public values.

Distributed Decryption

In order to decrypt C s = (c s,1 , c s,2 ) in G 1 or G 2 , each player in a sub-set of t players sends its contribution c sk i s,2 , that can be multiplied with Lagrange coefficients as exponents to obtain the mask c sk s,2 = pk -r s . To decrypt

C T = (c T,1 , c T,2 , c T,3 , c T,4 ) in G T , one can first use the shares of sk 1 to compute c sk 1
T,3 and c sk 1 T,4 , and then the shares of sk 2 to compute c sk 2 T,2 and c

sk 1 •sk 2 T,4 . Under the DDH assumptions in G 1 , G 2 and G T , one can show that the intermediate values c sk i s,2 , or c sk 1 T,3 , c sk 1 T,4 , c sk 2 T,2 , and c sk 1 •sk 2 T,4
do not leak more than the decryption itself. Of course, classical verifiable secret sharing techniques can be used, for both the decentralized generation and the distributed decryption. This can allow, with simple Schnorr-like proofs of Diffie-Hellman tuples, universal verifiability.

Distributed Re-encryption

Besides a distributed decryption, when outsourcing some computations on private information, a distributed authority may want to re-encrypt the encrypted result to a specific user, so that the latter can get the result in clear, and nobody else. More precisely, we assume the input data were encrypted under the keys pk 1 , pk 2 , and pk T = (pk 1 , pk 2 ), which leads, after quadratic evaluations, to a resulting ciphertext under the key pk T , for which the distributed authorities, knowing a t-out-of-n additive secret sharing (sk 1,i , sk 2,i ) i of (sk 1 , sk 2 ), will re-encrypt under PK T = (PK 1 , PK 2 ) for the target user.

Of course, such a re-encryption can be performed using multi-party computation, but we will show an efficient way to do it. And we start with the re-encryption of

c s = (c s,1 = g m s •pk r s , c s,2 = g r s ): player i chooses r i $ ← Z p , computes α i = c sk s,i s,2 • PK r i s and β i = g r i
s , and outputs (α i , β i ). Then, anybody can compute, for the appropriate Lagrange coefficients λ i 's,

C s = (C s,1 = c s,1 × α λ i i = g m s pk r s g r•sks s • PK r s = g m s • PK r s , C s,2 = β λ i i = g r s )
with r = λ i r i , where the sum is on the t members available.

For

s = T , given a ciphertext c T = (c T,1 , c T,2 , c T,3 , c T,4 ), player i chooses u i $ ← Z p ,

and first computes and sends α

3,i = c sk 1,i T,4 • e(g 1 , g 2 ) -u i . With a linear combination for the appropriate Lagrange coefficients λ i 's, anybody can compute, α 3 = α λ i 3,i = c sk 1 T,4 • e(g 1 , g 2 ) -u , with implicit u = λ i u i . Then each player i chooses r 11,i , r 12,i , r 21,i , r 22,i , v i $ ← Z p and computes α 1,i = c sk 2,i T,2 • e(PK 1 , g 2 ) r 21,i β i = e(g 1 , g 2 ) r 11,i +u i • e(PK 1 , g 2 ) r 22,i α 2,i = c sk 1,i T,3 • e(g 1 , PK 2 ) r 11,i γ i = e(g 1 , PK 2 ) r 12,i • e(g 1 , g 2 ) r 21,i +v i α 4,i = α sk 2,i 3 • e(PK 1 , g 2 ) v i δ i = e(g 1 , g 2 ) r 12,i +r 22,i
Again, with linear combinations for the appropriate Lagrange coefficients λ i 's, anybody can compute, with r jk = λ i r jk,i , for j, k ∈ {1, 2}, and v = λ i v i :

α 1 = c sk 2 T,2 • e(PK 1 , g 2 ) r 21 C T,2 = e(g 1 , g 2 ) r 11 +u • e(PK 1 , g 2 ) r 22 α 2 = c sk 1 T,3 • e(g 1 , PK 2 ) r 11 C T,3 = e(g 1 , PK 2 ) r 12 • e(g 1 , g 2 ) r 21 +v α 4 = c sk 1 sk 2 T,4 • e(g 1 , PK 2 ) u • e(PK 1 , g 2 ) v C T,4 = e(g 1 , g 2 ) r 12 +r 22 Then, C T,1 = c T,1 × α 1 α 2 α 4 = e(g 1 , g 2 ) m • e(g 1 , PK 2 ) r 11 +u • e(PK 1 , g 2 ) r 21 +v , so that C T = (C T,1 , C T,2 , C T,3 , C T,4
) is a re-encryption of c T under PK T .

For random scalars, the re-encryption algorithms (which is just a one-round protocol in G 1 and G 2 , but 2-round in G T ) generate new ciphertexts under appropriate keys that look perfectly fresh. In addition, one can claim: Theorem 6. The above distributed protocols for re-encryption do not leak additional information than the outputs of the non-distributed algorithms.

Proof. The goal of this proof is to show that the distributed protocol to re-encrypt a ciphertext under PK s does not leak more information than a direct encryption under PK s . For s ∈ {1, 2}, one is given

c s = Encrypt s (m, pk s ; r) = (c s,1 , c s,2 ) and C s = Encrypt s (m, PK s ; R) = (C s,1 , C s,2
), two ciphertexts of the same message m under pk s and PK s respectively. One can then note that

C s,1 /c s,1 = PK R s /pk r s = c sks s,2 /C SKs s,2 .
The Re-Encryption in G s , for s ∈ {1, 2}.

Game G 0 : In the first game, the simulator just receives c s = (c s,1 , c s,2 ), and plays the real protocol using the t-out-of-n distributed keys (sk s,i ) i to provide the keys to the corrupted users and to generate the values

α i = c sk s,i s,2 •PK r i s and β i = g r i
s , on behalf of the non-corrupted players. We assume that among t players, are honest and t -are corrupted. The latter are assumed to receive the secret keys sk s,i and to generate their own outputs (α i , β i ). The view of the attacker consists of the set of all the honest (α i , β i ).

Game G 1 : The simulator is now given c s = (c s,1 , c s,2 ) and C s = (C s,1 , C s,2 ) that encrypt the same message. We want, for the appropriate Lagrange coefficients

λ i C s,1 = c s,1 • α λ i i C s,2 = β λ i i .
Hence, the simulator can take, for all the honest players except the last one,

r i $ ← Z p to compute α i = c sk s,i s,2 • PK r i s and β i = g r i s .
For the last honest player, from all the honest-user shares and corrupted-user shares, one sets

α = (C s,1 /c s,1 • i = α -λ i i ) 1/λ β = (C s,2 • i = β -λ i i ) 1/λ .
Then, for the t players:

α λ i i = c sks s,2 • PK r s and β λ i i = g r s , for r = λ i r i and with the implicit r = (R -i = λ i r i )/λ . So r = R.
The view of the attacker remains exactly the same. Game G 2 : In this game, the simulator also takes as input a Diffie-Hellman tuple (A = g r , B = PK r s ) with (g s , PK s ): it first derives enough independent pairs

(A i , B i ) = (g x i s •A y i , PK x i s •B y i ), for random x i , y i ,
for all the non-corrupted players (excepted the last one), and computes

α i = c sk s,i s,2 • B i , β i = A i . Since (g s , PK s , A, B
) is a Diffie-Hellman tuple, the view is perfectly indistinguishable from the previous one. Game G 3 : In this game, the simulator now receives a random tuple (A, B), which makes all the (A i , B i ) independent random pairs, the rest is unchanged: under the DDH assumption in G s , the view is computationally indistinguishable. Game G 4 : This is the final simulation, where all the honest shares (α i , β i ) are chosen at random, except the last ones (α , β ) that are still computed as above to complete the values using c s and C s : the view is perfectly indistinguishable from the previous one and does not leak information.

As a consequence, we have proven that there is a simulator (defined in the last game) that produces a view indistinguishable from the real view, with just the input-output pairs. This proves that nothing else leaks.

The Re-Encryption in G T . The proof follows the same path as in the previous proof: one is given two ciphertexts c T = Encrypt T (m, (pk 1 , pk 2 ); r 11 , r 12 , r 21 , r 22 ) and

C T = Encrypt T (m, (PK 1 , PK 2 ); R 11 , R 12 , R 21 , R 22
) of the same message m under pk T and PK T respectively. One needs to simulate all the α 1,i , α 2,i , α 3,i , α 4,i , β i , γ i , δ i for all the non-corrupted players. Since c T and C T encrypt the same message, and we want

C T,1 = c T,1 • α λ i 1,i • α λ i 2,i • α λ i 4,i C T,2 = β λ i i C T,3 = γ λ i i C T,4 = δ λ i i
the simulator can take, for all the honest players except the last one, r 11,i , r 12,i , r 21,i , r 22,i , u i , v i $ ← Z p to compute, in the first round:

α 3,i = c sk 1,i T,4 • e(g 1 , g 2 ) -u i α 3, $ ← G T α 3 = α λ i 3,i
and in the second round, for all but the last honest player

α 1,i = c sk 2,i T,2 • e(PK 1 , g 2 ) r 21,i β i = e(g 1 , g 2 ) r 11,i +u i • e(PK 1 , g 2 ) r 22,i α 2,i = c sk 1,i T,3 • e(g 1 , PK 2 ) r 11,i γ i = e(g 1 , PK 2 ) r 12,i • e(g 1 , g 2 ) r 21,i +v i α 4,i = α sk 2,i 3 • e(PK 1 , g 2 ) v i δ i = e(g 1 , g 2 ) r 12,i +r 22,i
and for the last honest player:

α 2, $ ← G T β = (C T,2 × i = β -λ i i ) 1/λ α 4, $ ← G T γ = (C T,3 × i = γ -λ i i ) 1/λ δ = (C T,4 × i = δ -λ i i ) 1/λ
which implies implicit values for r 11, , r 12, , r 21, , r 22, , u , v because the above system is invertible, where X, Y , and Z are the constant values introduced by c sk j

T,i , for some i, j:

λ ×          log β log γ log δ log α 4, log α 3, log α 2,          =          0 0 0 X Y Z          +          1 0 0 -sk 1 1 0 0 sk 2 1 0 0 -1 0 1 0 1 0 0 0 0 0 0 sk 2, -1 0 0 0 0 1 0 1 0 0 0 0 0                    r 11, r 12, r 21, r 22, u v          
Then it is possible to set:

α 1, = (C T,1 /(c T,1 • α 2 α 4 ) × i = α -λ i 1,i ) 1/λ
. First, this is clear that the α 3,i 's do not leak anything as they contain random masks e(g 1 , g 2 ) -u i . Then, to prove that all the α 1,i , α 2,i , α 4,i , β i , γ i , δ i do not leak information, one can perform a similar proof as above for G s , by using the DDH assumption in both G 1 and G 2 . Indeed, each element is masked using a pair either (g r 2 , PK r 2 ) or (g r 1 , PK r 1 ), for some random r. If one wants to have an indistinguishability under the SXDH assumption (and thus only one DDH assumption in one group), one could add more masks. But this does not make sense to have one key compromised and not the other one, for the same user. Hence, we tried to make the re-encryption as efficient as possible.

We stress that for the re-encryption in G 1 or G 2 , one just needs the DDH assumption in this group G s . But for the re-encryption in G T , one needs the DDH assumption in both G 1 and G 2 (the so-called SXDH assumption). We could rely on only one of the two, by adding masking factors, but this does not really make sense for a user to have his private key sk 1 being compromised without sk 2 (or the opposite).

In addition, zero-knowledge proofs can be provided to guarantee the re-encryption is honestly applied: they just consist in proofs of representations, when g sk s,i s are all made public, for s ∈ {1, 2} and all indices i.

Efficiency

In the concrete case where we have n servers able to perform a distributed protocol as described above, each of them has two scalars corresponding to a secret key for the encryption in G 1 and a secret key for the encryption in G 2 . We recall that a ciphertext, in G 1 or G 2 , is composed of two group elements, and a ciphertext in G T is composed of four group elements. A recipient, that wants the result of either a decryption or a re-encryption with the help of t servers, has to perform a few exponentiations. The table below details the number of exponentiations for each player involved in the distributed protocols.

Applications

Encryption for Boolean Formulae

In this part, we detail the specific case of the evaluation of 2-DNF.

per server recipient distributed decryption in G1/G2 1 t in GT 4 4t distributed re-encryption in G1/G2 3 t in GT 13 7t
First, as explained in [BGN05], a way to guarantee the ciphertexts are encryption of inputs in {0, 1}, the verification can be done with our scheme (or the one of BGN or Freeman) with the additional term Add j (Multiply(C x j , Add(C x j , C -1 )), multiplied by a random constant, so that it adds zero if inputs are correct, or it adds a random value otherwise. This introduces a quadratic term, just for the verification. This is at no extra cost if the Boolean formula is already quadratic, which will be the case of our applications.

Every Boolean formula can be expressed as a disjunction of conjunctive clauses (an OR of ANDs). This form is called disjunctive normal form (DNF) and, more precisely, k-DNF when each clause contains at most k literals. Thus, a 2-DNF formula over the variables x 1 , . . . ,

x n ∈ {0, 1} is of the form m i=1 ( i,1 ∧ i,2 ) with i,1 , i,2 ∈ {x 1 , x 1 , . . . , x n , x n }.
The conversion of 2-DNF formulae into multivariate polynomials of total degree 2 is simple:

given Φ(x 1 , . . . , x n ) = m i=1 ( i,1 ∧ i,2 ) a 2-DNF formula, define φ(x 1 , . . . , x n ) = m i=1 (y i,1 × y i,2
) where y i,j = i,j if i,j ∈ {x 1 , . . . , x n } or y i,j = (1i,j ) otherwise. In this conversion, a true literal is replaced by 1, and a false literal by 0. Then, an OR is converted into an addition, and an AND is converted into a multiplication. A NOT is just (1 -x) when x ∈ {0, 1}. φ(x 1 , . . . , x n ) is the multivariate polynomial of degree 2 corresponding to Φ(x 1 , . . . , x n ). As just said, this conversion works if for the inputs, we consider 1 ∈ Z p as true and 0 ∈ Z p as false, but for the output, 0 ∈ Z p is still considered as false whereas any other non-zero value is considered as true.

To evaluate the 2-DNF in an encrypted manner, we propose to encrypt the data and to calculate the quadratic polynomial corresponding to the 2-DNF as seen above by performing Adds and Multiplys. Because the result of the 2-DNF is a Boolean, when a decryption is performed, if the result is equal to 0, one can consider it corresponds to the 0-bit (false) and else, it corresponds to the 1-bit (true).

Hence, when encrypting bits, we propose two different encodings before encryption, depending on the situation: either the 0-bit (false) is encoded by 0 ∈ Z p and the 1-bit (true) is encoded by any non-zero integer of Z * p ; or the 0-bit (false) is encoded by 0 ∈ Z p and the 1-bit (true) is encoded by 1 ∈ Z p . With this second solution, it offers the possibility to perform one NOT on the data before Adds and Multiplys by the operation 1 -x. However, one has to be aware of making Randomize before decryption to mask the operations but also the input data in some situations: for example, if an Add is performed between three 1s, the result 3 leaks information and needs to be randomized.

Because one just wants to know whether the result is equal to 0 or the result is different from 0, we do not need to compute the logarithm: we can decrypt by just checking whether

c s,1 • c sks s,2 = 1 s or not (for s = T , if c T,1 • c sk 2 T,2 • c sk 1 T,3 • c sk 1 •sk 2 T,4 = 1 T ).

Group Testing on Encrypted Data

In this application we assume that a hospital collects some blood samples and wants to check which samples are positive or negative to a specific test. Group testing [Dor43] is an efficient technique to detect positive samples with fewer tests in the case the proportion of positive cases is small. The technique consists in mixing some samples, and to perform tests on fewer mixes. More precisely, we denote X = (x ij ) the matrix of the mixes: x ij = 1 if the i-th sample is in the j-th mix, otherwise x ij = 0. The hospital then sends the (blood) mixes to a laboratory for testing them: we denote y j the result of the test on the j-th mix. If a patient (its sample) is in a mix with a negative result, he is negative (not infected). If a patient (its sample) is in a mix with a positive result, we cannot say anything. However, for well-chosen parameters, if a patient is not declared negative, he is likely positive. Thus, for a patient i, the formula that we want to evaluate is ¬F i (X, y), which means the patient's test is positive (infected) or not, for F i (X, y) = j (x ij ∧ ¬y j ). The latter is indeed true if there is a mix containing a i-th sample for which the test is negative, and this should claim patient i negative (false). The matrix X of the samples needs to be encrypted since the patient does not want the laboratory to know his result. Because of the sensitiveness of the data, the result of the tests needs to be encrypted too. But the patient will need access to his own result.

In this scenario, the hospital computes for all i, j, C x ij ∈ G 2 1 , the encryption of x ij , and the laboratory computes for all j, C y j ∈ G 2 2 , the encryption of y j . Then, they both send the ciphertexts to an external database. With our homomorphic encryption scheme, to compute ¬F i , we can publicly evaluate the following formula:

C i = Randomize(Add j (Multiply(C x ij , C y j )).
Anybody can publicly verify the computations and if it is correct, a pool of controllers perform a distributed re-encryption of the result of patient i under his key PK i . In this way, the patient cannot decrypt the database or the result of the tests directly, but only with the help of a pool of controller. The goal of the controllers is to limit access to the specific users only. Under an assumption about the collusions among the controllers, nobody excepted the users will have access to their own results.

Consistency Model on Encrypted Data

Another famous application is machine learning, where we have some trainers that fill a database and users who want to know a function of their inputs and the database. For privacy reasons, trainers do not want the users to learn the training set, and users do not want the trainers to learn their inputs. As in the previous case, we will involve a pool of distributed controllers to limit decryptions, but the controllers should not learn anything either.

Suppose a very large network of nodes in which some combinations should be avoided as they would result to failures. When a failure happens, the combination is stored in a database. And before applying a given combination, one can check whether it will likely lead to a failure, and then change. For example, the network can be a group of people where each of them can receive data. But, for some specific reasons, if a subgroup A of people is knowing a file a, the subgroup B must not have the knowledge of a file b. This case of application can be viewed as a consistency model [Sch14] which can be formally described as: the input is a vector of states (each being either true or false), and if in the database all the j-th states are true a new input needs to have its j-th state to be true; if all the j-th states in the database are false, the new input needs to have its j-th state to be false; otherwise the j-th state can be either true or false. As a consequence, if we denote the i-th element of the database as a vector x i = (x ij ) j and the user's vector by y = (y j ), that vector y is said consistent with the database if the following predicate is true:

j (∧ i x ij ∧ y j ) ∨ (∧ i x ij ∧ y j ) ∨ (∨ i x ij ∧ ∨ i x ij ) . Let X j = ∧ i x ij , Y j = ∧ i x ij , and Z j = ∨ i x ij ∧ ∨ i x ij .
We define F(x 1 , . . . , x m , y) the formula we want to compute on the encrypted inputs:

F(x 1 , . . . , x m , y) = j (X j ∧ y j ) ∨ (Y j ∧ y j ) ∨ Z j .
By definition, X j , Y j , and Z j are exclusive, as X j means the literals are all true, Y j means the literals are all false, and Z j means there are both true and false literals. So we have: X j ∨Z j = Y j and Y j ∨ Z j = X j . Thus, we have

¬F(x 1 , . . . , x m , y) = j ((Y j ∨ y j ) ∧ (X j ∨ y j )) .
Now, we see how the encryption and the decryption is performed to obtain the result of an evaluation. First, we explain how the trainers can update the database, when adding a vector x m . The values X j are updated into X j as

X j = m i=1 x ij = m-1 i=1 x ij ∧ x mj = X j = m-1 i=1 x ij if x mj = true false otherwise
which is easy to compute for the trainer, since it knows x m in clear, even if X j is encrypted: the trainer can dynamically compute C X j the encryption of X j , when adding a new line in the database, by just making a Randomize if x mj is true (to keep the value X j unchanged), or by replacing the value by a fresh encryption of 0 otherwise. Similarly, the trainer can update C Y j , the encryption of Y j . On the user-side, he can compute C y j and C y j the encryptions of his inputs y j and y j respectively. Then, everyone and thus the controllers can compute:

C j = Randomize Add j Multiply(Add(C Y j , C y j ), Add(C X j , C y j )) .
Because of the Multiply, C Y j and C y j must be ciphertexts in G 1 , while C X j and C y j must be ciphertexts in G 2 . To allow a control of the final decryption, a pool of controllers re-encrypt for the user in a distributed way.

-For x ∈ Zp, A ∈ Mm,n(Zp):

[x] = g x , [A] = g A = (g a ij ) ij -For x ∈ Zp, A, B ∈ Mm,n(Zp), X ∈ M n,n (Zp), Y ∈ M m ,m (Zp): x • [A] = g xA [A] • X = g AX Y • [A] = g YA [A] [B] = [A + B] -For A ∈ Mm,n(Zp), B ∈ M m ,n (Zp): [A]1 • [B]2 = [A ⊗ B]T

Figure 2. Bracket Notations

A Freeman's Approach

A.1 Notations

The vectors x = (x i ) i and matrices M = (m i,j ) ij are in bold and the vectors are written as row vectors, with sometimes components separated by commas for clarity: if

x $ ← X n , x = (x 1 x 2 • • • x n ) = (x 1 , x 2 , • • • , x n ).
We denote by M m,n (Z p ) the set of matrices on Z p , of size m × n, and thus m row-vectors of length n. (M m,n (Z p ), +) is an Abelian group. When A ∈ M m,n (Z p ) and B ∈ M n,n (Z p ), the matrix product is denoted A × B ∈ M m,n (Z p ), or just AB if there is no ambiguity. (M n,n (Z p ), +, ×) is a ring, and we denote by GL n (Z p ) ⊂ M n,n (Z p ) = M n (Z p ) the subset of the invertible matrices of size n (for the above matrix product ×), which is also called the general linear group.

We will use the tensor product: for two vectors a

= (a 1 , a 2 , • • • , a n ) ∈ Z n p and b = (b 1 , b 2 , • • • , b m ) ∈ Z m p , the tensor product a ⊗ b is the vector (a 1 b, • • • , a n b) = (a 1 b 1 , • • • , a 1 b m , a 2 b 1 , • • • , a 2 b m , • • • , a n b m ) ∈ Z mn p ; and for two matrices A ∈ M m,n (Z p ) and B ∈ M m ,n (Z p ), A =    a 1 . . . a m    B =    b 1 . . . b m    A ⊗ B =       a 1 ⊗ b 1 a 1 ⊗ b 2 . . . a m ⊗ b m       ∈ M mm ,nn (Z p ).
The bilinearity of the tensor product gives, for A, A ∈ M m,n (Z p ) and B, B ∈ M m ,n (Z p ),

(A + A ) ⊗ (B + B ) = (A ⊗ B) + (A ⊗ B ) + (A ⊗ B ) + (A ⊗ B
). We will also use the following important relation between matrix product and tensor product: for

A ∈ M m,k (Z p ), A ∈ M k,n (Z p ), B ∈ M m ,k (Z p ), and B ∈ M k ,n (Z p ), (A×A )⊗(B×B ) = (A⊗B)×(A ⊗B ).
For any group G, we denote by g the space generated by g ∈ G. For a generator g of a cyclic group G = g , we use the implicit representation [a] of any element h = g a ∈ G and by extension we will use the "bracket" notations, which makes use of the above matrix properties over the exponents, that are scalars in Z p when G is a cyclic group of order p. See Figure 2 for more details about the "brackets". In case of bilinear groups, we also define, for

A ∈ M m,n (Z p ) and B ∈ M m ,n (Z p ), [A] 1 • [B] 2 = [A ⊗ B] T ,
which can be evaluated with pairing operations between G 1 and G 2 group elements.

A.2 Projections

In order to continue with matrix properties and linear applications, a projection π, in a space of dimension n, is a linear function such that π •π = π. Any projection of rank 1 can be represented by the matrix P = B -1 U n B, where U n is the canonical projection and B is the change of basis matrix:

U n =      0 . . . 0 0 0 . . . 0 0 0 . . . 0 0 0 . . . 0 1      B =       p 1 . . . p n-1 b      
where K = p 1 , . . . , p n-1 is the kernel of the projection and b the image. Given two projections π 1 and π 2 of rank 1, that are represented by

P 1 = B -1 1 U n B 1 and P 2 = B -1 2 U n B 2 , respectively, the tensor product π = π 1 ⊗ π 2 is represented by P = P 1 ⊗ P 2 , that is equal to (B -1 1 U n B 1 ) ⊗ (B -1 2 U n B 2 ) = (B -1 1 ⊗ B -1 2 ) × (U n ⊗ U n ) × (B 1 ⊗ B 2 ) = (B 1 ⊗ B 2 ) -1 × U n 2 × (B 1 ⊗ B 2 ).
The associated change of basis matrix is thus B = B 1 ⊗ B 2 . In dimension 2:

B 1 = p 1 b 1 and B 2 = p 2 b 2 , then B = B 1 ⊗ B 2 =      p 1 ⊗ p 2 p 1 ⊗ b 2 b 1 ⊗ p 2 b 1 ⊗ b 2      , hence, the image of π = π 1 ⊗ π 2 is spanned by b = b 1 ⊗ b 2 , while {p 1 ⊗ p 2 , p 1 ⊗ b 2 , b 1 ⊗ p 2 }
is a basis of the kernel. But, as explained below,

p 1 ⊗ r 2 + r 1 ⊗ p 2 , for r 1 , r 2 $ ← Z 2
p , provides a uniform sampling in ker(π):

ker(π) = {(x 1 + x 2 ) • p 1 ⊗ p 2 + y 2 • p 1 ⊗ b 2 + y 1 • b 1 ⊗ p 2 , x 1 , x 2 , y 1 , y 2 ∈ Z p } = {p 1 ⊗ (x 2 • p 2 + y 2 • b 2 ) + (x 1 • p 1 + y 1 • b 1 ) ⊗ p , x 1 , x 2 , y 1 , y 2 ∈ Z p }

A.3 Freeman's Scheme with Projections

The main goal of Freeman's approach was to generalize the BGN cryptosystem to any hardsubgroup problems, which allows applications to prime-order groups under the classical Decisional Diffie-Hellman or Decisional Linear assumptions, with high gain in efficiency.

We now present a variant of the Freeman's cryptosystem allowing multiple users, without the twin ciphertexts (in G and H). Since we will work in groups G 1 , G 2 , and G T , the algorithms Keygen, Encrypt and Decrypt will take a sub-script s to precise the group G s in which they operate, but the Setup is common.

Setup(λ): Given a security parameter λ, run and output

param = (G 1 , G 2 , G T , p, g 1 , g 2 , e) ← G(λ). Keygen s (param): For s ∈ {1, 2}, choose B s $ ← GL 2 (Z p ), let P s = B -1
s U 2 B s and p s ∈ ker(P s ) \ {0}, and output the public key pk s = [p s ] s and the private key sk s = P s . In the following, we always implicitly assume that the public keys contain the public parameters param, and the private keys contain the public keys. From (pk 1 , sk 1 ) ← Keygen 1 (param) and (pk 2 , sk 2 ) ← Keygen 2 (param), one can consider pk T = (pk 1 , pk 2 ) and sk T = (sk 1 , sk 2 ), which are associated public and private keys in G T , as we explain below. Encrypt s (pk s , m, A s ): For s ∈ {1, 2}, to encrypt a message m ∈ Z p using public key pk s and

A s = [a] s ∈ G 2 s , choose r $ ← Z p and output the ciphertext C s = (m • [a] s r • [p s ] s , [a] s ) ∈ G 2 s × G 2 s . For s = T , with A s = ([a 1 ] 1 , [a 2 ] 2 ), set [a] T = [a 1 ] 1 • [a 2 ] 2 ∈ G 4 T , choose [r 1 ] 1 $ ← G 2 1 , [r 2 ] 2 $ ← G 2 2 , and output C T = (m • [a] T [p 1 ] 1 • [r 2 ] 2 [r 1 ] 1 • [p 2 ] 2 , [a] T ) ∈ G 4 T × G 4 T . Decrypt s (sk s , C s ): For s ∈ {1, 2}, given C s = ([c s,1 ] s , [c s,2 ] s ) and sk s = P s , let C s = ([c s,1 ] s • P s , [c s,2 ] s • P s ). For s = T , compute C T = ([c T,1 ] T • (P 1 ⊗ P 2 ), [c T,2 ] T • (P 1 ⊗ P 2 )).
In both cases, output the logarithm of the first component of c s,1 in base the first component of c s,2 .

As already explained above, the encryption process masks the message by an element in the kernel of a certain projection. The secret key is the corresponding projection P s which later removes this mask. In the Decrypt algorithm, C s is a Diffie-Hellman tuple (whatever the group under consideration), the discrete logarithm of one component is enough to decrypt, since the plaintext is the common exponent.

One can note that matrices B 1 and B 2 are drawn independently, so the keys in G 1 and G 2 are independent. For any pair of keys (pk 1 = [p 1 ] 1 , pk 2 = [p 2 ] 2 ), one can implicitly define a public key for the target group. To decrypt in the target group, both private keys sk 1 = P 1 and sk 2 = P 2 are needed. Actually, one just needs P 1 ⊗ P 2 to decrypt:

C T = ([c T,1 ] T • (P 1 ⊗ P 2 [c T,2 ] T • (P 1 ⊗ P 2 )
), but P 1 ⊗ P 2 and (P 1 , P 2 ) contain the same information and the latter is more compact.

With the algorithms defined above, we have three encryption schemes E s : (Setup, Keygen s , Encrypt s , Decrypt s ) for s = 1, 2 or T , with a common Setup.

A.4 Correctness of E

1 , E 2 , and E T Proposition 7. For s ∈ {1, 2, T }, E s is correct. Proof. For s = 1, 2: [c s,2 ] s • P s = [a] s • P s = [aP s ] s [c s,1 ] s • P s = (m • [a] s r • [p s ] s ) • P s = m • [a] s • P s r • [p s ] s • P s = m • [aP s ] s r • [p s P s ] s = m • [aP s ] s r • [0] s = m • [aP s ] s For s = T : [c T,2 ] T • (P 1 ⊗ P 2 ) = [a] T • (P 1 ⊗ P 2 ) = [a(P 1 ⊗ P 2 )] T [c T,1 ] T • (P 1 ⊗ P 2 ) = (m • [a] T [p 1 ] 1 • [r 2 ] 2 [r 1 ] 1 • [p 2 ] 2 ) • (P 1 ⊗ P 2 ) = m • [a(P 1 ⊗ P 2 )] T ([p 1 ] 1 • [r 2 ] 2 ) • (P 1 ⊗ P 2 ) ([r 1 ] 1 • [p 2 ] 2 ) • (P 1 ⊗ P 2 ) = m • [a(P 1 ⊗ P 2 )] T [p 1 ⊗ r 2 ] T • (P 1 ⊗ P 2 ) [r 1 ⊗ p 2 ] T • (P 1 ⊗ P 2 ) = m • [a(P 1 ⊗ P 2 )] T [p 1 P 1 ⊗ r 2 P 2 ] T [r 1 P 1 ⊗ p 2 P 2 ] T = m • [a(P 1 ⊗ P 2 )] T [0 ⊗ r 2 P 2 ] T [r 1 P 1 ⊗ 0] T = m • [a(P 1 ⊗ P 2 )] T In both cases, C s,1 = [c s,1 ] s = m•[c s,2 ] s = m•C s,2
. Whatever the size of the vectors, one discrete logarithm computation is enough to extract m.

A.5 Homomorphic Properties

As BGN, Freeman cryptosystem also allows additions, one multiplication layer, and additions: we detail the homomorphic functions below.

Add(C s , C s ): Given two ciphertexts C s = ([c s,1 ] s , [c s,2 ] s ), C = ([c s,1 ] s , [c s,2 ] s ) in one of G 2 1 × G 2 1 , G 2 2 × G 2 2 , G 4 T × G 4 T , if [c s,2 ] s = [c s,2 ] s , it outputs ([c s,1 ] s [c s,1 ] s , [c s,2 ] s ), otherwise it outputs ⊥. Multiply(C 1 , C 2 ): Given two ciphertexts C 1 = ([c 1,1 ] 1 , [c 1,2 ] 1 ) ∈ G 2 1 × G 2 1 and C 2 = ([c 2,1 ] 2 , [c 2,2 ] 2 ) ∈ G 2 2 × G 2 2 , it outputs C T = ([c 1,1 ] 1 • [c 2,1 ] 2 , [c 1,2 ] 1 • [c 2,2 ] 2 ) ∈ G 4 T × G 4 T . Randomize s (pk s , C s ): Given a ciphertext C s = ([c s,1 ] s , [c s,2 ] s ), for s ∈ {1, 2} and a public key pk s = [p s ] s , it chooses α, r $ ← Z p and outputs (α • ([c s,1 ] s r • [p s ] s ), α • [c s,2 ] s ); while for s = T and a public key pk T = ([p 1 ] 1 , [p 2 ] 2 ), it chooses α $ ← Z p , [r 1 ] 1 $ ← G 2 1 and [r 2 ] 2 $ ← G 2 2 , and outputs (α • ([c T,1 ] T [p 1 ] 1 • [r 2 ] 2 [r 1 ] 1 • [p 2 ] 2 ), α • [c T,2 ] T ).
Instead of performing a systematic randomization of ciphertexts as proposed by Freeman each time an Add or a Multiply is computed, we create a specific function Randomize usable at any time, when more privacy is required.

A.6 Correctness of the Homomorphic Properties

Let us check the correctness of the three homomorphic functions: Proposition 8. Add and Multiply are correct.

Proof. Let us first consider the addition operations:

-For s = 1, 2:

Add(Encrypt s (pk s , m, [a] s ; r), Encrypt s (pk s , m , [a] s ; r )) = ([ma + rp s ] s • [m a + r p s ] s , [a] s ) = ([(m + m )a + (r + r )p s ] s , [a] s ) = Encrypt s (pk s , m + m , [a] s ; r + r ) -For s = T : Add(Encrypt T (pk T , m, ([a 1 ] 1 , [a 2 ] 2 ); r 1 , r 2 ), Encrypt T (pk T , m , ([a 1 ] 1 , [a 2 ] 2 ); r 1 , r 2 )) = ([m([a 1 ] 1 • [a 2 2 ) + r 1 ⊗ p 2 + p 1 ⊗ r 2 ] T • [m ([a 1 ] 1 • [a 2 ] 2 ) + r 1 ⊗ p 2 + p 1 ⊗ r 2 ] T , [a 1 ] 1 • [a 2 ] 2 ) = ([(m + m )([a 1 ] 1 • [a 2 ] 2 ) + (r 1 + r 1 ) ⊗ p 2 + p 1 ⊗ (r 2 + r 2 )] T , [a 1 ] 1 • [a 2 ] 2 ) = Encrypt T (pk T , m + m , ([a 1 ] 1 , [a 2 ] 2 ); r 1 + r 1 , r 2 + r 2 )
About multiplication, we can see that

Multiply(Encrypt 1 (pk 1 , m 1 , [a 1 ] 1 ; r 1 ), Encrypt 2 (pk 2 , m 2 , [a 2 ] 2 ; r 2 )) = ([m 1 a 1 + r 1 p 1 ] 1 • [m 2 a 2 + r 2 p 2 ] 2 , [a 1 ] 1 • [a 2 ] 2 ) = ([(m 1 a 1 + r 1 p 1 ) ⊗ (m 2 a 2 + r 2 p 2 )] T , [a 1 ] 1 • [a 2 ] 2 ) = ([m 1 a 1 ⊗ m 2 a 2 + m 1 a 1 ⊗ r 2 p 2 + r 1 p 1 ⊗ m 2 a 2 + r 1 p 1 ⊗ r 2 p 2 ] T , [a 1 ] 1 • [a 2 ] 2 ) = ([m 1 a 1 ⊗ m 2 a 2 + m 1 a 1 ⊗ r 2 p 2 + r 1 p 1 ⊗ (m 2 a 2 + r 2 p 2 )] T , [a 1 ] 1 • [a 2 ] 2 ) = ([m 1 m 2 (a 1 ⊗ a 2 ) + p 1 ⊗ (r 1 m 2 a 2 + r 1 r 2 p 2 ) + (r 2 m 1 a 1 ) ⊗ p 2 ] T , [a 1 ] 1 • [a 2 ] 2 ) = Encrypt T (pk T , m 1 m 2 , ([a 1 ] 1 , [a 2 ] 2 ); m 1 r 2 a 1 , m 2 r 1 a 2 + r 1 r 2 p 2 )
Proposition 9. For s ∈ {1, 2, T }, Randomize s is correct, with α = 1. Proof. For s ∈ {1, 2}:

Randomize s (pk s , Encrypt s (pk s , m, [a] s ; r), α, r ) = ([α(ma + rp s + r p s )] s , [αa] s ) = ([m(αa) + α(r + r )p s ] s , [αa] s ) = Encrypt s (pk s , m, [αa] s ; α(r + r ))
Since r is uniformly distributed, the mask of the first component of the ciphertext is uniformly distributed, as in a fresh ciphertext, while with α = 1, the basis in the second component remains unchanged. In addition, the random α also randomizes the basis [αa] s , in the second component of the ciphertext, but computationally only, under the DDH assumption in G s .

For s = T :

Randomize T (pk T , Encrypt T (pk T , m, ([a 1 ] 1 , [a 2 ] 2 ); r), α, r 1 , r 2 ) = (α • (m • [a] T [p 1 ] 1 • [r 2 ] 2 [r 1 ] 1 • [p 2 ] 2 [p 1 ] 1 • [r 2 ] 2 [r 1 ] 1 • [p 2 ] 2 , [a] T ), ([αa 1 ] 1 , [αa 2 ] 2 )) = (α • (m • [a] T [p 1 ] 1 • [r 2 + r 2 ] 2 [r 1 + r 1 ] 1 • [p 2 ] 2 ), ([αa 1 ] 1 • [αa 2 ] 2 )) = Encrypt T (pk T , m, ([αa 1 ] 1 , [αa 2 ] 2 ); α(r 2 + r 1 ), α(r 2 + r 2 ))
Again, since r 1 and r 2 are uniformly distributed, the mask of the first component of the ciphertext is uniformly distributed, as in a fresh ciphertext. In addition, the random α randomizes the basis in the second component of the ciphertext, but computationally only, under the DDH assumption in both G 1 and G 2 .

Game G 0 : In the first game, the simulator plays the role of the challenger in the experiment Exp ind-cpa-0 E T (A), where b = 0: S(λ):

-

param = (G 1 , G 2 , G T , p, g 1 , g 2 , e) ← Setup(λ) -(sk 1 , pk 1 ) ← Keygen 1 (param),(sk 2 , pk 2 ) ← Keygen 2 (param) -m 0 , m 1 , [a] 1 , [a] 2 ← A(param, (pk 1 , pk 2 )) -C T = Encrypt T ((pk 1 , pk 2 ), m 0 , ([a] 1 , [a] 2 )) -β ← A(param, (pk 1 , pk 2 ), C T ) We are interested in the event E: b = 1. By definition, Pr G 0 [E] = Pr Exp ind-cpa-0 E T (A) = 1 .
Game G 1 : The simulator interacts with a challenger in Exp ind-cpa-0 E 1 (A), where b = 0. It thus first receives param, pk 1 from that challenger, generates pk 2 by himself to provide (pk T = (pk 1 , pk 2 )) to the adversary. The latter sends back (m 0 , m 1 , [a] 1 , [a] 2 ), from which it sends (m 0 , m 1 , [a] 1 ) to the challenger. It gets back

C 1 = Encrypt 1 (pk 1 , m 0 , [a] 1 ). It can compute the ciphertext C T = Multiply(C 1 , Encrypt 2 (pk 2 , 1, [a 2 ] 2 ))
, to be sent to the adversary. This game is perfectly indistinguishable from the previous one:

Pr G 1 [E] = Pr G 0 [E].
Game G 2 : The simulator interacts with a challenger in Exp ind-cpa-1

E 1 (A), where b = 1: Pr G 2 [E] -Pr G 1 [E] ≤ Adv ind-cpa E 1 (t + t m + t e ),
where t m is the time for one multiplication and t e the time for one encryption. Game G 3 : In this final game, the simulator plays the role of the challenger in the experiment Exp ind-cpa-1 ), where b = 1. This game is perfectly indistinguishable from the previous one:

E T (A
Pr G 3 [E] = Pr G 2 [E].
One can note, that in this last game, Pr G 3 [E] = Pr Exp ind-cpa-1

E T (A) = 1 , hence Pr Exp ind-cpa-1 E T (A) = 1 -Pr Exp ind-cpa-0 E T (A) = 1 ≤ Adv ind-cpa E T (t + t m + t e ),
which concludes the proof, since it works exactly the same way for G 2 .

A.8 Re-Encryption

We have three efficient encryption schemes able to compute homomorphic operations and supporting multiple users. Re-encryption, in order to transform a ciphertext for Alice into a ciphertext to Bob, might then be useful, as it will allow to target a specific end-user. With the Freeman's approach, and our formalism, this is just a change of basis in the exponents: we can re-encrypt a message encrypted under a private key pk a into another encryption for a private key pk b by using a special secret key called re-encryption key rk a→b . Below we describe REKeygen s that creates the re-encryption key from the secret keys and Re-encrypt s the function to re-encrypt a ciphertext, but under a different basis. ), as the matrix

R T actually is R 1 ⊗ R 2 . Re-encrypt s (rk a→b s , C s ): To re-encrypt a ciphertext C = ([c s,1 ] s , [c s,2 ] s ): -for s = 1, 2, output ([c s,1 ] s • rk a→b s , [c s,2 ] s • rk a→b s ); -for s = T , output ([c T,1 ] T • (rk a→b 1 ⊗ rk a→b 2 ), [c T,2 ] T • (rk a→b 1 ⊗ rk a→b 2 )).
We stress that the basis a is modified with the re-encryption process, into aR s or a(R 1 ⊗ R 2 ), which could leak some information about the re-encryption key. But as explained above, the randomization process can provide a new ciphertext that computationally hides it, under DDH assumptions. However, this requires this basis a to be part of the ciphertext as it cannot be a constant.

A.9 Correctness of Re-Encryption

The correctness of the re-encryption is based on a change of basis that transforms an element in the kernel of P s in an element in the kernel of P s : let p ∈ ker(P s ) and p ∈ ker(P s ) because ker(P s ) and ker(P s ) are of dimension 1 in Z 2 p , there exist a, b, k ∈ Z p , such that p = k • (a, b) and a , b , k ∈ Z p , such that p = k • (a , b ). We have:

p • rk = p • B -1 B = k(1, 0)B = k(a , b ) ⇒ p • rk = kk -1 p = r p
for some r ∈ Z p and with that, the correctness follows, where rk a→b s is denoted R s : for s ∈ {1, 2},

Re-encrypt s (rk a→b s , Encrypt s (pk a s , m, a, r)) = ([c s,1 ] s • rk a→b s , [c s,2 ] s • rk a→b s ) = ([maR s + rp s R s ] s , [aR s ] s ) = ([maR s + rr p s ] s , [aR s ] s ) = Encrypt s (pk b s , m, aR s ; rr ) For s = T , Re-encrypt T (rk a→b T , Encrypt T (pk a T , m, a; r 1 , r 2 )) = ([c T,1 ] T • (rk a→b 1 ⊗ rk a→b 2 ), [c T,2 ] T • (rk a→b 1 ⊗ rk a→b 2 )) = ([(ma + p 1 ⊗ r 2 + r 1 ⊗ p 2 ) • (R 1 ⊗ R 2 )] T , [a • (R 1 ⊗ R 2 )] T ) = ([ma(R 1 ⊗ R 2 ) + p 1 R 1 ⊗ r 2 R 2 + r 1 R 1 ⊗ p 2 R 2 ] T , [a • (R 1 ⊗ R 2 )] T ) = ([ma(R 1 ⊗ R 2 ) + r 1 p 1 ⊗ r 2 R 2 + r 1 R 1 ⊗ r 2 p 2 ] T , [a • (R 1 ⊗ R 2 )] T ) = ([ma(R 1 ⊗ R 2 ) + p 1 ⊗ r 1 r 2 R 2 + r 2 r 1 R 1 ⊗ p 2 ] T , [a • (R 1 ⊗ R 2 )] T ) = Encrypt T (pk b T , m, a(R 1 ⊗ R 2 ); r 2 r 1 R 1 , r 1 r 2 R 2 )

A.10 Distributed Decryption

When a third-party performs the decryption, it is important to be able to prove the correct decryption, which consists of zero-knowledge proofs, as described in the Appendix B. But this is even better if the decryption process can be distributed among several servers, under the assumption that only a small fraction of them can be corrupted or under the control of an adversary.

To decrypt a ciphertext in G s with s ∈ {1, 2}, one needs to compute (

[c s,1 ] s • sk s , [c s,2 ] s • sk s ).
In a Shamir's like manner [Sha79], one can perform a t-out-of-n threshold secret sharing by distributing sk s such that sk s = i∈I λ I,i sk s,i with I ⊂ {1, . . . , n} a subset of t users, and for all i ∈ I, λ I,i ∈ Z p and sk s,i is the secret key of the party P i .

For s = T and with just the distribution of sk 1 and sk 2 , it is also possible to perform a distributed decryption, using the relation sk 1 ⊗ sk 2 = (sk 1 ⊗ 1) × (1 ⊗ sk 2 ). One can thus make a two round decryption, first in G 1 and then in G 2 .

Remark 12. Because the operations to decrypt or re-encrypt are the same, one can make distributed re-encryption in the same vein: in our applications, computations will be performed on data encrypted under a controller's key, where the controller is actually a pool of controllers with a distributed decryption key. The latter will be used to re-encrypt the result under the targer end-user's key. However, in this scheme, the secret key must be a projection matrix, which is not easy to generate at random: for this key generation algorithm, a trusted dealer is required, which is not ideal when nobody is trusted. This is the goal of the rest of the paper, to show that we can optimize this generic construction, and distribute everything without any trusted dealer.

B Verifiability

When a ciphertext is randomized or re-encrypted by a third party, one may want to be sure the content is kept unchanged. Verifiability is thus an important property we can efficiently achieve, with classical zero-knowledge proofs of discrete logarithm relations à la Schnorr. Such linear proofs of existence of k scalars that satisfy linear relations generally consist of a commitment c, a challenge e ∈ Z p and the response r ∈ Z k p (details on the example below). The non-interactive variant just contains e and r, and thus k + 1 scalars.

Example 13. Let M ∈ M 2 (Z p ) and ([x] s , [y] s ), ([x ] s , [y ] s ) ∈ G 2
s . We will make the zeroknowledge proof of existence of M such that both [y]

s = [x] s • M and [y ] s = [x ] s • M, where [x] s , [y] s , [x ]
c] s = [x] s • R e[y] s and [c ] s = [x ] s • R e[y ] s , in G 2 s .
To make the proof non-interactive, one can use the Fiat-Shamir heuristic with e generated by a hash function (modeled as a random oracle) on the statement (

[x] s , [y] s ), ([x ] s , [y ] s ) and commitments ([c] s , [c ] s ).
The proof eventually consists of (e, R).

From this proof, one can compute the candidates for ([c] s , [c ] s ), and check whether the hash value gives back e.

Before entering into the details of the relations to be proven, for each function of our encryption scheme, we rewrite the Keygen s and REKeygen s algorithms to prepare the verifiability of Decrypt s and Re-encrypt s . These new Keygen s and REKeygen s algorithms consist of the original Keygen s and REKeygen s but with more elements in the output: they both output a public version of the produced secret key plus a zero-knowledge proof of the correctness of the keys. This significantly simplifies the relations to be proven afterwards for Decrypt s and Re-encrypt s . At the end of this section, we prove that adding those elements do not compromise the security of the encryption scheme. The proof π s guarantees that all the keys are well-formed: vsk s is the exponentiation of a 2 × 2matrix sk s , for which the discrete logarithm of pk s is in the kernel. Hence, sk s is not full rank, and vsk s = [0] s proves that sk s is of dimension 1: a projection. As a consequence, π s consists of 5 scalars of Z p , using the above non-interactive zero-knowledge technique à la Schnorr.

From (vsk 1 , vsk 2 ), we consider vsk T = vsk 1 •vsk 2 . It satisfies vsk T = [P 1 ⊗P 2 ] T if (vsk 1 , vsk 2 ) = ([P 1 ] 1 , [P 2 ] 2 ). needs 6 scalars of Z p as a proof à la Schnorr.

Similarly as for vsk s , from (vrk 1 , vrk 2 ), we consider vrk

T = vrk 1 • vrk 2 . So that, vrk T = [R 1 ⊗ R 2 ] T if (vrk 1 , vrk 2 ) = ([R 1 ] 1 , [R 2 ] 2 ).
Now, we explain for each function, the relations to be proven:

[c T,1 ] T = α • ([c T,1 ] T [p 1 ] 1 • [r 2 ] 2 [r 1 ] 1 • [p 2 ] 2 ) ∧ [c T,2 ] T = α • [c T,2 ] T
These relations are equivalent to the linear relations:

for s ∈ {1, 2}, it exists α, r ∈ Z p such that:

[c s,1 ] s = α • [c s,1 ] s r • [p s ] s ∧ [c s,2 ] s = α • [c s,2 ] s
for s = T , it exists α ∈ Z p , r 1 , r 2 ∈ Z 2 p such that: ] 2 ), it exists sk T = (P 1 , P 2 ) ∈ M 2 (Z p ) 2 such that:

[c T,1 ] T = α • [c T,1 ] T [p 1 ] T • r 2 r 1 • [p 2 ] T ∧ [c T,2 ] T = α • [c T,
[p 1 ] 1 • P 1 = [0] 1 ∧ [p 2 ] 2 • P 2 = [0] 2 ∧ P 1 = 0 ∧ P 2 = 0 ∧ [c T,1 ] T • (P 1 ⊗ P 2 ) = m • [c T,2 ] T • (P 1 ⊗ P 2 )
Instead of proving these relations, the prover will use vsk s for s ∈ {1, 2, T } produced by Keygen s for verifiability and will make the proof of the relations:

for s ∈ {1, 2}, it exists sk s = P s ∈ M 2 (Z p ) such that:

([c T,1 ] T , [c T,2 ] T ) = ([c T,1 ] T • (R 1 ⊗ R 2 ), [c T,2 ] T • (R 1 ⊗ R 2 )) ∧ pk b T = (pk b 1 , pk b 2 ) = (pk a 1 • R 1 , pk a 2 • R 2 )
Instead of proving these relations, the prover will use vrk s for s ∈ {1, 2, T } produced by REKeygen s for verifiability and will make the proof of the relations below:

for s ∈ {1, 2}, it knows rk a→b s = R s ∈ M 2 (Z p ) such that:

([c s,1 ] s , [c s,2 ] s ) = ([c s,1 ] s • R s , [c s,2 ] s • R s ) ∧ vrk a→b s = [1] s • R s -for s = T , it knows rk a→b T = (R 1 ⊗ R 2 ) ∈ M 4 (Z p ) such that: ([c T,1 ] T , [c T,2 ] T ) = ([c T,1 ] T • (R 1 ⊗ R 2 ), [c T,2 ] T • (R 1 ⊗ R 2 )) ∧ vrk a→b T = [1] T • (R 1 ⊗ R 2 )
This proof needs 5 scalars of Z p for s ∈ {1, 2} and 17 scalars of Z p for s = T .

  REKeygen s (sk a s , sk b s ): For s = 1, 2, from two different secret keys sk a s = P s and sk b s = P s associated respectively to the two public keys pk a s and pk b s , compute B s , B s ∈ GL 2 (Z p ) such that P s = B -1 s UB s and P s = B s -1 UB s and output rk a→b s = R s = B -1 s B s the secret re-encryption key. From the re-encryption keys rk a→b 1 = R 1 ← REKeygen 1 (sk a 1 , sk b 1 ) and rk a→b 2 = R 2 ← REKeygen 2 (sk a 2 , sk b 2 ), we will consider rk a→b T = (rk a→b 1 , rk a→b 2

  s and [y ] s are public, but the prover knows M. This is the classical zero-knowledge proof of equality of discrete logarithms with matrices.The prover chooses M $ ← M 2 (Z p ) and sends the commitments[c] s = [x] s • M and [c ] s = [x ] s • M tothe verifier that answers a challenge e ∈ Z p . The prover constructs its response R = M -eM in M 2 (Z p ) and the verifier checks whether both [

  Keygen s for Verifiability. While the secret key is the projection P s , the verification key vsk s consists of [P s ] s :Keygen s (param): For s ∈ {1, 2}. Choose B s $ ← GL 2 (Z p ). Let P s = B -1s U 2 B s and p s ∈ ker(P s )\ {0}. Output the public key pk s = [p s ] s , the private key sk s = P s and vsk s = [P s ] s a verifiable public version of the secret key with the proof π s :{∃sk s ∈ M 2 (Z p ), vsk s = [0] s ∧ vsk s = [1] s • sk s ∧ pk s • sk s = [0] s }.

  The function Randomize s . It takes a ciphertext C s = ([c s,1 ] s , [c s,2 ] s ) encrypted with a public key pk s and produces a ciphertext C s = ([c s,1 ] s , [c s,2 ] s ) such that:for s ∈ {1, 2} and pk s = [p s ] s , it exists α, r ∈ Z p such that:[c s,1 ] s = α • ([c s,1 ] s r • [p s ] s ) ∧ [c s,2 ] s = α • [c s,2 ] s for s = T and pk T = ([p 1 ] 1 , [p 2 ] 2 ), it exists α ∈ Z p , r 1 , r 2 ∈ Z 2p such that:

  2 ] T These proofs consist of 3 scalars of Z p for s ∈ {1, 2}, and 6 scalars of Z p for s = T . The functions Add and Multiply. They are public and deterministic thus everyone can check the operations. The function Decrypt s . It takes a ciphertext C s = ([c s,1 ] s , [c s,2 ] s ) encrypted with a public key pk s and produces its decryption m such that:for s ∈ {1, 2} and pk s = [p s ] s , it exists sk s = P s ∈ M 2 (Z p ) such that:[p s ] s • P s = [0] s ∧ P s = 0 ∧ [c s,1 ] s • P s = m • [c s,2 ] s • P s for s = T and pk T = ([p 1 ] 1 , [p 2

[

  vsk s ] s = [1] s • P s ∧ ([c s,1 ] s m • [c s,2 ] s ) • P s = [0] s for s = T , it exists sk T = (P 1 , P 2 ) ∈ M 2 (Z p ) 2 such that: [vsk T ] T = [1] T • (P 1 ⊗ P 2 ) ∧ ([c T,1 ] T m • [c T,2 ] T ) • (P 1 ⊗ P 2 ) = [0] TThe linear proofs consist of 5 scalars of Z p for s ∈ {1, 2} and 17 scalars of Z p for s = T .The function Re-encrypts . It takes a ciphertext C s = ([c s,1 ] s , [c s,2 ] s ) encrypted with a public key pk a s and produces a ciphertext C s = ([c s,1 ] s , [c s,2] s ) encrypted with a public key pk b s such that:for s ∈ {1, 2}, it knows rk a→b s = R s ∈ GL 2 (Z p ) such that:([c s,1 ] s , [c s,2 ] s ) = ([c s,1 ] s • R s , [c s,2 ] s • R s ) ∧ pk b s = pk a s • R s for s = T , pk a T = (pk a 1 , pk a 2 ), pk b T = (pk b 1 , pk b 2 ) and vrk T = ([R 1 ] 1 • [R 2 ]2 ), it knows rk a→b T = (R 1 , R 2 ) ∈ GL 2 (Z p ) 2 such that:

Acknowledgments

This work was supported in part by the European Community's Seventh Framework Programme (FP7/2007-2013 Grant Agreement no. 339563 -CryptoCloud) and the French ANR ALAMBIC Project (ANR16-CE39-0006).

A.7 Security Properties

Theorem 10. For s ∈ {1, 2}, E s is IND-CPA under the DDH assumption in G s : for any adversary A running within time t, Adv ind-cpa Es (A) ≤ 2 × Adv ddh Gs (t).

Proof. We denote by Adv ind-cpa Es (A) the advantage of A against E s . We assume the running time of A is bounded by t.

Game G 0 : In this first game, the simulator plays the role of the challenger in the experiment Exp ind-cpa-0 Es (A), where b = 0: S(λ):

Game G 1 : Now the simulator takes as input a Diffie-Hellman tuple ([p]

Thanks to the random mask [r] s , this game is perfectly indistinguishable from the previous one:

The simulator now receives a Diffie-Hellman tuple ([p] s , [r] s ), with r = r • p for some scalar r:

. Game G 5 : In this game, the simulator can perfectly emulate the challenger in the experiment Exp ind-cpa-1 Es (A), where b = 1: This game is perfectly indistinguishable from the previous one:

One can note, that in this last game, Pr G 5

which concludes the proof.

More precisely, for any adversary A running within time t,

, where t m is the time for one multiplication and t e the time for one encryption.

Proof. The semantic security for ciphertexts in G T comes from the fact that:

Indeed, with this relation, each ciphertext in G 1 can be transformed into a ciphertext in G T (idem with a ciphertext in G 2 ). Let A be an adversary against IND-CPA of E T , in G T .

Proof. The modified Keygen s also outputs vsk s and a zero-knowledge proof π s . This implies that some games need to be added before the first game in the security proof of E s for Theorem 10: Game G 0 : In the first game, the simulator plays the role of the challenger in the experiment Exp ind-cpa-0 Es (A), where b = 0: S(λ):

Game G 1 : The first modification is to replace π s by its simulation, possible thanks to the zero-knowledge property. This game is statistically indistinguishable from the previous one, under the statistical zero-knowledge property of the proof à la Schnorr in the Random Oracle Model. Game G 2 : Now the simulator takes as input a Diffie-Hellman tuple (

for some scalar r, and emulates Keygen s by defining vsk s = ([a] s , [b] s ). Thanks to the Diffie-Hellman tuple this corresponds to the matrix of a projection, and thus this game is perfectly indistinguishable from the previous one:

Adv ddh Gs (t). In this game, there is no information in vsk s anymore and the zero-knowledge proofs are simulated. In the original proof, sk s is never used, thus we can plug the games from the original proof here. To finish the proof we need to unravel the games of vsk s and π s in order to have: Game G 4 : S(λ):

- Corollary 15. E T with verifiability is still secure.

Proof. Similarly to the previous proof, the zero-knowledge proofs are replaced by their simulations. Then, vsk 1 and vsk 2 are replaced by random matrices in M 2 (Z p ). Thus, vsk T is also a random matrix.