One of the primary research challenges in AttributeBased Encryption
(ABE) is constructing and proving cryptosystems that are adaptively
secure. To date the main paradigm for achieving adaptive security in
ABE is dual system encryption. However, almost all such solutions in
bilinear groups rely on (variants of) either the subgroup decision
problem over composite order groups or the decision linear assumption.
Both of these assumptions are decisional rather than search
assumptions and the target of the assumption is a source or bilinear
group element. This is in contrast to earlier selectively secure ABE
systems which can be proven secure from either the decisional or
search Bilinear DiffieHellman assumption. In this work we make
progress on closing this gap by giving a new ABE construction for the
subset functionality and prove security under the Search Bilinear
DiffieHellman assumption.
We first provide a framework for
proving adaptive security in AttributeBased Encryption systems. We
introduce a concept of ABE with deletable attributes where any party
can take a ciphertext encrypted under the attribute string and modify it into a ciphertext encrypted under any string where is derived by replacing any bits of
with symbols (i.e. ``deleting" attributes of ). The
semantics of the system are that any private key for a circuit can
be used to decrypt a ciphertext associated with if none of the
input bits read by circuit are symbols and .
We show a pathway for combining ABE
with deletable attributes with constrained psuedorandom functions to
obtain adaptively secure ABE building upon the recent work of
Tsabary. Our new ABE system will be adaptively
secure and be a ciphertextpolicy ABE that supports the same
functionality as the underlying constrained PRF as long as the PRF is
``deletion conforming". Here we also provide a simple constrained PRF
construction that gives subset functionality.
Our approach enables us to access a
broader array of AttributeBased Encryption schemes support deletion
of attributes. For example, we show that both the Goyal~et
al.~(GPSW) and Boyen ABE schemes can
trivially handle a deletion operation. And, by using a hardcore bit
variant of GPSW scheme we obtain an adaptively secure ABE scheme under
the Search Bilinear DiffieHellman assumption in addition to
pseudo random functions in NC1. This gives the first adaptively
secure ABE from a search assumption as all prior work relied on
decision assumptions over source group elements.
more »
« less
Bounded Collusion ABE for TMs from IBE
We give an attributebased encryption system for Turing Machines that is provably secure assuming only the existence of identitybased encryption (IBE) for large identity spaces. Currently, IBE is known to be realizable from most mainstream number theoretic assumptions that imply public key cryptography including factoring, the search DiffieHellman assumption, and the Learning with Errors assumption.
Our core construction provides security against an attacker that makes a single key query for a machine before declaring a challenge string that is associated with the challenge ciphertext. We build our construction by leveraging a Garbled RAM construction of Gentry, Halevi, Raykova, and Wichs; however, to prove security we need to introduce a new notion of security called iterated simulation security.
We then show how to transform our core construction into one that is secure for an apriori bounded number of key queries that can occur either before or after the challenge ciphertext. We do this by first showing how one can use a special type of noncommitting encryption to transform a system that is secure only if a single key is chosen before the challenge ciphertext is declared into one where the single key can be requested either before or after the challenge ciphertext. We give a simple construction of this noncommitting encryption from public key encryption in the Random Oracle Model. Next, one can apply standard combinatorial techniques to lift from singlekey adaptive security to key adaptive security.
more »
« less
 Award ID(s):
 1908611
 NSFPAR ID:
 10345415
 Date Published:
 Journal Name:
 Asiacrypt 2021
 Page Range / eLocation ID:
 371402
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Largescale quantum computing is a significant threat to classical publickey cryptography. In strong "quantum access" security models, numerous symmetrickey cryptosystems are also vulnerable. We consider classical encryption in a model which grants the adversary quantum oracle access to encryption and decryption, but where the latter is restricted to nonadaptive (i.e., prechallenge) queries only. We define this model formally using appropriate notions of ciphertext indistinguishability and semantic security (which are equivalent by standard arguments) and call it QCCA1 in analogy to the classical CCA1 security model. Using a bound on quantum randomaccess codes, we show that the standard PRF and PRPbased encryption schemes are QCCA1secure when instantiated with quantumsecure primitives. We then revisit standard INDCPAsecure Learning with Errors (LWE) encryption and show that leaking just one quantum decryption query (and no other queries or leakage of any kind) allows the adversary to recover the full secret key with constant success probability. In the classical setting, by contrast, recovering the key uses a linear number of decryption queries, and this is optimal. The algorithm at the core of our attack is a (largemodulus version of) the wellknown BernsteinVazirani algorithm. We emphasize that our results should *not* be interpreted as a weakness of these cryptosystems in their stated security setting (i.e., postquantum chosenplaintext secrecy). Rather, our results mean that, if these cryptosystems are exposed to chosenciphertext attacks (e.g., as a result of deployment in an inappropriate realworld setting) then quantum attacks are even more devastating than classical ones.more » « less

Rosulek, Mike (Ed.)We introduce flexible passwordbased encryption (FPBE), an extension of traditional passwordbased encryption designed to meet the operational and security needs of contemporary applications like endtoend secure cloud storage. Operationally, FPBE supports nonces, associated data and salt reuse. Securitywise, it strengthens the usual privacy requirement, and, most importantly, adds an authenticity requirement, crucial because endtoend security must protect against a malicious server. We give an FPBE scheme called DtE that is not only proven secure, but with good bounds. The challenge, with regard to the latter, is in circumventing partitioningoracle attacks, which is done by leveraging keyrobust (also called keycommitting) encryption and a notion of authenticity with corruptions. DtE can be instantiated to yield an efficient and practical FPBE scheme for the target applications.more » « less

We study the problem of encrypting and authenticating quantum data in the presence of adversaries making adaptive chosen plaintext and chosen ciphertext queries. Classically, security games use string copying and comparison to detect adversarial cheating in such scenarios. Quantumly, this approach would violate nocloning. We develop new techniques to overcome this problem: we use entanglement to detect cheating, and rely on recent results for characterizing quantum encryption schemes. We give definitions for (i) ciphertext unforgeability, (ii) indistinguishability under adaptive chosenciphertext attack, and (iii) authenticated encryption. The restriction of each definition to the classical setting is at least as strong as the corresponding classical notion: (i) implies INTCTXT , (ii) implies INDCCA2 , and (iii) implies AE . All of our new notions also imply QINDCPA privacy. Combining onetime authentication and classical pseudorandomness, we construct symmetrickey quantum encryption schemes for each of these new security notions, and provide several separation examples. Along the way, we also give a new definition of onetime quantum authentication which, unlike all previous approaches, authenticates ciphertexts rather than plaintexts.more » « less

Atluri, Vijayalakshmi ; Di Pietro, Roberto ; Jensen, Christian D. ; Meng, Weizhi (Ed.)We provide a strong definition for committing authenticated encryption (cAE), as well as a framework that encompasses earlier and weaker definitions. The framework attends not only to what is committed but also the extent to which the adversary knows or controls keys. We slot into our framework strengthened cAEattacks on GCM and OCB. Our main result is a simple and efficient construction, CTX, that makes a noncebased AE (nAE) scheme committing. The transformed scheme achieves the strongest security notion in our framework. Just the same, the added computational cost (on top of the nAE scheme’s cost) is a single hash over a short string, a cost independent of the plaintext’s length. And there is no increase in ciphertext length compared to the base nAE scheme. That such a thing is possible, let alone easy, upends the (incorrect) intuition that you can’t commit to a plaintext or ciphertext without hashing one or the other. And it motivates a simple and practical tweak to AEschemes to make them committing.more » « less