Quantum information · Theory
Randomness Certification from Statistically Hiding Commitments
arXiv:2610.25518v1 ↗PDF ↗Submitted 18 October 2026
- Question
- What cryptographic assumption lets a classical verifier certify randomness from a single untrusted quantum device, secure against quantum side information?
- Result
- A statistically hiding bit commitment that is computationally binding against quantum senders suffices; stronger notions such as collapse-binding are not needed. Consequently, post-quantum one-way permutations suffice. Trapdoor claw-free functions give an efficient verifier, and the quantum random-oracle model gives certification with no further assumption but an inefficient verifier.
The paper in detail
A Bell test certifies that outputs are random, even to an adversary holding quantum side information, because spatially separated devices cannot learn each other’s inputs. A single device sees the whole transcript, so the separation must come from computational hardness instead. In the computational Bell framework, a virtual input \(x=\xi(t)\) is a function of the transcript that the device cannot efficiently compute, and a virtual output \(a=\alpha(t)\) is defined alongside it. A fresh challenge \(y\) and the device’s answer \(b\) complete a CHSH round, accepted when \(a\oplus b=xy\).
The paper distinguishes two kinds of hiding. If \(x\) is hidden from efficient classical predictors, a classical device cannot win with probability above \(3/4\) plus a negligible amount, so winning more proves quantumness. Randomness needs more. If a quantum device could recover \(x\) from its leftover quantum state, it could tailor its answer to \(x\) and win without the incompatible measurements that force uncertainty. The virtual input must therefore be hidden from quantum predictors that hold the residual state.
The protocol builds on a construction of Morimae and Yamakawa. The prover runs the commitment’s sender in superposition. Pairwise-independent hashing isolates one valid opening for each bit, leaving \(\ket0\ket{x_0}+\ket1\ket{x_1}\). The verifier sends random strings \(r_0,r_1\), and the prover computes inner products and measures in the Hadamard basis. This leaves a BB84 state whose basis is the virtual input \(\xi=(x_0\cdot r_0)\oplus(x_1\cdot r_1)\). Measuring \(M_y=(Z+(-1)^yX)/\sqrt2\) wins CHSH with probability \(\cos^2(\pi/8)\approx0.854\). Theorem 1 shows that \(\xi\) is hidden from quantum predictors if the commitment is binding against quantum senders.
Theorem 2 then bounds the conditional entropy of the answer, \(H(B\mid T,Y,E)\ge c_0-O(\sqrt\varepsilon)-\mathrm{negl}(\lambda)/\gamma\), when the device wins with probability \(\omega^*-\varepsilon\). A direct proof via Jordan’s lemma and entropic uncertainty relations is also given. Entropy accumulation extends this to a sequential protocol with smooth min-entropy guarantees. The two instantiations isolate the role of the trapdoor. Claw-free functions let the verifier recover the unique openings efficiently. The hash commitment \(c=\mathcal G(b\|r)\) in the random-oracle model satisfies hiding and binding, but its verifier must search exhaustively.
Transferable methods
Hide a BB84 basis inside two commitment openings
The prover holds a superposition of the two openings of one commitment. Random inner products plus a Hadamard measurement leave a single qubit whose basis is an unpredictable bit of the transcript.
After the verifier sends \(r_0,r_1\), the honest state is \(\ket0\ket{x_0}\ket{x_0\cdot r_0}+\ket1\ket{x_1}\ket{x_1\cdot r_1}\). The bit register is uncomputed, since \(b\) is determined by \(x\). Measuring the opening register in the Hadamard basis uses \(H^{\otimes\ell}\ket x=2^{-\ell/2}\sum_d(-1)^{d\cdot x}\ket d\). Outcome \(d\) leaves \[\ket{\psi_t}\propto\ket{x_0\cdot r_0}+(-1)^{d\cdot(x_0\oplus x_1)}\ket{x_1\cdot r_1}.\] If the two inner products agree (\(\xi=0\)), this is the \(Z\) eigenstate \(\ket{x_0\cdot r_0}\). If they differ (\(\xi=1\)), it is an \(X\) eigenstate with sign bit \(d\cdot(x_0\oplus x_1)\). These are the virtual outputs \(a\) of Definition 3.2.
CHSH check (editorial). For \(\xi=0\) the target is \(b=a\); measuring along \((Z\pm X)/\sqrt2\), at \(45^\circ\) to \(Z\), gives it with probability \(\cos^2(\pi/8)\). For \(\xi=1\) the target is \(b=a\oplus y\): \(M_0\) leans toward \(+X\), so \(b=a\), while \(M_1\) leans toward \(-X\), so \(b=a\oplus1\). Each case wins with probability \(\cos^2(\pi/8)\approx0.854>3/4\).
How to reuse it
Measuring in the Hadamard basis a register that holds one of two strings collapses the remaining qubit’s phase to the parity \(d\cdot(x_0\oplus x_1)\). Combined with public random inner products, this prepares a BB84 state remotely whose basis the preparer cannot know. It works from any primitive that yields a coherent pair of preimages: commitments, two-to-one functions, claw-free pairs.
Turn a predictor into two openings
Security reduces predicting the virtual input to breaking binding. A predictor for \(\xi\) is converted, via a quantum Goldreich–Levin procedure, into a sender that outputs both openings of one commitment.
The virtual input is an inner product of a secret with public randomness: \[\xi=(x_0\cdot r_0)\oplus(x_1\cdot r_1)=(x_0\|x_1)\cdot(r_0\|r_1).\] The Goldreich–Levin theorem states that if \(w\cdot r\) can be guessed with probability \(\tfrac12+\eta\) over uniform \(r\), then \(w\) can be recovered in time \(\mathrm{poly}(\ell,1/\eta)\). Editorial intuition for the easy case: \(w\cdot r\oplus w\cdot(r\oplus e_i)=w_i\), so two guesses with error rate below \(1/4\) give each bit \(w_i\) by majority vote. The full theorem handles any non-negligible advantage, and the Adcock–Cleve version applies to quantum predictors.
Recovering \(x_0\|x_1\) gives classical openings of the same commitment to both 0 and 1 in a single execution. That is exactly the event that computational binding against quantum senders forbids, so \(\Pr[\text{predict }\xi]\le\tfrac12+\mathrm{negl}(\lambda)\) whenever the protocol continues with non-negligible probability. The proof never needs the committed bit to be fixed after the commit phase. This is why collapse-binding and sum-binding are not required.
How to reuse it
To prove that a hidden bit is unpredictable, write it as an inner product of secret strings with fresh public randomness. Goldreich–Levin then turns any predictor into an extractor for the secrets, and security reduces to the hardness of producing them: binding, claw-freeness or collision resistance. Check which form of the underlying assumption the extraction actually contradicts; it may be weaker than expected.
Context & limitations
Why it matters. Separates what security needs (hiding and binding) from what efficient verification needs (a trapdoor to recover unique openings), and shows that a proof of quantumness is not automatically a randomness certificate.
Limitations. The honest prover gets past the hashing step only with probability about \(1/(10m)\), so the single-round gap is inverse-polynomial. Whether arbitrary post-quantum one-way functions suffice is open, and the random-oracle verifier uses exhaustive search.