# A Fuzzy Identity-Based Signature Scheme from Lattices in the Standard Model

Authors: Chunli Yang; Shihui Zheng; Licheng Wang; Miaomiao Tian; Lize Gu; Yixian Yang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

A fuzzy identity-based signature (FIBS) scheme allows a user with identityI
D to issue a signature that could be verified with identity I
D
' if and only if I
D and I
D
' lie within a certain distance. To obtain an FIBS scheme that can resist known quantum attacks, we use the double-trapdoor technique from ABB10a for secret key extracting and the vanishing trapdoor technique from Boyen10 for message signing. In addition, in order to reflect the functionality of fuzziness, Shamir secret sharing scheme is also used in our construction. In this paper, we propose an FIBS scheme from lattices and prove that this new scheme achieves strong unforgeability under selective chosen-identity and adaptive chosen-message attacks (SU-sID-CMA) in the standard model. To the best of our knowledge, our scheme is not only the first FIBS scheme from lattices without random oracles but also the first FIBS scheme that achieves strong unforgeability.


---

## Body

## 1. Introduction

In order to overcome certificates management problem in traditional public key cryptography, Shamir first put forward the concept of identity-based public key cryptography [1] in 1985; that is, the public key of an identity can be easily computed from his identity information. The first efficient and secure identity-based public key encryption (IBE) scheme was given by Boneh and Franklin in [2]. However, identity string for each identity is not unique, while biometric characteristics (e.g., fingerprints, faces, irises, etc.) are unique. Therefore, identity’s biometric characteristics can be used as public keys. Biometric keys have many advantages: hard to guess, forget, copy, share, and forge. However, biometric measurements are noisy, and there are many different measurements to the same biometric.Sahai and Waters first introduced the concept of fuzzy identity-based encryption (FIBE) [3] in 2005. In an FIBE scheme, a user using the secret key, which the identity ID described as an attribute set att, can decrypt a ciphertext encrypted with the public key at
t
′ if and only if att and at
t
′ lie within a certain distance judged by some metric. Thus, an FIBE scheme involves an error tolerance parameter between the identities. In 2007, Baek et al. [4] put forward two FIBE schemes; these new schemes provided public parameters whose size was independent of the number of attributes in each identity and had beautiful structures, which made the key extraction and encryption more efficient than the scheme [3]. In [5], Goyal et al. showed that FIBE can also be regarded as a type of application of attribute based encryption (ABE).Yang et al. [6] first introduced the concept of fuzzy identity-based signature (FIBS) and constructed an FIBS scheme based on scheme [3]. A fuzzy identity-based signature (FIBS) scheme allows a user with identity ID to issue a signature that could be verified with identity I
D
′ if and only if ID and I
D
′ lie within a certain distance judged by some metric. A number of FIBS schemes have been put forward in recent years, such as [7–11]. However, all of these schemes not only are based on hard number theoretical problems (e.g., integer factorization, discrete logarithm, and bilinear pairings), which are vulnerable to quantum computer attacks [12], but also achieved existential unforgeability. Existential unforgeability is only a basic requirement for a signature scheme; it means that an adversary is allowed to forge a new different signature of the same message. Strong unforgeability means that it prevents forging of signatures on messages that could have been signed previously. Cryptologists prefer to design digital signature schemes that can achieve strong unforgeability.In recent years, lattice-based cryptographic systems have attained a great interest for postcryptography, as the systems have the ability to resist the known quantum analysis (e.g., Shor algorithm analysis [12]). Furthermore, the systems also enjoy great promise because of having a very strong security proof based on worst-case hardness, relatively efficient implementations, and great simplicity due to the structure and linearity of lattices. Many cryptographic schemes are based on the learning with errors (LWE) problem and small integer solution (SIS) problem, for example, public key encryption schemes [13, 14], digital signatures [15, 16], identity-based encryption [17, 18], fully homomorphic encryption [19, 20], and so on.Meanwhile, researchers are always concerned with fuzzy identity-based signature (FIBS) scheme from lattices. An FIBS scheme from lattices was first proposed by Yao and Li [21] in 2013. The paper pointed out the defect of security model in [6] and put forward a more reasonable security model for FIBS scheme. In addition, authors also presented an FIBS scheme based on the SIS problem hardness assumption. However, the scheme could only achieve the standard of existentially unforgeable against adaptively chosen message and identity (EU-ACMIA) attacks in the random oracles. However, considering Canetti’s critical statement on provable security reduction based on random oracles [22] and the risk of random oracle model [23], it is a meaningful and relatively safe direction to design cryptographic schemes that are not in the random oracle model.Based on the security model of [21], we use the double-trapdoor technique from ABB10a for secret key extracting, the vanishing trapdoor technique from Boyen10 for message signing, and Shamir secret sharing scheme [24]. We propose a new FIBS scheme that achieves strong unforgeability against selective chosen-identity and adaptive chosen-message attacks (SU-sID-CMA) in the standard model. To the best of our knowledge, our scheme is the first FIBS scheme from lattices without random oracles and achieves strong unforgeability.The rest of this paper is organised as follows. In Section2, we introduce some preliminaries about SIS problem and some algorithms that will be used in our construction and security proof. The model of FIBS and security notations are given in Section 3. In Section 4, we present our main result that is an FIBS scheme from SIS. The security proof and parameters analysis are presented in Section 5. We give the performance analysis and simulations in Section 6. In Section 7, we present the conclusions and open problem for the future.


## 2. Preliminaries

### 2.1. Notation

We denote the set of integers and real numbers byZ and R, respectively. For a positive integer n, [
n
] denotes the set {
1,2
,
…
,
n
}. The vectors are denoted by lower-case bold letters (e.g., x), matrices by upper-case bold letters (e.g., A), and the Gram-Schmidt orthogonalization of A by A
~. We write ∥
x
∥ for the Euclidean norm of x and ∥
X
∥
=
ma
x
i
∥
x
i
∥ for the length of a matrix X. We use standard O, o for denoting the growth of functions. The notation poly(
n
) denotes a function f
(
n
)
=
O
(
n
c
) for some constant c. negl(
n
) denotes some unspecified function f
(
n
) such that f
(
n
)
=
o
(
n
-
c
) for constant c, and describing such a function is negligible. We also describe that a probability is overwhelming if it is 1
-
negl
(
n
). The base of logarithm function is 2.


### 2.2. Lattice and Small Integer Solution (SIS) Problem

Definition 1 (see [25]).
Ann-dimensional lattice Λ is a discrete additive subgroup of R
n. Formally, let B
=
{
b
1
,
b
2
,
…
,
b
n
} consist of n linearly independent vectors. The lattice generated by B is
(1)
Λ
=
L
(
B
)
=
{
B
x
=
∑
i
=
1
n
‍
x
i
b
i
∣
x
=
(
x
1
,
x
2
,
…
,
x
n
)
∈
Z
n
}
.
Here B is called a basis for the lattice Λ
=
L
(
B
).
For any basisB
=
{
b
1
,
b
2
,
…
,
b
n
}, let B
~
=
{
b
~
1
,
b
~
2
,
…
,
b
~
n
} denote its Gram-Schmidt orthogonalization of basis B. It is iteratively defined as follows: b
~
1
=
b
1, and b
~
i is the component of b
i orthogonal to span(
b
1
,
b
2
,
…
,
b
i
-
1
) for i
=
2,3
,
…
,
n.Definition 2 (see [25]).
Given a matrixA
∈
Z
q
n
×
m for some q, m, n, its q-ary lattice is defined as follows:
(2)
Λ
q
⊥
(
A
)
=
{
z
∈
Z
m
:
A
z
=
0
mod
⁡
q
}
.
We also define the coset for any y
∈
Z
q
n that is generated by the columns of A as
(3)
Λ
q
y
(
A
)
=
{
z
∈
Z
m
:
A
z
=
y
mod
⁡
q
}
.Definition 3 (see [26]).
Given any vectorc and real s
>
0, a Gaussian function on R
n centered at c with parameter s is defined by
(4)
ρ
s
,
c
(
x
)
=
e
-
π
∥
x
-
c
∥
2
/
s
2
.
For any vectorc, real s
>
0, and n-dimensional lattice Λ, the discrete Gaussian distribution over Λ is defined as follows:
(5)
∀
x
∈
Λ
,
D
Λ
,
s
,
c
(
x
)
=
ρ
s
,
c
(
x
)
ρ
s
,
c
(
Λ
)
,
where ρ
s
,
c
(
Λ
)
=
∑
x
∈
Λ
‍
ρ
s
,
c
(
x
).Definition 4 (small integer solution (SIS) problem [26]).
Given an integerq, a real β
>
0, and a matrix A
∈
Z
q
n
×
m, the goal of SIS
n
,
m
,
q
,
β is to find a vector z
∈
Z
m for satisfying z
∈
Λ
q
⊥
(
A
)
∖
{
0
} and ∥
z
∥
≤
β, where Λ
q
⊥
(
A
)
=
{
z
∈
Z
m
:
A
z
=
0
mod
⁡
q
}.Proposition 5 (hardness of SIS problem [26]).
Given security parametern, any poly-bounded m, β
=
p
o
l
y
(
n
), and any prime q
≥
β
·
ω
(
n
log
⁡
n
), the average-case problem S
I
S
n
,
m
,
q
,
β is as hard as approximating the SIVP problem in the worst case to within certain γ
=
β
·
O
~
(
n
) factors.


### 2.3. Some Algorithms

We recall some algorithms for our construction and security proof later.Lemma 6 (see [27]).
Letq
≥
3 be odd and m
=
⌈
6
n
log
⁡
q
⌉. There is a probabilistic polynomial time algorithm T
r
a
p
G
e
n
(
q
,
n
) that outputs a pair (
A
∈
Z
q
n
×
m
,
T
A
∈
Z
m
×
m
) such that A is statistically close to a uniform matrix in Z
q
n
×
m and T
A is a basis for Λ
q
⊥
(
A
) satisfying
(6)
∥
T
~
A
∥
≤
O
(
n
log
⁡
q
)
,
∥
T
A
∥
≤
O
(
n
log
⁡
q
)
with all but negligible probability in n.
For simplicity, we letL
=
O
(
n
log
⁡
q
) denote the maximum Gram-Schimidt norm of a basis produced by T
r
a
p
G
e
n
(
q
,
n
).Lemma 7 (see [15, 26]).
Letq
≥
2 and A be a matrix in Z
q
n
×
m with m
>
n. Let T
A be a basis for Λ
q
⊥
(
A
) and σ
≥
∥
T
~
A
∥
ω
(
log
⁡
m
). Then for any u
∈
Z
q
n,(1)
P
r
[
x
~
D
Λ
q
u
(
A
)
,
σ
:
∥
x
∥
>
σ
m
]
≤
n
e
g
l
(
n
);
(2)
there is a probabilistic polynomial time algorithmS
a
m
p
l
e
P
r
e
(
A
,
T
A
,
u
,
σ
) that returns x
∈
Λ
q
u
(
A
) sampled from a distribution statistically close to D
Λ
q
u
(
A
)
,
σ.Lemma 8 (see [18]).
Letq
>
2, m
>
n, and σ
>
∥
T
~
B
∥
s
R
ω
(
log
⁡
m
). There exists a polynomial time algorithm S
a
m
p
l
e
R
i
g
h
t
(
A
,
B
,
R
,
T
B
,
u
,
σ
) that takes a matrix A
∈
Z
q
n
×
k, a rank n matrix B
∈
Z
q
n
×
m, a matrix R
∈
Z
k
×
m, and a short basis T
B of Λ
q
⊥
(
B
) as inputs and outputs a vector e
∈
Z
m
+
k distributed statistically close to D
Λ
q
u
(
F
2
)
,
σ, where F
2
:
=
A
∥
(
A
R
+
B
) and s
R
:
=
∥
R
∥
=
sup
∥
x
∥
=
1
∥
R
x
∥.Lemma 9 (see [18]).
There exists a polynomial time algorithmS
a
m
p
l
e
B
a
s
i
s
L
e
f
t
(
A
,
M
,
T
A
,
0
,
σ
) that takes a matrix A
∈
Z
q
n
×
m
1, a matrix M
∈
Z
q
n
×
m
2, and a short basis T
A of Λ
q
⊥
(
A
) as inputs and outputs a basis T
F
1 of Λ
q
⊥
(
F
1
) with σ
>
∥
T
~
A
∥
ω
(
log
⁡
(
m
1
+
m
2
)
) and ∥
T
~
F
1
∥
=
∥
T
~
A
∥, where F
1
:
=
A
∥
M.Lemma 10 (see [18]).
There exists a polynomial time algorithmS
a
m
p
l
e
B
a
s
i
s
R
i
g
h
t
(
A
,
B
,
R
,
T
B
,
0
,
σ
) that takes matrices A
∈
Z
q
n
×
k, M
∈
Z
q
n
×
m, and R
∈
{
1
,
-
1
}
k
×
m and a short basis T
B of Λ
q
⊥
(
B
) as inputs and outputs a basis T
F
2 of Λ
q
⊥
(
F
2
) with σ
>
∥
T
~
B
∥
s
R
ω
(
log
⁡
(
m
)
) and ∥
T
~
F
2
∥
≤
∥
T
~
B
∥
(
s
R
+
1
), where F
2
:
=
A
∥
(
A
R
+
B
).


## 2.1. Notation

We denote the set of integers and real numbers byZ and R, respectively. For a positive integer n, [
n
] denotes the set {
1,2
,
…
,
n
}. The vectors are denoted by lower-case bold letters (e.g., x), matrices by upper-case bold letters (e.g., A), and the Gram-Schmidt orthogonalization of A by A
~. We write ∥
x
∥ for the Euclidean norm of x and ∥
X
∥
=
ma
x
i
∥
x
i
∥ for the length of a matrix X. We use standard O, o for denoting the growth of functions. The notation poly(
n
) denotes a function f
(
n
)
=
O
(
n
c
) for some constant c. negl(
n
) denotes some unspecified function f
(
n
) such that f
(
n
)
=
o
(
n
-
c
) for constant c, and describing such a function is negligible. We also describe that a probability is overwhelming if it is 1
-
negl
(
n
). The base of logarithm function is 2.


## 2.2. Lattice and Small Integer Solution (SIS) Problem

Definition 1 (see [25]).
Ann-dimensional lattice Λ is a discrete additive subgroup of R
n. Formally, let B
=
{
b
1
,
b
2
,
…
,
b
n
} consist of n linearly independent vectors. The lattice generated by B is
(1)
Λ
=
L
(
B
)
=
{
B
x
=
∑
i
=
1
n
‍
x
i
b
i
∣
x
=
(
x
1
,
x
2
,
…
,
x
n
)
∈
Z
n
}
.
Here B is called a basis for the lattice Λ
=
L
(
B
).
For any basisB
=
{
b
1
,
b
2
,
…
,
b
n
}, let B
~
=
{
b
~
1
,
b
~
2
,
…
,
b
~
n
} denote its Gram-Schmidt orthogonalization of basis B. It is iteratively defined as follows: b
~
1
=
b
1, and b
~
i is the component of b
i orthogonal to span(
b
1
,
b
2
,
…
,
b
i
-
1
) for i
=
2,3
,
…
,
n.Definition 2 (see [25]).
Given a matrixA
∈
Z
q
n
×
m for some q, m, n, its q-ary lattice is defined as follows:
(2)
Λ
q
⊥
(
A
)
=
{
z
∈
Z
m
:
A
z
=
0
mod
⁡
q
}
.
We also define the coset for any y
∈
Z
q
n that is generated by the columns of A as
(3)
Λ
q
y
(
A
)
=
{
z
∈
Z
m
:
A
z
=
y
mod
⁡
q
}
.Definition 3 (see [26]).
Given any vectorc and real s
>
0, a Gaussian function on R
n centered at c with parameter s is defined by
(4)
ρ
s
,
c
(
x
)
=
e
-
π
∥
x
-
c
∥
2
/
s
2
.
For any vectorc, real s
>
0, and n-dimensional lattice Λ, the discrete Gaussian distribution over Λ is defined as follows:
(5)
∀
x
∈
Λ
,
D
Λ
,
s
,
c
(
x
)
=
ρ
s
,
c
(
x
)
ρ
s
,
c
(
Λ
)
,
where ρ
s
,
c
(
Λ
)
=
∑
x
∈
Λ
‍
ρ
s
,
c
(
x
).Definition 4 (small integer solution (SIS) problem [26]).
Given an integerq, a real β
>
0, and a matrix A
∈
Z
q
n
×
m, the goal of SIS
n
,
m
,
q
,
β is to find a vector z
∈
Z
m for satisfying z
∈
Λ
q
⊥
(
A
)
∖
{
0
} and ∥
z
∥
≤
β, where Λ
q
⊥
(
A
)
=
{
z
∈
Z
m
:
A
z
=
0
mod
⁡
q
}.Proposition 5 (hardness of SIS problem [26]).
Given security parametern, any poly-bounded m, β
=
p
o
l
y
(
n
), and any prime q
≥
β
·
ω
(
n
log
⁡
n
), the average-case problem S
I
S
n
,
m
,
q
,
β is as hard as approximating the SIVP problem in the worst case to within certain γ
=
β
·
O
~
(
n
) factors.


## 2.3. Some Algorithms

We recall some algorithms for our construction and security proof later.Lemma 6 (see [27]).
Letq
≥
3 be odd and m
=
⌈
6
n
log
⁡
q
⌉. There is a probabilistic polynomial time algorithm T
r
a
p
G
e
n
(
q
,
n
) that outputs a pair (
A
∈
Z
q
n
×
m
,
T
A
∈
Z
m
×
m
) such that A is statistically close to a uniform matrix in Z
q
n
×
m and T
A is a basis for Λ
q
⊥
(
A
) satisfying
(6)
∥
T
~
A
∥
≤
O
(
n
log
⁡
q
)
,
∥
T
A
∥
≤
O
(
n
log
⁡
q
)
with all but negligible probability in n.
For simplicity, we letL
=
O
(
n
log
⁡
q
) denote the maximum Gram-Schimidt norm of a basis produced by T
r
a
p
G
e
n
(
q
,
n
).Lemma 7 (see [15, 26]).
Letq
≥
2 and A be a matrix in Z
q
n
×
m with m
>
n. Let T
A be a basis for Λ
q
⊥
(
A
) and σ
≥
∥
T
~
A
∥
ω
(
log
⁡
m
). Then for any u
∈
Z
q
n,(1)
P
r
[
x
~
D
Λ
q
u
(
A
)
,
σ
:
∥
x
∥
>
σ
m
]
≤
n
e
g
l
(
n
);
(2)
there is a probabilistic polynomial time algorithmS
a
m
p
l
e
P
r
e
(
A
,
T
A
,
u
,
σ
) that returns x
∈
Λ
q
u
(
A
) sampled from a distribution statistically close to D
Λ
q
u
(
A
)
,
σ.Lemma 8 (see [18]).
Letq
>
2, m
>
n, and σ
>
∥
T
~
B
∥
s
R
ω
(
log
⁡
m
). There exists a polynomial time algorithm S
a
m
p
l
e
R
i
g
h
t
(
A
,
B
,
R
,
T
B
,
u
,
σ
) that takes a matrix A
∈
Z
q
n
×
k, a rank n matrix B
∈
Z
q
n
×
m, a matrix R
∈
Z
k
×
m, and a short basis T
B of Λ
q
⊥
(
B
) as inputs and outputs a vector e
∈
Z
m
+
k distributed statistically close to D
Λ
q
u
(
F
2
)
,
σ, where F
2
:
=
A
∥
(
A
R
+
B
) and s
R
:
=
∥
R
∥
=
sup
∥
x
∥
=
1
∥
R
x
∥.Lemma 9 (see [18]).
There exists a polynomial time algorithmS
a
m
p
l
e
B
a
s
i
s
L
e
f
t
(
A
,
M
,
T
A
,
0
,
σ
) that takes a matrix A
∈
Z
q
n
×
m
1, a matrix M
∈
Z
q
n
×
m
2, and a short basis T
A of Λ
q
⊥
(
A
) as inputs and outputs a basis T
F
1 of Λ
q
⊥
(
F
1
) with σ
>
∥
T
~
A
∥
ω
(
log
⁡
(
m
1
+
m
2
)
) and ∥
T
~
F
1
∥
=
∥
T
~
A
∥, where F
1
:
=
A
∥
M.Lemma 10 (see [18]).
There exists a polynomial time algorithmS
a
m
p
l
e
B
a
s
i
s
R
i
g
h
t
(
A
,
B
,
R
,
T
B
,
0
,
σ
) that takes matrices A
∈
Z
q
n
×
k, M
∈
Z
q
n
×
m, and R
∈
{
1
,
-
1
}
k
×
m and a short basis T
B of Λ
q
⊥
(
B
) as inputs and outputs a basis T
F
2 of Λ
q
⊥
(
F
2
) with σ
>
∥
T
~
B
∥
s
R
ω
(
log
⁡
(
m
)
) and ∥
T
~
F
2
∥
≤
∥
T
~
B
∥
(
s
R
+
1
), where F
2
:
=
A
∥
(
A
R
+
B
).


## 3. The Model of FIBS

We recall the notation of FIBS scheme and security model from [21] in this section. A fuzzy identity-based signature scheme consists of four algorithms as follows.(i)
S
e
t
u
p
(
1
n
): this probabilistic algorithm takes a security parameter 1
n as an input and outputs the public parameters PP that contain an error tolerance parameter d and master key MK.
(ii)
E
x
t
r
a
c
t
(
MK
,
ID
): this probabilistic algorithm takes the master key MK and an identity ID as inputs and outputs a secret key s
k
ID for identity ID.
(iii)
S
i
g
n
(
PP
,
s
k
ID
,
μ
): this probabilistic algorithm takes public parameters PP, a private key s
k
ID associated with ID, and a message μ as inputs and outputs the signature σ
ID
,
μ on message μ for identity ID.
(iv)
V
e
r
i
f
y
(
I
D
′
,
μ
,
σ
ID
,
μ
): this deterministic algorithm takes identity I
D
′ such that |
ID
∩
I
D
′
|
≥
d, the message μ, and the corresponding signature σ
ID
,
μ as inputs and returns a bit b, where b
=
1 means that the signature is valid.For correctness purposes, for any fixedID, and arbitrary I
D
′ such that |
ID
∩
I
D
′
|
≥
d, it holds that
(7)
P
r
[
Verify
(
I
D
′
,
μ
,
S
i
g
n
(
s
k
ID
,
μ
)
)
=
1
]
=
1
-
negl
(
n
)
.We consider the security model of FIBS scheme as strong unforgeable against selective chosen-identity and adaptive chosen-message attacks (SU-sID-CMA). Strong unforgeability under adaptive chosen message attacks (SU-CMA) is stronger than existential unforgeability (EU-CMA) in the sense that the adversary is not restricted by the security model artificially. In EU-CMA, the adversary is only allowed to output a signature for a fresh messagem
*
≠
m
i, where the signature of m
i was known by adversary, while, the SU-CMA adversary is also allowed to output a fresh signature for one of the m
i.LetA be an adversary assumed to be a probabilistic turing machine taking a security parameter n as an input. Consider the following game in which A interacts with a challenger C.(i)
Init: the adversary A declares the target identity I
D
*
=
(
i
d
1
*
,
i
d
2
*
,
…
,
i
d
l
*
).
(ii)
Setup: the challenger C runs theSetup phase of the algorithm and tells the public parameters to adversary A.
(iii)
Queries: the adversary A launches a number of different queries for the challenger C.
(1)
Extract query: the adversary A issues private key queries for any identities η
i, where |
η
i
∩
I
D
*
|
<
d.
(2)
Sign query: the adversary A can ask for the signature of any identities η
i on any message μ.
(iv)
Forgery: the adversary A outputs (
I
D
*
,
μ
*
,
σ
ID
,
μ
*
). A succeeds if the following conditions hold:
(1)
Verify: (
I
D
*
,
μ
*
,
σ
ID
,
μ
*
)
=
1;
(2)
for any tuple(
ID
,
μ
,
σ
ID
,
μ
) that is generated during the Sign queries, we have (a) |
I
D
*
∩
ID
|
≥
d and μ
≠
μ
* or (b) |
I
D
*
∩
ID
|
<
d.We defineA
′s success probability by
(8)
Ad
v
FIBS
,
A
SU-sID-CMA
(
n
)
=
Pr
[
(
Verify
(
I
D
*
,
μ
*
,
σ
ID
,
μ
*
)
)
=
1
]
.A fuzzy identity-based signature (FIBS) scheme is said to be SU-sID-CMA secure ifAd
v
FIBS
,
A
SU-sID-CMA
(
n
) is negligible in the security parameter n.More stronger security model, strong unforgeability against adaptive chosen-identity and adaptive chosen-message attacks (SU-aID-CMA), can be obtained from SU-sID-CMA by a generic transformation that uses Chameleon hash function [28].


## 4. The FIBS Construction

Our construction is made of four algorithms as follows. In Section5.1, we will further analyse the parameters.(i)
S
e
t
u
p
(
1
n
): this is a probabilistic algorithm that takes security parameter n as an input and sets the parameters (
l
,
d
,
k
,
q
,
m
,
s
1
,
s
2
), where l is the identity size, d (d
<
l) is the error tolerance parameters, k is the length of message, q
=
poly
(
n
) is a prime, m
>
6
n
log
⁡
q is the dimension of lattice, and s
1 and s
2 are Gaussian parameters; then the algorithm performs the following steps.
(1)
Use algorithmTrapGen for generating matrices A
i
,
b
∈
Z
q
n
×
m and corresponding trapdoors S
i
,
b
∈
Z
m
×
m, where i
∈
[
l
], b
∈
{
0,1
}, and ∥
S
~
i
,
b
∥
≤
O
(
n
log
⁡
q
)
=
L.
(2)
Select uniformly random matricesB
i, C
i from Z
q
n
×
m, where i
∈
[
l
]. Draw k
+
1 independent matrices D
j from Z
q
n
×
m for j
∈
{
0,1
,
2
,
…
,
k
}. Select a random nonzero vector y
∈
Z
q
n.
(3)
LetH
:
Z
q
n
→
Z
q
n
×
n be the full rank differences map as defined in [18].
(4)
Output public parametersPP
=
(
{
A
i
,
b
}
i
∈
[
l
]
,
b
∈
{
0,1
}
,
{
B
i
}
i
∈
[
l
], {
C
i
}
i
∈
[
l
]
,
{
D
j
}
j
∈
{
0,1
,
2
,
…
,
k
}
,
y
,
H
) and master secret key MK
=
(
{
S
i
,
b
}
i
∈
[
l
]
,
b
∈
{
0,1
}
).
(ii)
E
x
t
r
a
c
t
(
MK
,
ID
): this is a probabilistic algorithm that takes the master key MK and an identity ID
=
(
i
d
1
,
i
d
2
,
…
,
i
d
l
)
∈
{
0,1
}
l as inputs and then performs the following steps.
(1)
Call algorithmS
i
,
i
d
i
′
←
S
a
m
p
l
e
B
a
s
i
s
L
e
f
t
(
A
i
,
i
d
i
,
B
i
+
H
(
ID
,
i
d
i
,
i
)
C
i
,
S
i
,
i
d
i
,
0
,
s
1
) for all i
∈
[
l
] (the i
d
i can be first expanded to {
0,1
}
*, hashing it to Z
q
n using a collision resistant hash). Let F
i
,
i
d
i
=
A
i
,
i
d
i
∥
B
i
+
H
(
ID
,
i
d
i
,
i
)
C
i; then F
i
,
i
d
i
S
i
,
i
d
i
′
=
0
(
mod
⁡
q
).
(2)
Output the secret keys
k
ID
=
(
S
1
,
i
d
1
′
,
S
2
,
i
d
2
′
,
…
,
S
l
,
i
d
l
′
) for identity ID.
(iii)
S
i
g
n
(
PP
,
s
k
ID
,
μ
): this is a probabilistic algorithm that takes public parameters PP, a private key s
k
ID associated with ID, and a message μ as inputs and then performs the following steps.
(1)
For every coordinate ofy, construct l shares of y
1
,
y
2
,
…
,
y
n independently using a Shamir secret-sharing scheme. Namely, for each i
∈
[
n
], choose a uniformly random polynomial p
i
(
x
)
∈
Z
q
[
x
] of degree d
-
1 such that p
i
(
0
)
=
y
i. Construct the ith share vector y
^
i
=
(
p
1
(
i
)
,
p
2
(
i
)
,
…
,
p
n
(
i
)
)
∈
Z
q
n. Thus for all I
⊆
[
l
] satisfying |
I
|
≥
d, we can compute fractional Lagrangian coefficients L
i such that y
=
∑
i
∈
I
‍
L
i
y
^
i
(
mod
⁡
q
).
(2)
For messageμ
∈
{
0,1
}
k, let D
μ
=
∑
j
=
0
k
‍
(
-
1
)
μ
[
j
]
×
D
j, where μ
[
0
]
=
0.
(3)
Fori
∈
[
l
], randomly choose σ
i
2
←
D
Z
m
,
s
2
,
0.
(4)
Run algorithmσ
i
1
←
S
a
m
p
l
e
P
r
e
(
F
i
,
i
d
i
,
S
i
,
i
d
i
′
,
y
^
i
-
D
μ
σ
i
2
,
s
2
). Let σ
i
=
(
σ
i
1
σ
i
2
).
(5)
Output signatureσ
ID
,
μ
=
(
μ
,
(
σ
1
,
σ
2
,
…
,
σ
l
)
,
ID
).
(iv)
V
e
r
i
f
y
(
I
D
′
,
μ
,
σ
ID
,
μ
): this is a deterministic algorithm that takes identity I
D
′, a message μ, and a signature σ
ID
,
μ as inputs and then performs the following steps.
(1)
LetI
⊆
[
l
] denote the set of matching bits in ID and ID
′.
(2)
If|
I
|
<
d, output ⊥.
(3)
Otherwise, computeF
i
,
i
d
i
=
A
i
,
i
d
i
∥
B
i
+
H
(
ID
,
i
d
i
,
i
)
C
i for all i
∈
[
l
] and D
μ
=
∑
j
=
0
k
‍
(
-
1
)
μ
[
j
]
D
j. If (a) ∥
σ
i
∥
≤
s
2
3
m for all i
∈
[
l
] and (b) ∑
i
∈
I
‍
L
i
(
F
i
,
i
d
i
∥
D
μ
)
σ
i
=
∑
i
∈
I
‍
L
i
y
^
i
=
y, where L
i
=
∏
i
∈
I
,
j
≠
i
‍
(
(
0
-
j
)
/
(
i
-
j
)
) is the corresponding fractional Lagrangian coefficient, then accept the signature σ
ID
,
μ. Otherwise, reject the signature σ
ID
,
μ.Remark 11.
In the verification equality, the only role ofI
D
′ is to compute the subset I. The F
i
,
i
d
i equals A
i
,
i
d
i
∥
B
i
+
H
(
ID
,
i
d
i
,
i
)
C
i instead of A
i
,
i
d
i
∥
B
i
+
H
(
I
D
′
,
i
d
i
,
i
)
C
i. This can be explained that the identity ID is a part of the signature σ
ID
,
μ. Designing a more graceful scheme such that the verification equality needs neither ID nor I
D
′ directly (like scheme based on pairing [6]) is our further research direction.


## 5. Correctness and Security

### 5.1. Correctness and Parameters

For proving the consistency of the scheme, we only consider the case|
I
|
<
d, where I is the matching bits set of ID and I
D
′. First, we give the correctness of our scheme.According to Lemma7, we know that, for every i
∈
[
l
], ∥
σ
i
1
∥
≤
s
2
2
m and ∥
σ
i
2
∥
≤
s
2
m. Thus, ∥
σ
i
∥
=
∥
σ
i
1
σ
i
2
∥
≤
∥
σ
i
1
∥
2
+
∥
σ
i
2
∥
2
=
s
2
3
m.On the other hand, for everyi
∈
[
l
], vector σ
i
1 satisfies F
i
,
i
d
i
σ
i
1
=
y
^
i
-
D
μ
σ
i
2 from Lemma 7. In other words, (
F
i
,
i
d
i
∥
D
μ
)
(
σ
i
1
σ
i
2
)
=
y
^
i. Therefore, for subset I, ∑
i
∈
I
‍
L
i
(
F
i
,
i
d
i
∥
D
μ
)
σ
i
=
∑
i
∈
I
‍
L
i
y
^
i
=
y.Secondly, for the scheme working correctly, we must satisfy the following conditions.(i)
AlgorithmTrapGen can operate, so m
≥
6
n
log
⁡
q.
(ii)
AlgorithmSampleBasisLeft used inExtract phase can operate; that is, s
1
≥
L
ω
(
log
⁡
(
2
m
)
), where L
=
O
(
n
log
⁡
q
).
(iii)
AlgorithmSamplePre used inSign phase can operate; that is, s
2
≥
L
ω
(
log
⁡
(
2
m
)
), where L
=
O
(
n
log
⁡
q
).Takingn as a security parameter, let δ satisfy n
δ
>
⌈
log
⁡
q
⌉
=
O
(
log
⁡
n
). The parameters (
m
,
s
1
,
s
2
) are set as follows: m
=
6
n
1
+
δ, s
1
=
s
2
=
m
ω
(
log
⁡
(
2
m
)
).


### 5.2. Security

Theorem 12.
The FIBS scheme is SU-sID-CMA in the standard model under the hardness assumption SIS problem. LetA be an adversary that makes at most q
e extract queries and q
s signature queries and produces a successful forgery against our FIBS scheme with probability ϵ; then there exists an algorithm B that solves the S
I
S
n
,
l
m
,
q
,
β problem with probability ϵ
′
≥
[
(
1
/
2
)
(
1
-
(
1
/
3
)
l
)
+
(
1
/
2
)
]
·
(
1
/
q
)
·
(
1
-
(
(
q
e
+
q
s
)
/
q
)
)
ϵ, where β
=
2
s
2
l
m
(
1
+
12
2
m
)
(
1
+
s
2
m
(
k
+
1
)
).Proof.
We prove this theorem by playing the classical provable secure game between an adversaryA and a challenger C.(i)
Init: let I
D
* be the identity that A intends to attack. The challenger C is invoked on a random SIS instance A
∈
Z
q
n
×
l
m and is asked to return an admissible solution e
0
∈
Z
l
m such that A
e
0
=
0
(
mod
⁡
q
) and 0
≠
∥
e
0
∥
≤
β.
(ii)
Setup: the challenger C generates the public parameters PP as follows.
(a)
Parse SIS instanceA as matrix A
1
,
A
2
,
…
,
A
l
∈
Z
q
n
×
m; choose randomly l uniformly random matrices A
1
′
,
A
2
′
,
…
,
A
l
′
∈
Z
q
n
×
m.
(b)
LetA
i
,
i
d
i
*
=
A
i, A
i
,
1
-
i
d
i
*
=
A
i
′ for i
∈
[
l
].
(c)
Choose randomlyl vectors x
1
,
x
2
,
…
,
x
l from D
Z
m
,
s
2. Let y
^
i
=
A
i
,
i
d
i
*
x
i and regard y
^
i as ith share vector of y. According to Shamir secret-sharing scheme, there exist fractional Lagrangian coefficients L
i for recovering y; that is, y
=
∑
i
∈
I
‍
L
i
y
^
i
(
mod
⁡
q
) for all I
⊆
[
l
] satisfying |
I
|
≥
d.
(d)
Run the algorithmTrapGen for generating the matrices C
i
,
E
i and corresponding trapdoors S
C
i, S
E
i. Let R
i be a m
×
m matrix chosen at random from {
-
1,1
}
m
×
m for i
∈
[
l
], and let R
j
′ be a 2
m
×
m matrix sampling each column from D
Z
2
m
,
s
2 for j
∈
[
k
] independently.
(e)
Pickk uniformly random scalars h
1
,
h
2
,
…
,
h
k
∈
Z
q and fix h
0
=
1
∈
Z
q. Set B
i
=
A
i
,
i
d
i
R
i
-
H
1
(
I
D
*
,
i
d
i
*
,
i
)
C
i and D
j
=
F
i
,
i
d
i
R
j
′
+
h
j
E
i, where F
i
,
i
d
i
=
A
i
,
i
d
i
∥
B
i
+
H
(
ID
,
i
d
i
,
i
)
C
i.
(iii)
Extract queries: the adversary A issues private key queries for any identity ID satisfying |
ID
∩
I
D
*
|
<
d. Considering a query for the private key of an identity ID, C does not know the master key {
S
i
,
b
}
i
∈
[
l
]
,
b
∈
{
0,1
}. For responding to a private key query for ID, the challenger uses the trapdoors S
C
i to produce short basis for Λ
q
⊥
(
F
i
,
i
d
i
), where F
i
,
i
d
i
=
A
i
,
i
d
i
∥
B
i
+
H
(
ID
,
i
d
i
,
i
)
C
i
=
A
i
,
i
d
i
∥
A
i
,
i
d
i
R
i + (
H
(
ID
,
i
d
i
,
i
)
-
H
(
I
D
*
,
i
d
i
*
,
i
)
)
C
i. For |
ID
∩
I
D
*
|
<
d, H
(
ID
,
i
d
i
,
i
)
-
H
(
I
D
*
,
i
d
i
*
,
i
) is nonsingular and therefore S
C
i is also a trapdoor for Λ
q
⊥
(
M
i
d
i
), where M
i
d
i
=
(
H
(
ID
,
i
d
i
,
i
)
-
H
(
I
D
*
,
i
d
i
*
,
i
)
)
C
i. The challenger can now respond to the private key query by running S
i
,
i
d
i
′
←
S
a
m
p
l
e
B
a
s
i
s
R
i
g
h
t
(
A
i
,
i
d
i
,
M
i
d
i
,
R
i
,
S
C
i
,
0
,
s
1
) and sending (
S
1
,
i
d
1
′
,
S
2
,
i
d
2
′
,
…
,
S
l
,
i
d
l
′
) to the adversary A.
(iv)
Sign queries: the adversary A asks signature for any identities on any message. Consider a query for a signature of ID on message μ.
(a)
If|
ID
∩
I
D
*
|
=
l, that is, ID
=
I
D
*, then the challenger C will try to construct a signature as aforementioned for extracting query using trapdoors S
E
i. Then, for every i
∈
[
l
], F
i
,
i
d
i
=
A
i
,
i
d
i
∥
B
i
+
H
(
ID
,
i
d
i
,
i
)
C
i = A
i
,
i
d
i
∥
A
i
,
i
d
i
R
i. Compute the matrix R
μ
=
∑
j
=
0
k
‍
(
-
1
)
μ
[
j
]
R
j
′ and the scalar h
μ
=
∑
j
=
0
k
‍
(
-
1
)
μ
[
j
]
h
j. Note that D
μ
=
∑
j
=
0
k
‍
(
-
1
)
μ
[
j
]
D
j
=
F
i
,
i
d
i
R
μ
+
h
μ
E
i. If h
μ
=
0
(
mod
⁡
q
), abort the simulation. Otherwise, compute the matrix F
i
,
i
d
i
,
μ
=
F
i
,
i
d
i
∥
F
i
,
i
d
i
R
μ
+
h
μ
E
i and run the algorithm σ
i
←
S
a
m
p
l
e
R
i
g
h
t
(
F
i
,
i
d
i
,
h
μ
E
i
,
R
μ
,
S
E
i
,
y
^
i, s
2
). Finally, respond to the adversary A with the signature (
μ
,
(
σ
1
,
σ
2
,
…
,
σ
l
)
,
ID
).
Now, we prove that the signature is a valid signature and the distribution is identical to the real one. First, according to lemma8, we have (
F
i
,
i
d
i
∥
F
i
,
i
d
i
R
μ
+
h
μ
E
i
)
σ
i
=
y
^
i for all i
∈
[
l
] and σ
i is with negligible statistical distance from the distribution D
Λ
q
y
^
i
(
Q
i
d
i
)
,
s
2, where Q
i
d
i
=
F
i
,
i
d
i
∥
F
i
,
i
d
i
R
μ
+
h
μ
E
i. Therefore, (
F
i
,
i
d
i
∥
D
μ
)
σ
i
=
y
^
i due to the assumptions that R
μ
=
∑
j
=
0
k
‍
(
-
1
)
μ
[
j
]
R
j
′ and h
μ
=
∑
j
=
0
k
‍
(
-
1
)
μ
[
j
]
h
j. In addition, ∥
σ
i
∥
≤
s
2
3
m for all i
∈
[
l
] from Lemma 7(1). Therefore, (
μ
,
(
σ
1
,
σ
2
,
…
,
σ
l
)
,
ID
) is a valid signature.
(b)
If|
ID
∩
I
D
*
|
<
d, the challenger C uses the secret key from extract query for responding the signature query by the signature algorithm.
(c)
Ifd
≤
|
ID
∩
I
D
*
|
<
l, the challenger C will firstly compute the secret key for identity ID like the extract query. Then, respond with the signature query as aforementioned.
(v)
Forgery: the adversary A outputs a valid forgery signature (
μ
*
,
(
σ
1
*
,
σ
2
*
,
…
,
σ
l
*
)
,
I
D
*
) for the target identity I
D
*. Then the challenger C computes the matrix R
μ
*
=
∑
j
=
0
k
‍
(
-
1
)
μ
*
[
j
]
R
j
′, h
*
=
∑
j
=
0
k
‍
(
-
1
)
μ
*
[
j
]
h
j. If h
*
≠
0
(
mod
⁡
q
), he aborts the simulation. According to whether the message μ
* is queried or not, there are two different cases that need to be considered.
(a)
The messageμ
* is queried in the Sign queries. Assume that the challenger responded (
μ
*
,
(
σ
1
′
,
σ
2
′
,
…
,
σ
l
′
)
,
I
D
*
) for message μ
* in the Sign queries. Then for all i
∈
[
l
], parse σ
i
*
=
[
σ
i
1
*
σ
i
2
*
σ
i
3
*
], σ
i
′
=
[
σ
i
1
′
σ
i
2
′
σ
i
3
′
],
(9)
A
i
,
i
d
i
*
[
(
R
μ
*
(
1
)
+
R
i
R
μ
*
(
2
)
)
(
σ
i
1
*
-
σ
i
1
′
)
+
R
i
(
σ
i
2
*
-
σ
i
2
′
)
h
h
h
h
h
+
(
R
μ
*
(
1
)
+
R
i
R
μ
*
(
2
)
)
(
σ
i
3
*
-
σ
i
3
′
)
]
=
0
(
mod
⁡
q
)
,
whereR
μ
*
(
1
) is the first m rows of matrix R
μ
* and R
μ
*
(
2
) is the last m rows of matrix R
μ
*. Let e
i
*
=
(
σ
i
1
*
-
σ
i
1
′
)
+
R
i
(
σ
i
2
*
-
σ
i
2
′
) + (
R
μ
*
(
1
)
+
R
i
R
μ
*
(
2
)
)
(
σ
i
3
*
-
σ
i
3
′
); then ∥
e
i
*
∥
≤
2
s
2
m
(
1
+
12
2
m
)
(
1
+
s
2
m
(
k
+
1
)
). The challenger C returns e
0
=
[
e
1
*
e
2
*
⋯
e
l
*
] as solution to A
e
0
=
0
(
mod
⁡
q
) and ∥
e
0
∥
≤
2
s
2
l
m
(
1
+
12
2
m
)
(
1
+
s
2
m
(
k
+
1
)
)
=
β.
In addition, According to Lemma26 of [16], Pr
{
e
i
*
≠
0
}
≥
2
/
3; therefore, the probability of e
0
≠
0 is at least 1
-
(
1
/
3
)
l.
(b)
The messageμ
* is not queried in the Sign queries. For every i
∈
[
l
], separate σ
i
* into [
σ
i
1
*
σ
i
2
*
σ
i
3
*
]; then
(10)
A
i
,
i
d
i
*
[
σ
i
1
*
+
R
i
σ
i
2
*
+
(
R
μ
*
(
1
)
+
R
i
R
μ
*
(
2
)
)
σ
i
3
*
-
x
i
]
=
0
(
mod
⁡
q
)
and∥
σ
i
1
*
+
R
i
σ
i
2
*
+
(
R
μ
*
(
1
)
+
R
i
R
μ
*
(
2
)
)
σ
i
3
*
-
x
i
∥ ≤ s
2
m
(
2
+
12
2
m
+
s
2
m
(
k
+
1
)
(
1
+
12
2
m
)
), where R
μ
*
(
1
) is the first m rows of matrix R
μ
* and R
μ
*
(
2
) is the last m rows of matrix R
μ
*. Let e
i
*
=
σ
i
1
*
+
R
i
σ
i
2
*
+
(
R
μ
*
(
1
)
+
R
i
R
μ
*
(
2
)
)
σ
i
3
*
-
x
i, and the challenger C returns e
0
=
[
e
1
*
e
2
*
⋯
e
l
*
] as solution to A
e
0
=
0
(
mod
⁡
q
) and ∥
e
0
∥
≤
s
2
l
m
(
2
+
12
2
m
+
s
2
m
(
k
+
1
)
(
1
+
12
2
m
)
) ≤ 2
s
2
l
m
(
1
+
12
2
m
)
(
1
+
s
2
m
(
k
+
1
)
)
=
β.
In addition, according to Lemma2.9 of [15], e
i
*
≠
0 with overwhelming probability; therefore, e
0
≠
0 with overwhelming probability.
Furthermore, according to Lemma27 of [16], the simulation completes both the Queries and the Forgery phases without aborting with probability of at least (
1
/
q
)
(
1
-
(
(
q
e
+
q
s
)
/
q
)
). Therefore, the probability that the challenger C can return a SIS solution is ϵ
′
≥
[
(
1
/
2
)
(
1
-
(
1
/
3
)
l
)
+
(
1
/
2
)
]
·
(
1
/
q
)
·
(
1
-
(
(
q
e
+
q
s
)
/
q
)
)
ϵ.Remark 13.
In fact, there is a weakness in the above security proof. Specifically, in the forge phase, the adversary outputs a signature signed byI
D
* instead of I
D
′
(
|
I
D
′
∩
I
D
*
|
≥
d
). If we change it into I
D
′ that satisfies |
I
D
′
∩
I
D
*
|
≥
d and the signature can be verified correctly, the SIS hardness problem could not be embedded and the SIS solution will not be found. In addition, there is a similar question in the security proof of [21]. We think this problem is the bottleneck of constructing fuzzy attribute-based signature from lattices, and we will solve this problem as a long-term research direction.


## 5.1. Correctness and Parameters

For proving the consistency of the scheme, we only consider the case|
I
|
<
d, where I is the matching bits set of ID and I
D
′. First, we give the correctness of our scheme.According to Lemma7, we know that, for every i
∈
[
l
], ∥
σ
i
1
∥
≤
s
2
2
m and ∥
σ
i
2
∥
≤
s
2
m. Thus, ∥
σ
i
∥
=
∥
σ
i
1
σ
i
2
∥
≤
∥
σ
i
1
∥
2
+
∥
σ
i
2
∥
2
=
s
2
3
m.On the other hand, for everyi
∈
[
l
], vector σ
i
1 satisfies F
i
,
i
d
i
σ
i
1
=
y
^
i
-
D
μ
σ
i
2 from Lemma 7. In other words, (
F
i
,
i
d
i
∥
D
μ
)
(
σ
i
1
σ
i
2
)
=
y
^
i. Therefore, for subset I, ∑
i
∈
I
‍
L
i
(
F
i
,
i
d
i
∥
D
μ
)
σ
i
=
∑
i
∈
I
‍
L
i
y
^
i
=
y.Secondly, for the scheme working correctly, we must satisfy the following conditions.(i)
AlgorithmTrapGen can operate, so m
≥
6
n
log
⁡
q.
(ii)
AlgorithmSampleBasisLeft used inExtract phase can operate; that is, s
1
≥
L
ω
(
log
⁡
(
2
m
)
), where L
=
O
(
n
log
⁡
q
).
(iii)
AlgorithmSamplePre used inSign phase can operate; that is, s
2
≥
L
ω
(
log
⁡
(
2
m
)
), where L
=
O
(
n
log
⁡
q
).Takingn as a security parameter, let δ satisfy n
δ
>
⌈
log
⁡
q
⌉
=
O
(
log
⁡
n
). The parameters (
m
,
s
1
,
s
2
) are set as follows: m
=
6
n
1
+
δ, s
1
=
s
2
=
m
ω
(
log
⁡
(
2
m
)
).


## 5.2. Security

Theorem 12.
The FIBS scheme is SU-sID-CMA in the standard model under the hardness assumption SIS problem. LetA be an adversary that makes at most q
e extract queries and q
s signature queries and produces a successful forgery against our FIBS scheme with probability ϵ; then there exists an algorithm B that solves the S
I
S
n
,
l
m
,
q
,
β problem with probability ϵ
′
≥
[
(
1
/
2
)
(
1
-
(
1
/
3
)
l
)
+
(
1
/
2
)
]
·
(
1
/
q
)
·
(
1
-
(
(
q
e
+
q
s
)
/
q
)
)
ϵ, where β
=
2
s
2
l
m
(
1
+
12
2
m
)
(
1
+
s
2
m
(
k
+
1
)
).Proof.
We prove this theorem by playing the classical provable secure game between an adversaryA and a challenger C.(i)
Init: let I
D
* be the identity that A intends to attack. The challenger C is invoked on a random SIS instance A
∈
Z
q
n
×
l
m and is asked to return an admissible solution e
0
∈
Z
l
m such that A
e
0
=
0
(
mod
⁡
q
) and 0
≠
∥
e
0
∥
≤
β.
(ii)
Setup: the challenger C generates the public parameters PP as follows.
(a)
Parse SIS instanceA as matrix A
1
,
A
2
,
…
,
A
l
∈
Z
q
n
×
m; choose randomly l uniformly random matrices A
1
′
,
A
2
′
,
…
,
A
l
′
∈
Z
q
n
×
m.
(b)
LetA
i
,
i
d
i
*
=
A
i, A
i
,
1
-
i
d
i
*
=
A
i
′ for i
∈
[
l
].
(c)
Choose randomlyl vectors x
1
,
x
2
,
…
,
x
l from D
Z
m
,
s
2. Let y
^
i
=
A
i
,
i
d
i
*
x
i and regard y
^
i as ith share vector of y. According to Shamir secret-sharing scheme, there exist fractional Lagrangian coefficients L
i for recovering y; that is, y
=
∑
i
∈
I
‍
L
i
y
^
i
(
mod
⁡
q
) for all I
⊆
[
l
] satisfying |
I
|
≥
d.
(d)
Run the algorithmTrapGen for generating the matrices C
i
,
E
i and corresponding trapdoors S
C
i, S
E
i. Let R
i be a m
×
m matrix chosen at random from {
-
1,1
}
m
×
m for i
∈
[
l
], and let R
j
′ be a 2
m
×
m matrix sampling each column from D
Z
2
m
,
s
2 for j
∈
[
k
] independently.
(e)
Pickk uniformly random scalars h
1
,
h
2
,
…
,
h
k
∈
Z
q and fix h
0
=
1
∈
Z
q. Set B
i
=
A
i
,
i
d
i
R
i
-
H
1
(
I
D
*
,
i
d
i
*
,
i
)
C
i and D
j
=
F
i
,
i
d
i
R
j
′
+
h
j
E
i, where F
i
,
i
d
i
=
A
i
,
i
d
i
∥
B
i
+
H
(
ID
,
i
d
i
,
i
)
C
i.
(iii)
Extract queries: the adversary A issues private key queries for any identity ID satisfying |
ID
∩
I
D
*
|
<
d. Considering a query for the private key of an identity ID, C does not know the master key {
S
i
,
b
}
i
∈
[
l
]
,
b
∈
{
0,1
}. For responding to a private key query for ID, the challenger uses the trapdoors S
C
i to produce short basis for Λ
q
⊥
(
F
i
,
i
d
i
), where F
i
,
i
d
i
=
A
i
,
i
d
i
∥
B
i
+
H
(
ID
,
i
d
i
,
i
)
C
i
=
A
i
,
i
d
i
∥
A
i
,
i
d
i
R
i + (
H
(
ID
,
i
d
i
,
i
)
-
H
(
I
D
*
,
i
d
i
*
,
i
)
)
C
i. For |
ID
∩
I
D
*
|
<
d, H
(
ID
,
i
d
i
,
i
)
-
H
(
I
D
*
,
i
d
i
*
,
i
) is nonsingular and therefore S
C
i is also a trapdoor for Λ
q
⊥
(
M
i
d
i
), where M
i
d
i
=
(
H
(
ID
,
i
d
i
,
i
)
-
H
(
I
D
*
,
i
d
i
*
,
i
)
)
C
i. The challenger can now respond to the private key query by running S
i
,
i
d
i
′
←
S
a
m
p
l
e
B
a
s
i
s
R
i
g
h
t
(
A
i
,
i
d
i
,
M
i
d
i
,
R
i
,
S
C
i
,
0
,
s
1
) and sending (
S
1
,
i
d
1
′
,
S
2
,
i
d
2
′
,
…
,
S
l
,
i
d
l
′
) to the adversary A.
(iv)
Sign queries: the adversary A asks signature for any identities on any message. Consider a query for a signature of ID on message μ.
(a)
If|
ID
∩
I
D
*
|
=
l, that is, ID
=
I
D
*, then the challenger C will try to construct a signature as aforementioned for extracting query using trapdoors S
E
i. Then, for every i
∈
[
l
], F
i
,
i
d
i
=
A
i
,
i
d
i
∥
B
i
+
H
(
ID
,
i
d
i
,
i
)
C
i = A
i
,
i
d
i
∥
A
i
,
i
d
i
R
i. Compute the matrix R
μ
=
∑
j
=
0
k
‍
(
-
1
)
μ
[
j
]
R
j
′ and the scalar h
μ
=
∑
j
=
0
k
‍
(
-
1
)
μ
[
j
]
h
j. Note that D
μ
=
∑
j
=
0
k
‍
(
-
1
)
μ
[
j
]
D
j
=
F
i
,
i
d
i
R
μ
+
h
μ
E
i. If h
μ
=
0
(
mod
⁡
q
), abort the simulation. Otherwise, compute the matrix F
i
,
i
d
i
,
μ
=
F
i
,
i
d
i
∥
F
i
,
i
d
i
R
μ
+
h
μ
E
i and run the algorithm σ
i
←
S
a
m
p
l
e
R
i
g
h
t
(
F
i
,
i
d
i
,
h
μ
E
i
,
R
μ
,
S
E
i
,
y
^
i, s
2
). Finally, respond to the adversary A with the signature (
μ
,
(
σ
1
,
σ
2
,
…
,
σ
l
)
,
ID
).
Now, we prove that the signature is a valid signature and the distribution is identical to the real one. First, according to lemma8, we have (
F
i
,
i
d
i
∥
F
i
,
i
d
i
R
μ
+
h
μ
E
i
)
σ
i
=
y
^
i for all i
∈
[
l
] and σ
i is with negligible statistical distance from the distribution D
Λ
q
y
^
i
(
Q
i
d
i
)
,
s
2, where Q
i
d
i
=
F
i
,
i
d
i
∥
F
i
,
i
d
i
R
μ
+
h
μ
E
i. Therefore, (
F
i
,
i
d
i
∥
D
μ
)
σ
i
=
y
^
i due to the assumptions that R
μ
=
∑
j
=
0
k
‍
(
-
1
)
μ
[
j
]
R
j
′ and h
μ
=
∑
j
=
0
k
‍
(
-
1
)
μ
[
j
]
h
j. In addition, ∥
σ
i
∥
≤
s
2
3
m for all i
∈
[
l
] from Lemma 7(1). Therefore, (
μ
,
(
σ
1
,
σ
2
,
…
,
σ
l
)
,
ID
) is a valid signature.
(b)
If|
ID
∩
I
D
*
|
<
d, the challenger C uses the secret key from extract query for responding the signature query by the signature algorithm.
(c)
Ifd
≤
|
ID
∩
I
D
*
|
<
l, the challenger C will firstly compute the secret key for identity ID like the extract query. Then, respond with the signature query as aforementioned.
(v)
Forgery: the adversary A outputs a valid forgery signature (
μ
*
,
(
σ
1
*
,
σ
2
*
,
…
,
σ
l
*
)
,
I
D
*
) for the target identity I
D
*. Then the challenger C computes the matrix R
μ
*
=
∑
j
=
0
k
‍
(
-
1
)
μ
*
[
j
]
R
j
′, h
*
=
∑
j
=
0
k
‍
(
-
1
)
μ
*
[
j
]
h
j. If h
*
≠
0
(
mod
⁡
q
), he aborts the simulation. According to whether the message μ
* is queried or not, there are two different cases that need to be considered.
(a)
The messageμ
* is queried in the Sign queries. Assume that the challenger responded (
μ
*
,
(
σ
1
′
,
σ
2
′
,
…
,
σ
l
′
)
,
I
D
*
) for message μ
* in the Sign queries. Then for all i
∈
[
l
], parse σ
i
*
=
[
σ
i
1
*
σ
i
2
*
σ
i
3
*
], σ
i
′
=
[
σ
i
1
′
σ
i
2
′
σ
i
3
′
],
(9)
A
i
,
i
d
i
*
[
(
R
μ
*
(
1
)
+
R
i
R
μ
*
(
2
)
)
(
σ
i
1
*
-
σ
i
1
′
)
+
R
i
(
σ
i
2
*
-
σ
i
2
′
)
h
h
h
h
h
+
(
R
μ
*
(
1
)
+
R
i
R
μ
*
(
2
)
)
(
σ
i
3
*
-
σ
i
3
′
)
]
=
0
(
mod
⁡
q
)
,
whereR
μ
*
(
1
) is the first m rows of matrix R
μ
* and R
μ
*
(
2
) is the last m rows of matrix R
μ
*. Let e
i
*
=
(
σ
i
1
*
-
σ
i
1
′
)
+
R
i
(
σ
i
2
*
-
σ
i
2
′
) + (
R
μ
*
(
1
)
+
R
i
R
μ
*
(
2
)
)
(
σ
i
3
*
-
σ
i
3
′
); then ∥
e
i
*
∥
≤
2
s
2
m
(
1
+
12
2
m
)
(
1
+
s
2
m
(
k
+
1
)
). The challenger C returns e
0
=
[
e
1
*
e
2
*
⋯
e
l
*
] as solution to A
e
0
=
0
(
mod
⁡
q
) and ∥
e
0
∥
≤
2
s
2
l
m
(
1
+
12
2
m
)
(
1
+
s
2
m
(
k
+
1
)
)
=
β.
In addition, According to Lemma26 of [16], Pr
{
e
i
*
≠
0
}
≥
2
/
3; therefore, the probability of e
0
≠
0 is at least 1
-
(
1
/
3
)
l.
(b)
The messageμ
* is not queried in the Sign queries. For every i
∈
[
l
], separate σ
i
* into [
σ
i
1
*
σ
i
2
*
σ
i
3
*
]; then
(10)
A
i
,
i
d
i
*
[
σ
i
1
*
+
R
i
σ
i
2
*
+
(
R
μ
*
(
1
)
+
R
i
R
μ
*
(
2
)
)
σ
i
3
*
-
x
i
]
=
0
(
mod
⁡
q
)
and∥
σ
i
1
*
+
R
i
σ
i
2
*
+
(
R
μ
*
(
1
)
+
R
i
R
μ
*
(
2
)
)
σ
i
3
*
-
x
i
∥ ≤ s
2
m
(
2
+
12
2
m
+
s
2
m
(
k
+
1
)
(
1
+
12
2
m
)
), where R
μ
*
(
1
) is the first m rows of matrix R
μ
* and R
μ
*
(
2
) is the last m rows of matrix R
μ
*. Let e
i
*
=
σ
i
1
*
+
R
i
σ
i
2
*
+
(
R
μ
*
(
1
)
+
R
i
R
μ
*
(
2
)
)
σ
i
3
*
-
x
i, and the challenger C returns e
0
=
[
e
1
*
e
2
*
⋯
e
l
*
] as solution to A
e
0
=
0
(
mod
⁡
q
) and ∥
e
0
∥
≤
s
2
l
m
(
2
+
12
2
m
+
s
2
m
(
k
+
1
)
(
1
+
12
2
m
)
) ≤ 2
s
2
l
m
(
1
+
12
2
m
)
(
1
+
s
2
m
(
k
+
1
)
)
=
β.
In addition, according to Lemma2.9 of [15], e
i
*
≠
0 with overwhelming probability; therefore, e
0
≠
0 with overwhelming probability.
Furthermore, according to Lemma27 of [16], the simulation completes both the Queries and the Forgery phases without aborting with probability of at least (
1
/
q
)
(
1
-
(
(
q
e
+
q
s
)
/
q
)
). Therefore, the probability that the challenger C can return a SIS solution is ϵ
′
≥
[
(
1
/
2
)
(
1
-
(
1
/
3
)
l
)
+
(
1
/
2
)
]
·
(
1
/
q
)
·
(
1
-
(
(
q
e
+
q
s
)
/
q
)
)
ϵ.Remark 13.
In fact, there is a weakness in the above security proof. Specifically, in the forge phase, the adversary outputs a signature signed byI
D
* instead of I
D
′
(
|
I
D
′
∩
I
D
*
|
≥
d
). If we change it into I
D
′ that satisfies |
I
D
′
∩
I
D
*
|
≥
d and the signature can be verified correctly, the SIS hardness problem could not be embedded and the SIS solution will not be found. In addition, there is a similar question in the security proof of [21]. We think this problem is the bottleneck of constructing fuzzy attribute-based signature from lattices, and we will solve this problem as a long-term research direction.


## 6. Performance Analysis and Simulations

### 6.1. Comparison with the Scheme of [21]

The efficiency and security of our scheme and the scheme of [21] are summarized in Table 1, where the efficiency includes the size of storage space, the communication cost, and computation cost.Table 1
Performance comparison with the scheme of [21].
Length of PP
Length of MK
Length of skID
Length ofσ
[21]
2
l
m
n
log
⁡
(
p
q
)
2
l
m
2
log
⁡
(
p
q
)
4
l
m
2
log
⁡
(
p
q
)
2
l
m
log
⁡
(
p
q
)
Ours
(
4
l
+
k
+
1
)
m
n
log
⁡
q
+
n
log
⁡
q
2
l
m
2
log
⁡
q
4
l
m
2
log
⁡
q
3
l
m
log
⁡
q
Sign cost
Verify cost
Unforgeability
Model
[21]
n
SSS
†
d
MVP
§(p
q)
EU
♭<
ROM
♮
+l
PS
‡
(
p
q
)
+d
SMP
¶ (p
q)
Ours
n SSS
d MVP (q)
+l
DGS
£ (q)
+d SMP (q)
SU
♯
SM
∥
+l PS (q)
+k
MMA
♠ (q)
Note.  The units of public parameters size, master secret key size, private key of identity size, and signature size are bits. The base of the logarithm function is 2;SSS
† denotes Shamir secret sharing operation; PS
‡ denotes preimage sampling algorithm; MVP
§ denotes matrix and vector product (where the matrix form is (
n
×
2
m
) and the vector form is 2
m-row); SMP
¶ denotes scalar multiplication; EU
♭ denotes existential unforgeability; ROM
♮ denotes random oracle model; DGS
£ DGS denotes discrete Gaussian sampling algorithm; MMA
♠ denotes matrix and matrix addition; SU
♯ denotes strong unforgeability; SM
∥ denotes the standard model. The (p
q) and (q)  denote modules that are used in the corresponding operations.Firstly, we consider the size of storage space and the communication cost. Specifically, we compare the length of public parametersPP, the master secret key MK, and the private key of identity ID, which affect the the size of storage space. We also compare the length of the signature, which affects the communication cost.(i)
As for the size of the public parametersPP, the scheme of [21] needs 2
l matrices in Z
p
q
n
×
m; the size is about 2
l
n
m
log
⁡
(
p
q
). Our scheme needs (
4
l
+
k
+
1
) matrices in Z
q
n
×
m and a vector in Z
q
n; the size is about (
4
l
+
k
+
1
)
n
m
log
⁡
q
+
n
log
⁡
q.
(ii)
As for the size of the master secret keyMK, the scheme of [21] needs 2
l matrices in Z
p
q
m
×
m; the size is about 2
l
m
2
log
⁡
(
p
q
). Our scheme needs 2
l matrices in Z
q
m
×
m; the size is about 2
l
m
2
log
⁡
q.
(iii)
As for the size of the private key of identityID, the scheme of [21] needs l matrices in Z
p
q
2
m
×
2
m; the size is about 4
l
m
2
log
⁡
(
p
q
). Our scheme needs l matrices in Z
q
2
m
×
2
m; the size is about 4
l
m
2
log
⁡
q.
(iv)
As for the size of the signatureσ, the signature of the scheme of [21] is made of l vectors in Z
p
q
2
m; the size is about 2
l
m
log
⁡
(
p
q
). Our signature is made of l vectors in Z
q
3
m; the size is about 3
l
m
log
⁡
q.Secondly, we compare sign cost and verify cost of our scheme and the scheme of [21], which affects the computation cost.(i)
Sign cost: in the scheme of [21], the process of signing is made of n times of Shamir secret-sharing operations (SSS) and l times of preimage sampling algorithms (PS) with module p
q. In our scheme, the process of signing is made of n times of Shamir secret-sharing operations (SSS), l times of discrete Gaussian sampling algorithms (DGS) with module q, and l times of preimage sampling algorithms (PS) with module q.
(ii)
Verify cost: in the scheme of [21], the process of verifying is made of d times of matrix and vector products in Z
p
q (MVP) (where the matrix form is (
n
×
2
m
) and the vector form is 2
m-row), d times of scalar multiplications in Z
p
q
2
m (SMP). In our scheme, the process of verifying is made of d times of matrix and vector products in Z
q (MVP) (where the matrix form is (
n
×
3
m
) and the vector form is 3
m-row), d times of scalar multiplication in Z
q
3
m (SMP), and k times of matrix and matrix additions (MMA) in Z
q
n
×
m.Finally, we compare the security that these two schemes achieved. Improving the security of the scheme of [21] is our motivation of this paper. Specifically, our scheme can achieve strong unforgeability instead of existential unforgeability. Meanwhile, we prove the security proof in the standard model instead of in the random oracle model. Therefore, our scheme seems safer than the scheme of [21]. To the best of our knowledge, our scheme is the first FIBS scheme from lattices without random oracles and achieves strong unforgeability.


### 6.2. Simulations

The scheme of [21] and our scheme are implemented in Visual Studio 2008 in Windows 7 Service Pack1 64-bit operating system. We use a desktop which has a 4-core Intel(R) Core (TM) i7-860 processor running at 2.79 GHz and 8 GB of RAM.We carry out 6 simulations with different parameter settings that are given in Table2 (it is suggested from [26, 29]). As for other parameters, we set the length of identity string l
=
80, the error tolerance parameter d
=
40, and the length of message k
=
80. We use the same parameter settings and choose another module p in [21]. We let p
=
q in the simulation, but in fact, the module p is larger than q. The average sign time and verify time are listed in Table 3 and illustrated in Figure 3. The length of public parameters and master secret key is illustrated in Figure 1. The length of private key of identity and signature is illustrated in Figure 2.Table 2
Parameters settings.
Number
1
2
3
4
5
6
n
128
136
192
214
256
320
q
2053
2003
4093
16381
4093
4093
m
8448
8976
13824
17976
18432
23040Table 3
Average sign/verify time (s).
Number
1
2
3
4
5
6
[21]
Sign
705.408
734.72
1041.344
1411.392
1455.824
1992.768
Verify
51.26
59.37
129.168
186.2
232.872
362.96
Ours
Sign
703.6
732.448
1040.336
1401.728
1449.056
2000.448
Verify
34.41
39.21
85.104
125.04
150.256
240.44Length of public parameters/master secret key.
(a)
Length of public parameters
(b)
Length of master secret keyLength of private key of identity/signature.
(a)
Length of private key of identity
(b)
Length of signatureAverage sign/verify time.
(a)
Average sign time
(b)
Average verify timeRemark 14.
In fact, in the simulation of signing, we only count the time ofl times preimage sampling algorithms (PS) with module p
q in the scheme of [21], and we count the time of l times discrete Gaussian sampling algorithms (DGS) with module q and l times preimage sampling algorithms (PS) with module q in our scheme. The time of n times Shamir secret-sharing operations (SSS) is not included because it is the same in these two schemes.Remark 15.
In the simulation of verifying, we count the time of(
d
+
1
) times matrix and vector products in Z
p
q (MVP) (where the matrix form is (
n
×
2
m
) and the vector form is 2
m-row) in the scheme of [21]; the additional one time MVP in Z
p
q is derived from d times scalar multiplications (SMP) in Z
p
q
2
m. We count the time of (
d
+
1
) times matrix and vector products in Z
q (MVP) (where the matrix form is (
n
×
3
m
) and the vector form is 3
m-row); the additional one time MVP in Z
q is derived from d times scalar multiplications in Z
q (SMP) and k times matrix and matrix additions (MMA).From Figures1, 2, and 3, we may draw the following conclusions. (1) In the aspect of storage space, the length of our scheme’s public parameters is longer than the one of [21], while the length of the master secret key and the length of identity’s private key are shorter than the ones of [21]. So, the storage space of PKG and identities is broadly flat in these two schemes. (2) The sign time in these two schemes is approximately the same, while the verify time of our scheme is longer than the one of [21]. Therefore, the computation cost of our scheme is larger than the scheme of [21]. (3) The length of signature of our scheme is shorter than the one of [21], which leads to the result that the communication cost is smaller the scheme of [21]. In general, in the personal computer, the storage space is large and the computational ability is strong enough, while the bandwidth becomes a main factor of restricting the communication. The signature size of our scheme is shorter, which is good for communication.


## 6.1. Comparison with the Scheme of [21]

The efficiency and security of our scheme and the scheme of [21] are summarized in Table 1, where the efficiency includes the size of storage space, the communication cost, and computation cost.Table 1
Performance comparison with the scheme of [21].
Length of PP
Length of MK
Length of skID
Length ofσ
[21]
2
l
m
n
log
⁡
(
p
q
)
2
l
m
2
log
⁡
(
p
q
)
4
l
m
2
log
⁡
(
p
q
)
2
l
m
log
⁡
(
p
q
)
Ours
(
4
l
+
k
+
1
)
m
n
log
⁡
q
+
n
log
⁡
q
2
l
m
2
log
⁡
q
4
l
m
2
log
⁡
q
3
l
m
log
⁡
q
Sign cost
Verify cost
Unforgeability
Model
[21]
n
SSS
†
d
MVP
§(p
q)
EU
♭<
ROM
♮
+l
PS
‡
(
p
q
)
+d
SMP
¶ (p
q)
Ours
n SSS
d MVP (q)
+l
DGS
£ (q)
+d SMP (q)
SU
♯
SM
∥
+l PS (q)
+k
MMA
♠ (q)
Note.  The units of public parameters size, master secret key size, private key of identity size, and signature size are bits. The base of the logarithm function is 2;SSS
† denotes Shamir secret sharing operation; PS
‡ denotes preimage sampling algorithm; MVP
§ denotes matrix and vector product (where the matrix form is (
n
×
2
m
) and the vector form is 2
m-row); SMP
¶ denotes scalar multiplication; EU
♭ denotes existential unforgeability; ROM
♮ denotes random oracle model; DGS
£ DGS denotes discrete Gaussian sampling algorithm; MMA
♠ denotes matrix and matrix addition; SU
♯ denotes strong unforgeability; SM
∥ denotes the standard model. The (p
q) and (q)  denote modules that are used in the corresponding operations.Firstly, we consider the size of storage space and the communication cost. Specifically, we compare the length of public parametersPP, the master secret key MK, and the private key of identity ID, which affect the the size of storage space. We also compare the length of the signature, which affects the communication cost.(i)
As for the size of the public parametersPP, the scheme of [21] needs 2
l matrices in Z
p
q
n
×
m; the size is about 2
l
n
m
log
⁡
(
p
q
). Our scheme needs (
4
l
+
k
+
1
) matrices in Z
q
n
×
m and a vector in Z
q
n; the size is about (
4
l
+
k
+
1
)
n
m
log
⁡
q
+
n
log
⁡
q.
(ii)
As for the size of the master secret keyMK, the scheme of [21] needs 2
l matrices in Z
p
q
m
×
m; the size is about 2
l
m
2
log
⁡
(
p
q
). Our scheme needs 2
l matrices in Z
q
m
×
m; the size is about 2
l
m
2
log
⁡
q.
(iii)
As for the size of the private key of identityID, the scheme of [21] needs l matrices in Z
p
q
2
m
×
2
m; the size is about 4
l
m
2
log
⁡
(
p
q
). Our scheme needs l matrices in Z
q
2
m
×
2
m; the size is about 4
l
m
2
log
⁡
q.
(iv)
As for the size of the signatureσ, the signature of the scheme of [21] is made of l vectors in Z
p
q
2
m; the size is about 2
l
m
log
⁡
(
p
q
). Our signature is made of l vectors in Z
q
3
m; the size is about 3
l
m
log
⁡
q.Secondly, we compare sign cost and verify cost of our scheme and the scheme of [21], which affects the computation cost.(i)
Sign cost: in the scheme of [21], the process of signing is made of n times of Shamir secret-sharing operations (SSS) and l times of preimage sampling algorithms (PS) with module p
q. In our scheme, the process of signing is made of n times of Shamir secret-sharing operations (SSS), l times of discrete Gaussian sampling algorithms (DGS) with module q, and l times of preimage sampling algorithms (PS) with module q.
(ii)
Verify cost: in the scheme of [21], the process of verifying is made of d times of matrix and vector products in Z
p
q (MVP) (where the matrix form is (
n
×
2
m
) and the vector form is 2
m-row), d times of scalar multiplications in Z
p
q
2
m (SMP). In our scheme, the process of verifying is made of d times of matrix and vector products in Z
q (MVP) (where the matrix form is (
n
×
3
m
) and the vector form is 3
m-row), d times of scalar multiplication in Z
q
3
m (SMP), and k times of matrix and matrix additions (MMA) in Z
q
n
×
m.Finally, we compare the security that these two schemes achieved. Improving the security of the scheme of [21] is our motivation of this paper. Specifically, our scheme can achieve strong unforgeability instead of existential unforgeability. Meanwhile, we prove the security proof in the standard model instead of in the random oracle model. Therefore, our scheme seems safer than the scheme of [21]. To the best of our knowledge, our scheme is the first FIBS scheme from lattices without random oracles and achieves strong unforgeability.


## 6.2. Simulations

The scheme of [21] and our scheme are implemented in Visual Studio 2008 in Windows 7 Service Pack1 64-bit operating system. We use a desktop which has a 4-core Intel(R) Core (TM) i7-860 processor running at 2.79 GHz and 8 GB of RAM.We carry out 6 simulations with different parameter settings that are given in Table2 (it is suggested from [26, 29]). As for other parameters, we set the length of identity string l
=
80, the error tolerance parameter d
=
40, and the length of message k
=
80. We use the same parameter settings and choose another module p in [21]. We let p
=
q in the simulation, but in fact, the module p is larger than q. The average sign time and verify time are listed in Table 3 and illustrated in Figure 3. The length of public parameters and master secret key is illustrated in Figure 1. The length of private key of identity and signature is illustrated in Figure 2.Table 2
Parameters settings.
Number
1
2
3
4
5
6
n
128
136
192
214
256
320
q
2053
2003
4093
16381
4093
4093
m
8448
8976
13824
17976
18432
23040Table 3
Average sign/verify time (s).
Number
1
2
3
4
5
6
[21]
Sign
705.408
734.72
1041.344
1411.392
1455.824
1992.768
Verify
51.26
59.37
129.168
186.2
232.872
362.96
Ours
Sign
703.6
732.448
1040.336
1401.728
1449.056
2000.448
Verify
34.41
39.21
85.104
125.04
150.256
240.44Length of public parameters/master secret key.
(a)
Length of public parameters
(b)
Length of master secret keyLength of private key of identity/signature.
(a)
Length of private key of identity
(b)
Length of signatureAverage sign/verify time.
(a)
Average sign time
(b)
Average verify timeRemark 14.
In fact, in the simulation of signing, we only count the time ofl times preimage sampling algorithms (PS) with module p
q in the scheme of [21], and we count the time of l times discrete Gaussian sampling algorithms (DGS) with module q and l times preimage sampling algorithms (PS) with module q in our scheme. The time of n times Shamir secret-sharing operations (SSS) is not included because it is the same in these two schemes.Remark 15.
In the simulation of verifying, we count the time of(
d
+
1
) times matrix and vector products in Z
p
q (MVP) (where the matrix form is (
n
×
2
m
) and the vector form is 2
m-row) in the scheme of [21]; the additional one time MVP in Z
p
q is derived from d times scalar multiplications (SMP) in Z
p
q
2
m. We count the time of (
d
+
1
) times matrix and vector products in Z
q (MVP) (where the matrix form is (
n
×
3
m
) and the vector form is 3
m-row); the additional one time MVP in Z
q is derived from d times scalar multiplications in Z
q (SMP) and k times matrix and matrix additions (MMA).From Figures1, 2, and 3, we may draw the following conclusions. (1) In the aspect of storage space, the length of our scheme’s public parameters is longer than the one of [21], while the length of the master secret key and the length of identity’s private key are shorter than the ones of [21]. So, the storage space of PKG and identities is broadly flat in these two schemes. (2) The sign time in these two schemes is approximately the same, while the verify time of our scheme is longer than the one of [21]. Therefore, the computation cost of our scheme is larger than the scheme of [21]. (3) The length of signature of our scheme is shorter than the one of [21], which leads to the result that the communication cost is smaller the scheme of [21]. In general, in the personal computer, the storage space is large and the computational ability is strong enough, while the bandwidth becomes a main factor of restricting the communication. The signature size of our scheme is shorter, which is good for communication.


## 7. Conclusions and Open Problems

In this paper, we present an FIBS scheme from lattices and prove the strong unforgeability of our scheme under selective chosen-identity and adaptive chosen-message attacks (SU-sID-CMA) in the standard model. In addition, complexity analysis and simulations are given in the end of the paper.Attribute-based signature (ABS) scheme extends (fuzzy) identity-based signature in which a signer is defined by a set of attributes instead of a single string representing the signer’s identity. For further research, we aim for constructing a fuzzy attribute-based signature scheme from lattices. In addition, we can also use other secret sharing schemes [30] to construct FIBS scheme.



---

*Source: 391276-2014-08-14.xml*