Quantum copy-protection of compute-and-compare programs in the quantum random oracle model

Abstract

Copy-protection allows a software distributor to encode a program in such a way that it can be evaluated on any input, yet it cannot be "pirated" - a notion that is impossible to achieve in a classical setting. Aaronson (CCC 2009) initiated the formal study of quantum copy-protection schemes, and speculated that quantum cryptography could offer a solution to the problem thanks to the quantum no-cloning theorem. In this work, we introduce a quantum copy-protection scheme for a large class of evasive functions known as "compute-and-compare programs" - a more expressive generalization of point functions. A compute-and-compare program $\mathsf{CC}[f,y]$ is specified by a function $f$ and a string $y$ within its range: on input $x$, $\mathsf{CC}[f,y]$ outputs $1$, if $f(x)=y$, and $0$ otherwise. We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM), which makes it the first copy-protection scheme to enjoy any level of provable security in a standard cryptographic model. As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing", introduced very recently by Ananth and La Placa (eprint 2020), with a standard security bound in the QROM, i.e. guaranteeing negligible adversarial advantage. Finally, as a third contribution, we elucidate the relationship between unclonable encryption and copy-protection for multi-bit output point functions.

70 pages. Published in Quantum

References in corpus (13)

• Strengths and Weaknesses of Quantum Computing
• The operational meaning of min- and max-entropy
• Coding Theorem and Strong Converse for Quantum Channels
• Random Oracles in a Quantum World
• Quantum Copy-Protection and Quantum Money
• A Monogamy-of-Entanglement Game With Applications to Device-Independent Quantum Cryptography
• Limitations of Quantum Advice and One-Way Communication
• Quantum-secure message authentication via blind-unforgeability
• Uncloneable Quantum Encryption via Oracles
• Secure Software Leasing
• Quantum Lazy Sampling and Game-Playing Proofs for Quantum Indifferentiability
• Limitations on Uncloneable Encryption and Simultaneous One-Way-to-Hiding
• Unclonable Cryptography with Unbounded Collusions and Impossibility of Hyperefficient Shadow Tomography

Cited by in corpus (8)

• Device-independent uncloneable encryption
• Secure Software Leasing Without Assumptions
• A General Quantum Duality for Representations of Groups with Applications to Quantum Money, Lightning, and Fire
• Uncloneable Quantum Advice
• Uncloneable Encryption from Decoupling
• Tight adaptive reprogramming in the QROM
• New Approaches for Quantum Copy-Protection
• Almost Public Quantum Coins