The NIST PQ Signature Zoo has nice benchmarking information on post-quantum signature schemes, including the new round three on-ramp schemes, of which many are being broken.
Isogenies schemes remain far too slow. Also the SIDH break narrows that playing field considerably.
In 2022, there was an amusing late game complete break of the multivariate quadratic scheme Rainbow. Imho all new multivariate quadratic schemes should be viewed with more skepticism than lattice based schemes, as perhaps the analysis remains less mature, which rules out DME-Sign & MAYO for now.
We’re left with two lattice based schemes:
Dilithium II
https://pq-crystals.org/dilithium/index.shtml
security level II --- At least as hard to break as SHA256 (collision search)
pk 1312 bytes
sig 2420 bytes
pk+sig 3732 bytes
sign 333 k cycles = 8 x slower than Ed25519
verify 118 k cycles = 10% faster than Ed25519
Falcon 512
https://falcon-sign.info/
security level I --- At least as hard to break as AES128 (exhaustive key search)
pk 897 bytes = 31.6 % smaller than Dilithium II
sig 666 bytes = 72.5 % smaller than Dilithium II
pk+sig 1563 bytes
sign 1,009 k cycles = 24 x slower than Ed25519 = 3x slower than Dilithium II
verify 81 k cycles = 37.7 % faster than Ed25519 = 31.4 % faster than Dilithium II
These are both much larger than the 32 bytes public keys and 64 byte signatures of Ed25519 and Sr25519, but Ed25519 needs 42 k cycles in signing and 130 k cycles in verifying.
We’ve inherited the poor performance of libp2p, so these large sizes cause us trouble of course.
We have 1000+ verifiers in consensus and relay chain tx, and cannot batch verify in consensus, so Falcon 512 should be a dramatic improvement in CPU time over Ed25519, but the sig+pk being 96 x larger sucks in gossip.
We’ve say 35 approval checkers for parachain blocks, plus any parachain nodes, so Falcon 512 still pays off in CPU and does less harm in bandwidth.
In brief, there is seemingly no reason to use Dilithium II over Falcon 512 in kusama or polkadot, unless the higher security level somehow becomes relevant.
Consensus signatures:
We should lazily begin experiments with Falcon 512 in relay chain consensus, like grandpa first, with the idea of eventually trying it temporarily on kusama. It doesn’t matter if this work is done by parity or an external team, but whoever does this should do quality network benchmarks.
Arguably these signatures should be hybrid aka Falcon+Ed25519, which makes everything purely a pessimization, so that’s worth doing in experiments too, but how far we push this remains an open questions. It’s likely whatever we do remains only experiments until further news indicates that deploying post-quantum signatures grows pressing. And clearly Falcon is remains less trusted than Ed25519 against classical adversaries.
Account signatures:
We need not rush deployment of post quantum signatures for accounts. Instead, we should wait until the consensus experiments help us assess the costs. It’s also plausible the NIST competition yields interesting alternatives, like maybe a multivariate quadratic scheme.
In practice, there is always a secret key derivation layer for Ed25519 and Sr25519. We should therefore have the treasury fund development of zkSNARK circuits that proves knowledge of this hash preimage, maybe in an AIR flavor with an open source proovers, but perhaps even in R1CS or related. A zkSNARK which proves a key derivation hash then acts like a signature, but does not reveal this preimage, even against a quantum attacker.
If this SNARK itself is not post-quantum then the attacker could still forge SNARKs, say by breaking their trusted setup, but this maybe useful in transition and signatures can be disputed by key holders. If the SNARK is post-quantum, then it provides a post-quantum signature based upon an Ed25519 or Sr25519 key!
This one good reason why we’ve no rush to deploy post-quantum accounts, especially if you think quantum computers won’t pose serious risks anytime soon.
We should fund academics who do work on batch verification of lattice based signatures though. We should also understand what the optimal host call interface for lattice based primitives.
Consensus VRFs:
Afaik there are no known sensible VRF signatures based upon lattices or multivariate quadratics, but single layer hash-based signatures provide VRFs. We should provide grant money to polish one of these options, probably one layer XMSS, but maybe academics should fold in optimizations from Sphincs+ or whatever.
These are problematic because secret keys must be gradually erased as they get used, which requires reforming the keystore design for secret key erasure, and automatic rotation & recertification by the node in a speedy-ish key rotation schedule.
I’ve proposed some flavor of mutable keys in the keystore in the nugget BLS crate, simply because BLS12-381 lacks established constant-time implementations. It’s not really the same problem though, as larger keystore changes arise from key erasure.
Ring VRFs:
We’d need lattice based or hash based zk proofs to have post-quantum soundness in ring VRFs, but our fast zk continuation have one flavor which gives fairly efficient post-quantum anonymity without post-quantum soundness.
Internally, we’ll discuss how important post-quantum anonymity vs soundness is in sassafras. We definitely envision doing the post-quantum anonymous ring VRF flavor anyways since voting applications could benefit from post-quantum anonymity.
We could provide a grant for doing ring VRFs in post-quantum zero-knowledge proofs
Transport layer:
We’ll just follow everyone else as they attempt to deploy post-quantum KEMs in Kyber in TLS 1.3. We’re sadly using Noise not TLS 1.3 but simply copying those efforts remains sensible.