Lattice Based Cryptography for Beginners

1 Lattice Based Cryptography for Beginners A supplementary note to the s Bonn Lecture , Peikert and Regev:A toolkit for s Lecture Slides on multilinear mapswith Cryptanalysis of GGH map due to Hu and JiaDong Pyo Chi1,2, Jeong Woon Choi3, Jeong San Kim4and Taewan Kim51 Division of General Studies, of Mathematics, Seoul National Technology R&D Center, SK of Applied Mathematics, Kyung Hee of Mathematical Sciences, Ewha Womans 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 fundamental problems about Lattice are thought to be hard even against quan-tum computer, compared to factorization problem which can be solved easily with quan-tum computer, via the celebrated Shor factorization quantum algorithm.

2 The first part ofour presentation is Based on slides of Christ Peikert 2013 Bonn lecture more or less, give somewhat detailed explanation of Professor Peikert s lecture 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-LWEC ryptography 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 ac-companied.

3 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 Lattice Based Cryptographyvii1 Mathematical and Computational Mathematical Background .. Definitions .. Two simple bounds on the minimum distance .. Computational Background.

4 Hard problems ..62 Short Integer Solution and Learning With Hard problems .. Short Integer Solution .. Learning With Errors .. Cryptosystems .. Public-Key Cryptosystem using LWE .. Dual cryptosystem .. More efficient Cryptosystem ..133 Discrete Gaussians and Discrete Gaussians and sampling .. Discrete Gaussians .. Sampling .. Applications .. Identity Based Encryption ..204 Constructing Trapdoors and More Strong trapdoor generation and inversion algorithms .. Methods .. Applications ..25II Introduction to Ring-LWE275 Preliminaries for Ring-LWE Notations .. Gaussians and Subgaussian Random Variables .. Lattice Background .. Decoding .. Algebraic Number Theory Background.

5 A key fact from algebraic number theory .. Canonical Embedding and Geometry .. The Ring of Integers and Its Ideals .. Duality .. Prime Splitting and Chinese Remainder Theorem .. Ring-LWE ..416 Discrete Fourier Transform & Chinese Remainder Transform457 Powerful Powerful basis~pofK=Q( m) andR=Z[ m] .. Gram-Schmidt orthogonalization ofCRTm..498 Chinese Remainder Basis and Fast Ring Operation519 Decoding Basis ofR Relation to the Powerful Basis .. DecodingR and its Powers .. Implementation of Decoding Operation .. Gaussian sampling in the Decoding Basis ..5610 Regularity5911 Dual-Style Cryptosystem [GPV08] .. Compact Public-key Cryptosystem .. Homomorphic Cryptosystem.

6 Modulus Reduction and Key Switching ..68 III Multilinear map7512 Multilinear Why multilinear map? .. Grag-Gentry-Halevi (GGH) Graded Encoding Scheme ..7813 GGHLite scheme fork-graded encoding8314 Cryptanalysis of GGH Schematic description of the cryptanalysis .. Generating an equivalent secret .. Modified Encoding/Decoding .. Witness encryption Based on 3 exact cover .. Breaking WE Based on the hardness of 3 exact cover problem .. Computing the Hermite Normal Form of g by computing the HermiteNormal Forms of h(1 +ag)K 2b(1) and h(1 +ag)K 2b(1)g ..93ivA Hermite Normal Form of Ideal Lattices (following Ding andLindner, Smart and Vercauteren)95B Notes on Cyclotomic Fields with Examples (by H.)

7 Kim) Cyclotomic Number Fields & Ring of Integers .. The SpaceHand the Canonical Embedding .. The SpaceH.. The Canonical Embedding .. Discriminant .. Ideals .. Fractional ideals ..107vviPart ILattice Based CryptographyviiChapter 1 Mathematical and Mathematical BackgroundIn Part I, we use the notations in [P13]. DefinitionsLatticeA latticeLofRnis by definition a discrete subgroup ofRn. In this note we only dealwith full-rank Lattice , ,LspansRnwith real coefficients. Moreover, we consider onlyinteger lattices, ,L + 2 Zis not a Lattice . Note that when is irrational,n mod 1 isuniformly dense inS1= [0,1]/0 1 (Weyl theorem).BasesA basis ofLis an ordered setB= (b1,b2,..,bn) such thatL=L(B) =B Zn={n i=1cibi:ci Z}.

8 ( )Note that by convention,biare column vectors andB k=k1b1+ +knbn, wherekis a column parallelepiped of basisBisP(B) =B [ 12,12)n( )={n i=1 ibi: 12 i<12}.( )Note thatP(B) depends not only on Lattice but also on the choice of basisB. A good basis ofLgives rather a square-like parallelepiped, while a bad basis gives a very thinparallelepiped. It is trivial to see the following v L(v+P(B)),( )that is, parallel translation by Lattice vectors of parallelepiped coversRnwithout anyp Rn,p= ixibi( )= idxicbi+ i(xi dxic)bi,( )wheredacmeans rounding off. For example, 3, 3, , 12 a dac<12.( )Hence, idxicbi Land i(xi dxic)bi P(B). This shows thatRn= v L(v+P(B)).If (v1+P(B)) (v2+P(B))6= for somev16=v2 L, thenv1+ =v2+ forsome , P(B), sov1 v2=.]

9 Sincev1 v2is aZ-linear combination ofbiwhile is a ( 1,1)-linear combination ofbi, sov1 v2= 0 = .BUis also basis for anyU GL(n:Z), ,Uis ann ninteger matrix withdeterminant 1. Note that, for example,(1 10230 1) GL(2 :Z).( )Coset and DeterminantIt is much better to think a coset element ofZn/Lconcretely (note that we assumedL Zn), as a subsetv+L, a shift of the latticeL, wherev Znrepresents a coset ofLhas a unique representative in a parallelepipedP(B),because v L(v+P(B)) coversRnwithout Znbe a representative of a cosetv+L. Since w L(w+P(B)) coversRnwithout any overlap, there exists a uniquew Lsuch thatv (w+P(B)). Thenv w P(B), andvrepresents the same coset, ,v+L= (v w) +L,( )sov wis a representative of the cosetv+LinP(B).

10 Moreover, such a representativeis unique, since ifv1,v2 P(B) andv1+L=v2+L,( )2wherev1= c1jbj, 12 c1j<12,( )v2= c2jbj, 12 c2j<12,( )thenv1 v2= (c1j c2j)bj L,( ) ,c1j c2j Zfor allj. Note that if 12 a <12and 12 b <12, then then 1 a b 1. Hence,c1j c2j= 0 forj= 1,2,.., definition,det(L) :=|Zn/L|=|detB|= vol(P(B))( )for any |Zn/L|= vol(P(B)). the following: L+P(B) coversRnwithout overlap. Zn+ coversRnwithout overlap, where means the half closed unit cube[ 12,12) ,L+P(B) =Rn( )=Zn+ ( )= c Zn/L(c+L+ ).( )It 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 v = minx6=y L x y i(L) := min{r:Lcontainsilinearly independent vectors of length r}.]