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 license 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 (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} 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 (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 (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 \delta} -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 security} if no polynomially bounded quantum adversary can efficiently copy a protected program, more formally if no such adversary can win the following game:

• 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 (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 \psi_A} and 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 \psi_B} to two of her agents, respectively Alice and Bob
• The Challenger samples two inputs 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_A, x_B} for the circuit and sends 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_A} to Alice and 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_B} to Bob.
• Alice sends 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 y_A} to the Challenger and Bob sends 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 y_B} to the Challenger.
• The Adversary wins iff 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(x_A) = y_A} and 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(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.