Attribute-based encryption with non-monotonic access structures

ABSTRACT

We construct an Attribute-Based Encryption (ABE) scheme that allows a user's private key to be expressed in terms of any access formula over attributes. Previous ABE schemes were limited to expressing only monotonic access structures. We provide a proof of security for our scheme based on the Decisional Bilinear Diffie-Hellman (BDH) assumption. Furthermore, the performance of our new scheme compares favorably with existing, less-expressive schemes.

REFERENCES

• 1: H. Anton and C. Rorres. Elementary Linear Algebra, 9th Edition. 2005.
• 2: A. Beimel. Secure Schemes for Secret Sharing and Key Distribution. PhD thesis, Israel Institute of Technology, Technion, Haifa, Israel, 1996.
• 3: Josh Cohen Benaloh , Jerry Leichter, Generalized Secret Sharing and Monotone Functions, Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, p.27-35, August 21-25, 1988
• 4: John Bethencourt , Amit Sahai , Brent Waters, Ciphertext-Policy Attribute-Based Encryption, Proceedings of the 2007 IEEE Symposium on Security and Privacy, p.321-334, May 20-23, 2007 [doi>10.1109/SP.2007.11]
• 5: G. R. Blakley. Safeguarding cryptographic keys. In National Computer Conference, pages 313--317. American Federation of Information Processing Societies Proceedings, 1979.
• 6: D. Boneh and X. Boyen. Efficient Selective-ID Secure Identity Based Encryption Without Random Oracles. In Advances in Cryptology - Eurocrypt, volume 3027 of LNCS, pages 223--238. Springer, 2004.
• 7: Dan Boneh , Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.213-229, August 19-23, 2001
• 8: D. Boneh, C. Gentry, and B. Waters. Collusion Resistant Broadcast Encryption with Short Ciphertexts and Private Keys. In Advances in Cryptology - CRYPTO, volume 3621 of LNCS, pages 258--275. Springer, 2005.
• 9: Robert W. Bradshaw , Jason E. Holt , Kent E. Seamons, Concealing complex policies with hidden credentials, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030104]
• 10: E. F. Brickell. Some ideal secret sharing schemes. Journal of Combinatorial Mathematics and Combinatorial Computing, 6:105--113, 1989.
• 11: R. Canetti, S. Halevi, and J. Katz. A Forward-Secure Public-Key Encryption Scheme. In Advances in Cryptology - Eurocrypt, volume 2656 of LNCS. Springer, 2003.
• 12: R. Canetti, S. Halevi, and J. Katz. Chosen Ciphertext Security from Identity Based Encryption. In Advances in Cryptology - Eurocrypt, volume 3027 of LNCS, pages 207--222. Springer, 2004.
• 13: M. Chase. Multi-authority attribute-based encryption. In The Fourth Theory of Cryptography Conference (TCC 2007), 2007.
• 14: Ling Cheung , Calvin Newport, Provably secure ciphertext policy ABE, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315302]
• 15: Clifford Cocks, An Identity Based Encryption Scheme Based on Quadratic Residues, Proceedings of the 8th IMA International Conference on Cryptography and Coding, p.360-363, December 17-19, 2001
• 16: Vipul Goyal , Omkant Pandey , Amit Sahai , Brent Waters, Attribute-based encryption for fine-grained access control of encrypted data, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180418]
• 17: M. Ito, A. Saito, and T. Nishizeki. Secret Sharing Scheme Realizing General Access Structure. In IEEE Globecom. IEEE, 1987.
• 18: Moni Naor , Benny Pinkas, Efficient Trace and Revoke Schemes, Proceedings of the 4th International Conference on Financial Cryptography, p.1-20, February 20-24, 2000
• 19: Matthew Pirretti , Patrick Traynor , Patrick McDaniel , Brent Waters, Secure attribute-based systems, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180419]
• 20: V. V. Prasolov. Problems and Theorems in Linear Algebra. American Mathematical Society, 1994.
• 21: A. Sahai and B. Waters. Fuzzy Identity Based Encryption. In Advances in Cryptology - Eurocrypt, volume 3494 of LNCS, pages 457--473. Springer, 2005.
• 22: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 23: Adi Shamir, Identity-based cryptosystems and signature schemes, Proceedings of CRYPTO 84 on Advances in cryptology, p.47-53, August 1985, Santa Barbara, California, United States
• 24: N. Smart. Access control using pairing based cryptography. In CT-RSA, pages 111--121, 2003.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

General Terms:
Security