Transcription
Lattice Based Cryptography for Beginners– A supplementary note to the following1. Peikert’s Bonn Lecture Slides2. Lyubashevsky, Peikert and Regev:A toolkit for Ring-LWE3. Steinfeld’s Lecture Slides on multilinear mapswith Cryptanalysis of GGH map due to Hu and JiaDong Pyo Chi1,2 , Jeong Woon Choi3 , Jeong San Kim4 and Taewan Kim51Division of General Studies, UNISTdpchi@unist.ac.kr2Department of Mathematics, Seoul National Universitydpchi@snu.ac.kr3Fusion Technology R&D Center, SK Telecomjw choi@sk.com4Department of Applied Mathematics, Kyung Hee Universityfreddie1@khu.ac.kr5Institute of Mathematical Sciences, Ewha Womans Universityaprilsec@ewha.ac.kr
AbstractThe purpose of this lecture note is to introduce lattice based cryptography, which isthought to be a cryptosystem of post-quantum age. We have tried to give as many detailspossible specially for novice on the subject. Something may be trivial to an expert butnot to a novice.Many fundamental problems about lattice are thought to be hard even against quantum computer, compared to factorization problem which can be solved easily with quantum computer, via the celebrated Shor factorization quantum algorithm. The first part ofour presentation is based on slides of Christ Peikert 2013 Bonn lecture (crypt@b-it2013).We, more or less, give somewhat detailed explanation of Professor Peikert’s lecture slides.We unfortunately could not attend his Bonn class. We are afraid that there are manymistakes in this note; if any, they are due to our misunderstanding of the material. PartII of our lecture note is on ring LWE, based on the paper “A tool-kit for Ring-LWECryptography” by Lyubashevsky, Peikert and Regev. Part III is about multilinear mapstogether with cryptanalysis of GGH map due to Hu and Jia. Our presentation followsprofessor Steinfeld’s lecture slides on GGHLite, and the paper by Yupu Hu and HuiwenJia. When you read this lecture note, the corresponding original paper should be accompanied. We thank professor Jung Hee Cheon for introducing the subject and askingDong Pyo Chi to give a lecture on the subject at the department of mathematics inSeoul National University. We also thank Hyeongkwan Kim for many helps, especiallymany corrections and improvements of the manuscript during the 2015 Summer sessionat UNIST. We also thank the students who took the classes at SNU and UNIST. Thelecture was given by a novice for novice, so many mistakes are unavoidable. If the readerlets us know any errors, we will very much appreciate it.i
ii
ContentsAbstractILattice Based Cryptography1 Mathematical and Computational Background1.1 Mathematical Background . . . . . . . . . . . . . . .1.1.1 Definitions . . . . . . . . . . . . . . . . . . . .1.1.2 Two simple bounds on the minimum distance1.2 Computational Background . . . . . . . . . . . . . .1.2.1 Hard problems . . . . . . . . . . . . . . . . .vii.1114662 Short Integer Solution and Learning With Errors2.1 Hard problems . . . . . . . . . . . . . . . . . . . .2.1.1 Short Integer Solution . . . . . . . . . . . .2.1.2 Learning With Errors . . . . . . . . . . . . .2.2 Cryptosystems . . . . . . . . . . . . . . . . . . . .2.2.1 Public-Key Cryptosystem using LWE . . . .2.2.2 Dual cryptosystem . . . . . . . . . . . . . .2.2.3 More efficient Cryptosystem . . . . . . . . .99910121212133 Discrete Gaussians and Applications3.1 Discrete Gaussians and sampling . .3.1.1 Discrete Gaussians . . . . . .3.1.2 Sampling . . . . . . . . . . .3.2 Applications . . . . . . . . . . . . . .3.2.1 Identity Based Encryption . .1515151920204 Constructing Trapdoors and More Applications4.1 Strong trapdoor generation and inversion algorithms . . . . . . . . . . .4.1.1 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21212125II.Introduction to Ring-LWE5 Preliminaries for Ring-LWE cryptography5.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5.2 Gaussians and Subgaussian Random Variables . . . . . . . . . . . . . . .iii27292930
5.35.45.5Lattice Background . . . . . . . . . . . . . . . . . . . . .5.3.1 Decoding . . . . . . . . . . . . . . . . . . . . . .Algebraic Number Theory Background . . . . . . . . . .5.4.1 A key fact from algebraic number theory . . . . .5.4.2 Canonical Embedding and Geometry . . . . . . .5.4.3 The Ring of Integers and Its Ideals . . . . . . . .5.4.4 Duality . . . . . . . . . . . . . . . . . . . . . . .5.4.5 Prime Splitting and Chinese Remainder TheoremRing-LWE . . . . . . . . . . . . . . . . . . . . . . . . . .3233343535363740416 Discrete Fourier Transform & Chinese Remainder Transform457 Powerful basis7.1 Powerful basis p of K Q(ζm ) and R Z[ζm ] . . . . . . . . . . . . . . .7.2 Gram-Schmidt orthogonalization of CRTm . . . . . . . . . . . . . . . . .4747498 Chinese Remainder Basis and Fast Ring Operation519 Decoding Basis of R 9.1 Relation to the Powerful Basis . . . . . . . . .9.2 Decoding R and its Powers . . . . . . . . . .9.2.1 Implementation of Decoding Operation9.3 Gaussian sampling in the Decoding Basis . . .535354555610 Regularity5911 Cryptosystems11.1 Dual-Style Cryptosystem [GPV08] .11.2 Compact Public-key Cryptosystem11.3 Homomorphic Cryptosystem . . . .11.3.1 Modulus Reduction and Key6565666768III. . . . . . . . . . . . . . . .Switching.Multilinear map7512 Multilinear maps12.1 Why multilinear map? . . . . . . . . . . . . . . . . . . . . . . . . . . . .12.2 Grag-Gentry-Halevi (GGH) Graded Encoding Scheme . . . . . . . . . . .77777813 GGHLite scheme for k-graded encoding8314 Cryptanalysis of GGH map14.1 Schematic description of the cryptanalysis . . . . . . . . . . . .14.2 Generating an equivalent secret . . . . . . . . . . . . . . . . . .14.3 Modified Encoding/Decoding . . . . . . . . . . . . . . . . . . .14.4 Witness encryption based on 3–exact cover . . . . . . . . . . . .14.5 Breaking WE based on the hardness of 3–exact cover problem .14.6 Computing the Hermite Normal Form of hgi by computing theNormal Forms of h(1 ag)K 2 b(1) and h(1 ag)K 2 b(1) g . .878787888889iv. . . . . . . . . . . . . . . . . . . . .Hermite. . . . .93
A Hermite Normal Form of Ideal Lattices (following Ding andLindner, Smart and Vercauteren)95B Notes on Cyclotomic Fields with Examples (by H. Kim)B.1 Cyclotomic Number Fields & Ring of Integers . . . . . . .B.2 The Space H and the Canonical Embedding . . . . . . . .B.2.1 The Space H . . . . . . . . . . . . . . . . . . . . .B.2.2 The Canonical Embedding . . . . . . . . . . . . . .B.3 Discriminant . . . . . . . . . . . . . . . . . . . . . . . . . .B.4 Ideals . . . . . . . . . . . . . . . . . . . . . . . . . . . . .B.4.1 Fractional ideals . . . . . . . . . . . . . . . . . . . .v.9797989899104105107
vi
Part ILattice Based Cryptographyvii
Chapter 1Mathematical and ComputationalBackground1.1Mathematical BackgroundIn Part I, we use the notations in [P13].1.1.1DefinitionsLatticeA lattice L of Rn is by definition a discrete subgroup of Rn . In this note we only dealwith full-rank lattice, i.e., L spans Rn with real coefficients. Moreover, we consider onlyinteger lattices, i.e., L Zn . Remark 1.1.1. Z 2Z is not a lattice. Note that when α is irrational, nα mod 1 isuniformly dense in S 1 [0, 1]/0 1 (Weyl theorem).BasesA basis of L is an ordered set B (b1 , b2 , . . . , bn ) such that( n)XL L(B) B · Zn c i bi : c i Z .(1.1)i 1Note that by convention, bi are column vectors and B · k k1 b1 · · · kn bn , where kis a column vector.Fundamental parallelepiped of basis B is n1 1P (B) B · ,(1.2)2 2( n)X11 αi bi : αi .(1.3)22i 1Note that P (B) depends not only on lattice but also on the choice of basis B. A “good”basis of L gives rather a square-like parallelepiped, while a ‘bad’ basis gives a very thinparallelepiped. It is trivial to see the following lemma.1
Lemma 1.1.2.Rn [(v P (B)),(1.4)v Lthat is, parallel translation by lattice vectors of parallelepiped covers Rn without overlap.Proof. For any p Rn ,p Xx i bi(1.5)iXX dxi cbi (xi dxi c)bi ,i(1.6)iwhere dac means rounding off. For example, d2.7c 3, d2.5c 3, and d2.1c 2.Therefore,11 a dac .(1.7)22XXSHence,dxi cbi L and(xi dxi c)bi P (B). This shows that Rn v L (v iiP (B)).If (v1 P (B)) (v2 P (B)) 6 for some v1 6 v2 L, then v1 α v2 β forsome α, β P (B), so v1 v2 β α. Since v1 v2 is a Z-linear combination of biwhile β α is a ( 1, 1)-linear combination of bi , so v1 v2 0 β α.BU is also basis for any U GL(n : Z), i.e., U is an n n integer matrix withdeterminant 1. Note that, for example, 1 1023 GL(2 : Z).(1.8)0 1Coset and DeterminantIt is much better to think a coset element of Zn /L concretely (note that we assumedL Z n ), as a subset v L, i.e. a shift of the lattice L, where v Zn represents a cosetof Zn /L.Lemma [1.1.3. Each coset of L has a unique representative in a parallelepiped P (B),because(v P (B)) covers Rn without overlap.v LProof. Let v Zn be a representative of a coset v L. Since[(w P (B)) coversw LRn without any overlap, there exists a unique w L such that v (w P (B)). Thenv w P (B), and v represents the same coset, i.e.,v L (v w) L,(1.9)so v w is a representative of the coset v L in P (B). Moreover, such a representativeis unique, since if v1 , v2 P (B) andv1 L v2 L,2(1.10)
wherev1 Xc1j bj ,v2 Xc2j bj ,11 c1j ,2211 c2j ,22(1.11)(1.12)thenv1 v2 X(c1j c2j )bj L,i.e., c1j c2j Z for all j. Note that if 12 a 12 and 12 b 1 a b 1. Hence, c1j c2j 0 for j 1, 2, . . . , n.(1.13)1,2then thenBy definition,det(L) : Zn /L det B vol(P (B))(1.14)for any basis B of L.Lemma 1.1.4. Zn /L vol(P (B)).Proof. Note the following: L P (B) covers Rn without overlap.nn Z 1 1 ·n covers R without overlap, where · means the half closed unit cube 2, 2 .Thus,L P (B) Rn Zn ·[ (c L · ).(1.15)(1.16)(1.17)c Zn/LIt follows that Zn /L · P (B) , so Zn /L vol(P (B)).Successive MinimaSuccessive minima of linearly independent vectors are defined as follows: λ1 (L) : min06 v L kvk minx6 y L kx yk λi (L) : min {r : L contains i linearly independent vectors of length r} .Then λ1 (L) λ2 (L) · · · λn (L). Let v1 , v2 , . . . , vn be corresponding lattice elements.Note that {v1 , v2 , . . . , vn } need not be a basis of L.Example 1.1.1. Let L Zn be spanned by 2e1 , . . . , 2en , (1, 1, . . . , 1), where n 4.Then v (v1 , . . . , vn ) L if and only if v1 v2 · · · vn mod 2. Thenλ1 (L) · · · λn (L) 2.(1.18)But {2e1 , . . . , 2en } is not a basis of L. (1, 1, . . . , 1) or its variation should be an elementof any basis of L.3
1.1.2Two simple bounds on the minimum distanceGram-Schmidt Orthogonalization and Lower Bounding λ1e of a basis B of L is given byThe Gram-Schmidt orthogonalization BB QR (1.19)f1 kkb . Q 0 1.e B 0where (1.20)fn kkb ,(1.21)1f1 kkb0.e Q B ,.fn kkb0e and R is a representation of B withand Q is an orthonormal basis reduced from B,respect to this basis. e Be · 1 , 1 n is a fundamental domain of L. That is, L P (B)eLemma 1.1.5. P (B)2 2ncovers R without overlap.e vol(P (B)), it suffices to show that there is no overlap. AssumeProof. Since vol(P (B))there is a overlap, i.e.,e By BβeBx Bα(1.22) ne β αfor some x, y Zn and α , β 12 , 12 . Then B(x y) B( ). Letting z x y, 1 .ee β α.B ),(1.23) z B(01so 1 . ).(1.24) z (β α.01Note that z is an integer vector and 1 βi αi 1.(1.25)From the equality (1.24),znzn 1 znzn 1 ··· z1 i.e., x βn αn zn 0 αn βnβn 1 αn 1βn 1 αn 1 zn 1 0 αn 1 βn 1(1.26)(1.27)(1.28)0y.(1.29)(1.30)4
It is easy to see that λ1 (L) min kbei k from Bc Q(Rc) for c Zn .iUpper Bounding λ1 : Minkowski’s TheoremTheorem 1.1.6 (Minkowski Theorem 1). Any convex centrally symmetric body S ofvolume 2n det(L) contains a nonzero lattice point.Proof. Let S 0 12 S, so vol(S 0 ) det(L). Then there exist x 6 y S 0 such thatx y L, since for some v1 6 v2 L,\(v1 S 0 ) (v2 S 0 ) 6 φ(1.31)z v1 x v2 y, x, y S 0x y v2 v1 6 0 L.(1.32)(1.33)Now 2x, 2y S by the definition of S 0 , so11x y (2x) ( 2y) S22by the convexity of S.Corollary 1.1.7.λ1 (L) 1n(det L) n .(1.34)Proof. We give a proof of the corollary using the following two facts: 1 A ball of radius n(det L) n is convex and centrally symmetric. 11 B(0, n(det L) n ) a cube of side length 2(det L) n , since dist ((1, . . . , 1), (0, . . . , 0)) n.It follows thatvol(B(0, 1n(det L) n )) 2n det L.Remark 1.1.8. We could obtain a more refined inequality if we use the exact formulafor vol(B(0, R)). Choose R such that vol(B(0, R)) 2n det L. Then λ1 (L) R.1Q 1Theorem 1.1.9 (Minkowski Theorem 2). ( ni 1 λi (L)) n n(det L) n .Proof. We may assume kbi k λi (L) for i 1, . . . , n, and consider a lattice generated byb1 , . . . , bn , possibly a sublattice of L. E 2 D en y, biXn 1 .T : y R :(1.35)ei kλi kb i 1Claim: The ellipsoid T does not contain any nonzero lattice point.Let 0 6 y L, and 1 k n maximal such thatλk 1 (L)kyk λk (L).5(1.36)
We claim y span{b1 , . . . , bk } span{b̃1 , . . . , b̃k }. If not, b1 , . . . , bk , y are k 1 linearlyindependent and their norms are less than λk 1 , a contradiction. Hence,E 2E 2 D Dnky,b̃y,b̃XXii (1.37)kb̃kλkb̃kλiiiii 1i 1E 2 Dky,b̃Xi1 (1.38)2λkb̃kkii 1kyk2 1,λ2k (1.39)so y / T , i.e., T does not contain any nonzero lattice vector. Hence,!! nnnYY2n 2 det(L) vol(T ) λi vol(B(0 : 1)) λi,ni 1i 1sonY! n1λi 1n(det L) n .(1.40)(1.41)i 11.21.2.1Computational BackgroundHard problemsShortest Vector Problem (SVP) SV Pγ : Given a basis B of L, find nonzero v L such that kvk γλ1 (L).There exists an exact algorithm for finding a nonzero minimum vector in time 2O(n) ,polynomial time algorithm for gap 2n , but no quantum algorithm with exponentialboost. GapSV Pγ : Given a basis B of L and a real d, decide between λ1 (L) d andλ1 (L) γd.Note that GapSV Pγ SV Pγ , i.e., GapSV Pγ reduces to SV Pγ . (SV Pγ find v 6 0 Lsuch that λ1 (L) kvk γλ1 (L).) If kvk γd, then λ1 γd. Hence, λ1 d (becauseeither λ1 d or λ1 γd). If kvk γd, then γd kvk γλ1 , so d λ1 , hence λ1 γd.)But the reverse direction is open.6
LLL (Lenstra-Lenstra-Lovaz) algorithmB (b1 , . . . , bn ) is a δ LLL reduced basis if(i) For 1 j i n, we have µi,j 12 .(ii) For 1 i n, we haveδkb̃i k2 kµi 1,i b̃i b̃i 1 k2 µi 1,i 2 kb̃i k2 kb̃i 1 k2 ,(1.42)whereDbi , b̃jEµi,j b̃i,kb̃j k2i 1X bi µi,j b̃j .(1.43)(1.44)j 1B has the following form with respect to the orthonormal basis kb̃1 k µ2,1 kb̃1 k µ3,1 kb̃1 k 12 kb̃1 k kb 2 kµ3,2 kb̃1 k 12 kb 2 k . . 1 k 2 kbn 1kb̃n k (1.45)In particular, if 1 δ 14 , then2kb̃i 1 k 1δ 4 kb̃i k2 .Hence,kb1 k kb̃1 k 2(n 1)/2 min kb̃i k 2(n 1)/2 λ1 (L).(We choose δ 34 .)7(1.46)
LLL-algorithm Input: Lattice basis b1 , . . . , bn Zn . Output: δ-LLL reduced basis of L. Start: compute the Gram-Schmidt Orthogonalization b̃1 , b̃2 , . . . , b̃n . Reduction Step:for i 2 to n dofor j i 1 to 1 dolDbi bi cij bj , where cij Dbi ,b̃jb̃j ·b̃jEE k. Swap Step:If i such that δkb̃i k2 kµi 1,i b̃i b̃i 1 k2bi bi 1goto start. Output: b1 , . . . , bn .Shortest Independent Vectors Problem (SIV Pγ )Given a basis B, find linearly independent vectors v1 , . . . , vn L such that kvi k γλn (L).Bounded-Distance Decoding (BDD)Given a basis B, t Rn , and real d λ1 /2 such that dist( t, L) d, find the uniquev L closest to t. BDD is equivalent to finding e t L such that kek d.Algorithms for BDD1. Babai’s Round off algorithm for BDDUsing a good basis B,XX t αi bi e : (αi dαi c)bi .(1.47) It works if Ball(d) P (B). Hence, d minkb i k/2, where bi is the orthogonalcomponent of bi to the hyperplane span{b1 , · · · , b̂i , · · · , bn }.2. Babai’s nearest plane algorithm for BDDe where e P (B).eOutput e t mod B,e where Be is the Gram-Schmidt Orthogonalization of BIt works if Ball(d) P (B),as before,i.e., d min kbei k/2.(1.48)ie is also a fundamental domain of the lattice L.Note that P (B)8
Chapter 2Short Integer Solution and LearningWith Errors2.12.1.1Hard problemsShort Integer SolutionShort Integer Solution (SIS)Znq : n-dimensional vectors modulo q. Given a 1 , . . . , a m Znq , find nontrivial and smallz1 , . . . , zm Z such thatz1 a 1 · · · zm a m 0(2.1)in Znq , i.e.,Az 0mod q,(2.2)where A ( a1 , . . . , am ). This is finding a short vector in the lattice L(A) : kermZA Zn mqz7 Az/Znq {x Zm : Ax u mod q}.One-way Hash FunctionSet m n log q. Define fA : {0, 1}m Znq asfA (x) Ax.(2.3)Then fA covers Zqn almost uniformly. (Note that since m n log q, the number ofelements in the domain, 2m , is much larger than the number of elements in the range,q n .)We say collision x, x0 {0, 1}m when Ax Ax0 . A (a 1 , . . . , a m ) Zn mdefines a q-ary latticeqL (A) {z Zm : Az 0 Hence, SIS is SVP on L (A).9mod q}.
A syndrome u Znq defines a cosetmL u (A) {x Z : Ax u mod q}of L (A).Remark 2.1.1. We are assuming that A has n-linearly independent columns. Hence,A : Zm Znq is onto, so Zm /L (A) q n , i.e., det L (A) q n .Worst-Case / Average-Case reductionFinding a short nonzero z L (A) for uniformly random A Zn m, where m n ln qq Solving GapSV Pβ n , SIV Pβ n on any n-dimensional lattice.Algorithm for reductionRepeat m-times.Pick a random lattice point vi L, where L is an n-dimensional lattice.Gaussian sample a point in 1q L around the lattice point vi L.Hence, each sampled point can be written as vi 1q B ai , where 1q B ai is short.Give the m Znq samples a 1 , . . . , a m to SIS oracle. Note thatA ( a1 , . . . , an ) Zn mqis uniform. We subdivided the sides of the given lattice by “q”. So each lattice domainof L has q n subpoints inside.SIS oracle outputs z1 , . . . , zm { 1, 0, 1} such thatz1 a 1 · · · zm a m 0 (mod q).Therefore,P(2.4)zi (vi 1q B ai ) is a lattice point of the given lattice L. Hence,1B(z1 a 1 · · · zm a m )q(2.5)is a short lattice vector in L since it is the sum of short vectors 1q B ai .2.1.2Learning With ErrorsLearning With Errors (LWE) Search LWE: Find s Znq given noisy random inner productsa 1 Znq ,a 2 Znq ,b1 hs, a 1 i e1b2 hs, a 2 i e2(2.6)(2.7).where ei χ, χ Gaussian over Z with width αq. (αq Znq ZmA Zn mq(s,e)7 st A e n)/ Zmq Decision LWE: Distinguish (A, bt st A et ) from uniform (A, bt ), where A (a 1 , . . . , a m ).Note that Search LWE Decision LWE.10
Lattice interpretation of LWEL(A) : {z Zm : zt st A mod q for some s Znq } π 1 (im A)ZmZnqAs7 st A π/ ZmqThen, LWE BDD on L(A). (Remark: From zt st A e, we obtain zt by BDD, thensolve the simultaneous equation zt st A mod q to obtain s.)SIS versus LWE Regev: LWE GapSVP, SIVP quantumly. (Peikert et al. showed LWE GapSVPclassically. But, classical reduction LWE SVP, or LWE SIVP is unknown.) SIS LWE:If we find short z such that Az 0, then from bt st A et , we find bt z 0 et z;if (A, bt ) is LWE, then bt Z is short; if (A, bt ) is not LWE, then bt z rather wellspread. SIS LWE quantumly.Simple properties of LWE1. Easy to check a candidate solution s0 Znq : test if b hs0 , ai is small.If s 6 s0 , then b hs0 , ai hs s0 , ai e is well spread in Zq .2. Shift the secret by any t Znq ,( a, b hs, ai e) ( a, b0 b ht, ai hs t, ai e).(2.8)random ts random self-reduction.We obtain many new LWEs with essentially the same solutions. Hence, we canboost success probabilities arbitrarily close to 1.Proof of equivalence of Search/Decision of LWE.Suppose that D solves decision-LWE, i.e., it perfectly distinguish between ( a, b hs, ai e)and uniform ( a, b). We want to solve search LWE; i.e., given pairs ( a, b), find s. To finds1 Zq , it suffices to test whether s1 0 because we can shift s1 by 0, 1, . . . , q 1, i.e.,choose t (0, 0, . . . , 0) or t (1, 0, . . . , 0), t (2, 0, . . . , 0), . . . , t (q 1, 0, . . . , 0). Foreach ( a, b), choose r Zq . Invoke D on pairs (a 0 a (r, 0, . . . , 0), b). Sinceb hs, ai eDE s, a 0 (r, 0, . . . , 0) eDE s, a 0 s1 r e,DE0 we see that if s1 0, then b s, a e is LWE, and if s1 6 0, then b is uniform.11
Decision-LWE with ‘Short’ SecretWe may assume that the secret is short, i.e., drawn from the error distribution χn . Inthis case, we say that our LWE is in Hermite Normal Form (HNF of LWE).1. Draw samples to get (Ā, b̄t st Ā ēt ) for square invertible Ā.2. Transform additional samples of LWE ( a, b hs, ai e) to a 0 Ā 1 a,b0D b b̄, a 0EDE hs, ai e Āt s ē, a 0DE DE hs, ai Āt s, a 0 ē, a 0 eDE 10 hs, ai s, Ā( Ā ) a ē, a eDE ē, a 0 e.(a 0 , b0 ) is LWE with secret ē. Then we obtain s from b̄t st Ā ēt .2.22.2.1CryptosystemsPublic-Key Cryptosystem using LWE(Due to Regev)A Zn m(i.e., uniformly random n m matrix over Zq ) open public.qns Zq Alice secret.Public key of Alicebt s t A e t .(2.9)u Ax,u0 bt x bit · q/2.(2.10)(2.11)x {0, 1}m Bob secret.Bob sends to AliceAlice decodes u0 st u bit · q/2.Note that (A, bt ) is LWE and (u, u0 ) uniformly random by left-over hash lemma whenm n log q.2.2.2Dual cryptosystemA Zn mopen public as before.qAlice chooses a secret x {0, 1}m .Alice’s public keyu Ax.12(2.12)
(by LHL, uniform if m n log q.)Bob chooses a secret s Znq .Bob sendsbt st A et ,b0 st u e0 bit · q/2.(2.13)(2.14)Adding bit · q/2 does not change the uniformity of st A et .Alice decodes b0 bt x bit · q/2.Note that (A, u; b, b0 ) is a LWE pair.2.2.3More efficient CryptosystemA Zn nopen public.qAlice chooses a secret s χn and an error e χn .Alice’s public keyut s t A e t .(2.15)Bob chooses a secret r χn , x χ, and x, x0 χ.Bob sendsb Ar xb0 ut r x0 bit · q/2.Alice decodes b0 st b bit · q/2.Note that (A, u; b, b0 ) is a Hermite normal form of LWE.13(2.16)(2.17)
14
Chapter 3Discrete Gaussians and Applications3.13.1.1Discrete Gaussians and samplingDiscrete GaussiansGaussian samplingDefine πkxk2ρs (x) : exp 2.s(3.1)Note that ρs is rather flat if s is large, and steep if s is small.Note thatZρs (x)dx sn .(3.2)nx RHence, vs : sρns is an n-dimensional Gaussian probability density. We define FourierTransform asZĥ(w) h(x)e 2πihx,wi dx.(3.3)nRHence,Zρ̂s (y) ρs (x)e 2πix·y dx(3.4)nR Zkxk2 π 2ix·ys2 edx(3.5)nZR 2P x π i si iyi s π(kyks)2 eedx(3.6)Rn sn ρ 1 (y).(3.7)sHence, if ρs (x) rather steep, then ρˆs is rather flat, and vice versa.Remark 3.1.1.Z2e πx dx 1,Z Re πR x 2sdx s.15(3.8)(3.9)
Poisson summation formulaLetf (x) : R CXF (θ) : f (θ n) : S 1 C,(3.10)(3.11)n Zwhere S 1 [0, 1]/0 1. Then the Fourier series of F (θ) isF (θ) Xan e2πinθ ,(3.12)n ZwhereZ1F (θ)e 2πinθ dθan (3.13)0Z!1X 0Zf (θ k) e 2πinθ dθ(3.14)k f (θ)e 2πinθ dθ (3.15) fˆ(n),(3.16)Pˆi.e., F (θ) f (n)e2πinθ .In particular, we obtain Poisson Summation FormulaF (0) Xf (n) n ZXfˆ(n).(3.17)n ZIn general, for h : Rn C,ĥ(Zn ) h(Zn ).(3.18)Generalized Poisson summation formulaLet f : Rn C.f (L) det L fˆ(L ),(3.19)where L Zn is a lattice andL {x Rn : x · y Z, y L}(3.20)is called the dual lattice of L.Proof. Let L AZn for some n n matrix A.f (L) (f A)(Zn )\ (f A)(Zn )16(3.21)(3.22)
by Poisson summation formula. Let’s computeZf[ A(y) e 2πihx,yi (f A)(x)dxnRputting Ax : x0Z1 1 0 e 2πi A x ,y f (x0 )dx0ndet A RZDET1 2πi x0 ,A 1 y ef (x0 )dx0ndet A R1 · fˆ(A T y).det A(3.23)(3.24)(3.25)(3.26)Hence,1 ˆ T nf (A Z )det A det L fˆ(L ),f[ A(Zn ) (3.27)(3.28)because in general,if L L(B), B (b1 , . . . , bn ),then L L(D), D (d1 , . . . , dn ),(3.29)(3.30)where bi · dj δij , i.e.,BT D I,(3.31)i.e., L L(B T Zn ). Note that det L (det L) 1 .Corollary 3.1.2. ρr (L c) rn det L (1 ε) if r ηε (L), i.e., ρ 1 (L \ 0) ε, i.e., ρ 1rris very steep.Proof.ρr (L c) Xρr (x c)(3.32)ρr, c (x)(3.33)x L Xx LX det L ρdr, c (y)(3.34)y L rn det L Xe2πihc,yi ρ 1 (y)y L rn det L (1 ε).r(3.35)(3.36)Smoothing parameter [MR04]ηε (L), defined above, is called the smoothing parameter, because if r ηε (L), then ρr israther flat, smooth, and ρr (L c) is almost uniform with respect to c. More quantitatively. ηε (L) n/λ1 (L ) where ε 2 n (Micciancio and Regev [MR04]).17
2 ε 2e πs such that ρs (c Z) 1 that ρs (c Z) ρs (Z))2 Xε1 ε s for all c R. Just we compute (note22e π(sn) n 12e πsε 21 ε1 e πs2(3.37)2for some ε 2e πs . (True if ε is sufficiently close to 2e πs .) The above example can be generalized to lattice L Zn Rn .s 2 ε 2ne π( M ) such that ρs (c L) [1 ε]sn for all c Rn , where M max kbei k.i 1Especially if s log nM , then ρs (c L) (1 ε) poly(n).Remark 3.1.3. ρs (x) e πkxk2s2 ρs (x1 ) · · · ρs (xn ) n Yεie ρs (L(B)) ρs (L(B))1 sn for some ε1 , . . . , εn , where1 εii 1 !2 s .εi 2 exp πkBei ke follows fromρs (L(B)) ρs (L(B)) f1 kkb . B Q 0(3.38) ,(3.39)fn kkbwhere Q is orthogonal.Discrete GaussiansDefinition 1. Discrete Gaussian distribution over coset c L is defined asDc L,s (x) ρs (x)ρs (c L)(3.40)for all x c L.Note that if s is sufficiently large (e.g., s ηε (L)), then the denominator is very closeto sn det L (e.g., with ε 2 n , s n/λ1 (L )), and the numerator is the restriction ofρs (x) on c L. Hence, we only obtain exponentially small information about c L whensampled from Dc L,s if s n/λ1 (L ).Choose x Zn from DZn ,s , where s ηε (L). Reveal the coset x L. Then everycoset c L is almost equally likely, i.e., the distribution is almost uniform over Zn /L.Given x c L, it has the conditional distribution Dc L,s .LetA Zn m, i.e., uniformlyqx DZm ,s18(3.41)(3.42)
define fA (x) : Ax( u) Znq . Then, inverting fA decoding uniform syndrome u solving SIS for A. (Solving Ax u is equivalent to solving [A u] [ 1x ] 0.)Conditional distribution when Ax u is DL u (A),s , wherenL u {x Z Ax u mod q}.3.1.2SamplingAlgorithms of Gaussian Sampling of DL u (A),s(As remarked before, DL u (A),s sample does not reveal syndrome u ifplog m max kbei k s,where S (b1 , . . . , bm ) is a short enough basis of L (A), since εi case.)1O(poly(m))in thisNearest plane algorithm with randomized roundingGaussian sample a hyperplane in the coset L u (A) which is parallel to span{s1 , . . . , sm 1 }, where S {s1 , . . . , sm } is a basis of L (A). Then consider the Z span of s1 , . . . , sm 1displaced by the closest vector from the origin to the chosen hyperplane. Do Gaussiansampling onT this displaced (m 1)-dimensional lattice. Iterate this process. Note thatρs ((c L) plane) depends only on dist(0, plane), since ρs (x) depends only on kxk.Remark 3.1.4. Gaussian nearest plane algorithm for sampling DL u (A),s is not efficientand inherently sequential. We need a more efficient Gaussian sampling.Randomized Babai’s roundoff algorithm. [Bab85]Babai’s roundoff algorithm for finding the representative of a coset in the fundamentalparallelepiped can be written asc 7 Sf rac(S 1 c),(3.43)where S {s1 , . . . , sm } is a basis of L (A). mNaive randomized rounding: Note that f rac(S 1 c) 12 , 12 Rm . Gaussian sample from f rac(S 1 c) Zm , i.e., instead of the deterministic f rac(S 1 c), we could getf rac(S 1 c) p for some p Zm . Then apply S to obtain x. But then we have nonspherical Gaussian distribution of x, because even though f rac(S 1 c) p is sphericalGaussian, when we apply S to f rac(S 1 c) p to obtain x, we have nonspherical discreteGaussian such thatEx (xxt ) S · S t ,(3.44)where S (s1 , . . . , sm ) is a short basis of L (A), i.e., it leaks some information aboutshort basis S.Breakthrough: Gaussian correction19
Note that the sum of the Gaussian distribution is again Gaussian with the sum of thecovariances as its covariance. (The probability distribution of the sum of two randomvariables X1 and X2 isZPX1 X2 (y) PX1 (x)PX2 (y x)dx.Hence, P̂X1 X2 PbX1 P̂X2 . In particular, if PX1 and PX2 are Gaussian with covariancess21 and s22 , respectively, then PX1 X2 is Gaussian with covariance s21 s22 .)PPP1. Generate perturbation p with covariance 2 σ 2 I 1 , where 1 SS t , andσ s1 (S), the largest singular value of S.2. Randomly round off c p to obtain a random sampleS · f rac(S 1 (c p)) L (A).3. Then add p.3.23.2.1ApplicationsIdentity Based EncryptionIdentity Based Encryption A: n m matrix, master public key. u H(Alice): hashed identity of Alice, public.Master finds a Gaussian short element in fA 1 (u), i.e., x fA 1 (u) (Master has a shortbasis of L (A)), and give Alice x as her secret key.I want to send a message bit to Alice so that only Alice can decode. Choose Gaussianshort s, e Znq , e0 Zqbt : st A et(3.45)qb0 st u e0 bit ·2(3.46)Alice decodes: b0 bt x bit · 2q .(Note that this protocol is just a little modification of dual LWE cryptosystem.)It seems that it is required to have a lattice together with a
Lattice Based Cryptography for Beginners { A supplementary note to the following 1: Peikert’s Bonn Lecture Slides 2: Lyubashevsky, Peikert and Regev: A toolkit for Ring-LWE 3: Steinfeld’s Lecture Slides on multilinear maps with Cryptanalysis of GGH map due to Hu and Jia Dong Pyo
