A Subfield Lattice Attack on Overstretched NTRU Assumptions

详细信息    查看全文

• 关键词：Subfield lattice attack ; Overstretched NTRU ; FHE ; Graded encoding schemes
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9814
• 期：1
• 页码：153-178
• 全文大小：402 KB
• 参考文献：[ABC+]Albrecht, M., Bai, S., Cadé, D., Pujol, X., Stehlé, D.: fpLLL-4.0, a floating-point LLL implementation. https://​github.​com/​dstehle/​fplll
  [ACLL15]Albrecht, M.R., Cocis, C., Laguillaumie, F., Langlois, A.: Implementing candidate graded encoding schemes from ideal lattices. In: Iwata, T., et al. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 752–775. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-48800-3_​31 CrossRef
  [BCLvV16]Bernstein, D.J., Chuengsatiansup, C., Lange, T., van Vredendaal, C.: NTRU prime. Cryptology ePrint Archive, Report 2016/461 (2016). http://​eprint.​iacr.​org/​
  [Ber14]Bernstein, D.: A subfield-logarithm attack against ideal lattices, Febuary 2014. http://​blog.​cr.​yp.​to/​20140213-ideal.​html
  [BF14]Biasse, J.-F., Fieker, C.: Subexponential class group, unit group computation in large degree number fields. LMS J. Comput. Math. 17(Suppl. A), 385–403 (2014)MathSciNet CrossRef MATH
  [Bia14]Biasse, J.-F.: Subexponential time relations in the class group of large degree number fields. Adv. Math. Commun. 8(4), 407–425 (2014)MathSciNet CrossRef MATH
  [BLLN13]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)CrossRef
  [BS16]Biasse, J.-F., Song, F.: Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. In: 27th ACM-SIAM Symposium on Discrete Algorithms (SODA 2016) (2016)
  [BV11]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
  [CDPR16]Cramer, R., Ducas, L., Peikert, C., Regev, O.: Recovering short generators of principal ideals in cyclotomic rings. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 559–585. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49896-5_​20 CrossRef
  [CG13]Canetti, R., Garay, J.A. (eds.): CRYPTO 2013. LNCS, vol. 8042. Springer, Heidelberg (2013)MATH
  [CGS14]Campbell, P., Groves, M., Shepherd, D.: Soliloquy: a cautionary tale. In: ETSI 2nd Quantum-Safe Crypto Workshop (2014). http://​docbox.​etsi.​org/​Workshop/​2014/​201410_​CRYPTO/​S07_​Systems_​and_​Attacks/​S07_​Groves_​Annex.​pdf
  [CIV16]Castryck, W., Iliashenko, I., Vercauteren, F.: Provably weak instances of ring-LWE revisited. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 147–167. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49890-3_​6 CrossRef
  [CJL16]Cheon, J.H., Jeong, J., Lee, C.: An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without an encoding of zero. Cryptology ePrint Archive, Report 2016/139 (2016). http://​eprint.​iacr.​org/​
  [CLS15]Chen, H., Lauter, K., Stange, K.E.: Attacks on search RLWE. Cryptology ePrint Archive, Report 2015/971 (2015). http://​eprint.​iacr.​org/​2015/​971
  [CLT13]Coron, J.-S., Lepoint, T., Tibouchi, M.: Practical multilinear maps over the integers. In: Canetti, R., Garay, J.A. (eds.) [CG13], pp. 476–493
  [CN11]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)CrossRef
  [CS97]Coppersmith, D., Shamir, A.: Lattice attacks on NTRU. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 52–61. Springer, Heidelberg (1997)
  [CS15]Costache, A., Smart, N.P.: Which ring based somewhat homomorphic encryption scheme is best? Cryptology ePrint Archive, Report 2015/889 (2015). http://​eprint.​iacr.​org/​2015/​889
  [DDLL13]Ducas, L., Durmus, A., Lepoint, T., Lyubashevsky, V.: Lattice signatures and bimodal gaussians. In: Canetti, R., Garay, J.A. (eds.) [CG13], pp. 40–56
  [Dev15]The Sage Developers: Sage Mathematics Software (2015). http://​www.​sagemath.​org
  [DHS15]Doröz, Y., Yin, H., Sunar, B.: Homomorphic AES evaluation using the modified LTV scheme. Des. Codes Crypt. 80(2), 333–358 (2016). http://​dx.​doi.​org/​10.​1007/​s10623-015-0095-1 MathSciNet CrossRef
  [EHKS14]Eisenträger, K., Hallgren, S., Kitaev, A., Song, F.: A quantum algorithm for computing the unit group of an arbitrary degree number field. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 293–302. ACM (2014)
  [EHL14]Eisenträger, K., Hallgren, S., Lauter, K.: Weak instances of PLWE. In: Joux, A., Youssef, A. (eds.) SAC 2014. LNCS, vol. 8781, pp. 183–194. Springer, Heidelberg (2014)CrossRef
  [ELOS15]Elias, Y., Lauter, K.E., Ozman, E., Stange, K.E.: Provably weak instances of ring-LWE. In: Gennaro, R., Robshaw, M. (eds.) [GR15], pp. 63–92
  [FM14]Ferraguti, A., Micheli, G.: On the Mertens-Cesàro theorem for number fields. Bull. Aust. Math. Soc. 93(2), 199–210 (2016). doi:10.​1017/​S000497271500128​8 . http://​journals.​cambridge.​org/​article_​S000497271500128​8 MathSciNet CrossRef MATH
  [Gen01]Gentry, C.: Key recovery and message attacks on NTRU-composite. In: Pfitzmann, B. (ed.) [Pfi01], pp. 182–194
  [GGH13a]Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 1–17. Springer, Heidelberg (2013)CrossRef
  [GGH+13b]Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: 54th FOCS, pp. 40–49. IEEE Computer Society Press, October 2013
  [GN08]Gama, N., Nguyen, P.Q.: Finding short lattice vectors within Mordell’s inequality. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 207–216. ACM Press, May 2008
  [GR15]Gennaro, R., Robshaw, M. (eds.): CRYPTO 2015. LNCS, vol. 9215. Springer, Heidelberg (2015)MATH
  [GS02]Gentry, C., Szydlo, M.: Cryptanalysis of the revised NTRU signature scheme. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 299–320. Springer, Heidelberg (2002)CrossRef
  [HG07]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)CrossRef
  [HHGP+03]Hoffstein, J., Howgrave-Graham, N., Pipher, J., Silverman, J.H., Whyte, W.: NTRUSIGN: digital signatures using the NTRU lattice. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 122–140. Springer, Heidelberg (2003)CrossRef
  [HJ15]Hu, Y., Jia, H.: Cryptanalysis of GGH map. Cryptology ePrint Archive, Report 2015/301 (2015). http://​eprint.​iacr.​org/​2015/​301
  [HPS96]Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a new high speed public key cryptosystem. In: Draft Distributed at Crypto 1996 (1996). http://​web.​securityinnovati​on.​com/​hubfs/​files/​ntru-orig.​pdf
  [HPS98]Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998)CrossRef
  [HPS01]Hoffstein, J., Pipher, J., Silverman, J.H.: NSS: an NTRU lattice-based signature scheme. In: Pfitzmann, B. (ed.) [Pfi01], pp. 211–228
  [HPS11]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)CrossRef
  [HPS+15]Hoffstein, J., Pipher, J., Schanck, J.M., Silverman, J.H., Whyte, W., Zhang, Z.: Choosing parameters for NTRUEncrypt. Cryptology ePrint Archive, Report 2015/708 (2015). http://​eprint.​iacr.​org/​2015/​708
  [HSW06]Hoffstein, J., Silverman, J.H., Whyte, W.: Meet-in-the-middle attack on an ntru private key, 2006. Technical report, NTRU Cryptosystems, Report #04, July 2006. http://​www.​ntru.​com
  [HT15]Hauteville, A., Tillich, J.-P.: New algorithms for decoding in the rank metric and an attack on the LRPC cryptosystem. In: IEEE International Symposium on Information Theory, ISIT 2015, pp. 2747–2751 (2015)
  [KF15]Kirchner, P., Fouque, P.-A.: An improved BKW algorithm for LWE with applications to cryptography and lattices. In: Gennaro, R., Robshaw, M. (eds.) [GR15], pp. 43–62
  [LJ14]Löndahl, C., Johansson, T.: Improved algorithms for finding low-weight polynomial multiples in \(f_{2}[x]\) and some cryptographic applications. Des. Codes Crypt. 73(2), 625–640 (2014)CrossRef MATH
  [LLL82]Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982)MathSciNet CrossRef MATH
  [LN14]Lepoint, T., Naehrig, M.: A comparison of the homomorphic encryption schemes \(\sf {FV}\) and \(\sf {YASHE}\) . In: Pointcheval, D., Vergnaud, D. (eds.) AFRICACRYPT. LNCS, vol. 8469, pp. 318–335. Springer, Heidelberg (2014)CrossRef
  [Loi14]Loidreau, P.: On cellular codes and their cryptographic applications. In: ACCT, Fourteenth International Workshop on Algebraic and Combinatorial Coding Theory, pp. 234–239 (2014)
  [Lov87]Lovasz, L.: An Algorithmic Theory of Numbers, Graphs and Convexity. CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics, Philadelphia (1987)MATH
  [LPR10]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)CrossRef
  [LS14]Lenstra, H.W., Silverberg, A.: Revisiting the Gentry-Szydlo algorithm. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 280–296. Springer, Heidelberg (2014)CrossRef
  [LSS14]Langlois, A., Stehlé, D., Steinfeld, R.: GGHLite: more efficient multilinear maps from ideal lattices. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 239–256. Springer, Heidelberg (2014)CrossRef
  [LTV12]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
  [Mic02]Micciancio, D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions. In: 43rd FOCS, pp. 356–365. IEEE Computer Society Press, November 2002
  [Pei16]Peikert, C.: How (not) to instantiate ring-LWE. Cryptology ePrint Archive, Report 2016/351 (2016). http://​eprint.​iacr.​org/​
  [Pfi01]Pfitzmann, B. (ed.): EUROCRYPT 2001. LNCS, vol. 2045. Springer, Heidelberg (2001)MATH
  [Pol74]Pollard, J.M.: Theorems on factorization and primality testing. In: Math-ematical Proceedings of the Cambridge Philosophical Society, vol. 76, no. 03, pp. 521–528 (1974)
  [Sam70]Samuel, P.: Algebraic Theory of Numbers. Hermann, Paris (1970)MATH
  [Sch87]Schnorr, C.-P.: A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci. 53, 201–224 (1987)MathSciNet CrossRef MATH
  [Sit10]Sittinger, B.D.: The probability that random algebraic integers are relatively r-prime. J. Number Theory 130(1), 164–171 (2010)MathSciNet CrossRef MATH
  [SS11]Stehlé, D., Steinfeld, R.: Making NTRU as secure as worst-case problems over ideal lattices. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 27–47. Springer, Heidelberg (2011)CrossRef
  [SSTX09]Stehlé, D., Steinfeld, R., Tanaka, K., Xagawa, K.: Efficient public key encryption based on ideal lattices. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 617–635. Springer, Heidelberg (2009)CrossRef
  [Was97]Washington, L.C.: Introduction to Cyclotomic Fields. Graduate Texts in Mathematics. Springer, New York (1997)CrossRef MATH
  
• 作者单位：Martin Albrecht (15)
  Shi Bai (16)
  Léo Ducas (17)
  
  15. Information Security Group, Royal Holloway, University of London, London, UK
  16. ENS de Lyon, Laboratoire LIP (U. Lyon, CNRS, ENSL, INRIA, UCBL), Lyon, France
  17. Cryptology Group, CWI, Amsterdam, The Netherlands
  
• 丛书名：Advances in Cryptology – CRYPTO 2016
• ISBN：978-3-662-53018-4
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9814

文摘

The subfield attack exploits the presence of a subfield to solve overstretched versions of the NTRU assumption: norming the public key h down to a subfield may lead to an easier lattice problem and any sufficiently good solution may be lifted to a short vector in the full NTRU-lattice. This approach was originally sketched in a paper of Gentry and Szydlo at Eurocrypt’02 and there also attributed to Jonsson, Nguyen and Stern. However, because it does not apply for small moduli and hence NTRUEncrypt, it seems to have been forgotten. In this work, we resurrect this approach, fill some gaps, analyze and generalize it to any subfields and apply it to more recent schemes. We show that for significantly larger moduli — a case we call overstretched — the subfield attack is applicable and asymptotically outperforms other known attacks.