WEBVTT Automatically timed original source text; AI narration; timing not manually listen-through verified.

00:00:00.000 --> 00:00:02.400
State of Post-Quantum Cryptography.

00:00:02.620 --> 00:00:11.600
Notes from a talk by Dan Boneh at the Post-Quantum Bitcoin Workshop at Stanford, 28 August 2026, written by Localhost Research.

00:00:11.980 --> 00:00:13.820
This is an AI recording.

00:00:14.140 --> 00:00:19.220
Find the original text and more information on btctranscripts.com.

00:00:19.420 --> 00:00:23.100
Setting the Stage: "When is Q-Day?"

00:00:23.750 --> 00:00:32.210
There is a lot of noise in the press ("PoW is going to collapse," etc.). It would be good for Bitcoin to have an answer to that noise.

00:00:32.510 --> 00:00:47.910
On hardware timelines: Boneh used to be more pessimistic; he is now more optimistic — or realistic — about quantum computers arriving in the "coming years," particularly given advances in neutral atom approaches.

00:00:48.330 --> 00:00:56.950
If pushed on a date: "If it doesn't happen by 2040, something has gone wrong and we don't know when it will happen."

00:00:57.840 --> 00:01:16.140
Fundamentally, though, "when" is the wrong question. The right question is: how do we make sure Bitcoin survives Q-Day whenever it happens? Answering that restores and preserves trust in Bitcoin today, even before a quantum computer exists.

00:01:17.600 --> 00:01:19.280
Which Signature Family?

00:01:19.860 --> 00:01:28.560
Options on the table: lattice-based, hash-based, isogenies, multivariate, and zk-proof-of-preimage.

00:01:29.220 --> 00:01:34.680
Boneh's personal preference (were he "king for a day"): lattice-based.

00:01:35.200 --> 00:01:44.800
Historically, the algebraic structure of signatures has been enormously useful for blockchains: threshold signing, multisignatures, aggregation.

00:01:45.060 --> 00:01:52.100
Many of those properties translate to lattices. It keeps the research community active and is more feature-rich.

00:01:52.480 --> 00:02:00.600
But the world seems to be going hash-based (both Ethereum and Bitcoin are focusing there), and that comes at a cost:

00:02:01.400 --> 00:02:04.580
Non-hardened key derivation appears impossible.

00:02:05.100 --> 00:02:07.040
Some features are simply lost.

00:02:07.660 --> 00:02:18.220
zk-proof-of-preimage can technically function as a hash-based signature, but the ecosystem seems to be converging on SLH-DSA and similar schemes.

00:02:19.680 --> 00:02:22.780
Terminology: The Hash-Based Signature Spectrum

00:02:22.780 --> 00:02:24.280
Scheme type: Property.

00:02:25.120 --> 00:02:30.820
OTS (one-time signatures): Secure if at most one signature is issued per public key.

00:02:31.210 --> 00:02:42.610
Stateless FTS (few-time): Secure for "a few" signatures per key — an ambiguous upper bound, up to a few thousand. Security degrades as more signatures are issued.

00:02:43.390 --> 00:02:49.850
Stateful FTS: Short signatures, but state must be maintained. Reusing state exposes you to forgery.

00:02:50.350 --> 00:02:57.760
Many-time (SPHINCS+ / SLH-DSA): Effectively stateless, huge signature budgets.

00:02:58.140 --> 00:03:08.000
Stateful schemes are a major footgun — people will have trouble ensuring state is never reused. If used at all, perhaps deploy as a hybrid (stateful + EC).

00:03:08.520 --> 00:03:19.680
SLH-DSA (SPHINCS+ NIST standard): supports 2⁶⁴ signatures, but signatures are massive — inappropriate for a blockchain as-is.

00:03:20.100 --> 00:03:34.060
Reducing the budget to 2²⁴ drops signature size to ~3.8 KB, at the cost of very long signing time (~1B hashes). The benefit: verification is very fast (~311 hashes).

00:03:34.160 --> 00:03:42.680
Many other parameterizations exist (e.g., 2¹⁴ budgets with faster signing; SHRINCS is another stateless variant).

00:03:43.320 --> 00:03:48.400
ML-DSA: the issue is that public keys must be included, and they are quite large.

00:03:49.580 --> 00:03:51.840
Threshold Hash-Based Signatures

00:03:52.260 --> 00:03:55.600
Approaches to thresholdizing hash-based schemes:

00:03:56.260 --> 00:03:58.500
Multi-signing — very large signatures

00:03:58.980 --> 00:04:03.540
SNARK-based aggregation — requires consensus-level understanding of SNARKs

00:04:04.020 --> 00:04:15.980
Universal thresholdizer (BGG '18) — single round, but slow: signing must run inside an FHE system; not practical yet without GPUs

00:04:15.980 --> 00:04:16.960
Generic MPC

00:04:16.960 --> 00:04:36.430
PRWNS — applies to hash-based signatures; the resulting signature is threshold but looks like a regular single-sig. The threshold mechanism is implemented with lattice techniques. Supports large n and t, updatable, single round — but only applicable to few-time signatures for now.

00:04:37.570 --> 00:04:41.130
Research Is Not Done — Expect a Two-Step Migration

00:04:41.130 --> 00:04:49.330
PQ signature research is still ongoing. ML-DSA is not the endgame — NIST possibly standardized it too early.

00:04:49.590 --> 00:05:00.230
There is no theorem ruling out a 100-byte signature with all the features we want. Building it is the major challenge for the community — such a scheme may well arise, but we can't wait forever.

00:05:00.950 --> 00:05:03.610
Likely migration shape: two steps, not one:

00:05:04.390 --> 00:05:09.720
1. E.g., Taproot with ECDSA + SHRINCS now

00:05:09.980 --> 00:05:20.860
2. Later, ECDSA + "DreamPQSig" when a better scheme arrives (possibly dropping ECDSA before then; assume the dream scheme won't be hash-based)

00:05:22.130 --> 00:05:27.710
A Second Reason for Two Steps: Is SHA-256 Actually PQ-Secure?

00:05:28.070 --> 00:05:32.190
(Boneh: "I don't mean to raise false alarms — but you should be aware.")

00:05:33.140 --> 00:05:42.570
Classical collision attacks: birthday attacks; the rho method (sequential, with parallel variants). All need ~√n evaluations of the hash function.

00:05:43.130 --> 00:05:52.490
Quantum collision finding: the BHT algorithm runs in cube-root-of-n time — and crucially makes only cube-root-of-n queries to the hash function.

00:05:52.810 --> 00:06:02.310
There's no reason a constant-space quantum collision finder couldn't exist. In theory: ~2⁸⁶ time to find a SHA-256 collision.

00:06:02.670 --> 00:06:06.970
Options: move to SHA-384, or decide not to care.

00:06:08.140 --> 00:06:08.900
Q&A

00:06:08.900 --> 00:06:09.980
On Grover's algorithm:

00:06:10.280 --> 00:06:23.440
The quadratic speedup from Grover is very slow in practice — "borderline fictitious." That's why SLH-DSA's 128-bit parameters are fine even though they're nominally 64-bit under Grover.

00:06:23.760 --> 00:06:27.920
Grover cannot be parallelized, so it's largely ignorable here.

00:06:28.580 --> 00:06:32.600
Q: How does the cube-root collision finding relate to Grover?

00:06:32.940 --> 00:06:46.080
BHT actually uses Grover as a subroutine (Grover inverts a function in √n time), which is how the cube-root collision algorithm arises. Bottom line: don't worry too much about this.

00:06:46.740 --> 00:06:51.260
Q: What about non-linear quantum speedups to PoW mining?

00:06:51.540 --> 00:07:08.580
A recent paper found this completely impractical. Grover matters even less here: the smaller the problem, the smaller the effective speedup, and because quantum machines are so slow at Grover, the problem size must be gigantic before the quadratic advantage shows up at all.

00:07:09.350 --> 00:07:18.190
Q: Any cracks in the fundamental SHA primitives (Merkle–Damgård)? Could quantum do better than classical there?

00:07:18.450 --> 00:07:31.840
Classical attacks are definitely progressing — e.g., alongside breaking HAWK, AI-assisted work broke 7-round AES. Could models reach 8 rounds next year? Unknown; we can't predict.

00:07:32.480 --> 00:07:49.500
Notably, few people are studying quantum attacks on specific block ciphers / SHA-256 — the research communities are fairly disjoint. Some papers exist but little progress. Quantum doesn't seem very helpful against symmetric systems so far — but that could change.

00:07:50.060 --> 00:08:06.520
Closing thought: we should use system context to design better schemes — signatures designed for the specific system they live in. (Segue to Antonio: e.g., a short-term key stored in Ethereum account metadata, updated across transactions.)