Abstract
We construct a simple public-key encryption scheme that supports polynomially many additions and one multiplication, similarly to the cryptosystem of Boneh, Goh, and Nissim (BGN). Security is based on the hardness of learning with errors (LWE), which is known to be as hard as certain worst-case lattice problems.
Abstract
Some features of our cryptosystem include support for large message space, an easy way of achieving formula-privacy, and a better message-to-ciphertext expansion ratio than BGN. Also, it offers an easy way of multiplying two encrypted polynomials.
Introduction
In this work we describe a variation of the Gentry-Peikert-Vaikuntanathan cryptosystem [GPV08] (GPV) that is not only additively homomorphic but also supports one multiplication. Recall that the public key in GPV is a matrix A ∈ Z m×n q (for m > n) and the corresponding trapdoor is a full rank integer matrix with small entries T ∈ Z m×m such that TA = 0 (mod q). The public and secret keys in our cryptosystem are the same as in GPV. We encrypt a square binary matrix B ∈ Z m×m 2 by setting C = AS + 2X + B mod q where S is a random matrix S ∈ Z n×m q and X is a "noise matrix" with small entries X ∈ Z m×m . Ciphertext matrices can be added, and a single matrix multiplication C = C 1 · C t 2 mod q is also supported. (C t is the transpose of C.) To decrypt, we set
Introduction
The security of our scheme is equivalent to the hardness of learning with errors (LWE). This problem, which is related to the well-known "learning parity with noise", has become standard in the study of lattice-based cryptography. The problem was first proposed by Regev [Reg05a] , and shown by Regev [Reg05a] and Peikert [Pei09] to be as hard as worst-case instances of various problems in integer lattices.
An Abridged History of Homomorphic Encryption
Encryption schemes that support operations on encrypted data (aka homomorphic encryption) are very useful for secure computation. Many public-key cryptosystems supports either addition or multiplication of encrypted data, but obtaining both at the same time seems harder.
An Abridged History of Homomorphic Encryption
It is known that computing arbitrary functions on encrypted data can be implemented, e.g., using Yao's "garbled circuit" technique [Yao82, LP09] , but the size of the ciphertext grows at least linearly with the number of gates in the circuit being computed. Also, Sander et al. [SYY99] described a technique that permits evaluation of arbitrary circuits, but the ciphertext size grows exponentially with the circuit depth. Both of these methods can be implemented using only "general hardness assumptions" (e.g., the existence of two-flow Oblivious-Transfer protocols etc. ) Boneh, Goh, and Nissim described a cryptosystem that permitted arbitrary number of additions and one multiplication, without growing the ciphertext size [BGN05] . Below we refer to this scheme as the BGN cryptosystem. Security of the BGN cryptosystem is based on the subgroup-membership problem in composite-order groups that admit bilinear maps. This cryptosystem immediately implies an efficient protocol for evaluating 2DNF formula (or more generally bilinear forms). Boneh et al. also described applications of the BGN cryptosystem to improving the efficiency of private information retrieval schemes (PIR) and for a voting protocol.
An Abridged History of Homomorphic Encryption
More recently, Melchor, Gaborit, and Herranz described in [MGH08] a "template" for converting additively homomorphic encryption into a cryptosystem that permits both additions and multiplications. They show how to use this template to combine the BGN cryptosystem with the cryptosystem of Kawachi et al. [KTX07] , thus obtaining a cryptosystem that supports two multiplications and arbitrary additions, based on the hardness of both the subgroup membership problem and the unique-shortest vector problem in lattices. They also show how to use this template with the cryptosystem of Melchor et al. [AMCG08] in order to obtain unlimited multiplication depth, where the ciphertext size grows exponentially with the multiplication depth but additions are supported without increasing the size. (Security of this last realization is based on a relatively unstudied hardness assumption, called the "Differential Knapsack Vector Problem.") Very recently, Gentry described a fully homomorphic cryptosystem [Gen09b] , supporting polynomially many additions and multiplications without increasing the ciphertext size, with security based on the hardness of finding short vectors in ideal lattices [Gen09a] .
Our Contributions
Even given the great advances in homomorphic encryption over the last year, our scheme still offers some advantages over the prior scheme in the literature. Below we list some of these advantages, mostly in comparison to the BGN cryptosystem.
Our Contributions
Perhaps the main difference between our scheme and previous work is the underlying hardness assumption. In particular, ours is the first reported cryptosystem based on LWE that has more than just additive homomorphism. Also, our scheme is very efficient: it can encrypt a matrix of m 2 elements in timeÕ(m 3 ), and decryption takes comparable time.
Our Contributions
One important difference between our scheme and the BGN cryptosystem is that the BGN cryptosystem can only encrypt messages from a small space (since on decryption one only recovers a group element g m , and then need to search for the message m). In our scheme, we can replace the binary matrices by matrices over Z p for any p, as long as the ciphertext is defined over Z q where q is sufficiently larger than p. A related advantage is that by choosing a large modulus p, our scheme can be made to have ciphertext expansion of O(1) (whereas the BGN cryptosystem expands O(log n) bits of plaintext to O(n) ciphertext bits.) 1 We also note that the modulus p that defines the message space in our scheme can be chosen dynamically by the encryptor: the same public/secret key pair can be used to encrypt/decrypt messages modulo many different fields (or rings). Our scheme also support ciphertext blinding (a given ciphertext is converted into a random ciphertext that encrypts the same thing), and also the stronger property of modular blinding: Given a ciphertext that encrypts a matrix B ∈ Z m×n p , and given some divisor p of p, we can produce a random ciphertext that encrypts B mod p . For example, if the original plaintext matrix had numbers in Z 2 n , we can blind the ciphertext so as to erase all but the least-significant bits of the entries in B.
Our Contributions
One consequence of the (standard) blinding property and the flexibility of choosing the message space is that our system provide a very simple procedure for formula-private secure computation. Namely, it is very easy to compute a 2DNF formulas (or a general bilinear form) on ciphertexts, while at the same time hiding from the holder of the secret key everything about the formula itself (other than the result of applying it on the given inputs).
Our Contributions
Relation to the MGH transformation. It turns out that our cryptosystem fits "right out of the box" in the template of Melchor, Gaborit, and Herranz [MGH08] . Their transformation apply to any additively homomorphic cryptosystem for which you can embed the ciphertexts back into the plaintext space while maintaining the semantics of addition, which is easy in our case. See the appendix for a brief description of their transformation and how it applies to our cryptosystem.
Our Contributions
Combining our cryptosystem with the MGH transformation yields a homomorphic encryption scheme for circuits of logarithmic multiplication depth (with arbitrary additions), whose security is based on the hardness of LWE. 2 We point out that even in this context, using our native multiplication operation will be advantageous, since it does not increase the ciphertext size (or the decryption time). Thus we can get either one more multiplication level for a given complexity bound, or a more efficient scheme for the same circuit depth.
Our Contributions
Applications. Clearly, our scheme can be used as a drop-in replacement in the applications to voting and PIR that were discussed in the paper of Boneh et al. [BGN05] . In addition, since out scheme encrypts matrices natively, it is a good match for applications that can benefit from batching, or when efficient linear algebra is important. Some examples of batching include applications that need to multiply polynomials (whose coefficients are to be encoded in the entries of the plaintext matrix) or large integers (whose bit representation is to be encoded in the entries of the plaintext matrix). In Section 5.3 we describe how these can be encoded in a matrix so that a single multiplication of m × m matrices can be used to multiply two degree-(m − 1) polynomials (or two m-bit integers), so that the result does not leak anything about the inputs other than their product.
Preliminaries
Notations. We denote scalars by lower-case letters (a, b, . . .), vectors by lower-case bold letters (a, b, . . .), and matrices by upper-case bold letters (A, B, . . .). We denote the Euclidean norm of a vector v by v , and the largest entry in a vector or a matrix is denoted v ∞ or M ∞ , respectively. We consider the operation (a mod q) as mapping the integer a into the interval (−q/2, +q/2].
Learning with errors (LWE)
The LWE problem was introduced by Regev [Reg05b] as a generalization of "learning parity with noise". For positive integers n and q ≥ 2, a vector s ∈ Z n q , and a probability distribution χ on Z q , let A s,χ be the distribution obtained by choosing a vector a ∈ Z n q uniformly at random and a noise term x ← χ, and outputting (a, a, s + x) ∈ Z n q × Z q .
Learning with errors (LWE)
Definition 1 (LWE) For an integer q = q(n) and an error distribution χ = χ(n) over Z q , the learning with errors problem LWE n,m,q,χ is defined as follows: Given m independent samples from A s,χ (for some s ∈ Z n q ), output s with noticeable probability. The decision variant of the LWE problem, denoted distLWE n,m,q,χ , is to distinguish (with nonnegligible advantage) m samples chosen according to A s,χ (for uniformly random s ∈ R Z n q ), from m samples chosen according to the uniform distribution over Z n q × Z q .
Learning with errors (LWE)
For cryptographic applications we are primarily interested in the decision problem distLWE. Regev [Reg05b] showed that for a prime modulus q, distLWE can be reduced to worst-case LWE, with a loss of up to a q · poly(n) factor in the parameter m.
Learning with errors (LWE)
At times, we find it convenient to describe the LWE problem LWE n,m,q,χ using a compact matrix notation: given (A, As + x) where A ← Z m×n q is uniformly random, s ← Z n q is the LWE secret, and x ← χ m , find s. We also use similar matrix notation for the decision version distLWE.
Learning with errors (LWE)
Gaussian error distributions Ψ β . We are primarily interested in the LWE and distLWE problems where the error distribution χ over Z q is derived from a Gaussian. For any β > 0, the density function of a Gaussian distribution over the reals is give by D β (x) = 1/β · exp(−π(x/β) 2 ). For an integer q ≥ 2, define Ψ β (q) to be the distribution on Z q obtained by drawing y ← D β and outputting q · y (mod q). We write LWE n,m,q,β as an abbreviation for LWE n,m,q,Ψ β (q) .
Learning with errors (LWE)
Here we state some basic facts about Gaussians (tailored to the error distribution Ψ β ); see, e.g. [Fel68] . (In what follows overwhelming probability means probability 1 − δ for δ which is negligible in n.)
Learning with errors (LWE)
Fact 1 Let β > 0 and q ∈ Z, and let the vector x be chosen as x ← Ψ β (q) n . Also let y ∈ Z n be an arbitrary vector and let g = ω( √ log n). Then with overwhelming probability | x, y | ≤ βq · g · y .
Learning with errors (LWE)
Fact 2 Let y ∈ R be arbitrary. The statistical distance between the distributions Ψ β and Ψ β + y is at most |y|/(βq).
Learning with errors (LWE)
Evidence for the hardness of LWE n,m,q,β follows from results of Regev [Reg05b] , who gave a quantum reduction from approximating certain problems on n-dimensional lattices in the worst case to within O(n/β) factors to solving LWE n,m,q,β for any desired m = poly(n), when β · q ≥ 2 √ n. Recently, Peikert [Pei09] also gave a related classical reduction for some other problems with similar parameters.
Trapdoor sampling
The basis of our encryption scheme is a trapdoor sampling algorithm first constructed by Ajtai [Ajt99] , and later improved by Alwen and Peikert [AP09] . The trapdoor sampling procedure generates an (almost) uniformly random matrix A ∈ Z m×n q , together with a matrix T ∈ Z m×m such that (a) T · A = 0 (mod q), (b) T is invertible, and (c) the entries of T are small (say, of size O(n log q)).
Trapdoor sampling
The trapdoor T can be used to solve the LWE problem relative to A, i.e., given y = As + x where x is any "sufficiently short" vector, it can be used to recover s. This is done as follows: compute
Trapdoor sampling
where the last equality follows since the rows of T belong to lattice Λ ⊥ (A). Now, since both T and x contain small entries, each entry of the vector Tx is smaller than q, and thus Tx mod q is Tx itself! Finally, multiplying by T −1 (which is well-defined since T is a basis and therefore has full rank) gives us x. The LWE secret s can then be recovered by Gaussian elimination. We state the result of Alwen and Peikert [AP09] below.
Trapdoor sampling
There is a probabilistic polynomial-time algorithm TrapSamp that, on input 1 n , a positive integer q ≥ 2, and a poly(n)-bounded positive integer m ≥ 8n log q, outputs matrices A ∈ Z m×n q and T ∈ Z m×m such that:
Trapdoor sampling
• A is statistically close to uniform over Z m×n q ,
Trapdoor sampling
• the rows of T form a basis of the lattice
Trapdoor sampling
• the Euclidean norm of all the rows is T (and therefore also T ∞ ) is bounded by O(n log q).
(Alwen and Peikert assert that the constant hidden in the O(·) is no more than 20.)
We note that since the rows of T span the lattice Λ ⊥ (A), it follows that det(T) = q n , hence for odd q we know that T is invertible mod 2.
The Encryption Scheme
For ease of presentation, we focus below on the case of encrypting binary matrices. The extension for encrypting matrices mod p for p > 2 is straightforward, and is discussed in Section 5.1. Below we let n denote the security parameter. Other parameters of the system are two numbers m, q = poly(n) (with q an odd prime), and a Gaussian error parameter β = 1/poly(n). (See Section 3.2 for concrete instantiations of these parameters.) For these parameters, the message space is the set of binary m-by-m matrices, i.e., B ∈ Z Dec(T, C): Set E ← TCT t mod q, and then output the matrix B ← T −1 E(T t ) −1 mod 2.
The Encryption Scheme
To see that decryption works, recall that T·A = 0 (mod q) and therefore TCT t = T(2X+B)T t (mod q). If in addition all the entries of T(2X + B)T t are smaller than q then we also have the equality over the integers E = (TCT t mod q) = T(2X + B)T t , and hence T −1 E(T t ) −1 = B (mod 2). This means that we have correct decryption as long as we set the parameter β small enough so that with high probability all the entries of T(2X + B)T t are smaller than q/2.
The Encryption Scheme
Remark 1 Note that the right-multiplication by T t and (T t ) −1 on decryption are redundant here, we can instead just compute B ← T −1 (TC mod q) mod 2. The right-multiplication is needed to decrypt product ciphertexts, as described below. As opposed to the BGN cryptosystem, in our scheme the "normal ciphertexts" and "product ciphertexts" live in the same space, and we can use the same decryption procedure to decrypt both.
The Encryption Scheme
Also, we can optimize away the need to multiply by T −1 and (T t ) −1 by using the modified trapdoor T = (T −1 mod 2) · T (product over the integers). Clearly we have T A = 0 (mod q), and the entries of T are not much larger than those of T (since (T −1 mod 2) is a 0-1 matrix).
Homomorphic operations
Addition. Given two ciphertexts C 1 , C 2 that decrypt to B 1 , B 2 , respectively, it is easy to see that the matrix C = C 1 + C 2 mod q would be decrypted to B 1 + B 2 mod 2, as long as there is no "overflow" in any entry. Specifically, if we have C 1 = AS 1 + 2X 1 + B 1 and
Homomorphic operations
which would be decrypted as B 1 + B 2 as long as all the entries in T(2(X 1 + X 2 ) + B 1 + B 2 )T t are smaller than q/2. See Section 3.2 for the exact parameters.
Homomorphic operations
Multiplication. Given two ciphertexts C 1 , C 2 that encrypt B 1 , B 2 , respectively, we compute the product ciphertext as C = C 1 ·C t 2 mod q. If we have C 1 = AS 1 +2X 1 +B 1 and C 2 = AS 2 +2X 2 +B 2 then
Homomorphic operations
Hence the product ciphertext has the form AS + 2X + B + S A t . As before, we see that TCT t = T(2X + B)T t (mod q), and if all the entries of T(2X + B)T t are smaller than q/2 then we have E = (TCT t mod q) = T(2X + B)T t over the integers, and therefore T −1 E(T t ) −1 = B (mod 2). Below we establish the parameters that we need for this to work.
Setting the parameters
Theorem 2 Fix the security parameter n and any c = c(n) > 0. Let q, m, β be set as q > 2 20 (c + 4) 3 n 3c+4 log 5 n, q is a prime m = 8n log q β = 1 27n 1+(3c/2) log n log q √ qm
Setting the parameters
Then the encryption scheme from above with parameters n, m, q, β supports n c additions and one multiplication (in any order) over the matrix ring Z m×m 2
Setting the parameters
.
Setting the parameters
Remark 2 Note that in Theorem 2 we can allow n c additions for a non-constant c. The reason that this may be needed is for taking linear combinations of ciphertexts with large coefficients. Specifically, if we have ciphertext matrices C 1 , C 2 , . . ., we can homomorphically compute α i C i as long as | α i | < n c .
Setting the parameters
Proof First, let C be a matrix that was obtained by adding ≤ n c ciphertexts,
Setting the parameters
, and we analyze the size of the entries in the matrix T(2X + B). Recall from Lemma 1 that every row of T has Euclidean norm at most 20n log q. Applying Fact 1 (with g = log n − 1), with overwhelming probability every entry of TX i is at most 20βq(log n − 1)n log q, hence every entry of TX is at most 20 βq(log n − 1)n log q. At the same time, all the B i 's are binary so each entry of TB is at most 20 n log q. Hence the absolute value of each entry in T(2X + B) is bounded by 20 n log q · (2βq(log n − 1) + 1) < 20 n log q · 2βq log n = 40 · n log n · q log q 27n 1+(3c/2) log n · log q √ qm
Setting the parameters
where inequality ( ) uses the fact that ≤ n c . This in particular means that each entry in T(2X + B)T t is bounded by m · 20n log q · q/m = 20n log q √ qm q/2. Since TA = 0 (mod q) then TCT t = T(2X + B)T t (mod q), and as all the entries in T(2X + B) are less than q/2 in absolute value, we have the equality over the integers (TCT t mod q) = T(2X + B)T t , hence T −1 (TCT t mod q)(T t ) −1 = B (mod 2).
Setting the parameters
Next, consider a circuit with one 1 -fan-in addition layer, followed by a multiplication layer of fan-in two, and another 2 -fan-in layer of addition, where 1 + 2 ≤ n c . We have shown above that when multiplying two matrices of the form AS i + 2X i + B i (i = 1, 2), the result is of the form AS + 2X + B + S A t . Hence all the matrices at the output of the multiplication layer are of this form, and therefore so is the output ciphertext that results from adding them all together. We now proceed to show that for that final ciphertext C = AS + 2X + B + S A t , it holds that every entry in T(2X + B)T t is less that q/2 in absolute value.
Setting the parameters
Consider one particular ciphertext at the output of the multiplication layer, this ciphertext is of the form C i = AS + (2X 1 + B 1 )(2X t 2 + B t 2 ) + S A t , and the matrices (2X i + B i ) were obtained from adding upto 1 encryptions. By the analysis from above, each entry in T(2X 1 + B 1 ) is bounded by
Setting the parameters
, and the same bound apply also to each entry in (2X t 2 + B t 2 )T t . Hence each entry in the product T(2X 1 + B 1 )(2X t 2 + B t 2 )T t is bounded by
Setting the parameters
Adding 2 ≤ n c − 1 such matrices, the entry in the result is bounded by 40 27
Setting the parameters
where the inequality ( ) follows since the function f (x) = x 2 (a − x) obtains its maximum at x = 2a/3, where f (x) = 2a 3 /9. Once again, since each entry in T(2X + B)T t is less than q/2 in absolute value, and since TCT t = T(2X + B)T t (mod q), we have the equality over the integers (TCT t mod q) = T(2X + B)T t , which in turn means that T −1 (TCT t mod q)(T t ) −1 = B (mod 2).
Security
The CPA security of the encryption scheme follows directly from the hardness of the decision LWE problem, as we now prove.
Security
Theorem 3 Any distinguishing algorithm with advantage against the CPA security of the scheme with parameters n, m, q, β, can be converted to a distinguisher against distLWE n,m,q,β with roughly the same running time and advantage at least /2m.
Security
Proof Let A be a CPA-adversary that distinguishes between encryptions of messages of its choice with advantage . We first construct a distinguisher D with advantage at least /2 between the two distributions
Security
The distinguisher D takes as input a pair of matrices (A ∈ Z m×n q , C ∈ Z m×m q ), and runs the adversary A with A as the public key. Upon receiving message B 0 , B 1 from the adversary, D chooses at random i ∈ R {0, 1}, returns the challenge ciphertext 2C + B i mod q, then outputs 1 if the adversary A guesses the right i, and 0 otherwise.
Security
On the one hand, if C is a uniformly random matrix then the challenge ciphertext is also uniformly random, regardless of the choice of i. Hence in this case D outputs 1 with probability at most 1/2. On the other hand, if C = AS + X mod q, then the challenge ciphertext is 2C + B = AS + 2X + B mod q, where S = 2S mod q is uniformly distributed (since q and 2 are relatively prime). This is identical to the output distribution of Enc(P K, B i ), hence by assumption A will guess the right i with probability (1+ )/2, which means that D outputs 1 with the same probability. Hence D has advantage at least /2.
Security
Finally, a standard hybrid argument can be used to convert the distinguisher D from above to a distLWE n,m,q,β distinguisher with advantage /2m.
Security
Worst-case Connection. Regev [Reg05b] showed that if there is a PPT algorithm that solves distLWE n,m,q,β , then there is an O(q · m)-time quantum algorithm that approximates various lattice problems on n-dimensional lattices in the worst case to within O(n/β) factors, when β · q ≥ 2 √ n. Recently, Peikert [Pei09] also gave a related classical reduction with similar parameters.
Security
Observe that for n ≥ max{140, 10 √ c + 4}, the conditions on q, m, β imply that βq > 2 √ n. Plugging in our parameters m, q and β for the scheme that supports n c additions, we get that breaking semantic security of the scheme is at least as hard as solving worst-case lattice problems to within a factor ofÕ(n 3c+7/2 ).
Extensions and Applications

Encrypting matrices over larger rings
As we said in the introduction, we can use the same scheme to encrypt matrices over larger rings and still enjoy the same homomorphic properties, just by working with a larger modulus q. Specifically, we can encrypt matrices over Z p for any p by setting q = ω(p 2 n 3c+1 log 5 n) while keeping all the other parameters intact. We then encrypt a matrix B ∈ Z m×m p as C = AS + pX + B, and decrypt it as T −1 · (TCT t mod q) · (T t ) −1 mod p. (We recall again that the determinant of T is q n , so T is invertible mod p.) Using the above with p ≥ n 3c+1 log 5 n, we have q ≤ p 3 which means that our ciphertext expansion ratio is only three. (The plaintext has m 2 log p bits while the ciphertext has m 2 log q bits.)
Encrypting matrices over larger rings
We comment that once we fix these larger parameters, the choice of the underlying ring can be made adaptively by the encryptor. Namely, with the same public key A and secret key T, the encryptor can choose the underlying ring as Z r for any r ≤ p (thereby computing the ciphertext as C = AS + rX + B), and the decryptor can decrypt accordingly.
Formula Privacy
As described so far, the scheme does not ensure "formula privacy" against the holder of the secret key. For example, given a ciphertext matrix C, the decryptor may be able to distinguish the case where this ciphertext was obtained by multiplying an encryption of the identity with an encryption of the zero matrix from the case where it was obtained by multiplying two encryptions of the zero matrix.
Formula Privacy
This deficiency can be remedied by standard techniques. We first need to increase the size of the modulus somewhat: switching from q as specified in Theorem 2 to q ≥ q · 2 ω(log n) . Then given a ciphertext matrix C * , encrypting some plaintext matrix mod p, we blind it by setting
Formula Privacy
where S, S are uniform in Z n×m q and each entry of X * is chosen from Ψ β (q) with β superpolynomially larger than the parameter β that is used in the scheme. Using Fact 2 we can then show that the noise in the added X * "drowns" all traces of the origin of this ciphertext. Namely, the resulting ciphertext is of the form C = AS 1 + pX + B + (S 2 ) t A t , where S 1 , S 2 are uniformly random, B is the corresponding plaintext, and the distribution of X is nearly independent of the provenance of this ciphertext matrix.
Formula Privacy
We note that the same blinding technique can be used even if the encrypted plaintext matrix was chosen in a larger ring Z p , as long as the parameter p that is used in the blinding procedure divides the original p .
Encrypting polynomials and large integers
To encrypt polynomials or large numbers, we need to encode them as matrices, in a way that would let us exploit the matrix operations that are supported natively by our scheme to do operations over the these polynomials or numbers.
Encrypting polynomials and large integers
We begin with polynomials: it is well known how to embed the coefficients of two polynomials in two matrices, so that multiplying these matrices we get all the coefficients of the resulting product polynomial. For example, for two polynomialsâ(x) = a i x i andb(x) = b i x i , we can use
Encrypting polynomials and large integers
Note that the product matrix above is not private, in that it reveals more than just the coefficients of the product polynomial. This can be fixed easily by adding an encryption of a matrix with zero first column and first row and random entries everywhere else. Also, this simple embedding is "wasteful" in that it results in ciphertext expansion ratio of O(m) (we encrypt degree-(m − 1) polynomials using m × m matrices). We do not know if more economical embeddings are possible. Moving to integer multiplication, an obvious way of multiplying two m-bit integers is to just set the plaintext space to Z p for some p ≥ 2 2m , but working with such large plaintext space may be inconvenient. We thus seek a method for implementing large integer multiplication with a small input space. One possibility is to use the same technique as we did for polynomials, viewing the integer with binary representation a = a i 2 i as a binary polynomialâ(x) evaluated at x = 2. Given two integers a, b, we encrypt the binary coefficients of the corresponding polynomialsâ,b over plaintext space Z p for some p ≥ m. Reading out the coefficients of the product polynomial, we then compute a · b = (â ·b)(2) over the integers.
Encrypting polynomials and large integers
This solution is not private however, it leaks more information about a, b than just their integer product. One approach for making it private is to add random elements r i ∈ Z p to the first row and column of the product matrix such that i 2 i r i = 0 (mod p). This will make it possible for the secret key holder to recover a · b (mod p). Repeating it several times with different p's, we can then use Chinese remaindering to recover a · b completely.
Two-out-of-two decryption
We point out a peculiar property of our cryptosystem, which so far we were not able to find applications for. Namely, if we have encryptions of two matrices under two different public keys, we can multiply these two ciphertexts, thus obtaining an "ciphertext" corresponding to the product of the two plaintext matrices". This "ciphertext" can then be decrypted by pulling together the two secret keys.
Two-out-of-two decryption
In more details, suppose that we have two public keys A 1 , A 2 and the corresponding two secret keys T 1 , T 2 , with both pairs defined modulo the same prime number q. (We also assume for simplicity that both pairs use the same parameters n and m, but this assumption is not really needed). Then, given two ciphertexts
Two-out-of-two decryption
we can compute the "product ciphertext" C = C 1 C t 2 (mod q), corresponding to the plaintext B 1 B t 2 (mod 2). This plaintext can be recovered if we know both T 1 and T 2 , by setting To evaluate d-degree binary polynomials with upto m terms, we need an encryption scheme E = (KeyGen, Enc, Dec) with message space Z p for p ≥ m + 1, that satisfies the following properties:
Two-out-of-two decryption
• The ciphertext is a vector of integers in [0, q − 1] (for some parameter q), which we denote by Greek letters,
Two-out-of-two decryption
(We identify Z q with the set of integers in [0, q − 1].) Denote the bit-length of the parameter q by t def = log(q + 1) , so the total size of the ciphertext is nt bits. (Note that to support message space Z p for p > m, we need nt ≥ Ω(κ + log m) for security parameter κ.)
Two-out-of-two decryption
• E is additively homomorphic, via mod-q addition of the ciphertext vectors. Specifically, what we need is that for any m ≤ m plaintext bits a 1 , . . . , a m ∈ {0, 1} and their encryption α j ← Enc(a j ), the vector α = j α j mod q whole elements are integers in [0, q − 1], is decrypted (with probability one) to the integer j a j . (Note that since m < p and all the a j 's are bits, then the sum of the a j 's is less than p, and hence addition modulo p is the same as the sum over the integers.)
Two-out-of-two decryption
Consider now a vector of m triples of plaintext bits (a 1 , b 1 , c 1 ) , . . . , (a m , b m , c m ) ∈ ({0, 1} 3 ) m , and their encryption α j ← Enc(a j ), β j ← Enc(b j ), γ j ← Enc(c j ). We now show how to generate a "ciphertext" of size (nt) 3 that can be decrypted to the bit Recall that these are all non-negative t-bit integers, and we denote their bit representations by
Two-out-of-two decryption
where each β 
Two-out-of-two decryption
In other words, each vector δ (i,k,i ,k ) is computed as a subset-sum (over Z q ) of the m ciphertext vectors α j . Since we have (nt) 2 such vectors, the total size of the compound ciphertext is (nt) 3 , as claimed.
Two-out-of-two decryption
1. For all k, k , i, i decrypt δ (i,k,i ,k ) to get an integer λ (i,k,i ,k ) ← Dec δ (i,k,i ,k ) . Due to the additive homomorphism of the underlying scheme, we have that
Two-out-of-two decryption
bit (equality over the integers)
Two-out-of-two decryption
Note that this equality is over the integers since this is a sum of m bits, and hence must be less than p.
Two-out-of-two decryption
2. For all k , i, i compute the integer λ (i ,k ) [i] ← t−1 k=0 2 k · λ (i,k,i ,k ) mod q. By construction we have λ (i ,k ) [i] ∈ Z q , and by changing the order of summation we see that
Two-out-of-two decryption
3. For all k , i denote
Two-out-of-two decryption
Again, each λ (i ,k ) is equal to a subset-sum over Z q of the β j ciphertext vectors.
Two-out-of-two decryption
4. For all k , i decrypt λ (i ,k ) to get an integer µ (i ,k ) ← Dec λ (i ,k ) . As before, due to the additive homomorphism of the underlying scheme we have that . Decrypt µ to get the integer ν ← Dec( µ), and once again due to the additive homomorphism we have the equality ν = j a j b j c j holding over the integers. Finally output (ν mod 2) as the decrypted bit.

{'paper_id': '7050945', 'title': 'A Simple BGN-type Cryptosystem from LWE', 's2_url': 'https://api.semanticscholar.org/CorpusID:7050945', 'source': 'S2ORC'}