Research on Quantum-Attack-Resistant Strong Forward-Secure Signature Schemes

Abstract

The security of digital signatures depends significantly on the signature key. Therefore, to reduce the impact of leaked keys upon existing signatures and subsequent ones, a digital signature scheme with strong forward security could be an effective solution. Most existing strong forward-secure digital signature schemes rely on traditional cryptosystems, which cannot effectively resist quantum attacks. By introducing lattice-based delegation technology into the key-iteration process, a two-direction and lattice-based key-iteration algorithm with strong forward security is proposed. In the proposed algorithm, a unique key pair is assigned to the signer in every period. Based on the proposed algorithm, a strong forward-secure signature scheme is further put forward, which achieves resistance to quantum attacks. Performance analysis shows that under the security assumption of the SIS problem on the lattice, the proposed strong forward-secure signature scheme is existentially unforgeable under the random oracle model. Ultimately, based on the proposed strong forward-secure signature scheme, a remote identity-authentication scheme that is resistant to quantum attacks is proposed, ensuring post-quantum security in the user-authentication process.

1. Introduction

As one of the essential tools of digital authentication, digital signatures are widely applied to e-commerce and network communication. The security of digital signatures depends largely on the signature key. Leaked keys threaten entire signature systems, and entire systems can collapse due to key leakage. Leaked private keys render all signatures generated by them untrustworthy. Therefore, to ensure the legitimacy of the signature, the signer must invalidate previous signatures and rebuild a new signature system before signing.

To address the above problems, Anderson proposed the concept of forward security at the ACM CSS conference in 1997 [1]. They achieved forward security by updating the keys. In 2000, Anderson further produced the concept of backward security [2]. Backward security ensures that the leakage of the current key will not hamper future signing. In 2001, Burmester et al. put forward the concept of strong forward security [3], which further improves the security of the signature system. A strong forward-secure signature scheme can ensure both forward security and backward security.

Since then, the strong forward-secure signature scheme has been deeply studied. Cheng Yage et al. proposed a dynamic threshold signature scheme with strong forward security [4]. Li Fengyin et al. put forward a privacy-aware PKI model with strong forward security [5]. Yoneyama put forward a one-round authenticated key exchange with strong forward secrecy in the standard model against a constrained adversary [6]. The above signature schemes are, respectively based on the Chinese remainder theorem, RSA, and the Diffie–Hellman difficult problem, which cannot resist quantum attacks.

Identity-based Cryptography (IBC) has received great attention due to its efficiency in key management [7]. To ensure the security of signatures in the case of key leakage, the identity-based strong forward-security signature scheme was studied. However, these identity-based strong forward-security signature schemes are based on traditional cryptosystems, which cannot resist quantum attacks.

Unlike classical solutions, quantum digital signatures use quantum laws to sign a document with information-theoretical integrity, authenticity, and non-repudiation [8]. Quantum laws refer to the laws of quantum mechanics. Quantum cryptography applies the basic principles of quantum mechanics, such as the uncertainty principle, quantum no-cloning theorem, and quantum entanglement characteristics, to ensure the security of quantum cryptography [9]. Gottesman and Chung pioneered a quantum digital signature scheme based on the basic principles of quantum physics in 2001 [10]. The research of quantum digital signatures is still in an active stage, so there is no widely used standardization scheme. Various things can be called quantum digital signatures [11].

Quantum key distribution also exploits the properties of quantum mechanics to secure communications. It enables both parties in communication to generate and share a random, secure key. Quantum key distribution is only used to generate and distribute keys, and does not transmit any real messages. The current blockchain platform relies on digital signatures and is vulnerable to attacks by a quantum computer. Kiktenko and Pozhar proposed to introduce quantum key distribution into the blockchain [12]. Due to the tremendous progress in the deployment of quantum key distribution, practical secure quantum key distribution protocols are also being investigated [13]. The implementation of quantum key distribution involves highly specialized technologies and equipment, which increases the cost of implementation and maintenance. Realizing a perfect quantum key distribution system is a lengthy process due to challenges such as technical limitations and infrastructure requirements in practical applications [14].

From the perspective of practicality, post-quantum cryptography has higher practicability at present. Consistent with the goal of quantum cryptography, the research of post-quantum cryptography is also to protect communication and data security from attacks by a quantum computer. There are four mainstream post-quantum cryptography algorithms: lattice-based, encode-based, hash-based, and multivariate-based [15]. Lattice-based algorithms are considered to be one of the most promising post-quantum encryption algorithms because of their better balance among security, public-key size, private key size, and computation speed [16]. Post-quantum cryptography technologies are being explored to develop cryptography algorithms that remain secure in the presence of quantum adversaries. Although these algorithms show promising prospects, more research is needed to ensure their security, efficiency, and widespread application in the face of quantum threats [17].

Therefore, the lattice-based signature scheme with quantum-resistant attacks has become a research hotspot. Kansals et al. proposed group signature from lattices preserving forward security in a dynamic setting [18]. Liao et al. put forward a fully dynamic forward-secure group signature from lattice [19]. Le et al. put forward lattice blind signatures with forward security [20]. Wu et al. presented an efficient identity-based forward-secure signature scheme from lattices [21]. Zhang et al. raised a lattice-based strongly unforgeable forward-secure identity-based signature scheme with a flexible key update [22]. All the above signature schemes neglect backward security. To solve this problem, we propose a novel key-iteration algorithm, upon which a signature scheme is further proposed, to achieve strong forward security. The proposed signature scheme could guarantee quantum-attack-resistant strong forward security.

2. Preliminaries

2.1. Framework of Strong Forward-Secure Signature Scheme

A strong forward-secure signature scheme consists of the following four polynomial time algorithms.

• Parameter generation: input security parameter n, output public parameter PP, master key msk and user initial key usk.
• Key iteration and update: When the user ${\mathrm{U}}_{\mathrm{k}}$ wants to use the private key, he initiates a key request to PKG and sends the identity ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}$ together. PKG inputs the public parameters PP, master key msk, user initial key usk and user identity ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}$, then executes the algorithm to generate the initial forward private key ${\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|0}$ and initial backward private key ${\mathrm{s}\mathrm{k}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{T}}$. When iterating the forward private key, user inputs the current period i, user identity ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}$ and current forward private key ${\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$, then outputs the forward private key ${\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}+1}$ for the next period i + 1. When iterating the backward private key, user inputs the current period i, user identity ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}$ and current backward private key are input ${\mathrm{s}\mathrm{k}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$, then outputs the backward private key ${\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}-1}$ for the previous period i − 1. The private key of the i-th period is ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$ = ${\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}+{\mathrm{s}\mathrm{k}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$, which is the result of concatenating the forward private key and the backward private key. The iteration process of the private key is shown in Figure 1.
• Signature generation: User inputs his identity ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}$, the private key ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$ of the current period i and the message m, then outputs the signature ${\mathrm{e}}_{\mathrm{i}}$ at this period.
• Signature verification: The verifier inputs the user’s identity ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}$, the public key ${\mathrm{P}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$ of the current period i, the original message m and the signature ${\mathrm{e}}_{\mathrm{i}}$, if the signature is valid then accept it, otherwise reject it.

2.2. Security Model

The identity-based strong forward-secure signature scheme is existentially unforgeable under adaptive chosen-message attack. The security of the model is defined using a game in which challenger C and adversary A interact.

Parameter establishment: The challenger runs the parameter generation algorithm and sends the generated public parameter PP to the adversary while keeping the master key msk and user master key usk for itself.

Queries: Adversary A adaptively issues many different following queries to the challenger:

• Key query: A own the ability to ask any identity ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}$(k = 1,2,…,N) for the key of any period i (i $\le$ T), and C generates the key ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$ of identity ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}$ in period i and sends it to A.
• Signature query: A can inquire about the signature of any identity ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}$ in any period i (i $\le$ T), and C generates the signature ${\mathrm{e}}_{\mathrm{i}}$ of the identity ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}$ in period i and sends it to A.

Forgery: A outputs an identity ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}^{\mathrm{*}}$, period ${\mathrm{i}}^{\mathrm{*}}$, message ${\mathrm{m}}^{\mathrm{*}}$ and signature ${{\mathrm{e}}_{\mathrm{i}}}^{\mathrm{*}}$. If the ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}^{\mathrm{*}}$ has not been subjected to key inquiry and signature inquiry, and the signature ${{\mathrm{e}}_{\mathrm{i}}}^{\mathrm{*}}$ will be verified to pass, then A wins the game. The advantage of A winning is:

$${\mathrm{A}\mathrm{d}\mathrm{v}}_{\mathrm{A},\mathrm{C}}^{\mathrm{U}\mathrm{n}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{g}\mathrm{e}}\left(\mathsf{\lambda }\right):=\mathrm{P}\mathrm{r}[\mathrm{A} \mathrm{w}\mathrm{i}\mathrm{n}\mathrm{s}]=\mathrm{n}\mathrm{e}\mathrm{g}\mathrm{l}\left(\mathsf{\lambda }\right)$$

2.3. Lattices and Hardness Assumptions

Definition 1

([23] Lattice). Lattice is a collection of linear combinations of all integer coefficients of n linearly independent vector groups $\bigwedge =\mathsf{L}({\mathsf{x}}_1,{\mathsf{x}}_2,\cdots \cdots {\mathsf{x}}_{\mathsf{n}})=\left\{\sum _{\mathsf{i}=1}^{\mathsf{n}}{\mathsf{a}}_{\mathsf{i}}{\mathsf{b}}_{\mathsf{i}}|{\mathsf{a}}_{\mathsf{i}}\in \mathsf{Z}\right\}$, namely: ${\mathsf{x}}_1,{\mathsf{x}}_2,\cdots \cdots {\mathsf{x}}_{\mathsf{n}}$.

Definition 2

([24] Full-rank lattice). Define the m-dimensional full-rank q-ary lattice as: ${\bigwedge }_{\mathsf{q}}^{\perp }\left(\mathsf{A}\right)=\left\{\mathsf{x}\in {\mathsf{Z}}^{\mathsf{m}}|\mathsf{A}\mathsf{x}=0(\mathsf{m}\mathsf{o}\mathsf{d}\mathsf{q})\right\}$, ${\bigwedge }_{\mathsf{q}}^{\mathsf{u}}\left(\mathsf{A}\right)=\left\{\mathsf{x}\in {\mathsf{Z}}^{\mathsf{m}}|\mathsf{A}\mathsf{x}=\mathsf{u}(\mathsf{m}\mathsf{o}\mathsf{d}\mathsf{q})\right\}$. Among them, q is a prime number, m and n are positive integers, matrix $\mathsf{A}\in {\mathsf{Z}}_{\mathsf{q}}^{\mathsf{n}\times \mathsf{m}}$, and vector $\mathsf{u}\in {\mathsf{Z}}_{\mathsf{q}}^{\mathsf{n}}$. ${\bigwedge }_{\mathsf{q}}^{\perp }\left(\mathsf{A}\right)$ and ${\bigwedge }_{\mathsf{q}}^{\mathsf{u}}\left(\mathsf{A}\right)$ can be abbreviated as ${\bigwedge }^{\perp }\left(\mathsf{A}\right)$ and ${\bigwedge }^{\mathsf{u}}\left(\mathsf{A}\right)$.

Definition 3

([24] SIS problem). Given an integer q, a matrix $\mathsf{A}\in {\mathsf{Z}}_{\mathsf{q}}^{\mathsf{n}\times \mathsf{m}}$ and a real number β, find a non-zero vector e such that Ae = 0 mod q $0<\left|\right|\mathsf{e}\left|\right|\le \mathsf{\beta }$ and such a problem is called an SIS problem. The SIS problem is considered to be a difficult computational problem, where a solution that satisfies the conditions cannot be found within the effective time. Based on this difficult assumption, the SIS problem is widely used to construct lattice-based Cryptography schemes.

Definition 4

([24] Gaussian distribution). For any positive parameter σ $\in$ R and any vector a $\in$ ${\mathsf{R}}^{\mathsf{n}}$, there is ${\mathsf{\rho }}_{\mathsf{\sigma },\mathsf{a}}\left(\mathsf{x}\right)=\mathsf{e}\mathsf{x}\mathsf{p}\left(-\mathsf{\pi }\frac{{\left|\right|\mathsf{x}-\mathsf{a}\left|\right|}^2}{{\mathsf{\sigma }}^2}\right)$.

Definition 5

([24,25] Trapdoor-Generation Algorithm). There is a PPT algorithm, given a prime number q $\ge$ 3, positive integer m $\ge$ 6 nlogq, security parameter n, run algorithm TrapGen(q,n) → (A,T), output a set of bases $\mathsf{T}\in {\mathsf{Z}}^{\mathsf{m}\times \mathsf{m}}$ of matrix $\mathsf{A}\in {\mathsf{Z}}_{\mathsf{q}}^{\mathsf{n}\times \mathsf{m}}$ and lattice ${\bigwedge }^{\perp }\left(\mathsf{A}\right)$, so that the distribution of A and the uniform distribution on ${\mathsf{Z}}_{\mathsf{q}}^{\mathsf{n}\times \mathsf{m}}$ are statistically Indistinguishable, and the conditions $\left|\right|\mathsf{T}\left|\right|$ $\le$ $\mathsf{O}$(nlbq) and $\left|\right|₸\left|\right|$ $\le \mathsf{O}\left(\sqrt{\mathsf{n}\mathsf{l}\mathsf{b}\mathsf{q}}\right)$ hold. where ₸ represents the basis after Gram-Schmidt orthogonalization of T. Trapdoor is a special type of key, usually generated in a public-key cryptosystem, which can achieve specific security functions such as encryption, signature, identity authentication, etc.

Definition 6

([26] Lattice-basis delegation algorithm). Let A∈${\mathsf{Z}}_{\mathsf{q}}^{\mathsf{n}\times \mathsf{m}}$ be a full-rank matrix, matrix $\mathsf{R}\in {\mathsf{D}}_{\mathsf{m}\times \mathsf{m}}$, T is a set of bases of lattice ${\bigwedge }^{\perp }\left(\mathsf{A}\right)$, Gaussian parameters satisfy $\mathsf{\sigma }>\left|\right|₸\left|\right|·{\mathsf{\sigma }}_{\mathsf{R}}\sqrt{\mathsf{m}}·\mathsf{\omega }\left({\mathsf{l}\mathsf{b}}^{3/2}\mathsf{m}\right)$. The Gaussian parameter ${\mathsf{\sigma }}_{\mathsf{R}}$ satisfies ${\mathsf{\sigma }}_{\mathsf{R}}=\sqrt{\mathsf{n}\mathsf{l}\mathsf{b}\mathsf{q}}·\mathsf{\omega }\left(\sqrt{\mathsf{l}\mathsf{b}\mathsf{m}}\right)$, ${\mathsf{D}}_{\mathsf{m}\times \mathsf{m}}$ represents the matrix distribution in ${\mathsf{Z}}^{\mathsf{m}\times \mathsf{m}}$ that satisfies ${\left({\mathsf{D}}_{{\mathsf{\sigma }}_{\mathsf{R}}}^{\mathsf{m}}\right)}^{\mathsf{m}}$ and the modulo q is invertible. Then there is a PPT algorithm BasisDel(A,R,T,$\mathsf{\sigma }$) that can output a set of bases ${\mathsf{T}}_{\mathsf{B}}$ for the lattice ${\bigwedge }^{\perp }\left(\mathsf{A}{\mathsf{R}}^{-1}\right)$, such that $\left|\right|{\mathsf{T}}_{\mathsf{B}}\left|\right|<\mathsf{\sigma }/\mathsf{\omega }\left(\sqrt{\mathsf{l}\mathsf{b}\mathsf{m}\mathsf{q}}\right)$. The generation of a set of lattice trapdoors is a relatively complex process. In some cases, when multiple pairs of lattice trapdoors are required, the lattice-basis delegation algorithm can be utilized to quickly generate another pair of related new lattice bases from a known pair.

Definition 7

([24] Difficulty specification of small integer solution problems). Knowing any polynomial bounded real number m,$\mathsf{\beta }=\mathsf{p}\mathsf{o}\mathsf{l}\mathsf{y}\left(\mathsf{n}\right)$ and prime numbers $\mathsf{q}\ge \mathsf{\beta }·\mathsf{\omega }\left(\sqrt{\mathsf{n}\mathsf{l}\mathsf{b}\mathsf{n}}\right)$, the difficulty of solving the SIS problem with average instances is comparable to that of solving the approximate shortest independent vectors problem with the worst-case on the lattice (shortest independent vectors problem, ${\mathsf{S}\mathsf{I}\mathsf{V}\mathsf{P}}_{\mathsf{\gamma }}$), where $\mathsf{\gamma }=\mathsf{\beta }·\mathsf{O}\left(\sqrt{\mathsf{n}}\right)$.

Definition 8

(Hash function). Randomly select prime numbers q, n, $\mathsf{m}>64+\mathsf{n}\mathsf{l}\mathsf{o}\mathsf{g}\mathsf{n}/\mathsf{l}\mathsf{o}\mathsf{g}3$, and define the following hash functions:${\mathsf{H}}_1:{\left\{\mathrm{0,1}\right\}}^{\mathsf{*}}\to {\mathsf{Z}}^{\mathsf{m}\times \mathsf{m}}$,${\mathsf{H}}_2:{\left\{\mathrm{0,1}\right\}}^{\mathsf{*}}\to \left\{\mathsf{v}:\mathsf{v}\in {\left\{-\mathrm{1,0},1\right\}}^{\mathsf{k}},\left|\right|\mathsf{v}\left|\right|\le \mathsf{k}\right\}$.

Lemma 1

([27] Rejection sampling). Let V be a subset of above ${\mathsf{Z}}^{\mathsf{m}}$, and the norm of the elements of V does not exceed T, r ∈ R exists, $\mathsf{r}=\mathsf{\omega }\left(\mathsf{T}\sqrt{\mathsf{l}\mathsf{o}\mathsf{g}\mathsf{m}}\right)$, h:V → R is a probability distribution, there is a constant M = O(1)) such that The probability of the distribution satisfying the following two algorithms is statistically asymptotic:

• v $\leftarrow$ h, z $\leftarrow$ ${\mathrm{D}}_{\mathrm{v},\mathrm{r}}^{\mathrm{m}}$, output signature(v,z) with probability $\mathrm{m}\mathrm{i}\mathrm{n}(1,\frac{{\mathrm{D}}_{{\mathrm{r}}_{\mathrm{i}}}^{\mathrm{m}}\left(\mathrm{z}\right)}{{\mathrm{M}\mathrm{D}}_{\mathrm{v},\mathrm{r}}^{\mathrm{m}}\left(\mathrm{z}\right)})$;
• v $\leftarrow$ h, z $\leftarrow$ ${\mathrm{D}}_{\mathrm{r}}^{\mathrm{m}}$, output the signature (v,z) with probability $\frac{1}{\mathrm{M}}$.

Lemma 2

([28] Fork Lemma). Let q be a positive integer and H be a set with h > 2 elements. Let IG be a parameter generation algorithm, B is a random algorithm, the input of algorithm B is {x,${\mathsf{h}}_1$,…,${\mathsf{h}}_{\mathsf{q}}$}, and the output is (J,$\mathsf{\sigma }$), where x∈{0,…,q}, ${\mathsf{h}}_{\mathsf{i}}$∈H (i∈[q]). Let the acceptance probability acc of algorithm B be the probability that J $\ge$ 1 in the trial EXP = [ x ← IG; ${\mathsf{h}}_1$,…,${\mathsf{h}}_{\mathsf{q}}$←H; (J,σ) ← B(x,${\mathsf{h}}_1$,…,${\mathsf{h}}_{\mathsf{q}}$)].Let the fork algorithm${\mathsf{F}}_{\mathsf{B}}$related to B is expressed as follows:

• Algorithm ${\mathrm{F}}_{\mathrm{B}}$ input x;
• Randomly select ρ ∈ {0,1};
• Randomly select ${\mathrm{h}}_1$,…,${\mathrm{h}}_{\mathrm{q}}$ from the set H;
• (I,$\mathsf{\sigma }$) ← B(x,${\mathrm{h}}_1$,…,${\mathrm{h}}_{\mathrm{q}}$; ρ);
• If I = 0, return (0, ε, ε);
• Randomly select ${\mathrm{h}\mathrm{’}}_1$,…,${\mathrm{h}\mathrm{’}}_{\mathrm{q}}$ from the set H;
• (I$\mathrm{’}$, $\mathsf{\sigma }\mathrm{’}$) ← B(x, ${\mathrm{h}}_1$, … , ${\mathrm{h}}_{\mathrm{I}-1}$, ${\mathrm{h}\mathrm{’}}_{\mathrm{I}}$, … , ${\mathrm{h}\mathrm{’}}_{\mathrm{q}}$; ρ);
• If I = I $\mathrm{’}$ and h$\ne$h$\mathrm{’}$, output (1, $\mathsf{\sigma }$, $\mathsf{\sigma }\mathrm{’}\mathrm{’}$); otherwise output (0, ε, ε), let frk=Pr[b=1,x←IG; (b,σ,σ$\mathrm{’}$)←${\mathrm{F}}_{\mathrm{B}}\left(\mathrm{x}\right)$], then frk$\ge$acc$·(\frac{\mathrm{a}\mathrm{c}\mathrm{c}}{\mathrm{q}}-\frac{1}{\mathrm{h}})$.

The random oracle model (ROM) is a universal model for proving the security of digital signature schemes. Under the ROM model, an important technology to prove the security of the scheme is the random oracle replay technology, i.e., to solve a hard problem of consciousness by replaying the hash value. The theoretical basis of this technique is the Fork Lemma.

3. A Strong Forward-Secure Signature Scheme Based on Identity on Lattice

To achieve quantum-attack-resistant security, this section introduces a lattice-basis delegation technology into the key-iteration process and proposes a key-iteration algorithm. This algorithm divides the key into T periods and assigns a unique key pair to each period through forward and backward iterations of two initial keys, which ensures strong forward security of the key. Then, an identity-based signature scheme with strong forward security that can resist quantum attacks is constructed using the proposed key-iteration algorithm.

3.1. Strong Forward-Security Key-Iteration Algorithm

Generating a set of lattice bases is relatively complex using the trapdoor-generation algorithm. However, when multiple pairs of lattice bases are needed, the lattice-delegation technology can quickly generate another pair of related new lattice bases based on a known pair. To ensure the security of signatures after the private key is leaked, this section introduces lattice-delegation technology into the key-iteration process, and proposes a bidirectional key-iteration algorithm with strong forward security. The proposed algorithm assigns a unique key pair for each period, therefore ensuring the forward security and backward security of the key. Specifically, in the key-iteration process, PKG divides the key into T periods, the signatures of different periods are relatively independent, and it is impossible to generate keys of other periods from the keys of a certain period. This solves the problem of whether the signature is still legal after the private key is leaked. The key-iteration algorithm for strong forward security is as follows:

3.1.1. Symbol Description

The specific meanings of the symbols used in the strong forward-security signature scheme constructed in this paper are shown in

Table 1. Symbols in Strong Forward-Secure Signature Scheme.

Symbol	Meaning
${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}$	The identity of user K
${\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{A}}_0}}$	User K’s master private key
${\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{B}}_0}}$	User K’s master public key
${\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|0}$	User K’s initial forward private key
${\mathrm{s}\mathrm{k}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|0}$	User K’s initial backward private key
${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{t}}$	The private key of user K in period t
${\mathrm{P}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{t}}$	The public key of user K in period t
PKG	key generation center
${\mathrm{e}}_{\mathsf{i}}$	signature

.

3.1.2. System Initialization

The strong forward-secure key-iteration algorithm has two entities: PKG and user. First, PKG performs parameter generation and master key generation, then publishes the parameters and sends the master key to the user through a secure channel. Users use the master key and the user key for key iteration and update.

• System parameter generation

PKG generates parameters, Setup(n) → PP:PKG inputs security parameter n, then randomly selects a prime number q, the prime $\mathrm{m}>64+\mathrm{n}\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{n}/\mathrm{l}\mathrm{o}\mathrm{g}3$, a Gaussian parameter ${\mathsf{\sigma }}_{\mathrm{R}}$ satisfies the relation ${\mathsf{\sigma }}_{\mathrm{R}}=\sqrt{\mathrm{n}\mathrm{l}\mathrm{b}\mathrm{q}}·\mathsf{\omega }\left(\sqrt{\mathrm{l}\mathrm{b}\mathrm{m}}\right)$, and a hash function ${\mathrm{H}}_1$. Then PKG publishes the parameters $\mathrm{P}\mathrm{P}=(\mathrm{n},\mathrm{q},\mathrm{m},{\mathsf{\sigma }}_{\mathrm{R}}{,\mathrm{H}}_1)$.

2.

Master key generation

PKG generates master key, KeyGen(PP) → $\left\{\right({\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{A}}_0},{\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{A}}_0}}),({\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{B}}_0},{\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{B}}_0}}\left)\right\}$: PKG inputs the public parameter PP, and generates the master key through the trapdoor-generation algorithm.

$\mathrm{T}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{G}\mathrm{e}\mathrm{n}(\mathrm{q},\mathrm{n})\to ({\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{A}}_0},{\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{A}}_0}})$, $\mathrm{T}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{G}\mathrm{e}\mathrm{n}(\mathrm{q},\mathrm{n})\to ({\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{B}}_0},{\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{B}}_0}})$, where ${\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{A}}_0}}$ and ${\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{B}}_0}}$ are the user’s master private key i.e., $\mathrm{m}\mathrm{s}\mathrm{k}=({\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{A}}_0}},{\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{B}}_0}})$,${\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{A}}_0}$ and ${\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{B}}_0}$ are the user’s master public key i.e., $\mathrm{m}\mathrm{p}\mathrm{k}=({\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{A}}_0},{\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{B}}_0})$. PKG transmits msk and mpk to users through a secure channel.

3.

User master key generation

User ${\mathrm{U}}_{\mathrm{k}}$(k = 1,2,…,N) generates user master key using public parameter PP. $\mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}\left(\mathrm{P}\mathrm{P}\right)\to ({\mathrm{U}}_{\mathrm{k}{\mathrm{A}}_0},{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}),({\mathrm{U}}_{\mathrm{k}{\mathrm{B}}_0},{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}})\}$: The user ${\mathrm{U}}_{\mathrm{k}}$ inputs the public parameter PP, and generates the user master key through the trapdoor-generation algorithm. $\mathrm{T}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{G}\mathrm{e}\mathrm{n}(\mathrm{q},\mathrm{n})\to ({\mathrm{U}}_{\mathrm{k}{\mathrm{A}}_0},{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}})$, $\mathrm{T}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{G}\mathrm{e}\mathrm{n}(\mathrm{q},\mathrm{n})\to ({\mathrm{U}}_{\mathrm{k}{\mathrm{B}}_0},{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}})$, where ${\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}$ and ${\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}$ are the user master private key i.e., $\mathrm{u}\mathrm{s}\mathrm{k}=({\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}},{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}})$, ${\mathrm{U}}_{\mathrm{k}{\mathrm{A}}_0}$ and ${\mathrm{U}}_{\mathrm{k}{\mathrm{B}}_0}$ are the user master public key i.e., $\mathrm{u}\mathrm{p}\mathrm{k}=({\mathrm{U}}_{\mathrm{k}{\mathrm{A}}_0},{\mathrm{U}}_{\mathrm{k}{\mathrm{B}}_0})$. In addition, the user ${\mathrm{U}}_{\mathrm{k}}$ selects two sets of Gaussian parameters $\mathsf{\sigma }=({\mathsf{\sigma }}_0,{\mathsf{\sigma }}_1,\cdots \cdots ,{\mathsf{\sigma }}_{\mathrm{T}})$, $\mathsf{\sigma }\mathrm{’}=({\mathsf{\sigma }\mathrm{’}}_0,{\mathsf{\sigma }\mathrm{’}}_1,\cdots \cdots ,{\mathsf{\sigma }\mathrm{’}}_{\mathrm{T}})$, to satisfies $\mathsf{\sigma }>\left|\right|{\mathrm{Ū}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}\left|\right|·{\mathsf{\sigma }}_{\mathrm{R}}\sqrt{\mathrm{m}}·\mathsf{\omega }\left({\mathrm{l}\mathrm{b}}^{3/2}\mathrm{m}\right)$ and $\mathsf{\sigma }\mathrm{’}>$ $\left|\right|{\mathrm{Ū}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}\left|\right|·{\mathsf{\sigma }}_{\mathrm{R}}\sqrt{\mathrm{m}}·\mathsf{\omega }\left({\mathrm{l}\mathrm{b}}^{3/2}\mathrm{m}\right)$. Where ${\mathrm{Ū}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}$ and ${\mathrm{Ū}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}$ are, respectively, the basis of ${\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}$, ${\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}$ after Gram-Schmidt orthogonalization.

3.1.3. Key-Iteration Algorithm

User ${\mathrm{U}}_{\mathrm{k}}$ performs key iteration using identity and master public and private key pair. Iteration $({\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{A}}_0}},{\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{B}}_0}},{{\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{A}}_0},{\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{B}}_0},\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}},{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}},{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}})$ $\to$ (${\mathrm{S}\mathrm{K}}_{{\mathrm{U}}_{\mathrm{k}}}$, ${\mathrm{P}\mathrm{K}}_{{\mathrm{U}}_{\mathrm{k}}}$): The user ${\mathrm{U}}_{\mathrm{k}}$ enters the master private key $({\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{A}}_0}},{\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{B}}_0}})$, the master public key ${(\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{A}}_0},{\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{B}}_0})$, the user master private key $({\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}},{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}})$ and the identity ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}$ of the user ${\mathrm{U}}_{\mathrm{k}}$. During the key-iteration process, the user performs the following operations:

• Forward private key iterative algorithm

The user ${\mathrm{U}}_{\mathrm{k}}$ generates the initial forward private key at period t = 0: ${\mathrm{R}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|0}={\mathrm{H}}_1\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}\right|\left|0\right)$, ${\mathrm{A}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|0}={\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{A}}_0}·{\left({\mathrm{R}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|0}\right)}^{-1}$, $\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}\mathrm{D}\mathrm{e}\mathrm{l}({\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{A}}_0},{\mathrm{R}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|0},{\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{A}}_0}},{\mathsf{\sigma }}_0)\to {\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|0}$, where ${\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|0}$ is the initial forward private key with forward security;

The user ${\mathrm{U}}_{\mathrm{k}}$ iterates the forward private key from period i − 1 to period i: ${\mathrm{R}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}-1}={\mathrm{H}}_1\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}\right||\mathrm{i}-1){\mathrm{H}}_1\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}\right||\mathrm{i}-2)\cdots \cdots {\mathrm{H}}_1\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}\right|\left|1\right){\mathrm{H}}_1\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}\right|\left|0\right)$, ${\mathrm{A}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}-1}={\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{A}}_0}·{\left({\mathrm{R}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}-1}\right)}^{-1}$, and compute the ${\mathrm{R}}_{\mathrm{i}}={\mathrm{H}}_1\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}\right|\left|\mathrm{i}\right)$, then use algorithm$\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}\mathrm{D}\mathrm{e}\mathrm{l}({\mathrm{A}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}-1},{\mathrm{R}}_{\mathrm{i}},{\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}-1},{\mathsf{\sigma }}_{\mathrm{i}})\to {\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$, since the forward private key ${\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$ of the i-th period is generated by the forward private key ${\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}-1}$ of the i − 1 period through the hash function and lattice-basis delegation algorithm, which ensures that the forward private keys ${({\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|0},\cdots \cdots ,\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}-1},{\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}},\cdots \cdots ,{\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{T}})$ have forward-secure.

2.

Backward private key-iteration algorithm

The user ${\mathrm{U}}_{\mathrm{k}}$ generates the initial backward private key in the period t=T: ${\mathrm{R}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{T}}={\mathrm{H}}_1\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}\right|\left|\mathrm{T}\right)$, and compute the ${\mathrm{A}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{T}}={\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{B}}_0}·{\left({\mathrm{R}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{T}}\right)}^{-1}$, then use algorithm $\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}\mathrm{D}\mathrm{e}\mathrm{l}({\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{B}}_0},{\mathrm{R}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{T}},{\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{B}}_0}},{\mathsf{\sigma }\mathrm{’}}_{\mathrm{T}})\to {\mathrm{s}\mathrm{k}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{T}}$, where ${\mathrm{s}\mathrm{k}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{T}}$ is the initial backward private key with backward security.

The user ${\mathrm{U}}_{\mathrm{k}}$ iterates the backward private key from period i to period i − 1: ${\mathrm{R}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}={\mathrm{H}}_1\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}\right|\left|\mathrm{T}\right){\mathrm{H}}_1\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}\right||\mathrm{T}-1)\cdots \cdots {\mathrm{H}}_1\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}\right||\mathrm{i}+1){\mathrm{H}}_1\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}\right|\left|\mathrm{i}\right)$, ${\mathrm{A}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}={\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{B}}_0}·{\left({\mathrm{R}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}\right)}^{-1}$, and compute the ${\mathrm{R}\mathrm{’}}_{\mathrm{i}-1}={\mathrm{H}}_1\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}\right|\left|\mathrm{i}\right)$, then use algorithm $\mathrm{B}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}\mathrm{D}\mathrm{e}\mathrm{l}({\mathrm{A}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}},{\mathrm{R}\mathrm{’}}_{\mathrm{i}-1},{\mathrm{s}\mathrm{k}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}},{\mathsf{\sigma }\mathrm{’}}_{\mathrm{i}-1})\to {\mathrm{s}\mathrm{k}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}-1}$, since the backward private key ${\mathrm{s}\mathrm{k}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}-1}$ of the i − 1th period is generated by the backward private key ${\mathrm{s}\mathrm{k}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$ of the i-th period through the hash function and lattice-basis delegation algorithm, which ensures the backward private keys ${({\mathrm{s}\mathrm{k}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|0},\cdots \cdots ,\mathrm{s}\mathrm{k}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}-1},{\mathrm{s}\mathrm{k}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}},\cdots \cdots ,{\mathrm{s}\mathrm{k}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{T}})$ have backward secure.

The private key of the user ${\mathrm{U}}_{\mathrm{k}}$ in period i is ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}={\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}+{\mathrm{s}\mathrm{k}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$. ${\mathrm{S}\mathrm{K}}_{{\mathrm{U}}_{\mathrm{k}}}=({\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|0},{\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|1},\cdots \cdots {,\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{T}})$ as all the private keys of the user ${\mathrm{U}}_{\mathrm{k}}$ in T periods, the user ${\mathrm{U}}_{\mathrm{k}}$ generates all the private keys and stores the private key set ${\mathrm{S}\mathrm{K}}_{{\mathrm{U}}_{\mathrm{k}}}$. Then calculate ${\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}={\mathrm{A}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}+{\mathrm{A}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$, ${\mathrm{T}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}={\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$, then the public key of the user ${\mathrm{U}}_{\mathrm{k}}$ in the i-th period is ${\mathrm{P}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}=({\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}},{\mathrm{T}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}})$. The public key set of the user ${\mathrm{U}}_{\mathrm{k}}$ in the T-period is ${\mathrm{P}\mathrm{K}}_{{\mathrm{U}}_{\mathrm{k}}}=({\mathrm{P}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|0},{\mathrm{P}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|1},\cdots \cdots {,\mathrm{P}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{T}})$. After the user ${\mathrm{U}}_{\mathrm{k}}$ generates the public key set, he stores ${\mathrm{P}\mathrm{K}}_{{\mathrm{U}}_{\mathrm{k}}}$ carefully at first, and then publishes the public key together with the signature after signing.

3.1.4. Key Update

The user ${\mathrm{U}}_{\mathrm{k}}$ updates the key, Update(q,n) $\to$ (${\mathrm{S}\mathrm{K}\mathrm{’}}_{{\mathrm{U}}_{\mathrm{k}}},{\mathrm{P}\mathrm{K}\mathrm{’}}_{{\mathrm{U}}_{\mathrm{k}}}$): To ensure the security of the signature system, users are advised to update their keys periodically. Under the circumstances in which the user key is not leaked and is still within the T-period, the user continues to use the original master key without PKG updating. To generate a new user master key in such cases, only step 3 in Section 3.1.1 needs to be repeated, followed by the calculation of key iteration as described in Section 3.1.2. When the key is used up or the key is leaked, the user sends a key request to PKG again to update the master key, i.e., the user will redo all the steps in Section 3.1.1 and Section 3.1.2 to update the key. Since the lattice-basis delegation algorithm takes less time to calculate than the trapdoor-generation algorithm, it will complete the calculation task quickly, which ensures that the user can update the key in a relatively short time.

3.2. Strong Forward-Secure Signature Scheme on Lattice

This section provides a detailed description of a strong forward-secure signature scheme. The construction of the signature scheme is based on the strong forward-secure key-iteration algorithm KI put forward in Section 3.1. It guarantees strong forward security of signatures under a quantum attack environment.

3.2.1. Parameter Generation

The strong forward-secure signature scheme on the lattice is composed of two entities, the identity-based cryptosystem IBC user and the key generation center PKG. When the user needs to obtain the key, he sends a key request to PKG, which includes the user’s ID and the period T of the required key. PKG will execute the parameter generation algorithm as soon as it receives the key request:

Setup(n) → PP: PKG inputs the security parameter n, and randomly selects the prime number q, $\mathrm{m}>64+\mathrm{n}\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{n}/\mathrm{l}\mathrm{o}\mathrm{g}3$, three sets of Gaussian parameters $\mathsf{\sigma }=({\mathsf{\sigma }}_0,{\mathsf{\sigma }}_1,\cdots \cdots ,{\mathsf{\sigma }}_{\mathrm{T}})$, $\mathsf{\sigma }\mathrm{’}=({\mathsf{\sigma }\mathrm{’}}_0,{\mathsf{\sigma }\mathrm{’}}_1,\cdots \cdots ,{\mathsf{\sigma }\mathrm{’}}_{\mathrm{T}})$,$\mathsf{\delta }=({\mathsf{\delta }}_0,{\mathsf{\delta }}_1,\cdots \cdots ,{\mathsf{\delta }}_{\mathrm{T}})$and a hash function ${\mathrm{H}}_2:{\left\{\mathrm{0,1}\right\}}^{\mathrm{*}}\to \left\{\mathrm{v}:\mathrm{v}\in {\left\{-\mathrm{1,0},1\right\}}^{\mathrm{k}},\left|\right|\mathrm{v}\left|\right|\le \mathrm{k}\right\}$. After that PKG publishes the parameters $\mathrm{P}\mathrm{P}=(\mathrm{n},\mathrm{q},\mathrm{m},\mathsf{\sigma },{\mathsf{\sigma }\mathrm{’},\mathsf{\delta },\mathrm{H}}_2)$.

3.2.2. Key Generation

Suppose the user is ${\mathrm{U}}_{\mathrm{k}}$, the user’s identity ID is ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}$, and the required key period is T. The user invokes the strong forward-secure key-iteration algorithm in 3.1 to generate a signature key:

KeyGen(PP) $\to$ (${\mathrm{S}\mathrm{K}}_{{\mathrm{U}}_{\mathrm{k}}}$,${\mathrm{P}\mathrm{K}}_{{\mathrm{U}}_{\mathrm{k}}}$): Inputting the security parameter PP, the user invokes the key-iteration algorithm in Section 3.1.2 to generate a private key set and a public key set (${\mathrm{S}\mathrm{K}}_{{\mathrm{U}}_{\mathrm{k}}}$,${\mathrm{P}\mathrm{K}}_{{\mathrm{U}}_{\mathrm{k}}}$) for T periods. The user ${\mathrm{U}}_{\mathrm{k}}$ first stores the set of public keys, and subsequently publishes the public key ${\mathrm{P}\mathrm{K}}_{{\mathrm{U}}_{\mathrm{k}}}$ of the current period along with its signature after signing. After the T-period public–private key set is used up, the user ${\mathrm{U}}_{\mathrm{k}}$ invokes the key update algorithm in Section 3.1.3 to generate another T$\mathrm{’}$-period public–private key set (${\mathrm{S}\mathrm{K}\mathrm{’}}_{{\mathrm{U}}_{\mathrm{k}}},{\mathrm{P}\mathrm{K}\mathrm{’}}_{{\mathrm{U}}_{\mathrm{k}}}$) for a new round of signature and verification.

3.2.3. Sign

When a user intends to sign a message, he checks the private key number in the private key set to determine the current period. He then publicizes the public key of the period along with the signature. The private key will become invalid once being used, because the user will delete the used private key from the private key set. This allows the period to be determined from the label of the private key.

Sign(PP,m,${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$) $\to$ ${\mathrm{e}}_{\mathrm{i}}$: Assuming that the current period is i and the user is ${\mathrm{U}}_{\mathrm{k}}$, then ${\mathrm{U}}_{\mathrm{k}}$ uses the private key of the i-th period ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$ to sign the message m. The user ${\mathrm{U}}_{\mathrm{k}}$ signature needs to do the following work:

• The user inputs the public parameters PP, the message $\mathrm{m}\in {\left\{\mathrm{0,1}\right\}}^{\mathrm{*}}$, and the private key of the i-th period ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$.
• The user randomly selects a vector ${\mathrm{y}}_{\mathrm{i}}\leftarrow {\mathrm{D}}_{{\mathrm{r}}_{\mathrm{i}}}^{\mathrm{m}}$.
• Calculates ${\mathrm{c}}_{\mathrm{i}}={\mathrm{H}}_2({\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{y}}_{\mathrm{i}},\mathrm{m})$.
• Then calculates ${\mathrm{z}}_{\mathrm{i}}={\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{c}}_{\mathrm{i}}+{\mathrm{y}}_{\mathrm{i}}$.
• Outputs the current period signature ${\mathrm{e}}_{\mathrm{i}}=\left({\mathrm{c}}_{\mathrm{i}}{,\mathrm{z}}_{\mathrm{i}}\right)$ with a probability of $\mathrm{m}\mathrm{i}\mathrm{n}(1,\frac{{\mathrm{D}}_{{\mathrm{r}}_{\mathrm{i}}}^{\mathrm{m}}\left({\mathrm{z}}_{\mathrm{i}}\right)}{{\mathrm{M}\mathrm{D}}_{{\mathrm{r}}_{\mathrm{i},{\mathrm{S}\mathrm{K}}_{\mathrm{I}\mathrm{D}\left|\right|\mathrm{i}}·{\mathrm{c}}_{\mathrm{i}}\left({\mathrm{z}}_{\mathrm{i}}\right)}}^{\mathrm{m}}})$, and re-executes the algorithm if there is no output.
• Publishes the current period public key ${\mathrm{P}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$.

3.2.4. Verify

The user ${\mathrm{U}}_{\mathrm{k}}$ signs the message, the verifier needs to verify the signature to confirm the validity of the signature.

Verify(PP,m,${\mathrm{e}}_{\mathrm{i}},{\mathrm{P}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$) $\to$ $0/1$:The verifier inputs the public parameter PP, the original message m, the public key ${\mathrm{P}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$ disclosed by user ${\mathrm{U}}_{\mathrm{k}}$ and the signature ${\mathrm{e}}_{\mathrm{i}}$, then the verifier performs the following operations:

If ${\mathrm{c}}_{\mathrm{i}}={\mathrm{H}}_2({\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{z}}_{\mathrm{i}}-{\mathrm{T}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{c}}_{\mathrm{i}},\mathrm{m})$ and the ${\mathrm{z}}_{\mathrm{i}}\le 2{\mathrm{r}}_{\mathrm{i}}·\sqrt{\mathrm{m}}$ are established simultaneously, the signature is accepted and the output result is 1, otherwise, the signature is rejected and the output result is 0.

Theorem 1 will help to prove the correctness of the identity-based strong forward-secure signature scheme brought forward in this paper.

Theorem 1.

The verification process of the signature guarantees the correctness of the signature.

Proof of Theorem 1.

The public key is ${\mathrm{P}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}=({\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}},{\mathrm{T}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}})$, the signature is ${\mathrm{e}}_{\mathrm{i}}=({\mathrm{c}}_{\mathrm{i}},{\mathrm{z}}_{\mathrm{i}})$, the message is m, and the public key and message signature pair are public. The correctness of the verifier’s success in verifying the signature is guaranteed by the following equation:

$$\begin{array}{l}{\mathrm{H}}_2({\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{z}}_{\mathrm{i}}-{\mathrm{T}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{c}}_{\mathrm{i}},\mathrm{m})\\ ={\mathrm{H}}_2({\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·({\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{c}}_{\mathrm{i}}+{\mathrm{y}}_{\mathrm{i}})-{\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{c}}_{\mathrm{i}},\mathrm{m})\\ ={\mathrm{H}}_2({\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{y}}_{\mathrm{i}},\mathrm{m})\\ ={\mathrm{c}}_{\mathrm{i}}\end{array}$$

□

By verifying the signature, it confirms that the signature is indeed generated by the holder of the private key, which guarantees both data integrity and unaltered transmission, therefore ensuring the accuracy of the signature.

4. Performance Analysis

4.1. Existential Unforgeability against Chosen-Message Attacks

Theorem 2 will help to prove the existential and unforgeability of the identity-based strong forward-secure signature scheme proposed in this paper.

Under the hard assumption of the SIS problem on the lattice, it is proved that the identity-based strong forward-secure signature scheme on the lattice is existentially unforgeable.

Theorem 2.

Under the random oracle model, according to the difficulty assumption of the SIS problem, the identity-based strong forward-secure signature scheme on the lattice realizes the existential unforgeability under the chosen-message attacks.

Proof of Theorem 2.

Assume that there is an adversary A of PPT who outputs a forged signature with a non-negligible probability after a polynomial query, which destroys the unforgeability of the identity-based strong forward-secure signature scheme given in 3.2. Then a simulator C with non-negligible advantages will be constructed, which can solve the SIS problem instance. □

Parameter establishment: C selects two hash functions ${\mathrm{H}}_1:{\left\{\mathrm{0,1}\right\}}^{\mathrm{*}}\to {\mathrm{Z}}^{\mathrm{m}\times \mathrm{m}}$, ${\mathrm{H}}_2:{\left\{\mathrm{0,1}\right\}}^{\mathrm{*}}\to \left\{\mathrm{v}:\mathrm{v}\in {\left\{-\mathrm{1,0},1\right\}}^{\mathrm{k}},\left|\right|\mathrm{v}\left|\right|\le \mathrm{k}\right\}$, and generates matrices ${\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{A}}_0},{\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{B}}_0}\in {\mathrm{Z}}_{\mathrm{q}}^{\mathrm{n}\times \mathrm{m}}$ and ${\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{A}}_0}},{\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{B}}_0}},{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}},{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}\in {\mathrm{Z}}^{\mathrm{m}\times \mathrm{m}}$, then sends $({\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{A}}_0},{\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{B}}_0},{\mathrm{H}}_1,{\mathrm{H}}_2)$ to A.

${\mathrm{H}}_1$ Query: For any time period i(i=1,2,…,T), the simulator C maintains two list ${\mathrm{L}}_1=\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}\right||\mathrm{i},{\mathrm{Q}}_{\mathrm{i}})$, ${\mathrm{L}\mathrm{’}}_1=\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}\right||\mathrm{i},{\mathrm{O}}_{\mathrm{i}})$ of ${\mathrm{H}}_1$ query, where ${\mathrm{Q}}_{\mathrm{i}}$ represented the hash value of ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}\left|\right|\mathrm{i}$, ${\mathrm{O}}_{\mathrm{i}}$ represented he hash value of ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}\left|\right|\mathrm{i}$, in which the initial lists are empty. A will conduct ${\mathrm{H}}_1$ query on $\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}\right||\mathrm{i},{\mathrm{Q}}_{\mathrm{i}})$, if the tuple $\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}\right||\mathrm{i},{\mathrm{Q}}_{\mathrm{i}})$ is in ${\mathrm{L}}_1$, C will use ${\mathrm{Q}}_{\mathrm{i}}$ as the response to the ${\mathrm{H}}_1$ query, otherwise C will randomly choose a ${\mathrm{G}}_{\mathrm{i}}\in {\mathrm{Z}}_{\mathrm{q}}^{\mathrm{m}\times \mathrm{m}}$ and use ${\mathrm{G}}_{\mathrm{i}}$ as the response to the ${\mathrm{H}}_1$ query, after that $\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}\right||\mathrm{i},{\mathrm{G}}_{\mathrm{i}})$ will be added into ${\mathrm{L}}_1$. A will conduct ${\mathrm{H}}_1$ query on $\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}\right||\mathrm{i},{\mathrm{O}}_{\mathrm{i}})$ , if $\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}\right||\mathrm{i},{\mathrm{O}}_{\mathrm{i}})$ is in ${\mathrm{L}\mathrm{’}}_1$, C will use ${\mathrm{O}}_{\mathrm{i}}$ as the response to the ${\mathrm{H}}_1$ query, otherwise C will randomly choose a ${\mathrm{J}}_{\mathrm{i}}\in {\mathrm{Z}}_{\mathrm{q}}^{\mathrm{m}\times \mathrm{m}}$ and use ${\mathrm{J}}_{\mathrm{i}}$ be the response to the ${\mathrm{H}}_1$ query, whereupon $\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}\right||\mathrm{i},{\mathrm{J}}_{\mathrm{i}})$ will be added into ${\mathrm{L}\mathrm{’}}_1$.

${\mathrm{H}}_2$ Query: C maintains a list ${\mathrm{L}}_2=({\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{y}}_{\mathrm{i}},{\mathrm{c}}_{\mathrm{i}}$) of ${\mathrm{H}}_2$ query, and the initial list is empty. A will conduct ${\mathrm{H}}_1$ query on $({\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{y}}_{\mathrm{i}},{\mathrm{c}}_{\mathrm{i}}$), if $({\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{y}}_{\mathrm{i}},{\mathrm{c}}_{\mathrm{i}}$) is in ${\mathrm{L}}_2$, C will respond ${\mathrm{c}}_{\mathrm{i}}$ as the response of ${\mathrm{H}}_2$ query, otherwise C will randomly choose a ${\mathrm{C}}_{\mathrm{i}}\in {\mathrm{Z}}_{\mathrm{q}}^{\mathrm{k}}$ and use it as the response to the ${\mathrm{H}}_2$ query, and then (${\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{y}}_{\mathrm{i}},{\mathrm{C}}_{\mathrm{i}}$) will be added into ${\mathrm{L}}_2$.

Key query: C maintains a list ${\mathrm{L}}_3=\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}\right||\mathrm{i},{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}\right||\mathrm{i},{\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}},{\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}})$, and the initial list is empty. C responds to the initial or iterative key query as follows:

• C first browses whether there is a corresponding hash value in the list ${\mathrm{L}}_1$ and ${\mathrm{L}\mathrm{’}}_1$, if exists, directly returns the corresponding hash value and calculates ${\mathrm{A}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}={\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{A}}_0}·{\left({\mathrm{H}}_1\right({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}\left|\right|0\left){\mathrm{H}}_1\right({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}\left|\right|1\left){\cdots \cdots \mathrm{H}}_1\right({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}\left|\right|\mathrm{i}\left)\right)}^{-1}$, ${\mathrm{A}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}={\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{B}}_0}·{\left({\mathrm{H}}_1\right({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}\left|\right|\mathrm{T}\left){\mathrm{H}}_1\right({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}\left|\right|\mathrm{T}-1{)\cdots \cdots \mathrm{H}}_1\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}\right|\left|\mathrm{i}\right))}^{-1}$. If the corresponding hash value does not exist, C randomly select a matrix ${\mathrm{P}}_{\mathrm{i}}\in {\mathrm{Z}}_{\mathrm{q}}^{\mathrm{n}\times \mathrm{m}}$, then run the BasisDel algorithm to generate a private key ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$and add it to the list ${\mathrm{L}}_3$.
• C maintains list ${\mathrm{L}}_4=\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}\right||\mathrm{i},{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}\right||\mathrm{i},{\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}{,\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}-1}{,\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}+1}$), if A performs a key query on ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|$i, C returns the current cycle private key ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$ of A as a response. Then C browses whether there is a corresponding hash value in the list ${\mathrm{L}}_1$ and ${\mathrm{L}\mathrm{’}}_1$, and if so, directly returns the corresponding hash value. After that calculate ${\mathrm{R}}_{\mathrm{i}+1}={\mathrm{H}}_1\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}\right||\mathrm{i}+1)$, ${\mathrm{R}}_{\mathrm{i}-1}={\mathrm{H}}_1\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{A}}_0}}\right||\mathrm{i}-1)$, ${\mathrm{R}\mathrm{’}}_{\mathrm{i}+1}={\mathrm{H}}_1\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}\right||\mathrm{i}+1)$, ${\mathrm{R}\mathrm{’}}_{\mathrm{i}-1}={\mathrm{H}}_1\left({\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\right|\left|{\mathrm{U}}_{\mathrm{k}{\mathrm{T}}_{{\mathrm{B}}_0}}\right||\mathrm{i}-1)$. If the corresponding hash value does not exist, C randomly selects a matrix ${\mathrm{G}}_{\mathrm{i}}\in {\mathrm{Z}}_{\mathrm{q}}^{\mathrm{m}\times \mathrm{m}}$, then runs the BasisDel algorithm to generate a forward private key ${\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}-1}$ and a backward private key ${\mathrm{s}\mathrm{k}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}+1}$, afterwards adds them into list ${\mathrm{L}}_4$.

Signature query: Adversary A asks for the signature of message m, B first browses the list ${\mathrm{L}}_1$, ${\mathrm{L}\mathrm{’}}_1$ and ${\mathrm{L}}_2$, for any period i $\le$ T, if there is a corresponding hash value, then C calculates ${\mathrm{z}}_{\mathrm{i}}={\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{c}}_{\mathrm{i}}+{\mathrm{y}}_{\mathrm{i}}$ and outputs the current period signature ${\mathrm{e}}_{\mathrm{i}}=({\mathrm{c}}_{\mathrm{i}},{\mathrm{z}}_{\mathrm{i}})$ with the probability of $\mathrm{m}\mathrm{i}\mathrm{n}(1,\frac{{\mathrm{D}}_{{\mathrm{r}}_{\mathrm{i}}}^{\mathrm{m}}\left({\mathrm{z}}_{\mathrm{i}}\right)}{{\mathrm{M}\mathrm{D}}_{{\mathrm{r}}_{\mathrm{i},{\mathrm{S}\mathrm{K}}_{\mathrm{I}\mathrm{D}\left|\right|\mathrm{i}}·{\mathrm{c}}_{\mathrm{i}}\left({\mathrm{z}}_{\mathrm{i}}\right)}}^{\mathrm{m}}})$; otherwise, C randomly selects the vector ${\mathrm{c}\mathrm{’}}_{\mathrm{i}}$ and ${\mathrm{z}\mathrm{’}}_{\mathrm{i}}$, whereupon obtained ${\mathrm{c}}_{\mathrm{i}}$ by ${\mathrm{H}}_2$ query with ${\mathrm{H}}_2({\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{z}\mathrm{’}}_{\mathrm{i}}-{\mathrm{T}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}|\mathrm{i}}·{\mathrm{c}\mathrm{’}}_{\mathrm{i}},\mathrm{m})$, and then computed ${\mathrm{z}}_{\mathrm{i}}={\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{c}}_{\mathrm{i}}+{\mathrm{y}}_{\mathrm{i}}$ to output the current period signature ${\mathrm{e}}_{\mathrm{i}}=({\mathrm{c}}_{\mathrm{i}},{\mathrm{z}}_{\mathrm{i}})$.

Forgery: The adversary ends the above queries, outputs the identity ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}^{\mathrm{*}}$ of current period ${\mathrm{i}}^{\mathrm{*}}$, message ${\mathrm{m}}^{\mathrm{*}}$ and signature of the current period ${\mathrm{e}}_{{\mathrm{i}}^{\mathrm{*}}}$. The adversary wins if the following conditions hold.

• 1 $\le {\mathrm{i}}^{\mathrm{*}}\le$ T.
• ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}^{\mathrm{*}}$ has not been queried in the key query.
• (${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}^{\mathrm{*}}$,${\mathrm{i}}^{\mathrm{*}}{,\mathrm{m}}^{\mathrm{*}}$) has not been asked in the signature query.
• Signature ${\mathrm{e}}_{{\mathrm{i}}^{\mathrm{*}}}$ pass the verification.

According to the Fork Lemma in the security proof, when adversary A successfully forges a signature ${\mathrm{e}}_{{\mathrm{i}}^{\mathrm{*}}}$ and is used by simulator C to crack a difficult problem, the challenge process needs to be run twice so that the output of both processes matches for a period of time before diverging at a certain point. This allows simulator C to solve the difficult problem. So there exists the following equation ${\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{z}}_{\mathrm{i}}-{\mathrm{T}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{c}}_{\mathrm{i}}=\mathrm{Ā}·{\mathrm{z}}_{{\mathrm{i}}^{\mathrm{*}}}-{\mathrm{T}}_{{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}}^{\mathrm{*}}\left|\right|{\mathrm{i}}^{\mathrm{*}}}·{\mathrm{c}}_{{\mathrm{i}}^{\mathrm{*}}}$, where ${\mathrm{T}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}={\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}$, ${\mathrm{T}}_{{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}}^{\mathrm{*}}\left|\right|{\mathrm{i}}^{\mathrm{*}}}=\mathrm{Ā}·{\mathrm{S}\mathrm{K}}_{{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}}^{\mathrm{*}}\left|\right|{\mathrm{i}}^{\mathrm{*}}}$. Transform the equation to obtain (${\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{z}}_{\mathrm{i}}-{\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{c}}_{\mathrm{i}})-({\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}^{\mathrm{*}}\left|\right|{\mathrm{i}}^{\mathrm{*}}}·{\mathrm{z}}_{{\mathrm{i}}^{\mathrm{*}}}-{\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}^{\mathrm{*}}\left|\right|{\mathrm{i}}^{\mathrm{*}}}·{\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}^{\mathrm{*}}\left|\right|{\mathrm{i}}^{\mathrm{*}}}·{\mathrm{c}}_{{\mathrm{i}}^{\mathrm{*}}})$ = 0, because of the collision resistance of the hash function, there obtains ${\mathrm{A}}_0({\left({\mathrm{R}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}\right)}^{-1}·{\mathrm{y}}_{\mathrm{i}}-{\left({\mathrm{R}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}^{\mathrm{*}}\left|\right|{\mathrm{i}}^{\mathrm{*}}}\right)}^{-1}·{\mathrm{y}}_{{\mathrm{i}}^{\mathrm{*}}})=0$, ${\mathrm{B}}_0({\left({\mathrm{R}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}\right)}^{-1}·{\mathrm{y}}_{\mathrm{i}}-{\left({\mathrm{R}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}^{\mathrm{*}}\left|\right|{\mathrm{i}}^{\mathrm{*}}}\right)}^{-1}·{\mathrm{y}}_{{\mathrm{i}}^{\mathrm{*}}})=0$. Let ${\mathsf{\lambda }}_1=({\left({\mathrm{R}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}\right)}^{-1}·{\mathrm{y}}_{\mathrm{i}}-{\left({\mathrm{R}}_{{\mathrm{I}\mathrm{D}}^{\mathrm{*}}\left|\right|{\mathrm{i}}^{\mathrm{*}}}\right)}^{-1}·{\mathrm{y}}_{{\mathrm{i}}^{\mathrm{*}}}$), ${\mathsf{\lambda }}_2=({\left({\mathrm{R}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}\right)}^{-1}·{\mathrm{y}}_{\mathrm{i}}-{\left({\mathrm{R}\mathrm{’}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}^{\mathrm{*}}\left|\right|{\mathrm{i}}^{\mathrm{*}}}\right)}^{-1}·{\mathrm{y}}_{{\mathrm{i}}^{\mathrm{*}}}$), ${\mathsf{\lambda }}_1$ and ${\mathsf{\lambda }}_2$ are both non-zero vectors, and there are ${\mathrm{A}}_0{\mathsf{\lambda }}_1$ = 0 and ${\mathrm{B}}_0{\mathsf{\lambda }}_2$ = 0, so ${\mathsf{\lambda }}_1$ and ${\mathsf{\lambda }}_2$ will be regarded as the solution to the SIS problem.

If there exists an adversary that can forge a valid signature of a digital signature scheme with probability acc, then there exists an algorithm ${\mathrm{F}}_{\mathrm{B}}$ that outputs the solution of the SIS problem instance with probability Adv $\ge$ acc$·(\frac{\mathrm{a}\mathrm{c}\mathrm{c}}{{\mathrm{q}}_{{\mathrm{H}}_1}+{\mathrm{q}}_{{\mathrm{H}}_2}}-\frac{1}{\mathrm{h}})$ by exploiting the capacity of the adversary, where acc $\ge$ε-$\frac{{\mathrm{q}}_{\mathrm{s}}({{\mathrm{q}}_{{\mathrm{H}}_1}+{\mathrm{q}}_{{\mathrm{H}}_2+}\mathrm{q}}_{\mathrm{s}}+1)}{2^{\mathrm{k}}}$, ${\mathrm{q}}_{{\mathrm{H}}_1}$ and ${\mathrm{q}}_{{\mathrm{H}}_2}$, respectively, represent the number of ${\mathrm{H}}_1$ and ${\mathrm{H}}_2$ query, ${\mathrm{q}}_{\mathrm{s}}$ represent the number of signature queries, h is the number of replies to random oracle queries. In this way, the simulator cracks the SIS problem with a non-negligible advantage, but because of the computational difficulty of the SIS problem, such an adversary cannot break through our scheme, so the scheme is secure.

4.2. Strong Forward Security

4.2.1. Forward-Security Analysis

• Key-iteration algorithm has forward security

The user’s signature private key iterates as the period increases. If an attacker obtains the user ${\mathrm{U}}_{\mathrm{k}}$’s signature private key ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}}$ of period j and wants to use the signature private key ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}}$ to obtain the private key ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}-1}$ of period j − 1, then the attacker needs to break through the problem of small integers on the lattice. As the computational difficulty of the problem, the attacker cannot obtain the private key ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}-1}$ used by ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}}$, as well as being unable to obtain the private keys such as ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}-2}$, ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}-3}$,…, ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|1}$ for the existing signatures.

2.

The signature scheme is forward-secure

The user ${\mathrm{U}}_{\mathrm{k}}$’s signature in the j-th period is ${\mathrm{e}}_{\mathrm{j}}=\left({\mathrm{c}}_{\mathrm{j}}{,\mathrm{z}}_{\mathrm{j}}\right)$, where ${\mathrm{c}}_{\mathrm{j}}={\mathrm{H}}_2({\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{y}}_{\mathrm{i}},\mathrm{m})$, ${\mathrm{z}}_{\mathrm{j}}={\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}}·{\mathrm{c}}_{\mathrm{j}}+{\mathrm{y}}_{\mathrm{j}}$, m is the message, ${\mathrm{P}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}}=({\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}},{\mathrm{T}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}})$ is the public key, and ${\mathrm{y}}_{\mathrm{j}}$ is selected randomly. The attacker wants to forge the signature of period j − 1. Since the public key is public, the attacker has the condition to calculate ${\mathrm{c}}_{\mathrm{j}-1}$. If he wants to forge the signature, the attacker needs to calculate it ${\mathrm{z}}_{\mathrm{j}-1}$. At this time, the private key of period j − 1 is needed. Due to the difficulty of solving the problem with small integers on the grid, even if the attacker obtains the signature key of period j, he cannot forge the signature key of period j − 1, so a valid signature cannot be generated. The statements mentioned above ensure the forward security of the signature.

4.2.2. Backward Security Analysis

• The key-iteration algorithm has backward security

The user’s signature private key iterates as the period decreases. If an attacker obtains the user ${\mathrm{U}}_{\mathrm{k}}$’s signature private key ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}}$ of period j and wants to use the signature private key ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}}$ to obtain the private key ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}+1}$ of period j + 1, then it needs the attacker to break through the small integer problem on the lattice, so the attacker cannot obtain the private key ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}+1}$ using ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}}$, as well as being unable to obtain the private keys such as ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}+2}$,${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}+3}$,…,${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{T}}$ for the subsequent signatures.

2.

The signature scheme is forward-secure

The user ${\mathrm{U}}_{\mathrm{k}}$’s signature in the j-th period is ${\mathrm{e}}_{\mathrm{j}}=\left({\mathrm{c}}_{\mathrm{j}}{,\mathrm{z}}_{\mathrm{j}}\right)$, where ${\mathrm{c}}_{\mathrm{j}}={\mathrm{H}}_2({\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{i}}·{\mathrm{y}}_{\mathrm{i}},\mathrm{m})$, ${\mathrm{z}}_{\mathrm{j}}={\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}}·{\mathrm{c}}_{\mathrm{j}}+{\mathrm{y}}_{\mathrm{j}}$, m is the message, ${\mathrm{P}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}}=({\mathrm{Ā}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}},{\mathrm{T}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}})$ is the public key, and ${\mathrm{y}}_{\mathrm{j}}$ is selected randomly. The attacker wants to forge the signature of period j+1. If the user ${\mathrm{U}}_{\mathrm{k}}$ has signed with ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}+1}$, the public key has been disclosed by the user ${\mathrm{U}}_{\mathrm{k}}$, then the attacker has the condition to calculate ${\mathrm{c}}_{\mathrm{j}+1}$. If he wants to forge the signature, the attacker still needs to calculate ${\mathrm{z}}_{\mathrm{j}+1}$. At this time, the private key of period j + 1 is needed. Due to the difficulty of solving the problem with small integers on the grid, even if the attacker obtains the signature key of period j, he cannot forge the signature key of period j + 1, so a valid signature cannot be generated. This ensures the forward security of the signature. If the user ${\mathrm{U}}_{\mathrm{k}}$ has not used ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{j}+1}$ to sign, then the user ${\mathrm{U}}_{\mathrm{k}}$ has not disclosed the public key. With the anti-collision property of the hash function, the attacker cannot calculate ${\mathrm{c}}_{\mathrm{j}}$, let alone calculate ${\mathrm{z}}_{\mathrm{j}}$. Therefore, a valid signature cannot be generated, thus ensuring the forward security of the signature.

Since the key-iteration algorithm and the signature scheme have both forward security and backward security, it is shown that the scheme proposed in Section 3 has strong forward security.

5. Remote Identity Authentication to Resist Quantum Attacks

With the popularity of the Internet, it has become more convenient and effective to use the Internet to engage in various activities, which inevitably requires the credibility of the participants. To ensure consistency between the users’ real identity and the digital identity on the network, it is necessary to use some technical verification methods for consistency verification. Identity-authentication technology solves the problem of consistency. It is an effective means to ensure information security. It plays an important role in information systems and is used as a tool to confirm the validity of participants’ identities.

5.1. Overview of Remote Identity Authentication

Remote identity authentication is the process of verifying a user’s identity through a network or remote communication channel. It allows users to authenticate without having to attend in person to gain access to systems or resources. Remote identity authentication includes static authentication, dynamic authentication, and multi-factor authentication [29]. It has been practiced in some public domains and has become a common authentication method. The dynamic password authentication of digital signatures plays a significant part in many fields because of its particularity and real-time characteristics [30].

Applying the digital signature scheme to the working process of remote identity dynamic authentication could guarantee the security of the authentication process. The whole process includes two stages of registration and authentication. In the registration stage, the user stores his information on the server. In the authentication stage, the user and the server interact to prove their identity [31]. This section applies the identity-based strong forward-secure signature scheme proposed in Section 3 to the remote identity-authentication process to implement a secure remote identity-authentication scheme.

The lattice-based signature scheme utilizes mathematical problems based on lattices as the fundamental security measure. The signature scheme proposed in Section 3 is specifically built upon the SIS problem, which poses a formidable challenge that currently remains unsolved by quantum computers. Therefore, the lattice-based signature scheme has strong security under quantum computer attacks.

5.2. Lattice-Based Strong Forward-Secure Signature Scheme for Remote Authentication

In the remote identity-authentication process based on the signature scheme, if only a pair of public and private keys are generated when the user registers, then the signature private key used by the user in each authentication process will remain unchanged. If the key is leaked, the entire authentication process will no longer be safe. At this time, the user signature system needs to be updated, otherwise a malicious third party may obtain the important information of the user stored on the server.

However, it will be inconvenient to update the user signature system. Applying an identity-based strong forward-secure signature scheme to remote user authentication can reduce the impact of key leakage. In the identity-based strong forward-security signature scheme, there will be a unique key pair for signing and verification in each period, so even if a private key is accidentally leaked due to user storage, it ensures that the user’s subsequent identity authentication is safe. With the strong forward security of the signature private key, the attacker cannot calculate the private key of other periods through a certain private key, so he cannot pretend to be a legitimate user for authentication. The remote identity-authentication framework of lattice-based strong forward-secure signature scheme is shown in Figure 2.

5.2.1. Enrollment Phase

When the user registers, first, they are supposed to send the identity information to PKG to obtain the master private key and master public key, and then the user’s master private key and master public key generate a public–private key set. After that, the user sends his identity and public key set to the server. When receiving the encrypted information, the server uses the private key to decrypt to obtain the user identity and public key set, and then stores it in the server database. The specific registration process is:

• The user ${\mathrm{U}}_{\mathrm{k}}$ first determines the required period T, initiates a key request to PKG to obtain the master private key ${\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{A}}_0}}$ and the master public key ${\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{B}}_0}}$, and then the user ${\mathrm{U}}_{\mathrm{k}}$ uses ${\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{A}}_0}}$, ${\mathrm{M}}_{{\mathrm{U}}_{\mathrm{k}}{\mathrm{T}}_{{\mathrm{B}}_0}}$ to generate the private key set ${\mathrm{S}\mathrm{K}}_{{\mathrm{U}}_{\mathrm{k}}}$ and the public key set ${\mathrm{P}\mathrm{K}}_{{\mathrm{U}}_{\mathrm{k}}}$, after that stores the private key set and the public key set carefully.
• The server uses a public-key encryption algorithm to generate a public–private key pair (ssk, spk), and sends the public key to the user ${\mathrm{U}}_{\mathrm{k}}$ to encrypt the transmitted identity information.
• The user ${\mathrm{U}}_{\mathrm{k}}$ uses the public key of the server to encrypt the identity ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}$ and the public key set ${\mathrm{P}\mathrm{K}}_{{\mathrm{U}}_{\mathrm{k}}}$ with spk and then sends them to the server.
• The server uses the ssk to decrypt and obtains the user’s sum ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}$ and store ${\mathrm{P}\mathrm{K}}_{{\mathrm{U}}_{\mathrm{k}}}$ it in the server’s database.

After the registration is completed, the user ${\mathrm{U}}_{\mathrm{k}}$ becomes a legal user of the server and performs remote identity authentication through the server.

5.2.2. Authentication Phase

The user ${\mathrm{U}}_{\mathrm{k}}$ proves his identity with the server through the following interactions:

• The user ${\mathrm{U}}_{\mathrm{k}}$ checks the private key number in the private key set to determine the current period t(t$\le$T), encrypts the user identity ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}$ as well as the public key corresponding to the current period ${\mathrm{P}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{t}}$ with the server’s public key spk, and sends it to the server.
• After receiving the ciphertext sent by ${\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}$ the user, the server decrypts it with the private key ssk to obtain the user’s ${\mathrm{U}}_{\mathrm{k}}$ and the public key of the current period ${\mathrm{P}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{t}}$, and then the server compares the user’s identity and public key in the database to see whether they are consistent with the stored ones. If they are consistent, continue 3, otherwise stop the interaction.
• The server randomly selects a challenge message and sends the challenge message to the user.
• The user replies to the challenge information, and takes the challenge information and replies to information as messages to be signed.
• Use the private key of the current period ${\mathrm{S}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{t}}$ to sign, and send the message signature pair to the server after signing.
• After the server receives the message signature pair, the public key ${\mathrm{P}\mathrm{K}}_{{\mathrm{I}\mathrm{D}}_{{\mathrm{U}}_{\mathrm{k}}}\left|\right|\mathrm{t}}$ is used to verify. If the signature is verified, the user is authenticated; otherwise, the authentication fails. The remote identity-authentication process of the lattice-based strong forward-secure signature scheme is shown in Figure 3.

6. Conclusions

In a digital signature scheme, if the key is leaked, the signature scheme will be insecure. To reduce the impact of leaked keys on the security of a signature scheme, a strong forward-secure signature scheme is proposed in this paper. With the emergence of quantum computing, the security of schemes based on RSA and discrete logarithm problems is corrupt. Therefore, a strong forward-secure signature scheme that is resistant to quantum attacks is proposed in this paper. The trapdoor-generation algorithm, lattice-basis delegation technology, and hash function are used to distribute a unique key pair for every period by iterating the key. The above algorithms ensure the forward security and backward security of the key, so that the key has strong forward security. Under the random oracle model, the proposed signature scheme satisfies existential unforgeability based on the difficulty assumption of the SIS problem. This paper is about a lattice-based strong forward-secure signature scheme under the random oracle model. In the future, a lattice-based strong forward-secure signature scheme under the standard model will be further studied.