# ID-Based Strong Designated Verifier Signature overR-SIS Assumption

Authors: Jie Cai; Han Jiang; Pingyuan Zhang; Zhihua Zheng; Hao Wang; Guangshi Lü; Qiuliang Xu
Journal: Security and Communication Networks
 (2019)

---

## Abstract

In this paper, we propose an ID-based strong designated verifier signature (SDVS) overR-SIS assumption in the random model. We remove pre-image sampling function and Bonsai trees such complex structures used in previous lattice-based SDVS schemes. We only utilize simple rejection sampling to protect the security of our scheme. Hence, we will show our design has the shortest signature size comparing with existing lattice-based ID-based SDVS schemes. In addition, our scheme satisfies anonymity (privacy of signer’s identity) proved in existing schemes rarely, and it can resist side-channel attacks with uniform sampling.


---

## Body

## 1. Introduction

The first designated verifier signature scheme was proposed by Jakobsson, Sako, and Impagliazzo [1] in 1996. This signature scheme satisfies that only the designated verifier can verify correctness of generated signatures and he can’t convince others to believe in the validity of these signatures. The main reason for satisfying this property is that the designated verifier can generate an indistinguishable transcript from the real signatures. In [1], they also provided a notion of strong designated verifier signature (SDVS) to resist an online eavesdropper’s attack. In a SDVS, anyone can create an identical transcript which is indistinguishable from real signatures. Generally speaking, a SDVS needs to satisfy unforgeability and untransferability which were provided by Saeednia, Kremer, and Markowitch in [2] formally. In [3], Laguillaumie and Vergnaud added a property, that is, privacy of signer’s identity (anonymity), which means any adversary can’t distinguish Alice’s signature for Bob from Cindy’s signature for Bob without Bob’s secret key.An advantage of identity-based scheme is that the verifier doesn’t need to generate his public key setup before receiving authenticated message from signer. In [4], Susilo, Zhang, and Mu first introduced the notion of identity-based SDVS (ID-based SDVS). They gave an efficiently generic construction of such schemes which were based on bilinear Diffie-Hellman assumption.


## 2. Related Work

### 2.1. Classical ID-Based SDVS Schemes

Several classical ID-based SDVS have been provided since the first general construction is introduced in [4]. In [5], Huang et al. proposed a short ID-based SDVS based on bilinear pairing. Their contributions of paper are not merely their shorter signature size, but having two security proofs in random model and in standard model. In addition, the scheme of [5] has anonymity compared with [4]. Recently, Blazy et al. provided an ID-based SDVS [6] under CDH assumption in the standard model.However, classical ID-based SDVS schemes can’t resist against quantum adversaries. Hence, people try to design postquantum ID-based SDVS schemes. With the collection of postquantum algorithms by NIST, lattice-based cryptography is widely studied.


### 2.2. Lattice-Based ID-Based SDVS Schemes

As far as we know, there are two main postquantum schemes both based on lattice hard problems. The first lattice-based ID-based SDVS was proposed by Noh et al. [7]. They used pre-image sampling function and Bonsai trees (see [8]) with large parameters to protect the security. Soon Wang et al. proposed a more efficient scheme [9]. The security of this scheme was based on the hardness of LWE and its unforgeability can be reduced to SIS problem in the random model. At the same time, they showed the signature size (3mlog⁡q) is shorter than any other already existing SDVS scheme.However, above schemes that used Gaussian sampling are unusual to resist side-channel attack [10–12], and the authors only gave the proofs of unforgeability and untransferability without anonymity.


### 2.3. Our Contribution

In this paper, we propose an efficient ID-based SDVS based on SIS problem over ring in the random model, and our design has advantages as follows:(1)
Shorter signature size and lower rejection time. The signature size of our scheme approximately equals 2mlog⁡q+m. Since q≫2 holds in practical application, it is easy to see our result is better than 3mlog⁡q [9]. The main reason for this is that we don’t utilize pre-image sampling function and Bonsai trees such complex structures. Then we needn’t choose too large parameters to protect the existence and security of scheme. About efficiency, we use filtering technique (see [13]) to make the rejection 1.28 lower than others.(2)
Resisting side-channel attacks. The common methods of existing sampling over lattice-based signature are Gaussian sampling (see [14–16]) and uniform sampling (see [13, 17, 18]). It has been proved that these schemes with Gaussian sampling lead to side-channel attacks easily [10–12]. Hence we choose uniform sampling to resist them efficiently.(3)
Satisfying anonymity. Although anonymity was introduced in [3] long ago, being proved in existing schemes is very rare indeed. Our scheme satisfies three properties of unforgeability, untransferability, and anonymity. In addition, anonymity can be reduced to solving SIS problem.Organization of the Paper. We will show the basic notations, relative lattice hard problem assumption and rejection sampling used in our scheme, and detailed definitions of ID-based SDVS and security model in Section 3. Then we propose our ID-based SDVS scheme in detail in Section 4. In Section 5, we provide the proof of security. In Section 6, we present the relationship of our parameters to ensure the existence and security of our scheme. Finally, we give a conclusion and further work in Section 7. Data availability, conflicts of interest, and funding statement can be seen in the last three sections, respectively.


## 2.1. Classical ID-Based SDVS Schemes

Several classical ID-based SDVS have been provided since the first general construction is introduced in [4]. In [5], Huang et al. proposed a short ID-based SDVS based on bilinear pairing. Their contributions of paper are not merely their shorter signature size, but having two security proofs in random model and in standard model. In addition, the scheme of [5] has anonymity compared with [4]. Recently, Blazy et al. provided an ID-based SDVS [6] under CDH assumption in the standard model.However, classical ID-based SDVS schemes can’t resist against quantum adversaries. Hence, people try to design postquantum ID-based SDVS schemes. With the collection of postquantum algorithms by NIST, lattice-based cryptography is widely studied.


## 2.2. Lattice-Based ID-Based SDVS Schemes

As far as we know, there are two main postquantum schemes both based on lattice hard problems. The first lattice-based ID-based SDVS was proposed by Noh et al. [7]. They used pre-image sampling function and Bonsai trees (see [8]) with large parameters to protect the security. Soon Wang et al. proposed a more efficient scheme [9]. The security of this scheme was based on the hardness of LWE and its unforgeability can be reduced to SIS problem in the random model. At the same time, they showed the signature size (3mlog⁡q) is shorter than any other already existing SDVS scheme.However, above schemes that used Gaussian sampling are unusual to resist side-channel attack [10–12], and the authors only gave the proofs of unforgeability and untransferability without anonymity.


## 2.3. Our Contribution

In this paper, we propose an efficient ID-based SDVS based on SIS problem over ring in the random model, and our design has advantages as follows:(1)
Shorter signature size and lower rejection time. The signature size of our scheme approximately equals 2mlog⁡q+m. Since q≫2 holds in practical application, it is easy to see our result is better than 3mlog⁡q [9]. The main reason for this is that we don’t utilize pre-image sampling function and Bonsai trees such complex structures. Then we needn’t choose too large parameters to protect the existence and security of scheme. About efficiency, we use filtering technique (see [13]) to make the rejection 1.28 lower than others.(2)
Resisting side-channel attacks. The common methods of existing sampling over lattice-based signature are Gaussian sampling (see [14–16]) and uniform sampling (see [13, 17, 18]). It has been proved that these schemes with Gaussian sampling lead to side-channel attacks easily [10–12]. Hence we choose uniform sampling to resist them efficiently.(3)
Satisfying anonymity. Although anonymity was introduced in [3] long ago, being proved in existing schemes is very rare indeed. Our scheme satisfies three properties of unforgeability, untransferability, and anonymity. In addition, anonymity can be reduced to solving SIS problem.Organization of the Paper. We will show the basic notations, relative lattice hard problem assumption and rejection sampling used in our scheme, and detailed definitions of ID-based SDVS and security model in Section 3. Then we propose our ID-based SDVS scheme in detail in Section 4. In Section 5, we provide the proof of security. In Section 6, we present the relationship of our parameters to ensure the existence and security of our scheme. Finally, we give a conclusion and further work in Section 7. Data availability, conflicts of interest, and funding statement can be seen in the last three sections, respectively.


## 3. Preliminaries

### 3.1. Notations

We note ringRq=Zq[x]/(xn+1), where q is a prime number and n is a power of 2 positive number. The bold small (capital) letters are vectors (matrices), and the normal letters are integers or real. The lp norm of a vector x is denoted by xp(p=1,2,∞). Dγ means a uniform distribution in which an element x←$Rq is chosen randomly such that x∞≤γ. An invertible element in distribution Dγ is represented by x-1. An element in Rqn×m is X=x1…xm,m≥nlog⁡q. We note h:0,1∗→r:r∈-1,0,1m,r1≤ι is a hash function. Function H maps 0,1∗ to Rqm×m, which is derived by using AES128-ECB [19, 20].


### 3.2. Rejection Sampling

In previous part of our paper, we have shown that using Gaussian sampling can cause serious side-channel attack; then we just provide uniform sampling in this part.The method of uniform sampling is usually called filtering technique [17, 18]. Its core idea is the signer needs to output a secure signature by choosing its proper range, and its main aim is making such a good output uniform to protect his secret key. In [13], Rückert provided a form over polynomial rings.Lemma 1 (see [13]).
Given two setsS1=a∈Zm∣a∞≤A and S2=b∈Zm∣b∞≤B,B≥ΦmA,Φ∈N+, and if given any a∈S1, b←$S2, then we have Pra-b∞≤B-A>e-1/Φ-o(1).Usually,a contains information of secret key and signature form is a-b. According to above lemma, we can see that the output a-b is indistinguishable with uniform distribution if and only if it is constrained in the range B-A. Further, if the signature is in this range, a doesn’t leak any information about the secret key.More importantly, this lemma tells us that the signature size is dependent on three parametersΦ,m, and A. In principle, the smaller these chosen parameters, the better. Unfortunately, a smaller value of Φ can cause a larger rejection time (≈e1/Φ); hence we must find a tradeoff for it. In our scheme, the chosen parameter A (replaced by υ) is smaller than any other existing ones, which makes our signature size the shortest.


### 3.3. Lattice Assumption

There are two important average-case problems, SIS and LWE, in lattices which can be reduced to the worst-case problems GapSVP and SIVP [21, 22]. A formal form of SIS problem is always denoted l2-SISq,n,m,β. Here we list its form over ring, which is at least as hard as worst-case problem SVPΓ on ideal lattices (see [23]).Definition 2 (see [14]).
LetR be some ring and K be some distribution over Rqn×m, where Rq is the quotient ring R/(qR). Given a random matrix A∈Rqn×m following the distribution K, find a nonzero vector v∈Rqm such that Av=0 and v2≤β(0<β≤q·poly(n)), which is denoted R-SISq,n,m,βK problem.Compared with SIS,R-SIS is more compact and more efficient. In order to ensure existing of a sufficiently short solution, the dimension m in R-SIS is approximate log⁡q instead of nlog⁡q in SIS problem. Furthermore, one can compute Av in quasilinear time with fast Fourier transform (FFT).Besides,R-SIS and its associated cryptographic functions also can be proved at least as hard as certain lattice (called ideal lattice over ring R) problems in the worst case. In [23], Peikert and Rosen provided that R-SIS is at least as hard as worst-case SVPΓ(Γ=Olog⁡n) on ideal lattice in R, where R=OK is the ring of algebraic integers in any number field K. Particularly, the fastest time in known (quantum) algorithms to solve SISΓ problem on ideal lattice is exponential 2Ω(n). Indeed, now it seems that the additional algebraic structure of ideal lattices does not bring any advantages to solving this problem.


### 3.4. An Equivalent Construction of Random MatrixA

Since our design has many matrix multiplications, we need to find an equivalent square matrix to satisfy their multiplicability. Moreover, in [16], Lyubashevsky showed that if m≥2n, there are n linearly independent columns in a random matrix A∈Rqn×m with probability e-Ω(n), when q is a prime of size bigger than 2m.In order to construct an efficient lattice-based SDVS scheme, we have introduced this idea in [24], so we provide it in brief here.Lemma 3.
IfA1∈Rqn×m, m=2n, X1∈Rqm×m satisfies A1X1=0mod⁡q, then we construct a new matrix(1)A=A1n×m0n×m∈Rqm×m, and we have AX=0mod⁡q, where X=X1.Proof.
According to the multiplicability of the partitioned matrix, we can compute the below equation,(2)AX=A1n×mX1m×m0n×mX1m×m=0mod⁡q.This lemma shows that such a square matrix has two advantages for our scheme as follows:(i)
Don’t change the security. Notice that the new square matrixA has the same solution as the common form A1∈Rqn×m based on SIS assumption. Hence, they have equivalent security.(ii)
Don’t change the efficiency. Although the dimension of matrix is increased, it doesn’t cause extra computation by filling zero matrix in original one.


### 3.5. Definitions of ID-Based SDVS

An ID-based SDVS scheme contains five polynomial time algorithms (Setup, Extract, Sign, Verf, and Sim) between two participants Alice (signer) and Bob (designated verifier). Every participant has his identityIDA(IDB). Generally, there exists a private key generator (PKG) to provide a secret key SIDA(SIDB) for each participant during an extract algorithm. The detailed descriptions of these algorithms are shown as follows.Definition 4.
Given a security parameterλ=poly(n), an ID-based SDVS is defined by algorithms:(1)
Setup: It is a probabilistic algorithm inputting the security parameter λ and outputting system parameters (sp) and master key (mk). That is, (3)sp,mk←Setupλ.(2)
Extract: It is a deterministic (probabilistic) algorithm inputting sp,mk, and participant’s identity IDi∈0,1∗ and outputting relative secret key SIDi. Actually, the identity IDi is often considered public key of participant, and IDA(IDB) belongs to Alice (Bob) in two-party schemes. Specifically, (4)SIDi←Extractsp,mk,IDi.(3)
Sign: It is a deterministic (probabilistic) algorithm inputting signer’s secret key SIDA, designated verifier’s public key IDB, and message μ. Then it outputs a signature σ.(5)σ←SignSIDA,IDB,μ.(4)
Verf: It is a deterministic algorithm inputting message μ and relatively received signature σ from signer Alice, SIDB and IDA. The designated verifier Bob verifies whether the following equation is correct or not: (6)True,⊥←VerfSIDB,IDA,μ,σ(5)
Sim: It is a probabilistic algorithm inputting a quadruple (SIDB,IDA,IDB,μ). Anyone can generate an indistinguishable signatures generated by the triple (SIDA,IDB,μ).Security Model  (1)
Correctness: For all valid Sign (SIDA,IDB,μ), the designated verifier always gets the following result: (7)VerfSIDB,IDA,μ,SignSIDA,IDB,μ=True. (2)
Unforgeability: We provide a game between a PPT adversary A and a challenger C to define existential unforgeability against adaptive chosen message attack (EUF-CMA). In addition, we denote that IDi and IDj are signer and designated verifier ID, respectively.
(i)
Setup. The challenger C runs the following algorithm to generate sp and mk. (8)sp,mk←Setupλ. (ii)
Extraction queries. The adversary A can query the secret key of signer with IDi. Then C runs Extract (sp,mk,IDi) to answer him. That is, A can get SIDi. (iii)
Sign queries. When A obtains SIDi, he queries a signature σ with message μ and designated verifier IDj. Then C answers him with a correct signature by algorithm Sign (SIDi,IDj,μ). (iv)
Output. At the end of this game, the adversary A is able to generate a new signature σ∗ with message μ∗, IDi∗ and IDj∗ satisfying necessary conditions:
(1)
I D i ∗ and IDj∗ have never been requested inExtraction queries step. (2)
Messageμ∗ related with IDi∗ and IDj∗ has never been requested inSign queries step. (3)
The signatureσ∗ with message μ∗, IDi∗ and IDj∗ is valid. Then, we provide a formal security description of EUF-CMA. We say the ID-based SDVS scheme is(t,ϵ) EUF-CMA secure, if the following probability is negligible for any PPT adversary A runs above game in time t.(9)PrVerfIDi∗,IDj∗,μ∗,σ∗=True≤ϵ, whereϵ>0 is a negligible function of secure parameter λ. (3)
Untransferability: This property simply means that any PPT adversary A can’t distinguish the real signature and simulated one in below game between A and challenger C.
(i)
Setup. The challenger C runs algorithm Setup(λ) to generate sp and mk. (ii)
Sign and Verf queries. The PPT adversary A queries for Sign and Verf queries adaptively for chosen message μi. The challenger C answers him by running algorithms Sign(SIDA,IDB,μi) and Verf(SIDB,IDA,μi,σi). Notice that the identities of two participants are fixed and the parameter i is form 1 to qs=poly(n) in this step. (iii)
Challenge. After qs signing and verifying queries, A chooses a new massage μ∗ to query C. C tosses a coin randomly and chooses b←$0,1. When b=0, he runs σ∗←Sign(SIDA,IDB,μ∗) correctly; otherwise he runs σ∗←Sim(SIDB,IDA,IDB,μ∗) to answer adversary’s request. (iv)
Output. At the end of this game, the adversary A outputs b′∈0,1. If b=b′ holds, the adversary succeeds in the game. Formally, for any PPT adversary, he has a correct guess afterqs quests in t time with negligible probability; then we say this ID-based SDVS is (t,qs) untansferable. That is, (10)Prb=b′-12<ϵ. (4)
Anonymity: To be accurate, any adversary can’t distinguish the real signer’s identity form given IDA0 and IDA1 for a designated verifier’s identity IDB. It is similar with witness indistinguishable property actually. The detailed description of game is shown as follows.
(i)
Setup. The challenger C runs algorithm Setup(λ) to generate sp and mk. (ii)
Extraction queries. The adversary A can query the secret key of signer with IDi. Then C runs Extract (sp,mk,IDi) to answer him. (iii)
Sign and Verf queries. A queries the signature with message μ for the signer IDi and designated verifier IDj. Then C outputs a signature σ and returns True or ⊥ if A inputs (μ,σ). (iv)
Challenge. The adversary A outputs a message μ∗ with signer’s possible identities IDA0, IDA1 and designated verifier’s identity IDB to challenger C satisfying necessary conditions:
(1)
I D A 0, IDA1, and IDB have never been requested inExtraction queries step. (2)
Messageμ∗ (or pair (μ∗,σ∗)) has never been requested inSign and Verf queries step with IDA0, IDA1, and IDB. After receivingμ∗, C tosses a coin randomly, chooses b←$0,1, and computes Sign (SIDAb,IDB,μ∗) returned to A. (v)
Output. At the end of this game, the adversary A outputs b′∈0,1. If b=b′ holds, the adversary succeeds in the game. Hence, for any PPT adversary, he has a correct guess afterqs quests in t time with negligible probability; then we say this ID-based SDVS satisfies property of (t,qs) privacy of signer’s identity. That is, (11)Prb=b′-12<ϵ.


## 3.1. Notations

We note ringRq=Zq[x]/(xn+1), where q is a prime number and n is a power of 2 positive number. The bold small (capital) letters are vectors (matrices), and the normal letters are integers or real. The lp norm of a vector x is denoted by xp(p=1,2,∞). Dγ means a uniform distribution in which an element x←$Rq is chosen randomly such that x∞≤γ. An invertible element in distribution Dγ is represented by x-1. An element in Rqn×m is X=x1…xm,m≥nlog⁡q. We note h:0,1∗→r:r∈-1,0,1m,r1≤ι is a hash function. Function H maps 0,1∗ to Rqm×m, which is derived by using AES128-ECB [19, 20].


## 3.2. Rejection Sampling

In previous part of our paper, we have shown that using Gaussian sampling can cause serious side-channel attack; then we just provide uniform sampling in this part.The method of uniform sampling is usually called filtering technique [17, 18]. Its core idea is the signer needs to output a secure signature by choosing its proper range, and its main aim is making such a good output uniform to protect his secret key. In [13], Rückert provided a form over polynomial rings.Lemma 1 (see [13]).
Given two setsS1=a∈Zm∣a∞≤A and S2=b∈Zm∣b∞≤B,B≥ΦmA,Φ∈N+, and if given any a∈S1, b←$S2, then we have Pra-b∞≤B-A>e-1/Φ-o(1).Usually,a contains information of secret key and signature form is a-b. According to above lemma, we can see that the output a-b is indistinguishable with uniform distribution if and only if it is constrained in the range B-A. Further, if the signature is in this range, a doesn’t leak any information about the secret key.More importantly, this lemma tells us that the signature size is dependent on three parametersΦ,m, and A. In principle, the smaller these chosen parameters, the better. Unfortunately, a smaller value of Φ can cause a larger rejection time (≈e1/Φ); hence we must find a tradeoff for it. In our scheme, the chosen parameter A (replaced by υ) is smaller than any other existing ones, which makes our signature size the shortest.


## 3.3. Lattice Assumption

There are two important average-case problems, SIS and LWE, in lattices which can be reduced to the worst-case problems GapSVP and SIVP [21, 22]. A formal form of SIS problem is always denoted l2-SISq,n,m,β. Here we list its form over ring, which is at least as hard as worst-case problem SVPΓ on ideal lattices (see [23]).Definition 2 (see [14]).
LetR be some ring and K be some distribution over Rqn×m, where Rq is the quotient ring R/(qR). Given a random matrix A∈Rqn×m following the distribution K, find a nonzero vector v∈Rqm such that Av=0 and v2≤β(0<β≤q·poly(n)), which is denoted R-SISq,n,m,βK problem.Compared with SIS,R-SIS is more compact and more efficient. In order to ensure existing of a sufficiently short solution, the dimension m in R-SIS is approximate log⁡q instead of nlog⁡q in SIS problem. Furthermore, one can compute Av in quasilinear time with fast Fourier transform (FFT).Besides,R-SIS and its associated cryptographic functions also can be proved at least as hard as certain lattice (called ideal lattice over ring R) problems in the worst case. In [23], Peikert and Rosen provided that R-SIS is at least as hard as worst-case SVPΓ(Γ=Olog⁡n) on ideal lattice in R, where R=OK is the ring of algebraic integers in any number field K. Particularly, the fastest time in known (quantum) algorithms to solve SISΓ problem on ideal lattice is exponential 2Ω(n). Indeed, now it seems that the additional algebraic structure of ideal lattices does not bring any advantages to solving this problem.


## 3.4. An Equivalent Construction of Random MatrixA

Since our design has many matrix multiplications, we need to find an equivalent square matrix to satisfy their multiplicability. Moreover, in [16], Lyubashevsky showed that if m≥2n, there are n linearly independent columns in a random matrix A∈Rqn×m with probability e-Ω(n), when q is a prime of size bigger than 2m.In order to construct an efficient lattice-based SDVS scheme, we have introduced this idea in [24], so we provide it in brief here.Lemma 3.
IfA1∈Rqn×m, m=2n, X1∈Rqm×m satisfies A1X1=0mod⁡q, then we construct a new matrix(1)A=A1n×m0n×m∈Rqm×m, and we have AX=0mod⁡q, where X=X1.Proof.
According to the multiplicability of the partitioned matrix, we can compute the below equation,(2)AX=A1n×mX1m×m0n×mX1m×m=0mod⁡q.This lemma shows that such a square matrix has two advantages for our scheme as follows:(i)
Don’t change the security. Notice that the new square matrixA has the same solution as the common form A1∈Rqn×m based on SIS assumption. Hence, they have equivalent security.(ii)
Don’t change the efficiency. Although the dimension of matrix is increased, it doesn’t cause extra computation by filling zero matrix in original one.


## 3.5. Definitions of ID-Based SDVS

An ID-based SDVS scheme contains five polynomial time algorithms (Setup, Extract, Sign, Verf, and Sim) between two participants Alice (signer) and Bob (designated verifier). Every participant has his identityIDA(IDB). Generally, there exists a private key generator (PKG) to provide a secret key SIDA(SIDB) for each participant during an extract algorithm. The detailed descriptions of these algorithms are shown as follows.Definition 4.
Given a security parameterλ=poly(n), an ID-based SDVS is defined by algorithms:(1)
Setup: It is a probabilistic algorithm inputting the security parameter λ and outputting system parameters (sp) and master key (mk). That is, (3)sp,mk←Setupλ.(2)
Extract: It is a deterministic (probabilistic) algorithm inputting sp,mk, and participant’s identity IDi∈0,1∗ and outputting relative secret key SIDi. Actually, the identity IDi is often considered public key of participant, and IDA(IDB) belongs to Alice (Bob) in two-party schemes. Specifically, (4)SIDi←Extractsp,mk,IDi.(3)
Sign: It is a deterministic (probabilistic) algorithm inputting signer’s secret key SIDA, designated verifier’s public key IDB, and message μ. Then it outputs a signature σ.(5)σ←SignSIDA,IDB,μ.(4)
Verf: It is a deterministic algorithm inputting message μ and relatively received signature σ from signer Alice, SIDB and IDA. The designated verifier Bob verifies whether the following equation is correct or not: (6)True,⊥←VerfSIDB,IDA,μ,σ(5)
Sim: It is a probabilistic algorithm inputting a quadruple (SIDB,IDA,IDB,μ). Anyone can generate an indistinguishable signatures generated by the triple (SIDA,IDB,μ).Security Model  (1)
Correctness: For all valid Sign (SIDA,IDB,μ), the designated verifier always gets the following result: (7)VerfSIDB,IDA,μ,SignSIDA,IDB,μ=True. (2)
Unforgeability: We provide a game between a PPT adversary A and a challenger C to define existential unforgeability against adaptive chosen message attack (EUF-CMA). In addition, we denote that IDi and IDj are signer and designated verifier ID, respectively.
(i)
Setup. The challenger C runs the following algorithm to generate sp and mk. (8)sp,mk←Setupλ. (ii)
Extraction queries. The adversary A can query the secret key of signer with IDi. Then C runs Extract (sp,mk,IDi) to answer him. That is, A can get SIDi. (iii)
Sign queries. When A obtains SIDi, he queries a signature σ with message μ and designated verifier IDj. Then C answers him with a correct signature by algorithm Sign (SIDi,IDj,μ). (iv)
Output. At the end of this game, the adversary A is able to generate a new signature σ∗ with message μ∗, IDi∗ and IDj∗ satisfying necessary conditions:
(1)
I D i ∗ and IDj∗ have never been requested inExtraction queries step. (2)
Messageμ∗ related with IDi∗ and IDj∗ has never been requested inSign queries step. (3)
The signatureσ∗ with message μ∗, IDi∗ and IDj∗ is valid. Then, we provide a formal security description of EUF-CMA. We say the ID-based SDVS scheme is(t,ϵ) EUF-CMA secure, if the following probability is negligible for any PPT adversary A runs above game in time t.(9)PrVerfIDi∗,IDj∗,μ∗,σ∗=True≤ϵ, whereϵ>0 is a negligible function of secure parameter λ. (3)
Untransferability: This property simply means that any PPT adversary A can’t distinguish the real signature and simulated one in below game between A and challenger C.
(i)
Setup. The challenger C runs algorithm Setup(λ) to generate sp and mk. (ii)
Sign and Verf queries. The PPT adversary A queries for Sign and Verf queries adaptively for chosen message μi. The challenger C answers him by running algorithms Sign(SIDA,IDB,μi) and Verf(SIDB,IDA,μi,σi). Notice that the identities of two participants are fixed and the parameter i is form 1 to qs=poly(n) in this step. (iii)
Challenge. After qs signing and verifying queries, A chooses a new massage μ∗ to query C. C tosses a coin randomly and chooses b←$0,1. When b=0, he runs σ∗←Sign(SIDA,IDB,μ∗) correctly; otherwise he runs σ∗←Sim(SIDB,IDA,IDB,μ∗) to answer adversary’s request. (iv)
Output. At the end of this game, the adversary A outputs b′∈0,1. If b=b′ holds, the adversary succeeds in the game. Formally, for any PPT adversary, he has a correct guess afterqs quests in t time with negligible probability; then we say this ID-based SDVS is (t,qs) untansferable. That is, (10)Prb=b′-12<ϵ. (4)
Anonymity: To be accurate, any adversary can’t distinguish the real signer’s identity form given IDA0 and IDA1 for a designated verifier’s identity IDB. It is similar with witness indistinguishable property actually. The detailed description of game is shown as follows.
(i)
Setup. The challenger C runs algorithm Setup(λ) to generate sp and mk. (ii)
Extraction queries. The adversary A can query the secret key of signer with IDi. Then C runs Extract (sp,mk,IDi) to answer him. (iii)
Sign and Verf queries. A queries the signature with message μ for the signer IDi and designated verifier IDj. Then C outputs a signature σ and returns True or ⊥ if A inputs (μ,σ). (iv)
Challenge. The adversary A outputs a message μ∗ with signer’s possible identities IDA0, IDA1 and designated verifier’s identity IDB to challenger C satisfying necessary conditions:
(1)
I D A 0, IDA1, and IDB have never been requested inExtraction queries step. (2)
Messageμ∗ (or pair (μ∗,σ∗)) has never been requested inSign and Verf queries step with IDA0, IDA1, and IDB. After receivingμ∗, C tosses a coin randomly, chooses b←$0,1, and computes Sign (SIDAb,IDB,μ∗) returned to A. (v)
Output. At the end of this game, the adversary A outputs b′∈0,1. If b=b′ holds, the adversary succeeds in the game. Hence, for any PPT adversary, he has a correct guess afterqs quests in t time with negligible probability; then we say this ID-based SDVS satisfies property of (t,qs) privacy of signer’s identity. That is, (11)Prb=b′-12<ϵ.


## 4. Our ID-Based SDVS Scheme

In this part, we will provide our detailed construction. Then we get an efficient ID-based SDVS scheme overR-SIS assumption. Always we assume Alice is the signer and Bob is designated verifier.


### 4.1. Setup

Letn be the rank of lattice, and PKG chooses A←$Rqm×m. There is a low norm solution of R-SIS problem X∈Rqm×m such that AX=0mod⁡q. We can see X is indeed the mk.


### 4.2. Extract

LetH:0,1∗→Rqm×m generated by using AES128-ECB [19, 20] be a mapping and h:0,1∗→r:r∈-1,0,1m,r1≤ι be a hash function. In addition, we denote IDA (IDB) is Alice’s (Bob’s) identity. Then, PKG computes H(IDi)=Hi(i=A,B) to be seen as the participant’s public key. Since Hi∈Rqm×m, X∈Rqm×m, PKG can generate the secret keys by computing X·HA=SAmod⁡q and HB·X=SBmod⁡q. Simply speaking,(12)Si←Extractn,H,X,IDii=A,B.


### 4.3. Sign

Alice executes the following steps to sign a signature for messageμ.(1)
t←$Dγ(γ<q)(2)
ift is not reversible, then go to step (1).(3)
k←$Dγ(4)
c=HB·kmod⁡q(5)
r=h(c,μ)(6)
z=SA·r+k·t-1(7)
ifz∞≥γ-υ or SA·r∞≥υ, then go to step (3).(8)
output signature(r,z,t) of message μ.Notice that there are two loop conditions in step (1) and step (7). Thus, it is necessary for us to evaluate their efficiencies.(i)
About step (1). In [25], Hoffstein et al. proposed a method to search an invertible polynomial t within 48.9 ms. Their instance is that t satisfies t1≤40 in a trinary polynomial set T(206,205), where 206 and 205 are numbers of positive coefficients and negative coefficients, respectively. Since such an invertible t is contained in set Dγ, we can also find it in 48.9 ms.(ii)
About step (7). This step is the key to compute the repetition using filtering technique (see [13]). In order to utilize their result, we require that the inequation mΦυ≤γ must be satisfied. Hence we get the repetition is approximately e1/Φ. Obviously, we can see that e1/Φ is a monotonically decreasing function with variable Φ∈N+, and the bigger value of Φ seemingly is better. However, two of composition parts of signature are z and t, and their size is mlog⁡(γ-υ)+mlog⁡γ which is positively correlated with parameter Φ. Hence, choosing bigger Φ is not wise. Then we get the optimal solution Φ=4 by observing the following expression, (13)Φ=min0.75≤e-1/Φ′≤1⁡Φ′,where1≤Prz∞≤γ-υ=e-1/Φ′≤0.75. Furthermore, the repetition is e1/Φ≈1.28.


### 4.4. Verf

When receiving signatureσ=(r,z,t) from signer Alice, Bob verifies whether the following equation is correct or not:(1)
h(c,μ)=h(HBzt-SBHArtmod⁡q,μ)(2)
z∞≤γ-υ


### 4.5. Sim

If one gets a quadruple(SB,IDA,IDB,μ), he chooses two random elements z′ (z′∞≥γ-υ) and r′ to compute z′t-1=z and r′t-1=z. Hence, he can also compute the following equation, (14)HBzt-SBHArt=c=HBz′-SBHAr′,which is an indistinguishable signature with Alice’s.


## 4.1. Setup

Letn be the rank of lattice, and PKG chooses A←$Rqm×m. There is a low norm solution of R-SIS problem X∈Rqm×m such that AX=0mod⁡q. We can see X is indeed the mk.


## 4.2. Extract

LetH:0,1∗→Rqm×m generated by using AES128-ECB [19, 20] be a mapping and h:0,1∗→r:r∈-1,0,1m,r1≤ι be a hash function. In addition, we denote IDA (IDB) is Alice’s (Bob’s) identity. Then, PKG computes H(IDi)=Hi(i=A,B) to be seen as the participant’s public key. Since Hi∈Rqm×m, X∈Rqm×m, PKG can generate the secret keys by computing X·HA=SAmod⁡q and HB·X=SBmod⁡q. Simply speaking,(12)Si←Extractn,H,X,IDii=A,B.


## 4.3. Sign

Alice executes the following steps to sign a signature for messageμ.(1)
t←$Dγ(γ<q)(2)
ift is not reversible, then go to step (1).(3)
k←$Dγ(4)
c=HB·kmod⁡q(5)
r=h(c,μ)(6)
z=SA·r+k·t-1(7)
ifz∞≥γ-υ or SA·r∞≥υ, then go to step (3).(8)
output signature(r,z,t) of message μ.Notice that there are two loop conditions in step (1) and step (7). Thus, it is necessary for us to evaluate their efficiencies.(i)
About step (1). In [25], Hoffstein et al. proposed a method to search an invertible polynomial t within 48.9 ms. Their instance is that t satisfies t1≤40 in a trinary polynomial set T(206,205), where 206 and 205 are numbers of positive coefficients and negative coefficients, respectively. Since such an invertible t is contained in set Dγ, we can also find it in 48.9 ms.(ii)
About step (7). This step is the key to compute the repetition using filtering technique (see [13]). In order to utilize their result, we require that the inequation mΦυ≤γ must be satisfied. Hence we get the repetition is approximately e1/Φ. Obviously, we can see that e1/Φ is a monotonically decreasing function with variable Φ∈N+, and the bigger value of Φ seemingly is better. However, two of composition parts of signature are z and t, and their size is mlog⁡(γ-υ)+mlog⁡γ which is positively correlated with parameter Φ. Hence, choosing bigger Φ is not wise. Then we get the optimal solution Φ=4 by observing the following expression, (13)Φ=min0.75≤e-1/Φ′≤1⁡Φ′,where1≤Prz∞≤γ-υ=e-1/Φ′≤0.75. Furthermore, the repetition is e1/Φ≈1.28.


## 4.4. Verf

When receiving signatureσ=(r,z,t) from signer Alice, Bob verifies whether the following equation is correct or not:(1)
h(c,μ)=h(HBzt-SBHArtmod⁡q,μ)(2)
z∞≤γ-υ


## 4.5. Sim

If one gets a quadruple(SB,IDA,IDB,μ), he chooses two random elements z′ (z′∞≥γ-υ) and r′ to compute z′t-1=z and r′t-1=z. Hence, he can also compute the following equation, (14)HBzt-SBHArt=c=HBz′-SBHAr′,which is an indistinguishable signature with Alice’s.


## 5. Security

In this part, we will show our scheme satisfies three properties including unforgeability, untransferability, and anonymity (privacy of signer’s identity) according to security model in Section2.


### 5.1. Correctness

After receiving the signature(r,z,t) of message μ, designated verifier verifies the condition z∞≤γ-υ and computes the value of hash function as follows.(15)hc,μ=hHBz-SArtmod⁡q,μ=hHBzt-HBSArtmod⁡q,μ=hHBzt-HBXHArtmod⁡q,μ=hHBzt-SBHArtmod⁡q,μ.Then the following equation holds. (16)VerfSB,IDA,μ,SignSA,IDB,μ=True.


### 5.2. Unforgeability

Theorem 5.
If there is a PPT adversaryA that has ability to succeed in (t,ϵ) EUF-CMA game, then he can solve SIS problem over Rqm×m.Proof.
Suppose EUF-CMA game proceeds as required betweenA and challenger C. When A finishesExtraction andSign queries in time t, he outputs a new signature (σ∗=(r∗,z∗,t∗),μ∗) with two new identities IDi∗ and IDj∗ satisfying the following conditions:
(1)IDi∗ and IDj∗ have never been requested inExtraction queries step.
(2) Messageμ∗ related with IDi∗ and IDj∗ has never been requested inSign queries step.
(3) The signatureσ∗ with message μ∗, IDi∗, and IDj∗ is valid.
If Verf (Sign(IDi∗,IDj∗,μ∗)) =True holds, then A can compute(17)Hj∗z∗-Si∗r∗t∗t∗-1-Hj∗z∗=Hj∗z∗-Hj∗Si∗r∗-Hj∗z∗=-Hj∗Si∗r∗mod⁡q.In addition, the equation z∗∞≤γ-υ holds, which means Si∗r∗∞≤υ is satisfied. We can easily see that the adversary gets a solution of SIS problem for a random element Hj∗∈Rqm×m.


### 5.3. Untransferability

Theorem 6.
Our ID-based SDVS is(t,qs) untransferability.Proof.
The adversaryA and challenger C play untransferable game as required. After qs signing and verifying queries, A chooses a new massage μ∗ to query C. C chooses b←$0,1, and if b=0, C computes σ∗← Sign(SA,IDB,μ∗) to answer A. That is,(18)t∗,k∗←$Dγ,r∗=hHB·k∗mod⁡q,μ∗,z∗=SA·r∗+k∗·t∗-1,
output signature(r∗,z∗,t∗) of message μ∗.
Otherwise,C runs σ∗← Sim(SB,IDA,IDB,μ∗) to answer adversary’s request. That is,(19)z′,r′←$Dγ,r∗=hHBz′-SBHAr′mod⁡q,μ∗,z∗=z′t∗-1,t∗=r′r∗-1,output signature (r∗,z∗,t∗) of message μ∗. Now we compute the probabilities of above two signatures σ∗ distributions.(20)Prr∗,z∗,t∗∣b=0=Prt∗,k∗≠0∣t∗,k∗←$Dγ=1γmγm-1.Prr∗,z∗,t∗∣b=1=Prz′,r′≠0∣z′,r′←$Dγ=1γmγm-1.Hence, the advantage of guessing b=b′ for A is negligible, and we can obtain (21)Prb=b′-12<ϵ.


### 5.4. Anonymity

Theorem 7.
If the PPT adversaryA can distinguish the signer’s identity from given IDA0 and IDA1 for a designated verifier’s identity IDB, then he can distinguish the different solutions of SIS problem over Rqm×m.Proof.
Here, we also suppose thatA and C interact with each other as defined of secure model. After Extraction, Sign, and Verf queries are finished, the adversary A outputs a message μ∗ with signer’s possible identities IDA0, IDA1 and designated verifier’s identity IDB to challenger C satisfying the above elements that have not been queried.
After receivingμ∗, C tosses a coin randomly, chooses b←$0,1, and computes Sign (SIDAb,IDB,μ∗) returned to A. If A can guess b correctly, this means he can compute the probability as follows.(22)Prb=b′=PrDHBz∗t∗-SBHA0r∗t∗-PrDHBz∗t∗-SBHA1r∗t∗=PrDSBHA0r∗t∗-PrDSBHA1r∗t∗=PrDHBXHA0r∗t∗-PrDHBXHA1r∗t∗=PrDHBSA0r∗t∗-PrDHBSA1r∗t∗=PrDHBSA0r∗-PrDHBSA1r∗We consider SA0r∗ and SA1r∗ as different solutions of SIS problem with HB∈Rqm×m. Since the result of final equation is negligible, Pr[b=b′]≤ϵ holds.


## 5.1. Correctness

After receiving the signature(r,z,t) of message μ, designated verifier verifies the condition z∞≤γ-υ and computes the value of hash function as follows.(15)hc,μ=hHBz-SArtmod⁡q,μ=hHBzt-HBSArtmod⁡q,μ=hHBzt-HBXHArtmod⁡q,μ=hHBzt-SBHArtmod⁡q,μ.Then the following equation holds. (16)VerfSB,IDA,μ,SignSA,IDB,μ=True.


## 5.2. Unforgeability

Theorem 5.
If there is a PPT adversaryA that has ability to succeed in (t,ϵ) EUF-CMA game, then he can solve SIS problem over Rqm×m.Proof.
Suppose EUF-CMA game proceeds as required betweenA and challenger C. When A finishesExtraction andSign queries in time t, he outputs a new signature (σ∗=(r∗,z∗,t∗),μ∗) with two new identities IDi∗ and IDj∗ satisfying the following conditions:
(1)IDi∗ and IDj∗ have never been requested inExtraction queries step.
(2) Messageμ∗ related with IDi∗ and IDj∗ has never been requested inSign queries step.
(3) The signatureσ∗ with message μ∗, IDi∗, and IDj∗ is valid.
If Verf (Sign(IDi∗,IDj∗,μ∗)) =True holds, then A can compute(17)Hj∗z∗-Si∗r∗t∗t∗-1-Hj∗z∗=Hj∗z∗-Hj∗Si∗r∗-Hj∗z∗=-Hj∗Si∗r∗mod⁡q.In addition, the equation z∗∞≤γ-υ holds, which means Si∗r∗∞≤υ is satisfied. We can easily see that the adversary gets a solution of SIS problem for a random element Hj∗∈Rqm×m.


## 5.3. Untransferability

Theorem 6.
Our ID-based SDVS is(t,qs) untransferability.Proof.
The adversaryA and challenger C play untransferable game as required. After qs signing and verifying queries, A chooses a new massage μ∗ to query C. C chooses b←$0,1, and if b=0, C computes σ∗← Sign(SA,IDB,μ∗) to answer A. That is,(18)t∗,k∗←$Dγ,r∗=hHB·k∗mod⁡q,μ∗,z∗=SA·r∗+k∗·t∗-1,
output signature(r∗,z∗,t∗) of message μ∗.
Otherwise,C runs σ∗← Sim(SB,IDA,IDB,μ∗) to answer adversary’s request. That is,(19)z′,r′←$Dγ,r∗=hHBz′-SBHAr′mod⁡q,μ∗,z∗=z′t∗-1,t∗=r′r∗-1,output signature (r∗,z∗,t∗) of message μ∗. Now we compute the probabilities of above two signatures σ∗ distributions.(20)Prr∗,z∗,t∗∣b=0=Prt∗,k∗≠0∣t∗,k∗←$Dγ=1γmγm-1.Prr∗,z∗,t∗∣b=1=Prz′,r′≠0∣z′,r′←$Dγ=1γmγm-1.Hence, the advantage of guessing b=b′ for A is negligible, and we can obtain (21)Prb=b′-12<ϵ.


## 5.4. Anonymity

Theorem 7.
If the PPT adversaryA can distinguish the signer’s identity from given IDA0 and IDA1 for a designated verifier’s identity IDB, then he can distinguish the different solutions of SIS problem over Rqm×m.Proof.
Here, we also suppose thatA and C interact with each other as defined of secure model. After Extraction, Sign, and Verf queries are finished, the adversary A outputs a message μ∗ with signer’s possible identities IDA0, IDA1 and designated verifier’s identity IDB to challenger C satisfying the above elements that have not been queried.
After receivingμ∗, C tosses a coin randomly, chooses b←$0,1, and computes Sign (SIDAb,IDB,μ∗) returned to A. If A can guess b correctly, this means he can compute the probability as follows.(22)Prb=b′=PrDHBz∗t∗-SBHA0r∗t∗-PrDHBz∗t∗-SBHA1r∗t∗=PrDSBHA0r∗t∗-PrDSBHA1r∗t∗=PrDHBXHA0r∗t∗-PrDHBXHA1r∗t∗=PrDHBSA0r∗t∗-PrDHBSA1r∗t∗=PrDHBSA0r∗-PrDHBSA1r∗We consider SA0r∗ and SA1r∗ as different solutions of SIS problem with HB∈Rqm×m. Since the result of final equation is negligible, Pr[b=b′]≤ϵ holds.


## 6. Parameters

Except form,n,q, there are several main parameters for evaluating our signature efficiency, which are ι,Φ,υ, and γ. We will describe them one by one.(i)
Parameterι. Generally, one wants to get λ bit security signature; then he will assume the output of hash function is also λ bit (see [15, 16]). So the parameter ι satisfies condition 2ι·Cmι≥2256.(ii)
ParameterΦ. It is chosen according to the actual situations. Firstly, it must make the value of e-1/Φ be in the range [0.75,1]. In this case, the chosen value satisfying e-1/Φ=1(≈1) is the best one. Secondly, it can’t enlarge the signature size m+mlog⁡(γ-υ)+mlog⁡γ. To sum up, we show the final equation,(23)Φ=min0.75≤e-1/Φ′≤1⁡Φ′.(iii)
Parametersυ and γ. In order to utilize the result [13], we get the condition mΦυ≤γ directly. In addition, since choosing bigger γ means that we can get a larger signature, we let γ equal mΦυ. Besides, according to the definition of Dγ, we can easily see γ<q. So γ=mΦυ<q holds.Comparison of Signature Size. Here we give a comparison with [9] about signature size, and our result is better than theirs (3mlog⁡q). Furthermore, we can see that the signature size of our design is the shortest among any other existing ID-based SDVS schemes over ideal lattice. The detailed parameters can be seen in Table 1. Based on what we have discussed in those parameters, we provide the final size of our signature as follows:(24)mlog⁡2+mlog⁡γ-υ+mlog⁡γ=m+mlog⁡γ-γ4m+mlog⁡γ≤m+mlog⁡q-q4m+mlog⁡q≤m+mlog⁡q+mlog⁡q≤3mlog⁡q.Table 1
Parameters of our ID-based SDVS overR-SIS.
Parameters Relationship n rank of lattice q a prime number m 2 n γ < q υ γ / 4 m ι 2 ι ⋅ C m ι ≥ 2 256 Φ 4 Signature size 2 m log ⁡ q + m Repetition e 1 / Φ ≈ 1.28


## 7. Conclusion and Further Work

Conclusion. In this paper, we provide an ID-based SDVS scheme over ideal lattice. Our scheme has the shortest signature size 2mlog⁡q+m and satisfies three properties unforgeability, untransferability, and anonymity proved in the random oracle. Moreover, we use uniform sampling to resist side-channel attacks in our design, and the repetition approximate 1 means our scheme has a relatively high efficiency.Further Work. We consider the quantum random oracle. As far as we know, in existing lattice-based signature schemes, only TESLA [26] has proved its security in the quantum random oracle. Hence, our further work is to use their method to give a proper proof in the quantum random oracle for our scheme.



---

*Source: 9678095-2019-07-15.xml*