Why Proving HIBE Systems Secure Is Difficult
Proving security of Hierarchical Identity-Based Encryption (HIBE) and Attribution Based Encryption scheme is a challenging problem. There are multiple well-known schemes in the literature where the best known (adaptive) security proofs degrade exponential
- PDF / 304,768 Bytes
- 19 Pages / 439.363 x 666.131 pts Page_size
- 1 Downloads / 185 Views
2
1 Columbia University [email protected] University of Texas at Austin [email protected]
Abstract. Proving security of Hierarchical Identity-Based Encryption (HIBE) and Attribution Based Encryption scheme is a challenging problem. There are multiple well-known schemes in the literature where the best known (adaptive) security proofs degrade exponentially in the maximum hierarchy depth. However, we do not have a rigorous understanding of why better proofs are not known. (For ABE, the analog of hierarchy depth is the maximum number of attributes used in a ciphertext.) In this work, we define a certain commonly found checkability property on ciphertexts and private keys. Roughly the property states that any two different private keys that are both “supposed to” decrypt a ciphertext will decrypt it to the same message. We show that any simple black box reduction to a non-interactive assumption for a HIBE or ABE system that contains this property will suffer an exponential degradation of security.
1
Introduction
In recent years, there has been emerging interest in increasing the expressiveness of encryption systems in terms of targeting ciphertexts to certain groups of users. First examples included Hierarchical Identity-Based Encryption (HIBE) [HL02] and Attribute-Based Encryption (ABE) [SW05]. The early difficulty in HIBE and ABE research was to obtain systems that were provably secure under robust security definitions. Initial constructions of HIBE [GS02, CHK03, BB04, BBG05] and ABE [SW05, GPSW06] had the drawback that their security reductions degraded exponentially in the depth of the hierarchy when encrypting an HIBE ciphertext or number of attributes used when creating an ABE ciphertext. For this reason, the first (standard model) security proofs were done in the selective
Work done while this author was at Microsoft Research. Supported by NSF CNS-0915361 and CNS-0952692, CNS-1228599 DARPA through the U.S. Office of Naval Research under Contract N00014-11-1-0382, DARPA N11AP20006, Google Faculty Research award, the Alfred P. Sloan Fellowship, Microsoft Faculty Fellowship, and Packard Foundation Fellowship. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the Department of Defense or the U.S. Government.
P.Q. Nguyen and E. Oswald (Eds.): EUROCRYPT 2014, LNCS 8441, pp. 58–76, 2014. c International Association for Cryptologic Research 2014
Why Proving HIBE Systems Secure Is Difficult
59
model, a term coined by Canetti, Halevi and Katz [CHK03]. In this weaker model, an attacker (artificially) declared the challenge identity he was attacking before seeing the public parameters of the system. At the time, researchers identified achieving standard (sometimes called adaptive or full) security for these systems as an important open problem. However, it was not well understood whether there existed full security reductions for the already proposed constructions without exponential decay, and if not, why. W
Data Loading...
