Efficient hierarchical identity based encryption scheme in the standard model over lattices

Abstract

Using lattice basis delegation in a fixed dimension, we propose an efficient lattice-based hierarchical identity based encryption (HIBE) scheme in the standard model whose public key size is only (dm²+ mn) log q bits and whose message-ciphertext expansion factor is only log q, where d is the maximum hierarchical depth and (n,m, q) are public parameters. In our construction, a novel public key assignment rule is used to averagely assign one random and public matrix to two identity bits, which implies that d random public matrices are enough to build the proposed HIBE scheme in the standard model, compared with the case in which 2d such public matrices are needed in the scheme proposed at Crypto 2010 whose public key size is (2dm²+ mn+m) log q. To reduce the message-ciphertext expansion factor of the proposed scheme to log q, the encryption algorithm of this scheme is built based on Gentry’s encryption scheme, by which m² bits of plaintext are encrypted into m² log q bits of ciphertext by a one time encryption operation. Hence, the presented scheme has some advantages with respect to not only the public key size but also the message-ciphertext expansion factor. Based on the hardness of the learning with errors problem, we demonstrate that the scheme is secure under selective identity and chosen plaintext attacks.

Keywords

Hierarchical identity based encryption scheme / Lattice-based cryptography / Standard model / Learning with errors problem / Gaussian

References

[1] Agrawal, S., Boneh, D., Boyen, X., 2010a. Efficient lattice (H)IBE in the standard model. Proc. 29th Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, p.553–572. http://dx.doi.org/10.1007/978-3-642-13190-5_28

[2] Agrawal, S., Boneh, D., Boyen, X., 2010b. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. Proc. 30th Annual Cryptology Conf., p.98–115. http://dx.doi.org/10.1007/978-3-642-14623-7_6

[3] Agrawal, S., Boyen, X., Vaikuntanathan, V., , 2012. Functional encryption for threshold functions (or fuzzy IBE) from lattices. Proc. 15th Int. Conf. on Practice and Theory in Public Key Cryptography, p.280–297. http://dx.doi.org/10.1007/978-3-642-30057-8_17

[4] Alwen, J., Peikert, C., 2009. Generating shorter bases for hard random lattices. Proc. 26th Int. Symp. on Theoretical Aspects of Computer Science, p.75–86. http://dx.doi.org/10.4230/LIPIcs.STACS.2009.1832

[5] Boneh, D., Franklin, M., 2001. Identity-based encryption from the Weil pairing. Proc. 21st Annual Int. Cryptology Conf., p.213–229. http://dx.doi.org/10.1007/3-540-44647-8_13

[6] Boneh, D., Boyen, X., Goh, E.J., 2005. Hierarchical identity based encryption with constant size ciphertext. Proc. 24th Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, p.440–456. http://dx.doi.org/10.1007/11426639_26

[7] Boyen, X., Waters, B., 2006. Anonymous hierarchical identity-based encryption (without random oracles). Proc. 26th Annual Int. Cryptology Conf., p.290–307. http://dx.doi.org/10.1007/11818175_17

[8] Canetti, R., Halevi, S., Katz, J., 2003. A forward-secure public-key encryption scheme. Proc. Int. Conf. on the Theory and Applications of Cryptographic Techniques, p.255–271. http://dx.doi.org/10.1007/3-540-39200-9_16

[9] Cash, D., Hofheinz, D., Kiltz, E., , 2010. Bonsai trees, or how to delegate a lattice basis. Proc. 29th Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, p.523–552. http://dx.doi.org/10.1007/978-3-642-13190-5_27

[10] Cheng, Y., Wang, Z.Y., Ma, J., , 2013. Efficient revocation in ciphertext-policy attribute-based encryption based cryptographic cloud storage. J. Zhejiang Univ.- Sci. C (Comput. & Electron.), 14(2):85–97. http://dx.doi.org/10.1631/jzus.C1200240

[11] Gentry, C., Halevi, S., 2009. Hierarchical identity based encryption with polynomially many levels. Proc. 6th Theory of Cryptography Conf., p.437–456. http://dx.doi.org/10.1007/978-3-642-00457-5_26

[12] Gentry, C., Silverberg, A., 2002. Hierarchical ID-based cryptography. Proc. 8th Int. Conf. on the Theory and Application of Cryptology and Information Security, p.548–566. http://dx.doi.org/10.1007/3-540-36178-2_34

[13] Gentry, C., Peikert, C., Vaikuntanathan, V., 2008. Trapdoors for hard lattices and new cryptographic constructions. Proc. 40th Annual ACM Symp. on Theory of Computing, p.197–206. http://dx.doi.org/10.1145/1374376.1374407

[14] Gentry, C., Halevi, S., Vaikuntanathan, V., 2010. A simple BGN-type cryptosystem from LWE. Proc. 29th Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, p.506–522. http://dx.doi.org/10.1007/978-3-642-13190-5_26

[15] Horwitz, J., Lynn, B., 2002. Toward hierarchical identitybased encryption. Proc. Int. Conf. on the Theory and Applications of Cryptographic Techniques, p.466–481. http://dx.doi.org/10.1007/3-540-46035-7_31

[16] Hu, Y.P., Lei, H., Wang, F.H., , 2014. Gaussian sampling of lattices for cryptographic applications. Sci. China Inform. Sci., 57(7):072112.1–072112.8. http://dx.doi.org/10.1007/s11432-013-4843-4

[17] Micciancio, D., Regev, O., 2004. Worst-case to averagecase reductions based on Gaussian measures. Proc. 45th Annual IEEE Symp. on Foundations of Computer Science, p.372–381. http://dx.doi.org/10.1109/FOCS.2004.72

[18] Regev, O., 2005. On lattices, learning with errors, random linear codes, and cryptography. Proc. 37th Annual ACM Symp. on Theory of Computing, p.84–93. http://dx.doi.org/10.1145/1060590.1060603

[19] Singh, K., Pandurangan, C., Banerjee, A.K., 2012. Adaptively secure efficient lattice (H)IBE in standard model with short public parameters. Proc. 2nd Int. Conf. on Security, Privacy, and Applied Cryptography Engineering, p.153–172. http://dx.doi.org/10.1007/978-3-642-34416-9_11

[20] Singh, K., Pandu Rangan, C., Banerjee, A.K., 2014. Efficient lattice HIBE in the standard model with shorter public parameters. Proc. 2nd IFIP TC5/8 Int. Conf. on Information and Communication Technology, p.542–553. http://dx.doi.org/10.1007/978-3-642-55032-4_56

[21] Wang, F.H., Hu, Y.P., Wang, B.C., 2013. Lattice-based linearly homomorphic signature scheme over binary field. Sci. China Inform. Sci., 56(11):112108.1–112108.9. http://dx.doi.org/10.1007/s11432-012-4681-9

[22] Wang, F.H., Liu, Z.H., Wang, C.X., 2016. Full secure identity-based encryption scheme with short public key size over lattices in the standard model. Int. J. Comput. Math., 93(6):854–863. http://dx.doi.org/10.1080/00207160.2015.1029464

[23] Waters, B., 2009. Dual system encryption: realizing fully secure IBE and HIBE under simple assumptions. Proc. 29th Annual Int. Cryptology Conf., p.619–636. http://dx.doi.org/10.1007/978-3-642-03356-8_36

RIGHTS & PERMISSIONS

2016 Zhejiang University and Springer-Verlag Berlin Heidelberg