# Strongly Unforgeable Ring Signature Scheme from Lattices in the Standard Model

Authors: Geontae Noh; Ji Young Chun; Ik Rae Jeong
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

In a ring signature scheme, a user selects an arbitrary ring to be able to
sign a message on behalf of the ring without revealing the signer’s identity. Whistle-blowers especially find this useful. To date, various ring signature schemes have been proposed, all considered to be secure as existentially unforgeable with respect to insider corruption; that is, an adversary who chooses ring-message pairs for which he requests signatures, corrupts honest users, and obtains their signing keys can not produce forgeries for new ring-message pairs. Lattice-based ring signature schemes offer lower computational overhead and security from quantum attacks. In this paper, we offer a lattice-based scheme. We begin by showing that the existing ring signature schemes are not sufficiently secure, because existential unforgeability still permits a signer to potentially produce a new signature on previously signed messages. Furthermore, we show that existing ring signature schemes
from lattices are not even existentially unforgeable with respect to insider corruption. We then improve previous schemes by applying, for the first time, the concept of strong unforgeability with respect to insider corruption to a ring signature scheme in lattices. This offers more security than any previous ring signature scheme: adversaries cannot produce new signatures for any ring-message pair, including previously signed ring-message pairs.


---

## Body

## 1. Introduction

Ring signatures were first introduced by Rivest et al. in 2001 in order to provide anonymity to signers [1]. The classic case of a signer who wishes to remain anonymous would be a whistle-blower, who wants to identify a problem without exposing himself as the source. Anyone seeking to expose wrongdoing or leak a secret would want to remain anonymous. Prior to the advent of the ring signature, group signatures were the best way to achieve this; however, group signatures have a group manager who can identify the signer and so complete anonymity is not possible. By contrast, a signer can select a ring for the signature, and no one can trace which member of the ring is the actual signer.In 2004, Dodis et al. proposed a ring signature scheme in the random oracle model using the Fiat-Shamir transformation [2, 3]. In 2006, Bender et al. proposed new definitions of anonymity and existential unforgeability and first proposed ring signature schemes in the standard model [4]. In 2007, Shacham and Waters proposed efficient ring signature schemes in the standard model based on bilinear groups [5]. In addition to these, various ring signature schemes have been studied [6–11].All of these early ring signatures used nonlattice based approaches. These cryptographic systems were based on integer factorization and discrete logarithmic problems based on average case problems. These nonlattice based approaches did not offer security against quantum computing attacks [12]. These early ring signatures also entailed more computational overhead because they require exponentiation, although they did offer existential unforgeability with respect to insider corruption and anonymity against full key exposure. Lattice-based cryptographic systems held promise in reducing computational overhead since they only require linear operations on matrices [13–18].In order to try to reduce computational overhead and make ring signatures secure against quantum computing attacks, Brakerski and Kalai introduced the first lattice-based system for ring signatures in 2010, using ring trapdoor functions [19]. The lattice-based approach is based on worst-case problems, which offers the sought for security against quantum computing attacks; however, Brakerski-Kalai’s ring signature scheme did not satisfy existential unforgeability with respect to insider corruption. In 2010, Cayrel et al. proposed a threshold ring signature scheme over ideal lattices (ideal lattices are described as ideals of certain polynomial rings; that is, ideal lattices are a special case of lattices) in the random oracle model; however, Cayrel et al.’s threshold ring signature scheme did not satisfy existential unforgeability with respect to insider corruption [20]. In 2011, Wang and Sun proposed two ring signature schemes, one in the random oracle model and one in the standard model, using lattice-based delegation techniques [21]. They claimed their ring signature schemes offered the existential unforgeability that had been lacking in Brakerski-Kalia’s ring signature scheme, but they in fact did not (see Section 3). In 2013, Aguilar Melchor et al. proposed a new ring signature scheme over ideal lattices; however, Aguilar Melchor et al.’s ring signature scheme is only existentially unforgeable with respect to insider corruption in the random oracle model [22]. Table 1 shows the comparison of ring signature schemes.Table 1
Comparison of ring signature schemes.
EU
SU
ROM/STM
[19]
×
×
STM
[20]
×
×
ROM
[21]
×
×
ROM/STM
[22]
◯
×
ROM
Ours
◯
◯
STM
EU means the ring signature scheme is existentially unforgeable with respect to insider corruption, SU means the ring signature scheme is strongly unforgeable with respect to insider corruption, ROM means the ring signature scheme is secure in the random oracle model, and STM means the ring signature scheme is secure in the standard model.In addition to showing that Wang and Sun’s ring signature scheme does not offer existential unforgeability, we introduce a novel lattice-based ring signature scheme that reduces the computational overhead inherent in nonlattice based schemes while successfully offering existential unforgeability with respect to insider corruption. Indeed, we are the first to suggest strong unforgeability for ring signatures, which is stronger than existential unforgeability.Before the work on strong unforgeability [23–25], if a signature scheme is existentially unforgeable, it has been considered to be secure. In other words, an adversary who chooses messages for which she requests signatures should not be able to produce signatures for new messages. However, in an existentially unforgeable signature scheme, the adversary could potentially produce a new signature on one or more of the previously signed messages. By contrast, if a signature scheme is strongly unforgeable, the adversary cannot ever produce a new signature for any message, including previously signed messages. Strongly unforgeable signature schemes can be especially useful in constructing chosen ciphertext secure encryption schemes and group signature schemes.Similarly, existentially unforgeable ring signature schemes have been considered to be secure. In other words, an adversary who chooses ring-message pairs for which she requests signatures is not able to produce signatures for new ring-message pairs. In this paper, we are the first to design a securer ring signature scheme, implementing the concept of strong unforgeability and ensuring that the adversary cannot ever produce a new signature for any ring-message pair, including previously signed ring-message pairs. That is, suppose an adversary chooses some ring-message pairs, requests their signatures, and obtains a tuple of ring, message, and signature(
R
,
m
,
σ
) along with other tuples of rings, messages, and signatures. If the adversary cannot ever produce a new signature σ
′ for (
R
,
m
), or any signatures for any of the ring-message pairs, we say that the ring signature scheme is strongly unforgeable.We accomplish this strong unforgeability using lattices in the standard model. Our ring signature scheme uses new trapdoor algorithms for lattices proposed by Micciancio and Peikert in 2012 [18]. They are much simpler, tighter, faster, and smaller than the existing algorithms. More concretely, their trapdoor algorithms do not run any expensive operation such as matrix inverse computations; their new trapdoor algorithms improved the quality s from s
≈
20
n
lg
q to s
≈
1.6
n
lg
q for some small q
=
poly
(
n
) and a security parameter n; using their new trapdoor algorithms reduces the lattice dimension m from m
>
5
n
lg
q to m
≈
2
n
lg
q. Therefore, our ring signature scheme is also much simpler, tighter, faster, and smaller than the existing lattice-based ring signature schemes. In fact, the lattice dimension of our ring signature scheme is m
≈
2
(
1
+
l
)
n
lg
q for the number of ring users instead of m
>
5
(
1
+
l
)
n
lg
q. Our ring signature scheme not only maintains anonymity against full key exposure but also offers strong unforgeability with respect to insider corruption in the standard model.


### 1.1. Our Contribution

Our work makes three significant contributions. First, we show that all of Wang-Sun’s ring signature schemes are insecure with respect to existential unforgeability. Second, we suggest the concept of strong unforgeability, which is a stronger notion than existential unforgeability, for ring signatures. None of the existing lattice-based ring signature schemes satisfy the conditions of strong unforgeability. Third, based on our new model, we construct a new ring signature scheme from lattices that is both anonymous against full key exposure and strongly unforgeable with respect to insider corruption in the standard model.


### 1.2. Our Approach

As with most existing ring signature schemes for lattices, we design our ring signature scheme using trapdoor delegation techniques for lattices, which afford anonymity against full key exposure. In addition, in our ring signature scheme, like most of the existing signature schemes from lattices, the “hash-and-sign” paradigm is used. Wang and Sun also used the “hash-and-sign” paradigm, but they did so in a way that failed to ensure the security of their schemes. Both of Wang-Sun’s ring signature schemes only hash the message, so that anyone can add a ring member and add another message, making it possible for anyone to produce a forgery. We address this problem in our ring signature scheme by hashing the message along with the ring and a random number. Because the ring is included in the hash value, an adversary cannot change the ring. We have drawn on the concept of strong unforgeability in signature schemes from lattices to extend strong unforgeability to a ring signature scheme. One of the features of the existing strongly unforgeable signature schemes is that the signature algorithm samples a signature in a coset of the lattice (not in the original lattice). Our ring signature scheme uses this signature algorithm. This is the defining feature that makes our ring signature scheme strongly unforgeable with respect to insider corruption in the standard model.


### 1.3. Organization of the Paper

The remainder of our paper is organized as follows. In Section2, we describe related work and preliminaries. We will describe early ring signature schemes, existing lattice-based schemes, and chameleon hash functions. In Section 3, we analyze Wang-Sun’s ring signature schemes and show that they do not provide existential unforgeability as they purport to do. In Section 4, we address our security model for ring signatures, describing anonymity against full key exposure and our new concept of strong unforgeability. In Section 5, we construct our ring signature scheme and demonstrate that it is secure in both of these respects. In Section 6, we will make our concluding comments.


## 1.1. Our Contribution

Our work makes three significant contributions. First, we show that all of Wang-Sun’s ring signature schemes are insecure with respect to existential unforgeability. Second, we suggest the concept of strong unforgeability, which is a stronger notion than existential unforgeability, for ring signatures. None of the existing lattice-based ring signature schemes satisfy the conditions of strong unforgeability. Third, based on our new model, we construct a new ring signature scheme from lattices that is both anonymous against full key exposure and strongly unforgeable with respect to insider corruption in the standard model.


## 1.2. Our Approach

As with most existing ring signature schemes for lattices, we design our ring signature scheme using trapdoor delegation techniques for lattices, which afford anonymity against full key exposure. In addition, in our ring signature scheme, like most of the existing signature schemes from lattices, the “hash-and-sign” paradigm is used. Wang and Sun also used the “hash-and-sign” paradigm, but they did so in a way that failed to ensure the security of their schemes. Both of Wang-Sun’s ring signature schemes only hash the message, so that anyone can add a ring member and add another message, making it possible for anyone to produce a forgery. We address this problem in our ring signature scheme by hashing the message along with the ring and a random number. Because the ring is included in the hash value, an adversary cannot change the ring. We have drawn on the concept of strong unforgeability in signature schemes from lattices to extend strong unforgeability to a ring signature scheme. One of the features of the existing strongly unforgeable signature schemes is that the signature algorithm samples a signature in a coset of the lattice (not in the original lattice). Our ring signature scheme uses this signature algorithm. This is the defining feature that makes our ring signature scheme strongly unforgeable with respect to insider corruption in the standard model.


## 1.3. Organization of the Paper

The remainder of our paper is organized as follows. In Section2, we describe related work and preliminaries. We will describe early ring signature schemes, existing lattice-based schemes, and chameleon hash functions. In Section 3, we analyze Wang-Sun’s ring signature schemes and show that they do not provide existential unforgeability as they purport to do. In Section 4, we address our security model for ring signatures, describing anonymity against full key exposure and our new concept of strong unforgeability. In Section 5, we construct our ring signature scheme and demonstrate that it is secure in both of these respects. In Section 6, we will make our concluding comments.


## 2. Preliminaries

The security parameter in this paper isn. We denote the real numbers and integers by ℝ and ℤ, respectively. For a positive integer k, we let [
1
,
k
]
=
{
1
,
…
,
k
}. We denote vectors by lower-case bold letters (e.g., v) and assume that v is a column vector. ∥
v
∥ means the Euclidean norm of  v. We denote matrices by upper-case bold letters (e.g., A) and represent the n-by-n identity matrix as I
n. We use standard big-O notation, and, if f
(
k
)
=
O
(
g
(
k
)
·
log
⁡
c
k
) for any fixed integer c, then we denote f
(
k
)
=
O
~
(
g
(
k
)
). q
=
poly
(
k
) means q
∈
Θ
(
k
c
) for some positive integer c. If |
f
(
k
)
|
<
1
/
k
c for sufficiently large k and any c
>
0, then a function f
:
ℝ
→
ℝ is negligible. We denote any negligible function by negl
(
n
). An overwhelming probability is greater than or equal to 1
-
f
(
k
), where f
(
k
) is a negligible function. When v is randomly chosen from a set R, we use the notation v
←
R. The statistical distance between two distributions X and Y over a countable domain 𝒟 is denoted by Δ
(
X
,
Y
)
=
1
/
2
·
∑
i
∈
𝒟
‍
|
X
(
i
)
-
Y
(
i
)
|.


### 2.1. Lattices

In this paper, we considerm-dimensional integer lattices. An m-dimensional integer lattice Λ is defined as follows:
(1)
Λ
=
{
B
z
=
∑
i
=
1
m
z
i
b
i
:
z
∈
ℤ
m
}
⊆
ℤ
m
,
where B
=
{
b
1
,
…
,
b
m
}
⊂
ℤ
m is a basis. The dual lattice Λ
* of Λ is defined as follows:
(2)
Λ
*
=
{
x
∈
ℤ
m
:
∀
y
∈
Λ
,
〈
x
,
y
〉
∈
ℤ
}
⊆
ℤ
m
.We use aq-ary lattice, which is one of m-dimensional integer lattices. For a parity-check matrix A
∈
ℤ
q
n
×
m, a q-ary lattice Λ
⊥
(
A
) is defined as follows:
(3)
Λ
⊥
(
A
)
=
{
z
∈
ℤ
m
:
A
z
=
0
(
mod
⁡
q
)
}
⊆
ℤ
m
,
where n and q are positive integers and 0
∈
ℤ
q
n is a zero vector. Next, we define a coset of Λ
⊥
(
A
). For a syndrome u
∈
ℤ
q
n, a coset Λ
u
⊥
(
A
) of Λ
⊥
(
A
) is defined as follows:
(4)
Λ
u
⊥
(
A
)
=
{
z
∈
ℤ
m
:
A
z
=
u
(
mod
⁡
q
)
}
=
Λ
⊥
(
A
)
+
z
¯
,
where A
z
¯
=
u
(
mod
⁡
q
) for z
¯
∈
ℤ
m.TheSIS (short integer solution) problem in lattices is defined as follows.Definition 1.
Given a uniformly random matrixA
∈
ℤ
q
n
×
m for any desired m
=
poly
(
n
), the SI
S
q
,
β problem is to find a nonzero vector v
∈
ℤ
m such that A
v
=
0
(
mod
⁡
q
) and ∥
v
∥
≤
β.The hardness of theSIS problem follows from [13, 26, 27]. For q
≥
β
·
n
·
ω
(
log
⁡
n
), the SIS problem in the average case is known to be as hard as approximating the SIVP (shortest independent vectors problem) under quantum reductions to within O
~
(
β
·
n
) factors in the worst case.We now review Gaussian distributions over lattices. First, we recall the Gaussian function as follows:(5)
ρ
ℋ
,
s
,
c
(
x
)
=
exp
⁡
⁡
(
-
π
∥
x
-
c
∥
2
s
2
)
,
where ℋ is a d-dimensional subspace of ℝ
m, m
≥
1, s
>
0, x
∈
ℋ, and the Gaussian function centered at c
∈
ℋ. The continuous distribution with density function is defined as follows:
(6)
𝒟
ℋ
,
s
,
c
(
x
)
=
ρ
ℋ
,
s
,
c
(
x
)
s
d
,
where
s
d
=
∫
x
∈
ℋ
ρ
s
,
c
(
x
)
d
x
.
‍Then, the discrete distribution with density function over a latticeΛ is defined as follows:
(7)
𝒟
Λ
,
s
,
c
(
x
)
=
𝒟
ℋ
,
s
,
c
(
x
)
𝒟
ℋ
,
s
,
c
(
Λ
)
,
where Λ
⊂
ℋ spans ℋ and x
∈
Λ. Next, we define the Gaussian parameter which is a lattice quantity.Definition 2 (see [27, 28]).
For anm-dimensional integer lattice Λ and a real number ϵ
>
0, the Gaussian parameter η
ϵ
(
Λ
) is the smallest s such that ρ
ℋ
,
1
/
s
(
Λ
*
∖
{
0
}
)
≤
ϵ, where ρ
ℋ
,
1
/
s
(
·
) is the Gaussian function (centered at 0) for 1
/
s,  Λ
⊂
ℋ spans ℋ, and Λ
* is the dual lattice of Λ.In this paper, we also use the following fact.Lemma 3 (see [18, 29]).
Forϵ
∈
(
0,1
), s
≥
η
ϵ
(
Λ
), and c
∈
span
⁡
(
Λ
):
(8)
Pr
⁡
[
∥
𝒟
Λ
,
s
,
c
∥
≥
s
·
m
]
≤
2
-
m
·
1
+
ϵ
1
-
ϵ
,
where Λ
⊂
ℝ
m is a lattice.


### 2.2. Basic Algorithms for Lattices

The trapdoor generation algorithmG
e
n
T
r
a
p
(
A
¯
,
H
) proposed by Micciancio and Peikert in 2012 [18] has the following properties.Lemma 4 (see [18]).
There exists a probabilistic polynomial time algorithmG
e
n
T
r
a
p
(
A
¯
,
H
) that takes a parity-check matrix A
¯
∈
ℤ
q
n
×
m
¯, an invertible matrix H
∈
ℤ
q
n
×
n, n
≥
1, m
=
O
(
n
log
⁡
⁡
q
), q
≥
2, and outputs a parity-check matrix A
∈
ℤ
q
n
×
m with its trapdoor T such that(i)
G
e
n
T
r
a
p
(
A
¯
,
H
) uses some fixed primitive matrix G
∈
ℤ
q
n
×
n
k whose columns generate all of ℤ
q
n;
(ii)
G
e
n
T
r
a
p
(
A
¯
,
H
) chooses a matrix T
←
𝒟
ℤ
,
ω
(
log
⁡
⁡
n
)
m
¯
×
n
k, where m
=
m
¯
+
n
k and k
=
O
(
log
⁡
⁡
n
);
(iii)
G
e
n
T
r
a
p
(
A
¯
,
H
) computes A
=
[
A
¯
∥
H
G
-
A
¯
T
]
∈
ℤ
q
n
×
m;
(iv)
the statistical distance between the distribution ofA and the uniform distribution is negligible;
(v)
s
1
(
T
)
=
s
T
·
O
(
m
¯
+
n
k
) holds with an overwhelming probability, where s
1
(
T
) is the maximal singular value of T and s
T
>
0;
(vi)
G
e
n
T
r
a
p
(
A
¯
) means G
e
n
T
r
a
p
(
A
¯
,
I
n
).
The trapdoor Gaussian sampling algorithmS
a
m
p
l
e
D
(
A
,
T
,
H
,
u
,
s
) proposed by Micciancio and Peikert in 2012 [18] has the following properties.Lemma 5 (see [18]).
There exists a probabilistic polynomial time algorithmS
a
m
p
l
e
D
(
A
,
T
,
H
,
u
,
s
) that takes a parity-check matrix A
∈
ℤ
q
n
×
m with its trapdoor T, an invertible matrix H
∈
ℤ
q
n
×
n, a syndrome u
∈
ℤ
q
n, s
=
O
(
n
log
⁡
⁡
q
)
≥
s
G
·
s
1
(
T
) (where s
G
=
2 if q is a power of 2, or s
G
=
5 otherwise), n
≥
1,  m
=
O
(
n
log
⁡
⁡
q
),  q
≥
2, and outputs a vector v such that(i)
S
a
m
p
l
e
D
(
A
,
T
,
H
,
u
,
s
) uses some fixed primitive matrix G
∈
ℤ
q
n
×
n
k whose columns generate all of ℤ
q
n;
(ii)
the statistical distance between the distribution ofv and the distribution of 𝒟
Λ
u
⊥
(
A
)
,
s
·
ω
(
log
⁡
⁡
n
) is negligiblel;
(iii)
S
a
m
p
l
e
D
(
A
,
T
,
u
,
s
) means S
a
m
p
l
e
D
(
A
,
T
,
I
n
,
u
,
s
).
The trapdoor delegation algorithmD
e
l
T
r
a
p
(
A
′
=
[
A
∥
A
1
]
,
T
,
H
′
,
s
′
) proposed by Micciancio and Peikert in 2012 [18] has the following properties.Lemma 6 (see [18]).
There exists a probabilistic polynomial time algorithmD
e
l
T
r
a
p
(
A
′
=
[
A
∥
A
1
]
,
T
,
H
′
,
s
′
) that takes a parity-check matrix A
′
=
[
A
∥
A
1
]
∈
ℤ
q
n
×
(
m
+
n
k
), a trapdoor T corresponding to A, an invertible matrix H
′
∈
ℤ
q
n
×
n, and s
′
≥
η
ϵ
(
Λ
⊥
(
A
)
), where n
≥
1, m
=
O
(
n
log
⁡
⁡
q
), q
≥
2, k
=
O
(
log
⁡
⁡
n
), and outputs a trapdoor T
′ corresponding to A
′
=
[
A
∥
A
1
] such that(i)
D
e
l
T
r
a
p
(
A
′
=
[
A
∥
A
1
]
,
T
,
H
′
,
s
′
) uses some fixed primitive matrix G
∈
ℤ
q
n
×
n
k whose columns generate all of ℤ
q
n;
(ii)
the statistical distance between the distribution ofT
′ and the Gaussian distribution with s
′ is negligible;
(iii)
s
1
(
T
′
)
≤
s
′
·
O
(
m
+
n
k
) holds with an overwhelming probability;
(iv)
D
e
l
T
r
a
p works even if the columns of A
′
=
[
A
∥
A
1
] are randomly permuted;
(v)
D
e
l
T
r
a
p
(
A
′
=
[
A
∥
A
1
]
,
T
,
s
′
) means D
e
l
T
r
a
p
(
A
′
=
[
A
∥
A
1
]
,
T
,
I
n
,
s
′
).


### 2.3. Properties ofℛ
*

We use a set of invertible elements in a certain ringℛ
=
ℤ
q
/
f
(
x
) introduced by Micciancio and Peikert in 2012 [18].Lemma 7 (see [18]).
Letf
(
x
)
=
x
n
+
a
n
-
1
x
n
-
1
+
⋯
+
a
1
x
+
a
0
∈
ℤ
[
x
] be a monic n-degree polynomial. Then, one defines ℛ
* as a set of invertible elements in the ring ℛ
=
ℤ
q
[
x
]
/
f
(
x
) with the following properties:(i)
an arbitrary subset-sum inℛ
* is also an invertible element in ℛ
*;
(ii)
there exists a ring homomorphismh
(
·
)
:
ℛ
*
→
ℤ
q
n
×
n that maps from a
∈
ℛ
* to an invertible matrix H
=
h
(
a
);
(iii)
the number of elements inℛ
* is at most (
p
-
1
)
·
n, where p is the smallest prime dividing q.


### 2.4. Chameleon Hash Function

A family of chameleon hash functionsH
(
·
,
·
)
:
{
0,1
}
*
×
{
0,1
}
m
→
{
0,1
}
h was proposed by Cash et al. in 2010 [15].Lemma 8 (see [15]).
If theS
I
S
q
,
β problem for q
≥
|
m
|
+
4
·
s
2
·
m
·
n
·
ω
(
log
⁡
⁡
n
) and β
=
|
m
|
+
4
·
s
2
·
m is hard, the hash function H
(
·
,
·
)
:
{
0,1
}
*
×
{
0,1
}
m
→
{
0,1
}
h has the trapdoor property and the collision resistance property, where |
m
| is the bit length of the message, h is the bit length of the hash value, s is a Gaussian parameter, n
≥
1, m
=
O
(
n
log
⁡
⁡
q
), and q
≥
2. The properties of H
(
·
,
·
) are as follows.(i)
The trapdoor property. For any H
(
m
,
r
) and m
′, we can sample r
′ with trapdoor information such that H
(
m
,
r
)
=
H
(
m
′
,
r
′
).
(ii)
The collision resistance property. It is hard to find (
m
,
r
) and (
m
′
,
r
′
) without trapdoor information such that H
(
m
,
r
)
=
H
(
m
′
,
r
′
) and (
m
,
r
)
≠
(
m
′
,
r
′
).


### 2.5. Ring Signatures

A ring signature schemeR
S is a triple set of algorithms {
R
S
.
G
e
n
,
R
S
.
S
i
g
n
,
R
S
.
V
r
f
y
}.(i)
R
S
.
G
e
n
(
1
n
): on input of a security parameter n, this algorithm outputs a signing key s
k
i and verification key v
k
i pair.
(ii)
R
S
.
S
i
g
n
(
s
k
i
,
R
,
m
): on input of a signing key s
k
i, a ring R, and a message m, this algorithm outputs a ring signature σ, where R is an ordered set of verification keys.
(iii)
R
S
.
V
r
f
y
(
R
,
m
,
σ
): on input of a ring R, a message m, and a ring signature σ, this algorithm outputs 1 if the ring signature is valid and 0 otherwise.Correctness. A ring signature scheme R
S is correct if, for any valid ring signature σ corresponding to (
R
,
m
), the R
S
.
V
r
f
y
(
R
,
m
,
σ
) algorithm outputs 1 with an overwhelming probability.Generally, ring signatures should be required to satisfy conditions of anonymity and unforgeability. Definitions of anonymity against full key exposure and existential unforgeability with respect to insider corruption were proposed by Bender et al. [4].


## 2.1. Lattices

In this paper, we considerm-dimensional integer lattices. An m-dimensional integer lattice Λ is defined as follows:
(1)
Λ
=
{
B
z
=
∑
i
=
1
m
z
i
b
i
:
z
∈
ℤ
m
}
⊆
ℤ
m
,
where B
=
{
b
1
,
…
,
b
m
}
⊂
ℤ
m is a basis. The dual lattice Λ
* of Λ is defined as follows:
(2)
Λ
*
=
{
x
∈
ℤ
m
:
∀
y
∈
Λ
,
〈
x
,
y
〉
∈
ℤ
}
⊆
ℤ
m
.We use aq-ary lattice, which is one of m-dimensional integer lattices. For a parity-check matrix A
∈
ℤ
q
n
×
m, a q-ary lattice Λ
⊥
(
A
) is defined as follows:
(3)
Λ
⊥
(
A
)
=
{
z
∈
ℤ
m
:
A
z
=
0
(
mod
⁡
q
)
}
⊆
ℤ
m
,
where n and q are positive integers and 0
∈
ℤ
q
n is a zero vector. Next, we define a coset of Λ
⊥
(
A
). For a syndrome u
∈
ℤ
q
n, a coset Λ
u
⊥
(
A
) of Λ
⊥
(
A
) is defined as follows:
(4)
Λ
u
⊥
(
A
)
=
{
z
∈
ℤ
m
:
A
z
=
u
(
mod
⁡
q
)
}
=
Λ
⊥
(
A
)
+
z
¯
,
where A
z
¯
=
u
(
mod
⁡
q
) for z
¯
∈
ℤ
m.TheSIS (short integer solution) problem in lattices is defined as follows.Definition 1.
Given a uniformly random matrixA
∈
ℤ
q
n
×
m for any desired m
=
poly
(
n
), the SI
S
q
,
β problem is to find a nonzero vector v
∈
ℤ
m such that A
v
=
0
(
mod
⁡
q
) and ∥
v
∥
≤
β.The hardness of theSIS problem follows from [13, 26, 27]. For q
≥
β
·
n
·
ω
(
log
⁡
n
), the SIS problem in the average case is known to be as hard as approximating the SIVP (shortest independent vectors problem) under quantum reductions to within O
~
(
β
·
n
) factors in the worst case.We now review Gaussian distributions over lattices. First, we recall the Gaussian function as follows:(5)
ρ
ℋ
,
s
,
c
(
x
)
=
exp
⁡
⁡
(
-
π
∥
x
-
c
∥
2
s
2
)
,
where ℋ is a d-dimensional subspace of ℝ
m, m
≥
1, s
>
0, x
∈
ℋ, and the Gaussian function centered at c
∈
ℋ. The continuous distribution with density function is defined as follows:
(6)
𝒟
ℋ
,
s
,
c
(
x
)
=
ρ
ℋ
,
s
,
c
(
x
)
s
d
,
where
s
d
=
∫
x
∈
ℋ
ρ
s
,
c
(
x
)
d
x
.
‍Then, the discrete distribution with density function over a latticeΛ is defined as follows:
(7)
𝒟
Λ
,
s
,
c
(
x
)
=
𝒟
ℋ
,
s
,
c
(
x
)
𝒟
ℋ
,
s
,
c
(
Λ
)
,
where Λ
⊂
ℋ spans ℋ and x
∈
Λ. Next, we define the Gaussian parameter which is a lattice quantity.Definition 2 (see [27, 28]).
For anm-dimensional integer lattice Λ and a real number ϵ
>
0, the Gaussian parameter η
ϵ
(
Λ
) is the smallest s such that ρ
ℋ
,
1
/
s
(
Λ
*
∖
{
0
}
)
≤
ϵ, where ρ
ℋ
,
1
/
s
(
·
) is the Gaussian function (centered at 0) for 1
/
s,  Λ
⊂
ℋ spans ℋ, and Λ
* is the dual lattice of Λ.In this paper, we also use the following fact.Lemma 3 (see [18, 29]).
Forϵ
∈
(
0,1
), s
≥
η
ϵ
(
Λ
), and c
∈
span
⁡
(
Λ
):
(8)
Pr
⁡
[
∥
𝒟
Λ
,
s
,
c
∥
≥
s
·
m
]
≤
2
-
m
·
1
+
ϵ
1
-
ϵ
,
where Λ
⊂
ℝ
m is a lattice.


## 2.2. Basic Algorithms for Lattices

The trapdoor generation algorithmG
e
n
T
r
a
p
(
A
¯
,
H
) proposed by Micciancio and Peikert in 2012 [18] has the following properties.Lemma 4 (see [18]).
There exists a probabilistic polynomial time algorithmG
e
n
T
r
a
p
(
A
¯
,
H
) that takes a parity-check matrix A
¯
∈
ℤ
q
n
×
m
¯, an invertible matrix H
∈
ℤ
q
n
×
n, n
≥
1, m
=
O
(
n
log
⁡
⁡
q
), q
≥
2, and outputs a parity-check matrix A
∈
ℤ
q
n
×
m with its trapdoor T such that(i)
G
e
n
T
r
a
p
(
A
¯
,
H
) uses some fixed primitive matrix G
∈
ℤ
q
n
×
n
k whose columns generate all of ℤ
q
n;
(ii)
G
e
n
T
r
a
p
(
A
¯
,
H
) chooses a matrix T
←
𝒟
ℤ
,
ω
(
log
⁡
⁡
n
)
m
¯
×
n
k, where m
=
m
¯
+
n
k and k
=
O
(
log
⁡
⁡
n
);
(iii)
G
e
n
T
r
a
p
(
A
¯
,
H
) computes A
=
[
A
¯
∥
H
G
-
A
¯
T
]
∈
ℤ
q
n
×
m;
(iv)
the statistical distance between the distribution ofA and the uniform distribution is negligible;
(v)
s
1
(
T
)
=
s
T
·
O
(
m
¯
+
n
k
) holds with an overwhelming probability, where s
1
(
T
) is the maximal singular value of T and s
T
>
0;
(vi)
G
e
n
T
r
a
p
(
A
¯
) means G
e
n
T
r
a
p
(
A
¯
,
I
n
).
The trapdoor Gaussian sampling algorithmS
a
m
p
l
e
D
(
A
,
T
,
H
,
u
,
s
) proposed by Micciancio and Peikert in 2012 [18] has the following properties.Lemma 5 (see [18]).
There exists a probabilistic polynomial time algorithmS
a
m
p
l
e
D
(
A
,
T
,
H
,
u
,
s
) that takes a parity-check matrix A
∈
ℤ
q
n
×
m with its trapdoor T, an invertible matrix H
∈
ℤ
q
n
×
n, a syndrome u
∈
ℤ
q
n, s
=
O
(
n
log
⁡
⁡
q
)
≥
s
G
·
s
1
(
T
) (where s
G
=
2 if q is a power of 2, or s
G
=
5 otherwise), n
≥
1,  m
=
O
(
n
log
⁡
⁡
q
),  q
≥
2, and outputs a vector v such that(i)
S
a
m
p
l
e
D
(
A
,
T
,
H
,
u
,
s
) uses some fixed primitive matrix G
∈
ℤ
q
n
×
n
k whose columns generate all of ℤ
q
n;
(ii)
the statistical distance between the distribution ofv and the distribution of 𝒟
Λ
u
⊥
(
A
)
,
s
·
ω
(
log
⁡
⁡
n
) is negligiblel;
(iii)
S
a
m
p
l
e
D
(
A
,
T
,
u
,
s
) means S
a
m
p
l
e
D
(
A
,
T
,
I
n
,
u
,
s
).
The trapdoor delegation algorithmD
e
l
T
r
a
p
(
A
′
=
[
A
∥
A
1
]
,
T
,
H
′
,
s
′
) proposed by Micciancio and Peikert in 2012 [18] has the following properties.Lemma 6 (see [18]).
There exists a probabilistic polynomial time algorithmD
e
l
T
r
a
p
(
A
′
=
[
A
∥
A
1
]
,
T
,
H
′
,
s
′
) that takes a parity-check matrix A
′
=
[
A
∥
A
1
]
∈
ℤ
q
n
×
(
m
+
n
k
), a trapdoor T corresponding to A, an invertible matrix H
′
∈
ℤ
q
n
×
n, and s
′
≥
η
ϵ
(
Λ
⊥
(
A
)
), where n
≥
1, m
=
O
(
n
log
⁡
⁡
q
), q
≥
2, k
=
O
(
log
⁡
⁡
n
), and outputs a trapdoor T
′ corresponding to A
′
=
[
A
∥
A
1
] such that(i)
D
e
l
T
r
a
p
(
A
′
=
[
A
∥
A
1
]
,
T
,
H
′
,
s
′
) uses some fixed primitive matrix G
∈
ℤ
q
n
×
n
k whose columns generate all of ℤ
q
n;
(ii)
the statistical distance between the distribution ofT
′ and the Gaussian distribution with s
′ is negligible;
(iii)
s
1
(
T
′
)
≤
s
′
·
O
(
m
+
n
k
) holds with an overwhelming probability;
(iv)
D
e
l
T
r
a
p works even if the columns of A
′
=
[
A
∥
A
1
] are randomly permuted;
(v)
D
e
l
T
r
a
p
(
A
′
=
[
A
∥
A
1
]
,
T
,
s
′
) means D
e
l
T
r
a
p
(
A
′
=
[
A
∥
A
1
]
,
T
,
I
n
,
s
′
).


## 2.3. Properties ofℛ
*

We use a set of invertible elements in a certain ringℛ
=
ℤ
q
/
f
(
x
) introduced by Micciancio and Peikert in 2012 [18].Lemma 7 (see [18]).
Letf
(
x
)
=
x
n
+
a
n
-
1
x
n
-
1
+
⋯
+
a
1
x
+
a
0
∈
ℤ
[
x
] be a monic n-degree polynomial. Then, one defines ℛ
* as a set of invertible elements in the ring ℛ
=
ℤ
q
[
x
]
/
f
(
x
) with the following properties:(i)
an arbitrary subset-sum inℛ
* is also an invertible element in ℛ
*;
(ii)
there exists a ring homomorphismh
(
·
)
:
ℛ
*
→
ℤ
q
n
×
n that maps from a
∈
ℛ
* to an invertible matrix H
=
h
(
a
);
(iii)
the number of elements inℛ
* is at most (
p
-
1
)
·
n, where p is the smallest prime dividing q.


## 2.4. Chameleon Hash Function

A family of chameleon hash functionsH
(
·
,
·
)
:
{
0,1
}
*
×
{
0,1
}
m
→
{
0,1
}
h was proposed by Cash et al. in 2010 [15].Lemma 8 (see [15]).
If theS
I
S
q
,
β problem for q
≥
|
m
|
+
4
·
s
2
·
m
·
n
·
ω
(
log
⁡
⁡
n
) and β
=
|
m
|
+
4
·
s
2
·
m is hard, the hash function H
(
·
,
·
)
:
{
0,1
}
*
×
{
0,1
}
m
→
{
0,1
}
h has the trapdoor property and the collision resistance property, where |
m
| is the bit length of the message, h is the bit length of the hash value, s is a Gaussian parameter, n
≥
1, m
=
O
(
n
log
⁡
⁡
q
), and q
≥
2. The properties of H
(
·
,
·
) are as follows.(i)
The trapdoor property. For any H
(
m
,
r
) and m
′, we can sample r
′ with trapdoor information such that H
(
m
,
r
)
=
H
(
m
′
,
r
′
).
(ii)
The collision resistance property. It is hard to find (
m
,
r
) and (
m
′
,
r
′
) without trapdoor information such that H
(
m
,
r
)
=
H
(
m
′
,
r
′
) and (
m
,
r
)
≠
(
m
′
,
r
′
).


## 2.5. Ring Signatures

A ring signature schemeR
S is a triple set of algorithms {
R
S
.
G
e
n
,
R
S
.
S
i
g
n
,
R
S
.
V
r
f
y
}.(i)
R
S
.
G
e
n
(
1
n
): on input of a security parameter n, this algorithm outputs a signing key s
k
i and verification key v
k
i pair.
(ii)
R
S
.
S
i
g
n
(
s
k
i
,
R
,
m
): on input of a signing key s
k
i, a ring R, and a message m, this algorithm outputs a ring signature σ, where R is an ordered set of verification keys.
(iii)
R
S
.
V
r
f
y
(
R
,
m
,
σ
): on input of a ring R, a message m, and a ring signature σ, this algorithm outputs 1 if the ring signature is valid and 0 otherwise.Correctness. A ring signature scheme R
S is correct if, for any valid ring signature σ corresponding to (
R
,
m
), the R
S
.
V
r
f
y
(
R
,
m
,
σ
) algorithm outputs 1 with an overwhelming probability.Generally, ring signatures should be required to satisfy conditions of anonymity and unforgeability. Definitions of anonymity against full key exposure and existential unforgeability with respect to insider corruption were proposed by Bender et al. [4].


## 3. Related Work

In this section, we review the existing ring signature schemes from lattices. In 2010, Brakerski and Kalai proposed the first ring signature scheme from lattices, using ring trapdoor functions [19]. However, the Brakerski-Kalai’s ring signature scheme is only existentially unforgeable under chosen subring attacks; that is, the Brakerski-Kalai’s ring signature scheme does not guarantee that their scheme is existentially unforgeable with respect to insider corruption, because existential unforgeability under chosen subring attacks is a weaker security notion than the existential unforgeability with respect to insider corruption.In 2011, Wang and Sun proposed two ring signature schemes in the random oracle model and in the standard model, using lattice-based delegation techniques [21]. They claimed that Wang-Sun’s ring signature schemes offered existential unforgeability with respect to insider corruption, but Wang-Sun’s ring signature schemes in fact did not. In this section, we discuss the definition of existential unforgeability with respect to insider corruption and show that all of Wang-Sun’s ring signature schemes are not existentially unforgeable with respect to insider corruption.


### 3.1. Existential Unforgeability with respect to Insider Corruption

In 2006, Bender et al. developed the definitions of anonymity and existential unforgeability for ring signatures [4]. Bender et al. developed four kinds of anonymity and three kinds of existential unforgeability, with anonymity against full key exposure and existential unforgeability with respect to insider corruption being the securest of these. The insider corruption means that an adversary can corrupt honest users and obtain their signing keys. Since then, most existing ring signature schemes are based on Bender et al.’s definitions. In 2011, Wang and Sun proposed two ring signature schemes and claimed that these two ring signature schemes were existentially unforgeable with respect to insider corruption, so we now discuss existential unforgeability with respect to insider corruption, before concluding that their ring signature schemes are not existentially unforgeable.Existential unforgeability with respect to insider corruption for a ring signature schemeR
S
=
{
R
S
.
G
e
n
,
R
S
.
S
i
g
n
,
R
S
.
V
r
f
y
} is defined by the game G
a
m
e
R
S
,
ℱ
e
u
(
n
) between a challenger 𝒞 and a forger ℱ as follows.(i)
Setup. 𝒞 runs R
S
.
G
e
n
(
1
n
)
t times to obtain {
(
s
k
1
,
v
k
1
)
,
…
,
(
s
k
t
,
v
k
t
)
}. 𝒞 sends an ordered set S
=
{
v
k
1
,
…
,
v
k
t
} of verification keys to ℱ. 𝒞 sets C
U
←
∅, where C
U is a set of corrupted users.
(ii)
Signing Queries. ℱ sends (
e
,
R
,
m
) such that v
k
e
∈
R
∩
S to 𝒞. We note that R may not be a subset of S. 𝒞 runs R
S
.
S
i
g
n
(
s
k
e
,
R
,
m
) to obtain σ and returns it to ℱ.
(iii)
Corruption Queries. ℱ sends i such that v
k
i
∈
S to 𝒞. 𝒞 returns s
k
i to ℱ and adds v
k
i to C
U.
(iv)
Output. ℱ outputs (
R
*
,
m
*
,
σ
*
). If R
S
.
V
r
f
y
(
R
*
,
m
*
,
σ
*
)
=
1, ℱ did not send (
·
,
R
*
,
m
*
) to 𝒞, and R
*
⊆
S
∖
C
U, then ℱ wins the game G
a
m
e
R
S
,
ℱ
e
u
(
n
).The advantage ofℱ in the above game is defined as follows:
(9)
A
d
v
R
S
,
ℱ
e
u
(
n
)
=
Pr
⁡
[
ℱ
wins
the
game
G
a
m
e
R
S
,
ℱ
e
u
(
n
)
]
.


### 3.2. Analysis of Wang-Sun’s Ring Signature Schemes

Here, we show that Wang-Sun’s ring signature schemes are not existentially unforgeable with respect to insider corruption. Wang-Sun’s ring signature schemeW
S
.
R
S
=
{
W
S
.
G
e
n
,
W
S
.
S
i
g
n
,
W
S
.
V
r
f
y
} in the random oracle model consists of the following algorithms.(i)
W
S
.
G
e
n
(
1
n
): this algorithm runs the trapdoor generation algorithm D
e
l
T
r
a
p to obtain (
A
i
,
T
i
). The signing key is s
k
i
=
T
i
∈
ℤ
m
×
m and the verification key is v
k
i
=
A
i
∈
ℤ
q
n
×
m.
(ii)
W
S
.
S
i
g
n
(
s
k
i
,
R
,
m
): on input of s
k
i
=
T
i, R
=
{
v
k
1
,
…
,
v
k
l
}
=
{
A
1
,
…
,
A
l
}, and m, this algorithm computes u
=
H
(
m
)
∈
ℤ
q
n and constructs A
R
=
[
A
1
∥
⋯
∥
A
l
]
∈
ℤ
q
n
×
l
m, where H
(
·
) is a hash function. The algorithm samples and outputs v
∈
ℤ
l
m from 𝒟
Λ
u
⊥
(
A
R
)
,
s using the Gaussian sampling algorithm S
a
m
p
l
e
D and the trapdoor delegation algorithm D
e
l
T
r
a
p with s
k
i
=
T
i, where s is a Gaussian parameter.
(iii)
W
S
.
V
r
f
y
(
R
,
m
,
v
): on input of R
=
{
v
k
1
,
…
,
v
k
l
}
=
{
A
1
,
…
,
A
l
}, m, and v, this algorithm constructs A
R
=
[
A
1
∥
⋯
∥
A
l
]
∈
ℤ
q
n
×
l
m. Then, the algorithm outputs 1 if
(i)
∥
v
∥
≤
s
·
l
m;
(ii)
A
R
·
v
=
H
(
m
)
(
mod
⁡
q
).
Otherwise, the algorithm outputs0.We now show that we can construct a forgerℱ mounting an existential forgery attack with a nonnegligible success probability. Let 𝒞 be a challenger in the game of existential unforgeability. ℱ sends (
e
,
R
,
m
*
) to 𝒞 in theSigning Queries phase and receives a ring signature v corresponding to (
e
,
R
,
m
*
). Then, ℱ makes a forgery (
R
*
,
m
*
,
v
*
) such that R
* is a proper (or strict) superset of R (i.e.; R
⊊
R
*).For example,ℱ chooses R
=
(
v
k
1
,
v
k
3
) in theSigning Queries phase. In this case, A
R
=
[
A
1
∥
A
3
]
∈
ℤ
n
×
2
m. ℱ chooses R
*
=
(
v
k
1
,
v
k
3
,
v
k
4
) in theOutput phase. In this case, A
R
*
=
[
A
1
∥
A
3
∥
A
4
]
∈
ℤ
n
×
3
m. Then, ℱ constructs v
*
=
[
v
0
] by inserting zeros into v, where v
∈
ℤ
2
m and 0
∈
ℤ
m. Note that the following equation holds:
(10)
[
A
1
∥
A
3
∥
A
4
]
·
v
*
=
[
A
1
∥
A
3
∥
A
4
]
·
[
v
0
]
[
A
1
∥
A
3
∥
A
4
]
·
v
*
=
[
A
1
∥
A
3
]
·
v
[
A
1
∥
A
3
∥
A
4
]
·
v
*
=
H
(
m
*
)
(
mod
⁡
q
)
.
Clearly, the Euclidean norms of v and v
* are the same, and the tuple (
R
*
,
m
*
,
v
*
) satisfies the verification algorithm (i.e.; W
S
.
V
r
f
y
(
R
*
,
m
*
,
v
*
)
=
1). Therefore, Wang-Sun’s ring signature scheme in the random oracle model is not existentially unforgeable with respect to insider corruption. Wang-Sun’s ring signature scheme in the standard model can similarly be broken.


## 3.1. Existential Unforgeability with respect to Insider Corruption

In 2006, Bender et al. developed the definitions of anonymity and existential unforgeability for ring signatures [4]. Bender et al. developed four kinds of anonymity and three kinds of existential unforgeability, with anonymity against full key exposure and existential unforgeability with respect to insider corruption being the securest of these. The insider corruption means that an adversary can corrupt honest users and obtain their signing keys. Since then, most existing ring signature schemes are based on Bender et al.’s definitions. In 2011, Wang and Sun proposed two ring signature schemes and claimed that these two ring signature schemes were existentially unforgeable with respect to insider corruption, so we now discuss existential unforgeability with respect to insider corruption, before concluding that their ring signature schemes are not existentially unforgeable.Existential unforgeability with respect to insider corruption for a ring signature schemeR
S
=
{
R
S
.
G
e
n
,
R
S
.
S
i
g
n
,
R
S
.
V
r
f
y
} is defined by the game G
a
m
e
R
S
,
ℱ
e
u
(
n
) between a challenger 𝒞 and a forger ℱ as follows.(i)
Setup. 𝒞 runs R
S
.
G
e
n
(
1
n
)
t times to obtain {
(
s
k
1
,
v
k
1
)
,
…
,
(
s
k
t
,
v
k
t
)
}. 𝒞 sends an ordered set S
=
{
v
k
1
,
…
,
v
k
t
} of verification keys to ℱ. 𝒞 sets C
U
←
∅, where C
U is a set of corrupted users.
(ii)
Signing Queries. ℱ sends (
e
,
R
,
m
) such that v
k
e
∈
R
∩
S to 𝒞. We note that R may not be a subset of S. 𝒞 runs R
S
.
S
i
g
n
(
s
k
e
,
R
,
m
) to obtain σ and returns it to ℱ.
(iii)
Corruption Queries. ℱ sends i such that v
k
i
∈
S to 𝒞. 𝒞 returns s
k
i to ℱ and adds v
k
i to C
U.
(iv)
Output. ℱ outputs (
R
*
,
m
*
,
σ
*
). If R
S
.
V
r
f
y
(
R
*
,
m
*
,
σ
*
)
=
1, ℱ did not send (
·
,
R
*
,
m
*
) to 𝒞, and R
*
⊆
S
∖
C
U, then ℱ wins the game G
a
m
e
R
S
,
ℱ
e
u
(
n
).The advantage ofℱ in the above game is defined as follows:
(9)
A
d
v
R
S
,
ℱ
e
u
(
n
)
=
Pr
⁡
[
ℱ
wins
the
game
G
a
m
e
R
S
,
ℱ
e
u
(
n
)
]
.


## 3.2. Analysis of Wang-Sun’s Ring Signature Schemes

Here, we show that Wang-Sun’s ring signature schemes are not existentially unforgeable with respect to insider corruption. Wang-Sun’s ring signature schemeW
S
.
R
S
=
{
W
S
.
G
e
n
,
W
S
.
S
i
g
n
,
W
S
.
V
r
f
y
} in the random oracle model consists of the following algorithms.(i)
W
S
.
G
e
n
(
1
n
): this algorithm runs the trapdoor generation algorithm D
e
l
T
r
a
p to obtain (
A
i
,
T
i
). The signing key is s
k
i
=
T
i
∈
ℤ
m
×
m and the verification key is v
k
i
=
A
i
∈
ℤ
q
n
×
m.
(ii)
W
S
.
S
i
g
n
(
s
k
i
,
R
,
m
): on input of s
k
i
=
T
i, R
=
{
v
k
1
,
…
,
v
k
l
}
=
{
A
1
,
…
,
A
l
}, and m, this algorithm computes u
=
H
(
m
)
∈
ℤ
q
n and constructs A
R
=
[
A
1
∥
⋯
∥
A
l
]
∈
ℤ
q
n
×
l
m, where H
(
·
) is a hash function. The algorithm samples and outputs v
∈
ℤ
l
m from 𝒟
Λ
u
⊥
(
A
R
)
,
s using the Gaussian sampling algorithm S
a
m
p
l
e
D and the trapdoor delegation algorithm D
e
l
T
r
a
p with s
k
i
=
T
i, where s is a Gaussian parameter.
(iii)
W
S
.
V
r
f
y
(
R
,
m
,
v
): on input of R
=
{
v
k
1
,
…
,
v
k
l
}
=
{
A
1
,
…
,
A
l
}, m, and v, this algorithm constructs A
R
=
[
A
1
∥
⋯
∥
A
l
]
∈
ℤ
q
n
×
l
m. Then, the algorithm outputs 1 if
(i)
∥
v
∥
≤
s
·
l
m;
(ii)
A
R
·
v
=
H
(
m
)
(
mod
⁡
q
).
Otherwise, the algorithm outputs0.We now show that we can construct a forgerℱ mounting an existential forgery attack with a nonnegligible success probability. Let 𝒞 be a challenger in the game of existential unforgeability. ℱ sends (
e
,
R
,
m
*
) to 𝒞 in theSigning Queries phase and receives a ring signature v corresponding to (
e
,
R
,
m
*
). Then, ℱ makes a forgery (
R
*
,
m
*
,
v
*
) such that R
* is a proper (or strict) superset of R (i.e.; R
⊊
R
*).For example,ℱ chooses R
=
(
v
k
1
,
v
k
3
) in theSigning Queries phase. In this case, A
R
=
[
A
1
∥
A
3
]
∈
ℤ
n
×
2
m. ℱ chooses R
*
=
(
v
k
1
,
v
k
3
,
v
k
4
) in theOutput phase. In this case, A
R
*
=
[
A
1
∥
A
3
∥
A
4
]
∈
ℤ
n
×
3
m. Then, ℱ constructs v
*
=
[
v
0
] by inserting zeros into v, where v
∈
ℤ
2
m and 0
∈
ℤ
m. Note that the following equation holds:
(10)
[
A
1
∥
A
3
∥
A
4
]
·
v
*
=
[
A
1
∥
A
3
∥
A
4
]
·
[
v
0
]
[
A
1
∥
A
3
∥
A
4
]
·
v
*
=
[
A
1
∥
A
3
]
·
v
[
A
1
∥
A
3
∥
A
4
]
·
v
*
=
H
(
m
*
)
(
mod
⁡
q
)
.
Clearly, the Euclidean norms of v and v
* are the same, and the tuple (
R
*
,
m
*
,
v
*
) satisfies the verification algorithm (i.e.; W
S
.
V
r
f
y
(
R
*
,
m
*
,
v
*
)
=
1). Therefore, Wang-Sun’s ring signature scheme in the random oracle model is not existentially unforgeable with respect to insider corruption. Wang-Sun’s ring signature scheme in the standard model can similarly be broken.


## 4. Security Model of Ring Signatures

### 4.1. Anonymity against Full Key Exposure

We first recall the definition of anonymity against full key exposure in [4]. Anonymity against full key exposure for a ring signature scheme R
S
=
{
R
S
.
G
e
n
,
R
S
.
S
i
g
n
,
R
S
.
V
r
f
y
} is defined by the following game G
a
m
e
R
S
,
𝒜
a
n
(
n
) between a challenger 𝒞 and an adversary 𝒜.(i)
Setup. 𝒞 runs R
S
.
G
e
n
(
1
n
)
t times to obtain {
(
s
k
1
,
v
k
1
)
,
…
,
(
s
k
t
,
v
k
t
)
}. 𝒞 sends an ordered set S
=
{
v
k
1
,
…
,
v
k
t
} of verification keys to 𝒜. 𝒞 sets C
U
←
∅, where C
U is a set of corrupted users.
(ii)
Signing Queries. 𝒜 sends (
e
,
R
,
m
) such that v
k
e
∈
R
∩
S to 𝒞. We note that R may not be a subset of S. 𝒞 runs R
S
.
S
i
g
n
(
s
k
e
,
R
,
m
) to obtain σ and returns σ to 𝒜.
(iii)
Corruption Queries. 𝒜 sends i such that v
k
i
∈
S to 𝒞. 𝒞 returns s
k
i to 𝒜 and adds v
k
i to C
U.
(iv)
Challenge. 𝒜 sends (
e
0
,
e
1
,
R
,
m
) such that v
k
e
0
∈
R
∩
S and v
k
e
1
∈
R
∩
S to 𝒞. We note that R may not be a subset of S. 𝒞 randomly chooses a bit b and returns σ
←
R
S
.
S
i
g
n
(
s
k
e
b
,
R
,
m
) to 𝒜.
(v)
Output. 𝒜 guesses and outputs b
′. If b
=
b
′, then 𝒜 wins the game G
a
m
e
R
S
,
𝒜
a
n
(
n
). We note that v
k
e
0 or v
k
e
1 may be in C
U.The advantage of𝒜 in the above game is defined as follows:
(11)
A
d
v
R
S
,
𝒜
a
n
(
n
)
=
Pr
⁡
[
ℱ
wins
the
game
G
a
m
e
R
S
,
𝒜
a
n
(
n
)
]
-
1
2
.


### 4.2. Strong Unforgeability with respect to Insider Corruption

We propose strong unforgeability with respect to insider corruption for ring signatures. This is a stronger condition than existential unforgeability. The strong unforgeability of ring signatures is based on the existential unforgeability defined in [4].Strong unforgeability with respect to insider corruption for a ring signature schemeR
S
=
{
R
S
.
G
e
n
,
R
S
.
S
i
g
n
,
R
S
.
V
r
f
y
} is defined by the following game G
a
m
e
R
S
,
ℱ
s
u between a challenger 𝒞 and a forger ℱ.(i)
Setup. 𝒞 runs R
S
.
G
e
n
(
1
n
)
t times to obtain {
(
s
k
1
,
v
k
1
)
,
…
,
(
s
k
t
,
v
k
t
)
}. 𝒞 sends an ordered set S
=
{
v
k
1
,
…
,
v
k
t
} of verification keys to ℱ. 𝒞 sets a set of corrupted users C
U
←
∅.
(ii)
Signing Queries. For 1
≤
i
≤
q
s, ℱ sends (
e
i
,
R
i
,
m
i
) such that v
k
e
i
∈
R
i
∩
S to 𝒞. We note that R
i may not be a subset of S. 𝒞 runs R
S
.
S
i
g
n
(
s
k
e
i
,
R
i
,
m
i
) to obtain σ
i and returns σ
i to ℱ.
(iii)
Corruption Queries. For 1
≤
j
≤
t, ℱ sends j such that v
k
j
∈
S to 𝒞. 𝒞 returns s
k
j to ℱ and adds v
k
j to C
U.
(iv)
Output. ℱ outputs (
R
*
,
m
*
,
σ
*
). If R
S
.
V
r
f
y
(
R
*
,
m
*
,
σ
*
)
=
1, σ
* is not made for (
R
*
,
m
*
) through signing queries, and R
*
⊆
S
∖
C
U, then ℱ wins the game G
a
m
e
R
S
,
ℱ
s
u
(
n
).The advantage ofℱ in the above game is defined as follows:
(12)
A
d
v
R
S
,
ℱ
s
u
(
n
)
=
Pr
⁡
[
ℱ
wins
the
game
G
a
m
e
R
S
,
ℱ
s
u
(
n
)
]
.Note thatℱ can send (
·
,
R
*
,
m
*
) in theSigning Queries phase of the game, whereas ℱ cannot send (
·
,
R
*
,
m
*
) in the existential unforgeability game.


## 4.1. Anonymity against Full Key Exposure

We first recall the definition of anonymity against full key exposure in [4]. Anonymity against full key exposure for a ring signature scheme R
S
=
{
R
S
.
G
e
n
,
R
S
.
S
i
g
n
,
R
S
.
V
r
f
y
} is defined by the following game G
a
m
e
R
S
,
𝒜
a
n
(
n
) between a challenger 𝒞 and an adversary 𝒜.(i)
Setup. 𝒞 runs R
S
.
G
e
n
(
1
n
)
t times to obtain {
(
s
k
1
,
v
k
1
)
,
…
,
(
s
k
t
,
v
k
t
)
}. 𝒞 sends an ordered set S
=
{
v
k
1
,
…
,
v
k
t
} of verification keys to 𝒜. 𝒞 sets C
U
←
∅, where C
U is a set of corrupted users.
(ii)
Signing Queries. 𝒜 sends (
e
,
R
,
m
) such that v
k
e
∈
R
∩
S to 𝒞. We note that R may not be a subset of S. 𝒞 runs R
S
.
S
i
g
n
(
s
k
e
,
R
,
m
) to obtain σ and returns σ to 𝒜.
(iii)
Corruption Queries. 𝒜 sends i such that v
k
i
∈
S to 𝒞. 𝒞 returns s
k
i to 𝒜 and adds v
k
i to C
U.
(iv)
Challenge. 𝒜 sends (
e
0
,
e
1
,
R
,
m
) such that v
k
e
0
∈
R
∩
S and v
k
e
1
∈
R
∩
S to 𝒞. We note that R may not be a subset of S. 𝒞 randomly chooses a bit b and returns σ
←
R
S
.
S
i
g
n
(
s
k
e
b
,
R
,
m
) to 𝒜.
(v)
Output. 𝒜 guesses and outputs b
′. If b
=
b
′, then 𝒜 wins the game G
a
m
e
R
S
,
𝒜
a
n
(
n
). We note that v
k
e
0 or v
k
e
1 may be in C
U.The advantage of𝒜 in the above game is defined as follows:
(11)
A
d
v
R
S
,
𝒜
a
n
(
n
)
=
Pr
⁡
[
ℱ
wins
the
game
G
a
m
e
R
S
,
𝒜
a
n
(
n
)
]
-
1
2
.


## 4.2. Strong Unforgeability with respect to Insider Corruption

We propose strong unforgeability with respect to insider corruption for ring signatures. This is a stronger condition than existential unforgeability. The strong unforgeability of ring signatures is based on the existential unforgeability defined in [4].Strong unforgeability with respect to insider corruption for a ring signature schemeR
S
=
{
R
S
.
G
e
n
,
R
S
.
S
i
g
n
,
R
S
.
V
r
f
y
} is defined by the following game G
a
m
e
R
S
,
ℱ
s
u between a challenger 𝒞 and a forger ℱ.(i)
Setup. 𝒞 runs R
S
.
G
e
n
(
1
n
)
t times to obtain {
(
s
k
1
,
v
k
1
)
,
…
,
(
s
k
t
,
v
k
t
)
}. 𝒞 sends an ordered set S
=
{
v
k
1
,
…
,
v
k
t
} of verification keys to ℱ. 𝒞 sets a set of corrupted users C
U
←
∅.
(ii)
Signing Queries. For 1
≤
i
≤
q
s, ℱ sends (
e
i
,
R
i
,
m
i
) such that v
k
e
i
∈
R
i
∩
S to 𝒞. We note that R
i may not be a subset of S. 𝒞 runs R
S
.
S
i
g
n
(
s
k
e
i
,
R
i
,
m
i
) to obtain σ
i and returns σ
i to ℱ.
(iii)
Corruption Queries. For 1
≤
j
≤
t, ℱ sends j such that v
k
j
∈
S to 𝒞. 𝒞 returns s
k
j to ℱ and adds v
k
j to C
U.
(iv)
Output. ℱ outputs (
R
*
,
m
*
,
σ
*
). If R
S
.
V
r
f
y
(
R
*
,
m
*
,
σ
*
)
=
1, σ
* is not made for (
R
*
,
m
*
) through signing queries, and R
*
⊆
S
∖
C
U, then ℱ wins the game G
a
m
e
R
S
,
ℱ
s
u
(
n
).The advantage ofℱ in the above game is defined as follows:
(12)
A
d
v
R
S
,
ℱ
s
u
(
n
)
=
Pr
⁡
[
ℱ
wins
the
game
G
a
m
e
R
S
,
ℱ
s
u
(
n
)
]
.Note thatℱ can send (
·
,
R
*
,
m
*
) in theSigning Queries phase of the game, whereas ℱ cannot send (
·
,
R
*
,
m
*
) in the existential unforgeability game.


## 5. Our Construction

### 5.1. Sets and Parameters

In this section, we propose our ring signature schemeS
R
S
=
{
S
R
S
.
G
e
n
,
S
R
S
.
S
i
g
n
,
S
R
S
.
V
r
f
y
} in the standard model. First, we define the following parameters.(i)
n is a security parameter.
(ii)
m
=
m
¯
+
(
l
+
1
)
·
n
k is the dimension of the ring signature, where m
¯
=
O
(
n
k
), k
=
O
(
log
⁡
⁡
n
), and l is the number of ring users.
(iii)
h
≤
(
p
-
1
)
·
n is the bit length of a hash value, where p is the smallest prime dividing q. That is, a hash value space is {
0,1
}
h.
(iv)
s
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
3 is a parameter used in the S
a
m
p
l
e
D algorithm and s
′
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2 is a parameter used in the D
e
l
T
r
a
p algorithm.
(v)
q
=
O
(
h
·
l
·
n
5
/
2
·
k
2
)
·
ω
(
log
⁡
⁡
n
)
5 and β
=
O
(
h
·
l
·
n
2
·
k
2
)
·
ω
(
log
⁡
⁡
n
)
4 are parameters for the SIS problem and SIVP.
(vi)
G
∈
ℤ
q
n
×
n
k is a primitive matrix whose columns generate all of ℤ
q
n.
(vii)
p
a
r
a
m
s
=
{
G
,
A
¯
,
C
0
,
…
,
C
h
,
u
,
H
(
·
,
·
)
} are public parameters, where A
¯
←
ℤ
q
n
×
m
¯, C
0
,
…
,
C
h
←
ℤ
q
n
×
n
k, u
←
ℤ
q
n, and H
(
·
,
·
)
:
{
0,1
}
*
×
{
0,1
}
m
→
{
0,1
}
h is a hash function.


### 5.2. Our Ring Signature Scheme

Our ring signature schemeS
R
S
=
{
S
R
S
.
G
e
n
,
S
R
S
.
S
i
g
n
,
S
R
S
.
V
r
f
y
} consists of the following algorithms.(i)
S
R
S
.
G
e
n
(
1
n
): on input of the security parameter n, this algorithm chooses T
i
←
𝒟
ℤ
,
ω
(
log
⁡
⁡
n
)
m
¯
×
n
k and computes A
i
=
[
G
-
A
¯
T
i
]. The signing key is s
k
i
=
T
i and the verification key is v
k
i
=
A
i.
(ii)
S
R
S
.
S
i
g
n
(
s
k
i
,
R
,
m
): on input of s
k
i
=
T
i, R
=
{
v
k
1
,
…
,
v
k
l
}
=
{
A
1
,
…
,
A
l
}, and m, this algorithm computes H
(
R
∥
m
,
r
)
=
μ
=
(
μ
1
,
…
,
μ
h
)
∈
{
0,1
}
h and C
μ
=
C
0
+
∑
j
=
1
h
‍
μ
j
C
j
∈
ℤ
q
n
×
n
k, where r
←
{
0,1
}
m and μ
j is the jth element in μ. The algorithm constructs A
R
,
μ
=
[
A
¯
∥
A
R
∥
C
μ
]
∈
ℤ
q
n
×
m, where A
R
=
[
A
1
∥
⋯
∥
A
l
] is the ordered concatenation of matrices in R. The algorithm samples v
∈
ℤ
m from 𝒟
Λ
u
⊥
(
A
R
,
μ
)
,
s using the S
a
m
p
l
e
D and D
e
l
T
r
a
p algorithms with s
k
i
=
T
i. The algorithm outputs a ring signature σ
=
(
v
,
r
).
(iii)
S
R
S
.
V
r
f
y
(
R
,
m
,
σ
): on input of R
=
{
v
k
1
,
…
,
v
k
l
}
=
{
A
1
,
…
,
A
l
}, m, and σ
=
(
v
,
r
), this algorithm computes H
(
R
∥
m
,
r
)
=
μ
=
(
μ
1
,
…
,
μ
h
)
∈
{
0,1
}
h and C
μ
=
C
0
+
∑
j
=
1
h
‍
μ
j
C
j
∈
ℤ
q
n
×
n
k, where μ
j is the jth element in μ. The algorithm constructs A
R
,
μ
=
[
A
¯
∥
A
R
∥
C
μ
]
∈
ℤ
q
n
×
m, where A
R
=
[
A
1
∥
⋯
∥
A
l
] is the ordered concatenation of matrices in R. Then, the algorithm outputs 1 if
(i)
A
R
,
μ
·
v
=
u
(
mod
⁡
q
);
(ii)
∥
v
∥
≤
s
·
m.
Otherwise, the algorithm outputs0.Correctness. We show that our ring signature scheme S
R
S is correct. The S
R
S
.
S
i
g
n
(
s
k
i
,
R
,
m
) algorithm can sample v from a distribution whose statistical distance from 𝒟
Λ
u
⊥
(
A
R
,
μ
)
,
s is negligible using the S
a
m
p
l
e
D and D
e
l
T
r
a
p algorithms with T
i such that A
R
,
μ
·
v
=
u
(
mod
⁡
q
) and ∥
v
∥
≤
s
·
m with an overwhelming probability [15, 18, 27]. Therefore, our ring signature scheme S
R
S is correct.


### 5.3. Anonymity against Full Key Exposure of Our Construction

We now show that our ring signature schemeS
R
S is anonymous against full key exposure in the standard model.Theorem 9.
S
R
S
=
{
S
R
S
.
G
e
n
,
S
R
S
.
S
i
g
n
,
S
R
S
.
V
r
f
y
} is anonymous against full key exposure in the standard model.Proof of Theorem9.
Recall that(
e
0
,
e
1
,
R
,
m
) is sent by 𝒜 in theChallenge phase of the game of anonymity. A challenge signature σ
b
=
(
v
b
,
r
b
)
←
R
S
.
S
i
g
n
(
s
k
e
b
,
R
,
m
) is then returned to 𝒜.
The signing algorithm withs
k
e
i
=
T
i samples v
i from a distribution whose statistical distance from 𝒟
Λ
u
⊥
(
A
R
,
μ
)
,
s is negligible. Therefore, the statistical distance between the distribution of v
0 and the distribution of v
1 is negligible. We also note that the distributions of r
0 and r
1 are the same. Therefore, the advantage A
d
v
S
R
S
,
𝒜
a
n of 𝒜 is negligible.


### 5.4. Strong Unforgeability with respect to Insider Corruption of Our Construction

We now show that our ring signature schemeS
R
S is strongly unforgeable with respect to insider corruption in the standard model.Theorem 10.
If theS
I
S
q
,
β problem for q
≥
|
R
|
+
|
m
|
+
4
·
s
2
·
m
·
n
·
ω
(
log
⁡
⁡
n
) and β
=
|
R
|
+
|
m
|
+
4
·
s
2
·
m and q
≥
O
(
h
·
l
·
n
5
/
2
·
k
2
)
·
ω
(
log
⁡
⁡
n
)
5 and β
=
O
(
h
·
l
·
n
2
·
k
2
)
·
ω
(
log
⁡
⁡
n
)
4 is hard, the ring signature scheme S
R
S
=
{
S
R
S
.
G
e
n
,
S
R
S
.
S
i
g
n
,
S
R
S
.
V
r
f
y
} proposed here is strongly unforgeable with respect to insider corruption in the standard model, where |
R
| is the ring size and |
m
| is the message bit length.Proof of Theorem10.
We show that, if a forger existsℱ with a nonnegligible probability, we can construct an algorithm 𝒜 solving the SI
S
q
,
β problem.
Assume thatℱ outputs a forgery (
R
*
,
m
*
,
σ
*
=
(
v
*
,
r
*
)
) in the game of strong unforgeability. Then, there exist three cases.(1)
μ
*
=
H
(
R
*
∥
m
*
,
r
*
)
=
H
(
R
i
∥
m
i
,
r
i
) for some i
∈
[
1
,
q
s
] such that R
*
≠
R
i, m
*
≠
m
i, or r
*
≠
r
i.
(2)
μ
*
=
H
(
R
*
∥
m
*
,
r
*
)
=
H
(
R
i
∥
m
i
,
r
i
) for some i
∈
[
1
,
q
s
] such that R
*
=
R
i, m
*
=
m
i, and r
*
=
r
i.
(3)
μ
*
=
H
(
R
*
∥
m
*
,
r
*
)
≠
H
(
R
i
∥
m
i
,
r
i
) for all i
∈
[
1
,
q
s
].
Note that the number of signing queries is at mostq
s, and (
R
i
,
m
i
,
r
i
) are used in the ith signing queries.
For the first case, we can construct𝒜 conducting a collision attack on H
(
·
,
·
) using ℱ. 𝒜 simulates the game of strong unforgeability with ℱ as follows.(i)
Setup. 𝒜 takes a hash function H
(
·
,
·
) as input and chooses {
G
,
A
¯
,
C
0
,
…
,
C
h
,
u
} at random. For 1
≤
i
≤
t, 𝒜 chooses T
i
←
𝒟
ℤ
,
ω
(
log
⁡
⁡
n
)
m
¯
×
n
k and computes A
i
=
[
G
-
A
¯
T
i
]. 𝒜 sends {
p
a
r
a
m
s
,
S
} to ℱ, where p
a
r
a
m
s
=
{
G
,
A
¯
,
C
0
,
…
,
C
h
,
u
,
H
(
·
,
·
)
} and S
=
{
v
k
1
,
…
,
v
k
t
}
=
{
A
1
,
…
,
A
t
}. 𝒜 sets C
U
←
∅, where C
U is a set of corrupted users.
(ii)
Signing Queries.  ℱ sends (
e
,
R
,
m
) such that v
k
e
∈
R
∩
S to 𝒜. 𝒜 chooses r
←
{
0,1
}
m and computes H
(
R
∥
m
,
r
)
=
μ
=
(
μ
1
,
…
,
μ
h
)
∈
{
0,1
}
h. A
R
,
μ is represented as [
A
¯
∥
A
R
∥
C
μ
], where A
R is the ordered concatenation of matrices in R, C
μ
=
C
0
+
∑
j
=
1
h
‍
μ
j
C
j
∈
ℤ
q
n
×
n
k, and μ
j is the jth element in μ.
The maximal singular value ofs
k
e
=
T
e (where s
T
>
0) is as follows:
(13)
s
1
(
T
e
)
=
s
T
·
O
(
m
¯
+
n
k
)
s
1
(
T
e
)
=
s
T
·
O
(
n
k
+
n
k
)
s
1
(
T
e
)
=
s
T
·
O
(
n
k
)
.
𝒜 calculates T
←
D
e
l
T
r
a
p
(
A
R
,
μ
,
T
e
,
s
′
), where s
′
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2.
Then, the maximal singular value ofT is as follows:
(14)
s
1
(
T
)
≤
s
′
·
O
(
m
¯
+
n
k
+
l
n
k
)
s
1
(
T
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2
·
O
(
n
k
+
n
k
+
l
n
k
)
s
1
(
T
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2
·
O
(
n
k
+
l
n
k
)
s
1
(
T
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2
·
O
(
l
n
k
)
s
1
(
T
)
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
2
.
𝒜 calculates v
←
S
a
m
p
l
e
D
(
A
R
,
μ
,
T
,
u
,
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
2
) from a distribution whose statistical distance from 𝒟
Λ
u
⊥
(
A
R
,
μ
)
,
s is negligible, where s
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
3. 𝒜 returns σ
=
(
v
,
r
) to ℱ.
(iii)
Corruption Queries. ℱ sends i such that v
k
i
∈
S to 𝒜. 𝒜 returns s
k
i
=
T
i to ℱ and adds v
k
i
=
A
i to C
U.
(iv)
Output. 𝒜 outputs (
R
*
,
m
*
,
σ
*
=
(
v
*
,
r
*
)
). For any i, μ
*
=
H
(
R
*
∥
m
*
,
r
*
)
=
H
(
R
i
∥
m
i
,
r
i
)
∈
{
H
(
R
1
∥
m
1
,
r
1
)
,
…
,
H
(
R
q
s
∥
m
q
s
,
r
q
s
)
}, where R
*
≠
R
i, m
*
≠
m
i, or r
*
≠
r
i. 𝒜 outputs two pairs {
(
R
*
∥
m
*
,
r
*
)
,
(
R
i
∥
m
i
,
r
i
)
} as a collision on H
(
·
,
·
).
To reduce the average-caseSIS problem to the worst-case SIVP in lattices, q
≥
β
·
n
·
ω
(
log
⁡
⁡
n
) should hold. Therefore,
(15)
q
≥
β
·
n
·
ω
(
log
⁡
⁡
n
)
q
=
|
R
|
+
|
m
|
+
4
·
s
2
·
m
·
n
·
ω
(
log
⁡
⁡
n
)
.
Naturally,(16)
A
d
v
𝒜
SIS
≥
A
d
v
H
(
·
,
·
)
,
𝒜
c
r
≥
A
d
v
S
R
S
,
ℱ
s
u
.
For the second case, we can construct𝒜 attacking the SI
S
q
,
β problem using ℱ. Assume that the number of corrupted users is at most l. 𝒜 simulates the game of strong unforgeability with ℱ as follows.(i)
Setup. 𝒜 chooses a primitive matrix G
∈
ℤ
q
n
×
n
k. 𝒜 takes as input A
′
∈
ℤ
q
n
×
(
m
¯
+
l
n
k
+
1
) as an SIS instance and parses A
′ as [
A
∥
u
′
]
=
[
A
¯
∥
A
1
*
∥
⋯
∥
A
l
*
∥
u
′
], where A
¯
∈
ℤ
q
n
×
m
¯, A
1
*
,
…
,
A
l
*
∈
ℤ
q
n
×
n
k, and u
′
∈
ℤ
q
n. 𝒜 chooses a chameleon hash function H
(
·
,
·
) with trapdoor information and distinct hash values {
μ
1
,
…
,
μ
q
s
}, where μ
i
←
{
0,1
}
h for 1
≤
i
≤
q
s. 𝒜 randomly selects μ
′
∈
{
μ
1
,
…
,
μ
q
s
}.
For0
≤
j
≤
h, 𝒜 computes H
j as follows:
(17)
H
j
=
{
(
-
1
)
μ
j
′
·
h
(
u
j
)
j
∈
{
1
,
…
,
h
}
-
∑
k
=
1
h
μ
k
′
·
H
k
j
=
0
,
whereμ
j
′ is the jth element in μ
′ and h
(
·
) is a ring homomorphism.
For0
≤
j
≤
h, 𝒜 chooses R
j
←
𝒟
ℤ
,
ω
(
log
⁡
⁡
n
)
m
¯
×
n
k and computes the following:
(18)
C
j
=
H
j
G
-
A
¯
R
j
.
Ifμ
i
=
μ
′, H
0
+
∑
j
=
1
h
‍
μ
i
,
j
H
j
=
0
∈
ℤ
n
×
n, where μ
i
,
j is the jth element in μ
i. Otherwise, H
0
+
∑
j
=
1
h
‍
μ
i
,
j
H
j
≠
0
∈
ℤ
n
×
n is an invertible matrix.
𝒜 chooses v
←
𝒟
ℤ
m
¯
+
(
l
+
1
)
n
k
,
s and computes u
=
[
A
∥
C
μ
′
]
·
v, where C
μ
′
=
C
0
+
∑
j
=
1
h
‍
μ
j
′
C
j and μ
j
′ is the jth element in μ
′.
𝒜 randomly chooses t
=
(
t
1
,
…
,
t
t
)
←
{
0,1
}
t such that the number of 1s in t is l. If t
k
=
1 for 1
≤
k
≤
t, 𝒜 sets A
k
=
A
i
* for 1
≤
i
≤
l in turn. Otherwise, 𝒜 chooses T
k
←
𝒟
ℤ
,
ω
(
log
⁡
⁡
n
)
m
¯
×
n
k and computes A
k
=
[
G
-
A
¯
T
k
].
𝒜 sends {
p
a
r
a
m
s
,
S
} to ℱ, where p
a
r
a
m
s
=
{
G
,
A
¯
,
C
0
,
…
,
C
h
,
u
,
H
(
·
,
·
)
} and S
=
{
v
k
1
,
…
,
v
k
t
}
=
{
A
1
,
…
,
A
t
}. 𝒜 sets C
U
←
∅, where C
U is a set of corrupted users.
(ii)
Signing Queries. For 1
≤
i
≤
q
s, ℱ sends (
e
i
,
R
i
,
m
i
) such that v
k
e
i
∈
R
i
∩
S to 𝒜. 𝒜 samples r
i with trapdoor information such that μ
i
=
H
(
R
i
∥
m
i
,
r
i
).
(1)
Forμ
i
=
μ
′: if A
≠
[
A
¯
∥
A
R
i
], 𝒜 aborts. Otherwise, 𝒜 returns σ
i
=
(
v
,
r
i
) to ℱ. Note that the distributions of v and 𝒟
Λ
u
⊥
(
A
∥
C
μ
′
)
,
s are the same.
(2)
Forμ
i
≠
μ
′: A
R
i
,
μ
i is represented as [
A
¯
∥
A
R
i
∥
H
G
-
A
¯
R
], where H
=
H
0
+
∑
j
=
1
h
‍
μ
i
,
j
H
j
≠
0
∈
ℤ
n
×
n and R
=
R
0
+
∑
j
=
1
h
‍
μ
i
,
j
R
j.
The maximal singular value ofR is as follows:
(19)
s
1
(
R
)
=
h
+
1
·
O
(
m
¯
+
n
k
)
·
ω
(
log
⁡
⁡
n
)
s
1
(
R
)
=
h
+
1
·
O
(
n
k
+
n
k
)
·
ω
(
log
⁡
⁡
n
)
s
1
(
R
)
=
h
+
1
·
O
(
n
k
)
·
ω
(
log
⁡
⁡
n
)
s
1
(
R
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
.
𝒜 calculates R
′
←
D
e
l
T
r
a
p
(
A
R
i
,
μ
i
,
R
,
s
′
), where s
′
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2.
Then, the maximal singular value ofR
′ is as follows:
(20)
s
1
(
R
′
)
≤
s
′
·
O
(
m
¯
+
n
k
+
l
n
k
)
s
1
(
R
′
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2
·
O
(
n
k
+
n
k
+
l
n
k
)
s
1
(
R
′
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2
·
O
(
n
k
+
l
n
k
)
s
1
(
R
′
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2
·
O
(
l
n
k
)
s
1
(
R
′
)
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
2
.
𝒜 calculates v
i
←
S
a
m
p
l
e
D
(
A
R
i
,
μ
i
,
R
′
,
u
,
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
2
) from a distribution whose statistical distance from 𝒟
Λ
u
⊥
(
A
R
i
,
μ
i
)
,
s is negligible, where s
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
3. 𝒜 returns σ
i
=
(
v
i
,
r
i
) to ℱ.
(iii)
Corruption Queries. If ℱ asks for s
k
j, where t
j
=
1, 𝒜 aborts. Otherwise, 𝒜 returns s
k
j
=
T
j and adds v
k
j
=
A
j to C
U.
(iv)
Output. ℱ outputs (
R
*
,
m
*
,
σ
*
=
(
v
*
,
r
*
)
). If μ
*
=
H
(
R
*
∥
m
*
,
r
*
)
≠
μ
′, 𝒜 aborts. Otherwise, A
R
*
,
μ
*
=
[
A
∥
C
μ
′
]
=
[
A
¯
∥
A
1
*
∥
⋯
∥
A
l
*
∥
-
A
¯
R
*
], where H
*
=
H
0
+
∑
j
=
1
h
‍
μ
j
*
H
j
=
0
∈
ℤ
n
×
n and R
*
=
R
0
+
∑
j
=
1
h
‍
μ
j
*
R
j.
Therefore, we obtain the following equation:(21)
[
A
∥
C
μ
′
]
·
v
=
[
A
∥
C
μ
′
]
·
v
*
=
u
(
mod
⁡
q
)
.
From the above equation, we have that(22)
[
A
∥
C
μ
′
]
·
(
v
*
-
v
)
=
[
A
¯
∥
A
1
*
∥
⋯
∥
A
l
*
∥
-
A
¯
R
*
]
·
(
v
*
-
v
)
=
A
[
I
m
¯
-
R
*
I
l
n
k
]
·
(
v
*
-
v
)
=
0
(
mod
⁡
q
)
.
Letz
∈
ℤ
m
¯
+
l
n
k be [
I
m
¯
-
R
*
I
l
n
k
]
·
(
v
*
-
v
) and let z
′
∈
ℤ
m
¯
+
l
n
k
+
1 be [
z
0
]. Then, A
z
=
0
(
mod
⁡
q
) and
(23)
A
′
z
′
=
[
A
∥
u
′
]
[
z
0
]
=
0
(
mod
⁡
q
)
.
𝒜 outputs z
′ as a SIS solution to A
′.The Euclidean norm of v
* is as follows:
(24)
∥
v
*
∥
≤
s
·
m
∥
v
*
∥
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
3
·
m
¯
+
(
l
+
1
)
·
n
k
∥
v
*
∥
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
3
·
O
(
n
k
+
(
l
+
1
)
·
n
k
)
∥
v
*
∥
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
3
·
O
(
l
n
k
)
∥
v
*
∥
=
O
(
h
1
/
2
·
l
·
n
3
/
2
·
k
3
/
2
)
·
ω
(
log
⁡
⁡
n
)
3
.
Because∥
v
∥
=
∥
v
*
∥
=
O
(
h
1
/
2
·
l
·
n
3
/
2
·
k
3
/
2
)
·
ω
(
log
⁡
⁡
n
)
3 and v
*
-
v
≠
0, ∥
z
′
∥
=
∥
z
∥
=
O
(
h
·
l
·
n
2
·
k
2
)
·
ω
(
log
⁡
⁡
n
)
4
=
β.
To reduce the average-caseSIS problem to the worst-case SIVP in lattices, q
≥
β
·
n
·
ω
(
log
⁡
⁡
n
) should hold. Therefore,
(25)
q
≥
β
·
n
·
ω
(
log
⁡
⁡
n
)
q
=
O
(
h
·
l
·
n
2
·
k
2
)
·
ω
(
log
⁡
⁡
n
)
4
·
n
·
ω
(
log
⁡
⁡
n
)
q
=
O
(
h
·
l
·
n
5
/
2
·
k
2
)
·
ω
(
log
⁡
⁡
n
)
5
.
We note that𝒜 succeeds in its forgery if it correctly guesses μ
′ and t. The probability of 𝒜 correctly guessing μ
′ is 1
/
q
s, and the probability of correctly guessing t is 1
/
t
C
l. Therefore,
(26)
A
d
v
𝒜
SIS
≥
1
t
C
l
·
q
s
·
A
d
v
S
R
S
,
ℱ
s
u
,
where t is the number of users and l is the upper bound of the number of corrupted users.
For the third case, we can construct𝒜 attacking the SI
S
q
,
β problem using ℱ. Assume that the number of corrupted users is at most l. 𝒜 simulates the game of strong unforgeability with ℱ as follows.(i)
Setup. 𝒜 chooses a primitive matrix G
∈
ℤ
q
n
×
n
k. 𝒜 takes as input A
′
∈
ℤ
q
n
×
(
m
¯
+
l
n
k
+
1
) as a SIS instance and parses A
′ as [
A
∥
u
]
=
[
A
¯
∥
A
1
*
∥
⋯
∥
A
l
*
∥
u
], where A
¯
∈
ℤ
q
n
×
m
¯,  A
1
*
,
…
,
A
l
*
∈
ℤ
q
n
×
n
k, and u
∈
ℤ
q
n. 𝒜 chooses a chameleon hash function H
(
·
,
·
) with trapdoor information and distinct hash values {
μ
1
,
…
,
μ
q
s
}, where μ
i
←
{
0,1
}
h for 1
≤
i
≤
q
s. 𝒜 constructs a set P of all shortest strings p
∈
{
0,1
}
≤
h such that each element of {
μ
1
,
…
,
μ
q
s
} has no p as a prefix. There exists an efficient algorithm for computing P, and the number of elements in P is at most (
h
-
1
)
·
q
s
+
1 [15, 17, 18]. 𝒜 chooses p from P at random. |
p
|
≤
h, where |
p
| is the bit length of p.
For0
≤
j
≤
h, 𝒜 computes H
j as follows:
(27)
H
j
=
{
h
(
0
)
=
0
j
>
|
p
|
(
-
1
)
p
j
·
h
(
u
j
)
j
∈
{
1
,
…
,
|
p
|
}
-
∑
k
=
1
|
p
|
p
k
·
H
k
j
=
0
,
wherep
j is the jth element in p and h
(
·
) is a ring homomorphism.
For0
≤
j
≤
h, 𝒜 chooses R
j
←
𝒟
ℤ
,
ω
(
log
⁡
⁡
n
)
m
¯
×
n
k and computes the following:
(28)
C
j
=
H
j
G
-
A
¯
R
j
.
If anyμ
i has p as a prefix, H
0
+
∑
j
=
1
h
‍
μ
i
,
j
H
j
=
0
∈
ℤ
n
×
n, where μ
i
,
j is the jth element in μ
i. Otherwise, H
0
+
∑
j
=
1
h
‍
μ
i
,
j
H
j
≠
0
∈
ℤ
n
×
n is an invertible matrix.
𝒜 randomly chooses t
=
(
t
1
,
…
,
t
t
)
←
{
0,1
}
t such that the number of 1s in t is l. If t
k
=
1 for 1
≤
k
≤
t, 𝒜 sets A
k
=
A
i
* for 1
≤
i
≤
l in turn. Otherwise, 𝒜 chooses T
k
←
𝒟
ℤ
,
ω
(
log
⁡
⁡
n
)
m
¯
×
n
k and computes A
k
=
[
G
-
A
¯
T
k
].
𝒜 sends {
p
a
r
a
m
s
,
S
} to ℱ, where p
a
r
a
m
s
=
{
G
,
A
¯
,
C
0
,
…
,
C
h
,
u
,
H
(
·
,
·
)
} and S
=
{
v
k
1
,
…
,
v
k
t
}
=
{
A
1
,
…
,
A
t
}. 𝒜 sets C
U
←
∅, where C
U is a set of corrupted users.
(ii)
Signing Queries. For 1
≤
i
≤
q
s, ℱ sends (
e
i
,
R
i
,
m
i
) such that v
k
e
i
∈
R
i
∩
S to 𝒜. 𝒜 samples r
i with trapdoor information such that μ
i
=
H
(
R
i
∥
m
i
,
r
i
). A
R
i
,
μ
i is represented as [
A
¯
∥
A
R
i
∥
H
G
-
A
¯
R
], where H
=
H
0
+
∑
j
=
1
h
‍
μ
i
,
j
H
j
≠
0
∈
ℤ
n
×
n and R
=
R
0
+
∑
j
=
1
h
‍
μ
i
,
j
R
j.
The maximal singular value ofR is as follows:
(29)
s
1
(
R
)
=
h
+
1
·
O
(
m
¯
+
n
k
)
·
ω
(
log
⁡
⁡
n
)
s
1
(
R
)
=
h
+
1
·
O
(
n
k
+
n
k
)
·
ω
(
log
⁡
⁡
n
)
s
1
(
R
)
=
h
+
1
·
O
(
n
k
)
·
ω
(
log
⁡
⁡
n
)
s
1
(
R
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
.
𝒜 calculates R
′
←
D
e
l
T
r
a
p
(
A
R
i
,
μ
i
,
R
,
s
′
), where s
′
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2.
Then, the maximal singular value ofR
′ is as follows:
(30)
s
1
(
R
′
)
≤
s
′
·
O
(
m
¯
+
n
k
+
l
n
k
)
s
1
(
R
′
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2
·
O
(
n
k
+
n
k
+
l
n
k
)
s
1
(
R
′
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2
·
O
(
n
k
+
l
n
k
)
s
1
(
R
′
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2
·
O
(
l
n
k
)
s
1
(
R
′
)
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
2
.
𝒜 calculates v
i
←
S
a
m
p
l
e
D
(
A
R
i
,
μ
i
,
R
′
,
u
,
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
2
) from a distribution whose statistical distance from 𝒟
Λ
u
⊥
(
A
R
i
,
μ
i
)
,
s is negligible, where s
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
3. 𝒜 returns σ
i
=
(
v
i
,
r
i
) to ℱ.
(iii)
Corruption Queries. If ℱ asks for s
k
i, where t
i
=
1, 𝒜 aborts. Otherwise, 𝒜 returns s
k
i
=
T
i and adds v
k
i
=
A
i to C
U.
(iv)
Output. ℱ outputs (
R
*
,
m
*
,
σ
*
=
(
v
*
,
r
*
)
). If μ
*
=
H
(
R
*
∥
m
*
,
r
*
) has no p as a prefix or A
≠
[
A
¯
∥
A
R
*
], 𝒜 aborts. Otherwise, A
R
*
,
μ
* is represented as [
A
¯
∥
A
R
*
∥
-
A
¯
R
*
], where H
*
=
H
0
+
∑
j
=
1
h
‍
μ
j
*
H
j
=
0
∈
ℤ
n
×
n and R
*
=
R
0
+
∑
j
=
1
h
‍
μ
j
*
R
j. Therefore, we obtain the following equation:
(31)
A
R
*
,
μ
*
·
v
*
=
[
A
¯
∥
A
R
*
∥
-
A
¯
R
*
]
·
v
*
A
R
*
,
μ
*
·
v
*
=
[
A
¯
∥
A
R
*
]
[
I
m
¯
-
R
*
I
l
n
k
]
·
v
*
A
R
*
,
μ
*
·
v
*
=
A
·
[
I
m
¯
-
R
*
I
l
n
k
]
·
v
*
A
R
*
,
μ
*
·
v
*
=
u
(
mod
⁡
q
)
.
Letz
∈
ℤ
m
¯
+
l
n
k be [
I
m
¯
-
R
*
I
l
n
k
]
·
v
* and let z
′
∈
ℤ
m
¯
+
l
n
k
+
1 be [
z
-
1
]. Then, A
z
=
u
(
mod
⁡
q
) and
(32)
A
′
z
′
=
[
A
∥
u
]
[
z
-
1
]
=
u
-
u
=
0
(
mod
⁡
q
)
.
𝒜 outputs z
′ as a SIS solution to A
′.
The Euclidean norm ofv
* is as follows:
(33)
∥
v
*
∥
≤
s
·
m
∥
v
*
∥
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
3
·
m
¯
+
(
l
+
1
)
·
n
k
∥
v
*
∥
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
3
·
O
(
n
k
+
(
l
+
1
)
·
n
k
)
∥
v
*
∥
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
3
·
O
(
l
n
k
)
∥
v
*
∥
=
O
(
h
1
/
2
·
l
·
n
3
/
2
·
k
3
/
2
)
·
ω
(
log
⁡
⁡
n
)
3
.
Because∥
v
*
∥
≤
s
·
m
=
O
(
h
1
/
2
·
l
·
n
3
/
2
·
k
3
/
2
)
·
ω
(
log
⁡
⁡
n
)
3, ∥
z
′
∥
≈
∥
z
∥
=
O
(
h
·
l
·
n
2
·
k
2
)
·
ω
(
log
⁡
⁡
n
)
4
=
β.
To reduce the average-caseSIS problem to the worst-case SIVP in lattices, q
≥
β
·
n
·
ω
(
log
⁡
⁡
n
) should hold. Therefore,
(34)
q
≥
β
·
n
·
ω
(
log
⁡
⁡
n
)
q
=
O
(
h
·
l
·
n
2
·
k
2
)
·
ω
(
log
⁡
⁡
n
)
4
·
n
·
ω
(
log
⁡
⁡
n
)
q
=
O
(
h
·
l
·
n
5
/
2
·
k
2
)
·
ω
(
log
⁡
⁡
n
)
5
.
We note that𝒜 succeeds in its forgery if 𝒜 correctly guesses μ
* and t such that μ
* has p as a prefix. The probability of 𝒜 correctly guessing μ
* such that μ
* has p as a prefix is 1
/
(
(
h
-
1
)
·
q
s
+
1
). The probability that 𝒜 correctly guesses t is 1
/
t
C
l. Therefore,
(35)
A
d
v
𝒜
SIS
≥
1
t
C
l
·
{
(
h
-
1
)
·
q
s
+
1
}
·
A
d
v
S
R
S
,
ℱ
s
u
,
where t is the number of users and l is the upper bound of the number of corrupted users.
Our ring signature scheme has the property that the upper bound of the number of corrupted users should be constant. In proving strong unforgeability with respect to insider corruption for our ring signature scheme, the advantage of a forger is limited by the advantage of the SIS problem solver factored byt
C
l, where t is the number of users and l is the upper bound of the number of corrupted users. The lower and upper bounds of t
C
l are as follows [30]:
(36)
(
t
l
)
l
≤
t
C
l
≤
(
e
t
l
)
l
.
Ifl
=
t
/
2 (i.e., the maximal value of t
C
l), the lower and upper bounds on t
C
l are as follows:
(37)
2
t
/
2
≤
C
t
t
/
2
≤
(
2
e
)
t
/
2
.
Thus, the value oft
C
t
/
2 grows exponentially if l grows polynomially; that is, the upper bound of corrupted users, l, in our ring signature scheme needs to be some constant.
Therefore, our ring signature schemeS
R
S is strongly unforgeable with respect to insider corruption in the standard model.


## 5.1. Sets and Parameters

In this section, we propose our ring signature schemeS
R
S
=
{
S
R
S
.
G
e
n
,
S
R
S
.
S
i
g
n
,
S
R
S
.
V
r
f
y
} in the standard model. First, we define the following parameters.(i)
n is a security parameter.
(ii)
m
=
m
¯
+
(
l
+
1
)
·
n
k is the dimension of the ring signature, where m
¯
=
O
(
n
k
), k
=
O
(
log
⁡
⁡
n
), and l is the number of ring users.
(iii)
h
≤
(
p
-
1
)
·
n is the bit length of a hash value, where p is the smallest prime dividing q. That is, a hash value space is {
0,1
}
h.
(iv)
s
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
3 is a parameter used in the S
a
m
p
l
e
D algorithm and s
′
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2 is a parameter used in the D
e
l
T
r
a
p algorithm.
(v)
q
=
O
(
h
·
l
·
n
5
/
2
·
k
2
)
·
ω
(
log
⁡
⁡
n
)
5 and β
=
O
(
h
·
l
·
n
2
·
k
2
)
·
ω
(
log
⁡
⁡
n
)
4 are parameters for the SIS problem and SIVP.
(vi)
G
∈
ℤ
q
n
×
n
k is a primitive matrix whose columns generate all of ℤ
q
n.
(vii)
p
a
r
a
m
s
=
{
G
,
A
¯
,
C
0
,
…
,
C
h
,
u
,
H
(
·
,
·
)
} are public parameters, where A
¯
←
ℤ
q
n
×
m
¯, C
0
,
…
,
C
h
←
ℤ
q
n
×
n
k, u
←
ℤ
q
n, and H
(
·
,
·
)
:
{
0,1
}
*
×
{
0,1
}
m
→
{
0,1
}
h is a hash function.


## 5.2. Our Ring Signature Scheme

Our ring signature schemeS
R
S
=
{
S
R
S
.
G
e
n
,
S
R
S
.
S
i
g
n
,
S
R
S
.
V
r
f
y
} consists of the following algorithms.(i)
S
R
S
.
G
e
n
(
1
n
): on input of the security parameter n, this algorithm chooses T
i
←
𝒟
ℤ
,
ω
(
log
⁡
⁡
n
)
m
¯
×
n
k and computes A
i
=
[
G
-
A
¯
T
i
]. The signing key is s
k
i
=
T
i and the verification key is v
k
i
=
A
i.
(ii)
S
R
S
.
S
i
g
n
(
s
k
i
,
R
,
m
): on input of s
k
i
=
T
i, R
=
{
v
k
1
,
…
,
v
k
l
}
=
{
A
1
,
…
,
A
l
}, and m, this algorithm computes H
(
R
∥
m
,
r
)
=
μ
=
(
μ
1
,
…
,
μ
h
)
∈
{
0,1
}
h and C
μ
=
C
0
+
∑
j
=
1
h
‍
μ
j
C
j
∈
ℤ
q
n
×
n
k, where r
←
{
0,1
}
m and μ
j is the jth element in μ. The algorithm constructs A
R
,
μ
=
[
A
¯
∥
A
R
∥
C
μ
]
∈
ℤ
q
n
×
m, where A
R
=
[
A
1
∥
⋯
∥
A
l
] is the ordered concatenation of matrices in R. The algorithm samples v
∈
ℤ
m from 𝒟
Λ
u
⊥
(
A
R
,
μ
)
,
s using the S
a
m
p
l
e
D and D
e
l
T
r
a
p algorithms with s
k
i
=
T
i. The algorithm outputs a ring signature σ
=
(
v
,
r
).
(iii)
S
R
S
.
V
r
f
y
(
R
,
m
,
σ
): on input of R
=
{
v
k
1
,
…
,
v
k
l
}
=
{
A
1
,
…
,
A
l
}, m, and σ
=
(
v
,
r
), this algorithm computes H
(
R
∥
m
,
r
)
=
μ
=
(
μ
1
,
…
,
μ
h
)
∈
{
0,1
}
h and C
μ
=
C
0
+
∑
j
=
1
h
‍
μ
j
C
j
∈
ℤ
q
n
×
n
k, where μ
j is the jth element in μ. The algorithm constructs A
R
,
μ
=
[
A
¯
∥
A
R
∥
C
μ
]
∈
ℤ
q
n
×
m, where A
R
=
[
A
1
∥
⋯
∥
A
l
] is the ordered concatenation of matrices in R. Then, the algorithm outputs 1 if
(i)
A
R
,
μ
·
v
=
u
(
mod
⁡
q
);
(ii)
∥
v
∥
≤
s
·
m.
Otherwise, the algorithm outputs0.Correctness. We show that our ring signature scheme S
R
S is correct. The S
R
S
.
S
i
g
n
(
s
k
i
,
R
,
m
) algorithm can sample v from a distribution whose statistical distance from 𝒟
Λ
u
⊥
(
A
R
,
μ
)
,
s is negligible using the S
a
m
p
l
e
D and D
e
l
T
r
a
p algorithms with T
i such that A
R
,
μ
·
v
=
u
(
mod
⁡
q
) and ∥
v
∥
≤
s
·
m with an overwhelming probability [15, 18, 27]. Therefore, our ring signature scheme S
R
S is correct.


## 5.3. Anonymity against Full Key Exposure of Our Construction

We now show that our ring signature schemeS
R
S is anonymous against full key exposure in the standard model.Theorem 9.
S
R
S
=
{
S
R
S
.
G
e
n
,
S
R
S
.
S
i
g
n
,
S
R
S
.
V
r
f
y
} is anonymous against full key exposure in the standard model.Proof of Theorem9.
Recall that(
e
0
,
e
1
,
R
,
m
) is sent by 𝒜 in theChallenge phase of the game of anonymity. A challenge signature σ
b
=
(
v
b
,
r
b
)
←
R
S
.
S
i
g
n
(
s
k
e
b
,
R
,
m
) is then returned to 𝒜.
The signing algorithm withs
k
e
i
=
T
i samples v
i from a distribution whose statistical distance from 𝒟
Λ
u
⊥
(
A
R
,
μ
)
,
s is negligible. Therefore, the statistical distance between the distribution of v
0 and the distribution of v
1 is negligible. We also note that the distributions of r
0 and r
1 are the same. Therefore, the advantage A
d
v
S
R
S
,
𝒜
a
n of 𝒜 is negligible.


## 5.4. Strong Unforgeability with respect to Insider Corruption of Our Construction

We now show that our ring signature schemeS
R
S is strongly unforgeable with respect to insider corruption in the standard model.Theorem 10.
If theS
I
S
q
,
β problem for q
≥
|
R
|
+
|
m
|
+
4
·
s
2
·
m
·
n
·
ω
(
log
⁡
⁡
n
) and β
=
|
R
|
+
|
m
|
+
4
·
s
2
·
m and q
≥
O
(
h
·
l
·
n
5
/
2
·
k
2
)
·
ω
(
log
⁡
⁡
n
)
5 and β
=
O
(
h
·
l
·
n
2
·
k
2
)
·
ω
(
log
⁡
⁡
n
)
4 is hard, the ring signature scheme S
R
S
=
{
S
R
S
.
G
e
n
,
S
R
S
.
S
i
g
n
,
S
R
S
.
V
r
f
y
} proposed here is strongly unforgeable with respect to insider corruption in the standard model, where |
R
| is the ring size and |
m
| is the message bit length.Proof of Theorem10.
We show that, if a forger existsℱ with a nonnegligible probability, we can construct an algorithm 𝒜 solving the SI
S
q
,
β problem.
Assume thatℱ outputs a forgery (
R
*
,
m
*
,
σ
*
=
(
v
*
,
r
*
)
) in the game of strong unforgeability. Then, there exist three cases.(1)
μ
*
=
H
(
R
*
∥
m
*
,
r
*
)
=
H
(
R
i
∥
m
i
,
r
i
) for some i
∈
[
1
,
q
s
] such that R
*
≠
R
i, m
*
≠
m
i, or r
*
≠
r
i.
(2)
μ
*
=
H
(
R
*
∥
m
*
,
r
*
)
=
H
(
R
i
∥
m
i
,
r
i
) for some i
∈
[
1
,
q
s
] such that R
*
=
R
i, m
*
=
m
i, and r
*
=
r
i.
(3)
μ
*
=
H
(
R
*
∥
m
*
,
r
*
)
≠
H
(
R
i
∥
m
i
,
r
i
) for all i
∈
[
1
,
q
s
].
Note that the number of signing queries is at mostq
s, and (
R
i
,
m
i
,
r
i
) are used in the ith signing queries.
For the first case, we can construct𝒜 conducting a collision attack on H
(
·
,
·
) using ℱ. 𝒜 simulates the game of strong unforgeability with ℱ as follows.(i)
Setup. 𝒜 takes a hash function H
(
·
,
·
) as input and chooses {
G
,
A
¯
,
C
0
,
…
,
C
h
,
u
} at random. For 1
≤
i
≤
t, 𝒜 chooses T
i
←
𝒟
ℤ
,
ω
(
log
⁡
⁡
n
)
m
¯
×
n
k and computes A
i
=
[
G
-
A
¯
T
i
]. 𝒜 sends {
p
a
r
a
m
s
,
S
} to ℱ, where p
a
r
a
m
s
=
{
G
,
A
¯
,
C
0
,
…
,
C
h
,
u
,
H
(
·
,
·
)
} and S
=
{
v
k
1
,
…
,
v
k
t
}
=
{
A
1
,
…
,
A
t
}. 𝒜 sets C
U
←
∅, where C
U is a set of corrupted users.
(ii)
Signing Queries.  ℱ sends (
e
,
R
,
m
) such that v
k
e
∈
R
∩
S to 𝒜. 𝒜 chooses r
←
{
0,1
}
m and computes H
(
R
∥
m
,
r
)
=
μ
=
(
μ
1
,
…
,
μ
h
)
∈
{
0,1
}
h. A
R
,
μ is represented as [
A
¯
∥
A
R
∥
C
μ
], where A
R is the ordered concatenation of matrices in R, C
μ
=
C
0
+
∑
j
=
1
h
‍
μ
j
C
j
∈
ℤ
q
n
×
n
k, and μ
j is the jth element in μ.
The maximal singular value ofs
k
e
=
T
e (where s
T
>
0) is as follows:
(13)
s
1
(
T
e
)
=
s
T
·
O
(
m
¯
+
n
k
)
s
1
(
T
e
)
=
s
T
·
O
(
n
k
+
n
k
)
s
1
(
T
e
)
=
s
T
·
O
(
n
k
)
.
𝒜 calculates T
←
D
e
l
T
r
a
p
(
A
R
,
μ
,
T
e
,
s
′
), where s
′
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2.
Then, the maximal singular value ofT is as follows:
(14)
s
1
(
T
)
≤
s
′
·
O
(
m
¯
+
n
k
+
l
n
k
)
s
1
(
T
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2
·
O
(
n
k
+
n
k
+
l
n
k
)
s
1
(
T
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2
·
O
(
n
k
+
l
n
k
)
s
1
(
T
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2
·
O
(
l
n
k
)
s
1
(
T
)
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
2
.
𝒜 calculates v
←
S
a
m
p
l
e
D
(
A
R
,
μ
,
T
,
u
,
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
2
) from a distribution whose statistical distance from 𝒟
Λ
u
⊥
(
A
R
,
μ
)
,
s is negligible, where s
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
3. 𝒜 returns σ
=
(
v
,
r
) to ℱ.
(iii)
Corruption Queries. ℱ sends i such that v
k
i
∈
S to 𝒜. 𝒜 returns s
k
i
=
T
i to ℱ and adds v
k
i
=
A
i to C
U.
(iv)
Output. 𝒜 outputs (
R
*
,
m
*
,
σ
*
=
(
v
*
,
r
*
)
). For any i, μ
*
=
H
(
R
*
∥
m
*
,
r
*
)
=
H
(
R
i
∥
m
i
,
r
i
)
∈
{
H
(
R
1
∥
m
1
,
r
1
)
,
…
,
H
(
R
q
s
∥
m
q
s
,
r
q
s
)
}, where R
*
≠
R
i, m
*
≠
m
i, or r
*
≠
r
i. 𝒜 outputs two pairs {
(
R
*
∥
m
*
,
r
*
)
,
(
R
i
∥
m
i
,
r
i
)
} as a collision on H
(
·
,
·
).
To reduce the average-caseSIS problem to the worst-case SIVP in lattices, q
≥
β
·
n
·
ω
(
log
⁡
⁡
n
) should hold. Therefore,
(15)
q
≥
β
·
n
·
ω
(
log
⁡
⁡
n
)
q
=
|
R
|
+
|
m
|
+
4
·
s
2
·
m
·
n
·
ω
(
log
⁡
⁡
n
)
.
Naturally,(16)
A
d
v
𝒜
SIS
≥
A
d
v
H
(
·
,
·
)
,
𝒜
c
r
≥
A
d
v
S
R
S
,
ℱ
s
u
.
For the second case, we can construct𝒜 attacking the SI
S
q
,
β problem using ℱ. Assume that the number of corrupted users is at most l. 𝒜 simulates the game of strong unforgeability with ℱ as follows.(i)
Setup. 𝒜 chooses a primitive matrix G
∈
ℤ
q
n
×
n
k. 𝒜 takes as input A
′
∈
ℤ
q
n
×
(
m
¯
+
l
n
k
+
1
) as an SIS instance and parses A
′ as [
A
∥
u
′
]
=
[
A
¯
∥
A
1
*
∥
⋯
∥
A
l
*
∥
u
′
], where A
¯
∈
ℤ
q
n
×
m
¯, A
1
*
,
…
,
A
l
*
∈
ℤ
q
n
×
n
k, and u
′
∈
ℤ
q
n. 𝒜 chooses a chameleon hash function H
(
·
,
·
) with trapdoor information and distinct hash values {
μ
1
,
…
,
μ
q
s
}, where μ
i
←
{
0,1
}
h for 1
≤
i
≤
q
s. 𝒜 randomly selects μ
′
∈
{
μ
1
,
…
,
μ
q
s
}.
For0
≤
j
≤
h, 𝒜 computes H
j as follows:
(17)
H
j
=
{
(
-
1
)
μ
j
′
·
h
(
u
j
)
j
∈
{
1
,
…
,
h
}
-
∑
k
=
1
h
μ
k
′
·
H
k
j
=
0
,
whereμ
j
′ is the jth element in μ
′ and h
(
·
) is a ring homomorphism.
For0
≤
j
≤
h, 𝒜 chooses R
j
←
𝒟
ℤ
,
ω
(
log
⁡
⁡
n
)
m
¯
×
n
k and computes the following:
(18)
C
j
=
H
j
G
-
A
¯
R
j
.
Ifμ
i
=
μ
′, H
0
+
∑
j
=
1
h
‍
μ
i
,
j
H
j
=
0
∈
ℤ
n
×
n, where μ
i
,
j is the jth element in μ
i. Otherwise, H
0
+
∑
j
=
1
h
‍
μ
i
,
j
H
j
≠
0
∈
ℤ
n
×
n is an invertible matrix.
𝒜 chooses v
←
𝒟
ℤ
m
¯
+
(
l
+
1
)
n
k
,
s and computes u
=
[
A
∥
C
μ
′
]
·
v, where C
μ
′
=
C
0
+
∑
j
=
1
h
‍
μ
j
′
C
j and μ
j
′ is the jth element in μ
′.
𝒜 randomly chooses t
=
(
t
1
,
…
,
t
t
)
←
{
0,1
}
t such that the number of 1s in t is l. If t
k
=
1 for 1
≤
k
≤
t, 𝒜 sets A
k
=
A
i
* for 1
≤
i
≤
l in turn. Otherwise, 𝒜 chooses T
k
←
𝒟
ℤ
,
ω
(
log
⁡
⁡
n
)
m
¯
×
n
k and computes A
k
=
[
G
-
A
¯
T
k
].
𝒜 sends {
p
a
r
a
m
s
,
S
} to ℱ, where p
a
r
a
m
s
=
{
G
,
A
¯
,
C
0
,
…
,
C
h
,
u
,
H
(
·
,
·
)
} and S
=
{
v
k
1
,
…
,
v
k
t
}
=
{
A
1
,
…
,
A
t
}. 𝒜 sets C
U
←
∅, where C
U is a set of corrupted users.
(ii)
Signing Queries. For 1
≤
i
≤
q
s, ℱ sends (
e
i
,
R
i
,
m
i
) such that v
k
e
i
∈
R
i
∩
S to 𝒜. 𝒜 samples r
i with trapdoor information such that μ
i
=
H
(
R
i
∥
m
i
,
r
i
).
(1)
Forμ
i
=
μ
′: if A
≠
[
A
¯
∥
A
R
i
], 𝒜 aborts. Otherwise, 𝒜 returns σ
i
=
(
v
,
r
i
) to ℱ. Note that the distributions of v and 𝒟
Λ
u
⊥
(
A
∥
C
μ
′
)
,
s are the same.
(2)
Forμ
i
≠
μ
′: A
R
i
,
μ
i is represented as [
A
¯
∥
A
R
i
∥
H
G
-
A
¯
R
], where H
=
H
0
+
∑
j
=
1
h
‍
μ
i
,
j
H
j
≠
0
∈
ℤ
n
×
n and R
=
R
0
+
∑
j
=
1
h
‍
μ
i
,
j
R
j.
The maximal singular value ofR is as follows:
(19)
s
1
(
R
)
=
h
+
1
·
O
(
m
¯
+
n
k
)
·
ω
(
log
⁡
⁡
n
)
s
1
(
R
)
=
h
+
1
·
O
(
n
k
+
n
k
)
·
ω
(
log
⁡
⁡
n
)
s
1
(
R
)
=
h
+
1
·
O
(
n
k
)
·
ω
(
log
⁡
⁡
n
)
s
1
(
R
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
.
𝒜 calculates R
′
←
D
e
l
T
r
a
p
(
A
R
i
,
μ
i
,
R
,
s
′
), where s
′
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2.
Then, the maximal singular value ofR
′ is as follows:
(20)
s
1
(
R
′
)
≤
s
′
·
O
(
m
¯
+
n
k
+
l
n
k
)
s
1
(
R
′
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2
·
O
(
n
k
+
n
k
+
l
n
k
)
s
1
(
R
′
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2
·
O
(
n
k
+
l
n
k
)
s
1
(
R
′
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2
·
O
(
l
n
k
)
s
1
(
R
′
)
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
2
.
𝒜 calculates v
i
←
S
a
m
p
l
e
D
(
A
R
i
,
μ
i
,
R
′
,
u
,
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
2
) from a distribution whose statistical distance from 𝒟
Λ
u
⊥
(
A
R
i
,
μ
i
)
,
s is negligible, where s
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
3. 𝒜 returns σ
i
=
(
v
i
,
r
i
) to ℱ.
(iii)
Corruption Queries. If ℱ asks for s
k
j, where t
j
=
1, 𝒜 aborts. Otherwise, 𝒜 returns s
k
j
=
T
j and adds v
k
j
=
A
j to C
U.
(iv)
Output. ℱ outputs (
R
*
,
m
*
,
σ
*
=
(
v
*
,
r
*
)
). If μ
*
=
H
(
R
*
∥
m
*
,
r
*
)
≠
μ
′, 𝒜 aborts. Otherwise, A
R
*
,
μ
*
=
[
A
∥
C
μ
′
]
=
[
A
¯
∥
A
1
*
∥
⋯
∥
A
l
*
∥
-
A
¯
R
*
], where H
*
=
H
0
+
∑
j
=
1
h
‍
μ
j
*
H
j
=
0
∈
ℤ
n
×
n and R
*
=
R
0
+
∑
j
=
1
h
‍
μ
j
*
R
j.
Therefore, we obtain the following equation:(21)
[
A
∥
C
μ
′
]
·
v
=
[
A
∥
C
μ
′
]
·
v
*
=
u
(
mod
⁡
q
)
.
From the above equation, we have that(22)
[
A
∥
C
μ
′
]
·
(
v
*
-
v
)
=
[
A
¯
∥
A
1
*
∥
⋯
∥
A
l
*
∥
-
A
¯
R
*
]
·
(
v
*
-
v
)
=
A
[
I
m
¯
-
R
*
I
l
n
k
]
·
(
v
*
-
v
)
=
0
(
mod
⁡
q
)
.
Letz
∈
ℤ
m
¯
+
l
n
k be [
I
m
¯
-
R
*
I
l
n
k
]
·
(
v
*
-
v
) and let z
′
∈
ℤ
m
¯
+
l
n
k
+
1 be [
z
0
]. Then, A
z
=
0
(
mod
⁡
q
) and
(23)
A
′
z
′
=
[
A
∥
u
′
]
[
z
0
]
=
0
(
mod
⁡
q
)
.
𝒜 outputs z
′ as a SIS solution to A
′.The Euclidean norm of v
* is as follows:
(24)
∥
v
*
∥
≤
s
·
m
∥
v
*
∥
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
3
·
m
¯
+
(
l
+
1
)
·
n
k
∥
v
*
∥
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
3
·
O
(
n
k
+
(
l
+
1
)
·
n
k
)
∥
v
*
∥
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
3
·
O
(
l
n
k
)
∥
v
*
∥
=
O
(
h
1
/
2
·
l
·
n
3
/
2
·
k
3
/
2
)
·
ω
(
log
⁡
⁡
n
)
3
.
Because∥
v
∥
=
∥
v
*
∥
=
O
(
h
1
/
2
·
l
·
n
3
/
2
·
k
3
/
2
)
·
ω
(
log
⁡
⁡
n
)
3 and v
*
-
v
≠
0, ∥
z
′
∥
=
∥
z
∥
=
O
(
h
·
l
·
n
2
·
k
2
)
·
ω
(
log
⁡
⁡
n
)
4
=
β.
To reduce the average-caseSIS problem to the worst-case SIVP in lattices, q
≥
β
·
n
·
ω
(
log
⁡
⁡
n
) should hold. Therefore,
(25)
q
≥
β
·
n
·
ω
(
log
⁡
⁡
n
)
q
=
O
(
h
·
l
·
n
2
·
k
2
)
·
ω
(
log
⁡
⁡
n
)
4
·
n
·
ω
(
log
⁡
⁡
n
)
q
=
O
(
h
·
l
·
n
5
/
2
·
k
2
)
·
ω
(
log
⁡
⁡
n
)
5
.
We note that𝒜 succeeds in its forgery if it correctly guesses μ
′ and t. The probability of 𝒜 correctly guessing μ
′ is 1
/
q
s, and the probability of correctly guessing t is 1
/
t
C
l. Therefore,
(26)
A
d
v
𝒜
SIS
≥
1
t
C
l
·
q
s
·
A
d
v
S
R
S
,
ℱ
s
u
,
where t is the number of users and l is the upper bound of the number of corrupted users.
For the third case, we can construct𝒜 attacking the SI
S
q
,
β problem using ℱ. Assume that the number of corrupted users is at most l. 𝒜 simulates the game of strong unforgeability with ℱ as follows.(i)
Setup. 𝒜 chooses a primitive matrix G
∈
ℤ
q
n
×
n
k. 𝒜 takes as input A
′
∈
ℤ
q
n
×
(
m
¯
+
l
n
k
+
1
) as a SIS instance and parses A
′ as [
A
∥
u
]
=
[
A
¯
∥
A
1
*
∥
⋯
∥
A
l
*
∥
u
], where A
¯
∈
ℤ
q
n
×
m
¯,  A
1
*
,
…
,
A
l
*
∈
ℤ
q
n
×
n
k, and u
∈
ℤ
q
n. 𝒜 chooses a chameleon hash function H
(
·
,
·
) with trapdoor information and distinct hash values {
μ
1
,
…
,
μ
q
s
}, where μ
i
←
{
0,1
}
h for 1
≤
i
≤
q
s. 𝒜 constructs a set P of all shortest strings p
∈
{
0,1
}
≤
h such that each element of {
μ
1
,
…
,
μ
q
s
} has no p as a prefix. There exists an efficient algorithm for computing P, and the number of elements in P is at most (
h
-
1
)
·
q
s
+
1 [15, 17, 18]. 𝒜 chooses p from P at random. |
p
|
≤
h, where |
p
| is the bit length of p.
For0
≤
j
≤
h, 𝒜 computes H
j as follows:
(27)
H
j
=
{
h
(
0
)
=
0
j
>
|
p
|
(
-
1
)
p
j
·
h
(
u
j
)
j
∈
{
1
,
…
,
|
p
|
}
-
∑
k
=
1
|
p
|
p
k
·
H
k
j
=
0
,
wherep
j is the jth element in p and h
(
·
) is a ring homomorphism.
For0
≤
j
≤
h, 𝒜 chooses R
j
←
𝒟
ℤ
,
ω
(
log
⁡
⁡
n
)
m
¯
×
n
k and computes the following:
(28)
C
j
=
H
j
G
-
A
¯
R
j
.
If anyμ
i has p as a prefix, H
0
+
∑
j
=
1
h
‍
μ
i
,
j
H
j
=
0
∈
ℤ
n
×
n, where μ
i
,
j is the jth element in μ
i. Otherwise, H
0
+
∑
j
=
1
h
‍
μ
i
,
j
H
j
≠
0
∈
ℤ
n
×
n is an invertible matrix.
𝒜 randomly chooses t
=
(
t
1
,
…
,
t
t
)
←
{
0,1
}
t such that the number of 1s in t is l. If t
k
=
1 for 1
≤
k
≤
t, 𝒜 sets A
k
=
A
i
* for 1
≤
i
≤
l in turn. Otherwise, 𝒜 chooses T
k
←
𝒟
ℤ
,
ω
(
log
⁡
⁡
n
)
m
¯
×
n
k and computes A
k
=
[
G
-
A
¯
T
k
].
𝒜 sends {
p
a
r
a
m
s
,
S
} to ℱ, where p
a
r
a
m
s
=
{
G
,
A
¯
,
C
0
,
…
,
C
h
,
u
,
H
(
·
,
·
)
} and S
=
{
v
k
1
,
…
,
v
k
t
}
=
{
A
1
,
…
,
A
t
}. 𝒜 sets C
U
←
∅, where C
U is a set of corrupted users.
(ii)
Signing Queries. For 1
≤
i
≤
q
s, ℱ sends (
e
i
,
R
i
,
m
i
) such that v
k
e
i
∈
R
i
∩
S to 𝒜. 𝒜 samples r
i with trapdoor information such that μ
i
=
H
(
R
i
∥
m
i
,
r
i
). A
R
i
,
μ
i is represented as [
A
¯
∥
A
R
i
∥
H
G
-
A
¯
R
], where H
=
H
0
+
∑
j
=
1
h
‍
μ
i
,
j
H
j
≠
0
∈
ℤ
n
×
n and R
=
R
0
+
∑
j
=
1
h
‍
μ
i
,
j
R
j.
The maximal singular value ofR is as follows:
(29)
s
1
(
R
)
=
h
+
1
·
O
(
m
¯
+
n
k
)
·
ω
(
log
⁡
⁡
n
)
s
1
(
R
)
=
h
+
1
·
O
(
n
k
+
n
k
)
·
ω
(
log
⁡
⁡
n
)
s
1
(
R
)
=
h
+
1
·
O
(
n
k
)
·
ω
(
log
⁡
⁡
n
)
s
1
(
R
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
.
𝒜 calculates R
′
←
D
e
l
T
r
a
p
(
A
R
i
,
μ
i
,
R
,
s
′
), where s
′
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2.
Then, the maximal singular value ofR
′ is as follows:
(30)
s
1
(
R
′
)
≤
s
′
·
O
(
m
¯
+
n
k
+
l
n
k
)
s
1
(
R
′
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2
·
O
(
n
k
+
n
k
+
l
n
k
)
s
1
(
R
′
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2
·
O
(
n
k
+
l
n
k
)
s
1
(
R
′
)
=
O
(
h
n
k
)
·
ω
(
log
⁡
⁡
n
)
2
·
O
(
l
n
k
)
s
1
(
R
′
)
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
2
.
𝒜 calculates v
i
←
S
a
m
p
l
e
D
(
A
R
i
,
μ
i
,
R
′
,
u
,
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
2
) from a distribution whose statistical distance from 𝒟
Λ
u
⊥
(
A
R
i
,
μ
i
)
,
s is negligible, where s
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
3. 𝒜 returns σ
i
=
(
v
i
,
r
i
) to ℱ.
(iii)
Corruption Queries. If ℱ asks for s
k
i, where t
i
=
1, 𝒜 aborts. Otherwise, 𝒜 returns s
k
i
=
T
i and adds v
k
i
=
A
i to C
U.
(iv)
Output. ℱ outputs (
R
*
,
m
*
,
σ
*
=
(
v
*
,
r
*
)
). If μ
*
=
H
(
R
*
∥
m
*
,
r
*
) has no p as a prefix or A
≠
[
A
¯
∥
A
R
*
], 𝒜 aborts. Otherwise, A
R
*
,
μ
* is represented as [
A
¯
∥
A
R
*
∥
-
A
¯
R
*
], where H
*
=
H
0
+
∑
j
=
1
h
‍
μ
j
*
H
j
=
0
∈
ℤ
n
×
n and R
*
=
R
0
+
∑
j
=
1
h
‍
μ
j
*
R
j. Therefore, we obtain the following equation:
(31)
A
R
*
,
μ
*
·
v
*
=
[
A
¯
∥
A
R
*
∥
-
A
¯
R
*
]
·
v
*
A
R
*
,
μ
*
·
v
*
=
[
A
¯
∥
A
R
*
]
[
I
m
¯
-
R
*
I
l
n
k
]
·
v
*
A
R
*
,
μ
*
·
v
*
=
A
·
[
I
m
¯
-
R
*
I
l
n
k
]
·
v
*
A
R
*
,
μ
*
·
v
*
=
u
(
mod
⁡
q
)
.
Letz
∈
ℤ
m
¯
+
l
n
k be [
I
m
¯
-
R
*
I
l
n
k
]
·
v
* and let z
′
∈
ℤ
m
¯
+
l
n
k
+
1 be [
z
-
1
]. Then, A
z
=
u
(
mod
⁡
q
) and
(32)
A
′
z
′
=
[
A
∥
u
]
[
z
-
1
]
=
u
-
u
=
0
(
mod
⁡
q
)
.
𝒜 outputs z
′ as a SIS solution to A
′.
The Euclidean norm ofv
* is as follows:
(33)
∥
v
*
∥
≤
s
·
m
∥
v
*
∥
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
3
·
m
¯
+
(
l
+
1
)
·
n
k
∥
v
*
∥
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
3
·
O
(
n
k
+
(
l
+
1
)
·
n
k
)
∥
v
*
∥
=
O
(
n
k
·
h
l
)
·
ω
(
log
⁡
⁡
n
)
3
·
O
(
l
n
k
)
∥
v
*
∥
=
O
(
h
1
/
2
·
l
·
n
3
/
2
·
k
3
/
2
)
·
ω
(
log
⁡
⁡
n
)
3
.
Because∥
v
*
∥
≤
s
·
m
=
O
(
h
1
/
2
·
l
·
n
3
/
2
·
k
3
/
2
)
·
ω
(
log
⁡
⁡
n
)
3, ∥
z
′
∥
≈
∥
z
∥
=
O
(
h
·
l
·
n
2
·
k
2
)
·
ω
(
log
⁡
⁡
n
)
4
=
β.
To reduce the average-caseSIS problem to the worst-case SIVP in lattices, q
≥
β
·
n
·
ω
(
log
⁡
⁡
n
) should hold. Therefore,
(34)
q
≥
β
·
n
·
ω
(
log
⁡
⁡
n
)
q
=
O
(
h
·
l
·
n
2
·
k
2
)
·
ω
(
log
⁡
⁡
n
)
4
·
n
·
ω
(
log
⁡
⁡
n
)
q
=
O
(
h
·
l
·
n
5
/
2
·
k
2
)
·
ω
(
log
⁡
⁡
n
)
5
.
We note that𝒜 succeeds in its forgery if 𝒜 correctly guesses μ
* and t such that μ
* has p as a prefix. The probability of 𝒜 correctly guessing μ
* such that μ
* has p as a prefix is 1
/
(
(
h
-
1
)
·
q
s
+
1
). The probability that 𝒜 correctly guesses t is 1
/
t
C
l. Therefore,
(35)
A
d
v
𝒜
SIS
≥
1
t
C
l
·
{
(
h
-
1
)
·
q
s
+
1
}
·
A
d
v
S
R
S
,
ℱ
s
u
,
where t is the number of users and l is the upper bound of the number of corrupted users.
Our ring signature scheme has the property that the upper bound of the number of corrupted users should be constant. In proving strong unforgeability with respect to insider corruption for our ring signature scheme, the advantage of a forger is limited by the advantage of the SIS problem solver factored byt
C
l, where t is the number of users and l is the upper bound of the number of corrupted users. The lower and upper bounds of t
C
l are as follows [30]:
(36)
(
t
l
)
l
≤
t
C
l
≤
(
e
t
l
)
l
.
Ifl
=
t
/
2 (i.e., the maximal value of t
C
l), the lower and upper bounds on t
C
l are as follows:
(37)
2
t
/
2
≤
C
t
t
/
2
≤
(
2
e
)
t
/
2
.
Thus, the value oft
C
t
/
2 grows exponentially if l grows polynomially; that is, the upper bound of corrupted users, l, in our ring signature scheme needs to be some constant.
Therefore, our ring signature schemeS
R
S is strongly unforgeable with respect to insider corruption in the standard model.


## 6. Conclusion

In this paper, we have shown that all of Wang-Sun’s ring signature schemes are not in fact existentially unforgeable. We then have developed the more secure concept of strong unforgeability for ring signatures and have suggested a new ring signature scheme from lattices in the standard model that satisfies strong unforgeability. Our ring signature scheme is anonymous against full key exposure and is strongly unforgeable with respect to insider corruption in the standard model.



---

*Source: 371924-2014-05-05.xml*