Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Bootstrapping BGV ciphertexts with a wider choice of p and q

© The Institution of Engineering and Technology
Received 06/11/2015, Accepted 18/02/2016, Revised 04/02/2016, Published 08/04/2016

The authors describe a method to bootstrap a packed BGV ciphertext which does not depend (as much) on any special properties of the plaintext and ciphertext moduli. Prior ‘efficient’ methods such as that of Gentry et al. (PKC 2012) required a ciphertext modulus q which was close to a power of the plaintext modulus p. This enables the authors’ method to be applied in a larger number of situations. The authors’ basic bootstrapping technique makes use of a representation based on polynomials of the group over the finite field , followed by polynomial interpolation of the reduction mod p map over the coefficients of the algebraic group. This technique is then extended to the full BGV packed ciphertext space, using a method whose depth depends only logarithmically on the number of packed elements. This method may be of interest as an alternative to the method of Alperin-Sheriff and Peikert (CRYPTO 2013). To aid efficiency, the authors utilise the ring/field switching technique of Gentry et al. (SCN 2012, JCS 2013).

Inspec keywords: interpolation; polynomials; cryptography

Other keywords: bootstrapping technique; reduction mod p map; full BGV packed ciphertext space; polynomial interpolation; plaintext modulus

Subjects: Interpolation and function approximation (numerical analysis); Algebra; Cryptography; Data security; Algebra; Interpolation and function approximation (numerical analysis)

References

    1. 1)
      • 2. Gentry, C.: ‘Fully homomorphic encryption using ideal lattices’. STOC, 2009, pp. 169–178.
    2. 2)
      • 19. Gentry, C., Halevi, S., Peikert, C., et al: ‘Field switching in BGV-style homomorphic encryption’, J. Comput. Secur., 2013, 21, (5), pp. 663–684.
    3. 3)
      • 6. Brakerski, Z.: ‘Fully homomorphic encryption without modulus switching from classical GapSVP’. CRYPTO, 2012 (LNCS, 7417), pp. 868–886.
    4. 4)
      • 15. Lyubashevsky, V., Peikert, C., Regev, O.: ‘On ideal lattices and learning with errors over rings’. EUROCRYPT, 2010 (LNCS, 6110), pp. 1–23.
    5. 5)
      • 10. Cheon, J.H., Coron, J.S., Kim, J., et al: ‘Batch fully homomorphic encryption over the integers’. EUROCRYPT, 2013 (LNCS, 7881), pp. 315–335.
    6. 6)
      • 12. Gentry, C., Halevi, S., Smart, N.P.: ‘Fully homomorphic encryption with polylog overhead’. EUROCRYPT, 2012 (LNCS, 7237), pp. 465–482.
    7. 7)
      • 22. Gentry, C., Halevi, S., Smart, N.P.: ‘Homomorphic evaluation of the AES circuit’. CRYPTO, 2012 (LNCS, 7417), pp. 850–867.
    8. 8)
      • 33. Micciancio, D., Regev, O.: ‘Lattice-based cryptography’. Post-Quantum Cryptography, 2009, pp. 147–191.
    9. 9)
      • 25. Lyubashevsky, V., Peikert, C., Regev, O.: ‘A toolkit for ring-LWE cryptography’. EUROCRYPT, 2013 (LNCS, 7881), pp. 35–54.
    10. 10)
      • 9. Brakerski, Z., Vaikuntanathan, V.: ‘Lattice-based FHE as secure as PKE’. ITCS, 2014, pp. 1–12.
    11. 11)
      • 14. Brakerski, Z., Gentry, C., Vaikuntanathan, V.: ‘In (leveled) fully homomorphic encryption without bootstrapping’. ITCS, 2012, pp. 309–325.
    12. 12)
      • 4. Alperin-Sheriff, J., Peikert, C.: ‘Faster bootstrapping with polynomial error’. CRYPTO, 2014 (LNCS, 8616), pp. 297–314.
    13. 13)
      • 16. Gentry, C., Halevi, S.: ‘Implementing Gentry's fully-homomorphic encryption scheme’. EUROCRYPT, 2011 (LNCS, 6632), pp. 129–148.
    14. 14)
      • 1. Gentry, C.: ‘A fully homomorphic encryption scheme’ (Stanford University, 2009), crypto.stanford.edu/craig.
    15. 15)
      • 24. Damgård, I., Pastro, V., Smart, N.P., et al: ‘Multiparty computation from somewhat homomorphic encryption’. CRYPTO, 2012 (LNCS, 7417), pp. 643–662.
    16. 16)
      • 8. Brakerski, Z., Vaikuntanathan, V.: ‘Fully homomorphic encryption from ring-LWE and security for key dependent messages’. CRYPTO, 2011 (LNCS, 6841), pp. 505–524.
    17. 17)
      • 28. Choudhury, A., Loftus, J., Orsini, E., et al: ‘Between a rock and a hard place: interpolating between MPC and FHE’. ASIACRYPT, 2013 (LNCS, 8270), pp. 221–240.
    18. 18)
      • 18. Smart, N.P., Vercauteren, F.: ‘Fully homomorphic SIMD operations’, Des. Codes Cryptogr., 2014, 71, pp. 57–81.
    19. 19)
      • 17. Smart, N.P., Vercauteren, F.: ‘Fully homomorphic encryption with relatively small key and ciphertext sizes’. PKC, 2010 (LNCS, 6056), pp. 420–443.
    20. 20)
      • 5. Ducas, L., Micciancio, D.: ‘FHEW: bootstrapping homomorphic encryption in less than a second’. Advances in Cryptology – EUROCRYPT 2015 – 34th Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, 26–30 April 2015, Proceedings, Part I, pp. 617–640.
    21. 21)
      • 20. Rohloff, K., Cousins, D.B.: ‘A scalable implementation of fully homomorphic encryption built on NTRU’. Financial Cryptography, 2014 (LNCS, 8438), pp. 221–234.
    22. 22)
      • 26. Halevi, S., Shoup, V.: ‘Algorithms in HElib’. Advances in Cryptology – EUROCRYPT 2015 – 34th Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, 26-30 April 2015, Proceedings, Part I, pp. 641–670.
    23. 23)
      • 30. Lepoint, T., Naehrig, M.: ‘A comparison of the homomorphic encryption schemes FV and YASHE’. AFRICACRYPT, 2014 (LNCS, 8469), pp. 318–335.
    24. 24)
      • 31. Lindner, R., Peikert, C.: ‘Better key sizes (and attacks) for LWE-based encryption’. CT-RSA, 2011 (LNCS, 6558), pp. 319–339.
    25. 25)
      • 32. Chen, Y., Nguyen, P.Q.: ‘BKZ 2.0: better lattice security estimates’. ASIACRYPT, 2011 (LNCS, 7073), pp. 1–20.
    26. 26)
      • 3. Alperin-Sheriff, J., Peikert, C.: ‘Practical bootstrapping in quasilinear time’. CRYPTO, 2013 (LNCS, 8042), pp. 1–20.
    27. 27)
      • 29. van de Pol, J., Smart, N.P.: ‘Estimating key sizes for high dimensional lattice-based systems’. IMA Int. Conf., 2013 (LNCS, 8308), pp. 290–303.
    28. 28)
      • 23. Orsini, E., van de Pol, J., Smart, N.P.: ‘Bootstrapping BGV ciphertexts with a wider choice of p and q’. Public-Key Cryptography – PKC 2015 – 18th IACR Int. Conf. on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, 30 March –1 April 2015, Proceedings, pp. 673–698.
    29. 29)
      • 7. Brakerski, Z., Vaikuntanathan, V.: ‘Efficient fully homomorphic encryption from (standard) LWE’. FOCS, 2011, pp. 97–106.
    30. 30)
      • 13. van Dijk, M., Gentry, C., Halevi, S., et al: ‘Fully homomorphic encryption over the integers’. EUROCRYPT, 2010 (LNCS, 6110), pp. 24–43.
    31. 31)
      • 21. Gentry, C., Sahai, A., Waters, B.: ‘Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based’. CRYPTO, 2013 (LNCS, 8042), pp. 75–92.
    32. 32)
      • 27. Damgård, I., Keller, M., Larraia, E., et al: ‘Practical covertly secure MPC for dishonest majority – or: breaking the SPDZ limits’. ESORICS, 2013 (LNCS, 8134), pp. 1–18.
    33. 33)
      • 11. Gentry, C., Halevi, S., Smart, N.P.: ‘Better bootstrapping in fully homomorphic encryption’. PKC, 2012 (LNCS, 7293), pp. 1–16.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2015.0505
Loading

Related content

content/journals/10.1049/iet-ifs.2015.0505
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address