International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Allison Bishop

Publications

Year
Venue
Title
2018
CRYPTO
A Simple Obfuscation Scheme for Pattern-Matching with Wildcards 📺
We give a simple and efficient method for obfuscating pattern matching with wildcards. In other words, we construct a way to check an input against a secret pattern, which is described in terms of prescribed values interspersed with unconstrained “wildcard” slots. As long as the support of the pattern is sufficiently sparse and the pattern itself is chosen from an appropriate distribution, we prove that a polynomial-time adversary cannot find a matching input, except with negligible probability. We rely upon the generic group heuristic (in a regular group, with no multilinearity). Previous work [9, 10, 32] provided less efficient constructions based on multilinear maps or LWE.
2016
EUROCRYPT
2016
PKC
2016
TCC
2016
TCC
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
PKC
2015
CRYPTO
2015
ASIACRYPT
2015
ASIACRYPT
2014
CRYPTO
2014
EUROCRYPT
2014
EPRINT
2014
EPRINT
2012
TCC
2012
EUROCRYPT
2012
EUROCRYPT
2012
CRYPTO
2012
ASIACRYPT
2011
TCC
2011
EUROCRYPT
2011
EUROCRYPT
2010
TCC
2010
EPRINT
Fully Secure Functional Encryption: Attribute-Based Encryption and (Hierarchical) Inner Product Encryption
In this paper, we present two fully secure functional encryption schemes. Our first result is a fully secure attribute-based encryption (ABE) scheme. Previous constructions of ABE were only proven to be selectively secure. We achieve full security by adapting the dual system encryption methodology recently introduced by Waters and previously leveraged to obtain fully secure IBE and HIBE systems. The primary challenge in applying dual system encryption to ABE is the richer structure of keys and ciphertexts. In an IBE or HIBE system, keys and ciphertexts are both associated with the same type of simple object: identities. In an ABE system, keys and ciphertexts are associated with more complex objects: attributes and access formulas. We use a novel information-theoretic argument to adapt the dual system encryption methodology to the more complicated structure of ABE systems. We construct our system in composite order bilinear groups, where the order is a product of three primes. We prove the security of our system from three static assumptions. Our ABE scheme supports arbitrary monotone access formulas. Our second result is a fully secure (attribute-hiding) predicate encryption (PE) scheme for inner-product predicates. As for ABE, previous constructions of such schemes were only proven to be selectively secure. Security is proven under a non-interactive assumption whose size does not depend on the number of queries. The scheme is comparably efficient to existing selectively secure schemes. We also present a fully secure hierarchical PE scheme under the same assumption. The key technique used to obtain these results is an elaborate combination of the dual system encryption methodology (adapted to the structure of inner product PE systems) and a new approach on bilinear pairings using the notion of dual pairing vector spaces (DPVS) proposed by Okamoto and Takashima.
2010
EPRINT
Decentralizing Attribute-Based Encryption
Allison B. Lewko Brent Waters
We propose a Multi-Authority Attribute-Based Encryption (ABE) system. In our system, any party can become an authority and there is no requirement for any global coordination other than the creation of an initial set of common reference parameters. A party can simply act as an ABE authority by creating a public key and issuing private keys to different users that reflect their attributes. A user can encrypt data in terms of any boolean formula over attributes issued from any chosen set of authorities. Finally, our system does not require any central authority. In constructing our system, our largest technical hurdle is to make it collusion resistant. Prior Attribute-Based Encryption systems achieved collusion resistance when the ABE system authority ``tied'' together different components (representing different attributes) of a user's private key by randomizing the key. However, in our system each component will come from a potentially different authority, where we assume no coordination between such authorities. We create new techniques to tie key components together and prevent collusion attacks between users with different global identifiers. We prove our system secure using the recent dual system encryption methodology where the security proof works by first converting the challenge ciphertexts and private keys to a semi-functional form and then arguing security. We follow a recent variant of the dual system proof technique due to Lewko and Waters and build our system using bilinear groups of composite order. We prove security under similar static assumptions to the LW paper in the random oracle model.
2010
EPRINT
On the Insecurity of Parallel Repetition for Leakage Resilience
Allison B. Lewko Brent Waters
A fundamental question in leakage-resilient cryptography is: can leakage resilience always be amplified by parallel repetition? It is natural to expect that if we have a leakage-resilient primitive tolerating $\ell$ bits of leakage, we can take $n$ copies of it to form a system tolerating $n\ell$ bits of leakage. In this paper, we show that this is not always true. We construct a public key encryption system which is secure when at most $\ell$ bits are leaked, but if we take $n$ copies of the system and encrypt a share of the message under each using an $n$-out-of-$n$ secret-sharing scheme, leaking $n\ell$ bits renders the system insecure. Our results hold either in composite order bilinear groups under a variant of the subgroup decision assumption \emph{or} in prime order bilinear groups under the decisional linear assumption. We note that the $n$ copies of our public key systems share a common reference parameter.
2010
EPRINT
Achieving Leakage Resilience Through Dual System Encryption
Allison B. Lewko Yannis Rouselakis Brent Waters
In this work, we show that strong leakage resilience for cryptosystems with advanced functionalities can be obtained quite naturally within the methodology of dual system encryption, recently introduced by Waters. We demonstrate this concretely by providing fully secure IBE, HIBE, and ABE systems which are resilient to bounded leakage from each of many secret keys per user, as well as many master keys. This can be realized as resilience against continual leakage if we assume keys are periodically updated and no (or logarithmic) leakage is allowed during the update process. Our systems are obtained by applying a simple modification to previous dual system encryption constructions: essentially this provides a generic tool for making dual system encryption schemes leakage-resilient.
2010
EUROCRYPT

Program Committees

Crypto 2015
TCC 2015
PKC 2014
PKC 2013
TCC 2013
Asiacrypt 2013