[PDF] degruyter_jmc_jmc-2021-0013 205..214 ++

View - Download degruyter_jmc_jmc-2021-0013 205..214 ++

Previous PDF

Next PDF

Research Article

Javad Sharafi

and Hassan Daghigh*

A Ring-LWE-based digital signature inspired

by Lindner-Peikert scheme https://doi.org/10.1515/jmc-2021-0013 received April 19, 2021; accepted April 24, 2022

Abstract:In this article, we give a digital signature by using Lindner-Peikert cryptosystem. The security of

this digital signature is based on the assumptions about hardness of Ring-LWE and Ring-SIS problems,

along with providing public key and signature of compact(1-1.5 kilobytes)size. We prove the security of

our signature scheme in the Quantum Random Oracle Model. Our cryptanalysis has been done based on methods of Aggarwal et al. and Chen et al. Keywords:lattice-based cryptography, Ring-LWE problem, Ring-SIS problem, Lindner-Peikert crypto- system, digital signature

MSC 2020:81P941 Introduction

The advent of Quantum computing threatens to break a lot of classical cryptographic schemes. This leads to

innovations in public key cryptography that focus on post-quantum cryptography primitives and protocols

resistant to quantum computing threats. Lattice-based cryptography is a promising post-quantum crypto-

graphy family, both in terms of foundational properties and its application to both traditional and emerging

security problems such as encryption, digital signature, key exchange, homomorphic encryption, etc.

The breakthrough work of Ajtai[1

]provides confidence for adopting lattice-based schemes in crypto-

graphy. Ajtai proved that solving NP-hard lattice problems, e.g.,Shortest Vector Problem(SVP), in the

average case is as hard as solving the worst-case assumption. It is conjectured that there is no probabilistic

polynomial-time algorithm that can approximate certain computational problems on lattices within poly-

nomial factors[2]. This is the basis for the security of lattice-based schemes. Based on the Ajtai's works in

the past two decades, great progress has been made in the lattice-based cryptography on various hard

lattice computational problems such asclosest vector problem(CVP),Shortest Independent Vectors Problem

(SIVP),bounded distance decoding(BDD),Shortest Integer Solution(SIS), etc.[2-5].Definition 1.1.Givennlinearly independent vectorsbbb,,,nd12

?...?, thelattice?is defined as ab ab a, nn i11 ??{∣}=+⋯+ ?(1.1) where the set of Bbb,, n1 {}=...is called abasisfor the lattice. The integersnd,are calledrankand dimensionof?, respectively. Ifnd=, then?is called afull rank(orfull dimension)in d ?, which is very common to use in lattice-based cryptography.

Javad Sharafi:Department of Mathematics, University of Kashan, Kashan, Iran, e-mail: Javadsharafi@grad.kashanu.ac.ir

* Corresponding author: Hassan Daghigh,Department of Mathematics, University of Kashan, Kashan, Iran,

e-mail: Hassan@Kashanu.ac.irJournal of Mathematical Cryptology 2022; 16: 205-214Open Access. © 2022 Javad Sharafiand Hassan Daghigh, published by De Gruyter.This work is licensed under the Creative

Commons Attribution 4.0 International License.

Remark 1.2.A lattice basisBis not unique. For a lattice?with basisB, and for every unimodular matrix U nn (i.e., one having determinant1±),BU.is also a basis ofB?().

Due to Regev[6

]a large number of cryptographic constructions based on the lattices are built over the average-caseLearning With Errors(LWE)problem. Definition 1.3.(LWE distribution). Letsbe a vector in q n ?(which is calledsecret). The LWE distribution A s, over qnq ??×is defined by samplinga q n ??uniformly at random and choosingeχ←, then outputting beqasa,, mod()=⟨ ⟩+wheresa,⟨⟩denotes the inner product of vectorssanda. There are two main versions of the LWE problem: thesearch versionwhich isfinding the secret according to the given LWE samples, and thedecision versionwhich is distinguishing between LWE samples and uniformly random samples:

Definition 1.4.(Search-

LWE nqχm,,, ).Itistofindsuniformly randomly, from q n ?, so thatmindependent samples ba, iiqnq ??()?×are drawn fromA s, (sisfixed for all samples).

Definition 1.5.(Decision-

LWE nqχm,,, ). It is to distinguish which of the followings is the case(with non- negligible advantage). mindependent samplesba, iiqnq ??()?×are either distributed according toA s, wheres q n ??uniformly random(fixed for all samples), or they are distributed uniformly. The LWE-based schemes, however, are not particularly efficient because LWE-based schemes inherently give rise to key sizes and/or outputs which are

Oλ˜

2 ()in the security parameterλ. In 2010, Lyubashevsky et al. [7

]introduced theRing-LWE Problemthat is the ring-based analogue of LWE, and proved the hardness of the

related problems. Ring-LWE isparameterized by a ring

Rof degreenover?, a positive integer modulusqthat

defines the quotient ring RRq q =/, and an error distributionχoverR. Typically, one takesRto be a cyclotomicring, and χto be some kind of discrete Gaussian in the canonical embedding ofR.

Definition 1.6.(Ring-LWE distribution). For allsR

q ?called the secret, the Ring-LWE distributionA sχ, overRR qq

×is sampled by choosingaR

q ?uniformly at random, choosingeχ←, and outputting ab sa e q,mod()=+. Definition 1.7.(The Ring-LWE Problem, decision version). Let

Rdenote the ring

X X1 n fornwhich is a power of 2, and R q be the residue ringRq/. Distinguish which of the following is the case(with non- negligible advantage); for a uniform random secret sR q ?()←and givenmsamples; each of them is of the form ab sa e q,mod()=+where the coefficients ofeare independently sampled from distributionχ,or they are from uniform distribution ab R R, qq

Remark 1.8.As it is stated before, due to the particularly nice algebraic structure ofcyclotomic ringsfor

implementation purposes, most proposals opt to work with this kind of rings such as X X1 n forna power of

2. Cyclotomic rings also have the feature that thedecision versionof the Ring-LWE problem in these rings is

hard[8 ], which makes them even more useful for cryptographic applications. We conclude this section by introducing the"Short Integer Solution(SIS)Problem"whose hardness is

needed as a part of security of our proposed scheme.(For the hardness of the SIS problem relative to worst-

case lattice problems, see ref.[3 , Section 4.1.2].)The SIS Problem is parameterized by positive integersnand q, which defines the group q n ?a positive real numberβand a numbermof group elements. Definition 1.9.(The SIS Problem).Givenmuniformly random vectorsa iqn ??forming the columns of a matrix A qn m ,find a nonzero integer vectorz m iii q n

206Javad Sharafiand Hassan Daghigh

Inspired by the ideas behind the"NTRU cryptosystem"[9], Micciancio[10]introduced a compact ring-

based analogue of Ajtai's SIS problem. This analogue has come to be known as the"Ring-SIS Problem"and

is parameterized by a ring Rwhich is often(but not always)taken to be a degree-npolynomial of the form R X fX?[] , a positive integer modulusq, a real norm boundβ0>, and a numbermof samples. Definition 1.10.(The Ring-SIS Problem). Givenmuniformly random elementsaRRq iq ?=/,defining a vector aR q m ?,find a nonzero vectorzR m iii q

Remark 1.11.Ring-SIS and its associated cryptographic functions can be proved at least as hard as certain

lattice problems in theworst case, similar to SIS([3 ], Section 4.3.4).

2 Related works and our contribution

For a long time, lattice-based signatures have been designed so that their security were obtainable only for

inefficiently large parameters, i.e., they were far from practicality, e.g., ref.[11 ], or were, likeGGH[12]and NTRUSign[13]broken due toflaws in the ad-hoc design approaches[14,15]. Though using theideal

lattices, introduced by Micciancio[10], and the related computationally hard problems, such as Ring-SIS

and Ring-LWE, one canfind many promising digital signatures in this area. In particular, the schemes that

use theFiat-Shamirapproach[16]have led to a family of fast signature schemes with reasonable signature

and key sizes[11,17-20]. In general, for building lattice-based signatures, there are two(seemingly distinct)frameworks: one using lattice trapdoors[21 -23]and the other, as mentioned above, through the Fiat-Shamir heuristic, whereas, a strong connection between these two approaches has been recently found, see ref.([24],

Theorem 1.4). In this article, inspiring from the protocol introduced by Lindner-Peikert[25]and using

the Fiat-Shamir paradigm, we present a lattice-based digital signature scheme whose structure is designed

for afixed length message, i.e., we will use thehash and signapproach. Our contribution is astraight

applyingthe Lindner-Peikert scheme[25], which can be seen, to the best of our knowledge, as a novel idea

for constructing digital signature through this primitive. In addition, as we will see in Section 6, we get an

appropriate trade offbetween the security levels and the key sizes, where the security of the proposed

scheme has been estimated by a very pessimistic approach(from the viewpoint of the defender against a

quantum adversary), namely the core SVP hardness, see Section 5.1. Although we cannot claim that the proposed signature is the best one(for a summarized comparison between some similar lattice-based

digital signatures, see Section 6), but one may hope for future improvements on this"naive"framework.

Remark 2.1.From sight of the practicality, the only complexity would be related to implementing performance

of thedecode-encode function,seeDefinition 3.1 , and to thesymmetric primitives, i.e., the hash functions, and

based on this, we expect the proposed scheme has a reasonable implementation speed, whereas we have not yet

implementedthatandwillbedoneinthefutureworks.Also,onecanconsiderthe"Module-LWE"-based version of the proposed signature, to achieve a more(expected)secure one, see Remark 6.2.

3 The proposed digital signature

In 2011, as a generalization of the previous LWE-based cryptosystems such as[6,21]and as an instance of

Micciancio's proposed system in ref.[26], Lindner-Peikert[25]gave a cryptosystem based on LWE and

Ring-LWE problems. The Lindner-Peikert cryptosystem provided smaller keys and ciphertexts by a factor of

about qlogand a concrete security stronger than the previous works(by the convention, the base-2 logarithm is denoted by log).

Ring-LWE digital signature207

In this article, using the Lindner-Peikert cryptosystem[25], we give a Ring-LWE-based digital signature

whose public key/signature sizes lie in the range 1-1.5 kilobytes, along with an easier implementation and a

slightly weaker security than the proposed scheme in ref.[25]. LetR X fX?[] be thecyclotomicpolynomial ring wherefXX1 n ()=+withna power of 2. Other proper- ties of this ring such as its security and cyclotomic polynomials, including degrees n2≠of the mentioned ring, are discussed in detail in ref.[7 ]. Suppose that the following considerations hold:q??is a suffi- ciently large integer modulus for which fx()splits into linear(or very low-degree)factors moduloq; R qZX fX q k andχ e are error distributions overRwhich are concentrated on"small"elements ofR. Hence, the error distributions enable rigorous security proofs(see refs[7]and[25]). LetΣbe a message alphabet, e.g.,Σ0,1{}=. The message encoder and decoder are functions encode R:Σ n q →anddecode R:Σ qn →, such that me qm eRdecode encode mod , for any small enough.(() )+= ?(3.1)

As an example consider an

esuch that for some integer thresholdt1≥, its coefficients as a polynomial inR are all intt,[)-.

Definition 3.1.[25

]Form0, 1{}?and a moduleq,define the functionsencodeanddecodeas follows: mmmqmmmqqencode: 0, 1 , decode: 0, 1

2,ˆ0, ifˆ4,4

1, otherwise.

qq We extend these functions component-wise to vectors. Remark 3.2.Note that in the above method the error tolerance is t q 4

In this protocol, we use a uniformly random

aR q ?that can be generated by a trusted source or it is

chosen by the user. Suppose that the signer(from now on will be calledAlice)wants to sign the message

m and send it to the verifier(from now on will be calledBob). rr χ, k12 ←andmHm¯encode(())=whereHis acollision-resistant hash function. The public key consists of the pair prara R, q12 2 ()=- ?and the secret key isr 2 eχ i e ←,i1, , 4=..., and Computes the valuesC i s as follows: Cpee

C pae e m

Caee, 112
213
324
Note that following Section 3.1 in ref.[25], we takeapm,, Σ n 123
(), where hHmH aredecode, 21
with acollision-resistant hash functionH.(Note that computing the value of decode(are 21
)is meaningful, since are R q21 ?, see Definition 3.1.)

3.1 Verification

Bob accept a quadrupleCCCh,,,

123
()as a valid signature for the messagem(withmHm¯encode(())=)if the following conditions hold: (i)

CaCC Hmdecode

213
()()-+=; note that

208Javad Sharafiand Hassan Daghigh

CaC C pae e m ape ae ae e H m e e¯encode ,

213 13 1224 34

small (3.2) see the relation(3.1 (ii)hHmHω(∣∣())=, whereωCdecode 1 ()=-; note that

Cpeearreeare reeR,

q112211221112 small (3.3) which implies that decode( C 1 -)is meaningful as an element of0, 1 n Therefore, the signature will be verified as long as the"error terms" ee 34
+andre e 112
--are within the error threshold of the function decode(see Definition 3.1); these hold with high probability whenχ e andχ k are sufficiently concentrated.

Remark 3.3.As stated before, the functionHin the above scheme is a collision-resistant hash function. For

implementation, one may useSHAKE-128[27

3.2 Correctness(decoding)

Based on the error terms which areee

34
+andre e 112
--, respectively, in equations(3.2)and(3.3), one can say that the upper bound on the Gaussian parameters ofquotesdbs_dbs41.pdfusesText_41

[PDF] analyse critique rapport de stage exemple

[PDF] taux de fécondité france 2016

[PDF] combien de familles nombreuses en france

[PDF] nombre de personnes agées en france 2016

[PDF] energie d'un photon

[PDF] singulier pluriel ce1 evaluation

[PDF] pluriel des noms ce1 bout de gomme

[PDF] singulier pluriel ce1 lutin bazar

[PDF] séquence singulier pluriel ce1

[PDF] évaluation masculin féminin ce1

[PDF] conversion homme mois homme jour

[PDF] budget jour homme

[PDF] calcul jour homme

[PDF] planning homme jour excel

[PDF] nombre postes capes 2018