Copy Protection of Compute and Compare Programs

The example protocol achieves the functionality of Copy Protection allowing a Vendor to send a program to a Client such that the Client cannot duplicate it. This protocol, in particular, achieves copy-protection for 'compute-and-compare' programs.

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

Assumptions

• Vendor and Client are connected by quantum and classical channels
• Vendor can create and transmit BB84 states
• Client has the capability to perform universal quantum computation

Outline

Any Copy Protection protocol consists of two algorithms: Protect and Eval. For the family of compute-and-compare programs, these algorithms are described as follows:

• Protect: The Vendor encodes the required qubits into BB84 states using the program description. The Vendor then calculates the output of some hash function on the program description as input. The encoded qubits and the hashed description are sent to the Client as output.
• Eval: The Client decrypts the received qubits using the input on which they wish to evaluate the program. Using these qubits as inputs, the Client computes the same hash function (on ancillary qubits) and coherently compares it with the hashed description received from the vendor. The Client finally measures and outputs the result of the comparison.

Notation

• 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 P_y}  : The point function to be copy-protected in Protocol 1. 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 P_y} is completely specified by a string of 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 n} bits, $y$. $P_{y}(x)=1$ if 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 x = y} 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/":): {\displaystyle 0} otherwise
• 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 CC[f,y]}  : The compute-and-compare program to be copy-protected in Protocol 2. It is completely specified by an efficiently computable function 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 f: \{0,1\}^n \rightarrow \{0,1\}^m} and a string of $m$ bits, 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 y} . $CC[f,y](x)$ is $1$ if $f(x)=y$ and $0$ otherwise.
• $n$ : Size of input string $x$
• $\lambda$: Security parameter
• $G:\{0,1\}^{n}\rightarrow \{0,1\}^{m(\lambda )}$ (Hash function)
• $H:\{0,1\}^{m(\lambda )}\rightarrow \{0,1\}^{\lambda }$ (Hash function)
• $|x^{\theta }\rangle =H^{\theta }|x\rangle =H^{\theta _{1}}\otimes ...\otimes H^{\theta _{\lambda }}|x\rangle$, where $\theta$ is a $\lambda$-bit string $\theta _{1},...,\theta _{\lambda }$

Protocol Description

First, we define a protocol for copy-protection of point functions. This protocol can then be extended to a protocol for compute-and-compare programs.

Protocol 1 - Copy protection of point functions

PF-Protect($\lambda ,y$)

Inputs: $\lambda$ - security parameter; $y$ - description of point function $P_{y}$

• Set $\theta =G(y)$
• Sample 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 v \leftarrow \{0,1\}^{m(\lambda)}} uniformly at random
• Let 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 z = H(v)}
• Output (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 |v^\theta\rangle,z} )

PF-Eval(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 \lambda,(\rho,z),x} )

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/":): {\displaystyle \lambda} - security parameter; 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 (\rho,z)} - Alleged copy-protected program; 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 x} - Input on which the program is to be evaluated

• Set 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 \theta^\prime = G(x)}
• Apply the Hadamard operator 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 H^{\theta^\prime}} to 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 \rho}
• Append 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 n+1} ancillary qubits to 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 \rho} , all in state 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 |0\rangle}
• Compute the hash function 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 H} onto the first 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 n} ancillary qubits with 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 \rho} as input
• Coherently measure whether the first 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 n} ancilla qubits are in state 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 |z\rangle} , recording the result in the last ancilla qubit
• Uncompute the hash function 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 H} and undo the Hadamards 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 H^{\theta^\prime}}
• Measure the last ancilla qubit to obtain a bit 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 b} as output

Protocol 2 - Copy protection of compute-and-compare programs

CC-Protect(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 \lambda,(f,y)} )

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/":): {\displaystyle \lambda} - security parameter; 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 (f,y)} - description of compute-and-compare program 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 CC[f,y]}

• Let 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 \rho = } PF-Protect(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 \lambda,y} )
• Output (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 f,\rho} )

CC-Eval(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 \lambda,(f,\rho),x} )

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/":): {\displaystyle \lambda} - security parameter; 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 (f,\rho)} - Alleged copy protected program; 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 x} - Input on which the program is to be evaluated

• Compute 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 y^\prime = f(x)}
• Let 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 b \leftarrow } PF-Eval(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 \lambda,\rho,y^\prime} ). Output 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 b} .

Properties

• Protocol 2 has provable non-trivial security in the quantum random oracle model. Informally, a query bounded adversary fails at pirating with at least some constant probability.
• The Client should be able to perform universal quantum computation in order to compute the hash function 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 H}
• The protected programs obtained in both protocols allow polynomially-many evaluations (as we evaluate the copy-protected programs reversibly).
• Protocol 1 also satisfies the primitive of Virtual Black Box Obfuscation
• By adding a verification step, Protocol 2 can be extended to the weaker primitive of Secure Software Leasing. This protocol for Secure Software Leasing does however provide a standard level of security, i.e. the adversarial success probability is negligible in the security parameter.

Further Information

For the security proof and extension of the protocols to other functionalities, refer to the same paper by Coladangelo et al. (2020)

*contributed by Chirag Wadhwa