Pseudo-Secret Random Qubit Generator (PSQRG)

The example protocol enables fully-classical parties to generate secret single qubit states using only public classical channels and a single quantum Server. This functionality could be used to replace a quantum channel completely such that a classical Client can perform various quantum applications over classical network connected to a quantum Server. An application of this functionality could be to carry out Delegated Quantum Computation by just classical online communication (classical communication throughout the protocol) and no quantum communication. It allows a fully classical Client to instructs Server to generate random single qubit states such that Client has complete knowledge of the state of qubit prepared but Server does not. It can be used for UBQC, VUBQC and for other protocols like Quantum Money, Quantum Digital Signatures etc.. which need user to share his/her private quantum key over a quantum channel.

Use Case

• Quantum Task
• No classical Analogue
• Replaces quantum channels by classical channels for quantum cloud computing
• Generating random qubits for protocols like quantum-key-distribution, quantum money, quantum coin-flipping, quantum signatures, two-party quantum computation, multiparty quantum computation etc.

Tags: Two Party,Universal Task, Quantum Functionality, Classical Online Communication, Superposition, Collision Resistant Functions, Learning With Errors

Assumption

• This protocol assumes an honest Client and proves security only for an adversarial Server.
• This protocol takes the assumption of a Quantum Honest But Curious (QHBC) adversary setting i.e. the protocol is secure against an honest Server who just wants to know Client’s hidden data but not modify it without Client’s consent.

Outline

The general idea is that a classical Client gives instructions to a quantum Server to perform certain actions (quantum computation). Those actions lead to the Server having as output a single qubit, which is randomly chosen from within a set of chosen (by the Client) states. On the other hand, Client is supposed to know the classical description of Server's output qubit. To achieve this task, the instructions/quantum computation the Client uses are based on a family of trapdoor, two regular, one-way functions with certain extra properties (see Properties and Definitions). Trapdoor one-way functions are hard to invert (e.g. for the Server) unless someone (the Client in this case) has some extra “trapdoor” information. Two-regular functions have two pre-images for every value in the range of the function. This extra information helps the Client classically reproduce the quantum computation to recover the classical description of the single qubit state, while it is still hard to classically reproduce for the Server, the same information as Client. Simple modifications to the protocol could achieve other similar sets of states.

The protocol can be divided into two stages, Pre-images Superposition, where Client instructs the Server to generate superposition using the function with above properties and, Squeezing, where the Server is instructed by the Client to measure his output qubits and deliver outcomes, which she (Client) would use to classically compute the value of r.

• Preparation. Client randomly selects a function with required properties, which is public (Server knows), but the trapdoor information needed to invert the function is known only to the Client.
• Preimages Superposition. Server prepares two quantum registers (system comprising multiple qubits), first being control (containing inputs) and second being target (containing output of the function). Client instructs Server to create a superposition of input states by applying Hadamard gate (quantum fourier transform) on control register. She then instructs Server to apply a unitary gate (all quantum gates are represented by unitary matrices) which computes output of the function in the target register, taking input from the control register, thus yielding an entangled state from the Server's superposition state. Server is required to measure the target register in the computational basis (along Z axis) and get an outcome. This action would reduce the control register into a superposition of two pre-images corresponding to the measurement outcome of the target register. He conveys this outcome to the Client who computes, classically, the two pre-images using her trapdoor. This pair of pre-image would have some isolated similar qubits (without superposition) and a superposition of dissimilar qubits. The dissimilar qubits can be written as a superposition of isolated 0s and isolated 1s (a GHZ state), with X (NOT) gates applied to qubits depending on the state of qubit in both the pre-images. If the last qubit belongs to the set of similar qubits, then Client aborts and this Stage is repeated.
• Squeezing. Client instructs Server to measure all the qubits of the control register in some basis chosen randomly by the Client, except the last one, and return to her the outcomes. The last unmeasured state contains the randomly prepared qubit hidden from the Server. Client can then compute the value of r by an equation (see Pseudo Code). This equation depends only on Client’s measurement basis angles, Server’s measurement outcome and the location of random X’s (unknown to the Server). Thus, the Client knows the state of her secret qubit prepared by the Server.

Notations

• • $f_{k}$, function for target register
  • $t_{k}$, trapdoor for function $f_{k}$
  • $U_{f_{k}}$, Unitary operated on the target register taking first register as control, used to compute output of the function in the target register
  • y, measurement outcome of the target register
  • $x,x'$, pre-image pair for a given measurement outcome y
  • $x_{i}$ value of qubit i for pre-image x
  • $x_{i}'$ value of qubit i for pre-image x’
  • $\alpha _{i}$, Client’s measurement angles for qubit i in the control register
  • $b_{i}$, Server’s measurement outcome for qubit i in the control register
  • $\theta$, classical description of the hidden input state

Properties

• $f_{k}$, the function with required properties as given below in point 4.
• n, number of qubits in the control register.
• The function used for the protocol is required to satisfy the following properties: one-way, trapdoor, two-regular, collision resistance, quantum-safe (See Definitions).
• This protocol is secure under learning with errors assumption i.e. it relies on assumption over a quantum Server to be unable solve a computationally hard problem.
• The protocol assumes that all quantum operators are described by polynomially-sized circuits.
• The randomness of the output qubit is due to the (fundamental) randomness of quantum measurements that are part of the instructions that the Client gives.
• The Server cannot guess the state any better than if he had just received that state directly from the Client (up to negligible probability).
• Correctness If both the Client and the Server follow the protocol, the protocol aborts when {missing equation}, while otherwise the Server ends up with the output (single) qubit being in the state ), where $\theta$ is given by equation (see Pseudo Code).
• The single qubit state generated by the protocol remains private against a QHBC Server.

Pseudocode

Stage1 Preimages superposition

• Input: Client uniformly samples a set of random three-bits strings α = (α1,··· ,αn−1) where αi ← {0,1}3, and runs the algorithm (k,tk) ← GenF(1n). The α and k are public inputs (known to both parties), while tk is the “private” input of the Client, A public function family F = {fk : {0,1}n → {0,1}m} of trapdoor one-way functions that are quantum safe, two-regular and collision resistant (or second preimage resistant) (See Supplementary Information for Function Construction)

1. Client: instructs Server to prepare one register at ⊗nH |0i and second register initiated at |0im
2. Client: returns k to Server and the Server applies Ufk using the first register as control and the second as target
3. Server: measures the second register in the computational basis, obtains the outcome y and returns this result y to the Client. Here, an honest Server would have a state (|xi + |x0i) ⊗ |yi with fk(x) = fk(x0) = y and y ∈ =fk.

Client can rewrite the superposition in the control register for herself as,

{missing equation}

where G¯ is the set of bits positions where x,x0 are identical, G is the set of bits positions where the preimages differ, while suitably changing the order of writing the qubits.

Stage2 Squeezing

• Output: If the protocol is run honestly, when there is no abort, the state that Server has is |+θi, where the Client (only) knows the classical description.

1. Client: instructs the Server to measure all the qubits (except the last one) of the first register in the basis. Server obtains the outcomes b = (b1,··· ,bn−1) and returns the result b to the Client
2. Client: using the trapdoor tk computes x,x0. Then check if the nth bit of x and x0 (corresponding to the y received in stage 1) are the same or different. If they are the same, returns abort, otherwise, obtains the classical description of the Server’s state.

Definitions (informal)

• Quantum-Safe A protocol/function is quantum-safe (also known as post-quantum secure), if all its properties remain valid when the adversaries are quantum polynomial-time (QPT).
• One-Way A family of functions $\{f_{k}:D\rightarrow R\}_{k\epsilon \{0,1\}}$ is one-way if there exists a QPT algorithm that can compute $f_{k}(x)$ for any k, any input x ∈ D, and any QPT algorithm can invert $f_{k}$ with at most negligible probability over the choice of k.
• Second pre-image Resistant A family of functions $\{f_{k}:D\rightarrow R\}_{k\epsilon \{0,1\}}$ is second pre-image resistant if there exists a QPT algorithm that can compute $f_{k}(x)$ for any index function k, any input x ∈ D, and given an input x, it can find a different input $x_{0}$ such that $f_{k}(x)=f_{k}(x')$ with at most negligible probability over the choice of k.
• Collision Resistant A family of functions $\{f_{k}:D\rightarrow R\}_{k\epsilon \{0,1\}}$ is collision resistant if there exists a QPT algorithm that can compute $f_{k}(x)$ for any index function k, any input $x\epsilon D$, any QPT algorithm can find two inputs $x\neq x'$ such that $f_{k}(x)=f_{k}(x')$ with at most negligible probability over the choice of k.
• Two-regular A deterministic function $\{f_{k}:D\rightarrow R\}_{k\epsilon \{0,1\}}$ is two-regular if $\forall y\epsilon Im(f)$, we have $|f^{-1}(y)|=2$
• Trapdoor Function A family of functions $\{f_{k}:D\rightarrow R\}_{k\epsilon \{0,1\}}$ is a trapdoor function if there exists a QPT algorithm Gen which on input $1^{n}$ outputs $(k,t_{k})$, where k represents the index of a function, $\{f_{k}:D\rightarrow R\}_{k\epsilon \{0,1\}}$, where $f_{k}$ is a one-way function, then there exists a QPT algorithm Inv, which on inputs $t_{k}$ (which is called the trapdoor information) which was output by Gen($1^{n}$), and $y=f_{k}(x)$ can invert y (by returning all pre-images of y with non-negligible probability over the choice of $(k,t_{k})$ and uniform choice of x.

*contributed by Shraddha Singh