Fuzzy identitybased cryptography introduces the threshold structure into identitybased cryptography, changes the receiver of a ciphertext from exact one to dynamic many, makes a cryptographic scheme more efficient and flexible. In this paper, we propose the first fuzzy identitybased signcryption scheme in latticebased cryptography. Firstly, we give a fuzzy identitybased signcryption scheme that is indistinguishable against chosen plaintext attack under selective identity model. Then we apply FujisakiOkamoto method to obtain a fuzzy identitybased signcryption scheme that is indistinguishable against adaptive chosen ciphertext attack under selective identity model. Thirdly, we prove our scheme is existentially unforgeable against chosen message attack under selective identity model. As far as we know, our scheme is the first fuzzy identitybased signcryption scheme that is secure even in the quantum environment.
1. Introduction
I
n public key cryptography, a user has a pair of public key and a private key, and this pair is bounded with the user by a trusted third party. For security consideration, the user and the matching public/private key should be updated frequently, and it is complicated to maintain public key infrastructure to support key authenticity. In order to solve this problem, Shamir introduced identitybased cryptography
[1]
. In identitybased cryptography, a user’s identity is viewed as his public key, and the associated private key is generated by a private key generator, and the relation between a user and his public/private key is natural. Identitybased cryptography doesn’t depend on the complex public key infrastructure, simplifies the user key management, and leads to more practical cryptosystems
[2
,
3]
.
However, one person must ascertain the receiver, in public key cryptography and identitybased cryptography, when he encrypts a message. The truth of the matter is that, the sender couldn’t ascertain the receiver in such situations as payTV systems and cloud storages, for the group of receivers is of a dynamic change. To adapt to this environment, we may introduce access control structure in encryption, and allow people, who are admitted by the access control structure, to decrypt the ciphertext. When the access control structure is specific to threshold structure, it is fuzzy identitybased cryptography. Fuzzy identitybased cryptography is an errortolerant identitybased cryptography. In other words, a ciphertext or signature obtained via an identity
id
can be decrypted or verified via an identity
id'
if and only if the difference between
id
and
id'
is within a certain range, and the range is the threshold value.
Fuzzy identitybased encryption(FIBE) was introduced by Sahai and Waters
[4]
. Sahai and Waters formalized the model of fuzzy identitybased encryption and provided two fuzzy identitybased encryption schemes which are secure against chosen plaintext attack under selective identity model. Subsequently, Baek et al. gave two more efficient fuzzy identitybased encryption schemes
[5]
using Pirretti et al.’s results
[6]
, and Li et al. proposed a fuzzy identitybased encryption scheme with dynamic threshold
[7]
.
When it comes to digital signature, Yang et al. firstly introduced the notion of fuzzy identitybased signature(FIBS)
[8]
and gave a specific construction based on Sahai and Waters’s fuzzy identitybased encryption schemes
[4]
. Afterward, Wang proposed a fuzzy identitybased signature scheme with shorter parameters and more efficient verification
[9]
, and Wu also proposed a fuzzy identitybased signature scheme with the generalized selective identity security
[10]
.
Aiming at further improvement in the practicability of cryptographic system, Zheng introduced the notion of signcryption to combine encryption and signature
[11]
. Signcryption is a cryptographic primitive that can perform the functions of public key encryption and digital signature in a logic step, so that it cuts down the cost of computation and communication without security compromise. To meet the needs of biometric identity, Zhang et al.
[12]
and Li et al.
[13]
introduced fuzziness property into signcryption respectively, and proposed fuzzy signcryption schemes.
So far, all the literatures mentioned above are based on the traditional numerical assumptions, and Shor’s groundbreaking results
[14]
show that these schemes are not secure in the quantum era. Thus, it is a rewarding work to build quantum secure cryptographic schemes. Latticebased cryptography is an outstanding representative of postquantum cryptography, and there exist many public key encryption schemes
[15
,
16
,
17]
and digital signature schemes
[18
,
19
,
20]
based on lattice theory. But as far as we know, there aren’t fuzzy identitybased signcryption schemes based on lattice assumptions.
In this paper, we give the first fuzzy identitybased signcryption scheme based on lattice assumptions. According to the technique in
[21]
, we take the signature associated with the message as an error vector, to disturb the lattice point associated with the message. As a result, we bind the encrypted message and the signature to realize confidentiality and authentication simultaneously. And we reduce the frequency of sampling errors compare with the generic signthenencrypt method. To accomplish ukeyExtract queries in the proof of existential unforgeability against chosen message attack under selective identity model, we introduce identity information to public key for encryption. In order to further decrease the length of the ciphertext, we make use of the technique of the lattice basis delegation in fixed dimension
[16]
. In addition, we apply the FujisakiOkamoto method
[22]
to increase our scheme’s security from indistinguishability against chosen plaintext attack under selective identity model(INDsIDCPA) to indistinguishability against adaptive chosen ciphertext attack under selective identity model(INDsIDCCA2).
The following is the roadmap of our paper. Section 2 includes preliminaries that are necessary in our construction, Section 3 gives the formal definition of a fuzzy identitybased signcryption scheme. Section 4 introduces the security definitions of a fuzzy identitybased signcryption scheme. Section 5 gives our new scheme and its consistency analysis. Section 6 gives the security analysis of our scheme. Section 7 provides its efficiency analysis and performance comparison with other related schemes. Finally, Section 8 is summary and conclusions.
2. Preliminaries
In this section, we give an overview of basic notions and results that are involved in our construction about latticebased cryptography. We refer readers to
[15
,
16
,
23]
for more details.
Definition 2.1
A lattice is a discrete addition subgroup in
R
^{m}
,
and if it is generated by n linearly independent vectors
a
_{1}
,⋯,
a_{n}
∈ R
^{m}
,
then matrix
A
= [
a
_{1}
⋯
a_{n}
]
is a basis of the lattice, and the lattice can be denoted by
∧(
A
).
Definition 2.2
Two integer lattices, as well as a lattice shift, are often used in latticebased cryptography, and we give their definitions as follows. For
,
Definition 2.3
For
∧ ⊆ Z
^{m}
,
c
∈ R
^{m}
,
σ
∈ R
^{+}
,
let
,
ρ_{σ,c}
(∧) = Σ
_{x∈∧}
ρ_{σ,c}
(x) ,
then
is a discrete Gaussian distribution over
∧,
whose center is c and parameter is σ
.
When c
= 0
or σ
= 1,
we can omit them
.
Lemma 2.4
With integer q
≥ 3.
m
≥
Cn
log
q
,
where C
> 1
is a fixed constant, algorithm TrapGen outputs
,
which satisfy the following properties
.
1. The statistical distance between the distribution of
A
and uniform distribution on
is negligible.
2.
AT
= 0(mod
q
).
3. ║
T
║ ≤
O
(
n
log
q
) and
.
Definition 2.5
Let
, D
_{mxm}
is the distribution
and if R
← D
_{mxm}
,
then R is Z_{q}  invertible
.
Lemma 2.6
For
with rank n
,
R
← D
_{mxm}
,
a short basis T_{A} of
,
and Gaussian parameter
,
algorithm BasisDel outputs a basis T_{B} of
.
Lemma 2.7
Algorithm SampleRwithBasis
(
A
)
is important in security proof. Its input is a matrix A
,
which comes from
uniformly and randomly. Its output are matrices R and T
,
where R follows the distribution
D
_{mxm}
,
T is a short basis of
.
Lemma 2.8
For
,
a short basis T_{B} of
,
and Gaussian parameter
,
algorithm SamplePre outputs some e
∈ Z
^{m}
such that
and Be
=
u
(mod
q
).
Definition 2.9
For a size parameter n
≥ 1,
a modulus q
≥ 2,
and an appropriate normal distribution
X
on Z_{q}
,
A
_{s,X}
is the distribution obtained by selecting a vector
uniformly, sampling x
: X ,
and outputting
.
An (Z
_{q}
,
n
,X)  LWE problem instance is composed of access to an unspecified challenge oracle O , which is, either, a pseudorandom sampler O
_{s}
associated with some random secret
, or, a random sampler O
_{u}
.
O
_{s}
: outputs such samples as
, where
a_{i}
follows uniform distribution on
,
x_{i}
follows distribution X .
O
_{u}
: outputs such samples as (
a_{i}
,
b_{i}
) which follows uniform distribution on
.
Given an (Z
_{q}
,
n
,X)  LWE problem instance, if there is an efficient algorithm to decide which oracle is accessed, then there is an efficient algorithm to approximate the SIVP and GapSVP problems in the worst case.
Definition 2.10
The
(
n
,
m
,
q
,
β
) 
small integer solution problem SIS_{n,m,q,β} is that for
,
and a real β
,
find a vector e
∈ Z
^{m}
such that Ae
= 0(mod
q
)
and
0 < ║e║
_{2}
≤
β
,
where
║‧║
_{2}
is the Euclidean norm
.
Given an
SIS_{n,m,q,β}
problem instance, if there is an efficient algorithm to find its small integer solution
e
, then there is an efficient algorithm to approximate the SIVP problem in the worst case.
3. Formal definition of a fuzzy identitybased signcryption
In this section, we give the formal definition of a fuzzy identitybased signcryption.
A fuzzy identitybased signcryption scheme has five PPT algorithms as follows.
• Setup (1
^{n}
,
d
,
d'
)  On input system security parameter 1
^{n}
, two thresholds
d
and
d'
, this algorithm outputs public parameter
PP
and master secret key
msk
.
• uKeyExtract (
msk
,
id
)  On input master secret key
msk
, an identity
id
, this algorithm outputs the unsigncryption key
uk_{id}
.
• sKeyExtract (
msk
,
id
)  On input master secret key
msk
, an identity
id
, this algorithm outputs the signature key
sk_{id}
.
• Signcrypt (
M
,
,
id_{e}
)  On input a message
M
, an identity
id_{e}
for encryption, an identity
id_{s}
as well as its signature key
, this algorithm outputs a ciphertext
C
.
• Unsigncrypt (
C
,
,
id_{v}
)  On input a ciphertext
C
, an identity
id_{v}
for verification, an identity
id_{u}
as well as its unsigncryption key
, if 
id_{u}
∩
id_{e}
 ≥
d
and 
id_{v}
∩
id_{s}
 ≥
d'
, this algorithm gets the message
M
, and verifies the validity of the message and its signature. If verification is successful, this algorithm returns the message
M
, otherwise returns ⊥.
These five algorithms must satisfy consistency property of a fuzzy identitybased signcryption, that is, if
C
=
Signcrypt
(
M
,
,
id_{e}
), and 
id_{u}
∩
id_{e}
 ≥
d
, 
id_{v}
∩
id_{s}
 ≥
d'
, then we should have
M
=
Unsigncrypt
(
C
,
,
id_{v}
).
4. Security notions
The security of a fuzzy identitybased signcryption scheme includes two factors: message confidentiality and ciphertext unforgeability, which are illuminated in detail as follows.
 4.1 Message confidentiality
With regard to the message confidentiality of a fuzzy identitybased signcryption scheme, we define two definitions of different security levels: indistinguishability against chosen plaintext attack under selective identity model(INDsIDCPA), and indistinguishability against adaptive chosen ciphertext attack under selective identity model(INDsIDCCA2).
The following game between a challenger C and an adversary A describes the indistinguishability against adaptive chosen ciphertext attack under selective identity model(INDsIDCCA2).
• Target – The adversary A decides an identity
id
^{*}
to be his attack target, and returns it to the challenger C.
• Setup – The challenger C inputs secure parameter 1
^{n}
, two thresholds
d
and
d'
, invokes Setup (1
^{n}
,
d
,
d'
) algorithm to get public parameter
PP
and master secret key
msk
. Public parameter
PP
is sent to the adversary A and master secret key
msk
is kept secret.
• Phase 1 – In this phase, the adversary A has the right to ask the following queries with a number of polynomial bounded, and the challenger C must return reasonable answers.
uKeyExtract (
id
) – The adversary A asks for the unsigncryption key for an identity
id
with 
id
∩
id
^{*}
 <
d
. The challenger C invokes algorithm uKeyExtract (
msk
,
id
) and returns its result to A .
sKeyExtract (
id
) – The adversary A asks for the signature key for an identity
id
. The challenger C invokes algorithm sKeyExtract (
msk
,
id
) and returns its result to A .
Unsigncrypt (
C
,
id_{u}
,
id_{v}
)  The adversary A provides a ciphertext
C
, an identity
id_{u}
for unsigncryption, and an identity
id_{v}
for verification. The challenger C computes
= uKeyExtract(
id_{u}
), then invokes algorithm Unsigncrypt(
C
,
,
id_{v}
) and returns its result to A .
• Challenge – When Phase 1 ends, the adversary A selects two messages
M
_{0}
,
M
_{1}
with same length, and an identity
id
^{*}
_{s}
for signature, sends all of them to the challenger C for challenge ciphertext. C selects a bit
b
randomly, computes the signature key
sk_{id*s}
= sKeyExtract (
id
^{*}
_{s}
) and returns
C
^{*}
= Signcrypt(
M_{b}
,
sk_{id*s}
,
id
^{*}
) to A .
• Phase 2 – The adversary A repeats what he did in Phase 1, with the exception that he couldn’t execute Unsigncrypt query on (
C
^{*}
,
id_{u}
,
id_{v}
) with 
id_{u}
∩
id
^{*}
 ≥
d
and 
id_{v}
∩
id
^{*}
_{s}
 ≥
d'
.
• Guess – The adversary A gives his guess
b'
for
b
which the challenger C used in Challenge phase. If
b'
=
b
, we say the adversary A wins the game.
The advantage of adversary A in this game is denoted as
.
Definition 4.1
If all polynomially bounded adversaries have negligible advantages in the above game, then a fuzzy identitybased signcryption scheme is indistinguishable against adaptive chosen ciphertext attack under selective identity model. In other words, a fuzzy identitybased signcryption scheme is INDsIDCCA2 secure
.
If the Unsigncrypt query is forbidden in the above game, then the game and the associated definition 4.1 describe the indistinguishability against chosen plaintext attack under selective identity model(INDsIDCPA).
 4.2 Ciphertext unforgeability
With regard to the ciphertext unforgeability of a fuzzy identitybased signcryption scheme, we define the following game between a challenger C and an adversary A to describe the existential unforgeability against chosen message attack under selective identity model(EUFsIDCMA).
• Target – The adversary A decides an identity
id
^{*}
to be his attack target, and returns it to the challenger C.
• Setup – The challenger C inputs secure parameter 1
^{n}
, two thresholds
d
and
d'
, invokes Setup(1
^{n}
,
d
,
d'
) algorithm to get public parameter
PP
and master secret key
msk
. Public parameter
PP
is sent to the adversary A and master secret key
msk
is kept secret.
• Query – In this phase, the adversary A has the right to ask the following queries with a number of polynomial bounded, and the challenger C must return reasonable answers.
uKeyExtract (
id
) – The adversary A asks for the unsigncryption key for an identity
id
. The challenger C invokes algorithm uKeyExtract (
msk
,
id
) and returns its result to A .
sKeyExtract (
id
) – The adversary A asks for the signature key for an identity
id
, which satisfy 
id
∩
id
^{*}
 <
d'
. The challenger C invokes algorithm sKeyExtract (
msk
,
id
) and returns its result to A .
Signcrypt(
M
,
id_{s}
,
id_{e}
)  The adversary A provides a message
M
, an identity
id_{s}
for signature, an identity
id_{e}
for encryption. The challenger C computes
= sKeyExtract(
id_{s}
), then invokes algorithm Signcrypt(
M
,
,
id_{e}
) and returns its result to A .
• Forge – The adversary A replies to C with a ciphertext
C
^{*}
as well as an encryption identity
id^{*}_{e}
. If adversary A ’s reply is valid, that is to say, there exist
id_{u}
and
id_{v}
which satisfy 
id_{u}
∩
id^{*}_{e}
 ≥
d
and 
id_{v}
∩
id
^{*}
 ≥
d'
, Unsigncrypt(
C
^{*}
,
,
id_{v}
) =
M
≠ ⊥ for
= uKeyExtract(
id_{u}
) and A didn’t make Signcrypt(
M
,
id
^{*}
,
id^{*}_{e}
) query, then we say the adversary A wins the game.
The advantage of adversary A in this game is denoted by
Adv
(A) =
Pr
[A
wins
] .
Definition 4.2
If all polynomially bounded adversaries have negligible advantages in the above game, then a fuzzy identitybased signcryption scheme is existentially unforgeable against chosen message attack under selective identity model. In other words, a fuzzy identitybased signcryption scheme is EUFsIDCMA secure
.
5. Our fuzzy identitybased signcryption scheme
At first, we give an INDsIDCPA secure fuzzy identitybased signcryption scheme – Construction 1, then we apply FujisakiOkamoto method to Construction 1 to obtain an INDsIDCCA2 secure fuzzy identitybased signcryption scheme – Construction 2.
 5.1 Construction 1
•
Setup
(
n
,
d
,
d'
) On input security parameter
, where
l
is the length of an identity,
ε
∈ (0,1) is a constant, and two thresholds
d
and
d'
,
1. For
q
=
poly
(
n
) and
pq
∈ [
n
^{6}
‧ 2
^{5}
^{l}
, 2
n
^{6}
‧ 2
^{5}
^{l}
], let
m
=
n
^{1.5}
,
2. For
i
∈ [
l
],
b
∈ {0,1}, invoke algorithm
TrapGen
(
n
) to obtain (
A_{i,b}
,
T_{i,b}
), with the condition that
(a)
follows uniform distribution with overwhelming probability.
(b)
T_{i,b}
is a short basis of
.
3. For message space M = {0,1}
^{k}
, let
t
∈ [
k
], select
uniformly and randomly.
4. Let D
_{mxm}
be the Gaussian distribution
,
H
_{1}
,
H
_{2}
: {0,1}
^{*}
→ D
_{mxm}
, and
H
_{3}
: {0,1}
^{*}
→
are three different hash functions.
5. Output
PP
= ({
A_{i,b}
}
_{i∈[l],b∈{0,1}}
, {
u_{t}
}
_{t∈[k]}
,
H
_{1}
,
H
_{2}
,
H
_{3}
) and
msk
= ({
T_{i,b}
}
_{i∈[l],b∈{0,1}}
).
•
uKeyExtract
(
msk
,
id
) On input
msk
= ({
T_{i,b}
}
_{i∈[l],b∈{0,1}}
) and an identity
id
= (
id
_{1}
, ⋯,
id_{l}
), the unsigncryption key
uk_{id}
is obtained as follows.
1. For
t
∈ [
k
], select a random polynomial vector
f_{t}
∈ R
^{n}
of degree
d
 1 such that R = Z
_{pq}
[
x
] and
f_{t}
(0) =
u_{t}
. Let
for
i
∈ [
l
]. By Shamir’s (
d
,
l
) threshold scheme, for
I
⊆ [
l
] such that 
I
 ≥
d
,
u_{t}
= Σ
_{i∈I}
L_{i}
‧
u_{ti}
(mod
pq
), where
L_{i}
is the associated Lagrangian coefficient.
2. For
i
∈ [
l
], let
=
H
_{1}
(
id_{i}
P
i
), invoke algorithm
BasisDel
(
,
,
,
σ
) to get a short basis
for lattice
.
3. For
t
∈ [
k
],
i
∈ [
l
] , run
SamplePre
(
,
,
u_{ti}
,
σ'
) to get
e_{ti}
∈ Z
^{m}
satisfying
‧
e_{ti}
=
u_{ti}
.
4. Output the unsigncryption key for the identity
id
as {
e_{ti}
}
_{t∈[k],i∈[l]}
.
•
sKeyExtract
(
msk
,
id
) On input
msk
= ({
T_{i,b}
}
_{i∈[l],b∈{0,1}}
) and an identity
id
= (
id
_{1}
, ⋯,
id_{l}
), the signature key
sk_{id}
is obtained as follows.
1. For
i
∈ [
l
] , let
=
H
_{2}
(
id
□
id_{i}
□
i
) , invoke algorithm
BasisDel
(
,
,
,
σ
) to get a short basis
for lattice
.
2. Output the signature key for the identity
id
as
•
Signcrypt
(
M
,
,
id_{e}
) On input the message
M
∈ {0,1}
^{k}
, the signature key
=
for
id_{s}
, and
id_{e}
= (
id
_{e1}
, ⋯,
id_{el}
) used for encryption,
1. Let
D
= (
l
!)
^{2}
,
u
=
H
_{3}
(
M
)
2. Select a random polynomial vector
f
∈ A
^{n}
of degree
d'
 1 such that A = Z
_{p}
[
x
] and
f
(0) =
u
. Let
u_{j}
=
f
(
j
) ∈
for
j
∈ [
l
]. By Shamir’s (
d'
,
l
) threshold scheme, for
J
⊆ [
l
] such that 
J
 ≥
d'
,
u
= Σ
_{j}
_{∈}
_{J}
L_{j}
‧
u_{j}
(mod
p
), where
L_{j}
is the associated Lagrangian coefficient.
3. For
i
∈ [
l
], compute
=
H
_{2}
(
id_{s}
□
id_{si}
□
i
),
.
4. For
i
∈ [
l
], sample
e_{i}
=
SamplePre
(
,
,
qu_{i}
,
σ'
) ∈ Z
^{m}
.
5. Select
randomly, compute
c
=
s
+
qu
.
6. For
t
∈ [
k
], let
.
7. For
i
∈ [
l
], let
.
8. For
i
∈ [
l
], let
.
9. Output the ciphertext
C
= (
id_{e}
,
id_{s}
,
c
,{
c
_{t}
_{0}
}
_{t∈[k]}
,{
c_{i}
}
_{i}
_{∈[}
_{l}
_{]}
).
•
Unsigncrypt
(
C
,
,
id_{v}
) On input the ciphertext
C
= (
id_{e}
,
id_{s}
,
c
,{
c
_{t}
_{0}
}
_{t∈[k]}
,{
c_{i}
}
_{i}
_{∈[}
_{l}
_{]}
, the unsigncryption key
= {
e_{ti}
}
_{t∈[k],i∈[l]}
for
id_{u}
, and
id_{v}
= (
id
_{v1}
, ⋯,
id_{vl}
) used for verification,
1. Let
I
=
id_{u}
∩
id_{e}
denote the set of matching bits in
id_{u}
and
id_{e}
, and
J
=
id_{v}
∩
id_{s}
denote the set of matching bits in
id_{v}
and
id_{s}
. If 
I
 <
d
or 
J
 <
d'
, output ⊥ and reject. Otherwise, continue.
2. For
i
∈ [
l
], let
=
H
_{1}
(
id_{ui}
P
i
),
. By Shamir’s (
d
,
l
) threshold scheme, we have Σ
_{i}
_{∈}
_{I}
L_{i}B_{i,idui} e_{ti}
=
u_{t}
(mod
pq
) for
t
∈ [
k
].
3. For
t
∈ [
k
], compute
, output
M_{t}
= 0, otherwise output
M_{t}
= 1. In this step, we retrieve the message
M
.
4. Compute
s
=
c

qH
_{3}
(
M
).
5. For
i
∈ [
l
], compute
=
H
_{1}
(
id_{ei}
P
i
),
.
6. For
i
∈ [
l
], compute
=
H
_{2}
(
id_{s}
P
id_{si}
P
i
),
.
7. Verify whether
and
e_{j}
∈ D
_{n}
for
j
∈ [
l
]. If all conditions hold, accept
M
as a valid message. Otherwise, output ⊥ and reject.
 5.2 Consistency of Construction 1
Let
I
=
id_{u}
∩
id_{e}
denote the set of matching bits in
id_{u}
and
id_{e}
,
J
=
id_{v}
∩
id_{s}
denote the set of matching bits in
id_{v}
and
id_{s}
, and 
I
 ≥
d
, 
J
 ≥
d'
. Then for
t
= 1,⋯,
k
,
According to parameters setting in
Setup
of our scheme,
with overwhelming probability, then
, then
M_{t}
= 0 ; otherwise
M_{t}
= 1. And
M
= (
M
_{1}
, ⋯,
M_{k}
).
Then
s
=
c

qH
_{3}
(
M
) and
for
i
∈ [
l
] . Because of
e_{i}
=
SamplePre
(
,
,
qu_{i}
,
σ'
) and
u
=
H
_{3}
(
M
) = Σ
_{j}
_{∈}
_{J}
L_{j}
‧
u_{j}
(mod
p
), we have
and
e_{j}
∈ D
_{n}
for
j
∈ [
l
].
As a result, as long as the ciphertext is got following our scheme religiously, a valid unsigncrypter can obtain the original message with overwhelming probability.
 5.3 INDsIDCPA security of Construction 1
Theorem 5.1
Assuming that the LWE problem is hard, Construction 1 is indistinguishable against chosen plaintext attack under selective identity model (INDsIDCPA)
.
Proof
. We prove Theorem 5.1 by contradiction. Suppose that there exists a PPT adversary A who can attack the INDsIDCPA security of Construction 1, we can construct a challenger C to solve an LWE problem instance, which is a contradiction with the hardness of the LWE problem. In other words, Construction 1 is INDsIDCPA secure under the hardness of the LWE problem.
To end this aim, the adversary A and the challenger C behave as follows.
• Target – The adversary A decides an encryption identity
id
^{*}
to be his attack target, and returns
id
^{*}
to the challenger C.
• Instance – The challenger C requests samples from the oracle O to get
for
t
= 1,⋯,
k
, and
for
i
∈ [
l
]. These samples follow LWE oracle O
_{s}
or uniform distribution oracle O
_{u}
, which will be decided by challenger C with the aid of A ’ attack ability to Construction 1.
• Setup – The public parameter
PP
is given by challenger C in the following manner.
1. Matrices
for
i
∈ [
l
].
2. Sample
l
random matrices
R
_{1}
^{*}
,⋯,
R_{l}
^{*}
← D
_{mxm}
, and let
for
i
∈ [
l
].
3. For
i
∈ [
l
],
is obtained by algorithm
TrapGen
, together with a short basis
.
4. Vectors
u_{t}
=
w_{t}
for
t
∈ [
k
].
Then
PP
= ({
A_{i,b}
}
_{i∈[l],b∈{0,1}}
, {
u_{t}
}
_{t∈[k]}
) is returned to the adversary A .
• Phase 1 – In this phase, the adversary A has the right to ask the following queries with a number of polynomial bounded, and the challenger C must return reasonable answers.
◊
H
_{1}
queries
– The adversary A asks for
H
_{1}
(
id
) for an identity
id
= (
id
_{1}
, ⋯,
id_{l}
), and the challenger C answers as follows.
For (
id_{i}
P
i
),
i
∈ [
l
],
1. If
id_{i}
=
id^{*}_{i}
, let
H
_{1}
(
id_{i}
P
i
) =
R_{i}
^{*}
.
2. If
id_{i}
≠
id^{*}_{i}
, sample
← D
_{mxm}
randomly, let
H
_{1}
(
id_{i}
P
i
) =
.
Then save(
id
,((
id_{i}
P
i
),
H
_{1}
(
id_{i}
P
i
))
_{i}
_{∈[}
_{l}
_{]}
) in list H
_{1}
and return ((
id_{i}
P
i
),
H
_{1}
(
id_{i}
P
i
))
_{i}
_{∈[}
_{l}
_{]}
.
◊
H
_{2}
queries
– The adversary A asks for
H
_{2}
(
id
) for an identity
id
= (
id
_{1}
, ⋯,
id_{l}
), and the challenger C answers as follows.
For (
id
P
id_{i}
P
i
),
i
∈ [
l
],
1. If
id_{i}
=
id^{*}_{i}
, run algorithm
SampleRwithBasis
to obtain a random
← D
_{mxm}
and a short basis
for lattice
.
Let
H
_{2}
(
id
P
id_{i}
P
i
) =
.
2. If
id_{i}
≠
id^{*}_{i}
, sample
← D
_{mxm}
randomly, let
H
_{2}
(
id
P
id_{i}
P
i
) =
, invoke algorithm
BasisDel
(
,
,
,
σ
) to get a short basis
for lattice
.
Then save
in list H
_{2}
and return
◊
uKeyExtract queries
– The adversary A asks for the unsigncryption key for an identity
id
with 
id
∩
id
^{*}
 = 
I
 =
d
_{0}
<
d
. The challenger C does the following steps to reply.
1. For simplicity, we assume that the first
d
_{0}
bits of
id
and
id
^{*}
are equal, then the challenger C has trapdoors for the matrices associated with the set
.
2. For
t
∈ [
k
] , let the shares of
u_{t}
be
u_{ti}
=
u_{t}
+
a
_{t}
_{1}
i
+
a
_{t}
_{2}
i
^{2}
+⋯+
a
_{td}
_{1}
i
^{d1}
, where
a
_{t}
_{1}
,⋯,
a
_{td}
_{1}
are vector variables with length
n
.
3. For
i
∈ [
l
], execute
H
_{1}
(
id
) query to obtain
=
H
_{1}
(
id_{i}
P
i
), and let
.
4. For
t
∈ [
k
],
i
∈ [
d
_{0}
], select
e_{ti}
←
, and let
u_{ti}
=
‧
e_{ti}
.
5. For
t
∈ [
k
],
i
∈ {
d
_{0}
+ 1,⋯,
d
1}, choose
d
 1 
d
_{0}
shares
,⋯,
u
_{td}
_{1}
randomly, then the values for
a
_{t}
_{1}
,⋯,
a
_{td}
_{1}
are fixed and all
l
shares
u
_{t}
_{1}
, ⋯,
u_{tl}
are known.
6. For
t
∈ [
k
],
i
∈ {
d
_{0}
+1,⋯,
l
}, since
is known, invoke algorithm
BasisDel
(
,
,
,
σ
) to get a short basis
for lattice
, then invoke algorithm
SamplePre
(
,
,
u_{ti}
,
σ'
) to get
e_{ti}
∈ Z
^{m}
satisfying
‧
e_{ti}
=
u_{ti}
.
7. Return the unsigncryption key for the identity
id
as {
e_{ti}
}
_{t∈[k],i∈[l]}
.
◊
sKeyExtract queries
– The adversary A asks for the signature key for an identity
id
. The challenger C executes
H
_{2}
(
id
) query to obtain
then returns
• Challenge – When Phase 1 ends, the adversary A selects two messages
M
^{(0)}
and
M
^{(1)}
with same length, and a signature identity
id
^{*}
_{s}
, sends all of them to the challenger C for challenge ciphertext. C selects
b
∈{0,1} randomly, does the following steps.
1. Let
for
t
∈ [
k
].
2. Let
for
i
∈ [
l
].
3. Select
randomly.
Then (
id
^{*}
,
id
^{*}
_{s}
,
c
,{
c
_{t}
_{0}
}
_{t∈[k]}
,{
c_{i}
}
_{i}
_{∈[}
_{l}
_{]}
) is returned.
• Phase 2 – The adversary A repeats what he did in Phase 1.
• Guess – The adversary A gives his guess
b'
for
b
which the challenger C used in Challenge phase. If
b'
=
b
, C decides the samples follow LWE oracle O
_{s}
; otherwise, C decides the samples follow uniform distribution oracle O
_{u}
.
 5.4 Construction 2
We apply FujisakiOkamoto method to Construction 1 to obtain an INDsIDCCA2 secure fuzzy identitybased signcryption scheme – Construction 2, which is illustrated as follows.
•
Setup
(
n
,
d
,
d'
) On input security parameter
, where
l
is the length of an identity,
ε
∈ (0,1) is a constant, and two thresholds
d
and
d'
,
1. For
q
=
poly
(
n
) and
pq
∈ [
n
^{6}
‧ 2
^{5}
^{l}
, 2
n
^{6}
‧ 2
^{5}
^{l}
], let
m
=
n
^{1.5}
,
2. For
i
∈ [
l
],
b
∈ {0,1}, invoke algorithm
TrapGen
(
n
) to obtain (
A_{i,b}
,
T_{i,b}
), with the condition that
(a)
follows uniform distribution with overwhelming probability.
(b)
T_{i,b}
is a short basis of