Paper 2020/1194

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

Andrea Coladangelo, Christian Majenz, and Alexander Poremba

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
quantum cryptographycopy-protection
Contact author(s)
andrea coladangelo @ gmail com
christian majenz @ cwi nl
aporemba @ caltech edu
History
2020-10-06: received
Short URL
https://ia.cr/2020/1194
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1194,
      author = {Andrea Coladangelo and Christian Majenz and Alexander Poremba},
      title = {Quantum copy-protection of compute-and-compare programs in the quantum random oracle model},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1194},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1194}},
      url = {https://eprint.iacr.org/2020/1194}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.