Opinions differ about the possibility of practical quantum computers that can easily break elliptic curve cryptography. However, if there is a breakthrough, it could be an existential threat. Since it will take some time to transition, it seems prudent to put a high priority on alternatives.
Is there any momentum towards a particular default post-quantum signature scheme for Ethereum?
Is XMSS popular among the research team? ( https://tools.ietf.org/html/rfc8391 )
I realize account abstraction can make the choice of signature scheme flexible, but most users will still want a default that protects them as much as possible.
It is believed that Lamport signatures are Quantum secure. Unfortunately, each Lamport key can only be used to sign a single message. However, combined with hash trees, a single key could be used for many messages, making this a fairly efficient digital signature scheme.
Size issues:
The size of Lamport public key and signature together is 231 times (106 bytes vs 24KB) more than the ECDSA public key and signature.
The public key and signature form part of each bitcoin transaction and are stored in blockchain. So use of Lamport Signature will need 231 times more storage than ECDSA.
Lamport is too large to be practical; you want Winternitz signatures (I much prefer Karl Gluck’s more descriptive name “hash ladder signatures”). You can get those down to 1 KB or less (and then you can add a hash tree to make them multi-use).
If you want a “stateless” signature scheme then I believe the state of the art is SPHINCS, where signature sizes come out to ~40 kB AFAIK, though you may be able to do better these days by adapting a STARK.
SPHINCS is state of the art only among hash-based signatures.
While it’s simple and reliable, I would look into more powerful platforms,
the best option is lattice-based cryptography. You can implement almost any cryptographic constructions using lattices, e.g. if you want to support some privacy-preserving mechanisms, or group signatures, whatsoever. So probably it makes more sense to look into it.
I am no expert but it seems there may be attack vectors with current stateless post-qc methods. I know BLISS is vulnerable to side channel attack, and it seems like SPHINCS is also vulnerable to attacks which XMSS is not.
I hear you Pratyush , thanks for your reply. I’m aware of this information : In [44], Shor presented two polynomial time quantum algorithms, one for factoring integers, the other for computing discrete logarithms in finite fields. The second one can naturally be applied for computing discrete logarithms in the group of points on an elliptic curve defined over a finite field.
It is well known in computer science that quantum computers will break some cryptographic algorithms , especially the public-key crypto-systems like RSA , ECC and ECDSA that rely on the IFP (integer factorization problem), the DLP (discrete logarithms problem) and the ECDLP (elliptic-curve discrete logarithm problem). Quantum algorithms will not be the end of cryptography, actually can be a cure to current problems of security and scalability. There is dedicated work to build quantum-secure robust crypto-systems.
Hi, here is our proposal about adding a new transaction type to the EVM to achieve a hybrid post quantum digital signature, in line with NIST latest PQ standardisation. Details in this post and full proposal here.
At Pauli Group we created an EVM smart contract wallet that requires a Lamport signature (with decentralized verification) to execute transactions. This is fully quantum resistant and can be used to protect digital assets over the long term. You can read our roadmap for more advanced quantum resistant smart contracts in our whitepaper.
The network will still have to upgrade to post-quantum signatures (like Falcon or Dilithium) but at least it’s now possible to start upgrading the quantum vulnerable ECDSA wallets now.