# Two-Party Secure Computation for Any Polynomial Function on Ciphertexts under Different Secret Keys

Authors: Bingbing Jiang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Multikey fully homomorphic encryption proposed by Lopez-Alt et al. (STOC12) is a significant primitive that allows one to perform computation on the ciphertexts encrypted by multiple different keys independently. Then, several schemes were constructed based on decisional small polynomial ratio or learning with errors. These schemes all require an expansion algorithm to transform a ciphertext under a single key into an encryption of the same message under a set of keys. To achieve the expansion algorithm without interaction with these key-keepers, their encryption algorithm not only outputs a ciphertext of a plaintext but also exports auxiliary information generated from the randomness used in the former encryption process. Beyond that, the size of the ciphertext encrypted by multiple keys increases linearly or quadratically in the number of participants. In this paper, we studied the problem whether someone can directly perform arbitrary computation on ciphertexts encrypted by different keys without any auxiliary information in the output of the encryption algorithm and an increase in the size of the ciphertext in the expansion algorithm. To this end, we proposed a novel and simple scheme of secure computation on ciphertexts under two different keys directly without any auxiliary information. In other words, each party just provides its own ciphertexts encrypted by the GSW scheme (CRYPTO13). In the procedure of executing evaluation on these ciphertexts, the size of the new ciphertext remains the same as that of the GSW ciphertext.


---

## Body

## 1. Introduction

The concept of multikey fully homomorphic encryption was proposed by Lopez-Alt et al. [1], which allows someone to perform arbitrary computations on the ciphertexts encrypted by multiple different secret keys. Specifically, each party independently encrypts input xi, to obtain a ciphertext ci=Encpkixi, and one can homomorphically evaluate an arbitrary function on these encrypted data without interaction between them. After this, there has been a lot of research [2–12] for its assumptions, functionalities, and performance.The main application of multikey FHE is that a plurality of parties is informed to engage in a computing task after they have submitted their data. This is a significant difference from the applications of the traditional (single-key) encryption schemes. For example, two hospitals want to cooperate and study the influence factors of some disease. However, the data of these patients has been encrypted and stored in their own servers ahead of this cooperation. How could an evaluation algorithm be performed directly on these ciphertexts without decrypting them? In [1], Lopez-Alt et al. focused on a problem whereby a (untrusted) cloud server wants to perform some computations over data from multiple clients without interacting with them after each client transmits their own (encrypted) input to the cloud and other clients. In the scheme proposed by Lopez-Alt et al. [1], although a ciphertext only contains an encryption of a plaintext, the size of a ciphertext under multiple secret keys becomes much larger than that of the original ciphertext and its security is based on the nonstandard assumption. The ciphertext’s length is related to the number of participants where the former increases at least linearly in the later. In the scheme of Clear and McGoldrick [3], an encryption of a message contains a universal mask U generated by another public-key encryption scheme. Also, the ratio of the size of the ciphertext under multiple keys and that under single key grow quadratically with an increase in the number of the associated participants. Afterwards, Mukherjee and Wichs [2] proposed an optimized scheme with a simple generation of the universal mask. However, there is still auxiliary information in the encryption algorithm and the ratio remains quadratic. Following the previous works, there are two independent researches about multikey fully homomorphic encryption introduced by Brakerski and Perlman [5] and Peikert and Shiehian [4], respectively. In the former scheme, although the authors replaced the algorithm of the universal mask with the bootstrapping algorithm, the ciphertext’s growth rate was still linear and their evaluation keys were generated by the previous multikey fully homomorphic encryption schemes. There are two versions in the paper in [4]. In the first scheme, the encryption of a message contains a commitment of the message and an encryption of the randomness used in the former commitment algorithm. The ratio becomes linear. In the second one, the encryption algorithm only outputs a ciphertext of a message, but the ratio becomes quadratic and the evaluation keys are generated by the first scheme. In [13], the growth rate is quadratic, and the output of the encryption algorithm also contains auxiliary information except a ciphertext of a plaintext. Recently, Chen et al. [6] proposed a multikey FHE scheme based on the ring-LWE (Learning with Errors) assumption, in which their ciphertext-extension algorithm only generates the evaluated keys for the scheme with multiple keys but the size of the ciphertext under multiple keys also relies on the number of associated parties.The first multikey fully homomorphic encryption was proposed by Lopez-Alt et al., but their solution is based on nonstandard assumptions. Subsequent solutions, despite being based on standard cryptographic assumptions (LWE), have two common shortcomings. The first shortcoming is that they require the encryption of not only the plaintext but also random numbers that have been used; namely,c=Encpk,m,r, and U=Encpk,r. Each ciphertext must be attached with additional information U. The second one is that the length of the ciphertext increases linearly or quadratically with the number of participants. In this paper, our main research problem is how to directly perform secure computation on ciphertext data c directly provided by each user without any additional information U. These ciphertext data are encrypted with different secret keys. Our main focus here is the case of encryption with two different keys. We begin by taking the GSW13 encryption scheme [14] into consideration as we notice that the main process of its decryption algorithm is the inner product of two vectors; that is, c,v=md+e, where d is a large constant. As such, if we want to calculate the product of ciphertexts c1 and c2 encrypted with different secret keys, we only need to calculate c1⋅c2T. This is because v1T⋅c1⋅c2T⋅v2=m1d+e1m2d+e2=m1m2d2+dm1e2+m2e1+e1e2. The final result is desirable, with m1m2 being one of its factors. However, there is another problem: the constant factor becomes d2, and small noises e1 and e2 are also multiplied by a large number. Therefore, we must find a way to decrease the constant factor to d, while keeping the noises within an acceptable range. Because the noise in the ciphertext grows with an increase in the number of addition and multiplication operations, when it increased to some value defined by the public parameters, it may cause incorrect decryption of the output ciphertext. Therefore, we should reduce the noise growth in evaluation.Our approach is to decryptc1⋅c2 in two steps without directly multiplying it by two secret keys. Instead, a single secret key is first used to decrypt it, that is, v1T⋅c1⋅c2T=m1d+e1c2 (denoted as tc1), before tc1/d is calculated and rounded to obtain tc=m1c2. Finally, another secret key is used to decrypt tc for the final plaintext m1m2. During the process, noises have been kept at a low level without being multiplied by a large constant factor. To sum up, the above description explains how to perform the multiplication operation on ciphertexts encrypted with two different keys. The addition operation can be transformed to the multiplication operation; that is, c1+c2=c1⋅c2′+c1′⋅c2, where c1′ and c2′ are encrypted from plaintext 1 with different secret keys. Till this step, we completed the addition and multiplication operations on ciphertexts encrypted with two different secret keys. However, this scheme has a shortcoming: the multiplication operation can only be performed once as the result of the multiplication operation on the ciphertexts encrypted with two different secret keys cannot be multiplied by other ciphertexts. In order to enable the support of polynomial calculation, we can write any polynomial f with u+v inputs x1,…,xu,y1,…,yv as follows: f=∑i=1wfi⋅gi, where the inputs of fi are x1,…,xu, and the inputs of gi are y1,…,yv. In this way, we can first use the single-key fully homomorphic encryption scheme to calculate fi and gi to obtain intermediate results and then calculate the final results with our proposed method. Therefore, our secure computation only involves the GSW13 encryption scheme without the requirement for additional information U. Moreover, unlike previous schemes where a ciphertext’s size grows linearly or quadratically as the number of secret keys increases, the ciphertext in our scheme always maintains its original size.Our Contributions. We proposed a protocol that allows one to perform any polynomial functions on the GSW ciphertexts under two different keys directly. Unlike the previous works, each party just provides the GSW ciphertexts without anything auxiliary of the private inputs and the size of the new ciphertext remains invariant when executing evaluations on these ciphertexts. In our Addition and Multiplication algorithms on ciphertexts under two different keys, the noise increases linearly. Compared to the scheme in [1], our scheme is based on the standard assumption. Our scheme reduces the size of the ciphertext under a single key from On4log4q in [2, 3] to On2log2q, where n is the lattice dimension and q is a modulus. Compared to the scheme in [5], our scheme does not require the expensive technique of bootstrapping to transform a ciphertext under a single key to a ciphertext under a set of keys. In the first scheme of [4], the size of the ciphertext under a single key is On3log3q. The second scheme of [4] requires its first scheme to generate a public key with larger size. Different from the scheme in [6], the size of the public key in our scheme is the same as that of the GSW13 scheme, whereas it is Ologq times the size of the GSW13 scheme.


## 2. Related Work

In the scheme proposed by Lopez-Alt et al. [1], although a ciphertext only contains an encryption of a plaintext, the size of a ciphertext under multiple secret keys becomes much larger than that of an original ciphertext and their security is based on the nonstandard assumption. The ciphertext’s length is related with the number of participants where the former increases at least linearly in the latter. In the scheme of Clear and McGoldrick [3], an encryption of a message contains a universal mask U generated by another public-key encryption scheme. Also, the ratio of the size of the ciphertext under multiple keys and that under single key grow quadratically with an increase in the number of the associated participants. Afterwards, Mukherjee and Wichs [2] proposed an optimized scheme with a simple generation of the universal mask. However, there is still auxiliary information in the encryption algorithm and the ratio remains quadratic. Following the previous works, there are two independent researches about multikey fully homomorphic encryption introduced by Brakerski and Perlman [5] and Peikert and Shiehian [4], respectively. In the former scheme, although the authors replaced the algorithm of the universal mask with the bootstrapping algorithm, the ciphertext’s growth rate was still linear and their evaluation keys were generated by the previous multikey fully homomorphic encryption schemes. There are two versions in the paper in [4]. In the first scheme, the encryption of a message contains a commitment of the message and an encryption of the randomness used in the former commitment algorithm. The ratio becomes linear. In the second one, the encryption algorithm only outputs a ciphertext of a message, but the ratio becomes quadratic and the evaluation keys are generated by the first scheme. In [13], the growth rate is quadratic and the output of the encryption algorithm also contains auxiliary information except a ciphertext of a plaintext. Recently, Chen et al. [6] proposed a multikey FHE scheme based on the ring-LWE assumption, in which their ciphertext-extension algorithm only generates the evaluated keys for the scheme with multiple keys but the size of the ciphertext under multiple keys also has a relationship with the number of associated parties.


## 3. Preliminary

### 3.1. Learning with Errors, SIVP, and GapSVP

Regev firstly introduced the Learning with Errors (LWE) problem in 2005 and showed that the hardness of LWE can be reduced quantum to the lattice hard problems. Then, Peikert introduced an efficient classical reduction between LWE and the lattice intractable problems. The details are given below.Definition 1.
(Learning with Errors). Letλ be the security parameter, let n=nλ be an integer dimension of a lattice, let q=qλ≥2 be an integer, and let χ=χλ be an error distribution over ℤ.(i)
(Searchable LWE) Samples⟵ℤqn uniformly and then draw ai⟵ℤqn uniformly, ei⟵χ. Set bi=ai,s+ei. The searchable LWE is to find s, given m=mλ samples ai,bii=1m, called LWEn,m,q,χ.(ii)
(Decision LWE) The decision LWE, denoted asLWEn,q,χ, is to distinguish two distributions: The first one is a uniform distribution over ℤqn+1. The second is that one first samples s⟵ℤqn and then draws ai,bi∈ℤqn+1 by sampling ai⟵ℤqn uniformly, ei⟵χ, and setting bi=ai,si+ei.
The Learning with Errors (LWE) assumption is thatLWEn,m,q,χLWEn,q,χ is intractable.Definition 2.
SIVPγn. Let Λ be an n−dimension lattice. The SIVPγn problem is to output n linearly independent vectors v1,…,vn such that maxivi≤γn⋅λn, where λn=minrr:dimspanB0,r∩Λ≥n.Definition 3.
GapSVPγn. Let Λ be an n−dimension lattice and let d be a real number. GapSVPγn is to distinguish whether λ1<d or λ1≥γn⋅d, where λ1 is the length of the shortest vector in Λ.Definition 4.
(B-bounded distributions). A distribution ensembleχnn∈ℕ over the integers is called B-bounded distribution if(1)Pre⟵χne>B=negln.Theorem 1.
Letq=qn be either a prime power or a product of small (size poly(n)) distinct primes, B≥ωlogn⋅n, and χ is an efficient sampleable B-bounded distribution. If there exists an efficient algorithm solving the LWEn,q,χ problem, thenThere is an efficient quantum algorithm forGapSVPO˜nq/B on any n-dimension latticeThere is an efficient classical algorithm that solvesGapSVPO˜nq/B on any n-dimension lattice
In both cases, if one also considers solvingLWEn,q,χ with subpolynomial advantage, then request B≥O˜n and γn≥O˜n1.5q/B.


### 3.2. Fully Homomorphic Encryption

A fully homomorphic encryption is a tuple of algorithms (Gen, Enc, Dec, Eval) described as follows:pk,sk,evk⟵Gen1λ: on the security parameter λ, output a public key pk, a secret key sk, and a public evaluation key evk.c⟵Encpk,μ: encrypt a message μ from the plaintext space and output a ciphertext c.μ⟵Decsk,c: decrypt a valid ciphertext c and output a corresponding message μ; otherwise, output a special symbol ⊥.cf⟵Evalevk,f,c1,…,cl: input the public evaluation key evk, a function f, and a sequence of ciphertexts c1,…,cl which are responding to the sequence of plaintexts μ1,…,μl; output a valid ciphertext cf responding to the message fμ1,…,μl.We say that a schemeΠ=Gen,Enc,Dec,Eval is fully homomorphic if it satisfies the following properties:Homomorphism: denote a class of all arithmetic circuits over GF2 as ℂ. If for arbitrary circuit f∈ℂ, the following inequation holds:(2)PrDecsk,Evalevk,f,c1,…,cl≠fμ1,…,μl=neglλ.Compactness: if there exists a polynomial p=polyλ, it holds that the output length of Eval is at most pλ bits without relation to the function f or the numbers of inputs.


### 3.3. Multikey Fully Homomorphic Encryption

Definition 5.
(multikey FHE). A multikey FHE is a tuple of algorithms (Setup, Keygen, Encrypt, Expand, Eval, Decrypt) described as follows:params⟵Setup1λ,1d: on the security parameter λ and the circuit depth d, the setup algorithm outputs the system parameters params. We assume that all the other algorithms take params as an input implicitly.sk,pk⟵Keygenparams: generate secret key sk and public key pk.c⟵Encryptpk,μ: take public key pk and a message μ as an input and output for a ciphertext c.c^⟵Expandpk1,…,pkN,i,c: on a sequence of N public keys and a fresh ciphertext c under the i−th key pki, it outputs an expanded ciphertext c^.c^:=Evalparams,C,c^1,…,c^l: given a Boolean circuit C of depth ≤d along with l expanded ciphertexts c^1,…,c^l, output an evaluated ciphertext c^.μ:=Decryptparams,sk1,…,skN,c^: take some ciphertext c^ and a sequence of N secret keys as an input and output a message μ.
The following properties hold:Semantic Security of Encryption. For any polynomial d=dλ and any two messages μ0,μ1, the distribution (params,pk, Encrypt(pk,μ0)) is computationally indistinguishable from the distribution (params,pk, Encryptpk,μ1), where params⟵Setup1λ,1d, sk,pk⟵Keygenparams.Correctness and Compactness. Let params⟵Setup1λ,1d. Consider any sequence of N correctly generated key pairs pki,ski⟵Keygenparamsi∈N and l−tuple of messages μ1,…,μl. For any sequence of indices I1,…,Il where each Ii∈N, let ci⟵EncryptpkIi,μii∈l be encryptions of the messages μi under the Ii−th public key and let c^i⟵Expandpk1,…,pkN,Ii,cii∈l be the corresponding expanded ciphertexts. Let C be any Boolean circuit of depth ≤d and let c^:=EvalC,c^1,…,c^l be the evaluated ciphertext. Then the following holds:Correctness of Expansion. ∀i∈l, Decryptsk1,…,skN,c^i=μi.Correctness of Evaluation. Decryptsk1,…,skN,c^=Cμ1,…,μl.Compactness. There exists a polynomial p⋅ such as c^≤pλ,d,N. In other words, the size of c^ should be independent of C and l but can depend on λ,d,N.


## 3.1. Learning with Errors, SIVP, and GapSVP

Regev firstly introduced the Learning with Errors (LWE) problem in 2005 and showed that the hardness of LWE can be reduced quantum to the lattice hard problems. Then, Peikert introduced an efficient classical reduction between LWE and the lattice intractable problems. The details are given below.Definition 1.
(Learning with Errors). Letλ be the security parameter, let n=nλ be an integer dimension of a lattice, let q=qλ≥2 be an integer, and let χ=χλ be an error distribution over ℤ.(i)
(Searchable LWE) Samples⟵ℤqn uniformly and then draw ai⟵ℤqn uniformly, ei⟵χ. Set bi=ai,s+ei. The searchable LWE is to find s, given m=mλ samples ai,bii=1m, called LWEn,m,q,χ.(ii)
(Decision LWE) The decision LWE, denoted asLWEn,q,χ, is to distinguish two distributions: The first one is a uniform distribution over ℤqn+1. The second is that one first samples s⟵ℤqn and then draws ai,bi∈ℤqn+1 by sampling ai⟵ℤqn uniformly, ei⟵χ, and setting bi=ai,si+ei.
The Learning with Errors (LWE) assumption is thatLWEn,m,q,χLWEn,q,χ is intractable.Definition 2.
SIVPγn. Let Λ be an n−dimension lattice. The SIVPγn problem is to output n linearly independent vectors v1,…,vn such that maxivi≤γn⋅λn, where λn=minrr:dimspanB0,r∩Λ≥n.Definition 3.
GapSVPγn. Let Λ be an n−dimension lattice and let d be a real number. GapSVPγn is to distinguish whether λ1<d or λ1≥γn⋅d, where λ1 is the length of the shortest vector in Λ.Definition 4.
(B-bounded distributions). A distribution ensembleχnn∈ℕ over the integers is called B-bounded distribution if(1)Pre⟵χne>B=negln.Theorem 1.
Letq=qn be either a prime power or a product of small (size poly(n)) distinct primes, B≥ωlogn⋅n, and χ is an efficient sampleable B-bounded distribution. If there exists an efficient algorithm solving the LWEn,q,χ problem, thenThere is an efficient quantum algorithm forGapSVPO˜nq/B on any n-dimension latticeThere is an efficient classical algorithm that solvesGapSVPO˜nq/B on any n-dimension lattice
In both cases, if one also considers solvingLWEn,q,χ with subpolynomial advantage, then request B≥O˜n and γn≥O˜n1.5q/B.


## 3.2. Fully Homomorphic Encryption

A fully homomorphic encryption is a tuple of algorithms (Gen, Enc, Dec, Eval) described as follows:pk,sk,evk⟵Gen1λ: on the security parameter λ, output a public key pk, a secret key sk, and a public evaluation key evk.c⟵Encpk,μ: encrypt a message μ from the plaintext space and output a ciphertext c.μ⟵Decsk,c: decrypt a valid ciphertext c and output a corresponding message μ; otherwise, output a special symbol ⊥.cf⟵Evalevk,f,c1,…,cl: input the public evaluation key evk, a function f, and a sequence of ciphertexts c1,…,cl which are responding to the sequence of plaintexts μ1,…,μl; output a valid ciphertext cf responding to the message fμ1,…,μl.We say that a schemeΠ=Gen,Enc,Dec,Eval is fully homomorphic if it satisfies the following properties:Homomorphism: denote a class of all arithmetic circuits over GF2 as ℂ. If for arbitrary circuit f∈ℂ, the following inequation holds:(2)PrDecsk,Evalevk,f,c1,…,cl≠fμ1,…,μl=neglλ.Compactness: if there exists a polynomial p=polyλ, it holds that the output length of Eval is at most pλ bits without relation to the function f or the numbers of inputs.


## 3.3. Multikey Fully Homomorphic Encryption

Definition 5.
(multikey FHE). A multikey FHE is a tuple of algorithms (Setup, Keygen, Encrypt, Expand, Eval, Decrypt) described as follows:params⟵Setup1λ,1d: on the security parameter λ and the circuit depth d, the setup algorithm outputs the system parameters params. We assume that all the other algorithms take params as an input implicitly.sk,pk⟵Keygenparams: generate secret key sk and public key pk.c⟵Encryptpk,μ: take public key pk and a message μ as an input and output for a ciphertext c.c^⟵Expandpk1,…,pkN,i,c: on a sequence of N public keys and a fresh ciphertext c under the i−th key pki, it outputs an expanded ciphertext c^.c^:=Evalparams,C,c^1,…,c^l: given a Boolean circuit C of depth ≤d along with l expanded ciphertexts c^1,…,c^l, output an evaluated ciphertext c^.μ:=Decryptparams,sk1,…,skN,c^: take some ciphertext c^ and a sequence of N secret keys as an input and output a message μ.
The following properties hold:Semantic Security of Encryption. For any polynomial d=dλ and any two messages μ0,μ1, the distribution (params,pk, Encrypt(pk,μ0)) is computationally indistinguishable from the distribution (params,pk, Encryptpk,μ1), where params⟵Setup1λ,1d, sk,pk⟵Keygenparams.Correctness and Compactness. Let params⟵Setup1λ,1d. Consider any sequence of N correctly generated key pairs pki,ski⟵Keygenparamsi∈N and l−tuple of messages μ1,…,μl. For any sequence of indices I1,…,Il where each Ii∈N, let ci⟵EncryptpkIi,μii∈l be encryptions of the messages μi under the Ii−th public key and let c^i⟵Expandpk1,…,pkN,Ii,cii∈l be the corresponding expanded ciphertexts. Let C be any Boolean circuit of depth ≤d and let c^:=EvalC,c^1,…,c^l be the evaluated ciphertext. Then the following holds:Correctness of Expansion. ∀i∈l, Decryptsk1,…,skN,c^i=μi.Correctness of Evaluation. Decryptsk1,…,skN,c^=Cμ1,…,μl.Compactness. There exists a polynomial p⋅ such as c^≤pλ,d,N. In other words, the size of c^ should be independent of C and l but can depend on λ,d,N.


## 4. A Scheme of Evaluation on Two-Key Ciphertexts for Any Polynomial

In this section, we formally describe our fully homomorphic encryption scheme. At the beginning, we introduce three operations used in the encryption algorithm for slow noise growth. Consider three vectorsa=a0,…,an−1∈ℤqn, α=α0,…,αN−1∈0,1N, and β=β0,…,βN−1∈ℤqN.BitDecompa=a0,0,a0,1,…,a0,l−1,a1,0,…,a1,l−1,…,an−1,l−1, where ai,j is the j-th element of the binary representation of ai.BitDecomp−1α=∑i=0l−12iαi,∑i=l2l−12i−lαi,…,∑i=n−1lN−12i−n−1lαi, where α∈0,1N.Flattenβ=BitDecompBitDecomp−1β.We can see thatBitDecomp⋅ expands each element of a vector to its binary representation, BitDecomp−1⋅ can be seen as the inverse operation of BitDecomp⋅, and it makes each l element of a vector to a number in ℤq. These three operations on a matrix are that they are performed on each column vector of the matrix. That is, BitDecompA=BitDecompA0⋮BitDecompAn−1. BitDecomp−1⋅ and Flatten⋅ on a matrix are similar to that.Our scheme consists of the following probabilistic polynomial time algorithms (Setup, Gen, Enc, Dec, Add, Mult, Add2, Mult2, and Dec2).Setup1λ,1L: let λ be the security parameter and let L be the max circuit depth. Choose appropriate LWE parameters: modulus q=qλ,L, lattice dimension n=nλ,L, and error distribution χ=χλ,L. Choose parameter m=Onlogq. Set params=q,n,χ,m. Let l=⌊logq⌋+1 and N=n×l.Genparams: choose randomly t⟵ℤqn−1. Choose a random matrix B⟵ℤqm×n−1 and a vector e⟵χm. Set b=B⋅t+e. Output the secret key sk=s=1,−t1,…,−tn−1∈ℤqn and the public key pk=A=b|B. Let v=Powerof2s (note that A⋅s=e.)Encparams,pk,μ: choose randomly a matrix R⟵0,1N×m. Then encrypt the message μ as follows:(3)C=Flattenμ⋅IN+BitDecompR⋅A∈ℤqN×N.Output the ciphertextC.Decparams,sk,C: let vi∈q/4,q/2. Output μ = └Ci,v/vi┐.Addparams,pk,C1,C2: to add two ciphertexts C1,C2∈ℤqN×N, output FlattenC1+C2.Multparams,pk,C1,C2: to multiply two ciphertexts C1,C2∈ℤqN×N, output FlattenC1⋅C2.Mult2params,pk1,pk2,C1,C2: these two keys are independently generated from the algorithm Gen () on the common parameters. If C1 is not encrypted under pk1 or C2 is not under pk2, then output ⊥. Otherwise, output C1,l−1⋅C2,l−1T.Add2params,pk1,pk2,C1,C2: if C1 is not encrypted under pk1 or C2 is not under pk2, then output ⊥. Otherwise, set C1′ and C2′ as encryptions of message 1 under pk1 and pk2, respectively, and output C1,l−1⋅C2,l−1′T+C1,l−1′⋅C2,l−1T.Dec2parmas,C,sk1,sk2: if C is an evaluated ciphertext from two ciphertexts under the public keys pk1 and pk2, respectively, then the first secret key sk1 holder computes tempc1=v1T⋅C and sends it to the sk2 holder. Similarly, the sk2 holder computes tempc2=C⋅v2 and sends it to the first holder. Then, the sk1 holder outputs v1T⋅tempc2 and the sk2 holder outputs tempc1⋅v2.The evaluation algorithmEval(⋅) that performs a depth-L circuit computations on polynomial GSW ciphertexts can be composed of Add and Multi operations.


## 5. Evaluation on Two-Key FHE Ciphertexts

### 5.1. Multiplication

Assume thatC1 is a GSW ciphertext of the message μ1 under the public key pk1 and C2 is that of μ2 under pk2. s1 and s2 are secret keys corresponding to pk1 and pk2, respectively. Set vi=Powerof2si, i=1,2. This function Powerof2() transforms a vector a0,…,an−1 into a new vector a0,2a0,…,2l−1a0,…,an−1,…,2l−1an−1, where l is the length of the binary representation of the modulus q.Mult2C1,C2=c1⋅c2T, where ci=Cil−1,⋅,i=1,2.Dec2v1,v2,C: Compute (└v1T⋅C/2l−1┐)T + c′, denoted as tc, where c′ is the l−1−th row of a ciphertext of a message 0 under the secret key v2 such that └(c′,v2/2l−1)┐. Output └tc,v2/2l−1┐.Theorem 2.
Suppose thatC1,C2 are ciphertexts under the secret keys v1,v2, respectively. If C is obtained from Mult2C1,C2 or Add2C1,C2, the probability of the decryption algorithm Dec2⋅ on inputs v1,v2,C running correctly is negligible. That is, there exists a negligible function negl⋅ on the security parameter λ, satisfying the following inequation:(4)PrDec2v1,v2,C≠μ1μ2pki,ski⟵GSW.Gen1λ,i=1,2;vi=Powerof2ski,i=1,2;μ1,μ2⟵0,1,Ci=GSW.Encpki,μi;C=Mult2C1,C2,≤neglλ.Proof.
Obviously,Ci⋅vi=μi⋅vi+ei,i=1,2. We also know that the first l elements of vi are 1,2,…,2l−1. Thus, we can decrypt the ciphertext Ci as μi = └Cil−1,⋅,vi/2l−1┐. Set ci=Cil−1,⋅ and ei=eil−1,i=1,2. So, ci,vi=μi⋅2l−1+ei. Running the first part of the decryption algorithm, we can obtain that tc = (└v1T⋅C/2l−1┐)T + c′ = (└v1T⋅c1⋅c2T/2l−1┐)T + c′= (└c2T⋅μ1⋅2l−1+ei/2l−1┐)T + c′ = μ1c2+c′. After the second part, we can get └tc,v2/2l−1┐ = └μ1c2,v2/2l−1+c′,v2/2l−1┐ = μ1μ2 That is to say, one-time multiplication on two ciphertexts under different secret keys only increases doubly the size of noise because the noise in the intermediate ciphertext tc can be viewed as that in an addition to two GSW ciphertexts under the same secret key. Therefore, the ciphertexts obtained from this multiplication algorithm can be decrypted correctly.
We can easily find that one-time multiplication causes a double increase of noise. Thus, scaling up the parameters or appending something auxiliary is undesired. We can directly perform one-time multiplication on two ciphertexts encrypted by two different keys without adjusting anything of the original GSW scheme.


### 5.2. Addition

We can achieve theAddition operation by using the operation Multiplication. That is, Add2C1,C2=Mult2C1,C¯2+Mult2C¯1,C2, where C¯i is a ciphertext of message 1 under the secret key vi, i=1,2.According to Theorem2, after one-time operation Multiplication on two ciphertexts under different secret keys, the noise increases doubly. Thus, one-time operation Addition causes the noise to increase quadruply, which is faster than that of Multiplication. It is not hard to find that the ciphertext C¯i is unnecessary to preserve the privacy of the plaintext, an exact number 1. Therefore, when constructing C¯i, we can set the randomness to zero. That is to say, C¯i is a special “ciphertext” of the plaintext 1 without noise. This change makes both the operations Addition and Multiplication have the same growth of the noise.Note that theAdd2 operation not only supports the input of two ciphertexts under different secret keys but also processes the input of one ciphertext obtained from the Add2 or Mult2 procedure and one ciphertext under a single key as well as the input of two former-type ciphertexts. The following are the details of the operation.Assume thatC′ is output by the Add2 or Mult2 procedure and C is a ciphertext under the secret key vb+1, where b⟵0,1. Then ADDC,C′=Mult2C,C¯+C′, where C¯ is a ciphertext of message 1 under the secret key vb¯+1.Assume thatC,C′ are both output by the Add2 or Mult2 procedure. Then, ADDC,C′=C+C′. It also can extend to the case of the input of polynomial ciphertexts from the Add2 or Mult2 procedure.


### 5.3. Evaluation of Any Polynomial Function

Assume thatf is an arbitrary polynomial function of u+v inputs, denoted as x1,…,xu,y1,…,yv and can be rewritten as fx1,…,yv=∑i=1wgix1,…,xufiy1,…,yv, where gi and fi are all L−bounded-depth circuits. Now, we have u+v ciphertexts denoted as C1,1,…,C1,u under the public key pk1 and C2,1,…,C2,v under the public key pk2. So,(5)Evalpk1,pk2,C1,1,…,C1,u,C2,1,…,C2,v,ℂf=∑i=1wMult2GSW.Evalpk1,C1,1,…,C1,u,ℂgi,GSW.Evalpk2,C2,1,…,C2,v,ℂfi=ADDMult2Cg1,Cf1,…,Mult2Cgw,Cfw,where Cgi=Evalpk1,C1,1,…,C1,u,gi and Cfi=Evalpk2,C2,1,…,C2,v,fi.Becausegi and fi are all L-bounded-depth circuits, Cgi and Cfi can be decrypted correctly by the secret keys sk1 and sk2, respectively. The operations Addition and Multiplication both cause the noise to increase linearly. Therefore, the output of the algorithm Eval can be decrypted correctly.


## 5.1. Multiplication

Assume thatC1 is a GSW ciphertext of the message μ1 under the public key pk1 and C2 is that of μ2 under pk2. s1 and s2 are secret keys corresponding to pk1 and pk2, respectively. Set vi=Powerof2si, i=1,2. This function Powerof2() transforms a vector a0,…,an−1 into a new vector a0,2a0,…,2l−1a0,…,an−1,…,2l−1an−1, where l is the length of the binary representation of the modulus q.Mult2C1,C2=c1⋅c2T, where ci=Cil−1,⋅,i=1,2.Dec2v1,v2,C: Compute (└v1T⋅C/2l−1┐)T + c′, denoted as tc, where c′ is the l−1−th row of a ciphertext of a message 0 under the secret key v2 such that └(c′,v2/2l−1)┐. Output └tc,v2/2l−1┐.Theorem 2.
Suppose thatC1,C2 are ciphertexts under the secret keys v1,v2, respectively. If C is obtained from Mult2C1,C2 or Add2C1,C2, the probability of the decryption algorithm Dec2⋅ on inputs v1,v2,C running correctly is negligible. That is, there exists a negligible function negl⋅ on the security parameter λ, satisfying the following inequation:(4)PrDec2v1,v2,C≠μ1μ2pki,ski⟵GSW.Gen1λ,i=1,2;vi=Powerof2ski,i=1,2;μ1,μ2⟵0,1,Ci=GSW.Encpki,μi;C=Mult2C1,C2,≤neglλ.Proof.
Obviously,Ci⋅vi=μi⋅vi+ei,i=1,2. We also know that the first l elements of vi are 1,2,…,2l−1. Thus, we can decrypt the ciphertext Ci as μi = └Cil−1,⋅,vi/2l−1┐. Set ci=Cil−1,⋅ and ei=eil−1,i=1,2. So, ci,vi=μi⋅2l−1+ei. Running the first part of the decryption algorithm, we can obtain that tc = (└v1T⋅C/2l−1┐)T + c′ = (└v1T⋅c1⋅c2T/2l−1┐)T + c′= (└c2T⋅μ1⋅2l−1+ei/2l−1┐)T + c′ = μ1c2+c′. After the second part, we can get └tc,v2/2l−1┐ = └μ1c2,v2/2l−1+c′,v2/2l−1┐ = μ1μ2 That is to say, one-time multiplication on two ciphertexts under different secret keys only increases doubly the size of noise because the noise in the intermediate ciphertext tc can be viewed as that in an addition to two GSW ciphertexts under the same secret key. Therefore, the ciphertexts obtained from this multiplication algorithm can be decrypted correctly.
We can easily find that one-time multiplication causes a double increase of noise. Thus, scaling up the parameters or appending something auxiliary is undesired. We can directly perform one-time multiplication on two ciphertexts encrypted by two different keys without adjusting anything of the original GSW scheme.


## 5.2. Addition

We can achieve theAddition operation by using the operation Multiplication. That is, Add2C1,C2=Mult2C1,C¯2+Mult2C¯1,C2, where C¯i is a ciphertext of message 1 under the secret key vi, i=1,2.According to Theorem2, after one-time operation Multiplication on two ciphertexts under different secret keys, the noise increases doubly. Thus, one-time operation Addition causes the noise to increase quadruply, which is faster than that of Multiplication. It is not hard to find that the ciphertext C¯i is unnecessary to preserve the privacy of the plaintext, an exact number 1. Therefore, when constructing C¯i, we can set the randomness to zero. That is to say, C¯i is a special “ciphertext” of the plaintext 1 without noise. This change makes both the operations Addition and Multiplication have the same growth of the noise.Note that theAdd2 operation not only supports the input of two ciphertexts under different secret keys but also processes the input of one ciphertext obtained from the Add2 or Mult2 procedure and one ciphertext under a single key as well as the input of two former-type ciphertexts. The following are the details of the operation.Assume thatC′ is output by the Add2 or Mult2 procedure and C is a ciphertext under the secret key vb+1, where b⟵0,1. Then ADDC,C′=Mult2C,C¯+C′, where C¯ is a ciphertext of message 1 under the secret key vb¯+1.Assume thatC,C′ are both output by the Add2 or Mult2 procedure. Then, ADDC,C′=C+C′. It also can extend to the case of the input of polynomial ciphertexts from the Add2 or Mult2 procedure.


## 5.3. Evaluation of Any Polynomial Function

Assume thatf is an arbitrary polynomial function of u+v inputs, denoted as x1,…,xu,y1,…,yv and can be rewritten as fx1,…,yv=∑i=1wgix1,…,xufiy1,…,yv, where gi and fi are all L−bounded-depth circuits. Now, we have u+v ciphertexts denoted as C1,1,…,C1,u under the public key pk1 and C2,1,…,C2,v under the public key pk2. So,(5)Evalpk1,pk2,C1,1,…,C1,u,C2,1,…,C2,v,ℂf=∑i=1wMult2GSW.Evalpk1,C1,1,…,C1,u,ℂgi,GSW.Evalpk2,C2,1,…,C2,v,ℂfi=ADDMult2Cg1,Cf1,…,Mult2Cgw,Cfw,where Cgi=Evalpk1,C1,1,…,C1,u,gi and Cfi=Evalpk2,C2,1,…,C2,v,fi.Becausegi and fi are all L-bounded-depth circuits, Cgi and Cfi can be decrypted correctly by the secret keys sk1 and sk2, respectively. The operations Addition and Multiplication both cause the noise to increase linearly. Therefore, the output of the algorithm Eval can be decrypted correctly.


## 6. Analysis

### 6.1. Correctness

Suppose thatC1 and C2 are GSW ciphertexts of the plaintexts μ1 and μ2 under the public keys pk1 and pk2, respectively, so that Ci⋅vi=μi⋅vi+smalli. These two ciphertexts are possibly fresh GSW ciphertexts and also can be evaluated ciphertexts through a circuit of the depth less than L. Also, a fresh GSW ciphertext has a B−bounded noise, namely, small∞≤B. The error is bounded by BN+1 after one homomorphic operation. So, Ci is a ciphertext with BN+1L−bounded noise. From the simple analysis in the front section, the noise in Mult2C1,C2 is bounded by 2BN+1L. Moreover, the noise in the addition of C1 and C2 increases linearly as the same as that of the Multiplication. So, finishing one-time homomorphic operation on two ciphertexts under different encryption keys, the noise grows up to 2BN+1L. We only discuss one multiplication operation on two ciphertexts under different keys and polynomial additions on two multiplied ciphertexts. Thus, we assume that there are polynomial additions w=polyλ,L. The final evaluated ciphertext is bounded 2wBN+1L. As long as this bound is less than q/8, we can decrypt the evaluated ciphertext correctly. We just set BN+1L≤1/4q/w. Then, it satisfies BN+1L≤q/8 so that GSW ciphertexts can be decrypted correctly. Also, 2BwN+1L≤q/8. We can decrypt correctly evaluated ciphertexts through quadratic computations on ciphertexts under two different keys. Now, we conclude this in the following theorem.Theorem 3.
Given the parameters, a modulusq, a lattice dimension n, a B−bounded distribution χ, and the max circuit-depth L, set N=n×⌊logq⌋+1. If BN+1L≤q/8, we can decrypt correctly a ciphertext from evaluating a depth-L circuit.Theorem 4.
Given the above parametersq,n,χ,B,L,N, and w, that is, the number of additions of a quadratic function, if BN+1L≤1/4q/w, we can decrypt a ciphertext, that is, from performing a quadratic computations on fresh GSW ciphertexts under two different keys or evaluated ciphertexts through a depth-L circuit under two different keys.


### 6.2. Security

The security of our scheme is dependent on that of the GSW scheme. The inputs of the evaluation algorithm are just the GSW-type ciphertexts, two public keys, and some common parameters without other information of private inputs. Thus, this process reveals no knowledge. In the process of the decryption, the output of the first part is indistinguishable with the uniform distribution because it adds a fresh ciphertext of message 0 and introduces a new noise in the intermediate result. So, we can conclude the following theorem.Theorem 5.
Assume that the GSW scheme is semantically secure, and so does our scheme. That is, if there exists a probabilistic polynomial time adversaryA which can distinguish the distribution of the ciphertext of the GSW scheme and the uniform distribution, we can construct another probabilistic polynomial time adversary ℬ which can distinguish the distribution of the ciphertext of our scheme and the uniform distribution.


## 6.1. Correctness

Suppose thatC1 and C2 are GSW ciphertexts of the plaintexts μ1 and μ2 under the public keys pk1 and pk2, respectively, so that Ci⋅vi=μi⋅vi+smalli. These two ciphertexts are possibly fresh GSW ciphertexts and also can be evaluated ciphertexts through a circuit of the depth less than L. Also, a fresh GSW ciphertext has a B−bounded noise, namely, small∞≤B. The error is bounded by BN+1 after one homomorphic operation. So, Ci is a ciphertext with BN+1L−bounded noise. From the simple analysis in the front section, the noise in Mult2C1,C2 is bounded by 2BN+1L. Moreover, the noise in the addition of C1 and C2 increases linearly as the same as that of the Multiplication. So, finishing one-time homomorphic operation on two ciphertexts under different encryption keys, the noise grows up to 2BN+1L. We only discuss one multiplication operation on two ciphertexts under different keys and polynomial additions on two multiplied ciphertexts. Thus, we assume that there are polynomial additions w=polyλ,L. The final evaluated ciphertext is bounded 2wBN+1L. As long as this bound is less than q/8, we can decrypt the evaluated ciphertext correctly. We just set BN+1L≤1/4q/w. Then, it satisfies BN+1L≤q/8 so that GSW ciphertexts can be decrypted correctly. Also, 2BwN+1L≤q/8. We can decrypt correctly evaluated ciphertexts through quadratic computations on ciphertexts under two different keys. Now, we conclude this in the following theorem.Theorem 3.
Given the parameters, a modulusq, a lattice dimension n, a B−bounded distribution χ, and the max circuit-depth L, set N=n×⌊logq⌋+1. If BN+1L≤q/8, we can decrypt correctly a ciphertext from evaluating a depth-L circuit.Theorem 4.
Given the above parametersq,n,χ,B,L,N, and w, that is, the number of additions of a quadratic function, if BN+1L≤1/4q/w, we can decrypt a ciphertext, that is, from performing a quadratic computations on fresh GSW ciphertexts under two different keys or evaluated ciphertexts through a depth-L circuit under two different keys.


## 6.2. Security

The security of our scheme is dependent on that of the GSW scheme. The inputs of the evaluation algorithm are just the GSW-type ciphertexts, two public keys, and some common parameters without other information of private inputs. Thus, this process reveals no knowledge. In the process of the decryption, the output of the first part is indistinguishable with the uniform distribution because it adds a fresh ciphertext of message 0 and introduces a new noise in the intermediate result. So, we can conclude the following theorem.Theorem 5.
Assume that the GSW scheme is semantically secure, and so does our scheme. That is, if there exists a probabilistic polynomial time adversaryA which can distinguish the distribution of the ciphertext of the GSW scheme and the uniform distribution, we can construct another probabilistic polynomial time adversary ℬ which can distinguish the distribution of the ciphertext of our scheme and the uniform distribution.


## 7. Conclusion

In this paper, we present an efficient algorithm of secure computation on ciphertexts under two different keys. In previous works, when evaluating multikey ciphertexts, the size of the ciphertext grows with the number of participants at a more or less linear rate. Although the size of the ciphertext remains invariant, it also provides auxiliary information of the plaintexts. We wanted to evaluate directly on the GSW ciphertexts from two parties without any auxiliary information or interaction between them. We designed a scheme in which one can directly perform any polynomial function on the GSW ciphertexts under two different keys.



---

*Source: 6695304-2021-02-22.xml*