Creating quantum-resistant classical-classical OWFs from quantum-classical OWFs

Let us consider the following construction of a classical-classical function. Let $\mathcal{S}\subseteq\mathbb{C}^{2^{m}}$ be some finite set of $m$-qubit states. Let $f_{1}:\{0,1\}^{n}\rightarrow\mathcal{S}$ be a classical-quantum function. Let $f_{2}:\mathcal{S}\rightarrow\{0,1\}^{n^{\prime}}$ be a quantum-classical function. Let $f:\{0,1\}^{n}\rightarrow\{0,1\}^{n^{\prime}}$ be defined by $f(x)=f_{2}(f_{1}(x))$. For now, we consider only the case where $f_{1}$ and $f_{2}$ (and hence $f$) are deterministic.

Next, we want to consider what happens if $f_{1}$ and/or $f_{2}$ is a OWF. First, we require definitions of classical-quantum and quantum-classical OWFs.

It is important to note the use of the swap test in the definition. We would like to know whether the $m$-qubit states $f_{1}(A(f_{1}(x)))$ and $f_{1}(x)$ are equal. Gottesman01 proposed to use the swap test as the test for equality, as there is no perfect equality test for two quantum states. In the swap test, we use a $|+\rangle$ qubit as the control qubit in a controlled-swap operation between the two states that are to be compared (denoted $|\psi_{1}\rangle$ and $|\psi_{2}\rangle$). We then apply a Hadamard gate to the control qubit and measure it. The swap test is passed if we measure $|0\rangle$ and failed otherwise. If $|\psi_{1}\rangle=|\psi_{2}\rangle$, we will measure $|0\rangle$ with probability 1. However, if $|\psi_{1}\rangle\neq|\psi_{2}\rangle$ and $\lvert\langle\psi_{1}|\psi_{2}\rangle\rvert\leq\delta$, then the swap test passes with probability at most $(1+\delta^{2})/2$, i.e. the swap test, serving as an equality test, has a probability of failure if the states are unequal. With this in mind, it would be ideal for the outputs of $f_{1}$ to be close to orthogonal, so that the swap test has a larger probability of failing if the states are unequal. Using the swap test as the equality test also means that we require a large enough number of copies of the challenge state (say, $k=\omega(\log n)$ copies), such that we can perform enough independent swap tests to eventually end up with a negligible probability that unequal states pass all the swap tests.

Next, we define a quantum-classical OWF.

While we do not need to define an equality test like in the classical-quantum case, we do need to consider the possibility of $A_{q}$ producing a state not in $\mathcal{S}$. $f_{2}$ was defined to be deterministic only for states in the domain $\mathcal{S}$. Therefore, on input states outside of $\mathcal{S}$, there is no longer a guarantee that the output will be deterministic. This opens up the possibility of $A_{q}$ producing a state that is not in $\mathcal{S}$, but when given as input to $f_{2}$, results in a non-negligible probability of outputting a certain string. When this happens, we can consider this as a kind of ‘cheating’, since $A_{q}$ did not actually find a preimage in the domain $\mathcal{S}$, but just managed to find some other state that makes $f_{2}$ output the desired string with non-negligible probability. One way to overcome this would be to simply define a successful inversion where $A_{q}$ must produce a state in $\mathcal{S}$. However, the definition we adopted was to simply mandate the function to not produce any output with non-negligible probability when given any state not in $\mathcal{S}$, demotivating $A_{q}$ from ‘cheating’. Note that there is potential for an extensive discussion on the best way to resolve the issue with ‘cheating’. For example, we can imagine more relaxed versions of the ‘no cheating’ property, e.g. if a state close enough to the preimage but not in $\mathcal{S}$ also produces the output string with non-negligible probability, we might want to consider that as a successful inversion as well and thus allow such a behavior from $f_{2}$, while defining it to be difficult to find such a state to retain the one-way property. However, regardless of the method of choice we use to prevent the adversary from ‘cheating’, if we were to consider the use of such a function for the purposes of building a classical-classical OWF as in Theorem 1, the adversary in the proof of Theorem 1 does not cheat, and hence we can consider definitions without the ‘no cheating’ property (i.e. it is only difficult to find a preimage in $\mathcal{S}$ but it may not be difficult to find a preimage outside of $\mathcal{S}$). The question about the feasibility of alternative quantum-classical OWF definitions and their potential cryptographic applications will be left as an open question for now. The question of whether quantum-classical functions exhibiting the ‘no cheating’ property as defined exists is also left unanswered for now.

With these definitions, we can now prove our first theorem.

Applying a similar construction as the proof above, we do not arrive at a contradiction if we instead set $f_{1}$ to be a OWF and not $f_{2}$. Suppose $A$, when given $y=f(x)$, can find an inverse $x^{\prime}$ such that $f(x^{\prime})=y$. Let $|\psi\rangle=f_{1}(x)$, $|\psi^{\prime}\rangle=f_{1}(x^{\prime})$. Clearly $|\psi\rangle$ and $|\psi^{\prime}\rangle$ can be different, i.e. $x^{\prime}$ is not necessarily a preimage of $|\psi\rangle$ with respect to $f_{1}$. Therefore, even if we assume $f$ is not one-way, we do not contradict $f_{1}$ being a OWF. Note that we have only ruled out one way of constructing classical-classical OWFs from classical-quantum OWFs. Whether classical-quantum OWFs can lead to classical-classical OWFs remains an open question.

Next, we aim to explore whether a quantum-classical OWF following the definition in Definition 4 can exist. While we do not show with certainty that such a function exists, we explore a non-exhaustive list of ways that do not result in a quantum-classical OWF.

Indeed, proving the existence of a quantum-classical OWF as defined in Definition 4 would almost certainly give us a quantum-resistant classical-classical OWF due to Theorem 1, provided a suitable and efficient classical-quantum function can be found. For now, we attempt to provide a non-exhaustive list of methods that do not work in giving us a quantum-classical OWF. The methods listed here are generally simple methods which only apply a unitary operation and make some kind of measurement at the end of the unitary operation.

Behera18 proposed a quantum-classical OWF that is different from Definition 4. In this approach, the OWF itself is defined dynamically based on the input state. To formally define this OWF, we have to first introduce GCH states. An $n$-qubit GCH state is a tensor product (in any order) of qubits in either the standard basis $\mathcal{C}=\{|0\rangle,|1\rangle\}$, the Hadamard basis $\mathcal{H}=\{|+\rangle,|-\rangle\}$, or GHZ states containing 2 to $n$ qubits $\mathcal{G}=\bigcup_{j=2}^{n}\mathcal{B}_{j}$, where $\mathcal{B}_{j}=\{\frac{1}{\sqrt{2}}(|x\rangle+|\bar{x}\rangle)\mid x\in\{0,1\}^{j}\}$. Now we can define the function signature of the candidate quantum-classical OWF:

where $\{|\psi^{(n)}\rangle_{GCH}\}$ refers to the set of $n$-qubit GCH states.

Here we briefly explain the construction of such an $\mathcal{F}$ for a given input state.

• •

  We generate a circuit by adding several layers of parallel CNOT gates (called OWF gate operations) which are randomly placed while following a set of rules. CNOT gates can only be used on two compatible qubits, such that if a GCH state is given to an OWF gate operation as an input, then the output is also a GCH state.

• •

  In the final OWF gate operation, we mark one qubit per CNOT gate using some fixed rules based on the type of qubit at each position, and choose $(\frac{n}{2}-1)$ of the marked qubits for measurement. The rules ensure that the marked qubits will either be $\mathcal{C}$ or $\mathcal{H}$ qubits.

• •

  Finally, we perform a POVM measurement on these marked qubits (hence not collapsing the state with measurement) to obtain the classical output. The classical output describes the state of each of the marked qubits (i.e. one of $|0\rangle,|1\rangle,|+\rangle,|-\rangle$).

• •

  We repeat the whole circuit generation procedure for $n$ times (which is possible since the measurement did not collapse the state, hence we can apply the reverse circuit to obtain the original input), i.e. we have $n$ such randomly generated circuits to produce $n$ sets of classical outputs. The final output of $\mathcal{F}|\psi\rangle$ is the concatenation of all $n$ sets of classical outputs.

• •

  The user is given the classical output as well as all $n$ circuits used. It will be difficult for the user to find an input GCH state by various methods of random guessing that produces the same output, except with negligible probability.

In short, the function involves $n$ repetitions of passing the input state through a circuit, measuring, and passing the state through the reverse circuit, where $n$ is the number of input qubits. In fact, we can imagine this whole process as a single circuit with intermediate non-destructive measurements, and therefore future mentions of the term ‘circuit’ will be referring to the one implementing the entire $\mathcal{F}$ instead of just one of the circuits used in some iteration of the algorithm.

The first thing to consider is to find a way to encode the input GCH states in binary. Fortunately, this can be easily done. One way to do this is to encode the circuit producing a GCH state in binary. Figure 1 shows a possible circuit for encoding a GCH state. We can encode such a circuit in the following manner:

• •

  First $n$ bits: describes the initial qubits ($|0\rangle$ or $|1\rangle$).

• •

  Next $n$ bits: describes which positions have the Hadamard gate applied.

• •

  Next $O(n\log n)$ bits: describes all the positions of CNOT gates. We can enforce certain rules for valid classical encodings at this part. Firstly, the control qubit of each CNOT gate must be on a qubit that is currently a $|+\rangle$. Secondly, for a set of qubits that are supposed to be entangled in the same GHZ state, all the CNOT gates used for entangling all of these qubits must have their control qubit be the qubit with the smallest-numbered position. For example, if qubits 6, 7, 8 are to be entangled, we must have two CNOT gates with (control, target) qubits be (6, 7) and (6, 8). Enforcing these rules will give us a bijective mapping from the set of valid encodings to the GCH states. Lastly, we use $O(n\log n)$ bits because there are at most $n$ CNOT gates since each qubit can only be the target qubit of each CNOT gate once, and the location of each CNOT gate can be described by two $\lceil\log n\rceil$ strings for the position of the two qubits. More precisely, we use at most $2n\lceil\log n\rceil=O(n\log n)$ bits for this section.

The next obstacle to overcome when converting the quantum-classical OWF of Behera18 to a deterministic classical-classical OWF is that, given a function $\mathcal{F}$ sampled according to the proposed algorithm, this function produces deterministic output on states with the same basis as the chosen input state but may produce non-deterministic output on states with a basis different from the chosen input state. At this stage, we make the following key observations:

• •

  A circuit (where ‘circuit’ refers to the entire implementation of $\mathcal{F}$ as explained in the previous subsection) sampled based on an input state $|\psi\rangle$ has deterministic output on all states with the same basis as $|\psi\rangle$. Therefore, if we are able to use a circuit family instead of just a single circuit, where each circuit in the circuit family caters to states of a certain basis, then the function implemented by the whole circuit family would be entirely deterministic.

• •

  Sampling the circuit is efficient since its size complexity is $O(n^{3})$ as proved by Behera18 , and so we only have to perform $O(n^{3})$ samplings. This means that at runtime, it is efficient to generate the appropriate circuit from the circuit family based on the basis of the input state. Clearly it is also efficient to know the basis of the input state since we need to generate the actual quantum state, and knowledge of the state automatically gives us knowledge of the basis.

Using these observations, we come up with the following algorithm. We require the use of a seeded pseudorandom number generator (PRNG) that we denote $\mathcal{P}_{s}$, where $s$ is the seed.

The only part of Algorithm 1 that has not been explained yet is the addition of an encoding of $\mathcal{F}_{b}$ to the output $y$. The adversary considered by Behera18 does indeed not only have access to the classical output, but also the implementation of the circuit $\mathcal{F}$. Therefore, by including information about the circuit in $y^{\prime}$, we ensure that our adversary has access to the same information as the one considered by Behera18 , allowing us to simply adopt their security guarantee. Another benefit of appending the encoding of $\mathcal{F}_{b}$ to the output is to prevent collisions. Since states with different bases will produce different circuits, the encoding of these circuits will also be different, which means the only possible collisions must come from states of the same basis. However, these collisions should occur on a low enough frequency such that the one-wayness of the quantum-classical function is not affected, otherwise this would contradict the results of Behera18 . Lastly, we do not cover in detail how to encode the circuit $\mathcal{F}_{b}$, since it should be clear that such a polynomial-sized circuit can be encoded efficiently. One possible method of encoding a constituent circuit (instead of the whole circuit representing $\mathcal{F}$; these encodings of each consituent circuit can then be concatenated eventually) is to simply produce a list of CNOT gate positions ordered first by layer, then by lexicographic order according to the control and target positions of the CNOT gates in each layer. The marked and measured qubits at the end of the circuit can each be encoded using $n$ bits. Using this method of encoding will give us a unique encoding for each circuit. In short, Algorithm 1 creates the input state, generates the appropriate circuit, executes the circuit to obtain the classical outputs, then returns the classical outputs along with an encoding of the circuit. If Algorithm 1 was not one-way, we can clearly see that we will be able to violate the one-wayness of the candidate quantum-classical OWF and contradict the results of Behera18 . This leads us to our final theorem:

• •

  $A$ knows the classical output and the circuit used. $A$ encodes the circuit in the same way that Algorithm 1 encodes the circuit.

• •

  $A$ now has a valid classical output for the classical-classical function implemented by Algorithm 1. Since this function is assumed to be not a quantum-resistant OWF, $A$ is able to obtain a valid preimage with non-negligible probability.

• •

  $A$ can then use the valid preimage to produce a GCH state that is a valid preimage for the candidate quantum-classical OWF, i.e. inverting it. This contradicts the assumption that the candidate quantum-classical OWF is secure.