Formulations and Constructions of Remote State Preparation with Verifiability, with Applications

In the RSP problem, ideally, the client would like to prepare a quantum state (sampled or chosen from a state family) on the server side; thus in the end the client knows the description of the state, while the server simply holds the state. The trivial solution is to simply send the quantum state through a quantum channel. RSP asks: how could we achieve this task using cheaper resources (for example, only classical communication), possibly under computational assumptions?

Studies of RSP have a long history [32, 8]. One setting of RSP is the fully honest setting [8]. In this work, we are interested in the cryptographic setting where the server could be malicious. Then a formulation of RSP should at least have a correctness requirement and a security requirement.

The natural correctness requirement for RSP says that when the server is honest, the server gets the state while the client gets the state description. For security, there are different security notions, including blindness (or privacy, secrecy) and verifiability (or soundness) [15, 20, 40]. In this paper we focus on RSP with verifiability (RSPV). In RSPV, intuitively, the client is able to verify that in the case of passing (or called acceptance, non-aborting) the server (approximately) really gets the state, as if it is sent through a quantum channel. A malicious server who attempts to get other information by deviating from the protocol would be caught cheating by the client.

As a natural quantum task, the RSPV problem is interesting on its own. What’s more, it has become an important building block in many other quantum cryptographic protocols. For example, [20] first constructs a classical channel cryptography-based RSPV and uses it to achieve classical verification of quantum computations; [19] explores more applications of RSPV; [41] takes the RSPV approach to achieve classical verification of quantum computations with linear total time complexity. Many quantum cryptographic protocols rely on the quantum channel and quantum communication, and an RSPV protocol could serve as a compiler: it allows us to replace these quantum communication steps by other cheaper resources, like the classical communication.

On the one hand, there have been many important and impressive results in this direction; on the other hand, there are also various limitations or subtleties in existing works, including formulations and constructions. Below we discuss existing works in more detail and motivate our results.

We first note that there are many variants of definitions for RSPV. For example, there are two subtlely different types of security notions, the rigidity-based (or isometry-based) soundness [15, 19] and simulation-based soundness [8, 20, 41]. Existing works do not seem to care about the differences; we note that these differences could have impact on the abstract properties of the definitions and could affect their well-behaveness. For example, we would like RSPV to have sequential composability between independent instances: if the client and the server execute an RSPV protocol for a state family ${ℱ}_1$, and then execute an RSPV protocol for a state family ${ℱ}_2$, we would like the overall protocol to be automatically an RSPV for ${ℱ}_1\otimes {ℱ}_2$. If such a sequential composability property holds, protocols for tensor products of states could be reduced to protocols for each simple state family.

In this background, we argue that:

It’s helpful to compare variants of definitions and formalize basic abstract properties.

We would like to have a more well-behaved framework for RSPV, which will lay a solid foundation for concrete constructions.

RSPV talks about the certification of server-side states. A closely related question is: how could the client certify the server-side operations?

To address this problem, existing works raise the notion of self-testing [38, 33, 28]. One famous scenario of self-testing is in non-local games [24, 35]. In this scenario, the verifier sends questions to two spatially-separated but entangled quantum provers (or called servers). The verifier’s questions and passing conditions are specially designed so that the provers have to perform specific operations to pass. This provides a way to constrain the provers’ operations through only classical interactions and spatial separation, which has become a fundamental technique in the study of non-local games.

Recently a series of works [29, 18, 11, 31] study the single-server cryptographic analog of the non-local game self-testing. [29] studies the cryptographic analog of the CHSH game, where the server needs to prepare the Bell states and perform measurements on two of its registers. [30, 18] further extend it to three-qubit and $N$-qubit; [25, 31] make use of QFHE [26] to formulate and address the problem, where the FHE-encrypted part takes the role of one prover and the unencrypted part takes the role of the other prover.

What’s common in these existing works is that they are defining the single-server cryptographic analog of the non-local game self-testing to be a protocol where the single server is playing the roles of both of the two provers. In this work we are interested in another viewpoint, which is:

How could we define a single-server cryptographic analog of the non-local game self-testing, where the single server is playing the role of one of the two provers?

Maybe the most natural question in the direction of RSPV is:

For what state families could we achieve RSPV?

Let’s quickly review what state families have been achieved in existing works. [20] achieves RSPV for $\{|{+}_{\theta }⟩:=\frac{1}{\sqrt{2}}(|0⟩+e^{\mathrm{i}\theta \pi /4}|1⟩),\theta \in \{0,1,2\mathrm{\cdots }7\}\}$; independently [15] gives a candidate RSPV construction for this state family and conjectures its security. [20] achieves RSPV for tensor products of BB84 states: ${\{|0⟩,|1⟩,|+⟩,|-⟩\}}^{\otimes n}$. [41] achieves RSPV for tensor products of $|{+}_{\theta }⟩$ states. [11] achieves RSPV for BB84 states.

For a broader viewpoint let’s also review some famous self-testing protocols. [29] achieves cryptographic self-testing for Bell states and the corresponding X/Z measurements. [30] achieves self-testing for a 3-qubit magic state and the corresponding measurements. [18] achieves self-testing for multiple Bell pairs and measurements. [31] achieves self-testing for “all-X” and “all-Z” operations.

As a summary, one significant limitations of existing works is that they could only handle simple tensor product states and operators. We consider this situation very undesirable since ideally we want a protocol that is sufficiently powerful to cover all the computationally-efficient state families. The lack of concrete protocols also restricts the applications of RSPV as a protocol compiler: suppose that we have a quantum cryptographic protocol that starts with sending states in (for example) $\{\frac{1}{\sqrt{2}}(|0⟩|x_0⟩+|1⟩|x_1⟩),x_0,x_1\in {\{0,1\}}^n\}$, it’s not clear how to use existing RSPV protocols to compile this quantum communication step to the classical communication. (Note that although there are mature techniques for creating this type of states with some other security notions [26, 10, 27], it’s not known how to construct RSPV for it.)

Besides the existency problem, it’s also desirable if we could weaken the assumptions needed or simplify existing results.

We will apply our results on RSPV to the classical verification of quantum computations (CVQC) problem. In this problem a classical client would like to delegate the evaluation of a BQP circuit $C$ to a quantum server, but it does not trust the server; thus it wants to make use of a protocol to verify the results. The first and perhaps the most famous construction is given by Mahadev [27]. Building on Mahadev’s work and related results [26, 10, 27], a series of new CVQC protocols are constructed [3, 20, 14, 41, 31, 5].

However, one undesirable situation is that all the existing constructions are either based on LWE [34], or based on the random oracle heuristic, or based on some new conjecture on the reduction between security notions. In more detail:

• $\mathrm{■}$

  Most existing works [27, 14, 20] make use of NTCF with the “adaptive hardcore bit property” (or some stronger variants). The only known instantiation of this primitive from standard assumption is based on LWE.

• $\mathrm{■}$

  [5] gives an instantiation of NTCF with a weaker variant of the adaptive hardcore bit property using cryptographic group actions. However, to achieve the adaptive hardcore bit property it relies on an unproven conjecture on the reduction between these two notions. Alternatively one could make use of the random oracle to construct CVQC without the adaptive hardcore bit property [12, 41] but the instantiation of the random oracle is heuristic.

• $\mathrm{■}$

  If we only make use of NTCF without the adaptive hardcore bit property, we could do RSPV for BB84 states [11], but BB84 states are not known to be sufficient for constructing CVQC.

• $\mathrm{■}$

  [31] makes use of a quantum FHE-based approach to construct CVQC. However instantiations of quantum FHE rely on (variants of) NTCF and the classical FHE [26, 22], which still rely on the LWE assumption.

As mentioned above, a type of cryptographic assumption that is different from LWE is the cryptographic group actions, for example, supersingular isogeny [4, 13]. In this background, we ask:

Could we construct CVQC from cryptographic group actions?

We first work on the definitions and abstract properties of RSPV.

1. 1.

   We first formulate and review the hierarchy of notions for formalizing RSPV. This includes the notions of registers, cq-states, protocols, paradigms of security definitions, etc.

2. 2.

   We then formalize the notion of RSPV. We formulate the soundness as a simulation-based definition and compare this definition with several other variants (like the rigidity-based soundness, which is also popular).

3. 3.

   We then study the abstract properties of RSPV including the sequential composability and amplification. This allows us to reduce the constructions of RSPV to primitives that are relatively easier to construct.

In summary, we clarify subtleties and build a well-behaved framework for RSPV, which enables us to build larger protocols from smaller or easier-to-construct components. In later part of this work we will build concrete RSPV constructions under this framework.

We then introduce a new notion called remote operator application with verifiability (ROAV), as our answer to the question in Section 1.2.2.

Let’s first review how the self-testing-based protocols typically work in the non-local game setting. Suppose the verifier would like to make use of the prover 1 and prover 2 to achieve some tasks – - for example, testing the ground state energy of a local Hamiltonian. One typical technique is to design two subprotocols ${\pi }_{\text{test}}$ and ${\pi }_{\text{comp}}$. Subprotocol ${\pi }_{\text{test}}$ is a non-local game with a self-testing property, while subprotocol ${\pi }_{\text{comp}}$ is to test the Hamiltonian. Furthermore, the games are designed specially so that the prover 2, without communicating with the prover 1, could not decide which subprotocol the verifier is currently performing. Then the setting, the overall protocol and the security proof roughly go as follows:

• $\mathrm{■}$

  (Setting) The prover 1 and prover 2 initially hold EPR states. They receive questions from the verifier, make the corresponding measurements and send back the results.

• $\mathrm{■}$

  (Overall protocol) The verifier randomly chooses to execute either ${\pi }_{\text{test}}$ or ${\pi }_{\text{comp}}$ (without telling the provers the choices).

• $\mathrm{■}$

  (Security proof)

  1. 1.

     To pass the overall protocol the provers have to pass ${\pi }_{\text{test}}$ with high probability. By the property of ${\pi }_{\text{test}}$ the operations of the prover 2 has to be close to the honest behavior.

  2. 2.

     By the design of ${\pi }_{\text{test}}$ and ${\pi }_{\text{comp}}$, and the fact that the prover 2 is close to the honest behavior in ${\pi }_{\text{test}}$, we could argue that the prover 2 is also close to the honest behavior in ${\pi }_{\text{comp}}$.

  3. 3.

     Since we already know the prover 2 is close to be honest in ${\pi }_{\text{comp}}$, it’s typically easy to analyze the execution of ${\pi }_{\text{comp}}$ directly and show that it achieves the task.

Recall that we would like to define a single-server cryptographic analog of the non-local game self-testing where the single server plays the role of one of the two provers. So what does the “non-local game self-testing” mean here? Our idea is to consider both the step 1 and step 2 in the security proof template above as the “non-local game self-testing”. Then let’s focus on the prover 2 (as “one of the two provers” in our question) and assume the prover 1 is honest. Then we could do the following simplifications in the non-local game self-testing:

• $\mathrm{■}$

  In ${\pi }_{\text{test}}$ we could assume the prover 1 first measures its states following the verifier’s question; as a result, the joint state of the prover 1 and prover 2 becomes a cq-state where the verifer knows its description. Then the verifier also gets the measurement results from the prover 1’s answer; so in the end we only need to consider the joint cq-state between the verifier and the prover 2.

• $\mathrm{■}$

  For ${\pi }_{\text{comp}}$, since we do not consider the step 3 above as a part of the self-testing notion, the question to the prover 1 in ${\pi }_{\text{comp}}$ could be left undetermined. Then ${\pi }_{\text{comp}}$ is not designed for any specific task any more, which in turn makes the self-testing a general notion.

Now the setting and the first two steps in the security proof could be updated as follows:

• $\mathrm{■}$

  (Setting) In ${\pi }_{\text{test}}$ the client and the prover 2 initially hold a cq-state, where the verifier holds the classical part and the prover 2 holds the quantum part. In ${\pi }_{\text{comp}}$ the prover 1 and prover 2 hold EPR states and the verifier does not have access to the prover 1’s information.

• $\mathrm{■}$

  (Security proof) To make the first two steps in the security proof template above go through, we should at least require that:

  “The prover could pass in ${\pi }_{\text{test}}$” should imply that the prover’s operation in ${\pi }_{\text{comp}}$ is close to the desired one.

This gives us the basic intuition for formalizing our single-server cryptographic analog of the non-local game self-testing. Below we introduce the notion, which we call reomte operator application with verifiability (ROAV).

An ROAV for a POVM $({ℰ}_1,{ℰ}_2,\mathrm{\cdots },{ℰ}_D)$ is defined as a tuple $({\rho }_{\text{test}},{\pi }_{\text{test}},{\pi }_{\text{comp}})$ where:

• $\mathrm{■}$

  The setting contains the following registers. $𝑫$ is a client-side classical register, $𝑸$ is a server-side quantum register, $𝑷$ is a quantum register in the environment with the same dimension with $𝑸$.

• $\mathrm{■}$

  ${\rho }_{\text{test}}$ is a cq-state on registers $𝑫$ and $𝑸$.

• $\mathrm{■}$

  ${\pi }_{\text{test}}$ is the protocol for the test mode. In the test mode ${\rho }_{\text{test}}$ is used as the input state and $𝑷$ is empty.

• $\mathrm{■}$

  ${\pi }_{\text{comp}}$ is the protocol for the computation mode (where the operations are applied). Denote the state of maximal entanglement (multiple EPR pairs) between $𝑷$ and $𝑸$ as $\mathrm{\Phi }$. In the comp mode $\mathrm{\Phi }$ is used as the input state and $𝑫$ is empty. Note that the execution of ${\pi }_{\text{comp}}$ does not touch $𝑷$.

The soundness of ROAV is defined roughly as follows: for any adversary $\mathrm{𝖠𝖽𝗏}$, at least one of the following is true:

• $\mathrm{■}$

  In the test mode (${\pi }_{test}$ is executed with input state ${\rho }_{\text{test}}$ against adversary $\mathrm{𝖠𝖽𝗏}$), the adversary gets caught cheating with significant probability;

• $\mathrm{■}$

  In the comp mode (${\pi }_{\text{comp}}$ is executed with input state $\mathrm{\Phi }$ against adversary $\mathrm{𝖠𝖽𝗏}$), the final state gives the outcome of the following operations:

  The measurement described by $({ℰ}_1,{ℰ}_2,\mathrm{\cdots },{ℰ}_D)$ is applied on $𝑸$, and the client gets the measurement result $i\in [D]$; the corresponding output state (on register $𝑷$ and $𝑸$) is $(𝕀\otimes {ℰ}_i)(\mathrm{\Phi })$.

We finally note that the definition of ROAV also use the simulation-based security definition paradigm, like RSPV.

Now we introduce a series of new RSPV constructions. Our results not only give arguably simplified constructions for existing results but also cover new state families.

Now we apply our results to the classical verification of quantum computations (CVQC) problem.

As the preparation, we give a more detailed review on the variants of NTCF, and their relations to RSPV. We refer to Section 1.2.4 for a CVQC-centric background.