# Deterministic Identity-Based Encryption from Lattice-Based Programmable Hash Functions with High Min-Entropy

Authors: Daode Zhang; Jie Li; Bao Li; Xianhui Lu; Haiyang Xue; Dingding Jia; Yamin Liu
Journal: Security and Communication Networks
 (2019)

---

## Abstract

There only exists one deterministic identity-based encryption (DIBE) scheme which is adaptively secure in the auxiliary-input setting, under the learning with errors (LWE) assumption. However, the master public key consists ofO(λ) basic matrices. In this paper, we consider to construct adaptively secure DIBE schemes with more compact public parameters from the LWE problem. (i) On the one hand, we gave a generic DIBE construction from lattice-based programmable hash functions with high min-entropy. (ii) On the other hand, when instantiating our generic DIBE construction with four LPHFs with high min-entropy, we can get four adaptively secure DIBE schemes with more compact public parameters. In one of our DIBE schemes, the master public key only consists of ω(log⁡λ) basic matrices.


---

## Body

## 1. Introduction

A DIBE scheme is an identity-based encryption (IBE) scheme [1] whose encryption algorithm is deterministic. This primitive was proposed by Bellare et al. [2] via extending the security definition under high min-entropy into the identity-based setting. In order to construct DIBE schemes, Bellare et al. [2] first defined a notion of identity-based lossy trapdoor functions (IB-LTDFs). And they obtained a DIBE scheme by constructing an IB-LTDF with a universal property, based on the DLIN assumption. However, due to the inherent limitation of IB-LTDFs, their scheme can only achieve a selective security; i.e., the adversary must commit an challenge identity before getting the master public key from the challenger.In SCN12, Xie et al. [3] gave a more efficient secure DIBE scheme in the auxiliary-input setting, based on the hardness of the LWE problem. In their scheme, there exists only 3 matrices in the master public key. However, the scheme only satisfies a selective security same as the scheme in [2]. The more significant contribution of Xie et al. [3] is that they proposed the first DIBE scheme with a much more realistic adaptive security (or equivalently, full security) in the auxiliary-input setting, based on the same assumption. To the best of our knowledge, their scheme is the only DIBE scheme that achieves an adaptive security. However, their scheme requires l+2 basic matrices in the master public key so that it is less efficient than their selectively secure scheme, where l is the bit length of the identity and l=Θ(λ).Our Contributions. In this paper, we consider to construct adaptively secure DIBE schemes with more compact public parameters from the LWE problem.(i)
We gave a generic DIBE construction from lattice-based programmable hash functions (LPHFs) with high min-entropy [4]. Note that the adaptively secure DIBE in [3] is in our framework.(ii)
We present more instantiations of LPHFs with high min-entropy. In fact, most of these instantiations are already implicit in recent works. Following the works of Zhang et al. [4] who proved that the IBE schemes in [4–6] imply instantiations of LPHFs with high min-entropy, we show that LPHFs with high min-entropy can be constructed from partitioning functions with compatible algorithms [7]. And we show that the IBE schemes in [8–10] naturally imply instantiations of LPHFs with high min-entropy. Combining with the result of Zhang et al., we conclude that the adaptively secure and anonymous IBE schemes in [4–10] naturally imply instantiations of LPHFs with high min-entropy (note that Boyen and Li [11] constructed an adaptively secure and anonymous IBE scheme with tight security. However, their construction does not imply a LPHF and is not in our framework).(iii)
When instantiating our generic DIBE construction with four LPHFs with high min-entropy in [4, 7, 8], we can get four adaptively secure DIBE schemes with more compact public parameters. In our DIBE schemes, the master public key, respectively, consists of ω(log2λ),ω(log⁡λ),λ,O(log⁡Q) number of basic matrices, where Q denotes the number of key extraction queries. Please see more details in Table 1.Table 1
Comparison of Adaptively Secure DIBE Schemes in the Auxiliary-Input Setting.
Schemes # of Zqn×m matrixmpk RoundingParameter p MessageSpace t SampleWidth σ ReductionCost XXZ12 [3] O ( λ ) O ~ ( n 4.5 + 3 η ) O ~ ( n 3.5 + 2 η ) O ~ ( n 2.5 + η ) O ϵ l Q  Ours: D I B E M A H ω ( l o g 2 λ ) O ~ ( n 6.5 + 5.5 η ) O ~ ( n 6 + 5 η ) O ~ ( n 5 + 4 η ) O ϵ φ + 1 Q φ † DIBEAFF ω ( l o g λ ) p o l y ( n ) p o l y ( n ) p o l y ( n ) O ϵ 2 l 2 Q DIBEYam16 λ O ~ ( n c + 3.5 + 2.5 η ) O ~ ( n c + 3 + 2 η ) O ~ ( n c + 2 + η ) § O ϵ 3 l Q 2 D I B E Z C Z 16 O ( l o g Q ) O ~ ( n c + 4 + 3 η ) O ~ ( n c + 3.5 + 2.5 η ) O ~ ( n c + 2.5 + 1.5 η ) ‡ O ϵ l Q 2 | m p k | shows the size of the master public key. Q and ϵ denote the number of key extraction queries and the advantage of the adversary, respectively. poly(n) represents a fixed but large polynomial that does not depend Q and ϵ. To measure the reduction cost, we show the advantage of the LWE algorithm constructed from the adversary against the corresponding DIBE scheme. †, φ>1 is the constant satisfying s=1-2-1/φ, where s∈{0,1} is the relative distance of the underlying error correcting code. We can take φ as close to 1 as one wants. §, c=c1+c2 and c1,c2 are the smallest integers satisfying that nc1/2≥Q+1 and n-c2≤ϵ. ‡, c is the smallest integer satisfying that nc≥Q+1.Related Works. In [2], Bellare et al. extended the notion of lossy trapdoor function (LDTF) to identity-setting and introduced the notion of identity-based LTDF (IB-LTDF). And they used IB-LTDF to construct DIBE scheme with a selective security from pairings. Soon afterwards, Escala et al. [12] extended the notion of IB-LTDF [2] and introduced the notion of hierarchical identity-based trapdoor functions (HIB-TDFs). With HIB-TDFs, they could construct deterministic hierarchical identity-based schemes (DHIBE). They instantiated HIB-TDFs from pairings so that they constructed a pairing-based DHIBE scheme. Fang et al. [13] constructed a DHIBE scheme with a selective security based on the hardness of the learning with rounding problem over small modulus [14]. In fact, a DHIBE with a selective security implies a selectively secure DIBE. In SCN12, Xie et al. [3] gave a more efficient DIBE scheme with a security. Additionally, they also proposed the first and the only DIBE scheme with an adaptive security in the auxiliary-input setting.Remarks. This work is very relevant to [15] in which we constructed the DIBE schemes DIBEMAH, DIBEAFF, and DIBEYam16 directly from the works of Yamada [7, 8]. As our growing understanding, we find that all adaptively secure DIBE schemes in [3, 15] can be explained by using LPHFs with high min-entropy (note that the adaptively secure DIBE scheme in [3] is constructed from the LPHF with high min-entropy in [5, 6].). So, in this paper, we present a generic DIBE construction from LPHFs with high min-entropy.


## 2. Preliminaries

Notations. Let λ be the security parameter, and all other quantities are implicitly dependent on λ. Let negl(λ) denote a negligible function and poly(λ) denote an unspecified function f(λ)=O(λc) for some constant c. A function f is ϵ-hard-to-invert with respect to the distribution D, if, given h(x) with x←$D, there exists no PPT algorithm that can find x with probability better than ϵ. For n∈N, we use [n] to denote a set {1,…,n}. And, for integer q≥2, Zq denotes the quotient ring of integer modulo q. We use bold capital letters to denote matrices, such as A,B, and bold lowercase letters to denote column vectors, such as x, y. The notations A⊤ and [A∣B] denote the transpose of the matrix A and the matrix of concatenating A and B, respectively.Forn∈N, we use [n] to denote a set {1,…,n}. For integer q≥2, Zq denotes the quotient ring of integer modulo q. For integers q≥p≥2 and x∈Zq, a rounding function ·p:Zq→Zp is defined by xp=⌊(p/q)·x⌉modp.


### 2.1. Deterministic Identity-Based Encryption and Its Security

A deterministic identity-based encryption schemeDIBE with the identity space ID can be defined by a tuple of PPT algorithms DIBE.Setup,DIBE.KGen,DIBE.Enc,DIBE.Dec. The DIBE.Setup algorithm takes a security parameter 1λ as input and outputs a master secret key mpk and a master secret key msk. The DIBE.KGen algorithm takes mpk,msk,id∈ID as input and outputs a private key skid. The deterministic algorithm DIBE.Enc takes mpk,id∈ID and a message m, outputs a ciphertext c. The deterministic algorithm DIBE.Dec decrypts ciphertexts using the private key skid. We require that, for all λ, all id∈ID, and all m in the specified message space, PrDIBE.Dec(mpk,skid,DIBE.Enc(mpk,id,m))=m=1-negl(λ).Definition 1 (see [3]).
We say that a DIBE schemeDIBE is PRIV1-ID-INDr-secure with respect to ϵ-hard-to-invert auxiliary inputs if for any PPT algorithm A, for any efficiently sampled distribution M, and for any efficiently computable H={h}, that is, ϵ-hard-to-invert with respect to M, the advantage of A in the following game is negligible. Setup. At the outset of the game, the challenger runs DIBE.Setup(1λ) which outputs a pair (mpk,msk) and gives mpk to A.Phase1. When A adaptively makes key-extraction queries to the challenger, the challenger returns skid←DIBE.KGen(mpk,msk,id), for all id in the key-extraction queries.ChallengePhase. At some point, A outputs an identity id∗, on which it wishes to be challenged. Then, the challenger picks a random coin coin←${0,1}, a message m←$M, a random ciphertext c1∗ from the ciphertext space C, and a function h←$H. If coin=0, it runs DIBE.Enc(mpk,id∗,m)→c0∗ and gives the challenge ciphertext (c0∗,h(m)) to A. If coin=1, it gives (c1∗,h(m)) to A.Phase2. A can also adaptively make key-extraction queries to the challenger, with the restriction id≠id∗.Gauss. Finally, A makes a guess coin′ for coin.
The advantage ofA is defined as Prcoin′=coin-1/2.


### 2.2. LPHFs with High Min-Entropy [4]

Letl,m¯,m,n,q,v be some polynomials in the security parameter λ. By In we denote the set of invertible matrices in Zqn×n. A hash function H:ID→Zqn×m consists of two algorithms (H.Gen,H.Eval). Given the security parameter λ, the probabilistic polynomial time (PPT) key generation algorithm H.Gen(1λ) outputs a key K; i.e., K←H.Gen(1λ). For any input id∈ID={0,1}l, the efficiently deterministic evaluation algorithm H.Eval(K,id) outputs a hash value Z∈Zqn×m; i.e., Z=H.Eval(K,id).Definition 2 (LPHFs).
A hash functionH:ID→Zqn×m is a (1,v,β,γ,δ)-LPHF if there exist a PPT trapdoor key generation algorithm H.TrapGen and a PPT deterministic trapdoor evaluation algorithm H.TrapEval such that given a uniformly random matrix A∈Zqn×m¯ and a (public) trapdoor matrix B∈Zqn×m the following properties hold: Syntax: the PPT algorithm (K′,td)←H.TrapGen(1λ,A,B) outputs a key K′ together with a trapdoor td. Moreover, for any input id∈ID, the deterministic algorithm (Rid′,Sid′)=H.TrapEval(td,K′,id) returns Rid′∈Zqm¯×m and Sid′∈Zqn×n such that s1(Rid′)≤β and Sid′∈In∪{0} hold with overwhelming probability over the trapdoor td that is produced along with K′.Correctness: for all possible (K′,td)←H.TrapGen(1λ,A,B), all id∈ID, and its corresponding (Rid′,Sid′)=H.TrapEval(td,K′,id), we have (1)H.EvalK′,id=ARid′+Sid′B.Statisticallyclosetrapdoorkeys: for all (K′,td)←H.TrapGen(1λ,A,B) and  K←H.Gen(1λ), the statistical distance between (A,K′) and (A,K) is at most γ.Well-distributedhiddenmatrices: for all (K′,td)←H.TrapGen(1λ,A,B), any inputs id∗,id1,…,idv such that id∗≠idj for any j∈[v], we have that Pr[Sid∗′=0∧Sid1′,…,Sidv′∈In]≥δ, where (Rid∗′,Sid∗′)=H.TrapEval(td,K′,id∗) and (Ridj′,Sidj′)=H.TrapEval(td,K′,idj).Definition 3 (LPHFs with high min-entropy).
LetH:ID→Zqn×m be a (1,v,β,γ,δ)-LPHF with γ=negl(λ) and noticeable δ>0. Let K be the key space of H, and let H.TrapGen and H.TrapEval be a pair of trapdoor generation and trapdoor evaluation algorithms for H. We say that H is a revised LPHF with high min-entropy if, for uniformly random matrix A∈Zqn×m¯ and a (public) trapdoor matrix B∈Zqn×m, the following condition holds(i)
Property1. For any (K′,td)←H.TrapGen(1λ,A,B), any id∈ID and its corresponding (Rid′,Sid′)=H.TrapEval(td,K′,id), the statistical distance between A,K′,v,u and (A,K′,v,(Rid′)⊤v) is negligible in λ, where u←$Zqm, v←$Zqm¯.Remark 4.
Note that this definition of LPHFs with min-high-entropy is much weaker than Zhang et al.’s definition of LPHFs with min-high-entropy which includes another one requirement. In [9], Katsumata and Yamada found that this requirement is not necessary; i.e., we can define this weaker version of LPHFs with min-high-entropy while keeping their functionality–constructing IBE schemes.


## 2.1. Deterministic Identity-Based Encryption and Its Security

A deterministic identity-based encryption schemeDIBE with the identity space ID can be defined by a tuple of PPT algorithms DIBE.Setup,DIBE.KGen,DIBE.Enc,DIBE.Dec. The DIBE.Setup algorithm takes a security parameter 1λ as input and outputs a master secret key mpk and a master secret key msk. The DIBE.KGen algorithm takes mpk,msk,id∈ID as input and outputs a private key skid. The deterministic algorithm DIBE.Enc takes mpk,id∈ID and a message m, outputs a ciphertext c. The deterministic algorithm DIBE.Dec decrypts ciphertexts using the private key skid. We require that, for all λ, all id∈ID, and all m in the specified message space, PrDIBE.Dec(mpk,skid,DIBE.Enc(mpk,id,m))=m=1-negl(λ).Definition 1 (see [3]).
We say that a DIBE schemeDIBE is PRIV1-ID-INDr-secure with respect to ϵ-hard-to-invert auxiliary inputs if for any PPT algorithm A, for any efficiently sampled distribution M, and for any efficiently computable H={h}, that is, ϵ-hard-to-invert with respect to M, the advantage of A in the following game is negligible. Setup. At the outset of the game, the challenger runs DIBE.Setup(1λ) which outputs a pair (mpk,msk) and gives mpk to A.Phase1. When A adaptively makes key-extraction queries to the challenger, the challenger returns skid←DIBE.KGen(mpk,msk,id), for all id in the key-extraction queries.ChallengePhase. At some point, A outputs an identity id∗, on which it wishes to be challenged. Then, the challenger picks a random coin coin←${0,1}, a message m←$M, a random ciphertext c1∗ from the ciphertext space C, and a function h←$H. If coin=0, it runs DIBE.Enc(mpk,id∗,m)→c0∗ and gives the challenge ciphertext (c0∗,h(m)) to A. If coin=1, it gives (c1∗,h(m)) to A.Phase2. A can also adaptively make key-extraction queries to the challenger, with the restriction id≠id∗.Gauss. Finally, A makes a guess coin′ for coin.
The advantage ofA is defined as Prcoin′=coin-1/2.


## 2.2. LPHFs with High Min-Entropy [4]

Letl,m¯,m,n,q,v be some polynomials in the security parameter λ. By In we denote the set of invertible matrices in Zqn×n. A hash function H:ID→Zqn×m consists of two algorithms (H.Gen,H.Eval). Given the security parameter λ, the probabilistic polynomial time (PPT) key generation algorithm H.Gen(1λ) outputs a key K; i.e., K←H.Gen(1λ). For any input id∈ID={0,1}l, the efficiently deterministic evaluation algorithm H.Eval(K,id) outputs a hash value Z∈Zqn×m; i.e., Z=H.Eval(K,id).Definition 2 (LPHFs).
A hash functionH:ID→Zqn×m is a (1,v,β,γ,δ)-LPHF if there exist a PPT trapdoor key generation algorithm H.TrapGen and a PPT deterministic trapdoor evaluation algorithm H.TrapEval such that given a uniformly random matrix A∈Zqn×m¯ and a (public) trapdoor matrix B∈Zqn×m the following properties hold: Syntax: the PPT algorithm (K′,td)←H.TrapGen(1λ,A,B) outputs a key K′ together with a trapdoor td. Moreover, for any input id∈ID, the deterministic algorithm (Rid′,Sid′)=H.TrapEval(td,K′,id) returns Rid′∈Zqm¯×m and Sid′∈Zqn×n such that s1(Rid′)≤β and Sid′∈In∪{0} hold with overwhelming probability over the trapdoor td that is produced along with K′.Correctness: for all possible (K′,td)←H.TrapGen(1λ,A,B), all id∈ID, and its corresponding (Rid′,Sid′)=H.TrapEval(td,K′,id), we have (1)H.EvalK′,id=ARid′+Sid′B.Statisticallyclosetrapdoorkeys: for all (K′,td)←H.TrapGen(1λ,A,B) and  K←H.Gen(1λ), the statistical distance between (A,K′) and (A,K) is at most γ.Well-distributedhiddenmatrices: for all (K′,td)←H.TrapGen(1λ,A,B), any inputs id∗,id1,…,idv such that id∗≠idj for any j∈[v], we have that Pr[Sid∗′=0∧Sid1′,…,Sidv′∈In]≥δ, where (Rid∗′,Sid∗′)=H.TrapEval(td,K′,id∗) and (Ridj′,Sidj′)=H.TrapEval(td,K′,idj).Definition 3 (LPHFs with high min-entropy).
LetH:ID→Zqn×m be a (1,v,β,γ,δ)-LPHF with γ=negl(λ) and noticeable δ>0. Let K be the key space of H, and let H.TrapGen and H.TrapEval be a pair of trapdoor generation and trapdoor evaluation algorithms for H. We say that H is a revised LPHF with high min-entropy if, for uniformly random matrix A∈Zqn×m¯ and a (public) trapdoor matrix B∈Zqn×m, the following condition holds(i)
Property1. For any (K′,td)←H.TrapGen(1λ,A,B), any id∈ID and its corresponding (Rid′,Sid′)=H.TrapEval(td,K′,id), the statistical distance between A,K′,v,u and (A,K′,v,(Rid′)⊤v) is negligible in λ, where u←$Zqm, v←$Zqm¯.Remark 4.
Note that this definition of LPHFs with min-high-entropy is much weaker than Zhang et al.’s definition of LPHFs with min-high-entropy which includes another one requirement. In [9], Katsumata and Yamada found that this requirement is not necessary; i.e., we can define this weaker version of LPHFs with min-high-entropy while keeping their functionality–constructing IBE schemes.


## 3. Generic DIBE Construction

Here, we construct an adaptively secure DIBE scheme in the auxiliary-input setting by using a(1,v,β,γ,δ) LPHF H with high min-entropy from {0,1}l to Zqn×m, where γ is negligible and δ>0 is noticeable. Let H.TrapGen and H.TrapEval be a pair of trapdoor generation and trapdoor evaluation algorithm of H that satisfies the condition in Definition 3, where integers n,m,q,v,β are polynomials in the security parameter λ. Additionally, let integers m¯=O(nlogq),m′=m¯+m. We assume ID={0,1}l and M=Ztn, where ID is the user identity space and M is the message space. Our generic DIBE scheme DIBE=DIBE.Setup,DIBE.KGen,DIBE.Enc,DIBE.Dec is defined as follows.(i)
Setup. Algorithm DIBE.Setup takes 1λ as input, and generates a pair (A,TA)←$TrapGen(1n,1m¯,q), where A∈Zqn×m¯ and TA∈Zqm¯×m¯. Then, it obtains K←H.Gen(1λ). Finally, it outputs(2)mpk=A,Kandmsk=TA.(ii)
Key Generation. Algorithm DIBE.KGen takes mpk and id∈ID as inputs. It first computes Fid=A∣H.Eval(K,id)∈Zqn×m′ and then generates TFid∈Zm′×m′ by running SampleBasisLeft(A,H.Eval(K,id),TA,σ). It finally outputs skid=TFid.(iii)
Encryption. Algorithm DIBE.Enc takes mpk, id∈ID, m∈M as inputs. It first computes Fid=[A∣H.Eval(K,id)]∈Zqn×m′and, then, it outputs the ciphertext c=Fid⊤mp.(iv)
Decryption. To decrypt a ciphertext c with a private key skid=TFid, the algorithm DIBE.Dec computes m←$Invert(c,Fid,skid). Then, if m∈Ztn it outputs m, and otherwise it outputs ⊥.


### 3.1. Correctness and Parameter Selection

In order to be sure of the correctness of the DIBE scheme and make the security proof follow through, we need the following to satisfy.(i)
TrapGen in Lemma A.2 (Item 1) can work (m¯≥6n⌈log⁡q⌉), and it returns TA satisfying TA~≥O(nlogq).(ii)
SampleBasisLeft in Lemma A.2 (Item 2) can operate (σ≥TA~·ω(log(m¯+m))=O(nlogq)·ω(log(m¯+m))).(iii)
SampleBasisRight in Lemma A.2 (Item 3) can operate (σ≥s1(Rid)·ω(logm)≥β·ω(logm)).(iv)
In order to keep the correctness of the DIBE scheme, i.e.,Invert in Lemma A.2 (Item 4) can work (TFid<p/(2m)), where TFid≤O(σ·m) given by both SampleBasisLeft and SampleBasisRight.(v)
ReRand (Lemma A.3) in the security proof can operate (θ>ω(logm¯), and θ′q/(2θq)>s1([Im∣Rid∗′]⊤), where s1([Im∣Rid∗′]⊤)≤(β+1).(vi)
LemmaA.1 holds (q is super-polynomial and α/θ=negl(λ)).(vii)
Pr[Bad7]≤2m(2B+1)p/q=negl(n)=n-ω(1), where B=θ′qn.To satisfy the above requirements, we set the parameters in Table2. The private key size, ciphertext siz,e and ciphertext expansion factor in our scheme are O(n2+3η), O(n1+ηlog⁡(mβ)), and O(nηlog⁡mβ/logt), respectively. To optimize the ciphertext expansion factor, we can choose t=mβ, which makes the ciphertext expansion factor to be O(nη).Table 2
Parameter Selection of Generic DIBE Construction.
Parameters Description Setting λ security parameter n PK-lattice row dimension n = λ l the length of identity l = n m¯ PK-matrix column number O ( n  l o g  q ) m matrix column number m = m ¯ σ S a m p l e B a s i s L e f t,SampleBasisRightwidth max ⁡ { β , m } ⋅ ω ( log ⁡ n ) p rounding parameter O ( σ ⋅ m 3 / 2 ) t message space m β q modulus the prime nearest to2nη, 0<η<1  θ error width ω ( log ⁡ n ) θ′ error width β ⋅ ω ( log ⁡ n )


### 3.2. Security of DIBE

Theorem 5.
IfH=(H.Gen,H.Eval) is a (1,v,β,γ,δ) LPHF with high min-entropy from {0,1}l to Zqn×m, where γ is negligible, δ>0 is noticeable and independent of the modulus q, and large enough v=poly(n). Then, the above DIBE scheme DIBE is PRIV1-ID-INDr-secure with respect to 2-klogt-hard-to-invert auxiliary inputs, assuming DLWEq,n,m¯,θ,H is hard.According to LemmaA.1, it is easy for us to get the following corollary.Corollary 6.
IfH=(H.Gen,H.Eval) is a (1,v,β,γ,δ)-LPHF with high min-entropy from {0,1}l to Zqn×m, where γ is negligible, δ>0 is noticeable and independent of the modulus q and large enough v=poly(n). Then, the above DIBE scheme DIBE is PRIV1-ID-INDr-secure with respect to 2-klogt-hard-to-invert auxiliary inputs, assuming DLWEq,z,m¯,α is hard, where z=△(klog(t)-ω(log⁡(λ)))/log(q).Proof of Theorem5.
LetA be a PPT adversary that breaks the PRIV1-ID-INDr-security with auxiliary inputs of the DIBE scheme. Moreover, let ϵ=ϵ(λ) and Q=Q(λ)≤v be its advantage and the upper bound of the number of IBE.KGen(·) queries, respectively. And let I∗={id∗,{idj}j∈[Q]} denote the challenge ID along with the queried IDs. For any distribution M over Ztn, let H={h} be a set of z-llog(t)-hard-to-invert functions with respect to M.
In order to prove the security of thisDIBE scheme, we define a sequence of games. In each game, the challenger selects a uniform bit coin←${0,1}, while the adversary A finally returns a guess bit coin′ to the challenger. The challenger sets coin^=coin′ in the first game; these values might be different in the latter games. In the following, we define Xi as the event that coin^=coin.
G a m e 0: this game is the original PRIV1-ID-INDr game with auxiliary inputs. By definition, we have(3)PrX0-12=Prcoin^=coin-12=Prcoin′=coin-12=ϵ.
G a m e 1: this game is identical to Game0 except that the challenger changes the setup and challenge phase as below.Setup. It first generates a pair (A,TA)←$TrapGen(1n,1m¯,q), where A∈Zqn×m¯ and TA∈Zqm¯×m¯. Then, it computes (K′,td)←H.TrapGen(A,G). Finally, it outputs mpk=(A,K′) and keeps the trapdoor td private.ChallengePhase. The challenger directly uses (K′,td) to generate the challenge ciphertext.
According to the property ofstatisticallyclosetrapdoorkeys, we have PrX1-PrX0<negl(λ).
G a m e 2: this game is identical to Game1 except that the challenger performs the following additional step at the end of the game. The challenger first defines(4)τtd^,K^,I∗=0ifS^id∗=0andS^idjisinvertibleforallj∈Q1otherwise,where (R^id∗,S^id∗)=H.TrapEval(td^,K^,id∗) and (R^idj,S^idj)=H.TrapEval(td^,K^,idj). Then, the challenger proceeds the following steps: AbortCheck: in the setup phase, the challenger generates a pair of (K′,td). If τ(td,K′,I∗)=1, the challenger aborts the game and sets coin^←${0,1} ignoring the output of A. Otherwise, the following equation holds:(5)H.TrapEvaltd,K′,id=ARid∗′ifid=id∗ARid′+Sid′Gotherwise.ArtificialAbort: Fix I∗; let p be the probability p=Pr[τ(td^,K^,I∗)=0] over the random choice of (td^,K^). Then, the challenger samples O(ϵ2log⁡ϵ-1δ-1log⁡(δ-1)) times the probability p by independently running (K^,td^)←H.TrapGen(A,G) and evaluating τ(td^,K^,I∗) to compute an estimate p′. Then if p′≥δ, the challenger will abort with probability (p′-δ)/p′ and sets coin^←${0,1} ignoring the output of A.
Finally, when receivingcoin′ from A, the challenger sets coin^=coin′.
Fori∈{2,3,4,5,6,7}, let p~i be the probability that the challenger does not abort in the abort check stage in Gamei, and let pi be the probability in the artificial abort stage of Gamei defined by pi=Pr[τ(td^,K^,I∗)=0]. Since the adversary might obtain some information of td from the challenge ciphertext, the probability p~i might not be equal to the probability pi. Formally, let Γi be the absolute difference between p~i and pi (i.e., Γi=p~i-pi). As we show in Lemma 8, we have(6)PrX2-12≥12ϵδ-Γ2.So as not to interrupt the proof of Theorem 5, we intentionally skip the proof for the time being.
G a m e 3: this game is identical to Game2 except that the challenger changes setup, phases 1 and 2, and challenge phase as below.Setup. It first selects a random matrix A←$Zqn×m¯. Then, it computes (K′,td)←H.TrapGen(A,G). Finally, it outputs mpk=(A,K′) and keeps the trapdoor td private.Phase1. When receiving the private key query with identity id, the challenger first computes Rid′,Sid′=H.TrapEvaltd,K′,id. If Sid′ is not invertible, the challenger aborts the game and sets coin^←$0,1. Otherwise, it computes skid=SampleBasisRightA,G,Rid′,Sid′,TG,σ and sends skid to A.ChallengePhase. The challenger computes (Rid∗′,Sid∗′)=H.TrapEval(td,K′,id∗). If Sid∗≠0, the challenger aborts the game and sets coin^←${0,1}. Otherwise, when coin=0, we have (7)c^=Fid∗⊤m=A⊤mRid∗′⊤A⊤m∈Zqm′.Then, the challenger computesc0∗=c^p. Finally, the challenger returns  ccoin∗,hm to the adversary A.Phase2. The challenger responds as in Phase1, when receiving the private key query with identity id≠id∗.
It is easy to see that(8)Pr⁡X3=Pr⁡X2andPrΓ3=PrΓ2.
G a m e 4: in this game, the challenger changes the way that the challenge ciphertext is created when coin=0.ChallengePhase. The challenger computes (Rid∗′,Sid∗′)=H.TrapEval(td,K′,id∗). If Sid∗≠0, the challenger aborts the game and sets coin^←${0,1}. Otherwise, when  coin=0, the challenger first picks m←$Ztn and chooses e1←$DZm¯,θ′q,e2←$DZm,θ′q and computes(9)c^=c^1+c^2=A⊤mRid∗′⊤A⊤m+e1e2=A⊤m+e1Rid∗′⊤A⊤m+e2.Then, the challenger computesc0∗=c^p. Finally, the challenger returns (ccoin∗,h(m)) to the adversary A.
Before analyzing the difference betweenGame3 and Game4, we first define a “bad event” as follows: Bad4=△c^1+[-B,B]m′p≠c^1p, where B=θ′qn.
IfBad4 does not occur for some c^1, then we have (10)c^p=A⊤m+e1pRid∗′⊤A⊤m+e2p=A⊤mpRid∗′⊤A⊤mp=Fid∗⊤mp.
It immediately follows that for any adversaryA(11)Pr⁡X4-Pr⁡X3≤Pr⁡Bad4andPrΓ4-PrΓ3≤PrBad4.
G a m e 5: in this game, the challenger changes the way that the challenge ciphertext is created when coin=0ChallengePhase. The challenger computes (Rid∗′,Sid∗′)=H.TrapEval(td,K′,id∗). If Sid∗′≠0, the challenger aborts the game and sets coin^←${0,1}. Otherwise, when coin=0, the challenger first picks m←$Ztn and e←$DZm¯,θq and computes b=A⊤m+e. It runs the algorithm ReRand to get c^; i.e.,(12)c^=ReRandIm¯Rid∗′⊤,b,θq,θ′q2θqin the LemmaA.3, where  Im¯  is the unit matrix of size m¯×m¯.According to the property of the algorithmReRand, we have(13)Pr⁡X5=Pr⁡X4andPrΓ5=Pr⁡Γ4andPrBad5=PrBad4.
G a m e 6: in this game, the challenger changes the way that the challenge ciphertext is created when coin=0.ChallengePhase. The challenger computes (Rid∗′,Sid∗′)=H.TrapEval(td,K′,id∗). If Sid∗′≠0, the challenger aborts the game and sets coin^←${0,1}. Otherwise, when coin=0, the challenger first picks v←$Zqm¯,e←$DZm¯,θq and sets b=v+e. Then, it computes(14)c^=ReRandIm¯Rid∗′⊤,b,θq,θ′q2θq∈Zqm′. We construct an algorithm B against the problem DLWEq,n,m¯,θ,H as follows. Given the problem instance of LWE (A,b=v+e)∈Zqn×m¯×Zqm¯, where e←$DZm¯,θq. The task of B is to distinguish whether v=A⊤m for m←$Ztn or v←$Zqm¯. This subtle change from the standard DLWEq,n,m¯,θ,H is done only for convenience of the proof. B simulates the security game for the adversary A. If v=A⊤m, the view of A corresponds to Game5; otherwise, the view of A corresponds to Game6. As a result, we get that(15)PrX6-PrX5≤DLWEq,n,m¯,θ,H,PrΓ6-PrΓ5≤DLWEq,n,m¯,θ,H,PrBad6-PrBad5≤DLWEq,n,m¯,θ,H.
G a m e 7: in this game, the challenger changes the way that the challenge ciphertext is created when coin=0.ChallengePhase. The challenger computes (Rid∗′,Sid∗′)=H.TrapEval(td,K′,id∗). If Sid∗′≠0, the challenger aborts the game and sets coin^←${0,1}. Otherwise, when coin=0, the challenger computes(16)c^=c^1+c^2=vRid∗′⊤v+e1e2=v+e1Rid∗′⊤v+e2,instead of running the algorithmReRand, where e1←$DZm¯,θ′q, e2←$DZm,θ′q, v←$Zqm¯.
According to the property of the algorithmReRand, we have(17)Pr⁡X7=Pr⁡X6andPrΓ7=Pr⁡Γ6andPrBad7=PrBad6.Because for id∗∈ID the statistical distance between (A,K′,v,(Rid∗′)⊤v) and (A,K′,v,u) is negligible in λ, where u←$Zqm, c^1 is statistically close to uniform distribution over Zqm′, therefore for uniform c^1,(18)PrBad7≤2m2B+1pq=neglλ,by assumption on q and θ′. In the meantime, because c^ is statistically close to uniform distribution over Zqm′, we can get that(19)Pr⁡X7=12andPrΓ7=0.Summing up (6), (8), (11), (13), (15), (17), (18), and (19), we can get(20)DLWEq,n,m¯,θ,H≥ϵδ6-neglλ.In order to prove Theorem5, we should prove that (6) holds. We will use Lemma 28 in the full version of the work [5], which is described as follows.Lemma 7 (see [5]).
LetI∗ be a (Q+1)-ID tuple {id∗,{idj}j∈[Q]} denoting the challenge ID along with the queried IDs, and η(I∗) define the probability that an abort does not happen in Game2. Let ηmax=maxη(I∗) and ηmin=minη(I∗). For i=1,2, we set Xi as the event that coin^=coin at the end of Gamei. Then,(21)PrX2-12≥ηminPr⁡X1-12-12ηmax-ηmin.Lemma 8.
IfH is a (1,v,β,γ,δ)-LPHF with high min-entropy and Q≤v, then Pr[X2]-1/2≥1/2ϵδ-Γ2.Proof.
According to Lemma7, we only need to compute ηmax, ηmin,  and  ηmax-ηmin. By the definition of p~2 and p2 in Game2, we have η(I∗)=p~2(δ/p′), where p′ is an estimate of p2. Since the challenger always samples O(ϵ-2log⁡ϵ-1δ-1log⁡(δ-1)) times the probability p2 to compute p′, according to the Chernoff bounds, we have Pr[p′>p2(1+ϵ/8)]<δ(ϵ/8) and Pr[p′<p2(1-ϵ/8)]<δ(ϵ/8). As a result, the following equations hold:(22)ηmax≤1-δϵ8p~2δp21-ϵ/8,ηmin≥1-δϵ8p~2δp21+ϵ/8≥7δp~29p2,ηmax-ηmin≤1-δϵ8ϵδp~241-ϵ2/64p2≤16ϵδp~263p2.Finally, we have Pr[X2]-1/2≥7δp~2/9p2·ϵ-1/2·16ϵδp~2/63p2≥ϵδp2-Γ2/2p2≥(1/2)ϵ(δ-Γ2).


## 3.1. Correctness and Parameter Selection

In order to be sure of the correctness of the DIBE scheme and make the security proof follow through, we need the following to satisfy.(i)
TrapGen in Lemma A.2 (Item 1) can work (m¯≥6n⌈log⁡q⌉), and it returns TA satisfying TA~≥O(nlogq).(ii)
SampleBasisLeft in Lemma A.2 (Item 2) can operate (σ≥TA~·ω(log(m¯+m))=O(nlogq)·ω(log(m¯+m))).(iii)
SampleBasisRight in Lemma A.2 (Item 3) can operate (σ≥s1(Rid)·ω(logm)≥β·ω(logm)).(iv)
In order to keep the correctness of the DIBE scheme, i.e.,Invert in Lemma A.2 (Item 4) can work (TFid<p/(2m)), where TFid≤O(σ·m) given by both SampleBasisLeft and SampleBasisRight.(v)
ReRand (Lemma A.3) in the security proof can operate (θ>ω(logm¯), and θ′q/(2θq)>s1([Im∣Rid∗′]⊤), where s1([Im∣Rid∗′]⊤)≤(β+1).(vi)
LemmaA.1 holds (q is super-polynomial and α/θ=negl(λ)).(vii)
Pr[Bad7]≤2m(2B+1)p/q=negl(n)=n-ω(1), where B=θ′qn.To satisfy the above requirements, we set the parameters in Table2. The private key size, ciphertext siz,e and ciphertext expansion factor in our scheme are O(n2+3η), O(n1+ηlog⁡(mβ)), and O(nηlog⁡mβ/logt), respectively. To optimize the ciphertext expansion factor, we can choose t=mβ, which makes the ciphertext expansion factor to be O(nη).Table 2
Parameter Selection of Generic DIBE Construction.
Parameters Description Setting λ security parameter n PK-lattice row dimension n = λ l the length of identity l = n m¯ PK-matrix column number O ( n  l o g  q ) m matrix column number m = m ¯ σ S a m p l e B a s i s L e f t,SampleBasisRightwidth max ⁡ { β , m } ⋅ ω ( log ⁡ n ) p rounding parameter O ( σ ⋅ m 3 / 2 ) t message space m β q modulus the prime nearest to2nη, 0<η<1  θ error width ω ( log ⁡ n ) θ′ error width β ⋅ ω ( log ⁡ n )


## 3.2. Security of DIBE

Theorem 5.
IfH=(H.Gen,H.Eval) is a (1,v,β,γ,δ) LPHF with high min-entropy from {0,1}l to Zqn×m, where γ is negligible, δ>0 is noticeable and independent of the modulus q, and large enough v=poly(n). Then, the above DIBE scheme DIBE is PRIV1-ID-INDr-secure with respect to 2-klogt-hard-to-invert auxiliary inputs, assuming DLWEq,n,m¯,θ,H is hard.According to LemmaA.1, it is easy for us to get the following corollary.Corollary 6.
IfH=(H.Gen,H.Eval) is a (1,v,β,γ,δ)-LPHF with high min-entropy from {0,1}l to Zqn×m, where γ is negligible, δ>0 is noticeable and independent of the modulus q and large enough v=poly(n). Then, the above DIBE scheme DIBE is PRIV1-ID-INDr-secure with respect to 2-klogt-hard-to-invert auxiliary inputs, assuming DLWEq,z,m¯,α is hard, where z=△(klog(t)-ω(log⁡(λ)))/log(q).Proof of Theorem5.
LetA be a PPT adversary that breaks the PRIV1-ID-INDr-security with auxiliary inputs of the DIBE scheme. Moreover, let ϵ=ϵ(λ) and Q=Q(λ)≤v be its advantage and the upper bound of the number of IBE.KGen(·) queries, respectively. And let I∗={id∗,{idj}j∈[Q]} denote the challenge ID along with the queried IDs. For any distribution M over Ztn, let H={h} be a set of z-llog(t)-hard-to-invert functions with respect to M.
In order to prove the security of thisDIBE scheme, we define a sequence of games. In each game, the challenger selects a uniform bit coin←${0,1}, while the adversary A finally returns a guess bit coin′ to the challenger. The challenger sets coin^=coin′ in the first game; these values might be different in the latter games. In the following, we define Xi as the event that coin^=coin.
G a m e 0: this game is the original PRIV1-ID-INDr game with auxiliary inputs. By definition, we have(3)PrX0-12=Prcoin^=coin-12=Prcoin′=coin-12=ϵ.
G a m e 1: this game is identical to Game0 except that the challenger changes the setup and challenge phase as below.Setup. It first generates a pair (A,TA)←$TrapGen(1n,1m¯,q), where A∈Zqn×m¯ and TA∈Zqm¯×m¯. Then, it computes (K′,td)←H.TrapGen(A,G). Finally, it outputs mpk=(A,K′) and keeps the trapdoor td private.ChallengePhase. The challenger directly uses (K′,td) to generate the challenge ciphertext.
According to the property ofstatisticallyclosetrapdoorkeys, we have PrX1-PrX0<negl(λ).
G a m e 2: this game is identical to Game1 except that the challenger performs the following additional step at the end of the game. The challenger first defines(4)τtd^,K^,I∗=0ifS^id∗=0andS^idjisinvertibleforallj∈Q1otherwise,where (R^id∗,S^id∗)=H.TrapEval(td^,K^,id∗) and (R^idj,S^idj)=H.TrapEval(td^,K^,idj). Then, the challenger proceeds the following steps: AbortCheck: in the setup phase, the challenger generates a pair of (K′,td). If τ(td,K′,I∗)=1, the challenger aborts the game and sets coin^←${0,1} ignoring the output of A. Otherwise, the following equation holds:(5)H.TrapEvaltd,K′,id=ARid∗′ifid=id∗ARid′+Sid′Gotherwise.ArtificialAbort: Fix I∗; let p be the probability p=Pr[τ(td^,K^,I∗)=0] over the random choice of (td^,K^). Then, the challenger samples O(ϵ2log⁡ϵ-1δ-1log⁡(δ-1)) times the probability p by independently running (K^,td^)←H.TrapGen(A,G) and evaluating τ(td^,K^,I∗) to compute an estimate p′. Then if p′≥δ, the challenger will abort with probability (p′-δ)/p′ and sets coin^←${0,1} ignoring the output of A.
Finally, when receivingcoin′ from A, the challenger sets coin^=coin′.
Fori∈{2,3,4,5,6,7}, let p~i be the probability that the challenger does not abort in the abort check stage in Gamei, and let pi be the probability in the artificial abort stage of Gamei defined by pi=Pr[τ(td^,K^,I∗)=0]. Since the adversary might obtain some information of td from the challenge ciphertext, the probability p~i might not be equal to the probability pi. Formally, let Γi be the absolute difference between p~i and pi (i.e., Γi=p~i-pi). As we show in Lemma 8, we have(6)PrX2-12≥12ϵδ-Γ2.So as not to interrupt the proof of Theorem 5, we intentionally skip the proof for the time being.
G a m e 3: this game is identical to Game2 except that the challenger changes setup, phases 1 and 2, and challenge phase as below.Setup. It first selects a random matrix A←$Zqn×m¯. Then, it computes (K′,td)←H.TrapGen(A,G). Finally, it outputs mpk=(A,K′) and keeps the trapdoor td private.Phase1. When receiving the private key query with identity id, the challenger first computes Rid′,Sid′=H.TrapEvaltd,K′,id. If Sid′ is not invertible, the challenger aborts the game and sets coin^←$0,1. Otherwise, it computes skid=SampleBasisRightA,G,Rid′,Sid′,TG,σ and sends skid to A.ChallengePhase. The challenger computes (Rid∗′,Sid∗′)=H.TrapEval(td,K′,id∗). If Sid∗≠0, the challenger aborts the game and sets coin^←${0,1}. Otherwise, when coin=0, we have (7)c^=Fid∗⊤m=A⊤mRid∗′⊤A⊤m∈Zqm′.Then, the challenger computesc0∗=c^p. Finally, the challenger returns  ccoin∗,hm to the adversary A.Phase2. The challenger responds as in Phase1, when receiving the private key query with identity id≠id∗.
It is easy to see that(8)Pr⁡X3=Pr⁡X2andPrΓ3=PrΓ2.
G a m e 4: in this game, the challenger changes the way that the challenge ciphertext is created when coin=0.ChallengePhase. The challenger computes (Rid∗′,Sid∗′)=H.TrapEval(td,K′,id∗). If Sid∗≠0, the challenger aborts the game and sets coin^←${0,1}. Otherwise, when  coin=0, the challenger first picks m←$Ztn and chooses e1←$DZm¯,θ′q,e2←$DZm,θ′q and computes(9)c^=c^1+c^2=A⊤mRid∗′⊤A⊤m+e1e2=A⊤m+e1Rid∗′⊤A⊤m+e2.Then, the challenger computesc0∗=c^p. Finally, the challenger returns (ccoin∗,h(m)) to the adversary A.
Before analyzing the difference betweenGame3 and Game4, we first define a “bad event” as follows: Bad4=△c^1+[-B,B]m′p≠c^1p, where B=θ′qn.
IfBad4 does not occur for some c^1, then we have (10)c^p=A⊤m+e1pRid∗′⊤A⊤m+e2p=A⊤mpRid∗′⊤A⊤mp=Fid∗⊤mp.
It immediately follows that for any adversaryA(11)Pr⁡X4-Pr⁡X3≤Pr⁡Bad4andPrΓ4-PrΓ3≤PrBad4.
G a m e 5: in this game, the challenger changes the way that the challenge ciphertext is created when coin=0ChallengePhase. The challenger computes (Rid∗′,Sid∗′)=H.TrapEval(td,K′,id∗). If Sid∗′≠0, the challenger aborts the game and sets coin^←${0,1}. Otherwise, when coin=0, the challenger first picks m←$Ztn and e←$DZm¯,θq and computes b=A⊤m+e. It runs the algorithm ReRand to get c^; i.e.,(12)c^=ReRandIm¯Rid∗′⊤,b,θq,θ′q2θqin the LemmaA.3, where  Im¯  is the unit matrix of size m¯×m¯.According to the property of the algorithmReRand, we have(13)Pr⁡X5=Pr⁡X4andPrΓ5=Pr⁡Γ4andPrBad5=PrBad4.
G a m e 6: in this game, the challenger changes the way that the challenge ciphertext is created when coin=0.ChallengePhase. The challenger computes (Rid∗′,Sid∗′)=H.TrapEval(td,K′,id∗). If Sid∗′≠0, the challenger aborts the game and sets coin^←${0,1}. Otherwise, when coin=0, the challenger first picks v←$Zqm¯,e←$DZm¯,θq and sets b=v+e. Then, it computes(14)c^=ReRandIm¯Rid∗′⊤,b,θq,θ′q2θq∈Zqm′. We construct an algorithm B against the problem DLWEq,n,m¯,θ,H as follows. Given the problem instance of LWE (A,b=v+e)∈Zqn×m¯×Zqm¯, where e←$DZm¯,θq. The task of B is to distinguish whether v=A⊤m for m←$Ztn or v←$Zqm¯. This subtle change from the standard DLWEq,n,m¯,θ,H is done only for convenience of the proof. B simulates the security game for the adversary A. If v=A⊤m, the view of A corresponds to Game5; otherwise, the view of A corresponds to Game6. As a result, we get that(15)PrX6-PrX5≤DLWEq,n,m¯,θ,H,PrΓ6-PrΓ5≤DLWEq,n,m¯,θ,H,PrBad6-PrBad5≤DLWEq,n,m¯,θ,H.
G a m e 7: in this game, the challenger changes the way that the challenge ciphertext is created when coin=0.ChallengePhase. The challenger computes (Rid∗′,Sid∗′)=H.TrapEval(td,K′,id∗). If Sid∗′≠0, the challenger aborts the game and sets coin^←${0,1}. Otherwise, when coin=0, the challenger computes(16)c^=c^1+c^2=vRid∗′⊤v+e1e2=v+e1Rid∗′⊤v+e2,instead of running the algorithmReRand, where e1←$DZm¯,θ′q, e2←$DZm,θ′q, v←$Zqm¯.
According to the property of the algorithmReRand, we have(17)Pr⁡X7=Pr⁡X6andPrΓ7=Pr⁡Γ6andPrBad7=PrBad6.Because for id∗∈ID the statistical distance between (A,K′,v,(Rid∗′)⊤v) and (A,K′,v,u) is negligible in λ, where u←$Zqm, c^1 is statistically close to uniform distribution over Zqm′, therefore for uniform c^1,(18)PrBad7≤2m2B+1pq=neglλ,by assumption on q and θ′. In the meantime, because c^ is statistically close to uniform distribution over Zqm′, we can get that(19)Pr⁡X7=12andPrΓ7=0.Summing up (6), (8), (11), (13), (15), (17), (18), and (19), we can get(20)DLWEq,n,m¯,θ,H≥ϵδ6-neglλ.In order to prove Theorem5, we should prove that (6) holds. We will use Lemma 28 in the full version of the work [5], which is described as follows.Lemma 7 (see [5]).
LetI∗ be a (Q+1)-ID tuple {id∗,{idj}j∈[Q]} denoting the challenge ID along with the queried IDs, and η(I∗) define the probability that an abort does not happen in Game2. Let ηmax=maxη(I∗) and ηmin=minη(I∗). For i=1,2, we set Xi as the event that coin^=coin at the end of Gamei. Then,(21)PrX2-12≥ηminPr⁡X1-12-12ηmax-ηmin.Lemma 8.
IfH is a (1,v,β,γ,δ)-LPHF with high min-entropy and Q≤v, then Pr[X2]-1/2≥1/2ϵδ-Γ2.Proof.
According to Lemma7, we only need to compute ηmax, ηmin,  and  ηmax-ηmin. By the definition of p~2 and p2 in Game2, we have η(I∗)=p~2(δ/p′), where p′ is an estimate of p2. Since the challenger always samples O(ϵ-2log⁡ϵ-1δ-1log⁡(δ-1)) times the probability p2 to compute p′, according to the Chernoff bounds, we have Pr[p′>p2(1+ϵ/8)]<δ(ϵ/8) and Pr[p′<p2(1-ϵ/8)]<δ(ϵ/8). As a result, the following equations hold:(22)ηmax≤1-δϵ8p~2δp21-ϵ/8,ηmin≥1-δϵ8p~2δp21+ϵ/8≥7δp~29p2,ηmax-ηmin≤1-δϵ8ϵδp~241-ϵ2/64p2≤16ϵδp~263p2.Finally, we have Pr[X2]-1/2≥7δp~2/9p2·ϵ-1/2·16ϵδp~2/63p2≥ϵδp2-Γ2/2p2≥(1/2)ϵ(δ-Γ2).


## 4. Constructions of LPHFs with High Min-Entropy

In [4], Zhang et al. proved that the IBE schemes in [4–6] imply instantiations of LPHFs with high min-entropy. In fact, the IBE scheme in [10] also implies an instantiation of LPHF with high min-entropy.In this section, we show that LPHFs with high min-entropy can be constructed from partitioning functions with compatible algorithms [7]. Moreover, we prove that the adaptively secure and anonymous IBE schemes in [8, 9] naturally imply instantiations of LPHFs with high min-entropy. In a word, the adaptively secure and anonymous IBE schemes in [4–10] naturally imply instantiations of LPHFs with high min-entropy.


### 4.1. From Partitioning Functions with Compatible Algorithms [7]

LetFPF:KPF×ID→{0,1} be a partitioning function with associating δPF-compatible algorithms (Encode,PubEval,TrapEval) (see the Appendix). We assume ID={0,1}l. Now, we show how to construct a (1,v,β,γ,δ)-LPHF with high min-entropy defined by us from the partitioning function FPF:KPF×ID→{0,1}.A hash functionH:ID→Zqn×m consists of two algorithms (H.Gen,H.Eval) which are defined as follows:(i)
H.Gen(1λ)→Klphf: it first computes KPF←$PrtSmp(1λ,Q,ϵ). Then, it gets k∈{0,1}u by operating the algorithm Encode(KPF). Finally, it randomly chooses matrices B1,…,Bu←$Zqn×m, B←$Zqn×m, and returns these u+1 matrices; i.e., Klphf≔{B1,…,Bu,B}.(ii)
H.Eval(Klphf,id∈ID)→Z∈Zqn×m: for id∈ID, it first gets Bid by running the algorithm PubEval(id∈ID,{Bi∈Zqn×m}i∈[u]). Then, it returns Z=B+Bid.The associating algorithmsH.TrapGen and H.TrapEval are defined as follows.(i)
H.TrapGen(1λ,A,G)→(Klphf′,td): it first computes KPF←$PrtSmp(1λ,Q,ϵ). Then, it gets k∈{0,1}u by operating the algorithm Encode(KPF). Finally, it randomly chooses matrices R1,…,Ru,R←${-1,1}m×m and returns Klphf′≔{AR1+k1G,…,ARu+kuG,AR} and td={KPF,R1,…,Ru,R}.(ii)
H.TrapEval(td,Klphf′,id∈ID)→(Rid′∈Zqm×m,Sid′∈Zqn×n): for id∈ID, it defines Rid′=R+TrapEval(KPF,id,A,{Ri}i∈[u]) and SX′=FPF(KPF,id)·In, where In denotes the identity matrix of n×n. In this case, s1(Rid′)≤m·2m·R+TrapEval(KPF,id,A,{Ri}i∈[u])∞≤2m·(1+δPF).Now, we show that this construction satisfies the following properties:(i)
Correctness:H.Eval(Klphf′,id)=B+PubEval(id,{ARi+kiG}i∈[u])=AR+(A·TrapEval(K,id,A,{Ri}i∈[u])+FPF(KPF,id)·G)=ARid′+Sid′G.(ii)
Statistically close trapdoor keys: according to the Leftover Hash Lemma, the statistical distance between the distributions{A,B1,…,Bu,B} and {A,AR1+k1G,…,ARu+kuG,AR} is negligible. As a result, the statistical distance between {A,Klphf} and {A,Klphf′} is negligible; i.e., γ=negl(λ).(iii)
Well-distributed hidden matrices: for all(KLPHF′,td)←H.TrapGen(1λ,A,G), any inputs id∗,id1,…,idv such that id∗≠idj for any j∈[v]. Then, (23)PrSid∗′=0∧Sid1′,…,Sidv′∈In=PrFPFKPF,id∗=0∧FPFKPF,id1=⋯=FPFKPF,idv=1≥γminλ.In a word, this construction is(1,v,2m·(1+δPF),negl(λ),γmin(λ))-LPHF. Finally, we show that this LPHF possesses Property 1, i.e., with high min-entropy.(i)
For any(Klphf′,td)←H.TrapGen(1λ,A,G), any id∈ID, and its corresponding (Rid′,Sid′)=H.TrapEval(td,Klphf′,id), the following distributions are statistically close: (24)A,Klphf′,v,Rid′⊤v=A,AR,ARi+kiG,v,R+TrapEvalK,id,A,Rii∈u⊤v≈A,U,ARi+kiG,v,u≈A,Klphf′,v,u,whereU←$Zqn×m,u←$Zqm,v←$Zqm. It can been seen that the second and the third distributions are negl(λ)-close, by applying Leftover Hash Lemma for A∣v⊤∈Zqn+1×m and R.In [7], Yamada elaborately constructed two partitioning functions FMAH based on modified admissible hash function [16] and FAFF based on affine function. As a result, we can get two LPHFs with high min-entropy from both FMAH and FAFF, which are denoted by HMAH and HAFF, respectively.


### 4.2. From Yam16 [8] and KY16 [9]

In [8], Yamada proposed an adaptively secure and anonymous IBE with asymptotically short parameters. In particular, the master public key consists of O(l1/2) basic matrices. In this part, we show that their construction implies a LPHF with high min-entropy. For simplicity, we denotes it by HYam16:ID→Z∈Zqn×m, where ID={0,1}l. In their construction, there exists an efficiently computable injective map S that maps an element id∈ID to a subset S(id) of [1,t]2, where t=⌈l⌉. The algorithms (HYam16.Gen,HYam16.Eval) are defined as below.(i)
HYam16.Gen(1λ)→K: it picks random matrices B0←$Zqn×m,Bi,j←$Zqn×m for (i,j)∈[2]×[t] and returns K=(B0,{Bi,j}(i,j)∈[2]×[t]).(ii)
HYam16.Eval(K,id)→Z∈Zqn×m: for all id∈ID, the algorithm HYam16.Eval is defined as follows:(25)HYam16.EvalK,id=B0+∑j1,j2∈SidB1,j1·G-1B2,j2∈Zqn×m.The associating algorithmsHYam16.TrapGen and HYam16.TrapEval are defined as(i)
HYam16.TrapGen(1λ,A,G)→(K′,td): it first selects random elements y0←$[-4(l+1)n2c+1,0] and yi,j←$[1,2nc], where c=c1+c2 and c1,c2 satisfy that nc1/2≥Q+1 and n-c2≤ϵ. Then, it randomly chooses matrices R0,Ri,j←${-1,1}m×m. Finally, it computes B0=AR0+y0G and Bi,j=ARi,j+yi,jG  returns K′={B0,Bi,j} and td={y0,yi,j,R0,Ri,j}.(ii)
HYam16.TrapEval(td,K′,id)→(Rid′∈Zqm×m,Sid′∈Zqn×n): for id∈ID, (26)Rid′=R0+∑j1,j2∈SidR1,j1G-1B2,j2+y1,j1R2,j2,Sid′=y0+∑j1,j2∈Sidy1,j1·y1,j2·In.In this case,s1(Rid′)≤m(1+4lnc).Now, we show that this construction satisfies the following properties:(i)
Correctness: it is easy to verify thatH.Eval(K′,id)=ARid′+Sid′G.(ii)
Statistically close trapdoor keys: according to the Leftover Hash Lemma, the statistical distance between the distributions(A,B,{Bi,j}(i,j)∈[2]×[t]) and (A,AR0+y0G,{ARi,j+yi,jG}(i,j)∈[2]×[t]) is negligible.(iii)
Well-distributed hidden matrices: for all(K′,td)←H.TrapGen(1λ,A,G), any inputs id∗,id1,…,idv such that id∗≠idj for any j∈[v]. Then, (27)PrSid∗′=0∧Sid1′,…,Sidv′∈In=PrFyid∗=0∧Fyid1≠0⋯=Fyidv≠0≥ϵ232l+1Q2,whereFy(id)=y0+∑(j1,j2)∈S(id)y1,j1·y1,j2.In a word, this construction is(1,v,m(1+4lnc),negl(λ),ϵ2/32(l+1)Q2)-LPHF. Then, we show that HYam16 is a LPHF which possesses Property 1, i.e., with high min-entropy.(i)
Property1. For any (K′,td)←HYam16.TrapGen(1λ,A,G), any id∈ID and its corresponding (Rid′,Sid′)=HYam16.TrapEval(td,K′,id), the following distributions are statistically close: (28)A,K′,v,Rid′⊤v=A,AR0+y0G,ARi,j+yi,jG,v,R0+R′⊤v≈A,U,ARi,j+yi,jG,v,u≈A,K′,v,u,whereR′=∑(j1,j2)∈S(id)R1,j1G-1(B2,j2)+y1,j1R2,j2, U←$Zqn×m, u←$Zqm, v←$Zqm. The second and the third distributions are negl(λ)-close, by applying the Leftover Hash Lemma for A⊤∣v∈Zqn+1×m and R0.Remark 9.
The subsequent work by Katsumata and Yamada [9] showed that, for the ring version of Yamada’s scheme [8], it is possible to reduce the magnitude of s1(Rid′) (which influences the selection of modulus q). We do not see any obstacle preventing us from constructing a programmable hash function with high min entropy from ideal lattices, according to the IBE scheme of [9].


## 4.1. From Partitioning Functions with Compatible Algorithms [7]

LetFPF:KPF×ID→{0,1} be a partitioning function with associating δPF-compatible algorithms (Encode,PubEval,TrapEval) (see the Appendix). We assume ID={0,1}l. Now, we show how to construct a (1,v,β,γ,δ)-LPHF with high min-entropy defined by us from the partitioning function FPF:KPF×ID→{0,1}.A hash functionH:ID→Zqn×m consists of two algorithms (H.Gen,H.Eval) which are defined as follows:(i)
H.Gen(1λ)→Klphf: it first computes KPF←$PrtSmp(1λ,Q,ϵ). Then, it gets k∈{0,1}u by operating the algorithm Encode(KPF). Finally, it randomly chooses matrices B1,…,Bu←$Zqn×m, B←$Zqn×m, and returns these u+1 matrices; i.e., Klphf≔{B1,…,Bu,B}.(ii)
H.Eval(Klphf,id∈ID)→Z∈Zqn×m: for id∈ID, it first gets Bid by running the algorithm PubEval(id∈ID,{Bi∈Zqn×m}i∈[u]). Then, it returns Z=B+Bid.The associating algorithmsH.TrapGen and H.TrapEval are defined as follows.(i)
H.TrapGen(1λ,A,G)→(Klphf′,td): it first computes KPF←$PrtSmp(1λ,Q,ϵ). Then, it gets k∈{0,1}u by operating the algorithm Encode(KPF). Finally, it randomly chooses matrices R1,…,Ru,R←${-1,1}m×m and returns Klphf′≔{AR1+k1G,…,ARu+kuG,AR} and td={KPF,R1,…,Ru,R}.(ii)
H.TrapEval(td,Klphf′,id∈ID)→(Rid′∈Zqm×m,Sid′∈Zqn×n): for id∈ID, it defines Rid′=R+TrapEval(KPF,id,A,{Ri}i∈[u]) and SX′=FPF(KPF,id)·In, where In denotes the identity matrix of n×n. In this case, s1(Rid′)≤m·2m·R+TrapEval(KPF,id,A,{Ri}i∈[u])∞≤2m·(1+δPF).Now, we show that this construction satisfies the following properties:(i)
Correctness:H.Eval(Klphf′,id)=B+PubEval(id,{ARi+kiG}i∈[u])=AR+(A·TrapEval(K,id,A,{Ri}i∈[u])+FPF(KPF,id)·G)=ARid′+Sid′G.(ii)
Statistically close trapdoor keys: according to the Leftover Hash Lemma, the statistical distance between the distributions{A,B1,…,Bu,B} and {A,AR1+k1G,…,ARu+kuG,AR} is negligible. As a result, the statistical distance between {A,Klphf} and {A,Klphf′} is negligible; i.e., γ=negl(λ).(iii)
Well-distributed hidden matrices: for all(KLPHF′,td)←H.TrapGen(1λ,A,G), any inputs id∗,id1,…,idv such that id∗≠idj for any j∈[v]. Then, (23)PrSid∗′=0∧Sid1′,…,Sidv′∈In=PrFPFKPF,id∗=0∧FPFKPF,id1=⋯=FPFKPF,idv=1≥γminλ.In a word, this construction is(1,v,2m·(1+δPF),negl(λ),γmin(λ))-LPHF. Finally, we show that this LPHF possesses Property 1, i.e., with high min-entropy.(i)
For any(Klphf′,td)←H.TrapGen(1λ,A,G), any id∈ID, and its corresponding (Rid′,Sid′)=H.TrapEval(td,Klphf′,id), the following distributions are statistically close: (24)A,Klphf′,v,Rid′⊤v=A,AR,ARi+kiG,v,R+TrapEvalK,id,A,Rii∈u⊤v≈A,U,ARi+kiG,v,u≈A,Klphf′,v,u,whereU←$Zqn×m,u←$Zqm,v←$Zqm. It can been seen that the second and the third distributions are negl(λ)-close, by applying Leftover Hash Lemma for A∣v⊤∈Zqn+1×m and R.In [7], Yamada elaborately constructed two partitioning functions FMAH based on modified admissible hash function [16] and FAFF based on affine function. As a result, we can get two LPHFs with high min-entropy from both FMAH and FAFF, which are denoted by HMAH and HAFF, respectively.


## 4.2. From Yam16 [8] and KY16 [9]

In [8], Yamada proposed an adaptively secure and anonymous IBE with asymptotically short parameters. In particular, the master public key consists of O(l1/2) basic matrices. In this part, we show that their construction implies a LPHF with high min-entropy. For simplicity, we denotes it by HYam16:ID→Z∈Zqn×m, where ID={0,1}l. In their construction, there exists an efficiently computable injective map S that maps an element id∈ID to a subset S(id) of [1,t]2, where t=⌈l⌉. The algorithms (HYam16.Gen,HYam16.Eval) are defined as below.(i)
HYam16.Gen(1λ)→K: it picks random matrices B0←$Zqn×m,Bi,j←$Zqn×m for (i,j)∈[2]×[t] and returns K=(B0,{Bi,j}(i,j)∈[2]×[t]).(ii)
HYam16.Eval(K,id)→Z∈Zqn×m: for all id∈ID, the algorithm HYam16.Eval is defined as follows:(25)HYam16.EvalK,id=B0+∑j1,j2∈SidB1,j1·G-1B2,j2∈Zqn×m.The associating algorithmsHYam16.TrapGen and HYam16.TrapEval are defined as(i)
HYam16.TrapGen(1λ,A,G)→(K′,td): it first selects random elements y0←$[-4(l+1)n2c+1,0] and yi,j←$[1,2nc], where c=c1+c2 and c1,c2 satisfy that nc1/2≥Q+1 and n-c2≤ϵ. Then, it randomly chooses matrices R0,Ri,j←${-1,1}m×m. Finally, it computes B0=AR0+y0G and Bi,j=ARi,j+yi,jG  returns K′={B0,Bi,j} and td={y0,yi,j,R0,Ri,j}.(ii)
HYam16.TrapEval(td,K′,id)→(Rid′∈Zqm×m,Sid′∈Zqn×n): for id∈ID, (26)Rid′=R0+∑j1,j2∈SidR1,j1G-1B2,j2+y1,j1R2,j2,Sid′=y0+∑j1,j2∈Sidy1,j1·y1,j2·In.In this case,s1(Rid′)≤m(1+4lnc).Now, we show that this construction satisfies the following properties:(i)
Correctness: it is easy to verify thatH.Eval(K′,id)=ARid′+Sid′G.(ii)
Statistically close trapdoor keys: according to the Leftover Hash Lemma, the statistical distance between the distributions(A,B,{Bi,j}(i,j)∈[2]×[t]) and (A,AR0+y0G,{ARi,j+yi,jG}(i,j)∈[2]×[t]) is negligible.(iii)
Well-distributed hidden matrices: for all(K′,td)←H.TrapGen(1λ,A,G), any inputs id∗,id1,…,idv such that id∗≠idj for any j∈[v]. Then, (27)PrSid∗′=0∧Sid1′,…,Sidv′∈In=PrFyid∗=0∧Fyid1≠0⋯=Fyidv≠0≥ϵ232l+1Q2,whereFy(id)=y0+∑(j1,j2)∈S(id)y1,j1·y1,j2.In a word, this construction is(1,v,m(1+4lnc),negl(λ),ϵ2/32(l+1)Q2)-LPHF. Then, we show that HYam16 is a LPHF which possesses Property 1, i.e., with high min-entropy.(i)
Property1. For any (K′,td)←HYam16.TrapGen(1λ,A,G), any id∈ID and its corresponding (Rid′,Sid′)=HYam16.TrapEval(td,K′,id), the following distributions are statistically close: (28)A,K′,v,Rid′⊤v=A,AR0+y0G,ARi,j+yi,jG,v,R0+R′⊤v≈A,U,ARi,j+yi,jG,v,u≈A,K′,v,u,whereR′=∑(j1,j2)∈S(id)R1,j1G-1(B2,j2)+y1,j1R2,j2, U←$Zqn×m, u←$Zqm, v←$Zqm. The second and the third distributions are negl(λ)-close, by applying the Leftover Hash Lemma for A⊤∣v∈Zqn+1×m and R0.Remark 9.
The subsequent work by Katsumata and Yamada [9] showed that, for the ring version of Yamada’s scheme [8], it is possible to reduce the magnitude of s1(Rid′) (which influences the selection of modulus q). We do not see any obstacle preventing us from constructing a programmable hash function with high min entropy from ideal lattices, according to the IBE scheme of [9].


## 5. Instantiations of Generic DIBE Construction

As mentioned in Section4, there are many LPHFs with high min-entropy in [4–10]. However, except the LPHF with high min-entropy used in [3], there only exist other four (1,v,β,γ,δ) LPHFs with high min-entropy which satisfy the requirement that δ is independent of the modulus q, under the LWE assumption. These four LPHFs with high min-entropy are briefly described in the following.(i)
HZCZ16 in ZCZ16 [4]: a (1,v,μvlm¯1.5·ω(logm¯),negl(λ),1/N) LPHF with high min-entropy, where N≤16v2l and μ=⌈log⁡N⌉. Additionally, the key of HZCZ16 only consists of μ=⌈log⁡N⌉ matrices.(ii)
HMAH in Yam17 [7]: a (1,v,m¯4u(l+1),negl(λ),O(ϵφ/Qφ)) LPHF with high min-entropy, where u=ω(log2λ), v is an arbitrary polynomial in λ and φ>1 is the constant satisfying s=1-2-1/φ, where s∈{0,1} is the relative distance of the underlying error correcting code. We can take φ as close to 1 as one wants. In addition, the key of HMAH only consists of u=ω(log2λ) matrices.(iii)
HAFF in Yam17 [7]: a (1,v,poly(λ),negl(λ),O(ϵ/l2Q)) LPHF with high min-entropy, where v is an arbitrary polynomial in λ. Furthermore, the key of HAFF only consists of ω(log⁡λ) matrices.(iv)
HYam16 in Yam16 [8] (our Section 4.2): a (1,v,m¯(1+4lnc),negl(λ),ϵ2/32(l+1)Q2) LPHF with high min-entropy, where v is an arbitrary polynomial in λ,c=c1+c2 and c1, c2 satisfy that nc1/2≥Q+1 and n-c2≤ϵ. Moreover, the key of HYam16 only consists of λ matrices.Embedding these four LPHFs with high min-entropy into our generic DIBE construction, we can obtain fourPRIV1-ID-INDr-secure DIBE schemes in the auxiliary-input setting, under the lWE assumption. Please see more details in Table 3.Table 3
Four Adaptively Secure DIBE Schemes in the Auxiliary-Input Setting.
Schemes # of Zqn×m matrix|mpk| RoundingParameterp MessageSpacet SampleWidthσ ReductionCost D I B E M A H ω ( l o g 2  λ ) O ~ ( n 6.5 + 5.5 η ) O ~ ( n 6 + 5 η ) O ~ ( n 5 + 4 η ) O ϵ φ + 1 Q φ †   DIBEAFF ω ( log ⁡ λ ) p o l y ( n ) p o l y ( n ) p o l y ( n ) O ϵ 2 l 2 Q   D I B E Z C Z 16 O ( log ⁡ Q ) O ~ ( n c + 4 + 3 η ) O ~ ( n c + 3.5 + 2.5 η ) O ~ ( n c + 2.5 + 1.5 η ) ‡ O ϵ l Q 2   DIBEYam16 λ O ~ ( n c + 3.5 + 2.5 η ) O ~ ( n c + 3 + 2 η ) O ~ ( n c + 2 + η ) § O ϵ 3 l Q 2 | m p k | , | c t | show the size of the master public keys and ciphertexts, respectively. Q and ϵ denote the number of key extraction queries and the advantage, respectively. poly(n) represents a fixed but large polynomial that does not depend Q and ϵ. To measure the reduction cost, we show the advantage of the LWE algorithm constructed from the adversary against the corresponding DIBE scheme. †  φ>1 is the constant satisfying s=1-2-1/φ, where s∈{0,1} is the relative distance of the underlying error correcting code. We can take φ as close to 1 as one wants. ‡  c is the smallest integer satisfying that nc≥Q+1. §   c = c 1 + c 2 and c1,c2 are the smallest integers satisfying that nc1/2≥Q+1 and n-c2≤ϵ.



---

*Source: 1816393-2019-01-13.xml*