×

Attribute-based encryption schemes with constant-size ciphertexts. (English) Zbl 1259.94043

Summary: Attribute-based encryption (ABE), as introduced by Sahai and Waters, allows for fine-grained access control on encrypted data. In its key-policy flavor (the dual ciphertext-policy scenario proceeds the other way around), the primitive enables senders to encrypt messages under a set of attributes and private keys are associated with access structures that specify which ciphertexts the key holder will be allowed to decrypt. In most ABE systems, the ciphertext size grows linearly with the number of ciphertext attributes and the only known exception only supports restricted forms of access policies. This paper proposes the first attribute-based encryption (ABE) schemes allowing for truly expressive access structures and with constant ciphertext size. Our first result is a ciphertext-policy attribute-based encryption (CP-ABE) scheme with \(O(1)\)-size ciphertexts for threshold access policies and where private keys remain as short as in previous systems. As a second result, we show that a certain class of identity-based broadcast encryption schemes generically yields monotonic key-policy attribute-based encryption (KP-ABE) systems in the selective set model. Our final contribution is a KP-ABE realization supporting non-monotonic access structures (i.e., that may contain negated attributes) with short ciphertexts. As an intermediate step toward this result, we describe a new efficient identity-based revocation mechanism that, when combined with a particular instantiation of our general monotonic construction, gives rise to the most expressive KP-ABE realization with constant-size ciphertexts. The downside of our second and third constructions is that private keys have quadratic size in the number of attributes. On the other hand, they reduce the number of pairing evaluations to a constant, which appears to be a unique feature among expressive KP-ABE schemes.

MSC:

94A60 Cryptography
68P25 Data encryption (aspects in computer science)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdalla, M.; Kiltz, E.; Neven, G., Generalized key delegation for hierarchical identity-based encryption, (ESORICS’07. ESORICS’07, LNCS, vol. 4734 (2007), Springer), 139-154
[2] Attrapadung, N.; Imai, H., Dual-policy attribute based encryption, (ACNS’09. ACNS’09, LNCS, vol. 5536 (2009)), 168-185
[3] Attrapadung, N.; Imai, H., Conjunctive broadcast and attribute-based encryption, (Pairing’09. Pairing’09, LNCS, vol. 5671 (2009)), 248-265 · Zbl 1248.94050
[4] Attrapadung, N.; Libert, B., Functional encryption for inner product: achieving constant-size ciphertexts with adaptive security or support for negation, (PKC’10. PKC’10, LNCS, vol. 6056 (2010), Springer), 384-402, Full version available from http://perso.uclouvain.be/benoit.libert/functional-full-version.pdf · Zbl 1281.94013
[5] Attrapadung, N.; Libert, B.; De Panfieu, E., Expressive key-policy attribute-based encryption with constant-size ciphertexts, (PKC’11. PKC’11, LNCS, vol. 6571 (2011), Springer), 90-108 · Zbl 1291.94049
[6] J. Bethencourt, A. Sahai, B. Waters, Ciphertext-policy attribute-based encryption, in: IEEE Symposium on Security and Privacy, S&P, 2007, pp. 321-334.; J. Bethencourt, A. Sahai, B. Waters, Ciphertext-policy attribute-based encryption, in: IEEE Symposium on Security and Privacy, S&P, 2007, pp. 321-334.
[7] Boneh, D.; Boyen, X., Efficient selective-ID secure identity-based encryption without random oracles, (Eurocrypt’04. Eurocrypt’04, LNCS, vol. 3027 (2004)), 223-238 · Zbl 1122.94355
[8] Boneh, D.; Boyen, X.; Goh, E.-J., Hierarchical identity-based encryption with constant size ciphertext, (Eurocrypt’05. Eurocrypt’05, LNCS, vol. 3494 (2005)), 440-456 · Zbl 1137.94340
[9] Boneh, D.; Boyen, X.; Shacham, H., Short group signatures, (Crypto’04. Crypto’04, LNCS, vol. 3152 (2004)), 41-55 · Zbl 1104.94044
[10] Boneh, D.; Franklin, M., Identity-based encryption from the Weil pairing, SIAM Journal of Computing, 32, 3, 586-615 (2003), Earlier version in Crypto’01, LNCS, vol. 2139, 2001, pp. 213-229 · Zbl 1046.94008
[11] Boneh, D.; Gentry, C.; Waters, B., Collusion resistant broadcast encryption with short ciphertexts and private keys, (Crypto’05. Crypto’05, LNCS, vol. 3621 (2005)), 258-275 · Zbl 1145.94434
[12] Boneh, D.; Hamburg, M., Generalized identity based and broadcast encryption schemes, (Asiacrypt’08. Asiacrypt’08, LNCS, vol. 5350 (2008)), 455-470 · Zbl 1206.94054
[13] Boneh, D.; Sahai, A.; Waters, B., Functional encryption: definitions and challenges, (TCC’11. TCC’11, LNCS, vol. 6597 (2011)), 253-273 · Zbl 1295.94027
[14] Boyen, X., General ad hoc encryption from exponent inversion IBE, (Eurocrypt’07. Eurocrypt’07, LNCS, vol. 4515 (2007)), 394-411 · Zbl 1141.94343
[15] Canetti, R.; Halevi, S.; Katz, J., A forward-secure public-key encryption scheme, (Eurocrypt’03. Eurocrypt’03, LNCS, vol. 2656 (2003)), 254-271 · Zbl 1037.68532
[16] Canetti, R.; Halevi, S.; Katz, J., Chosen-ciphertext security from identity-based encryption, (Eurocrypt’04. Eurocrypt’04, LNCS, vol. 3027 (2004)), 207-222 · Zbl 1122.94358
[17] Chase, M., Multi-authority attribute based encryption, (TCC’07. TCC’07, LNCS, vol. 4392 (2007)), 515-534 · Zbl 1156.94339
[18] M. Chase, S. Chow, Improving privacy and security in multi-authority attribute-based encryption, in: ACM-CCS’09, 2009, pp. 121-130.; M. Chase, S. Chow, Improving privacy and security in multi-authority attribute-based encryption, in: ACM-CCS’09, 2009, pp. 121-130.
[19] Cheon, J.-H., Security analysis of the strong diffie-hellman problem, (Eurocrypt’06. Eurocrypt’06, LNCS, vol. 4004 (2006)), 1-11 · Zbl 1129.94017
[20] L. Cheung, C. Newport, Provably secure ciphertext policy ABE, in: ACM-CCS’07, 2007, pp. 456-465.; L. Cheung, C. Newport, Provably secure ciphertext policy ABE, in: ACM-CCS’07, 2007, pp. 456-465.
[21] Delerablée, C.; Paillier, P.; Pointcheval, D., Fully collusion secure dynamic broadcast encryption with constant-size ciphertexts or decryption keys, (Pairing’07. Pairing’07, LNCS, vol. 4575 (2007), Springer), 39-59 · Zbl 1151.94502
[22] Delerablée, C.; Pointcheval, D., Dynamic threshold public-key encryption, (Crypto’08. Crypto’08, LNCS, vol. 5157 (2008), Springer), 317-334 · Zbl 1183.94028
[23] Emura, K.; Miyaji, A.; Nomura, A.; Omote, K.; Soshi, M., A ciphertext-policy attribute-based encryption scheme with constant ciphertext length, (ISPEC ’09. ISPEC ’09, LNCS, vol. 5451 (2009)), 13-23 · Zbl 1195.94054
[24] V. Goyal, O. Pandey, A. Sahai, B. Waters, Attribute-based encryption for fine-grained access control of encrypted data, in: ACM CCS’06, 2006, pp. 89-98.; V. Goyal, O. Pandey, A. Sahai, B. Waters, Attribute-based encryption for fine-grained access control of encrypted data, in: ACM CCS’06, 2006, pp. 89-98.
[25] Goyal, V.; Jain, A.; Pandey, O.; Sahai, A., Bounded ciphertext policy attribute based encryption, (ICALP (2) 2008. ICALP (2) 2008, LNCS, vol. 5126 (2008)), 579-591 · Zbl 1155.94369
[26] Herranz, J.; Laguillaumie, F.; Ràfols, C., Constant-size ciphertexts in threshold attribute-based encryption, (PKC’10. PKC’10, LNCS, vol. 6056 (2010), Springer) · Zbl 1271.94021
[27] Katz, J.; Sahai, A.; Waters, B., Predicate encryption supporting disjunctions, polynomial equations, and inner products, (Eurocrypt’08. Eurocrypt’08, LNCS, vol. 4965 (2008)), 146-162 · Zbl 1149.94323
[28] A. Lewko, A. Sahai, B. Waters, Revocation systems with very small private keys, in: IEEE Symposium on Security and Privacy, S&P, 2010.; A. Lewko, A. Sahai, B. Waters, Revocation systems with very small private keys, in: IEEE Symposium on Security and Privacy, S&P, 2010.
[29] Lewko, A.; Okamoto, T.; Sahai, A.; Takashima, K.; Waters, B., Fully secure functional encryption: attribute-based encryption and (hierarchical) inner product encryption, (Eurocrypt’10. Eurocrypt’10, LNCS, vol. 6110 (2010)), 62-91 · Zbl 1279.94095
[30] Naor, M., On cryptographic assumptions and challenges, (Crypto’03. Crypto’03, LNCS, vol. 2729 (2003)), 96-109 · Zbl 1122.94391
[31] Naor, M.; Pinkas, B., Efficient trace and revoke schemes, (Financial Cryptography 2000. Financial Cryptography 2000, LNCS, vol. 1962 (2000)), 1-20 · Zbl 0999.94522
[32] R. Ostrovsky, A. Sahai, B. Waters, Attribute-based encryption with non-monotonic access structures, in: ACM-CCS’07, 2007, pp. 195-203.; R. Ostrovsky, A. Sahai, B. Waters, Attribute-based encryption with non-monotonic access structures, in: ACM-CCS’07, 2007, pp. 195-203.
[33] R. Sakai, M. Kasahara, ID-based cryptosystems with pairing on elliptic curve, Cryptology ePrint Archive: Report 2003/054 (2003).; R. Sakai, M. Kasahara, ID-based cryptosystems with pairing on elliptic curve, Cryptology ePrint Archive: Report 2003/054 (2003).
[34] Sahai, A.; Waters, B., Fuzzy identity-based encryption, (Eurocrypt’05. Eurocrypt’05, LNCS, vol. 3494 (2005)), 457-473 · Zbl 1137.94355
[35] Shamir, A., Identity-based cryptosystems and signature schemes, (Crypto’84. Crypto’84, LNCS, vol. 196 (1984)), 47-53 · Zbl 1359.94626
[36] Okamoto, T.; Takashima, K., Fully secure functional encryption with general relations from the Decisional Linear assumption, (Crypto’10. Crypto’10, LNCS, vol. 6223 (2010)), 191-208 · Zbl 1280.94086
[37] Waters, B., Ciphertext-policy attribute-based encryption: an expressive, efficient, and provably secure realization, (PKC 2011. PKC 2011, LNCS, vol. 6571 (2011)), 53-70 · Zbl 1291.94165
[38] Yamada, S.; Attrapadung, N.; Hanaoka, G.; Kunihiro, N., Generic constructions for chosen-ciphertext secure attribute based encryption, (PKC 2011. PKC 2011, LNCS, vol. 6571 (2011)), 71-89 · Zbl 1291.94170
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.