59 research outputs found
Quantum Proofs of Deletion for Learning with Errors
No full textQuantum information has the property that measurement is an inherently
destructive process. This feature is most apparent in the principle of
complementarity, which states that mutually incompatible observables cannot be
measured at the same time. Recent work by Broadbent and Islam (TCC 2020) builds
on this aspect of quantum mechanics to realize a cryptographic notion called
certified deletion. While this remarkable notion enables a classical verifier
to be convinced that a (private-key) quantum ciphertext has been deleted by an
untrusted party, it offers no additional layer of functionality.
In this work, we augment the proof-of-deletion paradigm with fully
homomorphic encryption (FHE). We construct the first fully homomorphic
encryption scheme with certified deletion -- an interactive protocol which
enables an untrusted quantum server to compute on encrypted data and, if
requested, to simultaneously prove data deletion to a client. Our scheme has
the desirable property that verification of a deletion certificate is public;
meaning anyone can verify that deletion has taken place. Our main technical
ingredient is an interactive protocol by which a quantum prover can convince a
classical verifier that a sample from the Learning with Errors (LWE)
distribution in the form of a quantum state was deleted. As an application of
our protocol, we construct a Dual-Regev public-key encryption scheme with
certified deletion, which we then extend towards a (leveled) FHE scheme of the
same type. We introduce the notion of Gaussian-collapsing hash functions -- a
special case of collapsing hash functions defined by Unruh (Eurocrypt 2016) --
and we prove the security of our schemes under the assumption that the Ajtai
hash function satisfies a certain strong Gaussian-collapsing property in the
presence of leakage.Comment: Improved construction and new security conjecture. 61 page
Revocable Quantum Digital Signatures
No full textWe study digital signatures with revocation capabilities and show two results. First, we define and construct digital signatures with revocable signing keys from the LWE assumption. In this primitive, the signing key is a quantum state which enables a user to sign many messages and yet, the quantum key is also revocable, i.e., it can be collapsed into a classical certificate which can later be verified. Once the key is successfully revoked, we require that the initial recipient of the key loses the ability to sign. We construct digital signatures with revocable signing keys from a newly introduced primitive which we call two-tier one-shot signatures, which may be of independent interest. This is a variant of one-shot signatures, where the verification of a signature for the message "0" is done publicly, whereas the verification for the message "1" is done in private. We give a construction of two-tier one-shot signatures from the LWE assumption. As a complementary result, we also construct digital signatures with quantum revocation from group actions, where the quantum signing key is simply "returned" and then verified as part of revocation.
Second, we define and construct digital signatures with revocable signatures from OWFs. In this primitive, the signer can produce quantum signatures which can later be revoked. Here, the security property requires that, once revocation is successful, the initial recipient of the signature loses the ability to find accepting inputs to the signature verification algorithm. We construct this primitive using a newly introduced two-tier variant of tokenized signatures. For the construction, we show a new lemma which we call the adaptive hardcore bit property for OWFs, which may enable further applications
Quantum cryptography with classical communication: parallel remote state preparation for copy-protection, verification, and more
No full textQuantum mechanical effects have enabled the construction of cryptographic
primitives that are impossible classically. For example, quantum
copy-protection allows for a program to be encoded in a quantum state in such a
way that the program can be evaluated, but not copied. Many of these
cryptographic primitives are two-party protocols, where one party, Bob, has
full quantum computational capabilities, and the other party, Alice, is only
required to send random BB84 states to Bob. In this work, we show how such
protocols can generically be converted to ones where Alice is fully classical,
assuming that Bob cannot efficiently solve the LWE problem. In particular, this
means that all communication between (classical) Alice and (quantum) Bob is
classical, yet they can still make use of cryptographic primitives that would
be impossible if both parties were classical. We apply this conversion
procedure to obtain quantum cryptographic protocols with classical
communication for unclonable encryption, copy-protection, computing on
encrypted data, and verifiable blind delegated computation. The key technical
ingredient for our result is a protocol for classically-instructed parallel
remote state preparation of BB84 states. This is a multi-round protocol between
(classical) Alice and (quantum polynomial-time) Bob that allows Alice to
certify that Bob must have prepared uniformly random BB84 states (up to a
change of basis on his space). Furthermore, Alice knows which specific BB84
states Bob has prepared, while Bob himself does not. Hence, the situation at
the end of this protocol is (almost) equivalent to one where Alice sent
random BB84 states to Bob. This allows us to replace the step of preparing and
sending BB84 states in existing protocols by our remote-state preparation
protocol in a generic and modular way.Comment: 80 pages, 7 protocol
Weakening Assumptions for Publicly-Verifiable Deletion
No full textWe develop a simple compiler that generically adds publicly-verifiable
deletion to a variety of cryptosystems. Our compiler only makes use of one-way
functions (or one-way state generators, if we allow the public verification key
to be quantum). Previously, similar compilers either relied on the use of
indistinguishability obfuscation (Bartusek et. al., ePrint:2023/265) or
almost-regular one-way functions (Bartusek, Khurana and Poremba,
arXiv:2303.08676).Comment: 11 page
Weakening Assumptions for Publicly-Verifiable Deletion
No full textWe develop a simple compiler that generically adds publicly-verifiable deletion to a variety of cryptosystems. Our compiler only makes use of one-way functions (or one-way state generators, if we allow the public verification key to be quantum). Previously, similar compilers either relied on the use of indistinguishability obfuscation (Bartusek et. al., ePrint:2023/265) or almost-regular one-way functions (Bartusek, Khurana and Poremba, arXiv:2303.08676)
Publicly-Verifiable Deletion via Target-Collapsing Functions
No full textWe build quantum cryptosystems that support publicly-verifiable deletion from
standard cryptographic assumptions. We introduce target-collapsing as a
weakening of collapsing for hash functions, analogous to how second preimage
resistance weakens collision resistance; that is, target-collapsing requires
indistinguishability between superpositions and mixtures of preimages of an
honestly sampled image.
We show that target-collapsing hashes enable publicly-verifiable deletion
(PVD), proving conjectures from [Poremba, ITCS'23] and demonstrating that the
Dual-Regev encryption (and corresponding fully homomorphic encryption) schemes
support PVD under the LWE assumption. We further build on this framework to
obtain a variety of primitives supporting publicly-verifiable deletion from
weak cryptographic assumptions, including:
- Commitments with PVD assuming the existence of injective one-way functions,
or more generally, almost-regular one-way functions. Along the way, we
demonstrate that (variants of) target-collapsing hashes can be built from
almost-regular one-way functions.
- Public-key encryption with PVD assuming trapdoored variants of injective
(or almost-regular) one-way functions. We also demonstrate that the encryption
scheme of [Hhan, Morimae, and Yamakawa, Eurocrypt'23] based on pseudorandom
group actions has PVD.
- with PVD for attribute-based encryption, quantum
fully-homomorphic encryption, witness encryption, time-revocable
encryption, assuming and trapdoored variants of injective (or
almost-regular) one-way functions.Comment: 52 page
Publicly-Verifiable Deletion via Target-Collapsing Functions
No full textWe build quantum cryptosystems that support publicly-verifiable deletion from standard cryptographic assumptions. We introduce target-collapsing as a weakening of collapsing for hash functions, analogous to how second preimage resistance weakens collision resistance; that is, target-collapsing requires indistinguishability between superpositions and mixtures of preimages of an honestly sampled image.
We show that target-collapsing hashes enable publicly-verifiable deletion (PVD), proving conjectures from [Poremba, ITCS\u2723] and demonstrating that the Dual-Regev encryption (and corresponding fully homomorphic encryption) schemes support PVD under the LWE assumption. We further build on this framework to obtain a variety of primitives supporting publicly-verifiable deletion from weak cryptographic assumptions, including:
- Commitments with PVD assuming the existence of injective one-way functions, or more generally, almost-regular one-way functions. Along the way, we demonstrate that (variants of) target-collapsing hashes can be built from almost-regular one-way functions.
- Public-key encryption with PVD assuming trapdoored variants of injective (or almost-regular) one-way functions. We also demonstrate that the encryption scheme of [Hhan, Morimae, and Yamakawa, Eurocrypt\u2723] based on pseudorandom group actions has PVD.
- with PVD for attribute-based encryption, quantum fully-homomorphic encryption, witness encryption, time-revocable encryption, assuming and trapdoored variants of injective (or almost-regular) one-way functions
On non-adaptive quantum chosen-ciphertext attacks and Learning with Errors
No full textLarge-scale quantum computing is a significant threat to classical public-key cryptography. In strong “quantum access” security models, numerous symmetric-key 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 non-adaptive (i.e., pre-challenge) 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 random-access codes, we show that the standard PRF- and PRP-based encryption schemes are QCCA1-secure when instantiated with quantum-secure primitives.We then revisit standard IND-CPA-secure 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 (large-modulus version of) the well-known Bernstein-Vazirani algorithm. We emphasize that our results should not be interpreted as a weakness of these cryptosystems in their stated security setting (i.e., postquantum chosen-plaintext secrecy). Rather, our results mean that, if these cryptosystems are exposed to chosen-ciphertext attacks (e.g., as a result of deployment in an inappropriate realworld setting) then quantum attacks are even more devastating than classical ones.</p
- …
