On the Hardness of Learning With Errors with Binary Secrets

by Daniele Micciancio

Theory of Computing, Volume 14(13), pp. 1-17, 2018

Bibliography with links to cited articles

[1]   Martin R. Albrecht: On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL. In Proc. 36th Ann. Internat. Conf. on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’17), pp. 103–129. Springer, 2017. [doi:10.1007/978-3-319-56614-6_4]

[2]   Martin R. Albrecht, Carlos Cid, Jean-Charles Faugère, Robert Fitzpatrick, and Ludovic Perret: Algebraic algorithms for LWE problems. ACM Comm. Computer Algebra, 49(2):62, 2015. [doi:10.1145/2815111.2815158]

[3]   Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai: Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In Proc. 29th Ann. Internat. Crypto. Conf. (CRYPTO’09), pp. 595–618. Springer, 2009. [doi:10.1007/978-3-642-03356-8_35]

[4]   Sanjeev Arora and Rong Ge: New algorithms for learning in presence of errors. In Proc. 38th Internat. Colloq. on Automata, Languages and Programming (ICALP’11), pp. 403–415. Springer, 2011. [doi:10.1007/978-3-642-22006-7_34]

[5]   Shi Bai and Steven D. Galbraith: Lattice decoding attacks on binary LWE. In Proc. 19th Australasian Conf. on Information Security and Privacy (ACISP’14), pp. 322–337. Springer, 2014. [doi:10.1007/978-3-319-08344-5_21]

[6]   Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé: Classical hardness of learning with errors. In Proc. 45th STOC, pp. 575–584. ACM Press, 2013. [doi:10.1145/2488608.2488680, arXiv:1306.0281]

[7]   Johannes A. Buchmann, Florian Göpfert, Rachel Player, and Thomas Wunderer: On the hardness of LWE with binary error: Revisiting the hybrid lattice-reduction and meet-in-the-middle attack. In Proc. 8th Internat. Conf. on Progress in Cryptology (AFRICACRYPT’16), pp. 24–43. Springer, 2016. [doi:10.1007/978-3-319-31517-1_2]

[8]   Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène: Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. In Proc. 22nd Internat. Conf. on the Theory and Application of Cryptology and Information Security (ASIACRYPT’16), pp. 3–33. Springer, 2016. [doi:10.1007/978-3-662-53887-6_1]

[9]    Léo Ducas and Daniele Micciancio: FHEW: Bootstrapping homomorphic encryption in less than a second. In Proc. 34th Ann. Internat. Conf. on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’15), pp. 617–640. Springer, 2015. [doi:10.1007/978-3-662-46800-5_24]

[10]   Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan: Trapdoors for hard lattices and new cryptographic constructions. In Proc. 40th STOC, pp. 197–206. ACM Press, 2008. [doi:10.1145/1374376.1374407]

[11]   Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert, and Vinod Vaikuntanathan: Robustness of the learning with errors assumption. In Proc. 1st Conf. on Innovations in Theoret. Computer Science (ITCS’10), pp. 230–240. Tsinghua University Press, 2010.

[12]   Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby: A pseudorandom generator from any one-way function. SIAM J. Comput., 28(4):1364–1396, 1999. [doi:10.1137/S0097539793244708]

[13]   Paul Kirchner and Pierre-Alain Fouque: An improved BKW algorithm for LWE with applications to cryptography and lattices. In Proc. 35th Ann. Internat. Crypto. Conf. (CRYPTO’15), pp. 43–62. Springer, 2015. [doi:10.1007/978-3-662-47989-6_3, arXiv:1506.02717]

[14]   Vadim Lyubashevsky, Chris Peikert, and Oded Regev: On ideal lattices and learning with errors over rings. J. ACM, 60(6):43:1–43:35, 2013. Preliminary version in EUROCRYPT’10. [doi:10.1145/2535925]

[15]   Daniele Micciancio: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Comput. Complexity, 16(4):365–411, 2007. Preliminary version in FOCS’02. [doi:10.1007/s00037-007-0234-9]

[16]   Daniele Micciancio and Petros Mol: Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions. In Proc. 31st Ann. Internat. Crypto. Conf. (CRYPTO’11), pp. 465–484. Springer, 2011. [doi:10.1007/978-3-642-22792-9_26]

[17]   Daniele Micciancio and Chris Peikert: Hardness of SIS and LWE with small parameters. In Proc. 33rd Ann. Internat. Crypto. Conf. (CRYPTO’13), pp. 21–39. Springer, 2013. [doi:10.1007/978-3-642-40041-4_2]

[18]   Daniele Micciancio and Oded Regev: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput., 37(1):267–302, 2007. Preliminary version in FOCS’04. [doi:10.1137/S0097539705447360]

[19]   Chris Peikert: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In Proc. 41st STOC, pp. 333–342. ACM Press, 2009. [doi:10.1145/1536414.1536461]

[20]   Chris Peikert, Oded Regev, and Noah Stephens-Davidowitz: Pseudorandomness of ring-LWE for any ring and modulus. In Proc. 49th STOC, pp. 461–473. ACM Press, 2017. [doi:10.1145/3055399.3055489]

[21]   Oded Regev: On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6):34:1–34:40, 2009. Preliminary version in STOC’05. [doi:10.1145/1568318.1568324]

[22]   Oded Regev: The learning with errors problem (invited survey). In Proc. 25th Conf. on Computational Complexity (CCC’10), pp. 191–204. IEEE Comp. Soc. Press, 2010. [doi:10.1109/CCC.2010.26]