Editing Copy Protection of Compute and Compare Programs

<!-- This is a comment. You can erase them or write below -->
<!-- Intro: brief description of the protocol -->
The [https://arxiv.org/abs/2009.13865 example protocol] achieves the functionality of [[Copy Protection| 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.<br/><br/>
<!--Tags: related pages or category -->
'''Tags:''' [[:Category:Two Party Protocols|Two Party Protocols]], [[:Category:Quantum Functionality|Quantum Functionality]], [[:Category:Universal Task|Universal Task]], Computational Security

==Assumptions==
<!-- It describes the setting in which the protocol will be successful. -->
* 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==
<!-- A non-mathematical detailed outline which provides a rough idea of the concerned protocol -->
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==
<!--  Connects the non-mathematical outline with further sections. -->
* <math>P_y</math> : The point function to be copy-protected in [[#Protocol 1 - Copy protection of point functions|Protocol 1]]. <math>P_y</math> is completely specified by a string of <math>n</math> bits, <math>y</math>. <math>P_y(x) = 1</math> if <math>x = y</math> and <math>0</math> otherwise
* <math>CC[f,y]</math> : The compute-and-compare program to be copy-protected in [[#Protocol 2 - Copy protection of compute-and-compare programs|Protocol 2]]. It is completely specified by an efficiently computable function <math>f: \{0,1\}^n \rightarrow \{0,1\}^m</math> and a string of <math>m</math> bits, <math>y</math>. <math>CC[f,y](x)</math> is <math>1</math> if <math>f(x) = y</math> and <math>0</math> otherwise.
* <math>n</math> : Size of input string <math>x</math>
* <math>\lambda</math>: Security parameter
* <math>G : \{0,1\}^n \rightarrow \{0,1\}^{m(\lambda)} </math> (Hash function)
* <math>H : \{0,1\}^{m(\lambda)} \rightarrow \{0,1\}^\lambda </math> (Hash function)
* <math>|x^\theta\rangle = H^\theta |x\rangle = H^{\theta_1} \otimes ... \otimes H^{\theta_\lambda} |x\rangle</math>, where <math>\theta</math> is a <math>\lambda</math>-bit string <math>\theta_1,...,\theta_\lambda</math>

<!--==Knowledge Graph== -->
<!-- Add this part if the protocol is already in the graph -->
<!--{{graph}}-->
==Protocol Description==
<!-- Mathematical step-wise protocol algorithm helpful to write a subroutine. -->
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(<math>\lambda,y</math>)====
''Inputs'': <math>\lambda</math> - security parameter; <math>y</math> - description of point function <math>P_y</math>
* Set <math>\theta = G(y)</math>
* Sample <math>v \leftarrow \{0,1\}^{m(\lambda)}</math> uniformly at random
* Let <math>z = H(v)</math>
* Output (<math>|v^\theta\rangle,z</math>)

====PF-Eval(<math>\lambda,(\rho,z),x</math>)====
''Inputs'': <math>\lambda</math> - security parameter; <math>(\rho,z)</math> - Alleged copy-protected program; <math>x</math> - Input on which the program is to be evaluated
* Set <math>\theta^\prime = G(x)</math>
* Apply the Hadamard operator <math>H^{\theta^\prime}</math> to <math>\rho</math>
* Append <math>n+1</math> ancillary qubits to <math>\rho</math>, all in state <math>|0\rangle</math>
* Compute the hash function <math>H</math> onto the first <math>n</math> ancillary qubits with <math>\rho</math> as input
* Coherently measure whether the first <math>n</math> ancilla qubits are in state <math>|z\rangle</math>, recording the result in the last ancilla qubit
* Uncompute the hash function <math>H</math> and undo the Hadamards <math>H^{\theta^\prime}</math>
* Measure the last ancilla qubit to obtain a bit <math>b</math> as output

===Protocol 2 - Copy protection of compute-and-compare programs===
====CC-Protect(<math>\lambda,(f,y)</math>)====
''Inputs'': <math>\lambda</math> - security parameter; <math>(f,y)</math> - description of compute-and-compare program <math>CC[f,y]</math>
* Let <math>\rho = </math> '''PF-Protect'''(<math>\lambda,y</math>)
* Output (<math>f,\rho</math>)

====CC-Eval(<math>\lambda,(f,\rho),x</math>)====
''Inputs'': <math>\lambda</math> - security parameter; <math>(f,\rho)</math> - Alleged copy protected program; <math>x</math> - Input on which the program is to be evaluated
* Compute <math>y^\prime = f(x)</math>
* Let <math>b \leftarrow </math> '''PF-Eval'''(<math>\lambda,\rho,y^\prime</math>). Output <math>b</math>.

==Properties==
<!-- important information on the protocol: parameters (threshold values), security claim, success probability... -->
*Both protocols have 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 <math>H</math>
*The protected programs obtained in both protocols allow polynomially-many evaluations (as we evaluate the copy-protected programs reversibly). 
*[[#Protocol 1 - Copy protection of point functions|Protocol 1]] also satisfies the primitive of Virtual Black Box Obfuscation
*By adding a verification step, [[#Protocol 2 - Copy protection of compute-and-compare programs|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==
<!-- theoretical and experimental papers including requirements, security proof (important), which protocol does it implement, benchmark values... -->
For the security proof and extension of the protocols to other functionalities, refer to the same paper by [http://arxiv.org/abs/2009.13865 Coladangelo et al. (2020)]
<div style='text-align: right;'>''*contributed by Chirag Wadhwa''</div>