How to Copy-Protect Malleable-Puncturable Cryptographic Functionalities Under Arbitrary Challenge Distributions

Alper Çakan, Vipul Goyal · 2025

Read How to Copy-Protect Malleable-Puncturable Cryptographic Functionalities Under Arbitrary Challenge Distributions by Alper Çakan, Vipul Goyal (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-19032.txt.

Introduction

Alper Cakan and Vipul Goyal wrote a cryptography paper in two thousand twenty-five on copy-protecting software with quantum states. Copy protection encodes a program into a quantum state so that no one can split it into two working copies. Recent work secured a class of schemes whose secrets can be punctured at chosen points.

The authors widen that class. Their malleable-puncturable schemes only require that a circuit can be built which answers inputs away from the challenge point without helping with the challenge itself. That looser demand captures many more primitives. They show how to copy-protect the whole class under arbitrary challenge distributions.

Catalog record

CREATORAlper Çakan, Vipul Goyal
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE99 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-19032

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

How to Copy-Protect Malleable-Puncturable Cryptographic Functionalities Under Arbitrary Challenge Distributions Alper Çakan, Vipul Goyal Abstract A quantum copy-protection scheme (Aaronson, CCC’09) encodes a functionality into a quantum state such that given this state, no efficient adversary can create two (possibly entangled) quantum states that are both capable of running the functionality. There has been a recent line of works on constructing provably-secure copy-protection schemes for general classes of schemes in the plain model, and most recently the recent work of Çakan and Goyal (IACR Eprint, 2025) showed how to copy-protect all cryptographically puncturable schemes with pseudorandom puncturing points. In this work, we show how to copy-protect even a larger class of schemes. We define a class of cryptographic schemes called malleable-puncturable schemes where the only requirement is that one can create a circuit that is capable of answering inputs at points that are unrelated to the challenge in the security game but does not help the adversary answer inputs related to the challenge. This is a flexible generalization of puncturable schemes, and can capture a wide range of primitives that was not known how to copy-protect prior to our work. Going further, we show that our scheme is secure against arbitrary high min-entropy challenge distributions whereas previous work has only considered schemes that are punctured at pseudorandom points. 1 Introduction Starting with the seminal work of Wiesner [ Wie83 ] , a long line of research has shown that quantum information can be extremely useful in cryptography. One of the main areas where quantum information helps cryptography is achieving a task that is classically impossible task no matter what cryptographic assumptions are made. This line of applications of quantum information is also called quantum protection . This notion can further be divided into four main categories: copy-protection ( [ Aar09 ] ), secure leasing ( [ AL21 ] ), unbounded/LOCC leakage-resilience ( [ ÇGLZR24 ] ) and intrusion-detection ( [ ÇGLZR24 ] ). A recent line of works ( [ CG24b , AB24 ] ) have focused on constructing quantum copy-protection schemes for general classes of functionalities, culminating in the recent work of Çakan and Goyal ( [ ÇG25 ] ) who showed how to copy-protect in the plain model all cryptographically puncturable schemes with pseudorandom puncturing points. In this work, we further advance the class of functionalities that can be copy-protected: We define a class of cryptographic schemes called malleable-puncturable schemes where the only requirement is that one can create a circuit that is capable of answering inputs at points that are unrelated to the challenge in the security game but does not help the adversary answer inputs related to the challenge. This is an extremely flexible generalization of puncturable schemes, and can capture a wide range of primitives that was not known how to copy-protect prior to our work. Theorem 1 ( Corollary 1 , informal) . For any functionality \mathsf{F} that satisfies malleable-puncturing security ( Definition 4 ), there exists a quantum copy-protection scheme for \mathsf{F} secure against arbitrary high min-entropy challenge distributions; assuming subexponentially secure iO and one-way functions. 2 Preliminaries 2.1 Notation When S is a set, we write x\leftarrow S to mean that x is sampled uniformly at random from S . When \mathcal{D} is a distribution, we write x\leftarrow\mathcal{D} to mean that x is sampled from \mathcal{D} . Finally, we write x\leftarrow\mathcal{B}(\mathsf{R}) or \mathcal{B}(a) to mean that x is set to a sample as output by the quantum or classical randomized algorithm \mathcal{B} run on \mathsf{R} or a . We use similar notation for quantum registers, e.g., \mathsf{R}\leftarrow\mathcal{B}(a) . We write QPT to mean a stateful (unless otherwise specified) quantum polynomial time . We write \mathsf{R} to mean a quantum register, which keeps a quantum state that will evolve when the register is acted on, and it can be entangled with other registers. We write \mathsf{R}\leftarrow\rho to mean that the register \mathsf{R} is initialized with a sample from the quantum distribution (i.e. mixed state) \rho . We refer the reader to [ NC10 ] for a preliminary on quantum information and computation. Unless otherwise specified, all of our cryptographical assumptions are implicitly post-quantum, e.g., one-way functions means post-quantum secure one-way functions . 2.2 Cryptography 2.2.1 Puncturable Pseudorandom Functions In this section, we recall puncturable pseudorandom functions. Definition 1 ( [ SW14 ] ) . A puncturable pseudorandom function (PRF) is a family of functions \{F:\{0,1\}^{c(\lambda)}\times\{0,1\}^{m(\lambda)}\to\{0,1\}^{n(\lambda)}\}_{\lambda\in\mathds{N}^{+}} with the following associated efficient algorithms. • \mathsf{PRF}.\mathsf{Setup}(1^{\lambda}): Takes in the unary representation of the security parameter and outputs a key K in \{0,1\}^{c(\lambda)} . • \mathsf{PRF}.\mathsf{Eval}(K,x): Takes in a key K and an input x , outputs an evaluation of the PRF. • \mathsf{PRF}.\mathsf{Puncture}(K,S): Takes as input a key and a set S\subseteq\{0,1\}^{m(\lambda)} , outputs a punctured key. We require the following. Correctness. For all efficient distributions \mathcal{D}(1^{\lambda}) over the power set 2^{\{0,1\}^{m(\lambda)}} , we require \Pr[\forall x\not\in S~~\mathsf{PRF}.\mathsf{Eval}(K_{S},x)=F(K,x):\begin{array}[]{c}S\leftarrow\mathcal{D}(1^{\lambda})\\ K\leftarrow\mathsf{PRF}.\mathsf{Setup}(1^{\lambda})\\ K_{S}\leftarrow\mathsf{PRF}.\mathsf{Puncture}(K,S)\end{array}]=1. Puncturing Security We require that any stateful QPT adversary \mathcal{A} wins the following game with probability at most 1/2+\mathsf{negl}(\lambda) . 1. \mathcal{A} outputs a set S . 2. The challenger samples K\leftarrow\mathsf{PRF}.\mathsf{Setup}(1^{\lambda}) and K_{S}\leftarrow\mathsf{PRF}.\mathsf{Puncture}(K,S) 3. The challenger samples b\leftarrow\{0,1\} . If b=0 , the challenger submits K_{S},\{F(K,x)\}_{x\in S} to the adversary. Otherwise, it submits K_{S},\{y_{s}\}_{s\in S} to the adversary where y_{s}\leftarrow\{0,1\}^{n(\lambda)} for all s\in S . 4. The adversary outputs a guess b^{\prime} and we say that the adversary has won if b^{\prime}=b . Theorem 2 ( [ SW14 , Zha12 ] ) . Let n(\cdot),m(\cdot),e(\lambda),k(\lambda) be efficiently computable functions. • If (post-quantum) one-way functions exist, then there exists a (post-quantum) puncturable PRF with input space \{0,1\}^{m(\lambda)} and output space \{0,1\}^{n(\lambda)} . • If we assume subexponentially-secure (post-quantum) one-way functions exist, then for any c>0 , there exists a (post-quantum) 2^{-\lambda^{c}} -secure 1 1 1 While the original results are for negligible security against polynomial time adversaries, it is easy to see that they carry over to subexponential security. Further, by scaling the security parameter by a polynomial and simple input/output conversions, subexponentially secure (for any exponent c^{\prime} ) one-way functions is sufficient to construct for any c a puncturable PRF that is 2^{-\lambda^{c}} -secure. puncturable PRF against subexponential time adversaries with input space \{0,1\}^{m(\lambda)} and output space \{0,1\}^{n(\lambda)} . 2.2.2 Indistinguishability Obfuscation In this section, we introduce indistinguishability obfuscation. Definition 2 . An indistinguishability obfuscation scheme i\mathcal{O} for a class of circuits \mathcal{C}=\{\mathcal{C}_{\lambda}\}_{\lambda} satisfies the following. Correctness. For all \lambda,C\in\mathcal{C}_{\lambda} and inputs x , \Pr[\tilde{C}(x)=C(x):\tilde{C}\leftarrow i\mathcal{O}(1^{\lambda},C)]=1 . Security. Let \mathcal{B} be any QPT algorithm that outputs two circuits C_{0},C_{1}\in\mathcal{C} of the same size, along with auxiliary information, such that \Pr[\forall x~C_{0}(x)=C_{1}(x):(C_{0},C_{1},\mathsf{R}_{\mathsf{aux}})\leftarrow\mathcal{B}(1^{\lambda})]\geq 1-\mathsf{negl}(\lambda) . Then, for any QPT adversary \mathcal{A} , \displaystyle\bigg| \displaystyle\Pr[\mathcal{A}(i\mathcal{O}(1^{\lambda},C_{0}),\mathsf{R}_{\mathsf{aux}})=1:(C_{0},C_{1},\mathsf{R}_{\mathsf{aux}})\leftarrow\mathcal{B}(1^{\lambda})]- \displaystyle\Pr[\mathcal{A}(i\mathcal{O}(1^{\lambda},C_{1}),\mathsf{R}_{\mathsf{aux}})=1:(C_{0},C_{1},\mathsf{R}_{\mathsf{aux}})\leftarrow\mathcal{B}(1^{\lambda})]\bigg|\leq\mathsf{negl}(\lambda). 2.3 Quantum Information Lemma 1 (Almost As Good As New Lemma [ Aar16 ] , verbatim) . Let \rho be a mixed state acting on \mathds{C}^{d} . Let U be a unitary and (\Pi_{0},\Pi_{1}=I-\Pi_{0}) be projectors all acting on \mathds{C}^{d}\otimes\mathds{C}^{d^{\prime}} . We interpret (U,\Pi_{0},\Pi_{1}) as a measurement performed by appending an ancillary system of dimension d^{\prime} in the state \outerproduct{0}{0} , applying U and then performing the projective measurement \Pi_{0},\Pi_{1} on the larger system. Assuming that the outcome corresponding to \Pi_{0} has probability 1-\epsilon , we have \norm{\rho - \rho'}_{Tr}\leq\sqrt{\epsilon} where \rho^{\prime}

Read the complete text