Copy Protection

Functionality Description

Copy Protection is a functionality first defined by Aaronson [1] that enables a Vendor to send a program (a circuit) to a Client so that the Client cannot duplicate it.

Classically, this functionality has been proven impossible. However, it is possible to copy protect some families of programs using quantum computation.

Tags: Quantum Functionality, Two Party Protocols, Universal Task, Computational Security

Use-cases

• Any kind of software licence protection

Protocols

Currently, protocols for Copy Protection are only known for a few families of circuits.

• Quantum Copy Protection for Compute and Compare functions [3] [4]
• Quantum Copy Protection for Pseudo Random Number Generators [5]

Properties

A Copy Protection protocol for a family of circuits is made of two algorithms:

• Protect, which takes as input a classical description of a circuit Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\textstyle C} and outputs a quantum encoding Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \rho_C} of this circuit.
• Eval, which takes as input a quantum state and an classical input, and returns a classical output.

A Copy Protection scheme for a family of circuits has Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \varepsilon} -Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle correctness} if for any circuit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle C} of this family and for any input Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle x} for this circuit, Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle Pr[\mathbf {Eval} (\rho _{C},x)=f(x);\ \rho _{C}\gets \mathbf {Protect} (C)]\geq 1-\varepsilon }

A Copy Protection scheme for a family of circuits has Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\textstyle \delta } -${\textstyle security}$ if no polynomially bounded quantum adversary can efficiently copy a protected program, more formally if for any such adversary, her probability of winning the following game is lower than Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\textstyle 1-\delta } :

• A Challenger samples a circuit C in the family and sends Protect(C) to the Adversary
• The Adversary runs any polynomial computation she wants on Protect(C) and sends two quantum states, respectively Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\textstyle \psi _{A}} and Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\textstyle \psi _{B}} to two of her agents, respectively Alice and Bob
• The Challenger samples two inputs Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\textstyle x_{A},x_{B}} for the circuit and sends Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\textstyle x_{A}} to Alice and Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\textstyle x_{B}} to Bob.
• Alice sends Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\textstyle y_{A}} to the Challenger and Bob sends Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\textstyle y_{B}} to the Challenger.
• The Adversary wins iff Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\textstyle C(x_{A})=y_{A}} and ${\textstyle C(x_{B})=y_{B}}$

We assume that Alice and Bob cannot communicate with each other.

Further Information

Even with quantum computation, Copy Protection is not possible for all families of circuits. Currently, it has been proven impossible for all learnable functions and de-quantumizable functions [2] .

References

1. Aaronson (2009) proposed a fist definition of Quantum Copy Protection.
2. Ananth, Prabhanjan, and La Placa (2020) constructed a family of unlearnable circuits that cannot be copy protected.
3. Coladangelo et al. (2020) proposed a copy protection construction for Compute and Compare functions in the QROM.
4. Broadbent et al. (2021) proposed a copy protection construction for Compute and Compare functions without assumptions but with a weaker adversary model.
5. Coladangelo et al. (2021) proposed a copy protection construction for PRNGs based on coset states.