http://iet.metastore.ingenta.com
1887

Bootstrapping BGV ciphertexts with a wider choice of p and q

Bootstrapping BGV ciphertexts with a wider choice of p and q

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Information Security — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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).

References

    1. 1)
      • 1. Gentry, C.: ‘A fully homomorphic encryption scheme’ (Stanford University, 2009), crypto.stanford.edu/craig.
    2. 2)
      • 2. Gentry, C.: ‘Fully homomorphic encryption using ideal lattices’. STOC, 2009, pp. 169178.
    3. 3)
      • 3. Alperin-Sheriff, J., Peikert, C.: ‘Practical bootstrapping in quasilinear time’. CRYPTO, 2013 (LNCS, 8042), pp. 120.
    4. 4)
      • 4. Alperin-Sheriff, J., Peikert, C.: ‘Faster bootstrapping with polynomial error’. CRYPTO, 2014 (LNCS, 8616), pp. 297314.
    5. 5)
      • 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. 617640.
    6. 6)
      • 6. Brakerski, Z.: ‘Fully homomorphic encryption without modulus switching from classical GapSVP’. CRYPTO, 2012 (LNCS, 7417), pp. 868886.
    7. 7)
      • 7. Brakerski, Z., Vaikuntanathan, V.: ‘Efficient fully homomorphic encryption from (standard) LWE’. FOCS, 2011, pp. 97106.
    8. 8)
      • 8. Brakerski, Z., Vaikuntanathan, V.: ‘Fully homomorphic encryption from ring-LWE and security for key dependent messages’. CRYPTO, 2011 (LNCS, 6841), pp. 505524.
    9. 9)
      • 9. Brakerski, Z., Vaikuntanathan, V.: ‘Lattice-based FHE as secure as PKE’. ITCS, 2014, pp. 112.
    10. 10)
      • 10. Cheon, J.H., Coron, J.S., Kim, J., et al: ‘Batch fully homomorphic encryption over the integers’. EUROCRYPT, 2013 (LNCS, 7881), pp. 315335.
    11. 11)
      • 11. Gentry, C., Halevi, S., Smart, N.P.: ‘Better bootstrapping in fully homomorphic encryption’. PKC, 2012 (LNCS, 7293), pp. 116.
    12. 12)
      • 12. Gentry, C., Halevi, S., Smart, N.P.: ‘Fully homomorphic encryption with polylog overhead’. EUROCRYPT, 2012 (LNCS, 7237), pp. 465482.
    13. 13)
      • 13. van Dijk, M., Gentry, C., Halevi, S., et al: ‘Fully homomorphic encryption over the integers’. EUROCRYPT, 2010 (LNCS, 6110), pp. 2443.
    14. 14)
      • 14. Brakerski, Z., Gentry, C., Vaikuntanathan, V.: ‘In (leveled) fully homomorphic encryption without bootstrapping’. ITCS, 2012, pp. 309325.
    15. 15)
      • 15. Lyubashevsky, V., Peikert, C., Regev, O.: ‘On ideal lattices and learning with errors over rings’. EUROCRYPT, 2010 (LNCS, 6110), pp. 123.
    16. 16)
      • 16. Gentry, C., Halevi, S.: ‘Implementing Gentry's fully-homomorphic encryption scheme’. EUROCRYPT, 2011 (LNCS, 6632), pp. 129148.
    17. 17)
      • 17. Smart, N.P., Vercauteren, F.: ‘Fully homomorphic encryption with relatively small key and ciphertext sizes’. PKC, 2010 (LNCS, 6056), pp. 420443.
    18. 18)
      • 18. Smart, N.P., Vercauteren, F.: ‘Fully homomorphic SIMD operations’, Des. Codes Cryptogr., 2014, 71, pp. 5781.
    19. 19)
      • 19. Gentry, C., Halevi, S., Peikert, C., et al: ‘Field switching in BGV-style homomorphic encryption’, J. Comput. Secur., 2013, 21, (5), pp. 663684.
    20. 20)
      • 20. Rohloff, K., Cousins, D.B.: ‘A scalable implementation of fully homomorphic encryption built on NTRU’. Financial Cryptography, 2014 (LNCS, 8438), pp. 221234.
    21. 21)
      • 21. Gentry, C., Sahai, A., Waters, B.: ‘Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based’. CRYPTO, 2013 (LNCS, 8042), pp. 7592.
    22. 22)
      • 22. Gentry, C., Halevi, S., Smart, N.P.: ‘Homomorphic evaluation of the AES circuit’. CRYPTO, 2012 (LNCS, 7417), pp. 850867.
    23. 23)
      • 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. 673698.
    24. 24)
      • 24. Damgård, I., Pastro, V., Smart, N.P., et al: ‘Multiparty computation from somewhat homomorphic encryption’. CRYPTO, 2012 (LNCS, 7417), pp. 643662.
    25. 25)
      • 25. Lyubashevsky, V., Peikert, C., Regev, O.: ‘A toolkit for ring-LWE cryptography’. EUROCRYPT, 2013 (LNCS, 7881), pp. 3554.
    26. 26)
      • 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. 641670.
    27. 27)
      • 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. 118.
    28. 28)
      • 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. 221240.
    29. 29)
      • 29. van de Pol, J., Smart, N.P.: ‘Estimating key sizes for high dimensional lattice-based systems’. IMA Int. Conf., 2013 (LNCS, 8308), pp. 290303.
    30. 30)
      • 30. Lepoint, T., Naehrig, M.: ‘A comparison of the homomorphic encryption schemes FV and YASHE’. AFRICACRYPT, 2014 (LNCS, 8469), pp. 318335.
    31. 31)
      • 31. Lindner, R., Peikert, C.: ‘Better key sizes (and attacks) for LWE-based encryption’. CT-RSA, 2011 (LNCS, 6558), pp. 319339.
    32. 32)
      • 32. Chen, Y., Nguyen, P.Q.: ‘BKZ 2.0: better lattice security estimates’. ASIACRYPT, 2011 (LNCS, 7073), pp. 120.
    33. 33)
      • 33. Micciancio, D., Regev, O.: ‘Lattice-based cryptography’. Post-Quantum Cryptography, 2009, pp. 147191.
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
This is a required field
Please enter a valid email address