# Revocable ID-Based Signature with Short Size over Lattices

Authors: Ying-Hao Hung; Yuh-Min Tseng; Sen-Shan Huang
Journal: Security and Communication Networks
 (2017)

---

## Abstract

In the past, many ID-based signature (IBS) schemes based on the integer factorization or discrete logarithm problems were proposed. With the progress on the development of quantum technology, IBS schemes mentioned above would become vulnerable. Recently, several IBS schemes over lattices were proposed to be secure against attacks in the quantum era. As conventional public-key settings, ID-based public-key settings have to offer a revocation mechanism to revoke misbehaving or malicious users. However, in the past, little work focuses on the revocation problem in the IBS schemes over lattices. In this article, we propose a new revocable IBS (RIBS) scheme with short size over lattices. Based on the short integer solution (SIS) assumption, we prove that the proposed RIBS scheme provides existential unforgeability against adaptive chosen-message attacks. As compared to the existing IBS schemes over lattices, our RIBS scheme has better performance in terms of signature size, signing key size, and the revocation mechanism with public channels.


---

## Body

## 1. Introduction

The perception of identity-based cryptography (IBC) was first proposed by Shamir [1] in 1984. In IBC, a user’s public key can be derived from her/his identity such as email address and physical IP address. The private keys of users are generated by a trusted private key generator, named PKG. The private keys are, respectively, given to the corresponding users using secure channels. As contradicted to conventional public-key settings, IBC removes the need of certificate management. By following Shamir’s perception, Boneh and Franklin [2] proposed a practical identity- (ID-) based encryption (IBE) scheme based on bilinear pairings.The public key of a user is legal before its intended expiration date, but several circumstances must force to revoke it. So a public-key setting should offer a revocation method or mechanism to revoke the associated public keys of misbehaving or malicious users. Indeed, Boneh and Franklin [2] proposed not only a practical IBE scheme but also a revocation method for ID-based public-key setting. In their revocation method, the PKG periodically generates the new private keys for all nonrevoked users and securely sends the periodic private keys to these users, respectively. In such a case, a secure channel between the PKG and each nonrevoked user must be established to send the periodic private key. However, the size of the PKG’s key update equals the amount of all nonrevoked users. Afterward, Boldyreva et al. [3] employed a tree structure to propose a new revocable IBE (RIBE) scheme. In the RIBE scheme, the size of the PKG’s key update is reduced to the logarithm of the amount of all nonrevoked users, but the private key size of each user will increase from constant to the logarithm of the amount of all nonrevoked users. Nevertheless, two mentioned revocation mechanisms above still require encryption/decryption to send periodic private keys to users. Thus, the required periodic encryption/decryption will raise the workloads of both the PKG and users. To eliminate the requirement of encryption/decryption, Tseng and Tsai [4] proposed a new RIBE scheme with a public channel. In their RIBE scheme, the PKG and users do not need to encrypt/decrypt the periodic private keys. It provides an alternative which is more practical than the previously proposed revocation solutions.The security of today’s universally used public-key cryptographies (including the mentioned IBC above) is based on the prime factoring assumption or the hardness of the discrete logarithm problem. With the progress on the development of quantum technology, the computational power of quantum computers would cause instant threat to these public-key cryptographies [5]. Accordingly, this has motivated the era of postquantum cryptography (PQC). Among several postquantum research areas, lattice-based public-key cryptography has received the most significant attention from researchers. When compared with other (PQC) cryptographies, lattice-based public-key cryptography can provide more efficiency in public-key encryption and digital signature schemes. In the past five years, there has been a tremendous growth in lattice-based public-key cryptography and its related schemes have become viable.Related Work. To combine the advantages of IBC and lattices, Ruckert [6] proposed the first two ID-based signature (IBS) schemes over lattice assumptions. To improve the efficiency and security, several lattice-based IBS schemes [7–10] have been proposed. In [7, 8], they employed Gentry et al.’s signature scheme [11] with a user’s identity to generate the corresponding signing key. By the signing key, the user can run a preimage sampling algorithm (i.e., lattice basis delegation) [12] to obtain a signature. According to Gentry et al.’s signature scheme, the user’s signing key is a short basis of a lattice. In such a case, two lattice-based IBS schemes [7, 8] would be inefficient in practice since the signing key size and the signature size will increase dramatically after lattice basis delegation.Based on the lattice-based IBS scheme in [8], Tian and Huang [9] replaced the preimage sampling algorithm with the rejection sampling technique [13] to generate a signature. Their signature scheme can be viewed as an identity-based version of Lyubashevsky’s signature scheme [13]. The advantage of Tian and Huang’s lattice-based IBS scheme is to reduce the signature size and computation overhead of generating a signature. In 2016, inspired by the IBE scheme over NTRU lattice proposed by Ducas et al. [14], Xie et al. [10] employed their key extract algorithm to further improve the size of a user’s signing key. However, these lattice-based IBS schemes mentioned above did not address the revocation problem. Indeed, these lattice-based IBS schemes would use Boneh and Franklin’s periodic revocation mechanism [2] to achieve revocation functionality. However, in the revocation mechanism, the PKG and nonrevoked users require encryption/decryption to send periodic signing keys to users.Recently, Xiang [15] adopted the binary tree structure used in [3] to construct a revocable IBS (RIBS) scheme over lattices. As the advantage of Boldyreva et al.’s scheme [3], the size of the PKG’s key update is reduced to the logarithm of the amount of all nonrevoked users. Indeed, Xiang’s scheme also inherits the disadvantages that occurred in Boldyreva et al.’s scheme [3], namely, the private key size of a user increases from constant to the logarithm of the number of users, and encryption/decryption are required to securely send the users’ periodic signing keys. Meanwhile, the signing key size, signature size, and computational cost in Xiang’s scheme turn out to be inefficient.Contribution. In this article, we employ the revocation idea of Tseng and Tsai [4] to propose an efficient RIBS scheme over lattices while the size of a user’s signing key remains constant. In our RIBS scheme, a user’s signing key consists of two components, namely, initial key and time update key. The initial key is fixed and unchanged, while the time update key is changed along with time-period. The PKG periodically generates new time update keys and then sends them to nonrevoked users using a public channel. If the PKG would like to revoke misbehaving users, the PKG just stops issuing the new time update keys for those users. Thus, a RIBS scheme must address two kinds of adversaries: an inside adversary (or a revoked user) and an outside adversary. Based on the short integer solution (SIS) assumption over lattices [16], we prove that the proposed RIBS scheme provides existential unforgeability against adaptive chosen-message attacks for a revoked user and an outside adversary. As compared to the existing lattice-based RIBS schemes, our scheme possesses the following properties:(i)
Both the initial key and time update key of a user are generated using the Gaussian sampling technique over NTRU lattice. The point is that both keys are small and independent of the number of users in the system.(ii)
We employ the rejection sampling technique [13] to generate a signature while the signature size is lesser than that of the signature scheme using the preimage sampling algorithm.(iii)
The PKG and nonrevoked users do not need to encrypt/decrypt the periodic time update keys.In summary, as compared with previously proposed IBS and RIBS schemes over lattices, our scheme possesses better performance in terms of signing key size, signature size, and the revocation mechanism.Organization. The rest of this article is arranged as follows. Section 2 presents several important preliminaries. In Section 3, the syntax and adversary models of RIBS schemes are given. The proposed RIBS scheme over lattices is presented in Section 4. In Section 5, the security of the proposed RIBS scheme is formally analyzed. In Section 6, performance analysis and comparisons are made to demonstrate the advantages of the proposed scheme. In Section 7, conclusions are given.


## 2. Preliminaries

Here, we review several fundamental concepts and assumptions of lattices.


### 2.1. Notations

Throughout this article, letR be the set of real numbers, N be an integer with the type power-of-two, Z be the set of integers, and, for q∈Z, Zq be the set of integers in the set [-q/2,-q/2). x denotes the Euclidean norm of a vector x. X represents the norm of a matrix X which is defined as the largest norm of its columns. Let Rq=Zq[X]/(XN+1) be the ring of polynomials modulo XN+1 with coefficients in Zq. For f=∑i=0N-1fixi and g=∑i=oN-1gixi in Rq, let f+g and f·g denote, respectively, the addition and multiplication in Rq, defined by(1)f+g=∑i=0N-1fi+giximodq,f·g=∑k=oN-1∑i+j=kmodNfigixkmodq.Here, the coefficients off+g and f·g are reduced modulo q into the set Zq. For convenience, an element f in Rq will be written as a polynomial ∑i=0N-1fixi or a vector [f0,f1,…,fN-1].For any setB={b1,…,bn}⊂Rn of linearly independent vectors, let B~={b~1,…,b~n} denote its Gram-Schmidt orthogonalization, defined iteratively in the following way: b1~=b1, and for each i=2,…,n, bi~ is the component of bi orthogonal to span (b1,…,bi-1). Clearly, B~≤B.


### 2.2. Lattice

A lattice is a set of points inn-dimensional space with a periodic structure [16]. Let b1,b2,…,bn be n linearly independent vectors in Rn. These linearly independent vectors can generate a (n-dimensional) lattice Λ that is denoted by L(b1,…,bn), namely, the set {∑i=1nxibi:xi∈Z}. The set B={b1,…,bn} is viewed as a basis of the lattice Λ.


### 2.3. Anticirculant Matrices

Anticirculant matrices have become one of the most important and active research fields in recent years since they possess a special structure and nice properties.Definition 1.
AnN-dimensional anticirculant matrix with f=∑i=0N-1fixi is represented as in the following Toeplitz matrix:(2)ANf=fx·f⋮xN-1·f=f0f1⋯fN-1-fN-1f0⋯fN-2⋯⋯⋯⋯-f1-f2⋯f0.
For convenience, we denoteAN(f) as A(f) in this article. Anticirculant matrices possess the following important property.Lemma 2 (see [14]).
A ( f ) + A ( g ) = A ( f + g ) and A(f)×A(g)=A(f·g), where f,g∈Rq.


### 2.4. NTRU Lattices

NTRU [17] is a lattice-based cryptosystem that relied on a particularly efficient class of convolution modular lattices, called NTRU lattices. We briefly review the concept of NTRU lattices on which our scheme is based.Definition 3.
Assume thatq is a positive integer and N is a power-of-two integer while f,g∈Rq and h=g·f-1. By using h and q, a NTRU full-rank lattice of Z2N is represented as (3)Λh,q=u,v∈Rq2∣u+v·h=0.Indeed, the NTRU full-rank lattice Λh,q is generated by the matrix(4)Ah,q=-AhINqINON,where IN and ON are, respectively, the N×N unit matrix and N×N null matrix.
However, ifh is uniformly distributed in Rq, then the basis Ah,q is unsuitable for solving the closed lattice vector problem. To compensate this, Hoffstein et al. [18] constructed an appropriate basis(5)Bf,g=Ag-AfAG-Affor Λh,q while satisfying f·G-g·F=q, where F,G∈Rq. Indeed, it can be computed efficiently to find such F and G. Moreover, Bf,g provides a short basis for Λh,q due to the fact Bf,g≤Ah,q by Lemma 4 below.Lemma 4 (see [14]).
Assume thatf,g,F,G∈Rq satisfy f·G-g·F=q and h=g·f-1. Then, Ah,q and Bf,g are both bases of the NTRU lattice Λh,q and Bf,g≤Ah,q.Gentry et al. [11] proposed the Gaussian sampling technique as the trapdoor generation algorithm to produce a trapdoor of a one-way function. Ducas et al. [14] proposed a special distribution over the NTRU lattices to improve the performance of the trapdoor generation algorithm in Gentry et al.’s scheme. In this article, we adopt Ducas et al.’s scheme as the trapdoor generation algorithm as follows.Lemma 5 (see [14]).
Letq be a prime, N be a power-of-two integer, and σ=1.17q/2N. Then, we can construct a probabilistic polynomial-time (PPT) algorithm TrapGen(q,N) which generates two polynomials f and g to output h=g·f-1 and a matrix Bf,g such that h is statistically close to uniform in Rq and Bf,g is a short basis of Λh,q.


### 2.5. Gaussian (Normal) Distribution

Gentry et al. [11] proposed the Gaussian sampling technique as the trapdoor generation algorithm which produces a trapdoor without leaking any information of the short basis. Before we introduce Gentry et al.’s method, we define Gaussian distributions.Definition 6.
The continuous Gaussian distribution overRN centered at c∈RN with the standard deviation s>0 is defined by the function ρs,cN(x)=(1/s2π)Ne-∥x-c∥2/2s2, where x∈RN.For any latticeΛ∈RN, ρs,cN(Λ) represents ∑x∈Λρs,cN(x).Definition 7.
The discrete Gaussian distribution overRN centered at c∈RN with the standard deviation s>0 is defined as Ds,cN(x)=ρs,cN(x)/ρs,cN(Λ), where x∈RN.In this sequel, we can curtailρs,0N as ρsN and Ds,0N as DsN, respectively. On the other hand, Lyubashevsky [13] proposed an interesting fact of Dσ,vN(x), the discrete normal distribution in dimension N with standard deviation σ at center v.Lemma 8 (see [13]).
For anyv∈Zm and α>0, we have the following properties.Ifσ=ω(vlog⁡m), then Pr⁡[x∈Dσm:Dσm(x)/Dσ,vm(x)=O(1)]=1-2ω(log⁡m).Ifσ=αv, then Pr⁡[x∈Dσm:Dσm(x)/Dσ,vm(x)<e12/α+1/(2σ2)]>1-2-100.
According to Lemma8, there is real M≈e such that Dσm(x)≤MDσ,vm(x) for all x∈Zm [9].


### 2.6. Sampling Algorithms

Micciancio and Regev [19] defined a lattice parameter to determine the amount of Gaussian noise that one has to add to a lattice in order to get close to a uniform distribution. By Micciancio and Regev’s method, Gentry et al. [11] proposed a sampling algorithm as follows.Lemma 9 (see [11]).
Letq be a prime and B be a short basis of an N-dimensional lattice Λ. If s≥B~·ω(log⁡N) and 0<ε<1, then, for any c∈RN, we have the following properties:(1)
Pr⁡[x-c]>sN≤1+ε/1+ε·2-N, where x∈Ds,cN.(2)
There is a PPT algorithmSampleGau(B,s,c) that can output a sample in Λ from a distribution which is statistically close to Ds,cN.


### 2.7. Rejection Sampling Algorithm

Lyubashevsky [13] adopted the rejection sampling technique to sign a message. When a user with ID would like to sign a message with a signing key SID, she/he first chooses a vector y∈DσN. And then the user sets a candidate signature z as y+c·SID where c is a hash value of message. Let F be the target distribution of the signature z which is independent of SID. If G is a probability distribution and M>0 while satisfying F(x)≤M·G(x) for all x, then the candidate signature z can be output successfully with probability F(z)/M·G(z), and M is the expected number of times required for outputting a signature.


### 2.8. Hardness Assumptions

In the following, we present a mathematical problem, namely, the short integer solution (SIS) problem, which has at least the same difficulty with the worst case of short independent vector problem (SIVP) up to a polynomial approximation factor [16].Definition 10 (R-SISq,m,βΦ problem).
The small integer solution (SIS) problem on a ring with parametersq, m, β, and Φ is defined as follows. Given a1,a2,…,am chosen uniformly and independently from Rq=Zq[x]/(Φ), the associated SIS problem is to find r1,r2,…,rm∈Z such that ∑i=1mriai=0 mod q and z≤β, where z=(r1,r2,…,rm)T∈Zm.Stehle and Steinfeld [20] presented the idea that the statistical distance between the distribution of h=g/f and the uniform distribution of Rq is negligible. If we take an NTRU public key h=g/f, the R-SISq,m,βΦ problem on the NTRU lattices is to find a pair (z1,z2) that satisfies the conditions z1+h·z2=0 and (z1,z2)≤β.


## 2.1. Notations

Throughout this article, letR be the set of real numbers, N be an integer with the type power-of-two, Z be the set of integers, and, for q∈Z, Zq be the set of integers in the set [-q/2,-q/2). x denotes the Euclidean norm of a vector x. X represents the norm of a matrix X which is defined as the largest norm of its columns. Let Rq=Zq[X]/(XN+1) be the ring of polynomials modulo XN+1 with coefficients in Zq. For f=∑i=0N-1fixi and g=∑i=oN-1gixi in Rq, let f+g and f·g denote, respectively, the addition and multiplication in Rq, defined by(1)f+g=∑i=0N-1fi+giximodq,f·g=∑k=oN-1∑i+j=kmodNfigixkmodq.Here, the coefficients off+g and f·g are reduced modulo q into the set Zq. For convenience, an element f in Rq will be written as a polynomial ∑i=0N-1fixi or a vector [f0,f1,…,fN-1].For any setB={b1,…,bn}⊂Rn of linearly independent vectors, let B~={b~1,…,b~n} denote its Gram-Schmidt orthogonalization, defined iteratively in the following way: b1~=b1, and for each i=2,…,n, bi~ is the component of bi orthogonal to span (b1,…,bi-1). Clearly, B~≤B.


## 2.2. Lattice

A lattice is a set of points inn-dimensional space with a periodic structure [16]. Let b1,b2,…,bn be n linearly independent vectors in Rn. These linearly independent vectors can generate a (n-dimensional) lattice Λ that is denoted by L(b1,…,bn), namely, the set {∑i=1nxibi:xi∈Z}. The set B={b1,…,bn} is viewed as a basis of the lattice Λ.


## 2.3. Anticirculant Matrices

Anticirculant matrices have become one of the most important and active research fields in recent years since they possess a special structure and nice properties.Definition 1.
AnN-dimensional anticirculant matrix with f=∑i=0N-1fixi is represented as in the following Toeplitz matrix:(2)ANf=fx·f⋮xN-1·f=f0f1⋯fN-1-fN-1f0⋯fN-2⋯⋯⋯⋯-f1-f2⋯f0.
For convenience, we denoteAN(f) as A(f) in this article. Anticirculant matrices possess the following important property.Lemma 2 (see [14]).
A ( f ) + A ( g ) = A ( f + g ) and A(f)×A(g)=A(f·g), where f,g∈Rq.


## 2.4. NTRU Lattices

NTRU [17] is a lattice-based cryptosystem that relied on a particularly efficient class of convolution modular lattices, called NTRU lattices. We briefly review the concept of NTRU lattices on which our scheme is based.Definition 3.
Assume thatq is a positive integer and N is a power-of-two integer while f,g∈Rq and h=g·f-1. By using h and q, a NTRU full-rank lattice of Z2N is represented as (3)Λh,q=u,v∈Rq2∣u+v·h=0.Indeed, the NTRU full-rank lattice Λh,q is generated by the matrix(4)Ah,q=-AhINqINON,where IN and ON are, respectively, the N×N unit matrix and N×N null matrix.
However, ifh is uniformly distributed in Rq, then the basis Ah,q is unsuitable for solving the closed lattice vector problem. To compensate this, Hoffstein et al. [18] constructed an appropriate basis(5)Bf,g=Ag-AfAG-Affor Λh,q while satisfying f·G-g·F=q, where F,G∈Rq. Indeed, it can be computed efficiently to find such F and G. Moreover, Bf,g provides a short basis for Λh,q due to the fact Bf,g≤Ah,q by Lemma 4 below.Lemma 4 (see [14]).
Assume thatf,g,F,G∈Rq satisfy f·G-g·F=q and h=g·f-1. Then, Ah,q and Bf,g are both bases of the NTRU lattice Λh,q and Bf,g≤Ah,q.Gentry et al. [11] proposed the Gaussian sampling technique as the trapdoor generation algorithm to produce a trapdoor of a one-way function. Ducas et al. [14] proposed a special distribution over the NTRU lattices to improve the performance of the trapdoor generation algorithm in Gentry et al.’s scheme. In this article, we adopt Ducas et al.’s scheme as the trapdoor generation algorithm as follows.Lemma 5 (see [14]).
Letq be a prime, N be a power-of-two integer, and σ=1.17q/2N. Then, we can construct a probabilistic polynomial-time (PPT) algorithm TrapGen(q,N) which generates two polynomials f and g to output h=g·f-1 and a matrix Bf,g such that h is statistically close to uniform in Rq and Bf,g is a short basis of Λh,q.


## 2.5. Gaussian (Normal) Distribution

Gentry et al. [11] proposed the Gaussian sampling technique as the trapdoor generation algorithm which produces a trapdoor without leaking any information of the short basis. Before we introduce Gentry et al.’s method, we define Gaussian distributions.Definition 6.
The continuous Gaussian distribution overRN centered at c∈RN with the standard deviation s>0 is defined by the function ρs,cN(x)=(1/s2π)Ne-∥x-c∥2/2s2, where x∈RN.For any latticeΛ∈RN, ρs,cN(Λ) represents ∑x∈Λρs,cN(x).Definition 7.
The discrete Gaussian distribution overRN centered at c∈RN with the standard deviation s>0 is defined as Ds,cN(x)=ρs,cN(x)/ρs,cN(Λ), where x∈RN.In this sequel, we can curtailρs,0N as ρsN and Ds,0N as DsN, respectively. On the other hand, Lyubashevsky [13] proposed an interesting fact of Dσ,vN(x), the discrete normal distribution in dimension N with standard deviation σ at center v.Lemma 8 (see [13]).
For anyv∈Zm and α>0, we have the following properties.Ifσ=ω(vlog⁡m), then Pr⁡[x∈Dσm:Dσm(x)/Dσ,vm(x)=O(1)]=1-2ω(log⁡m).Ifσ=αv, then Pr⁡[x∈Dσm:Dσm(x)/Dσ,vm(x)<e12/α+1/(2σ2)]>1-2-100.
According to Lemma8, there is real M≈e such that Dσm(x)≤MDσ,vm(x) for all x∈Zm [9].


## 2.6. Sampling Algorithms

Micciancio and Regev [19] defined a lattice parameter to determine the amount of Gaussian noise that one has to add to a lattice in order to get close to a uniform distribution. By Micciancio and Regev’s method, Gentry et al. [11] proposed a sampling algorithm as follows.Lemma 9 (see [11]).
Letq be a prime and B be a short basis of an N-dimensional lattice Λ. If s≥B~·ω(log⁡N) and 0<ε<1, then, for any c∈RN, we have the following properties:(1)
Pr⁡[x-c]>sN≤1+ε/1+ε·2-N, where x∈Ds,cN.(2)
There is a PPT algorithmSampleGau(B,s,c) that can output a sample in Λ from a distribution which is statistically close to Ds,cN.


## 2.7. Rejection Sampling Algorithm

Lyubashevsky [13] adopted the rejection sampling technique to sign a message. When a user with ID would like to sign a message with a signing key SID, she/he first chooses a vector y∈DσN. And then the user sets a candidate signature z as y+c·SID where c is a hash value of message. Let F be the target distribution of the signature z which is independent of SID. If G is a probability distribution and M>0 while satisfying F(x)≤M·G(x) for all x, then the candidate signature z can be output successfully with probability F(z)/M·G(z), and M is the expected number of times required for outputting a signature.


## 2.8. Hardness Assumptions

In the following, we present a mathematical problem, namely, the short integer solution (SIS) problem, which has at least the same difficulty with the worst case of short independent vector problem (SIVP) up to a polynomial approximation factor [16].Definition 10 (R-SISq,m,βΦ problem).
The small integer solution (SIS) problem on a ring with parametersq, m, β, and Φ is defined as follows. Given a1,a2,…,am chosen uniformly and independently from Rq=Zq[x]/(Φ), the associated SIS problem is to find r1,r2,…,rm∈Z such that ∑i=1mriai=0 mod q and z≤β, where z=(r1,r2,…,rm)T∈Zm.Stehle and Steinfeld [20] presented the idea that the statistical distance between the distribution of h=g/f and the uniform distribution of Rq is negligible. If we take an NTRU public key h=g/f, the R-SISq,m,βΦ problem on the NTRU lattices is to find a pair (z1,z2) that satisfies the conditions z1+h·z2=0 and (z1,z2)≤β.


## 3. Syntax and Adversary Model of RIBS

In the following, we define the syntax and adversary model of RIBS schemes.Definition 11.
A RIBS scheme includes five algorithms:(i)
Setup. The algorithm takes a system parameter N and the amount J of all time-periods as input and publishes public parametersParms and sets a system secret key SPKG in secret.(ii)
Initial Key Extract. Given a user’s ID and the system secret key SPKG, it computes and sends the initial key DID to the user.(iii)
Time Key Update. Given a time-period t, a user’s ID, and the system secret key SPKG, this algorithm computes and sends the time update key TID,t to the user.(iv)
Signing. This algorithm takes a message μ, a user’s signing key SID,t, and a time-period t as input. It then returns a signature θ on μ.(v)
Verification. This algorithm takes a message μ, a signature θ, a user’s ID, and a time-period t as input. It returns “accept” if θ is valid and “reject” otherwise.
By the framework of the RIBS scheme, a user’s signing key consists of two components, namely, initial key and time update key. Thus, the associated adversary model consists of two kinds of adversaries: an inside adversary (or a revoked user) and an outside adversary.Definition 12.
For a RIBS scheme, if there exists no PPT adversaryA (a revoked user or an outside adversary) who has nonnegligible probability to forge a valid signature under adaptive chosen-message attacks, we say that the RIBS scheme is existentially unforgeable or RID-UF-ACMA secure. In the following RID-UF-ACMA game, the adversary A may interact with a challenger C to obtain some useful information.(i)
Initialization.C performs thesetup algorithm to setParms and SPKG. The PKG sendsParms to the adversary A and keeps SPKG in secret.(ii)
Queries.A can adaptively request a number of different queries as follows.
(a)
Initial Key Extract Query. Upon receiving an identity ID, C performs theinitial key extract algorithm to generate DID. C then sends DID to A.(b)
Time Key Update Query. Upon receiving a user’s ID and a time-period t, C performs thetime key update algorithm to generate TID,t. C then sends TID,t to A.(c)
Signing Query. Upon receiving a message μ, an identity ID, and a time-period t, C uses SID,t=(DID,TID,t) to perform the signing algorithm to obtain a signature θ. C then sends θ to A.(iii)
Forgery. If A with nonnegligible probability can forge a signature tuple (μ∗,ID∗,t∗,θ∗) that fulfills three following conditions, we call that A with nonnegligible probability wins the game. We define the nonnegligible probability as the advantage of A in the game.
(1)
For(μ∗,ID∗,t∗,θ∗), theverification algorithm outputs “accept.”(2)
The tuple(μ∗,ID∗,t∗) is not issued during thesigning query.(3)
IfA is an outside adversary, ID∗ is not issued during theinitial key extract query.(4)
IfA is a revoked user (inside adversary), (ID∗,t∗) is not issued during thetime key update query.


## 4. Efficient RIBS Scheme over NTRU Lattices

The proposed RIBS scheme over NTRU lattices includes five algorithms.(i)
Setup. Given a system parameter N, the PKG chooses a prime q, s>0, and σ>0. Then the PKG runs the algorithm TrapGen(q,N) presented in Lemma 5 to obtain (f,g) such that h=g·f-1, f<sN, and g<sN while generating a short basis(6)B=Ag-AfAG-Af∈Zq2N×2NofΛh,q.The PKG generates public parametersParms and a system secret key SPKG as follows:
(1)
Set three hash functionsH0, H1:{0,1}∗→ZqN, and H2:{0,1}∗→{vv∈{-1,0,1}Nsuch  thatv1≤λ}, where the vectors v can be viewed as polynomials with coefficients in the set {-1,0,1} and v1 denotes the number of nonzero components of v.(2)
Finally, the PKG setsSPKG=B and Parms=h,H0,H1,H2, where h is the system public key.(ii)
Initial Key Extract. Given a user’s ID∈{0,1}∗, the PKG first calculates H0(ID) and then uses the system secret key SPKG=B to run the algorithm SampleGau(B,s,H0(ID)) in Lemma 9 to output a sample (s1,s2) such that (s1,s2)<s2N and s1+h·s2=H0(ID). Then, the PKG sets the initial key DID=(s1,s2) and sends the user with DID using secure channel. In fact, if one knows (h,H0(ID)) and chooses si(i=1,2) from a Gaussian distribution instead of a uniform one, then recovering si is as hard as solving worst-case lattice problems [21].(iii)
Time Key Update. Upon receiving a time-period t and a user’s ID∈{0,1}∗, the PKG first calculates H1(ID,t) and uses the system secret key SPKG=B to run the algorithm SampleGau(B,s,H1(ID,t)) to output a sample (s3,s4) such that (s3,s4)<s2N and s3+h·s4=H1(ID,t). Then, the PKG sets the time update key TID,t=(s3,s4) and sends the user with TID,t using public channel. Meanwhile, the user sets the signing key SID,t=(DID,TID,t). In fact, if one knows (h,H1(ID,t)) and chooses si(i=3,4) from a Gaussian distribution instead of a uniform one, then recovering si is as hard as solving worst-case lattice problems [21].(iv)
Signing. Given a message μ∈{0,1}∗ and a time-period t, the user with ID∈{0,1}∗ first chooses y1, y2 from the distribution DσN and computes c=H2(y1+h·y2,μ), z1=y1+(s1+s3)·c, and z2=y2+(s2+s4)·c, where (z1,z2)≤2σ2N. Finally, the user can generate a signature (z1,z2,c) with probability min⁡[DσN/MDσ,c·SID,tN,1], where M=O(1). If nothing is generated by the user, the user repeats this algorithm.(v)
Verification. Given a signature (z1,z2,c) on a message μ for a user’s ID at a time-period t, a verifier validates the signature by checking the following equality:(7)c=H2z1+h·z2-H0ID+H1ID,t·c,μ.If the equality holds, theVerification algorithm returns “accept” and “reject” otherwise.Here, the correctness of the equality follows from(8)z1+h·z2-H0ID+H1ID,t·c=y1+s1+s3·c+h·y2+h·s2+s4·c-s1+h·s2+s3+h·s4·c=y1+h·y2.


## 5. Security Analysis

In this section, we demonstrate the security of the proposed RIBS scheme. In our RIBS scheme, a user’s signing key includes two parts, namely, the initial key and time update key. To revoke a user, the PKG simply stops issuing the user’s periodic time update key. As the RID-UF-ACMA game presented in Definition12, the adversary may get either the time update key or the initial key, but not both. Hence, there are two kinds of adversaries to be concerned with, namely, revoked user and outside adversary. An outside adversary cannot access the target’s initial key, but it may get all time update keys. Since a revoked user has already owned the associated initial key, the user cannot get the periodic time update key.Firstly, we adopt the key extract algorithm in Ducas et al. [14, Algorithm 3] to generate both initial keys and time update keys. Based on Ducas et al. [14], Lemma 13 demonstrates that our scheme is secure against the ID forgery attacks. Moreover, Theorem 14 demonstrates that the proposed RIBS scheme is secure for an outside adversary and a revoked user.Lemma 13.
Our RIBS scheme is secure against ID forgery attack.Proof.
In our scheme, we adopt the key extract algorithm in Ducas et al. [14] to generate initial keys. Let h=g·f-1 be the public key and(9)B=Ag-AfAG-Afbe a short basis of the NTRU, where f,g,F,G∈Rq, f·G-g·F=q, f<sN, and g<sN. The initial key (s1,s2) is generated by SampleGau(B,s,H0(ID)) to output a sample s1 as the first component of the initial key and determine the second component s2 such that s1+h·s2=H0(ID)∈ZqN. By the security analysis of [14], no PPT adversary A may find (s1,s2) with nonnegligible advantage. Therefore, the proposed RIBS scheme is secure against ID forgery attacks.Theorem 14.
Assume that there exists a PPT adversaryA (an outsider or a revoked user) who can break the proposed RIBS scheme with nonnegligible probability ε in the random oracle model. Based on the adversary A, we then construct a PPT algorithm C to compute the R-SIS problem with nonnegligible probability (1-2-ω(log⁡N))ε, where N is the system parameter.Proof.
Here, we demonstrate only the case whenA is an outside adversary since the other case when A is a revoked user can be proved similarly. Without loss of generality, an algorithm C receives a random instance (q,2N,4s2N+2λσ2N,XN+1) of the R-SIS problem, where q is a prime, N is a positive integer, and s, λ, σ>0. We will show how C can make use of the adversary A to output the R-SIS solution which is nonzero vector (u1,u2)∈Zq2N. The algorithm C plays the challenger and interacts with the adversary A as follows.(i)
Initialization. Given the system parameter N, the challenger C randomly chooses a polynomial h∈Rq. Then, C sets the public parameters Parms=h,H0,H1,H2, where the hash functions H0, H1, and H2 are viewed as random oracles controlled by C. Finally, C returnsParms to A.(ii)
Queries. The challenger C responds to these queries issued by the adversary A as follows.
(a)
H0Query. At any time, A can issue the query along with IDi. To respond to the query, C maintains an initially empty list L0 of tuples of the form IDi,PIDi,DIDi. When A queries the oracle H0 with IDi, C responds to A with PIDi according to the following rules.
(1)
IfIDi appears in a tuple IDi,PIDi,DIDi in L0, then C responds with PIDi.(2)
Otherwise, the challengerC randomly chooses si1, si2∈DsN such that (si1,si2)<s2N. Then C computes the polynomial PIDi=si1+h·si2 and adds the tuple IDi,PIDi,DIDi=(si1,si2) in L0. C responds to A with PIDi.(b)
H1Query. At any time, A can issue the query along with (IDi,t). To respond to the query, C maintains an initially empty list L1 of tuples of the form IDi,t,T1i,TID,t. When A queries the oracle H1, C responds to A with T1i according to the following rules.
(1)
If(IDi,t) appears in a tuple IDi,t,T1i,TID,t in L1, then C responds with T1i.(2)
Otherwise, the challengerC randomly chooses si3,si4∈DsN such that (si3,si4)<s2N. The challenger C sets the user’s time update key TID,t=(si3,si4) and computes T1i=si3+h·si4. Then C adds the tuple IDi,t,T1i,TID,t in L1. C responds to A with T1i.(c)
H2Query. At any time, A can issue the query along with (yj,μj). To respond to the query, C maintains an initially empty list L2 of tuples of the form yj,μj,cj. When A queries oracle H2, C responds to A with cj according to the following rules.
(1)
If(yj,μj) appears in a tuple yj,μj,cj in L2, then C responds with cj.(2)
Otherwise,C randomly chooses cj∈Rq. Then, C adds the tuple yj,μj,cj to the list L2. Finally, the challenger C responds to A with cj.(d)
Initial Key Extract Query. When A issues the query along with IDi, C first looks up the list L0 to find the tuple containing DIDi associated with IDi and send it to A. If no such tuple is found in L0, C obtains DIDi by issuing the H0(IDi) query and responds to A with DIDi.(e)
Time Key Update Query. When A issues the query along with (IDi,t), C first looks up the list L1 to find the tuple containing TID,t associated with (IDi,t) and send it to A. If no such tuple is found in L1, C obtains TID,t by issuing the H1(IDi,t) query and responds to A with TID,t.(f)
Sign Query. Upon receiving this query on (μj,IDi,t), the challenger C performs the following steps to generate a valid signature. First, C looks up the lists L0 and L1 to obtain, if there exist, the associated tuples IDi,PIDi,DIDi and IDi,t,T1i,TID,t, respectively. Then, C randomly chooses yj,z1,z2∈DσN and computes cj=(z1+h·z2-yj)/(PIDi+T1i). C adds yj,μj,cj in the list L2 and returns the signature (z1,z2,cj) on μj. Even though the challenger C does not hold the associated initial key and time update key, the generated tuple (z1,z2,cj) is still a valid signature. The reason is that the signature (z1,z2,cj) can pass the verification (10)z1+h·z2-H0ID+H1ID,t·cj=z1+h·z2-PIDi+T1i·z1+h·z2-yjPIDi+T1i=yj.(g)
Forgery. Finally, the adversary A forges a valid signature tuple (z1∗,z2∗,cj∗) on message μ∗ for identity ID∗ at the period t∗ with nonnegligible probability. Note that ID∗ is not issued during theinitial key extract query or (ID∗,t∗) is not issued during thetime key update query.
When the adversaryA successfully forges a valid signature (z1∗,z2∗,cj∗), we then use the Forking lemma in [22] to generate another valid signature (z1′,z2′,cj′) of the message μ∗ such that (z1∗,z2∗)≤2σ2N and (z1′,z2′)≤2σ2N. Since (z1∗,z2∗,cj∗) and (z1′,z2′,cj′) are two valid signatures for (μ∗,ID∗,t∗), we have the equality(11)H2z2∗+h·z2∗-H0ID∗+H1ID∗,t∗·c∗,μ∗=H2z2′+h·z2′-H0ID∗+H1ID∗,t∗·c′,μ∗which implies that (12)z2∗+h·z2∗-H0ID∗+H1ID∗,t∗·c∗=z2′+h·z2′H0ID∗+H1ID∗,t∗·c′.Since we have H0(ID∗)=s1+h·s2 and H1(ID∗)=s3+h·s4, we obtain (13)z1∗-z1′-s1c∗-c′-s3c∗-c′+h·z2∗-z2′-s2c∗-c′-s4c∗-c′=0.
We setu1,u2=z1∗-z1′-s1c∗-c′-s3c∗-c′ and   z2∗-z2′-s2c∗-c′-s4c∗-c′.
As(s1,s2)<s2N and (s3,s4)<s2N with overwhelming probability, we can see that (u1,u2)≤4s2N+2λσ2N. Since c∗≠c′ and by Lemma 13, we can obtain (u1,u2)≠0. According to [13], the probability that challenger C can solve the R-SIS on the NTRU lattice is at least (1-2-ω(log⁡N))ε.


## 6. Comparisons

Table1 presents the comparisons among Tian and Huang’s IBS scheme [9], Xiang’s RIBS scheme [15], and our RIBS scheme in terms of lattice type, signing key size, signature size, computation cost of signing phase, computation cost of verifying phase, revocable functionality, and security property under the same system parameter N.Table 1
Comparisons between the existing IBS/RIBS schemes and our RIBS scheme.
Tian and Huang’s IBS scheme [9] Xiang’s RIBS scheme [15] Our RIBS scheme Lattice type GPV lattice [11] GPV lattice [11] NTRU lattice [14] Signing key size m k log ⁡ ( s ^ m ) 2Nmlog⁡n⋅log⁡(s-2m) 4 N log ⁡ ( s N ) Signature size m log ⁡ 12 σ ^ + λ ( log ⁡ k + 1 ) 3 N m log ⁡ n ⋅ log ⁡ ( s - 3 m ) 2 N log ⁡ 12 σ + λ ( log ⁡ N + 1 ) Computation cost of signing 7 ( N m + m k ) T m 2 N m T m + T s p 7 ( N 2 + 2 N ) T m Computation cost of verifying ( N m + N k ) T m 3 N m T m ( N 2 + N ) T m Revocable functionality No Secure channel Public channel Security property ID-UF-ACMA secure RID-UF-ACMA secure RID-UF-ACMA secure N: the security parameter; λ,k: positive integers; n: the number of users; m>6Nlog⁡q; s^=mω(log⁡N); s-=mlog⁡n⋅ω(log⁡N); s=N5/22qω(log⁡N)); σ^=12s^λ^m; σ=12λsN; Tm: the cost of executing a multiplication operation in Zq; Tsp: the cost of executing the Samplepre algorithm in [12].Both Tian and Huang’s IBS and Xiang’s RIBS schemes adopted the GPV lattice in [11] to generate a user’s signing key. In our scheme, we adopted the NTRU lattice in [14] to generate a user’s signing key. It is obvious that both the signing key and signature sizes of our scheme are less than those of both Tian and Huang’s IBS and Xiang’s RIBS schemes. For the computation cost of the signing phase, both Tian and Huang’s IBS scheme and ours use the rejection sampling technique to generate a signature, in which the rejection sampling technique would repeat the signing phase at average 7 times so that their total computation costs are, respectively, 7(Nm+mk)Tm and 7(N2+2N)Tm, where Tm is the cost of executing a multiplication operation in Zq. In Xiang’s RIBS scheme [15], a user runs the Samplepre algorithm in [12] to obtain a signature so that it requires 2NmTm+Tsp, where Tsp is the cost of executing the Samplepre algorithm. For the computation cost of the verifying phase, three schemes, respectively, require (Nm+Nk)Tm, 3NmTm, and (N2+N)Tm. Since m>6Nlog⁡q, it is clear that our scheme has better performance in terms of the computation costs for the signing and verifying phases. For the revocable functionality, Xiang’s scheme uses secure channels to send periodic signing keys to nonrevoked users, which causes enormous computation workload to encrypt/decrypt the periodic signing keys for the PKG and users. In contract, our revocation mechanism adopts public channels to send the periodic time update keys. Based on the short integer solution (SIS) assumption over lattices, we proved that the proposed RIBS scheme provides existential unforgeability against adaptive chosen-message attacks (RID-UF-ACMA) for a revoked user and an outside adversary. Since Tian and Huang’s IBS scheme did not provide a revocation mechanism, it was proven to be only ID-UF-ACMA secure.Table2 lists comparisons of the signing key and signature sizes under the parameters N=512,   q≈225,   k=512,   λ=14,   m=89600, and n=1000. It turns out, in both sizes, that our scheme performs much better than the other two schemes.Table 2
Comparisons of the concrete instances.
Tian and Huang’s IBS scheme [9] Xiang’s RIBS scheme [15] Our RIBS scheme Signing key size in bits 1087044742 8309006384 92419 Signature size in bits 1127039723 1238468290 54726 Parameters:N=512, q≈225, k=512, λ=14, m=89600, and n=1000.


## 7. Conclusions

In the article, we proposed a new RIBS scheme over NTRU lattice with a public channel. As compared to the existing IBS schemes over lattices, our RIBS scheme has better performance in terms of signature size, signing key size, and the revocation mechanism. Security analysis is made to prove that our RIBS scheme is existentially unforgeable under adaptive chosen-message attacks based on the SIS assumption in the random oracle model.



---

*Source: 7571201-2017-01-11.xml*