Replace IBM Quantum back end with /dev/urandom
A developer provocatively demonstrates that a reported 'quantum attack' on ECDLP, previously claimed to use IBM Quantum hardware, can be fully replicated by simply replacing the quantum backend with /dev/urandom. This surgical patch reveals that the success was not due to quantum computation but rather classical verification applied to uniform-random candidates. The story resonates on HN by challenging bold claims in quantum computing with a clever, technically sound debunking.
The Lowdown
A compelling analysis challenges a significant claim within the quantum computing community: a supposed quantum attack on Elliptic Curve Discrete Logarithm Problem (ECDLP) that used IBM Quantum hardware. The original submission, which earned a Q-Day Prize, claimed to achieve key recovery on curves up to 17 bits.
- The Experiment: The author of this analysis surgically modified the original project's code,
projecteleven.py, by replacing the IBM Quantum backend with a simple call to/dev/urandom. This allowed the code to generate uniform-random bitstrings instead of interacting with quantum hardware. - The Hypothesis: If the quantum computer genuinely contributed to the key recovery, substituting it with randomness should have broken the results.
- The Results: Surprisingly, the patched version of the code, running on a standard laptop, recovered private keys at statistically indistinguishable rates from the original IBM hardware runs. This included successful recovery for both smaller (4-bit to 10-bit) and 'flagship' (16-bit and 17-bit) challenges.
- The Explanation: The success isn't quantum, but classical. The original extraction pipeline accepts candidate keys if they pass a classical verifier. When the number of 'shots' (attempts) is sufficiently large relative to the curve's order (
n), even uniform-random candidates have a high theoretical probability of passing this classical verification, a fact acknowledged in the original author's own README.
While the original project's quantum engineering, involving various oracle variants and phase estimation, was acknowledged as non-trivial, this demonstration conclusively argues that the cryptanalytic claim of quantum-powered ECDLP key recovery in this specific instance was unfounded. The success was purely classical verification of random guesses.