×

zbMATH — the first resource for mathematics

On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL. (English) Zbl 1415.94402
Coron, Jean-Sébastien (ed.) et al., Advances in cryptology – EUROCRYPT 2017. 36th annual international conference on the theory and applications of cryptographic techniques, Paris, France, April 30 – May 4, 2017. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 10211, 103-129 (2017).
Summary: We present novel variants of the dual-lattice attack against LWE in the presence of an unusually short secret. These variants are informed by recent progress in BKW-style algorithms for solving LWE. Applying them to parameter sets suggested by the homomorphic encryption libraries HElib and SEAL yields revised security estimates. Our techniques scale the exponent of the dual-lattice attack by a factor of \((2\,L)/(2\,L+1)\) when \(\log q = \varTheta {\left(L \log n\right)}\), when the secret has constant hamming weight \(h\) and where \(L\) is the maximum depth of supported circuits. They also allow to half the dimension of the lattice under consideration at a multiplicative cost of \(2^{h}\) operations. Moreover, our techniques yield revised concrete security estimates. For example, both libraries promise 80 bits of security for LWE instances with \(n=1024\) and \(\log_2 q \approx {47}\), while the techniques described in this work lead to estimated costs of 68 bits (SEAL) and 62 bits (HElib).
For the entire collection see [Zbl 1360.94006].

MSC:
94A60 Cryptography
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Albrecht, M., Bai, S., Ducas, L.: A subfield lattice attack on overstretched NTRU assumptions. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 153–178. Springer, Heidelberg (2016). doi: 10.1007/978-3-662-53018-4_6 · Zbl 1351.94019 · doi:10.1007/978-3-662-53018-4_6
[2] Albrecht, M.R., Cid, C., Faugère, J.-C., Fitzpatrick, R., Perret, L.: On the complexity of the BKW algorithm on LWE. Des. Codes Crypt. 74, 325–354 (2015) · Zbl 1331.94051 · doi:10.1007/s10623-013-9864-x
[3] Albrecht, M.R., Cid, C., Faugère, J.-C., Perret, L.: Algebraic algorithms for LWE. Cryptology ePrint Archive, Report 2014/1018 (2014). http://eprint.iacr.org/2014/1018
[4] Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 595–618. Springer, Heidelberg (2009). doi: 10.1007/978-3-642-03356-8_35 · Zbl 1252.94044 · doi:10.1007/978-3-642-03356-8_35
[5] Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange - a new hope. Cryptology ePrint Archive, Report 2015/1092 (2015). http://eprint.iacr.org/2015/1092
[6] Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange - a new hope. In: Holz, T., Savage, S. (eds.) 25th USENIX Security Symposium, USENIX Security, vol. 16, Austin, TX, USA, 10–12 August 2016, pp. 327–343. USENIX Association (2016)
[7] Albrecht, M.R., Faugère, J.-C., Fitzpatrick, R., Perret, L.: Lazy modulus switching for the bkw algorithm on LWE. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 429–445. Springer, Heidelberg (2014). doi: 10.1007/978-3-642-54631-0_25 · Zbl 1335.94025 · doi:10.1007/978-3-642-54631-0_25
[8] Albrecht, M.R., Fitzpatrick, R., Göpfert, F.: On the efficacy of solving LWE by reduction to unique-SVP. In: Lee, H.-S., Han, D.-G. (eds.) ICISC 2013. LNCS, vol. 8565, pp. 293–310. Springer, Cham (2014). doi: 10.1007/978-3-319-12160-4_18 · Zbl 1368.94082 · doi:10.1007/978-3-319-12160-4_18
[9] Arora, S., Ge, R.: New algorithms for learning in presence of errors. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6755, pp. 403–415. Springer, Heidelberg (2011). doi: 10.1007/978-3-642-22006-7_34 · Zbl 1332.68099 · doi:10.1007/978-3-642-22006-7_34
[10] Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: 28th ACM STOC, pp. 99–108. ACM Press, May 1996 · Zbl 0921.11071 · doi:10.1145/237814.237838
[11] Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of Learning with Errors. J. Math. Cryptology 9(3), 169–203 (2015) · Zbl 1352.94023 · doi:10.1515/jmc-2015-0016
[12] Bos, J.W., Costello, C., Ducas, L., Mironov, I., Naehrig, M., Nikolaenko, V., Raghunathan, A., Stebila, D.: Frodo: take off the ring! practical, quantum-secure key exchange from LWE. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, pp. 1006–1018. ACM Press, October 2016 · doi:10.1145/2976749.2978425
[13] Bos, J.W., Costello, C., Naehrig, M., Stebila, D.: Post-quantum key exchange for the TLS protocol from the ring learning with errors problem. In: 2015 IEEE Symposium on Security and Privacy, pp. 553–570. IEEE Computer Society Press, May 2015 · doi:10.1109/SP.2015.40
[14] Becker, A., Ducas, L., Gama, N., Laarhoven, T.: New directions in nearest neighbor searching with applications to lattice sieving. In: Krauthgamer, R. (ed.) 27th SODA, pp. 10–24. ACM-SIAM, January 2016 · Zbl 1410.68093 · doi:10.1137/1.9781611974331.ch2
[15] Bai, S., Galbraith, S.D.: Lattice decoding attacks on binary LWE. In: Susilo, W., Mu, Y. (eds.) ACISP 2014. LNCS, vol. 8544, pp. 322–337. Springer, Cham (2014). doi: 10.1007/978-3-319-08344-5_21 · Zbl 1337.94020 · doi:10.1007/978-3-319-08344-5_21
[16] Buchmann, J., Göpfert, F., Player, R., Wunderer, T.: On the hardness of LWE with binary error: revisiting the hybrid lattice-reduction and meet-in-the-middle attack. In: Pointcheval, D., Nitaj, A., Rachidi, T. (eds.) AFRICACRYPT 2016. LNCS, vol. 9646, pp. 24–43. Springer, Cham (2016). doi: 10.1007/978-3-319-31517-1_2 · Zbl 1345.94045 · doi:10.1007/978-3-319-31517-1_2
[17] Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Goldwasser, S. (ed.), ITCS 2012, pp. 309–325. ACM, January 2012 · Zbl 1347.68120 · doi:10.1145/2090236.2090262
[18] Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. In: 32nd ACM STOC, pp. 435–440. ACM Press, May 2000 · Zbl 1296.68122 · doi:10.1145/335305.335355
[19] Bos, J.W., Lauter, K., Loftus, J., Naehrig, M.: Improved security for a ring-based fully homomorphic encryption scheme. In: Stam, M. (ed.) IMACC 2013. LNCS, vol. 8308, pp. 45–64. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-45239-0_4 · Zbl 1317.94088 · doi:10.1007/978-3-642-45239-0_4
[20] Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) 45th ACM STOC, pp. 575–584. ACM Press, June 2013 · Zbl 1293.68159 · doi:10.1145/2488608.2488680
[21] Brakerski, Z.: Fully homomorphic encryption without modulus switching from classical GapSVP. In: In Safavi-Naini and Canetti [SNC12], pp. 868–886 · Zbl 1296.94091 · doi:10.1007/978-3-642-32009-5_50
[22] Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: Ostrovsky, R. (ed.) 52nd FOCS, pp. 97–106. IEEE Computer Society Press, October 2011 · Zbl 1292.94038
[23] Chen, Y.: Réduction de réseau et sécurité concrète du chiffrement complètement homomorphe. PhD thesis, Paris 7 (2013)
[24] Cheon, J.H., Han, K., Kim, J., Lee, C., Son, Y.: A practical post-quantum public-key cryptosystem based on spLWE. In: Hong, S., Park, J.H. (eds.) ICISC 2016. LNCS, vol. 10157, pp. 51–74. Springer, Cham (2017). doi: 10.1007/978-3-319-53177-9_3 · Zbl 1381.94067 · doi:10.1007/978-3-319-53177-9_3
[25] Cheon, J.H., Stehlé, D.: Fully homomophic encryption over the integers revisited. In: Oswald and Fischlin [OF15], pp. 513–536 · Zbl 1370.94496 · doi:10.1007/978-3-662-46800-5_20
[26] Chen, Y., Nguyen, P.Q.: BKZ 2.0: better lattice security estimates. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 1–20. Springer, Heidelberg (2011). doi: 10.1007/978-3-642-25385-0_1 · Zbl 1227.94037 · doi:10.1007/978-3-642-25385-0_1
[27] Chen, Y., Nguyen, P.Q.: BKZ 2.0: Better lattice security estimates (full version) (2012). http://www.di.ens.fr/ ychen/research/Full_BKZ.pdf · Zbl 1227.94037
[28] Costache, A., Smart, N.P.: Which ring based somewhat homomorphic encryption scheme is best? In: Sako, K. (ed.) CT-RSA 2016. LNCS, vol. 9610, pp. 325–340. Springer, Cham (2016). doi: 10.1007/978-3-319-29485-8_19 · Zbl 1334.94070 · doi:10.1007/978-3-319-29485-8_19
[29] Ding, J., Xie, X., Lin, X.: A simple provably secure key exchange scheme based on the learning with errors problem. Cryptology ePrint Archive, Report 2012/688 (2012). http://eprint.iacr.org/2012/688
[30] Duc, A., Tramèr, F., Vaudenay, S.: Better algorithms for LWE and LWR. In: Oswald and Fischlin [OF15], pp. 173–202 · Zbl 1365.94424 · doi:10.1007/978-3-662-46800-5_8
[31] The FPLLL development team. FPLLL 5.0, a lattice reduction library (2016). https://github.com/fplll/fplll
[32] Fan, J., Vercauteren, F.: Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Report 2012/144 (2012). http://eprint.iacr.org/2012/144
[33] Gentry, C., Halevi, S., Smart, N.P.: Homomorphic evaluation of the AES Circuit. In: Safavi-Naini and Canetti [SNC12], pages 850–867 · Zbl 1296.94117 · doi:10.1007/978-3-642-32009-5_49
[34] Gentry, C., Halevi, S., Smart, N.P.: Homomorphic evaluation of the AES circuit. Cryptology ePrint Archive, Report 2012/099 (2012). http://eprint.iacr.org/2012/099 · Zbl 1296.94117
[35] Guo, Q., Johansson, T., Stankovski, P.: Coded-BKW: solving LWE using lattice codes. In: Gennaro and Robshaw [GR15], pp. 23–42 · Zbl 1336.94051 · doi:10.1007/978-3-662-47989-6_2
[36] Gennaro, R., Robshaw, M. (eds.): CRYPTO 2015. LNCS, vol. 9215. Springer, Heidelberg (2015) · Zbl 1319.94003
[37] Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 75–92. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-40041-4_5 · Zbl 1310.94148 · doi:10.1007/978-3-642-40041-4_5
[38] Howgrave-Graham, N.: A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 150–169. Springer, Heidelberg (2007). doi: 10.1007/978-3-540-74143-5_9 · Zbl 1215.94053 · doi:10.1007/978-3-540-74143-5_9
[39] Hanrot, G., Pujol, X., Stehlé, D.: Analyzing blockwise lattice algorithms using dynamical systems. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 447–464. Springer, Heidelberg (2011). doi: 10.1007/978-3-642-22792-9_25 · Zbl 1287.94072 · doi:10.1007/978-3-642-22792-9_25
[40] Halevi, S., Shoup, V.: Algorithms in HElib. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 554–571. Springer, Heidelberg (2014). doi: 10.1007/978-3-662-44371-2_31 · Zbl 1343.94061 · doi:10.1007/978-3-662-44371-2_31
[41] Kirchner, P., Fouque, P.-A.: An improved BKW algorithm for LWE with applications to cryptography and lattices. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 43–62. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-47989-6_3 · Zbl 1336.94058 · doi:10.1007/978-3-662-47989-6_3
[42] Kirchner, P., Fouque, P.-A.: Comparison between subfield and straightforward attacks on NTRU. IACR Cryptology ePrint Archive, 2016: 717 (2016)
[43] Kim, M., Lauter, K.: Private genome analysis through homomorphic encryption. BMC Med. Inform. Decis. Mak. 15(5), 1–12 (2015)
[44] Laarhoven, T.: Sieving for shortest vectors in lattices using angular locality-sensitive hashing. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 3–22. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-47989-6_1 · Zbl 1336.94060 · doi:10.1007/978-3-662-47989-6_1
[45] Laine, K., Chen, H., Player, R.: Simple Encrypted Arithmetic Library - SEAL (v2.1). Technical report, Microsoft Research, MSR-TR-2016-68, September 2016
[46] Liu, M., Nguyen, P.Q.: Solving BDD by enumeration: an update. In: Dawson, E. (ed.) CT-RSA 2013. LNCS, vol. 7779, pp. 293–309. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-36095-4_19 · Zbl 1312.94070 · doi:10.1007/978-3-642-36095-4_19
[47] Lepoint, T., Naehrig, M.: A comparison of the homomorphic encryption schemes FV and YASHE. In: Pointcheval, D., Vergnaud, D. (eds.) AFRICACRYPT 2014. LNCS, vol. 8469, pp. 318–335. Springer, Cham (2014). doi: 10.1007/978-3-319-06734-6_20 · Zbl 1318.94071 · doi:10.1007/978-3-319-06734-6_20
[48] Lindner, R., Peikert, C.: Better key sizes (and attacks) for lwe-based encryption. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 319–339. Springer, Heidelberg (2011). doi: 10.1007/978-3-642-19074-2_21 · Zbl 1284.94088 · doi:10.1007/978-3-642-19074-2_21
[49] Laine, K., Player, R.: Simple Encrypted Arithmetic Library - SEAL (v2.0). Technical report, Microsoft Research, MSR-TR-2016-52, September 2016
[50] Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 1–23. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-13190-5_1 · Zbl 1279.94099 · doi:10.1007/978-3-642-13190-5_1
[51] Lyubashevsky, V., Peikert, C., Regev, O.: A toolkit for ring-LWE cryptography. Cryptology ePrint Archive, Report 2013/293 (2013). http://eprint.iacr.org/2013/293 · Zbl 1300.94082
[52] López-Alt, A., Tromer, E., Vaikuntanathan, V.: On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In: Karloff, H.J., Pitassi, T. (eds.) 44th ACM STOC, pp. 1219–1234. ACM Press, May 2012 · Zbl 1286.68114 · doi:10.1145/2213977.2214086
[53] Micciancio, D., Regev, O.: Lattice-based cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.) Post-Quantum Cryptography, Heidelberg, New York, pp. 147–191 (2009) · Zbl 1161.81324 · doi:10.1007/978-3-540-88702-7_5
[54] Oswald, E., Fischlin, M. (eds.): EUROCRYPT 2015. LNCS, vol. 9056. Springer, Heidelberg (2015) · Zbl 1321.94010
[55] Peikert, C.: Some recent progress in lattice-based cryptography. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 72–72. Springer, Heidelberg (2009). doi: 10.1007/978-3-642-00457-5_5 · Zbl 1213.94127 · doi:10.1007/978-3-642-00457-5_5
[56] Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th ACM STOC, pp. 84–93. ACM Press, May 2005 · Zbl 1192.94106 · doi:10.1145/1060590.1060603
[57] Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 1–40 (2009) · Zbl 1325.68101 · doi:10.1145/1568318.1568324
[58] Stein, W., et al.: Sage Mathematics Software Version 7.1. The Sage Development Team (2015). http://www.sagemath.org
[59] Schnorr, C.P.: Lattice reduction by random sampling and birthday methods. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 145–156. Springer, Heidelberg (2003). doi: 10.1007/3-540-36494-3_14 · Zbl 1035.68113 · doi:10.1007/3-540-36494-3_14
[60] Shoup, V.: NTL: A library for doing number theory (2001). http://www.shoup.net/ntl/
[61] Sarma, J., Lunawat, P.: IITM-CS6840: Advanced Complexity Theory – Lecture 11: Amplification Lemma (2012). http://www.cse.iitm.ac.in/ jayalal/teaching/CS6840/2012/lecture11.pdf
[62] Safavi-Naini, R., Canetti, R. (eds.): CRYPTO 2012. LNCS, vol. 7417. Springer, Heidelberg (2012) · Zbl 1246.94010
[63] Walter, M.: Lattice point enumeration on block reduced bases. In: Lehmann, A., Wolf, S. (eds.) ICITS 2015. LNCS, vol. 9063, pp. 269–282. Springer, Cham (2015). doi: 10.1007/978-3-319-17470-9_16 · Zbl 1359.94630 · doi:10.1007/978-3-319-17470-9_16
[64] Wunderer, T.: Revisiting the hybrid attack: Improved analysis and refined security estimates. Cryptology ePrint Archive, Report 2016/733 (2016). http://eprint.iacr.org/2016/733
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.