Abstract
We prove that there is no black-box construction of a threshold predicate encryption system from identity-based encryption. Our result signifies nontrivial progress in a line of research suggested by Boneh, Sahai and Waters (TCC ’11), where they proposed a study of the relative power of predicate encryption for different functionalities. We rely on and extend the techniques of Boneh et al. (FOCS ’08), where they give a black-box separation of identity-based encryption from trapdoor permutations.
In contrast to previous results where only trapdoor permutations were used, our starting point is a more powerful primitive, namely identity-based encryption, which allows planting exponentially many trapdoors in the public-key by only planting a single master public-key of an identity-based encryption system. This makes the combinatorial aspect of our black-box separation result much more challenging. Our work gives the first impossibility result on black-box constructions of any cryptographic primitive from identity-based encryption.
We also study the more general question of constructing predicate encryption for a complexity class \(\mathbb{F}\), given predicate encryption for a (potentially less powerful) complexity class \(\mathbb{G}\). Toward that end, we rule out certain natural black-box constructions of predicate encryption for NC 1 from predicate encryption for AC 0 assuming a widely believed conjecture in communication complexity.
Chapter PDF
Similar content being viewed by others
References
Babai, L., Frankl, P., Simon, J.: Complexity classes in communication complexity theory (preliminary version). In: FOCS, pp. 337–347 (1986)
Barak, B., Mahmoody-Ghidary, M.: Lower Bounds on Signatures From Symmetric Primitives. In: FOCS, pp. 680–688 (2007)
Barak, B., Mahmoody-Ghidary, M.: Merkle Puzzles Are Optimal — An O(n 2)-Query Attack on Any Key Exchange from a Random Oracle. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 374–390. Springer, Heidelberg (2009)
Bellare, M., Rogaway, P.: Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In: ACM Conference on Computer and Communications Security, pp. 62–73 (1993)
Boldyreva, A., Goyal, V., Kumar, V.: Identity-based encryption with efficient revocation. In: ACM Conference on Computer and Communications Security, pp. 417–426 (2008)
Boneh, D., Boyen, X.: Efficient Selective-ID Secure Identity-Based Encryption Without Random Oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 223–238. Springer, Heidelberg (2004)
Boneh, D., Boyen, X.: Secure Identity Based Encryption Without Random Oracles. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 443–459. Springer, Heidelberg (2004)
Boneh, D., Franklin, M.K.: Identity-Based Encryption from the Weil Pairing. SIAM J. Comput. 32(3), 586–615 (2003)
Boneh, D., Papakonstantinou, P.A., Rackoff, C., Vahlis, Y., Waters, B.: On the Impossibility of Basing Identity Based Encryption on Trapdoor Permutations. In: FOCS, pp. 283–292 (2008)
Boneh, D., Sahai, A., Waters, B.: Functional Encryption: Definitions and Challenges. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 253–273. Springer, Heidelberg (2011)
Boneh, D., Waters, B.: Conjunctive, Subset, and Range Queries on Encrypted Data. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 535–554. Springer, Heidelberg (2007)
Cocks, C.: An Identity Based Encryption Scheme Based on Quadratic Residues. In: IMA Int. Conf., pp. 360–363 (2001)
Fujisaki, E., Okamoto, T.: Secure Integration of Asymmetric and Symmetric Encryption Schemes. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 537–554. Springer, Heidelberg (1999)
Gentry, C.: Practical Identity-Based Encryption Without Random Oracles. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 445–464. Springer, Heidelberg (2006)
Goyal, V.: Reducing Trust in the PKG in Identity Based Cryptosystems. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 430–447. Springer, Heidelberg (2007)
Goyal, V., Kumar, V., Lokam, S., Mahmoody, M.: On Black-Box Reductions Between Predicate Encryption Schemes. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 440–457. Springer, Heidelberg (2012), http://eprint.iacr.org
Goyal, V., Pandey, O., Sahai, A., Waters, B.: Attribute-based encryption for fine-grained access control of encrypted data. In: ACM Conference on Computer and Communications Security, pp. 89–98 (2006)
Impagliazzo, R., Rudich, S.: Limits on the Provable Consequences of One-Way Permutations. In: STOC, pp. 44–61 (1989)
Katz, J., Sahai, A., Waters, B.: Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 146–162. Springer, Heidelberg (2008)
Katz, J., Yerukhimovich, A.: On Black-Box Constructions of Predicate Encryption from Trapdoor Permutations. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 197–213. Springer, Heidelberg (2009)
Klauck, H.: Rectangle Size Bounds and Threshold Covers in Communication Complexity. In: IEEE Conference on Computational Complexity, pp. 118–134 (2003)
Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press (1997)
Lee, T., Shraibman, A.: Lower Bounds in Communication Complexity. Foundations and Trends in Theoretical Computer Science 3(4), 263–398 (2009)
Lewko, A.B., Okamoto, T., Sahai, A., Takashima, K., Waters, B.: Fully Secure Functional Encryption: Attribute-Based Encryption and (Hierarchical) Inner Product Encryption. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 62–91. Springer, Heidelberg (2010)
Lokam, S.V.: Spectral Methods for Matrix Rigidity with Applications to Size-Depth Trade-offs and Communication Complexity. J. Comput. Syst. Sci. 63(3), 449–473 (2001)
Lokam, S.V.: Complexity Lower Bounds using Linear Algebra. Foundations and Trends in Theoretical Computer Science 4(1-2), 1–155 (2009)
Mahmoody-Ghidary, M., Wigderson, A.: Black Boxes, Incorporated (2009), http://www.cs.cornell.edu/~mohammad/files/papers/BlackBoxes.pdf
Okamoto, T., Takashima, K.: Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 191–208. Springer, Heidelberg (2010)
Razborov, A.: On Rigid Matrices (1989) (in Russian), http://people.cs.uchicago.edu/~razborov/rigid.pdf
Reingold, O., Trevisan, L., Vadhan, S.P.: Notions of Reducibility between Cryptographic Primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 1–20. Springer, Heidelberg (2004)
Sahai, A., Waters, B.: Fuzzy Identity-Based Encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 457–473. Springer, Heidelberg (2005)
Shamir, A.: Identity-Based Cryptosystems and Signature Schemes. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47–53. Springer, Heidelberg (1985)
Sipser, M.: Borel Sets and Circuit Complexity. In: STOC, pp. 61–69 (1983)
Waters, B.: Efficient Identity-Based Encryption Without Random Oracles. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 114–127. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goyal, V., Kumar, V., Lokam, S., Mahmoody, M. (2012). On Black-Box Reductions between Predicate Encryption Schemes. In: Cramer, R. (eds) Theory of Cryptography. TCC 2012. Lecture Notes in Computer Science, vol 7194. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-28914-9_25
Download citation
DOI: https://doi.org/10.1007/978-3-642-28914-9_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-28913-2
Online ISBN: 978-3-642-28914-9
eBook Packages: Computer ScienceComputer Science (R0)