[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

A Note on Ring-LWE Security in the Case of Fully Homomorphic Encryption

  • Conference paper
  • First Online:
Progress in Cryptology – INDOCRYPT 2017 (INDOCRYPT 2017)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 10698))

Included in the following conference series:

Abstract

Evaluating the practical security of Ring-LWE based cryptography has attracted lots of efforts recently. Indeed, some differences from the standard LWE problem enable new attacks. In this paper we discuss the security of Ring-LWE as found in Fully Homomorphic Encryption (FHE) schemes. These FHE schemes require parameters of very special shapes, that an attacker might use to its advantage. First we present the specificities of this case and recall state-of-the-art attacks, then we derive a new special-purpose attack. Our experiments show that this attack has unexpected performance and confirm that we need to study the security of special parameters sets carefully.

Funded and supported by Ecole navale, IMT Atlantique, Thales and Naval Group.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 35.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 44.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    https://bitbucket.org/malb/lwe-estimator/overview.

  2. 2.

    Computing the HNF of a matrix is not an intense computation, but can be avoided. See [SL96] for a complexity analysis.

References

  1. 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). https://doi.org/10.1007/978-3-642-22006-7_34

    Chapter  Google Scholar 

  2. Albrecht, M.R.: On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 103–129. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_4

    Chapter  Google Scholar 

  3. Melchor, C.A., Gaborit, P., Herranz, J.: Additively homomorphic encryption with d-operand multiplications. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 138–154. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_8

    Chapter  Google Scholar 

  4. Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of Learning with Errors. Cryptology ePrint Archive, Report 2015/046 (2015)

    Google Scholar 

  5. Babai, L.: On lovász’ lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1–13 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  6. 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). https://doi.org/10.1007/978-3-319-08344-5_21

    Google Scholar 

  7. Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pp. 309–325. ACM (2012)

    Google Scholar 

  8. Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM (JACM) 50(4), 506–519 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  9. Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: Faster fully homomorphic encryption: bootstrapping in less than 0.1 Seconds. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 3–33. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_1

    Chapter  Google Scholar 

  10. 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). https://doi.org/10.1007/978-3-662-49890-3_6

    Chapter  Google Scholar 

  11. Chen, H., Lauter, K., Stange, K.E.: Attacks on Search RLWE. Cryptology ePrint Archive, Report 2015/971 (2015). http://eprint.iacr.org/

  12. 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). https://doi.org/10.1007/978-3-642-25385-0_1

    Chapter  Google Scholar 

  13. CryptoExperts. FV-NFLlib. https://github.com/CryptoExperts/FV-NFLlib

  14. Dowlin, N., Gilad-Bachrach, R., Laine, K., Lauter, K., Naehrig, M., Wernsing, J.: Manual for using homomorphic encryption for bioinformatics. Technical report MSR-TR-2015-87, November 2015

    Google Scholar 

  15. Ducas, L., Micciancio, D.: FHEW: bootstrapping homomorphic encryption in less than a second. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 617–640. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_24

    Google Scholar 

  16. Doröz, Y., Sunar, B.: Flattening NTRU for Evaluation Key Free Homomorphic Encryption (2015). http://eprint.iacr.org/

  17. The FPLLL development team. fplll, a lattice reduction library (2016). https://github.com/fplll/fplll

  18. 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, Cham (2014). https://doi.org/10.1007/978-3-319-13051-4_11

    Chapter  Google Scholar 

  19. Elias, Y., Lauter, K.E., Ozman, E., Stange, K.E.: Provably weak instances of ring-LWE. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 63–92. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_4

    Chapter  Google Scholar 

  20. Fan, J., Vercauteren, F.: Somewhat practical fully homomorphic encryption. IACR Cryptology ePrint Archive 2012:144 (2012)

    Google Scholar 

  21. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC, vol. 9, pp. 169–178 (2009)

    Google Scholar 

  22. Gama, N., Howgrave-Graham, N., Nguyen, P.Q.: Symplectic lattice reduction and NTRU. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 233–253. Springer, Heidelberg (2006). https://doi.org/10.1007/11761679_15

    Chapter  Google Scholar 

  23. Guo, Q., Johansson, T., Stankovski, P.: Coded-BKW: solving LWE using lattice codes. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 23–42. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_2

    Chapter  Google Scholar 

  24. Gama, N., Nguyen, P.Q.: Finding short lattice vectors within mordell’s inequality. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 207–216. ACM (2008)

    Google Scholar 

  25. Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 31–51. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_3

    Chapter  Google Scholar 

  26. Gama, N., Nguyen, P.Q., Regev, O.: Lattice enumeration using extreme pruning. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 257–278. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_13

    Chapter  Google Scholar 

  27. 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). https://doi.org/10.1007/978-3-642-40041-4_5

    Chapter  Google Scholar 

  28. Halevi, S.: Helib. https://github.com/shaih/HElib

  29. Hanrot, G., Pujol, X., Stehlé, D.: Algorithms for the shortest and closest lattice vector problems. In: Chee, Y.M., Guo, Z., Ling, S., Shao, F., Tang, Y., Wang, H., Xing, C. (eds.) IWCC 2011. LNCS, vol. 6639, pp. 159–190. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20901-7_10

    Chapter  Google Scholar 

  30. Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415–440 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  31. Khedr, A., Gulak, G., Vaikuntanathan, V.: SHIELD: scalable homomorphic implementation of encrypted data-classifiers. IEEE Trans. Comput. 65(9), 2848–2858 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  32. Lepoint, T.: A proof-of-concept implementation of the homomorphic evaluation of SIMON using FV and YASHE leveled homomorphic cryptosystems (2014). Accessed 18 Aug 2015

    Google Scholar 

  33. Laine, K., Lauter, K.: Key Recovery for LWE in Polynomial Time. Cryptology ePrint Archive, Report 2015/176 (2015)

    Google Scholar 

  34. Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  35. 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). https://doi.org/10.1007/978-3-642-36095-4_19

    Chapter  Google Scholar 

  36. 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). https://doi.org/10.1007/978-3-319-06734-6_20

    Chapter  Google Scholar 

  37. 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). https://doi.org/10.1007/978-3-642-19074-2_21

    Chapter  Google Scholar 

  38. 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). https://doi.org/10.1007/978-3-642-13190-5_1

    Chapter  Google Scholar 

  39. Micciancio, D., Walter, M.: Practical, predictable lattice basis reduction. Cryptology ePrint Archive, Report 2015/1123 (2015). http://eprint.iacr.org/

  40. Nguên, P.Q., Stehlé, D.: Floating-point LLL revisited. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 215–233. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_13

    Chapter  Google Scholar 

  41. Peikert, C.: A decade of lattice cryptography. Cryptology ePrint Archive, Report 2015/939 (2015). http://eprint.iacr.org/

  42. Peikert, C.: How (Not) to Instantiate Ring-LWE. Cryptology ePrint Archive, Report 2016/351 (2016)

    Google Scholar 

  43. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, pp. 84–93. ACM (2005)

    Google Scholar 

  44. Schnorr, C.-P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66(1–3), 181–199 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  45. Shoup, V.: NTL - A Library for doing Number Theory (2015). Accessed 18 Aug 2015

    Google Scholar 

  46. Storjohann, A., Labahn, G.: Asymptotically fast computation of hermite normal forms of integer matrices. In: Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, pp 259–266. ACM (1996)

    Google Scholar 

  47. van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 24–43. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_2

    Chapter  Google Scholar 

  48. van de Pol, J., Smart, N.P.: Estimating key sizes for high dimensional lattice-based systems. In: Stam, M. (ed.) IMACC 2013. LNCS, vol. 8308, pp. 290–303. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-45239-0_17

    Chapter  Google Scholar 

Download references

Acknowledgements

This work has been supported by the Chair of Naval Cyber Defense, funded by Ecole Navale, IMT-Atlantique, Thales and Naval Group.

Author information

Authors and Affiliations

  1. Chair of Naval Cyber Defense – Ecole Navale, CC600, 29240, Brest Cedex 9, France

    Guillaume Bonnoron

  2. CNRS/Lab-STICC – IMT Atlantique, CS 83818, 29238, Brest Cedex 3, France

    Caroline Fontaine

Authors
  1. Guillaume Bonnoron
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Caroline Fontaine
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Caroline Fontaine .

Editor information

Editors and Affiliations

  1. Indian Institute of Science (IISc), Bengaluru, India

    Arpita Patra

  2. Department of Computer Science, University of Bristol, Bristol, United Kingdom

    Nigel P. Smart

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Bonnoron, G., Fontaine, C. (2017). A Note on Ring-LWE Security in the Case of Fully Homomorphic Encryption. In: Patra, A., Smart, N. (eds) Progress in Cryptology – INDOCRYPT 2017. INDOCRYPT 2017. Lecture Notes in Computer Science(), vol 10698. Springer, Cham. https://doi.org/10.1007/978-3-319-71667-1_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-71667-1_2

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-71666-4

  • Online ISBN: 978-3-319-71667-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation