Advanced
A Fuzzy Identity-Based Signcryption Scheme from Lattices
A Fuzzy Identity-Based Signcryption Scheme from Lattices
KSII Transactions on Internet and Information Systems (TIIS). 2014. Nov, 8(11): 4203-4225
Copyright © 2014, Korean Society For Internet Information
  • Received : July 18, 2014
  • Accepted : October 01, 2014
  • Published : November 30, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Xiuhua Lu
Faculty of Mathematics and Information Science, Langfang Teachers University Langfang, 065000 - China
Qiaoyan Wen
State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications Beijing, 100876 - China
Wenmin Li
State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications Beijing, 100876 - China
Licheng Wang
Information Security Center, Beijing University of Posts and Telecommunications Beijing, 100876 - China
Hua Zhang
State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications Beijing, 100876 - China

Abstract
Fuzzy identity-based cryptography introduces the threshold structure into identity-based 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 identity-based signcryption scheme in lattice-based cryptography. Firstly, we give a fuzzy identity-based signcryption scheme that is indistinguishable against chosen plaintext attack under selective identity model. Then we apply Fujisaki-Okamoto method to obtain a fuzzy identity-based 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 identity-based signcryption scheme that is secure even in the quantum environment.
Keywords
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 identity-based cryptography [1] . In identity-based 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. Identity-based 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 identity-based cryptography, when he encrypts a message. The truth of the matter is that, the sender couldn’t ascertain the receiver in such situations as pay-TV 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 identity-based cryptography. Fuzzy identity-based cryptography is an error-tolerant identity-based 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 identity-based encryption(FIBE) was introduced by Sahai and Waters [4] . Sahai and Waters formalized the model of fuzzy identity-based encryption and provided two fuzzy identity-based encryption schemes which are secure against chosen plaintext attack under selective identity model. Subsequently, Baek et al. gave two more efficient fuzzy identity-based encryption schemes [5] using Pirretti et al.’s results [6] , and Li et al. proposed a fuzzy identity-based encryption scheme with dynamic threshold [7] .
When it comes to digital signature, Yang et al. firstly introduced the notion of fuzzy identity-based signature(FIBS) [8] and gave a specific construction based on Sahai and Waters’s fuzzy identity-based encryption schemes [4] . Afterward, Wang proposed a fuzzy identity-based signature scheme with shorter parameters and more efficient verification [9] , and Wu also proposed a fuzzy identity-based 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. Lattice-based cryptography is an outstanding representative of post-quantum 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 identity-based signcryption schemes based on lattice assumptions.
In this paper, we give the first fuzzy identity-based 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 sign-then-encrypt 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 Fujisaki-Okamoto method [22] to increase our scheme’s security from indistinguishability against chosen plaintext attack under selective identity model(IND-sID-CPA) to indistinguishability against adaptive chosen ciphertext attack under selective identity model(IND-sID-CCA2).
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 identity-based signcryption scheme. Section 4 introduces the security definitions of a fuzzy identity-based 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 lattice-based 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 ,⋯, an ∈ R m , then matrix   A = [ a 1 |⋯| an ] 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 lattice-based cryptography, and we give their definitions as follows. For  
PPT Slide
Lager Image
,
PPT Slide
Lager Image
Definition 2.3   For ∧ ⊆ Z m , c ∈ R m , σ ∈ R + , let  
PPT Slide
Lager Image
, ρσ,c (∧) = Σ x∈∧ ρσ,c (x) , then  
PPT Slide
Lager Image
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  
PPT Slide
Lager Image
, which satisfy the following properties .
1. The statistical distance between the distribution of A and uniform distribution on
PPT Slide
Lager Image
is negligible.
2. AT = 0(mod q ).
3. ║ T ║ ≤ O ( n log q ) and
PPT Slide
Lager Image
.
Definition 2.5   Let  
PPT Slide
Lager Image
, D mxm   is the distribution  
PPT Slide
Lager Image
and if R ← D mxm , then R is Zq - invertible .
Lemma 2.6   For  
PPT Slide
Lager Image
with rank n , R ← D mxm , a short basis TA of  
PPT Slide
Lager Image
, and Gaussian parameter  
PPT Slide
Lager Image
, algorithm BasisDel outputs a basis TB of  
PPT Slide
Lager Image
.
Lemma 2.7   Algorithm SampleRwithBasis ( A ) is important in security proof. Its input is a matrix A , which comes from  
PPT Slide
Lager Image
uniformly and randomly. Its output are matrices R and T , where R follows the distribution D mxm , T is a short basis of  
PPT Slide
Lager Image
.
Lemma 2.8   For  
PPT Slide
Lager Image
, a short basis TB of  
PPT Slide
Lager Image
, and Gaussian parameter  
PPT Slide
Lager Image
, algorithm SamplePre outputs some e ∈ Z m such that  
PPT Slide
Lager Image
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 Zq , A s,X   is the distribution obtained by selecting a vector  
PPT Slide
Lager Image
uniformly, sampling x : X , and outputting  
PPT Slide
Lager Image
.
An (Z q , n ,X) - LWE problem instance is composed of access to an unspecified challenge oracle O , which is, either, a pseudo-random sampler O s associated with some random secret
PPT Slide
Lager Image
, or, a random sampler O u .
O s : outputs such samples as
PPT Slide
Lager Image
, where ai follows uniform distribution on
PPT Slide
Lager Image
, xi follows distribution X .
O u : outputs such samples as ( ai , bi ) which follows uniform distribution on
PPT Slide
Lager Image
.
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 SISn,m,q,β is that for  
PPT Slide
Lager Image
, 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 SISn,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 identity-based signcryption
In this section, we give the formal definition of a fuzzy identity-based signcryption.
A fuzzy identity-based 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 ukid .
• sKeyExtract ( msk , id ) - On input master secret key msk , an identity id , this algorithm outputs the signature key skid .
• Signcrypt ( M ,
PPT Slide
Lager Image
, ide ) - On input a message M , an identity ide for encryption, an identity ids as well as its signature key
PPT Slide
Lager Image
, this algorithm outputs a ciphertext C .
• Unsigncrypt ( C ,
PPT Slide
Lager Image
, idv ) - On input a ciphertext C , an identity idv for verification, an identity idu as well as its unsigncryption key
PPT Slide
Lager Image
, if | idu ide | ≥ d and | idv ids | ≥ 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 identity-based signcryption, that is, if C = Signcrypt ( M ,
PPT Slide
Lager Image
, ide ), and | idu ide | ≥ d , | idv ids | ≥ d' , then we should have M = Unsigncrypt ( C ,
PPT Slide
Lager Image
, idv ).
4. Security notions
The security of a fuzzy identity-based 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 identity-based signcryption scheme, we define two definitions of different security levels: indistinguishability against chosen plaintext attack under selective identity model(IND-sID-CPA), and indistinguishability against adaptive chosen ciphertext attack under selective identity model(IND-sID-CCA2).
The following game between a challenger C and an adversary A describes the indistinguishability against adaptive chosen ciphertext attack under selective identity model(IND-sID-CCA2).
• 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 , idu , idv ) - The adversary A provides a ciphertext C , an identity idu for unsigncryption, and an identity idv for verification. The challenger C computes
PPT Slide
Lager Image
= uKeyExtract( idu ), then invokes algorithm Unsigncrypt( C ,
PPT Slide
Lager Image
, idv ) 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 skid*s = sKeyExtract ( id * s ) and returns C * = Signcrypt( Mb , skid*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 * , idu , idv ) with | idu id * | ≥ d and | idv 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
PPT Slide
Lager Image
.
Definition 4.1   If all polynomially bounded adversaries have negligible advantages in the above game, then a fuzzy identity-based signcryption scheme is indistinguishable against adaptive chosen ciphertext attack under selective identity model. In other words, a fuzzy identity-based signcryption scheme is IND-sID-CCA2 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(IND-sID-CPA).
- 4.2 Ciphertext unforgeability
With regard to the ciphertext unforgeability of a fuzzy identity-based 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(EUF-sID-CMA).
• 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 , ids , ide ) - The adversary A provides a message M , an identity ids for signature, an identity ide for encryption. The challenger C computes
PPT Slide
Lager Image
= sKeyExtract( ids ), then invokes algorithm Signcrypt( M ,
PPT Slide
Lager Image
, ide ) 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 idu and idv which satisfy | idu id*e | ≥ d and | idv id * | ≥ d' , Unsigncrypt( C * ,
PPT Slide
Lager Image
, idv ) = M ≠ ⊥ for
PPT Slide
Lager Image
= uKeyExtract( idu ) 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 identity-based signcryption scheme is existentially unforgeable against chosen message attack under selective identity model. In other words, a fuzzy identity-based signcryption scheme is EUF-sID-CMA secure .
5. Our fuzzy identity-based signcryption scheme
At first, we give an IND-sID-CPA secure fuzzy identity-based signcryption scheme – Construction 1, then we apply Fujisaki-Okamoto method to Construction 1 to obtain an IND-sID-CCA2 secure fuzzy identity-based signcryption scheme – Construction 2.
- 5.1 Construction 1
Setup ( n , d , d' ) On input security parameter
PPT Slide
Lager Image
, 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 ,
PPT Slide
Lager Image
2. For i ∈ [ l ], b ∈ {0,1}, invoke algorithm TrapGen ( n ) to obtain ( Ai,b , Ti,b ), with the condition that
(a)
PPT Slide
Lager Image
follows uniform distribution with overwhelming probability.
(b) Ti,b is a short basis of
PPT Slide
Lager Image
.
3. For message space M = {0,1} k , let t ∈ [ k ], select
PPT Slide
Lager Image
uniformly and randomly.
4. Let D mxm be the Gaussian distribution
PPT Slide
Lager Image
, H 1 , H 2 : {0,1} * → D mxm , and H 3 : {0,1} *
PPT Slide
Lager Image
are three different hash functions.
5. Output PP = ({ Ai,b } i∈[l],b∈{0,1} , { ut } t∈[k] , H 1 , H 2 , H 3 ) and msk = ({ Ti,b } i∈[l],b∈{0,1} ).
uKeyExtract ( msk , id ) On input msk = ({ Ti,b } i∈[l],b∈{0,1} ) and an identity id = ( id 1 , ⋯, idl ), the unsigncryption key ukid is obtained as follows.
1. For t ∈ [ k ], select a random polynomial vector ft ∈ R n of degree d - 1 such that R = Z pq [ x ] and ft (0) = ut . Let
PPT Slide
Lager Image
for i ∈ [ l ]. By Shamir’s ( d , l ) threshold scheme, for I ⊆ [ l ] such that | I | ≥ d , ut = Σ iI Li uti (mod pq ), where Li is the associated Lagrangian coefficient.
2. For i ∈ [ l ], let
PPT Slide
Lager Image
= H 1 ( idi P i ), invoke algorithm BasisDel (
PPT Slide
Lager Image
,
PPT Slide
Lager Image
,
PPT Slide
Lager Image
, σ ) to get a short basis
PPT Slide
Lager Image
for lattice
PPT Slide
Lager Image
.
3. For t ∈ [ k ], i ∈ [ l ] , run SamplePre (
PPT Slide
Lager Image
,
PPT Slide
Lager Image
, uti , σ' ) to get eti ∈ Z m satisfying
PPT Slide
Lager Image
eti = uti .
4. Output the unsigncryption key for the identity id as { eti } t∈[k],i∈[l] .
sKeyExtract ( msk , id ) On input msk = ({ Ti,b } i∈[l],b∈{0,1} ) and an identity id = ( id 1 , ⋯, idl ), the signature key skid is obtained as follows.
1. For i ∈ [ l ] , let
PPT Slide
Lager Image
= H 2 ( id idi i ) , invoke algorithm BasisDel (
PPT Slide
Lager Image
,
PPT Slide
Lager Image
,
PPT Slide
Lager Image
, σ ) to get a short basis
PPT Slide
Lager Image
for lattice
PPT Slide
Lager Image
.
2. Output the signature key for the identity id as
PPT Slide
Lager Image
Signcrypt ( M ,
PPT Slide
Lager Image
, ide ) On input the message M ∈ {0,1} k , the signature key
PPT Slide
Lager Image
=
PPT Slide
Lager Image
for ids , and ide = ( id e1 , ⋯, idel ) 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 uj = f ( j ) ∈
PPT Slide
Lager Image
for j ∈ [ l ]. By Shamir’s ( d' , l ) threshold scheme, for J ⊆ [ l ] such that | J | ≥ d' , u = Σ j J Lj uj (mod p ), where Lj is the associated Lagrangian coefficient.
3. For i ∈ [ l ], compute
PPT Slide
Lager Image
= H 2 ( ids idsi i ),
PPT Slide
Lager Image
.
4. For i ∈ [ l ], sample ei = SamplePre (
PPT Slide
Lager Image
,
PPT Slide
Lager Image
, qui , σ' ) ∈ Z m .
5. Select
PPT Slide
Lager Image
randomly, compute c = s + qu .
6. For t ∈ [ k ], let
PPT Slide
Lager Image
.
7. For i ∈ [ l ], let
PPT Slide
Lager Image
.
8. For i ∈ [ l ], let
PPT Slide
Lager Image
.
9. Output the ciphertext C = ( ide , ids , c ,{ c t 0 } t∈[k] ,{ ci } i ∈[ l ] ).
Unsigncrypt ( C ,
PPT Slide
Lager Image
, idv ) On input the ciphertext C = ( ide , ids , c ,{ c t 0 } t∈[k] ,{ ci } i ∈[ l ] , the unsigncryption key
PPT Slide
Lager Image
= { eti } t∈[k],i∈[l] for idu , and idv = ( id v1 , ⋯, idvl ) used for verification,
1. Let I = idu ide denote the set of matching bits in idu and ide , and J = idv ids denote the set of matching bits in idv and ids . If | I | < d or | J | < d' , output ⊥ and reject. Otherwise, continue.
2. For i ∈ [ l ], let
PPT Slide
Lager Image
= H 1 ( idui P i ),
PPT Slide
Lager Image
. By Shamir’s ( d , l ) threshold scheme, we have Σ i I LiBi,idui eti = ut (mod pq ) for t ∈ [ k ].
3. For t ∈ [ k ], compute
PPT Slide
Lager Image
, output Mt = 0, otherwise output Mt = 1. In this step, we retrieve the message M .
4. Compute s = c - qH 3 ( M ).
5. For i ∈ [ l ], compute
PPT Slide
Lager Image
= H 1 ( idei P i ),
PPT Slide
Lager Image
.
6. For i ∈ [ l ], compute
PPT Slide
Lager Image
= H 2 ( ids P idsi P i ),
PPT Slide
Lager Image
.
7. Verify whether
PPT Slide
Lager Image
and ej ∈ 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 = idu ide denote the set of matching bits in idu and ide , J = idv ids denote the set of matching bits in idv and ids , and | I | ≥ d , | J | ≥ d' . Then for t = 1,⋯, k ,
PPT Slide
Lager Image
According to parameters setting in Setup of our scheme,
PPT Slide
Lager Image
with overwhelming probability, then
PPT Slide
Lager Image
, then Mt = 0 ; otherwise Mt = 1. And M = ( M 1 , ⋯, Mk ).
Then s = c - qH 3 ( M ) and
PPT Slide
Lager Image
for i ∈ [ l ] . Because of ei = SamplePre (
PPT Slide
Lager Image
,
PPT Slide
Lager Image
, qui , σ' ) and u = H 3 ( M ) = Σ j J Lj uj (mod p ), we have
PPT Slide
Lager Image
and ej ∈ 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 IND-sID-CPA 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 (IND-sID-CPA) .
Proof . We prove Theorem 5.1 by contradiction. Suppose that there exists a PPT adversary A who can attack the IND-sID-CPA 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 IND-sID-CPA 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
PPT Slide
Lager Image
for t = 1,⋯, k , and
PPT Slide
Lager Image
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
PPT Slide
Lager Image
for i ∈ [ l ].
2. Sample l random matrices R 1 * ,⋯, Rl * ← D mxm , and let
PPT Slide
Lager Image
for i ∈ [ l ].
3. For i ∈ [ l ],
PPT Slide
Lager Image
is obtained by algorithm TrapGen , together with a short basis
PPT Slide
Lager Image
.
4. Vectors ut = wt for t ∈ [ k ].
Then PP = ({ Ai,b } i∈[l],b∈{0,1} , { ut } 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 , ⋯, idl ), and the challenger C answers as follows.
For ( idi P i ), i ∈ [ l ],
1. If idi = id*i , let H 1 ( idi P i ) = Ri * .
2. If idi id*i , sample
PPT Slide
Lager Image
← D mxm randomly, let H 1 ( idi P i ) =
PPT Slide
Lager Image
.
Then save( id ,(( idi P i ), H 1 ( idi P i )) i ∈[ l ] ) in list H 1 and return (( idi P i ), H 1 ( idi P i )) i ∈[ l ] .
H 2   queries – The adversary A asks for H 2 ( id ) for an identity id = ( id 1 , ⋯, idl ), and the challenger C answers as follows.
For ( id P idi P i ), i ∈ [ l ],
1. If idi = id*i , run algorithm SampleRwithBasis  
PPT Slide
Lager Image
to obtain a random
PPT Slide
Lager Image
← D mxm and a short basis
PPT Slide
Lager Image
for lattice
PPT Slide
Lager Image
.
Let H 2 ( id P idi P i ) =
PPT Slide
Lager Image
.
2. If idi id*i , sample
PPT Slide
Lager Image
← D mxm randomly, let H 2 ( id P idi P i ) =
PPT Slide
Lager Image
, invoke algorithm BasisDel (
PPT Slide
Lager Image
,
PPT Slide
Lager Image
,
PPT Slide
Lager Image
, σ ) to get a short basis
PPT Slide
Lager Image
for lattice
PPT Slide
Lager Image
.
Then save
PPT Slide
Lager Image
in list H 2 and return
PPT Slide
Lager Image
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
PPT Slide
Lager Image
.
2. For t ∈ [ k ] , let the shares of ut be uti = ut + a t 1 i + a t 2 i 2 +⋯+ a td -1 i d-1 , where a t 1 ,⋯, a td -1 are vector variables with length n .
3. For i ∈ [ l ], execute H 1 ( id ) query to obtain
PPT Slide
Lager Image
= H 1 ( idi P i ), and let
PPT Slide
Lager Image
.
4. For t ∈ [ k ], i ∈ [ d 0 ], select eti
PPT Slide
Lager Image
, and let uti =
PPT Slide
Lager Image
eti .
5. For t ∈ [ k ], i ∈ { d 0 + 1,⋯, d -1}, choose d - 1 - d 0 shares
PPT Slide
Lager Image
,⋯, u td -1 randomly, then the values for a t 1 ,⋯, a td -1 are fixed and all l shares u t 1 , ⋯, utl are known.
6. For t ∈ [ k ], i ∈ { d 0 +1,⋯, l }, since
PPT Slide
Lager Image
is known, invoke algorithm BasisDel (
PPT Slide
Lager Image
,
PPT Slide
Lager Image
,
PPT Slide
Lager Image
, σ ) to get a short basis
PPT Slide
Lager Image
for lattice
PPT Slide
Lager Image
, then invoke algorithm SamplePre (
PPT Slide
Lager Image
,
PPT Slide
Lager Image
, uti , σ' ) to get eti ∈ Z m satisfying
PPT Slide
Lager Image
eti = uti .
7. Return the unsigncryption key for the identity id as { eti } 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
PPT Slide
Lager Image
then returns
PPT Slide
Lager Image
• 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
PPT Slide
Lager Image
for t ∈ [ k ].
2. Let
PPT Slide
Lager Image
for i ∈ [ l ].
3. Select
PPT Slide
Lager Image
randomly.
Then ( id * , id * s , c ,{ c t 0 } t∈[k] ,{ ci } 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 Fujisaki-Okamoto method to Construction 1 to obtain an IND-sID-CCA2 secure fuzzy identity-based signcryption scheme – Construction 2, which is illustrated as follows.
Setup ( n , d , d' ) On input security parameter
PPT Slide
Lager Image
, 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 ,
PPT Slide
Lager Image
2. For i ∈ [ l ], b ∈ {0,1}, invoke algorithm TrapGen ( n ) to obtain ( Ai,b , Ti,b ), with the condition that
(a)
PPT Slide
Lager Image