How to easily make Aptos post-quantum secure

tl;dr: “All is well. All is well.” – Ranchoddas Shamaldas Chanchad

I tend to get the “Is Aptos post-quantum (PQ) secure?” or “Can Aptos be made PQ-secure?” questions very often.

This post should serve as a good, initial answer. (I will evolve it in time.)

Post-quantum (PQ) Aptos

Like all other blockchains that I know of, Aptos is currently not PQ-secure: it simply does not make sense to pay the cost of doing PQ crypto given what we know about scalable quantum computing.

Nonetheless, upgradeable chains like Aptos can be easily made almost-fully PQ-secure.

How?

1. Assuming the BHT attack on hash functions does not actually scale in practice¹, hash function length can be kept the same.
2. Consensus BLS multi-signatures can be changed to a PQ variant via a simple protocol upgrade. The Ethereum Foundation has done a lot of great work on this lately²
3. We can add support for a new PQ-secure signature scheme. This way, new users are protected. Many interesting work in this space. Unclear what the best answer is. Personally, I like the idea of combining a post-quantum zkSNARK scheme with a one-way function (OWF) to get a signature scheme in a clean way.
4. Ed25519 signatures can be easily transformed into PQ-secure ones: the Ed25519 SK $\sk$ is derived from some secret bits $b$ via a hash function as $\sk = H(b)$. So even if a quantum computer obtains $\sk$ by computing a discrete log on the public key, we can nonetheless rely on the secrecy of the bits $b$ induced by the one-way hash function $H$. Then, we can do a PQ signature using $b$ as the secret key and $H(b)$ as the public key³.
5. Key rotation in Aptos requires a ZKPoK of the new secret key being rotated to. This can also be done using a post-quantum zkSNARK.
6. Keyless ZKPs can be transitioned to a PQ-secure zkSNARK (lattices, code-based, etc.)
7. Aptos randomnes will require a post-quantum DKG and VRF. PQ-DKGs are an emerging area of research⁴$^,$⁵$^,$⁶. And there are lattice-based key-homomorphic PRFs⁷ that could be very useful for obtaining a PQ-VRF⁸.

I may have missed stuff. Please let me know!

ECDSA signatures: the bane of my existence

There will be a problem with ECDSA signatures, since their secret keys are not derived in an Ed25519-like manner. As a result, the full secret key would be known to a quantum adversary. (Unlike in Ed25519.)

Nonetheless, ECDSA accounts can be manually rotated to a PQ-secure account by their owners, once it is well-known that a quantum computer exists.

Unfortunately, not everyone will be aware of the quantum threat. As a result, some inactive users will likely have their accounts stolen.

But, we would hope this number can be minimized as we work on increasing public awareness of the quantum threat.

Come to think about it, perhaps the BIP-39 and BIP-32 key deivation mechanism (from a 12-word or 24-word mnemonic down to an ECDSA secret key) can be leveraged to handle the problem in ECDSA as well, in a similar manner to Ed25519? One difficulty will be the large # of PB-KDF2 iterations in BIP-39.

Conclusion

“Keep calm and deploy cutting-edge cryptography.”

Of course, this post does not address two fascinating questions:

1. How efficient would a post-quantum Aptos be?
   • Let’s see; this is a growing area of research!
   • Encouraging that some PQ crypto can actually be faster, in some cases.
     • WHIR
     • Merkle-hashing with the Ajtai hash function
2. How much time it would take to make these changes?
   • Perhaps this is not as interesting to discuss: it really depends on engineering resources allocated.
   • Plus, my sense is that there would be more than enough time:
     • We’d see how fast quantum computers improve,
     • We’d predict the date by which we’d need to be ready,
     • We’d allocate all resources to ensure we are ready.

Acknowledgements

Thanks to Dan Boneh for encouraging me to write this.

References

For cited works, see below 👇👇