This is a handy table from @cryptoquick's as-yet unassigned pay to quantum resistant hash BIP
It shows that there are (at the moment) three kinds of quantum resistant signatures schemes that might work for Bitcoin:
- hash-based
- lattice
- isogeny
@conduition has already published an excellent (and very thorough) resource on isogeny-based cryptography (#1453183).
Several years ago, they published a post about using GPUs to speed up signing with hash-based signatures. Now, conduition is back with improvements (hacks?) to this scheme that trade's off the number of times such a hash-based key can be used in order to gain efficiency in signing speed.
This article demonstrates a hacky algorithmic trick I call hypertree pruning which SLH-DSA signer implementations can use to electively reduce a key’s signature use limit in exchange for better signing and/or keygen performance.
If you are like me and aren't quite fresh on what SLH-DSA is or any other of about half of what conduition said there -- never fear! The article and the one from a few years ago explain quite a lot!
The security trade-off can be parameterized to favor signing or keygen performance improvement, and the intensity of the trade-off may be tuned based on the number of signatures each keypair is expected to make over its lifetime.
As a result, the ideal use-cases for hypertree pruning are situations where verifier behavior is fixed, but the signer lacks hardware powerful enough to produce SLH-DSA keys or signatures using the verifier’s prescribed SLH-DSA parameter set. Hypertree pruning can empower signers who otherwise wouldn’t be able to produce compatible keys or signatures in a reasonable amount of time. Examples include low-power embedded hardware systems, legacy CPUs lacking hardware acceleration, or high-throughput applications which must be able to produce many signatures from multiple keys very quickly.
More plainly, hypertree pruning allows a signer to produce valid SLH-DSA keys and signatures which standard verifiers will accept, at the cost of a smaller limit on the number of signatures that each keypair can safely produce.
This is all from the introduction. I'm working my way through conduition's posts, feeling like I'm getting a pretty killer basis in applied cryptography. But I'm slow because I have to pause and think through each paragraph. Math doesn't come naturally to me.
Cryptography doesn't come naturally to me, either, and I find myself needing to pause to think carefully about it too.
I might write a primer on cryptography. One of my reasons for writing these primers is actually to help me think through the concepts more carefully. I think there might be a layer of abstraction that could help, when thinking about cryptographic systems.
I would be grateful for such a primer. I've tried a few I found online and none of them have stuck with me so far. I'm sure it's a lack of stick-to-it-ive-ness, but I do want to get a better understanding of the math behind this stuff. I don't like the feeling that I don't understand the pitfalls.
A weakness I've found about most online cryptography tutorials is that they focus too much on the actual algorithm.
I think it's better to start with the abstraction. Cryptography should boil down to three operations:
keygen,encrypt, anddecrypt. And maybesignandverify. Every cryptographic system basically has different approaches to these 5 functions. That's probably what my primer would focus on.