Part of the book series:Lecture Notes in Computer Science ((LNSC,volume 10005))
Included in the following conference series:
937Accesses
Abstract
A major open problem is to protect levelled homomorphic encryption from adaptive attacks that allow an adversary to learn the private key. The only positive results in this area are by Loftus, May, Smart and Vercauteren. They use a notion of “valid ciphertexts” and obtain an IND-CCA1 scheme under a strong knowledge assumption, but they also show their scheme is not secure under a natural adaptive attack based on a “ciphertext validity oracle”.
The main contribution of this paper is to explore a new approach to achieve security against adaptive attacks, which does not rely on a notion of “valid ciphertexts”. Instead, our idea is to generate a “one-time” private key every time the decryption algorithm is run, so that even if an attacker can learn some bits of the one-time private key from each decryption query, this does not allow them to compute a valid private key. We demonstrate how this idea can be implemented with the Gentry-Sahai-Waters levelled homomorphic encryption scheme, and we give an informal explanation of why the known attacks no longer break the system.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bleichenbacher, D.: Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 1–12. Springer, Heidelberg (1998). doi:10.1007/BFb0055716
Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) lwe. In: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 97–106. IEEE Computer Society (2011)
Chenal, M., Tang, Q.: On key recovery attacks against existing somewhat homomorphic encryption schemes. In: Aranha, D.F., Menezes, A. (eds.) LATINCRYPT 2014. LNCS, vol. 8895, pp. 239–258. Springer, Heidelberg (2015). doi:10.1007/978-3-319-16295-9_13
Chenal, M., Tang, Q.: Key recovery attacks against NTRU-based somewhat homomorphic encryption schemes. In: Lopez, J., Mitchell, C.J. (eds.) ISC 2015. LNCS, vol. 9290, pp. 397–418. Springer, Heidelberg (2015). doi:10.1007/978-3-319-23318-5_22
Dahab, R., Galbraith, S., Morais, E.: Adaptive key recovery attacks on NTRU-based somewhat homomorphic encryption schemes. In: Lehmann, A., Wolf, S. (eds.) ICITS 2015. LNCS, vol. 9063, pp. 283–296. Springer, Heidelberg (2015). doi:10.1007/978-3-319-17470-9_17
Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pp. 169–169. ACM Press (2009)
Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 197–206. ACM (2008)
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). doi:10.1007/978-3-642-40041-4_5
Impagliazzo, R., Levin, L.A., Luby, M.: Pseudo-random generation from one-way functions. In: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, pp. 12–24. ACM (1989)
Loftus, J., May, A., Smart, N.P., Vercauteren, F.: On CCA-secure somewhat homomorphic encryption. In: Miri, A., Vaudenay, S. (eds.) SAC 2011. LNCS, vol. 7118, pp. 55–72. Springer, Heidelberg (2012). doi:10.1007/978-3-642-28496-0_4
Micciancio, D., Regev, O.: Lattice-based cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.) Post-Quantum Cryptography, pp. 147–191. Springer, Heidelberg (2009)
Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pp. 333–342. ACM (2009)
Peikert, C., et al.: Decade of Lattice Cryptography. World Scientific (2016)
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)
Smart, N.P., Vercauteren, F.: Fully homomorphic encryption with relatively small key and ciphertext sizes. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 420–443. Springer, Heidelberg (2010). doi:10.1007/978-3-642-13013-7_25
Zhang, Z., Plantard, T., Susilo, W.: On the CCA-1 security of somewhat homomorphic encryption over the integers. In: Ryan, M.D., Smyth, B., Wang, G. (eds.) ISPEC 2012. LNCS, vol. 7232, pp. 353–368. Springer, Heidelberg (2012). doi:10.1007/978-3-642-29101-2_24
Acknowledgments
The authors would like to thank the anonymous reviewers for their helpful advice and comments. This work was supported by the National Natural Science Foundation of China (No.61472097), Specialized Research Fund for the Doctoral Program of Higher Education (No.20132304110017) and International Exchange Program of Harbin Engineering University for Innovation-oriented Talents Cultivation.
Author information
Authors and Affiliations
College of Computer Science and Technology, Harbin Engineering University, Harbin, 150001, China
Zengpeng Li & Chunguang Ma
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, 100093, China
Zengpeng Li & Chunguang Ma
Department of Mathematics, The University of Auckland, Auckland, 1142, New Zealand
Steven D. Galbraith
- Zengpeng Li
You can also search for this author inPubMed Google Scholar
- Steven D. Galbraith
You can also search for this author inPubMed Google Scholar
- Chunguang Ma
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toChunguang Ma.
Editor information
Editors and Affiliations
University of Surrey , Guildford, United Kingdom
Liqun Chen
Nanjing University of Finance and Economics, Nanjing, China
Jinguang Han
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Li, Z., Galbraith, S.D., Ma, C. (2016). Preventing Adaptive Key Recovery Attacks on the GSW Levelled Homomorphic Encryption Scheme. In: Chen, L., Han, J. (eds) Provable Security. ProvSec 2016. Lecture Notes in Computer Science(), vol 10005. Springer, Cham. https://doi.org/10.1007/978-3-319-47422-9_22
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-319-47421-2
Online ISBN:978-3-319-47422-9
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative