Abstract
Hierarchical identity-based fully homomorphic encryption (HIBFHE) scheme is a powerful scheme, as it aggregates the advantages of both fully homomorphic encryption and hierarchical identity-based encryption systems. In recent years, the construction of HIBFHE schemes were mainly based on lattices due to their conjectured resistance against quantum cryptanalysis, however, which makes these cryptosystems further unpractical. The first hierarchical identity-based fully homomorphic encryption scheme was presented by Gentry, Sahai and Waters (CRYPTO 2013). Their scheme however works with a not well performed trapdoor and delegation algorithm; that is, the trapdoor is conceptually and algorithmically complex, and the delegation algorithm’s performance is sensitive with the lattice dimension. In this work, we substantially improve their work by using a novel trapdoor function and its relevant algorithms. Specifically, we first use that construct an efficient algorithm for sampling-invertible matrix, based on this we construct a novel delegation algorithm which can keep the lattice dimension unchanged upon delegation. Building on this result, we first construct a more efficient hierarchical identity-based encryption scheme, and then transform it to HIBFHE scheme by using eigenvector method. Under the hardness of Learning with Errors problem, the resulting scheme can be proven secure in the standard model. To the best of our knowledge, this is the first HIBFHE scheme in fixed dimension.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of 41th ACM Symposium on Theory of Computing, STOC 2009, pp. 169–178. ACM, Bethesda (2009)
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
Brakerski, Z., Vaikuntanathan, V.: Fully homomorphic encryption from ring-LWE and security for key dependent messages. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 505–524. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_29
Gentry, C., Halevi, S., Smart, N.P.: Fully homomorphic encryption with polylog overhead. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 465–482. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_28
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
Nuida, K., Kurosawa, K.: Fully homomorphic encryption over integers for non-binary message spaces. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 537–555. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_21
Canetti, R., Halevi, S., Katz, J.: A forward-secure public-key encryption scheme. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 255–271. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_16
Dodis, Y., Fazio, N.: Public key broadcast encryption for stateless receivers. In: Feigenbaum, J. (ed.) DRM 2002. LNCS, vol. 2696, pp. 61–80. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-44993-5_5
Yao, D., Fazio, N., Dodis, Y., Lysyanskaya, A.: ID-based encryption for complex hierarchies with applications to forward security and broadcast encryption. In: ACM Conference on Computer and Communications Security, pp. 354–363. ACM, Washington (2004)
Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, Juan A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 75–92. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_5
Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai trees, or how to delegate a lattice basis. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 523–552. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_27
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC 2005 Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pp. 84–93. ACM, Baltimore (2005)
Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of 41th ACM Symposium on Theory of Computing, pp 197–206. ACM, Victoria (2008)
Agrawal, S., Boneh, D., Boyen, X.: Efficient lattice (H)IBE in the standard model. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 553–572. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_28
Agrawal, S., Boneh, D., Boyen, X.: Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 98–115. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_6
Ajtai, M.: Generating hard instances of the short basis problem. In: Wiedermann, J., van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 1–9. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48523-6_1
Alwen, J., Peikert, C.: Generating shorter bases for hard random lattices. Theor. Comput. Syst. 48(3), 535–553 (2009)
Micciancio, D., Peikert, C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 700–718. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_41
Micciancio, D., Goldwasser, S.: Complexity of lattice problems: a cryptographic perspective. Siam J. Comput. 671(6495), 220 (2002)
Ajtai, M.: Generating hard instances of lattice problems. In: STOC 1996 Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 99–108. ACM, Philadelphia (1996)
Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267–302 (2007)
Peikert, C.: An efficient and parallel Gaussian sampler for lattices. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 80–97. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_5
Yamada, S.: Adaptively secure identity-based encryption from lattices with asymptotically shorter public parameters. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 32–62. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_2
Acknowledgements
This work was supported by the “13th Five-Year” National Crypto Development Foundation (No.MMJJ20170122), the Project of Science and Technology Department of Henan Province (No.142300410147), the Project of Education Department of Henan Province (No.12A520021, No.16A520013), the Doctoral Fund of Henan Polytechnic University (No.B2014-044), the Natural Science Foundation of Henan Polytechnic University (No.T2018-1).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Hu, M., Ye, Q., Gao, W., Tang, Y. (2018). A Novel Hierarchical Identity-Based Fully Homomorphic Encryption Scheme from Lattices. In: Sun, X., Pan, Z., Bertino, E. (eds) Cloud Computing and Security. ICCCS 2018. Lecture Notes in Computer Science(), vol 11065. Springer, Cham. https://doi.org/10.1007/978-3-030-00012-7_39
Download citation
DOI: https://doi.org/10.1007/978-3-030-00012-7_39
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-00011-0
Online ISBN: 978-3-030-00012-7
eBook Packages: Computer ScienceComputer Science (R0)