# Compressible Multikey and Multi-Identity Fully Homomorphic Encryption

Authors: Tongchen Shen; Fuqun Wang; Kefei Chen; Zhonghua Shen; Renjun Zhang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

With the development of new computing models such as cloud computing, user’s data are at the risk of being leaked. Fully homomorphic encryption (FHE) provides a possible way to fundamentally solve the problem. It enables a third party who does not know anything about the secret key and plaintexts to homomorphically perform any computable functions on the corresponding ciphertexts. In 2009, Gentry proposed the first FHE scheme. After that, its inefficiency has always been a bottleneck of the development of practical schemes and applications. At TCC 2019, Gentry and Halevi proposed the first compressible FHE scheme that enables the ratio of plaintext size to the ciphertext size (i.e., the compression rate) to reach1−ε for any small ε>0 under the standard learning with errors (LWE) assumption. However, it is only a single-key one, where the homomorphic evaluation can only be performed over ciphertexts encrypted under the same key. Compared with single-key FHE, multikey FHE is more practical. Multikey FHE enables ciphertexts encrypted under different public keys to be homomorphically computed without having to decrypt these ciphertexts using their own private keys. In addition, in a multi-identity FHE scheme, only identity information and public parameters are required when encrypting, which simplifies certificate-based key management in public key infrastructure. In this paper, a new compressible ciphertext expansion technique is proposed. Then, we use this technique to construct a compressible multikey FHE scheme and a compressible multi-identity FHE scheme to overcome the bottleneck of bandwidth inefficiency in the multikey and multi-identity settings. The two schemes proposed in this paper make it possible that the objects of homomorphic operation can be the ciphertexts encrypted under different keys or different identities before compression, thus solving the single-key defect of the work of Gentry and Halevi.


---

## Body

## 1. Introduction

We are quickly entering a new digital era where huge amounts of data will be stored and operated remotely in powerful cloud servers. Cloud computing is a popular option for people and businesses for a number of reasons including cost savings, increased productivity, and performance. With all of these advantages, however, it also raises grave security issues and challenges. User’s sensitive information, such as medical data and organizational secrets, is vulnerable to be leaked to cloud providers and even clients. Thus, it is prudent for users to encrypt their data before transmitting to the cloud.Fully homomorphic encryption (FHE) provides a fundamental method to solve the issue, making it possible to perform arbitrary operations over encrypted data. In particular, FHE enables the third party who does not know anything about the secret key and plaintexts to homomorphically evaluate any computable functions on the corresponding ciphertexts. Since 2009, when Gentry proposed the first FHE scheme [1], FHE has been a research hot spot. Various FHE schemes were then proposed [2–4].However, conventional FHE is only a single-key one, where the homomorphic evaluation can only be performed over ciphertexts encrypted under the same key. Compared with single-key FHE, multikey FHE is more practical. In many scenarios, several users (often mutually distrusting) want to compute a joint function on their collective data, which have been encrypted and stored in the cloud. For example, two medical companies want the cloud to calculate some statistical information on their medical databases that are encrypted using their own public keys and stored on the cloud. In the meantime, they do not want to leak anything except the final result to others. Single-key FHE cannot deal with these situations, while multikey FHE enables ciphertexts encrypted under different public keys to be homomorphically computed without having to decrypt these ciphertexts using their own private keys.At STOC 2012, López-Alt, Tromer and Vaikuntanathan [5] proposed the notion of multikey FHE (MKFHE) and they provided the first MKFHE candidate from NTRU-based cryptography. At CRYPTO 2015, Clear and McGoldrick [6] constructed an MKFHE scheme based on the learning with errors (LWE) assumption, which was simplified by Mukherjee and Wichs [7] and then followed by [8–11]. Very recently, Chen, Chillotti, and Song proposed an MKFHE scheme [12] based on TFHE [13], and they were the first to implement an MKFHE scheme.Identity-based FHE (IBFHE) is an identity-based version of FHE. The first IBFHE scheme was achieved by Gentry, Sahai, and Waters [4] using a special compiler, which allows all lattice-based IBE schemes [14, 15] to be compiled into IBFHE schemes. Multi-identity FHE (MIFHE) is an identity-based version of MKFHE. In an MIFHE scheme, only identity information and public parameters are required when encrypting, which simplifies certificate-based key management in public key infrastructure. Clear and McGoldrick [6] also constructed the first MIFHE scheme in the random oracle model based on the GPV-IBE scheme [14].However, there is always a question plaguing FHE researchers. How bandwidth-efficient can FHE be? Although it is quite easy to achieve public key encryption (PKE) with nearly no loss in bandwidth, the same is nontrivial in the FHE case because there should be much more redundancy in an FHE ciphertext to support homomorphism, which means much more bandwidth waste.Some works managed to partly improve the inefficiency by using the “dimension-modulus reduction” technique [16, 17] to make ciphertexts have smaller dimensions and coefficients, and some by using the “ciphertext packing” technique [18–20] managed to encrypt an array of plaintexts in a single ciphertext and even encrypt a matrix of plaintexts in a single ciphertext [21, 22]. But none of them achieved a “sufficiently high” rate; that is, none of them break the rate-1/2 bottleneck. Very recently, Gentry and Halevi [23] proposed the first compressible FHE scheme, allowing compressing many ciphertexts into a compressed one, so that the compression rate can reach 1−ε for any small ε>0. A concurrent work of Brakerski et al. [24] also achieved compressible FHE, but their work is more general and is unlikely to yield practical schemes for applications.A natural question is the following: how can we extend their idea of compressible single-key FHE into compressible MKFHE or compressible MIFHE to achieve an optimal compression rate even in the multikey and multi-identity cases? In other words, we want to construct a compressible MKFHE scheme and a compressible MIFHE scheme that enable ciphertexts encrypted under different public keys and different identities to perform homomorphic operations without having to decrypt these ciphertexts using their own private keys. At the same time, expanded ciphertexts (under the combined key) are supposed to be compressed to achieve an optimal compression rate. In this work, we focus on this problem.


### 1.1. Technical Overview

We now give a technical overview of our new compressible expansion algorithm, which is the key step towards our constructions of compressible MKFHE and compressible MIFHE. We start with Gentry and Halevi’s basic ideas of constructing compressible single-key FHE [23]. Then, we give a discussion about the difficulties encountered when trying to construct compressible multikey (multi-identity) FHE, which can be solved using our new compressible expansion algorithm.


#### 1.1.1. Compressible Single-Key FHE

We begin with a brief description of the approach of Gentry and Halevi. At a very high level, their approach of building a compressible single-key FHE is based on two ideas:Using matrix versions of LWE and GSW-FHE [4]. Firstly, they noticed that the conventional GSW-FHE uses only one “slot” to place a message bit. To achieve an optimal compression rate, more message “slots” must be utilized. Their solution is to use LWE with matrix secrets, which yields a matrix version of GSW-FHE. Then, a compression algorithm is added after evaluation, so that multiple ciphertexts can be compressed into one. Besides, the secret key of matrix version is used in the decryption algorithm. The compression rate is now bounded by α=n×n/n+small×n+smallℓ≈1/ℓ=1/⌈logq⌉≤1/2.Using a “nearly square” gadget matrix. The second idea is to transform a “fat” compressed ciphertext matrix into a “nearly square” compressed ciphertext matrix using a “nearly square” gadget matrixH with some special properties, which comes with almost no dimension expansion. On the other hand, attributed to H, the redundancy in ciphertexts enables us to erase the noise and finally recover the message matrix. Using H instead of the original gadget matrix G, the compression rate is now α=n×n/n+small×n+small≈1, an optimal compression rate!More information can be found later in Section2.4.


#### 1.1.2. Compressible Multikey (Multi-Identity) FHE

We propose the first compressible multikey (multi-identity) FHE that achieves an optimal compression rate via a new compressible expansion algorithm. At a high level, the key observation of our compressible expansion algorithm is that we can transform a secret key vector and a “fat” ciphertext matrix into a “nearly square” secret key matrix and a “nearly square” ciphertext matrix, even in the multikey and multi-identity FHE cases.We note that it is nontrivial to utilize the powerful functionality of the nearly square gadget matrixH described above in the multikey (or multi-identity) setting. The idea of using the matrix version of secret key does not directly work because all of the secret matrices for different users, say 2 users totally, are required to decrypt the expanded ciphertext. Hence, the combined key matrix S^=S1S2 is a “fat” one, rather than a “nearly square” one. To the best of our knowledge, all of the existing GSW-based multikey (or multi-identity) FHE schemes combine secret keys like this. To make the combined secret key matrix more “square,” we must decrease the number of columns of the combined secret key matrix.Our solution is to delete the identity matrix in every single secret key matrix because it seems like the most insignificant part compared with the LWE secrets. After all, everybody knows there is an identity matrix in the secret key matrix but no one can recover the LWE secrets after discarding them. The combined secret key matrixS^=S¯1S¯2=InS1InS2∈ℤqn×2n+r now becomes S^=InS1S2∈ℤqn×n+2r, a nearly square one again.Meanwhile, the structure of corresponding expanded ciphertexts must be tailored to fit the combined secret key. Traditionally, the expanded ciphertexts are supposed to be partitioned into22 blocks, each with the same size. Since we have discarded some columns of the combined secret key, it is fair to also dump some rows of expanded ciphertexts. In particular, the expanded ciphertexts are now partitioned into 2+1×2 blocks, each with different size, i.e.,(1)C1,1X10C2,2⟶C1,1X1C2,1X20C3,3.However, abandoning some rows disrupts the structure of the G-trapdoor, which bears great responsibility on evaluation and decryption. Here comes our second idea: restoring the disrupted structure of the G-trapdoor. In particular, the expanded ciphertexts should be partitioned into2+1×2+1 blocks rather than 2+1×2 blocks as above. Our construction allows user 1 to generate some additional helper information X1 and X2 associated with the ciphertext Ci,j when encrypting, and releasing all of them does not compromise semantic security. We define the expanded ciphertext as(2)C^=C1,1C1,2X1C2,1C2,2X200C3,3∈ℤqn+2r×n+2rℓ,so that(3)S^C^=C1,1+S1C2,1C1,2+S1C2,2X1+S1X2+S2C3,3≈wantμ1InGnμ1S1Grμ1S2Gr=ΔPart1Part2Part3.Part 1 and Part 2 are nothing special and there are many ways to achieve them [6, 7, 11]. The major difficulty lies in Part 3, i.e., X1+S1X2+S2C3,3≈wantμ1S2Gr. The right-hand side must come from S2C3,3, since the randomness S2 can only come from this. In terms of normal routine, S2C3,3−μ1S2Gr≈A2R, where A2 is the public key of user 2 and R is the encryption randomness. Thus, the only thing left is to construct X1+S1X2≈want−A2R.Similarly, the expanded ciphertext for user 2 can be created, and then we can perform regular GSW-like homomorphic evaluations. Our new expansion technique leads to the first compressible MKFHE and the first compressible MIFHE. The relationship between them is just like the relationship between Regev-PKE [25] and GPV-IBE [14]. A more formal and detailed description can be found later in Sections 3 and 4.


### 1.2. Contribution

In this paper, a new compressible expansion algorithm is proposed, which makes it possible to construct the first compressible MKFHE scheme, as well as the first compressible MIFHE scheme, while the construction of Gentry and Halevi only works for compressible single-key FHE. Informally, the following theorem outlines our main result. A formal version will be presented later in Sections3 and 4.Theorem 1.
For anyε=ελ>0, there exist a rate-1−ε compressible multikey fully homomorphic encryption scheme that is semantically secure and a rate-1−ε compressible multi-identity fully homomorphic encryption scheme that is selectively secure, both under the decisional learning with error assumption.Besides, as Gentry and Halevi noted, a compressible MKFHE scheme or a compressible MIFHE scheme enables messages always in a compressed state except when operating homomorphic evaluation for a short time. In particular, freshly encrypted ciphertexts are compressed after encryption. The compressed ciphertexts are homomorphically decompressed before performing required homomorphic operations. Finally, these evaluated ciphertexts are compressed again and stored or transmitted to corresponding users.


### 1.3. Paper Organization

Firstly, we recall some notations, definitions, and facts in Section2. Then, we present our compressible MKFHE scheme in Section 3 and our compressible MIFHE scheme in Section 4, respectively. Finally, we conclude the paper in Section 5.


## 1.1. Technical Overview

We now give a technical overview of our new compressible expansion algorithm, which is the key step towards our constructions of compressible MKFHE and compressible MIFHE. We start with Gentry and Halevi’s basic ideas of constructing compressible single-key FHE [23]. Then, we give a discussion about the difficulties encountered when trying to construct compressible multikey (multi-identity) FHE, which can be solved using our new compressible expansion algorithm.


### 1.1.1. Compressible Single-Key FHE

We begin with a brief description of the approach of Gentry and Halevi. At a very high level, their approach of building a compressible single-key FHE is based on two ideas:Using matrix versions of LWE and GSW-FHE [4]. Firstly, they noticed that the conventional GSW-FHE uses only one “slot” to place a message bit. To achieve an optimal compression rate, more message “slots” must be utilized. Their solution is to use LWE with matrix secrets, which yields a matrix version of GSW-FHE. Then, a compression algorithm is added after evaluation, so that multiple ciphertexts can be compressed into one. Besides, the secret key of matrix version is used in the decryption algorithm. The compression rate is now bounded by α=n×n/n+small×n+smallℓ≈1/ℓ=1/⌈logq⌉≤1/2.Using a “nearly square” gadget matrix. The second idea is to transform a “fat” compressed ciphertext matrix into a “nearly square” compressed ciphertext matrix using a “nearly square” gadget matrixH with some special properties, which comes with almost no dimension expansion. On the other hand, attributed to H, the redundancy in ciphertexts enables us to erase the noise and finally recover the message matrix. Using H instead of the original gadget matrix G, the compression rate is now α=n×n/n+small×n+small≈1, an optimal compression rate!More information can be found later in Section2.4.


### 1.1.2. Compressible Multikey (Multi-Identity) FHE

We propose the first compressible multikey (multi-identity) FHE that achieves an optimal compression rate via a new compressible expansion algorithm. At a high level, the key observation of our compressible expansion algorithm is that we can transform a secret key vector and a “fat” ciphertext matrix into a “nearly square” secret key matrix and a “nearly square” ciphertext matrix, even in the multikey and multi-identity FHE cases.We note that it is nontrivial to utilize the powerful functionality of the nearly square gadget matrixH described above in the multikey (or multi-identity) setting. The idea of using the matrix version of secret key does not directly work because all of the secret matrices for different users, say 2 users totally, are required to decrypt the expanded ciphertext. Hence, the combined key matrix S^=S1S2 is a “fat” one, rather than a “nearly square” one. To the best of our knowledge, all of the existing GSW-based multikey (or multi-identity) FHE schemes combine secret keys like this. To make the combined secret key matrix more “square,” we must decrease the number of columns of the combined secret key matrix.Our solution is to delete the identity matrix in every single secret key matrix because it seems like the most insignificant part compared with the LWE secrets. After all, everybody knows there is an identity matrix in the secret key matrix but no one can recover the LWE secrets after discarding them. The combined secret key matrixS^=S¯1S¯2=InS1InS2∈ℤqn×2n+r now becomes S^=InS1S2∈ℤqn×n+2r, a nearly square one again.Meanwhile, the structure of corresponding expanded ciphertexts must be tailored to fit the combined secret key. Traditionally, the expanded ciphertexts are supposed to be partitioned into22 blocks, each with the same size. Since we have discarded some columns of the combined secret key, it is fair to also dump some rows of expanded ciphertexts. In particular, the expanded ciphertexts are now partitioned into 2+1×2 blocks, each with different size, i.e.,(1)C1,1X10C2,2⟶C1,1X1C2,1X20C3,3.However, abandoning some rows disrupts the structure of the G-trapdoor, which bears great responsibility on evaluation and decryption. Here comes our second idea: restoring the disrupted structure of the G-trapdoor. In particular, the expanded ciphertexts should be partitioned into2+1×2+1 blocks rather than 2+1×2 blocks as above. Our construction allows user 1 to generate some additional helper information X1 and X2 associated with the ciphertext Ci,j when encrypting, and releasing all of them does not compromise semantic security. We define the expanded ciphertext as(2)C^=C1,1C1,2X1C2,1C2,2X200C3,3∈ℤqn+2r×n+2rℓ,so that(3)S^C^=C1,1+S1C2,1C1,2+S1C2,2X1+S1X2+S2C3,3≈wantμ1InGnμ1S1Grμ1S2Gr=ΔPart1Part2Part3.Part 1 and Part 2 are nothing special and there are many ways to achieve them [6, 7, 11]. The major difficulty lies in Part 3, i.e., X1+S1X2+S2C3,3≈wantμ1S2Gr. The right-hand side must come from S2C3,3, since the randomness S2 can only come from this. In terms of normal routine, S2C3,3−μ1S2Gr≈A2R, where A2 is the public key of user 2 and R is the encryption randomness. Thus, the only thing left is to construct X1+S1X2≈want−A2R.Similarly, the expanded ciphertext for user 2 can be created, and then we can perform regular GSW-like homomorphic evaluations. Our new expansion technique leads to the first compressible MKFHE and the first compressible MIFHE. The relationship between them is just like the relationship between Regev-PKE [25] and GPV-IBE [14]. A more formal and detailed description can be found later in Sections 3 and 4.


## 1.1.1. Compressible Single-Key FHE

We begin with a brief description of the approach of Gentry and Halevi. At a very high level, their approach of building a compressible single-key FHE is based on two ideas:Using matrix versions of LWE and GSW-FHE [4]. Firstly, they noticed that the conventional GSW-FHE uses only one “slot” to place a message bit. To achieve an optimal compression rate, more message “slots” must be utilized. Their solution is to use LWE with matrix secrets, which yields a matrix version of GSW-FHE. Then, a compression algorithm is added after evaluation, so that multiple ciphertexts can be compressed into one. Besides, the secret key of matrix version is used in the decryption algorithm. The compression rate is now bounded by α=n×n/n+small×n+smallℓ≈1/ℓ=1/⌈logq⌉≤1/2.Using a “nearly square” gadget matrix. The second idea is to transform a “fat” compressed ciphertext matrix into a “nearly square” compressed ciphertext matrix using a “nearly square” gadget matrixH with some special properties, which comes with almost no dimension expansion. On the other hand, attributed to H, the redundancy in ciphertexts enables us to erase the noise and finally recover the message matrix. Using H instead of the original gadget matrix G, the compression rate is now α=n×n/n+small×n+small≈1, an optimal compression rate!More information can be found later in Section2.4.


## 1.1.2. Compressible Multikey (Multi-Identity) FHE

We propose the first compressible multikey (multi-identity) FHE that achieves an optimal compression rate via a new compressible expansion algorithm. At a high level, the key observation of our compressible expansion algorithm is that we can transform a secret key vector and a “fat” ciphertext matrix into a “nearly square” secret key matrix and a “nearly square” ciphertext matrix, even in the multikey and multi-identity FHE cases.We note that it is nontrivial to utilize the powerful functionality of the nearly square gadget matrixH described above in the multikey (or multi-identity) setting. The idea of using the matrix version of secret key does not directly work because all of the secret matrices for different users, say 2 users totally, are required to decrypt the expanded ciphertext. Hence, the combined key matrix S^=S1S2 is a “fat” one, rather than a “nearly square” one. To the best of our knowledge, all of the existing GSW-based multikey (or multi-identity) FHE schemes combine secret keys like this. To make the combined secret key matrix more “square,” we must decrease the number of columns of the combined secret key matrix.Our solution is to delete the identity matrix in every single secret key matrix because it seems like the most insignificant part compared with the LWE secrets. After all, everybody knows there is an identity matrix in the secret key matrix but no one can recover the LWE secrets after discarding them. The combined secret key matrixS^=S¯1S¯2=InS1InS2∈ℤqn×2n+r now becomes S^=InS1S2∈ℤqn×n+2r, a nearly square one again.Meanwhile, the structure of corresponding expanded ciphertexts must be tailored to fit the combined secret key. Traditionally, the expanded ciphertexts are supposed to be partitioned into22 blocks, each with the same size. Since we have discarded some columns of the combined secret key, it is fair to also dump some rows of expanded ciphertexts. In particular, the expanded ciphertexts are now partitioned into 2+1×2 blocks, each with different size, i.e.,(1)C1,1X10C2,2⟶C1,1X1C2,1X20C3,3.However, abandoning some rows disrupts the structure of the G-trapdoor, which bears great responsibility on evaluation and decryption. Here comes our second idea: restoring the disrupted structure of the G-trapdoor. In particular, the expanded ciphertexts should be partitioned into2+1×2+1 blocks rather than 2+1×2 blocks as above. Our construction allows user 1 to generate some additional helper information X1 and X2 associated with the ciphertext Ci,j when encrypting, and releasing all of them does not compromise semantic security. We define the expanded ciphertext as(2)C^=C1,1C1,2X1C2,1C2,2X200C3,3∈ℤqn+2r×n+2rℓ,so that(3)S^C^=C1,1+S1C2,1C1,2+S1C2,2X1+S1X2+S2C3,3≈wantμ1InGnμ1S1Grμ1S2Gr=ΔPart1Part2Part3.Part 1 and Part 2 are nothing special and there are many ways to achieve them [6, 7, 11]. The major difficulty lies in Part 3, i.e., X1+S1X2+S2C3,3≈wantμ1S2Gr. The right-hand side must come from S2C3,3, since the randomness S2 can only come from this. In terms of normal routine, S2C3,3−μ1S2Gr≈A2R, where A2 is the public key of user 2 and R is the encryption randomness. Thus, the only thing left is to construct X1+S1X2≈want−A2R.Similarly, the expanded ciphertext for user 2 can be created, and then we can perform regular GSW-like homomorphic evaluations. Our new expansion technique leads to the first compressible MKFHE and the first compressible MIFHE. The relationship between them is just like the relationship between Regev-PKE [25] and GPV-IBE [14]. A more formal and detailed description can be found later in Sections 3 and 4.


## 1.2. Contribution

In this paper, a new compressible expansion algorithm is proposed, which makes it possible to construct the first compressible MKFHE scheme, as well as the first compressible MIFHE scheme, while the construction of Gentry and Halevi only works for compressible single-key FHE. Informally, the following theorem outlines our main result. A formal version will be presented later in Sections3 and 4.Theorem 1.
For anyε=ελ>0, there exist a rate-1−ε compressible multikey fully homomorphic encryption scheme that is semantically secure and a rate-1−ε compressible multi-identity fully homomorphic encryption scheme that is selectively secure, both under the decisional learning with error assumption.Besides, as Gentry and Halevi noted, a compressible MKFHE scheme or a compressible MIFHE scheme enables messages always in a compressed state except when operating homomorphic evaluation for a short time. In particular, freshly encrypted ciphertexts are compressed after encryption. The compressed ciphertexts are homomorphically decompressed before performing required homomorphic operations. Finally, these evaluated ciphertexts are compressed again and stored or transmitted to corresponding users.


## 1.3. Paper Organization

Firstly, we recall some notations, definitions, and facts in Section2. Then, we present our compressible MKFHE scheme in Section 3 and our compressible MIFHE scheme in Section 4, respectively. Finally, we conclude the paper in Section 5.


## 2. Preliminaries

There are some notations that we will use throughout this paper. Letλ denote the security parameter throughout the paper. Matrices are represented by bold uppercase letters (e.g., A,B), vectors are represented by bold lowercase letters (e.g., a,b), the ith-entry of a is represented by the notation of ai, the n-dimensional identity matrix is represented by In, the concatenation of two matrices is represented by the notation of AB, and the concatenation of two vectors is represented by the notation of a,b.


### 2.1. Lattice Trapdoor

Our constructions will make use of the following results including theG-trapdoor generation algorithm, sub-Gaussian sampling algorithm, and Gaussian sampling algorithm [26]. We only summarize the following lemmas here while neglecting the details of implementation because they are not strictly required.LetD be a distribution over −1,0,1 which outputs 0 with a probability of 0.5, -1 with a probability of 0.25, and 1 with a probability of 0.25 (the notation of D will be used throughout this paper to denote this distribution).Given an integerq>2, for any n∈ℤ+, define Gn=ΔIn⊗gT∈ℤqn×n⌈logq⌉, where gT=1,2,22,…,2⌈logq⌉−1. The notation of Gn will be used throughout this paper.Lemma 1 (see [26]).
Letn,m0,m1,m,q,ℓ be positive integers such that q=qn,ℓ=⌈logq⌉,m0=nℓ+On, m1=nℓ, and m=m0+m1. For A0←$ℤqn×m0, invertible H∈ℤqn×n, and R←Dm0×m1, there exists an efficiently randomized algorithm GenTrap (A0,H) to generate a matrix A=ΔA0HGn−A0R∈ℤqn×m with trapdoor R and tag H such that A is negln-far from uniform. The matrix R is called the G-trapdoor of A with tag H.Lemma 2 (see [26, 27]).
Given any matrixA∈ℤqn×n′, there exists an efficiently randomized algorithm that samples a sub-Gaussian matrix X with some constant parameter O1 over ℤqnℓ×n′ such that X=Gn−1A, where the gadget matrix Gn is specified as above.Lemma 3 (see [26]).
Using the parameters described in Lemma1, given a uniformly random vector u∈ℤqn, there exists an efficient algorithm SampleDR,A0,H,u,s that samples a vector t over Dℤ,s·ωlognm for some s∈ℝ and ωlogn satisfying A·t=u.


### 2.2. LWE

The learning with errors (LWE) problem plays an important role in lattice-based cryptography. Although a ring-based version is more efficient, this work is confined to LWE. We define the decisional LWE (DLWEn,m,q,χ) problem as follows.Definition 1.
(DLWE) For positive integersn,q and an error distribution χ over ℤ, let As,χ be the distribution of a,a,s+e over ℤqn×ℤq, where s←$ℤqn , e←χ, and a←$ℤqn; and additions are performed in ℤq. Given m=polyn independent instances sampled either from the uniform distribution over ℤqn×ℤq or from As,χ, the decisional learning with errors (DLWEn,m,q,χ) problem is to determine which distribution these samples come from. The DLWE assumption says that these two distributions are computationally indistinguishable.
For simplicity,DLWEn,m,q,α is frequently used to denote DLWEn,m,q,χ and As,α to denote As,χ for χ=Dℤ,αq. It is generally known that the DLWEn,m,q,α problem in the average case is as hard as approximation lattices problems with approximation factors of O˜n/α in the worst case by quantum or classical reductions, when αq≥2n [25, 26, 28, 29].
In this work, we rely on the matrix form of LWE denoted by MLWE.Definition 2.
(MLWE) For positive integersn,m,r,q and an error distribution χ over ℤ, the MLWEn,r,m,q,χ problem is to distinguish between B,A=S·B+E, where S←$ℤqn×r,B←$ℤqr×m,E←χn×m; and additions are performed in ℤq, and B,A sampled uniformly at random from ℤqr×m×ℤqn×m.
Standard hybrid arguments show that MLWE is equivalent to DLWE with at most ann factor loss in the distinguishing advantage.


### 2.3. GSW-FHE

In this subsection, a matrix version of GSW-FHE [4] is given.GSW.Setup1λ: Given a security parameter λ, choose a lattice dimension r=rλ, a sufficiently large m modulus q=qλ, a number of LWE instances n=nλ, and a βχ-bounded error distribution χ=χλ. Set ℓ=Δ⌈logq⌉, n¯=Δn+r, and m=Δn¯ℓ. Output public parameters params=r,n,n¯,q,ℓ,βχ,χ,m.GSW.KeyGen(params): Randomly choose B←$ℤqr×m, S←$ℤqn×r, and E←χn×m. Compute A=SB+E. Let the secret key and public key be SK=ΔS¯=ΔInS∈ℤqn×n¯ and PK=ΔA¯=Δ−AB∈ℤqn¯×m. Note that S¯A¯=E. Output PK,SK.GSW.Enc(params,PK,μ∈0,1): Choose random matrices R¯←$0,1m×m. Set C=ΔμGn¯+A¯R¯∈ℤqn¯×m. Output the ciphertext C.GSW.Decparams,C,SK: Let c be the penultimate column vector of C and let s be any column of S¯. Output s,c2, where ·2:ℤq⟶0,1 maps a number xmodq to 0 if it is closer to 0 and to 1 if it is closer to 2ℓ−2.GSW.Evalparams,f,C^1,C^2,…,C^s: To homomorphically evaluate a function f, perform homomorphic addition and multiplication in sequence.Addition:Cadd=ΔC1+C2.Multiplication:Cmult=ΔC1×Gn¯−1C2.This also allows us to compute a homomorphic NAND gate by outputtingGn¯−C1×Gn¯−1C2.The correctness of decryption and homomorphic evaluation is obvious due to the correctness of the conventional GSW-FHE, and the semantic security is based on the MLWE assumption, which is in turn based on the DLWE assumption.


### 2.4. Compressible Single-Key FHE

Very recently, Gentry and Halevi proposed the first compressible single-key FHE. At a high level, their approach is based on two ideas:Using matrix versions of LWE and GSW-FHE [4]. Firstly, they noticed that the conventional GSW-FHE uses only one “slot” when decrypting, i.e.,(4)1,−sC=μ1,−sG+1,−sbAR≈μ,−μsG.Their solution to utilize more “slots” is to use LWE with matrix secrets, which yields the matrix version of GSW-FHE described above. They added a compression algorithm after evaluation:(5)C∗=Δ∑i∑j∑kCi,j,k·G−12k·Eni,j0G∈Zqn¯×n¯ℓ,whereC∗ is the compressed ciphertext and Eni,j is an n×n matrix that has 1 in the ith row and jth column and 0’s in all other entries. Then the matrix secrets are used in the decryption algorithm:(6)In−SC∗≈∑i∑j∑k2kμi,j,kInSEni,j0G=∑i∑j∑k2kμi,j,kInEni,jG=ΔMG,whereM∈Zqn×n. The compression rate is now bounded by α=n×n/n¯×n¯ℓ=n×n/n+small×n+smallℓ≈1/ℓ=1/logq.Using a “nearly square” gadget matrix. The second idea is to transform a “fat” compressed ciphertext matrix into a “nearly square” compressed ciphertext matrix using a “nearly square” gadget matrixH with some special properties, which comes with almost no dimension expansion. On the other hand, attributed to H, the redundancy in ciphertexts enables us to erase the noise and finally recover the message matrix. We omit the details of constructing the “nearly square” gadget matrix H because it is not strictly required in this paper. The essential characteristic of H that is required in our construction is that it has a “public trapdoor” matrix H−10=F satisfying the following:(1)
F has small entries (≪q);(2)
H×F=0 (mod q), i.e., all rows of H span the kernel space of F modulo q;(3)
F is full rank over R;(4)
F is efficiently computable.Then, the compression algorithms can produce an optimal rate compressed ciphertext. In particular, letCi,j,ki,j∈n,k∈ℓ be GSW ciphertexts encrypting μi,j,k∈0,1i,j∈n,k∈ℓ. Set the compressed ciphertext(7)C∗=Δ∑i∑j∑kCi,j,k×G−12k·Eni,j0H∈ℤqn¯×n¯,where Eni,j is an n×n matrix that has 1 in the ith row and jth column and 0’s in all other entries.Roughly speaking, they have now achieved an optimal compression rate because after “routine decryption” we get(8)InSC∗≈∑i∑j∑k2kμi,j,kInSEni,j0H=∑i∑j∑k2kμi,j,kInEni,jH=ΔMH,where M∈Zqn×n. The compression rate is now α=n×n/n¯×n¯=n×n/n+small×n+small≈1, an optimal compression rate!In particular, they upgrade the “routine decryption” into “compressed decryption” which is composed of four steps:(1)
Z=ΔS¯×C∗=MH+E (mod q), where M∈ℤqn×n is a message matrix; H∈ℤqn×n¯ is the nearly square gadget matrix; E∈ℤqn×n¯ is a small error matrix;(2)
Y=ΔZ×F=EF (mod q), where F∈ℤqn¯×n¯ is the public trapdoor matrix;(3)
X=ΔY×F−1=E (note that F is full rank over R and it is required that every entry of EF does not wrap around ℤq);(4)
M′=ΔZ−X×H−1=M (mod q) (note that H is a row full-rank matrix modulo q).Recall that the compression rate is the ratio of plaintext size to the ciphertext size. To achieve an optimal compression rate of1−ε for some small ε>0, set t=Δε/2, where t is the compression parameter defined as a function of the desired compression rate. Then the compression rate γ=n·n/n¯·n¯=t−1/t2≥1−ε.The additional compression algorithm does not compromise security and the key-generation, encryption, and evaluation algorithms are basically the same as the ones of matrix version of GSW-FHE. Thus, the semantic security of their compressible FHE is based solely on the DLWE assumption. However, the compressed ciphertexts are not GSW ciphertexts any longer, which means they can only support homomorphic addition and multiplication on the left by some GSW ciphertexts encrypting a small scalar. For more information, please refer to [23].


## 2.1. Lattice Trapdoor

Our constructions will make use of the following results including theG-trapdoor generation algorithm, sub-Gaussian sampling algorithm, and Gaussian sampling algorithm [26]. We only summarize the following lemmas here while neglecting the details of implementation because they are not strictly required.LetD be a distribution over −1,0,1 which outputs 0 with a probability of 0.5, -1 with a probability of 0.25, and 1 with a probability of 0.25 (the notation of D will be used throughout this paper to denote this distribution).Given an integerq>2, for any n∈ℤ+, define Gn=ΔIn⊗gT∈ℤqn×n⌈logq⌉, where gT=1,2,22,…,2⌈logq⌉−1. The notation of Gn will be used throughout this paper.Lemma 1 (see [26]).
Letn,m0,m1,m,q,ℓ be positive integers such that q=qn,ℓ=⌈logq⌉,m0=nℓ+On, m1=nℓ, and m=m0+m1. For A0←$ℤqn×m0, invertible H∈ℤqn×n, and R←Dm0×m1, there exists an efficiently randomized algorithm GenTrap (A0,H) to generate a matrix A=ΔA0HGn−A0R∈ℤqn×m with trapdoor R and tag H such that A is negln-far from uniform. The matrix R is called the G-trapdoor of A with tag H.Lemma 2 (see [26, 27]).
Given any matrixA∈ℤqn×n′, there exists an efficiently randomized algorithm that samples a sub-Gaussian matrix X with some constant parameter O1 over ℤqnℓ×n′ such that X=Gn−1A, where the gadget matrix Gn is specified as above.Lemma 3 (see [26]).
Using the parameters described in Lemma1, given a uniformly random vector u∈ℤqn, there exists an efficient algorithm SampleDR,A0,H,u,s that samples a vector t over Dℤ,s·ωlognm for some s∈ℝ and ωlogn satisfying A·t=u.


## 2.2. LWE

The learning with errors (LWE) problem plays an important role in lattice-based cryptography. Although a ring-based version is more efficient, this work is confined to LWE. We define the decisional LWE (DLWEn,m,q,χ) problem as follows.Definition 1.
(DLWE) For positive integersn,q and an error distribution χ over ℤ, let As,χ be the distribution of a,a,s+e over ℤqn×ℤq, where s←$ℤqn , e←χ, and a←$ℤqn; and additions are performed in ℤq. Given m=polyn independent instances sampled either from the uniform distribution over ℤqn×ℤq or from As,χ, the decisional learning with errors (DLWEn,m,q,χ) problem is to determine which distribution these samples come from. The DLWE assumption says that these two distributions are computationally indistinguishable.
For simplicity,DLWEn,m,q,α is frequently used to denote DLWEn,m,q,χ and As,α to denote As,χ for χ=Dℤ,αq. It is generally known that the DLWEn,m,q,α problem in the average case is as hard as approximation lattices problems with approximation factors of O˜n/α in the worst case by quantum or classical reductions, when αq≥2n [25, 26, 28, 29].
In this work, we rely on the matrix form of LWE denoted by MLWE.Definition 2.
(MLWE) For positive integersn,m,r,q and an error distribution χ over ℤ, the MLWEn,r,m,q,χ problem is to distinguish between B,A=S·B+E, where S←$ℤqn×r,B←$ℤqr×m,E←χn×m; and additions are performed in ℤq, and B,A sampled uniformly at random from ℤqr×m×ℤqn×m.
Standard hybrid arguments show that MLWE is equivalent to DLWE with at most ann factor loss in the distinguishing advantage.


## 2.3. GSW-FHE

In this subsection, a matrix version of GSW-FHE [4] is given.GSW.Setup1λ: Given a security parameter λ, choose a lattice dimension r=rλ, a sufficiently large m modulus q=qλ, a number of LWE instances n=nλ, and a βχ-bounded error distribution χ=χλ. Set ℓ=Δ⌈logq⌉, n¯=Δn+r, and m=Δn¯ℓ. Output public parameters params=r,n,n¯,q,ℓ,βχ,χ,m.GSW.KeyGen(params): Randomly choose B←$ℤqr×m, S←$ℤqn×r, and E←χn×m. Compute A=SB+E. Let the secret key and public key be SK=ΔS¯=ΔInS∈ℤqn×n¯ and PK=ΔA¯=Δ−AB∈ℤqn¯×m. Note that S¯A¯=E. Output PK,SK.GSW.Enc(params,PK,μ∈0,1): Choose random matrices R¯←$0,1m×m. Set C=ΔμGn¯+A¯R¯∈ℤqn¯×m. Output the ciphertext C.GSW.Decparams,C,SK: Let c be the penultimate column vector of C and let s be any column of S¯. Output s,c2, where ·2:ℤq⟶0,1 maps a number xmodq to 0 if it is closer to 0 and to 1 if it is closer to 2ℓ−2.GSW.Evalparams,f,C^1,C^2,…,C^s: To homomorphically evaluate a function f, perform homomorphic addition and multiplication in sequence.Addition:Cadd=ΔC1+C2.Multiplication:Cmult=ΔC1×Gn¯−1C2.This also allows us to compute a homomorphic NAND gate by outputtingGn¯−C1×Gn¯−1C2.The correctness of decryption and homomorphic evaluation is obvious due to the correctness of the conventional GSW-FHE, and the semantic security is based on the MLWE assumption, which is in turn based on the DLWE assumption.


## 2.4. Compressible Single-Key FHE

Very recently, Gentry and Halevi proposed the first compressible single-key FHE. At a high level, their approach is based on two ideas:Using matrix versions of LWE and GSW-FHE [4]. Firstly, they noticed that the conventional GSW-FHE uses only one “slot” when decrypting, i.e.,(4)1,−sC=μ1,−sG+1,−sbAR≈μ,−μsG.Their solution to utilize more “slots” is to use LWE with matrix secrets, which yields the matrix version of GSW-FHE described above. They added a compression algorithm after evaluation:(5)C∗=Δ∑i∑j∑kCi,j,k·G−12k·Eni,j0G∈Zqn¯×n¯ℓ,whereC∗ is the compressed ciphertext and Eni,j is an n×n matrix that has 1 in the ith row and jth column and 0’s in all other entries. Then the matrix secrets are used in the decryption algorithm:(6)In−SC∗≈∑i∑j∑k2kμi,j,kInSEni,j0G=∑i∑j∑k2kμi,j,kInEni,jG=ΔMG,whereM∈Zqn×n. The compression rate is now bounded by α=n×n/n¯×n¯ℓ=n×n/n+small×n+smallℓ≈1/ℓ=1/logq.Using a “nearly square” gadget matrix. The second idea is to transform a “fat” compressed ciphertext matrix into a “nearly square” compressed ciphertext matrix using a “nearly square” gadget matrixH with some special properties, which comes with almost no dimension expansion. On the other hand, attributed to H, the redundancy in ciphertexts enables us to erase the noise and finally recover the message matrix. We omit the details of constructing the “nearly square” gadget matrix H because it is not strictly required in this paper. The essential characteristic of H that is required in our construction is that it has a “public trapdoor” matrix H−10=F satisfying the following:(1)
F has small entries (≪q);(2)
H×F=0 (mod q), i.e., all rows of H span the kernel space of F modulo q;(3)
F is full rank over R;(4)
F is efficiently computable.Then, the compression algorithms can produce an optimal rate compressed ciphertext. In particular, letCi,j,ki,j∈n,k∈ℓ be GSW ciphertexts encrypting μi,j,k∈0,1i,j∈n,k∈ℓ. Set the compressed ciphertext(7)C∗=Δ∑i∑j∑kCi,j,k×G−12k·Eni,j0H∈ℤqn¯×n¯,where Eni,j is an n×n matrix that has 1 in the ith row and jth column and 0’s in all other entries.Roughly speaking, they have now achieved an optimal compression rate because after “routine decryption” we get(8)InSC∗≈∑i∑j∑k2kμi,j,kInSEni,j0H=∑i∑j∑k2kμi,j,kInEni,jH=ΔMH,where M∈Zqn×n. The compression rate is now α=n×n/n¯×n¯=n×n/n+small×n+small≈1, an optimal compression rate!In particular, they upgrade the “routine decryption” into “compressed decryption” which is composed of four steps:(1)
Z=ΔS¯×C∗=MH+E (mod q), where M∈ℤqn×n is a message matrix; H∈ℤqn×n¯ is the nearly square gadget matrix; E∈ℤqn×n¯ is a small error matrix;(2)
Y=ΔZ×F=EF (mod q), where F∈ℤqn¯×n¯ is the public trapdoor matrix;(3)
X=ΔY×F−1=E (note that F is full rank over R and it is required that every entry of EF does not wrap around ℤq);(4)
M′=ΔZ−X×H−1=M (mod q) (note that H is a row full-rank matrix modulo q).Recall that the compression rate is the ratio of plaintext size to the ciphertext size. To achieve an optimal compression rate of1−ε for some small ε>0, set t=Δε/2, where t is the compression parameter defined as a function of the desired compression rate. Then the compression rate γ=n·n/n¯·n¯=t−1/t2≥1−ε.The additional compression algorithm does not compromise security and the key-generation, encryption, and evaluation algorithms are basically the same as the ones of matrix version of GSW-FHE. Thus, the semantic security of their compressible FHE is based solely on the DLWE assumption. However, the compressed ciphertexts are not GSW ciphertexts any longer, which means they can only support homomorphic addition and multiplication on the left by some GSW ciphertexts encrypting a small scalar. For more information, please refer to [23].


## 3. Compressible Multikey Fully Homomorphic Encryption

In this section, utilizing the idea of our new compressible expansion algorithm described in Section1.1, we propose the first compressible MKFHE scheme and analyze the correctness and security level of the construction.


### 3.1. Compressible Multikey FHE

We begin with the definition of compressible MKFHE, which is adapted from the definitions of compressible FHE in [23] and MKFHE in [7].Definition 3.
A compressible multikey fully homomorphic encryption scheme consists of seven PPT algorithmsSetup,KeyGenerate,Encrypt,Expand,Evaluate,Compress and Decrypt defined as follows:Setup1λ,1N: Take a security parameter λ and a bound N on the number of users involved as inputs and output parameters params. params is taken in as an input in all of the following algorithms; thus, we just omit it.KeyGenparams,i∈N: Output a secret key SKi and a public key PKi for the ith user.EncPKi,μ∈0,1: Take a public key PKi and a bit μ∈0,1 as inputs, and output a fresh low-rate ciphertext ci .ExpPKjj∈N,ci: Take public keys PKjj∈N and a fresh ciphertext ci under the ith public key as inputs; and compute and output an expanded low-rate ciphertext c^ under N’s public keys PK1,PK2,…,PKN.Evalf,c^=c^ii∈t: Take a circuit f and a vector of expanded ciphertexts c^=c^1,c^2,…,c^t as inputs, corresponding to each input bit of f, and output another vector of evaluated low-rate ciphertext c^′=c^1′,c^2′,…,c^t′, corresponding to each output bit of f.Compc^=c^ii∈t: Take a vector of expanded or evaluated low-rate ciphertexts c^=c^1,c^2,…,c^t as inputs, and output one or more compressed high-rate ciphertext(s) c∗=ci∗i∈s.DecSKii∈N,c∗: Take N secret keys SK1,SK2,…,SKN, corresponding to identities id1,id2,…,idN, and the compressed ciphertext(s) c∗ as inputs, and output a vector of message bits m=μii∈t corresponding to c^ii∈t.
The scheme is said to be correct if, for every allowed circuitf and a vector of message bits m=μ1,…,μt∈0,1t corresponding to each input bit of f, it holds that(9)DecSKii∈N,CompEvalf,c^=c^ii∈t=m,where each c^i=ExpPKjj∈N,EncPKk,μi∈0,1.
Using the parameters described above, the scheme is said to have a compression rate of1−ε for any ε>0 if, for every allowed circuit f that has sufficiently long outputs, the compression rate(10)γ=mCompEvalf,c^=c^ii∈t≥1−ε.
The semantic security definition for compressible multikey fully homomorphic encryption is the same as that for multikey fully homomorphic encryption, which is the same as that for single-key fully homomorphic encryption because all of parameters used in the expansion and compression algorithms are public and thus do not compromise security. In particular, given a security parameterλ and a bound N on the number of users involved, the following distributions are computationally indistinguishable:(11)params,PKi,EncPKi,0≈compparams,PKi,EncPKi,1,where params←Setup1λ,1N and SKi,PKi←KeyGenparams,i∈N. We do not consider the distributed decryption for our MKFHE scheme, which can be used to construct round-efficient secure multiparty computation protocols, and instead put the main focus on the compressible expansion algorithm.


### 3.2. Our Construction

C-MKFHE.Setup1λ,1N: Choose a lattice dimension parameter r=polyλ,N, a sufficiently large modulus q, a βχ-bounded error distribution χ=χλ,N, and a compression parameter t=Δt′−1N. The parameter t′ will be specified in Subsection 3.3.2. All of the rows of the nearly square gadget matrix H′∈ℤqt′−1×t′ span the kernel space of its public trapdoor matrix F′∈ℤqt′×t′ having the properties stated in 2.4. Let ℓ=Δ⌈logq⌉, n=Δtr, n¯=Δt+Nr, m=Δt+1rℓ, and m¯=Δt+Nrℓ. Then, set H=ΔH′⊗IrN∈ℤqn×n¯ and F=ΔF′⊗IrN∈ℤqn¯×n¯. Choose a random matrix B←$ℤqr×m. Output params=r,N,q,ℓ,βχ,χ,t′,t,n,n¯,m,m¯,H,H′,F,F′,B.C-MKFHE.KeyGen(params): Choose random matrices S←$ℤqtr×r and E←χtr×m. Compute A=SB+E. Let the secret key and public key be SK=ΔS¯=ΔItrS∈ℤqtr×t+1r and PK=ΔA¯=Δ−AB∈ℤqt+1r×m. Note that S¯A¯=E. Output PK,SK.C-MKFHE.Enc(params,PKi,μ∈0,1): Given a message bit μ, randomly select a matrix R¯i←$0,1m×m. Set(12)C¯i=ΔμGt+1r+A¯iR¯i∈ℤqt+1r×m.Then, partitionC¯i as follows:(13)C¯i=ΔC¯i1,1C¯i1,2C¯i2,1C¯i2,2,whereC¯i1,1∈ℤqtr×trℓ,C¯i1,2∈ℤqtr×rℓ,C¯i2,1∈ℤqr×trℓ,C¯i2,2∈ℤqr×rℓ. Let Ri∈0,1m×rℓ be the last rℓ columns of R¯i. Note that(14)C¯i2,2=μGr+BRi∈ℤqr×rℓ.Forx∈t,y∈m,b∈rl, compute(15)Vi,1x,y,b=−AiR˜ix,y,b+Riy,bGmx∈ℤqtr×rℓ;Vi,2x,y,b=BR˜ix,y,b∈ℤqr×rℓ,whereR˜ix,y,b←$0,1m×rℓ and Grx=0x−1r×rℓGr0t−xr×rℓ∈ℤtr×rℓ.Set(16)Ui=ΔVi,1x,y,b,Vi,2x,y,bx∈t,y∈m,b∈rl.Output a tuple of encryptionCIPHERi=ΔC¯i,Ui.C-MKFHE.Exp(params,PKii∈N,CIPHERi): For every j∈N\i,x∈t,y∈n,b∈ml, compute(17)Zi,jx,y,bz1,z2=Δ−Ajz1+xr,y,ifz2=b,0,otherwise,that is,Zi,jx,y,b=Δ∑z1=1r−Ajz1+xr,y·Ez1,b′∈ℤqr×rℓ, where Ez1,b′ is an r×rℓ matrix that has 1 in the z1th row and the bth column and 0’s in all other entries. Set(18)Z¯i,jx,y,b=Δ0x−1r×rℓZi,jx,y,b0t−xr×rℓ∈ℤqtr×rℓ.Compute(19)Xi,j1=Δ∑x=1t∑y=1m∑b=1rlVi,1x,y,b·Gr−1Zi,jx,y,b∈ℤqtr×rℓ;Xi,j2=Δ∑x=1t∑y=1m∑b=1rlVi,2x,y,b·Gr−1Zi,jx,y,b∈ℤqr×rℓ.Finally, expand a fresh ciphertext to an expanded one.(20)C^i=ΔC¯i1,1Xi,11⋯C¯i1,2⋯Xi,N1C¯i2,2⋱C¯i2,1Xi,12⋯C¯i2,2⋯Xi,N2⋱C¯i2,2∈ℤqn¯×m¯.OutputC^i.C-MKFHE.Compparams,C^u,v,ωu,v∈n,ω∈ℓ: In this algorithm, a series of low-rate expanded (or evaluated) ciphertexts are compressed into a high-rate ciphertext. Let Tu,v=ΔEu,v′0Nr×n∈ℤn¯×n , where Eu,v′ is an n×n matrix that has 1 in the uth row and the vth column and 0’s in all other entries. Set the compressed ciphertext as(21)C∗=Δ∑u∈n∑v∈n∑ω∈ℓC^u,v,ω·Gn¯−12ωTu,v×H∈ℤqn¯×n¯.Note that the nearly square gadget matrixH∈ℤqn×n¯ and its public trapdoor F∈ℤqn¯×n¯ play a significant role in the compression and compressed decryption algorithms.C-MKFHE.CompDecparams,C∗,SKii∈N: Given a compressed ciphertext C∗, set the combined key S^=ΔItr,S1,…,SN∈ℤn×n¯. The compressed decryption is composed of four steps:(1)
Z=ΔS×C∗ (mod q);(2)
Y=ΔZ×F (mod q), where F∈ℤqn¯×n¯ is the public trapdoor matrix;(3)
X=ΔY×F−1 (note that F is full rank over R);(4)
M′=ΔZ−X×H−1 (mod q) (note that H is a row full-rank matrix modulo q, so that there exists a matrix H−1∈ℤqn¯×n such that H×H−1=In).C-MKFHE.NANDparams,C^1,C^2: Given two expanded ciphertext matrices C^1,C^2 for two plaintexts μ1,μ2, homomorphic NAND operation is defined as(22)C^NAND=ΔGn¯−C^1·Gn¯−1C^2.OutputC^NAND. Observe that Gx−1· is randomized, and so is this algorithm.C-MKFHE.Evalparams,f,C^1,C^2,…,C^s: An NAND-circuit f:0,1t⟶0,1 is applied to a set of ciphertexts C^1,C^2,…,C^s, which leads to a ciphertext C^f.


### 3.3. Setting the Parameters

In this subsection, the correctness, homomorphic properties, security, and compression rate of the proposed compressible MKFHE are analyzed. If we use a somewhat (or leveled) version without bootstrapping, then the error bound is dependent on the maximal multiplication depth of allowed evaluated functions. In this paper, we would like to give an asymptotic analysis of various parameters of a fully homomorphic one with bootstrapping so that all ciphertexts before being packed have an error bound similar to that of freshly expanded ciphertexts.


#### 3.3.1. Correctness and Homomorphism

The correctness of compressed decryption may be less obvious, since the encryption and expansion algorithms are quite different from previous ones. During encryption, it holds that(23)S¯i×C¯i=μS¯iGt+1r+EiR¯i∈ℤqn×m,because S¯iA¯i=Ei.Besides, for the additional helper information matrices, we have(24)Sj×C¯i2,2=μSjGr+AjRi−EjRi∈ℤqn×rℓ;Itr×Vi,1x,y,b=−AiR˜ix,y,b+Riy,bGrx∈ℤqn×rℓ;Si×Vi,2x,y,b=Ai−EiR˜ix,y,b∈ℤqn×rℓ,because Ai−Ei=SiB.During the expansion algorithm, those weird matricesXi,j1 and Xi,j2 are customized to eliminate the undesired AjRi in SjC¯i2,2. In particular, we have(25)Itr×Xi,j1=∑x=1t∑y=1m∑b=1rlVi,1x,y,b·Gr−1Zi,jx,y,b=∑x=1t∑y=1m∑b=1rlAiR˜ix,y,bGr−1Zi,jx,y,b+Riy,bZ¯i,jx,y,b¯=∑x=1t∑y=1m∑b=1rlAiR˜ix,y,bGr−1Zi,jx,y,b−AjRi¯,(26)Si×Xi,j2=∑x=1t∑y=1n∑b=1mlSiVi,2x,y,b·Gr−1Zix,y,b=∑x=1t∑y=1n∑b=1mlAi−EiR˜ix,y,b·Gr−1Zi,jx,y,b.The underlined part can be a tricky step. We now analyze it as follows:(27)∑y=1m∑b=1rlRiy,b∑x=1tZ¯i,jx,y,b=∑y=1m∑b=1rlRiy,b∑a=1tr−Aja,y×Ea,b′=∑a=1tr∑y=1m∑b=1rl−Aja,y·Riy,b×Ea,b′=−AjRi,where Ea,b′ is an tr×rℓ matrix that has 1 in the ath row and the bth column and 0’s in all other entries.Thus, for any expanded ciphertext, we have(28)S^×C^i=C¯i1,1+SiC¯i2,1Xi,11+S1C¯i2,2+SiXi,j2⋯C¯i1,2+SiC¯i2,2⋯Xi,N1+SNC¯i2,2+SiXi,N2∈ℤn×m¯.There are only two types of all blocks in the above seemingly cumbersome matrix. The first comes from equation (23) by partitioning(29)ItrSi×C¯i1,1C¯i1,2C¯i2,1C¯i2,2=μItrGtrSiGr+EiR¯i=ΔμItrGtr+E˜0μSiGr+E˜i∈ℤqn×m.The second comes from equations (24)–(26):(30)SjC¯i2,2+Xi,j1+SiXi,j2=μSjGr−EjRi−∑x=1t∑y=1n∑b=1mlEiR˜ix,y,bGr−1Zi,jx,y,b=ΔμSjGr+E˜j∈ℤqn×rℓ.Finally, we get the most important decryption invariant in all GSW-like encryption from equations (28)–(30):(31)S^×C^i=μItrGtr+E˜0μS1Gr+E˜1⋯μSNGr+E˜N=ΔμS^Gn¯+E^∈ℤqn×m¯.In terms of the error bound, we haveβExp=Δm4βχ; that is, maxa,bE^a,b<βExp with overwhelming probability.With equation (31) in mind, everything turns familiar again. Homomorphic properties are obvious, and one can find them in most GSW-like FHE (or MKFHE) schemes. Thus, we just omit them here.On the other hand, the correctness of compressed decryption also turns obvious. According to equation (31), we have(32)S^×C∗=∑u∈n∑v∈n∑ω∈ℓS^C^u,v,ω×Gn¯−12ω·Tu,vH=∑u,v,ωμu,v,ωS^Gn¯+E^Gn¯−12ω·Tu,vH=Δ∑u,v,ω2ωμu,v,ωS^Tu,vH+E∗=∑u,v,ω2ωμu,v,ωEu,v′H+E∗=ΔMH+E∗∈ℤqn×n¯,where Eu,v′ is an n×n matrix that has 1 in the uth row and the vth column and 0’s in all other entries and M∈ℤqn×n is a compressed plaintext matrix that can be obtained from Z=ΔS^×C∗=MH+E∗, by using Gentry and Halevi’s idea of the nearly square gadget matrix, which was briefly described in 2.4. That is,(1)
Y=ΔZ×F=E∗F (mod q), where F∈ℤqn¯×n¯ is the public trapdoor matrix;(2)
X=ΔY×F−1=E∗ (note that F is full rank over R);(3)
M′=ΔZ−X×H−1=M (mod q) (note that H is a row full-rank matrix modulo q, so that there exists a matrix H−1∈ℤqn¯×n such that H×H−1=In).The matrixM′ is the desired one if every entry of E∗F does not wrap around ℤq; that is, E∗Fmodq=E∗F over the integers. As for the error bound, we have βComp=Δm¯m2βExp; that is, maxa,bE∗a,b<βComp with overwhelming probability. On the other hand, by the construction of the public trapdoor matrix F, it is required that βComp≤q1/t′.


#### 3.3.2. Security and Compression Rate

It remains to show the security level and compression rate of our construction.The additional expansion and compression algorithms are public and do not compromise security. The key-generation algorithm is basically the same as that of the underlying GSW-FHE scheme. In addition, during the encryption procedure, a fresh ciphertext for theith user CIPHERi consists of two parts C¯i and Vi,1x,y,b,Vi,2x,y,b, of which randomness matrices are mutually independent, all in a similar encryption form. Exploiting a standard hybrid analysis, one can easily verify that the semantic security of our compressible MKFHE is based solely on the DLWE assumption.The view of the attacker is the following distribution:(33)params,PKi,C¯i,Ui=Vi,1x,y,b,Vi,2x,y,bx∈t,y∈m,b∈rl,generated via params←C−MKFHE⋅Setup1λ,1N, PKi,SKi←C−MKFHE⋅KeyGenparams, and C¯i,Ui←C−MKFHE⋅Encparams,PKi,μ, where μ∈0,1.We prove the semantic security of our construction by relying on the semantic security of the underlying matrix version of GSW-FHE scheme. The proof consists of the following hybrids:(1)
Firstly, we alter each of the ciphertextsVi,1x,y,b,Vi,2x,y,b, where x∈t,y∈m,b∈rl so that, instead of being GSW ciphertexts of Riy,b, we change them to GSW ciphertexts of 0. It follows from the semantic security of GSW encryption which is based solely on the DLWE assumption.(2)
After the first step, no information about the encryption randomnessRi is given out. Then, we choose C¯i as a GSW ciphertext of 0. It also follows from the semantic security of GSW encryption.(3)
Finally, the distribution is totally irrelevant to the plaintext bitμ, which completes the proof.Then, let us consider the compression rate of our construction. Recall thatt=t′−1N is the compression parameter. In order to achieve a compression rate of 1−ε for some small ε>0, it is sufficient to set t′=Δ2/ε, so that the compression rate(34)γ=n·nn¯·n¯=t′−1t′2≥1−ε.Thus, we need(35)βχ·polyrNε=βComp≤q1/t′2=qε/22.Settingβχ≤polyrN/ε, we need q=polyrN/εΘ1/ε. This means that the semantic security of our construction is based on approximation lattices problems with gap polyrN/εΘ1/ε. In particular, if we view the compression rate γ and maximal number of parties involved N as constants, then the hardness is only based on ones with polynomial gap. Formally, we have the following theorem.Theorem 2.
For anyε=ελ>0, there exists a rate-1−ε compressible multikey fully homomorphic scheme that is semantically secure assuming the hardness of approximate lattices problems with gap polyλN/ε1/ε.


## 3.1. Compressible Multikey FHE

We begin with the definition of compressible MKFHE, which is adapted from the definitions of compressible FHE in [23] and MKFHE in [7].Definition 3.
A compressible multikey fully homomorphic encryption scheme consists of seven PPT algorithmsSetup,KeyGenerate,Encrypt,Expand,Evaluate,Compress and Decrypt defined as follows:Setup1λ,1N: Take a security parameter λ and a bound N on the number of users involved as inputs and output parameters params. params is taken in as an input in all of the following algorithms; thus, we just omit it.KeyGenparams,i∈N: Output a secret key SKi and a public key PKi for the ith user.EncPKi,μ∈0,1: Take a public key PKi and a bit μ∈0,1 as inputs, and output a fresh low-rate ciphertext ci .ExpPKjj∈N,ci: Take public keys PKjj∈N and a fresh ciphertext ci under the ith public key as inputs; and compute and output an expanded low-rate ciphertext c^ under N’s public keys PK1,PK2,…,PKN.Evalf,c^=c^ii∈t: Take a circuit f and a vector of expanded ciphertexts c^=c^1,c^2,…,c^t as inputs, corresponding to each input bit of f, and output another vector of evaluated low-rate ciphertext c^′=c^1′,c^2′,…,c^t′, corresponding to each output bit of f.Compc^=c^ii∈t: Take a vector of expanded or evaluated low-rate ciphertexts c^=c^1,c^2,…,c^t as inputs, and output one or more compressed high-rate ciphertext(s) c∗=ci∗i∈s.DecSKii∈N,c∗: Take N secret keys SK1,SK2,…,SKN, corresponding to identities id1,id2,…,idN, and the compressed ciphertext(s) c∗ as inputs, and output a vector of message bits m=μii∈t corresponding to c^ii∈t.
The scheme is said to be correct if, for every allowed circuitf and a vector of message bits m=μ1,…,μt∈0,1t corresponding to each input bit of f, it holds that(9)DecSKii∈N,CompEvalf,c^=c^ii∈t=m,where each c^i=ExpPKjj∈N,EncPKk,μi∈0,1.
Using the parameters described above, the scheme is said to have a compression rate of1−ε for any ε>0 if, for every allowed circuit f that has sufficiently long outputs, the compression rate(10)γ=mCompEvalf,c^=c^ii∈t≥1−ε.
The semantic security definition for compressible multikey fully homomorphic encryption is the same as that for multikey fully homomorphic encryption, which is the same as that for single-key fully homomorphic encryption because all of parameters used in the expansion and compression algorithms are public and thus do not compromise security. In particular, given a security parameterλ and a bound N on the number of users involved, the following distributions are computationally indistinguishable:(11)params,PKi,EncPKi,0≈compparams,PKi,EncPKi,1,where params←Setup1λ,1N and SKi,PKi←KeyGenparams,i∈N. We do not consider the distributed decryption for our MKFHE scheme, which can be used to construct round-efficient secure multiparty computation protocols, and instead put the main focus on the compressible expansion algorithm.


## 3.2. Our Construction

C-MKFHE.Setup1λ,1N: Choose a lattice dimension parameter r=polyλ,N, a sufficiently large modulus q, a βχ-bounded error distribution χ=χλ,N, and a compression parameter t=Δt′−1N. The parameter t′ will be specified in Subsection 3.3.2. All of the rows of the nearly square gadget matrix H′∈ℤqt′−1×t′ span the kernel space of its public trapdoor matrix F′∈ℤqt′×t′ having the properties stated in 2.4. Let ℓ=Δ⌈logq⌉, n=Δtr, n¯=Δt+Nr, m=Δt+1rℓ, and m¯=Δt+Nrℓ. Then, set H=ΔH′⊗IrN∈ℤqn×n¯ and F=ΔF′⊗IrN∈ℤqn¯×n¯. Choose a random matrix B←$ℤqr×m. Output params=r,N,q,ℓ,βχ,χ,t′,t,n,n¯,m,m¯,H,H′,F,F′,B.C-MKFHE.KeyGen(params): Choose random matrices S←$ℤqtr×r and E←χtr×m. Compute A=SB+E. Let the secret key and public key be SK=ΔS¯=ΔItrS∈ℤqtr×t+1r and PK=ΔA¯=Δ−AB∈ℤqt+1r×m. Note that S¯A¯=E. Output PK,SK.C-MKFHE.Enc(params,PKi,μ∈0,1): Given a message bit μ, randomly select a matrix R¯i←$0,1m×m. Set(12)C¯i=ΔμGt+1r+A¯iR¯i∈ℤqt+1r×m.Then, partitionC¯i as follows:(13)C¯i=ΔC¯i1,1C¯i1,2C¯i2,1C¯i2,2,whereC¯i1,1∈ℤqtr×trℓ,C¯i1,2∈ℤqtr×rℓ,C¯i2,1∈ℤqr×trℓ,C¯i2,2∈ℤqr×rℓ. Let Ri∈0,1m×rℓ be the last rℓ columns of R¯i. Note that(14)C¯i2,2=μGr+BRi∈ℤqr×rℓ.Forx∈t,y∈m,b∈rl, compute(15)Vi,1x,y,b=−AiR˜ix,y,b+Riy,bGmx∈ℤqtr×rℓ;Vi,2x,y,b=BR˜ix,y,b∈ℤqr×rℓ,whereR˜ix,y,b←$0,1m×rℓ and Grx=0x−1r×rℓGr0t−xr×rℓ∈ℤtr×rℓ.Set(16)Ui=ΔVi,1x,y,b,Vi,2x,y,bx∈t,y∈m,b∈rl.Output a tuple of encryptionCIPHERi=ΔC¯i,Ui.C-MKFHE.Exp(params,PKii∈N,CIPHERi): For every j∈N\i,x∈t,y∈n,b∈ml, compute(17)Zi,jx,y,bz1,z2=Δ−Ajz1+xr,y,ifz2=b,0,otherwise,that is,Zi,jx,y,b=Δ∑z1=1r−Ajz1+xr,y·Ez1,b′∈ℤqr×rℓ, where Ez1,b′ is an r×rℓ matrix that has 1 in the z1th row and the bth column and 0’s in all other entries. Set(18)Z¯i,jx,y,b=Δ0x−1r×rℓZi,jx,y,b0t−xr×rℓ∈ℤqtr×rℓ.Compute(19)Xi,j1=Δ∑x=1t∑y=1m∑b=1rlVi,1x,y,b·Gr−1Zi,jx,y,b∈ℤqtr×rℓ;Xi,j2=Δ∑x=1t∑y=1m∑b=1rlVi,2x,y,b·Gr−1Zi,jx,y,b∈ℤqr×rℓ.Finally, expand a fresh ciphertext to an expanded one.(20)C^i=ΔC¯i1,1Xi,11⋯C¯i1,2⋯Xi,N1C¯i2,2⋱C¯i2,1Xi,12⋯C¯i2,2⋯Xi,N2⋱C¯i2,2∈ℤqn¯×m¯.OutputC^i.C-MKFHE.Compparams,C^u,v,ωu,v∈n,ω∈ℓ: In this algorithm, a series of low-rate expanded (or evaluated) ciphertexts are compressed into a high-rate ciphertext. Let Tu,v=ΔEu,v′0Nr×n∈ℤn¯×n , where Eu,v′ is an n×n matrix that has 1 in the uth row and the vth column and 0’s in all other entries. Set the compressed ciphertext as(21)C∗=Δ∑u∈n∑v∈n∑ω∈ℓC^u,v,ω·Gn¯−12ωTu,v×H∈ℤqn¯×n¯.Note that the nearly square gadget matrixH∈ℤqn×n¯ and its public trapdoor F∈ℤqn¯×n¯ play a significant role in the compression and compressed decryption algorithms.C-MKFHE.CompDecparams,C∗,SKii∈N: Given a compressed ciphertext C∗, set the combined key S^=ΔItr,S1,…,SN∈ℤn×n¯. The compressed decryption is composed of four steps:(1)
Z=ΔS×C∗ (mod q);(2)
Y=ΔZ×F (mod q), where F∈ℤqn¯×n¯ is the public trapdoor matrix;(3)
X=ΔY×F−1 (note that F is full rank over R);(4)
M′=ΔZ−X×H−1 (mod q) (note that H is a row full-rank matrix modulo q, so that there exists a matrix H−1∈ℤqn¯×n such that H×H−1=In).C-MKFHE.NANDparams,C^1,C^2: Given two expanded ciphertext matrices C^1,C^2 for two plaintexts μ1,μ2, homomorphic NAND operation is defined as(22)C^NAND=ΔGn¯−C^1·Gn¯−1C^2.OutputC^NAND. Observe that Gx−1· is randomized, and so is this algorithm.C-MKFHE.Evalparams,f,C^1,C^2,…,C^s: An NAND-circuit f:0,1t⟶0,1 is applied to a set of ciphertexts C^1,C^2,…,C^s, which leads to a ciphertext C^f.


## 3.3. Setting the Parameters

In this subsection, the correctness, homomorphic properties, security, and compression rate of the proposed compressible MKFHE are analyzed. If we use a somewhat (or leveled) version without bootstrapping, then the error bound is dependent on the maximal multiplication depth of allowed evaluated functions. In this paper, we would like to give an asymptotic analysis of various parameters of a fully homomorphic one with bootstrapping so that all ciphertexts before being packed have an error bound similar to that of freshly expanded ciphertexts.


### 3.3.1. Correctness and Homomorphism

The correctness of compressed decryption may be less obvious, since the encryption and expansion algorithms are quite different from previous ones. During encryption, it holds that(23)S¯i×C¯i=μS¯iGt+1r+EiR¯i∈ℤqn×m,because S¯iA¯i=Ei.Besides, for the additional helper information matrices, we have(24)Sj×C¯i2,2=μSjGr+AjRi−EjRi∈ℤqn×rℓ;Itr×Vi,1x,y,b=−AiR˜ix,y,b+Riy,bGrx∈ℤqn×rℓ;Si×Vi,2x,y,b=Ai−EiR˜ix,y,b∈ℤqn×rℓ,because Ai−Ei=SiB.During the expansion algorithm, those weird matricesXi,j1 and Xi,j2 are customized to eliminate the undesired AjRi in SjC¯i2,2. In particular, we have(25)Itr×Xi,j1=∑x=1t∑y=1m∑b=1rlVi,1x,y,b·Gr−1Zi,jx,y,b=∑x=1t∑y=1m∑b=1rlAiR˜ix,y,bGr−1Zi,jx,y,b+Riy,bZ¯i,jx,y,b¯=∑x=1t∑y=1m∑b=1rlAiR˜ix,y,bGr−1Zi,jx,y,b−AjRi¯,(26)Si×Xi,j2=∑x=1t∑y=1n∑b=1mlSiVi,2x,y,b·Gr−1Zix,y,b=∑x=1t∑y=1n∑b=1mlAi−EiR˜ix,y,b·Gr−1Zi,jx,y,b.The underlined part can be a tricky step. We now analyze it as follows:(27)∑y=1m∑b=1rlRiy,b∑x=1tZ¯i,jx,y,b=∑y=1m∑b=1rlRiy,b∑a=1tr−Aja,y×Ea,b′=∑a=1tr∑y=1m∑b=1rl−Aja,y·Riy,b×Ea,b′=−AjRi,where Ea,b′ is an tr×rℓ matrix that has 1 in the ath row and the bth column and 0’s in all other entries.Thus, for any expanded ciphertext, we have(28)S^×C^i=C¯i1,1+SiC¯i2,1Xi,11+S1C¯i2,2+SiXi,j2⋯C¯i1,2+SiC¯i2,2⋯Xi,N1+SNC¯i2,2+SiXi,N2∈ℤn×m¯.There are only two types of all blocks in the above seemingly cumbersome matrix. The first comes from equation (23) by partitioning(29)ItrSi×C¯i1,1C¯i1,2C¯i2,1C¯i2,2=μItrGtrSiGr+EiR¯i=ΔμItrGtr+E˜0μSiGr+E˜i∈ℤqn×m.The second comes from equations (24)–(26):(30)SjC¯i2,2+Xi,j1+SiXi,j2=μSjGr−EjRi−∑x=1t∑y=1n∑b=1mlEiR˜ix,y,bGr−1Zi,jx,y,b=ΔμSjGr+E˜j∈ℤqn×rℓ.Finally, we get the most important decryption invariant in all GSW-like encryption from equations (28)–(30):(31)S^×C^i=μItrGtr+E˜0μS1Gr+E˜1⋯μSNGr+E˜N=ΔμS^Gn¯+E^∈ℤqn×m¯.In terms of the error bound, we haveβExp=Δm4βχ; that is, maxa,bE^a,b<βExp with overwhelming probability.With equation (31) in mind, everything turns familiar again. Homomorphic properties are obvious, and one can find them in most GSW-like FHE (or MKFHE) schemes. Thus, we just omit them here.On the other hand, the correctness of compressed decryption also turns obvious. According to equation (31), we have(32)S^×C∗=∑u∈n∑v∈n∑ω∈ℓS^C^u,v,ω×Gn¯−12ω·Tu,vH=∑u,v,ωμu,v,ωS^Gn¯+E^Gn¯−12ω·Tu,vH=Δ∑u,v,ω2ωμu,v,ωS^Tu,vH+E∗=∑u,v,ω2ωμu,v,ωEu,v′H+E∗=ΔMH+E∗∈ℤqn×n¯,where Eu,v′ is an n×n matrix that has 1 in the uth row and the vth column and 0’s in all other entries and M∈ℤqn×n is a compressed plaintext matrix that can be obtained from Z=ΔS^×C∗=MH+E∗, by using Gentry and Halevi’s idea of the nearly square gadget matrix, which was briefly described in 2.4. That is,(1)
Y=ΔZ×F=E∗F (mod q), where F∈ℤqn¯×n¯ is the public trapdoor matrix;(2)
X=ΔY×F−1=E∗ (note that F is full rank over R);(3)
M′=ΔZ−X×H−1=M (mod q) (note that H is a row full-rank matrix modulo q, so that there exists a matrix H−1∈ℤqn¯×n such that H×H−1=In).The matrixM′ is the desired one if every entry of E∗F does not wrap around ℤq; that is, E∗Fmodq=E∗F over the integers. As for the error bound, we have βComp=Δm¯m2βExp; that is, maxa,bE∗a,b<βComp with overwhelming probability. On the other hand, by the construction of the public trapdoor matrix F, it is required that βComp≤q1/t′.


### 3.3.2. Security and Compression Rate

It remains to show the security level and compression rate of our construction.The additional expansion and compression algorithms are public and do not compromise security. The key-generation algorithm is basically the same as that of the underlying GSW-FHE scheme. In addition, during the encryption procedure, a fresh ciphertext for theith user CIPHERi consists of two parts C¯i and Vi,1x,y,b,Vi,2x,y,b, of which randomness matrices are mutually independent, all in a similar encryption form. Exploiting a standard hybrid analysis, one can easily verify that the semantic security of our compressible MKFHE is based solely on the DLWE assumption.The view of the attacker is the following distribution:(33)params,PKi,C¯i,Ui=Vi,1x,y,b,Vi,2x,y,bx∈t,y∈m,b∈rl,generated via params←C−MKFHE⋅Setup1λ,1N, PKi,SKi←C−MKFHE⋅KeyGenparams, and C¯i,Ui←C−MKFHE⋅Encparams,PKi,μ, where μ∈0,1.We prove the semantic security of our construction by relying on the semantic security of the underlying matrix version of GSW-FHE scheme. The proof consists of the following hybrids:(1)
Firstly, we alter each of the ciphertextsVi,1x,y,b,Vi,2x,y,b, where x∈t,y∈m,b∈rl so that, instead of being GSW ciphertexts of Riy,b, we change them to GSW ciphertexts of 0. It follows from the semantic security of GSW encryption which is based solely on the DLWE assumption.(2)
After the first step, no information about the encryption randomnessRi is given out. Then, we choose C¯i as a GSW ciphertext of 0. It also follows from the semantic security of GSW encryption.(3)
Finally, the distribution is totally irrelevant to the plaintext bitμ, which completes the proof.Then, let us consider the compression rate of our construction. Recall thatt=t′−1N is the compression parameter. In order to achieve a compression rate of 1−ε for some small ε>0, it is sufficient to set t′=Δ2/ε, so that the compression rate(34)γ=n·nn¯·n¯=t′−1t′2≥1−ε.Thus, we need(35)βχ·polyrNε=βComp≤q1/t′2=qε/22.Settingβχ≤polyrN/ε, we need q=polyrN/εΘ1/ε. This means that the semantic security of our construction is based on approximation lattices problems with gap polyrN/εΘ1/ε. In particular, if we view the compression rate γ and maximal number of parties involved N as constants, then the hardness is only based on ones with polynomial gap. Formally, we have the following theorem.Theorem 2.
For anyε=ελ>0, there exists a rate-1−ε compressible multikey fully homomorphic scheme that is semantically secure assuming the hardness of approximate lattices problems with gap polyλN/ε1/ε.


## 3.3.1. Correctness and Homomorphism

The correctness of compressed decryption may be less obvious, since the encryption and expansion algorithms are quite different from previous ones. During encryption, it holds that(23)S¯i×C¯i=μS¯iGt+1r+EiR¯i∈ℤqn×m,because S¯iA¯i=Ei.Besides, for the additional helper information matrices, we have(24)Sj×C¯i2,2=μSjGr+AjRi−EjRi∈ℤqn×rℓ;Itr×Vi,1x,y,b=−AiR˜ix,y,b+Riy,bGrx∈ℤqn×rℓ;Si×Vi,2x,y,b=Ai−EiR˜ix,y,b∈ℤqn×rℓ,because Ai−Ei=SiB.During the expansion algorithm, those weird matricesXi,j1 and Xi,j2 are customized to eliminate the undesired AjRi in SjC¯i2,2. In particular, we have(25)Itr×Xi,j1=∑x=1t∑y=1m∑b=1rlVi,1x,y,b·Gr−1Zi,jx,y,b=∑x=1t∑y=1m∑b=1rlAiR˜ix,y,bGr−1Zi,jx,y,b+Riy,bZ¯i,jx,y,b¯=∑x=1t∑y=1m∑b=1rlAiR˜ix,y,bGr−1Zi,jx,y,b−AjRi¯,(26)Si×Xi,j2=∑x=1t∑y=1n∑b=1mlSiVi,2x,y,b·Gr−1Zix,y,b=∑x=1t∑y=1n∑b=1mlAi−EiR˜ix,y,b·Gr−1Zi,jx,y,b.The underlined part can be a tricky step. We now analyze it as follows:(27)∑y=1m∑b=1rlRiy,b∑x=1tZ¯i,jx,y,b=∑y=1m∑b=1rlRiy,b∑a=1tr−Aja,y×Ea,b′=∑a=1tr∑y=1m∑b=1rl−Aja,y·Riy,b×Ea,b′=−AjRi,where Ea,b′ is an tr×rℓ matrix that has 1 in the ath row and the bth column and 0’s in all other entries.Thus, for any expanded ciphertext, we have(28)S^×C^i=C¯i1,1+SiC¯i2,1Xi,11+S1C¯i2,2+SiXi,j2⋯C¯i1,2+SiC¯i2,2⋯Xi,N1+SNC¯i2,2+SiXi,N2∈ℤn×m¯.There are only two types of all blocks in the above seemingly cumbersome matrix. The first comes from equation (23) by partitioning(29)ItrSi×C¯i1,1C¯i1,2C¯i2,1C¯i2,2=μItrGtrSiGr+EiR¯i=ΔμItrGtr+E˜0μSiGr+E˜i∈ℤqn×m.The second comes from equations (24)–(26):(30)SjC¯i2,2+Xi,j1+SiXi,j2=μSjGr−EjRi−∑x=1t∑y=1n∑b=1mlEiR˜ix,y,bGr−1Zi,jx,y,b=ΔμSjGr+E˜j∈ℤqn×rℓ.Finally, we get the most important decryption invariant in all GSW-like encryption from equations (28)–(30):(31)S^×C^i=μItrGtr+E˜0μS1Gr+E˜1⋯μSNGr+E˜N=ΔμS^Gn¯+E^∈ℤqn×m¯.In terms of the error bound, we haveβExp=Δm4βχ; that is, maxa,bE^a,b<βExp with overwhelming probability.With equation (31) in mind, everything turns familiar again. Homomorphic properties are obvious, and one can find them in most GSW-like FHE (or MKFHE) schemes. Thus, we just omit them here.On the other hand, the correctness of compressed decryption also turns obvious. According to equation (31), we have(32)S^×C∗=∑u∈n∑v∈n∑ω∈ℓS^C^u,v,ω×Gn¯−12ω·Tu,vH=∑u,v,ωμu,v,ωS^Gn¯+E^Gn¯−12ω·Tu,vH=Δ∑u,v,ω2ωμu,v,ωS^Tu,vH+E∗=∑u,v,ω2ωμu,v,ωEu,v′H+E∗=ΔMH+E∗∈ℤqn×n¯,where Eu,v′ is an n×n matrix that has 1 in the uth row and the vth column and 0’s in all other entries and M∈ℤqn×n is a compressed plaintext matrix that can be obtained from Z=ΔS^×C∗=MH+E∗, by using Gentry and Halevi’s idea of the nearly square gadget matrix, which was briefly described in 2.4. That is,(1)
Y=ΔZ×F=E∗F (mod q), where F∈ℤqn¯×n¯ is the public trapdoor matrix;(2)
X=ΔY×F−1=E∗ (note that F is full rank over R);(3)
M′=ΔZ−X×H−1=M (mod q) (note that H is a row full-rank matrix modulo q, so that there exists a matrix H−1∈ℤqn¯×n such that H×H−1=In).The matrixM′ is the desired one if every entry of E∗F does not wrap around ℤq; that is, E∗Fmodq=E∗F over the integers. As for the error bound, we have βComp=Δm¯m2βExp; that is, maxa,bE∗a,b<βComp with overwhelming probability. On the other hand, by the construction of the public trapdoor matrix F, it is required that βComp≤q1/t′.


## 3.3.2. Security and Compression Rate

It remains to show the security level and compression rate of our construction.The additional expansion and compression algorithms are public and do not compromise security. The key-generation algorithm is basically the same as that of the underlying GSW-FHE scheme. In addition, during the encryption procedure, a fresh ciphertext for theith user CIPHERi consists of two parts C¯i and Vi,1x,y,b,Vi,2x,y,b, of which randomness matrices are mutually independent, all in a similar encryption form. Exploiting a standard hybrid analysis, one can easily verify that the semantic security of our compressible MKFHE is based solely on the DLWE assumption.The view of the attacker is the following distribution:(33)params,PKi,C¯i,Ui=Vi,1x,y,b,Vi,2x,y,bx∈t,y∈m,b∈rl,generated via params←C−MKFHE⋅Setup1λ,1N, PKi,SKi←C−MKFHE⋅KeyGenparams, and C¯i,Ui←C−MKFHE⋅Encparams,PKi,μ, where μ∈0,1.We prove the semantic security of our construction by relying on the semantic security of the underlying matrix version of GSW-FHE scheme. The proof consists of the following hybrids:(1)
Firstly, we alter each of the ciphertextsVi,1x,y,b,Vi,2x,y,b, where x∈t,y∈m,b∈rl so that, instead of being GSW ciphertexts of Riy,b, we change them to GSW ciphertexts of 0. It follows from the semantic security of GSW encryption which is based solely on the DLWE assumption.(2)
After the first step, no information about the encryption randomnessRi is given out. Then, we choose C¯i as a GSW ciphertext of 0. It also follows from the semantic security of GSW encryption.(3)
Finally, the distribution is totally irrelevant to the plaintext bitμ, which completes the proof.Then, let us consider the compression rate of our construction. Recall thatt=t′−1N is the compression parameter. In order to achieve a compression rate of 1−ε for some small ε>0, it is sufficient to set t′=Δ2/ε, so that the compression rate(34)γ=n·nn¯·n¯=t′−1t′2≥1−ε.Thus, we need(35)βχ·polyrNε=βComp≤q1/t′2=qε/22.Settingβχ≤polyrN/ε, we need q=polyrN/εΘ1/ε. This means that the semantic security of our construction is based on approximation lattices problems with gap polyrN/εΘ1/ε. In particular, if we view the compression rate γ and maximal number of parties involved N as constants, then the hardness is only based on ones with polynomial gap. Formally, we have the following theorem.Theorem 2.
For anyε=ελ>0, there exists a rate-1−ε compressible multikey fully homomorphic scheme that is semantically secure assuming the hardness of approximate lattices problems with gap polyλN/ε1/ε.


## 4. Compressible Multi-Identity Fully Homomorphic Encryption

In this section, we propose the first compressible MIFHE scheme. All of the new techniques and analyses are similar to what we have done when constructing compressible MKFHE scheme.


### 4.1. Compressible Multi-Identity FHE

Similarly, we begin with the definition of the compressible MIFHE.Definition 4.
A compressible multi-identity fully homomorphic encryption scheme consists of seven PPT algorithmsSetup,Extract,Encrypt,Expand,Evaluate,Compress and Decrypt defined as follows:Setup1λ,1N: Take a security parameter λ and a bound N on the number of identities involved as inputs, generate a master public key MPK and a master secret key MSK, and output MPK,MSK. MPK is taken in as an input in all of the following algorithms; thus, we just omit it. The security parameter λ also defines an identity space ℐ.ExtMSK,id: Take the master secret key MSK and an identity id∈ℐ as inputs; and extract and output a user-specific secret key SKid for id.Encid,μ∈0,1: Take an identity id∈ℐ and a bit μ∈0,1 as inputs, and output a fresh low-rate ciphertext cid under the identity id.Expidjj∈N,ci: Take identities idjj∈N and a fresh ciphertext ci under the ith identity idi as inputs; and compute and output an expanded low-rate ciphertext c^i under N’s identities id1,id2,…,idN.Evalf,c^=c^ii∈t: Take a circuit f and a vector of expanded ciphertexts c^=c^1,c^2,…,c^t as inputs, corresponding to each input bit of f, and output another vector of evaluated low-rate ciphertext c^=c^1′,c^2′,…,c^t′, corresponding to each output bit of f.Compc^=c^ii∈t: Take a vector of expanded or evaluated low-rate ciphertexts c^=c^1,c^2,…,c^t as inputs, and output one or more compressed high-rate ciphertext(s) c∗=ci∗i∈s.DecSKidii∈N,c∗: Take N secret keys SKid1,SKid2,…,SKidN, corresponding to identities id1,id2,…,idN as inputs, as well as the compressed ciphertext(s) c∗, and output a vector of message bits m=μii∈t corresponding to c^ii∈t.
The definitions of correctness and compression rate are exactly the same as those of the compressible MKFHE in Section3.1. The selective security definition for compressible multi-identity fully homomorphic encryption is the same as that for multi-identity fully homomorphic encryption, which is the same as that for identity-based encryption. We do not consider the distributed decryption for our MIFHE scheme, which can be used to construct round-efficient secure multiparty computation protocols, and instead put the main focus on the compressible expansion algorithm.


### 4.2. Public Parameters

Before giving our construction of the first compressible MIFHE scheme, we first describe some public parameters that will be used throughout the rest of this section.(i)
LetN be the maximum number of identities the scheme can support. The integer n=polyλ,N is a lattice dimension parameter. The modulus q is a sufficiently large number. Let ℓ=⌈logq⌉, m0=nℓ+O1, m1=nℓ, and m=m0+m1.(ii)
Given any matrixA∈ℤqx×y, by Lemma 2, there exists an efficiently randomized algorithm that samples a sub-Gaussian matrix X with some constant parameter O1 over ℤxℓ×y such that X=Gx−1A.(iii)
LetD be the distribution over −1,0,1 as defined in Subsection 2.1, such that A0,A0R is negln-far from U0,U1←$ℤqn×m0×ℤqn×m1 for A0←$ℤqn×m0 and R←Dm0×m1. For more information, please refer to [26].(iv)
Every identity is assumed to have a counterpart element inGFqn. H:GFqn⟶ℤqn×n is said to be an invertible difference, if H is computable in polynomial time in nℓ and Hid1−Hid2 is invertible for any two different identities id1,id2. For more information, please refer to [15].(v)
The LWE error rateα should be sufficiently large satisfying αq≥2n for the sake of security.(vi)
Lett=Δt′−1N be the compression parameter. The parameter t′ will be specified in Subsection 4.4.2, All of the rows of the nearly square gadget matrix H′∈ℤqt′−1×t′ span the kernel space of its public trapdoor matrix F′∈ℤqt′×t′ having the properties stated in 2.4. Then, set H=ΔH′⊗ImN∈ℤqtm×t+Nm and F=ΔF′⊗ImN∈ℤqt+Nm×t+Nm.


### 4.3. Our Construction

C-MIFHE.Setup1λ,1N: Choose A0←$ℤqn×m0, U←$ℤqn×tm, and R←Dm0×m1. Let A=A0−A0R∈ℤqn×m. Let the master secret key and the master public key be MSK=R and MPK=UA. Output params=n,N,q,ℓ,t′,t,m0,m1,m,H,H′,F,F′,mpk,msk.C-MIFHE.Ext(params,mpk,msk,idi|i∈N): Given idi∈ℤqn, compute Hidi and set Ai=A0−A0R+Hidi·Gn∈ℤqn×m. Sample vectors sik∈ℤm for k∈tm with small entries satisfying Ai·sik=uk by running the algorithm SampleDR,A0,Hidi,uk,R2. Set SiT=si1,…,sitm∈ℤqm×tm. Let the secret key and public key for i be SKi=S¯i=ItmSi∈ℤqtm×t+1m and PKi=P¯i=U−Ai∈ℤqn×t+1m. Note that S¯i·P¯iT=0. Output PKi,SKii∈N.C-MIFHE.Enc(params,PKidi,idi,μ∈0,1): Given a message bit μ, randomly select two matrices Y¯i←$ℤqn×t+1mℓ and Ei=−Ei0−Ei1Ei2∈ℤt+1m×t+1mℓ, where Ei0←Dℤ,αqtm×t+1mℓ, Ei1=ei1,1,ei1,2,…,ei1,t+1mℓ←Dℤ,αqm0×t+1mℓ, and Ei2=ei2,1,ei2,2,…,ei2,t+1mℓ, where ei2,j←Dℤ,sjm1 for sj2=ei1,j22+m0αq2·ωlogn2. Set(36)C¯i=μGt+1m+P¯iTY¯i+Ei∈ℤqt+1m×t+1mℓ.Remark 1.
The setting of error parameters, especiallyEi2, plays a critical role in the security proof. For more information, please refer to [30, 31].
Then, partitionC¯i as follows:(37)C¯i=ΔC¯i1,1C¯i1,2C¯i2,1C¯i2,2,where C¯i1,1∈ℤqtm×tmℓ,C¯i1,2∈ℤqtm×mℓ,C¯i2,1∈ℤqm×tmℓ,C¯i2,2∈ℤqm×mℓ.
For everyj∈N\i, randomly select two matrices Yi,j←$ℤqn×mℓ and Ei,j=−Ei,j1Ei,j2∈ℤm×mℓ, where Ei,j1=ei,j1,1,ei,j1,2,…,ei,j1,mℓ←Dℤ,αqm0×mℓ, and Ei,j2=ei,j2,1,ei,j2,2,…,ei,j2,mℓ, where ei,j2,k←Dℤ,skm1 for sk2=ei,j1,k22+m0αq2·ωlogn2. Set(38)Ci,j=μGm+AjTYi,j+Ei,j∈ℤqm×mℓ.
Then, decompose the matrixYi,j that has every entry in ℤq to matrices in binary representation Yi,j=Δ∑k=0logq2k·Yi.jk, where Yi,jk∈0,1n×mℓ.
Forx∈t,y∈n,b∈ml,k+1∈ℓ, compute(39)Vi,j,1x,y,b,k=UTYi,jx,y,b,k+Ei,j,1x,y,b,k+Yi,jky,bGmx∈ℤqtm×mℓ;Vi,j,2x,y,b,k=AiTYi,jx,y,b,k+Ei,j,2x,y,b,k∈ℤqm×mℓ,where Yi,jx,y,b,k←$ℤqn×mℓ, Ei,j,2x,y,b,k∈ℤm×mℓ is extracted from the same distribution of Ei,j, and Ei,j,1x,y,b,k=−Ei,j,1x,y,b,k,0Ei,j,1x,y,b,k,1∈ℤtm×mℓ, where Ei,j,1x,y,b,k,0←Dℤ,αqt−1m×mℓ and Ei,j,1x,y,b,k,1∈ℤm×mℓ is extracted from the same distribution of Ei,j,2x,y,b,k, and Gmx=0x−1m×mℓGm0t−xm×mℓ∈ℤtm×mℓ.
SetUi=ΔCi,j,Vi,j,1x,y,b,k,Vi,j,2x,y,b,k, where j∈N\i,x∈t,y∈n,b∈ml,k+1∈ℓ. Output a tuple of encryption CIPHERi=ΔC¯i,Ui.C-MIFHE.Exp(params,idii∈N,CIPHERi): For every j∈N\i,x∈t,y∈n,b∈ml,k+1∈ℓ, compute(40)Zi,jx,y,bz1,z2=Δ−Ajz1+xr,y,ifz2=b,0,otherwise,that is,Zi,jx,y,b,k=Δ∑z1=1m2kUTz1+xm,y·Ez1,b′∈ℤqm×mℓ, where Ez1,b′ is an m×mℓ matrix that has 1 in the z1th row and the bth column and 0’s in all other entries. Set(41)Z¯i,jx,y,b=Δ0x−1r×rℓZi,jx,y,b0t−xr×rℓ∈ℤqtr×rℓ.Compute(42)Xi,j1=Δ∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1Vi,j,1x,y,b,k·Gm−1Zi,jx,y,b,k∈ℤqtm×mℓ;Xi,j2=Δ∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1Vi,j,2x,y,b,k·Gm−1Zi,jx,y,b,k∈ℤqm×mℓ.Finally, expand a fresh ciphertext to an expanded one.(43)C^i=ΔC¯i1,1−Xi,11⋯C¯i1,2⋯−Xi,N1Ci,1⋱C¯i2,1Xi,12⋯C¯i2,2⋯Xi,N2⋱Ci,N∈ℤqt+Nm×t+Nmℓ.OutputC^i.C-MIFHE.Compparams,C^u,v,ωu,v∈tm,ω∈ℓ: In this algorithm, a series of low-rate expanded (or evaluated) ciphertexts are compressed into a high-rate ciphertext. Let Tu,v=ΔEu,v′0Nm×tm∈ℤt+Nm×tm, where Eu,v′ is a tm×tm matrix that has 1 in the uth row and the vth column and 0’s in all other entries. Set the compressed ciphertext as(44)C∗=Δ∑u∈tm∑v∈tm∑ω∈ℓC^u,v,ω×Gt+Nm−12ω·Tu,v×H∈ℤqt+Nm×t+Nm.Note that the nearly square gadget matrixH∈ℤqtm×t+Nm and its public trapdoor F∈ℤqt+Nm×t+Nm play a significant role in the compression and compressed decryption algorithms.C-MIFHE.CompDecparams,C∗,SKii∈N: Given a compressed ciphertext C∗, set the combined key S^=ΔItm,S1,…,SN∈ℤtm×t+Nm. The compressed decryption is composed of four steps:(1)
Z=ΔS×C∗ (mod q);(2)
Y=ΔZ×F (mod q), where F∈ℤqt+Nm×t+Nm is the public trapdoor matrix;(3)
X=ΔY×F−1 (note that F is full rank over R);(4)
M′=ΔZ−X×H−1 (mod q) (note that H is a row full-rank matrix modulo q, so that there exists a matrix H−1∈ℤqt+Nm×tm such that H×H−1=Itm).C-MIFHE.NANDparams,C^1,C^2: Given two expanded ciphertext matrices C^1,C^2 for two plaintexts μ1,μ2, homomorphic NAND operation is defined as(45)C^NAND=ΔGt+Nm−C^1·Gt+Nm−1C^2.OutputC^NAND. Observe that Gx−1· is randomized, and so is this algorithm.C-MIFHE.Evalparams,f,C^1,C^2,…,C^s: An NAND-circuit f:0,1t⟶0,1 is applied to a set of ciphertexts C^1,C^2,…,C^s, which leads to a ciphertext C^f.


### 4.4. Setting the Parameters

In this subsection, the correctness, homomorphic properties, security, and compression rate of the proposed compressible MIFHE are analyzed. If we use a somewhat (or leveled) version without bootstrapping, then the error bound is dependent on the maximal multiplication depth of allowed evaluated functions. In this paper, we would like to give an asymptotic analysis of various parameters of a fully homomorphic one with bootstrapping, so that all ciphertexts before being packed have an error bound similar to that of freshly expanded ciphertexts.


#### 4.4.1. Correctness and Homomorphism

The correctness of compressed decryption may be less obvious, since the encryption and expansion algorithms are quite different from previous ones. During encryption, it holds that, for every identityidi and idjj≠i,(46)S¯i×C¯i=μS¯iGt+1m+S¯iEi∈ℤqtm×t+1mℓ,because S¯i×P¯iT=0. One can calculate the error bound βEnc=Δαqm0·ωlogn3; that is, maxa,bS¯iEia,b<βEnc with overwhelming probability.Besides, for the additional helper information matrices, we have(47)Sj×Ci,j=μSjGm+UTYi,j+SjEi,j∈ℤqtm×mℓ;Itm×Vi,j,1x,y,b,k=UTYi,jx,y,b,k+Ei,j,1x,y,b,k+Yi,jky,bGmx∈ℤqtm×mℓ;Si×Vi,j,2x,y,b,k=UTYi,jx,y,b,k+SiEi,j,2x,y,b,k∈ℤqtm×mℓ,because Sj×AjT=UT. Similarly, one can easily verify that, with overwhelming probability,(48)SjEi,ja,b,Ei,j,1x,y,b,kc,d,SiEi,j,2x,y,b,ke,f<βEnc.During the expansion algorithm, those weird matricesXi,j1 and Xi,j2 are customized to eliminate the undesired UTYi,j in SjCi,j. In particular, we have(49)Itm×Xi,j1=∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1Vi,j,1x,y,b,k·Gm−1Zi,jx,y,b,k=∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1UTYi,jx,y,b,kGm−1Zi,jx,y,b,k+Ei,j,1x,y,b,kGm−1Zi,jx,y,b,k+Yi,jky,bZ¯i,jx,y,b,k¯=∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1UTYi,jx,y,b,kGm−1Zi,jx,y,b,k+Ei,j,1x,y,b,kGm−1Zi,jx,y,b,k+UTYi,j¯,(50)Si×Xi,j2=∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1SiVi,j,2x,y,b,k·Gm−1Zi,jx,y,b,k=∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1UTYi,jx,y,b,kGm−1Zi,jx,y,b,k+SiEi,j,2x,y,b,kGm−1Zi,jx,y,b,k.The underlined part can be a tricky step. We now analyze it as follows:(51)∑y=1n∑b=1ml∑k=0ℓ−1Yi,jky,b∑x=1tZ¯i,jx,y,b,k=∑y=1n∑b=1ml∑k=0ℓ−1Yi,jky,b∑a=1tm2k·UTa,y×Ea,b′=∑a=1tm∑y=1n∑b=1mlUTa,y·Yi,jy,b×Ea,b′,=UTYi,j,where Ea,b′ is a tm×mℓ matrix that has 1 in the ath row and the bth column and 0’s in all other entries.Thus, for any expanded ciphertext, we have(52)S^×C^i=C¯i1,1+SiC¯i2,1−Xi,11+S1Ci,1+SiXi,j2⋯C¯i1,2+SiC¯i2,2⋯−Xi,N1+SNCi,N+SiXi,N2∈ℤtm×t+Nm.There are only two types of all blocks in the above seemingly cumbersome matrix. The first comes from equation (47) by partitioning(53)ItmSi×C¯i1,1C¯i1,2C¯i2,1C¯i2,2=μItmGtmSiGm+S¯iEi=ΔμItmGtm+E˜0μSiGm+E˜i∈ℤqtm×t+1mℓ.The second comes from equations (48), (49), and (51):(54)SjCi,j−Xi,j1+SiXi,j2=μSjGm+SjEi,j+∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1SiEi,j,2x,y,b,k−Ei,j,1x,y,b,kGm−1Zi,jx,y,b,k=ΔμSjGm+E˜j∈ℤqtm×mℓ.Finally, we get the most important decryption invariant in all GSW-like encryptions from equations (52)–(54).(55)S^×C^i=μItmGtm+E˜0μS1Gm+E˜1⋯μSNGm+E˜N=ΔμS^Gt+Nm+E^∈ℤqtm×t+Nmℓ.In terms of the error bound, we haveβExp=Δtnm2ℓ3βEnc; that is, maxa,bE^a,b<βExp with overwhelming probability.With equation (55) in mind, everything turns familiar again. Homomorphic properties are obvious, and one can find them in most GSW-like FHE (or MKFHE) schemes. Thus, we just omit them here.On the other hand, the correctness of compressed decryption also turns obvious. According to equation (55), we have(56)S^×C∗=∑u∈tm∑v∈tm∑ω∈ℓS^C^u,v,ω×Gt+Nm−12ω·Tu,vH=∑u,v,ωμu,v,ωS^Gt+Nm+E^Gt+Nm−12ω·Tu,vH=Δ∑u,v,ω2ωμu,v,ωS^Tu,vH+E∗=∑u,v,ω2ωμu,v,ωEu,v′H+E∗=ΔMH+E∗∈ℤqtm×t+Nm,where Eu,v′ is a tm×tm matrix that has 1 in the uth row and the vth column and 0’s in all other entries, and M∈ℤqtm×tm is a compressed plaintext matrix that can be obtained from Z=ΔS^×C∗=MH+E∗, by using Gentry and Halevi’s idea of the nearly square gadget matrix, which was briefly described in 2.4. That is,(1)
Y=ΔZ×F=E∗F (mod q), where F∈ℤqt+Nm×t+Nm is the public trapdoor matrix;(2)
X=ΔY×F−1=E∗ (note that F is full rank over R);(3)
M′=ΔZ−X×H−1=M (mod q) (note that H is a row full-rank matrix modulo q, so that there exists a matrix H−1∈ℤqt+Nm×tm such that H×H−1=Itm).The matrixM′ is the desired one if every entry of E∗F does not wrap around ℤq; that is, E∗Fmodq=E∗F over the integers. As for the error bound, we have βComp=Δt2t+Nm3ℓ2βExp, i.e., maxa,bE∗a,b<βComp with overwhelming probability. On the other hand, by the construction of the public trapdoor matrix F, it is required that βComp≤q1/t′.


#### 4.4.2. Security and Compression Rate

The security level and compression rate of our construction remain to be shown.The additional expansion and compression algorithms are public and do not compromise security. The key-extraction algorithm is similar to that of the underlying IBE in [15, 26] (ABB-IBE). In addition, during the encryption procedure, a fresh ciphertext for the ith user CIPHERi consists of three parts C¯i,Ci,j, and Vi,j,1x,y,b,k,Vi,j,2x,y,b,k, of which randomness matrices are mutually independent, all in a similar form. Exploiting a standard hybrid analysis, one can easily verify that the selective security of our compressible MIFHE is based solely on the DLWE assumption.The view of the attacker is the following distribution:params,MPK,PKi,C¯i,Ui=Ci,j,Vi,j,1x,y,b,k,Vi,j,2x,y,b,k, where j∈N\i,x∈t,y∈n,b∈ml,k+1∈ℓ generated via params,MPK,MSK←C−MIFHE⋅Setup1λ,1N, PKi,SKi←C−MIFHE⋅KeyGenparams, and C¯i,Ui←C−MIFHE⋅Encparams,PKi,μ, where μ∈0,1.We prove the selective security of our construction by relying on the selective security of the underlying ABB-IBE. The proof consists of the following hybrids:(1)
Firstly, we alter each of the ciphertextsVi,j,1x,y,b,k,Vi,j,2x,y,b,k, where j∈N\i,x∈t,y∈n,b∈ml,k+1∈ℓ, so that, instead of being ciphertexts of Yi,jky,b, we change them to ciphertexts of 0. It follows from the selective security of ABB-IBE, which is based solely on the DLWE assumption.(2)
After the first step, no information about the encryption randomnessYi,j is given out. Then, we choose C¯i,Ci,j as ciphertexts of 0. It also follows from the selective security of ABB-IBE.(3)
Finally, the distribution is totally irrelevant to the plaintext bitμ, which completes the proof.Then, let us consider the compression rate of our construction. Recall thatt=t′−1N is the compression parameter. In order to achieve a compression rate of 1−ε for some small ε>0, it is sufficient to set t′=Δ2/ε, so that the compression rate(57)γ=tm·tmt+Nm·t+Nm=t′−1t′2≥1−ε.Thus, we need(58)αq·polynNε=βComp≤q1/t′2=qε/22.Settingαq=2n, we need q=polynN/εΘ1/ε. This means that the selective security of our construction is based on approximation lattices problems with gap polynN/εΘ1/ε. In particular, if we view the compression rate γ and maximal number of parties involved N as constants, then the hardness is only based on ones with polynomial gap. Formally, we have the following theorem.Theorem 3.
For anyε=ελ>0, there exists a rate-1−ε compressible multi-identity fully homomorphic scheme that is selectively secure assuming the hardness of approximate lattices problems with gap polyλN/ε1/ε.


## 4.1. Compressible Multi-Identity FHE

Similarly, we begin with the definition of the compressible MIFHE.Definition 4.
A compressible multi-identity fully homomorphic encryption scheme consists of seven PPT algorithmsSetup,Extract,Encrypt,Expand,Evaluate,Compress and Decrypt defined as follows:Setup1λ,1N: Take a security parameter λ and a bound N on the number of identities involved as inputs, generate a master public key MPK and a master secret key MSK, and output MPK,MSK. MPK is taken in as an input in all of the following algorithms; thus, we just omit it. The security parameter λ also defines an identity space ℐ.ExtMSK,id: Take the master secret key MSK and an identity id∈ℐ as inputs; and extract and output a user-specific secret key SKid for id.Encid,μ∈0,1: Take an identity id∈ℐ and a bit μ∈0,1 as inputs, and output a fresh low-rate ciphertext cid under the identity id.Expidjj∈N,ci: Take identities idjj∈N and a fresh ciphertext ci under the ith identity idi as inputs; and compute and output an expanded low-rate ciphertext c^i under N’s identities id1,id2,…,idN.Evalf,c^=c^ii∈t: Take a circuit f and a vector of expanded ciphertexts c^=c^1,c^2,…,c^t as inputs, corresponding to each input bit of f, and output another vector of evaluated low-rate ciphertext c^=c^1′,c^2′,…,c^t′, corresponding to each output bit of f.Compc^=c^ii∈t: Take a vector of expanded or evaluated low-rate ciphertexts c^=c^1,c^2,…,c^t as inputs, and output one or more compressed high-rate ciphertext(s) c∗=ci∗i∈s.DecSKidii∈N,c∗: Take N secret keys SKid1,SKid2,…,SKidN, corresponding to identities id1,id2,…,idN as inputs, as well as the compressed ciphertext(s) c∗, and output a vector of message bits m=μii∈t corresponding to c^ii∈t.
The definitions of correctness and compression rate are exactly the same as those of the compressible MKFHE in Section3.1. The selective security definition for compressible multi-identity fully homomorphic encryption is the same as that for multi-identity fully homomorphic encryption, which is the same as that for identity-based encryption. We do not consider the distributed decryption for our MIFHE scheme, which can be used to construct round-efficient secure multiparty computation protocols, and instead put the main focus on the compressible expansion algorithm.


## 4.2. Public Parameters

Before giving our construction of the first compressible MIFHE scheme, we first describe some public parameters that will be used throughout the rest of this section.(i)
LetN be the maximum number of identities the scheme can support. The integer n=polyλ,N is a lattice dimension parameter. The modulus q is a sufficiently large number. Let ℓ=⌈logq⌉, m0=nℓ+O1, m1=nℓ, and m=m0+m1.(ii)
Given any matrixA∈ℤqx×y, by Lemma 2, there exists an efficiently randomized algorithm that samples a sub-Gaussian matrix X with some constant parameter O1 over ℤxℓ×y such that X=Gx−1A.(iii)
LetD be the distribution over −1,0,1 as defined in Subsection 2.1, such that A0,A0R is negln-far from U0,U1←$ℤqn×m0×ℤqn×m1 for A0←$ℤqn×m0 and R←Dm0×m1. For more information, please refer to [26].(iv)
Every identity is assumed to have a counterpart element inGFqn. H:GFqn⟶ℤqn×n is said to be an invertible difference, if H is computable in polynomial time in nℓ and Hid1−Hid2 is invertible for any two different identities id1,id2. For more information, please refer to [15].(v)
The LWE error rateα should be sufficiently large satisfying αq≥2n for the sake of security.(vi)
Lett=Δt′−1N be the compression parameter. The parameter t′ will be specified in Subsection 4.4.2, All of the rows of the nearly square gadget matrix H′∈ℤqt′−1×t′ span the kernel space of its public trapdoor matrix F′∈ℤqt′×t′ having the properties stated in 2.4. Then, set H=ΔH′⊗ImN∈ℤqtm×t+Nm and F=ΔF′⊗ImN∈ℤqt+Nm×t+Nm.


## 4.3. Our Construction

C-MIFHE.Setup1λ,1N: Choose A0←$ℤqn×m0, U←$ℤqn×tm, and R←Dm0×m1. Let A=A0−A0R∈ℤqn×m. Let the master secret key and the master public key be MSK=R and MPK=UA. Output params=n,N,q,ℓ,t′,t,m0,m1,m,H,H′,F,F′,mpk,msk.C-MIFHE.Ext(params,mpk,msk,idi|i∈N): Given idi∈ℤqn, compute Hidi and set Ai=A0−A0R+Hidi·Gn∈ℤqn×m. Sample vectors sik∈ℤm for k∈tm with small entries satisfying Ai·sik=uk by running the algorithm SampleDR,A0,Hidi,uk,R2. Set SiT=si1,…,sitm∈ℤqm×tm. Let the secret key and public key for i be SKi=S¯i=ItmSi∈ℤqtm×t+1m and PKi=P¯i=U−Ai∈ℤqn×t+1m. Note that S¯i·P¯iT=0. Output PKi,SKii∈N.C-MIFHE.Enc(params,PKidi,idi,μ∈0,1): Given a message bit μ, randomly select two matrices Y¯i←$ℤqn×t+1mℓ and Ei=−Ei0−Ei1Ei2∈ℤt+1m×t+1mℓ, where Ei0←Dℤ,αqtm×t+1mℓ, Ei1=ei1,1,ei1,2,…,ei1,t+1mℓ←Dℤ,αqm0×t+1mℓ, and Ei2=ei2,1,ei2,2,…,ei2,t+1mℓ, where ei2,j←Dℤ,sjm1 for sj2=ei1,j22+m0αq2·ωlogn2. Set(36)C¯i=μGt+1m+P¯iTY¯i+Ei∈ℤqt+1m×t+1mℓ.Remark 1.
The setting of error parameters, especiallyEi2, plays a critical role in the security proof. For more information, please refer to [30, 31].
Then, partitionC¯i as follows:(37)C¯i=ΔC¯i1,1C¯i1,2C¯i2,1C¯i2,2,where C¯i1,1∈ℤqtm×tmℓ,C¯i1,2∈ℤqtm×mℓ,C¯i2,1∈ℤqm×tmℓ,C¯i2,2∈ℤqm×mℓ.
For everyj∈N\i, randomly select two matrices Yi,j←$ℤqn×mℓ and Ei,j=−Ei,j1Ei,j2∈ℤm×mℓ, where Ei,j1=ei,j1,1,ei,j1,2,…,ei,j1,mℓ←Dℤ,αqm0×mℓ, and Ei,j2=ei,j2,1,ei,j2,2,…,ei,j2,mℓ, where ei,j2,k←Dℤ,skm1 for sk2=ei,j1,k22+m0αq2·ωlogn2. Set(38)Ci,j=μGm+AjTYi,j+Ei,j∈ℤqm×mℓ.
Then, decompose the matrixYi,j that has every entry in ℤq to matrices in binary representation Yi,j=Δ∑k=0logq2k·Yi.jk, where Yi,jk∈0,1n×mℓ.
Forx∈t,y∈n,b∈ml,k+1∈ℓ, compute(39)Vi,j,1x,y,b,k=UTYi,jx,y,b,k+Ei,j,1x,y,b,k+Yi,jky,bGmx∈ℤqtm×mℓ;Vi,j,2x,y,b,k=AiTYi,jx,y,b,k+Ei,j,2x,y,b,k∈ℤqm×mℓ,where Yi,jx,y,b,k←$ℤqn×mℓ, Ei,j,2x,y,b,k∈ℤm×mℓ is extracted from the same distribution of Ei,j, and Ei,j,1x,y,b,k=−Ei,j,1x,y,b,k,0Ei,j,1x,y,b,k,1∈ℤtm×mℓ, where Ei,j,1x,y,b,k,0←Dℤ,αqt−1m×mℓ and Ei,j,1x,y,b,k,1∈ℤm×mℓ is extracted from the same distribution of Ei,j,2x,y,b,k, and Gmx=0x−1m×mℓGm0t−xm×mℓ∈ℤtm×mℓ.
SetUi=ΔCi,j,Vi,j,1x,y,b,k,Vi,j,2x,y,b,k, where j∈N\i,x∈t,y∈n,b∈ml,k+1∈ℓ. Output a tuple of encryption CIPHERi=ΔC¯i,Ui.C-MIFHE.Exp(params,idii∈N,CIPHERi): For every j∈N\i,x∈t,y∈n,b∈ml,k+1∈ℓ, compute(40)Zi,jx,y,bz1,z2=Δ−Ajz1+xr,y,ifz2=b,0,otherwise,that is,Zi,jx,y,b,k=Δ∑z1=1m2kUTz1+xm,y·Ez1,b′∈ℤqm×mℓ, where Ez1,b′ is an m×mℓ matrix that has 1 in the z1th row and the bth column and 0’s in all other entries. Set(41)Z¯i,jx,y,b=Δ0x−1r×rℓZi,jx,y,b0t−xr×rℓ∈ℤqtr×rℓ.Compute(42)Xi,j1=Δ∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1Vi,j,1x,y,b,k·Gm−1Zi,jx,y,b,k∈ℤqtm×mℓ;Xi,j2=Δ∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1Vi,j,2x,y,b,k·Gm−1Zi,jx,y,b,k∈ℤqm×mℓ.Finally, expand a fresh ciphertext to an expanded one.(43)C^i=ΔC¯i1,1−Xi,11⋯C¯i1,2⋯−Xi,N1Ci,1⋱C¯i2,1Xi,12⋯C¯i2,2⋯Xi,N2⋱Ci,N∈ℤqt+Nm×t+Nmℓ.OutputC^i.C-MIFHE.Compparams,C^u,v,ωu,v∈tm,ω∈ℓ: In this algorithm, a series of low-rate expanded (or evaluated) ciphertexts are compressed into a high-rate ciphertext. Let Tu,v=ΔEu,v′0Nm×tm∈ℤt+Nm×tm, where Eu,v′ is a tm×tm matrix that has 1 in the uth row and the vth column and 0’s in all other entries. Set the compressed ciphertext as(44)C∗=Δ∑u∈tm∑v∈tm∑ω∈ℓC^u,v,ω×Gt+Nm−12ω·Tu,v×H∈ℤqt+Nm×t+Nm.Note that the nearly square gadget matrixH∈ℤqtm×t+Nm and its public trapdoor F∈ℤqt+Nm×t+Nm play a significant role in the compression and compressed decryption algorithms.C-MIFHE.CompDecparams,C∗,SKii∈N: Given a compressed ciphertext C∗, set the combined key S^=ΔItm,S1,…,SN∈ℤtm×t+Nm. The compressed decryption is composed of four steps:(1)
Z=ΔS×C∗ (mod q);(2)
Y=ΔZ×F (mod q), where F∈ℤqt+Nm×t+Nm is the public trapdoor matrix;(3)
X=ΔY×F−1 (note that F is full rank over R);(4)
M′=ΔZ−X×H−1 (mod q) (note that H is a row full-rank matrix modulo q, so that there exists a matrix H−1∈ℤqt+Nm×tm such that H×H−1=Itm).C-MIFHE.NANDparams,C^1,C^2: Given two expanded ciphertext matrices C^1,C^2 for two plaintexts μ1,μ2, homomorphic NAND operation is defined as(45)C^NAND=ΔGt+Nm−C^1·Gt+Nm−1C^2.OutputC^NAND. Observe that Gx−1· is randomized, and so is this algorithm.C-MIFHE.Evalparams,f,C^1,C^2,…,C^s: An NAND-circuit f:0,1t⟶0,1 is applied to a set of ciphertexts C^1,C^2,…,C^s, which leads to a ciphertext C^f.


## 4.4. Setting the Parameters

In this subsection, the correctness, homomorphic properties, security, and compression rate of the proposed compressible MIFHE are analyzed. If we use a somewhat (or leveled) version without bootstrapping, then the error bound is dependent on the maximal multiplication depth of allowed evaluated functions. In this paper, we would like to give an asymptotic analysis of various parameters of a fully homomorphic one with bootstrapping, so that all ciphertexts before being packed have an error bound similar to that of freshly expanded ciphertexts.


### 4.4.1. Correctness and Homomorphism

The correctness of compressed decryption may be less obvious, since the encryption and expansion algorithms are quite different from previous ones. During encryption, it holds that, for every identityidi and idjj≠i,(46)S¯i×C¯i=μS¯iGt+1m+S¯iEi∈ℤqtm×t+1mℓ,because S¯i×P¯iT=0. One can calculate the error bound βEnc=Δαqm0·ωlogn3; that is, maxa,bS¯iEia,b<βEnc with overwhelming probability.Besides, for the additional helper information matrices, we have(47)Sj×Ci,j=μSjGm+UTYi,j+SjEi,j∈ℤqtm×mℓ;Itm×Vi,j,1x,y,b,k=UTYi,jx,y,b,k+Ei,j,1x,y,b,k+Yi,jky,bGmx∈ℤqtm×mℓ;Si×Vi,j,2x,y,b,k=UTYi,jx,y,b,k+SiEi,j,2x,y,b,k∈ℤqtm×mℓ,because Sj×AjT=UT. Similarly, one can easily verify that, with overwhelming probability,(48)SjEi,ja,b,Ei,j,1x,y,b,kc,d,SiEi,j,2x,y,b,ke,f<βEnc.During the expansion algorithm, those weird matricesXi,j1 and Xi,j2 are customized to eliminate the undesired UTYi,j in SjCi,j. In particular, we have(49)Itm×Xi,j1=∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1Vi,j,1x,y,b,k·Gm−1Zi,jx,y,b,k=∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1UTYi,jx,y,b,kGm−1Zi,jx,y,b,k+Ei,j,1x,y,b,kGm−1Zi,jx,y,b,k+Yi,jky,bZ¯i,jx,y,b,k¯=∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1UTYi,jx,y,b,kGm−1Zi,jx,y,b,k+Ei,j,1x,y,b,kGm−1Zi,jx,y,b,k+UTYi,j¯,(50)Si×Xi,j2=∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1SiVi,j,2x,y,b,k·Gm−1Zi,jx,y,b,k=∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1UTYi,jx,y,b,kGm−1Zi,jx,y,b,k+SiEi,j,2x,y,b,kGm−1Zi,jx,y,b,k.The underlined part can be a tricky step. We now analyze it as follows:(51)∑y=1n∑b=1ml∑k=0ℓ−1Yi,jky,b∑x=1tZ¯i,jx,y,b,k=∑y=1n∑b=1ml∑k=0ℓ−1Yi,jky,b∑a=1tm2k·UTa,y×Ea,b′=∑a=1tm∑y=1n∑b=1mlUTa,y·Yi,jy,b×Ea,b′,=UTYi,j,where Ea,b′ is a tm×mℓ matrix that has 1 in the ath row and the bth column and 0’s in all other entries.Thus, for any expanded ciphertext, we have(52)S^×C^i=C¯i1,1+SiC¯i2,1−Xi,11+S1Ci,1+SiXi,j2⋯C¯i1,2+SiC¯i2,2⋯−Xi,N1+SNCi,N+SiXi,N2∈ℤtm×t+Nm.There are only two types of all blocks in the above seemingly cumbersome matrix. The first comes from equation (47) by partitioning(53)ItmSi×C¯i1,1C¯i1,2C¯i2,1C¯i2,2=μItmGtmSiGm+S¯iEi=ΔμItmGtm+E˜0μSiGm+E˜i∈ℤqtm×t+1mℓ.The second comes from equations (48), (49), and (51):(54)SjCi,j−Xi,j1+SiXi,j2=μSjGm+SjEi,j+∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1SiEi,j,2x,y,b,k−Ei,j,1x,y,b,kGm−1Zi,jx,y,b,k=ΔμSjGm+E˜j∈ℤqtm×mℓ.Finally, we get the most important decryption invariant in all GSW-like encryptions from equations (52)–(54).(55)S^×C^i=μItmGtm+E˜0μS1Gm+E˜1⋯μSNGm+E˜N=ΔμS^Gt+Nm+E^∈ℤqtm×t+Nmℓ.In terms of the error bound, we haveβExp=Δtnm2ℓ3βEnc; that is, maxa,bE^a,b<βExp with overwhelming probability.With equation (55) in mind, everything turns familiar again. Homomorphic properties are obvious, and one can find them in most GSW-like FHE (or MKFHE) schemes. Thus, we just omit them here.On the other hand, the correctness of compressed decryption also turns obvious. According to equation (55), we have(56)S^×C∗=∑u∈tm∑v∈tm∑ω∈ℓS^C^u,v,ω×Gt+Nm−12ω·Tu,vH=∑u,v,ωμu,v,ωS^Gt+Nm+E^Gt+Nm−12ω·Tu,vH=Δ∑u,v,ω2ωμu,v,ωS^Tu,vH+E∗=∑u,v,ω2ωμu,v,ωEu,v′H+E∗=ΔMH+E∗∈ℤqtm×t+Nm,where Eu,v′ is a tm×tm matrix that has 1 in the uth row and the vth column and 0’s in all other entries, and M∈ℤqtm×tm is a compressed plaintext matrix that can be obtained from Z=ΔS^×C∗=MH+E∗, by using Gentry and Halevi’s idea of the nearly square gadget matrix, which was briefly described in 2.4. That is,(1)
Y=ΔZ×F=E∗F (mod q), where F∈ℤqt+Nm×t+Nm is the public trapdoor matrix;(2)
X=ΔY×F−1=E∗ (note that F is full rank over R);(3)
M′=ΔZ−X×H−1=M (mod q) (note that H is a row full-rank matrix modulo q, so that there exists a matrix H−1∈ℤqt+Nm×tm such that H×H−1=Itm).The matrixM′ is the desired one if every entry of E∗F does not wrap around ℤq; that is, E∗Fmodq=E∗F over the integers. As for the error bound, we have βComp=Δt2t+Nm3ℓ2βExp, i.e., maxa,bE∗a,b<βComp with overwhelming probability. On the other hand, by the construction of the public trapdoor matrix F, it is required that βComp≤q1/t′.


### 4.4.2. Security and Compression Rate

The security level and compression rate of our construction remain to be shown.The additional expansion and compression algorithms are public and do not compromise security. The key-extraction algorithm is similar to that of the underlying IBE in [15, 26] (ABB-IBE). In addition, during the encryption procedure, a fresh ciphertext for the ith user CIPHERi consists of three parts C¯i,Ci,j, and Vi,j,1x,y,b,k,Vi,j,2x,y,b,k, of which randomness matrices are mutually independent, all in a similar form. Exploiting a standard hybrid analysis, one can easily verify that the selective security of our compressible MIFHE is based solely on the DLWE assumption.The view of the attacker is the following distribution:params,MPK,PKi,C¯i,Ui=Ci,j,Vi,j,1x,y,b,k,Vi,j,2x,y,b,k, where j∈N\i,x∈t,y∈n,b∈ml,k+1∈ℓ generated via params,MPK,MSK←C−MIFHE⋅Setup1λ,1N, PKi,SKi←C−MIFHE⋅KeyGenparams, and C¯i,Ui←C−MIFHE⋅Encparams,PKi,μ, where μ∈0,1.We prove the selective security of our construction by relying on the selective security of the underlying ABB-IBE. The proof consists of the following hybrids:(1)
Firstly, we alter each of the ciphertextsVi,j,1x,y,b,k,Vi,j,2x,y,b,k, where j∈N\i,x∈t,y∈n,b∈ml,k+1∈ℓ, so that, instead of being ciphertexts of Yi,jky,b, we change them to ciphertexts of 0. It follows from the selective security of ABB-IBE, which is based solely on the DLWE assumption.(2)
After the first step, no information about the encryption randomnessYi,j is given out. Then, we choose C¯i,Ci,j as ciphertexts of 0. It also follows from the selective security of ABB-IBE.(3)
Finally, the distribution is totally irrelevant to the plaintext bitμ, which completes the proof.Then, let us consider the compression rate of our construction. Recall thatt=t′−1N is the compression parameter. In order to achieve a compression rate of 1−ε for some small ε>0, it is sufficient to set t′=Δ2/ε, so that the compression rate(57)γ=tm·tmt+Nm·t+Nm=t′−1t′2≥1−ε.Thus, we need(58)αq·polynNε=βComp≤q1/t′2=qε/22.Settingαq=2n, we need q=polynN/εΘ1/ε. This means that the selective security of our construction is based on approximation lattices problems with gap polynN/εΘ1/ε. In particular, if we view the compression rate γ and maximal number of parties involved N as constants, then the hardness is only based on ones with polynomial gap. Formally, we have the following theorem.Theorem 3.
For anyε=ελ>0, there exists a rate-1−ε compressible multi-identity fully homomorphic scheme that is selectively secure assuming the hardness of approximate lattices problems with gap polyλN/ε1/ε.


## 4.4.1. Correctness and Homomorphism

The correctness of compressed decryption may be less obvious, since the encryption and expansion algorithms are quite different from previous ones. During encryption, it holds that, for every identityidi and idjj≠i,(46)S¯i×C¯i=μS¯iGt+1m+S¯iEi∈ℤqtm×t+1mℓ,because S¯i×P¯iT=0. One can calculate the error bound βEnc=Δαqm0·ωlogn3; that is, maxa,bS¯iEia,b<βEnc with overwhelming probability.Besides, for the additional helper information matrices, we have(47)Sj×Ci,j=μSjGm+UTYi,j+SjEi,j∈ℤqtm×mℓ;Itm×Vi,j,1x,y,b,k=UTYi,jx,y,b,k+Ei,j,1x,y,b,k+Yi,jky,bGmx∈ℤqtm×mℓ;Si×Vi,j,2x,y,b,k=UTYi,jx,y,b,k+SiEi,j,2x,y,b,k∈ℤqtm×mℓ,because Sj×AjT=UT. Similarly, one can easily verify that, with overwhelming probability,(48)SjEi,ja,b,Ei,j,1x,y,b,kc,d,SiEi,j,2x,y,b,ke,f<βEnc.During the expansion algorithm, those weird matricesXi,j1 and Xi,j2 are customized to eliminate the undesired UTYi,j in SjCi,j. In particular, we have(49)Itm×Xi,j1=∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1Vi,j,1x,y,b,k·Gm−1Zi,jx,y,b,k=∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1UTYi,jx,y,b,kGm−1Zi,jx,y,b,k+Ei,j,1x,y,b,kGm−1Zi,jx,y,b,k+Yi,jky,bZ¯i,jx,y,b,k¯=∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1UTYi,jx,y,b,kGm−1Zi,jx,y,b,k+Ei,j,1x,y,b,kGm−1Zi,jx,y,b,k+UTYi,j¯,(50)Si×Xi,j2=∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1SiVi,j,2x,y,b,k·Gm−1Zi,jx,y,b,k=∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1UTYi,jx,y,b,kGm−1Zi,jx,y,b,k+SiEi,j,2x,y,b,kGm−1Zi,jx,y,b,k.The underlined part can be a tricky step. We now analyze it as follows:(51)∑y=1n∑b=1ml∑k=0ℓ−1Yi,jky,b∑x=1tZ¯i,jx,y,b,k=∑y=1n∑b=1ml∑k=0ℓ−1Yi,jky,b∑a=1tm2k·UTa,y×Ea,b′=∑a=1tm∑y=1n∑b=1mlUTa,y·Yi,jy,b×Ea,b′,=UTYi,j,where Ea,b′ is a tm×mℓ matrix that has 1 in the ath row and the bth column and 0’s in all other entries.Thus, for any expanded ciphertext, we have(52)S^×C^i=C¯i1,1+SiC¯i2,1−Xi,11+S1Ci,1+SiXi,j2⋯C¯i1,2+SiC¯i2,2⋯−Xi,N1+SNCi,N+SiXi,N2∈ℤtm×t+Nm.There are only two types of all blocks in the above seemingly cumbersome matrix. The first comes from equation (47) by partitioning(53)ItmSi×C¯i1,1C¯i1,2C¯i2,1C¯i2,2=μItmGtmSiGm+S¯iEi=ΔμItmGtm+E˜0μSiGm+E˜i∈ℤqtm×t+1mℓ.The second comes from equations (48), (49), and (51):(54)SjCi,j−Xi,j1+SiXi,j2=μSjGm+SjEi,j+∑x=1t∑y=1n∑b=1ml∑k=0ℓ−1SiEi,j,2x,y,b,k−Ei,j,1x,y,b,kGm−1Zi,jx,y,b,k=ΔμSjGm+E˜j∈ℤqtm×mℓ.Finally, we get the most important decryption invariant in all GSW-like encryptions from equations (52)–(54).(55)S^×C^i=μItmGtm+E˜0μS1Gm+E˜1⋯μSNGm+E˜N=ΔμS^Gt+Nm+E^∈ℤqtm×t+Nmℓ.In terms of the error bound, we haveβExp=Δtnm2ℓ3βEnc; that is, maxa,bE^a,b<βExp with overwhelming probability.With equation (55) in mind, everything turns familiar again. Homomorphic properties are obvious, and one can find them in most GSW-like FHE (or MKFHE) schemes. Thus, we just omit them here.On the other hand, the correctness of compressed decryption also turns obvious. According to equation (55), we have(56)S^×C∗=∑u∈tm∑v∈tm∑ω∈ℓS^C^u,v,ω×Gt+Nm−12ω·Tu,vH=∑u,v,ωμu,v,ωS^Gt+Nm+E^Gt+Nm−12ω·Tu,vH=Δ∑u,v,ω2ωμu,v,ωS^Tu,vH+E∗=∑u,v,ω2ωμu,v,ωEu,v′H+E∗=ΔMH+E∗∈ℤqtm×t+Nm,where Eu,v′ is a tm×tm matrix that has 1 in the uth row and the vth column and 0’s in all other entries, and M∈ℤqtm×tm is a compressed plaintext matrix that can be obtained from Z=ΔS^×C∗=MH+E∗, by using Gentry and Halevi’s idea of the nearly square gadget matrix, which was briefly described in 2.4. That is,(1)
Y=ΔZ×F=E∗F (mod q), where F∈ℤqt+Nm×t+Nm is the public trapdoor matrix;(2)
X=ΔY×F−1=E∗ (note that F is full rank over R);(3)
M′=ΔZ−X×H−1=M (mod q) (note that H is a row full-rank matrix modulo q, so that there exists a matrix H−1∈ℤqt+Nm×tm such that H×H−1=Itm).The matrixM′ is the desired one if every entry of E∗F does not wrap around ℤq; that is, E∗Fmodq=E∗F over the integers. As for the error bound, we have βComp=Δt2t+Nm3ℓ2βExp, i.e., maxa,bE∗a,b<βComp with overwhelming probability. On the other hand, by the construction of the public trapdoor matrix F, it is required that βComp≤q1/t′.


## 4.4.2. Security and Compression Rate

The security level and compression rate of our construction remain to be shown.The additional expansion and compression algorithms are public and do not compromise security. The key-extraction algorithm is similar to that of the underlying IBE in [15, 26] (ABB-IBE). In addition, during the encryption procedure, a fresh ciphertext for the ith user CIPHERi consists of three parts C¯i,Ci,j, and Vi,j,1x,y,b,k,Vi,j,2x,y,b,k, of which randomness matrices are mutually independent, all in a similar form. Exploiting a standard hybrid analysis, one can easily verify that the selective security of our compressible MIFHE is based solely on the DLWE assumption.The view of the attacker is the following distribution:params,MPK,PKi,C¯i,Ui=Ci,j,Vi,j,1x,y,b,k,Vi,j,2x,y,b,k, where j∈N\i,x∈t,y∈n,b∈ml,k+1∈ℓ generated via params,MPK,MSK←C−MIFHE⋅Setup1λ,1N, PKi,SKi←C−MIFHE⋅KeyGenparams, and C¯i,Ui←C−MIFHE⋅Encparams,PKi,μ, where μ∈0,1.We prove the selective security of our construction by relying on the selective security of the underlying ABB-IBE. The proof consists of the following hybrids:(1)
Firstly, we alter each of the ciphertextsVi,j,1x,y,b,k,Vi,j,2x,y,b,k, where j∈N\i,x∈t,y∈n,b∈ml,k+1∈ℓ, so that, instead of being ciphertexts of Yi,jky,b, we change them to ciphertexts of 0. It follows from the selective security of ABB-IBE, which is based solely on the DLWE assumption.(2)
After the first step, no information about the encryption randomnessYi,j is given out. Then, we choose C¯i,Ci,j as ciphertexts of 0. It also follows from the selective security of ABB-IBE.(3)
Finally, the distribution is totally irrelevant to the plaintext bitμ, which completes the proof.Then, let us consider the compression rate of our construction. Recall thatt=t′−1N is the compression parameter. In order to achieve a compression rate of 1−ε for some small ε>0, it is sufficient to set t′=Δ2/ε, so that the compression rate(57)γ=tm·tmt+Nm·t+Nm=t′−1t′2≥1−ε.Thus, we need(58)αq·polynNε=βComp≤q1/t′2=qε/22.Settingαq=2n, we need q=polynN/εΘ1/ε. This means that the selective security of our construction is based on approximation lattices problems with gap polynN/εΘ1/ε. In particular, if we view the compression rate γ and maximal number of parties involved N as constants, then the hardness is only based on ones with polynomial gap. Formally, we have the following theorem.Theorem 3.
For anyε=ελ>0, there exists a rate-1−ε compressible multi-identity fully homomorphic scheme that is selectively secure assuming the hardness of approximate lattices problems with gap polyλN/ε1/ε.


## 5. Conclusion

Many outsourced computations require homomorphic evaluations on data provided by different owners (often mutually distrusting), thus encrypted using their own keys. Single-key FHE only allows homomorphic evaluation over ciphertexts encrypted under the same key, while MKFHE or MIFHE under different keys or different identities thus solves this issue. However, the compression rate (the ratio of plaintext size to the ciphertext size) is often too small to be tolerated. Our main technical contribution is that we proposed a new compressible expansion algorithm. Furthermore, we presented the first compressible MKFHE scheme that is semantically secure and the first compressible MIFHE scheme that is selectively secure, both under the decisional learning with error assumption, and both can reach an optimal compression rate. Our future direction is to concretely construct a homomorphic decompression algorithm to unpack compressed ciphertexts, which is a limitation of our constructions because homomorphic evaluations (except some special ones) are not allowed after compression.



---

*Source: 6619476-2021-03-04.xml*