Unclonable Cryptography with Unbounded Collusions
- URL: http://arxiv.org/abs/2311.18318v1
- Date: Thu, 30 Nov 2023 07:36:42 GMT
- Title: Unclonable Cryptography with Unbounded Collusions
- Authors: Alper Çakan, Vipul Goyal,
- Abstract summary: Quantum no-cloning theorem gives rise to the intriguing possibility of quantum copy protection.
We encode a program in a quantum state such that a user in possession of k such states cannot create k + 1 working copies.
We construct public-key encryption and functional encryption schemes whose secret keys are copy-protected against unbounded collusions.
- Score: 11.781645368622517
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum no-cloning theorem gives rise to the intriguing possibility of quantum copy protection where we encode a program in a quantum state such that a user in possession of k such states cannot create k + 1 working copies. Introduced by Aaronson (CCC 09) over a decade ago, copy protection has proven to be notoriously hard to achieve. In this work, we construct public-key encryption and functional encryption schemes whose secret keys are copy-protected against unbounded collusions in the plain model (i.e. without any idealized oracles), assuming (post-quantum) subexponentially secure iO, one-way functions and LWE. This resolves a long-standing open question of constructing fully collusion-resistant copy-protected functionalities raised by multiple previous works. Prior to our work, copy-protected functionalities were known only in restricted collusion models where either an a-priori bound on the collusion size was needed, in the plain model with the same assumptions as ours (Liu, Liu, Qian, Zhandry [TCC 22]), or adversary was only prevented from doubling their number of working programs, in a structured quantum oracle model (Aaronson [CCC 09]). We obtain our results through a novel technique which uses identity-based encryption to construct unbounded collusion resistant copy-protection schemes from 1-to-2 secure schemes. This is analogous to the technique of using digital signatures to construct full-fledged quantum money from single banknote schemes1 (Lutomirski et al. [ICS 09], Farhi et al. [ITCS 12], Aaronson and Christiano [STOC 12]). We believe our technique is of independent interest. Along the way, we also construct a puncturable functional encryption scheme whose master secret key can be punctured at all functions f such that f (m0) != f (m1). This might also be of independent interest.
Related papers
- A Modular Approach to Unclonable Cryptography [4.336971448707467]
We propose unclonable puncturable obfuscation (UPO) and study its implications for unclonable cryptography.
We present modular (and arguably, simple) constructions of many primitives in unclonable cryptography.
We show that any cryptographic functionality can be copy-protected as long as this functionality satisfies a notion of security.
arXiv Detail & Related papers (2023-11-20T16:22:52Z) - How to Use Quantum Indistinguishability Obfuscation [1.6298172960110866]
We show how to achieve "best-possible" copy protection for all programs.
We show that applying qsiO to a program immediately achieves best-possible copy protection.
We also show that, assuming injective one-way functions exist, qsiO is concrete copy protection for a large family of puncturable programs.
arXiv Detail & Related papers (2023-11-13T23:07:25Z) - Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
We show that targetcollapsing enables publiclyverifiable deletion (PVD)
We build on this framework to obtain a variety of primitives supporting publiclyverifiable deletion from weak cryptographic assumptions.
arXiv Detail & Related papers (2023-03-15T15:00:20Z) - Revocable Cryptography from Learning with Errors [61.470151825577034]
We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities.
We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
arXiv Detail & Related papers (2023-02-28T18:58:11Z) - Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
We construct the first fully homomorphic encryption scheme with certified deletion.
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 distribution in the form of a quantum state was deleted.
arXiv Detail & Related papers (2022-03-03T10:07:32Z) - Hidden Cosets and Applications to Unclonable Cryptography [15.248351992500078]
We study a generalization of hidden subspace states to hidden coset states (first introduced by Aaronson and Christiano [STOC '12]).
We explore unclonable properties of coset states and several applications.
arXiv Detail & Related papers (2021-07-12T19:04:01Z) - Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's
Post-Quantum Security [67.06003361150228]
A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task.
In this work, we examine the hardness of finding such chain of PoWs against quantum strategies.
We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity.
arXiv Detail & Related papers (2020-12-30T18:03:56Z) - Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel.
We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries.
We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
arXiv Detail & Related papers (2020-10-15T17:55:31Z) - Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs"
We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM)
As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
arXiv Detail & Related papers (2020-09-29T08:41:53Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.