CryptoDB
Jiahui Liu
Publications
Year
Venue
Title
2021
CRYPTO
New Approaches for Quantum Copy-Protection
📺
Abstract
Quantum copy protection uses the unclonability of quantum states to construct quantum software that provably cannot be pirated. Copy protection would be immensely useful, but unfortunately little is known about how to achieve it in general. In this work, we make progress on this goal, by giving the following results:
* We show how to copy protect any program that cannot be learned from its input-output behavior, relative to a classical oracle. This improves on Aaronson (CCC 2009), which achieves the same relative to a quantum oracle. By instantiating the oracle with post-quantum candidate obfuscation schemes, we obtain a heuristic construction of copy protection.
* We show, roughly, that any program which can be watermarked can be copy detected, a weaker version of copy protection that does not prevent copying, but guarantees that any copying can be detected. Our scheme relies on the security of the assumed watermarking, plus the assumed existence of public key quantum money. Our construction is general, applicable to many recent watermarking schemes.
2021
CRYPTO
Hidden Cosets and Applications to Unclonable Cryptography
📺
Abstract
In 2012, Aaronson and Christiano introduced the idea of hidden subspace states to build public-key quantum money [STOC '12]. Since then, this idea has been applied to realize several other cryptographic primitives which enjoy some form of unclonability.
In this work, we propose a generalization of hidden subspace states to hidden coset states. We study different unclonable properties of coset states and several applications:
* We show that, assuming indistinguishability obfuscation (iO), hidden coset states possess a certain direct product hardness property, which immediately implies a tokenized signature scheme in the plain model. Previously, a tokenized signature scheme was known only relative to an oracle, from a work of Ben-David and Sattath [QCrypt '17].
* Combining a tokenized signature scheme with extractable witness encryption, we give a construction of an unclonable decryption scheme in the plain model. The latter primitive was recently proposed by Georgiou and Zhandry [ePrint '20], who gave a construction relative to a classical oracle.
* We conjecture that coset states satisfy a certain natural monogamy-of-entanglement property. Assuming this conjecture is true, we remove the requirement for extractable witness encryption in our unclonable decryption construction. As potential evidence in support of the conjecture, we prove a weaker version of this monogamy property, which we believe will still be of independent interest.
* Finally, we give the first construction of a copy-protection scheme for pseudorandom functions (PRFs) in the plain model. Our scheme is secure either assuming iO and extractable witness encryption, or iO, LWE and the conjectured monogamy property mentioned above. This is the first example of a copy-protection scheme with provable security in the plain model for a class of functions that is not evasive.
2021
ASIACRYPT
Adaptive Security via Deletion in Attribute-Based Encryption: Solutions from Search Assumptions in Bilinear Groups
📺
Abstract
One of the primary research challenges in Attribute-Based 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 Diffie-Hellman 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
Diffie-Hellman assumption.
We first provide a framework for
proving adaptive security in Attribute-Based Encryption systems. We
introduce a concept of ABE with deletable attributes where any party
can take a ciphertext encrypted under the attribute string x in {0,
1}^n and modify it into a ciphertext encrypted under any string x'
in {0, 1, bot}^n where x' is derived by replacing any bits of
x with bot symbols (i.e. ``deleting" attributes of x). The
semantics of the system are that any private key for a circuit C can
be used to decrypt a ciphertext associated with x' if none of the
input bits read by circuit C are bot symbols and C(x') = 1.
We show a pathway for combining ABE
with deletable attributes with constrained pseudorandom functions to
obtain adaptively secure ABE building upon the recent work of
[Tsabary19]. Our new ABE system will be adaptively
secure and be a ciphertext-policy 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 Attribute-Based Encryption schemes support deletion
of attributes. For example, we show that both the [GPSW06] and [Boyen13] 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 Diffie-Hellman 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.
Coauthors
- Scott Aaronson (1)
- Andrea Coladangelo (1)
- Rishab Goyal (1)
- Qipeng Liu (2)
- Brent Waters (1)
- Mark Zhandry (2)
- Ruizhe Zhang (1)