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

Authors: Congge Xie; Jian Weng; Jinming Wen
Journal: Security and Communication Networks
 (2020)

---

## Abstract

In 2014, a new security definition of a revocable identity-based signature (RIBS) with signing key exposure resistance was introduced. Based on this new definition, many scalable RIBS schemes with signing key exposure resistance were proposed. However, the security of these schemes is based on traditional complexity assumption, which is not secure against attacks in the quantum era. Lattice-based cryptography has many attractive features, and it is believed to be secure against quantum computing attacks. We reviewed existing lattice-based RIBS schemes and found that all these schemes are vulnerable to signing key exposure. Hence, in this paper, we propose the first lattice-based RIBS scheme with signing key exposure resistance by using the left-right lattices and delegation technology. In addition, we employ a complete subtree revocation method to ensure our construction meeting scalability. Finally, we prove that our RIBS scheme is selective-ID existentially unforgeable against chosen message attacks (EUF-sID-CMA) under the standard short integer solutions (SIS) assumption in the random oracle model.


---

## Body

## 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 Section2, 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.


## 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 Section2, 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.


## 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 Section2, 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

ℤ
q is a ring of integers modulo q and represents integers in −q/2,q/2, where q≥2. ℤqn×m is a set of n×m matrices, in which the elements are in ℤq. x denotes the Euclidean norm of a vector x. Matrix AT is the transpose of A, and A represents the norm of a matrix A which is defined as the largest norm of its columns. Given matrix B, B˜ and B˜ are B’s Gram–Schmidt orthogonalization and Gram–Schmidt norm.


### 2.2. Lattices

Definition 1.
Given primeq, A∈ℤqn×m, and u∈ℤqn, define following lattices:(1)Λq⊥A=y∈ℤm:Ay=0modq,ΛquA=y∈ℤm:Ay=umodq.
Letρσ,cx≔exp−πx−c2/σ2 be the standard Gaussian function with center c and variance σ. For a lattice Λ and all the Λ’s points x, define the discrete Gaussian distribution over Λ as DΛ,σ,cx≔ρσ,cx/ρσ,cΛ. For ease of notation, we use DΛ,σ as DΛ,σ,0’s abbreviate.
The following lemma from [23, 24] is very useful for our construction.Lemma 1.
Givenq≥2 and A∈ℤqn×m, Λq⊥A’s basis TA, s≥TA˜ωlogm, Then, for c∈ℝm and u∈ℤqn, algorithm SamplePreA,TA,u,s outputs x∈ΛquA and its distribution is statistically close to DΛquA,s,c, where m>n and ΛquA is not empty.The following fact from [23] will be used in our security proof.Lemma 2.
Given n, positive prime q,m≥2nlogq, and s≥ωlogm, u≔Ae mod q’s distribution is statistically close to ℤqn’s uniform except with a 2q−n fraction of all A∈ℤqn×m, where e is from Dℤm,s.


### 2.3. Some Algorithms

We first recall an algorithm investigated by [24–26], which generates a random lattice A∈ℤqn×m and Λq⊥A’s short basis TA.Lemma 3.
Givenq≥2 and m≥6nlogq, with overwhelming probability, TrapGen1n,1m,q outputs (A∈ℤqn×m and its basis TA∈ℤm×m), TA˜≤Onlogq, where A’s distribution is statistically close to ℤqn×m’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Λ’s arbitrary basis B and a full-rank set S∈Λ, there exist a deterministic algorithm that can convert S to T and for all i∈l, ti˜≤si˜, where T is a basis of Λ.Another two algorithms in [27] will be used to construct and prove our following scheme, respectively.Lemma 5.
Givenq≥2, m≥n, and s≥TA˜⋅ωlogm+m1, algorithm SampleLeft A,B,TA,u,s outputs a vector e∈ℤm+m1 distributed statistically close to DΛquG,s with full-rank matrix A∈ℤqn×m, Λq⊥A’s basis TA, matrix B∈ℤqn×m1, and vector u∈ℤqn, where G≔AB.Lemma 6.
Givenq>2, m>n, and s>TB˜⋅l⋅sR⋅ωlogm, algorithm SampleRight A,B,R1,TB,u,s outputs a vector e∈ℤm+k distributed statistically close to DΛquG,s with A∈ℤqn×k, B∈ℤqn×m, R∈ℤqk×m, Λq⊥B’s basis TB, vector u∈ℤqn, and parameter s>TB˜⋅sR⋅ωlogm, where sR=supy=1Ry, G=AAR+B.The following two algorithms from [28] will be also used to construct and prove our following scheme respectively.Lemma 7.
Given a rank n matrixA∈ℤqn×m, a ℤq-invertible matrix R∈ℤm×m sampled from Dm×m, a basis TA of Λq⊥A, and a parameter s∈ℝ>0. Algorithm BasisDelA,R,TA,s outputs a basis TB of Λq⊥B, where B=AR−1.Lemma 8.
Letm>2nlogq and q>2 be a prime. For all but at most a q−n fraction of rank n matrix A∈ℤqn×m, algorithm SampleRwithBasisA outputs a matrix R∈ℤm×m sampled from a distribution statistically close to Dm×m. The generated basis TB of Λq⊥AR−1 satisfies TB˜≤nlogq 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 matrixR in ℤm×m is ℤq-invertible if R mod q is invertible as a matrix in ℤqm×m. Define αR≔nlogq⋅ωlogm. We let Dm×m denote the distribution on matrices in ℤm×m defined as Dℤm,αRm with the condition that R∈ℤq-invertible and meanwhile R≤αR⋅m. Algorithm SampleR1m samples matrices in ℤm×m and their distributions are statistically close to Dm×m.


### 2.5. Small Integer Solution Problem

Definition 3 (SIS).
For anyn∈ℤ and any function m≔mn,q≔qn,andβ≔βn, given an integer q, a uniform and random matrix A∈ℤqn×m and a real number β∈ℝ, the average-case SISq,n,m,β is the problem of finding a nonzero integer vector s∈ℤm∖0 satisfying As=0 mod q and s≤β.
It has been proved by Micciancio and Regev [29] that for certain parameters, the average-case SISq,n,m,β problem is as hard as approximating to the worst-case shortest independent vector problem within certain γ=β⋅O˜n factors.


### 2.6. Encoding Identities or Times as Matrices

In our following scheme, we use an injective encoding functionH:ℤqn⟶ℤqn×n to map identities or times in ℤqn to matrices in ℤqn×n, whose concrete construction can be found in [27].Definition 4.
Given a prime q and a positive integer n,H:ℤqn⟶ℤqn×n which is an encoding with full-rank differences (FRD) that satisfies the following:(1)
Hu−Hv∈ℤqn×n is full rank for all distinct u,v∈ℤqn(2)
H is a polynomial computable function in nlogq


## 2.1. Notation

ℤ
q is a ring of integers modulo q and represents integers in −q/2,q/2, where q≥2. ℤqn×m is a set of n×m matrices, in which the elements are in ℤq. x denotes the Euclidean norm of a vector x. Matrix AT is the transpose of A, and A represents the norm of a matrix A which is defined as the largest norm of its columns. Given matrix B, B˜ and B˜ are B’s Gram–Schmidt orthogonalization and Gram–Schmidt norm.


## 2.2. Lattices

Definition 1.
Given primeq, A∈ℤqn×m, and u∈ℤqn, define following lattices:(1)Λq⊥A=y∈ℤm:Ay=0modq,ΛquA=y∈ℤm:Ay=umodq.
Letρσ,cx≔exp−πx−c2/σ2 be the standard Gaussian function with center c and variance σ. For a lattice Λ and all the Λ’s points x, define the discrete Gaussian distribution over Λ as DΛ,σ,cx≔ρσ,cx/ρσ,cΛ. For ease of notation, we use DΛ,σ as DΛ,σ,0’s abbreviate.
The following lemma from [23, 24] is very useful for our construction.Lemma 1.
Givenq≥2 and A∈ℤqn×m, Λq⊥A’s basis TA, s≥TA˜ωlogm, Then, for c∈ℝm and u∈ℤqn, algorithm SamplePreA,TA,u,s outputs x∈ΛquA and its distribution is statistically close to DΛquA,s,c, where m>n and ΛquA is not empty.The following fact from [23] will be used in our security proof.Lemma 2.
Given n, positive prime q,m≥2nlogq, and s≥ωlogm, u≔Ae mod q’s distribution is statistically close to ℤqn’s uniform except with a 2q−n fraction of all A∈ℤqn×m, where e is from Dℤm,s.


## 2.3. Some Algorithms

We first recall an algorithm investigated by [24–26], which generates a random lattice A∈ℤqn×m and Λq⊥A’s short basis TA.Lemma 3.
Givenq≥2 and m≥6nlogq, with overwhelming probability, TrapGen1n,1m,q outputs (A∈ℤqn×m and its basis TA∈ℤm×m), TA˜≤Onlogq, where A’s distribution is statistically close to ℤqn×m’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Λ’s arbitrary basis B and a full-rank set S∈Λ, there exist a deterministic algorithm that can convert S to T and for all i∈l, ti˜≤si˜, where T is a basis of Λ.Another two algorithms in [27] will be used to construct and prove our following scheme, respectively.Lemma 5.
Givenq≥2, m≥n, and s≥TA˜⋅ωlogm+m1, algorithm SampleLeft A,B,TA,u,s outputs a vector e∈ℤm+m1 distributed statistically close to DΛquG,s with full-rank matrix A∈ℤqn×m, Λq⊥A’s basis TA, matrix B∈ℤqn×m1, and vector u∈ℤqn, where G≔AB.Lemma 6.
Givenq>2, m>n, and s>TB˜⋅l⋅sR⋅ωlogm, algorithm SampleRight A,B,R1,TB,u,s outputs a vector e∈ℤm+k distributed statistically close to DΛquG,s with A∈ℤqn×k, B∈ℤqn×m, R∈ℤqk×m, Λq⊥B’s basis TB, vector u∈ℤqn, and parameter s>TB˜⋅sR⋅ωlogm, where sR=supy=1Ry, G=AAR+B.The following two algorithms from [28] will be also used to construct and prove our following scheme respectively.Lemma 7.
Given a rank n matrixA∈ℤqn×m, a ℤq-invertible matrix R∈ℤm×m sampled from Dm×m, a basis TA of Λq⊥A, and a parameter s∈ℝ>0. Algorithm BasisDelA,R,TA,s outputs a basis TB of Λq⊥B, where B=AR−1.Lemma 8.
Letm>2nlogq and q>2 be a prime. For all but at most a q−n fraction of rank n matrix A∈ℤqn×m, algorithm SampleRwithBasisA outputs a matrix R∈ℤm×m sampled from a distribution statistically close to Dm×m. The generated basis TB of Λq⊥AR−1 satisfies TB˜≤nlogq 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 matrixR in ℤm×m is ℤq-invertible if R mod q is invertible as a matrix in ℤqm×m. Define αR≔nlogq⋅ωlogm. We let Dm×m denote the distribution on matrices in ℤm×m defined as Dℤm,αRm with the condition that R∈ℤq-invertible and meanwhile R≤αR⋅m. Algorithm SampleR1m samples matrices in ℤm×m and their distributions are statistically close to Dm×m.


## 2.5. Small Integer Solution Problem

Definition 3 (SIS).
For anyn∈ℤ and any function m≔mn,q≔qn,andβ≔βn, given an integer q, a uniform and random matrix A∈ℤqn×m and a real number β∈ℝ, the average-case SISq,n,m,β is the problem of finding a nonzero integer vector s∈ℤm∖0 satisfying As=0 mod q and s≤β.
It has been proved by Micciancio and Regev [29] that for certain parameters, the average-case SISq,n,m,β problem is as hard as approximating to the worst-case shortest independent vector problem within certain γ=β⋅O˜n factors.


## 2.6. Encoding Identities or Times as Matrices

In our following scheme, we use an injective encoding functionH:ℤqn⟶ℤqn×n to map identities or times in ℤqn to matrices in ℤqn×n, whose concrete construction can be found in [27].Definition 4.
Given a prime q and a positive integer n,H:ℤqn⟶ℤqn×n which is an encoding with full-rank differences (FRD) that satisfies the following:(1)
Hu−Hv∈ℤqn×n is full rank for all distinct u,v∈ℤqn(2)
H is a polynomial computable function in nlogq


## 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
λ
,
N takes a security parameter λ 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∈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∈T, the current revocation list RL, and the state ST as input and outputs a update key KUt. This is run by the key authority.
SignKeyGen
SK
id
,
KU
t takes a private key SKid and an update key KUt as input and outputs a signing key SKid,t or a special symbol ⊥ indicating that id was revoked. This is a probabilistic algorithm and run by the signer.
Sign
PP
,
id
,
t
,
SK
id
,
t
,
and
μ takes the public parameters PP, an identity id∈I, a time t∈T, a signing key SKid,t, and a message μ∈U as input and outputs a signature σ.
Verify
PP
,
id
,
t
,
μ
,
and
σ takes the public parameters PP and an identity id∈I, a time t∈T, and a message/signature pair (μ,σ) as input and outputs 1 (accept) or 0 (reject).
KeyRev
id
,
t
,
RL
,
and ST takes a revoked identity id∈I, a time t∈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λ∈ℕ, polynomials N, all PP,MSK output by Setup, all μ∈U, id∈I, t∈T, and all possible valid states ST and revocation lists RL, if identity id is not revoked in time t, then for SKid,ST⟵PriKeyGenPP,MSK,id, KUt⟵KeyUpdPP,MSK,t,RL,ST, and SKid,t⟵SignKeyGenSKid,KUt, it has Verify PP,id,t,μ,σ⟵SignPP,id,t,SKid,t,μ=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 adversaryA and a challenger C.Initial: the adversaryA first outputs the challenge identity id∗, time t∗, and also some information state it wants to preserve.Setup: the challenger runsSetup 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 KUt 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 AForgery: at the end of the game, A outputs a forgery of a message/signature pair on the behalf of the identity id∗ in the time period t∗.IfA satisfies the following four conditions, then it wins the above game:(i)
VerifyPP,id∗,t∗,μ∗,σ∗=1(ii)
Key Update Query andRevocation 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 timet if Key Update Query was queried on t(iv)
If PriKeyGen Query wasqueried for identity id∗, then the Revocation Query must be queried for identity id∗ on time t≤t∗(v)
SignKeyGen Query cannot be queried on timet before Key Update Query was queried on t(vi)
SignKeyGen Query cannot be queried for identityid∗ on time t∗(vii)
Signature Query cannot bequeried for challenge message μ∗ under identity id∗ on time t∗
The probability of winning the above game is the advantage ofA. 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.


## 3.1. Correctness

The correctness requires that for allλ∈ℕ, polynomials N, all PP,MSK output by Setup, all μ∈U, id∈I, t∈T, and all possible valid states ST and revocation lists RL, if identity id is not revoked in time t, then for SKid,ST⟵PriKeyGenPP,MSK,id, KUt⟵KeyUpdPP,MSK,t,RL,ST, and SKid,t⟵SignKeyGenSKid,KUt, it has Verify PP,id,t,μ,σ⟵SignPP,id,t,SKid,t,μ=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 adversaryA and a challenger C.Initial: the adversaryA first outputs the challenge identity id∗, time t∗, and also some information state it wants to preserve.Setup: the challenger runsSetup 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 KUt 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 AForgery: at the end of the game, A outputs a forgery of a message/signature pair on the behalf of the identity id∗ in the time period t∗.IfA satisfies the following four conditions, then it wins the above game:(i)
VerifyPP,id∗,t∗,μ∗,σ∗=1(ii)
Key Update Query andRevocation 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 timet if Key Update Query was queried on t(iv)
If PriKeyGen Query wasqueried for identity id∗, then the Revocation Query must be queried for identity id∗ on time t≤t∗(v)
SignKeyGen Query cannot be queried on timet before Key Update Query was queried on t(vi)
SignKeyGen Query cannot be queried for identityid∗ on time t∗(vii)
Signature Query cannot bequeried for challenge message μ∗ under identity id∗ on time t∗
The probability of winning the above game is the advantage ofA. 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 functionH0 refers to the FRD map H0:ℤqn⟶ℤqn×n (if id∈0,1∗, it can be hashed into ℤqn by using a collision resistant hash). Hash function H1 is a random oracle that outputs matrices in ℤ3m×3m, namely, H1:0,1∗⟶ℤ3m×3m: t⟶H1t∼D3m×3m.


### 4.1. SampleSubInv Algorithm

Algorithm SampleSubInv
A
,
M
,
T
A
,
U
,
and
s: the algorithm takes a rank n matrix A∈ℤqn×m, a matrix M∈ℤm×m, a basis TA of Λq⊥A, a matrix U=u1,…,um∈ℤqn×m, and a parameter s∈ℝ>0 as input and works as follows:(1)
LetM=e1,…,em, for i=1,…,m do(1a)
Sampleti∈ℤm as the output of SamplePreA,TA,ui,s, then Ati=ui mod q and ti is sampled from a distribution statistically close to DΛquiA,s(1b)
Ifti−ei is linearly independent of t1−e1,…,ti−1−ei−1, accept ti. Otherwise, repeat step (1a)(2)
LetT∈ℤm×m be the matrix whose columns are t1,…,tm. Output TNote thatAT=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 m2 samples from SamplePreA,TA,ui,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:Setup1λ,N: the setup algorithm takes a security parameter λ and a maximal number of users N as input and proceeds as follows:(1)
Pick Gaussian parameterss1,s2,ands3 and set the parameters n=nλ,q=qn,andm=mn. These parameters are implicitly known to all of the algorithms below.(2)
Samplel+3 random matrices: A1,A2,B,Dii∈l in ℤqn×m, where l is the length of message.(3)
Sample matrix with associated trapdoor:A,TA⟵TrapGen1n,1m,q.(4)
Output public parametersPP=A,A1,A2,B,Dii∈l, master secret key MSK=TA, a revocation list RL=∅, and a state ST=BT.PriKeyGenPP,MSK,id,and ST: this algorithm takes as input the public parameters PP, a master secret key MSK, an identity id∈0,1∗, and a state ST. Then it picks an unassigned leaf node ν from BT, stores id in that node, and performs the following steps:(1)
For each nodeθ∈Pathν, pick random matrix Uθ∈ℤqn×m and store it in node θ(2)
SampleR1⟵Dm×m, Eν⟵SamplePreA,TA,−A1+H0idBR1,s1(3)
SampleEθ,1Eθ,2⟵SampleLeftA,A1+H0idB,TA,Uθ,s1(4)
StoreHθ≔Eθ,1−EνR1−1Eθ,2 in node θ(5)
Output private keySKid=θ,Eθ,1Eθ,2θ∈Pathν,Eν,R1,STKeyUpdPP,MSK,t,RL,and ST: this algorithm takes the public parameters PP, a master secret key MSK, a time t∈0,1∗, a revocation list RL, and a state ST as input and proceeds as follows:(1)
SampleR2⟵Dm×m and Et⟵SamplePreA,TA,−A2+H0tBR2,s1(2)
∀θ∈KUNodesBT,RL,andt and sample Eθ,2′⟵Dℤm,s1m and compute Hθ′=EtR2−1Eθ,2′, where KUNodesBT,RL,andt is an algorithm KUNodes from [4](3)
SampleEθ,1′⟵SampleSubInvA,Hθ′−Hθ,TA,−Uθ−A2+H0tBEθ,2′,s1(4)
Output update keyKUt=θ,Eθ,1′Eθ,2′θ∈KUNodesBT,RL,t,Et,R2SignKeyGenSKidandKUt: this algorithm takes a private key SKid and an update key KUt as input and runs the following steps:(1)
SetAid,t≔AA1+H0idBA2+H0tB and compute Rid,t=H1idt and Fid,t≔Aid,t⋅Rid,t−1(2)
∀i,Ei,1Ei,2∈SKid and j,Ej,1′Ej,2′∈KUt, if ∃i=j, then set(2)Sid,t=Ei,1+Ej,1′EνEtEi,2R10Ej,2′0R2.(3)
GenerateSKid,t′ by running Lemma 4 which takes Sid,t as input (Sid,t is an invertible matrix with some norm which will be proved in the Theorem 1). Then, run the algorithm BasisDelAid,t,Rid,t,SKid,t′,s2 to generate SKid,t and output SKid,t.SignPP,id,t,SKid,t,andμ: the signing algorithm takes the public parameters PP, an identity id, a time t, a signing key SKid,t, and a message μ=μ1,…,μl∈0,1l as input and outputs signature σ as follows:(1)
Sample the algorithmσ⟵SampleLeftFid,t,B+∑i=1l−1μiDi,SKid,t,0,s3 such that Fid,tB+∑i=1l−1μiDi⋅σ=0, where s3≥SKid,t˜⋅ωlog4m(2)
Output signature σVerifyPP,id,t,μ,andσ : the verify algorithm takes the public parameters PP, an identity id∈0,1∗, a time t∈0,1∗, and a pair of message/signature μ,σ as input and accepts only if the following conditions are satisfied:(i)
σ∈ℤ4m, σ≤s34m(ii)
Fid,tB+∑i=1l−1μiDi⋅σ=0KeyRevid,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 ν associated with identity id and returns RL.Theorem 1.
S
id
,
t is an invertible matrix with small norm.Proof.
First, we show thatSid,t is a small norm matrix. From the construction, we know that(3)Ei,1≤s1⋅m,Ej,1′≤s1⋅m,Ei,2≤s1⋅m,Ej,2′≤s1⋅m,Eν≤s1⋅m,Et≤s1⋅m,R1≤αR⋅m,R2≤αR⋅m,which are small norm matrices. Then, we can get Sid,t≤max4s1m,ms1+αR. Second, we will show Sid,t is an invertible matrix. For matrix Sid,t, we make an elementary transformation and finally obtain(4)C≔Ei,1+Ej,1′−EνR1−1Ei,2−EtR2−1Ej,2′000R1000R2.
SinceEi,1+Ej,1′−EνR1−1Ei,2−EtR2−1Ej,2′=Ej,1′−Hj′−Hi, and by the SampleSubInv algorithm in the KeyGen phase, we can see Ej,1′−Hj′−Hi is an invertible matrix. Because R1 and R2 are ℤq-invertible matrices, then C is invertible and then Sid,t is an invertible matrix. In summary, Sid,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:n=λ, m=Onlogq, η=ωlogm, s1=Onlogqωlog2m, s2=Onlogqωlogn, s3=lm3/2ωlogm4, β=lm2+3lηm5/22 ωlogm4, q≥max2lm3ωlogm6,2Q, where λ 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 isEUF-sID-CMA secure provided that the SISq,n,m,β assumption holds.Proof.
AssumeA wins the game in Section 3 and Q is the signing queries maximum number. We can construct a solver ℬ that provides a valid solution to the SIS problem. A first gives the target identity and time id∗,t∗. ℬ is given a random instance of the q,n,m,andβ-SIS problem and is asked to return an admissible solution. That is,(i)
Provided: a matrixA0 from ℤqn×3m’s uniform distribution(ii)
Returned: any vectore0∈ℤ3m such that A0e0=0modq and 0≠e0≤β
ℬ performs as follows:Setup∗1λ,N,l: ℬ provides the adversary A with simulated parameters as follows:(1)
Run algorithmTrapGen to obtain B,TB⟵TrapGen1n,1m,q(2)
Choosel+3 random matrices U0,U1,U2∼Dm×m and Ri∗∼Dℤm,η and also choose l random scalars hi∈ℤq for i∈l. Let A=A0U0−1U1−1U2−1, A1=AU1−H0id∗Bmodq, A2=AU2−Ht∗Bmodq, and Di=A0Ri∗Ri∗Ri∗+hi⋅B∈ℤqn×m(3)
Output the parametersPP=A,A1,A2,B,andDii∈lPriKeyGen Query and Key Update Query: ℬ first picks a node ν∗∈BT and allots it to id∗. It is worth noting that there will be two types of adversaries:(i)
Type (a) adversaries are revoked users and can challenge the target identityid∗ before or on time t∗(ii)
Type (b) adversaries cannot challenge the target identityid∗ at any timeℬ picks a bit rev$⟵0,1 randomly as a guess for the type of adversarial behavior. Clearly, the probability of ℬ’s correct guesses is 1/2. Type (a) adversaries (rev=0): ℬ simulates each node θ’s matrix Uθ as follows:(i)
ifθ∈Pathν∗, sample Eθ,1,Eθ,2⟵Dℤm,s1m, and R1⟵Dm×m, set Uθ⟵AA1+H0id∗B⋅Eθ,1Eθ,2, Eν∗=−U1⋅R1. Compute Hθ≔Eθ,1−Eν∗R1−1Eθ,2, and store Hθ,Uθ in the node θ.(ii)
ifθ∉Pathν∗, sample Eθ,1′,Eθ,2′⟵Dℤm,s1m, and R2⟵Dm×m, set −Uθ⟵AA2+H0t∗B⋅Eθ,1′Eθ,2′, Et∗=−U2⋅R2. Store Uθ in the node θ.
Sinceid∗ has been revoked before time t∗, it has KUNodesBT,t∗∩Pathν∗=∅ and ℬ returns id∗’s private key θ,Eθ,1Eθ,2θ∈Pathν∗,Eν∗,R1 and t∗’s update key θ,Eθ,1′Eθ,2′θ∈KUNodesBT,t∗,Et∗,R2.
Type (b) adversaries (rev=1): ℬ simulates each node θ’s matrix Uθ as follows: Since id∗ is never queried, ℬ does not need to simulate id∗’s private key. It samples Eθ,1′,Eθ,2′⟵Dℤm,s1m and R2⟵Dm×m and sets −Uθ⟵AA2+H0t∗B⋅Eθ,1′Eθ,2′, Et∗=−U2⋅R2. It stores Uθ in the node θ. If t=t∗, ℬ returns t∗’s update key θ,Eθ,1′Eθ,2′θ∈KUNodesBT,t∗,Et∗,R2.Note that, when rev=0, for each node θ, Uθ is generated either through Uθ⟵AA1+H0id∗B⋅Eθ,1Eθ,2 or though −Uθ⟵AA2+H0t∗B⋅Eθ,1′Eθ,2′ where Eθ,1,Eθ,2⟵Dℤm,s1m and Eθ,1′,Eθ,2′⟵Dℤm,s1m. Since the distribution of AA1+H0id∗B=AAU1 and AA2+H0t∗B=AAU2 are statistically close to ℤqn×2m’s uniform distribution by leftover hash lemma, then all the above Uθ are statistically close to uniform over ℤqn×m; when rev=1, for each node θ, Uθ is generated either through or through uniform distribution in ℤqn×m, where Eθ,1′,Eθ,2′⟵Dℤm,s1m. No matter which case, we can have R1∼Dm×m and R2∼Dm×m and Eν∗=−U1⋅R1 and Et∗=−U2⋅R2. Since the distribution of R1 and R2 are Gaussian distribution, then the distribution of Eν∗ and Et∗ is statistically close to Gaussian distribution. In conclusion, the distribution of the simulated system is statistically close to the real system.
Forid≠id∗’s private key queries and t≠t∗’s update key queries, ℬ uses the trapdoor TB instead of TA. Let AA1+H0idB=AAU1+H0id−H0id∗B and AA2+H0tB=AAU2+H0t−H0t∗B. From the definition of FRD, H0id−H0id∗ and H0t−H0t∗ are nonsingular. Then, ℬ runs the sampleRightExt algorithm and generates id≠id∗’s private key(5)Eθ,1Eθ,2⟵SampleRightA,H0id−H0id∗B,U1,TB,Uθ,s2′∈ℤq2m×m,where s2′>TB˜⋅sU1⋅ωlogm. Moreover, ℬ samples R1′⟵Dm×m and calls algorithm RandBasisTB,s4 from [28]. It can obtain TB′ satisfying AA1+H0idB⋅−U1I⋅TB′R1′=0 where s4≥TB˜⋅ωlogn, that is, A⋅−U1TB′R1′=−A1+H0idBTB′R1′. Then, it sets Eν=−U1TB′R1′ and R1=TB′R1′ and returns θ,Eθ,1Eθ,2θ∈Pathν,Eν,R1. For all t≠t∗’s update key queries, ℬ runs(6)Eθ,1′Eθ,2′⟵SampleRightA,H0t−H0t∗B,U2,TB,−Uθ,s2′∈ℤq2m×m,where s2′>TB˜⋅sU2⋅ωlogm. Moreover, it samples R2′⟵Dm×m and then calls algorithm RandBasisTB,s4 to get a basis TB″ satisfying AA2+H0tB⋅−U2I⋅TB″R2′=0, where s4≥TB˜⋅ωlogn, that is, A⋅−U2TB′R2′=−A2+H0tBTB″R2′. It sets Et=−U2TB″R2′ and R2=TB″R2′ and then generates the update key θ,Eθ,1′Eθ,2′θ∈KUNodesBT,RL,t,Et,R2.
Since the parameters2′ is sufficiently large, Eθ,1’s distribution is statistically close to DΛqUθ−AAU1Eθ,2 and Eθ,1′’s distribution is statistically close to DΛq−Uθ−AAU2Eθ,2′. Eθ,2 and Eθ,2′’s distributions are distributed close to Dℤm,s2′m, respectively. Since TB′ and TB″ are the random bases of Λq⊥B, then Eν=−U1TB′R1′ and ET=−U2TB″R2′’s distributions are the same as those in the real system. R1=TB′R1′ and R2=TB″R2′ are ℤq-invertible, that is, R1 and R2 are distributed as in the real system.


### 4.3.1. Signing Key Query

ℬ first samples a random matrix R∗∼Dm×m and defines H1id∗t∗≔R∗. Then, it sets G=A0⋅R∗000R∗000R∗ and picks an empty list L. If the adversary A asks the signing key on identity id∗ and time t≠t∗, ℬ runs SampleRwithBasisG to obtain a random Rid∗,t∼D3m×3m and a short basis TFid∗,t for Fid∗,t=GRid∗,tmodq. Then, it saves the tuple id∗t,Rid∗,t,Fid∗,t,TFid∗,t in list L for future use and returns TFid∗,t to the adversary A. If the adversary A asks the signing key on identity id≠id∗ and time t, ℬ retrieves the list L and checks whether idt in L. If idt,Rid,t,Fid,t,TFid,t is in L, ℬ returns TFid,t to A. Otherwise, ℬ also runs SampleRwithBasisG to obtain a random Rid,t∼D3m×3m and a short basis TFid,t for Fid,t=GRid,tmodq. Then, it saves the tuple idt,Rid,t,Fid,t,TFid,t in list L for future use and returns TFid,t 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 H1 oracle queries and signing key queries are as in the real system.


### 4.3.2. Signature Queries

ℬ simulates signatures of messages μ for A’s adaptive signature queries as follows:(i)
If the queried messagesμ are under target identity id∗ in target time t∗, ℬ answers as follows:(1)
ComputeRμ=∑i=1l−1μiRi∗Ri∗Ri∗ and hμ=1+∑i=1l−1μihi(2)
Ifhμ=0 (mod q), abort the simulation(3)
Otherwise sample vector:(7)σ⟵SampleRightA0,hμB,Rμ,TB,0,s2′.(4)
Outputσ∈ℤ4m(ii)
If the queried messagesμ are under identity id≠id∗ or in time t≠t∗, ℬ first retrieves the list L and checks whether it has tuple idt,Rid,t,Fid,t,TFid,t. If yes, ℬ gets TFid,t and samples vector σ⟵SampleLeftFid,t,A0Rμ+hμB,TFid,t,0,s2′. Otherwise, ℬ also runs SampleRwithBasisG to obtain a random Rid,t∼D3m×3m and a short basis TFid,t for Fid,t=GRid,tmodq. Then, it saves the tuple idt,Rid,t,Fid,t,TFid,t in list L and uses TFid,t to sample algorithm σ⟵SampleLeftFid,t,A0Rμ+hμB,TFid,t,0,s2′. At last, ℬ returns σ to the adversary A.Forgery: ℬ obtains a forged signature σ∗ on an unqueried message μ∗ and performs the following:(1)
ComputeRμ∗=∑i=1l−1μ∗iRi∗Ri∗Ri∗ and hμ∗=1+∑i=1l−1μ∗ihi(2)
Ifhμ∗≠0 (mod q), abort the simulation(3)
Otherwise, separateσ∗=σ1∗Tσ2∗TT(4)
Outpute0=σ1∗+Rμ∗σ2∗∈ℤ3mFrom Lemma9, e0 is small and nonzero with good probability and is a valid q,n,m,β-SIS solution with good probability.Lemma 9.
IfA provides a valid forgery σ1∗Tσ2∗TT for message μ∗ with hμ∗=0 (mod q), then for polynomial function β=polyl,n,m=polyλ, e0=σ1∗+Rμ∗σ2∗∈ℤ3m satisfying e0∈Λ⊥A0 and 0≠e0≤β.Proof.
First, whenhμ∗=0, we have A0Rμ∗+hμ∗B=A0Rμ∗. Since σ∗ is message μ∗’s valid signature under identity id∗ in time t∗, then we can obtain(8)A0σ1∗+Rμ∗σ2∗=A0A0Rμ∗σ1∗σ2∗=0modq.
Next, we will show thate0 is appropriately short. Since Rμ∗ is the sum of l low-norm matrices Ri∗Ri∗Ri∗ and Ri∗ are nearly independent with the same variance VR1∗ and their coefficients are in 0,1, then we will have(9)VRμ∗=V∑i=1lμ∗iRi∗Ri∗Ri∗≈∑i=1lVRi∗Ri∗Ri∗=l⋅VR1∗R1∗R1∗.
In particular, since they are almost independent discrete Gaussian,ERμ∗≈ER1∗R1∗R1∗=0, PrRi∗Ri∗Ri∗>η3m=neglm and PrRμ∗>lη3m=neglm. With overwhelming probability e0≤β for β=polyl,n,m=polyλ, we set β=1+ηl3m4m⋅s3.
Finally, it remains to show thate0≠0. Suppose an easy case that σ2∗=0, then for a valid forgery, it must have σ1∗≠0, thus e0≠0. On the contrary, σ2∗≠0, since σ2∗<4m⋅s2≪q; thus, there must be at least one σ2∗’s coordinate that is nonzero modulo q. We set z be σ4∗’s last one coordinate. Let r∗ be Rμ∗’s last column and ri∗ be Ri∗’s last column for each i∈l. Then, we have r∗=∑i=1l−1μ∗iri∗, where the coefficients depend on the message bits. For r1∗, let v=−1μ∗1zr1∗, then e0=zr∗+e0′=v+e0″, where v depends on r1∗ and e0″ does not. The only information about r1∗ available to A is contained in the last column of D1’s last column. From a simple pigeonhole principle, there exists many admissible and equally likely vector r1∗ that are the same with A’s view. A cannot know the value of zr1∗ with probability exceeding once third, then every other zr1∗ would fail to do so. Thus, Pre0≠0≥1/2mm−1. If A forges a signature with probability ε with Q≤q/2, then the algorithm ℬ can solve the SISn,m,q,β problem with the advantage of 1/2mm−11/2⋅ε1−q−1Qq−1≥ε/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 realSetup, matrix A∈ℤqn×m is sampled from the algorithm TrapGen. Matrices A1,A2,B,andDii∈l are chosen uniformly at random. In simulated Setup∗, A=A0U0−1U1−1U2−1, A1=AU1−H0id∗Bmodq, A2=AU2−Ht∗Bmodq, Di=A0Ri∗Ri∗Ri∗+hi⋅B∈ℤqn×m for random U0,U1,U2∼Dm×m and Ri∗∼Dℤm,η, and B,TB⟵TrapGenq,n(ii)
In the realSign phase, algorithm SampleLeft generates signatures σ, whereas in the simulated Sign phase, signatures are generated by algorithm SampleLeft or algorithm SampleRight
We now argue that the distributionA,A1,A2,B,Dii∈l is statistically indistinguishable in the two experiments. Let(10)A′=A1A2D1⋯Dl∈ℤqn×l+2m.
Then, from Lemma2, we have(11)A,A′≈sA,AU1−H0id∗BAU2−H0t∗BAR1∗+h1B⋯ARl∗+hlB,for random matrices A,A′ from ℤqn×m,ℤqn×l+2m and(12)U1U2R0∗⋯Rl∗∼Dm×2m×Dℤm,ηl,chosen at random. Here, B’s distribution is statistically close to ℤqn×m’s uniform distribution. Therefore, the distribution of PP in the simulation is statistically indistinguishable to them in the real system.
For eachμ’s signature query, if Gaussian parameters s3ands3′ 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.


## 4.1. SampleSubInv Algorithm

Algorithm SampleSubInv
A
,
M
,
T
A
,
U
,
and
s: the algorithm takes a rank n matrix A∈ℤqn×m, a matrix M∈ℤm×m, a basis TA of Λq⊥A, a matrix U=u1,…,um∈ℤqn×m, and a parameter s∈ℝ>0 as input and works as follows:(1)
LetM=e1,…,em, for i=1,…,m do(1a)
Sampleti∈ℤm as the output of SamplePreA,TA,ui,s, then Ati=ui mod q and ti is sampled from a distribution statistically close to DΛquiA,s(1b)
Ifti−ei is linearly independent of t1−e1,…,ti−1−ei−1, accept ti. Otherwise, repeat step (1a)(2)
LetT∈ℤm×m be the matrix whose columns are t1,…,tm. Output TNote thatAT=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 m2 samples from SamplePreA,TA,ui,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:Setup1λ,N: the setup algorithm takes a security parameter λ and a maximal number of users N as input and proceeds as follows:(1)
Pick Gaussian parameterss1,s2,ands3 and set the parameters n=nλ,q=qn,andm=mn. These parameters are implicitly known to all of the algorithms below.(2)
Samplel+3 random matrices: A1,A2,B,Dii∈l in ℤqn×m, where l is the length of message.(3)
Sample matrix with associated trapdoor:A,TA⟵TrapGen1n,1m,q.(4)
Output public parametersPP=A,A1,A2,B,Dii∈l, master secret key MSK=TA, a revocation list RL=∅, and a state ST=BT.PriKeyGenPP,MSK,id,and ST: this algorithm takes as input the public parameters PP, a master secret key MSK, an identity id∈0,1∗, and a state ST. Then it picks an unassigned leaf node ν from BT, stores id in that node, and performs the following steps:(1)
For each nodeθ∈Pathν, pick random matrix Uθ∈ℤqn×m and store it in node θ(2)
SampleR1⟵Dm×m, Eν⟵SamplePreA,TA,−A1+H0idBR1,s1(3)
SampleEθ,1Eθ,2⟵SampleLeftA,A1+H0idB,TA,Uθ,s1(4)
StoreHθ≔Eθ,1−EνR1−1Eθ,2 in node θ(5)
Output private keySKid=θ,Eθ,1Eθ,2θ∈Pathν,Eν,R1,STKeyUpdPP,MSK,t,RL,and ST: this algorithm takes the public parameters PP, a master secret key MSK, a time t∈0,1∗, a revocation list RL, and a state ST as input and proceeds as follows:(1)
SampleR2⟵Dm×m and Et⟵SamplePreA,TA,−A2+H0tBR2,s1(2)
∀θ∈KUNodesBT,RL,andt and sample Eθ,2′⟵Dℤm,s1m and compute Hθ′=EtR2−1Eθ,2′, where KUNodesBT,RL,andt is an algorithm KUNodes from [4](3)
SampleEθ,1′⟵SampleSubInvA,Hθ′−Hθ,TA,−Uθ−A2+H0tBEθ,2′,s1(4)
Output update keyKUt=θ,Eθ,1′Eθ,2′θ∈KUNodesBT,RL,t,Et,R2SignKeyGenSKidandKUt: this algorithm takes a private key SKid and an update key KUt as input and runs the following steps:(1)
SetAid,t≔AA1+H0idBA2+H0tB and compute Rid,t=H1idt and Fid,t≔Aid,t⋅Rid,t−1(2)
∀i,Ei,1Ei,2∈SKid and j,Ej,1′Ej,2′∈KUt, if ∃i=j, then set(2)Sid,t=Ei,1+Ej,1′EνEtEi,2R10Ej,2′0R2.(3)
GenerateSKid,t′ by running Lemma 4 which takes Sid,t as input (Sid,t is an invertible matrix with some norm which will be proved in the Theorem 1). Then, run the algorithm BasisDelAid,t,Rid,t,SKid,t′,s2 to generate SKid,t and output SKid,t.SignPP,id,t,SKid,t,andμ: the signing algorithm takes the public parameters PP, an identity id, a time t, a signing key SKid,t, and a message μ=μ1,…,μl∈0,1l as input and outputs signature σ as follows:(1)
Sample the algorithmσ⟵SampleLeftFid,t,B+∑i=1l−1μiDi,SKid,t,0,s3 such that Fid,tB+∑i=1l−1μiDi⋅σ=0, where s3≥SKid,t˜⋅ωlog4m(2)
Output signature σVerifyPP,id,t,μ,andσ : the verify algorithm takes the public parameters PP, an identity id∈0,1∗, a time t∈0,1∗, and a pair of message/signature μ,σ as input and accepts only if the following conditions are satisfied:(i)
σ∈ℤ4m, σ≤s34m(ii)
Fid,tB+∑i=1l−1μiDi⋅σ=0KeyRevid,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 ν associated with identity id and returns RL.Theorem 1.
S
id
,
t is an invertible matrix with small norm.Proof.
First, we show thatSid,t is a small norm matrix. From the construction, we know that(3)Ei,1≤s1⋅m,Ej,1′≤s1⋅m,Ei,2≤s1⋅m,Ej,2′≤s1⋅m,Eν≤s1⋅m,Et≤s1⋅m,R1≤αR⋅m,R2≤αR⋅m,which are small norm matrices. Then, we can get Sid,t≤max4s1m,ms1+αR. Second, we will show Sid,t is an invertible matrix. For matrix Sid,t, we make an elementary transformation and finally obtain(4)C≔Ei,1+Ej,1′−EνR1−1Ei,2−EtR2−1Ej,2′000R1000R2.
SinceEi,1+Ej,1′−EνR1−1Ei,2−EtR2−1Ej,2′=Ej,1′−Hj′−Hi, and by the SampleSubInv algorithm in the KeyGen phase, we can see Ej,1′−Hj′−Hi is an invertible matrix. Because R1 and R2 are ℤq-invertible matrices, then C is invertible and then Sid,t is an invertible matrix. In summary, Sid,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:n=λ, m=Onlogq, η=ωlogm, s1=Onlogqωlog2m, s2=Onlogqωlogn, s3=lm3/2ωlogm4, β=lm2+3lηm5/22 ωlogm4, q≥max2lm3ωlogm6,2Q, where λ 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 isEUF-sID-CMA secure provided that the SISq,n,m,β assumption holds.Proof.
AssumeA wins the game in Section 3 and Q is the signing queries maximum number. We can construct a solver ℬ that provides a valid solution to the SIS problem. A first gives the target identity and time id∗,t∗. ℬ is given a random instance of the q,n,m,andβ-SIS problem and is asked to return an admissible solution. That is,(i)
Provided: a matrixA0 from ℤqn×3m’s uniform distribution(ii)
Returned: any vectore0∈ℤ3m such that A0e0=0modq and 0≠e0≤β
ℬ performs as follows:Setup∗1λ,N,l: ℬ provides the adversary A with simulated parameters as follows:(1)
Run algorithmTrapGen to obtain B,TB⟵TrapGen1n,1m,q(2)
Choosel+3 random matrices U0,U1,U2∼Dm×m and Ri∗∼Dℤm,η and also choose l random scalars hi∈ℤq for i∈l. Let A=A0U0−1U1−1U2−1, A1=AU1−H0id∗Bmodq, A2=AU2−Ht∗Bmodq, and Di=A0Ri∗Ri∗Ri∗+hi⋅B∈ℤqn×m(3)
Output the parametersPP=A,A1,A2,B,andDii∈lPriKeyGen Query and Key Update Query: ℬ first picks a node ν∗∈BT and allots it to id∗. It is worth noting that there will be two types of adversaries:(i)
Type (a) adversaries are revoked users and can challenge the target identityid∗ before or on time t∗(ii)
Type (b) adversaries cannot challenge the target identityid∗ at any timeℬ picks a bit rev$⟵0,1 randomly as a guess for the type of adversarial behavior. Clearly, the probability of ℬ’s correct guesses is 1/2. Type (a) adversaries (rev=0): ℬ simulates each node θ’s matrix Uθ as follows:(i)
ifθ∈Pathν∗, sample Eθ,1,Eθ,2⟵Dℤm,s1m, and R1⟵Dm×m, set Uθ⟵AA1+H0id∗B⋅Eθ,1Eθ,2, Eν∗=−U1⋅R1. Compute Hθ≔Eθ,1−Eν∗R1−1Eθ,2, and store Hθ,Uθ in the node θ.(ii)
ifθ∉Pathν∗, sample Eθ,1′,Eθ,2′⟵Dℤm,s1m, and R2⟵Dm×m, set −Uθ⟵AA2+H0t∗B⋅Eθ,1′Eθ,2′, Et∗=−U2⋅R2. Store Uθ in the node θ.
Sinceid∗ has been revoked before time t∗, it has KUNodesBT,t∗∩Pathν∗=∅ and ℬ returns id∗’s private key θ,Eθ,1Eθ,2θ∈Pathν∗,Eν∗,R1 and t∗’s update key θ,Eθ,1′Eθ,2′θ∈KUNodesBT,t∗,Et∗,R2.
Type (b) adversaries (rev=1): ℬ simulates each node θ’s matrix Uθ as follows: Since id∗ is never queried, ℬ does not need to simulate id∗’s private key. It samples Eθ,1′,Eθ,2′⟵Dℤm,s1m and R2⟵Dm×m and sets −Uθ⟵AA2+H0t∗B⋅Eθ,1′Eθ,2′, Et∗=−U2⋅R2. It stores Uθ in the node θ. If t=t∗, ℬ returns t∗’s update key θ,Eθ,1′Eθ,2′θ∈KUNodesBT,t∗,Et∗,R2.Note that, when rev=0, for each node θ, Uθ is generated either through Uθ⟵AA1+H0id∗B⋅Eθ,1Eθ,2 or though −Uθ⟵AA2+H0t∗B⋅Eθ,1′Eθ,2′ where Eθ,1,Eθ,2⟵Dℤm,s1m and Eθ,1′,Eθ,2′⟵Dℤm,s1m. Since the distribution of AA1+H0id∗B=AAU1 and AA2+H0t∗B=AAU2 are statistically close to ℤqn×2m’s uniform distribution by leftover hash lemma, then all the above Uθ are statistically close to uniform over ℤqn×m; when rev=1, for each node θ, Uθ is generated either through or through uniform distribution in ℤqn×m, where Eθ,1′,Eθ,2′⟵Dℤm,s1m. No matter which case, we can have R1∼Dm×m and R2∼Dm×m and Eν∗=−U1⋅R1 and Et∗=−U2⋅R2. Since the distribution of R1 and R2 are Gaussian distribution, then the distribution of Eν∗ and Et∗ is statistically close to Gaussian distribution. In conclusion, the distribution of the simulated system is statistically close to the real system.
Forid≠id∗’s private key queries and t≠t∗’s update key queries, ℬ uses the trapdoor TB instead of TA. Let AA1+H0idB=AAU1+H0id−H0id∗B and AA2+H0tB=AAU2+H0t−H0t∗B. From the definition of FRD, H0id−H0id∗ and H0t−H0t∗ are nonsingular. Then, ℬ runs the sampleRightExt algorithm and generates id≠id∗’s private key(5)Eθ,1Eθ,2⟵SampleRightA,H0id−H0id∗B,U1,TB,Uθ,s2′∈ℤq2m×m,where s2′>TB˜⋅sU1⋅ωlogm. Moreover, ℬ samples R1′⟵Dm×m and calls algorithm RandBasisTB,s4 from [28]. It can obtain TB′ satisfying AA1+H0idB⋅−U1I⋅TB′R1′=0 where s4≥TB˜⋅ωlogn, that is, A⋅−U1TB′R1′=−A1+H0idBTB′R1′. Then, it sets Eν=−U1TB′R1′ and R1=TB′R1′ and returns θ,Eθ,1Eθ,2θ∈Pathν,Eν,R1. For all t≠t∗’s update key queries, ℬ runs(6)Eθ,1′Eθ,2′⟵SampleRightA,H0t−H0t∗B,U2,TB,−Uθ,s2′∈ℤq2m×m,where s2′>TB˜⋅sU2⋅ωlogm. Moreover, it samples R2′⟵Dm×m and then calls algorithm RandBasisTB,s4 to get a basis TB″ satisfying AA2+H0tB⋅−U2I⋅TB″R2′=0, where s4≥TB˜⋅ωlogn, that is, A⋅−U2TB′R2′=−A2+H0tBTB″R2′. It sets Et=−U2TB″R2′ and R2=TB″R2′ and then generates the update key θ,Eθ,1′Eθ,2′θ∈KUNodesBT,RL,t,Et,R2.
Since the parameters2′ is sufficiently large, Eθ,1’s distribution is statistically close to DΛqUθ−AAU1Eθ,2 and Eθ,1′’s distribution is statistically close to DΛq−Uθ−AAU2Eθ,2′. Eθ,2 and Eθ,2′’s distributions are distributed close to Dℤm,s2′m, respectively. Since TB′ and TB″ are the random bases of Λq⊥B, then Eν=−U1TB′R1′ and ET=−U2TB″R2′’s distributions are the same as those in the real system. R1=TB′R1′ and R2=TB″R2′ are ℤq-invertible, that is, R1 and R2 are distributed as in the real system.


## 4.3.1. Signing Key Query

ℬ first samples a random matrix R∗∼Dm×m and defines H1id∗t∗≔R∗. Then, it sets G=A0⋅R∗000R∗000R∗ and picks an empty list L. If the adversary A asks the signing key on identity id∗ and time t≠t∗, ℬ runs SampleRwithBasisG to obtain a random Rid∗,t∼D3m×3m and a short basis TFid∗,t for Fid∗,t=GRid∗,tmodq. Then, it saves the tuple id∗t,Rid∗,t,Fid∗,t,TFid∗,t in list L for future use and returns TFid∗,t to the adversary A. If the adversary A asks the signing key on identity id≠id∗ and time t, ℬ retrieves the list L and checks whether idt in L. If idt,Rid,t,Fid,t,TFid,t is in L, ℬ returns TFid,t to A. Otherwise, ℬ also runs SampleRwithBasisG to obtain a random Rid,t∼D3m×3m and a short basis TFid,t for Fid,t=GRid,tmodq. Then, it saves the tuple idt,Rid,t,Fid,t,TFid,t in list L for future use and returns TFid,t 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 H1 oracle queries and signing key queries are as in the real system.


## 4.3.2. Signature Queries

ℬ simulates signatures of messages μ for A’s adaptive signature queries as follows:(i)
If the queried messagesμ are under target identity id∗ in target time t∗, ℬ answers as follows:(1)
ComputeRμ=∑i=1l−1μiRi∗Ri∗Ri∗ and hμ=1+∑i=1l−1μihi(2)
Ifhμ=0 (mod q), abort the simulation(3)
Otherwise sample vector:(7)σ⟵SampleRightA0,hμB,Rμ,TB,0,s2′.(4)
Outputσ∈ℤ4m(ii)
If the queried messagesμ are under identity id≠id∗ or in time t≠t∗, ℬ first retrieves the list L and checks whether it has tuple idt,Rid,t,Fid,t,TFid,t. If yes, ℬ gets TFid,t and samples vector σ⟵SampleLeftFid,t,A0Rμ+hμB,TFid,t,0,s2′. Otherwise, ℬ also runs SampleRwithBasisG to obtain a random Rid,t∼D3m×3m and a short basis TFid,t for Fid,t=GRid,tmodq. Then, it saves the tuple idt,Rid,t,Fid,t,TFid,t in list L and uses TFid,t to sample algorithm σ⟵SampleLeftFid,t,A0Rμ+hμB,TFid,t,0,s2′. At last, ℬ returns σ to the adversary A.Forgery: ℬ obtains a forged signature σ∗ on an unqueried message μ∗ and performs the following:(1)
ComputeRμ∗=∑i=1l−1μ∗iRi∗Ri∗Ri∗ and hμ∗=1+∑i=1l−1μ∗ihi(2)
Ifhμ∗≠0 (mod q), abort the simulation(3)
Otherwise, separateσ∗=σ1∗Tσ2∗TT(4)
Outpute0=σ1∗+Rμ∗σ2∗∈ℤ3mFrom Lemma9, e0 is small and nonzero with good probability and is a valid q,n,m,β-SIS solution with good probability.Lemma 9.
IfA provides a valid forgery σ1∗Tσ2∗TT for message μ∗ with hμ∗=0 (mod q), then for polynomial function β=polyl,n,m=polyλ, e0=σ1∗+Rμ∗σ2∗∈ℤ3m satisfying e0∈Λ⊥A0 and 0≠e0≤β.Proof.
First, whenhμ∗=0, we have A0Rμ∗+hμ∗B=A0Rμ∗. Since σ∗ is message μ∗’s valid signature under identity id∗ in time t∗, then we can obtain(8)A0σ1∗+Rμ∗σ2∗=A0A0Rμ∗σ1∗σ2∗=0modq.
Next, we will show thate0 is appropriately short. Since Rμ∗ is the sum of l low-norm matrices Ri∗Ri∗Ri∗ and Ri∗ are nearly independent with the same variance VR1∗ and their coefficients are in 0,1, then we will have(9)VRμ∗=V∑i=1lμ∗iRi∗Ri∗Ri∗≈∑i=1lVRi∗Ri∗Ri∗=l⋅VR1∗R1∗R1∗.
In particular, since they are almost independent discrete Gaussian,ERμ∗≈ER1∗R1∗R1∗=0, PrRi∗Ri∗Ri∗>η3m=neglm and PrRμ∗>lη3m=neglm. With overwhelming probability e0≤β for β=polyl,n,m=polyλ, we set β=1+ηl3m4m⋅s3.
Finally, it remains to show thate0≠0. Suppose an easy case that σ2∗=0, then for a valid forgery, it must have σ1∗≠0, thus e0≠0. On the contrary, σ2∗≠0, since σ2∗<4m⋅s2≪q; thus, there must be at least one σ2∗’s coordinate that is nonzero modulo q. We set z be σ4∗’s last one coordinate. Let r∗ be Rμ∗’s last column and ri∗ be Ri∗’s last column for each i∈l. Then, we have r∗=∑i=1l−1μ∗iri∗, where the coefficients depend on the message bits. For r1∗, let v=−1μ∗1zr1∗, then e0=zr∗+e0′=v+e0″, where v depends on r1∗ and e0″ does not. The only information about r1∗ available to A is contained in the last column of D1’s last column. From a simple pigeonhole principle, there exists many admissible and equally likely vector r1∗ that are the same with A’s view. A cannot know the value of zr1∗ with probability exceeding once third, then every other zr1∗ would fail to do so. Thus, Pre0≠0≥1/2mm−1. If A forges a signature with probability ε with Q≤q/2, then the algorithm ℬ can solve the SISn,m,q,β problem with the advantage of 1/2mm−11/2⋅ε1−q−1Qq−1≥ε/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 realSetup, matrix A∈ℤqn×m is sampled from the algorithm TrapGen. Matrices A1,A2,B,andDii∈l are chosen uniformly at random. In simulated Setup∗, A=A0U0−1U1−1U2−1, A1=AU1−H0id∗Bmodq, A2=AU2−Ht∗Bmodq, Di=A0Ri∗Ri∗Ri∗+hi⋅B∈ℤqn×m for random U0,U1,U2∼Dm×m and Ri∗∼Dℤm,η, and B,TB⟵TrapGenq,n(ii)
In the realSign phase, algorithm SampleLeft generates signatures σ, whereas in the simulated Sign phase, signatures are generated by algorithm SampleLeft or algorithm SampleRight
We now argue that the distributionA,A1,A2,B,Dii∈l is statistically indistinguishable in the two experiments. Let(10)A′=A1A2D1⋯Dl∈ℤqn×l+2m.
Then, from Lemma2, we have(11)A,A′≈sA,AU1−H0id∗BAU2−H0t∗BAR1∗+h1B⋯ARl∗+hlB,for random matrices A,A′ from ℤqn×m,ℤqn×l+2m and(12)U1U2R0∗⋯Rl∗∼Dm×2m×Dℤm,ηl,chosen at random. Here, B’s distribution is statistically close to ℤqn×m’s uniform distribution. Therefore, the distribution of PP in the simulation is statistically indistinguishable to them in the real system.
For eachμ’s signature query, if Gaussian parameters s3ands3′ 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 2NmTm+Tsp to obtain a signature, where Tsp is the cost of executing the SamplePre algorithm. In scheme [11], it requires 7N2+2NTm to obtain a signature, where Tm is the cost of executing a multiplication operation in ℤq. In our RIBS scheme, it needs O9m2n+lmnT++Om2nTm+Tinv+Tsl level time to obtain a signature, where T+ is the cost of executing an addition operation in ℤq, Tinv is the cost of executing a matrix inversion operation in ℤ3m×3m, and Tsl is the cost of executing the SampleLeft algorithm. For the computation cost of verifying, three schemes require 3NmTm, N2+NTm and OmnTm+OlmnT+, respectively, to verify a signature. Since m>6Nlogq, 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).Table 1
Efficiency comparisons with previous works.
[20]
[21]
[22]
[10]
[11]
Ours
Signing key size
4
G
3
G
3
G
2
2
N
m
⋅
log
r
⋅
log
s
¯
2
m
4
N
⋅
log
s
N
s
1
m
+
s
R
m
Signature size
4
G
4
G
4
G
2
3
N
m
⋅
log
r
⋅
log
s
¯
3
m
2
N
log
σ
+
λ
log
N
+
λ
s
3
4
m
Computation cost of signing
O
1
e
3
e
6
e
2
N
m
T
m
+
T
sp
7
N
2
T
m
+
14
N
T
m
O
9
m
2
n
+
l
m
n
⋅
T
+
+
O
m
2
n
T
m
+
T
inv
+
T
sl
Computation cost of verifying
O
1
p
e
+
4
p
4
p
3
N
m
T
m
N
2
T
m
+
N
T
m
O
m
n
T
m
+
O
l
m
n
T
+
Authority’s workload
O
log
r
O
r
∅
O
log
r
O
r
O
log
r
N: security parameter; λ: positive integer; r: number of nonrevoked users; m>6Nlogq; s¯=mlogr⋅ωlogN; s=N5/2⋅2qωlogN; σ=12λsN; s1=Om⋅ωlogm; s3=ms1+sR⋅ωlog4m; G or G2 is the size of an element in the group G or G2; p and e denote a pairing operation and an exponentiation operation, respectively; T+ is the cost of executing an addition operation in ℤq; Tm is the cost of executing a multiplication operation in ℤq; Tsp is the cost of executing the Samplepre algorithm in [23]; Tinv is the cost of executing a matrix inversion operation in ℤ3m×3m; Tsl is the cost of executing the Sampleleft algorithm in [27]; ∅ denotes that the workload of the authority performing the update procedure is independent of the number of nonrevoked users.


### 5.2. Functionality Comparisons

Firstly, as indicated in Table2, 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.Table 2
Functionality comparisons with previous works.
Schemes
Key exposure resistance
Quantum attacks resistance
Model
Transport channel
Scalability
Assumption
[20]
Yes
No
SD
Public
Yes
q-DHE
[21]
Yes
No
SD
Public
Yes
CDH
[22]
Yes
No
SD
Public
Yes
(3,n)-MDHE
[10]
No
Yes
SD
Secure
No
SIS
[11]
No
Yes
RO
Public
No
RSIS
Ours
Yes
Yes
RO
Public
Yes
SIS


## 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 2NmTm+Tsp to obtain a signature, where Tsp is the cost of executing the SamplePre algorithm. In scheme [11], it requires 7N2+2NTm to obtain a signature, where Tm is the cost of executing a multiplication operation in ℤq. In our RIBS scheme, it needs O9m2n+lmnT++Om2nTm+Tinv+Tsl level time to obtain a signature, where T+ is the cost of executing an addition operation in ℤq, Tinv is the cost of executing a matrix inversion operation in ℤ3m×3m, and Tsl is the cost of executing the SampleLeft algorithm. For the computation cost of verifying, three schemes require 3NmTm, N2+NTm and OmnTm+OlmnT+, respectively, to verify a signature. Since m>6Nlogq, 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).Table 1
Efficiency comparisons with previous works.
[20]
[21]
[22]
[10]
[11]
Ours
Signing key size
4
G
3
G
3
G
2
2
N
m
⋅
log
r
⋅
log
s
¯
2
m
4
N
⋅
log
s
N
s
1
m
+
s
R
m
Signature size
4
G
4
G
4
G
2
3
N
m
⋅
log
r
⋅
log
s
¯
3
m
2
N
log
σ
+
λ
log
N
+
λ
s
3
4
m
Computation cost of signing
O
1
e
3
e
6
e
2
N
m
T
m
+
T
sp
7
N
2
T
m
+
14
N
T
m
O
9
m
2
n
+
l
m
n
⋅
T
+
+
O
m
2
n
T
m
+
T
inv
+
T
sl
Computation cost of verifying
O
1
p
e
+
4
p
4
p
3
N
m
T
m
N
2
T
m
+
N
T
m
O
m
n
T
m
+
O
l
m
n
T
+
Authority’s workload
O
log
r
O
r
∅
O
log
r
O
r
O
log
r
N: security parameter; λ: positive integer; r: number of nonrevoked users; m>6Nlogq; s¯=mlogr⋅ωlogN; s=N5/2⋅2qωlogN; σ=12λsN; s1=Om⋅ωlogm; s3=ms1+sR⋅ωlog4m; G or G2 is the size of an element in the group G or G2; p and e denote a pairing operation and an exponentiation operation, respectively; T+ is the cost of executing an addition operation in ℤq; Tm is the cost of executing a multiplication operation in ℤq; Tsp is the cost of executing the Samplepre algorithm in [23]; Tinv is the cost of executing a matrix inversion operation in ℤ3m×3m; Tsl is the cost of executing the Sampleleft algorithm in [27]; ∅ denotes that the workload of the authority performing the update procedure is independent of the number of nonrevoked users.


## 5.2. Functionality Comparisons

Firstly, as indicated in Table2, 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.Table 2
Functionality comparisons with previous works.
Schemes
Key exposure resistance
Quantum attacks resistance
Model
Transport channel
Scalability
Assumption
[20]
Yes
No
SD
Public
Yes
q-DHE
[21]
Yes
No
SD
Public
Yes
CDH
[22]
Yes
No
SD
Public
Yes
(3,n)-MDHE
[10]
No
Yes
SD
Secure
No
SIS
[11]
No
Yes
RO
Public
No
RSIS
Ours
Yes
Yes
RO
Public
Yes
SIS


## 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.



---

*Source: 1743421-2020-01-14.xml*