Through interactive cryptographic protocols, secure multi-party computation (MPC) allows several parties to compute the image of a pre-agreed function of their private inputs. At the end of the interaction, anything that a party (or a sufficiently small coalition of parties) has learned from the protocol could have been deduced from its public and secret inputs and outputs. In other words, the adversary’s view can be efficiently forged by a simulator that has only access to the data publicly known by the adversary. This important area of research emerged in the 80s with the works of Yao [46] and Goldreich et al. [22]. Formal security notions can be found in [4,8,34]. Initially considered as a theoretical subject due to overly inefficient protocols, MPC has nowadays reached a reasonable complexity and has became relevant for practical purposes [6] especially in the 2-party case [31,33,40]. Several techniques may be used to design secure multi-party computation. Some recently proposed solutions use or combine tools from oblivious transfer [3,30], secret sharing with pre-processing [16,37], garbled circuits [31], homomorphic encryption [11,15], and somewhat or fully homomorphic encryption [2,5].

In [10], Couteau et al. formalized an innovative technique to securely compute functions between two players, thanks to interactive cryptographic protocols calledencryption switching protocols (ESP). This mechanism permits secure 2-party computations against semi-honest adversaries (honest-but-curious) as well as malicious adversaries, i.e. opponents which might not follow the specifications of the protocol. Couteau et al.’s proposal relies on a pair of encryption schemes\((\varPi _{+},\varPi _{\times })\) which are respectively additively and multiplicatively homomorphic and which share a common message space. Furthermore, there exists switching algorithms to securely convert ciphertexts between\(\varPi _{+}\) and\(\varPi _{\times }\). More precisely, there exists a protocol\(\mathsf {Switch}_{+\rightarrow \times }\) which takes as input an encryption\(C^+_m\) of a messagem under\(\varPi _{+}\), and returns a ciphertext\(C^\times _m\) of the same messagem under\(\varPi _{\times }\). Symmetrically, there exists a second protocol\(\mathsf {Switch}_{\times \rightarrow +}\) which computes a ciphertext form under\(\varPi _{+}\) when given a ciphertext form under\(\varPi _{\times }\). The advantage of this construction is that it benefits from the intrinsic efficiency of multiplicatively homomorphic encryption like Elgamal [18] or additively homomorphic encryption like Paillier [38]. In [10], Couteau et al. present a natural construction for secure 2-party computation from any ESP.

Applications. Two-party computation is the most important application of an ESP. In [11], an MPC protocol is built from only an additively homomorphic encryption scheme which is a natural alternative to an ESP. The round complexity of their protocol is in\(\mathcal {O}(d)\), whered is the depth of the circuit\(\mathcal {C}\) to be evaluated, and if we suppose that the multiplicative gates can be evaluated in parallel at each level. With an ESP, gathering the additive and multiplicative gates separately would imply a dramatic improvement. Fortunately, the result by Valiant et al. from [45, Theorem 3], states that for any circuit\(\mathcal {C}\) of sizes and degreed computing a polynomialf, there is another circuit\(\mathcal {C}'\) of size\(\mathcal {O}(s^3)\) and depth\(\mathcal {O}(\log (s)\log (d))\) which computes the same polynomialf. Moreover, Allender et al. showed that the circuit\(\mathcal {C}'\) is by construction layered (see [1]), in the sense that it is composed of layers whose gates are all the same and alternatively\(+\) and\(\times \). Roughly speaking,\(\mathcal {C}'\) is of the form\((\sum \prod )^{\mathcal {O}(\log (s)\log (d))}\) where\(\sum \) has only additive gates and\(\prod \) has only multiplicative gates. In other words, the polynomialf can be written as a composition of\({\mathcal {O}(\log (s)\log (d))}\) polynomials written in a sparse representation. The ESP allows to treat each\(\sum \) and\(\prod \) independently, so that the number of switches and therefore the number of rounds is essentially\(\mathcal {O}(\log (s)\log (d))\), instead of\(\mathcal {O}(d)\) for [11]. Any enhancement of an ESP will naturally improve any protocol which requires to evaluate on encrypted data a polynomial given in the form of a sum of monomials. Especially it is well-suited to oblivious evaluation of multivariate polynomials [27,36,42] or private disjointness testing [47].

Related Works. The idea of switching between ciphertexts for different homomorphic encryption schemes was first proposed by Gavin and Minier in [20] in the context of oblivious evaluation of multivariate polynomials. They proposed to combine a variant of Elgamal over\((\mathbf {Z}/N\mathbf {Z})^*\) (whereN is an RSA modulus) with a Goldwasser-Micali encryption protocol [23]. Unfortunately, as noticed by Couteau et al. [10], their design contains a serious flaw which renders their scheme insecure (the public key contains a square root of unity with Jacobi symbol\(-1\), which exposes the factorization ofN). Another attempt was proposed in [44] with a compiler designed to embed homomorphic computation into C programs to operate on encrypted data. The security of this construction relies on a very strong assumption since switching between the encryption schemes is done using a secure device which decrypts and re-encrypts using the secret key. In [29], Lim et al. proposed a primitive calledswitchable homomorphic encryption implemented using Paillier and Elgamal, in the context of computation on encrypted data. Again, this proposal uses an insecure version of Elgamal, which does not satisfy the indistinguishability under a chosen plaintext attack. It is indeed very difficult to design two compatible encryption schemes from unrelated protocols like Paillier and Elgamal. Couteau et al. managed to tune Elgamal so that it can switch with Paillier, but their construction remains fairly expensive. In particular, they constructed a variant of Elgamal over\((\mathbf {Z}/n\mathbf {Z})^*\), wheren is an RSA modulus, which is the same as the Paillier modulus. As Elgamal is secure only in the subgroup\(\mathbf {J}_n\) of\((\mathbf {Z}/n\mathbf {Z})^*\) of elements of Jacobi symbol\(+1\), they need a careful encoding of the group\((\mathbf {Z}/n\mathbf {Z})^*\). The security relies on the DDH assumption in\(\mathbf {J}_n\) and the quadratic residuosity assumption in\((\mathbf {Z}/n\mathbf {Z})^*\). Because their Elgamal variant does not support a simple 2-party decryption (a Paillier layer has to be added to Elgamal in order to simulate a threshold decryption), the switching protocols are intricate and specific to their construction.

Our Contributions and Overview of Our Results. In this paper, we first propose a generic ESP inspired by Couteau et al.’s solid basis. Our construction relies on the existence of an additively homomorphic encryption\(\varPi _{+}\) and a multiplicatively homomorphic encryption\(\varPi _{\times }\) which support a 1-round threshold decryption and achieve classical security properties (IND-CPA and zero-knowledge of the 2-party decryption). Because the message spaces must be compatible, we suppose that\(\varPi _{+}\) works over a ring\(\mathcal {R}\) and\(\varPi _{\times }\) over a monoid\(\mathcal {M}\) with\(\mathcal {R}\cap \mathcal {M}= \mathcal {R}^*\) where\(\mathcal {R}^*\) is the set of invertible elements of\(\mathcal {R}\). A major issue when designing an ESP is to embed the zero message^Footnote1 into the message space for\(\varPi _{\times }\), while preserving the homomorphic and security properties. In Sect. 4.2, we propose a generic technique to do so, inspired by the approach employed in [10]. Contrary to their construction, our switching protocols over\(\mathcal {R}^*\) (i.e. without the zero-message) are symmetrical, i.e. both\(\mathsf {Switch}_{+\rightarrow \times }\) and\(\mathsf {Switch}_{\times \rightarrow +}\) follow the same elementary description given in Fig. 3. This is possible for two reasons: first because we suppose that both\(\varPi _{+}\) and\(\varPi _{+}\) admit a single round 2-party decryption, and second because they both possess a\(\mathsf {ScalMul}\) algorithm which takes as input a ciphertext ofm and a plaintext\(\alpha \) and outputs a ciphertext of\(\alpha \times m\) (which is why we consider a ring as the message space for\(\varPi _{+}\) instead of an additive group).

Besides, they are very efficient: as detailed in Sect. 5.3, they only require 2 rounds, whereas Couteau et al.’s\(\mathsf {Switch}_{\times \rightarrow +}\) needs 6. Our full switching protocols work over\(\mathcal {R}^* \cup \{0\}\). They are built on top of the switching protocols over\(\mathcal {R}^*\) (i.e. without 0), plus some additional tools like 2-party re-encryption, encrypted zero test, and a 2-party protocol to homomorphically compute a product under\(\varPi _{+}\) (see Fig. 1). Our security proofs are simpler than Couteau et al.’s. In terms of round complexity, the savings are substantial: our full ESP protocols require 7 and 4 rounds respectively, whereas Couteau et al’s ESP need 7 and 11.

In a second part, we propose an efficient instantiation of our generic protocol over the field\(\mathbf {Z}/p\mathbf {Z}\). Working over\(\mathbf {Z}/p\mathbf {Z}\) has several advantages compared to\(\mathbf {Z}/n\mathbf {Z}\) (for an RSA modulusn): it means true message space equality, instead of computational equality. It also means faster arithmetic by carefully choosing the primep. Our instantiation combines a variant of Elgamal together with the Castagnos-Laguillaumie additively homomorphic encryption from [9]. Because Elgamal is only secure in the subgroup of squares modulop, our variant over\(\mathbf {Z}/p\mathbf {Z}^*\), denoted\(\mathsf {Eg}^*\), encodes the messages into squares and adds the encryption of a witness bit (i.e. the Legendre Symbol) under Goldwasser-Micali [23] for its homomorphic properties modulo 2. For\(\varPi _{+}\), we use a variant of the Castagnos-Laguillaumie encryption scheme (\(\mathsf {CL}\)) described in [9, Sect. 4]. We work over (subgroups of) the class group of an order of a quadratic field of discriminant\(\varDelta _p = -p^3\). Computations are done in this class group. The elements are represented by their unique reduced representative, i.e. by two integers of size\(\sqrt{|\varDelta _p|}\). Thus, an element of the class group requires\(3\log {p}\) bits. Under slightly different security assumptions, it is possible to further reduce the size of the elements and to achieve a better bit complexity. We discuss these implementation options in Sect. 5.3 and compare their costs with the ESP from Couteau et al. [10]. Our ESP protocol reduces the round complexity by a factor of almost 3 in the\(\times \rightarrow +\) direction, while remaining constant in the other direction. Using the variant of\(\mathsf {CL}\) optimized for size, the bit complexity is also significantly reduced in the\(\times \rightarrow +\), while remaining in the same order of magnitude in the other.

We also propose improvements on\(\mathsf {CL}\) that can be on independent interest. That system makes exponentiations in a group whose order is unknown but where a bound is known. We show that using discrete Gaussian distribution instead of uniform distribution improves the overall computational efficiency of the scheme. Moreover in order to use our generic construction, we devise a 2-party decryption for\(\mathsf {CL}\).

Eventually we discuss in Sect. 6 how to adapt our generic construction and our instantiation against malicious adversaries.

In this section, we recall some classical definitions and operations that will be useful in the rest of the paper.

2.1Homomorphic Encryption Schemes

In Sect. 3, we will give a definition ofEncryption Switching Protocols (ESP), previously proposed in [10]. An ESP allows to switch a ciphertext under an encryption protocol\(\varPi _1\) into a ciphertext under another encryption protocol\(\varPi _2\), and vice versa. ESP require the protocols\(\varPi _1\) and\(\varPi _2\) to be (partially) homomorphic. In this paper, we consider ESP between an additively homomorphic encryption\(\varPi _{+}\) and a multiplicatively homomorphic encryption\(\varPi _{\times }\).

In Definitions 1 and 2 below, we define\(\varPi _{+}\) and\(\varPi _{\times }\) formally in a generic context. An additive homomorphic encryption is most commonly defined over a group. In our setting,\(\varPi _{+}\) is defined over a ring\(\mathcal {R}\) to guarantee that for\(m, m' \in \mathcal {R}\), the product\(m \times m'\) is well defined. For genericity\(\varPi _{\times }\) is defined over an algebraic structure with a single associative binary operation (denoted\(\times \)) and an identity element; i.e. a monoid. By doing so, our definition encapsulates encryption schemes over\((\mathbf {Z}/pq\mathbf {Z})^* \cup \{0\}\) (withp, q primes) such as [10], as well as our instantiation over\(\mathbf {Z}/p\mathbf {Z}\) presented in Sect. 5.

Definition 1

(Additively homomorphic encryption). Let\((\mathcal {R}\),\(+\),\(\times \),\(1_{\mathcal {R}}\),\(0_{\mathcal {R}})\) be a ring. Anadditively homomorphic encryption scheme over the message space\(\mathcal {R}\) is a tuple\( \varPi _{+}= (\mathsf {Setup},\mathsf {KeyGen},\mathsf {Encrypt},\mathsf {Decrypt},\mathsf {Hom}_+, \mathsf {ScalMul}) \) such that:

\(\mathsf {Setup}\) is a PPT algorithm which takes as input a security parameter\(1^\lambda \) and outputs public parameters\(\mathsf{params}\) (these public parameters will be omitted in the algorithms’ inputs).

\(\mathsf {KeyGen}\) is a PPT algorithm taking public parameters as inputs and outputting a pair of public and secret key (pk, sk).

\(\mathsf {Encrypt}\) is a PPT algorithm which takes as input some public parameters, a public keypk and a message\(m \in \mathcal {R}\), and outputs an encryptionc.

\(\mathsf {Decrypt}\) is a PPT algorithm which takes as input public parameters, a public keypk (omitted in\(\mathsf {Decrypt}\)’s input), a secret keysk and a ciphertextc, and outputs a message\(m \in \mathcal {R}\).

\(\mathsf {Hom}_+\) is a PPT algorithm which takes as inputs some public parameters, a public keypk and two ciphertextsc and\(c'\) of\(m \in \mathcal {R}\) and\(m' \in \mathcal {R}\) respectively, and outputs a ciphertext\(c''\) such that\(\varPi _{+}{.}\mathsf {Decrypt}(sk,c'') = m + m' \in \mathcal {R}\).

\(\mathsf {ScalMul}\) is a PPT algorithm which takes as inputs some public parameters, a public keypk, a ciphertextc of\(m \in \mathcal {R}\) and a plaintext\(\alpha \in \mathcal {R}\), and outputs a ciphertext\(c'\) such that\(\varPi _{+}{.}\mathsf {Decrypt}(sk,c') = \alpha \times m \in \mathcal {R}\).

Remark 1

A generic algorithm for computing\(\varPi _{+}{.}\mathsf {ScalMul}(pk, c, \alpha )\) is given by\(\mathsf {2Mul}_{+}(c, \varPi _{+}{.}\mathsf {Encrypt}(\alpha ))\), where\(\mathsf {2Mul}_{+}\) is an interactive PPT algorithm which computes homomorphically the product of two ciphertexts for\(\varPi _{+}\).\(\mathsf {2Mul}_{+}\) is defined more formally in Sect. 2.3. For our instantiation we provide a non-interactive, more efficient version over\(\mathbf {Z}/p\mathbf {Z}\) (see Sect. 5).

Definition 2

(Multiplicatively homomorphic encryption). Let\((\mathcal {M}\),\(\times \),\(1_{\mathcal {M}})\) be a monoid. Amultiplicatively homomorphic encryption scheme over the message space\(\mathcal {M}\) is\(\varPi _{\times }= (\mathsf {Setup},\mathsf {KeyGen},\mathsf {Encrypt}, \mathsf {Decrypt},\mathsf {Hom}_\times , \mathsf {ScalMul})\) such that:

\(\mathsf {Setup}\),\(\mathsf {KeyGen}\),\(\mathsf {Encrypt}\) and\(\mathsf {Decrypt}\) as in Definition 1 except that\(\mathsf {Encrypt}\) and\(\mathsf {Decrypt}\) receives the input messages from\(\mathcal {M}\) instead of\(\mathcal {R}\).

\(\mathsf {Hom}_\times \) is a PPT algorithm which takes as input some public parameters, a public keypk and two ciphertextsc and\(c'\) of\(m \in \mathcal {M}\) and\(m' \in \mathcal {M}\) respectively, and outputs a ciphertext\(c''\) such that\(\varPi _{\times }{.}\mathsf {Decrypt}(sk,c'') = m \times m' \in \mathcal {M}\).

\(\mathsf {ScalMul}\) is a PPT algorithm which takes as inputs some public parameters, a public keypk, a ciphertextc of\(m \in \mathcal {M}\) and a plaintext\(\alpha \in \mathcal {M}\), and outputs a ciphertext\(c'\) such that\(\varPi _{\times }{.}\mathsf {Decrypt}(sk,c') = \alpha \times m \in \mathcal {M}\).

Remark 2

A generic algorithm for computing\(\varPi _{\times }{.}\mathsf {ScalMul}(pk, c, \alpha )\) is given by\(\varPi _{\times }{.}\mathsf {Hom}_\times (pk, c, c')\), where\(c' = \varPi _{\times }{.}\mathsf {Encrypt}(pk, \alpha )\). In Sect. 5, we provide a more efficient version over\((\mathbf {Z}/p\mathbf {Z})^*\).

The above encryption schemes must be correct in the usual sense. Moreover, we consider as a security requirement the indistinguishability under a chosen plaintext attack (IND-CPA). We refer the reader to e.g., [25] for the standard definition of IND-CPA.

2.2One Round 2-Party Decryption

A crucial feature of the encryption protocols which are used in the ESP is the fact that they support a 2-party decryption (threshold cryptosystems were introduced in [17]). These encryption schemes are equipped with aShare procedure that is run by a trusted dealer, which works as follows: it takes as input a pair of keys (sk, pk) obtained from the\(\mathsf {KeyGen}\) algorithm and produces two shares\(sk_A\) and\(sk_B\) of the secret keysk. It outputs\((sk_A,sk_B)\) and an updated public part still denotedpk. Its decryption procedure is an interactive protocol denoted\(2\mathsf {Dec}\) which takes as inputs the public parameters, a ciphertextc, and the secret key of each participant\(sk_A\) and\(sk_B\) and outputs a plaintextm which would have been obtained as\(\mathsf {Decrypt}(sk, c)\).

Contrary to the classical definition of threshold decryption, we suppose that the protocol is in asingle round. The protocol\(2\mathsf {Dec}(pk, c; sk_A; sk_B)\) is supposed as follows: Alice starts the protocol and sends her information in one flow to Bob which ends the computation and gets the plaintext. This is because in our context, we do not decrypt plaintexts but plaintexts which are masked by a random element. For example, protocols whose decryption only performs exponentiations with secret exponents gives one round 2-party decryption by sharing the exponentiations. This is the case for many cryptosystems.

The semantic security is adapted from the standard IND-CPA notion by giving the adversary one of the two secret keys, as well as a share decryption oracle which simulate the party with the other secret key. A formal definition can be found for instance in [11,41].

We need as an additional security requirement the notion of zero-knowledge defined in Appendix A, which means that no information on the secret keys are leaked during an interaction with a curious adversary. Cryptosystems like Elgamal [17] or Paillier [19] satisfy all these properties. We will propose a variant of Elgamal and a variant of Castagnos-Laguillaumie [9] that satisfy also these properties in Sect. 5.

2.3Homomorphically Computing a Product with\(\varPi _+\)

A core routine of our protocol is the computation of a\(\varPi _+\)-encryption of a productXY given\(\varPi _+\)-encryptions ofX andY (this is why we assume that\(\varPi _+\) has a ring\(\mathcal {R}\) as message space). We describe in Fig. 1 a protocol which is implicitly used in [10]. It is a simplified variant of a protocol proposed by Cramer et al. from [11]: the main difference comes from the fact that the result of this 2-party computation is obtained only by one of the user, who can forward the result to the other. This leads to the use of a single randomness on Alice’s side, instead of one on each side. We will denote by\(\mathsf {2Mul}_{+}(pk,C_X^+,C_Y^+;sk_A;sk_B)\) a call to this protocol. Again, this protocol will be a 2-round protocol since the shared decryption is single round, and the first ciphertext can be sent along with the shared decryption. This protocol has to be zero-knowledge in the sense similar to those of Definitions 5 and7 (we do not write down this definition which can be readily adapted).

\(\mathsf {2Mul}_{+}\): 2-party protocol to compute\(C_{XY}^+\) from\(C_{X}^+\) and\(C_{Y}^+\)

Full size image

Theorem 1

Let\(\varPi _+\) be an additively homomorphic encryption scheme with a zero-knowledge one round 2-party decryption. Then, the protocol described in Fig. 1 is correct and zero-knowledge.

Proof

The correctness follows from the correctness of the encryption scheme and its homomorphic properties. Let us prove first that it is zero-knowledge for Alice. We describe a simulator\(\mathsf{Sim}\) whose behavior is indistinguishable from Alice’s behavior in front of an adversarial Bob. The simulator receives as input the public key\(pk_+\) and will set\(\mathsf{Sim}_\mathsf{Share}\) as follows: it calls out\(\mathsf{Sim}^{2d}_\mathsf{Share}\) procedure of the zero-knowledge property of 2-party decryption for\(\varPi _{+}\) with\(pk_+\) as input. It obtains a simulated share\(sk_B=x_B^+\) and feeds the adversary with it. When\(\mathsf{Sim}\) is requested for the 2-party computation of\(C^+_{XY}\) from\(C_X^+\) and\(C_Y^+\), it receives a pair of\(((C_X^+,C_Y^+),\bar{C})\) where\(\bar{C}\) is a ciphertext ofXY, it does the following to simulate\(C^+_{-rX},C^+_{r+Y}\) and\(C_A\): First, It picksR at random in the plaintext space and sets\(C^+_{r+Y}=\mathsf {Encrypt}(pk,R)\). Then it uses the simulator for the zero-knowledge for Alice of the 2-party decryption\(\mathsf{Share}^{2d}_{A}(C^+_{r+Y},R,x_B^+)\) so that Bob decryptsR (which is equivalent to\({\mathsf {Decrypt}}(sk,C^+_{r+Y})\)). Eventually, it sets\(C_{-rX}=\mathsf {Hom}_+(\bar{C},\mathsf {ScalMul}(C_X^+,-R))\). This ciphertext encrypts\(XY-RX\) so that Bob’s final\(\mathsf {Hom}_+\) evaluation will cancel out theRX part and lead to\(\bar{C}\).

The simulated view is the same as a genuine one with\(R=r+Y\), which means that they are indistinguishable, and the protocol is zero-knowledge for Alice. The protocol is obviously zero-knowledge for Bob: Bob’s contribution is simulated by just sending\(\bar{C}\).    \(\square \)

2.42-Party Re-encryption

The final tool we need to build our encryption switching protocol is an interactive 2-party protocol to re-encrypt a ciphertext from an encryption scheme\(\varPi _+\) intended topk into a ciphertext of the same encryption scheme of the same message, but intended to another key\(pk'\). This protocol is depicted in Fig. 2. Note that the initial ciphertext to be transformed is not known to Bob. This protocol readily extends to the multiplicative case, which is useless for our purpose. With a proof similar to the proof of Theorem 1, we showed that

Theorem 2

Let\(\varPi _+\) be an additively homomorphic encryption scheme with a zero-knowledge one round 2-party decryption then the protocol described in Fig. 2 is correct and zero-knowledge.

2-party\(\mathsf{ReEnc}_{+}\)

Full size image

The global scenario is established as follows: two semantically secure threshold homomorphic encryption schemes, one additive, and the other multiplicative, are at the disposal of two players. A public key is provided for each protocols, and the matching secret key is shared among the players by a trusted dealer. Ideally, these two encryption schemes should have the same plaintext space, which is assumed to be a ring or a field. An encryption switching protocols makes it possible to interactively transform a ciphertext from a source encryption scheme into a ciphertext for the other encryption scheme (the target one) andvice versa. The formal definitions are given in the following paragraphs.

Definition 3

(Twin ciphertexts). Let\(\varPi _+\) and\(\varPi _\times \) be two different encryption schemes with plaintext and ciphertext spaces respectively\(\mathcal {M}_+,\mathcal {C}_+\) and\(\mathcal {M}_\times ,\mathcal {C}_\times \). If\(C^+_m\in \mathcal {C}_+\) and\(C^\times _m \in \mathcal {C}_\times \) are two encryptions of the same message\(m \in \mathcal {M}_+\cap \mathcal {M}_\times \), they are said to betwin ciphertexts.

We will say that two ciphertexts from the same encryption scheme which decrypt to the same plaintext areequivalent.

Definition 4

(Encryption Switching Protocols). An encryption switching protocol (ESP) between\(\varPi _+\) and\(\varPi _\times \), denoted\(\varPi _+ \rightleftharpoons \varPi _\times \), is a protocol involving three parties: a trusted dealer\(\mathcal {D}\) and two usersA andB. It uses commonSetup andKeyGen algorithms to set the message space between\(\varPi _+\) and\(\varPi _\times \) and keys. It is a pair of interactive protocols\((\mathsf{Share},\mathsf{Switch})\) defined as follows:

• \(\mathsf{Share}((pk_+,sk_+),(pk_\times ,sk_\times )) \rightarrow (pk,sk_A,sk_B)\): It is a protocol (run by\(\mathcal {D}\)) which takes as input two pairs of keys\((pk_+,sk_+)\) and\((pk_\times ,sk_\times )\) produced from\(\varPi _+{.}\mathsf {KeyGen}\),\(\varPi _\times {.}\mathsf {KeyGen}\) andSetup. It outputs the shares\(sk_A\) (sent toA) and\(sk_B\) (sent toB) of\((sk_+,sk_\times )\) and updates the public keypk.

• \(\mathsf{Switch}_{\mathsf{way}}((pk,sk_A,c),(pk,sk_B,C)) \rightarrow C' \text { or } \perp \): It is an interactive protocol in the direction\(\mathsf{way} \in \{+ \rightarrow \times , \times \rightarrow +\}\) which takes as common input the public key and a ciphertextC under the source encryption scheme and as secret input the secret shares\(sk_A\) and\(sk_B\). The output is a twin ciphertext\(C'\) ofC under the target encryption scheme or\(\perp \) if the execution encountered problems.

Correctness. An encryption switching protocols\(\varPi _+\rightleftharpoons \varPi _\times \) iscorrect if for any\(\lambda \in \mathbf {N}\),\((\mathsf{params}_+,\mathsf{params}_\times ) \leftarrow \mathsf{Setup}(1^\lambda )\), for any pair of keys\((pk_+,sk_+)\leftarrow \varPi _+{.}\mathsf {KeyGen}(1^\lambda ,\mathsf{params}_+)\) and\((pk_\times ,sk_\times )\leftarrow \varPi _\times {.}\mathsf {KeyGen}(1^\lambda ,\mathsf{params}_\times )\), for any shares\((pk,sk_A,sk_B) \leftarrow \mathsf{Share}((pk_+,sk_+),(pk_\times ,sk_\times ))\), for any twin ciphertext pair\((C^+_m,C^\times _m)\) of a message\(m \in \mathcal {M}_+\cap \mathcal {M}_\times \),

Zero-Knowledge. An ESP has to satisfy a notion of zero-knowledge similar to the notion of zero-knowledge for threshold decryption (see Definition 7). This property means that an adversary will not learn any other information on the secret share of a participant that he can learn from his own share, the input, and the output of the protocol.

Definition 5

An encryption switching protocols\(\varPi _+ \rightleftharpoons \varPi _\times \) iszero-knowledge for A if there exists an efficient simulator\(\mathsf{Sim} = (\mathsf{Sim}_\mathsf{Share},\mathsf{Sim}_A)\) which simulates the sharing phase and the playerA.

The subroutine\(\mathsf{Sim}_\mathsf{Share}\) takes as input a public key\((pk_+,pk_\times )\) and outputs\((pk',sk'_B)\) that simulates the public key obtained from theShare algorithm and Bob’s share of the secret key.

The subroutine\(\mathsf{Sim}_A\) takes as input a direction\(\mathsf{way} \in \{+\rightarrow \times , \times \rightarrow +\}\), a source ciphertextC, a twin ciphertext\(\bar{C}\) and a flowflow. It emulates the output of an honest playerA would answer upon receiving the flowflow when running the protocol\(\mathsf{Switch}_{\mathsf{way}}((pk,sk_A,C),(pk,sk_B,C))\) without\(sk_A\) but possibly\(sk_B\), and forcing the output to be a ciphertext\(C'\) which is equivalent to\(\bar{C}\).

Then, for all\(\lambda \in \mathbf {N}\), for any parameters\((\mathsf{params}_+,\mathsf{params}_\times ) \leftarrow \mathsf{Setup}(1^\lambda )\), for any pairs of keys\((pk_+,sk_+)\leftarrow \varPi _+{.}\mathsf {KeyGen}(1^\lambda ,\mathsf{params}_+)\) and\((pk_\times ,sk_\times )\leftarrow \varPi _\times {.}\mathsf {KeyGen}(1^\lambda ,\mathsf{params}_\times )\),\((pk,sk_A,sk_B) \leftarrow \mathsf{Share}((pk_+,sk_+),(pk_\times ,sk_\times ))\) or for anysimulated share\((pk',sk'_B)\leftarrow \mathsf{Sim}_\mathsf{Share}(pk)\), and for any adversary\(\mathcal {D}\) playing the role ofB, the advantage

is negligible.

We define similarly an encryption switching protocols\(\varPi _+ \rightleftharpoons \varPi _\times \) that iszero-knowledge forB. It iszero-knowledge if it is zero-knowledge forA andB.

We describe in this section a generic construction of an encryption switching protocol in the semi-honest model. Even though an ESP could allow to switch between any encryption schemes, its main interest is when its implemented with homomorphic encryptions. Therefore, we start with an additively homomorphic encryption\(\varPi _+\) and a multiplicatively homomorphic encryption\(\varPi _\times \) whose message space is respectively a ring\(\mathcal {R}\) and a monoid\(\mathcal {M}\). To fit most of the applications, we will make the assumption that\(\mathcal {M}= \mathcal {R}^*\), the subgroup of invertible elements of\(\mathcal {R}\), since in general the multiplicative homomorphic encryption will have a group as message space. In particular, this means that the intersection over which the switches are defined is\(\mathcal {R}\cap \mathcal {M}=\mathcal {R}^*\).

As in [10], in the first place, we are going to describe how we can switch between\(\varPi _{+}\)-encryptions and\(\varPi _{\times }\)-encryptions over\(\mathcal {R}^*\). Then we will show how to modify\(\varPi _\times \) in order to extend its message space to\(\mathcal {R}^*\cup \{0\}\).

Definition 6

(Compatible encryption protocols). Let\((\mathcal {R},+,\times )\) be a ring. Let\(\varPi _{+}\) and\(\varPi _{\times }\) be an additively and multiplicatively homomorphic encryption in the sense of Definitions 1 and2. They are said to becompatible if\(\varPi _{+}\) and\(\varPi _{\times }\) have respectively\(\mathcal {R}\) and\(\mathcal {R}^*\) as message space, both of them admit a one-round 2-party decryption as defined in Sect. 2.2, there exists a common setup algorithm\(\mathsf{Setup}\) and common\(\mathsf{KeyGen}\) which allows to set common parameters.

Remark 3

To illustrate this, our instantiation (resp. Couteau et al.’s instantiation) switches between an additively homomorphic encryption whose message space is the field\((\mathbf {Z}/p\mathbf {Z},+,\times )\) (resp. the ring\((\mathbf {Z}/N\mathbf {Z},+,\times )\)) and a multiplicative homomorphic encryption whose message space is the group\(((\mathbf {Z}/p\mathbf {Z})^*,\times )\) (resp.\(((\mathbf {Z}/N\mathbf {Z})^*,\times )\)) and the former is modified so that its message space is the monoid\((\mathbf {Z}/p\mathbf {Z},\times )\) (resp.\(((\mathbf {Z}/N\mathbf {Z})^*\cup \{0\},\times )\)). In particular, Couteau et al.’s make the additional algorithmic assumption that\((\mathbf {Z}/N\mathbf {Z})^*\) is computationally equal to\(\mathbf {Z}/N\mathbf {Z}\).

Share Protocol of the ESP. The keys of\(\varPi _{+}\) and\(\varPi _{\times }\) are first shared by a trusted dealer, this corresponds to theShare algorithm from Definition 4. From public parameters generated using the commonSetup algorithm and two pairs of keys\((pk_+,sk_+)\) and\((pk_\times ,sk_\times )\) it outputs the secret share\(sk_A=(sk_A^+,sk_A^\times )\) for Alice and\(sk_B=(sk_B^+,sk_B^\times )\) for Bob using theShare procedures of the 2-party decryption of\(\varPi _{+}\) and\(\varPi _{\times }\).

4.1Switching Protocols over\(\mathcal {R}^*\)

We describe here the two 2-party switching protocols from an additive homomorphic encryption ofm to a multiplicative one andvice versa. Contrary to Couteauet al.’s protocol [10], the two protocols are actually thesame since both the additive and the multiplicative scheme support a\(\mathsf {ScalMul}\) operation and asingle-round 2-party decryption. It is important to note that in our instantiation, the round complexity is only 2, since the first ciphertext\(C^{(2)}_{R^{-1}}\) can be sent within the flow of the 2-party decryption which is only one round (cf. Sect. 2.2 or Figs. 9 and11). We suppose that\(m \ne 0\) here, and more precisely the message to be switched lies in\(\mathcal {R}\cap \mathcal {M}= \mathcal {R}^*\).

Switching Protocols Between\(\varPi _1{.}\mathsf {Encrypt}(m)\)and\(\varPi _2{.}\mathsf {Encrypt}(m)\). In Fig. 3, as our switching protocols in the two directions are the same, the pair\((\varPi _1,\varPi _2)\) is either\((\varPi _+,\varPi _\times )\) or\((\varPi _\times ,\varPi _+)\).

2-party\(\mathsf{Switch}_{1\rightarrow 2}\) from\(\varPi _1\) to\(\varPi _2\) where\((\varPi _1,\varPi _2) \in \{(\varPi _+,\varPi _\times ), (\varPi _\times ,\varPi _+)\}\).

Full size image

The correctness of these two protocols is clear. They are generic and the switch from\(\varPi _{\times }\) to\(\varPi _{+}\) is highly simpler than the one in [10] (ours is 2-round instead of 6-round) and our instantiation will keep this simplicity. We prove in the following theorem that they are zero-knowledge, and the security proof itself is also very simple. It only relies on the zero-knowledge property of the shared decryptions.

Theorem 3

The ESP between\(\varPi _+\) and\(\varPi _\times \), whose switching routines are described in Fig. 3, is zero-knowledge if\(\varPi _+\) and\(\varPi _\times \) are two compatible encryption schemes which have zero-knowledge one round 2-party decryptions.

Proof

The proof consists in proving that after a share of the secret keys, both switching procedures are zero-knowledge for Alice and Bob. Let us start with the proof that the ESP is zero-knowledge for Alice. We are going to describe a simulator\(\mathsf{Sim}\) whose behavior is indistinguishable from Alice’s behavior in front of an adversarial Bob.

\(\mathsf{Sim_\mathsf{Share}}\): The simulator receives as input the public key\((pk_+,pk_\times )\) and simulates the\(\mathsf{Share}\) procedure as follows: it calls out the\(\mathsf{Sim}^{2d}_\mathsf{Share}\) procedures of the zero-knowledge property of Alice for 2-party decryption of respectively\(\varPi _{+}\) and\(\varPi _{\times }\) with\(pk_+\) and\(pk_\times \) as input. In particular it obtains\(sk_B'=(x_B^+,x_{B}^\times )\) it can feed the adversary with. When\(\mathsf{Sim}\) is requested for a switch, it receives a pair of twin ciphertexts\((C,\bar{C})\).

Game\(G_0\). This game is the real game. The simulator generates all the secret shares in an honest way and gives his share to Bob. It plays honestly any switching protocols on an input\((C,\bar{C})\) using Alice’s secret key.

Game\(G_1\). The first modification concerns theadditive to multiplicative direction. The setup and key generation are the same as in the previous game. When requested to participate to a\(\mathsf{Switch}_{+\rightarrow \times }\), with\((C,\bar{C})\) as input, the simulator picks uniformally at random\(x \in \mathcal {R}^*\) and sets\(C^+_{mR} = \varPi _+{.}\mathsf {Encrypt}(x)\) and\(C^\times _{R^{-1}}=\varPi _\times {.}\mathsf {ScalMul}(\bar{C},x^{-1})\). The simulator then concludes the protocol honestly. This game is indistinguishable from the previous since, asx is random, it is equivalent to a genuine protocol using\(R = x/m\), wherem is the plaintext underC and\(\bar{C}\).

Game\(G_2\). In this game, we modify the shared decryption for\(\varPi _+\) using the simulator of 2-party decryption. First, the simulation gives the key\(x_{B}^+\) obtained by the simulation of the shares to Bob. Then after\(\mathsf{Sim}\) simulated the pair\((C^+_{mR},C^\times _{R^{-1}})\) as above, it uses the simulator\(\mathsf{Sim}^{2d}_A(C^+_{mR},x,x_B^+,\cdot )\) for the 2-party decryption of\(\varPi _{+}\) to interact with Bob, where\(C^+_{mR}\) is an encryption ofx. Thanks to the property of this simulator this game is indistinguishable from the previous one (note that the key\(x_{B}^+\) is only used in that part of the protocol). Eventually, the last computation done by Bob,\(\varPi _{\times }{.}\mathsf {ScalMul}(C^\times _{R^{-1}},x)\) gives a multiplicative ciphertext ofm equivalent to\(\bar{C}\).

Game\(G_3\). In this game, we address themultiplicative to additive way. The setup and key generation are the same as in the previous games. As in Game\(G_1\), when requested to participate to a\(\mathsf{Switch}_{\times \rightarrow +}\), with\((C,\bar{C})\) as input, the simulator picks uniformally at random\(x\in \mathcal {R}^*\) and sets\(C^\times _{mR} = \varPi _{\times }{.}\mathsf {Encrypt}(x)\) and\(C^+_{R^{-1}}=\varPi _{+}{.}\mathsf {ScalMul}(\bar{C},x^{-1})\). Then,\(\mathsf{Sim}\) continues honestly the protocol. This game is indistinguishable from the previous one.

Game\(G_4\). The shared\(\varPi _\times \) decryption is modified as in Game\(G_2\). The simulation now gives the simulated key\(x_{B}^\times \) to Bob and then uses the simulator for the 2-party decryption of\(\varPi _{\times }\) with ciphertext\(C^\times _{mR}\) and corresponding plaintextx. Thanks to the property of this simulator this game is indistinguishable from the previous one. Again, Bob’s last computation\(\varPi _{+}{.}\mathsf {ScalMul}(C^+_{R^{-1}},x)\) gives a ciphertext equivalent to\(\bar{C}\).

In conclusion, the advantage of the attacker is negligible.

We now prove that the ESP is zero-knowledge for Bob, by describing a simulatorSim whose behavior is indistinguishable from Bob’s behavior in front of an adversarial Alice. The simulator receives as input the public key\(pk= (pk_+,pk_\times )\) and simulates the\(\mathsf{Share}\) procedure as above and feed the adversary (Alice) with the corresponding secret key. When\(\mathsf{Sim}\) is requested for a switch, it receives a pair of twin ciphertexts\((C,\bar{C})\). In both directions, the simulation is trivial, since Bob’s only flow is the final forward of the twin ciphertext (we have suppose that the 2-party decryption has only one round from Alice to Bob), which is done by sending the\(\bar{C}\) ciphertext. This is indistinguishable from a true execution since\(\bar{C}\) is a random ciphertext which encrypts the same plaintext thatC.    \(\square \)

4.2Modification of\(\varPi _\times \) to Embed the Zero Message

One technical issue to design switching protocols between\(\varPi _+\) and\(\varPi _\times \) is to embed the zero message into\(\varPi _\times \)’s message space so that the message spaces match. To do so, we need to modify the\(\varPi _\times \) encryption. We will use a technique quite similar to those in [10]: During their encryption, if the messagem is equal to 0, a bitb is set to 1. It is set to 0 for any other message. Then, the message\(m+b\) (which is never 0) is encrypted using their Elgamal encryption. As this encryption scheme is no longer injective, to discriminate an encryption of 0, the ciphertext is accompanied by two encryptions under classical Elgamal of\(T^b\) and\(T'^b\) where\(T,T'\) are random elements. We note that these two encryptions are in fact encryptions ofb which are homomorphic for the or gate: If\(b=0\), we get an Elgamal encryption of 1 and if\(b=1\), an Elgamal encryption of a random element (which is equal to 1 only with negligible probability). Thanks to the multiplicativity of Elgamal, if we multiply an encryption ofb and an encryption of\(b'\), we get an Elgamal encryption of 1 only if\(b=b'=0\) and an Elgamal encryption of a random element otherwise. In [10] the second encryption ofb is actually an extractable commitment, the corresponding secret key is only known by the simulator in the security proof.

In our case, we use the additively homomorphic encryption\(\varPi _+\) to discriminate the zero message:\(\varPi _+\) is used to encrypt a random elementr if\(m=0\) and 0 otherwise. As a consequence, it will be possible to directly obtain an encryption of\(\bar{b}\) (the complement of the bitb used during encryption) under\(\varPi _+\) using the zero-testing procedure during the switch from\(\varPi _\times ^0\) to\(\varPi _+\) (see Fig. 7). This gives a real improvement compared to [10] when we instantiate our generic protocols. As in [10] we add a useless second encryption ofr to be used by the simulation in the security proof. Our modification is formally described in Fig. 4. The\(\mathsf {Hom}_\times \) procedure is obtained by applying the\(\mathsf {Hom}_\times \) procedures of\(\varPi _\times \), and\(\varPi _+\). For the\(\mathsf {ScalMul}\) procedure, which corresponds to a multiplication by a plaintext\(\alpha \), it applies the\(\mathsf {ScalMul}\) procedure of\(\varPi _\times \) if\(\alpha \ne 0\) and add an encryption of 0 to the additive part. If\(\alpha =0\), it outputs an encryption of 0.

\(\varPi _\times \) over\(\mathcal {R}\):\(\varPi _\times ^0\)

Full size image

The protocol\(\varPi _\times ^0\) directly inherits the indistinguishability under a chosen message attack from those of\(\varPi _\times \) and\(\varPi _+\). By a standard hybrid argument, we can prove the following theorem, whose proof is omitted.

Theorem 4

If\(\varPi _+\) and\(\varPi _\times \) are IND-CPA, then\(\varPi _\times ^0\) is also IND-CPA.

4.3Full Switching Protocols

Encrypted Zero-Test. In [10] an encrypted zero test (EZT) to obliviously detect the zero messages during switches is presented. In our case,EZT takes as input a ciphertext\(C^+_m\) from the additively homomorphic encryption\(\varPi _+\) of a messagem and outputs a\(\varPi _+\) ciphertext\(C^+_{b}\) of a bitb equals to 1 if\(m=0\) and equals to 0 otherwise. TheEZT has to be zero-knowledge in the sense that there exists an efficient simulator for each player which, on input a pair of twin ciphertext\((C,\bar{C})\), is indistinguishable from these honest players. This simulator runs without the secret share of the user it simulates.

During the security proof, the simulator will obtain the bitb thanks to the knowledge of the secret key which decrypts the additional encryption ofr appended during encryption (see Fig. 4).

ThisEZT protocol is done using garbled circuits techniques. An alternative would be to use techniques based on homomorphic encryption [32]. The resulting protocol is described in Fig. 5. The function\(H: \mathcal {R}^* \longrightarrow \{0,1\}^\kappa \) (for a security parameter\(\kappa \)) belongs to a universal hash function family (in practice, this will be a reduction modulo\(2^\kappa \) of the integer representation of an element of\(\mathcal {R}\)). We denote by\(\mathsf{eq}\) the function that on input\((u,v)\in \{0,1\}^\kappa \) outputs 1 if\(u=v\) and 0 otherwise and we denote by\(\mathsf{Garble}(f)\) the computation of a garbled circuit evaluating the functionf.

\(\mathsf{EZT}\): 2-party protocol to compute\(C_{b}^+\) from\(C_{m}^+\)

Full size image

The correctness of the protocol comes from the fact that the last three lines of the protocol compute the encryption of\(b_A\oplus b_B\) by homomorphically evaluating\(b_A+b_B-2b_Ab_B\) from the encryptions of\(b_A\) and\(b_B\). By construction,\(b_A\oplus b_B = \mathsf{eq}(r',r'')\) which is equals to 1 if\(m =0\) and 0 otherwise, with probability\(1-2^{-\kappa }\). This is exactly the encryption of the bitb. This protocol is zero-knowledge (see [10]). Using [28], the communication needed is\(8\kappa ^2\) bits of preprocessing for the garbled circuit and\(\kappa ^2\) bits and\(\kappa \) oblivious transfers for the online phase (cf. [10, Fig. 4]).

2-party\(\mathsf{Switch}_{+ \rightarrow \times }\) from\(\varPi _+\) to\(\varPi _\times ^0\) over\(\mathcal {R}^*\cup \{0\}\)

Full size image

2-party\(\mathsf{Switch}_{\times \rightarrow +}\) from\(\varPi _\times ^0\) to\(\varPi _+\) over\(\mathcal {R}^*\cup \{0\}\)

Full size image

4.42-Party ESP Between\(\varPi _+{.}\mathsf {Encrypt}(m)\) and\(\varPi _\times ^0{.}\mathsf {Encrypt}(m)\)

The protocol of Fig. 6 is quite similar to the one of [10]. First we use the\(\mathsf {EZT}\) sub-protocol to get a\(\varPi _{+}\) encryption of the bitb. A notable difference with the protocol of [10] is that this encryption ofb can be used directly to set an element of the ciphertext for\(\varPi _{+}^0\), which saves many rounds in the interaction. Since the bitb is encrypted twice (this second encryption is only used during the security proof), the\(\mathsf{ReEnc}_+\) protocols allows to re-encrypt the output of\(\mathsf {EZT}\) to the right public key. Then, thanks to the homomorphic property of the\(\varPi _{+}\) scheme, Alice can construct an additive encryption of\(m+b\) and the\(\mathsf{Switch}_{+ \rightarrow \times }\) protocol of Fig. 3 is used to get the\(\varPi _{+}\)-encryption of\(m+b\). The two ciphertexts ofb are randomized to get a proper multiplicative ciphertext.

In Fig. 7, starting from a multiplicative ciphertext ofm, we run an\(\mathsf{Switch}_{\times \rightarrow +}\) with the first component of\(C_m^\times \), which is a\(\varPi _{\times }\)-encryption of\(m+b\). Hence, we get\(C^+_{m+b}\). Then, we run the\(\mathsf{EZT}\) protocol on the second component\(C_r^+\) and the output the encryption of a bit\(b'\) whose value is 1 when\(r = 0\), i.e., when\(b=0\) and 0 otherwise. Therefore\(b'=\bar{b}\) and\(\mathsf{EZT}\) actually outputs an encryption of\(\bar{b}\). It is now possible to homomorphically remove the bitb remaining in the\(\varPi _{+}\)-encryption of\(m+b\),\(C_{m+b}^+\). Inspired by the implicit technique used in [10], we use the\(\mathsf {2Mul}_{+}\) protocol to obtain, from\(C_{\bar{b}}^+\) and\(C_{m+b}^+\), a\(\varPi _{+}\)-encryption of\((m+b)\bar{b}\) which is equal to a\(\varPi _{+}\)-encryption ofm.

Note that we can not simply use the fact that\(m+b+\bar{b}-1 = m\) over\(\mathbf {Z}\) to getm: The expression\(m+b\) is really equal to the messagem plus the bitb only for fresh multiplicative ciphertexts. After an homomorphic multiplication between a ciphertext of a non zero message with a ciphertext of zero it becomes something random. As a result, we have to multiply it by\(\bar{b}\) to get 0.

The zero-knowledge property of our ESP essentially comes from the fact that each routine (\(\mathsf{ReEnc}_+\) and\(\mathsf {2Mul}_{+}\)) is individually zero-knowledge, inherited from the zero-knowledge of the 2-party decryption of the encryption protocols. We also use the fact that the encryption schemes are IND-CPA, in order to be able to simulate intermediate ciphertexts. This means that the assumptions in our theorem are weak and very natural.

Theorem 5

The ESP between\(\varPi _+\) and\(\varPi _\times ^0\) whose routines are described in Figs. 6 and7 is zero-knowledge if\(\varPi _{+}\) and\(\varPi _{\times }\) are two compatible encryptions that are IND-CPA and whose 2-party decryptions are zero-knowledge, and\(\mathsf {EZT}\) is zero-knowledge.

Proof

(sketch). The full proof of this theorem can be found in Appendix B. This proof can be sketched as follows: First we give the secret key\(sk'\) to the simulation. From a pair of twin ciphertexts, it allows the simulation to know the bit that encode the fact that the plaintext is 0 or not. With that knowledge, the simulation can retrieve the ciphertexts that constitute the input and the output of each building block, and use their zero-knowledge simulator to emulate them. Then, we remove the knowledge of\(sk'\) from the simulation which replaces each input and output by random ciphertexts. Thanks to the IND-CPA property of the encryption schemes this is indistinguishable from the previous step. As a result, the whole protocol is simulated without knowing any secret.    \(\square \)

In this section we provide an instantiation of our generic construction on a field\(\mathbf {Z}/p\mathbf {Z}\) for a primep, by describing an additively homomorphic encryption and a multiplicatively homomorphic one. Both schemes enjoy an Elgamal structure. For the additively homomorphic encryption scheme, we will use as a basis the scheme introduced in [9] (denoted\(\mathsf {CL}\) in the following). It uses the notion of a\(\mathsf {DDH}\)group with an easy\(\mathsf {DL}\)subgroup, which is instantiated using class groups of quadratic fields. For the multiplicatively homomorphic scheme, we devise a variant of the traditional Elgamal encryption over the whole group\((\mathbf {Z}/p\mathbf {Z})^{*}\). Both schemes are described in the next subsection. We also describe their 2-party decryption, since it is required by the generic construction.

5.1Additively Homomorphic Scheme over\(\mathbf {Z}/p\mathbf {Z}\)

Castagnos-Laguillaumie Encryption. The encryption scheme from [9] is additively homomorphic modulo a primep. The general protocol is well suited for relatively smallp. For the ESP context, we need a large message space asp must be at least of 2048 bits for the security of the Elgamal protocol. As a result, we use the first variant of\(\mathsf {CL}\) described in [9, Sect. 4]. This variant is defined with subgroups of the class group of an order of a quadratic field of discriminant\(\varDelta _p=-p^3\). Thus all computations are done in this class group. Note that elements are classes of ideals, that can be represented by their unique reduced elements, i.e., by two integers of roughly the size of\(\sqrt{|\varDelta _p|}\). As a consequence, a group element can be represented with\(3\log p\) bits.

We provide some improvements detailed in the following. The\(\mathsf {CL}\) scheme does exponentiations to some random powers in a cyclic group of unknown order. Let us denote by\(\mathfrak {g}\) a generator of this group. Only an upper boundB on this order is known. In order to make the result of these exponentiations look like uniform elements of the cyclic group, the authors of [9] choose to sample random exponents from a large enough uniform distribution, and more precisely over\(\{0,\dots ,B'\}\) where\(B'= 2^{\lambda -2} B\), so that the resulting distribution is as distance to uniform less than\(2^{-\lambda }\).

However, it is more efficient to use a folded discrete Gaussian Distribution instead of a folded uniform distribution. Let\(z\in \mathbf {Z}\) and\(\sigma >0\) a real number and let us denote by\(\rho _{\sigma }(z) = \exp (-\pi z^2 / \sigma ^2)\) a Gaussian centered function and define the probability mass function\(\mathcal D_{\sigma }\) over\(\mathbf {Z}\) by\(\mathcal D_{\sigma }(z):= \rho _{\sigma }(z) / \sum _{z \in \mathbf {Z}} \rho _\sigma (z)\).

Ifz is sampled from\(\mathcal D_\sigma \), we have\(|z|> \tau \sigma \) with probability smaller than\(\sqrt{2\pi e} \tau \exp (-\pi \tau ^2)\) (cf. [35, Lemma 2.10]). We denote by\(\tau (\lambda )\) the smallest\(\tau \) such that this probability is smaller than\(2^{-\lambda }\).

If we set\(\sigma = \sqrt{\ln (2(1+ 2^{\lambda +1}))/\pi } B\), Lemma 1 of Appendix C of the long version shows that the distribution obtained by samplingz from\(\mathcal D_\sigma \) and computing\(\mathfrak {g}^z\) is at distance less than\(2^{-\lambda }\) to the uniform distribution in\(\langle \mathfrak {g}\rangle \).

For instance for\(\lambda =128\), we only add, in the worst case, 6 iterations in the square and multiply algorithm to compute\(\mathfrak {g}^z\), whereas one has to add 126 iterations with a folded uniform distribution.

Description of the Scheme. We denote by\(\mathsf {CL}{.}\mathsf {Gen}\) a parameter generator for\(\mathsf {CL}\). It takes as input\(1^\lambda \) and outputs a tuple\((p,\mathfrak g, \mathfrak f,\sigma )\). This tuple is such thatp is a prime satisfying\(p\equiv 3 \pmod 4\) so that computing discrete logarithms in\(C(-p)\), the ideal class group of the quadratic order of discriminant\(-p\), takes\(2^\lambda \) times. Then\(\mathfrak g \in C(-p^3)\) is a class of orderps wheres is unknown and expected to be of the order of magnitude of the class number of\(C(-p)\): a concrete implementation for\(\mathfrak g\) is given in [9, Fig. 2]. It consists in generating a random ideal of the maximal order of discriminant\(-p\), and lifting it in the order of discriminant\(-p^3\). Eventually,\(\mathfrak {f} \in C(-p^3)\) is the class of the ideal\(p^2\mathbf {Z}+ ((-p+\sqrt{-p^3})/2)\mathbf {Z}\) and\(\sigma \) will be the standard deviation of the Gaussian Distribution discussed before:\(\sigma = \sqrt{\ln (2(1+ 2^{\lambda +1}))/\pi } B\), with\(B = \log (p)p^{3/2}/(4\pi )\).

The scheme relies on the notion of a\(\mathsf {DDH}\) group with an easy\(\mathsf {DL}\) subgroup. It is IND-CPA under the\(\mathsf {DDH}\) assumption in the group generated by\(\mathfrak g\). On the other hand, in the subgroup of orderp generated by\(\mathfrak f\), there is a polynomial time algorithm, denoted\(\mathsf {CL}{.}\mathsf {Solve}\) which takes as input an element of\(\langle \mathfrak f \rangle \) and which outputs its discrete logarithm in basis\(\mathfrak f\). We refer the reader to [9] for concrete implementation of\(\mathsf {CL}{.}\mathsf {Gen}\) and\(\mathsf {CL}{.}\mathsf {Solve}\). The resulted scheme is given in Fig. 8.

Castagnos-Laguillaumie over\(\mathbf {Z}/p\mathbf {Z}\):CL

Full size image

Theorem 6

[9]. The\(\mathsf {CL}\) scheme of Fig. 8 is an additively homomorphic encryption scheme over\(\mathbf {Z}/p\mathbf {Z}\), IND-CPA under the\(\mathsf {DDH}\) assumption in the ideal class group of the quadratic order of discriminant\(-p^3\).

One Round 2-Party Decryption for\(\mathsf {CL}\). We now devise in Fig. 9 a one round 2-party decryption for\(\mathsf {CL}\) as defined in Sect. 2.2, i.e. subroutines to share the secret key and the interactive protocol for decryption. As the scheme has an Elgamal structure, it can be readily adapted from the threshold variant of the original Elgamal scheme (cf. [39] for instance) with a simple additive secret sharing of the key\(x = x_A + x_B\). However, as the group order is unknown, this secret sharing must be done over the integers. This kind of sharing has been addressed before (cf. [14, Sect. 4] for instance).

Asx is sampled from\(\mathcal D_{\sigma }\), we saw before that\(x \in [-\tau (\lambda )\sigma , \tau (\lambda )\sigma ]\) for a small\(\tau (\lambda )\) except with negligible probability. Then the integer\(x_A\) is taken uniformly at random in the interval\([-\tau (\lambda )\sigma 2^{\lambda }, \tau (\lambda )\sigma 2^{\lambda }]\), and\(x_B = x- x_A\). This choice makes the secret sharing private. Note that in that case, there is no gain in using a Gaussian Distribution to generate the shares. We refer the interested reader to Appendix D of the long version for details.

2-party decryption for\(\mathsf {CL}\)

Full size image

Theorem 7

The 2-party Decryption for\(\mathsf {CL}\) described in Fig. 9 is correct and zero-knowledge.

Proof

Correctness follows from the shared exponentiation. Let us prove first that the protocol is zero-knowledge for Alice (see Definition 7 in Appendix A).

For the secret key shares, the simulator\(\mathsf{Sim}^{2d}_\mathsf{Share}\) picks\(x'\) from\(\mathcal {D_\sigma }\),\(x'_A \xleftarrow {\$}\{-\tau (\lambda )\sigma 2^{\lambda },\dots ,\tau (\lambda )\sigma 2^{\lambda } \}\) and set\(x'_B = x' - x'_A\). As the secret sharing is private, the distribution of\(x'_B\) is statistically indistinguishable from the distribution of the real\(x_B\) (see Appendix D of the long version for the computation of the statistical distance).

Then we describe the simulator\(\mathsf{Sim}^{2d}_A\) which emulates Alice. From a ciphertextC, a plaintextm, it computes\(\mathfrak M = \mathfrak f^m\). Then it simulates\(\mathfrak {c}_{1,A}\) by setting\(\mathfrak {c}_{1,A} = \mathfrak {c}_2/(\mathfrak M \mathfrak {c}_1^{x'_B})\), so that Bob’s computations leads to\(\mathfrak M\). The value sent by the simulation is thus perfectly indistinguishable from the real one.

It is straightforward to see that the protocol is zero-knowledge for Bob: secret key shares are simulated as previously, and\(x'_A\) is obviously indistinguishable from the real\(x_A\), and then Bob sends nothing during the protocol.    \(\square \)

5.2Multiplicatively Homomorphic Scheme over\(\mathbf {Z}/p\mathbf {Z}\)

Elgamal over (Z/pZ)*. Letq be an odd Sophie Germain prime, and let us denote byp the associated prime,i.e.,\(p=2q+1\). The\(\mathsf {DDH}\) assumption is widely supposed to hold in the subgroup of orderq of\((\mathbf {Z}/p\mathbf {Z})^{*}\) which is the subgroup of quadratic residues modulop, denoted\(S_p\). The Elgamal cryptosystem defined in\(S_p\) is multiplicatively homomorphic and semantically secure if the\(\mathsf {DDH}\) assumption holds in that subgroup.

It is well-known that the\(\mathsf {DDH}\) assumption does not hold in the whole group\((\mathbf {Z}/p\mathbf {Z})^{*}\). As a result, in order to extend the message space to\((\mathbf {Z}/p\mathbf {Z})^{*}\), we need to encode elements of\((\mathbf {Z}/p\mathbf {Z})^{*}\) as quadratic residues. The situation is quite similar to the Elgamal over\((\mathbf {Z}/n\mathbf {Z})^{*}\) of [10], but actually simpler to handle since we work modulo a primep and not modulo an RSA integern (in particular, we can publicly compute square roots or distinguish quadratic and non quadratic residues and we do not have to hide the factorization ofn).

Since\(p=2q+1\), we have\(p \equiv 3 \pmod 4\), and\(-1\) is not a quadratic residue modulop. Let\(m \in (\mathbf {Z}/p\mathbf {Z})^{*}\), let us denote by\(( m / p )\) the Legendre symbol ofm modulop. Then\(( m / p )\times m\) is a quadratic residue modp. LetL be the group morphism from\(((\mathbf {Z}/p\mathbf {Z})^{*},\times )\) to\((\mathbf {Z}/2\mathbf {Z},+)\) that mapsm to 0 (resp. to 1) ifm is a quadratic residue (resp. is a non quadratic residue). The map

is a group isomorphism. As a consequence we can encode elements of\((\mathbf {Z}/p\mathbf {Z})^{*}\) as a square plus one bit. The square can be encrypted with the traditional Elgamal encryption, and the bitL(m) has to be encrypted separately. In order to have a multiplicatively homomorphic encryption,L(m) has to be encrypted with a scheme that is homomorphic for the addition in\(\mathbf {Z}/2\mathbf {Z}\). We choose Goldwasser-Micali encryption [23] for that. The drawback is that we need an additional assumption, namely the Quadratic Residuosity assumption (\(\mathsf {QR}\)) for the security of our protocol. To avoid that, an idea could have been to encryptL(m) as an integer in the exponent with another Elgamal scheme or with the additive scheme of the previous Subsection. However, after computing the product of\(\ell \) messages\(m_1,\dots ,m_{\ell }\) over encrypted data, the decryption would give more information than the Legendre symbol of the product of the\(m_i\)’s, namely\(\sum _{i=1}^n L(m_i)\) in the integers, instead of modulo 2. Moreover, this extra information has to be taken into account to devise a zero-knowledge 2-party decryption. As this information can not be simulated, this gives a complex 2-party protocol, perhaps by using an extra homomorphic encryption scheme like in [10]. Note that a solution consisting in randomizingL(m) by adding a (small) even integer, with a Gaussian Distribution, for instance, still leaks the number\(\ell \) of multiplications that have been made. As a result, it seems to be an interesting open problem to devise an encryption scheme that allows homomorphic addition in\(\mathbf {Z}/2\mathbf {Z}\), or that simulates it without leaks, without relying on a factorization-based assumption (in [10], the same problem was handled more smoothly thanks to the fact that the authors worked with a composite modulus).

Description of the Scheme. Let\(\lambda \) be a security parameter. Let\(\mathsf {GM}{.}\mathsf {Gen}\) be a parameter generator for the Goldwasser-Micali encryption scheme. It takes as input\(1^\lambda \) and outputs\((N,p',q')\) such that\(p',q' \equiv 3 \pmod 4\) are primes and\(N=p'q'\) is such that factoringN takes\(2^\lambda \) time. We use the threshold variant of Goldwasser-Micali described in [26] to define a suitable 2-party decryption.

We also define\(\mathsf {Eg}^*{.}\mathsf {Gen}\) a parameter generator for Elgamal. It takes as input\(1^\lambda \) and outputs (p, q, g) such thatq is a prime,\(p=2q+1\) is a prime such that computing discrete logarithms in\((\mathbf {Z}/p\mathbf {Z})^{*}\) takes\(2^\lambda \) times, andg a generator of\(S_p\),i.e., and element of\((\mathbf {Z}/p\mathbf {Z})^{*}\) of orderq. We depict in Fig. 10, the adaptation of Elgamal over the whole multiplicative group\((\mathbf {Z}/p\mathbf {Z})^{*}\), denoted\(\mathsf {Eg}^*\).

Elgamal over\((\mathbf {Z}/p\mathbf {Z})^{*}\):\(\mathsf {Eg}^*\)

Full size image

The following theorem is a consequence of the previous discussion and the properties of the Goldwasser-Micali variant. Note that moduloN,\(c_3^{(N-p'-q'+1)/4}\) equals 1 if\(c_3\) is a quadratic residue, and\(-1\) if\(c_3\) has Jacobi symbol 1 and is not a quadratic residue.

Theorem 8

The\(\mathsf {Eg}^*\) scheme of Fig. 10 is multiplicatively homomorphic over\((\mathbf {Z}/p\mathbf {Z})^{*}\), and it is IND-CPA under the\(\mathsf {DDH}\) assumption in the subgroup of quadratic residues of\((\mathbf {Z}/p\mathbf {Z})^{*}\) and the\(\mathsf {QR}\) assumption in\((\mathbf {Z}/N\mathbf {Z})^\times \).

One Round 2-Party Decryption for\(\mathsf {Eg}^*\). We describe in Fig. 11 a one round 2-party decryption for\(\mathsf {Eg}^*\). This protocol is adapted from the threshold variant of the original Elgamal scheme and the basic threshold Goldwasser-Micali of [26, Subsect. 3.1].

This simple protocol gives a huge performance improvement compared to the Elgamal over\((\mathbf {Z}/n\mathbf {Z})^{*}\) of [10]: in that work, after the exponentiations, a CRT reconstruction is needed to recoverm, and a quantity that leads to the factorization ofn must be shared. To make this 2-party reconstruction zero-knowledge, the authors use an additional additively homomorphic encryption, and have to do the reconstruction over encrypted data. As a result, the protocol is very complex (implicitly described in [10, Fig. 2]) with 5 rounds instead of 1.

2-party decryption for\(\mathsf {Eg}^*\)

Full size image

Theorem 9

The 2-party Decryption for\(\mathsf {Eg}^*\) described in Fig. 11 is correct and zero-knowledge.

Proof

The proof is similar to the proof of Theorem 7. For the Elgamal part of the protocol, secret key shares are simply taken uniformly at random in\(\{ 0,\dots , q-1 \}\), and the value sent by Alice is computed as\(c_{1,A} = c_2/(M c_1^{x_B})\), where\(M = ( m / p )m\). The Goldwasser-Micali part of the protocol is also simulated in a similar fashion from\(c_3\) andL(m) and the key share from a fake factorization ofN just as in [26, Subsect. 3.1]    \(\square \)

Extension of the Message Space from\((\mathbf {Z}/p\mathbf {Z})^{*}\)to\(\mathbf {Z}/p\mathbf {Z}\). We use the generic construction depicted in Fig. 4 with the additively homomorphic scheme described in the previous subsection. We denote by\(\mathsf {Eg}_p{.}\mathsf {Gen}\), a group generator which combines the generators for\(\mathsf {Eg}^*\) and\(\mathsf {CL}\): on input\(1^\lambda \), it first runs\(\mathsf {Eg}^*{.}\mathsf {Gen}\), which outputs (p, q, g). The primep equals\(3 \mod 4\) and is such that computing discrete logarithms in\((\mathbf {Z}/p\mathbf {Z})^{*}\) takes time\(2^\lambda \). As the best algorithms for computing such discrete logarithms are faster than the algorithms for computing discrete logarithms in the class group\(C(-p)\) (the sub-exponential complexity is respectively\(L_p[1/3,(64/9)^{1/3}+o(1)]\) and\(L_p[1/2,1+o(1)]\), see [24,43]), this primep is compatible with the prime generated by\(\mathsf {CL}{.}\mathsf {Gen}\). As a result\(\mathsf {Eg}_p{.}\mathsf {Gen}\) executes\(\mathsf {CL}{.}\mathsf {Gen}\) by setting this primep and adapts the others quantities accordingly. The resulting scheme is described in Fig. 12 for completeness.

Elgamal over\(\mathbf {Z}/p\mathbf {Z}\):\(\mathsf {Eg}_p\)

Full size image

5.3ESP over\(\mathbf {Z}/p\mathbf {Z}\): Efficiency and Comparisons

In Table 1 we give the round complexity (rc) and bit complexity (bc) of our algorithms and we compare our full ESP protocols with that of Couteau et al. [10]. For sake of clarity, and because it is identical to that of [10], we omit the complexities resultant from the garbled circuit-based\(\mathsf {EZT}\) protocols. Our 2-party decryption algorithms (both for\(\mathsf {CL}\) and\(\mathsf {Eg}^*\)) only require 1 round. Note that we carefully analyzed the interactive algorithms so as to gather consecutive flows when possible within a single round. For example our\(\mathsf {2Mul}_{+}\) and\(\mathsf {ReEnc}_+\) protocols (see Figs. 1 and 2) require only 2 rounds since Alice can send\(C^+_{rX}\) (resp.\(C'_{-r}\)) and her\(2\mathsf {Dec}\) data simultaneously. For the same reason, our generic switches in\(\mathcal {R}^*\) also require 2 rounds. Therefore, our\((\varPi _+ \rightleftharpoons \varPi _\times ^0){.}\mathsf {Switch}_{+\rightarrow \times }\) needs 7 rounds: 2 for the initial\(\mathsf {EZT}\), 2 for\(\mathsf {ReEnc}_+\), 2 for sending\(C^+_{m+b}\) and the\(\mathsf {Switch}_{+\rightarrow \times }\), and 1 for sending the final result to Bob. In the other direction, the initial\(\mathsf {Switch}_{\times \rightarrow +}\) and the\(\mathsf {EZT}\) are independent and can thus be processed simultaneously in 2 rounds. Adding 2 rounds for the\(\mathsf {2Mul}_{+}\), the round complexity for\((\varPi _+ \rightleftharpoons \varPi _\times ^0){.}\mathsf {Switch}_{\times \rightarrow +}\) adds up to 4 rounds only. In comparison, and using the same optimizations, the ESP switches from Couteau et al. requires 7 and 11 rounds respectively.

We express the communication cost in terms of the number of bits exchanged between the parties. The bit complexity (bc) is given as a function of the ring/field size. Observe that although, the best (conjectured) asymptotic complexity to compute a discrete logarithm in the ideal class group used in\(\mathsf {CL}\) is in\(L_{p}[1/2,1+o(1)]\) (see [24]), one must consider a primep that is large enough to guarantee that the DLP over\((\mathbf {Z}/p\mathbf {Z})^{*}\) is hard, i.e. such that\(L_{p}[1/3,(64/9)^{1/3}+o(1)] > 2^\lambda \) (see e.g. [43]). In Table 1,\(\ell \), represents the bit length ofp for our protocol over\(\mathbf {Z}/p\mathbf {Z}\) and ofn for Couteau et al.’s protocol over\(\mathbf {Z}/n\mathbf {Z}\).

For our protocols, we give the bit complexities for two variants: for the version of\(\mathsf {CL}\) used in this paperbc is the cost deduced from Fig. 8. The drawback of this scheme is that ciphertexts are represented with 2 elements of\(C(-p^3)\) which gives\(2\times 2\times \frac{3}{2}\times \ell =6\ell \) against\(2\ell \) for Paillier. Therefore, we include a column with the costbc’ that correspond to the so-called “faster variant” of\(\mathsf {CL}\) from [9, Sect. 4]. This variant defines ciphertexts in\(C(-p)\times C(-p^3)\), represented with\(\ell + 3\ell = 4\ell \) elements. Moreover, for 2-party decryption we only have to share an exponentiation in\(C(-p)\) instead of\(C(-p^3)\) so the cost drops from\(6\ell + 3\ell = 9\ell \) to\(4\ell + \ell = 5\ell \).

For the former variant, the security depends upon DDH in\(C(-p^3)\) whereas for the faster variant it is based upon the following indistinguishability argument: Let\(\mathfrak g\) be a generator of a subgroup of\(C(-p)\). After having chosenm, the adversary is asked to distinguished the following distributions:\(\{(\mathfrak g^x\),\(\mathfrak g^y\),\(\psi (\mathfrak g^{xy}))\),\(x,y \leftarrow {\mathcal D}_{\sigma /p}\}\) and\(\{ (\mathfrak g^x,\mathfrak g^y,\psi (\mathfrak g^{xy}) {\mathfrak f}^m), x,y \leftarrow {\mathcal D}_{\sigma /p}\}\), where\(\mathcal D_{\sigma }\) is the Gaussian Discrete distribution defined in Subsect. 5.1 and\(\psi \) is a lifting map from\(C(-p)\) to\(C(-p^3)\), defined in [9, Lemma 3]. We denote LDDH by the corresponding assumption. The algorithmic assumptions required for each protocol are presented in Table 2.

To reach the security against malicious adversaries, it is necessary to add zero-knowledge proofs by all parties that every computation is done correctly with the knowledge of every plaintext. In [10], the zero-knowledge proofs are classical Schnorr-like proofs and range proofs, but they need also to design a new strong primitive calledtwin ciphertext proof (TCP) to prove that a pair of ciphertexts from two different encryption schemes is actually a pair of twin ciphertexts. This allows to avoid generic circuit-based zero-knowledge proofs, but still requires a costly cut-and-choose technique (which can be amortized). This proof consists first in gathering a large pool of random genuine twin ciphertexts (proved thanks to the knowledge of the plaintext and the randomness, and of the homomorphic property of the encryption schemes). This part is done once for all. During an ESP, each time a twin ciphertext proof is needed, a fresh twin ciphertext pair is taken from the pool to perform a simple co-linearity proof.

To enhance our generic construction against malicious adversaries, we use the same method. In fact, the additional properties needed for the homomorphic encryption schemes are the same as in [11]: the\(\varPi _+\) and the\(\varPi _\times \) encryption schemes must support zero-knowledge proof of plaintext knowledge, proof that the\(\mathsf {ScalMul}\) operation has been performed correctly and also support a 2-party decryption in the malicious setting. Then we use the TCP technique as in [10] for twin ciphertext proofs.

As a result, we modify our generic construction by adding such proofs in each step of the switching protocols. This ensures honest behavior and thus make the\(\mathsf {ESP}\) secure in the malicious settings. In particular this brings soundness in the sense of [10]: no malicious player can force the output of an\(\mathsf {ESP}\) not to be a twin ciphertext.

The protocols\(\varPi _+\) and\(\varPi _\times \) described in the instantiation from the previous section support the required features. For the\(\varPi _\times \) encryption scheme, we need zero knowledge proofs and 2-party decryption secure against malicious adversary for the classical Elgamal and for the Goldwasser-Micali encryption scheme. This can be done with classical methods: zero-knowledge proof\(\acute{a}\)la Schnorr, adding verification keys to the public keys for 2-party decryption and proof of exponentiations to the same power. Note that for Goldwasser-Micali, we need to modify key generation to use strong primes\(p'\) and\(q'\) as in [26].

For the\(\varPi _+\) encryption scheme which is based on the Castagnos-Laguillaumie encryption scheme, we need proofs for an Elgamal variant in a group of unknown order, namely a class group of a quadratic order. Then 2-party decryption secure against malicious adversary is obtained as for the\(\varPi _\times \) scheme.

Generalizations of Schnorr proofs in group of unknown orders have been addressed extensively in [7]. In this framework, a generalized Schnorr proof can be used if the cyclic group considered is what is called asafeguard group, which is roughly a group whose set of small orders elements is small and known, and for which it is hard to find roots of elements. The case of class groups has been explicitly taken in account for example in [12,13], where it is argue in particular that class groups of discriminant\(-p\),\(C(-p)\), can be considered to have the properties of safeguard groups. As a result, we can apply directly the framework of [7] for the faster variant of\(\mathsf {CL}\) mentioned in Subsect. 5.3 as exponentiations are defined in\(C(-p)\) for this variant.

The encryption switching protocol is a promising cryptographic primitive formalized by Couteau et al. in [10]. We propose in this article a generic framework to build such an ESP. Our approach makes the design of an ESP simple and efficient. In particular, we propose an instantiation whose round complexity is dramatically improved compared to Couteau et al., since we reduce by a factor 3 the number of round in the multiplicative to additive direction (while we have the same number of rounds in the other way). Again, in terms of bit complexity, our switching protocol in the multiplicative to additive direction gains a factor almost 1.7, while in the other direction Couteau et al.’s switch is smaller by a factor 1.2. This is essentially because in our case, the additively homomorphic encryption has large ciphertexts. In particular, any additively homomorphic encryption satisfying the conditions of our construction with smaller elements will allow to gain in terms of bit complexity. Our instantiation, which is secure in the semi-honest model under classical assumptions can be extended to the malicious case. We believe that it is possible to improve our instantiation by deviating a bit more from the generic construction. Moreover, an interesting open problem is to design an encryption scheme which is homomorphic for the\(+\) in\(\mathbf {F}_2\) without the factorization assumption. A consequence could be to have an ESP whose security relies only on a discrete logarithm related assumption. Designing a more efficient encrypted zero-test is also a direction which will allow a significant improvement in the protocol.