Lattice Decoding Attacks on Binary LWE
作者： Shi Bai , Steven D. Galbraith
DOI: 10.1007/978-3-319-08344-5_21
关键词:
摘要: We consider the binary-LWE problem, which is learning with errors problem when entries of secret vector are chosen from { 0, 1} or − 1, 1 }. Our main result an improved lattice decoding algorithm for binary-LWE, by translating to inhomogeneous short integer solution (ISIS) and then re-scaling lattice. also discuss modulus switching as approach problem. conclusion that easier than general LWE. give experimental results, theoretical estimates parameters achieve certain security levels.
springer.com
core.ac.uk 
sci-hub.st 参考文章(22)
Daniele Micciancio, Chris Peikert, Hardness of SIS and LWE with Small Parameters international cryptology conference. ,vol. 2013, pp. 21- 39 ,(2013) , 10.1007/978-3-642-40041-4_2
Yuanmi Chen, Phong Q. Nguyen, BKZ 2.0: better lattice security estimates international conference on the theory and application of cryptology and information security. ,vol. 7073, pp. 1- 20 ,(2011) , 10.1007/978-3-642-25385-0_1
Vadim Lyubashevsky, Lattice Signatures without Trapdoors Advances in Cryptology – EUROCRYPT 2012. ,vol. 7237, pp. 738- 755 ,(2012) , 10.1007/978-3-642-29011-4_43
Vadim Lyubashevsky, Daniele Micciancio, On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem international cryptology conference. pp. 577- 594 ,(2009) , 10.1007/978-3-642-03356-8_34
Mingjie Liu, Phong Q. Nguyen, Solving BDD by enumeration: an update the cryptographers track at the rsa conference. ,vol. 7779, pp. 293- 309 ,(2013) , 10.1007/978-3-642-36095-4_19
Sanjeev Arora, Rong Ge, New algorithms for learning in presence of errors international colloquium on automata languages and programming. pp. 403- 415 ,(2011) , 10.1007/978-3-642-22006-7_34
Nicolas Gama, Phong Q. Nguyen, Predicting Lattice Reduction Advances in Cryptology – EUROCRYPT 2008. pp. 31- 51 ,(2008) , 10.1007/978-3-540-78967-3_3
Nicolas Gama, Phong Q. Nguyen, Oded Regev, Lattice enumeration using extreme pruning theory and application of cryptographic techniques. pp. 257- 278 ,(2010) , 10.1007/978-3-642-13190-5_13
Zvika Brakerski, Vinod Vaikuntanathan, Efficient Fully Homomorphic Encryption from (Standard) LWE 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. pp. 97- 106 ,(2011) , 10.1109/FOCS.2011.12
Oded Regev, On lattices, learning with errors, random linear codes, and cryptography Journal of the ACM. ,vol. 56, pp. 1- 40 ,(2009) , 10.1145/1568318.1568324