Algorand's post-quantum crypto plans

General
1

Hi Algorand Community,

I already communicated with the Algorand foundation, so I also show their helpful answer below my questions:

How do you plan to address the post-quantum world? Our Algorand hardware wallet has a public key which I am assuming is based on Bernstein’s 25519 elliptic curve (Montgomery elliptic curves). As you know, there is a variant of Shor’s algorithm that can break these public keys with sufficient quantum computing resources. That means that a quantum computer could at some time in the future start with my public key and compute my private key and then send our ALGOs somewhere else.

Do you plan to use McEliece or lattice-based post-quantum crypto?
How will that transition work?

It is true that the cryptographic primitives currently used on Algorand are not
secure against a large enough quantum computer. There are two main places
where non-post-quantum signature schemes are used:

a. In the consensus protocol: for participation nodes to sign votes and
block proposals.

b. When transacting: to sign transactions for your accounts.

Regarding (a), the soon-to-be-available state proofs (previously
called compact certificates) will be based on post-quantum primitives
such as Falcon (New participation keys by id-ms · Pull Request #57 · algorandfoundation/specs · GitHub
[2]). This will allow post-quantum checkpoints / proofs of the
blockchain state.

Regarding (b), post-quantum signature schemes are not yet supported
but will be supported way before quantum computers will be able to
break ED25519 signatures. Algorand already has a mechanism to upgrade
keys: rekeying, which will make the transition quite smooth.

Do not hesitate to post such questions on forum.algorand.org as
answers can help the whole community.

Best,
The Algorand Foundation Team

1 Like
2

Hi, I made this Post a while back, which may be helpful. I think generally, Algorand is a quantum secure technology. There still aren’t quantum computers capable of inverting SHA-256 or running Shor’s Algorithm.

Probably the biggest security risk would be a random passphrase generator. Even still, such a generator would take a really long time to break into an account. And the account it would break into would be random. I am not sure current quantum computers would even offer a speedup here. In large part, this will depend on the performance improvement of adiabatic quantum computers or photonic circuit boards because gate model quantum computers are very slow to scale.

Thanks!

1 Like