Super cool work on the NTT precompile @rdubois-crypto. Just purely evaluating PQ signatures by EVM verification gas cost, I think one would choose WOTS+ (cca. 200k gas). One-time signatures (OTS) have already allowed us to survive in a post-quantum world since one can always sign the public key of the next transaction. Though, OTSs do not allow, for instance, “replace by fee” mechanism, since one would need to sign with the same secret key multiple times. Therefore, transactions could get stuck in the mempool, as this was previously observed in the Bitcoin community. I believe XMSS is on par with Falcon in terms of verification gas cost. I also think that MAYO (and possibly other 2nd round NIST contenders as well) might be good candidates given the upcoming EVM upgrades, e.g., SIMD operations for the EVM or EOF.
(lol. just realised that @CPerezz already brought this up above)
I want to bring in a new perspective to evaluate/benchmark PQ signature schemes that previously (at least not in this thread) were not considered in detail. It might be worthwhile to anticipate that people also want to use these signature schemes in (zero-knowledge) proof systems to prove various statements. So, it would also be interesting to evaluate the ZK/MPC circuit-friendliness of the above-discussed verification algorithms and, put differently, how amenable they are to proof systems. I’d assume that hash-based signatures will compose well with hash-based proof systems, while FALCON and DILITHIUM may perform better when proven with lattice-based proof systems. (???) It’d be cool to have a concrete analysis on this.
gas perspective is not fair, because hash functions used in the OTS are underpriced. When moving to a node implementation, the comparizon reflect the computational effort in client, which correspond to the effort for the network.
NTT can be implemented very efficiently in ZK. There also efficient MPC version like Musig-L for lattice candidates benefiting from the structure and not a “generic MPC compiler” working at gates level.
Looking at what the IACR community is pushing, lattice gonna be the future of ECC for web2. While NIST made another call to avoid to rely on a single technology, it seems like the way to go.
Also since last threads, we reduced the FALCON verification close to 2.5M, with SIMD, we will be able to be lesser than the 200k by vectorizing the operations (16 chunks of 16 bytes in a word).
This is why we remove gas costs all together. Or at least thats what I did with DSM. If you see my most recent recent post, you’re trying to solve problems that are already solved. Maybe just not in this platform really though if it’s solved. It’s solved… I’m using Sphincs+ with zero gas cost, and not a single worry about the overhead I handle it gracefully. Oh well, I think this is normal where we as a society keep trying to patch something up that maybe should just migrate.
I wish everyone a long, happy life, but no one here will live to see this fork. I’m glad though some people make money and feel they’re doing something important—life is a game, after all. If blindly subscribing to a false conspiracy of a “quantum disaster” makes people happy, let them do it.
Decoherence effects are EXPONENTIAL with time and size.
The quantum computing hype train, especially in the context of breaking cryptography (like Shor’s), has been rolling for decades now with zero tractrion. Lab setups can maybe maintain coherence for a few microseconds across a handful of qubits — but that’s galaxies away from factoring a RSA key. Decoherence makes quantum systems are unbelievably fragile - we do not have anything on Planet Earth to make this work.
You want to get real security? Focus on the fact that three parties control Ethrereum network so Nakamoto coefficient of ETH DRAMATICALLY dropped after POW to POS switch
It’s way better to be prepared for a post-quantum future and be cryptographically conservative than see an apocalyptic cryptographic disaster.
I like to compare the skepticism behind quantum computing to that of nuclear energy.
In 1939, countless famous scientists were dubious in the late 1930s about the successful application of nuclear fission. For instance, the renowned Sir Henry Tizard (rector of Imperial College London) stated in 1939 that atomic bombs being successfully developed has a 100,000 to 1 chance…we all know what happened in 1945 August 6 and 9.
Who knows…what’s gonna happen? But I would not bet a dime against technological development. So, let’s prepare Ethereum and ourselves for a possible post-quantum future!
Hey guys I have recently released something very relevant to this conversation that I think has been over looked.
I have produced a signature scheme that uses Winternitz at its core where each public key is authorized by revealing a hash preimage in a Lamport chain. This is a tested benchmarked on chain implementation that is currently live at block_opuslux.ar.io, you can create ERC-4337 smart accounts that have full post quantum security. Or you can create EIP-7702 accounts to experience the native EOA upgrade demo (full post quantum security is not possible until EIP-7701 is adopted). Since Winternitz is used at the core of every hash based post quantum signature it is the lightest weight possible signing scheme. Also, by adjusting the w parameter in the Winternitz equation you can produce signatures that range in size from 896B to 2,880B the trade off is the verification time / gas! I would love to get some feedback on my implementation from the ethereum developer community! I believe that this is the optimal signature solution for post quantum security on the blockchain and I would love to talk to any serious developers about it ! You can also read the full outline of WOTS-39 at block_opuslux.ar.io/#/essay where I describe in detail how this works, why it works along with all the details of the implementation. The source code for the wallet is waiting in a private repository, ready to be shared with the community at a moments notice. Thank you all for taking the time to read this comment and consider this option !
I don’t think regular PQC signature schemes have any use in post-quantum blockchains given the general desire to also prove them in zero-knowledge. zkSTARKs can make HMAC asymmetric with a very cheap and simple circuit. The resulting zkSTARK would be larger than a regular PQC signature, but unlike the latter you would be able to aggregate and wrap it inside a larger zkSTARK that proves the whole block. We’re discussing that scheme in this thread and I think that’s what Ethereum will use in the future because you should think about the zero-knowledge roadmap, not just the quantum-safety roadmap. @vbuterin has explicitly written he wants all consumer devices (including low-end ones) to be able to validate blocks in a matter of milliseconds, you need zkSTARKs for that.