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

Question

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).

Thus Peggy proves that she was able to execute a function in quantum superposition (or she has broken the security of the TCF).

The authors also require the TCF to satisfy the "adaptive hardcore bit" property, meaning, effectively, that it's computationally difficult to learn any joint property of individual bits of the separate claws $x_0$ and $x_1$ having $f_0(x_0)=f_1(x_1)=y$.

The authors instantiate their TCF's with "learning-with-errors", which, in addition to satisfying the hardcore bit requirement, also happens to be a leading candidate for "post-quantum cryptography" - that is, cryptographic protocols that are likely secure against a quantum prover.

But my question is whether such a scheme to just prove quantumness really should also have a post-quantum guarntee?

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

1. She has prepared and maintained a quantum superposition of the claws; or

2. She has broken the TCF - perhaps with another quantum computer. If she were able to break the claw quantumly, then she has also evidenced computational quantumness.

Is the post-quantum requirement if [BCMVV18] required to prove quantumness?

Answer 1

^{(self-answer made CW)}

---

I asked this a while back and then quickly deleted it (I don't recall why).

But the answer to the question in the title is affirmatively "no", tests of quantumness such as those introduced by Brakerski et al. need not require a post-quantum hash!

This was noted by Kahanamoku-Meyer, Choi, Vazirani, and Yao in "Classically-Verifiable Quantum Advantage from a Computational Bell Test" (arxiv link). They introduce a couple of tests, e.g. one based on differential Diffie-Hellman and one based on a Hadamard of the $x^2\bmod N$ hash (which is presumably much easier than Shor's QFT on $a^x\bmod N$ but is still broken by factoring $N$.)

They state:

Importantly, in this work we only require that breaking the claw-free property is hard classically — indeed, the claw-free property of the DDH and $x^2\bmod N$ TCF's described herein can be fully broken by quantum computers.

It's perhaps interesting to ponder what other cryptographic primitives can be used in interactive protocols with a quantum computer that are quantumly broken. I think you'd still need post-quantum crypto for, e.g., fully homomorphic encryption (FHE).