# Must the cryptographic test for quantumness in [BCMVV18] use post-quantum Trapdoor Claw-Free Functions?

Brakerski, Christiano, Mahadev, Vazirani, and Vidick propose a scheme for verifiable computational quantumness based on a strengthening of trap-door claw-free functions (TCFs).

In the above scheme:

1. Vicky the classical verifier provides a description of a pair of functions $$f_0$$ and $$f_1$$ to Peggy the quantum prover, while saving the trapdoor to $$f_0$$ and $$f_1$$;

2. Peggy prepares, measures, and reports the results of a register in a quantum state to provide a $$y$$ such that $$y=f_0(x_0)=f_1(x_1)$$, keeping a superposition of $$\vert b\rangle\vert x_b\rangle$$;

3. Vicky asks Peggy to measure the superposition in either (a) the computational basis to provide a bit $$b$$ and an $$x_b$$ such that $$f_b(x_b)=y$$, or (b) in the Hadamard basis to provide a string $$d$$ orthogonal to $$x_0\oplus x_1$$; and

4. Based on Vicky's possession of the trapdoor, Vicky can validate results (she uses the trapdoor to deduce both $$x_0$$ and $$x_1$$ from $$y$$ and Peggy's response above).

The authors instantiate their TCF's with lattice-based learning-with-errors, which, in addition to satisfying hardcore bit requirements, is also a leading candidate for post-quantum cryptography - that is, a cryptographic protocol that is likely secure against a quantum computer. They require post-quantum security for randomness generation, and Mahadev requires post-quantum security for her later breakthrough on classical verification of quantum computing.

But does such a scheme to just prove quantumness also need to be based on post-quantum TCFs?

For example if the trapdoor claw-free function was based on a classically-secure, but quantum-broken, TCF, and if Peggy could be consistent in reporting correct answers to Vicky, then Peggy has shown that either:

• She has prepared and maintained a quantum superposition of both preimages as intended; or

• She has broken the TCF with quantum computer to invert $$f_b$$ to find at least one preimage along with the string $$d$$.

Either way, she has evidenced computational quantumness.