# Lattice-Based Linearly Homomorphic Signature Scheme overF2

Authors: Jie Cai; Han Jiang; Hao Wang; Qiuliang Xu
Journal: Security and Communication Networks
 (2020)

---

## Abstract

In this paper, we design a new lattice-based linearly homomorphic signature scheme overF2. The existing schemes are all constructed based on hash-and-sign lattice-based signature framework, where the implementation of preimage sampling function is Gaussian sampling, and the use of trapdoor basis needs a larger dimension m≥5nlogq. Hence, they cannot resist potential side-channel attacks and have larger sizes of public key and signature. Under Fiat–Shamir with aborting signature framework and general SIS problem restricted condition m≥nlogq, we use uniform sampling of filtering technology to design the scheme, and then, our scheme has a smaller public key size and signature size than the existing schemes and it can resist side-channel attacks.


---

## Body

## 1. Introduction

The idea of the linear homomorphic signature scheme comes from network coding routing mechanism. Specifically, after a signer sends a number of signatures for messages to router (verifier) in a computer network using network coding, the router can generate a random linear combinationμ of the received messages. Using the homomorphic property, the router computes a signature σ of μ and transmits σ,μ to the next router, and the process will be continued for different linear combined messages. The final router accepts properly signed signature and recovers the original message by solving a full-rank linear system over Fp.Then, one can easily abstract definition from applications. Informally, givenn−dimensional message vectors μ1,…,μk∈Fpn and signatures σ1,…,σk, anyone can create a signature for any vector μ∈spanμ1,…,μk. At the same time, if any adversary cannot produce a valid signature for μ′∉spanμ1,…,μk, we say the linear homomorphic signature scheme is secure. There exit many classical linearly homomorphic signatures [1–4] based on the difficulty in solving discrete logarithm or the difficulty in integer factoring. However, they have two obvious disadvantages.First, the parameterp must be large enough to guarantee the difficulties in classical problems, but implementations are generally given over F2 in network coding. Second, these schemes cannot resist quantum computing attack as we all know. Hence, more and more people focus on designing postquantum linearly homomorphic signature scheme over F2, where lattice-based schemes are significant.


## 2. Related Work

### 2.1. Lattice-Based Signature Schemes

The existing lattice-based signature schemes are mostly based on short integer solution (SIS) problem first provided in [5] x:As=0modq,s≤β,A∈ℤqn×m,s∈ℤm. There are two frameworks to construct lattice-based signature schemes: hash-and-sign type [6, 7] and Fiat–Shamir type [8–11]. In schemes of hash-and-sign type, the signer uses trapdoor basis to compute preimage sampling function to create signature σ satisfying Aσ=Hμmodq, where H is a hash function. Unlike the hash-and-sign lattice-based signature framework, aborting technology is used in schemes of Fiat–Shamir type without trapdoor. This is the output of the signature z=sc+y according to some probabilities (rejection sampling) or the norm of signature must be in a security range (filtering outputting), where c=HAymodq,μ and y⟵Dy (D is a Gaussian distribution or uniform distribution).Furthermore, Gaussian distribution is utilized in preimage sampling and rejection sampling, which cannot resist partial side-channel attacks (see [12, 13]). Although, the author in [14] showed that an almost perfect implementation could resist these attacks, and the designed programme errors might occur.


### 2.2. Lattice-Based Linearly Homomorphic Signature

The first lattice-based linearly homomorphic signature scheme overF2 was proposed by Boneh and Freeman [15] in 2011, which was based on k−SIS problem, that is, finding a solution s satisfying s∉spans1,…,sk under giving Asi=0modq. In addition, the specific sign process is Aσ=Hμmod2q, where A∈ℤ2qn×m. Soon after, Wang et al. proposed an improved scheme [16] based on the general SIS problem, and the size of public key and signature is smaller than [15] by changing 2q into q. Compared to signature size, 2m+2mlogq+n in scheme [15, 16] has the smaller size mlogq+n.In fact, both of them are designed in terms of the hash-and-sign lattice-based signature framework [6], where Gaussian sampling is used inevitably. Meanwhile, the generation of trapdoor basis needs that lattice dimension is m≥5nlogq (see [17, 18]), which is larger than m≥nlogq for SIS problem itself.


### 2.3. Our Contributions

In this paper, our scheme overcomes the drawbacks of existing schemes. Specifically, based on the SIS problem, we use filtering technology of Fiat–Shamir with aborting signature framework to design a new linearly homomorphic signature scheme overF2, and the advantages can be seen as follows:(1)
The signature size is smaller than existing lattice-based schemes. The signature of our scheme isσ=z,h,τ, and the size is 2mlogq+n, where m≥nlogq. Since our design does not utilize preimage trapdoor sampling, the signature size is smaller than m′logq+n in [16] with the same n and q, where m′≥5nlogq. Here, we use a different lattice dimension m′ to distinguish the difference in signature size.(2)
Our scheme can resist side-channel attacks. Using filtering technology, the masked elementy is chosen uniformly at random under restriction y∞≤γ, and z must satisfy the condition z∞≤γ−β; otherwise, z⟵⊥ (aborting). Hence, the signature output can protect secret key, and the scheme can resist side-channel attacks without Gaussian sampling.


### 2.4. Organization of the Paper

We will provide two main technical descriptions to show how our scheme can have the above advantages in Section3. Then, we propose the basic notations and definitions of linearly homomorphic signature in Section 4. We show the detailed design and security proof of our lattice-based linearly homomorphic signature in Section 5 and Section 6, respectively. In Section 7, we present efficiency comparisons. Finally, we give a conclusion and further work in Section 8. Data availability, conflicts of interest, and funding statement can be seen in the last three sections, respectively.


## 2.1. Lattice-Based Signature Schemes

The existing lattice-based signature schemes are mostly based on short integer solution (SIS) problem first provided in [5] x:As=0modq,s≤β,A∈ℤqn×m,s∈ℤm. There are two frameworks to construct lattice-based signature schemes: hash-and-sign type [6, 7] and Fiat–Shamir type [8–11]. In schemes of hash-and-sign type, the signer uses trapdoor basis to compute preimage sampling function to create signature σ satisfying Aσ=Hμmodq, where H is a hash function. Unlike the hash-and-sign lattice-based signature framework, aborting technology is used in schemes of Fiat–Shamir type without trapdoor. This is the output of the signature z=sc+y according to some probabilities (rejection sampling) or the norm of signature must be in a security range (filtering outputting), where c=HAymodq,μ and y⟵Dy (D is a Gaussian distribution or uniform distribution).Furthermore, Gaussian distribution is utilized in preimage sampling and rejection sampling, which cannot resist partial side-channel attacks (see [12, 13]). Although, the author in [14] showed that an almost perfect implementation could resist these attacks, and the designed programme errors might occur.


## 2.2. Lattice-Based Linearly Homomorphic Signature

The first lattice-based linearly homomorphic signature scheme overF2 was proposed by Boneh and Freeman [15] in 2011, which was based on k−SIS problem, that is, finding a solution s satisfying s∉spans1,…,sk under giving Asi=0modq. In addition, the specific sign process is Aσ=Hμmod2q, where A∈ℤ2qn×m. Soon after, Wang et al. proposed an improved scheme [16] based on the general SIS problem, and the size of public key and signature is smaller than [15] by changing 2q into q. Compared to signature size, 2m+2mlogq+n in scheme [15, 16] has the smaller size mlogq+n.In fact, both of them are designed in terms of the hash-and-sign lattice-based signature framework [6], where Gaussian sampling is used inevitably. Meanwhile, the generation of trapdoor basis needs that lattice dimension is m≥5nlogq (see [17, 18]), which is larger than m≥nlogq for SIS problem itself.


## 2.3. Our Contributions

In this paper, our scheme overcomes the drawbacks of existing schemes. Specifically, based on the SIS problem, we use filtering technology of Fiat–Shamir with aborting signature framework to design a new linearly homomorphic signature scheme overF2, and the advantages can be seen as follows:(1)
The signature size is smaller than existing lattice-based schemes. The signature of our scheme isσ=z,h,τ, and the size is 2mlogq+n, where m≥nlogq. Since our design does not utilize preimage trapdoor sampling, the signature size is smaller than m′logq+n in [16] with the same n and q, where m′≥5nlogq. Here, we use a different lattice dimension m′ to distinguish the difference in signature size.(2)
Our scheme can resist side-channel attacks. Using filtering technology, the masked elementy is chosen uniformly at random under restriction y∞≤γ, and z must satisfy the condition z∞≤γ−β; otherwise, z⟵⊥ (aborting). Hence, the signature output can protect secret key, and the scheme can resist side-channel attacks without Gaussian sampling.


## 2.4. Organization of the Paper

We will provide two main technical descriptions to show how our scheme can have the above advantages in Section3. Then, we propose the basic notations and definitions of linearly homomorphic signature in Section 4. We show the detailed design and security proof of our lattice-based linearly homomorphic signature in Section 5 and Section 6, respectively. In Section 7, we present efficiency comparisons. Finally, we give a conclusion and further work in Section 8. Data availability, conflicts of interest, and funding statement can be seen in the last three sections, respectively.


## 3. Technical Notes

In this part, we give detailed descriptions to show how we get a smaller signature size and the scheme can resist side-channel attacks.


### 3.1. Different Lattice Dimension Assumptions

As we know, given security parametern, m influences the signature size directly. Thus, we want to reduce it. Fortunately, compared to hash-and-sign signature framework, the Fiat–Shamir signature framework has advantage in this aspect. We show the main reason as follows.Definition 1.
(the short integer solution problem SIS). Givenm uniformly random elements ai∈ℤqn, find a nonzero z∈ℤm of norm z≤β satisfying(1)∑i=1maizi=0∈ℤqn.
Usually, it is denotedAz=0∈ℤqn, where ai∈ℤqn forms the columns of A∈ℤqn×m. To guarantee the hardness (existence of solution) of this problem, the parameters satisfy conditions m≤β<q,m≥nlogq,q∈ℤ+,n≥100. Normally, people consider the inhomogeneous version of the SIS problem, which is to find a small solution of equation Az=b.
To design Fiat–Shamir signature schemes, the lattice dimensionm satisfies m≥nlogq enough. However, hash-and-sign type needs m≥5nlogq to get trapdoor basis; thus, we provide the existing conclusion below.Proposition 1 (see [6, 17, 18]).
Given any primeq and m≥5nlogq, then there exists a PPT algorithm which outputs A∈ℤqn×m statistically close to uniform over ℤqn×m and a full-rank set S⊂Λ⊥A,S≤m2.5 by input 1n. Then, it further gets a good basis T⊂Λ⊥A satisfying T≤S.From what has been discussed above, we get the smallerm the better for the size of signature and secret key under the same n. Hence, we design a new scheme using Fiat–Shamir signature framework without trapdoor (basis).


### 3.2. Filtering Technology

Since the existing lattice-based linearly homomorphic signature schemes are based on the hash-and-sign signature framework in which they use preimage sampling function implemented by Gaussian sampling, the schemes cannot resist side-channel attacks. Hence, we unitize uniform sampling of Fiat–Shamir framework to generate signature.The idea of filtering can be traced back to [10, 19], and it is formally provided in [20] to design a blind signature scheme. Here, we rewrite this lemma according to our construction.Lemma 1.
For arbitrarya∈x∈ℤk:x∞≤β and random b⟵x∈ℤk:x∞≤γ,k=Ωn, if γ≥ϕkβ with ϕ∈ℕ+, then we have Pra−b∞≤γ−β>1/e1/ϕ−o1.Then, the repeat time of our scheme can be computed bye1/ϕ. Intuitively, bigger ϕ size is better. However, this value has influence on the size of a−b∞ directly; thus, it leads to increased communication costs. Hence, we can assign this value according to different efficiency requirements, which is a nice advantage in practice. According to [20], the authors provide the condition ϕ=4 is the best; then, the repeat time is no more than 2, which is also hold for our scheme.In our scheme, the parametersγ,β satisfy γ,β<q. In addition, to facilitate comparisons with schemes [15, 16], we use a−b∞≤q to compute signature size instead of γ−β (see Table 1).Table 1
Comparison.
Public key sizeSignature sizeDimensionResist side-channel attacks[15]m′n+m′nlogq2m′+2m′logq+nm′≥5nlogq×[16]m′nlogqm′logq+nm′≥5nlogq×Oursmnlogq2mlogq+nm≥nlogq√


## 3.1. Different Lattice Dimension Assumptions

As we know, given security parametern, m influences the signature size directly. Thus, we want to reduce it. Fortunately, compared to hash-and-sign signature framework, the Fiat–Shamir signature framework has advantage in this aspect. We show the main reason as follows.Definition 1.
(the short integer solution problem SIS). Givenm uniformly random elements ai∈ℤqn, find a nonzero z∈ℤm of norm z≤β satisfying(1)∑i=1maizi=0∈ℤqn.
Usually, it is denotedAz=0∈ℤqn, where ai∈ℤqn forms the columns of A∈ℤqn×m. To guarantee the hardness (existence of solution) of this problem, the parameters satisfy conditions m≤β<q,m≥nlogq,q∈ℤ+,n≥100. Normally, people consider the inhomogeneous version of the SIS problem, which is to find a small solution of equation Az=b.
To design Fiat–Shamir signature schemes, the lattice dimensionm satisfies m≥nlogq enough. However, hash-and-sign type needs m≥5nlogq to get trapdoor basis; thus, we provide the existing conclusion below.Proposition 1 (see [6, 17, 18]).
Given any primeq and m≥5nlogq, then there exists a PPT algorithm which outputs A∈ℤqn×m statistically close to uniform over ℤqn×m and a full-rank set S⊂Λ⊥A,S≤m2.5 by input 1n. Then, it further gets a good basis T⊂Λ⊥A satisfying T≤S.From what has been discussed above, we get the smallerm the better for the size of signature and secret key under the same n. Hence, we design a new scheme using Fiat–Shamir signature framework without trapdoor (basis).


## 3.2. Filtering Technology

Since the existing lattice-based linearly homomorphic signature schemes are based on the hash-and-sign signature framework in which they use preimage sampling function implemented by Gaussian sampling, the schemes cannot resist side-channel attacks. Hence, we unitize uniform sampling of Fiat–Shamir framework to generate signature.The idea of filtering can be traced back to [10, 19], and it is formally provided in [20] to design a blind signature scheme. Here, we rewrite this lemma according to our construction.Lemma 1.
For arbitrarya∈x∈ℤk:x∞≤β and random b⟵x∈ℤk:x∞≤γ,k=Ωn, if γ≥ϕkβ with ϕ∈ℕ+, then we have Pra−b∞≤γ−β>1/e1/ϕ−o1.Then, the repeat time of our scheme can be computed bye1/ϕ. Intuitively, bigger ϕ size is better. However, this value has influence on the size of a−b∞ directly; thus, it leads to increased communication costs. Hence, we can assign this value according to different efficiency requirements, which is a nice advantage in practice. According to [20], the authors provide the condition ϕ=4 is the best; then, the repeat time is no more than 2, which is also hold for our scheme.In our scheme, the parametersγ,β satisfy γ,β<q. In addition, to facilitate comparisons with schemes [15, 16], we use a−b∞≤q to compute signature size instead of γ−β (see Table 1).Table 1
Comparison.
Public key sizeSignature sizeDimensionResist side-channel attacks[15]m′n+m′nlogq2m′+2m′logq+nm′≥5nlogq×[16]m′nlogqm′logq+nm′≥5nlogq×Oursmnlogq2mlogq+nm≥nlogq√


## 4. Preliminaries

### 4.1. Notions

We denoteℛ=ℤ. The elements in ℛ (vector or matrix) are marked in bold, y is l2 norm, and y∞ is l∞ norm. y⟵Dy means that y is chosen according to some distribution Dy (uniform or Gaussian) at random. If y⟵Dγ, it means that y∞≤γ using uniform sampling. Using Gaussian sampling, we denote y⟵Dσ, where σ is the standard deviation.


### 4.2. Definitions of Linearly Homomorphic Signature

Definition 2.
Given a fixed ringℛ, a linearly homomorphic signature over it contains a tuple of probabilistic polynomial-time algorithms Setup,Sign,Verify,Combine and the detailed descriptions can be seen as follows:(1)
Setup (n, params). It is a probabilistic algorithm that outputs pk,sk by inputting a security parameter n and other public parameters params.(2)
Signμ,sk,τ. It is a probabilistic algorithm that outputs a valid signature σ by inputting secret key sk, a basis vector μ of message set ℳμ∈ℳ⊂F2n, and a tag (or an identifier id) τ∈0,1∗ of message ℳ.(3)
Verifyμ,pk,σ,τ. It is a deterministic algorithm that outputs a bit b by inputting the tuple μ,pk,σ,τ. If σ is a valid signature of μ, the algorithm outputs b=1 (accept); otherwise, b=0 (reject).(4)
Combinepk,τ,ai,μi,σii=1l,L. This algorithm outputs a valid combined signature σ′ of μ′=∑i=1laiμimod2, where ai∈0,1,l≤L. The parameter L is the maximum circuit depth.
In general, the security properties of a linearly homomorphic signature scheme contain correctness, unforgeability, and privacy. We will give the specific contents for them as follows:(1)
Correctness: the outputs from above algorithms Sign and Combine can be accepted by the Verify algorithm.(2)
Unforgeability: we will show a game between challenger C and a polynomial-time adversary A.(1)
Setup: the challenger C runs algorithm Setupn, params to get pk, sk and gives pk to the adversary A.(2)
Signqueries: the adversary A makes adaptive signature queries on k-dimensional subspaces Ui of message space ℳ, and he chooses a basis vectors μi1,…,μik for Ui. For each subspaces Ui, the challenger C chooses τi from 0,1n at random and gives τi and j signatures σij⟵Signsk,τi,μij to the adversary A, where j=1,2,…,k.(3)
Output: the adversary A outputs a tag τ∗, a nonzero message U∗, and a signature σ∗.
The adversary wins the game when his outputs satisfy the algorithm(2)VerifyU∗,pk,σ∗,τ∗=1,and this algorithm satisfies the following one of two conditions:(1)
Type 1.τ∗≠τi for all i.(2)
Type 2.τ∗=τi but U∗∉Ui.Definition 3.
A linearly homomorphic signature schemeSetup,Sign,Verify,Combine is unforgeability if the probability advantage of adversary winning above game is negligible with security parameter n. That is,(3)PrVerifyU∗,pk,σ∗,τ∗=1τ∗≠τi≤εn,orPrVerifyU∗,pk,σ∗,τ∗=1τ∗=τi,U∗∉Ui≤εn.(3)
Privacy: a game between challenger C and a polynomial-time adversary A is shown as follows:(1)
Setup: the challenger C runs algorithm Setup (n, params) to get pk, sk and gives pk to the adversary A.(2)
Challenge: the adversary A chooses two linear message subspaces U0 and U1 represented as vectors μ1b,…,μkb for b=0,1. In addition, he selects functions f1,…,fs, which satisfy fiμ10,…,μk0=fiμ11,…,μk1, where i=1,2,…,s.(3)
Response: the challenger C chooses a random bit b∈0,1, a tag τ∈0,1n, and signs the vector space Ub. Then, the challenger uses the combine algorithm to generate signatures σi for fiμ1b,…,μkb and sends σi to A.(4)
Outputs: A outputs a guess bit b′. If b′=b holds, the adversary A succeeds in the game.Definition 4.
A linearly homomorphic signature schemeSetup, Sign, Verify, Combine is privacy if the probability advantage of adversary winning above game is negligible with security parameter n. That is, Prb′=b−1/2≤εn.


## 4.1. Notions

We denoteℛ=ℤ. The elements in ℛ (vector or matrix) are marked in bold, y is l2 norm, and y∞ is l∞ norm. y⟵Dy means that y is chosen according to some distribution Dy (uniform or Gaussian) at random. If y⟵Dγ, it means that y∞≤γ using uniform sampling. Using Gaussian sampling, we denote y⟵Dσ, where σ is the standard deviation.


## 4.2. Definitions of Linearly Homomorphic Signature

Definition 2.
Given a fixed ringℛ, a linearly homomorphic signature over it contains a tuple of probabilistic polynomial-time algorithms Setup,Sign,Verify,Combine and the detailed descriptions can be seen as follows:(1)
Setup (n, params). It is a probabilistic algorithm that outputs pk,sk by inputting a security parameter n and other public parameters params.(2)
Signμ,sk,τ. It is a probabilistic algorithm that outputs a valid signature σ by inputting secret key sk, a basis vector μ of message set ℳμ∈ℳ⊂F2n, and a tag (or an identifier id) τ∈0,1∗ of message ℳ.(3)
Verifyμ,pk,σ,τ. It is a deterministic algorithm that outputs a bit b by inputting the tuple μ,pk,σ,τ. If σ is a valid signature of μ, the algorithm outputs b=1 (accept); otherwise, b=0 (reject).(4)
Combinepk,τ,ai,μi,σii=1l,L. This algorithm outputs a valid combined signature σ′ of μ′=∑i=1laiμimod2, where ai∈0,1,l≤L. The parameter L is the maximum circuit depth.
In general, the security properties of a linearly homomorphic signature scheme contain correctness, unforgeability, and privacy. We will give the specific contents for them as follows:(1)
Correctness: the outputs from above algorithms Sign and Combine can be accepted by the Verify algorithm.(2)
Unforgeability: we will show a game between challenger C and a polynomial-time adversary A.(1)
Setup: the challenger C runs algorithm Setupn, params to get pk, sk and gives pk to the adversary A.(2)
Signqueries: the adversary A makes adaptive signature queries on k-dimensional subspaces Ui of message space ℳ, and he chooses a basis vectors μi1,…,μik for Ui. For each subspaces Ui, the challenger C chooses τi from 0,1n at random and gives τi and j signatures σij⟵Signsk,τi,μij to the adversary A, where j=1,2,…,k.(3)
Output: the adversary A outputs a tag τ∗, a nonzero message U∗, and a signature σ∗.
The adversary wins the game when his outputs satisfy the algorithm(2)VerifyU∗,pk,σ∗,τ∗=1,and this algorithm satisfies the following one of two conditions:(1)
Type 1.τ∗≠τi for all i.(2)
Type 2.τ∗=τi but U∗∉Ui.Definition 3.
A linearly homomorphic signature schemeSetup,Sign,Verify,Combine is unforgeability if the probability advantage of adversary winning above game is negligible with security parameter n. That is,(3)PrVerifyU∗,pk,σ∗,τ∗=1τ∗≠τi≤εn,orPrVerifyU∗,pk,σ∗,τ∗=1τ∗=τi,U∗∉Ui≤εn.(3)
Privacy: a game between challenger C and a polynomial-time adversary A is shown as follows:(1)
Setup: the challenger C runs algorithm Setup (n, params) to get pk, sk and gives pk to the adversary A.(2)
Challenge: the adversary A chooses two linear message subspaces U0 and U1 represented as vectors μ1b,…,μkb for b=0,1. In addition, he selects functions f1,…,fs, which satisfy fiμ10,…,μk0=fiμ11,…,μk1, where i=1,2,…,s.(3)
Response: the challenger C chooses a random bit b∈0,1, a tag τ∈0,1n, and signs the vector space Ub. Then, the challenger uses the combine algorithm to generate signatures σi for fiμ1b,…,μkb and sends σi to A.(4)
Outputs: A outputs a guess bit b′. If b′=b holds, the adversary A succeeds in the game.Definition 4.
A linearly homomorphic signature schemeSetup, Sign, Verify, Combine is privacy if the probability advantage of adversary winning above game is negligible with security parameter n. That is, Prb′=b−1/2≤εn.


## 5. Our Lattice-Based Linearly Homomorphic Signature

Setup. A⟵ℤqn×m and T=ASmodq, where the public key is T,A and secret key is S. We denote the hash function as H:0,1∗⟶ℤqm and another hash function hαμ=α,μmodq. Obviously, this function satisfies a property ∑i=1maihαμi=hα∑i=1maiμi,ai∈ℤ. Especially, we assume ai∈0,1 in our scheme as below.Sign: we suppose the massage satisfies μ∈ℤ2m and choose a basis of it, that is, μ1,…,μm (for the sake of design, we have assumed that it is a full-rank space). In addition, the used linear function is fμ=∑j=1majμj. Then, signer does the following steps:(1)
He choosesyi⟵RDγmγ<q and computes m vectors αi=HAyimodq,τ, where τ∈0,1m is a tag of massage basis vector μj1≤j≤m.(2)
He computeshαiμj=hij=αi,μjmodq. Then, fixing the parameter j for any message μj, he denotes a vector hj=h1j,…,hjj,…,hmjT.(3)
He computeszj=Shj+yj. If zj∞≤γ−β, output the signature zj,hj,τ, or else, go to the first step. Here, yj=yi holds.Verify: the verifier verifies the conditions as follows:(1)
He computesαj=HAzj−Thjmodq,τ.(2)
He computes whether the equationhjj=αj,μjmodq holds or not.(3)
zj∞≤γ−β.Combine: given public key A and an array aj,μj,zj,hj for j=1,…,m. This algorithm outputs signature ∑j=1majzj,∑j=1majhj of message ∑j=1majμj.


## 6. Proof of Security

### 6.1. Correctness

Since correctness refers to two verifications from the outputs ofSign and Combine algorithms, we prove it one by one:(1)
The signature fromSign algorithm is valid. For each j, when the verifier receives the signature zj,hj,τ, he computes(4)αj=HAyjmodq,τ=HAzj−Shjmodq,τ=HAzj−AShjmodq,τ=HAzj−Thjmodq,τ.Then, he computes whether the equationαj,μjmodq=hjj holds or not.(2)
The signature fromCombine algorithm is valid. We let matrix H be a composition of vectors αj1≤j≤m; that is, H=α1,α2,…,αmT. Hence, we have hj=Hμjmodq. Since condition αj=HAyj,τ holds for each j, we only need to verify the linear property of ∑j′=1maj′hjj′ and linear bound of ∑j=1majzj. At first, we consider the following equation:(5)∑j′=1maj′hj′=∑j′=1maj′Hμj′modq=H∑j′=1maj′μj′modq.Thus,∑j′=1maj′hjj′=αj,∑j′=1maj′μj′modq holds because of hjj′=αj,μj′modq when αj=HAzj−Thjmodq,τ holds. Next, we can see that the bound of our signature size is linear obviously. That is,(6)∑j′=1maj′zj′∞≤mzj′∞.Hence, as long as this in equation holds, the signature is accepted.


### 6.2. Unforgeability

Theorem 1.
Our scheme is unforgeability if the lattice problem SIS is hard.Proof.
We suppose that the defined unforgeability game is correctly performed between a challengerC and a polynomial-time adversary A. In addition, qH,h and qsig are the times of random oracle and signature oracle. Specifically, given the public key A,T, A adaptively chooses some m−dimensional subspaces Uin and chooses basis μi1,…,μim for Ui. To return m signatures to A, the challenger makes query to above oracles and outputs σi1,…,σim for the chosen basis.
When above game is finished, the adversaryA outputs a tag τ∗, a nonzero message U∗, and a signature σ∗. Next, we consider two types forgeries, respectively.Type 1.
Ifτ∗≠τi for all i and VerifyU∗,pk,σ∗,τ∗=1 holds, the adversary has ability to solve the SIS problem. Suppose A has gotten zij,hij,j=1,…,m, then he chooses αij∗ randomly and computes hij∗. Hence, he can combine equations as follows:(7)zij=Shij+yij,zij∗=Shij∗+yij.
Thus, he getszij−zij∗=Shij−hij∗ and computes(8)Azij−zij∗=AShij−hij∗AΔz=TΔh.
Notice that ifΔh≠0, the adversary forgeries a signature if and only is he can solve SIS instance. Furthermore, since PrVerifyU∗,pk,σ∗,τ∗=1τ∗≠τi = PrΔh=0αij∗⟵Rℤqm=1/qH,h+1/qsig≤εn, we can see that the probability of success for this type of attack is negligible.Type 2.
If conditionsτ∗=τi and U∗∉Ui hold, the adversary also can solve the SIS problem. In this case, for the same hash value αij, the adversary chooses massage space U∗ and one of its basis μj∗∉Ui. Then, he computes αij,μj∗modq and hj∗. Since αij is a fixed value, the adversary can compute:(9)αj=HAyij,τ=HAzij−Thij,τ=HAzj∗−Thj∗,τ.
Then, he obtains equationAzij−zj∗=Thij−hj∗, which is marked as AΔz=TΔh.
SincePrVerifyU∗,pk,σ∗,τ∗=1τ∗=τi,U∗∉Ui=PrΔz=0zj∗⟵Rℤqm,μj∗∉Ui=1/qsig≤εn, the adversary cannot forgery a valid signature; otherwise, he is able to search a SIS problem solution. In addition, the reason why he does not use hash oracle is that the condition τ∗=τi determines this oracle has the same input.


### 6.3. Privacy

Theorem 2.
Our scheme is privacy.Proof.
According to the definition of privacy game, challengerC and adversary A firstly finish the setup step. Then, A chooses two basis vectors μ1b,…,μmb from message spaces Ub, where b=0,1. At the same time, he selects linear functions fii=1,2,…,sn satisfying fiμ10,…,μm0=fiμ11,…,μm1. Specifically, for a fixed i, the condition ∑j=1majiμj0=∑j=1majiμj1 holds.
When challengerC obtains μ1b,…,μmb, he chooses b and τ∈0,1m randomly. Then, he signs basis vectors under fi and outputs the signature σi computed using the Combine algorithm. And he sends σi to A.
Finally, the adversary outputs a guess bitb′. Next, we will show that it is negligible for him to succeed in this game. That is, Prb′=b−1/2≤ϵn.
In fact, we let two distinguished signatures areσi0=∑j=1majizj0,∑j=1majihj1 of message ∑j=1majiμj0, σi1=∑j=1majizj1,∑j=1majihj1 of message ∑j=1majiμj1, and condition is Con=∑j=1majiμj0=∑j=1majiμj1. Then, we have(10)H∑j=1majiμj0=H∑j=1majiμj1modq∑j=1majihj0=∑j=1majihj1modq,where H=α1,α2,…,αmT. Hence, we get(11)Prσi0Con−Prσi1Con≤εn.
Becauseσi0 and σi1 are indistinguishable under Con for the adversary, we show Prb′=b−1/2≤εn holds.


## 6.1. Correctness

Since correctness refers to two verifications from the outputs ofSign and Combine algorithms, we prove it one by one:(1)
The signature fromSign algorithm is valid. For each j, when the verifier receives the signature zj,hj,τ, he computes(4)αj=HAyjmodq,τ=HAzj−Shjmodq,τ=HAzj−AShjmodq,τ=HAzj−Thjmodq,τ.Then, he computes whether the equationαj,μjmodq=hjj holds or not.(2)
The signature fromCombine algorithm is valid. We let matrix H be a composition of vectors αj1≤j≤m; that is, H=α1,α2,…,αmT. Hence, we have hj=Hμjmodq. Since condition αj=HAyj,τ holds for each j, we only need to verify the linear property of ∑j′=1maj′hjj′ and linear bound of ∑j=1majzj. At first, we consider the following equation:(5)∑j′=1maj′hj′=∑j′=1maj′Hμj′modq=H∑j′=1maj′μj′modq.Thus,∑j′=1maj′hjj′=αj,∑j′=1maj′μj′modq holds because of hjj′=αj,μj′modq when αj=HAzj−Thjmodq,τ holds. Next, we can see that the bound of our signature size is linear obviously. That is,(6)∑j′=1maj′zj′∞≤mzj′∞.Hence, as long as this in equation holds, the signature is accepted.


## 6.2. Unforgeability

Theorem 1.
Our scheme is unforgeability if the lattice problem SIS is hard.Proof.
We suppose that the defined unforgeability game is correctly performed between a challengerC and a polynomial-time adversary A. In addition, qH,h and qsig are the times of random oracle and signature oracle. Specifically, given the public key A,T, A adaptively chooses some m−dimensional subspaces Uin and chooses basis μi1,…,μim for Ui. To return m signatures to A, the challenger makes query to above oracles and outputs σi1,…,σim for the chosen basis.
When above game is finished, the adversaryA outputs a tag τ∗, a nonzero message U∗, and a signature σ∗. Next, we consider two types forgeries, respectively.Type 1.
Ifτ∗≠τi for all i and VerifyU∗,pk,σ∗,τ∗=1 holds, the adversary has ability to solve the SIS problem. Suppose A has gotten zij,hij,j=1,…,m, then he chooses αij∗ randomly and computes hij∗. Hence, he can combine equations as follows:(7)zij=Shij+yij,zij∗=Shij∗+yij.
Thus, he getszij−zij∗=Shij−hij∗ and computes(8)Azij−zij∗=AShij−hij∗AΔz=TΔh.
Notice that ifΔh≠0, the adversary forgeries a signature if and only is he can solve SIS instance. Furthermore, since PrVerifyU∗,pk,σ∗,τ∗=1τ∗≠τi = PrΔh=0αij∗⟵Rℤqm=1/qH,h+1/qsig≤εn, we can see that the probability of success for this type of attack is negligible.Type 2.
If conditionsτ∗=τi and U∗∉Ui hold, the adversary also can solve the SIS problem. In this case, for the same hash value αij, the adversary chooses massage space U∗ and one of its basis μj∗∉Ui. Then, he computes αij,μj∗modq and hj∗. Since αij is a fixed value, the adversary can compute:(9)αj=HAyij,τ=HAzij−Thij,τ=HAzj∗−Thj∗,τ.
Then, he obtains equationAzij−zj∗=Thij−hj∗, which is marked as AΔz=TΔh.
SincePrVerifyU∗,pk,σ∗,τ∗=1τ∗=τi,U∗∉Ui=PrΔz=0zj∗⟵Rℤqm,μj∗∉Ui=1/qsig≤εn, the adversary cannot forgery a valid signature; otherwise, he is able to search a SIS problem solution. In addition, the reason why he does not use hash oracle is that the condition τ∗=τi determines this oracle has the same input.


## 6.3. Privacy

Theorem 2.
Our scheme is privacy.Proof.
According to the definition of privacy game, challengerC and adversary A firstly finish the setup step. Then, A chooses two basis vectors μ1b,…,μmb from message spaces Ub, where b=0,1. At the same time, he selects linear functions fii=1,2,…,sn satisfying fiμ10,…,μm0=fiμ11,…,μm1. Specifically, for a fixed i, the condition ∑j=1majiμj0=∑j=1majiμj1 holds.
When challengerC obtains μ1b,…,μmb, he chooses b and τ∈0,1m randomly. Then, he signs basis vectors under fi and outputs the signature σi computed using the Combine algorithm. And he sends σi to A.
Finally, the adversary outputs a guess bitb′. Next, we will show that it is negligible for him to succeed in this game. That is, Prb′=b−1/2≤ϵn.
In fact, we let two distinguished signatures areσi0=∑j=1majizj0,∑j=1majihj1 of message ∑j=1majiμj0, σi1=∑j=1majizj1,∑j=1majihj1 of message ∑j=1majiμj1, and condition is Con=∑j=1majiμj0=∑j=1majiμj1. Then, we have(10)H∑j=1majiμj0=H∑j=1majiμj1modq∑j=1majihj0=∑j=1majihj1modq,where H=α1,α2,…,αmT. Hence, we get(11)Prσi0Con−Prσi1Con≤εn.
Becauseσi0 and σi1 are indistinguishable under Con for the adversary, we show Prb′=b−1/2≤εn holds.


## 7. Efficiency Comparisons

In schemes of hash-and-sign type [15, 16], the signer uses trapdoor basis to compute preimage sampling function to create signature σ. However, the lattice dimension m must satisfy m≥5nlogq to get a trapdoor basis (see [17, 18]) and a larger m will result in a larger size of public key and signature.Our design using the Fiat–Shamir signature framework without trapdoor has smaller public key and signature sizes mainly becausem≥nlogq is enough. Then, compared to public key size m′nlogq≈5n2logq2 in [16], our result mnlogq≈n2logq2 is smaller than theirs. In addition, signature size of our scheme 2mlogq+n≈2nlogq2+n is also smaller than m′logq+n≈5nlogq2+n in [16].Furthermore, preimage sampling function utilizes Gaussian distribution which cannot resist partial side-channel attacks, and we use uniform distribution of aborting technology to resist such attacks effectively. The detailed comparisons can be seen in Table1.


## 8. Conclusion and Further Work

### 8.1. Conclusion

In this paper, we provide a new lattice-based linearly homomorphic signature scheme overF2 based on the SIS problem. Since we use Fiat–Shamir signature framework instead of hash-and-sign signature framework to design this signature scheme, we do not need to construct a trapdoor basis, and then the whole design is simpler than the existing schemes. At the same time, without the trapdoor basis, our scheme has the smallest public key size n2logq2 and signature size 2nlogq2+n in the existing schemes because of parameter m satisfying m≈nlogq rather than m≈5nlogq. In addition, under the Fiat–Shamir framework, the use of filtering technology with uniform sampling can resist side-channel attacks.


### 8.2. Further Work

Decreasing interaction and storage costs is the main work of our future research. In fact, new compression skill and decreasing parametersm and n must be improved efficiency. Since our scheme can be designed on R-SIS directly, we no longer give a special scheme. That is, if each element chosen forms the ring ℛ=ℤx/fx or ℛq=ℤqx/fx, where fx=xn+1, n is power of 2, and q is prime, then the parameter m only needs to satisfy m≈logq, rather than m≈nlogq for SIS. Hence, it can improve the efficiency.Specifically, we focus on [9], where it also uses filtering technology (uniform distribution), and special compression methods are used. Meanwhile, module lattice form brings an advantage to parameters m and n, which can be the 1/4 of existing set. In addition, this form can be transformed into lattice hard problem over ring (R-SIS) and general problem (SIS) by setting relative parameters.


## 8.1. Conclusion

In this paper, we provide a new lattice-based linearly homomorphic signature scheme overF2 based on the SIS problem. Since we use Fiat–Shamir signature framework instead of hash-and-sign signature framework to design this signature scheme, we do not need to construct a trapdoor basis, and then the whole design is simpler than the existing schemes. At the same time, without the trapdoor basis, our scheme has the smallest public key size n2logq2 and signature size 2nlogq2+n in the existing schemes because of parameter m satisfying m≈nlogq rather than m≈5nlogq. In addition, under the Fiat–Shamir framework, the use of filtering technology with uniform sampling can resist side-channel attacks.


## 8.2. Further Work

Decreasing interaction and storage costs is the main work of our future research. In fact, new compression skill and decreasing parametersm and n must be improved efficiency. Since our scheme can be designed on R-SIS directly, we no longer give a special scheme. That is, if each element chosen forms the ring ℛ=ℤx/fx or ℛq=ℤqx/fx, where fx=xn+1, n is power of 2, and q is prime, then the parameter m only needs to satisfy m≈logq, rather than m≈nlogq for SIS. Hence, it can improve the efficiency.Specifically, we focus on [9], where it also uses filtering technology (uniform distribution), and special compression methods are used. Meanwhile, module lattice form brings an advantage to parameters m and n, which can be the 1/4 of existing set. In addition, this form can be transformed into lattice hard problem over ring (R-SIS) and general problem (SIS) by setting relative parameters.



---

*Source: 8857815-2020-10-29.xml*