Sieving for shortest vectors in lattices using (angular) locality-sensitive hashing Thijs Laarhoven [email protected] http://www.thijs.com/ Crypto 2015, Santa Barbara (CA), USA (August 17, 2015) Lattices What is a lattice? O Lattices What is a lattice? b 2 b 1 O Lattices What is a lattice? b 2 b 1 O Lattices Shortest Vector Problem (SVP) b 2 b 1 s O Lattices Exact SVP algorithms Algorithm log (Time) log (Space) 2 2 Enumeration[Poh81,Kan83,...,GNR10] Ω(nlogn) O(logn) P V AKS-sieve[AKS01,NV08,MV10,HPS11] 3.398n 1.985n S ListSieve[MV10,MDB14] 3.199n 1.327n ble AKS-sieve-birthday[PS09,HPS11] 2.648n 1.324n va ListSieve-birthday[PS09] 2.465n 1.233n o Pr Voronoicellalgorithm[MV10b] 2.000n 1.000n DiscreteGaussiansampling[ADRS15] 1.000n 1.000n Nguyen-Vidicksieve[NV08] 0.415n 0.208n GaussSieve[MV10,...,IKMT14,BNvdP14] 0.415n? 0.208n P V Two-levelsieve[WLTB11] 0.384n 0.256n S Three-levelsieve[ZPH13] 0.3778n 0.283n tic Overlatticesieving[BGJ14] 0.3774n 0.293n s uri e H Lattices Exact SVP algorithms Algorithm log (Time) log (Space) 2 2 Enumeration[Poh81,Kan83,...,GNR10] Ω(nlogn) O(logn) P V AKS-sieve[AKS01,NV08,MV10,HPS11] 3.398n 1.985n S ListSieve[MV10,MDB14] 3.199n 1.327n ble AKS-sieve-birthday[PS09,HPS11] 2.648n 1.324n va ListSieve-birthday[PS09] 2.465n 1.233n o Pr Voronoicellalgorithm[MV10b] 2.000n 1.000n DiscreteGaussiansampling[ADRS15] 1.000n 1.000n Nguyen-Vidicksieve[NV08] 0.415n 0.208n GaussSieve[MV10,...,IKMT14,BNvdP14] 0.415n? 0.208n P V Two-levelsieve[WLTB11] 0.384n 0.256n S Three-levelsieve[ZPH13] 0.3778n 0.283n tic Overlatticesieving[BGJ14] 0.3774n 0.293n s uri HyperplaneLSH[Laa15] 0.337n 0.208n e H Lattices Exact SVP algorithms Algorithm log (Time) log (Space) 2 2 Enumeration[Poh81,Kan83,...,GNR10] Ω(nlogn) O(logn) P V AKS-sieve[AKS01,NV08,MV10,HPS11] 3.398n 1.985n S ListSieve[MV10,MDB14] 3.199n 1.327n ble AKS-sieve-birthday[PS09,HPS11] 2.648n 1.324n va ListSieve-birthday[PS09] 2.465n 1.233n o Pr Voronoicellalgorithm[MV10b] 2.000n 1.000n DiscreteGaussiansampling[ADRS15] 1.000n 1.000n Nguyen-Vidicksieve[NV08] 0.415n 0.208n GaussSieve[MV10,...,IKMT14,BNvdP14] 0.415n? 0.208n P V Two-levelsieve[WLTB11] 0.384n 0.256n S Three-levelsieve[ZPH13] 0.3778n 0.283n tic Overlatticesieving[BGJ14] 0.3774n 0.293n s uri HyperplaneLSH[Laa15],[MLB15] 0.337n 0.208n e MayandOzerov’sNNSmethod[BGJ15] 0.311n 0.208n H SphericalLSH[LdW15] 0.298n 0.208n Cross-polytopeLSH[BL15] 0.298n 0.208n Nguyen-Vidick sieve O Nguyen-Vidick sieve 1. Sample a list L of random lattice vectors O