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

access icon free Sparse subset sum problem from Gentry–Halevi's fully homomorphic encryption

© The Institution of Engineering and Technology
Received 25/06/2015, Accepted 09/02/2016, Published 15/02/2016

In Gentry's fully homomorphic encryption scheme, a sparse subset sum problem (SSSP) is used and a big set is included in the public key. In the implementation of a variant, to reduce the size of the public key, Gentry and Halevi used a specific form of a SSSP constructed from geometric progressions. In this study, the authors solve Gentry and Halevi's sparse subset sum challenges for the first time. Owing to the aggressive choice of parameters, the process is fairly easy and can be done by simply modifying their lattice-based attack. Their experiment shows that even a large challenge can be solved within two days. As a second contribution, considering other attacks such as a hybrid attack combining a meet in the middle attack with a lattice-based attack, they provide a new condition for hard instances of the SSSP from geometric progressions.

Inspec keywords: lattice theory; set theory; public key cryptography; geometry

Other keywords: lattice-based attack; sparse subset sum problem; geometric progressions; public key; SSSP; middle attack; Gentry-Halevi fully homomorphic encryption scheme

Subjects: Cryptography theory; Combinatorial mathematics; Combinatorial mathematics; Cryptography; Data security

References

    1. 1)
      • 10. Brakerski, Z., Vaikuntanathan, V.: ‘Efficient fully homomorphic encryption from (standard) LWE’, IEEE 52nd Annual Symp. on Foundations of Computer Science – FOCS 2011, 2011, pp. 97–106.
    2. 2)
      • 16. Lenstra, A., Lenstra, H.W., Lov′asz, L.: ‘Factoring polynomials with rational coefficients’, Math. Ann., 1982, 261, (4), pp. 515–534. Available at URL http://www.springerlink.com/index/lh1m24436431g068.pdf.
    3. 3)
      • 18. Cadé, X.P.D., Stehlé, D.: ‘FPLLL library’, version 3.1.1. Available at http://www.perso.ens-lyon.fr/xavier.pujol/fplll/.
    4. 4)
      • 14. Gentry, C., Sahai, A., Waters, B.: ‘Homomorphic encryption from learning with errors: conceptually-simpler, Asymptotically-Faster, Attribute-Based’. Advances in Cryptology – CRYPTO’2013, (LNCS, 8042), pp. 75–92.
    5. 5)
      • 20. Lee, M., Hahn, S.: ‘Cryptanalysis of the GGH cryptosystem’, Math. Comput. Sci., 2010, 3, pp. 201–208, doi: 10.1007/s11786-009-0018-5. Available at URL http://www.dx.doi.org/10.1007/s11786-009-0018-5.
    6. 6)
      • 17. Schnorr, C.P., Euchner, M.: ‘Lattice basis reduction: improved practical algorithms and solving subset sum problems’, Math. Program., 1994, 66, pp. 181–199, doi: 10.1007/BF01581144. Available at URL http://www.dx.doi.org/10.1007/BF01581144.
    7. 7)
      • 19. May, A., Silverman, J.: ‘Dimension reduction methods for convolution modular lattices’ Cryptography and Lattices, 2001 (LNCS, 2146), pp. 110–125, doi: 10.1007/3-540-44670-2 10. Available at URL http://www.dx.doi.org/10.1007/3-540-44670-2_10.
    8. 8)
      • 22. Becker, A., Coron, J.-S., Joux, A.: ‘Improved generic algorithms for hard knapsacks’ Advances in Cryptology – EUROCRYPT 2011, 2011 (LNCS, 6632), pp. 364–385. Available at URL http://www.dx.doi.org/10.1007/978-3-642-20465-4_21.
    9. 9)
      • 8. Gentry, C., Halevi, S.: ‘Implementing Gentry's fully-homomorphic encryption scheme, cryptology ePrint archive’, Report, 2010/520, 2010. Available at http://www.eprint.iacr.org/, full version of [7].
    10. 10)
      • 11. Coron, J.-S., Mandal, A., Naccache, D., et al: ‘Fully homomorphic encryption over the integers with shorter public keys’. Advances in Cryptology – CRYPTO 2011 – 31st Annual Cryptology Conf., Santa Barbara, CA, USA, 14–18 August 2011 (LNCS, 6841) pp. 487–504.
    11. 11)
      • 13. Cheon, J.H., Coron, J.-S., Kim, J., et al: ‘Batch fully homomorphic encryption over the integers’ Advances in Cryptology – EUROCRYPT 2013’, 2013 (LNCS, 7881), pp. 315–335.
    12. 12)
      • 3. Gentry, C.: ‘Fully homomorphic encryption using ideal lattices’. STOC'09 Proc. of the 41st Annual ACM Symp. on Theory of Computing, 2009, pp. 169–178.
    13. 13)
      • 6. Smart, N., Vercauteren, F.: ‘Fully homomorphic SIMD operations, cryptology ePrint archive’, Report, 2011/133, (2011. Available at http://www.eprint.iacr.org/.
    14. 14)
      • 5. Smart, N.P., Vercauteren, F.: ‘Fully homomorphic encryption with relatively small key and ciphertext sizes’. Public Key Cryptography – PKC 2010 (LNCS, 6056), pp. 420–443.
    15. 15)
      • 7. Gentry, C., Halevi, S.: ‘Implementing Gentry's fully-homomorphic encryption scheme’. Advances in Cryptology – EUROCRYPT 2011, 2011 (LNCS, 6632) pp. 129–148.
    16. 16)
      • 21. Howgrave-Graham, N., Joux, A.: ‘New generic algorithms for hard knapsacks’ Advances in Cryptology – EUROCRYPT 2010, 2010 (LNCS, 6110), pp. 235–256. Available at URL http://www.dx.doi.org/10.1007/978-3-642-13190-5_12.
    17. 17)
      • 15. Coron, J.-S., Lepoint, T., Tibouchi, M.: ‘Scale-invariant fully homomorphic encryption over the integers’. Public Key Cryptography, Lecture Notes in Computer Science, 2014, pp. 311–328.
    18. 18)
      • 4. Dijk, M.V., Gentry, C., Halevi, S., et al: ‘Fully homomorphic encryption over the integers’. Advances in Cryptology – EUROCRYPT 2010, 2010 (LNCS, 6110), pp. 24–43Available at URL http://www.dx.doi.org/10.1007/978-3-642-13190-5_2.
    19. 19)
      • 1. Merkle, R., Hellman, M.: ‘Hiding information and signatures in trapdoor knapsacks’, IEEE Trans. Inf. Theory, 1978, 24, (5), pp. 525–530, doi: 10.1109/TIT.1978.1055927.
    20. 20)
      • 12. Coron, J.-S., Naccache, D., Tibouchi, M.: ‘Public key compression and modulus switching for fully homomorphic encryption over the Integers’. EUROCRYPT (LNCS, 7237), 2012, pp. 446–464.
    21. 21)
      • 9. Brakerski, Z., Vaikuntanathan, V.: ‘Fully homomorphic encryption from ring-LWE and security for key dependent messages’. Advances in Cryptology – CRYPTO 2011, 2011 (LNCS, 6841), pp. 505–524.
    22. 22)
      • 2. Matsumoto, T., Kato, K., Imai, H.: ‘Speeding up secret computations with insecure auxiliary devices’. Proc. of the Eighth Annual Int. Cryptology Conf. on Advances in Cryptology, CRYPTO ‘88, London, UK, 1990, pp. 497–506. Available at URL http://www.dl.acm.org/citation.cfm?id=646753.704908.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2015.0263
Loading

Related content

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