# NTRU-Based Fully Homomorphic Signature

Authors: Ruonan Li; Fuqun Wang; Renjun Zhang; Kefei Chen
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Although the fully homomorphic signature (FHS) has made great progress, the low efficiency of existing FHS schemes as one main drawback cannot reach the requirements in practical application. It is well known that Number-Theory-Research-Unit (NTRU)-based cryptography is not only considered to be resistant to the quantum computer but also has high efficiency compared with the standard lattice-based cryptographic systems. In this paper, our goal is to construct a simple and highly efficient FHS scheme. To this end, we first devise an NTRU-based homomorphic trapdoor function (HTDF), which is more effective than the one proposed by Gorbunov et al. (STOC 2015). We then convert it into an efficient NTRU-based FHS scheme. Additionally, the HTDF we constructed is not only collision-resistant but is also claw-free, resulting in our FHS scheme is being strongly unforgeable.


---

## Body

## 1. Introduction

As the advantages of cloud computing increase, fully homomorphic cryptography has aroused great interest due to its remarkable characteristics. It not only allows the client to safely upload his/her data to some unreliable clouds but also allows the server to perform calculations on the data. Fully homomorphic cryptography consists of fully homomorphic encryption (FHE) and fully homomorphic signature (FHS). Gentry [1] designed the first fully homomorphic encryption system at STOC 2009 and Gorbunov et al. [2] constructed the first leveled fully homomorphic signature scheme at STOC 2015. In this work, we mainly discuss the issues related to FHS.Rivest [3] first proposed the concept of homomorphic signature (HS) in 2000. Two years later, Johnson et al. [4] gave a security model and designed several provable secure HS schemes. In a HS scheme, a user signs a data m=m1,…,mk in the message space ℳ using his/her signing key and then distributes the signed data σ=σ1,…,σk to some unreliable remote server. The server can run arbitrary computations y=gm over the signed data σ and homomorphically derive a short signature σg,y, which can verify that y is indeed the correct output of g operation on message m. Anyone can check the tuple g,y,σg,y by employing the user’s public verification key and then determine that y is indeed the correct outcome of g′s calculation on m. In addition, the verification process does not need the underlying data m.According to the homomorphic capability of HS schemes, we can divide the homomorphic signature schemes into three categories: linear homomorphic signature, somewhat homomorphic signature (SHS), and fully homomorphic signature.Zhao et al. [5] proposed a linear HS scheme to resolve the inherent network pollution problem in network coding. This scheme allows an arbitrary linear combination calculation of the signature data, which can both conveniently verify the integrity of the received message and effectively prevent the application built on the network code from being attacked by pollution. In further research studies, many papers [6–11] have made further improvements in efficiency, security, and privacy protection.In 2011, Boneh and Freeman [12] constructed the first SHS scheme, which is selectively secure in the random oracle (RO) model. Subsequently, Catalano et al. [13] proposed a new SHS scheme, which is adaptively secure, whose security no longer depends on RO model, and whose verification process is more efficient.Different from the abovementioned homomorphic signature schemes, the FHS allows polynomial depth circuit operations on the signed data. In 2014, Gorbunov et al. [2] proposed the first leveled FHS scheme based on the hardness of the small integer solution (SIS) problem in standard lattices [14, 15]. To this end, a building block called the homomorphic trapdoor function (HTDF) is proposed. This new cryptographic primitive helps us to conceptually unify digital signatures [16–18] and fully homomorphic encryption [19]. They showed that if an HTDF function is claw-free, then you can directly use the HTDF function to construct an existentially unforgeable FHS scheme under a selective chosen-message attack (EU-sCMA), and that an EU-sCMA secure FHS can be converted into an existentially unforgeable under the adaptive chosen-message attack (EU-aCMA) one with the help of HTDF functions. Additionally, this solution has the following advantages: First, it allows quick amortization verification of calculations on multiple different datasets, even though these datasets belong to different users with different verification keys. Second, the scheme can be made context hiding, that is, the signature σg,y corresponding to y=gm will not expose any information about the underlying data m. Third, the scheme also allows several different calculations to be combined on signed data. Inspired by the key-homomorphic function encryption of the circuit, Boyen et al. [20] constructed the first adaptively secure homomorphic signature scheme utilizing the vanishing trapdoor technique [21]. Compared with Gorbunov et al. FHS, the efficiency of this scheme has been significantly improved, and it can fight against stronger adversaries, but this scheme does not reach context hiding. Later, Tsabary [22] demonstrated the equivalence between FHS and attribute-based signature (ABS) [23]. They can be implied by each other under certain conditions, which opens up a new direction for constructing FHS schemes. Furthermore, Tsabary built an ABS from lattices and converted it into a new FHS scheme. All the abovementioned existing HS algorithms can only produce one signature for a single message at a time, which is inefficient. Therefore, Luo et al. [24] proposed a new leveled fully homomorphic signature scheme, which generates signatures for all messages in the dataset only by calling the signature algorithm twice. To the end, the vector coding technique [25] is used, which encodes all messages in the dataset into two matrices.In addition, Wang et al. [26] constructed an identity-based HTDF IBHTDF, which has better parameters and stronger security. The maximum noise compared with Gorbunov et al. HTDF is roughly reduced from Omdβ to O4dmβ, which will lead to a polynomial modulus q=ployλ when d=Ologλ, where d is the maximum depth of the circuit and λ is the security parameter. The stronger security requires that IBHTDF be not only claw-free but also collision-resistant. Then, they converted the abovementioned IBHTDF into a leveled strongly unforgeable IBFHS scheme. However, the leveled IBFHS scheme is only secure in the selective security model under the hardness of the SIS problem. Recently, Wang et al. [27] used trapdoor vanishing [21] and vector coding techniques [25] to construct an efficient leveled strongly unforgeable IBFHS scheme based on the SIS problem on arbitrary lattices. Compared with [26], this scheme is adaptively secure against chosen identity and chosen message attacks under the standard SIS assumption. Concurrently, Wang and Wang [28] constructed a new leveled strongly unforgeable IBFHS scheme based on a new IBHTDF, whose homomorphic multiplication operation is very similar to the homomorphic addition operation, resulting in that the noise level of IBHTDF is used to evaluate circuits with depth d was reduced from O4dmβ in [26] to O2dβ.


### 1.1. Motivation and Contribution

Fully homomorphic signature is an important branch of digital signatures, which plays a significant role in the information age. At present, many achievements have been made in this research field. To our best knowledge, the existing FHS schemes are constructed on the standard lattices. They are not practical because of their low efficiency. Therefore, it is intriguing to design more efficient FHS schemes.In 1998, Hoffstein et al. [29] put forward a new public key cryptography system called NTRU. NTRU features relatively short, easy to create key, high speed, and low memory requirements. The security of the NTRU cryptosystem comes from the interaction of the polynomial hybrid system and the independence of the reduced modulus of two relatively prime integers p and q. Stehlé and Steinfeld [30] present a provably secure NTRU-based signature (denoted by NTRUSign in this work) scheme, which is a novel adaption of the unfledged and heuristic NTRU-based signature scheme [31] and the standard lattice-based signature scheme [16]. However, NTRUSign has no homomorphic property. Therefore, it is necessary to design an NTRU-based FHS.Following the blueprint of [2, 26], we first devise an NTRU-based HTDF function from the NTRUSign proposed by Stehlé et al., which is both collision-resistant and claw-free. We then convert it into a strongly unforgeable FHS scheme.We point out that when only performing polylog-depth circuits, we can compute them by Barrington’s theorem [32]. Hence, a polynomial modulus is enough, resulting in improved efficiency and security [26]. In addition, we also could choose the ring X/Xn−1+⋯+X+1 used in [33] to construct an FHS scheme with similar efficiency.


### 1.2. Paper Organization

In Section2, we provide some background used in this work. We then formally describe our NTRU-based HTDF functions in Section 3 and NTRU-based FHS in Section 4. Finally, we conclude in Section 5.


## 1.1. Motivation and Contribution

Fully homomorphic signature is an important branch of digital signatures, which plays a significant role in the information age. At present, many achievements have been made in this research field. To our best knowledge, the existing FHS schemes are constructed on the standard lattices. They are not practical because of their low efficiency. Therefore, it is intriguing to design more efficient FHS schemes.In 1998, Hoffstein et al. [29] put forward a new public key cryptography system called NTRU. NTRU features relatively short, easy to create key, high speed, and low memory requirements. The security of the NTRU cryptosystem comes from the interaction of the polynomial hybrid system and the independence of the reduced modulus of two relatively prime integers p and q. Stehlé and Steinfeld [30] present a provably secure NTRU-based signature (denoted by NTRUSign in this work) scheme, which is a novel adaption of the unfledged and heuristic NTRU-based signature scheme [31] and the standard lattice-based signature scheme [16]. However, NTRUSign has no homomorphic property. Therefore, it is necessary to design an NTRU-based FHS.Following the blueprint of [2, 26], we first devise an NTRU-based HTDF function from the NTRUSign proposed by Stehlé et al., which is both collision-resistant and claw-free. We then convert it into a strongly unforgeable FHS scheme.We point out that when only performing polylog-depth circuits, we can compute them by Barrington’s theorem [32]. Hence, a polynomial modulus is enough, resulting in improved efficiency and security [26]. In addition, we also could choose the ring X/Xn−1+⋯+X+1 used in [33] to construct an FHS scheme with similar efficiency.


## 1.2. Paper Organization

In Section2, we provide some background used in this work. We then formally describe our NTRU-based HTDF functions in Section 3 and NTRU-based FHS in Section 4. Finally, we conclude in Section 5.


## 2. Preliminaries

Throughout, we use the bold lowercase letters (e.g.,a⟶) to denote row vectors. We use the a⟶i to denote the i-th entry of a⟶ and a⟶∞=maxia⟶i∞ to represent the infinity norm of a⟶. Sometimes, we denote u⟶=u⟶1,u⟶2∈R2×ℓ and u⟶=u⟶1,u⟶2∈R2ℓ. We let n denote the set n=1,2,…,n.LetRx/ϕx denote the rings for some integer polynomials ϕx∈x of degree n. In this paper, we use the cyclotomic polynomial ϕx=xn+1, where n=2k for positive integer k and Rq≜R/qR for some integer q which is isomorphic to ℤqx/ϕx. We represent elements in Rq as ax=a0+a1x+⋯+an−1xn−1, where its coefficients are in the range −q/2,q/2 and the infinity norm of a is a∞=maxai.Then, we introduced a parameterλ and a negligible function negl λ. λ is used to denote the security parameter. The growth negl λ is slower than λ−c for any constant c>0 and any sufficiently large value of λ. An event with an overwhelming probability is equivalent to its occurrence with a probability of at least 1−neglλ.


### 2.1. Basic Notions

#### 2.1.1. Distributions

For a probability distributionD, we use x←D to denote that x is sampled according to D. For a set S, we use y←$SS to denote that y is sampled uniformly at random from S. For two distributions D1 and D2, D1≈cD2 and D1≈sD2 denote that D1 and D2 are computationally indistinguishable and statistically indistinguishable, respectively.


#### 2.1.2. Entropy

The min entropy of a random variableX, denoted by H∞X, is defined as H∞X≜−logmaxxPrX=x. The average min entropy of X conditioned on Y, denoted with H˜∞X|Y, is defined as follows:(1)H˜∞X|Y≜−logEy←YmaxxPrX=x|Y=y=−logEy←Y2−H∞X|Y=y.Given the correlation valueY, the optimal probability of an infinite attacker predicting X is 2−H˜∞X|Y.


#### 2.1.3.B-Bounded

A distribution ensembleχkk∈ℕ, supported over the ring R, is called B-bounded if Pra←χka∞≤B=1.Lemma 1.
(see [34]). In a ring R=≜x/xn+1, for any two polynomials a,b∈R, we have the following norm ab∞≤na∞⋅b∞.Lemma 2.
(see [34]). In a ring R=≜x/xn+1, let χ be a B-bounded distribution over R, let a1,…,am←χ. Then, the value of ∏i=1mai is nm−1Bm bounded.


### 2.2. Gaussian and Discrete Gaussian

Forr>0, the Gaussian function ρr,c⟶x⟶, supported on ℝn and centered at c⟶ with parameter r and x∈ℝn, is defined as follows: ρr,c⟶x⟶≜e−πx⟶−c⟶2/r2.


#### 2.2.1. Discrete Gaussian Distribution

Forr>0, the discrete Gaussian function ρr,c⟶x⟶, supported on ℤn and centered at c⟶ with parameter r and x∈ℤn, is defined as follows: Dℤn,r,c⟶≜ρr,c⟶x⟶/ρr,c⟶ℤn. When c equals 0, it is denoted by Dℤn,r. Take note that the following Lemma illustrates that a discrete Gaussian distribution Dℤn,r outputs a rn-bounded polynomial with overwhelming probability. So, we define a rn-bounded distribution called truncated Gaussian distribution which is statistically indistinguishable from discrete Gaussian distribution.Lemma 3.
(see [34]). For n=ωlogλ and r>ωlogn, it holds that Prx←Dℤn,rx>rn≤2−n+1=neglλ.The truncated discrete Gaussian distribution centered at 0 and denoted byD¯ℤ,r is that sample polynomials from Dℤn,r, and if the polynomial is not rn-bounded, then discards it and repeats the sampling. According to Lemma 3, if n=ωlogλ and r>ωlogn, then we have D¯ℤ,r≈sDℤn,r.


### 2.3. Lattices

#### 2.3.1. RSIS

Choosem polynomials a⟶=a⟶1,…,a⟶m∈Rqm uniformly and independently, find x⟶∈Rqm/0 such that ∑ia⟶ix⟶i=0modq and x⟶≤β, then this problem is called RSIS q,m,β.The following theorem shows that there is a reduction from the average-case hardness of RSIS to the worst-case hardness of ideal-SVP as follows:Theorem 1.
(see [30]). For n=2k, ϕx=xn+1 and ε>0. Let m,q>0 such that q>βn⋅ωlogn and m,logq≤polyn. A polynomial-time algorithm solving RSISq,m,β with overwhelming probability can be used to solve Ideal-SVPγ in polynomial time with the approximate factor γ≥βn⋅ωlogn.


#### 2.3.2. Lattice Trapdoor

In this paper, for an odd integerq and ℓ=logq, we use the “powers of two” gadget g⟶=1,2,…,2ℓ−1∈Rqℓ first introduced by Micciancio and Peikert. [18]. For a⟶∈Rqℓ, g⟶−1⋅ is the deterministic bit decomposition function, which outputs a matrix X∈R2ℓ×ℓ so as to X=g⟶−1a⟶ and g⟶⋅X=a⟶.Lemma 4.
(see [30]). There are three efficient algorithms as follows:(1)
TrapGen1n,q,σ: It runs the NTRUSign key generation algorithm same as [30] and returns h,td. Recall that h=gf−1∈Rq∗ is a signing key and td=fgFG is the corresponding trapdoor R-basis for the R module h⊥=u=u1,u2∈R1×2:h,−1u=hu1−u2=0modq.(2)
SamDom12ℓ,q: It samples u⟶=u⟶1,u⟶2∈R2×ℓ such that u⟶∞≤βsam with probability 1.(3)
SamPreh,v⟶,td: Given h∈Rq∗,v⟶∈Rqℓ and the trapdoor td, it returns u⟶=u⟶1,u⟶2∈R2×ℓ such that h,−1u⟶=hu⟶1−u⟶2=v⟶modq and u⟶∞≤βsam with probability 1.(4)
We have the statistical indistinguishability:(2)h≈sh′andh,td,u⟶,v⟶≈sh,td,u⟶′,v⟶′,where h,td←TrapGen1n,q,σ,h′←$Rq∗, and u⟶←SamDom12ℓ,q,v⟶=h,−1u⟶modq,v⟶′←$Rqℓ,u⟶′←SamPreh,v⟶′,td.


### 2.4. Permutation Branching Program

Then, a permutation branching programΠ is defined as follows [35]. Π with input space of 0,1t, length L, and width w is a sequence of L tuples of the form rk,σk,0,σk,1 where.r:L⟶t is a function associates the k-th tuple with an input bit xrk.σk,0,σk,1 are permutations over w=1,2,…,w.Π performs calculation on input x=x1,x2,…,xt as follows. Let the initial state be η0=1 and the k-th state be ηk∈w. Then, the state ηk is calculated recursively according to the formula given below.(3)ηk=σk,xrkηk−1.AfterL steps, the final state is ηL. If ηL=1, the output of Π is 1, otherwise it is 0.In order to handle the problem of excessive noise growth caused by homomorphic operation, we present the state in the form of bits, as described in [35]. Specifically, for η0=1, we use an w-dimensional unit vector e⟶k, e.g., e⟶0=1,0,0,…,0 instead of the state ηk∈w. The principal idea of this design is that e⟶ki=1 holds only when σk,xrkηk−1=i. If e⟶ki=1 holds, if and only if either:xrk=1 and e⟶k−1σk,1−1i=1 orxrk=0 and e⟶k−1σk,0−1i=1.Hence, fork∈L,i∈w, we have the following:(4)e⟶ki=e⟶k−1σk,1−1i⋅xrk+e⟶k−1σk,0−1i⋅1−xrk=e⟶k−1ξk,i,1⋅xrk+e⟶k−1ξk,i,0⋅1−xrk,where ξk,i,1≜σk,1−1i and ξk,i,0≜σk,0−1i are fully determined by the description of Π and can be computed easily and publicly. In order to make the homomorphic operation more concise and efficient, we give another representation of permutation branching program, such that rk,ξk,i,0,ξk,i,1k∈L,i∈w.


## 2.1. Basic Notions

### 2.1.1. Distributions

For a probability distributionD, we use x←D to denote that x is sampled according to D. For a set S, we use y←$SS to denote that y is sampled uniformly at random from S. For two distributions D1 and D2, D1≈cD2 and D1≈sD2 denote that D1 and D2 are computationally indistinguishable and statistically indistinguishable, respectively.


### 2.1.2. Entropy

The min entropy of a random variableX, denoted by H∞X, is defined as H∞X≜−logmaxxPrX=x. The average min entropy of X conditioned on Y, denoted with H˜∞X|Y, is defined as follows:(1)H˜∞X|Y≜−logEy←YmaxxPrX=x|Y=y=−logEy←Y2−H∞X|Y=y.Given the correlation valueY, the optimal probability of an infinite attacker predicting X is 2−H˜∞X|Y.


### 2.1.3.B-Bounded

A distribution ensembleχkk∈ℕ, supported over the ring R, is called B-bounded if Pra←χka∞≤B=1.Lemma 1.
(see [34]). In a ring R=≜x/xn+1, for any two polynomials a,b∈R, we have the following norm ab∞≤na∞⋅b∞.Lemma 2.
(see [34]). In a ring R=≜x/xn+1, let χ be a B-bounded distribution over R, let a1,…,am←χ. Then, the value of ∏i=1mai is nm−1Bm bounded.


## 2.1.1. Distributions

For a probability distributionD, we use x←D to denote that x is sampled according to D. For a set S, we use y←$SS to denote that y is sampled uniformly at random from S. For two distributions D1 and D2, D1≈cD2 and D1≈sD2 denote that D1 and D2 are computationally indistinguishable and statistically indistinguishable, respectively.


## 2.1.2. Entropy

The min entropy of a random variableX, denoted by H∞X, is defined as H∞X≜−logmaxxPrX=x. The average min entropy of X conditioned on Y, denoted with H˜∞X|Y, is defined as follows:(1)H˜∞X|Y≜−logEy←YmaxxPrX=x|Y=y=−logEy←Y2−H∞X|Y=y.Given the correlation valueY, the optimal probability of an infinite attacker predicting X is 2−H˜∞X|Y.


## 2.1.3.B-Bounded

A distribution ensembleχkk∈ℕ, supported over the ring R, is called B-bounded if Pra←χka∞≤B=1.Lemma 1.
(see [34]). In a ring R=≜x/xn+1, for any two polynomials a,b∈R, we have the following norm ab∞≤na∞⋅b∞.Lemma 2.
(see [34]). In a ring R=≜x/xn+1, let χ be a B-bounded distribution over R, let a1,…,am←χ. Then, the value of ∏i=1mai is nm−1Bm bounded.


## 2.2. Gaussian and Discrete Gaussian

Forr>0, the Gaussian function ρr,c⟶x⟶, supported on ℝn and centered at c⟶ with parameter r and x∈ℝn, is defined as follows: ρr,c⟶x⟶≜e−πx⟶−c⟶2/r2.


### 2.2.1. Discrete Gaussian Distribution

Forr>0, the discrete Gaussian function ρr,c⟶x⟶, supported on ℤn and centered at c⟶ with parameter r and x∈ℤn, is defined as follows: Dℤn,r,c⟶≜ρr,c⟶x⟶/ρr,c⟶ℤn. When c equals 0, it is denoted by Dℤn,r. Take note that the following Lemma illustrates that a discrete Gaussian distribution Dℤn,r outputs a rn-bounded polynomial with overwhelming probability. So, we define a rn-bounded distribution called truncated Gaussian distribution which is statistically indistinguishable from discrete Gaussian distribution.Lemma 3.
(see [34]). For n=ωlogλ and r>ωlogn, it holds that Prx←Dℤn,rx>rn≤2−n+1=neglλ.The truncated discrete Gaussian distribution centered at 0 and denoted byD¯ℤ,r is that sample polynomials from Dℤn,r, and if the polynomial is not rn-bounded, then discards it and repeats the sampling. According to Lemma 3, if n=ωlogλ and r>ωlogn, then we have D¯ℤ,r≈sDℤn,r.


## 2.2.1. Discrete Gaussian Distribution

Forr>0, the discrete Gaussian function ρr,c⟶x⟶, supported on ℤn and centered at c⟶ with parameter r and x∈ℤn, is defined as follows: Dℤn,r,c⟶≜ρr,c⟶x⟶/ρr,c⟶ℤn. When c equals 0, it is denoted by Dℤn,r. Take note that the following Lemma illustrates that a discrete Gaussian distribution Dℤn,r outputs a rn-bounded polynomial with overwhelming probability. So, we define a rn-bounded distribution called truncated Gaussian distribution which is statistically indistinguishable from discrete Gaussian distribution.Lemma 3.
(see [34]). For n=ωlogλ and r>ωlogn, it holds that Prx←Dℤn,rx>rn≤2−n+1=neglλ.The truncated discrete Gaussian distribution centered at 0 and denoted byD¯ℤ,r is that sample polynomials from Dℤn,r, and if the polynomial is not rn-bounded, then discards it and repeats the sampling. According to Lemma 3, if n=ωlogλ and r>ωlogn, then we have D¯ℤ,r≈sDℤn,r.


## 2.3. Lattices

### 2.3.1. RSIS

Choosem polynomials a⟶=a⟶1,…,a⟶m∈Rqm uniformly and independently, find x⟶∈Rqm/0 such that ∑ia⟶ix⟶i=0modq and x⟶≤β, then this problem is called RSIS q,m,β.The following theorem shows that there is a reduction from the average-case hardness of RSIS to the worst-case hardness of ideal-SVP as follows:Theorem 1.
(see [30]). For n=2k, ϕx=xn+1 and ε>0. Let m,q>0 such that q>βn⋅ωlogn and m,logq≤polyn. A polynomial-time algorithm solving RSISq,m,β with overwhelming probability can be used to solve Ideal-SVPγ in polynomial time with the approximate factor γ≥βn⋅ωlogn.


### 2.3.2. Lattice Trapdoor

In this paper, for an odd integerq and ℓ=logq, we use the “powers of two” gadget g⟶=1,2,…,2ℓ−1∈Rqℓ first introduced by Micciancio and Peikert. [18]. For a⟶∈Rqℓ, g⟶−1⋅ is the deterministic bit decomposition function, which outputs a matrix X∈R2ℓ×ℓ so as to X=g⟶−1a⟶ and g⟶⋅X=a⟶.Lemma 4.
(see [30]). There are three efficient algorithms as follows:(1)
TrapGen1n,q,σ: It runs the NTRUSign key generation algorithm same as [30] and returns h,td. Recall that h=gf−1∈Rq∗ is a signing key and td=fgFG is the corresponding trapdoor R-basis for the R module h⊥=u=u1,u2∈R1×2:h,−1u=hu1−u2=0modq.(2)
SamDom12ℓ,q: It samples u⟶=u⟶1,u⟶2∈R2×ℓ such that u⟶∞≤βsam with probability 1.(3)
SamPreh,v⟶,td: Given h∈Rq∗,v⟶∈Rqℓ and the trapdoor td, it returns u⟶=u⟶1,u⟶2∈R2×ℓ such that h,−1u⟶=hu⟶1−u⟶2=v⟶modq and u⟶∞≤βsam with probability 1.(4)
We have the statistical indistinguishability:(2)h≈sh′andh,td,u⟶,v⟶≈sh,td,u⟶′,v⟶′,where h,td←TrapGen1n,q,σ,h′←$Rq∗, and u⟶←SamDom12ℓ,q,v⟶=h,−1u⟶modq,v⟶′←$Rqℓ,u⟶′←SamPreh,v⟶′,td.


## 2.3.1. RSIS

Choosem polynomials a⟶=a⟶1,…,a⟶m∈Rqm uniformly and independently, find x⟶∈Rqm/0 such that ∑ia⟶ix⟶i=0modq and x⟶≤β, then this problem is called RSIS q,m,β.The following theorem shows that there is a reduction from the average-case hardness of RSIS to the worst-case hardness of ideal-SVP as follows:Theorem 1.
(see [30]). For n=2k, ϕx=xn+1 and ε>0. Let m,q>0 such that q>βn⋅ωlogn and m,logq≤polyn. A polynomial-time algorithm solving RSISq,m,β with overwhelming probability can be used to solve Ideal-SVPγ in polynomial time with the approximate factor γ≥βn⋅ωlogn.


## 2.3.2. Lattice Trapdoor

In this paper, for an odd integerq and ℓ=logq, we use the “powers of two” gadget g⟶=1,2,…,2ℓ−1∈Rqℓ first introduced by Micciancio and Peikert. [18]. For a⟶∈Rqℓ, g⟶−1⋅ is the deterministic bit decomposition function, which outputs a matrix X∈R2ℓ×ℓ so as to X=g⟶−1a⟶ and g⟶⋅X=a⟶.Lemma 4.
(see [30]). There are three efficient algorithms as follows:(1)
TrapGen1n,q,σ: It runs the NTRUSign key generation algorithm same as [30] and returns h,td. Recall that h=gf−1∈Rq∗ is a signing key and td=fgFG is the corresponding trapdoor R-basis for the R module h⊥=u=u1,u2∈R1×2:h,−1u=hu1−u2=0modq.(2)
SamDom12ℓ,q: It samples u⟶=u⟶1,u⟶2∈R2×ℓ such that u⟶∞≤βsam with probability 1.(3)
SamPreh,v⟶,td: Given h∈Rq∗,v⟶∈Rqℓ and the trapdoor td, it returns u⟶=u⟶1,u⟶2∈R2×ℓ such that h,−1u⟶=hu⟶1−u⟶2=v⟶modq and u⟶∞≤βsam with probability 1.(4)
We have the statistical indistinguishability:(2)h≈sh′andh,td,u⟶,v⟶≈sh,td,u⟶′,v⟶′,where h,td←TrapGen1n,q,σ,h′←$Rq∗, and u⟶←SamDom12ℓ,q,v⟶=h,−1u⟶modq,v⟶′←$Rqℓ,u⟶′←SamPreh,v⟶′,td.


## 2.4. Permutation Branching Program

Then, a permutation branching programΠ is defined as follows [35]. Π with input space of 0,1t, length L, and width w is a sequence of L tuples of the form rk,σk,0,σk,1 where.r:L⟶t is a function associates the k-th tuple with an input bit xrk.σk,0,σk,1 are permutations over w=1,2,…,w.Π performs calculation on input x=x1,x2,…,xt as follows. Let the initial state be η0=1 and the k-th state be ηk∈w. Then, the state ηk is calculated recursively according to the formula given below.(3)ηk=σk,xrkηk−1.AfterL steps, the final state is ηL. If ηL=1, the output of Π is 1, otherwise it is 0.In order to handle the problem of excessive noise growth caused by homomorphic operation, we present the state in the form of bits, as described in [35]. Specifically, for η0=1, we use an w-dimensional unit vector e⟶k, e.g., e⟶0=1,0,0,…,0 instead of the state ηk∈w. The principal idea of this design is that e⟶ki=1 holds only when σk,xrkηk−1=i. If e⟶ki=1 holds, if and only if either:xrk=1 and e⟶k−1σk,1−1i=1 orxrk=0 and e⟶k−1σk,0−1i=1.Hence, fork∈L,i∈w, we have the following:(4)e⟶ki=e⟶k−1σk,1−1i⋅xrk+e⟶k−1σk,0−1i⋅1−xrk=e⟶k−1ξk,i,1⋅xrk+e⟶k−1ξk,i,0⋅1−xrk,where ξk,i,1≜σk,1−1i and ξk,i,0≜σk,0−1i are fully determined by the description of Π and can be computed easily and publicly. In order to make the homomorphic operation more concise and efficient, we give another representation of permutation branching program, such that rk,ξk,i,0,ξk,i,1k∈L,i∈w.


## 3. HTDF Functions

A homomorphic trapdoor function (HTDF) allows anyone to calculate a homomorphic inputug and an output vg. The input depends only on g,x1,u1,v1,…,xt,ut,vt and the output depends on g,v1,…,vt. That is, fpk,gx1,…,xtug=vg holds, where g is an admissible function (or called circuit) defined very soon.


### 3.1. Definition

A HTDF consists of five polytime algorithmsHTDF.KeyGen, f,Inv,HTDF.Evalin,HTDF.Evalout with syntax as follows:pk,sk←HTDF.KeyGen1λ: A key generation procedure. The security parameter λ defines the input space U, the index space X, and the output space V and some efficiently sampleable input-distribution DU over U. We require that elements in U,V, and X can be efficiently tested and that elements in V can efficiently be sampled uniformly at random.fpk,x:U⟶V: A deterministic function indexed by pk and x∈X.Invertsk,x:V⟶U: A probabilistic inverter indexed by sk and x∈X.ug=HTDF.Evaling,x1,u1,v1,…,xt,ut,vt: A deterministic input homomorphic evaluation algorithm. It takes some function g:Xt⟶X as input and values xi∈X,ui∈U,vi∈Vi∈t and outputs ug∈U.vg=HTDF.Evaloutg,v1,…,vt: A deterministic  output  homomorphic evaluation algorithm. It takes some function g:Xt⟶X as input and values vi∈Vi∈t and outputs vg∈V.


#### 3.1.1. Correctness of Homomorphic Computation

Letpk,sk←HTDF.KeyGen1λ and g:Xt⟶X be a function on x1,…,xt∈X, and set y=gx1,…,xt. Let u1,…,ut∈U and set vi=fpk,xiui for i∈t. Set vg=HTDF.Evaloutg,v1,…,vt, ug=HTDF.Evaling,x1,u1,v1,…,xt,ut,vt. The correctness requirement is established for ug∈U and fpk,yug=vg.


#### 3.1.2. Relaxed Correctness of Leveled HTDFs

In a leveled fully homomorphic scheme, the size of noise carried by each inputui∈U is βi∈ℤ. The initial samples selected from the input-distribution DU carries a small noise of β0 and the noise size βg of the evaluated input ug depends on the noise size βi of ui, the indices xi, and the function g. In fact, if the noise size βg>βmax, where βmax is an extreme value of noise size, the correctness of the scheme cannot be guaranteed. Thus, we ought to pay attention to limiting the types of functions that can be calculated homomorphically. A function g is admissible on indices x1,…,xt if, βg≤βmax whenever ui carries noise with size βi≤β0.


#### 3.1.3. Distributional Equivalence of Inversion

In order to illustrate the security of our main construction FHS, we demand the following statistical indistinguishability:(5)pk,sk,x,u,v≈spk,sk,x,u′,v′,where pk,sk←HTDF.KeyGen1λ, x∈X, u←DU,v=fpk,xu,v′←$V,u′←Invsk,xv′.


#### 3.1.4. HTDF Security

Gorbunov et al. [2] constructed an existential unforgeability FHS based on the security of claw-freeness HTDF. Here, we want to construct a FHS scheme that is strongly unforgeable like Wang et al. [26] did, so the security of HTDF is required to meet the two characteristics of claw-freeness and collision-resistance. In particular, it should be hard to find u≠u′∈U and x,x′∈X such that fpk,xu=fpk,x′u′. Notice that if x=x′ holds, then u,u′ is a collision, otherwise a claw. Formally, for any PPT attacker A, the following holds:(6)Prfpk,xu=fpk,x′u′u≠u′∈U,x,x′∈Xpk,sk←HTDF.KeyGenu,u′,x,x′←A1λ,pk≤neglλ.


### 3.2. Construction: Basic Algorithms and Security

It is to be remembered thatλ is the security parameter. In order to illustrate the HTDF function concisely, we need to introduce some asymptotic public parameters, as shown below.


#### 3.2.1. Parameters

We define flexibled≤polyλ as the maximum depth of the circuit that supported by homomorphic trapdoor function. Choose an integer n=polyλ and a sufficiently large prime q=qn, and set ℓ=logq. Set β0=Oq1/2⋅polyn=Oq1/2⋅polyλ,βmax=O4dnℓβ0,βRSIS=Onℓβmax<q.


#### 3.2.2. Construction of HTDF

Below, we give the basic algorithm of the HTDF functionℱ.SetX=ℤ2,V=Rqℓ and U=u⟶=u⟶1,u⟶2∈Rq2×ℓ:u⟶∞≤βmax. Define the distribution DU and sample u⟶←SamDom12ℓ,q as in Lemma 4 so that u⟶∞≤β0.pk,sk←HTDF.KeyGen1λ: Run h,td←TrapGen1n,1ℓ,q and set pk=h∈Rq and sk=td.Definefpk,xu⟶≜h,−1u⟶+xg⟶=hu⟶1−u⟶2+xg⟶.Defineu⟶←Invsk,xv⟶ to output u⟶←SamePreh,v⟶−xg⟶,td.


#### 3.2.3. Distributional Equivalence of Inversion

Letx∈X and pk=h,sk=td←HTDF.KeyGen1λ. Let u⟶←DU, v⟶=fpk,xu⟶=h,−1u⟶+xg⟶=hu⟶1−u⟶2+xg⟶, v⟶′←$V,u⟶′←SamPreh,v⟶′−xg⟶,td. Obviously v⟶′−xg⟶ is uniformly random, then by Lemma 4 and a simple hybrid argument, we can obtain as follows:(7)h,td,u⟶,hu⟶1−u⟶2≈sh,td,u⟶′,v⟶′−xg⟶We perform the following operations on both sides of the equation: put in anx∈X and then add xg⟶ to the last entry to both sides, we can obtain as follows:(8)h,td,x,u⟶,v⟶=hu⟶1−u⟶2+xg⟶≈sh,td,x,u⟶′,v⟶′


#### 3.2.4. HTDF Security

Next, it is proved that if the RSIS assumption holds, the HTDF functionℱ constructed above is safe. Recall that in the original HTDF security experiment, we generate the public key h along with the secret key td for h←$Rq∗.Theorem 2.
Suppose that theRSISq,2,βRSIS-assumption holds for the described parameters, then the HTDF function ℱ satisfies the HTDF security.Proof. Assume that there exists a PPT adversary A, which can have a nonnegligible probability δ win the HTDF security experiment. Then, we establish a probability polynomial time simulator S that breaks the RSIS q,2,βRSIS assumption with nonnegligible probability.Next, we revise the HTDF security experiment, we sampleh←$Rq∗, instead of sampling h,td←TrapGen1n,1ℓ,q and setting pk=h and sk=td. Please note that sk=td has never been used anywhere in the primeval HTDF security experiment. Hence, adversary A′s point of view among the original HTDF security experiment and the simulated HTDF security experiment are indistinguishable by Lemma 4. Specifically, adversary A attacks the security experiment of simulated HTDF and gains the security experiment with a probability of at least δ−neglλ.At present, we have proved that the PPT adversaryA, who won in the simulated HTDF security experiment, can be used to settle the RSIS problem. Suppose that the successful adversary A outputs values u⟶≠u⟶′∈U,x,x′∈X such that fpk,xu⟶=fpk,x′u⟶′. Let u⟶∗=u⟶−u⟶′ and x∗=x′−x. Then, we obtain as follows:(9)fpk,xu⟶=h,−1u⟶+xg⟶=h,−1u⟶′+x′g⟶=fpk,x′u⟶′⇒h,−1u⟶∗=x∗g⟶.Additionally, becauseu⟶,u⟶′∈U, it holds that u⟶∞,u⟶′∞≤βmax and thus u⟶∗∞≤2βmax. Moreover, since u⟶≠u⟶′, it holds that u⟶∗≠0⟶.To solve the RSIS problem defined byh,−1, where h∈Rq∗, then we talk over the two situations given below:x=x′: In this situation, the small u⟶∗=u⟶−u⟶′≠0⟶ is a nonzero solution of the RSIS problem, as h,−1u⟶−u⟶′=h,−1u⟶∗=x∗g⟶=x−x′g⟶=0, .x≠x′: On this event, we prove that the simulator S pretty good at using the knowledge of a small u⟶∗≠0⟶ and some x∗≠0 satisfying the right side of the (9) to find a nonzero solution of the RSIS problem (similarly as [2]).Samplet⟶←$R22 and let r⟶≜h,−1t⟶∈Rq. Calculate t⟶′=g⟶−1r⟶/x∗∈R2ℓ such that x∗g⟶t⟶′=r⟶. Therefore,(10)h,−1u⟶∗t⟶′−t⟶=h,−1u⟶∗t⟶′−h,−1t⟶=x∗g⟶t⟶′−r⟶=r⟶−r⟶=0⟶.Settingu⟶⋄≜u⟶∗t⟶′−t⟶, we then have h,−1u⟶⋄=0⟶ and u⋄∞≤2nℓβmax+1≤βSIS. Below the u⟶⋄≠0⟶, i.e., t⟶≠u⟶∗t⟶′ have to be proved. Here we show that, even given h,u⟶∗,x∗, the following inequality holds with overwhelming probability for uniformly random t⟶ Actually, we have(11)H˜∞t⟶|t⟶′≥H˜∞t⟶|h,−1t⟶≥ωn,The reason for the first inequality is thatt⟶′ is completely determined by r⟶=h,−1t⟶ as g⟶−1⋅ is deterministic, and the reason for the second inequality comes from Lemma 4. Therefore, Prt⟶=u⟶∗t⟶′≤2−ωn=neglλ.So, if the adversaryA wins any situation in the abovementioned simulated HTDF security game with a nonnegligible probability δ/2−neglλ, the simulator S will generate an effective and small enough solution to solve the RSIS problem with a probability of δ/2−neglλ. The process of the proof ends. □


### 3.3. Basic Homomorphic Evaluation

In an HTDF scheme, in order to verify an evaluated function value, we demand to design two corresponding algorithms: one is the input algorithm, another kind is the output algorithm, and both algorithms are deterministic. This is different from a homomorphic encryption system; in a homomorphic encryption system, only one (random or deterministic) homomorphic algorithm that acts on the ciphertext needs to be designed.The two basic homomorphic algorithms addition and multiplication are described as follows. Here, we will simplify some notations (e.g.,Evalin instead of HTDF.Evalin). Recall that for i=1,2, v⟶i=h,−1u⟶i+xig⟶. Let u⟶i∞≤βi and xi∈0,1.


#### 3.3.1. Homomorphic Addition Algorithms

They calculate the sum of the corresponding input and output vectors, respectively.EvalinAdd,x1,u⟶1,v⟶1,x2,u⟶2,v⟶2≜u⟶1+u⟶2modqEvaloutAdd,v⟶1,v⟶2≜v⟶1+v⟶2modqThe noise of the addition is bounded byβ1+β2. The correctness comes from v⟶1+v⟶2=h,−1u⟶1+u⟶2+x1+x2g⟶.


#### 3.3.2. Homomorphic Multiplication Algorithms

The homomorphic output multiplication algorithm is a multiplication of the output vectors which is performed the multiplication defined in Section3.1. The homomorphic input multiplication algorithm is asymmetric and it needs partial output, index, and the whole input to compute.EvalinMult,x1,u⟶1,v⟶1,x2,u⟶2,v⟶2≜u⟶1⋅g⟶−1v⟶2+x1u⟶2modqEvaloutMult,v⟶1,v⟶2≜v1⟶⋅g⟶−1v2⟶modqThe noise of multiplication is bounded bynℓβ1+x1β2=nℓβ1+β2. Assuming v⟶i=h,−1u⟶i+xig⟶, the correctness follows by the computation:(12)v⟶1⋅g⟶−1v2⟶=h,−1u⟶1+x1g⟶⋅g⟶−1v⟶2=h,−1u⟶1⋅g⟶−1v⟶2+x1h,−1u⟶2+x2g⟶=h,−1u⟶1⋅g⟶−1v⟶2+x1u⟶2+x1x2g⟶.


### 3.4. Homomorphic Output and Input Evaluation

According to the abovementioned discussion, it is very easy to homomorphically calculate an arithmetic circuit or Boolean circuit similar as [2], we are not satisfied. We want to show how to design the scheme as well as [26] based on the fact that the noise growth is asymmetric.


#### 3.4.1. Homomorphic Output Evaluation

Below we describe the definition of the homomorphic output evaluation algorithm(13)EvaloutΠ,v⟶0,v⟶0,ii∈w,v⟶jj∈t⟶v⟶Π,for a length is L and a width is w permutation branching program Π. In the initialization stage, we will assign v⟶0,v⟶0,ii∈w below and v⟶j is the vector such that v⟶j=h,−1u⟶j+xjg⟶, where u⟶j=u⟶j,1,u⟶j,2. Recall that rk,ξk,i,0,ξk,i,1k∈L,i∈w is a description of the permutation branching program Π, and the initial state vector is defined as the first w-dimensional unit vector e⟶0=1,0,0,…,0. For k∈L and i∈w, it holds that:(14)e⟶ki=e⟶k−1ξk,i,1⋅xrk+e⟶k−1ξk,i,0⋅1−xrk.Here, we give the full description of the process of the homomorphic output evaluation algorithmEvalout of the permutation branching program Π.Initialization: Letv⟶k,i be an output relevant to the state e⟶ki, where k∈L,i∈w,(1)
Choosev⟶0←$Rqℓ and set it to be a corresponding output of the state 1.(2)
Choosev⟶0,i←$Rqℓ and set it to be a corresponding initial output of the initial state e⟶0i.(3)
Setv⟶¯j≜v⟶0−v⟶j, where v⟶j (such that v⟶j=h,−1u⟶j+xjg⟶) is an output corresponding to xj, and set it to be a corresponding output of 1−xj.Calculation: Fork=1,2,…,L, suppose that at step k−1, we have v⟶k−1,ii∈w. Then, we can calculate inductively as follows:(15)v⟶k,i=v⟶rk⋅g⟶−1v⟶k−1,ξk,i,1+v⟶¯rk⋅g⟶−1v⟶k−1,ξk,i,0.Final output: After finishing the computation, we have the value ofv⟶L,ii∈w. Finally, output the final output v⟶L,1 corresponding to the state e⟶L1, i.e., v⟶Π=v⟶L,1.


#### 3.4.2. Homomorphic Input Evaluation

Here, we give the full description of the process of the homomorphic input evaluation algorithmEvalinΠ,1,u⟶0,v⟶0, e⟶0i,u⟶0,i,v⟶0,ii∈w, xj,u⟶j,v⟶jj∈t⟶u⟶Π of the permutation branching program Π.Initialization: Letu⟶k,i be an input relevant to the state e⟶ki, where k∈L,i∈w.(1)
Sampleu⟶0=u⟶0,1,u⟶0,2←DU (such that v⟶0=h,−1u⟶0+1⋅g⟶) and set it as input relevant to the state 1.(2)
Sampleu⟶0,i=u⟶0,i,1,u⟶0,i,2←DU (such that v⟶0,i=h,−1u⟶0,i+e⟶0ig⟶) and set it as the initial input relevant to the initial state e⟶0i.(3)
Setu⟶¯j≜u⟶0−u⟶j, where u⟶j=u⟶j,1,u⟶j,2 (such that v⟶j=h,−1u⟶j+xjg⟶) is an input corresponding to xj, and set it to the input relevant to 1−xj.Calculation: Fork=1,2,…,L, suppose that at step k−1, we have u⟶k−1,ii∈w. Then, we can calculate inductively as follows.(16)u⟶k,i=u⟶rk⋅g⟶−1v⟶k−1,ξk,i,1+xrk⋅u⟶k−1,ξk,i,1+u⟶¯rk⋅g⟶−1v⟶k−1,ξk,i,0+1−xrk⋅u⟶k−1,ξk,i,0.Final input: After finishing the computation process, we have the value ofu⟶L,ii∈w. Finally, output the final input u⟶L,1 corresponding to e⟶L1, i.e., u⟶Π=u⟶L,1.


### 3.5. Correctness of Homomorphic Evaluation and Noise Analysis

In the following lemmas, we testify the validity of homomorphic input and homomorphic output algorithms and explain in detail the noise growth in the above homomorphic evaluation.Lemma 5.
Suppose thatEvaloutΠ,v⟶0,v⟶0,ii∈w, v⟶jj∈t⟶v⟶Π and EvalinΠ,1,u⟶0,v⟶0, e⟶0i,u⟶0,i,v⟶0,ii∈w, xj,u⟶j,v⟶jj∈t⟶u⟶Π, where v⟶0=h,−1u⟶0+1⋅g⟶, v⟶0,i=h,−1u⟶0,i+e⟶0ig⟶ and v⟶j=h,−1u⟶j+xjg⟶ for i∈w,j∈t. Then for all k∈L,i∈w, we have v⟶k,i=h,−1u⟶k,i+e⟶kig⟶. For k=L, we have v⟶L,1=h,−1u⟶L,1+e⟶L1g⟶.Proof. Using formulas (1), (4), and (5) and the above conditions, for all k∈L,i∈w, it holds as follows:(17)v⟶k,i=v⟶rk⋅g⟶−1v⟶k−1,ξk,i,1+v⟶¯rk⋅g⟶−1v⟶k−1,ξk,i,0=h,−1u⟶rk+xrkg⟶⋅g⟶−1v⟶k−1,ξk,i,1+h,−1u⟶¯rk+1−xrkg⟶⋅g⟶−1v⟶k−1,ξk,i,0=h,−1u⟶rk⋅g⟶−1v⟶k−1,ξk,i,1+xrkh,−1u⟶k−1,ξk,i,1+xrk⋅e⟶k−1ξk,i,1g⟶+h,−1u⟶¯rk⋅g⟶−1v⟶k−1,ξk,i,0+1−xrkh,−1u⟶k−1,ξk,i,0+1−xrk⋅e⟶k−1ξk,i,0g⟶=h,−1u⟶rk⋅g⟶−1v⟶k−1,ξk,i,1+xrk⋅u⟶k−1,ξk,i,1+u⟶¯rk⋅g⟶−1v⟶k−1,ξk,i,0+1−xrk⋅u⟶k−1,ξk,i,0+xrk⋅e⟶k−1ξk,i,1+1−xrk⋅e⟶k−1ξk,i,0⋅g⟶=h,−1u⟶k,i+e⟶kig⟶.The process of proof ends. □Lemma 6.
Assuming  thatEvalinΠ,1,u⟶0,v⟶0, e⟶0i,u⟶0,i,v⟶0,ii∈w, xj,u⟶j,v⟶jj∈t⟶u⟶Π and all the noises of the inputs are bounded by β, i.e., u⟶0∞,u⟶0,i∞, u⟶j∞≤β, then we have ‖u⟶Π‖∞≤3nℓLβ+β.Proof. We use the inductive method to prove the lemma. That is, for any stepk=0,1,2,…,L and i∈w, we will show that ‖u⟶k,i‖∞≤3nℓkβ+β.Ifk=0, it is not difficult to find that all the initial noises are such that u⟶0,i∞≤β,i∈w.Suppose that at stepk−1, we have u⟶k−1,i∞≤3nℓk−1β+β. Then, according to formula (16), we have as follows:(18)u⟶k,i∞=u⟶rk⋅g⟶−1v⟶k−1,ξk,i,1+xrk⋅u⟶k−1,ξk,i,1+u⟶¯rk⋅g⟶−1v⟶k−1,ξk,i,0+1−xrk⋅u⟶k−1,ξk,i,0∞≤u⟶rk⋅g⟶−1v⟶k−1,ξk,i,1∞+xrk⋅u⟶k−1,ξk,i,1∞+u⟶¯rk⋅g⟶−1v⟶k−1,ξk,i,0∞+1−xrk⋅u⟶k−1,ξk,i,0∞≤nℓβ+xrk⋅3nℓk−1β+β+2nℓβ+1−xrk⋅3nℓk−1β+β=3nℓkβ+β,where u⟶¯rk∞=u⟶0−u⟶rk∞≤u⟶0∞+u⟶rk∞≤β+β=2β.Through induction, we obtainu⟶Π∞=u⟶L,1∞≤3nℓLβ+β. The process of proof ends. □Remark 1.
Barrington’s theorem [32] states that a circuit with a depth of d can be transformed into a permutation branching program with a length of 4d. Thus, simply by setting d≤polyλ, the resulting maximum noise level is less than O4dnℓβ. In particular, in the setting where it only requires d=Ologλ, we obtain the modulus q=polyλ>O4dnℓβ to be a middle large polynomial, which can supply a better security for the scheme. In other words, it is based on Ideal-SVP assumption with polynomial approximation factors.


## 3.1. Definition

A HTDF consists of five polytime algorithmsHTDF.KeyGen, f,Inv,HTDF.Evalin,HTDF.Evalout with syntax as follows:pk,sk←HTDF.KeyGen1λ: A key generation procedure. The security parameter λ defines the input space U, the index space X, and the output space V and some efficiently sampleable input-distribution DU over U. We require that elements in U,V, and X can be efficiently tested and that elements in V can efficiently be sampled uniformly at random.fpk,x:U⟶V: A deterministic function indexed by pk and x∈X.Invertsk,x:V⟶U: A probabilistic inverter indexed by sk and x∈X.ug=HTDF.Evaling,x1,u1,v1,…,xt,ut,vt: A deterministic input homomorphic evaluation algorithm. It takes some function g:Xt⟶X as input and values xi∈X,ui∈U,vi∈Vi∈t and outputs ug∈U.vg=HTDF.Evaloutg,v1,…,vt: A deterministic  output  homomorphic evaluation algorithm. It takes some function g:Xt⟶X as input and values vi∈Vi∈t and outputs vg∈V.


### 3.1.1. Correctness of Homomorphic Computation

Letpk,sk←HTDF.KeyGen1λ and g:Xt⟶X be a function on x1,…,xt∈X, and set y=gx1,…,xt. Let u1,…,ut∈U and set vi=fpk,xiui for i∈t. Set vg=HTDF.Evaloutg,v1,…,vt, ug=HTDF.Evaling,x1,u1,v1,…,xt,ut,vt. The correctness requirement is established for ug∈U and fpk,yug=vg.


### 3.1.2. Relaxed Correctness of Leveled HTDFs

In a leveled fully homomorphic scheme, the size of noise carried by each inputui∈U is βi∈ℤ. The initial samples selected from the input-distribution DU carries a small noise of β0 and the noise size βg of the evaluated input ug depends on the noise size βi of ui, the indices xi, and the function g. In fact, if the noise size βg>βmax, where βmax is an extreme value of noise size, the correctness of the scheme cannot be guaranteed. Thus, we ought to pay attention to limiting the types of functions that can be calculated homomorphically. A function g is admissible on indices x1,…,xt if, βg≤βmax whenever ui carries noise with size βi≤β0.


### 3.1.3. Distributional Equivalence of Inversion

In order to illustrate the security of our main construction FHS, we demand the following statistical indistinguishability:(5)pk,sk,x,u,v≈spk,sk,x,u′,v′,where pk,sk←HTDF.KeyGen1λ, x∈X, u←DU,v=fpk,xu,v′←$V,u′←Invsk,xv′.


### 3.1.4. HTDF Security

Gorbunov et al. [2] constructed an existential unforgeability FHS based on the security of claw-freeness HTDF. Here, we want to construct a FHS scheme that is strongly unforgeable like Wang et al. [26] did, so the security of HTDF is required to meet the two characteristics of claw-freeness and collision-resistance. In particular, it should be hard to find u≠u′∈U and x,x′∈X such that fpk,xu=fpk,x′u′. Notice that if x=x′ holds, then u,u′ is a collision, otherwise a claw. Formally, for any PPT attacker A, the following holds:(6)Prfpk,xu=fpk,x′u′u≠u′∈U,x,x′∈Xpk,sk←HTDF.KeyGenu,u′,x,x′←A1λ,pk≤neglλ.


## 3.1.1. Correctness of Homomorphic Computation

Letpk,sk←HTDF.KeyGen1λ and g:Xt⟶X be a function on x1,…,xt∈X, and set y=gx1,…,xt. Let u1,…,ut∈U and set vi=fpk,xiui for i∈t. Set vg=HTDF.Evaloutg,v1,…,vt, ug=HTDF.Evaling,x1,u1,v1,…,xt,ut,vt. The correctness requirement is established for ug∈U and fpk,yug=vg.


## 3.1.2. Relaxed Correctness of Leveled HTDFs

In a leveled fully homomorphic scheme, the size of noise carried by each inputui∈U is βi∈ℤ. The initial samples selected from the input-distribution DU carries a small noise of β0 and the noise size βg of the evaluated input ug depends on the noise size βi of ui, the indices xi, and the function g. In fact, if the noise size βg>βmax, where βmax is an extreme value of noise size, the correctness of the scheme cannot be guaranteed. Thus, we ought to pay attention to limiting the types of functions that can be calculated homomorphically. A function g is admissible on indices x1,…,xt if, βg≤βmax whenever ui carries noise with size βi≤β0.


## 3.1.3. Distributional Equivalence of Inversion

In order to illustrate the security of our main construction FHS, we demand the following statistical indistinguishability:(5)pk,sk,x,u,v≈spk,sk,x,u′,v′,where pk,sk←HTDF.KeyGen1λ, x∈X, u←DU,v=fpk,xu,v′←$V,u′←Invsk,xv′.


## 3.1.4. HTDF Security

Gorbunov et al. [2] constructed an existential unforgeability FHS based on the security of claw-freeness HTDF. Here, we want to construct a FHS scheme that is strongly unforgeable like Wang et al. [26] did, so the security of HTDF is required to meet the two characteristics of claw-freeness and collision-resistance. In particular, it should be hard to find u≠u′∈U and x,x′∈X such that fpk,xu=fpk,x′u′. Notice that if x=x′ holds, then u,u′ is a collision, otherwise a claw. Formally, for any PPT attacker A, the following holds:(6)Prfpk,xu=fpk,x′u′u≠u′∈U,x,x′∈Xpk,sk←HTDF.KeyGenu,u′,x,x′←A1λ,pk≤neglλ.


## 3.2. Construction: Basic Algorithms and Security

It is to be remembered thatλ is the security parameter. In order to illustrate the HTDF function concisely, we need to introduce some asymptotic public parameters, as shown below.


### 3.2.1. Parameters

We define flexibled≤polyλ as the maximum depth of the circuit that supported by homomorphic trapdoor function. Choose an integer n=polyλ and a sufficiently large prime q=qn, and set ℓ=logq. Set β0=Oq1/2⋅polyn=Oq1/2⋅polyλ,βmax=O4dnℓβ0,βRSIS=Onℓβmax<q.


### 3.2.2. Construction of HTDF

Below, we give the basic algorithm of the HTDF functionℱ.SetX=ℤ2,V=Rqℓ and U=u⟶=u⟶1,u⟶2∈Rq2×ℓ:u⟶∞≤βmax. Define the distribution DU and sample u⟶←SamDom12ℓ,q as in Lemma 4 so that u⟶∞≤β0.pk,sk←HTDF.KeyGen1λ: Run h,td←TrapGen1n,1ℓ,q and set pk=h∈Rq and sk=td.Definefpk,xu⟶≜h,−1u⟶+xg⟶=hu⟶1−u⟶2+xg⟶.Defineu⟶←Invsk,xv⟶ to output u⟶←SamePreh,v⟶−xg⟶,td.


### 3.2.3. Distributional Equivalence of Inversion

Letx∈X and pk=h,sk=td←HTDF.KeyGen1λ. Let u⟶←DU, v⟶=fpk,xu⟶=h,−1u⟶+xg⟶=hu⟶1−u⟶2+xg⟶, v⟶′←$V,u⟶′←SamPreh,v⟶′−xg⟶,td. Obviously v⟶′−xg⟶ is uniformly random, then by Lemma 4 and a simple hybrid argument, we can obtain as follows:(7)h,td,u⟶,hu⟶1−u⟶2≈sh,td,u⟶′,v⟶′−xg⟶We perform the following operations on both sides of the equation: put in anx∈X and then add xg⟶ to the last entry to both sides, we can obtain as follows:(8)h,td,x,u⟶,v⟶=hu⟶1−u⟶2+xg⟶≈sh,td,x,u⟶′,v⟶′


### 3.2.4. HTDF Security

Next, it is proved that if the RSIS assumption holds, the HTDF functionℱ constructed above is safe. Recall that in the original HTDF security experiment, we generate the public key h along with the secret key td for h←$Rq∗.Theorem 2.
Suppose that theRSISq,2,βRSIS-assumption holds for the described parameters, then the HTDF function ℱ satisfies the HTDF security.Proof. Assume that there exists a PPT adversary A, which can have a nonnegligible probability δ win the HTDF security experiment. Then, we establish a probability polynomial time simulator S that breaks the RSIS q,2,βRSIS assumption with nonnegligible probability.Next, we revise the HTDF security experiment, we sampleh←$Rq∗, instead of sampling h,td←TrapGen1n,1ℓ,q and setting pk=h and sk=td. Please note that sk=td has never been used anywhere in the primeval HTDF security experiment. Hence, adversary A′s point of view among the original HTDF security experiment and the simulated HTDF security experiment are indistinguishable by Lemma 4. Specifically, adversary A attacks the security experiment of simulated HTDF and gains the security experiment with a probability of at least δ−neglλ.At present, we have proved that the PPT adversaryA, who won in the simulated HTDF security experiment, can be used to settle the RSIS problem. Suppose that the successful adversary A outputs values u⟶≠u⟶′∈U,x,x′∈X such that fpk,xu⟶=fpk,x′u⟶′. Let u⟶∗=u⟶−u⟶′ and x∗=x′−x. Then, we obtain as follows:(9)fpk,xu⟶=h,−1u⟶+xg⟶=h,−1u⟶′+x′g⟶=fpk,x′u⟶′⇒h,−1u⟶∗=x∗g⟶.Additionally, becauseu⟶,u⟶′∈U, it holds that u⟶∞,u⟶′∞≤βmax and thus u⟶∗∞≤2βmax. Moreover, since u⟶≠u⟶′, it holds that u⟶∗≠0⟶.To solve the RSIS problem defined byh,−1, where h∈Rq∗, then we talk over the two situations given below:x=x′: In this situation, the small u⟶∗=u⟶−u⟶′≠0⟶ is a nonzero solution of the RSIS problem, as h,−1u⟶−u⟶′=h,−1u⟶∗=x∗g⟶=x−x′g⟶=0, .x≠x′: On this event, we prove that the simulator S pretty good at using the knowledge of a small u⟶∗≠0⟶ and some x∗≠0 satisfying the right side of the (9) to find a nonzero solution of the RSIS problem (similarly as [2]).Samplet⟶←$R22 and let r⟶≜h,−1t⟶∈Rq. Calculate t⟶′=g⟶−1r⟶/x∗∈R2ℓ such that x∗g⟶t⟶′=r⟶. Therefore,(10)h,−1u⟶∗t⟶′−t⟶=h,−1u⟶∗t⟶′−h,−1t⟶=x∗g⟶t⟶′−r⟶=r⟶−r⟶=0⟶.Settingu⟶⋄≜u⟶∗t⟶′−t⟶, we then have h,−1u⟶⋄=0⟶ and u⋄∞≤2nℓβmax+1≤βSIS. Below the u⟶⋄≠0⟶, i.e., t⟶≠u⟶∗t⟶′ have to be proved. Here we show that, even given h,u⟶∗,x∗, the following inequality holds with overwhelming probability for uniformly random t⟶ Actually, we have(11)H˜∞t⟶|t⟶′≥H˜∞t⟶|h,−1t⟶≥ωn,The reason for the first inequality is thatt⟶′ is completely determined by r⟶=h,−1t⟶ as g⟶−1⋅ is deterministic, and the reason for the second inequality comes from Lemma 4. Therefore, Prt⟶=u⟶∗t⟶′≤2−ωn=neglλ.So, if the adversaryA wins any situation in the abovementioned simulated HTDF security game with a nonnegligible probability δ/2−neglλ, the simulator S will generate an effective and small enough solution to solve the RSIS problem with a probability of δ/2−neglλ. The process of the proof ends. □


## 3.2.1. Parameters

We define flexibled≤polyλ as the maximum depth of the circuit that supported by homomorphic trapdoor function. Choose an integer n=polyλ and a sufficiently large prime q=qn, and set ℓ=logq. Set β0=Oq1/2⋅polyn=Oq1/2⋅polyλ,βmax=O4dnℓβ0,βRSIS=Onℓβmax<q.


## 3.2.2. Construction of HTDF

Below, we give the basic algorithm of the HTDF functionℱ.SetX=ℤ2,V=Rqℓ and U=u⟶=u⟶1,u⟶2∈Rq2×ℓ:u⟶∞≤βmax. Define the distribution DU and sample u⟶←SamDom12ℓ,q as in Lemma 4 so that u⟶∞≤β0.pk,sk←HTDF.KeyGen1λ: Run h,td←TrapGen1n,1ℓ,q and set pk=h∈Rq and sk=td.Definefpk,xu⟶≜h,−1u⟶+xg⟶=hu⟶1−u⟶2+xg⟶.Defineu⟶←Invsk,xv⟶ to output u⟶←SamePreh,v⟶−xg⟶,td.


## 3.2.3. Distributional Equivalence of Inversion

Letx∈X and pk=h,sk=td←HTDF.KeyGen1λ. Let u⟶←DU, v⟶=fpk,xu⟶=h,−1u⟶+xg⟶=hu⟶1−u⟶2+xg⟶, v⟶′←$V,u⟶′←SamPreh,v⟶′−xg⟶,td. Obviously v⟶′−xg⟶ is uniformly random, then by Lemma 4 and a simple hybrid argument, we can obtain as follows:(7)h,td,u⟶,hu⟶1−u⟶2≈sh,td,u⟶′,v⟶′−xg⟶We perform the following operations on both sides of the equation: put in anx∈X and then add xg⟶ to the last entry to both sides, we can obtain as follows:(8)h,td,x,u⟶,v⟶=hu⟶1−u⟶2+xg⟶≈sh,td,x,u⟶′,v⟶′


## 3.2.4. HTDF Security

Next, it is proved that if the RSIS assumption holds, the HTDF functionℱ constructed above is safe. Recall that in the original HTDF security experiment, we generate the public key h along with the secret key td for h←$Rq∗.Theorem 2.
Suppose that theRSISq,2,βRSIS-assumption holds for the described parameters, then the HTDF function ℱ satisfies the HTDF security.Proof. Assume that there exists a PPT adversary A, which can have a nonnegligible probability δ win the HTDF security experiment. Then, we establish a probability polynomial time simulator S that breaks the RSIS q,2,βRSIS assumption with nonnegligible probability.Next, we revise the HTDF security experiment, we sampleh←$Rq∗, instead of sampling h,td←TrapGen1n,1ℓ,q and setting pk=h and sk=td. Please note that sk=td has never been used anywhere in the primeval HTDF security experiment. Hence, adversary A′s point of view among the original HTDF security experiment and the simulated HTDF security experiment are indistinguishable by Lemma 4. Specifically, adversary A attacks the security experiment of simulated HTDF and gains the security experiment with a probability of at least δ−neglλ.At present, we have proved that the PPT adversaryA, who won in the simulated HTDF security experiment, can be used to settle the RSIS problem. Suppose that the successful adversary A outputs values u⟶≠u⟶′∈U,x,x′∈X such that fpk,xu⟶=fpk,x′u⟶′. Let u⟶∗=u⟶−u⟶′ and x∗=x′−x. Then, we obtain as follows:(9)fpk,xu⟶=h,−1u⟶+xg⟶=h,−1u⟶′+x′g⟶=fpk,x′u⟶′⇒h,−1u⟶∗=x∗g⟶.Additionally, becauseu⟶,u⟶′∈U, it holds that u⟶∞,u⟶′∞≤βmax and thus u⟶∗∞≤2βmax. Moreover, since u⟶≠u⟶′, it holds that u⟶∗≠0⟶.To solve the RSIS problem defined byh,−1, where h∈Rq∗, then we talk over the two situations given below:x=x′: In this situation, the small u⟶∗=u⟶−u⟶′≠0⟶ is a nonzero solution of the RSIS problem, as h,−1u⟶−u⟶′=h,−1u⟶∗=x∗g⟶=x−x′g⟶=0, .x≠x′: On this event, we prove that the simulator S pretty good at using the knowledge of a small u⟶∗≠0⟶ and some x∗≠0 satisfying the right side of the (9) to find a nonzero solution of the RSIS problem (similarly as [2]).Samplet⟶←$R22 and let r⟶≜h,−1t⟶∈Rq. Calculate t⟶′=g⟶−1r⟶/x∗∈R2ℓ such that x∗g⟶t⟶′=r⟶. Therefore,(10)h,−1u⟶∗t⟶′−t⟶=h,−1u⟶∗t⟶′−h,−1t⟶=x∗g⟶t⟶′−r⟶=r⟶−r⟶=0⟶.Settingu⟶⋄≜u⟶∗t⟶′−t⟶, we then have h,−1u⟶⋄=0⟶ and u⋄∞≤2nℓβmax+1≤βSIS. Below the u⟶⋄≠0⟶, i.e., t⟶≠u⟶∗t⟶′ have to be proved. Here we show that, even given h,u⟶∗,x∗, the following inequality holds with overwhelming probability for uniformly random t⟶ Actually, we have(11)H˜∞t⟶|t⟶′≥H˜∞t⟶|h,−1t⟶≥ωn,The reason for the first inequality is thatt⟶′ is completely determined by r⟶=h,−1t⟶ as g⟶−1⋅ is deterministic, and the reason for the second inequality comes from Lemma 4. Therefore, Prt⟶=u⟶∗t⟶′≤2−ωn=neglλ.So, if the adversaryA wins any situation in the abovementioned simulated HTDF security game with a nonnegligible probability δ/2−neglλ, the simulator S will generate an effective and small enough solution to solve the RSIS problem with a probability of δ/2−neglλ. The process of the proof ends. □


## 3.3. Basic Homomorphic Evaluation

In an HTDF scheme, in order to verify an evaluated function value, we demand to design two corresponding algorithms: one is the input algorithm, another kind is the output algorithm, and both algorithms are deterministic. This is different from a homomorphic encryption system; in a homomorphic encryption system, only one (random or deterministic) homomorphic algorithm that acts on the ciphertext needs to be designed.The two basic homomorphic algorithms addition and multiplication are described as follows. Here, we will simplify some notations (e.g.,Evalin instead of HTDF.Evalin). Recall that for i=1,2, v⟶i=h,−1u⟶i+xig⟶. Let u⟶i∞≤βi and xi∈0,1.


### 3.3.1. Homomorphic Addition Algorithms

They calculate the sum of the corresponding input and output vectors, respectively.EvalinAdd,x1,u⟶1,v⟶1,x2,u⟶2,v⟶2≜u⟶1+u⟶2modqEvaloutAdd,v⟶1,v⟶2≜v⟶1+v⟶2modqThe noise of the addition is bounded byβ1+β2. The correctness comes from v⟶1+v⟶2=h,−1u⟶1+u⟶2+x1+x2g⟶.


### 3.3.2. Homomorphic Multiplication Algorithms

The homomorphic output multiplication algorithm is a multiplication of the output vectors which is performed the multiplication defined in Section3.1. The homomorphic input multiplication algorithm is asymmetric and it needs partial output, index, and the whole input to compute.EvalinMult,x1,u⟶1,v⟶1,x2,u⟶2,v⟶2≜u⟶1⋅g⟶−1v⟶2+x1u⟶2modqEvaloutMult,v⟶1,v⟶2≜v1⟶⋅g⟶−1v2⟶modqThe noise of multiplication is bounded bynℓβ1+x1β2=nℓβ1+β2. Assuming v⟶i=h,−1u⟶i+xig⟶, the correctness follows by the computation:(12)v⟶1⋅g⟶−1v2⟶=h,−1u⟶1+x1g⟶⋅g⟶−1v⟶2=h,−1u⟶1⋅g⟶−1v⟶2+x1h,−1u⟶2+x2g⟶=h,−1u⟶1⋅g⟶−1v⟶2+x1u⟶2+x1x2g⟶.


## 3.3.1. Homomorphic Addition Algorithms

They calculate the sum of the corresponding input and output vectors, respectively.EvalinAdd,x1,u⟶1,v⟶1,x2,u⟶2,v⟶2≜u⟶1+u⟶2modqEvaloutAdd,v⟶1,v⟶2≜v⟶1+v⟶2modqThe noise of the addition is bounded byβ1+β2. The correctness comes from v⟶1+v⟶2=h,−1u⟶1+u⟶2+x1+x2g⟶.


## 3.3.2. Homomorphic Multiplication Algorithms

The homomorphic output multiplication algorithm is a multiplication of the output vectors which is performed the multiplication defined in Section3.1. The homomorphic input multiplication algorithm is asymmetric and it needs partial output, index, and the whole input to compute.EvalinMult,x1,u⟶1,v⟶1,x2,u⟶2,v⟶2≜u⟶1⋅g⟶−1v⟶2+x1u⟶2modqEvaloutMult,v⟶1,v⟶2≜v1⟶⋅g⟶−1v2⟶modqThe noise of multiplication is bounded bynℓβ1+x1β2=nℓβ1+β2. Assuming v⟶i=h,−1u⟶i+xig⟶, the correctness follows by the computation:(12)v⟶1⋅g⟶−1v2⟶=h,−1u⟶1+x1g⟶⋅g⟶−1v⟶2=h,−1u⟶1⋅g⟶−1v⟶2+x1h,−1u⟶2+x2g⟶=h,−1u⟶1⋅g⟶−1v⟶2+x1u⟶2+x1x2g⟶.


## 3.4. Homomorphic Output and Input Evaluation

According to the abovementioned discussion, it is very easy to homomorphically calculate an arithmetic circuit or Boolean circuit similar as [2], we are not satisfied. We want to show how to design the scheme as well as [26] based on the fact that the noise growth is asymmetric.


### 3.4.1. Homomorphic Output Evaluation

Below we describe the definition of the homomorphic output evaluation algorithm(13)EvaloutΠ,v⟶0,v⟶0,ii∈w,v⟶jj∈t⟶v⟶Π,for a length is L and a width is w permutation branching program Π. In the initialization stage, we will assign v⟶0,v⟶0,ii∈w below and v⟶j is the vector such that v⟶j=h,−1u⟶j+xjg⟶, where u⟶j=u⟶j,1,u⟶j,2. Recall that rk,ξk,i,0,ξk,i,1k∈L,i∈w is a description of the permutation branching program Π, and the initial state vector is defined as the first w-dimensional unit vector e⟶0=1,0,0,…,0. For k∈L and i∈w, it holds that:(14)e⟶ki=e⟶k−1ξk,i,1⋅xrk+e⟶k−1ξk,i,0⋅1−xrk.Here, we give the full description of the process of the homomorphic output evaluation algorithmEvalout of the permutation branching program Π.Initialization: Letv⟶k,i be an output relevant to the state e⟶ki, where k∈L,i∈w,(1)
Choosev⟶0←$Rqℓ and set it to be a corresponding output of the state 1.(2)
Choosev⟶0,i←$Rqℓ and set it to be a corresponding initial output of the initial state e⟶0i.(3)
Setv⟶¯j≜v⟶0−v⟶j, where v⟶j (such that v⟶j=h,−1u⟶j+xjg⟶) is an output corresponding to xj, and set it to be a corresponding output of 1−xj.Calculation: Fork=1,2,…,L, suppose that at step k−1, we have v⟶k−1,ii∈w. Then, we can calculate inductively as follows:(15)v⟶k,i=v⟶rk⋅g⟶−1v⟶k−1,ξk,i,1+v⟶¯rk⋅g⟶−1v⟶k−1,ξk,i,0.Final output: After finishing the computation, we have the value ofv⟶L,ii∈w. Finally, output the final output v⟶L,1 corresponding to the state e⟶L1, i.e., v⟶Π=v⟶L,1.


### 3.4.2. Homomorphic Input Evaluation

Here, we give the full description of the process of the homomorphic input evaluation algorithmEvalinΠ,1,u⟶0,v⟶0, e⟶0i,u⟶0,i,v⟶0,ii∈w, xj,u⟶j,v⟶jj∈t⟶u⟶Π of the permutation branching program Π.Initialization: Letu⟶k,i be an input relevant to the state e⟶ki, where k∈L,i∈w.(1)
Sampleu⟶0=u⟶0,1,u⟶0,2←DU (such that v⟶0=h,−1u⟶0+1⋅g⟶) and set it as input relevant to the state 1.(2)
Sampleu⟶0,i=u⟶0,i,1,u⟶0,i,2←DU (such that v⟶0,i=h,−1u⟶0,i+e⟶0ig⟶) and set it as the initial input relevant to the initial state e⟶0i.(3)
Setu⟶¯j≜u⟶0−u⟶j, where u⟶j=u⟶j,1,u⟶j,2 (such that v⟶j=h,−1u⟶j+xjg⟶) is an input corresponding to xj, and set it to the input relevant to 1−xj.Calculation: Fork=1,2,…,L, suppose that at step k−1, we have u⟶k−1,ii∈w. Then, we can calculate inductively as follows.(16)u⟶k,i=u⟶rk⋅g⟶−1v⟶k−1,ξk,i,1+xrk⋅u⟶k−1,ξk,i,1+u⟶¯rk⋅g⟶−1v⟶k−1,ξk,i,0+1−xrk⋅u⟶k−1,ξk,i,0.Final input: After finishing the computation process, we have the value ofu⟶L,ii∈w. Finally, output the final input u⟶L,1 corresponding to e⟶L1, i.e., u⟶Π=u⟶L,1.


## 3.4.1. Homomorphic Output Evaluation

Below we describe the definition of the homomorphic output evaluation algorithm(13)EvaloutΠ,v⟶0,v⟶0,ii∈w,v⟶jj∈t⟶v⟶Π,for a length is L and a width is w permutation branching program Π. In the initialization stage, we will assign v⟶0,v⟶0,ii∈w below and v⟶j is the vector such that v⟶j=h,−1u⟶j+xjg⟶, where u⟶j=u⟶j,1,u⟶j,2. Recall that rk,ξk,i,0,ξk,i,1k∈L,i∈w is a description of the permutation branching program Π, and the initial state vector is defined as the first w-dimensional unit vector e⟶0=1,0,0,…,0. For k∈L and i∈w, it holds that:(14)e⟶ki=e⟶k−1ξk,i,1⋅xrk+e⟶k−1ξk,i,0⋅1−xrk.Here, we give the full description of the process of the homomorphic output evaluation algorithmEvalout of the permutation branching program Π.Initialization: Letv⟶k,i be an output relevant to the state e⟶ki, where k∈L,i∈w,(1)
Choosev⟶0←$Rqℓ and set it to be a corresponding output of the state 1.(2)
Choosev⟶0,i←$Rqℓ and set it to be a corresponding initial output of the initial state e⟶0i.(3)
Setv⟶¯j≜v⟶0−v⟶j, where v⟶j (such that v⟶j=h,−1u⟶j+xjg⟶) is an output corresponding to xj, and set it to be a corresponding output of 1−xj.Calculation: Fork=1,2,…,L, suppose that at step k−1, we have v⟶k−1,ii∈w. Then, we can calculate inductively as follows:(15)v⟶k,i=v⟶rk⋅g⟶−1v⟶k−1,ξk,i,1+v⟶¯rk⋅g⟶−1v⟶k−1,ξk,i,0.Final output: After finishing the computation, we have the value ofv⟶L,ii∈w. Finally, output the final output v⟶L,1 corresponding to the state e⟶L1, i.e., v⟶Π=v⟶L,1.


## 3.4.2. Homomorphic Input Evaluation

Here, we give the full description of the process of the homomorphic input evaluation algorithmEvalinΠ,1,u⟶0,v⟶0, e⟶0i,u⟶0,i,v⟶0,ii∈w, xj,u⟶j,v⟶jj∈t⟶u⟶Π of the permutation branching program Π.Initialization: Letu⟶k,i be an input relevant to the state e⟶ki, where k∈L,i∈w.(1)
Sampleu⟶0=u⟶0,1,u⟶0,2←DU (such that v⟶0=h,−1u⟶0+1⋅g⟶) and set it as input relevant to the state 1.(2)
Sampleu⟶0,i=u⟶0,i,1,u⟶0,i,2←DU (such that v⟶0,i=h,−1u⟶0,i+e⟶0ig⟶) and set it as the initial input relevant to the initial state e⟶0i.(3)
Setu⟶¯j≜u⟶0−u⟶j, where u⟶j=u⟶j,1,u⟶j,2 (such that v⟶j=h,−1u⟶j+xjg⟶) is an input corresponding to xj, and set it to the input relevant to 1−xj.Calculation: Fork=1,2,…,L, suppose that at step k−1, we have u⟶k−1,ii∈w. Then, we can calculate inductively as follows.(16)u⟶k,i=u⟶rk⋅g⟶−1v⟶k−1,ξk,i,1+xrk⋅u⟶k−1,ξk,i,1+u⟶¯rk⋅g⟶−1v⟶k−1,ξk,i,0+1−xrk⋅u⟶k−1,ξk,i,0.Final input: After finishing the computation process, we have the value ofu⟶L,ii∈w. Finally, output the final input u⟶L,1 corresponding to e⟶L1, i.e., u⟶Π=u⟶L,1.


## 3.5. Correctness of Homomorphic Evaluation and Noise Analysis

In the following lemmas, we testify the validity of homomorphic input and homomorphic output algorithms and explain in detail the noise growth in the above homomorphic evaluation.Lemma 5.
Suppose thatEvaloutΠ,v⟶0,v⟶0,ii∈w, v⟶jj∈t⟶v⟶Π and EvalinΠ,1,u⟶0,v⟶0, e⟶0i,u⟶0,i,v⟶0,ii∈w, xj,u⟶j,v⟶jj∈t⟶u⟶Π, where v⟶0=h,−1u⟶0+1⋅g⟶, v⟶0,i=h,−1u⟶0,i+e⟶0ig⟶ and v⟶j=h,−1u⟶j+xjg⟶ for i∈w,j∈t. Then for all k∈L,i∈w, we have v⟶k,i=h,−1u⟶k,i+e⟶kig⟶. For k=L, we have v⟶L,1=h,−1u⟶L,1+e⟶L1g⟶.Proof. Using formulas (1), (4), and (5) and the above conditions, for all k∈L,i∈w, it holds as follows:(17)v⟶k,i=v⟶rk⋅g⟶−1v⟶k−1,ξk,i,1+v⟶¯rk⋅g⟶−1v⟶k−1,ξk,i,0=h,−1u⟶rk+xrkg⟶⋅g⟶−1v⟶k−1,ξk,i,1+h,−1u⟶¯rk+1−xrkg⟶⋅g⟶−1v⟶k−1,ξk,i,0=h,−1u⟶rk⋅g⟶−1v⟶k−1,ξk,i,1+xrkh,−1u⟶k−1,ξk,i,1+xrk⋅e⟶k−1ξk,i,1g⟶+h,−1u⟶¯rk⋅g⟶−1v⟶k−1,ξk,i,0+1−xrkh,−1u⟶k−1,ξk,i,0+1−xrk⋅e⟶k−1ξk,i,0g⟶=h,−1u⟶rk⋅g⟶−1v⟶k−1,ξk,i,1+xrk⋅u⟶k−1,ξk,i,1+u⟶¯rk⋅g⟶−1v⟶k−1,ξk,i,0+1−xrk⋅u⟶k−1,ξk,i,0+xrk⋅e⟶k−1ξk,i,1+1−xrk⋅e⟶k−1ξk,i,0⋅g⟶=h,−1u⟶k,i+e⟶kig⟶.The process of proof ends. □Lemma 6.
Assuming  thatEvalinΠ,1,u⟶0,v⟶0, e⟶0i,u⟶0,i,v⟶0,ii∈w, xj,u⟶j,v⟶jj∈t⟶u⟶Π and all the noises of the inputs are bounded by β, i.e., u⟶0∞,u⟶0,i∞, u⟶j∞≤β, then we have ‖u⟶Π‖∞≤3nℓLβ+β.Proof. We use the inductive method to prove the lemma. That is, for any stepk=0,1,2,…,L and i∈w, we will show that ‖u⟶k,i‖∞≤3nℓkβ+β.Ifk=0, it is not difficult to find that all the initial noises are such that u⟶0,i∞≤β,i∈w.Suppose that at stepk−1, we have u⟶k−1,i∞≤3nℓk−1β+β. Then, according to formula (16), we have as follows:(18)u⟶k,i∞=u⟶rk⋅g⟶−1v⟶k−1,ξk,i,1+xrk⋅u⟶k−1,ξk,i,1+u⟶¯rk⋅g⟶−1v⟶k−1,ξk,i,0+1−xrk⋅u⟶k−1,ξk,i,0∞≤u⟶rk⋅g⟶−1v⟶k−1,ξk,i,1∞+xrk⋅u⟶k−1,ξk,i,1∞+u⟶¯rk⋅g⟶−1v⟶k−1,ξk,i,0∞+1−xrk⋅u⟶k−1,ξk,i,0∞≤nℓβ+xrk⋅3nℓk−1β+β+2nℓβ+1−xrk⋅3nℓk−1β+β=3nℓkβ+β,where u⟶¯rk∞=u⟶0−u⟶rk∞≤u⟶0∞+u⟶rk∞≤β+β=2β.Through induction, we obtainu⟶Π∞=u⟶L,1∞≤3nℓLβ+β. The process of proof ends. □Remark 1.
Barrington’s theorem [32] states that a circuit with a depth of d can be transformed into a permutation branching program with a length of 4d. Thus, simply by setting d≤polyλ, the resulting maximum noise level is less than O4dnℓβ. In particular, in the setting where it only requires d=Ologλ, we obtain the modulus q=polyλ>O4dnℓβ to be a middle large polynomial, which can supply a better security for the scheme. In other words, it is based on Ideal-SVP assumption with polynomial approximation factors.


## 4. Strongly Unforgeable NTRU-Based FHS

We construct a single key FHS scheme that is strongly unforgeable against selective chosen-message-attack (SU-sCMA) using the HTDF function, which appears in the form of a black box in the fore chapter.


### 4.1. Definition

A single data-set homomorphic signature scheme consists of the following seven PPT algorithms PrmsGen, KeyGen, Sign, SignEval, Process, and Verify:prms←PrmsGen1λ,1N: Input the security parameter λ and the maximum data-size N, and output public parameters prms. In addition, the security parameters define the message space X.pk,sk←KeyGen1λ: Take the security parameter λ as input. Output the key pair pk,sk of verification key and signing key.σ1,…,σN←Signskprms,x1,…,xN: Sign data x1,…,xN∈XN.σg=SignEvalprmsg,x1,σ1,…,xt,σt: Deterministically and homomorphically evaluate a signature σg for some function g over x1,…,xt∈Xt.vg=Processprmsg: A deterministic algorithm that can homomorphically evaluate a certificate vg from the public parameters prms.Verifypkvg,y,σg: Verify that y is indeed the output of function g by proving that σg and vg are corresponding.


#### 4.1.1. Correctness

Forprms←PrmsGen1λ,1N, pk,sk←KeyGen1λ,prms, x1,…,xN∈XN, σ1,…,σN←Signskprms,x1,…,xN, and g:XN⟶X, we need the following equation:(19)Verifypkvg,y=gx1,…,xN,σg=accept,holds, where vg=Processprmsg and σg=SignEvalprmsg,x1,σ1,…,xt,σt.Notice that the correctness of singing by settingg=idi and hence omitted, where idi is the i-th identity mapping.


#### 4.1.2. Relaxed Correctness of Leveled FHS

Since the relaxed correctness of the leveled FHS can be deduced from the correctness of the leveled HTDF, we omit this process.


#### 4.1.3. Security Experiment

The SU-sCMA security experiment for FHS describes the adversary needs to determine the data to be signed before receiving public parameters and verification key. Then, the adversary struggled to discoverg,y′,σ′ so that it could meet the conditions for winning the experiment. It is noted that here we do not require y=y′ or y\≠y′. Therefore, if y=y′ holds, then σ′ is a strongly forgeable signature, otherwise it is an existentially forgeable signature.We now proceed to define the SU-sCMA security experiment for FHS among an adversaryA and a challenger C as follows:The adversaryA selects at one-time data x1,…,xN∈XN and sends it to the challenger C.The challengerC runs prms←PrmsGen1λ,1N and pk,sk←KeyGen1λ,prms and returns prms,pk back to the adversary A.The challengerC runs σ1,…,σN←Signskprms,x1,…,xN and sends the signatures σ1,…,σN to the adversary A.The adversaryA selects a function g:XN⟶X and values y′,σ′. Let y=gx1…,xN. If all the following conditions are met, A wins:(1)
g is admissible on the data-set x1,…,xN;(2)
σ′≠σg, where σg=SignEvalprmsg,x1,σ1,…,xN,σN;(3)
Verifypkvg,y′,σ′ accept, where vg=Processprmsg.If for all PPT adversaryA, inequality PrAwins≤neglλ always holds. We say that the FHS scheme is SU-sCMA secure.Remark 2.
Define the stronger SU-aCMA security notion for FHS describing the strongly unforgeable adaptive chosen-message-attack game, where the adversary can select data to be signed after seeing the public parameters and the verification key. It is to be noted that an adaptively secure FHS can be transformed from a selectively secure FHS together with a chameleon hash with homomorphism [2], and that our HTDF built in the previous section is a chameleon hash. Therefore, we believe that we can obtain an adaptively secure NTRU-based FHS via the transformation.


### 4.2. Construction

Letℱ=HTDF.KeyGen,f,Inv,HTDF.Evalin, HTDF.Evalout be an HTDF with index space X, input space U, output space V and some efficiently sampleable input distribution DU over U. We construct an FHS scheme S=PrmsGen,KeyGen,Sign,SignEval,Process,Verify, with message space X as follows.prms←PrmsGen1λ,1N: Sample vi←V,i∈N and set public parameters prms=v1,…,vN.pk,sk←KeyGen1λ,prms: Choose pk′,sk′←HTDF.KeyGen and set pk=pk′,sk=sk′.σ1,…,σN←Signskprms,x1,…,xN: Sample ui←Invsk′,xivi and set σi=ui,i∈N.σg=SignEvalprmsg,x1,σ1,…,xt,σt: Run HTDF.Evaling, x1,u1,v1,…,xt,ut,vt and output ug, then set σg=ug.vg=Processprmsg: Run HTDF.Evaloutg,v1,…,vt and output the result vg.Verifypkvg,y,σg: If fpk′,yσg=vg accept, else reject.


#### 4.2.1. Correctness

The discussion on the correctness of the above-built leveled FHS is the same as the discussion on the correctness of the underlying leveledHTDFℱ, so it is omitted.


#### 4.2.2. Security

Now, we testify that the above FHS scheme is SU-sCMA secure.Theorem 3.
Supposeℱ is a secure HTDF function, then the above FHS scheme S is SU-sCMA secure.Proof. Assume there exists a PPT adversary A that wins the SU-sCMA security experiment of FHS with nonnegligible probability δ. We build a PPT reduction ℬ that breaks the HTDF security of ℱ.In the SU-sCMA experiment, adversaryA first selects a data x1,…,xN∈XN and then receives prms=v1,…,vN, pk′ and σ1,…,σN, where vi←V,pk′,sk′←HTDF.KeyGen and σi=ui←Invsk′,xivi. Next, we revise the experiment by sampling ui←DU and setting vi=fpk′,xiui. Adversary A′s point of view among the original security experiment and the changed security experiment are indistinguishable by the distributional equivalence of inversion property of the underlying HTDF function. Therefore, A attacks the changed experiment and wins with a probability of at least δ−neglλ.Then, we prove that there is a PPT reductionℬ, which can take any PPT adversary A, and the adversary has the ability to win the changed experiment with nonnegligible advantage δ−neglλ. Hence, the probability of breaking the HTDF security experiment of the underlying ℱ is δ−neglλ.After receiving a challenge public keypk′ and a data-set x1,…,xN, the reduction ℬ selects σi=uii∈N and computes vii∈N as in the changed experiment and returns pk′,σi,vii∈N back to A.Suppose that the adversaryA winning the changed experiment outputs values g,y′,σ′, where g:XN⟶X is an admissible function and σ′=u′. Let y=gx1,…,xN,ug=σg=SignEvalprmsg, x1,σ1, …,xt,σt,vg=Processprmsg. So, on the one hand, fpk,y′u′=vg holds as the forged signature σ′ verifies. On the other hand, fpk,yug=vg also holds as g is admissible. Thus, we have values ug≠u′∈U and y,y′∈X satisfying fpk,yug=fpk,y′u′, which allows ℬ to break HTDF security of ℱ with probability δ−neglλ whenever A wins the changed experiment with probability δ−neglλ. □


## 4.1. Definition

A single data-set homomorphic signature scheme consists of the following seven PPT algorithms PrmsGen, KeyGen, Sign, SignEval, Process, and Verify:prms←PrmsGen1λ,1N: Input the security parameter λ and the maximum data-size N, and output public parameters prms. In addition, the security parameters define the message space X.pk,sk←KeyGen1λ: Take the security parameter λ as input. Output the key pair pk,sk of verification key and signing key.σ1,…,σN←Signskprms,x1,…,xN: Sign data x1,…,xN∈XN.σg=SignEvalprmsg,x1,σ1,…,xt,σt: Deterministically and homomorphically evaluate a signature σg for some function g over x1,…,xt∈Xt.vg=Processprmsg: A deterministic algorithm that can homomorphically evaluate a certificate vg from the public parameters prms.Verifypkvg,y,σg: Verify that y is indeed the output of function g by proving that σg and vg are corresponding.


### 4.1.1. Correctness

Forprms←PrmsGen1λ,1N, pk,sk←KeyGen1λ,prms, x1,…,xN∈XN, σ1,…,σN←Signskprms,x1,…,xN, and g:XN⟶X, we need the following equation:(19)Verifypkvg,y=gx1,…,xN,σg=accept,holds, where vg=Processprmsg and σg=SignEvalprmsg,x1,σ1,…,xt,σt.Notice that the correctness of singing by settingg=idi and hence omitted, where idi is the i-th identity mapping.


### 4.1.2. Relaxed Correctness of Leveled FHS

Since the relaxed correctness of the leveled FHS can be deduced from the correctness of the leveled HTDF, we omit this process.


### 4.1.3. Security Experiment

The SU-sCMA security experiment for FHS describes the adversary needs to determine the data to be signed before receiving public parameters and verification key. Then, the adversary struggled to discoverg,y′,σ′ so that it could meet the conditions for winning the experiment. It is noted that here we do not require y=y′ or y\≠y′. Therefore, if y=y′ holds, then σ′ is a strongly forgeable signature, otherwise it is an existentially forgeable signature.We now proceed to define the SU-sCMA security experiment for FHS among an adversaryA and a challenger C as follows:The adversaryA selects at one-time data x1,…,xN∈XN and sends it to the challenger C.The challengerC runs prms←PrmsGen1λ,1N and pk,sk←KeyGen1λ,prms and returns prms,pk back to the adversary A.The challengerC runs σ1,…,σN←Signskprms,x1,…,xN and sends the signatures σ1,…,σN to the adversary A.The adversaryA selects a function g:XN⟶X and values y′,σ′. Let y=gx1…,xN. If all the following conditions are met, A wins:(1)
g is admissible on the data-set x1,…,xN;(2)
σ′≠σg, where σg=SignEvalprmsg,x1,σ1,…,xN,σN;(3)
Verifypkvg,y′,σ′ accept, where vg=Processprmsg.If for all PPT adversaryA, inequality PrAwins≤neglλ always holds. We say that the FHS scheme is SU-sCMA secure.Remark 2.
Define the stronger SU-aCMA security notion for FHS describing the strongly unforgeable adaptive chosen-message-attack game, where the adversary can select data to be signed after seeing the public parameters and the verification key. It is to be noted that an adaptively secure FHS can be transformed from a selectively secure FHS together with a chameleon hash with homomorphism [2], and that our HTDF built in the previous section is a chameleon hash. Therefore, we believe that we can obtain an adaptively secure NTRU-based FHS via the transformation.


## 4.1.1. Correctness

Forprms←PrmsGen1λ,1N, pk,sk←KeyGen1λ,prms, x1,…,xN∈XN, σ1,…,σN←Signskprms,x1,…,xN, and g:XN⟶X, we need the following equation:(19)Verifypkvg,y=gx1,…,xN,σg=accept,holds, where vg=Processprmsg and σg=SignEvalprmsg,x1,σ1,…,xt,σt.Notice that the correctness of singing by settingg=idi and hence omitted, where idi is the i-th identity mapping.


## 4.1.2. Relaxed Correctness of Leveled FHS

Since the relaxed correctness of the leveled FHS can be deduced from the correctness of the leveled HTDF, we omit this process.


## 4.1.3. Security Experiment

The SU-sCMA security experiment for FHS describes the adversary needs to determine the data to be signed before receiving public parameters and verification key. Then, the adversary struggled to discoverg,y′,σ′ so that it could meet the conditions for winning the experiment. It is noted that here we do not require y=y′ or y\≠y′. Therefore, if y=y′ holds, then σ′ is a strongly forgeable signature, otherwise it is an existentially forgeable signature.We now proceed to define the SU-sCMA security experiment for FHS among an adversaryA and a challenger C as follows:The adversaryA selects at one-time data x1,…,xN∈XN and sends it to the challenger C.The challengerC runs prms←PrmsGen1λ,1N and pk,sk←KeyGen1λ,prms and returns prms,pk back to the adversary A.The challengerC runs σ1,…,σN←Signskprms,x1,…,xN and sends the signatures σ1,…,σN to the adversary A.The adversaryA selects a function g:XN⟶X and values y′,σ′. Let y=gx1…,xN. If all the following conditions are met, A wins:(1)
g is admissible on the data-set x1,…,xN;(2)
σ′≠σg, where σg=SignEvalprmsg,x1,σ1,…,xN,σN;(3)
Verifypkvg,y′,σ′ accept, where vg=Processprmsg.If for all PPT adversaryA, inequality PrAwins≤neglλ always holds. We say that the FHS scheme is SU-sCMA secure.Remark 2.
Define the stronger SU-aCMA security notion for FHS describing the strongly unforgeable adaptive chosen-message-attack game, where the adversary can select data to be signed after seeing the public parameters and the verification key. It is to be noted that an adaptively secure FHS can be transformed from a selectively secure FHS together with a chameleon hash with homomorphism [2], and that our HTDF built in the previous section is a chameleon hash. Therefore, we believe that we can obtain an adaptively secure NTRU-based FHS via the transformation.


## 4.2. Construction

Letℱ=HTDF.KeyGen,f,Inv,HTDF.Evalin, HTDF.Evalout be an HTDF with index space X, input space U, output space V and some efficiently sampleable input distribution DU over U. We construct an FHS scheme S=PrmsGen,KeyGen,Sign,SignEval,Process,Verify, with message space X as follows.prms←PrmsGen1λ,1N: Sample vi←V,i∈N and set public parameters prms=v1,…,vN.pk,sk←KeyGen1λ,prms: Choose pk′,sk′←HTDF.KeyGen and set pk=pk′,sk=sk′.σ1,…,σN←Signskprms,x1,…,xN: Sample ui←Invsk′,xivi and set σi=ui,i∈N.σg=SignEvalprmsg,x1,σ1,…,xt,σt: Run HTDF.Evaling, x1,u1,v1,…,xt,ut,vt and output ug, then set σg=ug.vg=Processprmsg: Run HTDF.Evaloutg,v1,…,vt and output the result vg.Verifypkvg,y,σg: If fpk′,yσg=vg accept, else reject.


### 4.2.1. Correctness

The discussion on the correctness of the above-built leveled FHS is the same as the discussion on the correctness of the underlying leveledHTDFℱ, so it is omitted.


### 4.2.2. Security

Now, we testify that the above FHS scheme is SU-sCMA secure.Theorem 3.
Supposeℱ is a secure HTDF function, then the above FHS scheme S is SU-sCMA secure.Proof. Assume there exists a PPT adversary A that wins the SU-sCMA security experiment of FHS with nonnegligible probability δ. We build a PPT reduction ℬ that breaks the HTDF security of ℱ.In the SU-sCMA experiment, adversaryA first selects a data x1,…,xN∈XN and then receives prms=v1,…,vN, pk′ and σ1,…,σN, where vi←V,pk′,sk′←HTDF.KeyGen and σi=ui←Invsk′,xivi. Next, we revise the experiment by sampling ui←DU and setting vi=fpk′,xiui. Adversary A′s point of view among the original security experiment and the changed security experiment are indistinguishable by the distributional equivalence of inversion property of the underlying HTDF function. Therefore, A attacks the changed experiment and wins with a probability of at least δ−neglλ.Then, we prove that there is a PPT reductionℬ, which can take any PPT adversary A, and the adversary has the ability to win the changed experiment with nonnegligible advantage δ−neglλ. Hence, the probability of breaking the HTDF security experiment of the underlying ℱ is δ−neglλ.After receiving a challenge public keypk′ and a data-set x1,…,xN, the reduction ℬ selects σi=uii∈N and computes vii∈N as in the changed experiment and returns pk′,σi,vii∈N back to A.Suppose that the adversaryA winning the changed experiment outputs values g,y′,σ′, where g:XN⟶X is an admissible function and σ′=u′. Let y=gx1,…,xN,ug=σg=SignEvalprmsg, x1,σ1, …,xt,σt,vg=Processprmsg. So, on the one hand, fpk,y′u′=vg holds as the forged signature σ′ verifies. On the other hand, fpk,yug=vg also holds as g is admissible. Thus, we have values ug≠u′∈U and y,y′∈X satisfying fpk,yug=fpk,y′u′, which allows ℬ to break HTDF security of ℱ with probability δ−neglλ whenever A wins the changed experiment with probability δ−neglλ. □


## 4.2.1. Correctness

The discussion on the correctness of the above-built leveled FHS is the same as the discussion on the correctness of the underlying leveledHTDFℱ, so it is omitted.


## 4.2.2. Security

Now, we testify that the above FHS scheme is SU-sCMA secure.Theorem 3.
Supposeℱ is a secure HTDF function, then the above FHS scheme S is SU-sCMA secure.Proof. Assume there exists a PPT adversary A that wins the SU-sCMA security experiment of FHS with nonnegligible probability δ. We build a PPT reduction ℬ that breaks the HTDF security of ℱ.In the SU-sCMA experiment, adversaryA first selects a data x1,…,xN∈XN and then receives prms=v1,…,vN, pk′ and σ1,…,σN, where vi←V,pk′,sk′←HTDF.KeyGen and σi=ui←Invsk′,xivi. Next, we revise the experiment by sampling ui←DU and setting vi=fpk′,xiui. Adversary A′s point of view among the original security experiment and the changed security experiment are indistinguishable by the distributional equivalence of inversion property of the underlying HTDF function. Therefore, A attacks the changed experiment and wins with a probability of at least δ−neglλ.Then, we prove that there is a PPT reductionℬ, which can take any PPT adversary A, and the adversary has the ability to win the changed experiment with nonnegligible advantage δ−neglλ. Hence, the probability of breaking the HTDF security experiment of the underlying ℱ is δ−neglλ.After receiving a challenge public keypk′ and a data-set x1,…,xN, the reduction ℬ selects σi=uii∈N and computes vii∈N as in the changed experiment and returns pk′,σi,vii∈N back to A.Suppose that the adversaryA winning the changed experiment outputs values g,y′,σ′, where g:XN⟶X is an admissible function and σ′=u′. Let y=gx1,…,xN,ug=σg=SignEvalprmsg, x1,σ1, …,xt,σt,vg=Processprmsg. So, on the one hand, fpk,y′u′=vg holds as the forged signature σ′ verifies. On the other hand, fpk,yug=vg also holds as g is admissible. Thus, we have values ug≠u′∈U and y,y′∈X satisfying fpk,yug=fpk,y′u′, which allows ℬ to break HTDF security of ℱ with probability δ−neglλ whenever A wins the changed experiment with probability δ−neglλ. □


## 5. Conclusion and Open Problem

In this paper, we propose an SU-sCMA secure NTRU-based FHS scheme, which can be transformed to an SU-aCMA one with the help of NTRU-based HTDF functions (and without additional assumptions) using a similar transformation as introduced in [2]. Our next station is improving the efficiency of our FHS scheme and accomplishing the implementation with the consideration of practical attacks [36–39]. In addition, it is well known that the leveled FHE can be transformed into pure FHE via bootstrapping [40], the only workable way to get pure FHE at the present. However, there is no similar bootstrapping to improve homomorphic capability in the HS scenario, as the evaluated signature not only certifies the corresponding message, but also certifies the computation process. Therefore, it is still open to build a pure FHS.



---

*Source: 9942717-2022-06-22.xml*