Improved (hierarchical) inner-product encryption from lattices. (English) Zbl 1314.94097
Kurosawa, Kaoru (ed.) et al., Public-key cryptography – PKC 2013. 16th international conference on practice and theory in public-key cryptography, Nara, Japan, February 26–March 1, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-36361-0/pbk). Lecture Notes in Computer Science 7778, 235-252 (2013).
Summary: Inner-product encryption (IPE) provides fine-grained access control and has attractive applications. Agrawal, Freeman, and Vaikuntanathan [S. Agrawal et al., Asiacrypt 2011, Lect. Notes Comput. Sci. 7073, 21–40 (2011; Zbl 1227.94023)] proposed the first IPE scheme from lattices by twisting the identity-based encryption (IBE) scheme by Agrawal, Boneh, and Boyen [S. Agrawal et al., Eurocrypt 2010, Lect. Notes Comput. Sci. 6110, 553–572 (2010; Zbl 1227.94022)]. Their IPE scheme supports inner-product predicates over \(R ^{\mu}\), where the ring is \(R = \mathbb Z_q\). Several applications require the ring \(R\) to be exponentially large and, thus, they set \(q = 2^{O(n)}\) to implement such applications. This choice results in the AFV IPE scheme with public parameters of size \(O(\mu n^2 \log^3{q}) = O(\mu n^5)\) and ciphertexts of size \(O(\mu n \log^3{q}) = O(\mu n^4)\), where \(n\) is the security parameter. Hence, this makes the scheme impractical, as they noted.
We address this efficiency issue by “untwisting” their twist and providing another twist. Our scheme supports inner-product predicates over \(R^{\mu}\) where \(R = \mathrm{GF}(q^n)\) instead of \(\mathbb Z_q\). Our scheme has public parameters of size \(O(\mu n^2 \log^2{q})\) and ciphertexts of size \(O(\mu n \log^2{q})\). Since the cardinality of \(\mathrm{GF}(q^n)\) is inherently exponential in \(n\), we have no need to set \(q\) as the exponential size for applications.
As side contributions, we extend our IPE scheme to a hierarchical IPE (HIPE) scheme and propose a fuzzy IBE scheme from IPE. Our HIPE scheme is more efficient than that developed by Abdalla, De Caro, and Mochetti [M. Abdalla et al., Latincrypt 2012, Lect. Notes Comput. Sci. 7533, 121–138 (2012; Zbl 1303.94063)]. Our fuzzy IBE is secure under a much weaker assumption than that employed by S. Agrawal et al. [PKC 2012, Lect. Notes Comput. Sci. 7293, 316–333 (2012; Zbl 1294.94028)], who constructed the first lattice-based fuzzy IBE scheme.
For the entire collection see [Zbl 1258.94004].
We address this efficiency issue by “untwisting” their twist and providing another twist. Our scheme supports inner-product predicates over \(R^{\mu}\) where \(R = \mathrm{GF}(q^n)\) instead of \(\mathbb Z_q\). Our scheme has public parameters of size \(O(\mu n^2 \log^2{q})\) and ciphertexts of size \(O(\mu n \log^2{q})\). Since the cardinality of \(\mathrm{GF}(q^n)\) is inherently exponential in \(n\), we have no need to set \(q\) as the exponential size for applications.
As side contributions, we extend our IPE scheme to a hierarchical IPE (HIPE) scheme and propose a fuzzy IBE scheme from IPE. Our HIPE scheme is more efficient than that developed by Abdalla, De Caro, and Mochetti [M. Abdalla et al., Latincrypt 2012, Lect. Notes Comput. Sci. 7533, 121–138 (2012; Zbl 1303.94063)]. Our fuzzy IBE is secure under a much weaker assumption than that employed by S. Agrawal et al. [PKC 2012, Lect. Notes Comput. Sci. 7293, 316–333 (2012; Zbl 1294.94028)], who constructed the first lattice-based fuzzy IBE scheme.
For the entire collection see [Zbl 1258.94004].
MSC:
| 94A60 | Cryptography |
Keywords:
predicate encryption; (hierarchical) inner-product encryption; lattices; learning with errors; full-rank difference encoding; pseudo-commutativityReferences:
| [1] | Abdalla, M.; Birkett, J.; Catalano, D.; Dent, A. W.; Malone-Lee, J.; Neven, G.; Schuldt, J. C.N.; Smart, N. P., Wildcarded identity-based encryption, Journal of Cryptology, 24, 1, 42-82 (2011) · Zbl 1208.94037 · doi:10.1007/s00145-010-9060-3 |
| [2] | Abdalla, M.; Catalano, D.; Dent, A. W.; Malone-Lee, J.; Neven, G.; Smart, N. P.; Bugliesi, M.; Preneel, B.; Sassone, V.; Wegener, I., Identity-Based Encryption Gone Wild, Automata, Languages and Programming, 300-311 (2006), Heidelberg: Springer, Heidelberg · Zbl 1133.94340 · doi:10.1007/11787006_26 |
| [3] | Abdalla, M.; De Caro, A.; Mochetti, K.; Hevia, A.; Neven, G., Lattice-Based Hierarchical Inner Product Encryption, Progress in Cryptology - LATINCRYPT 2012, 121-138 (2012), Heidelberg: Springer, Heidelberg · Zbl 1303.94063 · doi:10.1007/978-3-642-33481-8_7 |
| [4] | Agrawal, S., Boneh, D., Boyen, X.: Efficient lattice (H)IBE in the standard model. In: Gilbert (ed.) [27], pp. 553-572 · Zbl 1227.94022 |
| [5] | Agrawal, S., Boyen, X., Vaikuntanathan, V., Voulgaris, P., Wee, H.: Functional encryption for threshold functions (or, fuzzy IBE) from lattices. In: Fischlin, et al. (eds.) [25], pp. 280-297 · Zbl 1290.94039 |
| [6] | Agrawal, S.; Freeman, D. M.; Vaikuntanathan, V.; Lee, D. H.; Wang, X., Functional Encryption for Inner Product Predicates from Learning with Errors, Advances in Cryptology - ASIACRYPT 2011, 21-40 (2011), Heidelberg: Springer, Heidelberg · Zbl 1227.94023 · doi:10.1007/978-3-642-25385-0_2 |
| [7] | Ajtai, M.; Wiedermann, J.; Van Emde Boas, P.; Nielsen, M., Generating Hard Instances of the Short Basis Problem, Automata, Languages and Programming, 1-9 (1999), Heidelberg: Springer, Heidelberg · Zbl 0987.94021 · doi:10.1007/3-540-48523-6_1 |
| [8] | Alperin-Sheriff, J., Peikert, C.: Circular and KDM security for identity-based encryption. In: Fischlin, et al. (eds.) [25], pp. 334-352 · Zbl 1294.94030 |
| [9] | Alwen, J.; Peikert, C.; Albers, S.; Marion, J. Y., Generating shorter bases for hard random lattices, STACS 2009, 75-86 (2009), Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany · Zbl 1236.94049 |
| [10] | Attrapadung, N.; Libert, B.; Nguyen, P. Q.; Pointcheval, D., Functional Encryption for Inner Product: Achieving Constant-Size Ciphertexts with Adaptive Security or Support for Negation, Public Key Cryptography - PKC 2010, 384-402 (2010), Heidelberg: Springer, Heidelberg · Zbl 1281.94013 · doi:10.1007/978-3-642-13013-7_23 |
| [11] | Birkett, J.; Dent, A. W.; Neven, G.; Schuldt, J. C.N.; Pieprzyk, J.; Ghodosi, H.; Dawson, E., Efficient Chosen-Ciphertext Secure Identity-Based Encryption with Wildcards, Information Security and Privacy, 274-292 (2007), Heidelberg: Springer, Heidelberg · Zbl 1213.94084 · doi:10.1007/978-3-540-73458-1_21 |
| [12] | Boneh, D.; Boyen, X.; Cachin, C.; Camenisch, J. L., Efficient selective-ID secure identity-based encryption without random oracles, Advances in Cryptology - EUROCRYPT 2004, 223-238 (2004), Heidelberg: Springer, Heidelberg · Zbl 1122.94355 · doi:10.1007/978-3-540-24676-3_14 |
| [13] | Boneh, D.; Canetti, R.; Halevi, S.; Katz, J., Chosen-ciphertext security from identity-based encryption, SIAM Journal on Computing, 36, 5, 1301-1328 (2006) · Zbl 1138.94010 · doi:10.1137/S009753970544713X |
| [14] | Boneh, D.; Hamburg, M.; Pieprzyk, J., Generalized Identity Based and Broadcast Encryption Schemes, Advances in Cryptology - ASIACRYPT 2008, 455-470 (2008), Heidelberg: Springer, Heidelberg · Zbl 1206.94054 · doi:10.1007/978-3-540-89255-7_28 |
| [15] | Boneh, D.; Waters, B.; Vadhan, S. P., Conjunctive, Subset, and Range Queries on Encrypted Data, Theory of Cryptography, 535-554 (2007), Heidelberg: Springer, Heidelberg · Zbl 1156.94335 · doi:10.1007/978-3-540-70936-7_29 |
| [16] | Boyen, X.: Attribute-based encryption from lattices (2012) (to appear TCC 2013) · Zbl 1310.94131 |
| [17] | Brakerski, Z.; Safavi-Naini, R.; Canetti, R., Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP, CRYPTO 2012, 868-886 (2012), Heidelberg: Springer, Heidelberg · Zbl 1296.94091 · doi:10.1007/978-3-642-32009-5_50 |
| [18] | Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Goldwasser, S. (ed.) ITCS 2012, pp. 309-325. ACM (2012), see also http://eprint.iacr.org/2011/277 · Zbl 1347.68120 |
| [19] | Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: FOCS 2011, pp. 97-106. IEEE Computer Society (2011), see also http://eprint.iacr.org/2011/344 · Zbl 1292.94038 |
| [20] | Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai trees, or how to delegate a lattice basis. In: Gilbert (ed.) [27], pp. 523-552 · Zbl 1280.94043 |
| [21] | Chen, J., Lim, H.W., Ling, S., Wang, H.: The relation and transformation between hierarchical inner product encryption and spatial encryption. Designs, Codes and Cryptography, Online First (2012), see also http://eprint.iacr.org/2011/455 |
| [22] | Chen, J.; Lim, H. W.; Ling, S.; Wang, H.; Nguyen, K.; Susilo, W.; Mu, Y.; Seberry, J., Revocable Identity-Based Encryption from Lattices, Information Security and Privacy, 390-403 (2012), Heidelberg: Springer, Heidelberg · Zbl 1308.94064 · doi:10.1007/978-3-642-31448-3_29 |
| [23] | Cramer, R.; Damgård, I.; Halevi, S., On the Amortized Complexity of Zero-Knowledge Protocols, Advances in Cryptology - CRYPTO 2009, 177-191 (2009), Heidelberg: Springer, Heidelberg · Zbl 1252.94056 · doi:10.1007/978-3-642-03356-8_11 |
| [24] | Dwork, C. (ed.): Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20. ACM (2008) · Zbl 1255.90002 |
| [25] | Fischlin, M.; Buchmann, J.; Manulis, M., Public Key Cryptography - PKC 2012 (2012), Heidelberg: Springer, Heidelberg · Zbl 1241.94004 |
| [26] | Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Dwork (ed.) [24], pp. 197-206, see also http://eprint.iacr.org/2007/432 · Zbl 1231.68124 |
| [27] | Gilbert, H., Advances in Cryptology - EUROCRYPT 2010 (2010), Heidelberg: Springer, Heidelberg · Zbl 1188.94008 |
| [28] | Gordon, S. D.; Katz, J.; Vaikuntanathan, V.; Abe, M., A Group Signature Scheme from Lattice Assumptions, Advances in Cryptology - ASIACRYPT 2010, 395-412 (2010), Heidelberg: Springer, Heidelberg · Zbl 1253.94071 · doi:10.1007/978-3-642-17373-8_23 |
| [29] | Hamburg, M.: Spatial Encryption. Ph.D. thesis, Stanford University (2011), http://eprint.iacr.org/2011/389 |
| [30] | Katz, J.; Sahai, A.; Waters, B.; Smart, N. P., Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products, Advances in Cryptology - EUROCRYPT 2008, 146-162 (2008), Heidelberg: Springer, Heidelberg · Zbl 1149.94323 · doi:10.1007/978-3-540-78967-3_9 |
| [31] | Lewko, A., Okamoto, T., Sahai, A., Takashima, K., Waters, B.: Fully secure functional encryption: Attribute-based encryption and (hierarchical) inner product encryption. In: Gilbert (ed.) [27], pp. 62-91, the full version is available at http://eprint.iacr.org/2010/110 · Zbl 1279.94095 |
| [32] | Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert (ed.) [27], pp. 1-23 · Zbl 1279.94099 |
| [33] | Micciancio, D., Generalized compact knapsacks, cyclic lattices, and efficient one-way functions, Computational Complexity, 16, 365-411 (2007) · Zbl 1133.68024 |
| [34] | Micciancio, D., Peikert, C.: Private communication (December 12, 2012) |
| [35] | Micciancio, D., Peikert, C.: Trapdoors for lattices: Simpler, tighter, faster, smaller. In: Pointcheval, Johansson (eds.) [44], pp. 700-718, http://eprint.iacr.org/2011/501 · Zbl 1297.94090 |
| [36] | Okamoto, T.; Takashima, K.; Matsui, M., Hierarchical Predicate Encryption for Inner-Products, Advances in Cryptology - ASIACRYPT 2009, 214-231 (2009), Heidelberg: Springer, Heidelberg · Zbl 1267.94089 · doi:10.1007/978-3-642-10366-7_13 |
| [37] | Okamoto, T., Takashima, K.: Fully secure functional encryption with general relations from the decisional linear assumption. In: Rabin (ed.) [45], pp. 191-208, the full version is available at http://eprint.iacr.org/2010/563 · Zbl 1280.94086 |
| [38] | Okamoto, T.; Takashima, K.; Lin, D.; Tsudik, G.; Wang, X., Achieving Short Ciphertexts or Short Secret-Keys for Adaptively Secure General Inner-Product Encryption, Cryptology and Network Security, 138-159 (2011), Heidelberg: Springer, Heidelberg · Zbl 1307.94082 · doi:10.1007/978-3-642-25513-7_11 |
| [39] | Okamoto, T., Takashima, K.: Adaptively attribute-hiding (hierarchical) inner product encryption. In: Pointcheval, Johansson (eds.) [44], pp. 591-608, the full version is available at http://eprint.iacr.org/2010/543 · Zbl 1297.94096 |
| [40] | Park, J. H., Inner-product encryption under standard assumptions, Designs, Codes and Cryptography, 58, 3, 235-257 (2011) · Zbl 1215.68097 · doi:10.1007/s10623-010-9405-9 |
| [41] | Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: Mitzenmacher, M. (ed.) STOC 2009, pp. 333-342. ACM (2009) · Zbl 1304.94079 |
| [42] | Peikert, C.: An efficient and parallel Gaussian sampler for lattices. In: Rabin (ed.) [45], pp. 80-97 · Zbl 1280.94091 |
| [43] | Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: Dwork (ed.) [24], pp. 187-196 · Zbl 1228.94027 |
| [44] | Pointcheval, D.; Johansson, T., Advances in Cryptology - EUROCRYPT 2012 (2012), Heidelberg: Springer, Heidelberg · Zbl 1239.94002 |
| [45] | Rabin, T., Advances in Cryptology - CRYPTO 2010 (2010), Heidelberg: Springer, Heidelberg · Zbl 1194.94022 |
| [46] | Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM 56(6), Article 34 (2009), a preliminary version appeared in STOC 2005 (2005) · Zbl 1192.94106 |
| [47] | Stehlé, D.: Private communication (December 12, 2012) |
| [48] | Waters, B.; Cramer, R., Efficient Identity-Based Encryption Without Random Oracles, Advances in Cryptology - EUROCRYPT 2005, 114-127 (2005), Heidelberg: Springer, Heidelberg · Zbl 1137.94360 · doi:10.1007/11426639_7 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
