A Digital signature scheme based on Module-LWE and Module-SIS
Huda Naeem Hleeb Al-Jabbari Ali Rajaei Abbas Maarefparvar





Department of Mathematics, Tarbiat Modares University, 14115-134, Tehran, Iran
 h-aljbbari@modares.ac.ir



Department of Mathematics, Tarbiat Modares University, 14115-134, Tehran, Iran

alirajaei@modares.ac.ir
^*Corresponding author


Department of Mathematics and Computer Science, University of Lethbridge, Lethbridge, Canada

abbas.maarefparvar@uleth.ca





[2010]Primary: 94A60,  11T71, 68P25, 06B10 – Secondary: 68T05




§ ABSTRACT 
In this paper,  we present an improved version of the digital signature scheme proposed by Sharafi and Daghigh <cit.> based on Module-LWE and Module-SIS problems. Our proposed signature scheme has a notably higher security level and smaller decoding failure probability, than the ones in the Sharaf-Daghigh scheme, at the expense of enlarging the module of the underlying basic ring.


A Digital signature scheme based on Module-LWE and Module-SIS
    Abbas Maarefparvar
    
=============================================================



§ NOTATIONS


We use bold lower-case letters to denote vectors, e.g., a, and use bold upper-case letters like A to denote matrices. The concatenation of two vectors a and b is denoted by
a || b. 
The uniform probability distribution over some finite set S will be denoted by U(S). If s is sampled from a distribution D, we write s ← D. Logarithms are base 2 if not stated otherwise. 
By default, all vectors will be column vectors, and for a vector v, we denote by v^T its transpose. The boolean operator
statement evaluates to 1 if statement is true, and to 0 otherwise.




 

  

 
 
 
 

§ INTRODUCTION


 
 
 
 
 The advent of quantum computing poses significant challenges to the security of classical digital signature schemes. In anticipation of this paradigm shift, the cryptographic community has turned its focus towards post-quantum cryptography, seeking to develop algorithms that can withstand the computational prowess of quantum adversaries.

 In 2016, the National Institute of Standards and Technology (NIST) initiated a process to solicit, evaluate, and standardize one or more quantum-resistant public-key cryptographic algorithms <cit.>.  The submitted algorithms for the NIST PQC standardization are designed based on various hard computational problems, including lattices, codes, and hash functions, which are currently believed to resist quantum algorithm attacks.  Due to its rich number-theoretic structure, Lattice-Based Cryptography (LBC)  is one of the most promising alternatives among all the candidates. In particular,  most of the algorithms selected for NIST standardization, are lattice-based ones, namely Crystals-Kyber <cit.> (in the part “Public-key Encryption and Key-establishment Algorithms”) and Crystals-Dilithium <cit.> and FALCON <cit.> (in the part  “Digital Signature Algorithms”), see <cit.>. 
  
  
 

 
 






 
 
 
 
 
 
 
 
 
 
 

 

 
 
 

 
 

 §.§ Post-Quantum Alternatives

 Investigating alternative (quantum-resistant) fundamental problems, as in the NIST Post-Quantum Cryptography Competition <cit.>, has led to efficient implementations of various schemes based on the following categories <cit.>.
 
 
 	
  (1)
 	Hash-based cryptography includes cryptographic systems based on hash functions in contrast to number-theoretic schemes. SPHINCS+ <cit.> signature scheme is a representative
 	of that family.
 	
 	
  (2)
 	Code-based cryptography involves cryptographic schemes based on error-correcting
 	codes. Classic McEliece <cit.> encryption schemes belong to this type.
 	
 	
  (3)
 	 Lattice-based cryptography. The example that has perhaps attracted
 	the most interest, not the first example historically, is the Hoffstein–
 	Pipher–Silverman “NTRU” public-key encryption system <cit.>.
 	
 	
 	
  (4)
 	Multivariate cryptography is a type of quantum-safe algorithms based on multivariate
 	polynomials. This includes cryptographic schemes which are based on the difficulty of
 	solving systems of multivariate equations. An example of this family is Rainbow  signature scheme <cit.>.
 	
 	
  (5)
 	Zero-knowledge proof systems are based on zero-knowledge proofs and symmetric key
 	primitives such as hash functions and block ciphers. Picnic signature <cit.> is one scheme of
 	this type.
 	 
 	 
  (6) Supersingular elliptic curve isogeny cryptography is a family of schemes based on
 	 the properties of supersingular elliptic curves and supersingular isogeny graphs. Isogeny-based
 	 schemes use the mathematics of supersingular elliptic curves to create a Diffie–
 	 Hellman-like key exchange, see e.g. SIKE <cit.>.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



 
 
 
 
 Recently, inspired by the Lindner-Pikert cryptosystem <cit.>, Sharafi and Daghigh <cit.> designed a lattice-based digital signature whose security is based on the hardness assumption of the Ring Learning With Errors (Ring-LWE) and the Ring Short Integer Solution (Ring-SIS) problems, see Section <ref> for their definitions. In this paper, using the Module Learning With Errors problem (Module-LWE) and the Module Short Integer Solution problem (Module-SIS) we give some improvements to the Sharafi-Daghigh signature scheme. In particular, we show that using the Module-LWE/SIS would significantly increase the security of the algorithm. In addition, applying some implementation considerations we achieve much shorter public key and signature sizes than the ones in <cit.>.
 
 
 
 
 


























§ LATTICE-BASED CRYPTOGRAPHY
 


The study of lattices, specifically from a computational point of view,
was marked by two major breakthroughs: the development of the LLL 
lattice reduction algorithm by Lenstra, Lenstra, and Lovász in the early
80s <cit.>, and Ajtai's discovery of a connection between the worst-case and
average-case hardness of certain lattice problems in the late 90's <cit.>. Recently, lattice-based cryptography has received much attention from cryptographers and a comprehensive
background on hard problems and security reductions exists. In this section, we introduce some basic notions in lattice-based cryptography and present some fundamental computational hard problems in this area. 



	
	
	









 
For   d ≥ 1 integer, a d-dimensional lattice ℒ is a discrete subgroup of ℝ^d. A basis of the lattice ℒ is a set B={b_1,…,b_n}⊆ℝ^d such that b_i's are linearly independent vectors in ℝ^d and all their integer combinations form ℒ:

    ℒ(B)=ℒ(b_1,…,b_n)={∑_i=1^n c_i b_i   :   c_i ∈ℤ,  ∀ i=1,…,n }.




The integers d and n are called  dimension and rank of the lattice ℒ, respectively (Note that n ≤ d). If n=d, the lattice ℒ is called full rank. Throughout the paper, we only
consider the full-rank (n-dimensional) lattices in ℝ^n.








	A lattice basis B is not unique. For a lattice ℒ   with basis B, and for every unimodular
	matrix U∈ℤ^n × n (i.e., one having determinant ± 1), B.U is also a basis of ℒ(B).
	







The determinant det(ℒ) of  a lattice ℒ is |det(B)| for any basis B of ℒ. 



 
The dual (sometimes called reciprocal) of a lattice ℒ⊆ℝ^n is defined as 

    ℒ^⊥:={w : <w,ℒ> ⊆ℤ},

i.e., the set of points whose inner products with the vectors in ℒ are all integers. It is straightforward to 
that ℒ^⊥ is a lattice. 





	For a lattice , the minimum distance of  is the length of a shortest lattice element:
	
    λ_1():= min_v ∈∖{ 0 } ||v||,

	where ||.|| is the Euclidean norm. In general, we define λ_i()=r, if 
	r is the smallest value such that  
	has i independent vector of norm at most r.

Since a lattice  is an additive group, we have a quotient group ℝ^n/ with cosets as follows.

    c+={ c+v :v ∈} .






	For a lattice , the minimum distance of  is the length of a shortest lattice element:
	
    λ_1():= min_v∈∖{ 0 } ||v||,

	  where ||v|| is the Euclidean norm of v=(v_1,…,v_n), i.e., ||v||=√(∑_i=1^n v_i^2).







 §.§ Computational hard problems on lattices

The shortest vector problem (SVP) and the closest vector problem (CVP) are two fundamental problems in lattices and their conjectured intractability is the foundation for a large number of cryptographic applications of lattices.
 
For a lattice ℒ with basis B, the Shortest Vector Problem (SVP) asks to find a shortest nonzero lattice vector, i.e., a vector v∈ℒ(B) with ||v||=λ_1((B)). In the γ-approximate SVP_γ, for γ≥ 1, the goal is to find a shortest nonzero lattice vector v∈ℒ(B) \{0} of norm at most ||v|| ≤γ. λ_1(ℒ(B)).



 
For a lattice ℒ with basis B and a target vector t∈ℝ^n, the Closest Vector Problem (CVP) asks, to find a vector v∈ℒ(B) such that || v-t || is minimized. In the γ-approximate CVP_γ, for γ≥ 1, the goal is to find a lattice vector v∈ℒ  such that || v-t || ≤γ . dist(t,ℒ(B)) where

    dist(t,ℒ(B))=inf{|| w-t ||   :  w∈ℒ(B) }.





	One can show that SVP and CVP and their γ-approximate versions are NP-hard problems, see <cit.> for a survey on this subject.



Today, the approximation problems for lattice cryptography are more important. Hence, we first pose the Approximate Shortest Vector Problem (SVP_ γ).

	For a n-dimensional lattice =(B), find a nonzero vector v ∈ such that ||v|| ≤γ(n) λ_1().

For several cryptosystems, there exist secure assuming proofs for the hardness of particular lattice problems. But there is no proof for search version of SVP_ γ. Instead, decision version of approximate-SVP can be proved.


	For a basis B with an n-dimensional lattice
	= (B) such that either λ_1() ≤ 1 or λ_1() 
	> γ(n), find out which is the case. 



Now we define Approximate Shortest Independent Vectors Problem (SIVP_γ).

	Let = (B) be a full-rank n-dimensional lattice, where B is its basis. Then output a set S={ s_i }⊆ of n linearly independent lattice elements such that for all i, ||s_i|| ≤γ(n) λ_1().



	Let  be a lattice and x a traget point,  Closest Vector Problem (CVP) asks for finding the lattice point closest to the target.

















 §.§ Learning With Errors (LWE)
 

A fundamental problem in lattice-based cryptography is the Learning with
Errors problem (LWE).
The seminal work of Regev <cit.> establishes reductions from standard
problems such as SVP in general lattices to LWE, suggesting that
LWE is indeed a difficult problem to solve. In particular, the ability to solve LWE
in dimension n implies an efficient algorithm to find somewhat short vectors in
any n-dimensional lattice. LWE is parameterized by positive integers n and q and an error distribution χ over ℤ, which is usually taken to be a discrete Gaussian of width α∈ (0,1).


	For a vector s∈ℤ_q^n called the secret, the LWE distribution A_s,χ over ℤ_q^n ×ℤ_q is sampled by choosing a∈ℤ_q^n uniformly at random, choosing e ←χ, and outputting (a,b=<s,a>+e  mod  q), where <s,a> denotes the inner product of the vectors s and a.


Search and decision are two main types of the LWE problem. The first case is to find the secret given LWE samples, and the second case is to distinguish between LWE samples and uniformly random ones.

 
	(Search-LWE_n,q,χ,m).
	Suppose m independent samples (a_i,b_i)∈ℤ_q^n ×ℤ_q are drawn by using A_s,χ for a uniformly random s∈ℤ_q^n (fixed for all samples), find s.



 
	(Decision -LWE_n,q,χ,m).
	Given m independent samples (a_i,b_i) ∈ℤ_q^n ×ℤ_q where every sample is distributed according to either A_s,χ for a uniformly random s∈ℤ_q^n (fixed for all samples), or the uniform distribution, distinguish which is the case (with non-negligible advantage).











The concrete and asymptotic hardness of theLWE has recently been surveyed in <cit.>. In particular, the hardness of the LWE can be reduced to the approximate SVP in the worst case. 



 §.§ Ring-LWE
 


The Ring Learning With Errors problem (Ring-LWE) is a variant of the Learning With Errors problem (LWE) that was introduced by Lyubashevsky et al. in <cit.> to achieve faster and more efficient cryptographic schemes. Like LWE, the security of Ring-LWE is based on the hardness of solving certain lattice problems in the worst case, even with quantum computers. The specific lattice problem that underlies Ring-LWE is the approximate Shortest Vector Problem (SVP) on ideal lattices, which are special types of lattices that have an algebraic structure related to the ring of integers of a number field.

Let K be a number field, 𝒪_K its ring of integers, and q ≥ 2 a rational integer. The search variant of Ring-LWE with parameters K and q consists in recovering a secret s ∈𝒪_K^∨/q𝒪_K^∨ from arbitrarily many samples (a_i,a_i.s+e_i), where 

    𝒪_K^∨={x ∈ K  |  Tr_K/ℚ(xy) ∈ℤ,  ∀ y ∈𝒪_K}

 denotes the dual of 𝒪_K (by Tr_K/ℚ(a) we mean the trace of a ∈ K over ℚ), each a_i is uniformly sampled in 𝒪_K/q 𝒪_K and each e_i is a small random element of K_ℝ:=K ⊗_ℚℝ. The decision variant of Ring-LWE consists in distinguishing arbitrarily many such pairs for a common secret s chosen uniformly random in 𝒪_K^∨/q 𝒪_K^∨, from uniform samples in 𝒪_K^∨/q𝒪_K^∨× K_ℝ/q 𝒪_K^∨ <cit.>. 



	 The ring R=𝒪_K is typically taken to be a power-of-two cyclotomic ring, i.e., R=ℤ[ζ_n] where ζ_n is a primitive n^th-root of unity for  n=2^k a power of 2. This has led to practical implementation advantages and a simpler interpretation of formally defined Ring-LWE, see <cit.>
 for more details on this subject.





Ring-LWE is characterized by three items, a ring R of degree n over ℤ, a positive integer modulus q defining the quotient ring R_q:=R/qR, and an error distribution χ over R. An “error rate" α < 1 relative to q appears if R is a cyclotomic ring, and χ is a kind of discretized Gaussian in the cannonical embedding of R.

 
	(Ring-LWE distribution).
	For an s ∈ R_q called the secret, the Ring-LWE distribution A_s,χ over R_q × R_q is sampled by choosing a ∈ R_q uniformly at random, choosing e ←χ, and outputting (a,b=s.a+e  mod  q).


 
	(The Ring-Learning With Errors Problem, decisional version). Let R denote the ring ℤ[X]/<X^n+1> for n a power of 2, and R_q be the residue ring R/qR. The decisional Ring-Learning With Errors problem, DRLWE_m,q,χ, is as follows: for a uniform random secret s ←𝒰(R_q), and given m samples either all of the form (a,b=s.a+e  mod  q) where  the coefficients of e are independently sampled from the distribution χ, or from the unifrom distribution (a,b) ←𝒰(R_q × R_q), distinguish which is the case (with non-negligible advantage).




 §.§ Short Integer Solution (SIS) Problem

The short integer solution (SIS) hard problem Starting with Ajtai’s seminal work <cit.>, and has considered as the foundation for collision-resistant hash algorithms, identification schemes, digital
signatures.
Given many uniformly random elements of a certain large finite additive
group, the SIS problem asks to find a sufficiently “short” nontrivial integer combination of them that sums to zero. Indeed, SIS is parameterized by positive integers n and q defining the group ℤ_q^n, a positive real β, and a number m of group elements.

  
	(SIS problem).
	For a matrix A ∈ℤ_q^m × n, where its columns are m uniformly random vectors a_i ∈ℤ_q^n
	find a nonzero integer vector z ∈ℤ^m of norm ||z|| ≤β such that Az=∑_i a_i.z_i=0 ∈ℤ_q^n. 


In a different way, we can see
the SIS problem as an “average-case" short-vector problem on a certain family of so-called
“q-ary" m-dimensional integer lattices, namely, the lattices 

    ℒ^(A)={z ∈ℤ^m   :   Az=0 ∈ℤ_q^n }⊇ q ℤ^m.



	One can also consider an inhomogeneous version of the SIS problem, which is to find a short integer
	solution to 
	Ax=u ∈ℤ_q^n, where A and u are uniformly random and independent. Notice that, disregarding
	the norm constraint, the set of all solutions is the lattice coset 
	ℒ_u^(A):= c+ ℒ^(A), where c ∈ℤ^m is an
	arbitrary (not necessarily short) solution. It is not hard to show that the homogeneous and inhomogeneous
	problems are essentially equivalent for typical parameters.




 §.§ Ideal Lattices and Hardness of Ring-SIS


It is proved that R-SIS and its associated cryptographic functions are as hard as certain lattice
problems in the worst case, similarly to SIS. However, the underlying lattice problems are specialized to
algebraically structured lattices, called ideal lattices, arising from the ring R . Moreover, the algebraic and
geometric properties of R play a major role to distinguished what kinds of security properties R-SIS can be expected to
have, and as sequence in the quantitative strength of the underlying worst-case guarantee.


	An operator is called coefficient embedding if each z ∈ℤ[X]/<f(X)> associates with the n-dimensional integer vector of coefficients of its canonical
	representative in ℤ[X].


	An ideal of a commutative ring R is an additive subgroup I ⊆ R such that is also closed under multiplication.This multiplicative closure means that ideal lattices have
	geometric symmetries that lattices do not have in general.

For example, under the coefficient embedding of ℤ[X]/<X^n-1> an ideal corresponds to a cyclic lattice in ℤ^n.
 
	(Ideal lattices).
	An ideal lattice is simply a lattice corresponding to an ideal in R under some fixed choice of
	geometric embedding such as the coefficient or canonical embedding.


	For the ring R=ℤ[X]/<X^n-1> and other appropriate parameters, Micciancio proved that
	the function Az in definition 2.18 is one-way. The concurrent and independent works of Peikert and Rosen <cit.> and Lyubashevsky
	and Micciancio <cit.>, published in 2006, showed that the function Az over 
	R=ℤ[X]/<X^n-1>
	turns out not to be collision resistant. the same works in <cit.> showed that over appropriate integral
	domains R, the function Az is indeed collision resistant.


 
	(Tighter approximation factors from number fields).
	Subsequent work by Peikert and Rosen <cit.>
	generalized the above results, demonstrating that R-SIS is at least as hard as worst-case SVP
	on ideal lattices
	in R, where R= O_K is the ring of algebraic integers in any number field K . Notice that the approximation
	factor for the underlying SVP
	problem can be as small as 
	γ=O(√(log n)) in certain families of number
	fields. This work revealed how the discriminant of the number field—essentially, the determinant of R under
	the canonical embedding-controls the worst-case approximation factors.









 §.§ Discrete Gaussians

Many modern works on lattices in complexity and cryptography rely on Gaussian-like probability distributions
over lattices, called discrete Gaussians. Here we recall the relevant definitions. 


 
	For any positive integer n and real s>0, which is taken to be s=1 when omitted, define the
	Gaussian function ρ_s:ℝ^n →ℝ^+ of parameter (or width) s as 
	
    ρ_s(𝐱):=exp(-π ||𝐱||^2/s^2)=ρ(𝐱/s).


Note that ρ_s is invariant under rotations of ℝ^n, and that ρ_s(𝐱)=∏_i=1^n ρ_s(x_i) for any vector 𝐱=(x_1,x_2,…,x_n) ∈ℝ^n.

The (continuous) Gaussian distribution D_s of parameter s over ℝ^n is defined to have probability density
function proportional to ρ_s, i.e., 

    f(𝐱):=ρ_s(𝐱)/∫_ℝ^nρ_s(𝐳)d𝐳=ρ_s(𝐱)/s^n.


For a lattice ℒ and a positive real s >0, the discrete Gaussian distribution D_ℒ,s over ℒ with parameter s
is the probability distribution having support ℒ that assigns a probability proportional to ρ_s(𝐱)
to each 𝐱∈ℒ. For ℒ=ℤ^n, it is easy to see (by orthonormality of its standard basis) that the discrete
Gaussian D_ℤ^n,s is simply the product distribution of n independent copies of D_ℤ,s. There are efficient
algorithms for sampling from a distribution within negligible statistical distance of D_ℤ,s, given any s>0, see e.g. <cit.>; for arbitrary s there is a rejection sampling algorithm, and for small s one can compute
a close approximation to the cumulative distribution function. See <cit.> for more details. 











 §.§ Polynomials and NTT
 
In general, fast quasi-logarithmic algorithms exist for polynomial
multiplication, like Nussbaumer, Karatsuba, or Schoolbook
multiplication; but past research shows that the Number Theoretic Transform (NTT) is a
very suitable way to implement polynomial multiplication on various platforms, especially for large
dimensions n;  the implicit usage of the NTT allows for memory efficient in place computation, and no big temporary data structures are required. Here we just describe
the basic definition and refer to <cit.>  for details on the efficient implementation of the NTT. Also basic mechanism to protect the NTT and arithmetic of lattice-based schemes can be
found in <cit.>.




The main mathematical objects that are manipulated in our digital signature scheme, are polynomials in R_q:=ℤ_q[X]/<X^n+1>. For a polynomial f ∈ R_q, where f:=∑_i=0^n-1 f_i X^i we denote by f_i the i-th coefficient of f for all i ∈{0,1,…, n-1 }. Addition or subtraction of
polynomials in R_q (denoted as + or -, respectively) is the usual coefficient-wise addition or subtraction, such that for f=∑_i=0^n-1 f_i X^i ∈ R_q and g=∑_i=0^n-1 g_i X^i ∈ R_q we get f± g=∑_i=0^n-1( f_i ± g_i  mod  q ) X^i. 


With the NTT, a polynomial multiplication for elements in R_q can be performed
by computing h=NTT^-1( NTT(f) o NTT(g) ) for f,g,h ∈ R_q. The o operator denotes coefficient-wise
multiplication of two polynomials f,g ∈ R_q such that fog=∑_i=0^n-1(f_i.g_i  mod, q ) X^i. The NTT defined in R_q can be implemented very efficiently if n is a power of two and q is a prime for which it holds that q ≡ 1 (mod  2n). This way a primitive n-th root of unity ω and its square root γ=√(ω) mod  q exist. By multiplying
coefficient-wise by powers of γ before the NTT computation and after the reverse transformation by powers
of γ-1 mod q, no zero padding is required and an n-point NTT can be used to transform a polynomial with
n coefficients.


For a polynomial g=∑_i=0^n-1 g_i X^i ∈ R_q we define 

    NTT(g):=ĝ=∑_i=0^n-1ĝ_i X^i,

where 

    ĝ_i=∑_j=0^n-1γ^j g_j ω^ij mod  q,

where ω is an n-th primitive root of unity and γ=√(ω) mod  q. The computation of NTT^-1 is essentially the same as the computation of NTT, except that it uses ω^-1 mod  q, multiplies by powers of γ^-1 mod  q after the summation, and also multiplies each coefficient by the scalar n^-1 mod  q so that

    NTT^-1(ĝ)=g=∑_i=0^n-1 g_i X^i,

where

    g_i=( n^-1γ^-i∑_j=0^n-1ĝ_j ω^-ij)  mod  q.



	Note that we define the x  mod  q operation for integers x,q to always produce an output in the range [0,q-1].
	Unless otherwise stated, when we access an element f_i of a polynomial f ∈ R_q we always assume that a_i is
	reduced modulo q and in the range [0,q-1].






 §.§ Module-LWE

The Module Learning With Errors problem (Module-LWE) is a generalization of the Ring Learning With Errors problem (Ring-LWE) that allows for more flexibility and efficiency in lattice-based cryptography <cit.>.  Module-LWE is based on the hardness of finding small errors in linear equations over modules, which are collections of ring elements with a common structure. Module-LWE can be seen as a way of interpolating between LWE and Ring-LWE, where the module rank (the number of ring elements in each module) determines the level of security and performance. In particular, Ring-LWE is a special case of Module-LWE with module rank 1 <cit.>.






In order to give the formal definition of the Module-LWE, we have to fix some notations. Similar to the Ring-LWE, let K be a number field of degree n, R be the ring of integers of K, R^∨ be the dual of R, as defined in (<ref>), and q ≥ 2 be integer. Also let K_ℝ:=K ⊗_ℚℝ,  𝕋_R:=K_ℝ/R^∨, R_q:=R/(qR) and R_q^∨:=R^∨/(qR^∨).




 
	(Module-LWE distribution, statement from <cit.>) Let M:=R^d. For s∈ (R_q^∨)^d and an error distribution ψ over K_ℝ, we sample  the module learning with error distribution A_d,q,s,ψ^M over (R_q)^d ×𝕋_R^∨ by outputting (a, 1/q <a,s>+e   mod   R^∨) where a ← U((R_q)^d) and e ←ψ. 
	




 
	(Decision/Search Module-LWE problem, statement from <cit.>) Let Ψ be a family of distributions over K_ℝ and D be distribution over R_q^∨. For	
	M=R^d,  the decision module learning with errors problem Module-LWE_m,q,Ψ^(M) entails distinguishing m samples of U((R_q)^d) ×𝕋_R^∨ from A_q,s,ψ^(M) where s← D^d and ψ is an arbitrary distribution in Ψ.




Let [K:ℚ]=r_1+2r_2, where r_1 and r_2 denote the number of real and complex (non-real) embedding of K, respectively.	One can show that  
	
    K_ℝ≃	H:={x∈ℝ^r_1×ℂ^2r_2  :   x_i=x_i+r_2  ,   i=r_1+1, …, r_1+r_2},

where x_i+r_2 denotes the complex conjugate of x_i+r_2. Hence the distribution over K_ℝ are sampled by choosing an element of the space H according to the distribution and mapping back to K_ℝ via the isomorphism (<ref>), see <cit.>. 



Module-LWE comes with hardness guarantees given by lattice problems based on a certain class of lattices, called  module lattices. 


  In this case, solving the approximate SVP on module lattices
for polynomial approximation factors would permit solving Module-LWE (and thus Ring-LWE) efficiently <cit.>.


    Module-LWE is a promising alternative to Ring-LWE that can resist potential attacks that exploit the algebraic structure of the rings <cit.>. Therefore, Module-LWE may provide a higher level of security than Ring-LWE, while still being more efficient than plain LWE. Moreover, Module-LWE allows for more fine-grained control over the security level by adjusting the module rank, which is not possible with efficient Ring-LWE schemes. Furthermore, Module-LWE implementations can be easily adapted to different security levels by reusing the same code and parameters <cit.>.














 §.§ SIS, Ring-SIS, and Module-SIS problems

The Short Integer Solution (SIS) problem, introduced by Ajtai <cit.>, serves as one of the foundations of numerous lattice-based cryptographic protocols. The SIS problem is to find a short nonzero solution z∈ℤ^m, with 0 < ||z || ≤β, to the homogeneous linear system Az≡0 mod  q for uniformly random A∈ℤ^m × n, where m,n,q denote positive integers and β∈ℝ. Inspired by the efficient NTRU encryption scheme <cit.>, Micciancio <cit.> initiated an approach that consists of changing the SIS problem to variants involving structured matrices. This approach was later replaced by a more powerful variant referred to as the Ring Short Integer Solution (Ring-SIS) problem <cit.>. There are several reductions from some hard lattice problems to SIS and Ring-SIS, see <cit.>. 
The Module Short Integer Solution (Module-SIS) problem is a generalization of the Ring Short Integer Solution (Ring-SIS) problem that involves finding short vectors in module lattices, which are lattices with a module structure. 
By viewing the rings as modules of rank 1, we can extend the definition of Ring-SIS to Module-SIS and study its hardness and applications.

 
	Let K be a number field with ring of integers R, and R_q:=R/qR where q ≥ 2 is an integer. For positive numbers m,d ∈ℤ and β∈ℝ, the problem Module-SIS_q,n,m,β  is to find z_1,…,z_m ∈ R such that  0<  ||(z_1,…,z_m) || ≤β and ∑_i=1^ma_i.z_i ≡0 mod  q, where  a_1,…, a_m ∈ R_q^d are chosen independently from the uniform distribution.



	Note that N=nd denotes the dimension of the corresponding module lattice and gives the complexity statements for N growing to infinity, where n denotes the extension degree of K over ℚ <cit.>. For the worst-case to average-case reduction from computational hard lattice problems to Module-SIS problems, see <cit.>.












§ OUR CONTRIBUTION

The worst-case to average-case reductions for the module problems
are (qualitatively) sharp, in the sense that there exist converse reductions. This property is
not known to hold in the context of Ring-SIS/Ring-LWE <cit.>. In addition, using these module problems, one could design cryptographic algorithms whose key sizes are notably smaller than similar ring-based schemes, see e.g.  <cit.>.
 
 In this section,  we present an improved version of the digital signature proposed in <cit.> based on Module-LWE and Module-SIS problems. Similar to the Sharafi-Daghigh scheme <cit.>, the structure of our digital signature algorithm is based on the “hash-and-sign” approach and “Fiat-Shamir paradigm” <cit.>. Our contribution to the proposed signature scheme can be summarized as follows:
 
 	
  * Using Module-LWE and Module-SIS problems, instead of Ring-LWE and Ring-SIS respectively,  would increase the security levels at the cost of slightly increasing the key sizes, see Section <ref>.
 	
 	
  * Inspired by some celebrated lattice-based algorithms <cit.>, we generate the public key A from a 256-bits seed ζ as input of a hash function G. Based on this standard technique, instead of n log q bits as in  <cit.>, one needs only 256 bits to store the public key 𝐀.
 	
 	
 	
  * The encode and decode functions (for serializing a polynomial in byte arrays and its inverse) used in <cit.> are the straightforward methods introduced in Lindner-Peikert scheme <cit.>.  In this paper,  as a modification,  we use the NHSEncode and NHSDecode functions given in  NewHope-Simple <cit.>.  This method will decrease  the decoding failure rate significantly, see Sections <ref> and <ref>.
 	
 	
  * Following Crystals-Kyber <cit.> and NewHope <cit.>, we use the centered binomial distribution, instead of the Gaussian one as used in <cit.>, to sample noise and secret vectors in the proposed signature scheme. This gives a  more efficient implementation than <cit.> and increases the security against side-channel attacks.
 
  






§ PROPOSED DIGITAL SIGNATURE


In this section, we present a Module-LWE based version of Sharafi-Daghigh digital signature <cit.>. It must be noted that we only provide a module version of the signature scheme and its efficient implementation would be an interesting challenge for future works. So we will describe each step by pseudocodes, however, one can apply the corresponding auxiliary functions of any Module-LWE based algorithm, e.g. Crystals schemes <cit.>, to gain a test implementation. 




 §.§ Encoding and Decoding functions
  In <cit.> in order to encode a bit array ν=(ν_0,…,ν_n-1) ∈{0,1}^n into a polynomial  v∈ R_q and its inverse, the authors use the following  methods as proposed by Lindner and Peikert <cit.>:

    v=Encode(ν_0,…,ν_n-1)=∑_i=0^n-1ν_i.⌊q/2⌋ . X^i, 
       μ=(μ_0,…,μ_n-1)=Decode(∑_i=0^n-1 v_i . X^i),   where  μ_i={[                         1 if   v_i ∈[- ⌊q/4⌋,⌊q/4⌋);                         0                otherwise.;                           ].



As mentioned before, one of our contributions is to use different encoding-decoding functions leading to a much lower error rate. We use the NHSEncode and NHSDecode functions introduced in NewHope-Simple <cit.>. Moreover, sampling secret and error polynomials from a binomial distribution enables us to apply the same analysis as NewHope <cit.> to obtain an error rate bounded by 2^-60. In NHSEncode, each bit of ν∈{0,1}^256 is encoded into four coefficients. The decoding function NHSDecode maps from four coefficients back
to the original key bit; 


Take four coefficients (each in the range  {0,…,q-1}), subtract
⌊q/2⌋ from each of them, accumulate their absolute values and set the key bit to 0 if the sum is larger
than q or to 1 otherwise. See Algorithms 1 and 2 in NewHope-Simple <cit.> for more details.



 §.§ Key Generation
 In order to decrease size of the public key, in comparison to <cit.>, one can use a seed (as input parameter of informal function GenA) to generate uniformly public matrix Â∈ R_q^k × k in NTT domain. To accomplish this, for instance, the key generation algorithms of Crystals schemes <cit.> could be applied. Likewise, the secret and error vectors s, e∈ R_q^k could be sampled from a seed. Moreover, in order to ease implementation, s and e would be drawn from the binomial distribution with standard derivation η instead of the Gaussian one. Following Crystals-Dilithum <cit.>, we use the notation S_η to denote the subset of R_q consisting of all polynomials whose coefficients have size at most η. Also, we denote the corresponding informal function by GenSE. The pseudocode for the key generation is described in Algorithm <ref>. 





 §.§ Signing
 In order to generate a signature σ assigned to a message M, the signer first uses a collision-resistant hash function, denoted by CRH, and computes the hash of M, say μ. Then using a random 256-bits coin r, as input value of the function GenSE, she generates the vectors e_1,e_2 ∈ R_q^k and e_3,e_4 ∈ R_q from a binomial distribution of parameter η. The signature σ would contain the following four components 

    z_1   =Ae_1+e_2 ∈ R_q^k, 
    
    z_2   =Pe_2+e_4 ∈ R_q, 
    
    z_3   = APe_1+e_3+NHSEncode(μ) ∈ R_q, 
    
    h   =CRH(μ || CRH(NHSDecode(Ase_2))).


 (Recall that the functions NHSEncode and NHSDecode are introduced in Section <ref> and s denotes the secret key). The pseudocode for the signing step is described in Algorithm <ref>. 




 §.§ Verification
 As described in Algorithm <ref>, using the public key P, the verifier accepts σ=(z_1,z_2,z_3,h) as a valid signature of the message M if and only if both of the following conditions hold:

	
  (1)
NHSDecode(z_2+z_3-Pz_1)=CRH(M),
	
  (2)
	h=CRH(CRH(M) || CRH(NHSDecode(z_2)).
 



	





	



	


  
	Note that the publick key (A,P) has size 256+knlog q bits or equivalently its size would be 32+knlog q/8 bytes. Likewise, the secret key s∈ R_q^k has size knlog q/8 bytes, and the size of the signature σ is (k+2)nlog q/8+32 bytes. The corresponding sizes for each parameter set are given in Table <ref>.




 §.§ Decoding failure probability
  Similar to computations as in <cit.>, we have

    z_2+z_3-Pz_1   =Pe_2+e_4+APe_1+e_3+NHSEncode(μ)-P(Ae_1+e_2) 
       =NHSEncode(μ)+(e_3+e_4), 
    
    	z_2   =(As+e)e_2+e_4=Ase_2+(ee_2+e_4).


Hence applying NHSDecode on the above terms, the verifier obtains respectively μ and Ase_2 as long as the error terms e_3+e_4 and ee_2+e_4 have been sufficiently small sampled. But following NewHope <cit.> all the polynomials e,e_1,e_2,e_3,e_4 are drawn from the centered binomial distribution ψ_η of parameter η=16. Since the decoding function NHSDecode maps from four coefficients to one bit, the rounding error for every 4-dim chunk has size at most q/4+4. As mentioned in NewHope-Simple <cit.>, one can use the same analysis as in NewHope-USENIX <cit.> to conclude that the total failure rate in encoding-decoding process is at most 2^-60. In Section <ref>, we will choose the parameter sets for the proposed scheme to achieve this failure probability.
(Note that the upper bound of the failure rate in Sharafi-Daghigh scheme <cit.> is 2^-40). 


 


§ UNFORGEABILITY IN RANDOM ORACLE MODEL
 

The proposed digital signature scheme is a module-LWE-based version of the Sharafi-Daghigh algorithm <cit.>. Hence replacing ring-based hard problems with corresponding module-based ones, one can transmit the security proof in <cit.> to the module-based setting. Similar to <cit.>, the security of our proposed digital signature in the UF-CMA model (Unforgeability under Chosen Message Attack[This means that an adversary who is given a signature for a few messages of his choice should not be able to produce a valid signature for a new message  <cit.>.]) arises from two hard assumptions, namely the decision Module LWE  and the combined hardness of Module-SIS with the hash function H. By the decision Module LWE assumption, which  denoted as Adv_k,η^MLWE in Theorem <ref> below, the public key (A,P) (a module-LWE sample) is indistinguishable from the pair (A^',P^') chosen uniformly at random. This guarantees the security against the key recovery attack. In order to prove the security against chosen message attacks (UF-CMA), let the adversary get the public key (A,P) and successfully produce a signature σ^'=(z_1^',z_2^',z_3^',h^') of a new message M which is valid according to  the Verification Algorithm <ref>.
In particular, the adversary would be able to find  z_2^'∈ S_η such that

    H(NHSDecode(z_2^'))=H(NHSDecode(Ase_2)).
  
 






Therefore to create a forged signature of the message M, the adversary will encounter two challenges; he has to either break the hash function H or find a nonzero z ∈ S_η^1 for which A.(z-se_2)=0  mod  q, i.e., find a solution of the Module-SIS problem given in Definition <ref> (with m=1 and d=k^2). This challenge is the aforementioned combined hard problem denoted as Adv_k,η^H-MSIS (Note that as in Crystals-Dilithium, the infinity norm, rather than the Euclidean norm, has been considered to avoid the trivial solution (q,0,…,0)^T for the underlying Module-SIS problem). More formally, following Crystals-dilithium <cit.>, the UF-CMA security of the proposed signature scheme in the Random Oracle Model (ROM) can be stated as follows.

 



 
	Assume that H:{0,1}^* → R_q is a cryptographic hash function modeled as a random oracle. If there exists an adversary 𝒜 (who has classical access to H) that can break the UF-CMA security of the proposed signature, then there exist also adversaries ℬ and 𝒞 such that
	
    Adv^UF-CMA(𝒜) ≤Adv_k,η^MLWE(ℬ) + Adv_k,η^H-MSIS(𝒞),

where

    Adv_k,η^MLWE   :=|Pr[b=1| A← R_q^k × k; P← R_q^k; b ←𝒜(A,P)] 
       -Pr[b=1 | A← R_q^k; s← S_η^1; e← S_η^1; b ←𝒜(A,As+e)]|,

and

    Adv_k,η^H-MSIS=
       Pr[0<||z||_∞≤η ∧ H(M||Az)=h^' | A← R_q^k × k; (z,h^',M) ←𝒜^|H(.)>(A) ].





Although the above reduction is non-tight, yet it can be used to set the parameters, see <cit.>. In addition, we have to consider the security in the quantum random oracle model (QROM). As stated in Crystals-Dilithium, although the above reduction does not transfer over the quantum setting, but the assumption Adv_k,η^H-MSIS is tightly equivalent, even under quantum reductions, to the UF-CMA security of the proposed signature. Hence, in the above theorem, one can assume that the adversary 𝒜 has a quantum access to the hash function H, see  <cit.> for more details.










§ CHOOSING PARAMETERS AND SECURITY ESTIMATION
 




We use the ring R_q=ℤ_q[x]/(x^n+1) with n  a power-of-two, a favorable choice by many Ring/Module-LWE based schemes. We use the polynomial ring of degree n=256, for every parameter set, as the basic block of the Module-LWE problem. Similar to NewHope Scheme<cit.> we choose the modulus q=12289 and sample the Module-LWE secret and error terms by the centered binomial distribution ψ_η of parameter η=16. Note that q ≡ 1   (mod  n) which  enables the use of NTT over the ring R_q.
Also it must be noted that due to replacing the Ring-LWE with Module-LWE, we have decreased the ring dimension 1024 in NewHope <cit.> to 256,  yet we use the same modulus and the same sampling distribution as in NewHope to achieve the decoding failure probability 2^-60. In other words, since we have used the encoding-decoding functions introduced in the NewHope-Simple algorithm, using the same modulus q=12289, the same binomial distribution ψ_16 and the ring dimensions 256k^2 (with k=2), ensures us that the upper bound 2^-60, as in NewHope <cit.>, works also for the failure probability in the proposed scheme, see Section <ref>. Moreover, using these parameters, we can use the same security analysis as in NewHope-USENIX <cit.>, and in comparison to Sharafi-Daghigh scheme <cit.>, we obtain much smaller failure probability and higher security levels at the cost of increasing the modulus q, see Table <ref>.


	Note that increasing the parameter k will increase the security level but makes the scheme too inefficient. So we have determined only one set of parameters, whereas finding different encoding-decoding functions to achieve an appropriate failure rate with a smaller modulus q, might be an interesting challenge for future works. 




 §.§ Security Estimation
 

As mentioned before, the security of the proposed digital signature scheme is based on the hardness of Module-LWE and Module-SIS problems. Any MLWE_k,D instance for some distribution D can be viewed as an LWE instance of dimension (nk)^2. Indeed the underlying MLWE_k,D problem for the proposed digital signature can be rewritten as finding vec(s), vec(e) ∈ℤ^nk from (rot(A), vec(P)) where (A,P) is the public key as in Algorithm <ref>, vec(.) maps a vector of ring elements to the vector obtained by concatenating the coefficients of its coordinates, and rot(A) ∈ℤ_q^nk × nk is obtained by replacing all entries a_ij∈ R_q of A by the n × n matrix whose z-the column is vec(x^z-1.a_ij).
Similarly, the attack against the MSIS_k,η instance can be mapped to a SIS_nk,η instance by considering the matrix rot(A) ∈ℤ^nk × nk
, see <cit.> for more details.


In order to do security estimation, we will not consider BKW-type attacks <cit.> and linearization attacks <cit.>, since based on our parameter set, there are only “(k+1)n” LWE samples available, see <cit.>. Hence the main challenge is security analysis against the lattice attacks. All the best-known lattice attacks are essentially finding a nonzero short vector in the Euclidean lattices, using the Block-Korkine-Zolotarev (BKZ) lattice reduction algorithm <cit.>. The algorithm BKZ proceeds by reducing a lattice basis using an SVP oracle in a smaller dimension b. The strength of BKZ increases with b, however, the cost of solving SVP is exponential in b <cit.>. It is known that the number of calls to that oracle remains polynomial. Following NewHope <cit.>, we ignore this polynomial factor, and rather evaluate only the core SVP hardness, that is the cost of one call to an SVP oracle in dimension b, which is clearly a pessimistic estimation, from the defender's point of view.



There are two well-known BKZ-based attacks, usually referred to as
primal attack and dual attack. As explained in Crystals-Dilithium <cit.>, the primal attack for the proposed scheme is to find a short non-zero vector in the lattice

    Λ={x∈ℤ^d   :  Mx=0  mod  q},

where M=(rot(A)_[1:m] | I_m | vec(P)_[1:m]) is an m × d matrix with d=nk+m+1 and m ≤ nk. By increasing the block size b in BKZ, for all possible values m, the primal attack solves the SVP problem in the lattice Λ.

The dual attack consists in finding a short non-zero vector in the lattice

    Λ^'={(x,y) ∈ℤ^m ×ℤ^d   :  M^T x+y=0  mod  q},

where M=(rot(A))_[1:m] is an m × d matrix  with m ≤ d=nk. Similar to the primal attack, the dual attack solves the SVP problem in the lattice Λ^', by increasing the block size b in BKZ, for all possible values m. 

According to the parameters n,k,q,η, we have used the core SVP hardness methodology and the cost estimation of NewHope-USENIX <cit.> against the primal and dual attacks, as presented in Table <ref>. 
































§ COMPARISON TO SOME RELATED WORKS



Two of the most celebrated lattice-based signature algorithms are Crystals-Dilithium <cit.> and FALCON <cit.>, selected for
NIST [National Institute of Standards and Technology] Post-Quantum
Cryptography Standardization  <cit.>. Crystals-Dilithium, one of our main references, is based on the Fiat-Shamir with aborts approach <cit.> whose security is based on Module-LWE and Module-SIS problems. As stated in <cit.>, FALCON [Fast Fourier Lattice-based Compact Signatures over NTRU] is a lattice-based signature scheme utilizing the “hash-and-sign” paradigm. FALCON follows the GPV framework, introduced by Gentry, Peikert, and Vaikuntanathan <cit.> and builds on a sequence of works whose aim is to instantiate the GPV approach efficiently in NTRU lattices <cit.> with a particular focus on the compactness of key sizes. There is also another lattice-based digital signature, namely “qTESLA” <cit.>, among the second-round (but not finalist) candidate algorithms in the NIST post-quantum project. qTESLA is a Ring-LWE-based digital signature in which signing is done using hash functions and Fiat-Shamir with aborts technique.


In addition to the above algorithms in the NIST post-quantum project, for comparison, we have tried to consider those digital signatures, including Sharafi-Daghigh scheme <cit.>, BLISS <cit.>, and GLP <cit.>, that are most relevant to the proposed scheme. The comparison results are presented in Table <ref>.











alpha
















