# Provably Secure Identity-Based Encryption and Signature over Cyclotomic Fields

Authors: Yang Wang; Mingqiang Wang; Jingdan Zou; Jin Xu; Jing Wang
Journal: Wireless Communications and Mobile Computing
 (2019)

---

## Abstract

Identity-based cryptography is a type of public key cryptography with simple key management procedures. To our knowledge, till now, the existing identity-based cryptography based on NTRU is all over power-of-2 cyclotomic rings. Whether there is provably secure identity-based cryptography over more general fields is still open. In this paper, with the help of the results of collision resistance preimage sampleable functions (CRPSF) over cyclotomic fields, we give concrete constructions of provably secure identity-based encryption schemes (IBE) and identity-based signature schemes (IBS) based on NTRU over any cyclotomic field. Our IBE schemes are provably secure under adaptive chosen-plaintext and adaptive chosen-identity attacks, meanwhile, our IBS schemes are existentially unforgeable against adaptively chosen message and adaptively chosen identity attacks for any probabilistic polynomial time (PPT) adversary in the random oracle model. The securities of both schemes are based on the worst-case approximate shortest independent vectors problem (SIVPγ) over corresponding ideal lattices. The secret key size of our IBE (IBS) scheme is short—only one (two) ring element(s). The ciphertext (signature) is also short—only two (three) ring elements. Meanwhile, as the case of NTRUEncrypt, our IBE scheme could encrypt n bits in each encryption process. These properties may make our schemes have more advantages for some IoT applications over postquantum world in theory.


---

## Body

## 1. Introduction

Nowadays, Internet of things (IoT) plays an extremely important role by comprising millions of smart and connected devices to offer benefits in a wide range of situations, for example, smart cities, smart grads, smart traffic, and smart buildings. The corresponding techniques have been unprecedentedly developed and adopted due to the quick evolution of smart devices and the continuous investment of leading communities. In a smart IoT system, data collected by mote devices will be transferred to gateway/cloud; the cloud will perform data analysis and send the results to the particular management system which takes suitable action. How to protect this complete network against malicious events, as well as the privacy and authenticity of data, is one of the toughest challenges for the deploying IoT technology. Several considerations and solutions are discussed in [1–4]. Due to the constrained resources (i.e., the size of memory, CPU speed, and network bandwidth), we could not directly use the traditional public key system, since the key management is complicated and the computations and storages may consume large amount of resources.Identity-based cryptography is a type of public key cryptography in which the public key of a user is some unique information about the identity of the user (e.g., a user’s e-mail address and the MAC address of devices). This means that a sender who has access to the public parameters of the system can encrypt a message (verify a signature) by using the receiver’s (signer’s) identity as a public key. The receiver (signer) obtains its decryption (signing) key from a central authority, which needs to be trusted as it generates secret keys for every user. Such cryptographic primitives significantly simplify the key management procedures of certificated-based public key infrastructures.IBE and IBS were proposed by Shamir [5]; from then on, a large number of papers have been published in this area, including IBE [6–12], IBS [13–17], and identity-based signcryption (sign-then-encrypt a message) schemes [13, 18, 19]. Till now, the fully practical identity-based cryptographic primitives are based on bilinear pairings. With the rapid development of quantum computation, in a not-so-distant future, quantum computers are expected to break such systems, and it is urgent to design quantum-immune IBE and IBS schemes. Cryptographic primitives based on hard lattice problems are good candidates, and many such identity-based schemes were designed [6, 9, 10, 16]. However, the efficiency of these schemes is not very satisfactory, especially in the IoT applications. As we all know, cryptographic primitives based on NTRU usually have high efficiency [20] and are good candidates of lightweight cryptographic systems in the postquantum world. Therefore, IBE and IBS schemes based on NTRU may enjoy the advantages of high efficiency and quantum-immune at the same time.To the best of our knowledge, the existing IBE [21] and IBS [17] based on NTRU are all over power-of-2 cyclotomic rings, in which NTT algorithm can be implemented and calculations can be done very fast. However, there are too many subfields in the corresponding cyclotomic fields, making these settings more sensitive to subfield attacks [22, 23, 24]. So, seeking constructions of IBE and IBS over more general fields is a meaningful work. Meanwhile, strictly speaking, both of the schemes [17, 21] lack a security proof in the following two senses: (1) The PPT key generation algorithm [21] is heuristic and the CPA security of the schemes is guaranteed by a key-encapsulation mechanism designed in the process of encryption and is measured by the Kullback–Leibler “distance”—not statistical distance. Then, security is estimated in the aspect of attacks. So, the magnitude of module q is small and the schemes are practical. (2) Parameter settings of IBS [17] were referred to [25]; while the main lemma for proving the PPT trapdoor generation algorithm of CRPSF in [25] had some deficiencies, making the parameter choices in [17] could not achieve the desired result.


### 1.1. Our Contributions and Technique Overview

Motivated by the above reasons, we construct provably secure IBE and IBS schemes over any cyclotomic field.Compared with [21], our IBE scheme is strictly provably secure under adaptive chosen-plaintext and adaptive chosen-identity attacks. So, at a high level, our result implies that we can heuristically design IBE scheme by using similar parameters as [21] in any cyclotomic field. Since we use the modified algorithms of CRPSF proposed in [26], our IBS scheme is existentially unforgeable against adaptively chosen message and adaptively chosen identity attacks in theory. Though the efficiency of our IBE and IBS schemes may be not satisfactory when we set parameters to achieve the provably security, our results give a high-level implication that we can heuristically design IBE and IBS over any cyclotomic field with small parameters (for example, settings of the classical NTRU-based cryptography [20]) and construct a lightweight cryptosystem, which can be used in some IoT applications.Next, we give a brief review of constructions.The construction of our IBE scheme is inspired by [21] and followed the route of [10]. The setup algorithm uses the key generation algorithm of CRPSF constructed in [26] to generate some public parameters PP, including a cyclotomic field K and an element h∈Rq×. Here, R=OK is the ring of integers of K and Rq× is the set of invertible elements of Rq=R/qR. Meanwhile, the key generation algorithm of CRPSF also outputs a short trapdoor basis of the NTRU lattice Λhq=x,y∈R2:y=hxmodqR. The secret key of an identity (we map an identity to Rq by using a random oracle H:0,1∗↦Rq) is the element in Λhq outputted by the SamplePre algorithm of CRPSF by using the trapdoor basis. The encryption and decryption follow the idea of [10]. We embed the message in a Ring-LWE instance in the encryption process and the outputted ciphertext consists of two Ring-LWE instances (only the b-component) (u, v) with the “implied” relation that v−u⋅sk is short. Then, the decryption process only need to remove the errors by rounding ⋅. Security (indistinguishability) is based on the hardness of corresponding decision Ring-LWE problems, and we do not need to use the key-encapsulation mechanism in the encryption process.The construction of IBS follows the route of [17], which is a combination of techniques shown in [10, 27]. We also use the key generation algorithm of CRPSF to generate Msk. The secret key σ1,σ2 of an identity id is produced by the SamplePre algorithm of CRPSF, satisfying hσ1−σ2=Hid. The signing and verification follow the idea of [27] by using a rejection sampling algorithm. The signature of a message μ contains a triple z1,z2,u with yi↩DR,s, zi=yi+σi⋅u, and u=H′hy1−y2modqR,μ. The rejection sampling algorithm could make it seem that zi is independent of yi, in particular, zi↩DR,s. Then, to verify a signature, one only needs to make sure that zi is short and u=H′hz1−z2−Hid⋅umodqR,μ. Unforgeability of our scheme can be reduced to the corresponding Ring-SIS problems.Finally, we remark that techniques used in [28] are also vital to bound the decryption error of our IBE scheme. Though we design our IBE schemes in R∨, the dual ideal of R, we can convert it to work in an integral ideal of R or we can directly design the IBE scheme in R by using the hardness result shown in [29] (with larger parameter γ and q). Also, we can discuss the practicability under the Kullback–Leibler “distance” by using the same method as in [21]. Meanwhile, our construction provides an important support for designing IBE and IBS over general cyclotomic rings with relative small parameters (with no provably secure guarantee, but the key generation algorithm is PPT by our results) and analyzing the security from the view of attacks. How to reduce the magnitudes of parameters of provably secure identity-based cryptographic primitives and improve the efficiency of these schemes are important and meaningful open problems.


### 1.2. Organization

In Section2, we will introduce some notations and basic results we need in our discussion. In Section 3, we shall discuss the IBE schemes, including the basic definitions, security models, constructions, and security analysis. Discussions of IBS schemes are put in Section 4.


## 1.1. Our Contributions and Technique Overview

Motivated by the above reasons, we construct provably secure IBE and IBS schemes over any cyclotomic field.Compared with [21], our IBE scheme is strictly provably secure under adaptive chosen-plaintext and adaptive chosen-identity attacks. So, at a high level, our result implies that we can heuristically design IBE scheme by using similar parameters as [21] in any cyclotomic field. Since we use the modified algorithms of CRPSF proposed in [26], our IBS scheme is existentially unforgeable against adaptively chosen message and adaptively chosen identity attacks in theory. Though the efficiency of our IBE and IBS schemes may be not satisfactory when we set parameters to achieve the provably security, our results give a high-level implication that we can heuristically design IBE and IBS over any cyclotomic field with small parameters (for example, settings of the classical NTRU-based cryptography [20]) and construct a lightweight cryptosystem, which can be used in some IoT applications.Next, we give a brief review of constructions.The construction of our IBE scheme is inspired by [21] and followed the route of [10]. The setup algorithm uses the key generation algorithm of CRPSF constructed in [26] to generate some public parameters PP, including a cyclotomic field K and an element h∈Rq×. Here, R=OK is the ring of integers of K and Rq× is the set of invertible elements of Rq=R/qR. Meanwhile, the key generation algorithm of CRPSF also outputs a short trapdoor basis of the NTRU lattice Λhq=x,y∈R2:y=hxmodqR. The secret key of an identity (we map an identity to Rq by using a random oracle H:0,1∗↦Rq) is the element in Λhq outputted by the SamplePre algorithm of CRPSF by using the trapdoor basis. The encryption and decryption follow the idea of [10]. We embed the message in a Ring-LWE instance in the encryption process and the outputted ciphertext consists of two Ring-LWE instances (only the b-component) (u, v) with the “implied” relation that v−u⋅sk is short. Then, the decryption process only need to remove the errors by rounding ⋅. Security (indistinguishability) is based on the hardness of corresponding decision Ring-LWE problems, and we do not need to use the key-encapsulation mechanism in the encryption process.The construction of IBS follows the route of [17], which is a combination of techniques shown in [10, 27]. We also use the key generation algorithm of CRPSF to generate Msk. The secret key σ1,σ2 of an identity id is produced by the SamplePre algorithm of CRPSF, satisfying hσ1−σ2=Hid. The signing and verification follow the idea of [27] by using a rejection sampling algorithm. The signature of a message μ contains a triple z1,z2,u with yi↩DR,s, zi=yi+σi⋅u, and u=H′hy1−y2modqR,μ. The rejection sampling algorithm could make it seem that zi is independent of yi, in particular, zi↩DR,s. Then, to verify a signature, one only needs to make sure that zi is short and u=H′hz1−z2−Hid⋅umodqR,μ. Unforgeability of our scheme can be reduced to the corresponding Ring-SIS problems.Finally, we remark that techniques used in [28] are also vital to bound the decryption error of our IBE scheme. Though we design our IBE schemes in R∨, the dual ideal of R, we can convert it to work in an integral ideal of R or we can directly design the IBE scheme in R by using the hardness result shown in [29] (with larger parameter γ and q). Also, we can discuss the practicability under the Kullback–Leibler “distance” by using the same method as in [21]. Meanwhile, our construction provides an important support for designing IBE and IBS over general cyclotomic rings with relative small parameters (with no provably secure guarantee, but the key generation algorithm is PPT by our results) and analyzing the security from the view of attacks. How to reduce the magnitudes of parameters of provably secure identity-based cryptographic primitives and improve the efficiency of these schemes are important and meaningful open problems.


## 1.2. Organization

In Section2, we will introduce some notations and basic results we need in our discussion. In Section 3, we shall discuss the IBE schemes, including the basic definitions, security models, constructions, and security analysis. Discussions of IBS schemes are put in Section 4.


## 2. Preliminaries

In this section, we introduce some background results and notations.


### 2.1. Notations

We usen to denote the set 1,2,…,n. ⋅ represents the l2 norm corresponding to the canonical embedding. For two random variables X and Y, ΔX,Y stands for their statistic distance. When we write X↩ξ, we mean that the random variable X obeys to a distribution ξ. If S is a finite set, then S is its cardinality and US is the uniform distribution over S. Symbols ℤ+ and ℝ+ stand for the sets of positive integers and positive reals. Symbol logx represents log2x for x∈ℝ+. Functions φn and μn stand for the Euler function and the Möbius function.


### 2.2. Cyclotomic Fields, SpaceH, and Ideal Lattices

Throughout this paper, we only consider cyclotomic fields. For a cyclotomic fieldK=ℚζ with ζ=ζl the primitive l-th root of unity, its minimal polynomial is Φlx=∏ilxi−1μl/i∈ℤx with degree n=φl. As usual, we set R=OK=ℤζ, which is the ring of integers of K. Then, K:ℚ=n≔2r, K≅ℚx/Φlx and R≅ℤx/Φlx. K is Galois over ℚ. We set GalK/ℚ=σi:i=1,…,n and use the canonical embedding σ on K, which maps x∈K to a space σixi∈H≔x1,…,xn∈ℂn:xn+1−i=xi¯,∀i∈r via embeddings in GalK/ℚ. H is isomorphic to ℝn as an inner product space via the orthonormal basis hi∈n defined as follows: for 1≤j≤r,(1)hj=12ej+en+1−j,hn+1−j=i2ej−en+1−j,where ej∈ℂn is the vector with 1 in its j-th coordinate and 0 elsewhere and i is the imaginary number such that i2=−1. For any element x∈K, we can define its norm by x≔σx and its infinity norm by x∞≔maxi∈nσix.We define a lattice as a discrete additive subgroup ofH. The dual lattice of Λ⊆H is defined as Λ∨=y∈H:∀x∈Λ,<x,y¯>=∑i=1nxi⋅yi∈ℤ. One can check that this definition is actually the complex conjugate of the dual lattice as usually defined in ℂn. All of the properties of the dual lattice that we use also hold for the conjugate dual. Any fractional ideal I of K is a free ℤ module of rank n. So, σI is a lattice of H, and we call σI an ideal lattice and identify I with this lattice and associate with I all the usual lattice quantities. Meanwhile, its dual is defined as I∨=a∈K:Tra⋅I⊆ℤ. Then, it is easy to verify that I∨∨=I, I∨ is a fractional ideal, and I∨ embeds under σ as the dual lattice of I as defined above.


### 2.3. Gaussian Distributions, Ring-SIS Problems, and Ring-LWE Problems

The Gaussian distribution is defined as usual. For anys>0, c∈H, which is taken to be s=1 or c=0 when omitted, define the Gaussian function ρs,c:H⟶0,1 as ρs,cx=e−πx−c2/s2. By normalizing this function, we obtain the continuous Gaussian probability distribution Ds,c of parameter s, whose density function is given by s−n⋅ρs,cx. For a real vector r=r1,…,rn∈ℝ+n, we define the elliptical Gaussian distributions in the basis hii≤n as follows: a sample from Dr is given by ∑i∈nxihi, where xi is chosen independently from the Gaussian distribution Dri over ℝ. Note that if we define a map φ:H⟶ℝn by φ∑i∈nxihi=x1,…,xn, then Dr is also a (elliptical) Gaussian distribution over ℝn.For a latticeΛ⊆H, σ>0 and c∈H, we define the lattice Gaussian distribution of support Λ, deviation σ, and center c by DΛ,σ,cx=ρσ,cx/ρσ,cΛ for any x∈Λ. For δ>0, we define the smoothing parameter ηδΛ as the smallest σ>0 such that ρ1/σΛ∨\0≤δ. The following theorem comes from [10, 30]. Here we use B˜ to represent the Gram–Schmidt orthogonalization of B and regard the columns of B as a set of vectors. For B=b1,…,bn, define B=maxibi.Theorem 1.
There is a probabilistic polynomial time algorithm that, given a basis B of an n-dimensional latticeΛ=ℒB, a standard deviation σ≥B˜⋅ωlogn, and a c∈H, outputs a sample whose distribution is statistically close to DΛ,σ,c.We will use following lemmata from [10, 31].Lemma 1.
For any full-rank latticeΛ and positive real ε>0, we have ηεΛ≤ln2n1+1/ε/π⋅λnΛ.Lemma 2.
For any full-rank latticeΛ, c∈H, ε∈0,1 and σ≥ηεΛ, we have Prb↩DΛ,σ,cb−c≥σn≤1+ε/1−ε⋅2−n.Lemma 3.
For any full-rank latticeΛ⊆H, c∈H, δ∈0,1, σ≥2ηδΛ and b∈Λ, we have DΛ,σ,cb≤1+δ/1−δ⋅2−n.The following useful rejection sampling theorem comes from [27]. We state an adapted version, corresponding to the canonical embedding and space H. Its proof is essentially the same as that in [27], so we put it in Appendix with a remark that the constant M can be effectively calculated in practice.Theorem 2.
LetΛ⊆H be an arbitrary lattice, V⊆H be a set in which all elements have norms less than T, σ be some elements in ℝ such that σ=ωT⋅logn, and h:V↦0,1 be a probability distribution. Then, there exists an absolute constant M such that the distribution of the output of the following algorithm A:(1)
v↩h(2)
z↩DΛ,σ,v(3)
Outputz,v with probability minDΛ,σz/M⋅DΛ,σ,vz,1is within statistical distance 2−ωlogn/M of the distribution of the output of the following algorithm ℱ:(1)
v↩h(2)
z↩DΛ,σ(3)
Outputz,v with probability 1/M.
Moreover, the probabilityp that A outputs something satisfies 1−2−ωlogn/M≤p≤1/M.The hard lattice problems we use are Ring-SIS and Ring-LWE problems. For an elementz=z1,…,zm∈Rm, let us define z≔∑i=1mzi21/2. We first introduce the Ring-SIS problem. The definition is as follows.Definition 1.
Let R be the ring of integers of K, q and m be positive integers, andβ be a real number. The small integer solution problem over R (R-SISq, m, β) is given a1,…,am∈Rq chosen independently from URq, find z=z1,…,zm∈Rm such that ∑i=1maizi=0modqR and 0<z≤β.For appropriate parameters, the following theorem comes from [32], which shows that the Ring-SIS problem is hard.Theorem 3.
Forε∈0,1, there is a PPT reduction from solving Ideal‐SIVPγ⋅ln2n1+1/ε/π with high probability in polynomial time in the worst case to solving R-SISq, m, β with nonnegligible probability in polynomial time, for any m,q,β,γ such that γ≥βn⋅ωlogn, q≥βn⋅ωlogn, and m,β,logq≤polyn.The Ring-LWE problem is defined as follows. LetT=H/R∨.Definition 2.
Fors∈Rq∨ and an error distribution ψ over H, the Ring-LWE distribution As,ψ∨ over Rq×T is sampled by independently choosing a uniformly random a↩URq and an error term e↩ψ and outputting a,b=a⋅s/q+emodR∨.Definition 3.
LetΨ be a family of distributions over H. The average-case Ring-LWE decision problem, denoted R-DLWEq,Ψ∨, is to distinguish (with nonnegligible advantage) between independent samples from As,ψ∨ for a random choice of s,ψ↩URq∨×Ψ and the same number of uniformly random and independent samples from Rq×T.In [33], a reduction from Ideal-SIVPγ to decision Ring-LWE problem over any algebraic number field is given.Theorem 4.
Let K be an algebraic number field andR=OK, K:ℚ=n. Assume α∈0,1 such that α≤logn/n, and let q≥2 be an integer such that αq≥ω1. Then there is a polynomial time quantum reduction from Ideal-SIVPγ (in the worst case) to R−DLWEq,Dξ∨, where ξ=αnk/lognk1/4 with k the number of samples to be used and γ=ωn⋅logn/α.We can modify the samplea,b of Ring-LWE distribution to Rq×Rq∨ as in [28]. We scale the b component by a factor of q, so that it is an element in H/qR∨. The corresponding error distribution is Dqξ with ξ=α⋅nk/lognk1/4 and k the number of samples. Then, we discretize the error, by taking e↩⌊Dqξ⌉R∨. The decision version of Ring-LWE becomes to distinguish between the modified distribution of As,⌊Dqξ⌉R∨∨ and the uniform samples from Rq×Rq∨. Notice that by using the same method proposed in [34], we can change the secret s to obey the error distributions, i.e., s↩⌊Dqξ⌉R∨. We will use the symbol R−DLWEq,⌊Dqξ⌉R∨ to denote this problem. Meanwhile, note that, if we constrain a↩UT for some T⊆Rq, where T=c⋅Rq and c≠negln, the hardness of the corresponding problem does not decrease. We will use the symbol R−DLWEq,⌊Dqξ⌉R∨× to denote this problem. For more details, one can refer to [28, 34].


### 2.4. Key Generation Algorithm and Regularity Result

In this subsection, we shall introduce some useful algorithms and results we need. The following algorithm plays a key role in our constructions of IBE and IBS. It is a modified version of key generation algorithm of traditional NTRU signatures. For simplicity, we denote it byN-KeyGen.Algorithm 1
(i)
Input: n,q∈ℤ+, σ>0.
(ii)
Output: A key pair sk,pk∈R2×2×Rq×.
(1)
Samplef from DR,σ, if fmodq∉Rq×, resample.
(2)
Sampleg from DR,σ, if gmodq∉Rq×, resample.
(3)
Iff≥nσ or g≥nσ, restart.
(4)
Iff,g≠R, restart.
(5)
ComputeFq,Gq∈R such that f⋅Gq−g⋅Fq=q, e.g., using a Hermite normal form algorithm.
(6)
Use Babai rounding nearest plane algorithm to approximateFq,Gq in the lattice spanned by f,g, let rf,g be the output, set F,G=Fq,Gq−rf,g for some r∈R.
(7)
IfF,G>nσl, restart.
(8)
Return secret keysk=fgFG and public key pk=h=g⋅f−1∈Rq×.The following theorem comes from [26] (Algorithm 1). Note that in the case of cyclotomic fields, it was shown in [26] that the value of Dedekind zeta function at 2 (i.e. ζK2) has a relatively small absolute upper bound.Theorem 5.
LetK=ℚζl be a cyclotomic field, R=OK, n=φl, q≥64nζK2 be a prime such that q∤ΔK and the prime ideal decomposition of qR in R is qR=B1,…,Bg such that f⋅g=n, ε>0 be an arbitrary positive number. Assume that σ≥max8n3.6lnn,ωnln0.5n⋅q1/g,ωn0.25q0.5l−0.25. Then, the key generation algorithm proposed in this section terminates in polynomial time, and the output matrix fgFG is an R basis of Λhq for h=gf−1modqR. Meanwhile, if σ≥n3/2ln8nq⋅q1/2+1+f/2ε, the distribution of h is rejected with probability c<1 for some absolute constant c from a distribution whose statistical distance from URq× is ≤28n/qεn.Based on theN-KeyGen algorithm, Wang and Wang [26] gave a detailed construction of CRPSF, which was first proposed in [10], over any cyclotomic field. The preimage sampling algorithm of CRPSF is useful for us to design our IBE and IBS. We also use NTRUCRPSF n,q,σ,s to represent the CRPSF and only describe the results we need. For more details, one can refer to [26]. The construction of CRPSF is as follows:(1)
TrapGen1n,q,σ: by running the N-KeyGen algorithm, we get a public key h=g⋅f−1∈Rq× and a private key sk=fgFG. The key h defines function fhz=fhz1,z2=hz1−z2∈Rq with domain Dn=z∈R2:z<s2n and range ℜn=Rq. The trapdoor of fh is sk.(2)
SampleDom1n,q,s: sample z↩DR2,s, if z≥s⋅2n, resample.(3)
SamplePresk,t: to find a preimage in Dn for a target t∈ℜn=Rq under fh by using the trapdoor sk, sample z↩DΛhq+c,s with Λhq=z1,z2∈R2:z2=hz1modqR and c=1,h−t. Return z.Theorem 6.
Assumeσ≥max8n3.6lnn,ωnln0.5n⋅q1/g,ωn0.25q0.5l−0.25,n3/2ln8nq⋅q1/2+ε for some ε∈0,1/2 and s≥n3/2⋅σ⋅ωlogn. Then, the constructed NTRUCRPSF n,q,σ,s is a CRPSF against ployn time adversaries, assuming the hardness of the worst-case Ideal-SIVPγ over K against ployn time adversaries, with γ=O˜n⋅s.We also need the following regularity theorem. For more details, one can refer to [26, 28, 29].Theorem 7.
Let K be a cyclotomic field withK:ℚ=n, R=OK, m≥2, q is a positive prime such that q∤ΔK and the prime ideal decomposition of qR in R is qR=B1,…,Bg, δ∈0,1/2, ε>0, and ai↩URq× for all i∈m. Assume t↩DRm,σ with σ≥n⋅ln2mn1+1/δ/π⋅q1/m+ε. Then, we have(2)Δa1,…,am,∑i=1mtiai;URq×m×Rq≤2δ+22mn+gq−εmn.As in [28], we only use the powerful basis p→ii=1n of R and the decoding basis d→ii=1n of R∨. We mainly use the following definition and arrangements. More details can be found in [28].Definition 4.
Given a basisB=b1,…,bn of a fractional ideal J, for any x∈J with x=x1b1+⋯+xnbn, the B-coefficient embedding of x is defined as the vector x1,…,xn and the B-coefficient embedding norm of x is defined as xBc=∑i=1nxi21/2.Setl^=l when l is odd and l^=l/2 when l is even. If l=∏i=1mpiαi for primes pi, then we define radl=∏i=1mpi. If we represent x∈R (or R∨) with respect to the powerful basis (or decoding basis), we have(3)lradlxσp→c≤σx≤l^xσp→c,forx∈R,(4)1l^xσd→c≤σx≤radllxσd→c,forx∈R∨.We will omit the subscriptsσd→ and σp→ in the following applications when it does not cause ambiguities.When we writexmodqR∨, we use the representative element of the coset x+qR∨ as ∑i=1Nxid→i with xi∈−q/2,q/2. It is similar for element x∈R. Notice that R⊆R∨, and any element of R can also be represented as a ℤ-linear combination of the decoding basis.


## 2.1. Notations

We usen to denote the set 1,2,…,n. ⋅ represents the l2 norm corresponding to the canonical embedding. For two random variables X and Y, ΔX,Y stands for their statistic distance. When we write X↩ξ, we mean that the random variable X obeys to a distribution ξ. If S is a finite set, then S is its cardinality and US is the uniform distribution over S. Symbols ℤ+ and ℝ+ stand for the sets of positive integers and positive reals. Symbol logx represents log2x for x∈ℝ+. Functions φn and μn stand for the Euler function and the Möbius function.


## 2.2. Cyclotomic Fields, SpaceH, and Ideal Lattices

Throughout this paper, we only consider cyclotomic fields. For a cyclotomic fieldK=ℚζ with ζ=ζl the primitive l-th root of unity, its minimal polynomial is Φlx=∏ilxi−1μl/i∈ℤx with degree n=φl. As usual, we set R=OK=ℤζ, which is the ring of integers of K. Then, K:ℚ=n≔2r, K≅ℚx/Φlx and R≅ℤx/Φlx. K is Galois over ℚ. We set GalK/ℚ=σi:i=1,…,n and use the canonical embedding σ on K, which maps x∈K to a space σixi∈H≔x1,…,xn∈ℂn:xn+1−i=xi¯,∀i∈r via embeddings in GalK/ℚ. H is isomorphic to ℝn as an inner product space via the orthonormal basis hi∈n defined as follows: for 1≤j≤r,(1)hj=12ej+en+1−j,hn+1−j=i2ej−en+1−j,where ej∈ℂn is the vector with 1 in its j-th coordinate and 0 elsewhere and i is the imaginary number such that i2=−1. For any element x∈K, we can define its norm by x≔σx and its infinity norm by x∞≔maxi∈nσix.We define a lattice as a discrete additive subgroup ofH. The dual lattice of Λ⊆H is defined as Λ∨=y∈H:∀x∈Λ,<x,y¯>=∑i=1nxi⋅yi∈ℤ. One can check that this definition is actually the complex conjugate of the dual lattice as usually defined in ℂn. All of the properties of the dual lattice that we use also hold for the conjugate dual. Any fractional ideal I of K is a free ℤ module of rank n. So, σI is a lattice of H, and we call σI an ideal lattice and identify I with this lattice and associate with I all the usual lattice quantities. Meanwhile, its dual is defined as I∨=a∈K:Tra⋅I⊆ℤ. Then, it is easy to verify that I∨∨=I, I∨ is a fractional ideal, and I∨ embeds under σ as the dual lattice of I as defined above.


## 2.3. Gaussian Distributions, Ring-SIS Problems, and Ring-LWE Problems

The Gaussian distribution is defined as usual. For anys>0, c∈H, which is taken to be s=1 or c=0 when omitted, define the Gaussian function ρs,c:H⟶0,1 as ρs,cx=e−πx−c2/s2. By normalizing this function, we obtain the continuous Gaussian probability distribution Ds,c of parameter s, whose density function is given by s−n⋅ρs,cx. For a real vector r=r1,…,rn∈ℝ+n, we define the elliptical Gaussian distributions in the basis hii≤n as follows: a sample from Dr is given by ∑i∈nxihi, where xi is chosen independently from the Gaussian distribution Dri over ℝ. Note that if we define a map φ:H⟶ℝn by φ∑i∈nxihi=x1,…,xn, then Dr is also a (elliptical) Gaussian distribution over ℝn.For a latticeΛ⊆H, σ>0 and c∈H, we define the lattice Gaussian distribution of support Λ, deviation σ, and center c by DΛ,σ,cx=ρσ,cx/ρσ,cΛ for any x∈Λ. For δ>0, we define the smoothing parameter ηδΛ as the smallest σ>0 such that ρ1/σΛ∨\0≤δ. The following theorem comes from [10, 30]. Here we use B˜ to represent the Gram–Schmidt orthogonalization of B and regard the columns of B as a set of vectors. For B=b1,…,bn, define B=maxibi.Theorem 1.
There is a probabilistic polynomial time algorithm that, given a basis B of an n-dimensional latticeΛ=ℒB, a standard deviation σ≥B˜⋅ωlogn, and a c∈H, outputs a sample whose distribution is statistically close to DΛ,σ,c.We will use following lemmata from [10, 31].Lemma 1.
For any full-rank latticeΛ and positive real ε>0, we have ηεΛ≤ln2n1+1/ε/π⋅λnΛ.Lemma 2.
For any full-rank latticeΛ, c∈H, ε∈0,1 and σ≥ηεΛ, we have Prb↩DΛ,σ,cb−c≥σn≤1+ε/1−ε⋅2−n.Lemma 3.
For any full-rank latticeΛ⊆H, c∈H, δ∈0,1, σ≥2ηδΛ and b∈Λ, we have DΛ,σ,cb≤1+δ/1−δ⋅2−n.The following useful rejection sampling theorem comes from [27]. We state an adapted version, corresponding to the canonical embedding and space H. Its proof is essentially the same as that in [27], so we put it in Appendix with a remark that the constant M can be effectively calculated in practice.Theorem 2.
LetΛ⊆H be an arbitrary lattice, V⊆H be a set in which all elements have norms less than T, σ be some elements in ℝ such that σ=ωT⋅logn, and h:V↦0,1 be a probability distribution. Then, there exists an absolute constant M such that the distribution of the output of the following algorithm A:(1)
v↩h(2)
z↩DΛ,σ,v(3)
Outputz,v with probability minDΛ,σz/M⋅DΛ,σ,vz,1is within statistical distance 2−ωlogn/M of the distribution of the output of the following algorithm ℱ:(1)
v↩h(2)
z↩DΛ,σ(3)
Outputz,v with probability 1/M.
Moreover, the probabilityp that A outputs something satisfies 1−2−ωlogn/M≤p≤1/M.The hard lattice problems we use are Ring-SIS and Ring-LWE problems. For an elementz=z1,…,zm∈Rm, let us define z≔∑i=1mzi21/2. We first introduce the Ring-SIS problem. The definition is as follows.Definition 1.
Let R be the ring of integers of K, q and m be positive integers, andβ be a real number. The small integer solution problem over R (R-SISq, m, β) is given a1,…,am∈Rq chosen independently from URq, find z=z1,…,zm∈Rm such that ∑i=1maizi=0modqR and 0<z≤β.For appropriate parameters, the following theorem comes from [32], which shows that the Ring-SIS problem is hard.Theorem 3.
Forε∈0,1, there is a PPT reduction from solving Ideal‐SIVPγ⋅ln2n1+1/ε/π with high probability in polynomial time in the worst case to solving R-SISq, m, β with nonnegligible probability in polynomial time, for any m,q,β,γ such that γ≥βn⋅ωlogn, q≥βn⋅ωlogn, and m,β,logq≤polyn.The Ring-LWE problem is defined as follows. LetT=H/R∨.Definition 2.
Fors∈Rq∨ and an error distribution ψ over H, the Ring-LWE distribution As,ψ∨ over Rq×T is sampled by independently choosing a uniformly random a↩URq and an error term e↩ψ and outputting a,b=a⋅s/q+emodR∨.Definition 3.
LetΨ be a family of distributions over H. The average-case Ring-LWE decision problem, denoted R-DLWEq,Ψ∨, is to distinguish (with nonnegligible advantage) between independent samples from As,ψ∨ for a random choice of s,ψ↩URq∨×Ψ and the same number of uniformly random and independent samples from Rq×T.In [33], a reduction from Ideal-SIVPγ to decision Ring-LWE problem over any algebraic number field is given.Theorem 4.
Let K be an algebraic number field andR=OK, K:ℚ=n. Assume α∈0,1 such that α≤logn/n, and let q≥2 be an integer such that αq≥ω1. Then there is a polynomial time quantum reduction from Ideal-SIVPγ (in the worst case) to R−DLWEq,Dξ∨, where ξ=αnk/lognk1/4 with k the number of samples to be used and γ=ωn⋅logn/α.We can modify the samplea,b of Ring-LWE distribution to Rq×Rq∨ as in [28]. We scale the b component by a factor of q, so that it is an element in H/qR∨. The corresponding error distribution is Dqξ with ξ=α⋅nk/lognk1/4 and k the number of samples. Then, we discretize the error, by taking e↩⌊Dqξ⌉R∨. The decision version of Ring-LWE becomes to distinguish between the modified distribution of As,⌊Dqξ⌉R∨∨ and the uniform samples from Rq×Rq∨. Notice that by using the same method proposed in [34], we can change the secret s to obey the error distributions, i.e., s↩⌊Dqξ⌉R∨. We will use the symbol R−DLWEq,⌊Dqξ⌉R∨ to denote this problem. Meanwhile, note that, if we constrain a↩UT for some T⊆Rq, where T=c⋅Rq and c≠negln, the hardness of the corresponding problem does not decrease. We will use the symbol R−DLWEq,⌊Dqξ⌉R∨× to denote this problem. For more details, one can refer to [28, 34].


## 2.4. Key Generation Algorithm and Regularity Result

In this subsection, we shall introduce some useful algorithms and results we need. The following algorithm plays a key role in our constructions of IBE and IBS. It is a modified version of key generation algorithm of traditional NTRU signatures. For simplicity, we denote it byN-KeyGen.Algorithm 1
(i)
Input: n,q∈ℤ+, σ>0.
(ii)
Output: A key pair sk,pk∈R2×2×Rq×.
(1)
Samplef from DR,σ, if fmodq∉Rq×, resample.
(2)
Sampleg from DR,σ, if gmodq∉Rq×, resample.
(3)
Iff≥nσ or g≥nσ, restart.
(4)
Iff,g≠R, restart.
(5)
ComputeFq,Gq∈R such that f⋅Gq−g⋅Fq=q, e.g., using a Hermite normal form algorithm.
(6)
Use Babai rounding nearest plane algorithm to approximateFq,Gq in the lattice spanned by f,g, let rf,g be the output, set F,G=Fq,Gq−rf,g for some r∈R.
(7)
IfF,G>nσl, restart.
(8)
Return secret keysk=fgFG and public key pk=h=g⋅f−1∈Rq×.The following theorem comes from [26] (Algorithm 1). Note that in the case of cyclotomic fields, it was shown in [26] that the value of Dedekind zeta function at 2 (i.e. ζK2) has a relatively small absolute upper bound.Theorem 5.
LetK=ℚζl be a cyclotomic field, R=OK, n=φl, q≥64nζK2 be a prime such that q∤ΔK and the prime ideal decomposition of qR in R is qR=B1,…,Bg such that f⋅g=n, ε>0 be an arbitrary positive number. Assume that σ≥max8n3.6lnn,ωnln0.5n⋅q1/g,ωn0.25q0.5l−0.25. Then, the key generation algorithm proposed in this section terminates in polynomial time, and the output matrix fgFG is an R basis of Λhq for h=gf−1modqR. Meanwhile, if σ≥n3/2ln8nq⋅q1/2+1+f/2ε, the distribution of h is rejected with probability c<1 for some absolute constant c from a distribution whose statistical distance from URq× is ≤28n/qεn.Based on theN-KeyGen algorithm, Wang and Wang [26] gave a detailed construction of CRPSF, which was first proposed in [10], over any cyclotomic field. The preimage sampling algorithm of CRPSF is useful for us to design our IBE and IBS. We also use NTRUCRPSF n,q,σ,s to represent the CRPSF and only describe the results we need. For more details, one can refer to [26]. The construction of CRPSF is as follows:(1)
TrapGen1n,q,σ: by running the N-KeyGen algorithm, we get a public key h=g⋅f−1∈Rq× and a private key sk=fgFG. The key h defines function fhz=fhz1,z2=hz1−z2∈Rq with domain Dn=z∈R2:z<s2n and range ℜn=Rq. The trapdoor of fh is sk.(2)
SampleDom1n,q,s: sample z↩DR2,s, if z≥s⋅2n, resample.(3)
SamplePresk,t: to find a preimage in Dn for a target t∈ℜn=Rq under fh by using the trapdoor sk, sample z↩DΛhq+c,s with Λhq=z1,z2∈R2:z2=hz1modqR and c=1,h−t. Return z.Theorem 6.
Assumeσ≥max8n3.6lnn,ωnln0.5n⋅q1/g,ωn0.25q0.5l−0.25,n3/2ln8nq⋅q1/2+ε for some ε∈0,1/2 and s≥n3/2⋅σ⋅ωlogn. Then, the constructed NTRUCRPSF n,q,σ,s is a CRPSF against ployn time adversaries, assuming the hardness of the worst-case Ideal-SIVPγ over K against ployn time adversaries, with γ=O˜n⋅s.We also need the following regularity theorem. For more details, one can refer to [26, 28, 29].Theorem 7.
Let K be a cyclotomic field withK:ℚ=n, R=OK, m≥2, q is a positive prime such that q∤ΔK and the prime ideal decomposition of qR in R is qR=B1,…,Bg, δ∈0,1/2, ε>0, and ai↩URq× for all i∈m. Assume t↩DRm,σ with σ≥n⋅ln2mn1+1/δ/π⋅q1/m+ε. Then, we have(2)Δa1,…,am,∑i=1mtiai;URq×m×Rq≤2δ+22mn+gq−εmn.As in [28], we only use the powerful basis p→ii=1n of R and the decoding basis d→ii=1n of R∨. We mainly use the following definition and arrangements. More details can be found in [28].Definition 4.
Given a basisB=b1,…,bn of a fractional ideal J, for any x∈J with x=x1b1+⋯+xnbn, the B-coefficient embedding of x is defined as the vector x1,…,xn and the B-coefficient embedding norm of x is defined as xBc=∑i=1nxi21/2.Setl^=l when l is odd and l^=l/2 when l is even. If l=∏i=1mpiαi for primes pi, then we define radl=∏i=1mpi. If we represent x∈R (or R∨) with respect to the powerful basis (or decoding basis), we have(3)lradlxσp→c≤σx≤l^xσp→c,forx∈R,(4)1l^xσd→c≤σx≤radllxσd→c,forx∈R∨.We will omit the subscriptsσd→ and σp→ in the following applications when it does not cause ambiguities.When we writexmodqR∨, we use the representative element of the coset x+qR∨ as ∑i=1Nxid→i with xi∈−q/2,q/2. It is similar for element x∈R. Notice that R⊆R∨, and any element of R can also be represented as a ℤ-linear combination of the decoding basis.


## 3. Identity-Based Encryption Schemes

In this section, we shall give the definition of IBE schemes and then construct a provably secure IBE scheme based on NTRU over any cyclotomic field.


### 3.1. Basic Definition and Security Model

We give the definition of IBE system first.Definition 5.
An identity-based encryption system consists of four PPT algorithms:Setup, KeyGen, Encrypt, and Decrypt.(i)
Setup λ: this algorithm takes as input a security parameter λ and generates public parametersPPand a master secret keyMsk.(ii)
KeyGen id,Msk,PP: this algorithm uses the master secret keyMskto generate an identity private key skid corresponding to an identity id.(iii)
Encrypt PP,id,m: this algorithm takes the public parametersPPto encrypt a message m for any given identityid.(iv)
Decrypt c,skid: this algorithm decrypts ciphertext c by using the identity private key skid if the identity of the ciphertext matches the identity of the private key.
The security model of IBE is defined through the following game between an adversaryA and a challenger ℬ. For a security parameter λ, let ℳλ be the plaintext space and Cλ be the ciphertext space. The game, which appraises the indistinguishability of plaintext under adaptive chosen-plaintext and adaptive chosen-identity attack (IND-ID-CPA), is defined as follows:(i)
Setup: ℬ runs the algorithm Setup λ to get the public parameters PP and the master secret key Msk; then, it sends PP to A and keeps the master secret key Msk.(ii)
Phase 1: A adaptively issues private key queries q1,…,qk for identity id1,…,idk. In each query qi for i=1,…,k, ℬ runs KeyGen to generate skidi and sends it to A.(iii)
Challenge: once A decides the Phase 1 is over, it outputs a challenge identity id∗, which has not been queried during Phase 1, and two plaintext message m0,m1∈ℳλ. ℬ chooses a random element b∈0,1 uniformly and sends cb=EncryptPP,id∗,mb to A.(iv)
Phase 2: A adaptively issues more private key queries qk+1,…,qQ for identity idk+1,…,idQ. The only requirement is that id∗≠idi for any i=k+1,…,Q.(v)
Guess: A outputs an element b′∈0,1 and wins if and only if b′=b.
We refer to such an adversaryA as an IND-ID-CPA adversary and define the advantage (in the security parameter λ) of A in attacking an IBE scheme ℰ as Advℰ,Aλ=Prb′=b−1/2.Definition 6.
For a security parameterλ, we say that an IBE scheme ℰ is adaptively IND-ID-CPA secure if for any PPT adversary A that takes at most Q=polyλ private key queries, Advℰ,Aλ≤neglλ.


### 3.2. Constructions of IBE Based on NTRU

Now, we can give the construction of IBE system over any cyclotomic field. The construction is inspired by [21], which follows the route of [10] and could be regarded as a generalization from power of 2 cyclotomic field to arbitrary cyclotomic field. The detailed construction is as follows, where ΔK denotes the discriminant of K and qR=B1,…,Bg.(i)
Setup λ: given a security parameter λ, first construct a set of parameters K,R,q,σ,s such that K=ℚζl with n=φl≥λ, R=OK, and q≥64nζK2 such that q∤ΔK. Meanwhile, σ≥max8n3.6lnn,ωnln0.5n⋅q1/g,ωn0.25q0.5l−0.25,n3/2ln8nq⋅q1/2+ε for some ε∈0,1/2, s≥n3/2⋅σ⋅ωlogn. Then, call the N-KeyGen algorithm to generate a public key h and a secret key sk=fgFG∈R2×2. Set the public parameters PP=K,R,q,σ,Rq,Rq∨,h,H, where H:0,1∗↦Rq is a random oracle, and the master secret key Msk=sk=fgFG.(ii)
KeyGen id,Msk,PP: if the pair (id, skid) is in the local storage, output skid to the user id. Otherwise,(1)
Sett=Hid∈Rq.(2)
Takeσ1,σ2=SamplePreMsk,t, where σ1,σ2 satisfies hσ1−σ2=tmodqR.(3)
Outputskid=σ1 and keep the pair (id, skid) in the local storage.(iii)
Encrypt PP,id,m: given a plaintext m=∑i=1nmi⋅d⟶i∈Rq∨ with coefficients mi∈0,1, the encryption process is as follows:(1)
Sampler,e1,e2↩χ≔⌊Dξ⋅q⌉R∨ with ξ=α⋅nk/lognk1/4, where k=O1 is a positive integer.(2)
Computet=Hid∈Rq, u=r⋅h+e1modqR∨ and v=t⋅r+e2+⌊q/4⌋⋅mmodqR∨.(3)
Output the ciphertextc=u,v.(iv)
Decrypt c=u,v,skid: this algorithm first computes w=v−u⋅skid=∑i=1nwi⋅d⟶imodqR∨ and returns m=∑i=1n⌊4/q⋅wi⌉⋅d⟶imodqR∨.Note that we havew=v−uσ1=rt+e2+⌊q/4⌋⋅m−rhσ1−e1σ1=⌊q/4⌋⋅m+emodqR∨ where e=e2−rσ2−e1σ1∈R∨ for some σ1,σ2 satisfying hσ1−σ2=tmodqR. If e∞c<q/10, then we get that w has the representation of the form ⌊q/4⌋⋅m+e in Rq∨. Setting w=∑i=1nwi⋅d⟶i and e=∑i=1nei′⋅d⟶i, we can conclude that for any q>40,(5)4qwi=4q⌊q4⌋⋅mi+4qei′=4qei′∈−25,25,ifmi=0,4q⌊q4⌋+4qei′∈12,32,ifmi=1.Therefore, the decryption process succeeds in recovering the encrypted messagem whenever e2−rσ2−e1σ1∞c<q/10. Now, we bound the probability that e2−rσ2−e1σ1∞c≥q/10. Here, ⋅∞c represents the basis-coefficient norm under the decoding basis with respect to the l∞ norm.Lemma 4.
Assume thatα∈0,1 such that α≤logn/n and let q≥2 be an integer such that αq≥ω1; meanwhile, ωn3/2lognloglogn⋅α2⋅q2⋅s<q/302; then, we have e2−rσ2−e1σ1∞c<q/10 with probability at least 1−n−ωnlogn.Proof.
Lemma 5.1 of [28] implies that Prx↩χx∞>ωnlogn⋅α2⋅q2≤n−ωnlogn. Note that σ1,σ2≤2n⋅s; we have(6)e2−rσ2−e1σ1∞c≤l^⋅e2+r⋅σ2+e1⋅σ1≤l^⋅n⋅e2∞+r∞⋅σ2+e1∞⋅σ1.
Therefore, we get(7)e2−rσ2−e1σ1∞c≤32⋅ω′n3/2lognloglogn⋅α2⋅q2⋅s,with probability at least 1−n−ωnlogn, where we have used that l^=Onloglogn.
Overall, we get the following lemma.Lemma 5.
Assume thatα∈0,1 such that α≤logn/n and let q≥2 be an integer such that αq≥ω1; meanwhile, ωn3/2lognloglogn⋅α2⋅q2⋅s<q/302; then, the decryption algorithm of the IBE scheme succeeds in recovering the encrypted message with probability at least 1−n−ωnlogn.We can prove that our IBE scheme is secure, assuming thatR−DLWEq,⌊Dqξ⌉R∨ problem and R−DLWEq,⌊Dqξ⌉R∨× problem are hard. We first give a IND-CPA secure public key encryption scheme (denoted by BasicPub). Note that Lemma 5 is suitable for BasicPub as well.(i)
Setup λ: given a security parameter λ, do as the Setup algorithm of IBE scheme. Set the public parameters PP=K,R,q,σ,Rq,Rq∨,h.(ii)
KeyGen PP: sample σ1,σ2=SampleDomPP; set the secret key sk=σ1 and the public key pk=hσ1−σ2modqR.(iii)
Encrypt PP,pk,m: do as the Encrypt algorithm of IBE scheme with t=pk.(iv)
Decrypt c=u,v,sk: the same as the Decrypt algorithm of IBE scheme.Lemma 6.
LetK=ℚζl be a cyclotomic field, n=φl, R=OK, and q≥64nζK2 be a prime such that q∤ΔK. Set σ≥max8n3.6lnn,ωnln0.5n⋅q1/g,ωn0.25q0.5l−0.25,n3/2ln8nq⋅q1/2+ε for some ε∈0,1/2 and s≥n3/2⋅σ⋅ωlogn; meanwhile, assume that α∈0,1 such that α≤logn/n, αq≥ω1, and ωn3/2lognloglogn⋅α2⋅q2⋅s<q/302. Then, the BasicPub is IND-CPA secure assuming that R−DLWEq,⌊Dqξ⌉R∨ problem and R−DLWEq,⌊Dqξ⌉R∨× problem are hard.Proof.
Note that, by the property of SampleDom algorithm, the distribution ofpk is statistically close to URq. Then, for a ciphertext u,v of either m0 or m1, by our choices of parameters, the entire view h,pk,u,v∈Rq××Rq×Rq×Rq∨ of the adversary is indistinguishable from the uniform distribution, assuming the hardness of R−DLWEq,⌊Dqξ⌉R∨ problem and R−DLWEq,⌊Dqξ⌉R∨× problem. Hence, the adversary could not distinguish the ciphertexts of 0 and 1. We get the results, as desired.Theorem 8.
Suppose that Lemma 6 holds, i.e., the BasicPub is correct and IND-CPA secure in the standard model; then, the IBE scheme is adaptively IND-ID-CPA secure in the random oracle model.Proof.
LetA be a PPT adversary that attacks the IBE scheme with advantage δ by using Q=polyn distinct H queries. We shall construct an algorithm ℬ to attack the BasicPub scheme with advantage δ/Q. The algorithm ℬ works as follows:(1)
ℬ calls an oracle (or the challenger) to get the public parameters PP′=K,R,q,σ,Rq,Rq∨,h and a public key pk. Then, it sends the public parameters PP=K,R,q,σ,Rq,Rq∨,h,H to A. Here, ℬ simulates the random oracle H; meanwhile, ℬ chooses an i∈Q uniformly at random.(2)
ℬ simulates the view of A as follows:(i)
Hash queries: on A’s jth distinct query idj to H, if j=i, then store the tuple idi,pk,⊥ and return pk to A. Otherwise, j≠i, A runs the BasicPub.KeyGen (PP′) to generate a public/secret key pair skj,pkj, locally store the tuple idj,pkj,skj, and return skj to A.(ii)
KeyGen queries: when A asks for a secret key for an identity id, assume without loss of generality that A has already queried H on id. Retrieve the unique tuple id,pk,sk from local storage. If sk=⊥, then output a random bit and abort. Otherwise, return sk to A.(3)
WhenA produces a challenge identity id∗ which is distinct from all its secret key queries and two messages m0,m1, assume without loss of generality that A has already queried H on id∗. If id∗≠idi, output a random bit and abort. Otherwise, return cb=BasicPub.EncryptPP′,pk,mb for b↩U0,1 to A.
WhenA terminates with some output, ℬ terminates with the same output.
AssumeA makes N distinct KeyGen queries for some N≤Q. Notice that the probability that ℬ does not abort is(8)Pr=1−1Q⋅1−1Q−1⋯1−1Q−N−1⋅1Q−N=1Q.
Meanwhile, conditioned onℬ not aborting, the view it provides to A is statistically close to the view of the real IBE scheme. Hence, the advantage that ℬ attacks the IND-CPA secure of BasicPub is δ/Q, as desired.
Overall, we conclude the following theorem.Theorem 9.
LetK=ℚζl be a cyclotomic field, n=φl, R=OK, and q≥64nζK2 be a prime such that q∤ΔK. Set σ≥max8n3.6lnn,ωnln0.5n⋅q1/g,ωn0.25q0.5l−0.25,n3/2ln8nq⋅q1/2+ε for some ε∈0,1/2 and s≥n3/2⋅σ⋅ωlogn; meanwhile, assume that α∈0,1 such that α≤logn/n, αq≥ω1, and ωn3/2lognloglogn⋅α2⋅q2⋅s<q/302. Then, the IBE scheme is adaptively IND-ID-CPA secure against any PPT adversary in the random oracle model, assuming the hardness of worst-case Ideal-SIVPγ over K against PPT adversaries, with γ=O˜n2⋅s.Remark 1.
If we chooseαq=ω1, then s=O˜n7.5, q=O˜n9 and γ=O˜n9.5. As remarked in [28], we can also convert our constructions to work in an ideal of R, or we can directly design our schemes in R (with larger γ and q). Moreover, when we require that q=1modl with l having some special cases (for example, l=pα,2αp or 2αpq for some prime p,q), we can use the hardness results shown in [35] and techniques shown in [36] to reduce the magnitude of the parameters q and γ. Usually, the module q is far away from practicality. A heuristic practical choice of parameters (with respect to coefficient embedding) is shown in [21]. How to reduce the size of q and γ is a hard problem which is worth studying.


## 3.1. Basic Definition and Security Model

We give the definition of IBE system first.Definition 5.
An identity-based encryption system consists of four PPT algorithms:Setup, KeyGen, Encrypt, and Decrypt.(i)
Setup λ: this algorithm takes as input a security parameter λ and generates public parametersPPand a master secret keyMsk.(ii)
KeyGen id,Msk,PP: this algorithm uses the master secret keyMskto generate an identity private key skid corresponding to an identity id.(iii)
Encrypt PP,id,m: this algorithm takes the public parametersPPto encrypt a message m for any given identityid.(iv)
Decrypt c,skid: this algorithm decrypts ciphertext c by using the identity private key skid if the identity of the ciphertext matches the identity of the private key.
The security model of IBE is defined through the following game between an adversaryA and a challenger ℬ. For a security parameter λ, let ℳλ be the plaintext space and Cλ be the ciphertext space. The game, which appraises the indistinguishability of plaintext under adaptive chosen-plaintext and adaptive chosen-identity attack (IND-ID-CPA), is defined as follows:(i)
Setup: ℬ runs the algorithm Setup λ to get the public parameters PP and the master secret key Msk; then, it sends PP to A and keeps the master secret key Msk.(ii)
Phase 1: A adaptively issues private key queries q1,…,qk for identity id1,…,idk. In each query qi for i=1,…,k, ℬ runs KeyGen to generate skidi and sends it to A.(iii)
Challenge: once A decides the Phase 1 is over, it outputs a challenge identity id∗, which has not been queried during Phase 1, and two plaintext message m0,m1∈ℳλ. ℬ chooses a random element b∈0,1 uniformly and sends cb=EncryptPP,id∗,mb to A.(iv)
Phase 2: A adaptively issues more private key queries qk+1,…,qQ for identity idk+1,…,idQ. The only requirement is that id∗≠idi for any i=k+1,…,Q.(v)
Guess: A outputs an element b′∈0,1 and wins if and only if b′=b.
We refer to such an adversaryA as an IND-ID-CPA adversary and define the advantage (in the security parameter λ) of A in attacking an IBE scheme ℰ as Advℰ,Aλ=Prb′=b−1/2.Definition 6.
For a security parameterλ, we say that an IBE scheme ℰ is adaptively IND-ID-CPA secure if for any PPT adversary A that takes at most Q=polyλ private key queries, Advℰ,Aλ≤neglλ.


## 3.2. Constructions of IBE Based on NTRU

Now, we can give the construction of IBE system over any cyclotomic field. The construction is inspired by [21], which follows the route of [10] and could be regarded as a generalization from power of 2 cyclotomic field to arbitrary cyclotomic field. The detailed construction is as follows, where ΔK denotes the discriminant of K and qR=B1,…,Bg.(i)
Setup λ: given a security parameter λ, first construct a set of parameters K,R,q,σ,s such that K=ℚζl with n=φl≥λ, R=OK, and q≥64nζK2 such that q∤ΔK. Meanwhile, σ≥max8n3.6lnn,ωnln0.5n⋅q1/g,ωn0.25q0.5l−0.25,n3/2ln8nq⋅q1/2+ε for some ε∈0,1/2, s≥n3/2⋅σ⋅ωlogn. Then, call the N-KeyGen algorithm to generate a public key h and a secret key sk=fgFG∈R2×2. Set the public parameters PP=K,R,q,σ,Rq,Rq∨,h,H, where H:0,1∗↦Rq is a random oracle, and the master secret key Msk=sk=fgFG.(ii)
KeyGen id,Msk,PP: if the pair (id, skid) is in the local storage, output skid to the user id. Otherwise,(1)
Sett=Hid∈Rq.(2)
Takeσ1,σ2=SamplePreMsk,t, where σ1,σ2 satisfies hσ1−σ2=tmodqR.(3)
Outputskid=σ1 and keep the pair (id, skid) in the local storage.(iii)
Encrypt PP,id,m: given a plaintext m=∑i=1nmi⋅d⟶i∈Rq∨ with coefficients mi∈0,1, the encryption process is as follows:(1)
Sampler,e1,e2↩χ≔⌊Dξ⋅q⌉R∨ with ξ=α⋅nk/lognk1/4, where k=O1 is a positive integer.(2)
Computet=Hid∈Rq, u=r⋅h+e1modqR∨ and v=t⋅r+e2+⌊q/4⌋⋅mmodqR∨.(3)
Output the ciphertextc=u,v.(iv)
Decrypt c=u,v,skid: this algorithm first computes w=v−u⋅skid=∑i=1nwi⋅d⟶imodqR∨ and returns m=∑i=1n⌊4/q⋅wi⌉⋅d⟶imodqR∨.Note that we havew=v−uσ1=rt+e2+⌊q/4⌋⋅m−rhσ1−e1σ1=⌊q/4⌋⋅m+emodqR∨ where e=e2−rσ2−e1σ1∈R∨ for some σ1,σ2 satisfying hσ1−σ2=tmodqR. If e∞c<q/10, then we get that w has the representation of the form ⌊q/4⌋⋅m+e in Rq∨. Setting w=∑i=1nwi⋅d⟶i and e=∑i=1nei′⋅d⟶i, we can conclude that for any q>40,(5)4qwi=4q⌊q4⌋⋅mi+4qei′=4qei′∈−25,25,ifmi=0,4q⌊q4⌋+4qei′∈12,32,ifmi=1.Therefore, the decryption process succeeds in recovering the encrypted messagem whenever e2−rσ2−e1σ1∞c<q/10. Now, we bound the probability that e2−rσ2−e1σ1∞c≥q/10. Here, ⋅∞c represents the basis-coefficient norm under the decoding basis with respect to the l∞ norm.Lemma 4.
Assume thatα∈0,1 such that α≤logn/n and let q≥2 be an integer such that αq≥ω1; meanwhile, ωn3/2lognloglogn⋅α2⋅q2⋅s<q/302; then, we have e2−rσ2−e1σ1∞c<q/10 with probability at least 1−n−ωnlogn.Proof.
Lemma 5.1 of [28] implies that Prx↩χx∞>ωnlogn⋅α2⋅q2≤n−ωnlogn. Note that σ1,σ2≤2n⋅s; we have(6)e2−rσ2−e1σ1∞c≤l^⋅e2+r⋅σ2+e1⋅σ1≤l^⋅n⋅e2∞+r∞⋅σ2+e1∞⋅σ1.
Therefore, we get(7)e2−rσ2−e1σ1∞c≤32⋅ω′n3/2lognloglogn⋅α2⋅q2⋅s,with probability at least 1−n−ωnlogn, where we have used that l^=Onloglogn.
Overall, we get the following lemma.Lemma 5.
Assume thatα∈0,1 such that α≤logn/n and let q≥2 be an integer such that αq≥ω1; meanwhile, ωn3/2lognloglogn⋅α2⋅q2⋅s<q/302; then, the decryption algorithm of the IBE scheme succeeds in recovering the encrypted message with probability at least 1−n−ωnlogn.We can prove that our IBE scheme is secure, assuming thatR−DLWEq,⌊Dqξ⌉R∨ problem and R−DLWEq,⌊Dqξ⌉R∨× problem are hard. We first give a IND-CPA secure public key encryption scheme (denoted by BasicPub). Note that Lemma 5 is suitable for BasicPub as well.(i)
Setup λ: given a security parameter λ, do as the Setup algorithm of IBE scheme. Set the public parameters PP=K,R,q,σ,Rq,Rq∨,h.(ii)
KeyGen PP: sample σ1,σ2=SampleDomPP; set the secret key sk=σ1 and the public key pk=hσ1−σ2modqR.(iii)
Encrypt PP,pk,m: do as the Encrypt algorithm of IBE scheme with t=pk.(iv)
Decrypt c=u,v,sk: the same as the Decrypt algorithm of IBE scheme.Lemma 6.
LetK=ℚζl be a cyclotomic field, n=φl, R=OK, and q≥64nζK2 be a prime such that q∤ΔK. Set σ≥max8n3.6lnn,ωnln0.5n⋅q1/g,ωn0.25q0.5l−0.25,n3/2ln8nq⋅q1/2+ε for some ε∈0,1/2 and s≥n3/2⋅σ⋅ωlogn; meanwhile, assume that α∈0,1 such that α≤logn/n, αq≥ω1, and ωn3/2lognloglogn⋅α2⋅q2⋅s<q/302. Then, the BasicPub is IND-CPA secure assuming that R−DLWEq,⌊Dqξ⌉R∨ problem and R−DLWEq,⌊Dqξ⌉R∨× problem are hard.Proof.
Note that, by the property of SampleDom algorithm, the distribution ofpk is statistically close to URq. Then, for a ciphertext u,v of either m0 or m1, by our choices of parameters, the entire view h,pk,u,v∈Rq××Rq×Rq×Rq∨ of the adversary is indistinguishable from the uniform distribution, assuming the hardness of R−DLWEq,⌊Dqξ⌉R∨ problem and R−DLWEq,⌊Dqξ⌉R∨× problem. Hence, the adversary could not distinguish the ciphertexts of 0 and 1. We get the results, as desired.Theorem 8.
Suppose that Lemma 6 holds, i.e., the BasicPub is correct and IND-CPA secure in the standard model; then, the IBE scheme is adaptively IND-ID-CPA secure in the random oracle model.Proof.
LetA be a PPT adversary that attacks the IBE scheme with advantage δ by using Q=polyn distinct H queries. We shall construct an algorithm ℬ to attack the BasicPub scheme with advantage δ/Q. The algorithm ℬ works as follows:(1)
ℬ calls an oracle (or the challenger) to get the public parameters PP′=K,R,q,σ,Rq,Rq∨,h and a public key pk. Then, it sends the public parameters PP=K,R,q,σ,Rq,Rq∨,h,H to A. Here, ℬ simulates the random oracle H; meanwhile, ℬ chooses an i∈Q uniformly at random.(2)
ℬ simulates the view of A as follows:(i)
Hash queries: on A’s jth distinct query idj to H, if j=i, then store the tuple idi,pk,⊥ and return pk to A. Otherwise, j≠i, A runs the BasicPub.KeyGen (PP′) to generate a public/secret key pair skj,pkj, locally store the tuple idj,pkj,skj, and return skj to A.(ii)
KeyGen queries: when A asks for a secret key for an identity id, assume without loss of generality that A has already queried H on id. Retrieve the unique tuple id,pk,sk from local storage. If sk=⊥, then output a random bit and abort. Otherwise, return sk to A.(3)
WhenA produces a challenge identity id∗ which is distinct from all its secret key queries and two messages m0,m1, assume without loss of generality that A has already queried H on id∗. If id∗≠idi, output a random bit and abort. Otherwise, return cb=BasicPub.EncryptPP′,pk,mb for b↩U0,1 to A.
WhenA terminates with some output, ℬ terminates with the same output.
AssumeA makes N distinct KeyGen queries for some N≤Q. Notice that the probability that ℬ does not abort is(8)Pr=1−1Q⋅1−1Q−1⋯1−1Q−N−1⋅1Q−N=1Q.
Meanwhile, conditioned onℬ not aborting, the view it provides to A is statistically close to the view of the real IBE scheme. Hence, the advantage that ℬ attacks the IND-CPA secure of BasicPub is δ/Q, as desired.
Overall, we conclude the following theorem.Theorem 9.
LetK=ℚζl be a cyclotomic field, n=φl, R=OK, and q≥64nζK2 be a prime such that q∤ΔK. Set σ≥max8n3.6lnn,ωnln0.5n⋅q1/g,ωn0.25q0.5l−0.25,n3/2ln8nq⋅q1/2+ε for some ε∈0,1/2 and s≥n3/2⋅σ⋅ωlogn; meanwhile, assume that α∈0,1 such that α≤logn/n, αq≥ω1, and ωn3/2lognloglogn⋅α2⋅q2⋅s<q/302. Then, the IBE scheme is adaptively IND-ID-CPA secure against any PPT adversary in the random oracle model, assuming the hardness of worst-case Ideal-SIVPγ over K against PPT adversaries, with γ=O˜n2⋅s.Remark 1.
If we chooseαq=ω1, then s=O˜n7.5, q=O˜n9 and γ=O˜n9.5. As remarked in [28], we can also convert our constructions to work in an ideal of R, or we can directly design our schemes in R (with larger γ and q). Moreover, when we require that q=1modl with l having some special cases (for example, l=pα,2αp or 2αpq for some prime p,q), we can use the hardness results shown in [35] and techniques shown in [36] to reduce the magnitude of the parameters q and γ. Usually, the module q is far away from practicality. A heuristic practical choice of parameters (with respect to coefficient embedding) is shown in [21]. How to reduce the size of q and γ is a hard problem which is worth studying.


## 4. Identity-Based Signature Schemes

In this section, we shall give the definition of IBS schemes and then construct a provably secure IBS scheme based on NTRU over any cyclotomic field.


### 4.1. Basic Definition and Security Model

We give the definition of IBS system first.Definition 7.
An identity-based signature system consists of four PPT algorithms:Setup, KeyGen, Sign, and Verification.(i)
Setup λ: this algorithm takes as input a security parameter λ and generates public parameters PP and a master secret key Msk.(ii)
KeyGen id,Msk,PP: this algorithm uses the master secret key Msk to generate an identity private key skid corresponding to an identity id.(iii)
Sign PP,id,skid,μ: this algorithm takes the public parameters PP, a message μ, an identity id, and the secret key skid to generate a signature Sig of μ.(iv)
Verification PP,μ,Sig,id: on input of the identity id, the message μ, the parameters PP, and a signature Sig, this algorithm outputs 1 when the verification is correct (i.e., the signature is valid) and outputs 0 otherwise.
The security model of IBS is defined through the following game between an adversaryA and a challenger ℬ. For a security parameter λ, let ℳλ be the message space and Sλ be the signature space. The game, which appraises the property of existentially unforgeable against adaptively chosen message and adaptively chosen identity attacks, is defined as follows:(i)
Setup: ℬ runs the algorithm Setup λ to get the public parameters PP and the master secret key Msk; then, it sends PP to A and keeps the master secret key Msk.(ii)
Phase 1: A adaptively issues private key queries q1,…,qk for identity id1,…,idk. In each query qi for i=1,…,k, ℬ runs KeyGen to generate skidi and sends it to A.(iii)
Challenge: once A decides the Phase 1 is over, it outputs an identity id∗, which has not been queried during Phase 1.(iv)
Phase 2: A adaptively issues more queries qk+1,…,qQ where each query qi is one of the following:(1)
Private key query foridi≠id∗: ℬ responds as in Phase 1.(2)
Signature query for a messageμ under identity id∗: this query can be regarded as an oracle, and ℬ runs the oracle to get a signature Sig=SignPP,id∗,skid∗,μ and sends Sig to A.(v)
Forge: A outputs a forge Sig∗ for a message μ under identity id∗. It wins if and only if one of the following two cases happens:(1)
Ifμ is queried in Phase 2, then we require that Sig∗≠Sig, where Sig is the signature of μ that A got in Phase 2. Meanwhile, VerificationPP,μ,Sig∗,id∗=1.(2)
Otherwise, we simply require thatVerificationPP,μ,Sig∗,id∗=1.
We define the advantage (in the security parameterλ) of A in attacking an IBS scheme ℰ as Advℰ,Aλ=PrAwins−1/2.Definition 8.
For a security parameterλ, we say that an IBS scheme ℰ is existentially unforgeable against adaptively chosen message and adaptively chosen identity attacks if for any PPT adversary A that takes at most Q=polyλ queries, Advℰ,Aλ≤neglλ.


### 4.2. Constructions of IBS Based on NTRU

Now, we can give the construction of IBS system over any cyclotomic field. The detailed construction is as follows:(i)
Setup λ: given a security parameter λ, first construct a set of parameters K,R,q,σ,s such that K=ℚζl with n=φl≥λ, R=OK, and q≥64nζK2 such that q∤ΔK. Meanwhile, σ≥max8n3.6lnn,ωnln0.5n⋅q1/g,ωn0.25q0.5l−0.25,n3/2ln8nq⋅q1/2+ε for some ε∈0,1/2, s≥n3/2⋅σ⋅ωlogn. Then, call the N-KeyGen algorithm to generate a public key h and a secret key sk=fgFG∈R2×2. Set the public parameters PP=K,R,q,σ,Rq,Rq∨,h,H,H′, where H:0,1∗↦Rq and H′:Rq×0,1∗↦Rq are two random oracles, and the master secret key Msk=sk=fgFG.(ii)
KeyGen id,Msk,PP: if the pair (id, skid) is in the local storage, output skid to the user id. Otherwise,(1)
Sett=Hid∈Rq.(2)
Takeσ1,σ2=SamplePreMsk,t, where σ1,σ2 satisfies hσ1−σ2=tmodqR.(3)
Outputskid=σ1,σ2 and keep the pair (id, skid) in the local storage.(iii)
Sign PP,id,skid,μ: given a message μ, the signature process is as follows:(1)
Sampley1,y2↩DR,s.(2)
Computeu=H′hy1−y2modqR,μ∈Rq and zi=yi+σi⋅u for i=1,2.(3)
Output the signatureSig=z1,z2,u of message μ with probability minDR2,sz/M⋅DR2,s,vz,1 with v=σ1u,σ2u and M=O1 (in practice, M can be computed efficiently).(iv)
Verification PP,μ,Sig,id: for Sig=z1,z2,u, if z1,z2≤2n⋅s and H′hz1−z2−Hid⋅umodqR,μ=u∈Rq, output 1. Otherwise, output 0.The signing algorithm outputs something with probabilityminDR2,sz/M⋅DR2,s,σ1u,σ2uz,1, if nothing was output, the signer runs the signing algorithm again until some signature is outputted. Note that hz1−z2−Hid⋅u=hy1−y2+hσ1−σ2⋅u−Hid⋅u=hy1−y2modqR. Meanwhile, Lemma 2 and Theorem 2.2 imply that z1,z2≤2n⋅s with overwhelming probability. We conclude the following lemma.Lemma 7.
The IBS scheme proposed above satisfies correctness.The security of the IBS scheme can be reduced to the worst-case SIVPγ problem over K.Theorem 10.
LetK=ℚζl be a cyclotomic field, n=φl, R=OK, and q≥64nζK2 be a prime such that q∤ΔK. Assume that σ≥max8n3.6lnn,ωnln0.5n⋅q1/g,ωn0.25q0.5l−0.25,n3/2ln8nq⋅q1/2+ε for some ε∈0,1/2, s≥n3/2⋅σ⋅ωlogn. The IBS scheme is existentially unforgeable against adaptively chosen message and adaptively chosen identity attacks for any PPT adversary in the random oracle model, assuming the hardness of worst-case Ideal-SIVPγ over K against PPT adversaries, with γ=O˜n⋅s.Proof.
Suppose that there is an adversaryA which can break the existentially unforgeable IBS scheme with advantage δ; we can construct an algorithm ℬ to solve the R−SISq,2,β problem over K for β=22n⋅s. The interactions between ℬ and A are described as follows:(1)
For an R-SISq,2,β instance a1,a2, if a1,a2∉Rq×2, abort. Otherwise, ℬ sends h=a2−1⋅a1modqR↩URq× to A.(2)
A can adaptively query in the following ways. In general, we can assume that A has to query the random oracle H for id before it makes other kinds of queries.(i)
H query: at the beginning, ℬ keeps an ID-list which consists of elements of the form id,tid,skid. The list is empty initially. For a query of identity id∗, if it is contained in the ID-list, ℬ simply sends tid∗ to A. Otherwise, id∗ is fresh. ℬ samples z=σ1,σ2↩DR2,s and computes tid∗=hσ1−σ2modqR. Then, ℬ sends tid∗ to A and stores id∗,tid∗,skid∗=σ1,σ2 in the ID-list.(ii)
KeyGen query: given id∗, ℬ looks up the ID-list to find skid∗ corresponding to id∗ and sends skid∗ to A.(iii)
Sign query: ℬ also keeps a SIGN-list which is empty initially and consists of elements of the form μ,id,y1,y2,skid,u,z1,z2. To obtain the signature of message μ∗∈0,1∗ under the identity id∗, if μ∗,id∗ is in the SIGN-list, ℬ simply sends z1∗,z2∗,u∗ to A. Otherwise, μ∗ is fresh and ℬ looks up the ID-list for skid∗ and runs Sign PP,id∗,skid∗,μ∗ to get a signature z1∗,z2∗,u∗. ℬ sends z1∗,z2∗,u∗ to A and stores μ∗,id∗,y1∗,y2∗,skid∗,u∗,z1∗,z2∗ in the SIGN-list. Here, y1∗,y2∗ is obtained through the algorithm Sign PP,id∗,skid∗,μ∗.(iv)
H′ query: when A sends a message μ∗ under identity id∗ to ℬ for the H′ query, ℬ finds the corresponding u∗ in the SIGN-list and sends it to A (if μ∗ is not in the SIGN-list, ℬ implements Sign query for μ∗,id∗ and sends corresponding u∗ obtained by Sign query to A).(3)
Forge: after finishing the queries listed above,A outputs a forgery z1∗′,z2∗′,u∗′ for id∗,μ∗ with a nonnegligible probability δ.
Note that, without loss of generality, we can assume that before outputting the attempted forgeryz1∗′,z2∗′,u∗′, A has made a query for Sign (or strictly speaking, A has made a query for H′, but a H′ query is equivalent to a Sign query, by our constructions), i.e. u∗′=u∗ for a u∗ in the SIGN-list. ℬ can get z1∗,z2∗ from the SIGN-list, which satisfies H′hz1∗−z2∗−Hid∗⋅u∗,μ∗=H′hz1∗′−z2∗′−Hid∗⋅u∗′,μ∗=u∗=u∗′. Hence, we have hz1∗−z2∗−Hid∗⋅u∗=hz1∗′−z2∗′−Hid∗⋅u∗modqR (up to a negligible probability). Therefore, a1z1∗−z1∗′+a2z2∗′−z2∗=0modqR. Let z=z1∗−z1∗′,z2∗′−z2∗; we have z2=z1∗−z1∗′2+z2∗′−z2∗2≤8ns2. Hence, if z≠0, it is a valid solution of R−SISq,2,22n⋅s.
Also, note that in order to give a valid forge,A needs to find z1∗′,z2∗′ to fulfil that z1∗′,z2∗′≤2n⋅s and hz1∗′−z2∗′=wmodqR for w=hz1∗−z2∗modqR. Theorem 2.2 implies that we can regard zi∗↩DR,s. Theorem 2.7 implies that w↩URq. For any w∈Rq, the solutions of the equation hx1−x2=wmodqR form a lattice Λ′=z1∗,z2∗+Λhq. Hence, for the parameter choices of s and σ, Lemma 3 indicates that the probability that z=0 is negligible. Therefore, except with some negligible probability εn, we can solve R-SISq,2,22n⋅s with advantage δ′=1−εnδ.Remark 2.
By the conditions in Theorem 4.1, we can takes=O˜n7, q=O˜n8 and γ=O˜n8. Also, the module q is far away from practicality. How to reduce the size of q and γ is a hard problem which is worth studying.
One may note that the trapdoor generation algorithms used in IBE and IBS schemes are the same, so as the case of IBE in power-of-2 cyclotomic rings; we can also use the parameter choices (with respect to coefficient embedding) as in [21], together with the parameter choices of rejection sampling as in [27] to give a practical implementation of our schemes. A more heuristic implementation with respect to coefficient embedding in power-of-2 cyclotomic rings is also shown in [17].


## 4.1. Basic Definition and Security Model

We give the definition of IBS system first.Definition 7.
An identity-based signature system consists of four PPT algorithms:Setup, KeyGen, Sign, and Verification.(i)
Setup λ: this algorithm takes as input a security parameter λ and generates public parameters PP and a master secret key Msk.(ii)
KeyGen id,Msk,PP: this algorithm uses the master secret key Msk to generate an identity private key skid corresponding to an identity id.(iii)
Sign PP,id,skid,μ: this algorithm takes the public parameters PP, a message μ, an identity id, and the secret key skid to generate a signature Sig of μ.(iv)
Verification PP,μ,Sig,id: on input of the identity id, the message μ, the parameters PP, and a signature Sig, this algorithm outputs 1 when the verification is correct (i.e., the signature is valid) and outputs 0 otherwise.
The security model of IBS is defined through the following game between an adversaryA and a challenger ℬ. For a security parameter λ, let ℳλ be the message space and Sλ be the signature space. The game, which appraises the property of existentially unforgeable against adaptively chosen message and adaptively chosen identity attacks, is defined as follows:(i)
Setup: ℬ runs the algorithm Setup λ to get the public parameters PP and the master secret key Msk; then, it sends PP to A and keeps the master secret key Msk.(ii)
Phase 1: A adaptively issues private key queries q1,…,qk for identity id1,…,idk. In each query qi for i=1,…,k, ℬ runs KeyGen to generate skidi and sends it to A.(iii)
Challenge: once A decides the Phase 1 is over, it outputs an identity id∗, which has not been queried during Phase 1.(iv)
Phase 2: A adaptively issues more queries qk+1,…,qQ where each query qi is one of the following:(1)
Private key query foridi≠id∗: ℬ responds as in Phase 1.(2)
Signature query for a messageμ under identity id∗: this query can be regarded as an oracle, and ℬ runs the oracle to get a signature Sig=SignPP,id∗,skid∗,μ and sends Sig to A.(v)
Forge: A outputs a forge Sig∗ for a message μ under identity id∗. It wins if and only if one of the following two cases happens:(1)
Ifμ is queried in Phase 2, then we require that Sig∗≠Sig, where Sig is the signature of μ that A got in Phase 2. Meanwhile, VerificationPP,μ,Sig∗,id∗=1.(2)
Otherwise, we simply require thatVerificationPP,μ,Sig∗,id∗=1.
We define the advantage (in the security parameterλ) of A in attacking an IBS scheme ℰ as Advℰ,Aλ=PrAwins−1/2.Definition 8.
For a security parameterλ, we say that an IBS scheme ℰ is existentially unforgeable against adaptively chosen message and adaptively chosen identity attacks if for any PPT adversary A that takes at most Q=polyλ queries, Advℰ,Aλ≤neglλ.


## 4.2. Constructions of IBS Based on NTRU

Now, we can give the construction of IBS system over any cyclotomic field. The detailed construction is as follows:(i)
Setup λ: given a security parameter λ, first construct a set of parameters K,R,q,σ,s such that K=ℚζl with n=φl≥λ, R=OK, and q≥64nζK2 such that q∤ΔK. Meanwhile, σ≥max8n3.6lnn,ωnln0.5n⋅q1/g,ωn0.25q0.5l−0.25,n3/2ln8nq⋅q1/2+ε for some ε∈0,1/2, s≥n3/2⋅σ⋅ωlogn. Then, call the N-KeyGen algorithm to generate a public key h and a secret key sk=fgFG∈R2×2. Set the public parameters PP=K,R,q,σ,Rq,Rq∨,h,H,H′, where H:0,1∗↦Rq and H′:Rq×0,1∗↦Rq are two random oracles, and the master secret key Msk=sk=fgFG.(ii)
KeyGen id,Msk,PP: if the pair (id, skid) is in the local storage, output skid to the user id. Otherwise,(1)
Sett=Hid∈Rq.(2)
Takeσ1,σ2=SamplePreMsk,t, where σ1,σ2 satisfies hσ1−σ2=tmodqR.(3)
Outputskid=σ1,σ2 and keep the pair (id, skid) in the local storage.(iii)
Sign PP,id,skid,μ: given a message μ, the signature process is as follows:(1)
Sampley1,y2↩DR,s.(2)
Computeu=H′hy1−y2modqR,μ∈Rq and zi=yi+σi⋅u for i=1,2.(3)
Output the signatureSig=z1,z2,u of message μ with probability minDR2,sz/M⋅DR2,s,vz,1 with v=σ1u,σ2u and M=O1 (in practice, M can be computed efficiently).(iv)
Verification PP,μ,Sig,id: for Sig=z1,z2,u, if z1,z2≤2n⋅s and H′hz1−z2−Hid⋅umodqR,μ=u∈Rq, output 1. Otherwise, output 0.The signing algorithm outputs something with probabilityminDR2,sz/M⋅DR2,s,σ1u,σ2uz,1, if nothing was output, the signer runs the signing algorithm again until some signature is outputted. Note that hz1−z2−Hid⋅u=hy1−y2+hσ1−σ2⋅u−Hid⋅u=hy1−y2modqR. Meanwhile, Lemma 2 and Theorem 2.2 imply that z1,z2≤2n⋅s with overwhelming probability. We conclude the following lemma.Lemma 7.
The IBS scheme proposed above satisfies correctness.The security of the IBS scheme can be reduced to the worst-case SIVPγ problem over K.Theorem 10.
LetK=ℚζl be a cyclotomic field, n=φl, R=OK, and q≥64nζK2 be a prime such that q∤ΔK. Assume that σ≥max8n3.6lnn,ωnln0.5n⋅q1/g,ωn0.25q0.5l−0.25,n3/2ln8nq⋅q1/2+ε for some ε∈0,1/2, s≥n3/2⋅σ⋅ωlogn. The IBS scheme is existentially unforgeable against adaptively chosen message and adaptively chosen identity attacks for any PPT adversary in the random oracle model, assuming the hardness of worst-case Ideal-SIVPγ over K against PPT adversaries, with γ=O˜n⋅s.Proof.
Suppose that there is an adversaryA which can break the existentially unforgeable IBS scheme with advantage δ; we can construct an algorithm ℬ to solve the R−SISq,2,β problem over K for β=22n⋅s. The interactions between ℬ and A are described as follows:(1)
For an R-SISq,2,β instance a1,a2, if a1,a2∉Rq×2, abort. Otherwise, ℬ sends h=a2−1⋅a1modqR↩URq× to A.(2)
A can adaptively query in the following ways. In general, we can assume that A has to query the random oracle H for id before it makes other kinds of queries.(i)
H query: at the beginning, ℬ keeps an ID-list which consists of elements of the form id,tid,skid. The list is empty initially. For a query of identity id∗, if it is contained in the ID-list, ℬ simply sends tid∗ to A. Otherwise, id∗ is fresh. ℬ samples z=σ1,σ2↩DR2,s and computes tid∗=hσ1−σ2modqR. Then, ℬ sends tid∗ to A and stores id∗,tid∗,skid∗=σ1,σ2 in the ID-list.(ii)
KeyGen query: given id∗, ℬ looks up the ID-list to find skid∗ corresponding to id∗ and sends skid∗ to A.(iii)
Sign query: ℬ also keeps a SIGN-list which is empty initially and consists of elements of the form μ,id,y1,y2,skid,u,z1,z2. To obtain the signature of message μ∗∈0,1∗ under the identity id∗, if μ∗,id∗ is in the SIGN-list, ℬ simply sends z1∗,z2∗,u∗ to A. Otherwise, μ∗ is fresh and ℬ looks up the ID-list for skid∗ and runs Sign PP,id∗,skid∗,μ∗ to get a signature z1∗,z2∗,u∗. ℬ sends z1∗,z2∗,u∗ to A and stores μ∗,id∗,y1∗,y2∗,skid∗,u∗,z1∗,z2∗ in the SIGN-list. Here, y1∗,y2∗ is obtained through the algorithm Sign PP,id∗,skid∗,μ∗.(iv)
H′ query: when A sends a message μ∗ under identity id∗ to ℬ for the H′ query, ℬ finds the corresponding u∗ in the SIGN-list and sends it to A (if μ∗ is not in the SIGN-list, ℬ implements Sign query for μ∗,id∗ and sends corresponding u∗ obtained by Sign query to A).(3)
Forge: after finishing the queries listed above,A outputs a forgery z1∗′,z2∗′,u∗′ for id∗,μ∗ with a nonnegligible probability δ.
Note that, without loss of generality, we can assume that before outputting the attempted forgeryz1∗′,z2∗′,u∗′, A has made a query for Sign (or strictly speaking, A has made a query for H′, but a H′ query is equivalent to a Sign query, by our constructions), i.e. u∗′=u∗ for a u∗ in the SIGN-list. ℬ can get z1∗,z2∗ from the SIGN-list, which satisfies H′hz1∗−z2∗−Hid∗⋅u∗,μ∗=H′hz1∗′−z2∗′−Hid∗⋅u∗′,μ∗=u∗=u∗′. Hence, we have hz1∗−z2∗−Hid∗⋅u∗=hz1∗′−z2∗′−Hid∗⋅u∗modqR (up to a negligible probability). Therefore, a1z1∗−z1∗′+a2z2∗′−z2∗=0modqR. Let z=z1∗−z1∗′,z2∗′−z2∗; we have z2=z1∗−z1∗′2+z2∗′−z2∗2≤8ns2. Hence, if z≠0, it is a valid solution of R−SISq,2,22n⋅s.
Also, note that in order to give a valid forge,A needs to find z1∗′,z2∗′ to fulfil that z1∗′,z2∗′≤2n⋅s and hz1∗′−z2∗′=wmodqR for w=hz1∗−z2∗modqR. Theorem 2.2 implies that we can regard zi∗↩DR,s. Theorem 2.7 implies that w↩URq. For any w∈Rq, the solutions of the equation hx1−x2=wmodqR form a lattice Λ′=z1∗,z2∗+Λhq. Hence, for the parameter choices of s and σ, Lemma 3 indicates that the probability that z=0 is negligible. Therefore, except with some negligible probability εn, we can solve R-SISq,2,22n⋅s with advantage δ′=1−εnδ.Remark 2.
By the conditions in Theorem 4.1, we can takes=O˜n7, q=O˜n8 and γ=O˜n8. Also, the module q is far away from practicality. How to reduce the size of q and γ is a hard problem which is worth studying.
One may note that the trapdoor generation algorithms used in IBE and IBS schemes are the same, so as the case of IBE in power-of-2 cyclotomic rings; we can also use the parameter choices (with respect to coefficient embedding) as in [21], together with the parameter choices of rejection sampling as in [27] to give a practical implementation of our schemes. A more heuristic implementation with respect to coefficient embedding in power-of-2 cyclotomic rings is also shown in [17].



---

*Source: 1742386-2019-10-17.xml*