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

• How to Copy-Protect Malleable-Puncturable Cryptographic Functionalities Under Arbitrary Challenge Distributions [11.781645368622517]
  A quantum copy-protection scheme encodes a functionality into a quantum state.<n>We show how to copy-protect even a larger class of schemes.
  arXiv  Detail & Related papers  (2025-07-25T07:40:44Z)
• (Quantum) Indifferentiability and Pre-Computation [50.06591179629447]
  Indifferentiability is a cryptographic paradigm for analyzing the security of ideal objects. Despite its strength, indifferentiability is not known to offer security against pre-processing attacks. We propose a strengthening of indifferentiability which is not only composable but also takes arbitrary pre-computation into account.
  arXiv  Detail & Related papers  (2024-10-22T00:41:47Z)
• Revocable Encryption, Programs, and More: The Case of Multi-Copy Security [48.53070281993869]
  We show the feasibility of revocable primitives, such as revocable encryption and revocable programs. This suggests that the stronger notion of multi-copy security is within reach in unclonable cryptography.
  arXiv  Detail & Related papers  (2024-10-17T02:37:40Z)
• 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)
• 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)
• A Note on Copy-Protection from Random Oracles [7.129830575525267]
  Quantum copy-protection uses the no-cloning principle of quantum mechanics to protect software from being illegally distributed. Since copy-protection is shown to be impossible to achieve in the plain model, we investigate the question of constructing copy-protection for arbitrary classes of unlearnable functions.
  arXiv  Detail & Related papers  (2022-08-26T22:40:07Z)
• 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 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)
• Quantum-secure message authentication via blind-unforgeability [74.7729810207187]
  We propose a natural definition of unforgeability against quantum adversaries called blind unforgeability. This notion defines a function to be predictable if there exists an adversary who can use "partially blinded" access to predict values. We show the suitability of blind unforgeability for supporting canonical constructions and reductions.
  arXiv  Detail & Related papers  (2018-03-10T05:31:38Z)

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.