An Efficient Identity-Based Forward Secure Signature Scheme from Lattices

Guang Wu, Ruwei Huang

School of Computer, Electronics and Information, Guangxi University, Nanning, China.

DOI: 10.4236/oalib.1107126                

Abstract

With the use of a large number of mobile devices, the problem of key leakage becomes more and more serious. In view of the excellent characteristics of lattice cipher and forward-secure digital signature scheme, the construction of identity-based forward-secure digital signature based on lattice technology has become a research hotspot. However, the identity-based forward secure digital signature scheme on the existing grid has the disadvantage of excessive signature length. This paper uses the technique (without trapdoors) of Lyubashevsky and extended Samplepre, an efficient identity-based forward secure signature scheme from lattice is proposed. Its security is based on the Small Integer Solution (SIS) difficulty assumption, and the strong non-forgery of the signature scheme is achieved. The analysis results show that, compared with the existing schemes, the key and signature are smaller in size, more efficient in computing, able to resist quantum attacks, and more practical.

Keywords

Identity-Based Signature, Lattice, Forward Security, Without Trapdoors, Small Integer Solution (SIS)

1. Introduction

1.1. Background of This Study

The identity-based signature scheme (IBS) was first proposed by Shamir [1] in 1984 and is a public key encryption system. So far, most traditional identity-based signature schemes [2] - [7] have been proposed based on the bilinear or quadratic residual assumption.

Although the existing traditional identity-based signature schemes are very efficient and the types can basically meet the needs of most applications, such signature schemes have obvious security flaws. Shor [8] pointed out that the prime number decomposition and discrete logarithm problems based on traditional cryptography can be broken by quantum computers in polynomial time. This means that once quantum computers become a reality, the existing public key cryptography will be compromised and will no longer be secure. Ajtai [9] proved that the difficulty of the difficult problem on the lattice under the random instance is equivalent to the difficulty under the worst instance; in addition, the grid public key cryptographic algorithm is simple, efficient, and suitable for low-power devices. There are no effective algorithms, including quantum algorithms, which can solve difficult problems on the grid. In recent years, lattice-based cryptosystems have achieved fruitful results in applications such as digital signatures [10] [11] [12], hierarchical identity-based encryption schemes (HIBE) [13], and fully homomorphic encryption [14].

In 1997, Anderson et al. [15] first proposed the idea of forward secure signature, Bellare and Miner [16] further proposed more practical algorithms, and gave a formal definition of forward-secure digital signature and its security. More forward secure digital signature algorithms [17] [18] are proposed. However, there are few researches on identity-based forward security digital signature algorithms. Liu proposed the first identity-based forward secure digital signature algorithm in [19], however, he did not give a formal definition and formal security proof. Yu et al. gave the formal definition and security proof of an identity-based forward secure digital signature algorithm in literature [20], but the algorithm required a large number of bilinear pairing operations and was not suitable for mobile devices with limited computing power. Ebri [21] gave the general construction algorithm of forward secure digital signature algorithm based on identity, and simplified the definition of security. However, all of the above are based on the assumptions of difficult problems in traditional cryptography and cannot resist quantum computer attacks.

Zhang [22] proposed the first identity-based forward secure digital signature scheme (FSIBS), whose main idea is based on the layered identity-based signature scheme of Ruckert [23].

1.2. Contributions of This Article

In this paper, in the random oracle model, based on the assumption of small integers to solve difficult problems, we prove that our scheme is unforgeable against adaptive identity selection and selection message attacks. In addition, Zhang’s scheme uses the lattice proxy algorithm of literature [24] to update the signature key, keeping the dimensionality unchanged. In our research, we combine the trapdoor-free signature with the trapdoor base to realize the identity-based signature design that does not rely on the expansion of the lattice dimension, which will not bring large calculation, communication or storage overhead, and is more efficient. Our signature key size and signature size are much shorter. In this way, our scheme can be applied to post-quantum communication more efficiently.

1.3. The Structure of the Organization

The rest of this paper is arranged as follows: In the second section, we give the prerequisite knowledge to be used in this paper; in the third section, the formal definition and security model of our FSIBS scheme are given. In the fourth section, the algorithm description and security proof of our scheme are given. In the fifth section, the performance comparison of the scheme is given. Finally, we conclude our work in section 6.

2. Prerequisite Knowledge

2.1. Description of Related Symbols

For a positive integer n, use [n] to represent the set $\left\{1,2,\cdots ,n\right\}$. For any character string a and b, |a| represents the bit length of a, and a‖b represents the concatenation of two characters a and b, and $a\oplus b$ represents their exclusive OR operation.

2.2. Definitions and Tools Related to Cryptography

Definition 2.1 (Hash function) Hash function is a one-way function with compression characteristics. Its input is a string of arbitrary length, and its output is a string of fixed length, namely $H:{\left\{0,1\right\}}^{*}\to {\left\{0,1\right\}}^n$. It is mainly used for message authentication and digital signature.

A common tool used in cryptography is: Random Oracle. At present, in the provable security discussion of many cryptographic algorithms, the hash function is regarded as a random oracle. This basic idea comes from the literature [25]. Fiat and Shamir [26] first transformed an identification algorithm into a signature algorithm under a random oracle model. Later, Bellare and Rogaway formally proposed a random oracle model in [27], and constructed a general proof framework for cryptographically provable security statements under the random oracle model.

2.3. Theoretical Basis of Lattice Cipher

Definition 2.2 (integer lattice), let $B=\left[b_1,b_2,\cdots ,b_m\right]\in Z^{m\times m}$ is an $m\times m$ -dimensional invertible matrix. It consists of m linearly independent vectors $b_1,b_2,\cdots ,b_m\in Z^m$. The m-dimensional integer lattice generated by matrix B is:

$\text{Λ}=\left\{y\in Z^m|y=Bc=\underset{i=1}{\overset{m}{{\displaystyle \sum }}}{c}_i{b}_i,c\in Z^m\right\}$ (1)

2.4. Discrete Gaussian Distribution

Definition 2.3 for any real parameter $s>0,c\in R^m$ as the center, the discrete Gaussian distribution density function of lattice $\Lambda$ is defined as:

$\forall x\in \text{Λ},{\rho }_{s,c}\left(x\right)=\exp \left(-\pi \frac{{\Vert x-c\Vert }^2}{s^2}\right)$ (2)

Let ${\rho }_{s,c}\left(\text{Λ}\right)={\displaystyle {\sum }_{x\in \text{Λ}}{\rho }_{s,c}}\left(x\right),\text{Λ}$, the discrete Gaussian distribution on Λ is defined as:

$\forall y\in \text{Λ},D_{\text{Λ},s,c}\left(y\right)=\frac{{\rho }_{s,c}\left(y\right)}{{\rho }_{s,c}\left(\text{Λ}\right)}$ (3)

Lemma 2.1 (Properties of Discrete Gaussian Distribution on Lattice [11] [28] ). Let prime number $q\ge 3$, integer $m\ge 2n\log q$, T is a set of basis of lattice ${\text{Λ}}_q^{\perp }\left(A\right)$, Gaussian parameter $s\ge \Vert \tilde{T}\Vert \omega \left(\sqrt{\log m}\right)$. Then for any vector $y\in Z_q^n$, there are the following results:

1) $\mathrm{Pr}\left[x\leftarrow D_{\Lambda ,s,c}\left(x\right):\Vert x\Vert >s\sqrt{m}\right]\le negl\left(n\right)$ ;

2) For a randomly selected matrix $A\in Z_q^{n\times m}$, if $e\leftarrow G_{Z^m,s}$, then we have a statistical distribution of $y=Ae\left(\mathrm{mod}q\right)$ close to the uniform distribution on $Z_q^n$.

2.5. Difficult Questions on Grid

Definition 2.4 (Small integer solution problem) Let the parameters n and m be positive integers, q be prime numbers, and given a small real number $\beta >0$. A is a randomly selected matrix on $Z_q^{n\times m}$. The SIS problem is to find a short vector v on the lattice ${\text{Λ}}_q^{\perp }\left(A\right)$, namely $Av=0\left(\mathrm{mod}q\right)$, so that its norm satisfies $\Vert v\Vert \le \beta$.

2.6. Basic Algorithm on Grid

Lemma 2.2 (TrapGen generation algorithm, TrapGen [29] ) There is a probability polynomial time algorithm TrapGen. The algorithm inputs integers $q\ge 2$ and $m\ge 5n\log q$, and outputs a matrix $A\in Z_q^{n\times m}$ and a short basis $T_A\in Z_q^{m\times m}$ of lattice ${\text{Λ}}_q^{\perp }\left(A\right)$ in polynomial time. Make A statistically close to the uniform distribution $Z_q^{m\times m}$, and the short basis $T_A\in Z_q^{m\times m}$ satisfies $\Vert \widetilde{T_A}\Vert \le O\left(\sqrt{n\log q}\right)$.

In 2008, scholars such as Gentry constructed the pre-image sampling function (PSF) in the literature [11]. This technology plays an important role in the construction of the lattice encryption algorithm.

Lemma 2.3 (Original image sampling algorithm) Let the integer $m\ge n$, q be a prime number, and ${\text{Λ}}_q^{\perp }\left(A\right)$ is a lattice defined by the matrix $A\in Z_q^{n\times m}$. The matrix $T_A\in Z_q^{m\times m}$ is a short basis of the lattice ${\text{Λ}}_q^{\perp }\left(A\right)$. If the parameter $s\ge \Vert \widetilde{T_A}\Vert \omega \left(\sqrt{\log m}\right)$, then there is a polynomial time algorithm $\text{SamplePre}\left(A,T_A,s,u\right)$ for all $u\in Z_q^n$. It can output a vector $v\in {\text{Λ}}^u\left(A\right)$ drawn from a distribution statistically close to $D_{\text{Λ},s,c}\left(x\right)$.

According to Lemma 2.1, we know that an original image v corresponding to the vector $u\in Z_q^n$ extracted by the original image sampling algorithm SamplePre will satisfy $\Vert v\Vert \le s\sqrt{m}$ with an overwhelming probability.

The above SamplePre algorithm is only for the case of a vector. In many cases, we need to calculate a pre-image with a smaller norm corresponding to a matrix. Therefore, we need to extend the algorithm to a more general situation. Here we refer to the definition of the general Gaussian distribution given by Tian [30].

Definition 2.5 (General Discrete Gaussian Distribution) Let the integer $m\ge n$, q be a prime number, and k is a positive integer, we define $k<n\le m$, so that the matrix U satisfies the smaller norm. For any real number s > 0 and matrix $A\in Z_q^{n\times m}$ and $U=\left[u_1,u_2,\cdots ,u_k\right]\in Z_q^{n\times k}$, define the distribution $G{\text{Λ}}^u{\left(A\right)}_{,s}=G{\text{Λ}}^{u_1}{\left(A\right)}_{,s}\times \cdots \times G{\text{Λ}}^{u_k}{\left(A\right)}_s$.

According to Lemma 2.1, we know that a vector x randomly selected from the distribution $G{\text{Λ}}^u{\left(A\right)}_{,s}$ will satisfy $\Vert x\Vert \le s\sqrt{m}$ with an overwhelming probability. Therefore, it is not difficult to obtain that the matrix X randomly selected from the distribution $G{\text{Λ}}^u{\left(A\right)}_{,s}$ will also satisfy $\Vert X\Vert =\max \left(\Vert x_i\Vert \right)\le s\sqrt{m}$ with an overwhelming probability. If we can find an algorithm, it can output a matrix V for any input matrix U, so that $AV=U\left(\mathrm{mod}q\right)$ and the distribution statistics of matrix V are close to $G{\text{Λ}}^u{\left(A\right)}_{,s}$, according to our analysis of the distribution $G{\text{Λ}}^u{\left(A\right)}_{,s}$, this algorithm is the general pre-image sampling algorithm we require. This algorithm is recorded as the SampleMat algorithm.

Lemma 2.4 (General Original Image Sampling Algorithm) Let the integer $m\ge n$, q be a prime number, and k is a positive integer. Here we define $k<n\le m$ so that the matrix U satisfies the smaller norm. ${\text{Λ}}^{\perp }\left(A\right)$ is a lattice defined by matrix A, and matrix $T_A\in Z_q^{m\times m}$ is a short basis of lattice ${\text{Λ}}_q^{\perp }\left(A\right)$. Parameter $s\ge \Vert \widetilde{T_A}\Vert \omega \left(\sqrt{\log m}\right)$, then for any matrix $U\in Z_q^{n\times k}$, there is a polynomial time algorithm $\text{SampleMat}\left(A,T_A,s,U\right)$, it can extract a matrix $V\in Z_q^{m\times k}$ from a distribution statistically close to $G{\text{Λ}}^u{\left(A\right)}_{,s}$ to satisfy $AV=U\left(\mathrm{mod}q\right)$.

Definition 2.6 (Discrete normal distribution) Let the parameter $\sigma >0$ and the center $c\in R^m$, then the continuous normal distribution in the space $R^m$ is ${\rho }_{\sigma ,c}^m\left(x\right)={\left(2\pi {\sigma }^2\right)}^{-\frac{m}{2}}\exp \left(-\frac{{\Vert x-c\Vert }^2}{2{\sigma }^2}\right)$. Let ${\rho }_{\sigma ,c}^m\left(Z^m\right)={\displaystyle {\sum }_{x\in Z^m}{\rho }_{\sigma ,c}^m\left(x\right)}$. Define the discrete normal distribution with $c\in Z^m$ as the center and $\sigma$ parameter in $Z^m$ as $D_{\sigma ,c}^m\left(x\right)={\rho }_{\sigma ,c}^m\left(x\right)/{\rho }_{\sigma ,c}^m\left(Z^m\right)$. For the convenience of notation, we abbreviate ${\rho }_{\sigma ,0}^m$ and $D_{\sigma ,0}^m$ as ${\rho }_{\sigma }^m$ and $D_{\sigma }^m$, respectively.

Literature [29] [31] on two basic properties of discrete normal distribution:

Lemma 2.5. For any real number $\sigma >0$ and integer $m>0$, we have:

1) $\mathrm{Pr}\left[x\leftarrow D_{\sigma }^1:\left|x\right|>12\sigma \right]<2^{-100}$ ;

2) $\mathrm{Pr}\left[x\leftarrow D_{\sigma }^m:\Vert x\Vert >2\sigma \sqrt{m}\right]<2^{-m}$ ;

Lemma 2.6. For any vector $v\in Z^m$ and positive real number $\alpha$, if $\sigma =\omega \left(\Vert v\Vert \sqrt{\log m}\right)$, we have: $\mathrm{Pr}\left[x\leftarrow D_{\sigma }^m:D_{\sigma }^m\left(x\right)/D_{\sigma ,v}^m\left(x\right)=O\left(1\right)\right]=1-2^{\omega \left(\log m\right)}$ More specifically, if $\sigma =\alpha \Vert v\Vert$, then $\mathrm{Pr}\left[x\leftarrow D_{\sigma }^m:D_{\sigma }^m\left(x\right)/D_{\sigma ,v}^m\left(x\right)<{\text{e}}^{12/\alpha +1/\left(2{\alpha }^2\right)}\right]>1-2^{-100}$

In view of the complicated calculation of the sampling technique of Genntry et al. [11], Lyubashevsky [31] proposed a signature algorithm that does not require sampling operations on the grid. The technique used in this algorithm is called the non-sampling technique. At present, the non-sampling technology has gradually become an important technology of the social lattice signature scheme. Its core idea is to force the distribution of the output signature to be independent of the signature key $s_k$ of the signer by outputting candidate signatures probabilistically.

This paper needs to use the general bifurcation lemma when proving the security of the signature scheme. Bellare and Neven [32] gave the following general bifurcation lemma.

Lemma 2.7 (General Bifurcation Lemma) Let q be a positive integer, and H is a set with $h\ge 2$ elements. Let $\mathcal{J}\mathcal{G}$ be a parameter generation algorithm, B is a random algorithm, the input of B is $\left\{x,h_1,\cdots ,h_q\right\}$, and the output is (J, σ), where $x\in \left\{0,\cdots ,q\right\}$ $h_i\in H\left(i\in \left[q\right]\right)$. Let the acceptance probability acc of Algorithm B be the probability of $J\ge 1$ in the experiment $EXP=\left\{x\leftarrow \mathcal{J}\mathcal{G};h_1,\cdots ,h_q\leftarrow H;\left(J,\sigma \right)\leftarrow \mathcal{B}\left(x,h_1,\cdots ,h_q\right)\right\}$.

3. Formal Definition and Security Model

This article first provides a formal definition of an identity-based forward secure digital signature algorithm. According to the literature [21], this paper also sets the time period to be associated with the signature private key information, which can be determined by each signing user, and the algorithm is more flexible. In order to set the initial signature private key, PKG needs to set the time period and the signer’s identity information in advance. The identity-based forward secure digital signature algorithm consists of the following five sub-algorithms:

FSIBSSetup: The key generation algorithm is a probabilistic polynomial time algorithm, the input is the security parameter κ, the output is the system master key msk, and the public parameter mpk;

FSIBSExtract: The identity-based key proposal algorithm is a probabilistic polynomial time algorithm. The input is the public parameter mpk, the master key msk, and the user’s identity information $id\in {\left\{0,1\right\}}^{*}$, where $id=id\parallel T$, ID is the user’s real identity, and T is the time period preset by the system. The output of the algorithm is the initial private key $S{K}_{id\parallel 0}$ corresponding to the identity information id, which is transmitted to the user through a secure channel.

FSIBSUpdate: The key update algorithm is a probabilistic polynomial time algorithm. The input is the current time i, the user’s identity information id, and the user’s private key at this moment $S{k}_{id\parallel i}$, and the output is the next time i + 1 private key $S{k}_{id\parallel i+1}$.

FSIBSSign: The signature algorithm is a probabilistic polynomial time algorithm. The input is the current time i, the user’s identity information id, and the user’s private key at this time $S{k}_{id\parallel i}$, the message M, the digital signature of the output message M sig.

FSIBSVerify: The verification algorithm is a deterministic algorithm. Input the user’s identity information id, time i, information M, and digital signature sig. If sig is valid, the algorithm output is 1, otherwise the output is 0.

The correctness of the scheme: If the signature sig is a valid signature of message M, then ${\text{FSIBSVerify}}_{mpk}\left(id,i,M,sig\right)=1$.

The following introduces the security model of the identity-based forward secure digital signature algorithm. The FSIBS algorithm defined in this article is unforgeability in the case of adaptive identity selection and adaptive selection message attacks.

Setup: Challenger C sets the system public parameters mpk, and sends mpk to opponent F.

Queries: At this stage, opponent F makes the following queries:

UserKeyExt: Adversary F makes an inquiry about identity information $id\left(id=ID\parallel T\right)$. Challenger C generates a signature private key for identity information id $S{K}_{id\parallel 0}$, and sends it to opponent F;

Breaking oracle: When receiving an inquiry (id, j) from the opponent F. Where $id=ID\parallel T$, $1\le j\le T$, challenger C returns the signature private key at time j $S{K}_{id\parallel j}$ to opponent F;

Signing oracle: When receiving an inquiry $\left(id,i,M\right)$ from adversary F, using the signature private key at time i $S{K}_{id\parallel i}$, challenger C generates a digital signature sig about message M.

After each moment, the adversary F can choose to execute the signature query at the next moment, or execute the corresponding forgery.

Forgery phase: In this phase, after polynomial time, the adversary F ends the above-mentioned inquiry phase, and then uses the knowledge he has acquired to forge a signature of the user whose identity is $i{d}^{*}$ to the message $M^{*}si{g}^{*}$, the opponent F can win the game if and only if the following conditions are true:

1) ${\text{FSIBSVerify}}_{mpk}\left(i{d}^{*},i^{*},M^{*},si{g}^{*}\right)=1,1\le i^{*}<j$ ;

2) The adversary F has never asked about the identity $i{d}^{*}$ ;

3) The opponent F has never signed $\left(i{d}^{*},i^{*},M^{*}\right)$.

4. Description of Forward Secure Digital Signature Algorithm Based on Identity on Grid

In this section, we present the forward secure digital signature algorithm (FSIBS) based on the identity on the grid. Set the required parameters of the program: Prime number $q\ge 3$, positive real number $M\approx e$, positive integer $m>5n\log q,k,\lambda$, real number $\tilde{L}=O\left(\sqrt{n\log q}\right)$, Gaussian parameter $s=\stackrel{⌣}{L}\cdot \omega \left(\sqrt{\log n}\right)$ and real number $\sigma =12s\lambda m$. The system defines two secure hash functions $H_1:{\left\{0,1\right\}}^{*}\to Z_q^{n\times k}~D_{n\times k}$ ; $H:{\left\{0,1\right\}}^{*}\to \left\{v:v\in {\left\{-1,0,1\right\}}^k,{\Vert v\Vert }_1\le \lambda \right\}$. Below we give an identity-based forward secure digital signature algorithm under the random oracle model:

FSIBSSetup: Based on the security parameter n, PKG runs the algorithm $\text{TrapGen}\left(q,n\right)$ to generate a matrix $A\in Z_q^{n\times m}$, and a short basis $T_A\in Z_q^{m\times m}$ of the lattice ${\text{Λ}}_q^{\perp }\left(A\right)$, and satisfy $\Vert \widetilde{T_A}\Vert \le O\left(\sqrt{n\log q}\right)$. The system outputs public parameters $mpk=\left\{A,H,H_1\right\}$, and keeps the secret master key $msk=T_A$.

FSIBSExtract: the received user’s identity information $id=ID\parallel T$, where ID is the user’s real identity, and T is the preset time period associated with the signature private key. PKG uses its own master key msk to generate the user’s original private key $S{K}_{id\parallel 0}$.

1) Let $R_{id\parallel 0}=H_1\left(id\parallel 0\right)\in Z_q^{n\times k}$, calculate $A_{id\parallel 0}=A{\left(R_{id\parallel 0}\right)}^{-1}$ ;

2) PKG runs the algorithm $\text{SampleMat}\left(A,T_A,s,H_1\left(id\parallel 0\right)\right)$ to generate $S{K}_{id\parallel 0}$ as the user’s original private key, and then secretly sends it to the user through a secure channel. According to the nature of the algorithm SampleMat, we know that the key $S{K}_{id\parallel 0}$ satisfies $A_{id\parallel 0}\cdot S{K}_{id\parallel 0}=H_1\left(id\parallel 0\right)$ and $\Vert S{K}_{id\parallel 0}\Vert \le s\sqrt{m}$.

FSIBSUpdate: Given $\left(id,i,S{K}_{id\parallel i-1}\right)$, where $id=ID\parallel T$, i is this moment. $S{K}_{id\parallel i-1}$ is the signature private key of i − 1 at the previous moment, the user performs the following steps:

For i = 1 to T, the execution is as follows:

1) If i = 1, set $S{K}_{id\parallel 0}$ as the user’s original signature private key;

2) Calculate $R_{id\parallel i-1}=H_1\left(id\parallel i-1\right)\cdots H_1\left(id\parallel 0\right)\in Z_q^{n\times k}$, $A_{id\parallel i-1}=A{\left(R_{id\parallel i-1}\right)}^{-1}$ as the public key at time i − 1.

3) Let $R_i=H_1\left(id\parallel i\right)$, calculate $S{K}_{id\parallel i}\leftarrow \text{SampleMat}\left(A_{id\parallel i-1},T_A,s,H_1\left(id\parallel i\right)\right)$.

4) Output $S{K}_{id\parallel i}$.

FSIBSSign: Given $\left(id,i,M\right)$, where $id=ID\parallel T$, i is the moment, M is the message to be signed, the user performs the following operations:

1) First choose a $y_i\leftarrow D_{\sigma }^m$ ;

2) Calculate $c_i=H\left(A_{id\parallel i}{y}_i,M\right)$ and $z_i=S{K}_{id\parallel i}\cdot c_i+y_i$ ;

3) With the probability $\min \left(1,\frac{D_{\sigma }^m\left(z_i\right)}{M{D}_{\sigma ,S{k}_{id\parallel i}c}^m\left(z_i\right)}\right)$, output the signature $sig=\left(z_i,c_i\right)$. If there is no signature output, the algorithm is repeated until there is a signature output.

FSIBSVerify: Given $\left(id,i,M,sig\right)$, enter the system’s public parameters mpk, message M, signature $sig=\left(z_i,c_i\right)$, and identity $id=ID\parallel T$, if $c_i=H\left(A_{id\parallel i}{z}_i-H_1\left(id\parallel i\right)c_i,M\right)$ and $\Vert z_i\Vert \le 2\sigma \sqrt{m}$, then output Accept.

Theorem 4.1 the identity-based forward secure digital signature scheme proposed in this section satisfies the correctness.

Proof: According to the construction of the above signature scheme, we know

$\begin{array}{c}{A}_{id\parallel i}{z}_i-H_1\left(id\parallel i\right)c_i=A_{id\parallel i}{z}_i-A_{id\parallel i}\cdot S{K}_{id\parallel i}{c}_i\\ =A_{id\parallel i}\left(z_i-S{K}_{id\parallel i}{c}_i\right)\\ =A_{id\parallel i}{y}_i\end{array}$

So we have $H\left(A_{id\parallel i}{z}_i-H_1\left(id\parallel i\right)c_i,M\right)=H\left(A_{id\parallel i}{y}_i,M\right)=c_i$. In addition, according to Lemma 2.6 of the unsampling technique, we know that the distribution of $z_i$ is very close to $D_{\sigma }^m$. Therefore, according to Lemma 2.5, we know that $z_i$ will satisfy $\Vert z_i\Vert \le 2\sigma \sqrt{m}$ with a probability of not less than $1-2^{-m}$.

5. Proof of Safety

In this section, we mainly prove that under the random oracle model, the identity-based forward secure digital signature algorithm on the lattice can resist the unforgeability in the case of adaptive identity selection and adaptive selection message attacks.

Theorem 5.1 under the random oracle model, if the adversary F breaks the security of the identity-based forward secure digital signature scheme on the lattice with a non-negligible probability ε. Then there is an algorithm C to solve the SIS difficult problem with a non-negligible probability ε’.

Proof: Assuming that there is an opponent F that forges a digital signature with a non-negligible probability ε, below we construct an algorithm C to solve the SIS difficulty problem by running the opponent F as a subroutine and with a non-negligible probability ε’. Assume as follows:

1) For each time $i=0,1,\cdots ,T$, the adversary F adaptively performs a polynomial H1 query about the user’s identity.

2) When the adversary F performs the H1 query about the identity at time i, we assume that it has performed the H1 query before the time i.

When adversary F executes an inquiry about the user’s signature private key, we assume that it has executed the related H1 inquiry.

Setup: Algorithm C sets the corresponding public parameters, and sends the system public parameters $mpk=\left\{A,H,H_1\right\}$ to the adversary F, and the secret master key $msk=T_A$.

Attack Phase: First, algorithm C randomly guesses $i^{*}\left(1\le i^{*}\le T\right)$ as the forged signature of opponent F at this moment. Without loss of generality, suppose that the adversary F has made an H query about $\left(id,i,M\right)$ before asking about the digital signature of $\left(id,i,M\right)$. C creates four lists, $L_1,L_2,L_3,L_4$, respectively, and the initial values of the four lists are all empty.

H1 query: For any $i=0,1,\cdots ,T$, C maintains a list of H1 queries $L_1=\left(id\parallel i,{\mathcal{Q}}_i\right)$ (where Q_i represents the H1 hash function value of $id|1$. The initial value of the list is empty. Adversary F makes H1 query to $id|1$. If $\left(id\parallel i,{\mathcal{Q}}_i\right)$ is in the list, C will pass Q_i as the result of responding to H1 query to opponent F. Otherwise, C randomly selects a $R_i~D_{n\times k}$, sends R_i as the result of the response to the H1 query to the opponent F, and adds $\left(id\parallel i,R_i\right)$ to the list L1.

UserkeyExt: Adversary F randomly selects $\mathcal{l}\in \left\{1,2,\cdots ,\mathcal{Q}\right\}$, where Q is defined as the maximum number of queries about UserkeyExt. Algorithm C performs the following steps:

Adversary F makes H1 query on $id|0$, and C queries the list to find $\left(id\parallel 0,{\mathcal{Q}}_0\right)$, ${\mathcal{Q}}_0=H_1\left(id\parallel 0\right)$. C runs the algorithm $\text{SampleMat}\left(A,T_A,s,H_1\left(id\parallel 0\right)\right)$ to generate $S{K}_{id\parallel 0}$ as the user’s original private key, and then secretly sends it to the adversary F through a secure channel. And separately store $\left(id\parallel 0,{\mathcal{Q}}_0,S{K}_{id\parallel 0}\right)$ in list L2 for subsequent use.

If id is the $\mathcal{l}$ query, C terminates the operation.

Signing secret key queries: When the adversary F executes the enquiry about the signature private key of (id, i), C provides the adversary F with the signature private key at time i in the following manner $S{K}_{id\parallel i}$.

If id is not in the $\mathcal{l}$ query, the execution steps are as follows: For each time $i\in \left[T\right]$, assume in advance that the H1 query about $id\parallel j$ before time i has been responded, where $j<i$. For each inquiry about the signature private key of $id\parallel i$, C calculates $A_{id\parallel i-1}=A{\left(H_1\left(id\parallel 0\right)\right)}^{-1}{\left(H_1\left(id\parallel 1\right)\right)}^{-1}\cdots {\left(H_1\left(id\parallel i-1\right)\right)}^{-1}$, let $R_i=H_1\left(id\parallel i\right)$. Calculate $S{K}_{id\parallel i}\leftarrow \text{SampleMat}\left(A_{id\parallel i-1},T_A,s,H_1\left(id\parallel i\right)\right)$, as the user signature private key at time i, the user public key at time i is specifically expressed as follows: $A_{id\parallel i}=A{\left(H_1\left(id\parallel 0\right)\right)}^{-1}{\left(H_1\left(id\parallel 1\right)\right)}^{-1}\cdots {\left(H_1\left(id\parallel i-1\right)\right)}^{-1}{R}_i^{-1}$. Finally, C returns $S{K}_{id\parallel i}$ to opponent F, and stores $\left(id\parallel i,A_{id\parallel i},S{K}_{id\parallel i}\right)$ to list L3.

If id is the $\mathcal{l}$ query, C executes as follows:

If $i\le i^{*}$, then C chooses a random uniform matrix $W\in Z_q^{n\times k}$ to the opponent F.

If $i=i^{*}+1$, C runs the trapdoor generation algorithm $\text{TrapGen}\left(q,n\right)$ to generate a matrix $A_{id\parallel i^{*}+1}\in Z_q^{n\times m}$, and the corresponding trapdoor short base $S{K}_{id\parallel i^{*}+1}\in Z_q^{m\times m}$. Then C returns $S{K}_{id\parallel i^{*}+1}$ to opponent F, and finally C stores $\left(id\parallel i^{*}+1,A_{id\parallel i^{*}+1},S{K}_{id\parallel i^{*}+1}\right)$, to list L3.

If $i^{*}+1\le i\le T$, then C executes the same steps as if id was not in the $\mathcal{l}$ query.

H query: For a different $\left(id,i,M\right)$, C first verifies whether it has been asked before, and if it has been asked, it returns the corresponding value. Otherwise, C queries the lists L_1 and L_3 to see if it can find $\left(id\parallel i,H_1\left(id\parallel i\right)\right)$ and $\left(id\parallel i,A_{id\parallel i},S{K}_{id\parallel i}\right)$. If they can all be found, randomly select a vector $y_i\leftarrow D_{\sigma }^m$, and C runs the algorithm: $c_i=H\left(A_{id\parallel i}{y}_i,M\right)$ and $z_i=S{K}_{id\parallel i}\cdot c_i+y_i$, C with probability $\min \left(1,\frac{D_{\sigma }^m\left(z_i\right)}{M{D}_{\sigma ,S{k}_{id\parallel i}c}^m\left(z_i\right)}\right)$ output the signature $sig=\left(z_i,c_i\right)$ to the opponent F. Store $\left(id,i,M,sig\right)$ to list L4. If none of them are found, C generates and stores the corresponding values in the lists L1 and L3 as before, and then continues with the above steps.

Sign queries: Adversary F makes a signature query about each information $\left(id,i,M\right)$, and C answers the query as follows:

If id is not in the $\mathcal{l}$ query, the steps are as follows: C query list L4 to see if $\left(id,i,M,sig\right)$ can be found, if it can be found in the list, C returns the digital signature sig of message M at time i. Otherwise, C queries lists L1 and L3 respectively to see if it can find $H_1\left(id\parallel i\right)$ and $S{K}_{id\parallel i}$. If not found, C generates these values as before, and finally C runs the algorithm: $c_i=H\left(A_{id\parallel i}{y}_i,M\right)$ and $z_i=S{K}_{id\parallel i}\cdot c_i+y_i$. C outputs the signature $sig=\left(z_i,c_i\right)$ to the opponent F with probability $\min \left(1,\frac{D_{\sigma }^m\left(z_i\right)}{M{D}_{\sigma ,S{k}_{id\parallel i}c}^m\left(z_i\right)}\right)$. And store $\left(id,i,M,sig\right)$ to list L4.

If id is the $\mathcal{l}$ query, the execution steps are as follows: if $i^{*}<i\le T$, then C generates the corresponding digital signature as before. Otherwise, C terminates the operation.

Breaking queries: The adversary asks about the signature private key of a specific identity and time (id, j). If id is not in the $\mathcal{l}$ query, C queries list L3 and provides the signature private key $S{K}_{id\parallel j}$ at time j to opponent F. If id is the $\mathcal{l}$ query and $j=i^{*}$, then C terminates the operation.

Forgery Phase: At this stage, adversary F outputs identity $i{d}^{*}$, time t^*, message M^*, signature sig^*, and the forgery of adversary F is successful if and only if the following conditions are met simultaneously:

1) ${\text{FSIBSVerify}}_{mpk}\left(i{d}^{*},i^{*},M^{*},si{g}^{*}\right)=1,1\le i^{*}<j$ ;

2) The adversary F has never asked about the identity $i{d}^{*}$ ;

3) Rival F has never signed $\left(i{d}^{*},i^{*},M^{*}\right)$.

Once the adversary F outputs the forged digital signature, C performs the following steps:

First check whether $i{d}^{*}$ is the $\mathcal{l}$ query, and check whether $t^{*}=i^{*}$ holds. If any of the conditions are not met, C terminates the operation.

The SIS problem that Algorithm C hopes to solve is to find a non-zero vector $x\in Z^m$ that satisfies $\Vert x\Vert \le \left(4\sigma +2s\lambda \right)\sqrt{m}$ so that $Ax=0\left(\mathrm{mod}q\right)$. C calls opponent F again and runs the above simulation process again. According to the general bifurcation lemma [32], the adversary F outputs a new forged digital signature $\left(c^{\prime },z^{\prime }\right)$ about the identity $i{d}^{*}$ and the message M^* with a non-negligible probability. Make $c^{*}\ne c^{\prime }$, and $A_{id\parallel i}{z}^{*}-H_1\left(id\parallel i\right)c^{*}=A_{id\parallel i}{z}^{\prime }-H_1\left(id\parallel i\right)c^{\prime }$. Substituting $H_1\left(id\parallel i\right)=A_{id\parallel i}\cdot S{K}_{id\parallel i}$ into the above formula, and combining similar terms, we can get:

$\begin{array}{l}{A}_{id\parallel i}{z}^{*}-H_1\left(id\parallel i\right)c^{*}-A_{id\parallel i}{z}^{\prime }+H_1\left(id\parallel i\right)c^{\prime }\\ =A_{id\parallel i}\left(z^{*}-z^{\prime }+S{K}_{id\parallel i}{c}^{\prime }-S{K}_{id\parallel i}{c}^{*}\right)=0\end{array}$

According to the legality of the signature, we know that $\Vert z^{*}\Vert$, $\Vert z^{\prime }\Vert \le 2\sigma \sqrt{m}$. At the same time, according to the above simulation parameter generation process, we also know that $\Vert S{K}_{id\parallel i}{c}^{\prime }\Vert$, $\Vert S{K}_{id\parallel i}{c}^{*}\Vert \le s\lambda \sqrt{m}$ holds with overwhelming probability.

Obviously, if $\Vert z^{*}-z^{\prime }+S{K}_{id\parallel i}{c}^{\prime }-S{K}_{id\parallel i}{c}^{*}\Vert \ne 0$, we get one of the above SIS problems solution. Therefore, we need to prove that the probability of $z^{*}-z^{\prime }+S{K}_{id\parallel i}{c}^{\prime }-S{K}_{id\parallel i}{c}^{*}\ne 0$ is not negligible.

Because $c^{*}\ne c^{\prime }$, there is $c_i^{\ast }\ne {c^{\prime }}_i$. In addition, according to the minimum entropy property of the original image given in the literature [32]. We know that there is a high probability that there is a signature private key $S{K}_{id\parallel i}^{*}$, so that in addition to the i-th column, $S{K}_{id\parallel i}^{*}$ and $S{K}_{id\parallel i}$ is exactly the same. And $A_{id\parallel i}S{K}_{id\parallel i}=A_{id\parallel i}S{K}_{id\parallel i}^{*}$.

Table 1. Scheme performance comparison.

Because $\begin{array}{l}{z}^{*}-z^{\prime }+S{K}_{id\parallel i}^{*}\left(c^{\prime }-c^{*}\right)-\left(z^{*}-z^{\prime }+S{K}_{id\parallel i}\left(c^{\prime }-c^{*}\right)\right)\\ =\left(S{K}_{id\parallel i}^{*}-S{K}_{id\parallel i}\right)\left(c^{\prime }-c^{*}\right)\ne 0\end{array}$. Therefore, if $z^{*}-z^{\prime }+S{K}_{id\parallel i}^{*}\left(c^{\prime }-c^{*}\right)=0$, then $z^{*}-z^{\prime }+S{K}_{id\parallel i}\left(c^{\prime }-c^{*}\right)\ne 0$ must be true. In addition, we know that the signature keys $S{K}_{id\parallel i}^{*}$ and $S{K}_{id\parallel i}$ play exactly the same role in the simulation process. Therefore, the adversary F does not know which signature key algorithm C uses in the simulation process. Therefore, $\mathrm{Pr}\left[z^{*}-z^{\prime }+S{K}_{id\parallel i}\left(c^{\prime }-c^{*}\right)\ne 0\right]\ge 0.5$, and we have completed the proof of the theorem.

Here we compare with the classic algorithm in literature [22] [23], in which literature [22] constructs the first identity-based forward secure digital signature algorithm on the grid. Literature [23] proposed the most famous lattice identity-based hierarchical identity signature algorithm so far. Define UPK as the size of the user’s public key, and USK as the size of the user’s private key. The bit length of the elements in $Z_q$ is expressed as $\log q$. In these algorithms, the master public key and the master private key are respectively $Z_q^{n\times m}$, $Z_q^{m\times m}$, and no more comparison between them. Table 1 shows the performance comparison between the programs.

According to the definition 2.5, we know that $k<n\le m$, so the signature private key and signature length in our scheme are smaller than those in [22] [23]. In addition, the cumbersome Samplepre algorithm and lattice delegation technology used in the literature [22] require large calculation, communication, and storage costs, and are less efficient. Therefore, our program has certain advantages.

6. Conclusion

This paper combines Lyubashevsky [31] ’s trap-free signature and extended pre-image sampling function technology to design an efficient (FSIBS) scheme. Under the random oracle model, the hypothesis based on small integers to solve difficult problems proves that our scheme is unforgeable against adaptive selection identity and adaptive selection message attacks, without the cumbersome Samplepre algorithm and lattice delegation technology. Compared with the existing scheme, the signature private key and signature length are shorter, which has certain practicability. How to extend our program to the standard model is our next research goal.

Acknowledgements

The authors would like to thank the reviewers for their detailed reviews and constructive comments, which have helped improve the quality of the paper. This work is supported by the National Natural Science Foundation of China (No. 6206070270).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Shamir, A. (1984) Identity-Based Cryptosystems and Signature Schemes. In: Proceedings of Workshop on the Theory and Application of Cryptographic Techniques, Springer Press, Paris, 47-53. https://doi.org/10.1007/3-540-39568-7_5
[2]	Hess, F. (2002) Efficient Identity Based Signature Schemes Based on Pairings. In: Proceedings of International Workshop on Selected Areas in Cryptography, Springer Press, Newfoundland, 310-324. https://doi.org/10.1007/3-540-36492-7_20
[3]	Yi, X. (2003) An Identity-Based Signature Scheme from the Weil Pairing. IEEE Communications Letters, 7, 76-78. https://doi.org/10.1109/LCOMM.2002.808397
[4]	Barreto, P.S.L.M., Libert, B., McCullagh, N., et al. (2005) Efficient and Provably-Secure Identity-Based Signatures and Signcryption from Bilinear Maps. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Springer, Chennai, 515-532. https://doi.org/10.1007/11593447_28
[5]	Chai, Z., Cao, Z. and Dong, X. (2007) Identity-Based Signature Scheme Based on Quadratic Residues. Science in China Series F: Information Sciences, 50, 373-380. https://doi.org/10.1007/s11432-007-0038-1
[6]	Xiong, H., Hu, J., Chen, Z., et al. (2011) On the Security of an Identity Based Multi-Proxy Signature Scheme. Computers & Electrical Engineering, 37, 129-135. https://doi.org/10.1016/j.compeleceng.2011.01.006
[7]	Yang, P., Cao, Z. and Dong, X. (2011) Fuzzy Identity Based Signature with Applications to Biometric Authentication. Computers & Electrical Engineering, 37, 532-540. https://doi.org/10.1016/j.compeleceng.2011.04.013
[8]	Shor, P.W. (1999) Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Review, 41, 303-332. https://doi.org/10.1137/S0036144598347011
[9]	Ajtai, M. (1996) Generating Hard Instances of Lattice Problems. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, ACM Press, New York City, 99-108. https://doi.org/10.1145/237814.237838
[10]	Lyubashevsky, V. and Micciancio, D. (2008) Asymptotically Efficient Lattice-Based Digital Signatures. In: Proceedings of Theory of Cryptography Conference, ACM Press, New York, 37-54. https://doi.org/10.1007/978-3-540-78524-8_3
[11]	Gentry, C., Peikert, C. and Vaikuntanathan, V. (2008) Trapdoors for Hard Lattices and New Cryptographic Constructions. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, ACM Press, Victoria, 197-206. https://doi.org/10.1145/1374376.1374407
[12]	Cash, D., Hofheinz, D., Kiltz, E., et al. (2010) Bonsai Trees, or How to Delegate a Lattice Basis. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer Press, Tallinn, 523-552. https://doi.org/10.1007/978-3-642-13190-5_27
[13]	Agrawal, S., Boneh, D. and Boyen, X. (2010) Efficient Lattice (H) IBE in the Standard Model. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer Press, Tallinn, 553-572. https://doi.org/10.1007/978-3-642-13190-5_28
[14]	Gentry, C. (2009) Fully Homomorphic Encryption Using Ideal Lattices. In: Proceedings of the 51st Annual ACM Symposium on Theory of Computing, ACM Press, Phoenix, 169-178. https://doi.org/10.1145/1536414.1536440
[15]	Anderson, R. (1997) Two Remarks on Public Key Cryptology (Invited Lecture). In: Proceedings of the ACM Conference on Computer and Communications, ACM Press, Zurich, 135-147.
[16]	Bellare, M. and Miner, S.K. (1999) A Forward-Secure Digital Signature Scheme. In: Proceedings of Annual International Cryptology Conference, Spring Press, Santa Barbara, 431-448. https://doi.org/10.1007/3-540-48405-1_28
[17]	Yu, J., Kong, F., Cheng, X., et al. (2011) Forward-Secure Identity-Based Public-Key Encryption without Random Oracles. Fundamenta Informaticae, 111, 241-256. https://doi.org/10.3233/FI-2011-562
[18]	Chen, X., Zhang, F., Tian, H., et al. (2011) Discrete Logarithm Based Chameleon Hashing and Signatures without Key Exposure. Computers & Electrical Engineering, 37, 614-623. https://doi.org/10.1016/j.compeleceng.2011.03.011
[19]	Liu, Y., Yin, X. and Qiu, L. (2008) ID-Based Forward-Secure Signature Scheme from the Bilinear Pairings. In: Proceedings of International Symposium on Electronic Commerce and Security, IEEE Press, Guangzhou, 179-183. https://doi.org/10.1109/ISECS.2008.220
[20]	Yu, J., Hao, R., Kong, F., et al. (2011) Forward-Secure Identity-Based Signature: Security Notions and Construction. Information Sciences, 181, 648-660. https://doi.org/10.1016/j.ins.2010.09.034
[21]	Al Ebri, N., Baek, J., Shoufan, A., et al. (2013) Forward-Secure Identity-Based Signature: New Generic Constructions and Their Applications. Journal of Wireless Mobile Networks, Ubiquitous Computing and Dependable Applications, 4, 32-54.
[22]	Zhang, X., Xu, C., Jin, C., et al. (2014) Efficient Forward Secure Identity-Based Shorter Signature from Lattice. Computers & Electrical Engineering, 40, 1963-1971. https://doi.org/10.1016/j.compeleceng.2013.12.003
[23]	Rückert, M. (2010) Strongly Unforgeable Signatures and Hierarchical Identity-Based Signatures from Lattices without Random Oracles. In: Proceedings of International Workshop on Post-Quantum Cryptography, Springer Press, Darmstadt, 182-200. https://doi.org/10.1007/978-3-642-12929-2_14
[24]	Agrawal, S., Boneh, D. and Boyen, X. (2010) Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE. In: Proceedings of Annual Cryptology Conference, Springer, Press, Santa Barbara, 98-115. https://doi.org/10.1007/978-3-642-14623-7_6
[25]	Goldreich, O., Goldwasser, S. and Micali, S. (1984) On the Cryptographic Applications of Random Functions. In: Proceedings of Workshop on the Theory and Application of Cryptographic Techniques, Springer Press, Paris, 276-288. https://doi.org/10.1007/3-540-39568-7_22
[26]	Fiat, A. and Shamir, A. (1986) How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In: Proceedings of Conference on the Theory and Application of Cryptographic Techniques, Springer Press, Saragossa, 186-194. https://doi.org/10.1007/3-540-47721-7_12
[27]	Bellare, M. and Rogaway, P. (1993) Random Oracles Are Practical: A Paradigm for Designing Efficient Protocols. In: Proceedings of the 1st ACM Conference on Computer and Communications Security, ACM Press, Fairfax, 62-73. https://doi.org/10.1145/168588.168596
[28]	Micciancio, D. and Regev, O. (2007) Worst-Case to Average-Case Reductions Based on Gaussian Measures. SIAM Journal on Computing, 37, 267-302. https://doi.org/10.1137/S0097539705447360
[29]	Alwen, J. and Peikert, C. (2011) Generating Shorter Bases for Hard Random Lattices. Theory of Computing Systems, 48, 535-553. https://doi.org/10.1007/s00224-010-9278-3
[30]	Tian, M. and Huang, L. (2013) Lattice-Based Message Recovery Signature Schemes. International Journal of Electronic Security and Digital Forensics, 5, 257-269. https://doi.org/10.1504/IJESDF.2013.058658
[31]	Lyubashevsky, V. (2012) Lattice Signatures without Trapdoors. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer Press, Minneapolis, 738-755. https://doi.org/10.1007/978-3-642-29011-4_43
[32]	Bellare, M. and Neven, G. (2006) Multi-Signatures in the Plain Public-Key Model and a General Forking Lemma. In: Proceedings of the 13th ACM Conference on Computer and Communications Security, ACM Press, Taiwan, 390-399. https://doi.org/10.1145/1180405.1180453