There is quite a few things in there.
First, challenges from 6 bits to 256 bits which are compatible with Shor’s algorithm.
The 256-bit challenge is literally the (unspendable) public key of Bitcoin’s genesis block, very high symbolic value.
Notice that the logical resources interpolate between the current NISQ regime all the way to CRQCs! So we bridge the application gap (I should make that figure actually, now you still have to map it on those charts).
By mapping both the progress of quantum algorithms and quantum hardware along with their roadmaps we can get a pretty good estimate of the timeline to CRQCs: 2027-2033 seems to be the sweet spot. Meaning it will be a very sharp transition over 24-36 months! I think 6 bits should be doable this year or early next year.
Also there will be very little warning in between the point where quantum computers can beat the best classical record, classical is already at 129 bits!
The goal with this paper is really to review the state of the field and set the stage for experimentalists to start demonstrating the building blocks for cryptanalysis and provide signal to the cybersecurity world to accelerate the PQC upgrade.
Also as bonus we find that LDCP cat codes can break Bitcoin with only 38,581 physical (cat) qubits! It’s the lowest figure in terms of physical resources so far!
First of all, thanks for putting this together. I think it’s an excellent resource and ties together a lot of different estimates for Q-Day timelines.
Secondly, I love the challenges and how explicit they’ve been made. One thing that I think might be interesting is to add bounties to each step of the ladder. That could be potentially done using Ethereum smart contracts, and it would help create upside as well as be open for all to see.
We had done some kind of bounty system on https://proof-of-quantum.com/ (old set of challenges with reduced range, it works with Pollard-rho but not Shor).
I’ve been looking into ways to deploy smart contracts where certain (admin) functions are quantum-secure, it’s actually fairly straightforward. The contract could host a series of challenges, each one requiring Shor’s to break progressively larger key sizes.
What’s interesting is the baseline on the classical side, thank you for providing this. There’s an inflection point where quantum “overtakes” classical in terms of bits broken. Technically it’s apples to oranges, but socially that crossover point will be treated as a big milestone and that perception matters IMO.
On EVM chains, the verification of hash-based signatures is quite straightforward, it’s the key state management on the user which is the bulk of the work.
Yeah, it would a series of challenges which are time bound. Those would act as oracle for the payout. The rest are typical functions for a prediction market: adding/removing liquidities, buy/selling positions, resolving payouts, etc.
