# Leveled Multi-Hop Multi-Identity Fully Homomorphic Encryption

Authors: Wen Liu; Fuqun Wang; Xiaodan Jin; Kefei Chen; Zhonghua Shen
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Gentry, Sahai, and Waters (CRYPTO 2013) proposed the notion of multi-identity fully homomorphic encryption (MIFHE), which allows homomorphic evaluation of data encrypted under multiple identities. Subsequently, Clear and McGoldrick (CANS 2014, CRYPTO 2015) proposed leveled MIFHE candidates. However, the proposed MIFHE is either based oniO, which is a nonstandard assumption or single hop; that is, an arbitrary “evaluated” ciphertext under a set of identities is difficult to further evaluate when new ciphertexts are encrypted under additional identities. To overcome these drawbacks, we propose a leveled multi-hop MIFHE scheme. In a multi-hop MIFHE scheme, one can evaluate a group of ciphertexts under a set of identities to obtain an “evaluated” ciphertext, which can be further evaluated with other ciphertexts encrypted under additional identities. We also show that the proposed MIFHE scheme is secure against selective identity and chosen-plaintext attacks (IND-sID-CPA) under the learning with errors (LWE) assumption.


---

## Body

## 1. Introduction

The idea of homomorphic encryption was first proposed by Rivest et al. [1] in 1978. How to construct a scheme with homomorphic properties is used to be a difficult problem for cryptographers. With the advent of the information age and the development of cloud computing technology, it is particularly urgent to solve this problem. It was not until 2009 that Gentry proposed the first fully homomorphic encryption (FHE) system based on ideal lattices, allowing anyone without a secret key to compute any efficiently computable function over encrypted data [2]. Because FHE is suitable to apply cloud computing without compromising security, it has quickly become a research hot topic [3–7].All of the above FHE schemes are single-key homomorphic, that is, only suitable for the homomorphic evaluation of ciphertext encrypted under a single key. However, in many realistic scenarios, the ciphertext of homomorphic encryption is usually encrypted under multiple different keys. Therefore, at STOC 2012, López-Alt, Tromer, and Vaikuntanathan [8] proposed the first cryptographic construction of multi-key full homomorphic encryption (MKFHE) based on NTRU cryptography, which enables the evaluation of data encrypted under different keys. Subsequently, a large number of articles appeared to improve MKFHE, including single hop only [9, 10], multi-hop with bootstrapping [11–16], and multi-hop without bootstrapping [17].Although (MK) FHEs have extensive applications, they require complex certificate management in implementation. To simplify the certificate management, Naccache [18] introduced a notion of identity-based fully homomorphic encryption (IBFHE), where there is no user-specific key that the evaluator must use. In particular, in an IBFHE scheme, data encrypted under a single identity can perform homomorphic operations by any evaluator with only public parameters. In 2013, Gentry et al. [7] constructed an IBFHE scheme from GSW-FHE. The IBFHE scheme only allows homomorphic evaluation of encrypted data under single identity but not multiple identities. Clear and McGoldrick [19] gave an MIFHE based on the indistinguishability obfuscation (iO) [20] to overcome the disadvantage of single identity at CANS 2014. Then, they [9] proposed a leveled MIFHE candidate under LWE in the random oracle model at CRYPTO 2015. However, the later scheme needs to set the number of users participating in homomorphic evaluation in advance, and new users cannot be added to the operation process, which is single hop in MIFHE cryptography. In 2017, Canetti et al. [21] proposed two MIFHE schemes. The first combines MKFHE and identity-based encryption (IBE) on the fly. Therefore, the ciphertext extension depends on the number of ciphertexts, which is not compact. The second is nonleveled, but uses iO. In 2020, with the help of an MKFHE, Pal and Dutta [22] extended IBE to a CCA1 secure MIFHE scheme. However, their extension process uses witness pseudorandom function (WPRF), which is a nonstandard assumption. Recently, Shen et al. [23] proposed a compressible MIFHE scheme based on [9, 10, 24]. The scheme is selectively secure under the LWE assumption and can reach an optimal compression rate, but it is single hop.Thus, it is interesting to construct a compact MIFHE scheme with the multi-hop homomorphism under standard assumption, where one can evaluate a group of ciphertexts under a set of identities to obtain an “evaluated” ciphertext, which can be further evaluated with other ciphertexts encrypted under additional identities.


### 1.1. Contribution

We propose a leveled multi-hop MIFHE scheme adapted from the GPV-FHE [25], following the construction method of the PS-MKFHE, which is a leveled multi-hop MKFHE scheme built by Peikert and Shiehian [17]. We show that it is compact and secure against the IND-sID-CPA attack under the LWE assumption in the random oracle model. In our construction, we use a fully homomorphic commitment to commit the plaintext bit to help homomorphic operations. Additionally, by combining the transformation of MIFHE to the nonadaptive chosen-ciphertext attack (CCA1) secure FHE proposed by Canetti et al. [21], we can obtain a CCA1 secure FHE with multi-hop homomorphism. Finally, we note that our construction can be applied to the ring setting as [9] for shorter parameters.


### 1.2. Technical Overview

It is well known that the efficient multi-hop MKFHE obtained by bootstrapping is difficult to generalize MIFHE, because the public homomorphic evaluation key cannot be extracted from identity secret keySKid as it is a ciphertext of SKid and even the SKid is not generated before decryption. Therefore, we focus on the PS-MKFHE [17], which does not use bootstrapping. Our key observation is that we can construct a multi-hop MIFHE scheme following the ideas introduced by Peikert and Shiehian [17]. They built multi-hop MKFHE schemes to overcome the single hop drawback of the MKFHE schemes [9, 10]. In their first construction, a ciphertext consists of C,F,D, where C is a GSW-FHE ciphertext [7] that encrypts message μ, F is a fully homomorphic commitment [26] to the same message, and D is a special encryption of the commitment randomness implied in F under the same key to C. Here, D,F provides the power of expanding C to C′ with additional keys (with a part of the public key) and preserves some invariant, which can be further used. In total, after expanding or computing, the form of C,F,D remains. This finding is the reason to support the multi-hop computation with respect to additional keys.However, it is nontrivial to construct a multi-hop MIFHE scheme because PS-MKFHE [17] is built from GSW-FHE [7] but not from GPV-FHE [26]. For simplicity, we now informally describe a multi-hop MKFHE from GPV-FHE [26], which can be converted into a multi-hop MIFHE scheme (see Section 3).In a multi-hop MKFHE scheme based on GPV-FHE, a ciphertext under a secret keyt∈ℤmk consists of four components C,D,E,F:(1)
A GPV-FHE ciphertextC∈ℤqmk×mkℓ that encrypts μ under t.(2)
A GPV-FHE style fully homomorphic commitmentD∈ℤqm×mℓ to the same message μ with underlying commitment randomness R,X.(3)
A special encryptionE∈ℤqnmℓ×mℓ under t of the former part of the commitment randomness R.(4)
Another special encryptionF∈ℤqm2×mℓ under t of the latter part of the commitment randomness X.To expandC to an additional secret key t˜∈ℤqm, we define(1)C′=CU0D∈ℤqmk+1×mk+1ℓ,where U is derived from E. The commitment D is preserved, and E,F are padded with zeros to fit the long secret key t,t˜. Moreover, the homomorphic evaluation can be simply designed as GPV-FHE (see Section 3 for more details about our MIFHE scheme).


### 1.3. Paper Organization

First, we recall some notions, definitions, and facts in Section2. Then, we propose our MIFHE scheme that satisfies IND-sID-CPA secure in Section 3. In the end, we conclude in Section 4.


## 1.1. Contribution

We propose a leveled multi-hop MIFHE scheme adapted from the GPV-FHE [25], following the construction method of the PS-MKFHE, which is a leveled multi-hop MKFHE scheme built by Peikert and Shiehian [17]. We show that it is compact and secure against the IND-sID-CPA attack under the LWE assumption in the random oracle model. In our construction, we use a fully homomorphic commitment to commit the plaintext bit to help homomorphic operations. Additionally, by combining the transformation of MIFHE to the nonadaptive chosen-ciphertext attack (CCA1) secure FHE proposed by Canetti et al. [21], we can obtain a CCA1 secure FHE with multi-hop homomorphism. Finally, we note that our construction can be applied to the ring setting as [9] for shorter parameters.


## 1.2. Technical Overview

It is well known that the efficient multi-hop MKFHE obtained by bootstrapping is difficult to generalize MIFHE, because the public homomorphic evaluation key cannot be extracted from identity secret keySKid as it is a ciphertext of SKid and even the SKid is not generated before decryption. Therefore, we focus on the PS-MKFHE [17], which does not use bootstrapping. Our key observation is that we can construct a multi-hop MIFHE scheme following the ideas introduced by Peikert and Shiehian [17]. They built multi-hop MKFHE schemes to overcome the single hop drawback of the MKFHE schemes [9, 10]. In their first construction, a ciphertext consists of C,F,D, where C is a GSW-FHE ciphertext [7] that encrypts message μ, F is a fully homomorphic commitment [26] to the same message, and D is a special encryption of the commitment randomness implied in F under the same key to C. Here, D,F provides the power of expanding C to C′ with additional keys (with a part of the public key) and preserves some invariant, which can be further used. In total, after expanding or computing, the form of C,F,D remains. This finding is the reason to support the multi-hop computation with respect to additional keys.However, it is nontrivial to construct a multi-hop MIFHE scheme because PS-MKFHE [17] is built from GSW-FHE [7] but not from GPV-FHE [26]. For simplicity, we now informally describe a multi-hop MKFHE from GPV-FHE [26], which can be converted into a multi-hop MIFHE scheme (see Section 3).In a multi-hop MKFHE scheme based on GPV-FHE, a ciphertext under a secret keyt∈ℤmk consists of four components C,D,E,F:(1)
A GPV-FHE ciphertextC∈ℤqmk×mkℓ that encrypts μ under t.(2)
A GPV-FHE style fully homomorphic commitmentD∈ℤqm×mℓ to the same message μ with underlying commitment randomness R,X.(3)
A special encryptionE∈ℤqnmℓ×mℓ under t of the former part of the commitment randomness R.(4)
Another special encryptionF∈ℤqm2×mℓ under t of the latter part of the commitment randomness X.To expandC to an additional secret key t˜∈ℤqm, we define(1)C′=CU0D∈ℤqmk+1×mk+1ℓ,where U is derived from E. The commitment D is preserved, and E,F are padded with zeros to fit the long secret key t,t˜. Moreover, the homomorphic evaluation can be simply designed as GPV-FHE (see Section 3 for more details about our MIFHE scheme).


## 1.3. Paper Organization

First, we recall some notions, definitions, and facts in Section2. Then, we propose our MIFHE scheme that satisfies IND-sID-CPA secure in Section 3. In the end, we conclude in Section 4.


## 2. Preliminaries

Let us start with the following notations that will be used throughout the study. We use the bold uppercase letters (e.g.,A,B) to represent matrices. Similarly, the bold lowercase letters (e.g., a,b) represent column vectors. We use ai to denote the i entry of a and ai,j to denote the i,j entry of A. A‖B is used to denote the concatenation of two matrices. Similarly, a,b is used to denote the concatenation of two column vectors. Let λ denote the security parameter. We define n=1,2,…,n for any positive integer n. Let negl λ denote a negligible function that grows slower than λ−c for any constant c>0 and any sufficiently large value of λ. An event occurs with overwhelming probability; i.e., it occurs with a probability of at least 1−neglλ.


### 2.1. Basic Notions

#### 2.1.1. Approximations

Very recently, Peikert and Shiehian [17] suggested a simple method to indicate that the two sides in some “noisy equations” extensively used in lattice-based cryptography were approximately equal to an additive error. We will follow their notation using:(2)x≈yerrorE.To indicate thatx=y+e for some e∈−E,E, the notation can be naturally expanded to the vector or matrix type using the infinite norm.


#### 2.1.2. Tensor Product

For matricesA∈ℤm×n,B∈ℤs×t, tensor product A⊗B is an ms×nt matrix, which consists of m×n blocks, whose i,j block is ai,j·B.In this work, we widely use the mixed-product property: for any matricesA,B,C,D with compatible dimensions, it holds that:(3)A⊗B·C⊗D=A·C⊗B·D.


### 2.2. Background on Lattices

#### 2.2.1. Lattices

For matrixA∈ℤqn×m, we define the q-ary integer lattice in this way:(4)Λ⊥A=x∈ℤm:Ax=0modq.For vectoru∈ℤqn, we now define the coset (or “shifted” lattice) in this way:(5)Λu⊥A=x∈ℤm:Ax=umodq.


#### 2.2.2. LWE

The learning with errors (LWE) problem was first introduced by Regev [27] as an extension of the “learning parity with noise.” In this study, we define the decisional learning with errors (DLWE) problem that is equivalent to LWE for certain parameters as follows.Definition 1.
(Decisional Learning with Errors (DLWE)) For positive integers n,m,q and an error distribution χ over ℤ, the DLWEn,m,q,χ problem is to distinguish with nonnegligible advantage between A,b=AT·t+e, where A←$ℤqn×m,t←$ℤqn,e←χmb2−4ac, and A,b sampled uniformly at random from ℤqn×m×ℤqm.Letχ be a discrete Gaussian distribution over ℤ with parameter r=2n, and it is a well-established instantiation of LWE. A sample drawn from this distribution has magnitude bounded by rn=Θn except with a probability of at most 2−n. For this parameterization and any m=polyλ, it is easy to see LWE by quantum reduction at least as difficult as certain worst-case difficult problems (e.g., the shortest independent vector problem) on n-dimensional lattices with approximate factor O˜qn [27]. Classical reductions are also famous for subexponential modulus q [28] and polynomial q [29].In this work, we rely on the tensor form of LWE denoted by TLWE and the matrix form of LWE denoted by MLWE, whose specific definitions are introduced below.Definition 2.
(The Matrix Form of Learning with Errors (MLWE)) For positive integers n,m,k,q and an error distribution χ over ℤ, the MLWEn,m,k,q,χ problem is to distinguish with nonnegligible advantage between A,B=AT·T+E, where A←$ℤqn×m,T←$ℤqn×k,E←χm×k, and A,B sampled uniformly at random from ℤqn×m×ℤqm×k.Definition 3.
(The Tensor Form of Learning with Errors (TLWE)) For positive integers n,m,k,t,q and an error distribution χ over ℤ, the TLWEn,m,k,t,q,χ problem is to distinguish with nonnegligible advantage between A,B=It⊗AT·T+E, where A←$ℤqn×m,T←$ℤqnt×k,E←χmt×k, and It denotes the t-dimensional identity matrix, and A,B sampled uniformly at random from ℤqn×m×ℤqmt×k.According to the standard mixed argument, we can get that MLWE is equivalent to DLWE with at mostk factor loss in the distinguishing advantage, and TLWE is equivalent to MLWE with at most t2 factor loss in the distinguishing advantage.


#### 2.2.3. Lattice Trapdoor

We recall some cryptographic facts about trapdoor generation and preimage sampling algorithms with important properties [30]. Since all the details of implementation are not strictly necessary in this work, we ignore them. Note that there are improved algorithms but only within Ologλ factor [31].Lemma 1 (see [30]).
Letn=polyλ,q≥3be odd, andm=⌈6nlogq⌉. There is a probabilistic polynomial timePPTalgorithmTrapGenn,m,qthat outputs a pairA∈ℤqn×m,TA∈ℤm×m, such thatAis statistically close to a uniform matrix inℤqn×m, andTAis a basis forΛ⊥AsatisfyingTA≤OnlogqandT˜A≤Onlogqwith overwhelming probability inλ.Lemma 2 (see [30]).
Letn=polyλbe a positive integer,qbe a prime, andm≥2nlogq. Then, for all but a2q−nfraction of allA∈ℤqn×mand for anyr≥ωlogm, the distribution of the syndromeu=Asmodqis statistically close to uniform overℤqn, wheres←Dℤm,r.Lemma 3 (see [30]).
SetA∈ℤqn×m,TA∈ℤm×m←TrapGenn,m,qfrom Lemma 1. Then, for a parameterr≥T˜A·ωlogmand a uniformly random vectoru∈ℝn, there is a PPT algorithm, which outputs vectors∈Λu⊥Asampled from a statistically similar distribution toDΛu⊥A,r; thus,As=uwheneverΛu⊥Ais not empty.


#### 2.2.4. Gadget Matrices and Bit Decomposition

We recall a useful notion ofgadget matrix, which was first introduced in [31], to decompose vectors or matrices over ℤq into short vectors or matrices over ℤ.For integerq, let ℓ=⌈logq⌉. Gadget matrix gT=1,2,22,…,2ℓ−1 and bit decomposition function g−1:ℤq⟶0,1ℓ are defined, which outputs a binary column vector that consists of the binary representation of its argument, such that gT·g−1a=a, for any a∈ℤq.More generally, for any positive integerk, Gk=Ik⊗gT∈ℤqk×kℓ is defined, where Ik denotes the k-dimensional identity matrix. For any t, the general bit decomposition function G−1:ℤqk×t⟶0,1kℓ×t outputs a binary kℓ×tmatrix (invoking g−1), such that G·G−1A=A, for A∈ℤqk×t. Additionally, we often write G−TA=G−1AT for simplicity.


### 2.3. Multi-Identity Fully Homomorphic Encryption

We begin with the definition of the leveled multi-hop MIFHE, which is adapted and summarized from the definition of the single-hop MIFHE in [9], definition of the single-hop MKFHE in [10], and definition of the multi-hop MKFHE in [17]. Here, we require a bound d on the NAND circuit depth and a bound L on the number of identities in one evaluation, and we mainly focus on the bit encryption scheme and [17].Now, a ciphertext is called a “fresh” ciphertext if it is generated by the encryption algorithmEnc defined below (i.e., it corresponds to a single identity), an “expanded” ciphertext if it is the output of expansion algorithm Expand (which relates to multiple identities), or an “evaluated” ciphertext if it is the output of homomorphic evaluation algorithm Eval.Definition 4.
A leveled multi-hop multi-identity fully homomorphic encryption scheme consists of sixPPT algorithms Setup,Extract,Enc,Expand,Eval,andDec defined as follows:(i)
Setup1λ,1d,1L: on inputting a security parameter λ, a bound d on the NAND circuit depth, and a bound L on the number of identities involved in one evaluation, generate a master public key MPK and a master secret key MSK, and then output MPK,MSK. Here, the security parameter λ also defines an identity space ℐ(ii)
ExtractMPK,MSK,id: on inputting the MPK, MSK, and identity id∈ℐ, extract a user-specific secret key SKid, and output it(iii)
EncMPK,id,μ∈0,1: on inputting the MPK, identity id∈ℐ, and bit μ∈0,1, output a “fresh” ciphertext id;c(iv)
ExpandMPK,idk+1,id1,id2,…,idk;c: on inputting the MPK, identity idk+1, and any (“fresh,” “expanded,” or “evaluated”) ciphertext id1,id2,…,idk;c under k identities id1,id2,…,idk, compute and output an “expanded” ciphertext id1,id2,…,idk,idk+1;c′ under k+1 identities id1,id2,…,idk,idk+1(v)
EvalMPK,f,c1,c2,…,cN: on inputting MPK, an NAND circuit f, and N ciphertexts c1,c2,…,cN, output an “evaluated” ciphertext cf(vi)
Dec(SKid1,SKid2,…,SKidk,id1,id2,…,idk;c): on inputting k secret keys SKid1,SKid2,…,SKidk, which correspond to identities id1,id2,…,idk and any ciphertext id1,id2,…,idk;c, output a bit μWe underline that we will homomorphically evaluate anyNAND circuit gate by gate as described in [17], which indicates that the evaluation is multi-hop as previous multi-key FHE schemes [8, 17].


#### 2.3.1. Correctness

A leveled multi-hop MIFHE scheme is correct if it satisfies the following conditions. For all positive integersλ,d,L, for every NAND circuit f of depth at most d with N input wires, for every function π:N⟶L (which relates each input wire to a key pair), and for every μ∈0,1N, the following experiment succeeds with overwhelming probability: MPK,MSK←Setup1λ,1d,1L, generate identity key pairs PKidπi,SKidπi←ExtractMPK,MSK,idπi for every i∈N, generate ciphertext ci←EncMPK,idπi,μi∈0,1 for every i∈N, compute cf←EvalMPK,f,c1,c2,…,cN (may invoke algorithm Expand), and finally check whether DecSKidπii∈N,cf=fμ1,μ2,…,μN.


#### 2.3.2. Compactness

A leveled multi-hop MIFHE scheme is compact if there exists a polynomialp·,·,· such that cf≤pλ,d,L in the experiment from Definition 4. In other words, the length of cf is independent of both f and N but can depend polynomially on λ,d, and L.


#### 2.3.3. Security

The security game of MIFHE is the same as that of IBE, but there is no reference to the expansion algorithm and evaluation algorithm because they are public and do not impact the security. In this study, we will mainly focus on the semantically secure under selective identity and chosen-plaintext attack (IND-sID-CPA) security game for MIFHE between a challengerC and a PPT attacker A, which is defined as follows:(i)
Initial Stage. AttackerA is given bound d on the NAND circuit depth and bound L on the number of identities and outputs target identity id∗.(ii)
Setup. ChallengerC runs Setup1λ,1d,1L to generate MPK,MSK and sends MPK to attacker A.(iii)
Query Stage 1. AdversaryA adaptively issues a query on any identity id such that id≠id∗. Challenger C runs ExtractMPK,MSK,id to obtain identity secret key skid that corresponds to id and sends skid back to A.(iv)
Challenge. ChallengerC selects a uniformly random bit μ∗←$0,1, computes a challenge ciphertext c∗←EncMPK,id∗,μ∗, and sends it to attacker A.(v)
Query Stage 2. AdversaryA issues additional adaptive identity secret key queries, and challenger C responds as in query stage 1.(vi)
Output. The attacker outputs a guessμ′∈0,1 and wins if μ′=μ∗.The advantage of the attacker in the above IND-sID-CPA security game is defined asPrμ′=μ∗−1/2, where the probability is taken over the random bits used by all algorithms in the game.Definition 5.
A leveled multi-identity fully homomorphic encryption scheme isIND-sID-CPA secure if any PPT attacker has at most a negligible advantage in the IND-sID-CPA security game defined above.


## 2.1. Basic Notions

### 2.1.1. Approximations

Very recently, Peikert and Shiehian [17] suggested a simple method to indicate that the two sides in some “noisy equations” extensively used in lattice-based cryptography were approximately equal to an additive error. We will follow their notation using:(2)x≈yerrorE.To indicate thatx=y+e for some e∈−E,E, the notation can be naturally expanded to the vector or matrix type using the infinite norm.


### 2.1.2. Tensor Product

For matricesA∈ℤm×n,B∈ℤs×t, tensor product A⊗B is an ms×nt matrix, which consists of m×n blocks, whose i,j block is ai,j·B.In this work, we widely use the mixed-product property: for any matricesA,B,C,D with compatible dimensions, it holds that:(3)A⊗B·C⊗D=A·C⊗B·D.


## 2.1.1. Approximations

Very recently, Peikert and Shiehian [17] suggested a simple method to indicate that the two sides in some “noisy equations” extensively used in lattice-based cryptography were approximately equal to an additive error. We will follow their notation using:(2)x≈yerrorE.To indicate thatx=y+e for some e∈−E,E, the notation can be naturally expanded to the vector or matrix type using the infinite norm.


## 2.1.2. Tensor Product

For matricesA∈ℤm×n,B∈ℤs×t, tensor product A⊗B is an ms×nt matrix, which consists of m×n blocks, whose i,j block is ai,j·B.In this work, we widely use the mixed-product property: for any matricesA,B,C,D with compatible dimensions, it holds that:(3)A⊗B·C⊗D=A·C⊗B·D.


## 2.2. Background on Lattices

### 2.2.1. Lattices

For matrixA∈ℤqn×m, we define the q-ary integer lattice in this way:(4)Λ⊥A=x∈ℤm:Ax=0modq.For vectoru∈ℤqn, we now define the coset (or “shifted” lattice) in this way:(5)Λu⊥A=x∈ℤm:Ax=umodq.


### 2.2.2. LWE

The learning with errors (LWE) problem was first introduced by Regev [27] as an extension of the “learning parity with noise.” In this study, we define the decisional learning with errors (DLWE) problem that is equivalent to LWE for certain parameters as follows.Definition 1.
(Decisional Learning with Errors (DLWE)) For positive integers n,m,q and an error distribution χ over ℤ, the DLWEn,m,q,χ problem is to distinguish with nonnegligible advantage between A,b=AT·t+e, where A←$ℤqn×m,t←$ℤqn,e←χmb2−4ac, and A,b sampled uniformly at random from ℤqn×m×ℤqm.Letχ be a discrete Gaussian distribution over ℤ with parameter r=2n, and it is a well-established instantiation of LWE. A sample drawn from this distribution has magnitude bounded by rn=Θn except with a probability of at most 2−n. For this parameterization and any m=polyλ, it is easy to see LWE by quantum reduction at least as difficult as certain worst-case difficult problems (e.g., the shortest independent vector problem) on n-dimensional lattices with approximate factor O˜qn [27]. Classical reductions are also famous for subexponential modulus q [28] and polynomial q [29].In this work, we rely on the tensor form of LWE denoted by TLWE and the matrix form of LWE denoted by MLWE, whose specific definitions are introduced below.Definition 2.
(The Matrix Form of Learning with Errors (MLWE)) For positive integers n,m,k,q and an error distribution χ over ℤ, the MLWEn,m,k,q,χ problem is to distinguish with nonnegligible advantage between A,B=AT·T+E, where A←$ℤqn×m,T←$ℤqn×k,E←χm×k, and A,B sampled uniformly at random from ℤqn×m×ℤqm×k.Definition 3.
(The Tensor Form of Learning with Errors (TLWE)) For positive integers n,m,k,t,q and an error distribution χ over ℤ, the TLWEn,m,k,t,q,χ problem is to distinguish with nonnegligible advantage between A,B=It⊗AT·T+E, where A←$ℤqn×m,T←$ℤqnt×k,E←χmt×k, and It denotes the t-dimensional identity matrix, and A,B sampled uniformly at random from ℤqn×m×ℤqmt×k.According to the standard mixed argument, we can get that MLWE is equivalent to DLWE with at mostk factor loss in the distinguishing advantage, and TLWE is equivalent to MLWE with at most t2 factor loss in the distinguishing advantage.


### 2.2.3. Lattice Trapdoor

We recall some cryptographic facts about trapdoor generation and preimage sampling algorithms with important properties [30]. Since all the details of implementation are not strictly necessary in this work, we ignore them. Note that there are improved algorithms but only within Ologλ factor [31].Lemma 1 (see [30]).
Letn=polyλ,q≥3be odd, andm=⌈6nlogq⌉. There is a probabilistic polynomial timePPTalgorithmTrapGenn,m,qthat outputs a pairA∈ℤqn×m,TA∈ℤm×m, such thatAis statistically close to a uniform matrix inℤqn×m, andTAis a basis forΛ⊥AsatisfyingTA≤OnlogqandT˜A≤Onlogqwith overwhelming probability inλ.Lemma 2 (see [30]).
Letn=polyλbe a positive integer,qbe a prime, andm≥2nlogq. Then, for all but a2q−nfraction of allA∈ℤqn×mand for anyr≥ωlogm, the distribution of the syndromeu=Asmodqis statistically close to uniform overℤqn, wheres←Dℤm,r.Lemma 3 (see [30]).
SetA∈ℤqn×m,TA∈ℤm×m←TrapGenn,m,qfrom Lemma 1. Then, for a parameterr≥T˜A·ωlogmand a uniformly random vectoru∈ℝn, there is a PPT algorithm, which outputs vectors∈Λu⊥Asampled from a statistically similar distribution toDΛu⊥A,r; thus,As=uwheneverΛu⊥Ais not empty.


### 2.2.4. Gadget Matrices and Bit Decomposition

We recall a useful notion ofgadget matrix, which was first introduced in [31], to decompose vectors or matrices over ℤq into short vectors or matrices over ℤ.For integerq, let ℓ=⌈logq⌉. Gadget matrix gT=1,2,22,…,2ℓ−1 and bit decomposition function g−1:ℤq⟶0,1ℓ are defined, which outputs a binary column vector that consists of the binary representation of its argument, such that gT·g−1a=a, for any a∈ℤq.More generally, for any positive integerk, Gk=Ik⊗gT∈ℤqk×kℓ is defined, where Ik denotes the k-dimensional identity matrix. For any t, the general bit decomposition function G−1:ℤqk×t⟶0,1kℓ×t outputs a binary kℓ×tmatrix (invoking g−1), such that G·G−1A=A, for A∈ℤqk×t. Additionally, we often write G−TA=G−1AT for simplicity.


## 2.2.1. Lattices

For matrixA∈ℤqn×m, we define the q-ary integer lattice in this way:(4)Λ⊥A=x∈ℤm:Ax=0modq.For vectoru∈ℤqn, we now define the coset (or “shifted” lattice) in this way:(5)Λu⊥A=x∈ℤm:Ax=umodq.


## 2.2.2. LWE

The learning with errors (LWE) problem was first introduced by Regev [27] as an extension of the “learning parity with noise.” In this study, we define the decisional learning with errors (DLWE) problem that is equivalent to LWE for certain parameters as follows.Definition 1.
(Decisional Learning with Errors (DLWE)) For positive integers n,m,q and an error distribution χ over ℤ, the DLWEn,m,q,χ problem is to distinguish with nonnegligible advantage between A,b=AT·t+e, where A←$ℤqn×m,t←$ℤqn,e←χmb2−4ac, and A,b sampled uniformly at random from ℤqn×m×ℤqm.Letχ be a discrete Gaussian distribution over ℤ with parameter r=2n, and it is a well-established instantiation of LWE. A sample drawn from this distribution has magnitude bounded by rn=Θn except with a probability of at most 2−n. For this parameterization and any m=polyλ, it is easy to see LWE by quantum reduction at least as difficult as certain worst-case difficult problems (e.g., the shortest independent vector problem) on n-dimensional lattices with approximate factor O˜qn [27]. Classical reductions are also famous for subexponential modulus q [28] and polynomial q [29].In this work, we rely on the tensor form of LWE denoted by TLWE and the matrix form of LWE denoted by MLWE, whose specific definitions are introduced below.Definition 2.
(The Matrix Form of Learning with Errors (MLWE)) For positive integers n,m,k,q and an error distribution χ over ℤ, the MLWEn,m,k,q,χ problem is to distinguish with nonnegligible advantage between A,B=AT·T+E, where A←$ℤqn×m,T←$ℤqn×k,E←χm×k, and A,B sampled uniformly at random from ℤqn×m×ℤqm×k.Definition 3.
(The Tensor Form of Learning with Errors (TLWE)) For positive integers n,m,k,t,q and an error distribution χ over ℤ, the TLWEn,m,k,t,q,χ problem is to distinguish with nonnegligible advantage between A,B=It⊗AT·T+E, where A←$ℤqn×m,T←$ℤqnt×k,E←χmt×k, and It denotes the t-dimensional identity matrix, and A,B sampled uniformly at random from ℤqn×m×ℤqmt×k.According to the standard mixed argument, we can get that MLWE is equivalent to DLWE with at mostk factor loss in the distinguishing advantage, and TLWE is equivalent to MLWE with at most t2 factor loss in the distinguishing advantage.


## 2.2.3. Lattice Trapdoor

We recall some cryptographic facts about trapdoor generation and preimage sampling algorithms with important properties [30]. Since all the details of implementation are not strictly necessary in this work, we ignore them. Note that there are improved algorithms but only within Ologλ factor [31].Lemma 1 (see [30]).
Letn=polyλ,q≥3be odd, andm=⌈6nlogq⌉. There is a probabilistic polynomial timePPTalgorithmTrapGenn,m,qthat outputs a pairA∈ℤqn×m,TA∈ℤm×m, such thatAis statistically close to a uniform matrix inℤqn×m, andTAis a basis forΛ⊥AsatisfyingTA≤OnlogqandT˜A≤Onlogqwith overwhelming probability inλ.Lemma 2 (see [30]).
Letn=polyλbe a positive integer,qbe a prime, andm≥2nlogq. Then, for all but a2q−nfraction of allA∈ℤqn×mand for anyr≥ωlogm, the distribution of the syndromeu=Asmodqis statistically close to uniform overℤqn, wheres←Dℤm,r.Lemma 3 (see [30]).
SetA∈ℤqn×m,TA∈ℤm×m←TrapGenn,m,qfrom Lemma 1. Then, for a parameterr≥T˜A·ωlogmand a uniformly random vectoru∈ℝn, there is a PPT algorithm, which outputs vectors∈Λu⊥Asampled from a statistically similar distribution toDΛu⊥A,r; thus,As=uwheneverΛu⊥Ais not empty.


## 2.2.4. Gadget Matrices and Bit Decomposition

We recall a useful notion ofgadget matrix, which was first introduced in [31], to decompose vectors or matrices over ℤq into short vectors or matrices over ℤ.For integerq, let ℓ=⌈logq⌉. Gadget matrix gT=1,2,22,…,2ℓ−1 and bit decomposition function g−1:ℤq⟶0,1ℓ are defined, which outputs a binary column vector that consists of the binary representation of its argument, such that gT·g−1a=a, for any a∈ℤq.More generally, for any positive integerk, Gk=Ik⊗gT∈ℤqk×kℓ is defined, where Ik denotes the k-dimensional identity matrix. For any t, the general bit decomposition function G−1:ℤqk×t⟶0,1kℓ×t outputs a binary kℓ×tmatrix (invoking g−1), such that G·G−1A=A, for A∈ℤqk×t. Additionally, we often write G−TA=G−1AT for simplicity.


## 2.3. Multi-Identity Fully Homomorphic Encryption

We begin with the definition of the leveled multi-hop MIFHE, which is adapted and summarized from the definition of the single-hop MIFHE in [9], definition of the single-hop MKFHE in [10], and definition of the multi-hop MKFHE in [17]. Here, we require a bound d on the NAND circuit depth and a bound L on the number of identities in one evaluation, and we mainly focus on the bit encryption scheme and [17].Now, a ciphertext is called a “fresh” ciphertext if it is generated by the encryption algorithmEnc defined below (i.e., it corresponds to a single identity), an “expanded” ciphertext if it is the output of expansion algorithm Expand (which relates to multiple identities), or an “evaluated” ciphertext if it is the output of homomorphic evaluation algorithm Eval.Definition 4.
A leveled multi-hop multi-identity fully homomorphic encryption scheme consists of sixPPT algorithms Setup,Extract,Enc,Expand,Eval,andDec defined as follows:(i)
Setup1λ,1d,1L: on inputting a security parameter λ, a bound d on the NAND circuit depth, and a bound L on the number of identities involved in one evaluation, generate a master public key MPK and a master secret key MSK, and then output MPK,MSK. Here, the security parameter λ also defines an identity space ℐ(ii)
ExtractMPK,MSK,id: on inputting the MPK, MSK, and identity id∈ℐ, extract a user-specific secret key SKid, and output it(iii)
EncMPK,id,μ∈0,1: on inputting the MPK, identity id∈ℐ, and bit μ∈0,1, output a “fresh” ciphertext id;c(iv)
ExpandMPK,idk+1,id1,id2,…,idk;c: on inputting the MPK, identity idk+1, and any (“fresh,” “expanded,” or “evaluated”) ciphertext id1,id2,…,idk;c under k identities id1,id2,…,idk, compute and output an “expanded” ciphertext id1,id2,…,idk,idk+1;c′ under k+1 identities id1,id2,…,idk,idk+1(v)
EvalMPK,f,c1,c2,…,cN: on inputting MPK, an NAND circuit f, and N ciphertexts c1,c2,…,cN, output an “evaluated” ciphertext cf(vi)
Dec(SKid1,SKid2,…,SKidk,id1,id2,…,idk;c): on inputting k secret keys SKid1,SKid2,…,SKidk, which correspond to identities id1,id2,…,idk and any ciphertext id1,id2,…,idk;c, output a bit μWe underline that we will homomorphically evaluate anyNAND circuit gate by gate as described in [17], which indicates that the evaluation is multi-hop as previous multi-key FHE schemes [8, 17].


### 2.3.1. Correctness

A leveled multi-hop MIFHE scheme is correct if it satisfies the following conditions. For all positive integersλ,d,L, for every NAND circuit f of depth at most d with N input wires, for every function π:N⟶L (which relates each input wire to a key pair), and for every μ∈0,1N, the following experiment succeeds with overwhelming probability: MPK,MSK←Setup1λ,1d,1L, generate identity key pairs PKidπi,SKidπi←ExtractMPK,MSK,idπi for every i∈N, generate ciphertext ci←EncMPK,idπi,μi∈0,1 for every i∈N, compute cf←EvalMPK,f,c1,c2,…,cN (may invoke algorithm Expand), and finally check whether DecSKidπii∈N,cf=fμ1,μ2,…,μN.


### 2.3.2. Compactness

A leveled multi-hop MIFHE scheme is compact if there exists a polynomialp·,·,· such that cf≤pλ,d,L in the experiment from Definition 4. In other words, the length of cf is independent of both f and N but can depend polynomially on λ,d, and L.


### 2.3.3. Security

The security game of MIFHE is the same as that of IBE, but there is no reference to the expansion algorithm and evaluation algorithm because they are public and do not impact the security. In this study, we will mainly focus on the semantically secure under selective identity and chosen-plaintext attack (IND-sID-CPA) security game for MIFHE between a challengerC and a PPT attacker A, which is defined as follows:(i)
Initial Stage. AttackerA is given bound d on the NAND circuit depth and bound L on the number of identities and outputs target identity id∗.(ii)
Setup. ChallengerC runs Setup1λ,1d,1L to generate MPK,MSK and sends MPK to attacker A.(iii)
Query Stage 1. AdversaryA adaptively issues a query on any identity id such that id≠id∗. Challenger C runs ExtractMPK,MSK,id to obtain identity secret key skid that corresponds to id and sends skid back to A.(iv)
Challenge. ChallengerC selects a uniformly random bit μ∗←$0,1, computes a challenge ciphertext c∗←EncMPK,id∗,μ∗, and sends it to attacker A.(v)
Query Stage 2. AdversaryA issues additional adaptive identity secret key queries, and challenger C responds as in query stage 1.(vi)
Output. The attacker outputs a guessμ′∈0,1 and wins if μ′=μ∗.The advantage of the attacker in the above IND-sID-CPA security game is defined asPrμ′=μ∗−1/2, where the probability is taken over the random bits used by all algorithms in the game.Definition 5.
A leveled multi-identity fully homomorphic encryption scheme isIND-sID-CPA secure if any PPT attacker has at most a negligible advantage in the IND-sID-CPA security game defined above.


## 2.3.1. Correctness

A leveled multi-hop MIFHE scheme is correct if it satisfies the following conditions. For all positive integersλ,d,L, for every NAND circuit f of depth at most d with N input wires, for every function π:N⟶L (which relates each input wire to a key pair), and for every μ∈0,1N, the following experiment succeeds with overwhelming probability: MPK,MSK←Setup1λ,1d,1L, generate identity key pairs PKidπi,SKidπi←ExtractMPK,MSK,idπi for every i∈N, generate ciphertext ci←EncMPK,idπi,μi∈0,1 for every i∈N, compute cf←EvalMPK,f,c1,c2,…,cN (may invoke algorithm Expand), and finally check whether DecSKidπii∈N,cf=fμ1,μ2,…,μN.


## 2.3.2. Compactness

A leveled multi-hop MIFHE scheme is compact if there exists a polynomialp·,·,· such that cf≤pλ,d,L in the experiment from Definition 4. In other words, the length of cf is independent of both f and N but can depend polynomially on λ,d, and L.


## 2.3.3. Security

The security game of MIFHE is the same as that of IBE, but there is no reference to the expansion algorithm and evaluation algorithm because they are public and do not impact the security. In this study, we will mainly focus on the semantically secure under selective identity and chosen-plaintext attack (IND-sID-CPA) security game for MIFHE between a challengerC and a PPT attacker A, which is defined as follows:(i)
Initial Stage. AttackerA is given bound d on the NAND circuit depth and bound L on the number of identities and outputs target identity id∗.(ii)
Setup. ChallengerC runs Setup1λ,1d,1L to generate MPK,MSK and sends MPK to attacker A.(iii)
Query Stage 1. AdversaryA adaptively issues a query on any identity id such that id≠id∗. Challenger C runs ExtractMPK,MSK,id to obtain identity secret key skid that corresponds to id and sends skid back to A.(iv)
Challenge. ChallengerC selects a uniformly random bit μ∗←$0,1, computes a challenge ciphertext c∗←EncMPK,id∗,μ∗, and sends it to attacker A.(v)
Query Stage 2. AdversaryA issues additional adaptive identity secret key queries, and challenger C responds as in query stage 1.(vi)
Output. The attacker outputs a guessμ′∈0,1 and wins if μ′=μ∗.The advantage of the attacker in the above IND-sID-CPA security game is defined asPrμ′=μ∗−1/2, where the probability is taken over the random bits used by all algorithms in the game.Definition 5.
A leveled multi-identity fully homomorphic encryption scheme isIND-sID-CPA secure if any PPT attacker has at most a negligible advantage in the IND-sID-CPA security game defined above.


## 3. Multi-Identity Fully Homomorphic Encryption

### 3.1. MIFHE Scheme

In this section, we will describe the proposed MIFHE scheme. We present one more algorithmMIFHE.NAND to help understand MIFHE.Eval.We parameterize the system by dimensionn=polyλ, modulus q, and error distribution χ for the underlying LWE problem; we set m=⌈6nlogq⌉, r=Onlogq·ωlogm, and B=Θrn. For the worst-case security, we set χ to be the standard discrete Gaussian distribution over ℤ with parameter 2n, which implies that the samples drawn from χ have magnitudes bounded by E=Θn except with probability 2−n. Modulus q is set in the following Section 3.2 based on the bound on the maximum depth of the supported circuit and the bound of the number of identities. The scheme is described as follows:(i)
MIFHE.Setup1λ,1d,1L: On inputting security parameter λ, bound d on the NAND circuit depth, and bound L on the number of identities in one evaluation, do(1)
Run algorithm TrapGenn,m−1,q to generate a uniformly random matrix A1∈ℤqn×m−1 with a short basis TA1∈ℤm−1×m−1 for Λq⊥A1 such that T˜A1≤Onlogq.(2)
Choose a vectora←$ℤqn and set A=A1‖a∈ℤqn×m.(3)
OutputMPK=A=A1‖a as the master public key and output MSK=TA1 as the master secret key.(ii)
MIFHE.ExtractMPK,MSK,id: on inputting MPK, MSK, and identity id∈ℐ, do:(1)
Ifid,u,SKid∈storage is from a previous inquiry on identity id, then return SKid. Otherwise, compute u=Hid∈ℤn, where H is a hash function modeled as a random oracle.(2)
RunSamplePreA1,TA1,u−a,r to output a vector s∈ℤm−1 such that A1s=u−a. Set user-specific secret key SKid=t=s,1, and store id,u,t locally. Note that At=u and t∞≤B.(3)
OutputSKid=t.(iii)
MIFHE.EncMPK,id,μ∈0,1: on inputting master public key MPK, identity id∈ℐ, and bit message μ∈0,1, do:(1)
Setu=Hid∈ℤn and compute B=A−enT⊗u∈ℤqn×m, where en is the nth standard unit (column) vector. (Remark: observe that Bt=0).(2)
Choose a uniformly random matrixQ←$ℤqn×mℓ and a discrete Gaussian matrix W←χm×mℓ, and define the following:(6)C=BTQ+W+μGm∈ℤqm×mℓ.Note thatC is nicely a GPV-FHE ciphertext [26] encrypting μ under the secret key t. In particular,(7)tTC=tTW+μtTGm≈μtTGm.errorβC(3)
Choose a matrixR←$ℤqn×mℓ and a discrete Gaussian matrix X←χm×mℓ, and define the following:(8)D=ATR+X+μGm∈ℤqm×mℓ.Here,D is regarded as a commitment to the message μ under commitment randomness R,X.(4)
Choose a matrixS←$ℤqn2ℓ×mℓ and a discrete Gaussian matrix Y←χnmℓ×mℓ, and define the following:(9)E=Inℓ⊗BTS+Y+R⊗g⊗em∈ℤqnmℓ×mℓ.Note that(10)Inℓ⊗tT·E=Inℓ⊗tT·Y+R⊗g⊗em≈R⊗g.errorβETherefore,E is regarded as a sort of encryption of R (the tensor product with g corresponding to some bit decomposition appeared in expansion algorithm is vital to control the error growth), the former part of the commitment randomness used in D.(5)
Choose a uniformly random matrixT←$ℤqnm×mℓ and a discrete Gaussian matrix Z←χm2×mℓ, and define the following:(11)F=Im⊗BTT+Z+X⊗em∈ℤqm2×mℓ.Note that:(12)Im⊗tT·F=Im⊗tT·Z+X⊗em≈X.errorβF.Therefore,F is regarded as a sort of encryption of X, the latter part of commitment randomness used in D.(6)
Output a “fresh” ciphertextid;C,D,E,F to identity id.(iv)
MIFHE.ExpandMPK,idk+1,id1,id2,…,idk;C,D,E,F: on inputting MPK, identity idk+1, and ciphertext id1,id2,…,idk;C∈ℤqmk×mkℓ,D∈ℤqm×mℓ,E∈ℤqnmkℓ×mℓ,F∈ℤqm2kℓ×mℓ encrypting μ under identities id1,id2,…,idk, do:(1)
Setuk+1=Hidk+1.(2)
We define the following:(13)C′=CU0D∈ℤqmk+1×mk+1ℓ,  where U is defined as follows:(14)U=Gn−T−uk+1⊗Imk·E∈ℤqmk×mℓ.(3)
We leave the commitment and its randomness unchanged:D′=D,R′=R, and X′=X.(4)
We define the following:(15)E′=Inℓ⊗Imk0m×mk·E∈ℤqnmk+1ℓ×mℓ.(5)
Similarly, we define the following:(16)F′=Im⊗Imk0m×mk·F∈ℤqm2k+1×mℓ.(6)
Outputid1,id2,…,idk+1;C′,D′,E′,F′ as the “expanded” ciphertext to identities id1,id2,…, idk+1.(v)
MIFHE.NAND(id1,id2,…,idk;C1,D1,E1,F1,id1,id2,…,idk;C2,D2,E2,F2): on inputting two ciphertexts id1,id2,…,idk;C1,D1,E1,F1,id1,id2,…,idk;C2,D2,E2,F2 that encrypt μ1,μ2 under identities id1,id2,…,idk, do:(1)
We define the following:(17)CNAND=Gmk−C1·Gmk−1C2∈ℤqmk×mkℓ.(2)
We define the following:(18)DNAND=Gm−D1·Gm−1D2∈ℤqm×mℓ.(3)
We define the following:(19)ENAND=−E1·Gm−1D2+Inℓ⊗C1·Gnmkℓ−1E2∈ℤqnmkℓ×mℓ.(4)
We define the following:(20)FNAND=−F1·Gm−1D2+Im⊗C1·Gm2k−1F2∈ℤqm2k×mℓ.(5)
Finally, outputid1,id2,…,idk;CNAND,DNAND,ENAND,FNAND as the “evaluated” NAND ciphertext.(vi)
MIFHE.EvalMPK,f,c1,c2,…,cN: on inputting MPK, NAND circuit f:0,1N⟶0,1, and any N ciphertexts c1,c2,…,cN, compute homomorphically f over any N ciphertexts c1,c2,…,cN gate by gate by invoking MIFHE.Expand and MIFHE.NAND, and output an “evaluated” ciphertext cf.(vii)
MIFHE.Dec(SKid1,SKid2,…,SKidk,id1,id2,…,idk;C,D,E,F): on inputting the secret keys SKid1,SKid2,…,SKidk and a ciphertext id1,id2,…,idk;C∈ℤqmk×mkℓ,D∈ℤqm×mℓ,E∈ℤqnmkℓ×mℓ,F∈ℤqm2k×mℓ under identities id1,id2,…,idk, let t∈ℤmk be the (column) concatenation of the secret keys SKid1,SKid2,…,SKidk, and compute:(21)tTC≈μtTGmk.errorβCIf βC<q/4, where q is set in the next section, we can recover μ from the last term of vector μtTGmk: if this term is closer to 0, output 0; otherwise, output 1.


### 3.2. Analyzing the Noise Growth and Setting the Parameters

Now, we provide the reasons for definitions and analyze the noise growth inMIFHE.Expand and MIFHE.NAND to easily set the parameters. We instantiate the parameters and ensure correctness of MIFHE.First, as described in the previous section in theMIFHE.Expand algorithm, let us do the following analysis:(1)
We have the following:(22)C′=CU0D∈ℤqmk+1×mk+1ℓ.Givent∈ℤmk that is the (column) concatenation of the secret keys corresponding to identities id1,id2,…,idk, respectively, and a new secret key tk+1, which is the secret key of idk+1, we set t′=t,tk+1 and then have the following:(23)t′T·C′=tT·C,tT·U+tk+1T·D,≈μtT·Gmk,tT·U+tk+1T·DerrorβC=μtT·Gmk,tT·Gn−T−uk+1⊗Imk·E+tk+1T·D=μtT·Gmk,Gn−T−uk+1⊗tT·E+tk+1T·D=μtT·Gmk,Gn−T−uk+1·Inℓ⊗tT·E+tk+1T·D=μtT·Gmk,Gn−T−uk+1·Inℓ⊗tT·Y+GnT·R+tk+1T·D≈μtT·Gmk,Gn−T−uk+1·GnT·R+tk+1T·DerrornℓβE=μtT·Gmk,−uk+1T·R+tk+1T·D=μtT·Gmk,−uk+1T·R+tk+1T·ATR+X+μGm=μtT·Gmk,−uk+1T·R+uk+1T·R+tk+1T·X+μtk+1T·Gm=μtT·Gmk,tk+1T·X+μtk+1T·Gm≈μtT·Gmk,μtk+1T·GmerrormBE=μt′T·Gmk+1, which indicates that (7) holds. In general, the error implied in the “expanded” ciphertext C′ is as follows:(24)βC′=βC+nℓβE+mBE.(2)
This visibly satisfies equation (8), and the error implied in the “expanded” ciphertext D′ is as follows:(25)βD′=βD.(3)
We have the following:(26)E′=Inℓ⊗Imk0m×mk·E∈ℤqnmk+1ℓ×mℓ.It is obvious that:(27)Inℓ⊗t′T·E′=Inℓ⊗tT·E≈R⊗g=R′⊗g.errorβE.Thus, (10) is kept up to expansion.(4)
We have the following:(28)F′=Im⊗Imk0m×mk·F∈ℤqm2k+1×mℓ.Similar to the above step, (12) is also kept up to expansion as follows:(29)Im⊗t′T·F′=Im⊗tT·F≈X=X′.errorβF.Second, we analyze theMIFHE.NAND algorithm.(1)
We have the following:(30)CNAND=Gmk−C1·Gmk−1C2∈ℤqmk×mkℓ.Witht∈ℤmk, which is the (column) concatenation of the secret keys that correspond to identities id1,id2,…,idk, we have the following:(31)tT·CNAND=tT·Gmk−C1·Gmk−1C2=tT·Gmk−tT·C1·Gmk−1C2≈tT·Gmk−μ1tT·Gmk·Gmk−1C2errormkℓ·βC1=tT·Gmk−μ1tT·C2≈tT·Gmk−μ1μ2tT·GmkerrorβC2=1−μ1μ2tT·Gmk, which indicates that (7) holds. In total, the error implied in the NAND ciphertext CNAND is as follows:(32)βCNAND=mkℓ·βC1+βC2.(2)
We have the following:(33)DNAND=Gm−D1·Gm−1D2∈ℤqm×mℓ,and the commitment randomness is as follows:(34)RNAND=−R1·Gm−1D2−μ1R2,XNAND=−X1·Gm−1D2−μ1X2.By simply computing, we can see that (8) is preserved:(35)DNAND=Gm−D1·Gm−1D2=Gm−ATR1+X1+μ1Gm·Gm−1D2=Gm−ATR1+X1·Gm−1D2−μ1D2=Gm−ATR1+X1·Gm−1D2−μ1ATR2+X2+μ2Gm=AT·−R1·Gm−1D2−μ1R2+−X1·Gm−1D2−μ1X2+1−μ1μ2Gm=AT·RNAND+XNAND+1−μ1μ2Gm.(3)
We have the following:(36)ENAND=−E1·Gm−1D2+Inℓ⊗C1·Gnmkℓ−1E2∈ℤqnmkℓ×mℓ.To see that (10) holds for ENAND, first note that:(37)Inℓ⊗tT·E1·Gm−1D2=Inℓ⊗tT·E1·Gm−1D2≈R1⊗g·Gm−1D2errormℓ·βE1=R1·Gm−1D2⊗g.Second, note that:(38)Inℓ⊗tT·Inℓ⊗C1·Gnmkℓ−1E2=Inℓ⊗tT·C1·Gnmkℓ−1E2≈Inℓ⊗μ1tT·Gmk·Gnmkℓ−1E2errornmkℓ2·βC1=μ1Inℓ⊗tT⊗gT·Gnmkℓ−1E2=μ1Inℓ⊗tT·Inmkℓ⊗gT·Gnmkℓ−1E2=μ1Inℓ⊗tT·E2≈μ1R2⊗g⋅errorβE2.Finally, from the above, we have the following:(39)Inℓ⊗tT·ENAND≈−R1·Gm−1D2−μ1R2⊗gerrornmkℓ2·βC1+mℓ·βE1+βE2=RNAND⊗g, which indicates that (10) holds.(4)
We have the following:(40)FNAND=−F1·Gm−1D2+Im⊗C1·Gm2k−1F2∈ℤqm2k×mℓ.To see that (12) holds for FNAND, first, note that:(41)Im⊗tT·F1·Gm−1D2=Im⊗tT·F1·Gm−1D2≈X1·Gm−1D2⋅errormℓ·βF1.Second, note that:(42)Im⊗tT·Im⊗C1·Gm2k−1F2=Im⊗tT·C1·Gm2k−1F2≈Im⊗μ1tT·Gmk·Gm2k−1F2errorm2kℓ·βC1=μ1Im⊗tT⊗gT·Gm2k−1F2=μ1Im⊗tT·Im2k⊗gT·Gm2k−1F2=μ1Im⊗tT·F2≈μ1X2⋅errorβF2.Finally, from the above, we have the following:(43)Im⊗tT·FNAND≈−X1·Gm−1D2−μ1X2errorm2kℓ·βC1+mℓ·βF1+βF2=XNAND, which indicates that (12) holds.Then, as [17], we now instantiate the parameters by bounding the worst-case error growth when homomorphically computing a depth dNAND circuit for up to L distinct identities. For a ciphertext id1,id2,…,idk;C,D,E,F with commitment randomness R,X, the max error is defined:(44)β=maxβC,βE,βF,BE.With the bounds from the above, for any ciphertext with errors bounded byβ, its “expanded” ciphertext has a max error of at most nℓ+m+1·β=polyn,ℓ·β. Similarly, when we homomorphically compute an NAND gate of two ciphertexts with errors bounded by β, the result has a max error of at most m2Lℓ+mℓ+1·β=polyn,ℓ,L·β. Thus, after computing any depth dNAND circuit on “fresh” ciphertexts under L distinct keys, then the result has a max error of at most:(45)polyn,ℓ,Ld+L.Thus, we can set4·polyn,ℓ,Ld+L=q for the correctness of decryption. Recall that ℓ=Θlogq=O˜d+L; therefore, polyn,ℓ,Ld+L=polyn,d,Ld+L. Thus, the security of our scheme corresponds to a worst-case n-dimensional lattice problem with an approximation factor of polyn,d,Ld+L.Finally, the compactness requirement is satisfied because any ciphertext in our construction is bounded bypolyn,d,L=polyλ,d,L.


### 3.3. Security

Now, we prove that the proposed scheme MIFHE is IND-sID-CPA secure under the hardness of the DLWE assumption in the random oracle model.Theorem 1.
The multi-hop multi-identity fully homomorphic encryption scheme MIFHE, which was constructed in Section 3.1, is IND-sID-CPA secure in the random oracle model assuming that the DLWEn,q,χassumption holds.Proof.
We prove the security of the proposed scheme MIFHE using a sequence of hybrid games. The first one of this game is the real IND-sID-CPA security game in Definition5, and the last one is the ideal game, where the challenge ciphertext (except challenge identity id∗) is uniformly random and independent of the challenge bit μ∗. We proceed by considering a sequence of hybrid games as follows:Game 0: This is the original game described in Definition5, and it is IND-sID-CPA security. Recall that id∗∈ℐ is the target identity; that is, attacker A plans to attack id∗, and the challenge ciphertext is id∗;C∗,D∗,E∗,F∗ encrypting μ∗.Game 1: In this game, we change the methods of generating master public keyA, answering hash (random oracle) queries and answering identity secret key queries as follows.(1)
Uniformly select at random a matrixA1←$ℤqn×m−1 and a vector a←$ℤqn, and set A=A1‖a∈ℤqn×m.(2)
Uniformly select at random a vectoruid∗←$ℤqn.(3)
When attackerA issues a hash query H on identity id∈ℐ, do:(a)
Ifid=id∗, return uid∗.(b)
Otherwise, ifid,uid,tid∈store, return uid.(c)
Otherwise, sample vectorsid∈Dℤm−1,r, and compute uid=A1sid+a, set tid=sid,1, and store id,uid,tid locally. Finally, return uid.(4)
When attackerA issues an identity secret key query on identity id∈ℐ, where id≠id∗, without loss of generality, we assume that A has queried H on id and return tid, where id,uid,tid∈store.Game 2: this game is the same as Game 1 except thatC∗,E∗,F∗, which is a part of the challenge ciphertext, is selected as uniformly random independent elements in ℤqm×mℓ×ℤqnmℓ×mℓ×ℤqm2×mℓ.Game 3: this game is the same as Game 2, except thatD∗ is selected as a uniformly random element in ℤqm×mℓ. In fact, Game 3 is the ideal game.
We show the indistinguishability among all sequential hybrid games.Lemma 4.
Game 0 and Game 1 are statistically indistinguishable.Proof.
We show that Game 0 is statistically close to Game 1 by analyzing that the changes are undetectable by any attacker between them step by step using Lemmas1–3.
First, note that while the former part of master public keyA1 is generated by running algorithm TrapGenn,m−1,q (with a trapdoor TA1) in Game 0, A1 is sampled from the uniform distribution over ℤqn×m−1 in Game 1. By Lemma 1, A1 in Game 0 is distributed statistically close to a uniform distribution over ℤqn×m−1 as in Game 1.
Second, in regard to the simulation of hash queryH, we discuss two cases:(1)
Ifid=id∗, then return uid∗, which was uniformly sampled from ℤqn at random. This perfectly simulates hash query Hid∗.(2)
Otherwise, sample a Gaussian vectorsid∈Dℤm−1,r, compute uid=A1sid+a, and return uid. Here, uid is distributed statistically close to the uniform distribution over ℤqn, since A1sid is distributed statistically close to uniform distribution over ℤqn by Lemma 2 and a←$ℤqn.
Finally, note that the identity secret key ofid is tid=sid,1, where sid is generated by running algorithm SamplePreA1,TA1,uid−a,r in Game 0, and the identity secret key of id is tid=sid,1, where sid is sampled from Dℤm−1,r such that uid=A1sid+a in Game 1. By Lemma 3, sid in Game 0 is distributed statistically close to DΛuid−a⊥A1,r such that A1sid=uid−a. Thus, the identity secret key tid in Game 0 is distributed statistically close to that in Game 1. Therefore, Game 0 and Game 1 are statistically indistinguishable.Lemma 5.
Game 1 and Game 2 are computationally indistinguishable.Proof.
The computational indistinguishability between Game 1 and Game 2 follows the assumed intractability of DLWE (and MLWE and TLWE). To show this behavior, we present a simulatorS that can draw samples and form B,C∗,E∗,F∗; it simulates Game 1 when the samples are DLWE samples; it simulates Game 2 when they are uniformly random samples. S proceeds as follows:(1)
Draw sufficient samples, and formB,C∗,E∗,F∗. Uniformly select at random a vector uid∗←$ℤqn, and let A=B+enT⊗uid∗∈ℤqn×m.(2)
The hash query and identity secret key query are identical to those in Game 1. GenerateD∗ exactly as in MIFHE.Enc.
Therefore, ifB,C∗,E∗,F∗ is sampled from DLWE, then S perfectly simulates Game 1. In contrast, if B,C∗,E∗,F∗ is uniformly random, then S simulates perfectly Game 2previous.Lemma 6.
Game 2 and Game 3 are computationally indistinguishable.Proof.
Similar to the previous proof of Lemma5, the computational indistinguishability between Game 2 and Game 3 follows the assumed intractability of DLWE (or MLWE). To show this effect, we present a simulator S that can draw samples and form A,D∗; it simulates Game 2 when the samples are DLWE samples; it simulates Game 3 when they are uniformly random samples. S proceeds as follows:(1)
Draw sufficient samples, and formA,D∗. Uniformly choose at random a vector uid∗←$ℤqn, and let B=A−enT⊗uid∗∈ℤqn×m.(2)
The hash query and identity secret key query are identical to those in Game 2. Uniformly choose randomC∗,E∗,F∗.
Therefore, ifA,D∗ is sampled from DLWE, then S perfectly simulates Game 2. In contrast, if A,D∗ is uniformly random, then S perfectly simulates Game 3.There is no information of messageμ∗ in Game 3. Additionally, Game 0 and Game 3 are computationally indistinguishable by Lemmas 4–6. Therefore, if the DLWE is difficult, attacker A only has negligible advantage, which completes the proof of the IND-sID-CPA security of MIFHE.


## 3.1. MIFHE Scheme

In this section, we will describe the proposed MIFHE scheme. We present one more algorithmMIFHE.NAND to help understand MIFHE.Eval.We parameterize the system by dimensionn=polyλ, modulus q, and error distribution χ for the underlying LWE problem; we set m=⌈6nlogq⌉, r=Onlogq·ωlogm, and B=Θrn. For the worst-case security, we set χ to be the standard discrete Gaussian distribution over ℤ with parameter 2n, which implies that the samples drawn from χ have magnitudes bounded by E=Θn except with probability 2−n. Modulus q is set in the following Section 3.2 based on the bound on the maximum depth of the supported circuit and the bound of the number of identities. The scheme is described as follows:(i)
MIFHE.Setup1λ,1d,1L: On inputting security parameter λ, bound d on the NAND circuit depth, and bound L on the number of identities in one evaluation, do(1)
Run algorithm TrapGenn,m−1,q to generate a uniformly random matrix A1∈ℤqn×m−1 with a short basis TA1∈ℤm−1×m−1 for Λq⊥A1 such that T˜A1≤Onlogq.(2)
Choose a vectora←$ℤqn and set A=A1‖a∈ℤqn×m.(3)
OutputMPK=A=A1‖a as the master public key and output MSK=TA1 as the master secret key.(ii)
MIFHE.ExtractMPK,MSK,id: on inputting MPK, MSK, and identity id∈ℐ, do:(1)
Ifid,u,SKid∈storage is from a previous inquiry on identity id, then return SKid. Otherwise, compute u=Hid∈ℤn, where H is a hash function modeled as a random oracle.(2)
RunSamplePreA1,TA1,u−a,r to output a vector s∈ℤm−1 such that A1s=u−a. Set user-specific secret key SKid=t=s,1, and store id,u,t locally. Note that At=u and t∞≤B.(3)
OutputSKid=t.(iii)
MIFHE.EncMPK,id,μ∈0,1: on inputting master public key MPK, identity id∈ℐ, and bit message μ∈0,1, do:(1)
Setu=Hid∈ℤn and compute B=A−enT⊗u∈ℤqn×m, where en is the nth standard unit (column) vector. (Remark: observe that Bt=0).(2)
Choose a uniformly random matrixQ←$ℤqn×mℓ and a discrete Gaussian matrix W←χm×mℓ, and define the following:(6)C=BTQ+W+μGm∈ℤqm×mℓ.Note thatC is nicely a GPV-FHE ciphertext [26] encrypting μ under the secret key t. In particular,(7)tTC=tTW+μtTGm≈μtTGm.errorβC(3)
Choose a matrixR←$ℤqn×mℓ and a discrete Gaussian matrix X←χm×mℓ, and define the following:(8)D=ATR+X+μGm∈ℤqm×mℓ.Here,D is regarded as a commitment to the message μ under commitment randomness R,X.(4)
Choose a matrixS←$ℤqn2ℓ×mℓ and a discrete Gaussian matrix Y←χnmℓ×mℓ, and define the following:(9)E=Inℓ⊗BTS+Y+R⊗g⊗em∈ℤqnmℓ×mℓ.Note that(10)Inℓ⊗tT·E=Inℓ⊗tT·Y+R⊗g⊗em≈R⊗g.errorβETherefore,E is regarded as a sort of encryption of R (the tensor product with g corresponding to some bit decomposition appeared in expansion algorithm is vital to control the error growth), the former part of the commitment randomness used in D.(5)
Choose a uniformly random matrixT←$ℤqnm×mℓ and a discrete Gaussian matrix Z←χm2×mℓ, and define the following:(11)F=Im⊗BTT+Z+X⊗em∈ℤqm2×mℓ.Note that:(12)Im⊗tT·F=Im⊗tT·Z+X⊗em≈X.errorβF.Therefore,F is regarded as a sort of encryption of X, the latter part of commitment randomness used in D.(6)
Output a “fresh” ciphertextid;C,D,E,F to identity id.(iv)
MIFHE.ExpandMPK,idk+1,id1,id2,…,idk;C,D,E,F: on inputting MPK, identity idk+1, and ciphertext id1,id2,…,idk;C∈ℤqmk×mkℓ,D∈ℤqm×mℓ,E∈ℤqnmkℓ×mℓ,F∈ℤqm2kℓ×mℓ encrypting μ under identities id1,id2,…,idk, do:(1)
Setuk+1=Hidk+1.(2)
We define the following:(13)C′=CU0D∈ℤqmk+1×mk+1ℓ,  where U is defined as follows:(14)U=Gn−T−uk+1⊗Imk·E∈ℤqmk×mℓ.(3)
We leave the commitment and its randomness unchanged:D′=D,R′=R, and X′=X.(4)
We define the following:(15)E′=Inℓ⊗Imk0m×mk·E∈ℤqnmk+1ℓ×mℓ.(5)
Similarly, we define the following:(16)F′=Im⊗Imk0m×mk·F∈ℤqm2k+1×mℓ.(6)
Outputid1,id2,…,idk+1;C′,D′,E′,F′ as the “expanded” ciphertext to identities id1,id2,…, idk+1.(v)
MIFHE.NAND(id1,id2,…,idk;C1,D1,E1,F1,id1,id2,…,idk;C2,D2,E2,F2): on inputting two ciphertexts id1,id2,…,idk;C1,D1,E1,F1,id1,id2,…,idk;C2,D2,E2,F2 that encrypt μ1,μ2 under identities id1,id2,…,idk, do:(1)
We define the following:(17)CNAND=Gmk−C1·Gmk−1C2∈ℤqmk×mkℓ.(2)
We define the following:(18)DNAND=Gm−D1·Gm−1D2∈ℤqm×mℓ.(3)
We define the following:(19)ENAND=−E1·Gm−1D2+Inℓ⊗C1·Gnmkℓ−1E2∈ℤqnmkℓ×mℓ.(4)
We define the following:(20)FNAND=−F1·Gm−1D2+Im⊗C1·Gm2k−1F2∈ℤqm2k×mℓ.(5)
Finally, outputid1,id2,…,idk;CNAND,DNAND,ENAND,FNAND as the “evaluated” NAND ciphertext.(vi)
MIFHE.EvalMPK,f,c1,c2,…,cN: on inputting MPK, NAND circuit f:0,1N⟶0,1, and any N ciphertexts c1,c2,…,cN, compute homomorphically f over any N ciphertexts c1,c2,…,cN gate by gate by invoking MIFHE.Expand and MIFHE.NAND, and output an “evaluated” ciphertext cf.(vii)
MIFHE.Dec(SKid1,SKid2,…,SKidk,id1,id2,…,idk;C,D,E,F): on inputting the secret keys SKid1,SKid2,…,SKidk and a ciphertext id1,id2,…,idk;C∈ℤqmk×mkℓ,D∈ℤqm×mℓ,E∈ℤqnmkℓ×mℓ,F∈ℤqm2k×mℓ under identities id1,id2,…,idk, let t∈ℤmk be the (column) concatenation of the secret keys SKid1,SKid2,…,SKidk, and compute:(21)tTC≈μtTGmk.errorβCIf βC<q/4, where q is set in the next section, we can recover μ from the last term of vector μtTGmk: if this term is closer to 0, output 0; otherwise, output 1.


## 3.2. Analyzing the Noise Growth and Setting the Parameters

Now, we provide the reasons for definitions and analyze the noise growth inMIFHE.Expand and MIFHE.NAND to easily set the parameters. We instantiate the parameters and ensure correctness of MIFHE.First, as described in the previous section in theMIFHE.Expand algorithm, let us do the following analysis:(1)
We have the following:(22)C′=CU0D∈ℤqmk+1×mk+1ℓ.Givent∈ℤmk that is the (column) concatenation of the secret keys corresponding to identities id1,id2,…,idk, respectively, and a new secret key tk+1, which is the secret key of idk+1, we set t′=t,tk+1 and then have the following:(23)t′T·C′=tT·C,tT·U+tk+1T·D,≈μtT·Gmk,tT·U+tk+1T·DerrorβC=μtT·Gmk,tT·Gn−T−uk+1⊗Imk·E+tk+1T·D=μtT·Gmk,Gn−T−uk+1⊗tT·E+tk+1T·D=μtT·Gmk,Gn−T−uk+1·Inℓ⊗tT·E+tk+1T·D=μtT·Gmk,Gn−T−uk+1·Inℓ⊗tT·Y+GnT·R+tk+1T·D≈μtT·Gmk,Gn−T−uk+1·GnT·R+tk+1T·DerrornℓβE=μtT·Gmk,−uk+1T·R+tk+1T·D=μtT·Gmk,−uk+1T·R+tk+1T·ATR+X+μGm=μtT·Gmk,−uk+1T·R+uk+1T·R+tk+1T·X+μtk+1T·Gm=μtT·Gmk,tk+1T·X+μtk+1T·Gm≈μtT·Gmk,μtk+1T·GmerrormBE=μt′T·Gmk+1, which indicates that (7) holds. In general, the error implied in the “expanded” ciphertext C′ is as follows:(24)βC′=βC+nℓβE+mBE.(2)
This visibly satisfies equation (8), and the error implied in the “expanded” ciphertext D′ is as follows:(25)βD′=βD.(3)
We have the following:(26)E′=Inℓ⊗Imk0m×mk·E∈ℤqnmk+1ℓ×mℓ.It is obvious that:(27)Inℓ⊗t′T·E′=Inℓ⊗tT·E≈R⊗g=R′⊗g.errorβE.Thus, (10) is kept up to expansion.(4)
We have the following:(28)F′=Im⊗Imk0m×mk·F∈ℤqm2k+1×mℓ.Similar to the above step, (12) is also kept up to expansion as follows:(29)Im⊗t′T·F′=Im⊗tT·F≈X=X′.errorβF.Second, we analyze theMIFHE.NAND algorithm.(1)
We have the following:(30)CNAND=Gmk−C1·Gmk−1C2∈ℤqmk×mkℓ.Witht∈ℤmk, which is the (column) concatenation of the secret keys that correspond to identities id1,id2,…,idk, we have the following:(31)tT·CNAND=tT·Gmk−C1·Gmk−1C2=tT·Gmk−tT·C1·Gmk−1C2≈tT·Gmk−μ1tT·Gmk·Gmk−1C2errormkℓ·βC1=tT·Gmk−μ1tT·C2≈tT·Gmk−μ1μ2tT·GmkerrorβC2=1−μ1μ2tT·Gmk, which indicates that (7) holds. In total, the error implied in the NAND ciphertext CNAND is as follows:(32)βCNAND=mkℓ·βC1+βC2.(2)
We have the following:(33)DNAND=Gm−D1·Gm−1D2∈ℤqm×mℓ,and the commitment randomness is as follows:(34)RNAND=−R1·Gm−1D2−μ1R2,XNAND=−X1·Gm−1D2−μ1X2.By simply computing, we can see that (8) is preserved:(35)DNAND=Gm−D1·Gm−1D2=Gm−ATR1+X1+μ1Gm·Gm−1D2=Gm−ATR1+X1·Gm−1D2−μ1D2=Gm−ATR1+X1·Gm−1D2−μ1ATR2+X2+μ2Gm=AT·−R1·Gm−1D2−μ1R2+−X1·Gm−1D2−μ1X2+1−μ1μ2Gm=AT·RNAND+XNAND+1−μ1μ2Gm.(3)
We have the following:(36)ENAND=−E1·Gm−1D2+Inℓ⊗C1·Gnmkℓ−1E2∈ℤqnmkℓ×mℓ.To see that (10) holds for ENAND, first note that:(37)Inℓ⊗tT·E1·Gm−1D2=Inℓ⊗tT·E1·Gm−1D2≈R1⊗g·Gm−1D2errormℓ·βE1=R1·Gm−1D2⊗g.Second, note that:(38)Inℓ⊗tT·Inℓ⊗C1·Gnmkℓ−1E2=Inℓ⊗tT·C1·Gnmkℓ−1E2≈Inℓ⊗μ1tT·Gmk·Gnmkℓ−1E2errornmkℓ2·βC1=μ1Inℓ⊗tT⊗gT·Gnmkℓ−1E2=μ1Inℓ⊗tT·Inmkℓ⊗gT·Gnmkℓ−1E2=μ1Inℓ⊗tT·E2≈μ1R2⊗g⋅errorβE2.Finally, from the above, we have the following:(39)Inℓ⊗tT·ENAND≈−R1·Gm−1D2−μ1R2⊗gerrornmkℓ2·βC1+mℓ·βE1+βE2=RNAND⊗g, which indicates that (10) holds.(4)
We have the following:(40)FNAND=−F1·Gm−1D2+Im⊗C1·Gm2k−1F2∈ℤqm2k×mℓ.To see that (12) holds for FNAND, first, note that:(41)Im⊗tT·F1·Gm−1D2=Im⊗tT·F1·Gm−1D2≈X1·Gm−1D2⋅errormℓ·βF1.Second, note that:(42)Im⊗tT·Im⊗C1·Gm2k−1F2=Im⊗tT·C1·Gm2k−1F2≈Im⊗μ1tT·Gmk·Gm2k−1F2errorm2kℓ·βC1=μ1Im⊗tT⊗gT·Gm2k−1F2=μ1Im⊗tT·Im2k⊗gT·Gm2k−1F2=μ1Im⊗tT·F2≈μ1X2⋅errorβF2.Finally, from the above, we have the following:(43)Im⊗tT·FNAND≈−X1·Gm−1D2−μ1X2errorm2kℓ·βC1+mℓ·βF1+βF2=XNAND, which indicates that (12) holds.Then, as [17], we now instantiate the parameters by bounding the worst-case error growth when homomorphically computing a depth dNAND circuit for up to L distinct identities. For a ciphertext id1,id2,…,idk;C,D,E,F with commitment randomness R,X, the max error is defined:(44)β=maxβC,βE,βF,BE.With the bounds from the above, for any ciphertext with errors bounded byβ, its “expanded” ciphertext has a max error of at most nℓ+m+1·β=polyn,ℓ·β. Similarly, when we homomorphically compute an NAND gate of two ciphertexts with errors bounded by β, the result has a max error of at most m2Lℓ+mℓ+1·β=polyn,ℓ,L·β. Thus, after computing any depth dNAND circuit on “fresh” ciphertexts under L distinct keys, then the result has a max error of at most:(45)polyn,ℓ,Ld+L.Thus, we can set4·polyn,ℓ,Ld+L=q for the correctness of decryption. Recall that ℓ=Θlogq=O˜d+L; therefore, polyn,ℓ,Ld+L=polyn,d,Ld+L. Thus, the security of our scheme corresponds to a worst-case n-dimensional lattice problem with an approximation factor of polyn,d,Ld+L.Finally, the compactness requirement is satisfied because any ciphertext in our construction is bounded bypolyn,d,L=polyλ,d,L.


## 3.3. Security

Now, we prove that the proposed scheme MIFHE is IND-sID-CPA secure under the hardness of the DLWE assumption in the random oracle model.Theorem 1.
The multi-hop multi-identity fully homomorphic encryption scheme MIFHE, which was constructed in Section 3.1, is IND-sID-CPA secure in the random oracle model assuming that the DLWEn,q,χassumption holds.Proof.
We prove the security of the proposed scheme MIFHE using a sequence of hybrid games. The first one of this game is the real IND-sID-CPA security game in Definition5, and the last one is the ideal game, where the challenge ciphertext (except challenge identity id∗) is uniformly random and independent of the challenge bit μ∗. We proceed by considering a sequence of hybrid games as follows:Game 0: This is the original game described in Definition5, and it is IND-sID-CPA security. Recall that id∗∈ℐ is the target identity; that is, attacker A plans to attack id∗, and the challenge ciphertext is id∗;C∗,D∗,E∗,F∗ encrypting μ∗.Game 1: In this game, we change the methods of generating master public keyA, answering hash (random oracle) queries and answering identity secret key queries as follows.(1)
Uniformly select at random a matrixA1←$ℤqn×m−1 and a vector a←$ℤqn, and set A=A1‖a∈ℤqn×m.(2)
Uniformly select at random a vectoruid∗←$ℤqn.(3)
When attackerA issues a hash query H on identity id∈ℐ, do:(a)
Ifid=id∗, return uid∗.(b)
Otherwise, ifid,uid,tid∈store, return uid.(c)
Otherwise, sample vectorsid∈Dℤm−1,r, and compute uid=A1sid+a, set tid=sid,1, and store id,uid,tid locally. Finally, return uid.(4)
When attackerA issues an identity secret key query on identity id∈ℐ, where id≠id∗, without loss of generality, we assume that A has queried H on id and return tid, where id,uid,tid∈store.Game 2: this game is the same as Game 1 except thatC∗,E∗,F∗, which is a part of the challenge ciphertext, is selected as uniformly random independent elements in ℤqm×mℓ×ℤqnmℓ×mℓ×ℤqm2×mℓ.Game 3: this game is the same as Game 2, except thatD∗ is selected as a uniformly random element in ℤqm×mℓ. In fact, Game 3 is the ideal game.
We show the indistinguishability among all sequential hybrid games.Lemma 4.
Game 0 and Game 1 are statistically indistinguishable.Proof.
We show that Game 0 is statistically close to Game 1 by analyzing that the changes are undetectable by any attacker between them step by step using Lemmas1–3.
First, note that while the former part of master public keyA1 is generated by running algorithm TrapGenn,m−1,q (with a trapdoor TA1) in Game 0, A1 is sampled from the uniform distribution over ℤqn×m−1 in Game 1. By Lemma 1, A1 in Game 0 is distributed statistically close to a uniform distribution over ℤqn×m−1 as in Game 1.
Second, in regard to the simulation of hash queryH, we discuss two cases:(1)
Ifid=id∗, then return uid∗, which was uniformly sampled from ℤqn at random. This perfectly simulates hash query Hid∗.(2)
Otherwise, sample a Gaussian vectorsid∈Dℤm−1,r, compute uid=A1sid+a, and return uid. Here, uid is distributed statistically close to the uniform distribution over ℤqn, since A1sid is distributed statistically close to uniform distribution over ℤqn by Lemma 2 and a←$ℤqn.
Finally, note that the identity secret key ofid is tid=sid,1, where sid is generated by running algorithm SamplePreA1,TA1,uid−a,r in Game 0, and the identity secret key of id is tid=sid,1, where sid is sampled from Dℤm−1,r such that uid=A1sid+a in Game 1. By Lemma 3, sid in Game 0 is distributed statistically close to DΛuid−a⊥A1,r such that A1sid=uid−a. Thus, the identity secret key tid in Game 0 is distributed statistically close to that in Game 1. Therefore, Game 0 and Game 1 are statistically indistinguishable.Lemma 5.
Game 1 and Game 2 are computationally indistinguishable.Proof.
The computational indistinguishability between Game 1 and Game 2 follows the assumed intractability of DLWE (and MLWE and TLWE). To show this behavior, we present a simulatorS that can draw samples and form B,C∗,E∗,F∗; it simulates Game 1 when the samples are DLWE samples; it simulates Game 2 when they are uniformly random samples. S proceeds as follows:(1)
Draw sufficient samples, and formB,C∗,E∗,F∗. Uniformly select at random a vector uid∗←$ℤqn, and let A=B+enT⊗uid∗∈ℤqn×m.(2)
The hash query and identity secret key query are identical to those in Game 1. GenerateD∗ exactly as in MIFHE.Enc.
Therefore, ifB,C∗,E∗,F∗ is sampled from DLWE, then S perfectly simulates Game 1. In contrast, if B,C∗,E∗,F∗ is uniformly random, then S simulates perfectly Game 2previous.Lemma 6.
Game 2 and Game 3 are computationally indistinguishable.Proof.
Similar to the previous proof of Lemma5, the computational indistinguishability between Game 2 and Game 3 follows the assumed intractability of DLWE (or MLWE). To show this effect, we present a simulator S that can draw samples and form A,D∗; it simulates Game 2 when the samples are DLWE samples; it simulates Game 3 when they are uniformly random samples. S proceeds as follows:(1)
Draw sufficient samples, and formA,D∗. Uniformly choose at random a vector uid∗←$ℤqn, and let B=A−enT⊗uid∗∈ℤqn×m.(2)
The hash query and identity secret key query are identical to those in Game 2. Uniformly choose randomC∗,E∗,F∗.
Therefore, ifA,D∗ is sampled from DLWE, then S perfectly simulates Game 2. In contrast, if A,D∗ is uniformly random, then S perfectly simulates Game 3.There is no information of messageμ∗ in Game 3. Additionally, Game 0 and Game 3 are computationally indistinguishable by Lemmas 4–6. Therefore, if the DLWE is difficult, attacker A only has negligible advantage, which completes the proof of the IND-sID-CPA security of MIFHE.


## 4. Conclusion and Open Problem

We present a multi-hop MIFHE scheme, which is IND-sID-CPA secure in the random oracle model under the standard LWE assumption. However, the proposed MIFHE scheme is only leveled homomorphic. Therefore, it is interesting to construct a nonleveled multi-hop MIFHE scheme (i.e., there is no a priori bound on the depth of the circuits) under standard assumptions such as LWE (without unfalsifiableiO or WPRF).



---

*Source: 1023439-2022-03-22.xml*