Abstract
ABSTRACT The designated verifier signature (DVS), introduced by Jakobsson et al., has the property that only the designated verifier can verify the generated signature. In order to prevent an eavesdropper to get the signature on-line before the designated verifier receives it, they also proposed strong designated verifier signature (SDVS). In this paper, according to an efficient SDVS proposed by Saeednia et al., we present a post-quantum SDVS in the random oracle model based on lattice assumption. The unforgeability is based on the hardness of the average-case hard problem R−SIS q,n,m,β , which is at least as hard as worst-case SVP γ over ideal lattices. In addition, compared with existing lattice-based SDVS schemes, our scheme cuts by more than 50 percent repetitions and the size of signature is shorter with 256 bits security.
Abstract
INDEX TERMS Designated verifier signature, lattice, post-quantum, SIS problem.
I. INTRODUCTION
With the development of digital signature schemes, more and more signature schemes with special characteristics are considered, such as blind signature, ID-based signature, group (ring) signature etc. In the cases of private bidding and auctions, secret ballot elections etc, there is a question that how to solve the contradiction between reliability and privacy. Designated verifier signature scheme provided the answer.
I. INTRODUCTION
In 1996, the designated verifier signature (DVS) was first introduced by Jakobsson et al. [1] . It needs to satisfy a particular property that only designated verifier can verify the generated signature. Although the designated verifier can produce a simulated signature which is indistinguishable with the signer's, he can't convince others that the signer is the real producer for some signatures.
I. INTRODUCTION
Unfortunately, the first proposed DVS scheme can't prevent an on-line eavesdropper to get the signature before it is received by designated verifier. And the signature is able to be verified by a third party. Thus, a definition called strong designated verifier signature (SDVS) against this attack was also proposed in [1] . In a SDVS scheme, verification step needs the private key of verifier, hence no one except designated verifier can verify it.
A. RELATED WORK 1) SDVS SCHEME BASED ON DISCRETE LOGARITHM PROBLEM
In [1] , Jakobsson et al. provided two feasible techniques for making DVS to be a SDVS in transcripts. One way is to use a probabilistically encrypted with the public key of intended verifier; the other is to choose the symmetry encryption of a session key. However, the latter one inevitably brings an additional complex operation. In 2003, Saeednia et al. (SKM, for short) [2] designed the first efficient SDVS which was based on a merged applications of the Schnorr signature [3] and the Zheng signcryption schemes [4] , without using any encryption or other operations. Thus, this scheme becomes a basic framework in designing SDVS schemes.
A. RELATED WORK 1) SDVS SCHEME BASED ON DISCRETE LOGARITHM PROBLEM
Then many other SDVS were provided [5] - [9] . Specifically, in 2004, Laguillaumie and Vergnaud [9] gave some new security definitions including unforgeability, untransferability and privacy of signer's identity (undelegateability). In 2007, Li et al. [8] showed undelegateability of [9] was so strong that no SDVS existed and maybe it was a controversial definition. Hence we don't consider this property in our scheme until a standard definition for protecting privacy of signer's identity is developed. Unfortunately, the schemes described above are based on discrete logarithm problem, which can't resist against quantum adversaries. Hence more and more cryptographers begin to design post-quantum cryptographic schemes.
2) LATTICE-BASED SIGNATURES WITH GAUSSIAN SAMPLING AND UNIFORM SAMPLING
Generally speaking, the post-quantum cryptography systems mainly include lattice-based, code-based, multivariate cryptosystems and homology-based on supersingular elliptic curves cryptography.
2) LATTICE-BASED SIGNATURES WITH GAUSSIAN SAMPLING AND UNIFORM SAMPLING
Among of them, lattice-based cryptography has been widely studied. In recent years, many efficient lattice-based signature schemes were proposed [10] - [12] . From the viewpoint of improvement tendency, cryptographers focus on how to shorten the size of signature and times of rejection sampling. They usually use compression technique to shorten the signature size, where one can sign a message with high bits of a random number. In order to lower the repetition, people mainly utilize rejection sampling lemma and filtering technique.
2) LATTICE-BASED SIGNATURES WITH GAUSSIAN SAMPLING AND UNIFORM SAMPLING
Rejection sampling lemma (see [12] ) was first provided in 2012, and the author gave a signature scheme with Gaussian sampling. In addition, the rejection probability was defined by min(f (z)/Mg v (z), 1), where f , g were gaussian distribution, and v, z, M ∈ R. It is easy to see a low rejection probability is depended on a small M . In 2013, Ducas et.al. proposed bimodal gaussian (see [11] ) to reduce the number M .
2) LATTICE-BASED SIGNATURES WITH GAUSSIAN SAMPLING AND UNIFORM SAMPLING
However, in 2016, it has been proved that, with discrete Gaussian sampling technique, these schemes could lead to a lot of potential side-channel attacks, even complete leakage of private key [13] , [14] . Although, one can design almost perfect implementations to protect against some side-channel attacks (see [15] ), the intricacies make it an area where one can easily make mistakes.
2) LATTICE-BASED SIGNATURES WITH GAUSSIAN SAMPLING AND UNIFORM SAMPLING
To make schemes resist above attacks, one may use filtering technique with uniform sampling (see [16] , [17] ). The aim of rejection sampling aspect is to protect the secret key. The idea is the signer can select to output signatures by simply checking whether those signatures fall in a fixed range or not. Simply speaking, if we want to get a special number c = a + b which can't reveal anything about a secret number a ∈ [−B, B] (here B presents a non-negative bound ), where
2) LATTICE-BASED SIGNATURES WITH GAUSSIAN SAMPLING AND UNIFORM SAMPLING
, 5B] is uniformly chosen, the range of c must satisfies c ∈ [−4B, 4B]. Otherwise, we refresh b to make the distribution of c independent on a. Rückert (see [18] ) extended it to polynomial rings and gave a reject aborting equation e 1/ , where ∈ N + . In a concrete scheme, is related to the size of signature more or less. Hence, determining its value needs to balance both of them.
3) LATTICE-BASED SDVS SCHEMES
As far as we know, The first lattice-based SDVS scheme [19] was proposed by Wang et.al. in 2012. According to the framework of SKM, they utilized the Bonsai trees and pre-image sampling function primitives to construct the SDVS. Its unforgeability and nontransferability were based on SIS problem and LWE problem respectively, which were proved in the random oracle model.
3) LATTICE-BASED SDVS SCHEMES
In 2013, Li et al. proposed a post-quantum SDVS [20] according to lattice-based signature scheme [21] . The security is based on SIS problem in the standard model, and they also use pre-image sampling function. In 2016, Noh and Jeong [22] provided a SIS-based SDVS scheme following from [19] , and its security was reduced to the same hard problems with [19] . It is proved in the standard model.
3) LATTICE-BASED SDVS SCHEMES
However, all of these schemes have several disadvantages listed as follows:
3) LATTICE-BASED SDVS SCHEMES
• Gaussian sampling was used in their schemes, which is unusual to resist side-channel attack.
3) LATTICE-BASED SDVS SCHEMES
• They were designed in regular lattices instead of ideal lattice. Hence, this will inevitably bring larger size of public key and signature.
3) LATTICE-BASED SDVS SCHEMES
• They used pre-image sampling function and Bonsai trees, which will result in having fairly complex operations and large parameters.
3) LATTICE-BASED SDVS SCHEMES
• Since they focused on pure theoretical research, they didn't provide specific parameters of a real implementation in their schemes. In addition, no detailed comparisons were shown with other lattice-based SDVS schemes.
B. OUR CONTRIBUTION
In this paper, we put forward a new efficient SDVS scheme that is based on R−SIS q,n,m,d problem in ideal lattice with uniform sampling. Notice that our design is totally different from above lattice-based SDVS in the aspect of constructions of hard problem and sampling methods. In addition, we propose a new lemma (Lemma 1) to support the correctness of our design and proof.
B. OUR CONTRIBUTION
• Lower repetition and shorter size of signature. The repetition of our scheme is 1.28 and the size of the signature is 42721 bits (16448 bits can be done using the technology in [10] ) with 256-bit security. Obviously, our scheme has shorter signature size and repetition. There are several reasons for this: 1) Our scheme is the first SDVS over ideal lattice (R−SIS problem), and we don't use Bonsai trees and pre-image sampling. Hence we reduce the size of pk, signature and communication cost. 2) We use a similar Fiat-Shamir framework [23] which is always used in many lattice-based signature schemes [10] - [12] , [16] , [17] to improve their efficiency. So our SDVS is efficient based on this framework.
B. OUR CONTRIBUTION
• Resisting side-channel attacks. We utilize uniform sampling instead of Gaussian sampling which can effectively resist side-channel attacks [13] - [15] .
B. OUR CONTRIBUTION
• Giving detailed parameters. We provide the detailed parameters to show the lower size of pk, signature VOLUME 7, 2019 and communication cost in our SDVS. Moreover, we also give comparisons with above lattice-based SDVS scheme.
C. ORGANIZATION OF THE PAPER
We firstly introduce some definitions of SDVS, describe the major design ideas of SKM lattices briefly and provide some necessary hard problems and lemmas in Section II. Then we show our detailed lattice-based SDVS scheme, its security proof and comparisons of parameter in Section III. Finally we present a conclusion and further work in Section IV.
II. PRELIMINARIES A. STRONG DESIGNATED VERIFIER SIGNATURE
A SDVS scheme consists of four algorithms between signer (Alice) and a designated verifier (Bob). The specific definition is as follows: Definition 1: Given an integer n, a SDVS with security parameter n is defined by the following:
II. PRELIMINARIES A. STRONG DESIGNATED VERIFIER SIGNATURE
• Setup: it is a probabilistic algorithm which takes n as input. The outputs are the public parameters (PK a , SK a ) and (PK b , SK b ) which belong to signer and designated verifier respectively;
II. PRELIMINARIES A. STRONG DESIGNATED VERIFIER SIGNATURE
• Sign: it is a probabilistic (deterministic) algorithm which takes a triple (µ, SK a , PK b ) containing a message, a signing sk and a verifying pk as inputs. The output is a designated verifier signature σ of message µ;
II. PRELIMINARIES A. STRONG DESIGNATED VERIFIER SIGNATURE
• Verify: it is a deterministic algorithm which takes a quadruple (σ, µ, PK a , SK b ) containing a bit string, a message, a signing pk and a verifying sk as inputs, and tests whether σ is a valid designated signature of µ with the keys (PK a , SK a , PK b , SK b ).
II. PRELIMINARIES A. STRONG DESIGNATED VERIFIER SIGNATURE
• Simulation: it is a probabilistic algorithm which takes a quadruple (µ, PK a , SK b , PK b ) as inputs. Anyone and generate an indistinguishable signatures form those generated by the triple (µ, SK a , PK b ). A SDVS must satisfy the following secure properties. 1) correctness: a properly formed designated verifier signature must be accepted by the verifying algorithm.
II. PRELIMINARIES A. STRONG DESIGNATED VERIFIER SIGNATURE
That is, for all valid (PK a , SK a , PK b , SK b ) and a message µ, the equation holds:
II. PRELIMINARIES A. STRONG DESIGNATED VERIFIER SIGNATURE
2) unforgeability: here we give a brief game of existential unforgeable against adaptive chosen message attack (EUF-CMA) [8] between a polynomially bounded adversary A and a challenger C.
II. PRELIMINARIES A. STRONG DESIGNATED VERIFIER SIGNATURE
• The challenger C constructs valid pk and sk,
II. PRELIMINARIES A. STRONG DESIGNATED VERIFIER SIGNATURE
where n is the security parameter. Then C sends (PK a , PK b ) to the adversary A.
II. PRELIMINARIES A. STRONG DESIGNATED VERIFIER SIGNATURE
• A queries the signing oracle q s times (which is polynomially bounded in n) at any time for message µ i . The challenger C answers his queries by
II. PRELIMINARIES A. STRONG DESIGNATED VERIFIER SIGNATURE
• At the end of the game, we say that the adversary is success if he outputs a new signature σ * for message µ * satisfying correctness equation and µ * = µ i . For any polynomial time adversary A running above game in time t, we say that a SDVS scheme is (t, ε) EUF-CMA secure (unforgeability) if the below equation holds:
II. PRELIMINARIES A. STRONG DESIGNATED VERIFIER SIGNATURE
where ε > 0 is a negligible function of secure parameter n. 3) untransferability: we also provide a game involving a challenger C and a distinguisher D. C provides Sign and Simulation algorithms to simulate the attack environment for the distinguisher D, then D tries to distinguish that a given output comes from the signer or designated verifier.
II. PRELIMINARIES A. STRONG DESIGNATED VERIFIER SIGNATURE
• The challenger C produces valid pk and sk,
II. PRELIMINARIES A. STRONG DESIGNATED VERIFIER SIGNATURE
where n is the security parameter. Then C sends (PK a , PK b ) to D, and the left keys are kept secret.
II. PRELIMINARIES A. STRONG DESIGNATED VERIFIER SIGNATURE
• The distinguisher D queries the signatures for any message µ i . The challenger C answers them by
II. PRELIMINARIES A. STRONG DESIGNATED VERIFIER SIGNATURE
• The distinguisher queries a new message µ * . C tosses a coin b ← R {0, 1}. If b = 0, he runs Sign algorithm and returns σ * = Sign(PK a , PK b , SK a , µ * ). Otherwise, he runs Simulation algorithm and returns σ * = Simulation (PK a , PK b , SK b , µ * ).
II. PRELIMINARIES A. STRONG DESIGNATED VERIFIER SIGNATURE
• After receiving the challenging signature σ * , D can query new messages expect for µ * .
II. PRELIMINARIES A. STRONG DESIGNATED VERIFIER SIGNATURE
• At the end of this game, D outputs a bit b and wins it if b = b . The advantage of D is defined as:
II. PRELIMINARIES A. STRONG DESIGNATED VERIFIER SIGNATURE
We say that a SDVS scheme is untransferability against a (t, q s ) adaptively chosen message distinguisher D if the value of the above equation is negligible after querying q s signatures in time t. In our paper, we will prove our scheme satisfies all of the above secure properties according to these formal definitions.
B. SKM DESIGNATED VERIFIER SCHEME
The SKM scheme is based on DL problem, they assume: a large prime p with a prime factor q of p−1, a generator g ∈ Z * p with order q and a hash function h with values in Z q . And all the initially common parameters are shared between the participants Bob and Alice.
B. SKM DESIGNATED VERIFIER SCHEME
Each participant i chooses his secret key x i ∈ Z q and publishes the corresponding public key y i = g x i mod p.
1) SIGNATURE GENERATION
To sign a message µ for Bob, Alice selects two random values k ∈ Z q , t ∈ Z * p and computes
1) SIGNATURE GENERATION
The triple (r, s, t) is the signature of the message µ. 
3) TRANSCRIPT SIMULATION
Bob has the ability to simulate the signature. For example, he selects s ∈ Z q , r ∈ Z * q at random and computes
3) TRANSCRIPT SIMULATION
These values are substituted in the expression (g s y r a ) tx b mod p to calculate c and get h(c, µ) = r.
4) SECURITY
If an adversary can generate a valid signature without Alice's or Bob's secret keys, then he will have the ability to solve Diffie-Hellman problem g x a x b in polynomial time (see [2] ).
C. LATTICES
Notation: We choose the quotient ring
C. LATTICES
, where q is a polynomial-size prime number, n is a power of 2 and elements in ring Z q are the integers in the range [−q/2, q/2]. t −1 represents an invertible element in R q . The statement x ← R D shows that x is chosen uniformly at random from the finite set D. We will write D k to denote all elements ω ∈ R q such that ω ∞ ≤ k. Particularly, B k means ω ∈ {−1, 0, 1} m such that ω 1 ≤ k. We denote two random variables X , Y over a discrete domain D, and define the statistical distance of them as (
C. LATTICES
The bold capital letters are matrices and bold small letters are vectors, while normal fonts for integers and real. All vectors are column-vectors unless otherwise noted. For a vector v (a matrix S ), we denote by v T (S T ) its transpose, by v its Euclidean norm ( 2 norm), and by v ∞ its infinity norm. We let the 2 norm of the matrix is S = max s i instead of the minimum of eigenvalue [24] , where s i is each column vector in S. h : {0, 1} * → {−1, 0, 1} m is a cryptographic hash function hashing onto B k (see [10] , [12] ).
C. LATTICES
Lattices are formally defined as discrete additive subgroups of R m . We often represent them as L = BZ n , n m, where B is a basis. In cryptography, integral lattices, i.e. subgroups of Z m are usually considered.
C. LATTICES
One of the most common hard problems about lattice is shortest vector problem (SVP). In fact, there are three variants of SVP, depending on whether find the shortest vector (search SVP), compute its length (optimization SVP), or decide if it is shorter than some given number ( decisional SVP). And the three above variants are essentially equivalent.
C. LATTICES
Particularly important to lattice cryptography is approximation problem SVP γ .
C. LATTICES
Definition 2: Given a basis B of n-dimensional lattice and
C. LATTICES
Similarly, approximate problems also have three versions. However, they are not equivalent, and whether the search version is not harder than the optimization version is an open question. Usually, the decisional version is denoted GapSVP γ . The security of our scheme can be reduced to the decision version.
D. HARD PROBLEMS IN OUR SCHEME 1) HARD PROBLEM OVER RING
Generally speaking, lattice-based cryptographic schemes have large keys sizes, which mainly because the private and public keys matrices have large dimension and every entry in them is independent. Hence, People are beginning to think about ways to reduce this independence. For example, the matrix A ∈ Z n×m q can be generated by choosing its first column a 0 uniformly at random form Z n q and the left n − 1 columns, a 1 , . . . , a n−1 are the coefficient representation of the polynomial a 0 x i in the ring Z q [x]/(x n +1). The generation of column a n is the same as the first one. Repeat the previous process and get the final matrix.
D. HARD PROBLEMS IN OUR SCHEME 1) HARD PROBLEM OVER RING
The ring R q is also considered as the sub-ring of anticirculant square matrices where each ring element r ∈ R q can be regarded as a linear transformationx → r · x over the coefficient embedding of R q . By constructing A like this, As is equivalent to polynomial multiplications and additions in the ring Z q [x]/(x n + 1). In 2006, references [25] and [26] introduced a ring variant of SIS independently.
2) SPECIFIC HARD PROBLEM OVER RING
The construction of our scheme is based on R−SIS q,n,m,d which is a variant of R−SIS q,n,m,β problem (see [12] ). Always we suppose m ≥ 2n, then a random matrix A ∈ Z n×m q will contain n linearly independent columns over Z q with high probability which is up to e − (n) when q is a prime of size at least 2m. First we give definition of R−SIS problem. VOLUME 7, 2019 Definition 3 [11] : Let R be some ring and K be some distribution over R n×m q , where R q is the quotient ring R/(qR). Given a random matrix A ∈ R n×m q following the distribution K, find a non-zero vector v ∈ R m q such that Av = 0 and v ≤ β, which is denoted R−SIS K q,n,m,β problem. Then R−SIS K q,n,m,d problem has a limitation s ∈ {−d, . . . , 0 , . . . , d} m such that As = t. Lyubashevsky [12] has proven the decision SIS q,n,m,d problem is harder with increase of d, and there exists a polynomial-time reduction from SIS q,n,m,d decision problem to the 2 −SIS q,n,m,β problem under conditions m = 2n and 4dβ ≤ q.
2) SPECIFIC HARD PROBLEM OVER RING
In [26] , it was shown that if the ring
2) SPECIFIC HARD PROBLEM OVER RING
, where q is a polynomial-size prime number, n is a power of 2, then average case R−SIS K q,1,m,β problem is as hard as the worst caseÕ( √ nβ)−SVP problem for all lattices that are ideals in R where K is the uniform distribution over R 1×m q . In order to make our constructing correct and efficient, we provide a new lemme in the next part.
E. A NEW LEMMA FOR THE DESIGN OF OUR SCHEME
Here, we give the below lemma to show the conclusion over ring R 2×m q still holds. We provide the following lemma to ensure the security of our scheme. Now we show the necessity of constructing it, and then give a proof in detail.
E. A NEW LEMMA FOR THE DESIGN OF OUR SCHEME
• The design of square matrix is necessary. Since there are operations of matrix multiplication in our scheme, we need to design a square matrix to support multiplicative property.
E. A NEW LEMMA FOR THE DESIGN OF OUR SCHEME
• The efficiency must kept. We don't want to increase the computation with the increase of its dimension. Hence, we fill a general matrix A 1 with zero matrix to get a square form directly. Notice that doing like this, the actual calculation is A 1 V 1 , and the expected result is attained.
E. A NEW LEMMA FOR THE DESIGN OF OUR SCHEME
• The security must be ensured. By proving the lemma, we can easily see that there is no change of the problem itself. Furthermore, the norm of new solution to SIS problem is equal to the original one. It means that this special square matrix doesn't impact on our security assumption. , 0 m×n , then, we verify that the value of AV mod q is zero matrix or not. According to the multiplicative principle of block matrices, we get
E. A NEW LEMMA FOR THE DESIGN OF OUR SCHEME
Since we have the known condition A 1 v i = 0 mod q, then we get
E. A NEW LEMMA FOR THE DESIGN OF OUR SCHEME
Hence, AV = 0 mod q holds. By definition, V = max v i , where i = 1, · · · , 2n. However, according to the construction of V, the values of i from n + 1 to 2n are 0. Then we have V = max v i = V 1 = β. Since it doesn't change the length of the shortest vector, its security also can be reduced toÕ( √ nβ)−SVP problem without a loss of problem gap. We finish our proof.
E. A NEW LEMMA FOR THE DESIGN OF OUR SCHEME
With the above proof and analysis, the unforgeability of our scheme can be reduced to R−SIS q,n,m,d problem, which ensures the problem our design based on is also hard.
F. FILTERING TECHNIQUE OVER RING
In our scheme, we use uniform distribution over ring, and the rejection sampling aspect is simply check whether the individual coefficients of signature fall in a fixed range. 
F. FILTERING TECHNIQUE OVER RING
This lemma tells us that if we choose random vector b appropriately, the norm of a − b is constrained in a expected range with high probability. Thus it can protect the secret vector (usually a). In our scheme, there is an important signature process z = S a r + kt −1 , in which the signature z can be fell within a range to hide the secret key S a , as long as kt −1 is reasonably assigned.
F. FILTERING TECHNIQUE OVER RING
Besides, the final probability inequation in this lemma is actually a formula of repetitions. If we want get a secure domain for the signature z, we must repeat this process e 1/ times. In addition, the value of affects the size of signature, thus how to determine it is an emphatic problem (see Fig.1 ).
III. OUR CONSTRUCTION
In this section, we firstly go into details about our postquantum protocol in which it contains key-generation, signing, verification, simulation algorithms. Then we provide the security proof according to our formal security definitions. Finally, we list the parameters in our scheme.
III. OUR CONSTRUCTION
Particularly, in the key-generation phase of our scheme, we need construct a square matrix public key A, which can't add extra calculations. Hence, we use a obvious method that is filling the square matrix with A ∈ R n×m q and 0 n×m . Furthermore, the security of this structure is still proved (see detailed Lemma 1). In signing and verification phases, we using filtering technique (Lemma 2) over ring to get an efficient scheme, which can resist side-channel attacks and has lower repetition 1.28.
III. OUR CONSTRUCTION
In order to shorten the signature size in Table 1 , we utilize a form of Module-SIS problem, then the final result is 16448 bits.
III. OUR CONSTRUCTION
A. OUR SCHEME
1) KEY GENERATION
We now briefly sketch the key generation algorithm of our designated verifier signature scheme. Here we firstly give a description on regular lattice, then show a ring setting on ideal lattice. There are two secret matrices . Nevertheless, this will not increase the actually computational capacity by the proof of lemma 1. In ring variants of our scheme,
1) KEY GENERATION
q . In the following algorithm, KeyGen, SigKey, VerKey, and RO represent key generation, signing key, verification key and random oracle respectively.
KeyGen:
SigKey:
KeyGen:
h : {0, 1} * → {r : r ∈ {−1, 0, 1} m , r 1 ≤ η}, η is the Hamming weight of r.
KeyGen:
(S a , Y a ) is Alice's secret key and (S b , Y b ) belongs to Bob.
2) SIGNATURE GENERATION
Let β be a integer such that S a r ∞ < β with high probability over the choices of S a ← D m×m d and r ← B η . Then Alice computes Sign:
2) SIGNATURE GENERATION
8. output the signature (r, z, t) of message µ.
2) SIGNATURE GENERATION
Notice that there are two rejecting steps, step 2 and step 7. We now compute the probability step 2 and step 7 will not result in a restart.
2) SIGNATURE GENERATION
About step 2, we will refer to [27] for the invertibility of parameter t. We give a simple description Input : parameters N , σ, q and B γ Output : t 1. t ← T (σ + 1, σ ) 2. if t is not invertible mod q then goto step 1 end if 3. if t 1 ≥ B γ then goto step 1 end 4. return t Here, T (σ + 1, σ ) is a trinary polynomials of degree less than N , where there are σ + 1 positive coefficients and σ negative coefficients. If σ = 205, γ = 40, the above process can be completed in 48.9ms (see [27] ). Hence we do not consider the probability of repetition in this step any longer.
2) SIGNATURE GENERATION
About step 7, the probability z ∞ ≥ γ − β(γ > 1/2) can be computed by considering each coefficient separately. Suppose each coefficient of S a r is δ, then the corresponding coefficient of z will fall within −γ + β + 1 and γ − β − 1 when the coefficient of kt −1 falls within −γ + β + 1 − δ and γ − β − 1 − δ. The size of this range is 2(γ − β) − 1 and the coefficient of kt −1 have 2γ − 1. Thus, the probability that every coefficient of kt −1 is in the good range is
2) SIGNATURE GENERATION
About β in step 7, S a r ∞ ≤ dη, then β ≤ dη. And by the lemma 2, β must satisfy the inequations mβ ≤ γ .
3) VERIFICATION
Bob verities the equations Verify:
3) VERIFICATION
It is easy to see that the private key of Bob makes the verification equation can be computed by him only.
4) TRANSCRIPT SIMULATION
Bob simulates the signature as follows. He randomly chooses z and r . Let
4) TRANSCRIPT SIMULATION
We get equations
4) TRANSCRIPT SIMULATION
Compared to SKM designated verifier scheme, an important part of the constructed signature, (z, r), doesn't contain Bob's secret key here. Even so, it does not affect Bob's ability. Rather, we can see that anybody who gets the value of t may produce a distinguishable view with Bob's. This way, it satisfies strong designated verifier scheme requirements defined above. VOLUME 7, 2019 B. SECURITY 1) CORRECTNESS Suppose Bob gets the signature σ = (r, z, t) form Alice, if the condition z ∞ ≥ γ − β holds, then he computes
4) TRANSCRIPT SIMULATION
Hence, the below equation holds,
4) TRANSCRIPT SIMULATION
2) UNFORGEABILITY
Theorem 1:
If an adversary A can generate a new valid signature σ * by the game of EUF-CMA in time t, then he may have the ability to solve the R−SIS q,n,m,d search problem in polynomial time.
Theorem 1:
Proof: We now prove that our scheme is (t, ε) EUF-CMA secure (unforgeability).
Theorem 1:
Assume a PPT attacker A has an ability to produce a signature σ * = (r * , z * , t * ) which can be correctly verified at the end of the EUF-CMA game, then he can compute the following equation.
Theorem 1:
As a matter of fact, the attacker can continue to calculate the above equation, i.e.,
Theorem 1:
In fact, he can simplify −S T b Y a r * further to −Y T b S a r * . We note W = −Y T b S a r * mod q, and so long as S a r * ≤ β (0 < β < dη is polynomial in n), thereupon, he gets a solution for R−SIS q,n,m,d search problem.
Theorem 1:
To further discuss security, the Lemma 1 provides the possibility which is polynomial-time reduction form this average-case hard problem to the worst-case hard problem.
Theorem 1:
Summing up the above analysis, we get
Theorem 1:
≤ ε.
3) UNTRANSFERABILITY
Theorem 2: The above scheme is untransferability against a (t, q s ) adaptively chosen message distinguisher D, where q s is the times of querying signatures in time t from challenger C.
3) UNTRANSFERABILITY
Proof: According to the definition of untransferability game between the distinguisher D and challenger C, we now prove the advantage of D is negligible. That is the equation
3) UNTRANSFERABILITY
Suppose distinguisher D has adaptively queried q s signatures, then he queries a new message µ * . C tosses a coin b ← R {0, 1}. If b = 0, he runs Sign algorithm and returns σ * = Sign(PK a , PK b , SK a , µ * ). Otherwise, he runs Simulation algorithm and returns σ * = Simulation(PK a , PK b , SK b , µ * ). After receiving the challenging signature σ * , D can query new messages expect for µ * .
3) UNTRANSFERABILITY
At the end of game, we will compute the advantage of b = b . Firstly, we prove the following distributions are identical. Then we give the result. We let the left of vertical bar represent the case b = 0 (Sign algorithm), and the right part is the case b = 1 (Simulation algorithm). Then we compute the probabilities of these cases:
3) UNTRANSFERABILITY
Let (r,z,t) be a randomly chosen signature in the set where all valid signatures. Then we have the following probability distribution equations:
3) UNTRANSFERABILITY
Pr[(r, z, t) = (r,z,t)]
3) UNTRANSFERABILITY
which means that both distributions of probabilities are the same. Since the probability is the same in the two case, we can see distinguisher D can't distinguish the signature query about message µ * at the end of this game. That is to say, the below equation holds.
C. PARAMETERS 1) PARAMETERS OF OUR SCHEME
We let m = 2n to ensure that there exists a polynomialtime reduction from solving the SIS q,n,m,d decision problem to the 2 −SIS q,n,m,β problem. η satisfies 2 η · C η m ≥ 2 256 for which main reason is that (generally) one only needs random oracle output λ bits for obtaining signatures with λ bits security. According to the signature size discussion, smaller is better, but it can increase the repetitions. Thus, taking into consideration of these characteristics, we set = 4. A simple analysis is given in appendix I later (see, Fig. 1 ). Since η = 31, β ≤ dη, we let d = 1 so that making the value of β small enough, and then the signature size is also sufficiently small.
C. PARAMETERS 1) PARAMETERS OF OUR SCHEME
The sizes of secret key and public key are in regular lattice of our scheme, and if the secret key and public key are chosen in ideal lattice, they exactly are m log(2d + 1) and mlog q. See the table below for more details. Apparently the signature size of our scheme is a little larger than the other general lattice-based schemes in ideal lattices because of an extra parameter t.
2) IMPROVED PARAMETERS
From Table 1 , we can see the sizes of the sk, pk and signature in our scheme typically rely on the parameter n. Notice that our scheme doesn't use module lattices or any other compression techniques. If we utilize compression method of [10] , the signature length is small enough to use in practice. Ducas et al. [10] presented the Module-SIS problem, where k, l ≥ 1 (k, l ∈ Z) and R q = Z q [x]/(x n + 1) (they choose k = l = 4, n = 256 which is similar with the ring case k = l = 1 and n = 1024) to ensure the same security with 256 bits. Our construction is actually based on the case k = l = 1. Ultimately, the signature length is 16448 bits which is small enough, and the approximate value of pk is 2 13.5 bits.
2) IMPROVED PARAMETERS
We state any method which can reduce the size of parameter n under a certain security must reduce the sizes of the sk, pk and signature in our scheme.
3) THE COMPARISONS
The size of our scheme is clearly larger than SKM based on discrete logarithm problem. That is because lattice-based schemes basically need choose a large parameter to ensure security. Thus we don't give a contrast of sizes for those parameters anymore.
3) THE COMPARISONS
Additionally, since SDVS schemes [20] , [22] are proved the security in standard model which include more complex operations, here we only show comparable parameters except repetition in the following table with them.
3) THE COMPARISONS
Actually, in SDVS schemes Wang et al. [19] , Li et al. [20] , and Boyen [21] must choose large parameters to use preimage sampling function and Bonsai trees with Gaussian sampling. For example, they need to choose m 2n, which result in large signature size. In addition, we know that as signature size increases, the repetition M also increases with Gaussian sampling (see [11] ). Since our scheme is based on R−SIS assumption with uniform sampling, our results of signature size and repetition are better than others.
IV. CONCLUSION AND FURTHER WORK

Conclusion:
In this paper, according to the first SDVS scheme (SKM), we show an efficient lattice-based designated verifier signature. Our scheme has shorter signature size and lower repetition compared with other known lattice-based SDVS schemes.
Conclusion:
Further Work: We are certain that the sizes of parameters in our scheme can be as short as existing lattice-based ones. However, there are several meaningful points that need to be focused on in the design aspect.
Conclusion:
1) The generations of pk for Alice and Bob are a little different, A T S a mod q = Y a , AS b mod q = Y b respectively. We want to design them in the same form if we can.
Conclusion:
2) The definition of strong designated verifier scheme is only qualified in SKM and ours. The privacy of signers identity (non-delegate-ability) is also a meaningful definition SDVS (see [9] ). We find the latter is actually show a description of witness indistinguishable of knowledge for the signer. In the next stage we will constructs a lattice-based witness indistinguishable of knowledge protocol to reach the aim. 3) If the above failed, we continue to explore new frameworks to design SDVS. And we try to give a proof that one SDVS based on a combination of a signature protocol and signcryption can not possibly satisfy the above requirements.
APPENDIX
We show the acceptation probability and repetition functions in Fig. 1 . Without loss of generality, we denote x and y represent independent and dependent variables respectively. We can see that the probability y is decreased first, and then increase with increased x (repetition is opposite). If you just see it from probability and repetition, the value of x is as bigger as better. And in that case, probability and repetition are close to 1. Nonetheless, the size of our signature increases with the increase of variable x. The expression can be simplified log(2 2055 x − 2 5 ). Of course, people want to x, the smaller the better, in order to shorten the size. For above reasons, we must make a trade off. So we only consider the part in which y is more than 0.75 and less than 1.5. At this point, x need satisfy condition x ≥ 4 and x = 4 should be most appropriate.
APPENDIX
JIE CAI received the master's degree from the School of Mathematics, Shandong University, Jinan, China, in 2012, where she is currently pursuing the Ph.D. degree in mathematics and information security. Her research interest includes information security and cryptography, especially post-quantum cryptography based on lattices. 
HAN JIANG


{'paper_id': '57763253', 'title': 'An Efficient Strong Designated Verifier Signature Based on $\\mathcal{R}-$ SIS Assumption', 's2_url': 'https://api.semanticscholar.org/CorpusID:57763253', 'source': 'S2ORC'}