Printer Friendly

Scalable Revocable Identity-Based Signature Scheme with Signing Key Exposure Resistance from Lattices.

1. Introduction

Nowadays, dynamic management systems are becoming increasingly popular in enterprises and schools. A common operation in these systems is deleting users. Although many works with efficient revocation mechanisms have been proposed for public key cryptography, and only a few studies have been conducted on identity-based cryptography, which uses a user's identity as his/her public key. Boneh and Franklin [1] proposed an approach to revoke users in an identity-based setting, but this results in a heavy computation overhead at the key generation center (KGC). In order to reduce the KGC's overhead, Boldyreva et al. [2] employed a binary tree to propose the first scalable revocable identity-based encryption (RIBE) scheme, in which the overhead of the KGC is logarithmically increased based on the number of users. All subsequent scalable RIBE schemes [3-5] followed Boldyreva et al.'s basic framework and security model. However, in 2013, Seo and Emura [6] found that all existing Boldyreva-based scalable RIBE schemes are vulnerable to decryption key exposure. They then improved the definition and security model of RIBE and proposed the first scalable RIBE with decryption key exposure resistance. Meanwhile, they also introduced a new security definition of an RIBS with signing key exposure resistance and proposed the first scalable RIBS scheme. In 2013, Tsai et al. studied the revocation problem in identity-based signatures and proposed the first revocable identity-based signature (RIBS) scheme from bilinear pairings. All subsequent RIBS schemes [7-9] were constructed based on Tsai's definition and security model. Unfortunately, these RIBS schemes are also vulnerable to signing key exposure attacks. It is worth noting that the security of all abovementioned RIBS schemes are based on the traditional complexity problem, namely, the Diffie-Hellman problem. Hence, these schemes would not be secure against attacks from quantum computers. Lattice-based cryptography has many attractive features, and it is believed to be secure against attacks using quantum computers. In 2015, Xinyin [10] utilized a complete subtree structure to propose the first lattice-based RIBS scheme, which adopts secret channels to send periodic time update keys. Since the update keys are transmitted in a secret way, they can avoid signing key exposure. Recently, Hung et al. [11] employed the rejection sampling technique [12] to propose a new latticed-based RIBS scheme. Their scheme has a better performance in terms of signature size, signing key size,

and the revocation mechanism with public channels. However, the KGC's overhead increases linearly with the number of users, which results in issues with scalability. Moreover, their scheme cannot avoid signing key exposure. As far as we know, there is no lattice-based scalable RIBS scheme with signing key exposure resistance and the update keys are regularly sent over public channels.

1.1. Our Contributions. The main contributions of our paper are summarized as follows:

(1) We study the approach used to achieve signing key exposure resistance in Seo et al.'s RIBS scheme and adopt Agrawal et al.'s left-right lattices and delegation technology to propose the first lattice-based RIBS scheme with signing key resistance

(2) We then set all the parameters to ensure our construction's correctness and prove that our construction is selective-ID existentially unforgeable against chosen message attacks (EUF-sID-CMA) under the standard short integer solutions (SIS) assumption

(3) Our revocation mechanism employs Boldyreva et al.'s binary tree structure to meet scalability needs and ensures that the KGC does not need to send periodic time update keys over secret channels

1.2. Related Work

1.2.1. Revocable Identity-Based Encryption Schemes. In 1984, Shamir [13] first proposed the concept of an identity-based cryptosystem, which uses a user's identity as his/her public key. In 2001, Boneh and Franklin [1] proposed the first practical identity-based encryption (IBE) scheme. They also considered the revocation problem in an identity-based setting and presented an approach to revoke users, but this imposes a huge overhead on the KGC. In 2008, Boldyreva et al. [2] introduced a basic framework and security model for RIBE and proposed the first scalable RIBE scheme, which greatly reduces the KGC's overhead. However, their scheme is only selective-ID secure. Later, Libert and Vergnaud [3] proposed an adaptive-ID secure RIBE scheme. All of the above RIBE schemes are constructed based on parings. In 2012, Chen et al. [4] proposed the first lattice-based scalable RIBE scheme based on Boldyreva's definition and security model. In 2013, Seo and Emura [6] revisited all existing scalable RIBE schemes and found that all of them are vulnerable to decryption key exposure. They then introduced a new security definition for RIBE and proposed the first scalable RIBE scheme with decryption key exposure resistance. Since then, several RIBE schemes with decryption key exposure resistance [14-17] have been proposed that are built on bilinear groups. In 2017, Takayasu and Watanabe [18] proposed the first lattice-based RIBE scheme with bounded decryption key exposure resistance.

1.2.2. Revocable Identity-Based Signature Schemes. In 2013, Tsai et al. [7] proposed the first RIBS scheme based on bilinear pairings, which is EUF-CMA in a random oracle. Also relying on bilinear pairings, Hung et al. [9] proposed a strongly EUF-CMA secure RIBS scheme without a random oracle. Since the pairing computation is considered a rather expensive operation, Sun et al. [8] proposed an RIBS scheme without pairings. Aforementioned all RIBS schemes are not scalable or satisfying signing key exposure resistance. In 2013, Seo and Emura [6] introduced a new security definition of revocable identity-based signature (RIBS) with signing key exposure resistance and proposed the first scalable RIBS scheme based on the Paterson-Schuldt IBS. In order to improve the efficiency of key revocation, Liu et al. [19] proposed a strongly unforgeable RIBS scheme in the standard model, which can efficiently revoke users and resist key exposure attacks. Subsequently, Wei et al. [20] proposed an RIBS scheme with forward secure. Yang et al. [21] improved Hung et al.'s RIBS scheme [9] and also constructed an RIBS scheme in the standard model with strong unforgeability and signing key exposure resistance. And Zhao et al. [22] also proposed a communication-efficient RIBS scheme from multilinear maps. However, all of them cannot resist quantum attacks. In 2015, Xinyin [10] proposed an RIBS scheme based on lattices, but the revocable functionality channel is secret. Then, Hung et al. [11] proposed an RIBS scheme based on NTRU lattices, in which the KGC sends regular update keys in public channels. One limitation of their scheme is that it is vulnerable to decryption key exposure. Therefore, no lattice-based scalable RIBS schemes with signing key exposure resistance have been proposed so far.

The rest of the paper is organized as follows: in Section 2, we present some important preliminaries. In Section 3, we present the definition and security model of the RIBS. In Section 4, based on Agrawal et al.'s left-right lattices and delegation technology, we construct a concrete scalable RIBS scheme and prove that our construction meets the EUF-sID-CMA security standards. In Section 5, we give some comparisons with previous works in terms of functionalities. Section 6 concludes the paper.

2. Preliminaries

2.1. Notation. [Z.sub.q] is a ring of integers modulo q and represents integers in (-q/2,q/2], where q [greater than or equal to] 2. [Z.sup.nxm.sub.q] is a set of n x m matrices, in which the elements are in [Z.sub.q]. [parallel]x[parallel] denotes the Euclidean norm of a vector x. Matrix [A.sup.T] is the transpose of A, and [parallel]A[parallel] represents the norm of a matrix A which is defined as the largest norm of its columns. Given matrix B, [??] and [parallel][??][parallel] are B's Gram-Schmidt orthogonalization and Gram-Schmidt norm.

2.2. Lattices

Definition 1. Given prime q, A [member of [Z.sup.n x m.sub.q], and u [member of [Z.sup.n.sub.q] define following lattices:

[[LAMBDA].sup.[perpendicular].sub.q](A) = {y [member of [Z.sup.m]: Ay = 0 mod q},

[[LAMBDA].sup.u.sub.q](A) = {y [member of [Z.sup.m]: Ay = u mod q}. (1)

Let [[rho].sub.[sigma],c](x) [??] exp(-[pi][[parallel]x - c[parallel].sup.2]/[[sigma].sup.2]) be the standard Gaussian function with center c and variance a. For a lattice [LAMBDA] and all the [LAMBDA]'s points x, define the discrete Gaussian distribution over [LAMBDA] as [D.sub.[LAMBDA],[sigma],c](x) [??] [[rho].sub.[sigma],c](x)/[[rho].sub.[sigma],c]([LAMBDA]). For ease of notation, we use [D.sub.[LAMBDA],[sigma]] as [D.sub.[LAMBDA],[sigma],0]'s abbreviate.

The following lemma from [23, 24] is very useful for our construction.

Lemma 1. Given q [greater than or equal to] 2 and A [member of] [Z.sup.n x m.sub.q], [[LAMBDA].sup.[perpendicular].sub.q](A)'s basis [T.sub.A], s [greater than or equal to] [parallel][[??].sub.A][parallel][omega]([square root of (log m)]), Then, for [member of] [R.sup.m] and u [member of] [Z.sup.n.sub.q], algorithm SamplePre(A, [T.sub.A], u, s) outputs x [member of] [[LAMBDA].sup.u.sub.q](A) and its distribution is statistically close to [mathematical expression not reproducible] is not empty.

The following fact from [23] will be used in our security proof.

Lemma 2. (Given n, positive prime q, m [greater than or equal to] 2n log q, and s [greater than or equal to] [omega]([square root of (log m)]), u [??] Ae mod q's distribution is statistically close to [Z.sup.n x m.sub.q] uniform except with a [2q.sup.-n] fraction of all A [member of] [Z.sup.n x m.sub.q], where e is from [mathematical expression not reproducible].

2.3. Some Algorithms. We first recall an algorithm investigated by [24-26], which generates a random lattice A [member of] [Z.sup.n x m.sub.q] and [[LAMBDA].sup.[perpendicular].sub.q](A)'s short basis [T.sub.A].

Lemma 3. Given q [greater than or equal to] 2 and m [greater than or equal to] 6n log q, with overwhelming probability, TrapGen([1.sup.n], [l.sup.m], q) outputs (A [member of [Z.sup.n x m.sub.q], and its basis [T.sub.A] [member of] [Z.sup.mxm]), [parallel][[??].sub.A][parallel] [less than or equal to] O ([square root of (n log q)]), where A's distribution is statistically close to [Z.sup.n x m.sub.q]'s uniform.

The following lemma derived from [23] shows that the algorithm can convert any full-rank set of vectors in a lattice to a basis efficiently and meanwhile cannot increase the norm of the Gram-Schmidt vectors.

Lemma 4. Given a l-dimensional lattice A's arbitrary basis B and a full-rank set S [member of] [LAMBDA], there exist a deterministic algorithm that can convert S to T and for all i [member of] [l], [parallel][[??].sub.i][parallel] [less than or equal to] [parallel][[??].sub.i][parallel], where T is a basis of [LAMBDA].

Another two algorithms in [27] will be used to construct and prove our following scheme, respectively.

Lemma 5. Given q [greater than or equal to] 2, m [greater than or equal to] n, and s [greater than or equal to] [parallel][[??].sub.A][parallel]. [omega] ([square root of (log(m + [m.sub.1]))], algorithm SampleLeft (A, B, [T.sub.A], u, s) outputs a vector [mathematical expression not reproducible] distributed statistically close to [mathematical expression not reproducible].

Lemma 6. Given q > 2, m > n, and s > [parallel][[??].sub.TB][parallel] * l * [s.sub.R] * [omega] ([square root of (log m)]), algorithm SampleRight (A, B, [R.sub.1], [T.sub.B], u, s) outputs a vector e [member of] [Z.sup.m+k] distributed statistically close to [mathematical expression not reproducible]. The following two algorithms from [28] will be also used to construct and prove our following scheme respectively.

Lemma 7. Given a rank n matrix A [member of [Z.sup.n x m.sub.q], a [Z.sub.q]-invertible matrix R [member of] [Z.sup.mxm] sampled from [D.sub.mxm], a basis [T.sub.A] of [[LAMBDA].sup.[perpendicular].sub.q] (A), and a parameter s [member] [R.sub.>0]. Algorithm BasisDel(A, R, [T.sub.A], s) outputs a basis [T.sub.B] of [[LAMBDA].sup.[perpendicular].sub.q] (B), where B = [AR.sup.-1].

Lemma 8. Let m > 2n log q and q > 2 be a prime. For all but at most a [q.sup.-n] fraction of rank n matrix A [member of] [Z.sup.n x m.sub.q], algorithm SampleRwithBasis (A) outputs a matrix R [member of [Z.sup.mxm] sampled from a distribution statistically close to [D.sub.mxm]. The generated basis [T.sub.B] of [[LAMBDA].sup.[perpendicular].sub.q] ([AR.sup.-1]) satisfies [parallel][[??].sub.B][parallel] [less than or equal to] [square root of (n log q)] with overwhelming probability.

2.4. Norm of Random Matrix. The following definition from [28] defines a distribution on matrices with low norm and defines an algorithm to sample these matrices.

Definition 2. We say that a matrix R in [Z.sup.mxm] is [Z.sub.q]-invertible if R mod q is invertible as a matrix in [Z.sup.mxm.sub.q]. Define [[alpha].sub.R] [??] [square root of (n log q)] * [omega] ([square root of (log m)]). We let [D.sub.mxm] denote the distribution on matrices in [mathematical expression not reproducible] with the condition that R [member of] [Z.sub.q]-invertible and meanwhile [parallel]R[parallel] [less than or equal to] [[alpha].sub.R] * [square root of (m)]. Algorithm SampleR([1.sup.m]) samples matrices in [Z.sup.mxm] and their distributions are statistically close to [D.sub.mxm].

2.5. Small Integer Solution Problem

Definition 3 (SIS). For any n [member of] Z and any function m [??] m(n),q [??] q(n), and [beta] [??] [beta](n), given an integer q, a uniform and random matrix A [member of [Z.sup.nxm.sub.q] and a real number [beta] [member of] R, the average-case [SIS.sub.q,n,m,[beta] is the problem of finding a nonzero integer vector s [member of] [Z.sup.m]\{0} satisfying As = 0 mod q and [parallel]s[parallel] [less than or equal to] [beta].

It has been proved by Micciancio and Regev [29] that for certain parameters, the average-case [SIS.sub.q,n,m,[beta] problem is as hard as approximating to the worst-case shortest independent vector problem within certain [gamma] = [beta] * [??] ([square root of (n)]) factors.

2.6. Encoding Identities or Times as Matrices. In our following scheme, we use an injective encoding function H: [Z.sup.n.sub.q] [right arrow] [Z.sup.nxn.sub.q] to map identities or times in [Z.sup.n.sub.q] to matrices in [Z.sup.nxn.sub.q], whose concrete construction can be found in [27].

Definition 4. Given a prime q and a positive integer n, H: [Z.sup.n.sub.q] [right arrow] [Z.sup.nxn.sub.q] which is an encoding with full-rank differences (FRD) that satisfies the following:

(1) H(u) - H(v) [member of [Z.sup.nxn.sub.q] is full rank for all distinct u, v [member of [Z.sup.n.sub.q]

(2) H is a polynomial computable function in n log q

3. Definition of RIBS Scheme

In this section, we give the formal definition of the syntax and the security model of RIBS derived in [6]. First, we give the syntax of the RIBS scheme. An RIBS scheme consists of seven algorithms (Setup, PriKeyGen, KeyUpd, SignKeyGen, Sign, Verify, and KeyRev). Let U, I, and T be a message space, an identity space, and a time space, respectively.

Definition 5 (syntax of RIBS).

Setup ([1.sup.[lambda], N) takes a security parameter [lambda] and a maximal number of users N as input and outputs the public parameters PP which includes the message space U, a master secret key MSK, a revocation list RL (initially empty), and a state ST. This is a stateful algorithm and run by the key authority.

PriKeyGen (PP, MSK, id) takes the public parameters PP, the master secret key MSK, and an identity id [member of] I as input and outputs a private key SKid and an updated state ST. This is stateful and also run by the key authority.

KeyUpd(PP, MSK, t, RL, and ST) takes the public parameters PP, the master secret key MSK, a time t [member of] T, the current revocation list RL, and the state ST as input and outputs a update key [KU.sub.t]. This is run by the key authority.

SignKeyGen ([SK.sub.id], [KU.sub.t]) takes a private key [SK.sub.id] and an update key [KU.sub.t] as input and outputs a signing key [SK.sub.id,t] or a special symbol [perpendicular] indicating that id was revoked. This is a probabilistic algorithm and run by the signer.

Sign(PP, id, t, [SK.sub.id,t], an [micro]y) takes the public parameters PP, an identity id [member of] I, a time t [member of] T, a signing key [SK.sub.id,t], and a message [mu] [member of] U as input and outputs a signature [sigma].

Verify (PP, id, t, [mu], and [sigma]) takes the public parameters PP and an identity id [member of] I, a time t [member of] T, and a message/ signature pair ([mu], [sigma]) as input and outputs 1 (accept) or 0 (reject).

KeyRev (id, t, RL, and ST) takes a revoked identity id [member of] I, a time t [member of] T, a revocation list RL, and a state ST as input and outputs an updated revocation list RL. This is stateful and run by the key authority.

3.1. Correctness. The correctness requires that for all [lambda] [member of] N, polynomials N, all (PP, MSK) output by Setup, all [mu] [member of] U, id [member of] I, t [member of] T, and all possible valid states ST and revocation lists RL, if identity id is not revoked in time t, then for ([SK.sub.id], ST) [left arrow] PriKeyGen (PP, MSK, id), [KU.sub.t] [left arrow] KeyUpd (PP, MSK, t, RL, ST), and [SK.sub.id,t] [left arrow] SignKeyGen([SK.sub.id], [KU.sub.t]), it has Verify (PP, id, t, [mu], [sigma] [left arrow] Sign(PP, id, t, [SK.sub.id,t], [mu])) = 1.

Next, we provide a security definition of the RIBS scheme that captures realistic threats including signing key exposure.

Definition 6 (EUF-sID-CMA). The selective-ID essential unforgeable against chosen message attacks (EUF-sID-CMA) security model of the RIBS scheme is defined via the following game between an adversary A and a challenger C. Initial: the adversary A first outputs the challenge identity [id.sup.*], time [t.sup.*], and also some information state it wants to preserve.

Setup: the challenger runs Setup to generate public parameters PP, a master secret key MSK, a revocation list RL (initial empty), and a state ST. It gives PP to the adversary and keeps MSK secret. Query: A may make some queries as follows:

(i) PriKeyGen Query: on receiving a private key query, the challenger runs PriKeyGen to return a private key to A

(ii) Key Update Query: on receiving an update key query, the challenger runs KeyUpd to return an update key [KU.sub.t] to A

(iii) Revocation Query: on receiving a revocation query, the challenger runs KeyRev to return an update list RL to A

(iv) SignKeyGen Query: on receiving a signing key query for an identity and a time, the challenger runs PriKeyGen and KeyUpd to return a signing key to A

(v) Signature Query: on receiving a signature query for a chosen message, an identity, and a time, the challenger runs Sign to return a signature to A

Forgery: at the end of the game, A outputs a forgery of a message/signature pair on the behalf of the identity [id.sup.*] in the time period [t.sup.*].

If A satisfies the following four conditions, then it wins the above game:

(i) Verify (PP, [id.sup.*], [t.sup.*], [[mu].sup.*], [[sigma].sup.*]) = 1

(ii) Key Update Query and Revocation Query can be queried on time which is greater than or equal to the time of all previous queries

(iii) Revocation Query cannot be queried on time t if Key Update Query was queried on t

(iv) If PriKeyGen Query was queried for identity [id.sup.*], then the Revocation Query must be queried for identity [id.sup.*] on time t [less than or equal to] [t.sup.*]

(v) SignKeyGen Query cannot be queried on time t before Key Update Query was queried on t

(vi) SignKeyGen Query cannot be queried for identity [id.sup.*] on time [t.sup.*]

(vii) Signature Query cannot be queried for challenge message [[mu].sup.*] under identity [id.sup.*] on time [t.sup.*]

The probability of winning the above game is the advantage of A. If there does not exist any PPT adversary who has nonnegligible advantage in the above game, then the RIBS scheme is EUF-sID-CMA secure.

4. Our Scalable RIBS Scheme

In our RIBS scheme, a user's signing key is generated from a private key and periodical update key. The PKG periodically generates update keys and sends them to the nonrevoked users. After obtaining the update keys, the nonrevoked users can generate a valid signing key with their private key. In the process of constructing our RIBS, it is a challenging technical difficulty that a valid signing key should be guaranteed as a certain lattice space's short basis which is used as a trapdoor to sample vectors. In order to solve this difficulty, we improve the preimage sampling algorithm and redefine it as the SampleSubInv algorithm. Therefore, in the following, we first introduce the SampleSubInv algorithm and then we give the concrete construction of RIBS and provide the process of proving its security. Throughout the section, the function [H.sub.0] refers to the FRD map [H.sub.0]: [Z.sup.n.sub.q] [right arrow] [Z.sup.nxn.sub.q] (if id [member of] [{0,1}.sup.*], it can be hashed into [Z.sup.n.sub.q] by using a collision resistant hash). Hash function [H.sub.1] is a random oracle that outputs matrices in [Z.sup.3mx3m], name1y, [H.sub.1]: [{0,1}.sup.*] [right arrow] [Z.sup.3mx3m]: t [right arrow] [H.sub.1](t) ~ [D.sub.3mx3m].

4.1. SampleSubInv Algorithm. Algorithm SampleSubInv (A, M, [T.sub.A], U, and s): the algorithm takes a rank n matrix A [member of] [Z.sup.n x m.sub.q], a matrix M [member of] [Z.sup.mxm], a basis [T.sub.A] of [[LAMBDA].sup.[perpendicular].sub.q] (A), a matrix U = ([u.sub.1], ..., [u.sub.m]) [member of] [Z.sup.n x m.sub.q], and a parameter s [member of] [R.sub.>0] as input and works as follows:

(1) Let M = ([e.sub.1], ..., [e.sub.m]), for i = 1, ..., m do

(1a) Sample [t.sub.i] [member of] [Z.sub.m] as the output of SamplePre (A, [T.sub.A], [u.sub.i], s), then A[t.sub.i] = [u.sub.i] mod q and [t.sub.i] is sampled from a distribution statistically close to [mathematical expression not reproducible]

(1b) If [t.sub.i] - [e.sub.i] is linearly independent of {[t.sub.1] - [e.sub.1], ..., [t.sub.i-1] - [e.sub.i-1]}, accept [t.sub.i]. Otherwise, repeat step (1a)

(2) Let T [member of] [Z.sup.mxm] be the matrix whose columns are [t.sub.1], ..., [t.sub.m]. Output T

Note that AT = U, and matrix T - M is invertible. The analysis of algorithm SampleSubInv uses Corollary 3.16 of literature [30] which shows that a linearly independent set is produced in step (1a) w.h.p. after [m.sup.2] samples from SamplePre (A, [T.sub.A], [u.sub.i], s). It is not difficult to show that only 2m samples are needed in expectation.

4.2. Construction. Our concrete scalable RIBS scheme with signing key resistance works as follows:

Setup ([1.sup.[lambda]], N): the setup algorithm takes a security parameter [lambda] and a maximal number of users N as input and proceeds as follows:

(1) Pick Gaussian parameters [s.sub.1], [s.sub.2], and [s.sub.3] and set the parameters n = n([lambda]), q = q(n), and m = m(n). These parameters are implicitly known to all of the algorithms below.

(2) Sample l + 3 random matrices: [A.sub.1], [A.sub.2], B, [{[D.sub.i]}.sub.i[member of][l]] in [Z.sup.n x m.sub.q], where l is the length of message.

(3) Sample matrix with associated trapdoor: (A, [T.sub.A]) [left arrow] TrapGen ([1.sup.n], [1.sup.m], q).

(4) Output public parameters PP = (A, [A.sub.1], [A.sub.2], B, [{[D.sub.i]}.sub.i[member of][l]]), master secret key MSK = [T.sub.A], a revocation list RL = [empty set], and a state ST = BT.

PriKeyGen(PP, MSK, id, and ST): this algorithm takes as input the public parameters PP, a master secret key MSK, an identity id [member of] [{0,1}.sup.*], and a state ST. Then it picks an unassigned leaf node v from BT, stores id in that node, and performs the following steps:

(1) For each node [theta] [member of] Path(v), pick random matrix [U.sub.[theta]] [member of] [Z.sup.nxm.sub.q] and store it in node [theta]

(2) Sample [R.sub.1] [left arrow] [D.sub.mxm], [E.sub.v] [left arrow] SamplePre (A, [T.sub.A], -([A.sub.1] + [H.sub.0](id)B)[R.sub.1], [s.sub.1])

(3) Sample [mathematical expression not reproducible]

(4) Store [H.sub.[theta] [??] [E.sub.[theta],1] - [E.sub.v] [R.sup.-1.sub.1][E.sub.[theta],2] in node [theta]

(5) Output private key [mathematical expression not reproducible]

KeyUpd(PP, MSK,t, RL, and ST): this algorithm takes the public parameters PP, a master secret key MSK, a time t [member of] [{0,1}.sup.*], a revocation list RL, and a state ST as input and proceeds as follows:

(1) Sample [R.sup.2] [left arrow] [D.sub.mxm] and [E.sub.t] [left arrow] SamplePre (A, [T.sub.A], - ([A.sub.2] + [H.sub.0](t)B)[R.sub.2], [s.sub.1])

(2) [for all][theta] [member of] KUNodes (BT, RL, and t) and sample [mathematical expression not reproducible] and compute [H'.sub.[theta] = [E.sub.t][R.sup.-1.sub.2][E'.sub.[theta,2], where KUNodes (BT, RL, and t) is an algorithm KUNodes from [4]

(3) Sample [E'.sub.[theta],1] [left arrow] SampleSubInv (A, [H'.sub.[theta]] - [H.sub.[theta]], [T.sub.A], -[U.sub.[theta]] - ([A.sub.2] + [H.sub.0](t)B)[E'.sub.[theta],2], [s.sub.1])

(4) Output update key [mathematical expression not reproducible]

SignKeyGen ([SK.sub.id] and [KU.sub.t]): this algorithm takes a private key [SK.sub.id] and an update key [KU.sub.t] as input and runs the following steps:

(1) Set [A.sub.id,t] [??] (A | [A.sub.1] + [H.sub.0] (id)B | [A.sub.2] + [H.sub.0] (t)B) and compute [Ri.sub.d,t] = [H.sub.1] (id | t) and [F.sub.id,t] [??] [A.sub.id,t] * [R.sup.-1.sub.id,t]

(2) [mathematical expression not reproducible] if [there exists] = j, then set

[mathematical expression not reproducible]. (2)

(3) Generate [SK'.sub.id,t] by running Lemma 4 which takes [S.sub.id,t] as input ([S.sub.id,t] is an invertible matrix with some norm which will be proved in the Theorem 1). Then, run the algorithm BasisDel([A.sub.id,t], [R.sub.id,t], [SK'.sub.id,t], [s.sub.2]) to generate SKidt and output [SK.sub.id,t].

Sign(PP, id, t, [SK.sub.id,t], and [mu]): the signing algorithm takes the public parameters PP, an identity id, a time t, a signing key [SK.sub.id,t], and a message [mu] = ([mu](1), ...., [mu](l)) [member of] [{0,1}.sup.l] as input and outputs signature a as follows:

(1) Sample the algorithm [sigma] [left arrow] SampleLeft([F.sub.id,t], B + [[summation].sup.l.sub.i=1][(- 1).sup.[mu](i)] [D.sub.i], [SK.sub.id,t], 0, [s.sub.3]) such that ([F.sub.id,t] | B + [[summation].sup.l.sub.i=1] [(-1).sup.[mu](i)] [D.sub.i]) * [sigma] = 0, where [s.sub.3] [greater than or equal to] [parallel][[??].sub.id,t][parallel] * [omega] ([square root of (log 4 m)])

(2) Output signature [sigma]

Verify (PP, id, t, [mu], and [sigma]): the verify algorithm takes the public parameters PP, an identity id [member of] [{0,1}.sup.*], a time t [member of] [{0,1}.sup.*], and a pair of message/signature ([mu], [sigma]) as input and accepts only if the following conditions are satisfied:

(i) [sigma] [member of] [Z.sup.4m], [parallel][sigma][parallel] [less than or equal to] [s.sub.3] [square root of (4m)]

(ii) [[F.sub.id,t] | B + [[summation].sup.l.sub.i=1] [(-1).sup.[mu](i)] [D.sub.i]] * [sigma] = 0

KeyRev(id, t, RL, and ST): this algorithm takes a revoked identity id, a time t, a revocation list RL, and a state ST as input and adds (id, t) to RL for all nodes v associated with identity id and returns RL.

Theorem 1. [S.sub.id,t] is an invertible matrix with small norm.

Proof. First, we show that [S.sub.id,t] is a small norm matrix. From the construction, we know that

[mathematical expression not reproducible], (3)

which are small norm matrices. Then, we can get [parallel][S.sub.id,t][parallel] [less than or equal to] max{4[s.sub.1] [square root of (m)], [square root of (m)] ([s.sub.1] + [[alpha].sub.R])}. Second, we will show [parallel]Sid t[parallel] < max{4[s.sub.1] [square root of m], [square root of m] ([s.sub.1] + [[alpha].sub.R])}. Second, we will show [S.sub.id,t] is an invertible matrix. For matrix [S.sub.id,t], we make an elementary transformation and finally obtain

[mathematical expression not reproducible]. (4)

Since [E.sub.i,1] + [E'.sub.j,1] - [E.sub.v][[R.sup.-1.sub.1][E.sub.i,2] - [E.sub.t][R.sup.-1.sub.2][E'.sub.j,2] = [E'.sub.j,1] - (H'.sub.j] - [H.sub.i]), and by the SampleSubInv algorithm in the KeyGen phase, we can see [E'.sub.j,1] - ([H'.sub.j] - [H.sub.i]) is an invertible matrix. Because [R.sub.1] and [R.sub.2] are [Z.sub.q]-invertible matrices, then C is invertible and then [S.sub.id,t] is an invertible matrix. In summary, [S.sub.id,t] is an invertible matrix with small norm.

The correctness equality in Verify follows from the SampleLeft algorithm. In order to ensure the correctness and security of the above construction, we set the following: [mathematical expression not reproducible] is the security parameter.

4.3. Security. The following theorem shows that our scalable RIBS scheme is secure.

Theorem 2. The construction of the scalable RIBS scheme is EUF-sID-CMA secure provided that the [SIS.sub.q,n,m,[beta]] assumption holds.

Proof. Assume A wins the game in Section 3 and Q is the signing queries maximum number. We can construct a solver B that provides a valid solution to the SIS problem. A first gives the target identity and time ([id.sup.*], [t.sup.*]). B is given a random instance of the (q, n, m, and [beta])-SIS problem and is asked to return an admissible solution. That is,

(i) Provided: a matrix [A.sub.0] from [Z.sup.nx3m.sub.q]'s uniform distribution

(ii) Returned: any vector [e.sub.0] [member of] [Z.sup.3m] such that [A.sub.0][e.sub.0] = 0 mod q and 0 [not equal to] [parallel][e.sub.0][parallel] [less than or equal to] [beta]

B performs as follows:

[Setup.sup.*] ([1.sup.[lambda]], N, l): B provides the adversary A with simulated parameters as follows:

(1) Run algorithm TrapGen to obtain (B, [T.sub.B])[left arrow] TrapGen ([1.sup.n], [1.sup.m], q)

(2) Choose l + 3 random matrices [mathematical expression not reproducible] n and also choose l random scalars [h.sub.i] [member of] [Z.sub.q] for i [member of] [l]. Let [mathematical expression not reproducible],

[A.sub.1] = A[U.sub.1] - [H.sub.0]([id.sup.*])B mod q,

[mathematical expression not reproducible]

(3) Output the parameters PP = (A, [A.sub.1], [A.sub.2], B, and [{D.sub.i]}.sub.i[member of][l]])

PriKeyGen Query and Key Update Query: B first picks a node [v.sup.*] [member of] BT and allots it to [id.sup.*]. It is worth noting that there will be two types of adversaries:

(i) Type (a) adversaries are revoked users and can challenge the target identity [id.sup.*] before or on time [t.sup.*]

(ii) Type (b) adversaries cannot challenge the target identity [id.sup.*] at any time

B picks a bit [rev.sup.$] [left arrow] {0,1} randomly as a guess for the type of adversarial behavior. Clearly, the probability of B's correct guesses is 1/2. Type (a) adversaries (rev = 0): B simulates each node [theta]'s matrix [U.sub.[theta]] as follows:

(i) if [theta] [member of] Path ([v.sup.*]), sample [mathematical expression not reproducible]. Compute [mathematical expression not reproducible].

[R.sup.-1.sub.1][E.sub.[theta],2], and store [H.sub.[theta]], [U.sub.[theta]] in the node [theta].

(ii) if [mathematical expression not reproducible]. Store [U.sub.[theta]] in the node [theta].

Since [id.sup.*] has been revoked before time [t.sup.*], it has [mathematical expression not reproducible].

Type (b) adversaries (rev = 1): B simulates each node [theta]'s matrix [U.sub.[theta]] as follows: Since [id.sup.*] is never queried, B does not need to simulate [id.sup.*]'s private key. It samples [mathematical expression not reproducible]. It stores [U.sub.[theta]] in the node [theta]. If t = [t.sup.*], B returns [t.sup.*]'s update key [mathematical expression not reproducible]. Note that, when rev = 0, for each node [theta], [U.sub.[theta]] is generated either through [mathematical expression not reproducible]. Since the distribution of [A | [A.sub.1] + [H.sub.0] ([id.sup.*])B] = [A| A[U.sub.1]] and [A | [A.sub.2] + [H.sub.0] ([t.sup.*])B] = [A | A[U.sub.2]] are statistically close to [Z.sup.n*2m.sub.q]'s uniform distribution by leftover hash lemma, then all the above [U.sub.[theta]] are statistically close to uniform over [Z.sup.n x m.sub.q]; when rev = 1, for each node [theta], [U.sub.[theta]] is generated either through or through uniform distribution in [mathematical expression not reproducible]. No matter which case, we can have [mathematical expression not reproducible]. Since the distribution of [R.sub.1] and [R.sub.2] are Gaussian distribution, then the distribution of [mathematical expression not reproducible] is statistically close to Gaussian distribution. In conclusion, the distribution of the simulated system is statistically close to the real system.

For id [not equal to] [id.sup.*]'s private key queries and t [not equal to] [t.sup.*]'s update key queries, B uses the trapdoor [T.sub.B] instead of [T.sub.A]. Let [A | [A.sub.1] + [H.sub.0] (id)B] = [A | A[U.sub.1] + ([H.sub.0] (id) - [H.sub.0] ([id.sup.*]))B] and [A | [A.sub.2] + [H.sub.0] (t)B] = [A | A[U.sub.2] + ([H.sub.0] (t) - [H.sub.0] ([t.sup.*]))B]. From the definition of FRD, [H.sub.0](id)- [H.sub.0]([id.sup.*]) and [H.sub.0](t) - [H.sub.0]([t.sup.*]) are nonsingular. Then, B runs the sampleRightExt algorithm and generates id [not equal to] [id.sup.*]'s private key

[mathematical expression not reproducible], (5)

where [mathematical expression not reproducible]. Moreover, B samples [R'.sub.1] [left arrow] [D.sub.mxm] and calls algorithm RandBasis([T.sub.B], [s.sub.4]) from [28]. It can obtain [mathematical expression not reproducible] where [s.sub.4] [greater than or equal to] [parallel][[??].sub.B][parallel] * [omega]([square root of (log n)]), that is, A * (-[U.sub.1][T'.sub.B][R'.sub.1]) = - ([A.sub.1] + [H.sub.0] (id)B)[T'.sub.B][R'.sub.1]. Then, it [mathematical expression not reproducible]. For all t [not equal to] [t.sup.*]'s update key queries, B runs

[mathematical expression not reproducible], (6)

where [mathematical expression not reproducible]. Moreover, it samples [R'.sub.2] [left arrow] [D.sub.mxm] and then calls algorithm RandBasis ([T.sub.B], [s.sub.4]) to get a basis [mathematical expression not reproducible]. It sets [E.sub.t] = -[U.sub.2][T".sub.B] [R'.auv.2] and [R.sub.2] = [T".sub.B][R'sub.2], and then generates the update key [mathematical expression not reproducible].

Since the parameter [s'.sub.2] is sufficiently large, [E.sub.[theta],1]'s distribution is statistically close to [mathematical expression not reproducible] distribution is statistically close to [mathematical expression not reproducible]. [E.sub.[theta],2] and [E'.sub.[theta],2]'s distribution are distributed close to [mathematical expression not reproducible], respectively. Since [T'.sub.B] and [T".sub.B] are the random bases of [[LAMBDA].sup.[perpendicular].sub.q] (B), then [E.sub.v] = -[U.sub.1][T'.sub.B][R'.sub.1] and [E.sub.T] = -[U.sub.2][T".sub.B][R'.sub.2]'s distributions are the same as those in the real system. [R.sub.1] = [T'.sub.B][R'.sub.1] and [R.sub.2] = [T'.sub.B][R'.sub.2] are [Z.sub.q]-invertible, that is, [R.sub.1] and [R.sub.2] are distributed as in the real system.

4.3.1. Signing Key Query. B first samples a random matrix [R.sup.*] ~ [D.sub.mxm] and defines [H.sub.1] ([id.sup.*] | [t.sup.*]) [??] [R.sup.*]. Then, it sets [mathematical expression not reproducible] and picks an empty list L. If the adversary A asks the signing key on identity [id.sup.*] and time t [not equal to] [t.sup.*], B runs SampleRwithBasis(G) to obtain a random [mathematical expression not reproducible] and a short basis [mathematical expression not reproducible] modq. Then, it saves the tuple ([mathematical expression not reproducible]) in list L for future use and returns [mathematical expression not reproducible] to the adversary A. If the adversary A asks the signing key on identity id [not equal to] [id.sup.*] and time t, B retrieves the list L and checks whether i d|t in L. If ([mathematical expression not reproducible]) is in L, B returns [mathematical expression not reproducible] to A. Otherwise, B also runs SampleRwithBasis (G) to obtain a random [mathematical expression not reproducible]. Then, it saves the tuple ([mathematical expression not reproducible]) in list L for future use and returns [mathematical expression not reproducible] to the adversary A. In the real SignKeyGen phase, the signing keys are generated by using algorithm BasisDel. In the Simulated signing key queries, the signing keys are generated from algorithm SampleRwithBasis. By Lemma 7 and 8, the responses to [H.sub.1] oracle queries and signing key queries are as in the real system.

4.3.2. Signature Queries. B simulates signatures of messages [mu] for A's adaptive signature queries as follows:

(i) If the queried messages [mu] are under target identity [id.sup.*] in target time [t.sup.*], B answers as follows:

(1) Compute [mathematical expression not reproducible]

(2) If [h.sub.[mu]] = 0 (mod q), abort the simulation

(3) Otherwise sample vector:

[sigma] [left arrow] SampleRight([A.sub.0], [h.sub.[mu]] B, [R.sub.[mu]], [T.sub.B], 0, [s'.sub.2]. (7)

(4) Output [sigma] [member of] [Z.sup.4m]

(ii) If the queried messages p are under identity id [not equal to] [id.sup.*] or in time t [not equal to] [t.sup.*], B first retrieves the list L and checks whether it has tuple ([mathematical expression not reproducible]). If yes, B gets [mathematical expression not reproducible] and samples vector [sigma] [left arrow] SampleLeft ([mathematical expression not reproducible]). Otherwise, B also runs SampleRwithBasis (G) to obtain a random [mathematical expression not reproducible] and a short basis [mathematical expression not reproducible] modq. Then, it saves the tuple ([mathematical expression not reproducible]) in list L and uses [mathematical expression not reproducible]. At last, B returns [sigma] to the adversary A.

Forgery: B obtains a forged signature [[sigma].sup.*] on an unqueried message [[mu.sup.*] and performs the following:

(1) Compute [mathematical expression not reproducible]

(2) If [mathematical expression not reproducible] (mod q), abort the simulation

(3) Otherwise, separate [[sigma].sup.*] = [([[sigm].sup.*T.sub.1] | [[sigma].sup.*T.sub.2].sup.T]

(4) Output [mathematical expression not reproducible]

From Lemma 9, [e.sub.0] is small and nonzero with good probability and is a valid (q, n, m, [beta])-SIS solution with good probability.

Lemma 9. If A provides a valid forgery [mathematical expression not reproducible] (mod q), then for polynomial function [mathematical expression not reproducible].

Proof. First, when [mathematical expression not reproducible], we have [mathematical expression not reproducible]. Since [[sigma].sup.*] is message [[mu].sup.*]'s valid signature under identity [id.sup.*] in time [t.sup.*], then we can obtain

[mathematical expression not reproducible]. (8)

Next, we will show that [e.sub.0] is appropriately short. Since [mathematical expression not reproducible] is the sum of l low-norm matrices [mathematical expression not reproducible] are nearly independent with the same variance V{[R.sup.*.sub.1]} and their coefficients are in {0,1}, then we will have

[mathematical expression not reproducible]. (9)

In particular, since they are almost independent discrete Gaussian, [mathematical expression not reproducible]. With overwhelming probability [parallel][e.sub.0][parallel] [less than or equal to] [beta] for [beta] = poly(l, n, m) = poly([lambda]), we set [beta] = (1 + [eta][square root of (l)] [square root of (3m)]) [square root of (4m)] * [s.sub.3].

Finally, it remains to show that [e.sub.0] [not equal to] 0. Suppose an easy case that [[sigma].sup.*.sub.2] = 0, then for a valid forgery, it must have [[sigma].sup.*.sub.1] [not equal to] 0, thus [e.sub.0] [not equal to] 0. On the contrary, [[sigma].sup.*.sub.2] [not equal to] 0, since [parallel][[sigma].sup.*.sub.2][parallel] < [square root of (4m)] * [s.sub.2] [much less than] q; thus, there must be at least one [[sigma].sup.*.sub.2]'s coordinate that is nonzero modulo q. We set z be [[sigma].sup.*.sub.4]'s last one coordinate. Let [r.sup.*] be [mathematical expression not reproducible]'s last column and [r.sup.*.sub.i] be [R.sup.*.sub.i]'s last column for each i [member of] [l]. Then, we have [mathematical expression not reproducible], where the coefficients depend on the message bits. For [r.sup.*.sub.1], let [mathematical expression not reproducible] does not. The only information about [r.sup.*.sub.1] available to A is contained in the last column of [D.sub.1]'s last column. From a simple pigeonhole principle, there exists many admissible and equally likely vector [r.sup.*.sub.1] that are the same with A's view. A cannot know the value of z[r.sup.*.sub.1] with probability exceeding once third, then every other z[r.sup.*.sub.1] would fail to do so. Thus, Pr{[e.sub.0] [not equal to] 0} [greater than or equal to] [1/2.sup.m(m-1)]. If A forges a signature with probability [epsilon] with Q [less than or equal to] q/2, then the algorithm B can solve the SIS (n, m, q, [beta]) problem with the advantage of [1/2.sup.m(m-1)] (1/2) * [epsilon] (1 - [q.sup.-1] [greater than or equal to] [epsilon]/3q.

We will show that the simulation (without aborting) is statistically indistinguishable from the real system.

The differences of the algorithms are summarized as follows:

(i) In real Setup, matrix A [member of] [Z.sup.n x m.sub.q] is sampled from the algorithm TrapGen. Matrices ([A.sub.1], [A.sub.2], B, and [{[D.sub.i]}.sub.i[member of][l]]) are chosen uniformly at random. In simulated [mathematical expression not reproducible]

(ii) In the real Sign phase, algorithm SampleLeft generates signatures [sigma], whereas in the simulated Sign phase, signatures are generated by algorithm SampleLeft or algorithm SampleRight

We now argue that the distribution (A, [A.sub.1], [A.sub.2], B, [{[D.sub.i]}.sub.i[member of][l]]) is statistically indistinguishable in the two experiments. Let

A' = [[A.sub.1]|[A.sub.2]|[D.sub.1]| ... |[D.sub.l]] [member of] [Z.sup.n*(l+2)m.sub.q]. (10)

Then, from Lemma 2, we have

(A, A') s = (A, [A[U.sub.1] - [H.sub.0] ([id.sup.*])B | A[U.sub.2] - [H.sub.0] ([t.sub.*])B | A[R.sup.*.sub.1] + [h.sub.1]B | ... | A[R.sup.*.sub.l] + [h.sujb.l]B]), (11)

for random matrices A, A' from [Z.sup.n x m.sub.q], [Z.sup.n*(l+2)m and.sub.q] and

[mathematical expression not reproducible], (12)

chosen at random. Here, B's distribution is statistically close to [Z.sup.n x m.sub.q]'s uniform distribution. Therefore, the distribution of PP in the simulation is statistically indistinguishable to them in the real system.

For each [mu]'s signature query, if Gaussian parameters [s.sub.3] and [s'.sub.3] are sufficiently large, then the outputs' distributions of SampleLeft and SampleRight are statistically close.

At last, since the SIS problem is as hard as approximating to the worst-case shortest independent vector problem from [29], the adversary A cannot succeed in attacking our scalable RIBS scheme.

5. Comparisons

This section will be divided into two parts to evaluate the performance of our RIBS scheme: first efficiency and second functionality.

5.1. Efficiency Comparisons. Here, we emphasis that since our scheme is built upon lattices, which is different from other listed schemes ([20-22]) based on bilinear maps or 3-linear maps, the running times in our scheme and in other listed map-based schemes may be different. Thus, when we discuss the computation cost, we only focus on the number of the corresponding operations and give comparisons with the lattice-based schemes ([10, 11]). First, since in scheme [11], the authors adopted the ideal lattice (NTRU lattice) to generate a user's signing key, it is obvious that both the signing key and signature sizes of their scheme are less than those of both Xiang's RIBS [10] and ours RIBS schemes. Next, for the computation cost of signing, in Xiang's RIBS scheme, it requires 2Nm[T.sub.m] + [T.sub.sp] to obtain a signature, where [T.sub.sp] is the cost of executing the SamplePre algorithm. In scheme [11], it requires 7([N.sup.2] + 2N)[T.sub.m] to obtain a signature, where [T.sub.m] is the cost of executing a multiplication operation in [Z.sub.q]. In our RIBS scheme, it needs O(9[m.sup.2]n + lmn)[T.sub.+] + O([m.sup.2]n)[T.sub.m] + [T.sub.inv] + [T.sub.sl] level time to obtain a signature, where T+ is the cost of executing an addition operation in [Z.sub.q], [T.sub.inv] is the cost of executing a matrix inversion operation in [Z.sup.3mx3m], and [T.sub.sl] is the cost of executing the SampleLeft algorithm. For the computation cost of verifying, three schemes require 3Nm[T.sub.m], ([N.sup.2] + N)[T.sub.m] and O(mn)[T.sub.m] + O(lmn)[T.sub.+], respectively, to verify a signature. Since m > 6N log q, it is obvious that the ideal lattice-based scheme [11] has higher efficiency in terms of the computation costs of signing and verifying. Finally, since our RIBS scheme employs the binary tree to revoke users, the authority's workload performing the update procedure is the logarithm of nonrevoked users. In Xiang's RIBS scheme, it also employs the binary tree to revoke users. But it then uses secure channels to send periodic signing keys to nonrevoked users, and it will make the authority having linearity level workload. In scheme [11], the authority's workload is linearity of nonrevoked users (Table 1).

5.2. Functionality Comparisons. Firstly, as indicated in Table 2, Wei et al.'s [20] RIBS, Yang et al.'s [21] RIBS, and Zhao et al.'s [22] RIBS schemes can resist key exposure attacks in the standard (SD) model with scalability under different Diffie-Hellman assumptions (namely, q-DHE, CDH, and (3,n)-MDHE assumptions, respectively). However, these schemes cannot resist quantum computer attacks. Our RIBS, Xinyin's [10] RIBS, and Hung et al.'s [11] RIBS schemes from lattices can resist quantum computer attacks. Secondly, both our RIBS and Hung et al.'s [11] RIBS schemes broadcast the update keys regularly through public channels. But Xinyin's [10] RIBS scheme uses secure channels to send periodic update keys. Thirdly, both Xinyin's [10] RIBS and Hung's [11] RIBS schemes are not scalable RIBS schemes. Although Xiang's RIBS scheme uses the binary tree structure, it requires a secure channel between a user and PKG and does not support scalability. Our RIBS is a scalable RIBS scheme by using the binary structure and public channel. Finally, both our RIBS and Hung et al.'s RIBS schemes have a limitation that the schemes are only proved secure in the random oracle (RO) model under SIS assumption and RSIS assumption, respectively.

6. Conclusion

In this paper, we have proposed the first scalable RIBS scheme with signing key exposure resistance over lattices, in which the update keys are broadcast regularly over public channels. Then, we proved its EUF-sID-CMA security under the SIS assumption. In the future, we intend to improve the efficiency of the lattice-based RIBS with signing key exposure resistance.

Data Availability

All data used to support the findings of this study are included within the article.

Disclosure

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

Conflicts of Interest

The authors declare that there are no conflicts of interest regarding the publication of this article.

Acknowledgments

Jian Weng was supported by National Natural Science Foundation of China (Grant Nos. 61825203, U1736203 and No. 61732021), the Major Program of Guangdong Basic and Applied Research (Grant No. 2019B030302008), and Science and Technology Program of Guangzhou of China (Grant No. 201802010061). Congge Xie was supported by National Natural Science Foundation of China (Grant No. 61872153), Science and Technology Planning Project of Guangdong Province of China (Grant No. 2017B010111005), National Key R&D Program of China (Grant No. 2018YFB1402600). Jinming Wen was supported by National Natural Science Foundation of China (Grant No. 11871248).

https://doi.org/10.1155/2020/1743421

References

[1] D. Boneh and M. K. Franklin, "Identity-based encryption from the weil pairing," in Proceedings of the 21st Annual International Cryptology Conference-Advances in Cryptology (CRYPTO 2001), pp. 213-229, Santa Barbara, CA, USA, August 2001.

[2] A. Boldyreva, V. Goyal, and V. Kumar, "Identity-based encryption with efficient revocation," in Proceedings of the 2008 ACM Conference on Computer and Communications Security (CCS 2008), pp. 417-426, Alexandria, VA, USA, October 2008.

[3] B. Libert and D. Vergnaud, "Adaptive-ID secure revocable identity-based encryption," in Proceedings of the Cryptographers' Track at the RSA Conference 2009-Topics in Cryptology (CT-RSA 2009), pp. 1-15, San Francisco, CA, USA, April 2009.

[4] J. Chen, H. W. Lim, S. Ling, H. Wang, and K. Nguyen, "Revocable identity-based encryption from lattices," in Proceedings of the 17th Australasian Conference-Information Security and Privacy (ACISP), pp. 390-403, Wollongong, Australia, July 2012.

[5] S. Cheng and J. Zhang, "Adaptive-ID secure revocable identity-based encryption from lattices via subset difference method," in Proceedings of the 11th International Conference-Information Security Practice and Experience (ISPEC 2015), pp. 283-297, Beijing, China, May 2015.

[6] J. H. Seo and K. Emura, "Revocable identity-based encryption revisited: security model and construction," in Proceedings of the 16th International Conference on Practice and Theory in Public-Key Cryptography, PKC 2013, pp. 216-234, Nara, Japan, January 2013.

[7] T. Tsai, Y. Tseng, and T. Wu, "Provably secure revocable ID-based signature in the standard model," Security and Communication Networks, vol. 6, no. 10, pp. 1250-1260, 2013.

[8] Y. Sun, F. Zhang, L. Shen, and R. H. Deng, "Revocable identity-based signature without pairing," in Proceedings of the 5th International Conference on Intelligent Networking and Collaborative Systems 2013, pp. 363-365, Xi'an, China, September 2013.

[9] Y. Hung, T. Tsai, Y. Tseng, and S. Huang, "Strongly secure revocable ID-based signature without random oracles," ITC, vol. 43, no. 3, pp. 264-276, 2014.

[10] X. Xinyin, "Adaptive secure revocable identity-based signature scheme over lattices," Computer Engineering, vol. 10, p. 25, 2015.

[11] Y.-H. Hung, Y.-M. Tseng, and S.-S. Huang, "Revocable ID-based signature with short size over lattices," Security and Communication Networks, vol. 2017, Article ID 7571201, 9 pages, 2017.

[12] V. Lyubashevsky, "Lattice signatures without trapdoors," in Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques-Advances in Cryptology (EUROCRYPT 2012), pp. 738-755, Cambridge, UK, April 2012.

[13] A. Shamir, "Identity-based cryptosystems and signature schemes," in Proceedings of the CRYPTO'84-Advances in Cryptology (CRYPTO 1984), pp. 47-53, Santa Barbara, CA, USA, April 1984.

[14] Y. Ishida, Y. Watanabe, and J. Shikata, "Constructions of CCA-secure revocable identity-based encryption," in Proceedings of the 20th Australasian Conference on Information Security and Privacy, ACISP 2015, pp. 174-191, Brisbane, Australia, June-July 2015.

[15] K. Emura, J. H. Seo, and T. Youn, "Semi-generic transformation of revocable hierarchical identity-based encryption and its DBDH instantiation," IEICE Transactions, vol. E99.A, no. 1, pp. 83-91, 2016.

[16] J. H. Seo and K. Emura, "Revocable hierarchical identity-based encryption via history-free approach," Theoretical Computer Science, vol. 615, pp. 45-60, 2016.

[17] K. Lee and S. Park, "Revocable hierarchical identity-based encryption with shorter private keys and update keys," Designs, Codes and Cryptography, vol. 86, no. 10, pp. 2407-2440, 2018.

[18] A. Takayasu and Y. Watanabe, "Lattice-based revocable identity-based encryption with bounded decryption key exposure resistance," in Proceedings of the 22nd Australasian Conference on Information Security and Privacy, ACISP 2017, pp. 184-204, Auckland, New Zealand, July 2017.

[19] Z. Liu, X. Zhang, Y. Hu, and T. Takagi, "Revocable and strongly unforgeable identity-based signature scheme in the standard model," Security and Communication Networks, vol. 9, no. 14, pp. 2422-2433, 2016.

[20] J. Wei, W. Liu, and X. Hu, "Forward-secure identity-based signature with efficient revocation," International Journal of Computer Mathematics, vol. 94, no. 7, pp. 1390-1411, 2017.

[21] X. Yang, T. Ma, P. Yang, F. An, and C. Wang, "Security analysis of a revocable and strongly unforgeable identity-based signature scheme," ITC, vol. 47, no. 3, pp. 575-587, 2018.

[22] J. Zhao, B. Wei, and Y. Su, "Communication-efficient revocable identity-based signature from multilinear maps," Journal of Ambient Intelligence and Humanized Computing, vol. 10, no. 1, pp. 187-198, 2019.

[23] C. Gentry, C. Peikert, and V. Vaikuntanathan, "Trapdoors for hard lattices and new cryptographic constructions," in Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 197-206, Victoria, Canada, May 2008.

[24] D. Micciancio and C. Peikert, "Trapdoors for lattices: simpler, tighter, faster, smaller," in Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques-Advances in Cryptology (EUROCRYPT 2012), pp. 700-718, Cambridge, UK, April 2012.

[25] M. Ajtai, "Generating hard instances of the short basis problem," in Proceedings of the 26th International Colloquium-Automata, Languages and Programming (ICALP 1999), pp. 1-9, Prague, Czech Republic, July 1999.

[26] J. Alwen and C. Peikert, "Generating shorter bases for hard random lattices," in Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), pp. 75-86, Freiburg, Germany, February 2009.

[27] S. Agrawal, D. Boneh, and X. Boyen, "Efficient lattice (H)IBE in the standard model," in Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques--Advances in Cryptology (EUROCRYPT 2010), pp. 553-572, Riviera, French, May-June 2010.

[28] S. Agrawal, D. Boneh, and X. Boyen, "Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE," in Proceedings of the 30th Annual Cryptology Conference-Advances in Cryptology (CRYPTO 2010), pp. 98-115, Santa Barbara, CA, USA, August 2010.

[29] D. Micciancio and O. Regev, "Worst-case to average-case reductions based on Gaussian measures," SIAM Journal on Computing, vol. 37, no. 1, pp. 267-302, 2007.

[30] O. Regev, "On lattices, learning with errors, random linear codes, and cryptography," in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 84-93, Baltimore, MD, USA, May 2005.

Congge Xie [ID], Jian Weng [ID], and Jinming Wen [ID]

College of Information Science and Technology, Jinan University, Guangzhou, China

Correspondence should be addressed to Jian Weng; cryptjweng@gmail.com

Received 23 August 2019; Accepted 12 December 2019; Published 14 January 2020

Academic Editor: Bruce M. Kapron
Table 1: Efficiency comparisons with previous works.

                            [20]                     [21]

Signing key size   4[absolute value of G]   3[absolute value of G]

Signature size     4[absolute value of G]   4[absolute value of G]

Computation cost           O(1)e                      3e
of signing

Computation cost           O(1)p                    e + 4p
of verifying

Authority's               O(log r)                   O(r)
workload

                           [22]                     [10]

Signing key size   3[absolute value of       2Nm * (log r) * log
                        [G.sub.2]]        ([bar.s] [square root of
                                                   (2m)])

Signature size     4[absolute value of       3Nm * (log r) * log
                        [G.sub.2]]         ([bar.s][square root of
                                                   (3m)])

Computation cost            6e            2Nm[T.sub.m] + [T.sub.sp]
of signing

Computation cost            4p                  3Nm[T.sub.m]
of verifying

Authority's            [empty set]                O(log r)
workload

                             [11]

Signing key size   4N * log(s[square root of
                             (N)])

Signature size     2N log [sigma] + [lambda]
                       log N + [lambda]

Computation cost     7[N.sup.2][T.sub.m] +
of signing               14N[T.sub.m]

Computation cost     [N.sup.2][T.sub.m] +
of verifying              N[T.sub.m]

Authority's                  O(r)
workload

                             Ours

Signing key size   [s.sub.1] [square root of
                   (m)] + [s.sub.R] [square
                         root of (m)]

Signature size     [s.sub.3] [square root of
                             (4m)]

Computation cost    O (9[m.sup.2]n + lmn) *
of signing               [T.sub.+] + O
                    ([m.sup.2]n)[T.sub.m] +
                   [T.sub.inv] + [T.sub.sl]

Computation cost       O(mn)[T.sub.m] +
of verifying            O(lmn)[T.sub.+]

Authority's                O(log r)
workload

N: security parameter; [lambda]: positive integer; r: number of
nonrevoked users; m > 6N log q; [bar.s] = m log r * [omega]
([square root of (log N)]); s = [N.sup.5/2] * [square root of
(2q)][omega]([square root of (log N)]); [sigma] = 12[lambda]sN;
[s.sub.1] = O([square root of ([)]) * [omega] ([square root of
(log m)]); [s.sub.3] = [square root of (m)]([s.sub.1] + [s.sub.R])
* [omega] ([square root of (log 4 m)]); [absolute value of G] or
[absolute value of [G.sub.2]] is the size an element in the group
G or [G.sub.2]; p and e denote a pairing operation and an
exponentiation operation, respectively; [T.sub.+] is the cost of
executing an addition operation in [Z.sub.q]; [T.sub.m] is the cost
of executing a multiplication operation in [Z.sub.q]; [T.sub.sp]
is the cost of executing the Samplepre algorithm in [23]; [T.sub.inv]
is the cost of executing a matrix inversion operation in [Z.sup.3mx3m];
[T.sub.sl] is the cost of executing the Sampleleft algorithm in
[27]; [empty set] denotes that the workload of the authority
performing the update procedure is independent of the number of
nonrevoked users.

Table 2: Functionality comparisons with previous works.

Schemes   Key exposure resistance   Quantum attacks resistance   Model

[20]                Yes                         No                SD
[21]                Yes                         No                SD
[22]                Yes                         No                SD
[10]                No                         Yes                SD
[11]                No                         Yes                RO
Ours                Yes                        Yes                RO

Schemes   Transport channel   Scalability   Assumption

[20]           Public             Yes          q-DHE
[21]           Public             Yes           CDH
[22]           Public             Yes       (3,n)-MDHE
[10]           Secure             No            SIS
[11]           Public             No           RSIS
Ours           Public             Yes           SIS
COPYRIGHT 2020 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2020 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Xie, Congge; Weng, Jian; Wen, Jinming
Publication:Security and Communication Networks
Geographic Code:9CHIN
Date:Jan 1, 2020
Words:10081
Previous Article:EPLC: An Efficient Privacy-Preserving Line-Loss Calculation Scheme for Residential Areas of Smart Grid.
Next Article:Survey of Attack Graph Analysis Methods from the Perspective of Data and Knowledge Processing.
Topics:

Terms of use | Privacy policy | Copyright © 2022 Farlex, Inc. | Feedback | For webmasters |