Interesting development. Merkle Tree Certificates throw away decades of cruft, but also decades of battle testing and ancillary tools. I trust the teams involved, but this will be a hell of a project.
Still better than the alternatives that would saddle us with worse performance for ~ever.
Better encryption sounds good to me in general, but I don't really understand, how we can make quantum safe encryption, when we don't know yet, what capabilities it will have (or if it is possible at all).
I am obviously not in the field, but as far as I know, no QC is close of working for a practical purpose(aside quantum research), but to make it practical, it needs a groundbraking brakethrough of some sort. But if a brakethrough happens, can we really estimate the consequences?
The capabilities of quantum computing, in theory, are pretty well known. There's basically a few extra operations which can be done efficiently on it and so that can be built into the threat model, even if no-one's built a quantum computer yet.
(Of course, basically all encryption, especially asymmetric encryption, is predicated on there not being some as-yet-undiscovered exploitable structure to the mathematics on which it is built. Modern cryptography, AFAIK, tends to have some decent arguments for why this is not expected to be the case, but it's never completely proven top-to-bottom outside of fairly niche/trivial cases. It's always in principle possible that someone discovers an attack on these new algorithms, classical or quantum)
Supersingular Isogeny Key Exchange is one that was invented to be quantum-safe but turned out to be unsafe at any speed, so hybrid encryption is still a good idea. You use both a quantum-safe algorithm and a classical algorithm, encrypting your data twice and remaining secure if either one is broken.
By this standard, there is no current encryption method (except for pre-shared one time pads when used correctly) that is known to be unbreakable. For example, it is not proven that prime factoring can't be done much more efficiently on a classical computer - for all we know, it's possible that tomorrow someone will come up with a novel algorithm that can break RSA in just a small number of operations. Same is true for elyptic curves - we don't have any mathematical proof that it's impossible for a much better algorithm than the currently known ones is possible.
However, just like for RSA we know that the problem of efficient integer factoring has been worked on for a long time with no progress, the same is true for quantum computing. We have been trying to figure out quantum algorithms for a great number of problems that are hard for classical computers for a long time now, and we haven't been able to, except for the ones that we have. Mathematicians have also developed certain intuitions for which problems have characteristics that make them potentially easier to solve on a QC and which don't.
In general, just like with P=NP?, we haven't proven yet if BQP, roughly the class of problems which have efficient QC versions, is equal or not to P, the class of problems that can be efficiently solved on a classical computer; and we also don't know if BQP=NP.
So yes, there is at least a theoretical possibility that the problems used for creating post-quantum encryption will turn out to be in BQP, will turn out to have an efficient quantum algorithm that solves them. But that would come from mathematical research, it is entirely unrelated to creating and tinkering with actual quantum computers. The math of quantum algorithms is currently far ahead of the engineering and physics on building the actual computers.
> except for pre-shared one time pads when used correctly
The relevant property here is known as "information-theoretic security", and I'm not sure if one-time pads are the only way to achieve it, e.g. Shamir's secret sharing also has this property (although the use case is slightly different): https://en.wikipedia.org/wiki/Information-theoretic_security
To answer your "if it's possible at all" question: it's full of hard engineering problems, but none of it looks unsolvable, and the investments are there.
And even if there was only a 10% chance of QC breaking crypto, the community is not comfortable with a 10% chance of such a catastrophic scenario.
This is part of my day job, so here's another interesting fact: for migrating encryption use cases, you have to consider that attackers can capture your encrypted data today to break in the future. So, as a rule of thumb, your migration timeline is much shorter for encryption than for signatures.
The problem is perhaps more theoretical than you might think. The security of post-quantum schemes basically comes down to the fact that researchers have thought long and hard about whether there are efficient classical or quantum algorithms to solve a given problem, and haven't found any yet. That's not necessarily anything new. Even RSA is predicated on no one having a fast factorisation algorithm.
Well similar to how turing machines are a sufficient theoretical model to make all kinds of arguments about runtime complexity of classical computers without relying on their actual physical implementation, we have theoretical models for the way we are approaching quantum computation that do the same thing (Namely the quantum circuit model)
> In the common case, the entire authentication path in an MTC handshake is one signature, one public key, and one inclusion proof. That’s smaller than today’s Web PKI handshake, even though MTCs use post-quantum algorithms. [...] There is more to MTCs than size optimization. Because every certificate is part of a published Merkle tree, transparency becomes a property of issuance itself. Today’s Certificate Transparency ecosystem is bolted on after the fact: certificates are issued by CAs, then logged separately, with extra signatures riding along in the TLS handshake to attest to that logging. With MTCs, a certificate cannot exist outside the Merkle tree. Certificate Transparency is built in.
These upsides seem extremely promising, but I'm curious to know if there are any notable downsides as well.
Still better than the alternatives that would saddle us with worse performance for ~ever.
I am obviously not in the field, but as far as I know, no QC is close of working for a practical purpose(aside quantum research), but to make it practical, it needs a groundbraking brakethrough of some sort. But if a brakethrough happens, can we really estimate the consequences?
(Of course, basically all encryption, especially asymmetric encryption, is predicated on there not being some as-yet-undiscovered exploitable structure to the mathematics on which it is built. Modern cryptography, AFAIK, tends to have some decent arguments for why this is not expected to be the case, but it's never completely proven top-to-bottom outside of fairly niche/trivial cases. It's always in principle possible that someone discovers an attack on these new algorithms, classical or quantum)
However, just like for RSA we know that the problem of efficient integer factoring has been worked on for a long time with no progress, the same is true for quantum computing. We have been trying to figure out quantum algorithms for a great number of problems that are hard for classical computers for a long time now, and we haven't been able to, except for the ones that we have. Mathematicians have also developed certain intuitions for which problems have characteristics that make them potentially easier to solve on a QC and which don't.
In general, just like with P=NP?, we haven't proven yet if BQP, roughly the class of problems which have efficient QC versions, is equal or not to P, the class of problems that can be efficiently solved on a classical computer; and we also don't know if BQP=NP.
So yes, there is at least a theoretical possibility that the problems used for creating post-quantum encryption will turn out to be in BQP, will turn out to have an efficient quantum algorithm that solves them. But that would come from mathematical research, it is entirely unrelated to creating and tinkering with actual quantum computers. The math of quantum algorithms is currently far ahead of the engineering and physics on building the actual computers.
The relevant property here is known as "information-theoretic security", and I'm not sure if one-time pads are the only way to achieve it, e.g. Shamir's secret sharing also has this property (although the use case is slightly different): https://en.wikipedia.org/wiki/Information-theoretic_security
And even if there was only a 10% chance of QC breaking crypto, the community is not comfortable with a 10% chance of such a catastrophic scenario.
This is part of my day job, so here's another interesting fact: for migrating encryption use cases, you have to consider that attackers can capture your encrypted data today to break in the future. So, as a rule of thumb, your migration timeline is much shorter for encryption than for signatures.
These upsides seem extremely promising, but I'm curious to know if there are any notable downsides as well.