# An Efficient Homomorphic Aggregate Signature Scheme Based on Lattice

Authors: Zhengjun Jing
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Homomorphic aggregate signature (HAS) is a linearly homomorphic signature (LHS) for multiple users, which can be applied for a variety of purposes, such as multi-source network coding and sensor data aggregation. In order to design an efficient postquantum secure HAS scheme, we borrow the idea of the lattice-based LHS scheme over binary field in the single-user case, and develop it into a new lattice-based HAS scheme in this paper. The security of the proposed scheme is proved by showing a reduction to the single-user case and the signature length remains invariant. Compared with the existing lattice-based homomorphic aggregate signature scheme, our new scheme enjoys shorter signature length and high efficiency.


---

## Body

## 1. Introduction

The homomorphic signature, proposed originally by Johnson et al. [1], is an important cryptographic primitive commonly used to secure computation. In a linear homomorphic signature scheme, a user generates a set of signatures on the corresponding messages in an information subspace. When the collection of messages is operated by a linear function which generates a new message belonging to the same information subspace, any other user, who does not know the signing private key, can produce a valid signature on this result of the linear function.The linear homomorphic signature has been the subject of many researches in terms of its definitions, security model, and privacy property. The homomorphic property of signature scheme, proposed by Boneh et al. in [2], was viewed as signing a subspace and instantiated based on the bilinear maps over large prime fields in the random model. Later on, Gennaro et al. [3] showed the efficient homomorphic signature based on RSA over integers in the random model too. In the standard model, Freeman [4] defined a generic framework of linearly homomorphic signatures, in which three ordinary signature schemes having certain properties could be converted into linearly homomorphic signature schemes. More importantly, the framework provides enhanced security in the standard model under the computational Diffie-Hellman assumption, the q-strong Diffie-Hellman assumption, and the RSA assumption, respectively. Recently, the breakthrough has been achieved by Bohen and Freeman [5, 6]. Their works give an example of linearly homomorphic signature built using the lattice assumption over binary field [5], while they also show that a homomorphic signature supporting authenticated polynomial functions on signed data can be constructed by using “ideal lattice” in the random model [6]. Follow-up work by Wang et al. [7] implements an efficient lattice-based linearly homomorphic signature scheme using an additive homomorphic hash function over F
2, in which both the public key size and signature length are shorter. In addition, for the privacy of homomorphic signature, a notion of the so-called “weakly context hiding” is defined in [5], which requires the derived signature not to leak any information about the original messages provided that the original signatures are kept private. For attaining the stronger privacy notion, Ahn et al. [8] defines the concept of “strong context hiding,” which requires the infeasibility of linking the derived signature to the signatures it was derived from even in the condition that the original signatures are public. After that, Attrapadung et al. [9, 10] proposed a new definition of privacy, called “adaptively context hiding,” which requires context hiding on adversarially chosen signature with private key exposure. In other words, if a linearly homomorphic signature scheme guarantees unlinkability even when the original signatures are produced by illegitimate signing algorithm, this scheme holds the privacy of adaptively context hiding.The linearly homomorphic signature can be used for many purposes, such as authenticating packets in network coding protocols and computing statistics on authenticated data. In particular for the secure network coding, it is the most effective cryptographic tool to prevent “pollution attack.” Most of the above-mentioned linearly homomorphic signature schemes can be applied to prevent the pollution attack by the malicious node.Here we want to point out that all of the above-mentioned authentication schemes could only be applicable to the case of single user or single source network coding system. Usually, in real world some applications involve many signatures on messages produced by many different users or sources. For example, in the multi-source network coding system [11, 12], packets from multiple different sources are needed to be linearly combined so as to exploit the benefits provided by network coding. For such multi-source network coding in an adversary situation, Agrawal et al. [13] constructed a complex scheme against pollution attack in the general case, in which a merged algorithm is used to generate several public keys and signatures in the mediate nodes. In order to find more efficient and practical solutions, the follow-up works [14–16] all considered the specific case where only the packets (or messages) that have the same identifier are combined together. Czap and Vajda’s work [14] is obtained from the pairing-based homomorphic signature scheme proposed in [2], while Yan et al. [15] proposed an elegant homomorphic signature scheme based on the bilinear pairings and obtained a shorter homomorphic signature by using a novel homomorphic hash function. Recently, Zhang et al. [16] introduced aggregation property into homomorphic signature for multiple users case and formed a homomorphic aggregation signature scheme (HAS) by using preimage sampling function and Bonsai tree technique over random lattice.However, these authentication schemes designed for multiuser case (or multi-source case) all have their own flaws. As is shown from the above, the unforgeability of both [14, 15] is based on CDH (computational Diffie-Hellman problem) in the bilinear group. As a result, these schemes involve a large number of point multiplication on elliptic curve. If a homomorphic signature scheme for multi-source can be used in network coding, it is necessary that this scheme should support the linearly homomorphic operations over binary field, just like that in [5, 7] for the single source. In addition, we need to emphasize that their security based on classical number theoretic problem is threatened by the power of quantum computers. As for the HAS proposed in [16], although its security is based on the hard assumption over lattice which is considered infeasible even under the quantum computer, the length of the aggregate signature is two times that of each original signature. We know the larger the length of the signature, the higher overhead of verification. Hence, it is significant to construct an efficient postquantum linearly homomorphic signature scheme for the multiple users case.In this paper, we propose a short latticed-based linearly homomorphic aggregate signature scheme over binary field after optimizing our initial scheme in the multiple users case. Our scheme is an extension of the lattice-based linearly homomorphic signature scheme overF
2 in [7]. Each user, in our scheme, signs the original messages using their own private key, and the aggregate signature on aggregate message which is the combination of original messages from different users can be generated just by using the combination of original signatures without knowing any user’s private key. In this way, these valid aggregate messages can be authenticated using a common public key formed by all the users’ public keys. We point out that the common public key is independent of the signed message space, which means our signature scheme still supports signature on multiple message subspaces (or files) without updating the public keys. Compared to the HAS in [16], the length of aggregate signature in our scheme is as short as that of original signatures, which is only half the length of aggregate signature proposed in [16]. More importantly, this length of aggregate signature is independent of the number of the signing users. In addition, we also prove that the security of our solution can be reduced to that of the latticed-based LHS scheme in the single user case in [7].The rest of this paper is organized as follows. In Section2, we introduce the background about lattice and briefly overview the model of linearly homomorphic signature based on lattice over binary field in [7]. Our HAS scheme is described in detail in Section 3, including the general model definition, the initial scheme, and optimization. Section 4 proves the security of the presented scheme, and Section 5 is the analysis of the efficiency. Finally, in Section 6, we summarize this paper.


## 2. Preliminaries

### 2.1. Notation

We useZ and R to denote the set of integers and the set of real numbers, respectively. For any integer q, let Z
q denote the ring of integer mod q. By convention, we use bold lower case letters for vectors (e.g., a) and bold upper case letters for matrix (e.g., A). The member of vector is denoted by lowercase (e.g., a
i), while the ith column of a matrix is denoted by a
i. For a positive integer k, [
k
] denotes {
1
,
…
,
k
}. In this paper, let A
- denote the Gram-Schmidt orthogonalization of matrix A. The Euclidean norm of a vector is considered as its length (e.g., ‖
a
‖), and the length of a matrix is the norm of its longest column vector (e.g., ‖
A
‖
=
max
⁡
‖
a
i
‖). In addition, the function negl
(
n
) is negligible in n if it is smaller than all polynomial fractions for larger n.


### 2.2. Random Lattice and Hard Assumption

LetB
=
{
b
1
,
…
,
b
n
}
⊂
R
m be a set of n linearly independent vectors; then, the lattice Λ generated by the basis B is Λ
=
{
B
·
x
:
x
∈
Z
n
}
⊂
R
m. In the cryptography based on lattice, we always focus on the integer lattice where the lattice points are contained in Z
m. For some integer q
≥
2, m
,
n, let A
∈
Z
q
n
×
m be a random matrix. Then, the two kinds of full rank random lattice defined by A are used in this paper. Their specific definitions are as follows:
(1)
Λ
q
⊥
(
A
)
=
{
e
∈
Z
q
m
:
A
·
e
=
0
mod
⁡
q
}
,
Λ
q
u
(
A
)
=
{
e
∈
Z
q
m
:
A
·
e
=
u
mod
⁡
q
}
.In fact, the latticeΛ
q
u
(
A
) is a coset of Λ
q
⊥
(
A
). Namely, Λ
q
u
(
A
)
=
Λ
q
⊥
(
A
)
+
t
, where A
·
t
=
u
mod
⁡
q. In addition, it is noted that the variable n is the security parameter as the prior works defined, and the other variables are the functions of n. Typically, m is O
(
n
log
⁡
n
) and the modulus q is some small polynomial, for example, O
(
n
3
).Hard Assumption. The security of lattice-based LHS schemes [5, 7] is all based on the hardness assumption of the short integer solution (SIS) problem over the lattice Λ
q
⊥
(
A
). The definition of SIS problem is as follows.Definition 1.
Given positive integersq
,
m
,
n and a real δ, for a random matrix A
∈
Z
q
n
×
m, the goal of SIS (
q
,
m
,
δ
) is to find a nonzero vector v
∈
Λ
q
⊥
(
A
) such that ‖
v
‖
≤
δ.In [17], it has been proven that solving SIS problem on the average is as hard as approximating certain lattice problems in the worst case, such as SIVP problem (shortest independent vectors problem).


### 2.3. Gaussian Distribution on Lattices

Gaussian distribution technique is widely used in the analysis of the results in the area of lattice-based cryptography. Here, we briefly review some important conclusion from previous works [5, 15, 16], which will be used to analyze our scheme.Discrete Gaussian Distribution. For the parameter σ
>
0 and any vector c
∈
R
m, the probability density function of Gaussian distribution D
σ
,
c on R
m centered at c is defined as ρ
σ
,
c
=
exp
⁡
(
-
π
‖
x
-
c
‖
2
/
σ
2
). For the m-dimensional lattice Λ, the discrete Gaussian distribution over Λ is a conditional probability distribution with center c and parameter σ, which is defined as D
Λ
,
σ
,
c
(
x
)
=
ρ
σ
,
c
(
x
)
/
∑
v
∈
Λ
ρ
σ
,
c
(
v
), where x
∈
Λ. Micciancio and Regev [17] introduced the notion of “smoothing parameter” of lattice and showed that if the parameter σ is greater than the smoothing parameter, then the discrete distribution D
Λ
,
σ
,
c is statically close to the continuous distribution D
σ
,
c. In particular, Ρ
x
~
D
Λ
,
σ
,
c
{
‖
x
-
c
‖
>
σ
m
}
≤
negl
(
n
).Sampling from Discrete Gaussian. Gentry et al. [18] gave a new bound on the smoothing parameter relative to a certain lattice quality and showed algorithm for sampling from discrete Gaussian distribution which was commonly used in signature scheme [5, 7, 16, 19]. In addition, Boneh and Freeman in [5] showed that the sum of independent discrete Gaussian variables still remains discrete Gaussian distribution. Some relevant facts are listed as follows.Lemma 2 (see [18, Theorem 4.1]).
Given a basisT of any dimension lattice Λ, a parameter σ
>
‖
T
-
‖
·
ω
(
log
⁡
n
), and a center c
∈
R
m, there is a PPT (probabilistic polynomial-time) algorithm that outputs a sample from a distribution that is statically close to D
Λ
,
σ
,
c.Lemma 3 (see [18, Theorem 5.6]).
Letn be a positive integer, q
≥
2, and m
>
2
n
log
⁡
(
q
). For a matrix A
∈
Z
q
n
×
m, let T be a basis of Λ
q
⊥
(
A
) and σ
>
‖
T
-
‖
·
ω
(
log
⁡
n
); then, one has the following.(1)
For anyt
∈
Z
n, there is a probability polynomial-time algorithmSamplePre
(
A
,
T
,
σ
,
t
) that outputs a sample t
′ from a distribution that is statically close to D
Λ
q
t
(
A
)
,
σ
.. In particular, the vector t
′ satisfies ‖
t
′
‖
≤
σ
m with overwhelming probability.
(2)
For anyt
~
D
Z
m
,
σ
,
0, the distribution of syndrome u
=
A
·
t
mod
⁡
q is statically close to uniform over Z
q
n.Lemma 4 (see [5, Theorem 9]).
For a latticeΛ, the parameter σ
∈
R, and t
i
∈
[
k
]
∈
Z
m, let x
i
∈
[
k
] be mutually independent random variables sampled from a discrete Gaussian distribution D
t
i
+
Λ
,
σ
,
0. Let c
=
(
c
1
,
…
,
c
k
)
∈
Z
k, g
=
gcd
(
c
1
,
…
,
c
k
), and t
=
∑
i
=
1
k
c
i
·
t
i. Suppose that σ
>
‖
c
‖
·
η
ε
(
Λ
) where η
ε
(
Λ
) is the smooth parameter of lattice Λ for some negligible number ε; then, z
=
∑
i
=
1
k
c
i
·
x
i is statically close to D
t
+
g
Λ
,
‖
c
‖
·
σ
,
0.


### 2.4. Short Basis of Lattice

In cryptography based on lattice, a short basis of a lattice can be considered a trapdoor basis which was used as private key in cryptographic application. For the latticeΛ
q
⊥
(
A
), its short basis T can be generated using theTrapGen algorithm proposed by Alwen and Peikert in [20]. In addition, the common public key used to sign in our initial HAS scheme consists of the public keys of multiple users in the form of A
=
A
1
‖
⋯
‖
A
l, where l is the number of the signing users. To derive a new short basis of the high-dimension lattice Λ
⊥
(
A
)
⊂
Z
q
l
m, some lemmas about the basis delegation mechanism proposed by Cash et al. in [21] will be employed. All of them are listed below.Lemma 5 (see [19, Theorem 3.2]).
Forq
>
2 and m
>
5
n
log
⁡
q, there is a probabilistic polynomial-time algorithm T
r
a
p
G
e
n
(
1
n
) that outputs a matrix A
∈
Z
q
n
×
m statically close to a uniform matrix in Z
q
n
×
m and a basis T
∈
Z
q
n
×
m of the lattice Λ
q
⊥
(
A
) such that ‖
T
-
‖
≤
O
(
n
log
⁡
q
) with overwhelming probability.Lemma 6.
For an arbitrary basisT
∈
Z
q
m
×
m of the lattice Λ
⊥
(
A
) about a random matrix A
∈
Z
q
n
×
m and the parameter σ
>
‖
T
-
‖
·
ω
(
log
⁡
n
); then,(1)
(see [20, Lemma 3.2]) for any matrix A
′
∈
Z
q
n
×
m
′, there is a deterministic polynomial-time algorithm E
x
t
B
a
s
i
s
(
T
,
B
=
A
∥
A
′
) that outputs a basis T
′ of the lattice Λ
q
⊥
(
B
)
⊂
Z
(
m
+
m
′
)
×
(
m
+
m
′
) such that ‖
T
-
′
‖
=
‖
T
-
‖;
(2)
(see [20, Lemma 3.3]) there is a probabilistic polynomial-time algorithm R
a
n
d
B
a
s
i
s
(
T
,
σ
) that outputs another basis T
′ of the lattice Λ
q
⊥
(
A
), which is statically independent of the original basis T and is still short.


### 2.5. Linearly Homomorphic Signature Scheme (LHS) Based on Lattice overF
2

Our homomorphic aggregate signature scheme is an extension of an efficient linearly homomorphic signature scheme proposed by Wang et al. in the single user case [7], which makes improvement on the scheme of Boneh and Freeman [5]. At present, lattice-based LHS over F
2 is called L-limited, which means we can only guarantee successful verification for combination of a finite number of valid signatures where L is the maximal number. Here, we briefly describe theLHS1 as follows, and the details about lattice-based LHS over binary field can be referred to [5, 7].Homomorphic Hash
h
α
Based-on Lattice. Lyubashevsky and Micciancio in [22] defined a secure hash function based on the approximate SVP (short vector problem) of lattice, which was used in [5]. This hash function family maps Z
q
m to Z
q in the way of inner product and holds homomorphic property. Specifically, given that vectors α, v
1, v
2 belonged to Z
q
m with vector α fixed, the hash function h
α
=
〈
α
,
v
i
〉 (i is 1 or 2) satisfies linearly homomorphic conditions. Namely, it holds h
α
(
v
1
+
v
2
)
=
h
α
(
v
1
)
+
h
α
(
v
2
) and h
α
〈
c
·
v
i
〉
=
c
·
h
α
(
v
i
) where c
∈
Z
q.Wang’s Signature Scheme. The Wang’s lattice-based LHS scheme [7], which will be calledLHS1, consists of four polynomial-time algorithms proposed as follows.WSetup. Let the parameters (
q
,
m
,
n
,
σ
) be the same as those in Lemma 5. Given that H be a collision-resistant hash function which maps (
0,1
)
* to Z
q
m and letting the coefficients a of the linearly function belong to F
2, the signer runs T
r
a
p
G
e
n
(
1
n
) algorithm to produce the pair of public key and private key {
T
∈
Z
q
m
×
m
,
A
∈
Z
q
n
×
m
}.WSign. To sign a subspace V
id of the message space {
0,1
}
m, where id
∈
{
0,1
}
n is a identifier of V, given the fact that the set of vectors {
v
1
,
…
,
v
k
} is the basis of V, the signer does as follows to sign a basis vector v
j
∈
[
k
].(1)
Computen vectors α
i
∈
[
n
]
=
H
(
id
∥
i
)
⊂
Z
q
m.
(2)
Compute the hash value ofv
j through homomorphic hash function h
α, and denote it as a column vector h
j
=
(
v
i
∈
[
n
]
)
T
∈
Z
q
n, where the element is v
i
=
h
α
(
v
j
)
mod
⁡
q.
(3)
Use theS
a
m
p
l
e
P
r
e
(
A
,
T
,
σ
,
h
j
) algorithm in Lemma 3 to attain a signature s
j of the hash value h
j, and the linearly homomorphic signature on v
j can be denoted by (
id
,
s
j
).WVerify. Let L be the maximal number of signatures that can be combined. To verify the linearly homomorphic signature of the message v
j, the verifier firstly computes the hash value h
j of v
j just as steps (
1
) and (
2
) inSign do and then outputs 1 (accept) if and only if the conditions hold, such as A
·
s
j
=
h
j
mod
⁡
q and ‖
e
j
‖
≤
L
σ
m, or outputs 0 (reject).WCombine. Given l pairs of (
a
i
,
s
i
,
v
i
), where l
≤
L, it outputs a vector ∑
i
=
1
l
a
i
·
s
i
(
mod
⁡
q
) as the signature of the message ∑
i
=
1
l
a
i
·
v
i
(
mod
⁡
q
).For the linearly homomorphic signature in adversary situation, there is two types of forgeability. For example, an output(
id
*
,
v
*
,
s
*
) produced by an adversary can be accepted byVerify algorithm where either (1) id
*
≠
id or (2) id
*
=
id, but v
*
∉
V
id. Theorem 2 in [7] shows thatLHS1 is unforgeable against these types of adversaries in oracle model.Lemma 7 (see [7, Theorem 2]).
If an stateful adversary without knowing the signing private can output any kind of the above forgery with the probabilityε, the SIS problem can be solved by a challenger with a probability 2
ε.


## 2.1. Notation

We useZ and R to denote the set of integers and the set of real numbers, respectively. For any integer q, let Z
q denote the ring of integer mod q. By convention, we use bold lower case letters for vectors (e.g., a) and bold upper case letters for matrix (e.g., A). The member of vector is denoted by lowercase (e.g., a
i), while the ith column of a matrix is denoted by a
i. For a positive integer k, [
k
] denotes {
1
,
…
,
k
}. In this paper, let A
- denote the Gram-Schmidt orthogonalization of matrix A. The Euclidean norm of a vector is considered as its length (e.g., ‖
a
‖), and the length of a matrix is the norm of its longest column vector (e.g., ‖
A
‖
=
max
⁡
‖
a
i
‖). In addition, the function negl
(
n
) is negligible in n if it is smaller than all polynomial fractions for larger n.


## 2.2. Random Lattice and Hard Assumption

LetB
=
{
b
1
,
…
,
b
n
}
⊂
R
m be a set of n linearly independent vectors; then, the lattice Λ generated by the basis B is Λ
=
{
B
·
x
:
x
∈
Z
n
}
⊂
R
m. In the cryptography based on lattice, we always focus on the integer lattice where the lattice points are contained in Z
m. For some integer q
≥
2, m
,
n, let A
∈
Z
q
n
×
m be a random matrix. Then, the two kinds of full rank random lattice defined by A are used in this paper. Their specific definitions are as follows:
(1)
Λ
q
⊥
(
A
)
=
{
e
∈
Z
q
m
:
A
·
e
=
0
mod
⁡
q
}
,
Λ
q
u
(
A
)
=
{
e
∈
Z
q
m
:
A
·
e
=
u
mod
⁡
q
}
.In fact, the latticeΛ
q
u
(
A
) is a coset of Λ
q
⊥
(
A
). Namely, Λ
q
u
(
A
)
=
Λ
q
⊥
(
A
)
+
t
, where A
·
t
=
u
mod
⁡
q. In addition, it is noted that the variable n is the security parameter as the prior works defined, and the other variables are the functions of n. Typically, m is O
(
n
log
⁡
n
) and the modulus q is some small polynomial, for example, O
(
n
3
).Hard Assumption. The security of lattice-based LHS schemes [5, 7] is all based on the hardness assumption of the short integer solution (SIS) problem over the lattice Λ
q
⊥
(
A
). The definition of SIS problem is as follows.Definition 1.
Given positive integersq
,
m
,
n and a real δ, for a random matrix A
∈
Z
q
n
×
m, the goal of SIS (
q
,
m
,
δ
) is to find a nonzero vector v
∈
Λ
q
⊥
(
A
) such that ‖
v
‖
≤
δ.In [17], it has been proven that solving SIS problem on the average is as hard as approximating certain lattice problems in the worst case, such as SIVP problem (shortest independent vectors problem).


## 2.3. Gaussian Distribution on Lattices

Gaussian distribution technique is widely used in the analysis of the results in the area of lattice-based cryptography. Here, we briefly review some important conclusion from previous works [5, 15, 16], which will be used to analyze our scheme.Discrete Gaussian Distribution. For the parameter σ
>
0 and any vector c
∈
R
m, the probability density function of Gaussian distribution D
σ
,
c on R
m centered at c is defined as ρ
σ
,
c
=
exp
⁡
(
-
π
‖
x
-
c
‖
2
/
σ
2
). For the m-dimensional lattice Λ, the discrete Gaussian distribution over Λ is a conditional probability distribution with center c and parameter σ, which is defined as D
Λ
,
σ
,
c
(
x
)
=
ρ
σ
,
c
(
x
)
/
∑
v
∈
Λ
ρ
σ
,
c
(
v
), where x
∈
Λ. Micciancio and Regev [17] introduced the notion of “smoothing parameter” of lattice and showed that if the parameter σ is greater than the smoothing parameter, then the discrete distribution D
Λ
,
σ
,
c is statically close to the continuous distribution D
σ
,
c. In particular, Ρ
x
~
D
Λ
,
σ
,
c
{
‖
x
-
c
‖
>
σ
m
}
≤
negl
(
n
).Sampling from Discrete Gaussian. Gentry et al. [18] gave a new bound on the smoothing parameter relative to a certain lattice quality and showed algorithm for sampling from discrete Gaussian distribution which was commonly used in signature scheme [5, 7, 16, 19]. In addition, Boneh and Freeman in [5] showed that the sum of independent discrete Gaussian variables still remains discrete Gaussian distribution. Some relevant facts are listed as follows.Lemma 2 (see [18, Theorem 4.1]).
Given a basisT of any dimension lattice Λ, a parameter σ
>
‖
T
-
‖
·
ω
(
log
⁡
n
), and a center c
∈
R
m, there is a PPT (probabilistic polynomial-time) algorithm that outputs a sample from a distribution that is statically close to D
Λ
,
σ
,
c.Lemma 3 (see [18, Theorem 5.6]).
Letn be a positive integer, q
≥
2, and m
>
2
n
log
⁡
(
q
). For a matrix A
∈
Z
q
n
×
m, let T be a basis of Λ
q
⊥
(
A
) and σ
>
‖
T
-
‖
·
ω
(
log
⁡
n
); then, one has the following.(1)
For anyt
∈
Z
n, there is a probability polynomial-time algorithmSamplePre
(
A
,
T
,
σ
,
t
) that outputs a sample t
′ from a distribution that is statically close to D
Λ
q
t
(
A
)
,
σ
.. In particular, the vector t
′ satisfies ‖
t
′
‖
≤
σ
m with overwhelming probability.
(2)
For anyt
~
D
Z
m
,
σ
,
0, the distribution of syndrome u
=
A
·
t
mod
⁡
q is statically close to uniform over Z
q
n.Lemma 4 (see [5, Theorem 9]).
For a latticeΛ, the parameter σ
∈
R, and t
i
∈
[
k
]
∈
Z
m, let x
i
∈
[
k
] be mutually independent random variables sampled from a discrete Gaussian distribution D
t
i
+
Λ
,
σ
,
0. Let c
=
(
c
1
,
…
,
c
k
)
∈
Z
k, g
=
gcd
(
c
1
,
…
,
c
k
), and t
=
∑
i
=
1
k
c
i
·
t
i. Suppose that σ
>
‖
c
‖
·
η
ε
(
Λ
) where η
ε
(
Λ
) is the smooth parameter of lattice Λ for some negligible number ε; then, z
=
∑
i
=
1
k
c
i
·
x
i is statically close to D
t
+
g
Λ
,
‖
c
‖
·
σ
,
0.


## 2.4. Short Basis of Lattice

In cryptography based on lattice, a short basis of a lattice can be considered a trapdoor basis which was used as private key in cryptographic application. For the latticeΛ
q
⊥
(
A
), its short basis T can be generated using theTrapGen algorithm proposed by Alwen and Peikert in [20]. In addition, the common public key used to sign in our initial HAS scheme consists of the public keys of multiple users in the form of A
=
A
1
‖
⋯
‖
A
l, where l is the number of the signing users. To derive a new short basis of the high-dimension lattice Λ
⊥
(
A
)
⊂
Z
q
l
m, some lemmas about the basis delegation mechanism proposed by Cash et al. in [21] will be employed. All of them are listed below.Lemma 5 (see [19, Theorem 3.2]).
Forq
>
2 and m
>
5
n
log
⁡
q, there is a probabilistic polynomial-time algorithm T
r
a
p
G
e
n
(
1
n
) that outputs a matrix A
∈
Z
q
n
×
m statically close to a uniform matrix in Z
q
n
×
m and a basis T
∈
Z
q
n
×
m of the lattice Λ
q
⊥
(
A
) such that ‖
T
-
‖
≤
O
(
n
log
⁡
q
) with overwhelming probability.Lemma 6.
For an arbitrary basisT
∈
Z
q
m
×
m of the lattice Λ
⊥
(
A
) about a random matrix A
∈
Z
q
n
×
m and the parameter σ
>
‖
T
-
‖
·
ω
(
log
⁡
n
); then,(1)
(see [20, Lemma 3.2]) for any matrix A
′
∈
Z
q
n
×
m
′, there is a deterministic polynomial-time algorithm E
x
t
B
a
s
i
s
(
T
,
B
=
A
∥
A
′
) that outputs a basis T
′ of the lattice Λ
q
⊥
(
B
)
⊂
Z
(
m
+
m
′
)
×
(
m
+
m
′
) such that ‖
T
-
′
‖
=
‖
T
-
‖;
(2)
(see [20, Lemma 3.3]) there is a probabilistic polynomial-time algorithm R
a
n
d
B
a
s
i
s
(
T
,
σ
) that outputs another basis T
′ of the lattice Λ
q
⊥
(
A
), which is statically independent of the original basis T and is still short.


## 2.5. Linearly Homomorphic Signature Scheme (LHS) Based on Lattice overF
2

Our homomorphic aggregate signature scheme is an extension of an efficient linearly homomorphic signature scheme proposed by Wang et al. in the single user case [7], which makes improvement on the scheme of Boneh and Freeman [5]. At present, lattice-based LHS over F
2 is called L-limited, which means we can only guarantee successful verification for combination of a finite number of valid signatures where L is the maximal number. Here, we briefly describe theLHS1 as follows, and the details about lattice-based LHS over binary field can be referred to [5, 7].Homomorphic Hash
h
α
Based-on Lattice. Lyubashevsky and Micciancio in [22] defined a secure hash function based on the approximate SVP (short vector problem) of lattice, which was used in [5]. This hash function family maps Z
q
m to Z
q in the way of inner product and holds homomorphic property. Specifically, given that vectors α, v
1, v
2 belonged to Z
q
m with vector α fixed, the hash function h
α
=
〈
α
,
v
i
〉 (i is 1 or 2) satisfies linearly homomorphic conditions. Namely, it holds h
α
(
v
1
+
v
2
)
=
h
α
(
v
1
)
+
h
α
(
v
2
) and h
α
〈
c
·
v
i
〉
=
c
·
h
α
(
v
i
) where c
∈
Z
q.Wang’s Signature Scheme. The Wang’s lattice-based LHS scheme [7], which will be calledLHS1, consists of four polynomial-time algorithms proposed as follows.WSetup. Let the parameters (
q
,
m
,
n
,
σ
) be the same as those in Lemma 5. Given that H be a collision-resistant hash function which maps (
0,1
)
* to Z
q
m and letting the coefficients a of the linearly function belong to F
2, the signer runs T
r
a
p
G
e
n
(
1
n
) algorithm to produce the pair of public key and private key {
T
∈
Z
q
m
×
m
,
A
∈
Z
q
n
×
m
}.WSign. To sign a subspace V
id of the message space {
0,1
}
m, where id
∈
{
0,1
}
n is a identifier of V, given the fact that the set of vectors {
v
1
,
…
,
v
k
} is the basis of V, the signer does as follows to sign a basis vector v
j
∈
[
k
].(1)
Computen vectors α
i
∈
[
n
]
=
H
(
id
∥
i
)
⊂
Z
q
m.
(2)
Compute the hash value ofv
j through homomorphic hash function h
α, and denote it as a column vector h
j
=
(
v
i
∈
[
n
]
)
T
∈
Z
q
n, where the element is v
i
=
h
α
(
v
j
)
mod
⁡
q.
(3)
Use theS
a
m
p
l
e
P
r
e
(
A
,
T
,
σ
,
h
j
) algorithm in Lemma 3 to attain a signature s
j of the hash value h
j, and the linearly homomorphic signature on v
j can be denoted by (
id
,
s
j
).WVerify. Let L be the maximal number of signatures that can be combined. To verify the linearly homomorphic signature of the message v
j, the verifier firstly computes the hash value h
j of v
j just as steps (
1
) and (
2
) inSign do and then outputs 1 (accept) if and only if the conditions hold, such as A
·
s
j
=
h
j
mod
⁡
q and ‖
e
j
‖
≤
L
σ
m, or outputs 0 (reject).WCombine. Given l pairs of (
a
i
,
s
i
,
v
i
), where l
≤
L, it outputs a vector ∑
i
=
1
l
a
i
·
s
i
(
mod
⁡
q
) as the signature of the message ∑
i
=
1
l
a
i
·
v
i
(
mod
⁡
q
).For the linearly homomorphic signature in adversary situation, there is two types of forgeability. For example, an output(
id
*
,
v
*
,
s
*
) produced by an adversary can be accepted byVerify algorithm where either (1) id
*
≠
id or (2) id
*
=
id, but v
*
∉
V
id. Theorem 2 in [7] shows thatLHS1 is unforgeable against these types of adversaries in oracle model.Lemma 7 (see [7, Theorem 2]).
If an stateful adversary without knowing the signing private can output any kind of the above forgery with the probabilityε, the SIS problem can be solved by a challenger with a probability 2
ε.


## 3. Homomorphic Aggregate Signature Based on Lattice

For the most general setting of multiuser, Agrawal et al. in [13] have shown that it is difficult to find efficient solutions to homomorphic signature. In this paper, we deal with the specific case, the same one considered in [11–13], where only the messages tagged the same identifier are combined together. In addition, our signature scheme requires that a trusted private key generator (PKG) is available, which makes it possible that all users have their own public-private key pairs.In the HAS, assumingid
∈
{
0,1
}
n is a unique identifier of messages subspace, for a message v
i from the subspace V
id, the signed message is a tuple of (
id
,
v
i
,
s
i
), where s
i is the signature of v
i from the jth user using his (or her) own private key. So, the aggregate message is gained through linearly combination of different messages tagged the same id from distinct users. Now, we present the system model of HAS and give a detailed structure of our signature scheme.


### 3.1. Definition of HAS

The presented system definition of lattice-based HAS is a variant of that of linearly homomorphic signature in [5]. Compared with the model of single-user homomorphic signature [5, 7], theSetup andVerify parts of HAS system need to define some new properties and additional operators, while theSign part does not change. Formally, the definition of HAS is a tuple of polynomial-time algorithms H
A
S
(
S
e
t
u
p
,
S
i
g
n
s
k
i
,
C
o
m
b
i
n
e
,
V
e
r
i
f
y
c
p
k
), which is as follows.S
e
t
u
p
(
1
n
,
L
). This probabilistic algorithm takes as input the security parameter 1
n and the maximum number of users L and outputs the public-private pair (
p
k
i
,
s
k
i
) for each user (
0
<
i
≤
L
) and the common public key p
c
k shared with everyone.S
i
g
n
(
i
d
,
m
i
,
s
k
i
). For the jth user, this probabilistic algorithm takes as input a message m
i of subspace V
id and the private key s
k
j, and outputs the signature s
i on message m
i.C
o
m
b
i
n
e
(
i
d
,
a
,
{
(
m
i
,
s
i
)
}
i
=
1
l
). Given the combination coefficient vector a and l (l
≤
L) pairs of message sharing the same id and the corresponding signature, output the aggregate signature s on the aggregate message ∑
i
=
1
l
a
i
m
i.V
e
r
i
f
y
c
p
k
(
i
d
,
∑
i
=
1
l
a
i
m
i
,
s
). This is a deterministic algorithm. Given an identifier id, the common public key c
p
k, the aggregate message ∑
i
=
1
l
a
i
m
i, and the corresponding signature s, output either 1 (accept) or 0 (reject).In terms of the correctness and security for the homomorphic aggregate signature scheme, it should have not only the characteristics of general linearly homomorphic signature in case of one user, but also some features of its own in multiuser case. On the one hand, assume that each user is honest, the verification should be able to accept the valid signed message from each user, while a forged signed message must be rejected, which is the same as in the case of the single user. On the other hand, given a series of valid signed message(
id
,
m
i
,
s
k
i
), where i
∈
[
l
], a new valid signed message denoted by (
id
,
∑
i
=
1
l
a
i
m
i
,
s
) can be produced without having access to any private key.


### 3.2. Our Scheme

According to the definition of HAS, we show how to extend the homomorphic signature schemeLHS1 described in Section 2.5 to handle multiuser case. Our initial HAS scheme is as follows.S
e
t
u
p
(
1
n
,
L
). Given a security parameter n and the maximum number of users L, the PKG initializes the scheme from four aspects.(1)
Choose parametersparams
=
{
m
,
q
}. For β
=
poly
(
n
) and let q
≥
β
ω
(
log
⁡
n
) and m
>
c
n
log
⁡
(
q
), where c
>
0 is a constant.
(2)
ForL users, T
r
a
p
G
e
n
(
1
n
) algorithm is repeatedly run L times to generate matrix A
i
∈
Z
q
n
×
m and the corresponding trapdoor basis T
i of Λ
q
⊥
(
A
i
), where 0
<
i
≤
L.
(3)
LetH
:
{
0,1
}
*
→
Z
q
L
m be a collision-resistant hash function which is viewed as a random oracle, and let h be a lattice-based homomorphic hash function described in Section 2.5.
(4)
The pair of{
A
i
,
T
i
} is assigned to the corresponding user u
i as the user’s private key and public key, respectively. Let A
0
=
A
1
‖
⋯
‖
A
L
∈
Z
q
n
×
L
m be the common public key and publish it to all the users. Of course, it is required that delivering the private key should be done secretly.S
i
g
n
(
i
d
,
m
i
,
T
i
). For the ith user, given the common signing key A
0, private key T
i, and one of basis vectors of message subspace V
id, for example, m
i
∈
V
id
⊂
Z
2
m where id
∈
{
0,1
}
n, the signature on message m
i is produced as follows.(1)
To obtain the short basis ofΛ
⊥
(
A
0
)
⊂
Z
l
m, the algorithm E
x
t
e
n
d
B
a
s
i
s
(
T
i
,
A
0
) in Lemma 6 is run to get S
i such that ‖
S
-
i
‖
=
‖
T
-
i
‖.
(2)
Use the homomorphic hash function to produce the hash valueh
i
∈
Z
q
n of the message m
i, as is done in theWSign ofLHS1.
(3)
Output the signaturee
i
∈
Z
q
l
m on the hash value by using algorithm S
a
m
p
l
e
P
r
e
(
A
0
,
S
i
,
σ
,
h
i
).C
o
m
b
i
n
e
(
i
d
,
A
0
,
{
(
c
i
,
m
i
,
e
i
)
}
i
=
1
l
). Given a common public key A
0 and the l
≤
L messages tagged the same id from the corresponding users, output an aggregate signature ∑
i
=
1
l
c
i
·
e
i on the combined message ∑
i
=
1
l
c
i
·
m
i, where c
i
∈
{
0,1
}.V
e
r
i
f
y
(
i
d
,
A
0
,
m
a
g
g
=
∑
i
=
1
l
c
i
m
i
,
e
a
g
g
=
∑
i
=
1
l
c
i
e
i
). Given a common public key A
0, an identifier id, an aggregate message m
agg, and the corresponding signature e
agg, do the following.(1)
Compute the hash valueh
agg of m
agg using the homomorphic hash function just like the step (
2
) ofSign does.
(2)
Verify two conditions such asA
0
e
agg
=
h
agg
(
mod
⁡
q
) and ‖
e
agg
‖
≤
L
σ
l
m.
(3)
Output 1 (accept) if and only if the above two conditions hold. Otherwise, output 0 (reject).


### 3.3. Correctness

First of all, we show the correctness of the proposed HAS scheme provided that the related functions are all computed successfully, such as homomorphic hash functionh
α, preimage sampling function, and collision-resistant hash function H.We know thatm
agg
=
∑
i
=
1
l
c
i
m
i, e
agg
=
∑
i
=
1
l
c
i
e
i, and h
α
i
,
j
(
m
i
)
=
(
h
α
i
,
1
(
m
i
)
⋯
h
α
i
,
n
(
m
i
)
)
T, where c
i
∈
{
0,1
}, 0
<
i
≤
l
≤
L, 0
<
j
≤
n and the vector α
i
,
j
=
H
(
id
∥
j
). Since the messages combined are tagged the same identifier, the vectors α
i
∈
[
l
]
,
j
∈
[
n
] originated from H
(
id
∥
j
) are the same for each user. Thus, we can directly use h
α
(
m
i
) to represent the hash value of m
i in order to simplify the notations. Then
(2)
A
0
·
e
agg
=
A
0
·
∑
i
=
1
l
c
i
e
i
=
∑
i
=
1
l
c
i
A
0
e
i
=
∑
i
=
1
l
c
i
h
α
(
m
i
)
=
∑
i
=
1
l
h
α
(
c
i
m
i
)
=
h
α
(
∑
i
=
1
l
c
i
m
i
)
=
h
α
(
m
agg
)
mod
⁡
q
.
Hence, the condition one in the progress ofVerify holds, while ((2)) holds because of the homomorphic property of function h
α. Furthermore, since each signature e
i on massage is obtained by preimage sampling algorithm S
a
m
p
l
e
P
r
e
(
A
0
,
S
i
,
σ
,
h
i
), the length of e
i denoted by the Euclidean norm is not larger than σ
l
m. Thus, the upper length bound of aggregate signature is as follow:
(3)
‖
e
agg
‖
=
‖
∑
i
=
1
l
c
i
e
i
‖
≤
∑
i
=
1
l
‖
c
i
e
i
‖
≤
L
σ
l
m
,
where c
i
∈
{
0,1
} and the first inequality over ((3)) holds by the triangle inequality theorem. It is inferred from the above analysis that the signature e
agg on message ∑
i
=
1
l
c
i
m
i can be verified and can satisfy the requirement of correctness of aggregate signature model defined in Section 2.1.


### 3.4. Optimization

The aggregated signature(
id
,
m
agg
,
e
agg
) of the proposed HAS scheme is accepted byVerify algorithm and confirms to the definition of HAS. However, compared with the signature of single user scheme in [7], it is easy to observe that, in our scheme, the length of each signature on message grows linearly with the number of users. The cause for this problem is that the dimension of random lattice used to sign in our multiuser scheme increases with the number of users, which can be clearly seen from the common public key A
0
∈
Z
q
n
×
l
m. Obviously, the larger the common public key size, the longer the length of aggregate signature and the larger communication cost. Through the observation of the entire HAS scheme, it is clear that the common public key A
0 is shared by each user. In order to reduce the common public key size, the algorithm R
a
n
d
o
m
B
a
s
i
s in Lemma 6 is introduced to our signature scheme, which could generate several different short bases through an arbitrary basis of a lattice. So, we can optimize the proposed HAS scheme from the following aspects.In theS
e
t
u
p
(
1
n
,
L
) phase, while the parameters are consistent with those of the initial scheme, we firstly use T
r
a
p
G
e
n
(
1
n
) algorithm only once to get a matrix A
∈
Z
q
n
×
m and a short basis T
1 of lattice Λ
⊥
(
A
)
∈
Z
q
m, and then, call R
a
n
d
o
m
B
a
s
i
s
(
T
1
,
σ
) algorithm repeatedly to generate l
-
1 independent short basis T
i (2
≤
i
<
l) of lattice Λ
⊥
(
A
). Therefore, let the vectors T
i (1
≤
i
<
l) be user’s private key, respectively, and let A be the common public key shared by everyone, just like the way in [16]. In S
i
g
n
(
id
,
m
i
,
T
i
), we can directly take preimage sampling algorithm S
a
m
p
l
e
P
r
e
(
A
,
T
i
,
σ
,
h
α
(
m
i
)
) to get the signature e
i
∈
Z
q
m on the hash value of m
i denoted by h
α
(
m
i
), where h
α
(
m
i
) is obtained as done in the initial scheme. It should be noted that each user should use his private key in the signing progress. As for theCombine andVerify, the operation of both sections is almost unchanged except that one of verification conditions becomes ‖
e
agg
‖
≤
L
σ
m.It can be proved that the optimized solution meets the correctness of homomorphic aggregate signature model, just like the way of proving in the initial HAS scheme. More importantly, the optimization reduces the size of the common public key and signature to as short as the sizes of those in the single user schemeLHS1.


## 3.1. Definition of HAS

The presented system definition of lattice-based HAS is a variant of that of linearly homomorphic signature in [5]. Compared with the model of single-user homomorphic signature [5, 7], theSetup andVerify parts of HAS system need to define some new properties and additional operators, while theSign part does not change. Formally, the definition of HAS is a tuple of polynomial-time algorithms H
A
S
(
S
e
t
u
p
,
S
i
g
n
s
k
i
,
C
o
m
b
i
n
e
,
V
e
r
i
f
y
c
p
k
), which is as follows.S
e
t
u
p
(
1
n
,
L
). This probabilistic algorithm takes as input the security parameter 1
n and the maximum number of users L and outputs the public-private pair (
p
k
i
,
s
k
i
) for each user (
0
<
i
≤
L
) and the common public key p
c
k shared with everyone.S
i
g
n
(
i
d
,
m
i
,
s
k
i
). For the jth user, this probabilistic algorithm takes as input a message m
i of subspace V
id and the private key s
k
j, and outputs the signature s
i on message m
i.C
o
m
b
i
n
e
(
i
d
,
a
,
{
(
m
i
,
s
i
)
}
i
=
1
l
). Given the combination coefficient vector a and l (l
≤
L) pairs of message sharing the same id and the corresponding signature, output the aggregate signature s on the aggregate message ∑
i
=
1
l
a
i
m
i.V
e
r
i
f
y
c
p
k
(
i
d
,
∑
i
=
1
l
a
i
m
i
,
s
). This is a deterministic algorithm. Given an identifier id, the common public key c
p
k, the aggregate message ∑
i
=
1
l
a
i
m
i, and the corresponding signature s, output either 1 (accept) or 0 (reject).In terms of the correctness and security for the homomorphic aggregate signature scheme, it should have not only the characteristics of general linearly homomorphic signature in case of one user, but also some features of its own in multiuser case. On the one hand, assume that each user is honest, the verification should be able to accept the valid signed message from each user, while a forged signed message must be rejected, which is the same as in the case of the single user. On the other hand, given a series of valid signed message(
id
,
m
i
,
s
k
i
), where i
∈
[
l
], a new valid signed message denoted by (
id
,
∑
i
=
1
l
a
i
m
i
,
s
) can be produced without having access to any private key.


## 3.2. Our Scheme

According to the definition of HAS, we show how to extend the homomorphic signature schemeLHS1 described in Section 2.5 to handle multiuser case. Our initial HAS scheme is as follows.S
e
t
u
p
(
1
n
,
L
). Given a security parameter n and the maximum number of users L, the PKG initializes the scheme from four aspects.(1)
Choose parametersparams
=
{
m
,
q
}. For β
=
poly
(
n
) and let q
≥
β
ω
(
log
⁡
n
) and m
>
c
n
log
⁡
(
q
), where c
>
0 is a constant.
(2)
ForL users, T
r
a
p
G
e
n
(
1
n
) algorithm is repeatedly run L times to generate matrix A
i
∈
Z
q
n
×
m and the corresponding trapdoor basis T
i of Λ
q
⊥
(
A
i
), where 0
<
i
≤
L.
(3)
LetH
:
{
0,1
}
*
→
Z
q
L
m be a collision-resistant hash function which is viewed as a random oracle, and let h be a lattice-based homomorphic hash function described in Section 2.5.
(4)
The pair of{
A
i
,
T
i
} is assigned to the corresponding user u
i as the user’s private key and public key, respectively. Let A
0
=
A
1
‖
⋯
‖
A
L
∈
Z
q
n
×
L
m be the common public key and publish it to all the users. Of course, it is required that delivering the private key should be done secretly.S
i
g
n
(
i
d
,
m
i
,
T
i
). For the ith user, given the common signing key A
0, private key T
i, and one of basis vectors of message subspace V
id, for example, m
i
∈
V
id
⊂
Z
2
m where id
∈
{
0,1
}
n, the signature on message m
i is produced as follows.(1)
To obtain the short basis ofΛ
⊥
(
A
0
)
⊂
Z
l
m, the algorithm E
x
t
e
n
d
B
a
s
i
s
(
T
i
,
A
0
) in Lemma 6 is run to get S
i such that ‖
S
-
i
‖
=
‖
T
-
i
‖.
(2)
Use the homomorphic hash function to produce the hash valueh
i
∈
Z
q
n of the message m
i, as is done in theWSign ofLHS1.
(3)
Output the signaturee
i
∈
Z
q
l
m on the hash value by using algorithm S
a
m
p
l
e
P
r
e
(
A
0
,
S
i
,
σ
,
h
i
).C
o
m
b
i
n
e
(
i
d
,
A
0
,
{
(
c
i
,
m
i
,
e
i
)
}
i
=
1
l
). Given a common public key A
0 and the l
≤
L messages tagged the same id from the corresponding users, output an aggregate signature ∑
i
=
1
l
c
i
·
e
i on the combined message ∑
i
=
1
l
c
i
·
m
i, where c
i
∈
{
0,1
}.V
e
r
i
f
y
(
i
d
,
A
0
,
m
a
g
g
=
∑
i
=
1
l
c
i
m
i
,
e
a
g
g
=
∑
i
=
1
l
c
i
e
i
). Given a common public key A
0, an identifier id, an aggregate message m
agg, and the corresponding signature e
agg, do the following.(1)
Compute the hash valueh
agg of m
agg using the homomorphic hash function just like the step (
2
) ofSign does.
(2)
Verify two conditions such asA
0
e
agg
=
h
agg
(
mod
⁡
q
) and ‖
e
agg
‖
≤
L
σ
l
m.
(3)
Output 1 (accept) if and only if the above two conditions hold. Otherwise, output 0 (reject).


## 3.3. Correctness

First of all, we show the correctness of the proposed HAS scheme provided that the related functions are all computed successfully, such as homomorphic hash functionh
α, preimage sampling function, and collision-resistant hash function H.We know thatm
agg
=
∑
i
=
1
l
c
i
m
i, e
agg
=
∑
i
=
1
l
c
i
e
i, and h
α
i
,
j
(
m
i
)
=
(
h
α
i
,
1
(
m
i
)
⋯
h
α
i
,
n
(
m
i
)
)
T, where c
i
∈
{
0,1
}, 0
<
i
≤
l
≤
L, 0
<
j
≤
n and the vector α
i
,
j
=
H
(
id
∥
j
). Since the messages combined are tagged the same identifier, the vectors α
i
∈
[
l
]
,
j
∈
[
n
] originated from H
(
id
∥
j
) are the same for each user. Thus, we can directly use h
α
(
m
i
) to represent the hash value of m
i in order to simplify the notations. Then
(2)
A
0
·
e
agg
=
A
0
·
∑
i
=
1
l
c
i
e
i
=
∑
i
=
1
l
c
i
A
0
e
i
=
∑
i
=
1
l
c
i
h
α
(
m
i
)
=
∑
i
=
1
l
h
α
(
c
i
m
i
)
=
h
α
(
∑
i
=
1
l
c
i
m
i
)
=
h
α
(
m
agg
)
mod
⁡
q
.
Hence, the condition one in the progress ofVerify holds, while ((2)) holds because of the homomorphic property of function h
α. Furthermore, since each signature e
i on massage is obtained by preimage sampling algorithm S
a
m
p
l
e
P
r
e
(
A
0
,
S
i
,
σ
,
h
i
), the length of e
i denoted by the Euclidean norm is not larger than σ
l
m. Thus, the upper length bound of aggregate signature is as follow:
(3)
‖
e
agg
‖
=
‖
∑
i
=
1
l
c
i
e
i
‖
≤
∑
i
=
1
l
‖
c
i
e
i
‖
≤
L
σ
l
m
,
where c
i
∈
{
0,1
} and the first inequality over ((3)) holds by the triangle inequality theorem. It is inferred from the above analysis that the signature e
agg on message ∑
i
=
1
l
c
i
m
i can be verified and can satisfy the requirement of correctness of aggregate signature model defined in Section 2.1.


## 3.4. Optimization

The aggregated signature(
id
,
m
agg
,
e
agg
) of the proposed HAS scheme is accepted byVerify algorithm and confirms to the definition of HAS. However, compared with the signature of single user scheme in [7], it is easy to observe that, in our scheme, the length of each signature on message grows linearly with the number of users. The cause for this problem is that the dimension of random lattice used to sign in our multiuser scheme increases with the number of users, which can be clearly seen from the common public key A
0
∈
Z
q
n
×
l
m. Obviously, the larger the common public key size, the longer the length of aggregate signature and the larger communication cost. Through the observation of the entire HAS scheme, it is clear that the common public key A
0 is shared by each user. In order to reduce the common public key size, the algorithm R
a
n
d
o
m
B
a
s
i
s in Lemma 6 is introduced to our signature scheme, which could generate several different short bases through an arbitrary basis of a lattice. So, we can optimize the proposed HAS scheme from the following aspects.In theS
e
t
u
p
(
1
n
,
L
) phase, while the parameters are consistent with those of the initial scheme, we firstly use T
r
a
p
G
e
n
(
1
n
) algorithm only once to get a matrix A
∈
Z
q
n
×
m and a short basis T
1 of lattice Λ
⊥
(
A
)
∈
Z
q
m, and then, call R
a
n
d
o
m
B
a
s
i
s
(
T
1
,
σ
) algorithm repeatedly to generate l
-
1 independent short basis T
i (2
≤
i
<
l) of lattice Λ
⊥
(
A
). Therefore, let the vectors T
i (1
≤
i
<
l) be user’s private key, respectively, and let A be the common public key shared by everyone, just like the way in [16]. In S
i
g
n
(
id
,
m
i
,
T
i
), we can directly take preimage sampling algorithm S
a
m
p
l
e
P
r
e
(
A
,
T
i
,
σ
,
h
α
(
m
i
)
) to get the signature e
i
∈
Z
q
m on the hash value of m
i denoted by h
α
(
m
i
), where h
α
(
m
i
) is obtained as done in the initial scheme. It should be noted that each user should use his private key in the signing progress. As for theCombine andVerify, the operation of both sections is almost unchanged except that one of verification conditions becomes ‖
e
agg
‖
≤
L
σ
m.It can be proved that the optimized solution meets the correctness of homomorphic aggregate signature model, just like the way of proving in the initial HAS scheme. More importantly, the optimization reduces the size of the common public key and signature to as short as the sizes of those in the single user schemeLHS1.


## 4. Security Analysis

For the security of linearly homomorphic signature (LHS), two aspects, including unforgeability and privacy, are generally considered in solutions [4]. Clearly, this consideration also can apply to the security of linearly homomorphic aggregate signature scheme (HAS). In this section, we focus on the security of LHS scheme.To prove the unforgeability and privacy of the proposed signature scheme, a reduction to the case of the single user is shown [7]. Obviously, if the number of users equals one (
L
=
1
), our (optimized) scheme is almost identical to LHS1 scheme. Next, we discuss unforgeability and privacy of the proposed HAS scheme in the multiuser case.


### 4.1. Unforgeability

Assuming that no polynomial-time algorithm can solve SIS problem in the average case, Lemma7 proves that in LHS1 the advantage in winning the unforgeability game is negligible. Based on this result, it is able to prove computational security from a reduction of our HAS signature scheme to LHS1 and get the following theorem.Theorem 8.
The presented HAS scheme is unforgeable, if the lattice-based linearly homomorphic signature scheme LHS1 in [7] is unforgeable.Proof.
With the usual method of reduction, assuming there is a polynomial-time algorithmA
* to generate a forged signed aggregate message in HAS, an efficient algorithm C is able to be constructed to produce a forged signed message forLHS1 in polynomial time.
The algorithmA
* takes as input the tuple of public parameters, the common signing key shared by all users, and the set of corresponding signed messages in the subspace V
id from l
≤
L users. The signed message from the ith user is denoted by (
id
,
m
i
,
s
i
), where id is the valid identifier for message subspace. The output of algorithm A
*, denoted by (
id
*
,
β
*
,
y
*
,
s
*
), can be accepted by theVerify algorithm of the presented homomorphic aggregated signature, where β
*
∈
F
2
l is the aggregate coefficient vector. However, this is a forged signed aggregate message, in which either id
*
≠
id or id
*
=
id and y
*
≠
∑
i
=
1
l
β
i
*
m
i for y
*
≠
0.
We assume that the challenger takes the system parameters(
q
,
m
,
n
,
σ
,
l
,
H
) and the key-pair (
A
,
T
) to employ A
* algorithm, where T is a short vector of lattice Λ
⊥
(
A
)
∈
Z
q
m and l is the dimension of the subspace V
id. Thus, the construction of algorithm C by challenger is as follows.(1)
Construct a homomorphic aggregated signature scheme (HAS) withl users. First of all, the challenger extends theWSetup ofLHS1 to generate the l key-pairs (
A
,
T
j
∈
[
l
]
) for users. Specifically, let matrix A be the common public key shared by users, and the corresponding private key T
j of the jth user is the output of the algorithm R
a
n
d
o
m
B
a
s
i
s
(
T
,
σ
), which run repeatedly l times. Then, for message subspace V
id, assume that challenger keeps several answers from the random oracle H and is stored in a list (e.g., L
i
s
t
1), which is just like what the H-Q
u
e
r
y does inLHS1. As a result, each element a
id of L
i
s
t
1 is a tuple (
id
,
{
(
e
j
,
u
j
)
}
i
=
1
l
) where e
j
~
D
Z
m
,
σ
,
0 is directly sampled from the discrete Gaussian distribution D
Z
m for Gaussian parameter σ, and u
j
=
A
e
j
mod
⁡
q is statically close to uniform distribution according to Lemma 3, which could be considered as the basis vectors of V
id. Thereby, a signature s
j on message u
j from the jth user can be produced by calling the algorithm S
a
m
p
l
e
P
r
e
(
A
,
T
i
,
u
j
).
(2)
Call algorithmA
*, which takes on inputs the system parameters and l signed messages (
id
,
v
j
,
s
j
). The output of A
* is a forged signed message (
id
*
,
β
*
,
y
*
,
s
*
) in the HAS scheme, where β
*
∈
F
2
l is the aggregate coefficient vector and s
* is the aggregate signature on the aggregate message y
*
=
∑
j
=
1
l
u
j
*. It is worth noting that the vectors u
j
*
∈
Z
q
n eventually exist, though they are not known and may not be unique.
(3)
The algorithmC outputs the signed message (
id
*
,
β
*
,
y
*
,
s
*
*
) where s
*
*
=
s
*.
Now, we analyze the reduction and show that the output ofC is a forged signed message inLHS1. Firstly, it should be determined whether the output of C can be accepted byLHS1. Since the output of A
* passes the verification of the homomorphic aggregate signature (HAS) scheme, we can know A
s
*
=
y
*
(
mod
⁡
q
) and ‖
s
*
‖
≤
L
σ
m. According to this result, it is easy to obtain that it can pass the verification inLSH1 because the parameters used to verify in both schemes are the same, for example, the matrix A and σ. On the other hand, the output of C is a forged signed message inLHS1 if and only if either id
*
≠
id or id
*
=
id and y
*
≠
∑
i
=
1
l
β
i
*
m
i for y
*
≠
0. Since the signed message (
id
*
,
β
*
,
y
*
,
s
*
) is a forged signed aggregate message, this means that the condition above is satisfied. Consequently, this signed message (
id
*
,
y
*
,
s
*
*
) is a forged signed message inLHS1, and Theorem 8 is proved.


### 4.2. Privacy

In order to prove the privacy of this presented signature scheme, we introduce the “weakly context hiding” of the linearly homomorphic aggregate signature, which is adapted from [5] in the case of single user. The “weakly context hiding” property of the linearly homomorphic signature means the signature on the derived message in some message subspace spanned by {
v
1
,
…
,
v
l
} does not disclose any information about the original messages {
v
1
,
…
,
v
l
}. However, the linear function to combine the messages v
i is not hidden while the original signatures on these messages are kept private, which is why it is called “weakly context hiding.” According to the definition of the linearly homomorphic aggregate signature, we know that this property also applies to our scheme in the case of multiuser, which is shown through proving Theorem 9.Theorem 9.
The proposed linearly homomorphic aggregate signature scheme has the “weakly context hiding” property.Proof.
Suppose that there arel
≤
L users who are assigned the corresponding private key T
i
∈
[
l
] by running the S
e
t
u
p of the proposed signature scheme. In the proposed signature scheme, the ith user employs the algorithm S
a
m
p
l
e
P
r
e to sign original message m
i, and the aggregate signature s
agg on message ∑
i
=
1
l
c
i
m
i is generated through combining the original signatures s
i of the corresponding messages m
i, where each message combined should be tagged the same id and c
i
∈
{
0,1
}. According to Lemma 3 about the distribution of original signatures, despite coming from different users, we know they are all statically close to the Gaussian distribution, for example, s
i
~
D
t
i
+
Λ
⊥
(
A
)
,
σ
,
0, where t
i
∈
Z
m is an arbitrary solution to A
t
i
=
h
α
(
m
i
)
mod
⁡
q and the definitions of remaining variables are the same as those in theSign part of proposed scheme. Hence, by knowledge of Lemma 4, the distribution of the aggregate signature s
agg
=
∑
i
l
c
i
·
s
i
(
mod
⁡
q
) on the aggregate message ∑
i
=
1
l
c
i
m
i is statically close to Gaussian distribution, for example, s
agg
~
D
t
+
g
Λ
,
‖
c
‖
σ
,
0, where t
=
∑
i
=
1
l
c
i
·
t
i and c
i
∈
{
0,1
}. Formally, the distribution of signature on aggregate message only depends on the linear function that was used to compute m
agg rather than on each original message m
i. Thus, it follows that the aggregate signature does not leak any of the original message except for the aggregate message itself, and Theorem 9 above is true.


## 4.1. Unforgeability

Assuming that no polynomial-time algorithm can solve SIS problem in the average case, Lemma7 proves that in LHS1 the advantage in winning the unforgeability game is negligible. Based on this result, it is able to prove computational security from a reduction of our HAS signature scheme to LHS1 and get the following theorem.Theorem 8.
The presented HAS scheme is unforgeable, if the lattice-based linearly homomorphic signature scheme LHS1 in [7] is unforgeable.Proof.
With the usual method of reduction, assuming there is a polynomial-time algorithmA
* to generate a forged signed aggregate message in HAS, an efficient algorithm C is able to be constructed to produce a forged signed message forLHS1 in polynomial time.
The algorithmA
* takes as input the tuple of public parameters, the common signing key shared by all users, and the set of corresponding signed messages in the subspace V
id from l
≤
L users. The signed message from the ith user is denoted by (
id
,
m
i
,
s
i
), where id is the valid identifier for message subspace. The output of algorithm A
*, denoted by (
id
*
,
β
*
,
y
*
,
s
*
), can be accepted by theVerify algorithm of the presented homomorphic aggregated signature, where β
*
∈
F
2
l is the aggregate coefficient vector. However, this is a forged signed aggregate message, in which either id
*
≠
id or id
*
=
id and y
*
≠
∑
i
=
1
l
β
i
*
m
i for y
*
≠
0.
We assume that the challenger takes the system parameters(
q
,
m
,
n
,
σ
,
l
,
H
) and the key-pair (
A
,
T
) to employ A
* algorithm, where T is a short vector of lattice Λ
⊥
(
A
)
∈
Z
q
m and l is the dimension of the subspace V
id. Thus, the construction of algorithm C by challenger is as follows.(1)
Construct a homomorphic aggregated signature scheme (HAS) withl users. First of all, the challenger extends theWSetup ofLHS1 to generate the l key-pairs (
A
,
T
j
∈
[
l
]
) for users. Specifically, let matrix A be the common public key shared by users, and the corresponding private key T
j of the jth user is the output of the algorithm R
a
n
d
o
m
B
a
s
i
s
(
T
,
σ
), which run repeatedly l times. Then, for message subspace V
id, assume that challenger keeps several answers from the random oracle H and is stored in a list (e.g., L
i
s
t
1), which is just like what the H-Q
u
e
r
y does inLHS1. As a result, each element a
id of L
i
s
t
1 is a tuple (
id
,
{
(
e
j
,
u
j
)
}
i
=
1
l
) where e
j
~
D
Z
m
,
σ
,
0 is directly sampled from the discrete Gaussian distribution D
Z
m for Gaussian parameter σ, and u
j
=
A
e
j
mod
⁡
q is statically close to uniform distribution according to Lemma 3, which could be considered as the basis vectors of V
id. Thereby, a signature s
j on message u
j from the jth user can be produced by calling the algorithm S
a
m
p
l
e
P
r
e
(
A
,
T
i
,
u
j
).
(2)
Call algorithmA
*, which takes on inputs the system parameters and l signed messages (
id
,
v
j
,
s
j
). The output of A
* is a forged signed message (
id
*
,
β
*
,
y
*
,
s
*
) in the HAS scheme, where β
*
∈
F
2
l is the aggregate coefficient vector and s
* is the aggregate signature on the aggregate message y
*
=
∑
j
=
1
l
u
j
*. It is worth noting that the vectors u
j
*
∈
Z
q
n eventually exist, though they are not known and may not be unique.
(3)
The algorithmC outputs the signed message (
id
*
,
β
*
,
y
*
,
s
*
*
) where s
*
*
=
s
*.
Now, we analyze the reduction and show that the output ofC is a forged signed message inLHS1. Firstly, it should be determined whether the output of C can be accepted byLHS1. Since the output of A
* passes the verification of the homomorphic aggregate signature (HAS) scheme, we can know A
s
*
=
y
*
(
mod
⁡
q
) and ‖
s
*
‖
≤
L
σ
m. According to this result, it is easy to obtain that it can pass the verification inLSH1 because the parameters used to verify in both schemes are the same, for example, the matrix A and σ. On the other hand, the output of C is a forged signed message inLHS1 if and only if either id
*
≠
id or id
*
=
id and y
*
≠
∑
i
=
1
l
β
i
*
m
i for y
*
≠
0. Since the signed message (
id
*
,
β
*
,
y
*
,
s
*
) is a forged signed aggregate message, this means that the condition above is satisfied. Consequently, this signed message (
id
*
,
y
*
,
s
*
*
) is a forged signed message inLHS1, and Theorem 8 is proved.


## 4.2. Privacy

In order to prove the privacy of this presented signature scheme, we introduce the “weakly context hiding” of the linearly homomorphic aggregate signature, which is adapted from [5] in the case of single user. The “weakly context hiding” property of the linearly homomorphic signature means the signature on the derived message in some message subspace spanned by {
v
1
,
…
,
v
l
} does not disclose any information about the original messages {
v
1
,
…
,
v
l
}. However, the linear function to combine the messages v
i is not hidden while the original signatures on these messages are kept private, which is why it is called “weakly context hiding.” According to the definition of the linearly homomorphic aggregate signature, we know that this property also applies to our scheme in the case of multiuser, which is shown through proving Theorem 9.Theorem 9.
The proposed linearly homomorphic aggregate signature scheme has the “weakly context hiding” property.Proof.
Suppose that there arel
≤
L users who are assigned the corresponding private key T
i
∈
[
l
] by running the S
e
t
u
p of the proposed signature scheme. In the proposed signature scheme, the ith user employs the algorithm S
a
m
p
l
e
P
r
e to sign original message m
i, and the aggregate signature s
agg on message ∑
i
=
1
l
c
i
m
i is generated through combining the original signatures s
i of the corresponding messages m
i, where each message combined should be tagged the same id and c
i
∈
{
0,1
}. According to Lemma 3 about the distribution of original signatures, despite coming from different users, we know they are all statically close to the Gaussian distribution, for example, s
i
~
D
t
i
+
Λ
⊥
(
A
)
,
σ
,
0, where t
i
∈
Z
m is an arbitrary solution to A
t
i
=
h
α
(
m
i
)
mod
⁡
q and the definitions of remaining variables are the same as those in theSign part of proposed scheme. Hence, by knowledge of Lemma 4, the distribution of the aggregate signature s
agg
=
∑
i
l
c
i
·
s
i
(
mod
⁡
q
) on the aggregate message ∑
i
=
1
l
c
i
m
i is statically close to Gaussian distribution, for example, s
agg
~
D
t
+
g
Λ
,
‖
c
‖
σ
,
0, where t
=
∑
i
=
1
l
c
i
·
t
i and c
i
∈
{
0,1
}. Formally, the distribution of signature on aggregate message only depends on the linear function that was used to compute m
agg rather than on each original message m
i. Thus, it follows that the aggregate signature does not leak any of the original message except for the aggregate message itself, and Theorem 9 above is true.


## 5. Efficiency

In order to analyze the performance, we compare the proposed signatures scheme with previous lattice-based linearly homomorphic signature schemes [5, 7, 16] in terms of public key size, signature length, signing cost, verifying overhead, and multiuser supporting, respectively.LetT
ps denote the time cost to run once S
a
m
p
l
e
P
r
e algorithm and let T
bs denote the time cost to run once E
x
t
B
a
s
i
s algorithm. Since these two algorithms commonly used in lattice-based signature scheme take up most of the time cost throughout the whole signature process, T
ps and T
bs could be the main indicators in comparison of signing cost. However, the verifying part of schemes mainly involves simple addition and multiplication operations over the modulo, so we use space overhead as the indicator in comparison of the verifying cost. In addition, in the comparison of signature length, for example, (
id
,
s
), the length of id can be ignored because this length is the same for each scheme.Table1 shows that Wang’s scheme [7] is more efficient than Boneh’s scheme [5] in the case of single user. In the case of multiple users, our scheme displays the same efficiency as Wang’s in the single user case. Compared with our scheme, the length of signature in Zhang’s scheme [16] is twice that of our scheme, and its verifying cost is four times.Table 1
Comparison of several lattice-based linearly homomorphic signature schemes.
Scheme
Multiuser supporting
Public key length
Signature length
Signing cost
Verifying cost(Space overhead)
Boneh’s [5]
No
n
m
+
n
m
lg
⁡
q
2
m
+
2
m
lg
⁡
q
T
ps
+
T
bs
n
m
2
+
2
n
m
2
lg
⁡
q
+
n
m
2
(
lg
⁡
q
)
2
Wang’s [7]
No
n
m
lg
⁡
q
m
lg
⁡
q
T
ps
n
m
2
(
lg
⁡
q
)
2
Zhang’s [16]
Yes
n
m
lg
⁡
q
2
m
lg
⁡
q
T
ps
+
T
bs
4n
m
2
(
lg
⁡
q
)
2
Our scheme
Yes
n
m
lg
⁡
q
m
lg
⁡
q
T
ps
n
m
2
(
lg
⁡
q
)
2


## 6. Conclusions

In this paper, we propose a novel lattice-based HAS scheme with short signature, which is an extension of LHS scheme based on lattice over binary field in the single user case [7]. Our scheme holds both homomorphic property and aggregate property, in which a signed aggregate message can be verified by using the combination of signatures of the original messages and the common public key derived from the public keys of the corresponding users. We prove its security through decreasing to the single user case. At the same time, the “weakly context hiding” property holds in the proposed scheme. Furthermore, it is more practical than the Zhang’s HAS scheme [16]. However, there is still much work to be done in order to improve the capability of the scheme, such as how to design a variant of the scheme with “strong context hiding” property and how to take advantage of “ideal lattice” to decrease the public key size.



---

*Source: 536527-2014-11-06.xml*