# Provably Secure Lattice-Based Self-Certified Signature Scheme

Authors: Qiang Yang; Daofeng Li
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Digital signatures are crucial network security technologies. However, in traditional public key signature schemes, the certificate management is complicated and the schemes are vulnerable to public key replacement attacks. In order to solve the problems, in this paper, we propose a self-certified signature scheme over lattice. Using the self-certified public key, our scheme allows a user to certify the public key without an extra certificate. It can reduce the communication overhead and computational cost of the signature scheme. Moreover, the lattice helps prevent quantum computing attacks. Then, based on the small integer solution problem, our scheme is provable secure in the random oracle model. Furthermore, compared with the previous self-certified signature schemes, our scheme is more secure.


---

## Body

## 1. Introduction

Due to the development of the Internet, various networks require to verify the authenticity of the message or the user, such as data verification for Internet of Vehicles [1] and user authentication for industry and mobility networks [2, 3]. In general, these authentication systems can be divided into traditional public key infrastructure- (PKI-) based cryptosystems with certificates [4] and certificateless cryptosystems [5, 6]. In a PKI-based cryptosystem, a certificate issued by the certificate authority (CA) is often required to certify the authenticity of the relationship between the public key and the user. However, it increases the computation overheads and communication costs because certificate management is complicated. Furthermore, it is vulnerable to public key replacement attacks if certificates are not used. To avoid certificate management, in 1984, Shamir [5] introduced the idea of an identity-based (IB) cryptosystem. The public key of a user is the user’s identity information. Although it does not require any certificates, it suffers from the key escrow problem.To deal with the above problems, in 1991, Girault [7] introduced the notion of self-certified public keys, which can enable the public key to implicitly authorize the user’s identity without an extra certificate. Concretely, the public key is computed by the user and the authority. Then, the verification of the authenticity of the signature and public key is placed in a logically single step. Thus the self-certified signature scheme can mitigate the burdens for the certificate management and storage and prevent the key escrow problem. Therefore, self-certified signature schemes have a promising future for environments with limited memory and computational capacity, such as smart mobile devices [8], wireless sensor networks [9], the cloud [10], and vehicular ad hoc networks [11].However, most of them are based on discrete logarithm problems or large integer factorization problems. Unfortunately, Shor [12] pointed out that the two problems are easily solved by quantum computers, so the signature schemes based on the two problems are no longer secure in the quantum era. Lattice cryptography is one of the postquantum candidate schemes proposed by the National Institute of Standards and Technology [13]. Meanwhile, in recent years, lattice cryptography on the refinements of the security assessment and the fast implementation [14, 15] has achieved rapid developments. Thus, to prevent quantum attacks, in this paper, based on lattice cryptography, we propose a provably secure self-certified signature scheme in the random oracle model (ROM).Our contributions are mainly as follows: firstly, our scheme adopts the advantages of self-certified public keys and lattice signature schemes, which simplifies the public key authentication process of the scheme and avoids the key escrow problems and public key replacement attacks. Moreover, it can resist quantum attacks. Secondly, based on the hardness of the small integer solution (SIS) problem, our scheme is existential unforgeability against two types of adversaries in the ROM.Related work: in PKI-based signature schemes [16], CA issues a certificate for the user, which increases the burden of certificate management and storage.Many schemes are proposed to reduce the cost of certification management and storage. For instance, numerous IB signature schemes are proposed. In these schemes, the public key is the user’s identity. Therefore, it does not need an extra certificate, but it is vulnerable to the key escrow problem because the key generation center (KGC) generates the private keys of all users [17]. Thus, a malicious KGC can impersonate any user. The certificateless public key cryptography [6] also does not require a separate certificate. Recently, Gowri et al. [18] proposed a certificateless signatures scheme from ECC, but later Xu et al. [19] found that it is vulnerable to signature forgery attacks.To solve the above problems, Girault [7] proposed the self-certified cryptosystem, in which there are no certificates, and neither the user nor the authority can independently obtain the full private key of the user.Since the self-certificated public key was introduced, many self-certified signature schemes have been proposed. Shao [20] proposed a novel self-certified signature scheme from pairings, but it was later proved to be insecure. In addition, some self-certified signature schemes based on discrete logarithm problems were also proposed, Xie [21] and Wu and Xu [22]. However, Sadeghpour [23] pointed out that Wu and Xu’s scheme [22] is vulnerable to internal attacks. Moreover, there exist also several self-certified signature and authentication schemes applied to specific scenarios [9, 11, 24, 25]. Nevertheless, these schemes are not secure against quantum attacks because the hard assumptions are not difficult for quantum computers.Using the lattice to implement the postquantum self-certified signature scheme is a considerable method. Li et al. [8] first proposed a lattice-based self-certified signatures scheme. However, this scheme is based on NTRUSign, so it lacks rigorous security proof. Moreover, there are no other self-certified signature schemes over lattice. Tian and Huang [26] and others propose several lattice-based certificateless signatures schemes, which do not need the certificate too. However, they cannot prevent insider attack, and there exist other flaws [27, 28]. Hence, in this paper, we aim to propose a provably secure self-certified signature scheme over lattice.The rest of the paper is organized as follows: in Section2, we introduce some basic concepts of lattice signature schemes. In Section 3, we introduce the syntax of the self-certified signature scheme and the security model. In Section 4, we introduce our scheme. In Section 5, we analyze the correctness, security, and comparisons. Finally, we give our conclusion and further work.


## 2. Preliminaries

### 2.1. Notations

The notations used in this paper are listed as follows:(1)
Letℝ be the set of real numbers, ℤ the set of integers, and ℕ the set of nonnegative integer numbers. For a positive integer p, ℤp is the set of integers modulo p.(2)
Column vectors are written as bold lowercase letters, for example,v. The i th component of v is represented by vi, the lp norm of v is denoted by vp, and define vp:=∑vip1/p. The l2 norm of v can be denoted by v, and the l∞ norm of v is denoted by v∞, and define v∞:=maxivi. Matrices are represented by bold uppercase letters, for example, B. Let the i th column of B be represented by bi and define the norm B=maxibi. If B is a full rank square matrix, its Gram–Schmidt orthogonalization is denoted by B˜, and B˜=maxibi. Let vt and Bt denote the transpositions of the vector v and the matrix B, respectively.(3)
For a real numberσ, Dσ denotes the Gaussian distribution with the standard variance σ. Moreover, a←Dσm denotes that each component of the vector a is sampled from Dσm. For a random value v and a set S, v←S denotes that v is sampled uniform from the set S.


### 2.2. Lattice

Definition 1.
(lattice). A lattice is a discrete subgroup ofℝn. Let B=b1,b2,…,bn∈ℝn×n, where b1,b2,…,bn are n linear independent vectors. The lattice ℒB in the n-dimensional Euclidean space generated by the basis B is defined as ℒB=ΛB=∑i=1ncibi:ci∈ℤ.Forq,n,m∈ℕ, let q≥2 and A∈ℤn×m and define the q-ary lattice as follows:(1)Λ⊥AorΛq⊥A:x∈ℤm:Ax=0modq,w∈ℤqn,Λw⊥A:x∈ℤm:Ax=wmodq.The dual lattice ofΛ is denoted by Λ∗, defined as Λ∗=x∈ℝn:∀v∈Λ,x,v=ℤ.Definition 2.
(small integer solution (SIS) problem [29]). For any n∈ℤ, given positive integers q,m∈ℤ, a matrix A∈ℤqn×m and β∈ℝ, SISn,m,q,β problem is finding a nonzero integer vector x∈ℤm satisfying Ax=0modq and x≤β.Definition 3.
(inhomogeneous SIS(ISIS) problem).For anyn∈ℤ, positive integersq,m∈ℤ,A∈ℤqn×m, andβ∈ℝ,ISISn,m,q,βproblem is defined as follows: giveny∈ℤqn, find a vectorx∈ℤmsuch thatAx=ymodqandx≤β.The hardness of (I)SIS is based on the lattice problems in the worst case [29, 30].Lemma 1.
(hardness). For any polynomial boundsm,β and a prime number q≥βωnlogn, solving (I)SIS problems is as hard as solving GapSVP and SIVP on an arbitrary n-dimensional lattice.


### 2.3. Gaussian on Lattices

Definition 4.
(Gaussian function). For any reals>0, center c∈ℝn and define the Gaussian function on ℝn as(2)∀x∈ℝn,ρc,sx=exp−πx−c2/s2.For simplicity, whens and c are taken to be 1 and 0, respectively, they can be omitted.Discrete Gaussian distribution: the Gaussian distribution overℤ is defined as Dsx=ρsx/ρsℤ.For anys>0, c∈ℝn, and n-dimensional lattice Λ, define the discrete Gaussian distribution over lattice DΛ+c,s as(3)∀x∈Λ+c,DΛ+c,sx=ρsx/ρsΛ+c.Definition 5.
(smoothing parameter [31]). For a lattice Λ and real ε>0, the smoothing parameter ηεΛ of the lattice is the smallest real s>0 such that ρ1/sΛ∗\0<ε.Fors≥2ηεΛ, the Gaussian distribution DΛ,s is close to a uniform distribution.Lemma 2.
(see[30]). For the lattice Λ with a basis B, let Gaussian parameter s≥B˜⋅ωlogm, Prx←DΛ,s:x≥sm≤negln.Lemma 3.
(see[30]). For any n-dimensional lattice Λ with basis B and real ε>0, there is ηεΛ≤B˜⋅ln2n1+1/ε/π, where B˜=b2+1 with a base b and ηεℤn≤ln2n1+1/ε/π.


### 2.4. Short Bases of Lattice

Definition 6.
(gadget-lattice [32]). The gadget matrix G is defined as G=In⊗gt∈ℤn×nk with k-dimensional gadget vector gt=1,b,…,bk−1, where k=⌈logbq⌉, and the default value of b is 2. The q-ary lattice Λq⊥G is the sum of n copies of the lattice Λq⊥gt. And Λu⊥G=Λu1⊥gt⊕⋯⊕Λun⊥gt, where Λu⊥gt=x∈ℤk:gtx=umodq=Λq⊥gt+u and ui∈ℤq.The (I)SIS problems are easily solved on the gadget matrixG.Definition 7.
(G-Trapdoor [32]). For the matrices A∈ℤqn×m and G∈ℤqn×w, where m=Onlogq, w=nk, k=⌈log2q⌉, and m≥w≥n. The G-Trapdoor of A is a matrix R∈ℤm−w×w such that ARI=HG for H∈ℤqn×n.Here,H is an invertible matrix. The quality of the trapdoor is determined by its maximum singular value s1R.The most efficient trapdoor generation algorithm now is the G-TrapGen [32].Lemma 4.
(G-TrapGen [32]). Let m¯=m−w and A¯∈ℤqn×m¯, and set H=I. There is a probabilistic polynomial time (PPT) algorithm that outputs a parity-check matrix A=A¯|G−A¯R∈ℤqn×m and the trapdoor R∈ℤm¯×w.The matrixA is statistically close to uniformly random. The quality of the trapdoor is s1R≤m⋅ωlogn.Lemma 5.
(G-Trapdoor SamlePre [32]). For the matrix-trapdoor pair A,R∈ℤqn×m×ℤm¯×w, a positive definite matrix is defined as Σp:=s2I−σ2RRtRtRI, where σ≥ηεΛq⊥G and s≈s1R⋅σ2. Given a vector u∈ℤm, there is a PPT algorithm that outputs the preimage y=p+RIz∈ℤm where p←Dℤm,Σp is a perturbation and z←DΛv⊥G,σ, such that v=u−Ap∈ℤqn.Lemma 6.
(SampleMat [26]). Let the integers n≥1, q≥2, m=Onlogq, given a matrix A∈ℤn×m and the trapdoor R, for U∈ℤn×k and the Gaussian parameter s=Onlogq. There is a PPT algorithm SampleMAT (A,R,s,U) that outputs the preimage X∈ℤm×k such that AX=U and X≤sm.


### 2.5. Rejection Sampling Technique

Lemma 7.
(see [31]). For any Gaussian parameter σ>0 and positive integer m,(4)Prx←Dσ1:x>12σ<2−100,Prx←Dσm:x>2σm<2−m.Lemma 8.
(see [33]). For any c∈ℤm, positive real α and σ=ωclogm, x←Dσm, we have(5)PrDσmx/Dc,σmx=O1<1−2ωlogm,and more specifically, if σ=αc, then(6)PrDσmx/Dc,σmx<e12/α+1/2α2>1−2−100.The rejection sampling technique ensures that the distribution of the outputted signature is independent of the signing key so that a valid signature is generated without leaking any useful information about the key.Concretely, given the distributionDσm, the signing key S, and a message μ, first sample y←Dσm, then compute c=Hy,μ and z=Sc+y, and the signature is z,c. Here, we want to obtain z sampled from Dσm instead of DSc,σm, where DSc,σm is the distribution from the shift of the distribution Dσm by an offset vector Sc. Therefore, we select an appropriate value M and output z with the probability min1,Dσmz/MDSc,σmz, so that the distribution of z is statistically indistinguishable from the distribution Dσm.


## 2.1. Notations

The notations used in this paper are listed as follows:(1)
Letℝ be the set of real numbers, ℤ the set of integers, and ℕ the set of nonnegative integer numbers. For a positive integer p, ℤp is the set of integers modulo p.(2)
Column vectors are written as bold lowercase letters, for example,v. The i th component of v is represented by vi, the lp norm of v is denoted by vp, and define vp:=∑vip1/p. The l2 norm of v can be denoted by v, and the l∞ norm of v is denoted by v∞, and define v∞:=maxivi. Matrices are represented by bold uppercase letters, for example, B. Let the i th column of B be represented by bi and define the norm B=maxibi. If B is a full rank square matrix, its Gram–Schmidt orthogonalization is denoted by B˜, and B˜=maxibi. Let vt and Bt denote the transpositions of the vector v and the matrix B, respectively.(3)
For a real numberσ, Dσ denotes the Gaussian distribution with the standard variance σ. Moreover, a←Dσm denotes that each component of the vector a is sampled from Dσm. For a random value v and a set S, v←S denotes that v is sampled uniform from the set S.


## 2.2. Lattice

Definition 1.
(lattice). A lattice is a discrete subgroup ofℝn. Let B=b1,b2,…,bn∈ℝn×n, where b1,b2,…,bn are n linear independent vectors. The lattice ℒB in the n-dimensional Euclidean space generated by the basis B is defined as ℒB=ΛB=∑i=1ncibi:ci∈ℤ.Forq,n,m∈ℕ, let q≥2 and A∈ℤn×m and define the q-ary lattice as follows:(1)Λ⊥AorΛq⊥A:x∈ℤm:Ax=0modq,w∈ℤqn,Λw⊥A:x∈ℤm:Ax=wmodq.The dual lattice ofΛ is denoted by Λ∗, defined as Λ∗=x∈ℝn:∀v∈Λ,x,v=ℤ.Definition 2.
(small integer solution (SIS) problem [29]). For any n∈ℤ, given positive integers q,m∈ℤ, a matrix A∈ℤqn×m and β∈ℝ, SISn,m,q,β problem is finding a nonzero integer vector x∈ℤm satisfying Ax=0modq and x≤β.Definition 3.
(inhomogeneous SIS(ISIS) problem).For anyn∈ℤ, positive integersq,m∈ℤ,A∈ℤqn×m, andβ∈ℝ,ISISn,m,q,βproblem is defined as follows: giveny∈ℤqn, find a vectorx∈ℤmsuch thatAx=ymodqandx≤β.The hardness of (I)SIS is based on the lattice problems in the worst case [29, 30].Lemma 1.
(hardness). For any polynomial boundsm,β and a prime number q≥βωnlogn, solving (I)SIS problems is as hard as solving GapSVP and SIVP on an arbitrary n-dimensional lattice.


## 2.3. Gaussian on Lattices

Definition 4.
(Gaussian function). For any reals>0, center c∈ℝn and define the Gaussian function on ℝn as(2)∀x∈ℝn,ρc,sx=exp−πx−c2/s2.For simplicity, whens and c are taken to be 1 and 0, respectively, they can be omitted.Discrete Gaussian distribution: the Gaussian distribution overℤ is defined as Dsx=ρsx/ρsℤ.For anys>0, c∈ℝn, and n-dimensional lattice Λ, define the discrete Gaussian distribution over lattice DΛ+c,s as(3)∀x∈Λ+c,DΛ+c,sx=ρsx/ρsΛ+c.Definition 5.
(smoothing parameter [31]). For a lattice Λ and real ε>0, the smoothing parameter ηεΛ of the lattice is the smallest real s>0 such that ρ1/sΛ∗\0<ε.Fors≥2ηεΛ, the Gaussian distribution DΛ,s is close to a uniform distribution.Lemma 2.
(see[30]). For the lattice Λ with a basis B, let Gaussian parameter s≥B˜⋅ωlogm, Prx←DΛ,s:x≥sm≤negln.Lemma 3.
(see[30]). For any n-dimensional lattice Λ with basis B and real ε>0, there is ηεΛ≤B˜⋅ln2n1+1/ε/π, where B˜=b2+1 with a base b and ηεℤn≤ln2n1+1/ε/π.


## 2.4. Short Bases of Lattice

Definition 6.
(gadget-lattice [32]). The gadget matrix G is defined as G=In⊗gt∈ℤn×nk with k-dimensional gadget vector gt=1,b,…,bk−1, where k=⌈logbq⌉, and the default value of b is 2. The q-ary lattice Λq⊥G is the sum of n copies of the lattice Λq⊥gt. And Λu⊥G=Λu1⊥gt⊕⋯⊕Λun⊥gt, where Λu⊥gt=x∈ℤk:gtx=umodq=Λq⊥gt+u and ui∈ℤq.The (I)SIS problems are easily solved on the gadget matrixG.Definition 7.
(G-Trapdoor [32]). For the matrices A∈ℤqn×m and G∈ℤqn×w, where m=Onlogq, w=nk, k=⌈log2q⌉, and m≥w≥n. The G-Trapdoor of A is a matrix R∈ℤm−w×w such that ARI=HG for H∈ℤqn×n.Here,H is an invertible matrix. The quality of the trapdoor is determined by its maximum singular value s1R.The most efficient trapdoor generation algorithm now is the G-TrapGen [32].Lemma 4.
(G-TrapGen [32]). Let m¯=m−w and A¯∈ℤqn×m¯, and set H=I. There is a probabilistic polynomial time (PPT) algorithm that outputs a parity-check matrix A=A¯|G−A¯R∈ℤqn×m and the trapdoor R∈ℤm¯×w.The matrixA is statistically close to uniformly random. The quality of the trapdoor is s1R≤m⋅ωlogn.Lemma 5.
(G-Trapdoor SamlePre [32]). For the matrix-trapdoor pair A,R∈ℤqn×m×ℤm¯×w, a positive definite matrix is defined as Σp:=s2I−σ2RRtRtRI, where σ≥ηεΛq⊥G and s≈s1R⋅σ2. Given a vector u∈ℤm, there is a PPT algorithm that outputs the preimage y=p+RIz∈ℤm where p←Dℤm,Σp is a perturbation and z←DΛv⊥G,σ, such that v=u−Ap∈ℤqn.Lemma 6.
(SampleMat [26]). Let the integers n≥1, q≥2, m=Onlogq, given a matrix A∈ℤn×m and the trapdoor R, for U∈ℤn×k and the Gaussian parameter s=Onlogq. There is a PPT algorithm SampleMAT (A,R,s,U) that outputs the preimage X∈ℤm×k such that AX=U and X≤sm.


## 2.5. Rejection Sampling Technique

Lemma 7.
(see [31]). For any Gaussian parameter σ>0 and positive integer m,(4)Prx←Dσ1:x>12σ<2−100,Prx←Dσm:x>2σm<2−m.Lemma 8.
(see [33]). For any c∈ℤm, positive real α and σ=ωclogm, x←Dσm, we have(5)PrDσmx/Dc,σmx=O1<1−2ωlogm,and more specifically, if σ=αc, then(6)PrDσmx/Dc,σmx<e12/α+1/2α2>1−2−100.The rejection sampling technique ensures that the distribution of the outputted signature is independent of the signing key so that a valid signature is generated without leaking any useful information about the key.Concretely, given the distributionDσm, the signing key S, and a message μ, first sample y←Dσm, then compute c=Hy,μ and z=Sc+y, and the signature is z,c. Here, we want to obtain z sampled from Dσm instead of DSc,σm, where DSc,σm is the distribution from the shift of the distribution Dσm by an offset vector Sc. Therefore, we select an appropriate value M and output z with the probability min1,Dσmz/MDSc,σmz, so that the distribution of z is statistically indistinguishable from the distribution Dσm.


## 3. Self-Certified Signature Scheme

### 3.1. The Syntax of the SCS

A self-certified signature (SCS) scheme consists of the following algorithms: Setup, KeyGen, Extract, Sign, and Verify:(1)
Setup: it takes a security parameter n as input and returns the system parameter pp.(2)
KeyGen: CA selects the master private key s and generates its public key PCA.(3)
Extract: each user Ui first selects his private key and the partial public key Yid and then sends Yid to CA. After receiving the request, CA extracts the partial private key sid of the user. Therefore, the full public key is PCA,ID,Yid, and the full private key is xid,sid.(4)
Sign: the user generates a signature sig of the message m with the private key xid,sid.(5)
Verify: a verifier checks the signature sig.


### 3.2. Security Model

In this section, we give the security model of the SCS scheme.SCS schemes are secure against two types of adversaries, which are classified as external and internal adversaries as follows.Type 1: Adversary (Outsider). A type 1 adversary knows the secret value of any user by listening to the public channel or replacing the public key.Type 2: Adversary (Honest-But-Curious CA). A type 2 adversary can compute the partial private key of any user, but it does not know the user’s secret value.Definition 8.
(type 1 attack). A SCS scheme is existentially unforgeable against adaptive chosen message type 1 attacks if no polynomial bounded type 1 adversaryA1 with a nonnegligible advantage wins the following game.Setup: the challengerC takes a security parameter as input and runs the setup and the KeyGen algorithms. It gives the system parameters and CA’s master public key to the adversary A1 and keeps the master secrete key secret.Queries:A1 makes following adaptive queries:(i)
Hash queries: given anyM∈0,1∗, C returns the hash value HM to A1.(ii)
Secret key queries: given a user’s identityID∈0,1∗, C returns the user’s secret key to A1.(iii)
Partial private key queries: given a user’s identityID, C returns the user’s partial private key to A1.(iv)
Public key queries: given a user’s identityID, C returns the user’s public key to A1.(v)
Public key replacement queries: given a user’s identityID and a public key pk∗, C replaces the user’s public key with pk∗.(vi)
Sign queries: given a messagem, C returns a signature σ of m to A1.(vii)
Verify queries: given a signatureσ, C responds the verification result to A1.Forgery:A1 outputs a new signature σ∗ for a message m∗, and A1 wins the game if the outputted signature σ∗ is valid and without making a partial private key query or a sign query for the message m∗.Definition 9.
(type 2 attack). A SCS scheme is existentially unforgeable under adaptive chosen message type 2 attacks if no polynomial bounded type 2 adversaryA2 with a nonnegligible advantage wins the following game.Setup: the challengerC takes a security parameter as input and runs the setup and the KeyGen algorithms. It gives the system parameters and CA’s master public key to the adversary A2 and keeps the master secrete key secret.Queries:A2 makes following adaptive queries:(i)
Hash queries: given anyM∈0,1∗, C returns the hash value HM to A2.(ii)
Secret key queries: given a user’s identityID, C returns the user’s secret key to A2.(iii)
Public key queries: given a user’s identityID, C returns the user’s public key to A2.(vi)
Sign queries: given a messagem, C returns a signature σ of m to A2.(v)
Verify queries: given a signatureσ, C returns the verification result to A2.Forgery:A2 outputs a new signature σ∗ for a message m∗, and A2 wins the game if the outputted signature σ∗ is valid and without making a secret key query or a sign query for the message m∗.Definition 10.
(unforgeability). A SCS scheme is secure if it is existentially unforgeable under adaptive chosen attacks; namely, the advantages that the adversariesA1 and A2 successfully forge a valid signature are negligible.


## 3.1. The Syntax of the SCS

A self-certified signature (SCS) scheme consists of the following algorithms: Setup, KeyGen, Extract, Sign, and Verify:(1)
Setup: it takes a security parameter n as input and returns the system parameter pp.(2)
KeyGen: CA selects the master private key s and generates its public key PCA.(3)
Extract: each user Ui first selects his private key and the partial public key Yid and then sends Yid to CA. After receiving the request, CA extracts the partial private key sid of the user. Therefore, the full public key is PCA,ID,Yid, and the full private key is xid,sid.(4)
Sign: the user generates a signature sig of the message m with the private key xid,sid.(5)
Verify: a verifier checks the signature sig.


## 3.2. Security Model

In this section, we give the security model of the SCS scheme.SCS schemes are secure against two types of adversaries, which are classified as external and internal adversaries as follows.Type 1: Adversary (Outsider). A type 1 adversary knows the secret value of any user by listening to the public channel or replacing the public key.Type 2: Adversary (Honest-But-Curious CA). A type 2 adversary can compute the partial private key of any user, but it does not know the user’s secret value.Definition 8.
(type 1 attack). A SCS scheme is existentially unforgeable against adaptive chosen message type 1 attacks if no polynomial bounded type 1 adversaryA1 with a nonnegligible advantage wins the following game.Setup: the challengerC takes a security parameter as input and runs the setup and the KeyGen algorithms. It gives the system parameters and CA’s master public key to the adversary A1 and keeps the master secrete key secret.Queries:A1 makes following adaptive queries:(i)
Hash queries: given anyM∈0,1∗, C returns the hash value HM to A1.(ii)
Secret key queries: given a user’s identityID∈0,1∗, C returns the user’s secret key to A1.(iii)
Partial private key queries: given a user’s identityID, C returns the user’s partial private key to A1.(iv)
Public key queries: given a user’s identityID, C returns the user’s public key to A1.(v)
Public key replacement queries: given a user’s identityID and a public key pk∗, C replaces the user’s public key with pk∗.(vi)
Sign queries: given a messagem, C returns a signature σ of m to A1.(vii)
Verify queries: given a signatureσ, C responds the verification result to A1.Forgery:A1 outputs a new signature σ∗ for a message m∗, and A1 wins the game if the outputted signature σ∗ is valid and without making a partial private key query or a sign query for the message m∗.Definition 9.
(type 2 attack). A SCS scheme is existentially unforgeable under adaptive chosen message type 2 attacks if no polynomial bounded type 2 adversaryA2 with a nonnegligible advantage wins the following game.Setup: the challengerC takes a security parameter as input and runs the setup and the KeyGen algorithms. It gives the system parameters and CA’s master public key to the adversary A2 and keeps the master secrete key secret.Queries:A2 makes following adaptive queries:(i)
Hash queries: given anyM∈0,1∗, C returns the hash value HM to A2.(ii)
Secret key queries: given a user’s identityID, C returns the user’s secret key to A2.(iii)
Public key queries: given a user’s identityID, C returns the user’s public key to A2.(vi)
Sign queries: given a messagem, C returns a signature σ of m to A2.(v)
Verify queries: given a signatureσ, C returns the verification result to A2.Forgery:A2 outputs a new signature σ∗ for a message m∗, and A2 wins the game if the outputted signature σ∗ is valid and without making a secret key query or a sign query for the message m∗.Definition 10.
(unforgeability). A SCS scheme is secure if it is existentially unforgeable under adaptive chosen attacks; namely, the advantages that the adversariesA1 and A2 successfully forge a valid signature are negligible.


## 4. Our Signature Scheme

Our scheme consists of five algorithms: Setup, KeyGen, Extract, Sign, and Verify.(1) Setup: given security parametersλ,n, for positive integers q,m,d,k,κ, and σ,s∈ℝ. Let q≥2, m=Onlogq>64+nlogq/log2d+1, d≪qn/m, 2κnκ≥2λ, s=Onlogq, σ=12sκ2m, and select two secure hash functions: H1:0,1∗⟶ℤqn×k, H2:0,1∗⟶v:v∈−1,0,1k,v1≤κ. Finally, publish system parameters Para=λ,n,q,m,d,k,κ,s,σ,H1,H2.(2) KeyGen: the KeyGen algorithm is described in Algorithm1. CA runs the algorithm G-TrapGen n to output the public-private key pair. The master private key is the trapdoor R, and the public key is the public matrix A.Algorithm 1: KeyGen.
Input: security parameter n.Output:A,R.(1)
OutputA,R← G-TrapGen n, A∈ℤqn×m is the master public key and R∈ℤ2n×nlogq is the master private key.(2)
Choose a random uniform matrixB∈ℤqn×m.(3)
PublishA and B, and keep R secret.(3) Extract: the extract algorithm is described in Algorithm2. The user’s public-private key pair is generated by the user and CA. UserID first selects his secret key BID and computes the partial public key PID. CA generates the partial private key XID and sends it to the user through a secure channel. Therefore, the full private key is BID,XID and the full public key is the A,PID,ID.Algorithm 2: Extract.
Input:UserID with an identity ID∈0,1∗, B∈ℤqn×m.Output: the user’s key PID,BID,XID.(1)
UserID selects a random uniform matrix BID∈ℤm×k from −d,…,0⋯,dm×k as the secret key, where BID≤dm.(2)
ComputesPID=BBIDmodq, and sends PID,ID to CA.(3)
Upon receiving thePID,ID, CA performs as follows:(i)
computesU=H1A,PID,ID∈ℤqn×k.(ii)
uses the algorithm SampleMATA,R,s,U to output XID∈ℤm×k.(iii)
sendsXID to UserID through a secure channel.(4)
UserID checks the authenticity of XID by verifying AXID=U and XID≤sm. If so, output XID as their partial private key. Otherwise, reject it.Algorithm 3: Sign.
Input: a message μ∈0,1∗, ID, the signing key BID,XID and other public parameters.Output: the signature z,c.(1)
Randomly selecty1,y2←Dσm, and compute c=H2Ay1+By2,μ.(2)
Computez1=XIDc+y1, z2=BIDc+y2, and let z=z1t,z2tt.(3)
Output the signaturez,c with probability min1,Dσ2mz/MDv,σ2mz, where v=XIDct,BIDctt.(4)
Ifz>2σ2m, repeat this algorithm.(4) Sign: the Sign algorithm is described in Algorithm3. UserID generates a signature of the message μ using the rejection sampling technique.Remark 1.
According to the rejection sampling technique described in Section2, at most M attempts, we will output a signature such that the distribution of z is statistically close to Dσ2m, and we have Prz≤2σ2m≥1−2−2m.(5) Verify: the KeyGen algorithm is described in Algorithm4. The verifier verifies the signature z,c of the message μ on ID.Algorithm 4:Verify.
Input:A,B,PID and ID, the message μ, the signature z,c.Output: the verification result.(1)
ComputeU=H1A,PID,ID.(2)
Check whetherz≤2σ2m and c=H2Az1+Bz2−PIDc−Uc,μ.(3)
If so, return accept. Otherwise, return reject.


## 5. Analysis

### 5.1. Correctness

The correctness of the scheme is as follows:First, we haveAXID=U, BBID=PID, so(7)H2Az1+Bz2−PIDc−Uc,μ,=H2AXIDc+y1+BBIDc+y2−PIDc−Uc,μ,=H2AXIDc+Ay1+BBIDc+By2−PIDc−Uc,μ,=H2AXID−U+BBID−PIDc+Ay1+By2,μ,=H2Ay1+By2,μ,=c.At this moment, we complete the proof.


### 5.2. Security Analysis

Our scheme is existentially unforgeable under the adaptive chosen message attacks in the random oracle model.Theorem 1.
Our SCS scheme is existentially unforgeable in ROM for a polynomial-time type 1 adversary. If the adversary can successfully forge a valid signature, then it can solve theSISn,m,q,β problem, where β=22σ+sκm.Proof.
Assume that there is a type 1 adversaryA who can break the scheme with nonnegligible probability. Then, we can construct a polynomial-time challenger C, who runs A as a subroutine to solve the SISn,m,q,β problem with nonnegligible probability; that is, C wins Game 1:
Game 1 setup: input the security parametern. C runs the setup and the KeyGen algorithm to obtain Para=λ,n,q,m,d,k,κ,s,σ,H1,H2 and A,R. Then, C publishes Para and A and keeps R secret. C maintains several initially empty lists: List 0, List 1, List 2, List 3, and List 4. List 0 contains IDi,PID,U=H1A,PID,IDi, where IDi is the user’s identity and PID is the partial public key. List 1 contains IDi,BID,PID,U, where BID is the secret key. List 2 contains IDi,BID,PID,U,X, where X is the partial private key. List 3 contains μ,y1,y2,c=H2⋅, where y1,y2 are two random vectors. List 4 contains IDi,μ,z,c, where z,c is the signature.
Queries:A adaptively issues several queries to C:(i)
H1queries: A sends a user’s identity IDi to C; then, C performs as follows:(1)
First looks upIDi in List 0. If found, C directly returns the hash value U of the public key.(2)
Otherwise,C randomly selects a matrix U∈ℤqm×k and returns it; then, it selects a matrix PID∈ℤqm×k, and adds IDi,PID,U to List 0.(ii)
H2 queries: A sends a message μ to C; then, C performs as follows:(1)
First, it looks upμ in List 3. If found, C directly returns the hash value c of message μ.(2)
Otherwise,C randomly selects a vector c from c:c∈−1,0,1k,c1≤κ and returns it. Then, it randomly selects two vectors y1,y2←Dσm and adds μ,y1,y2,c to List 3.(iii)
Secret matrix queries:A sends an identity IDi to C; then, C performs as follows:(1)
First, it looks upIDi in List 1. If found, C directly returns the user’s secret matrix BID.(2)
Otherwise,C selects a matrix BID∈ℤm×k from −d,…,0,…,dm×k and returns it. Then, it computes PID=BBID, U=H1A,PID,IDi and adds IDi,BID,PID,U to List 1.(vi)
Partial private key queries:A sends IDi to C; then, C performs as follows:(1)
First, it looks upIDi in List 2. If found, C directly returns the partial private key X.(2)
Otherwise,C issues a secret matrix query to obtain BID,PID,U and runs the algorithm SampleMAT A,R,s,U to output a matrix X∈ℤm×k as the partial private key.(3)
Finally,C returns X and adds IDi,BID,PID,U,X to List 2.(v)
Public key replacement queries:A sends IDi and a public key PID∗ to C and then wants to replace the user’s public key. After receiving the identity IDi, C replaces the public key with PID∗ and records this replacement.(vi)
Sign queries:A sends a message μ, IDi, and a secret matrix BID to C. Then, C performs as follows:(1)
First, it looks up the parameters in List 4. If found,C directly returns the signature.(2)
Otherwise,C issues a partial private key query to obtain the signing key X,BID, issues a H2 query to obtain c, and computes z1=Xc+y1,z2=BIDc+y2.(3)
Finally,C returns the signature z,c, where z=z1t,z2tt, and adds IDi,μ,z,c to List 4.
Forgery: after polynomial-time queries finish,A outputs a forgery z∗,c∗ on message μ∗ for IDi with nonnegligible probability. If the signature can pass the verification and partial private key queries and the sign queries for the message μ∗ are never involved in this game, then A wins the game.
Using the forking lemma [34], C replays A with different hash values of H2 queries to get another valid signature z′,c′ such that c∗≠c′ and H2Az1∗+Bz2∗−PIDc∗−Uc∗,μ∗=H2Az1′+Bz2′−PIDc′−Uc′,μ∗.
BecauseA is a type 1 adversary that can make public key replacement attacks, it is easy to obtain PID and BID. Then, only the partial private key X needs to be considered. Since U=AX, we have the equality:(8)Az1∗−Uc∗=Az′1−Uc′,Az1∗−AXc∗=Az′1−AXc′,Az1∗−z1′+Xc′−Xc∗.
Asz1∗≤2σm, z1′≤2σm, Xc∗≤sκm, Xc′≤sκm with overwhelming probability, we can see that(9)z1∗−z1′+Xc′−Xc∗≤22σ+sκm.
Now, we provez1∗−z1′+Xc′−Xc∗≠0 with nonnegligible probability.
Sincem>64+nlogq/log12s, then, by Lemma 4.2 from [33], there is another X′ with probability larger than 1−2−100 such that all the columns except for the i th column are the same as X. And AX=AX′=U. So, if z1∗−z1′+Xc′−Xc∗=0, then we have z1∗−z1′+X′c′−X′c∗≠0. Because X and X′ have the same role in our scheme, C does not know which one is used in the simulation. Hence, C can make z1∗−z1′+Xc′−Xc∗≠0 with the probability not less than 0.5. As a result, we can construct an algorithm to solve the SISn,m,q,β problem with overwhelming probability, where β=22σ+sκm.Theorem 2.
Our SCS scheme is existentially unforgeable in ROM for a polynomial-time type 2 adversary. If the adversary can successfully forge a valid signature, then it can solve theSISn,m,q,β problem, where β=22σ+dκm.Proof.
Assume that there is a type 2 adversaryA that can break out the scheme with nonnegligible probability. Then, we can construct a polynomial-time challenger C that runs A as a subroutine to solve the SISn,m,q,β problem with nonnegligible probability, that is, C wins Game 2:
Game 2 Setup: input the security parametern. C runs the setup and KeyGen algorithm to obtain Para=λ,n,q,m,d,k,κ,s,σ,H1,H2 and A,R. Then, C publishes Para and A and keeps R secret. C maintains several initially empty lists: List 0, List 1, List 3, and List 4.
Queries:A adaptively issues several queries to C:(i)
H1 queries: it is the same as the above proof.(ii)
H2 queries: it is the same as the above proof.(iii)
Secret matrix queries:A sends a user’s identity IDi to C; then, C performs as follows:(1)
First, it looks upIDi in List 1. If found, C directly returns the user’s secret matrix BID.(2)
Otherwise,C randomly selects a matrix BID∈ℤm×k from −d,…,0,…,dm×k, returns it, then computes PID=BBID, U=H1A,PID,IDi, and adds IDi,BID,PID,U to List 1.(vi)
Sign queries:A sends IDi and a message μ to C; then, C performs as follows:(1)
First, it looks up the parameters in List 4. If found,C directly returns the signature.(2)
Otherwise,C issues a secret matrix query to obtain BID, issues a H1 query to obtain the public key, and then computes X. C also issues a H2 query to obtain c and computes z1=Xc+y1,z2=BIDc+y2.(3)
Finally,C returns the signature z,c, where z=z1t,z2tt, and adds IDi,μ,z,c to List 4.
Forgery: after polynomial-time queries finish,A outputs a forgery z∗,c∗ on message μ∗ for IDi with nonnegligible probability. If the signature can pass the verification, and the secret matrix queries and the sign queries for the message μ∗ are never involved in this game, then A wins the game.
Using the forking lemma,C replays A with different hash values of H2 queries to get another valid signature z′,c′ such that c∗≠c′ and H2Az1∗+Bz2∗−PIDc∗−Uc∗,μ∗=H2Az′1+Bz′2−PIDc′−Uc′,μ∗.
BecauseA is a type 2 adversary that can obtain the partial private key XID, only the secret key BID needs to be considered. Moreover, since PID=BBID, we have the equality(10)Bz2∗−PIDc∗=Bz′2−PIDc′,Bz2∗−BBIDc∗=Bz′2−BBIDc′,Bz2∗−z2′+BIDc′−BIDc∗=0.
Asz2∗≤2σm, z2′≤2σm, BIDc∗≤dκm, BIDc′≤dκm with overwhelming probability, we can see that(11)z2∗−z2′+BIDc′−BIDc∗≤22σ+dκm.
Now, we provez2∗−z2′+BIDc′−BIDc∗≠0 with nonnegligible probability.
Sincem>64+nlogq/log2d+1 and according to Lemma 4.2 from [33], there is another secret key BID′ with the probability larger than 1−2−100 such that all columns except for the i th column are the same as BID. And PID=BB′ID=BBID. So, if z2∗−z2′+BIDc′−BIDc∗=0, then we know z2∗−z2′+BID′c′−BID′c∗≠0. Because BID and BID′ have the same role in our scheme, the challenger C does not know which one is used in the simulation. Therefore, C can make z2∗−z2′+BIDc′−BIDc∗≠0 with probability not less than 0.5. Finally, we can construct an algorithm to solve the SISn,m,q,β problem with overwhelming probability, where β=22σ+dκm.


### 5.3. Comparisons

In this section, we compare our scheme with several typical self-certified authentication or signature schemes. We mainly focus on the computational costs, the storage overheads, and several security properties.As in Table1, we compare the computational costs. Let tbp, tbpm, teccm, tmul, and th denote the execution times of a bilinear pairing operation, a scale multiplication for the bilinear pairing, a scale multiplication for the ECC, a polynomial multiplication, and a general hash function operation. Although our scheme has higher computational costs, based on the lattice, our scheme provides more robust security.Table 1
The comparisons of computational costs.
SchemeSigning costVerify costLi et al.’s scheme [10]tbpm+th3tbp+thTahat et al.’s scheme [35]4teccm+3th2teccm+3thLi et al.’s scheme [8]7tmul+thtmul+thOur scheme4ntmul+th4ntmul+2thAs depicted in Table2, we compare the storage overheads. For the key size, we use an improved trapdoor generation algorithm [32] based on GPV [30] to reduce the dimensionality of the trapdoor. For the signature length, we only use Gaussian sampling in the key extract phase but use the rejection sampling technique in the signature generation phase, which helps to reduce the signature length. Moreover, according to Lemma 2 in [14], if the key is distributed as a discrete Gaussian distribution with the parameter σ such that x≤sm, the bit size of x is bounded by mlog2s bits.Table 2
The comparisons of storage overheads.
SchemePublic key sizePrivate key sizeSignature lengthLi et al. [10]G1G12G1Tahat et al. [35]2GG3GLi et al. [8]nlogq4nlogqnlogqOurnklogqmklog2s+mklog2d+12mlog12σIn Table3, we compare the security properties. According to the above tables, Li et al. [10] and Tahat et al.’s [35] schemes are more efficient than the SCS schemes over lattice, where G=320 bits and G1=1024 bits. However, their schemes are not secure against quantum attacks because the security is based on the pairing or elliptic curve discrete logarithm problems (ECDLP). Li et al.’s [8] scheme is the first SCS scheme over lattice. It has a shorter key size and signature length because of using NTRU lattice, but it lacks provable security. Our scheme is based on the standard lattice, so the key size and the signature length are less efficient than Li et al.’s scheme. However, our scheme is provably secure in the ROM under the SIS assumption. Therefore, our scheme is more secure against quantum computers.Table 3
The comparisons of security properties.
SchemeProvable securityAssumptionPostquantumLi et al. [10]YesBilinear pairingsNoTahat et al. [35]NoECDLPNoLi et al. [8]NoNTRU CVPYesOurYesLattice SISYes


## 5.1. Correctness

The correctness of the scheme is as follows:First, we haveAXID=U, BBID=PID, so(7)H2Az1+Bz2−PIDc−Uc,μ,=H2AXIDc+y1+BBIDc+y2−PIDc−Uc,μ,=H2AXIDc+Ay1+BBIDc+By2−PIDc−Uc,μ,=H2AXID−U+BBID−PIDc+Ay1+By2,μ,=H2Ay1+By2,μ,=c.At this moment, we complete the proof.


## 5.2. Security Analysis

Our scheme is existentially unforgeable under the adaptive chosen message attacks in the random oracle model.Theorem 1.
Our SCS scheme is existentially unforgeable in ROM for a polynomial-time type 1 adversary. If the adversary can successfully forge a valid signature, then it can solve theSISn,m,q,β problem, where β=22σ+sκm.Proof.
Assume that there is a type 1 adversaryA who can break the scheme with nonnegligible probability. Then, we can construct a polynomial-time challenger C, who runs A as a subroutine to solve the SISn,m,q,β problem with nonnegligible probability; that is, C wins Game 1:
Game 1 setup: input the security parametern. C runs the setup and the KeyGen algorithm to obtain Para=λ,n,q,m,d,k,κ,s,σ,H1,H2 and A,R. Then, C publishes Para and A and keeps R secret. C maintains several initially empty lists: List 0, List 1, List 2, List 3, and List 4. List 0 contains IDi,PID,U=H1A,PID,IDi, where IDi is the user’s identity and PID is the partial public key. List 1 contains IDi,BID,PID,U, where BID is the secret key. List 2 contains IDi,BID,PID,U,X, where X is the partial private key. List 3 contains μ,y1,y2,c=H2⋅, where y1,y2 are two random vectors. List 4 contains IDi,μ,z,c, where z,c is the signature.
Queries:A adaptively issues several queries to C:(i)
H1queries: A sends a user’s identity IDi to C; then, C performs as follows:(1)
First looks upIDi in List 0. If found, C directly returns the hash value U of the public key.(2)
Otherwise,C randomly selects a matrix U∈ℤqm×k and returns it; then, it selects a matrix PID∈ℤqm×k, and adds IDi,PID,U to List 0.(ii)
H2 queries: A sends a message μ to C; then, C performs as follows:(1)
First, it looks upμ in List 3. If found, C directly returns the hash value c of message μ.(2)
Otherwise,C randomly selects a vector c from c:c∈−1,0,1k,c1≤κ and returns it. Then, it randomly selects two vectors y1,y2←Dσm and adds μ,y1,y2,c to List 3.(iii)
Secret matrix queries:A sends an identity IDi to C; then, C performs as follows:(1)
First, it looks upIDi in List 1. If found, C directly returns the user’s secret matrix BID.(2)
Otherwise,C selects a matrix BID∈ℤm×k from −d,…,0,…,dm×k and returns it. Then, it computes PID=BBID, U=H1A,PID,IDi and adds IDi,BID,PID,U to List 1.(vi)
Partial private key queries:A sends IDi to C; then, C performs as follows:(1)
First, it looks upIDi in List 2. If found, C directly returns the partial private key X.(2)
Otherwise,C issues a secret matrix query to obtain BID,PID,U and runs the algorithm SampleMAT A,R,s,U to output a matrix X∈ℤm×k as the partial private key.(3)
Finally,C returns X and adds IDi,BID,PID,U,X to List 2.(v)
Public key replacement queries:A sends IDi and a public key PID∗ to C and then wants to replace the user’s public key. After receiving the identity IDi, C replaces the public key with PID∗ and records this replacement.(vi)
Sign queries:A sends a message μ, IDi, and a secret matrix BID to C. Then, C performs as follows:(1)
First, it looks up the parameters in List 4. If found,C directly returns the signature.(2)
Otherwise,C issues a partial private key query to obtain the signing key X,BID, issues a H2 query to obtain c, and computes z1=Xc+y1,z2=BIDc+y2.(3)
Finally,C returns the signature z,c, where z=z1t,z2tt, and adds IDi,μ,z,c to List 4.
Forgery: after polynomial-time queries finish,A outputs a forgery z∗,c∗ on message μ∗ for IDi with nonnegligible probability. If the signature can pass the verification and partial private key queries and the sign queries for the message μ∗ are never involved in this game, then A wins the game.
Using the forking lemma [34], C replays A with different hash values of H2 queries to get another valid signature z′,c′ such that c∗≠c′ and H2Az1∗+Bz2∗−PIDc∗−Uc∗,μ∗=H2Az1′+Bz2′−PIDc′−Uc′,μ∗.
BecauseA is a type 1 adversary that can make public key replacement attacks, it is easy to obtain PID and BID. Then, only the partial private key X needs to be considered. Since U=AX, we have the equality:(8)Az1∗−Uc∗=Az′1−Uc′,Az1∗−AXc∗=Az′1−AXc′,Az1∗−z1′+Xc′−Xc∗.
Asz1∗≤2σm, z1′≤2σm, Xc∗≤sκm, Xc′≤sκm with overwhelming probability, we can see that(9)z1∗−z1′+Xc′−Xc∗≤22σ+sκm.
Now, we provez1∗−z1′+Xc′−Xc∗≠0 with nonnegligible probability.
Sincem>64+nlogq/log12s, then, by Lemma 4.2 from [33], there is another X′ with probability larger than 1−2−100 such that all the columns except for the i th column are the same as X. And AX=AX′=U. So, if z1∗−z1′+Xc′−Xc∗=0, then we have z1∗−z1′+X′c′−X′c∗≠0. Because X and X′ have the same role in our scheme, C does not know which one is used in the simulation. Hence, C can make z1∗−z1′+Xc′−Xc∗≠0 with the probability not less than 0.5. As a result, we can construct an algorithm to solve the SISn,m,q,β problem with overwhelming probability, where β=22σ+sκm.Theorem 2.
Our SCS scheme is existentially unforgeable in ROM for a polynomial-time type 2 adversary. If the adversary can successfully forge a valid signature, then it can solve theSISn,m,q,β problem, where β=22σ+dκm.Proof.
Assume that there is a type 2 adversaryA that can break out the scheme with nonnegligible probability. Then, we can construct a polynomial-time challenger C that runs A as a subroutine to solve the SISn,m,q,β problem with nonnegligible probability, that is, C wins Game 2:
Game 2 Setup: input the security parametern. C runs the setup and KeyGen algorithm to obtain Para=λ,n,q,m,d,k,κ,s,σ,H1,H2 and A,R. Then, C publishes Para and A and keeps R secret. C maintains several initially empty lists: List 0, List 1, List 3, and List 4.
Queries:A adaptively issues several queries to C:(i)
H1 queries: it is the same as the above proof.(ii)
H2 queries: it is the same as the above proof.(iii)
Secret matrix queries:A sends a user’s identity IDi to C; then, C performs as follows:(1)
First, it looks upIDi in List 1. If found, C directly returns the user’s secret matrix BID.(2)
Otherwise,C randomly selects a matrix BID∈ℤm×k from −d,…,0,…,dm×k, returns it, then computes PID=BBID, U=H1A,PID,IDi, and adds IDi,BID,PID,U to List 1.(vi)
Sign queries:A sends IDi and a message μ to C; then, C performs as follows:(1)
First, it looks up the parameters in List 4. If found,C directly returns the signature.(2)
Otherwise,C issues a secret matrix query to obtain BID, issues a H1 query to obtain the public key, and then computes X. C also issues a H2 query to obtain c and computes z1=Xc+y1,z2=BIDc+y2.(3)
Finally,C returns the signature z,c, where z=z1t,z2tt, and adds IDi,μ,z,c to List 4.
Forgery: after polynomial-time queries finish,A outputs a forgery z∗,c∗ on message μ∗ for IDi with nonnegligible probability. If the signature can pass the verification, and the secret matrix queries and the sign queries for the message μ∗ are never involved in this game, then A wins the game.
Using the forking lemma,C replays A with different hash values of H2 queries to get another valid signature z′,c′ such that c∗≠c′ and H2Az1∗+Bz2∗−PIDc∗−Uc∗,μ∗=H2Az′1+Bz′2−PIDc′−Uc′,μ∗.
BecauseA is a type 2 adversary that can obtain the partial private key XID, only the secret key BID needs to be considered. Moreover, since PID=BBID, we have the equality(10)Bz2∗−PIDc∗=Bz′2−PIDc′,Bz2∗−BBIDc∗=Bz′2−BBIDc′,Bz2∗−z2′+BIDc′−BIDc∗=0.
Asz2∗≤2σm, z2′≤2σm, BIDc∗≤dκm, BIDc′≤dκm with overwhelming probability, we can see that(11)z2∗−z2′+BIDc′−BIDc∗≤22σ+dκm.
Now, we provez2∗−z2′+BIDc′−BIDc∗≠0 with nonnegligible probability.
Sincem>64+nlogq/log2d+1 and according to Lemma 4.2 from [33], there is another secret key BID′ with the probability larger than 1−2−100 such that all columns except for the i th column are the same as BID. And PID=BB′ID=BBID. So, if z2∗−z2′+BIDc′−BIDc∗=0, then we know z2∗−z2′+BID′c′−BID′c∗≠0. Because BID and BID′ have the same role in our scheme, the challenger C does not know which one is used in the simulation. Therefore, C can make z2∗−z2′+BIDc′−BIDc∗≠0 with probability not less than 0.5. Finally, we can construct an algorithm to solve the SISn,m,q,β problem with overwhelming probability, where β=22σ+dκm.


## 5.3. Comparisons

In this section, we compare our scheme with several typical self-certified authentication or signature schemes. We mainly focus on the computational costs, the storage overheads, and several security properties.As in Table1, we compare the computational costs. Let tbp, tbpm, teccm, tmul, and th denote the execution times of a bilinear pairing operation, a scale multiplication for the bilinear pairing, a scale multiplication for the ECC, a polynomial multiplication, and a general hash function operation. Although our scheme has higher computational costs, based on the lattice, our scheme provides more robust security.Table 1
The comparisons of computational costs.
SchemeSigning costVerify costLi et al.’s scheme [10]tbpm+th3tbp+thTahat et al.’s scheme [35]4teccm+3th2teccm+3thLi et al.’s scheme [8]7tmul+thtmul+thOur scheme4ntmul+th4ntmul+2thAs depicted in Table2, we compare the storage overheads. For the key size, we use an improved trapdoor generation algorithm [32] based on GPV [30] to reduce the dimensionality of the trapdoor. For the signature length, we only use Gaussian sampling in the key extract phase but use the rejection sampling technique in the signature generation phase, which helps to reduce the signature length. Moreover, according to Lemma 2 in [14], if the key is distributed as a discrete Gaussian distribution with the parameter σ such that x≤sm, the bit size of x is bounded by mlog2s bits.Table 2
The comparisons of storage overheads.
SchemePublic key sizePrivate key sizeSignature lengthLi et al. [10]G1G12G1Tahat et al. [35]2GG3GLi et al. [8]nlogq4nlogqnlogqOurnklogqmklog2s+mklog2d+12mlog12σIn Table3, we compare the security properties. According to the above tables, Li et al. [10] and Tahat et al.’s [35] schemes are more efficient than the SCS schemes over lattice, where G=320 bits and G1=1024 bits. However, their schemes are not secure against quantum attacks because the security is based on the pairing or elliptic curve discrete logarithm problems (ECDLP). Li et al.’s [8] scheme is the first SCS scheme over lattice. It has a shorter key size and signature length because of using NTRU lattice, but it lacks provable security. Our scheme is based on the standard lattice, so the key size and the signature length are less efficient than Li et al.’s scheme. However, our scheme is provably secure in the ROM under the SIS assumption. Therefore, our scheme is more secure against quantum computers.Table 3
The comparisons of security properties.
SchemeProvable securityAssumptionPostquantumLi et al. [10]YesBilinear pairingsNoTahat et al. [35]NoECDLPNoLi et al. [8]NoNTRU CVPYesOurYesLattice SISYes


## 6. Conclusion and Further Work

In this paper, we propose a self-certified signature scheme over the standard lattice, which authenticates the integrity of the message and the user’s public key and identity without the need for additional certificates, thus not only avoiding the key escrow problems and public key replacement attacks but also preventing quantum attacks. Based on the hardness of the SIS assumption, our scheme is provably secure in the random oracle model. Our scheme is more feasible than previous schemes.Future work: we consider the standard model. The standard model is more secure and practical than the random oracle model. Hence, our further work is to transfer our scheme into a SCS scheme in the standard model. Furthermore, the efficiency of the scheme can be further improved.



---

*Source: 2459628-2021-12-31.xml*