{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T08:58:34Z","timestamp":1766048314562,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642289132"},{"type":"electronic","value":"9783642289149"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-28914-9_25","type":"book-chapter","created":{"date-parts":[[2012,3,5]],"date-time":"2012-03-05T21:12:39Z","timestamp":1330981959000},"page":"440-457","source":"Crossref","is-referenced-by-count":11,"title":["On Black-Box Reductions between Predicate Encryption Schemes"],"prefix":"10.1007","author":[{"given":"Vipul","family":"Goyal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Virendra","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Satya","family":"Lokam","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad","family":"Mahmoody","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"25_CR1","doi-asserted-by":"crossref","unstructured":"Babai, L., Frankl, P., Simon, J.: Complexity classes in communication complexity theory (preliminary version). In: FOCS, pp. 337\u2013347 (1986)","DOI":"10.1109\/SFCS.1986.15"},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"Barak, B., Mahmoody-Ghidary, M.: Lower Bounds on Signatures From Symmetric Primitives. In: FOCS, pp. 680\u2013688 (2007)","DOI":"10.1109\/FOCS.2007.71"},{"key":"25_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-642-03356-8_22","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"B. Barak","year":"2009","unstructured":"Barak, B., Mahmoody-Ghidary, M.: Merkle Puzzles Are Optimal \u2014 An O(n 2)-Query Attack on Any Key Exchange from a Random Oracle. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol.\u00a05677, pp. 374\u2013390. Springer, Heidelberg (2009)"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"Bellare, M., Rogaway, P.: Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In: ACM Conference on Computer and Communications Security, pp. 62\u201373 (1993)","DOI":"10.1145\/168588.168596"},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"Boldyreva, A., Goyal, V., Kumar, V.: Identity-based encryption with efficient revocation. In: ACM Conference on Computer and Communications Security, pp. 417\u2013426 (2008)","DOI":"10.1145\/1455770.1455823"},{"key":"25_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/978-3-540-24676-3_14","volume-title":"Advances in Cryptology - EUROCRYPT 2004","author":"D. Boneh","year":"2004","unstructured":"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.\u00a03027, pp. 223\u2013238. Springer, Heidelberg (2004)"},{"key":"25_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/978-3-540-28628-8_27","volume-title":"Advances in Cryptology \u2013 CRYPTO 2004","author":"D. Boneh","year":"2004","unstructured":"Boneh, D., Boyen, X.: Secure Identity Based Encryption Without Random Oracles. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol.\u00a03152, pp. 443\u2013459. Springer, Heidelberg (2004)"},{"issue":"3","key":"25_CR8","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1137\/S0097539701398521","volume":"32","author":"D. Boneh","year":"2003","unstructured":"Boneh, D., Franklin, M.K.: Identity-Based Encryption from the Weil Pairing. SIAM J. Comput.\u00a032(3), 586\u2013615 (2003)","journal-title":"SIAM J. Comput."},{"key":"25_CR9","doi-asserted-by":"crossref","unstructured":"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\u2013292 (2008)","DOI":"10.1109\/FOCS.2008.67"},{"key":"25_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/978-3-642-19571-6_16","volume-title":"Theory of Cryptography","author":"D. Boneh","year":"2011","unstructured":"Boneh, D., Sahai, A., Waters, B.: Functional Encryption: Definitions and Challenges. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol.\u00a06597, pp. 253\u2013273. Springer, Heidelberg (2011)"},{"key":"25_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/978-3-540-70936-7_29","volume-title":"Theory of Cryptography","author":"D. Boneh","year":"2007","unstructured":"Boneh, D., Waters, B.: Conjunctive, Subset, and Range Queries on Encrypted Data. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol.\u00a04392, pp. 535\u2013554. Springer, Heidelberg (2007)"},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"Cocks, C.: An Identity Based Encryption Scheme Based on Quadratic Residues. In: IMA Int. Conf., pp. 360\u2013363 (2001)","DOI":"10.1007\/3-540-45325-3_32"},{"key":"25_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1007\/3-540-48405-1_34","volume-title":"Advances in Cryptology - CRYPTO \u201999","author":"E. Fujisaki","year":"1999","unstructured":"Fujisaki, E., Okamoto, T.: Secure Integration of Asymmetric and Symmetric Encryption Schemes. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol.\u00a01666, pp. 537\u2013554. Springer, Heidelberg (1999)"},{"key":"25_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/11761679_27","volume-title":"Advances in Cryptology - EUROCRYPT 2006","author":"C. Gentry","year":"2006","unstructured":"Gentry, C.: Practical Identity-Based Encryption Without Random Oracles. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol.\u00a04004, pp. 445\u2013464. Springer, Heidelberg (2006)"},{"key":"25_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1007\/978-3-540-74143-5_24","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"V. Goyal","year":"2007","unstructured":"Goyal, V.: Reducing Trust in the PKG in Identity Based Cryptosystems. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol.\u00a04622, pp. 430\u2013447. Springer, Heidelberg (2007)"},{"key":"25_CR16","series-title":"LNCS","first-page":"440","volume-title":"TCC 2012","author":"V. Goyal","year":"2012","unstructured":"Goyal, V., Kumar, V., Lokam, S., Mahmoody, M.: On Black-Box Reductions Between Predicate Encryption Schemes. In: Cramer, R. (ed.) TCC 2012. LNCS, vol.\u00a07194, pp. 440\u2013457. Springer, Heidelberg (2012), http:\/\/eprint.iacr.org"},{"key":"25_CR17","doi-asserted-by":"crossref","unstructured":"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\u201398 (2006)","DOI":"10.1145\/1180405.1180418"},{"key":"25_CR18","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Rudich, S.: Limits on the Provable Consequences of One-Way Permutations. In: STOC, pp. 44\u201361 (1989)","DOI":"10.1145\/73007.73012"},{"key":"25_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/978-3-540-78967-3_9","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2008","author":"J. Katz","year":"2008","unstructured":"Katz, J., Sahai, A., Waters, B.: Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol.\u00a04965, pp. 146\u2013162. Springer, Heidelberg (2008)"},{"key":"25_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/978-3-642-10366-7_12","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2009","author":"J. Katz","year":"2009","unstructured":"Katz, J., Yerukhimovich, A.: On Black-Box Constructions of Predicate Encryption from Trapdoor Permutations. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol.\u00a05912, pp. 197\u2013213. Springer, Heidelberg (2009)"},{"key":"25_CR21","doi-asserted-by":"crossref","unstructured":"Klauck, H.: Rectangle Size Bounds and Threshold Covers in Communication Complexity. In: IEEE Conference on Computational Complexity, pp. 118\u2013134 (2003)","DOI":"10.1109\/CCC.2003.1214415"},{"key":"25_CR22","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511574948"},{"issue":"4","key":"25_CR23","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1561\/0400000040","volume":"3","author":"T. Lee","year":"2009","unstructured":"Lee, T., Shraibman, A.: Lower Bounds in Communication Complexity. Foundations and Trends in Theoretical Computer Science\u00a03(4), 263\u2013398 (2009)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"25_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/978-3-642-13190-5_4","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"A.B. Lewko","year":"2010","unstructured":"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.\u00a06110, pp. 62\u201391. Springer, Heidelberg (2010)"},{"issue":"3","key":"25_CR25","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1006\/jcss.2001.1786","volume":"63","author":"S.V. Lokam","year":"2001","unstructured":"Lokam, S.V.: Spectral Methods for Matrix Rigidity with Applications to Size-Depth Trade-offs and Communication Complexity. J. Comput. Syst. Sci.\u00a063(3), 449\u2013473 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1-2","key":"25_CR26","first-page":"1","volume":"4","author":"S.V. Lokam","year":"2009","unstructured":"Lokam, S.V.: Complexity Lower Bounds using Linear Algebra. Foundations and Trends in Theoretical Computer Science\u00a04(1-2), 1\u2013155 (2009)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"25_CR27","unstructured":"Mahmoody-Ghidary, M., Wigderson, A.: Black Boxes, Incorporated (2009), http:\/\/www.cs.cornell.edu\/~mohammad\/files\/papers\/BlackBoxes.pdf"},{"key":"25_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/978-3-642-14623-7_11","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"T. Okamoto","year":"2010","unstructured":"Okamoto, T., Takashima, K.: Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.\u00a06223, pp. 191\u2013208. Springer, Heidelberg (2010)"},{"key":"25_CR29","unstructured":"Razborov, A.: On Rigid Matrices (1989) (in Russian), http:\/\/people.cs.uchicago.edu\/~razborov\/rigid.pdf"},{"key":"25_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-24638-1_1","volume-title":"Theory of Cryptography","author":"O. Reingold","year":"2004","unstructured":"Reingold, O., Trevisan, L., Vadhan, S.P.: Notions of Reducibility between Cryptographic Primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol.\u00a02951, pp. 1\u201320. Springer, Heidelberg (2004)"},{"key":"25_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1007\/11426639_27","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2005","author":"A. Sahai","year":"2005","unstructured":"Sahai, A., Waters, B.: Fuzzy Identity-Based Encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol.\u00a03494, pp. 457\u2013473. Springer, Heidelberg (2005)"},{"key":"25_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/3-540-39568-7_5","volume-title":"Advances in Cryptology","author":"A. Shamir","year":"1985","unstructured":"Shamir, A.: Identity-Based Cryptosystems and Signature Schemes. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol.\u00a0196, pp. 47\u201353. Springer, Heidelberg (1985)"},{"key":"25_CR33","doi-asserted-by":"crossref","unstructured":"Sipser, M.: Borel Sets and Circuit Complexity. In: STOC, pp. 61\u201369 (1983)","DOI":"10.1145\/800061.808733"},{"key":"25_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/11426639_7","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2005","author":"B. Waters","year":"2005","unstructured":"Waters, B.: Efficient Identity-Based Encryption Without Random Oracles. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol.\u00a03494, pp. 114\u2013127. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-28914-9_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T12:03:50Z","timestamp":1742645030000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28914-9_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642289132","9783642289149"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28914-9_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}