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?
rcxdude•44m ago
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)
chadgpt3•15m ago
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.
some_furry•2m ago
> You use both a quantum-safe algorithm and a classical algorithm, encrypting your data twice and remaining secure if either one is broken.
No. Don't do that.
If you encrypt your data twice, and one of them is broken by a quantum computer, the adversary gets the plaintext anyway.
You want a Hybrid KEM, not encrypting twice. The nuance matters.
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.
BoppreH•36m ago
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.
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)
tsimionescu•34m ago
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.
Cider9986•30m ago
Would post-quantum encryption also be harder for regular computers to crack?
kibwen•22m ago
> 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
BoppreH•27m ago
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.
kibwen•27m ago
> 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.
2close4comfort•16m ago
I too was wondering how they feel about the potential downsides which is not really mentioned.
chadgpt3•14m ago
Those are the only two known algorithms that have this property.
lukan•49m ago
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?
rcxdude•44m ago
(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)
chadgpt3•15m ago
some_furry•2m ago
No. Don't do that.
If you encrypt your data twice, and one of them is broken by a quantum computer, the adversary gets the plaintext anyway.
You want a Hybrid KEM, not encrypting twice. The nuance matters.
https://durumcrustulum.com/2024/02/24/how-to-hold-kems/
n4r9•39m ago
BoppreH•36m ago
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.
thenthenthen•35m ago
fxwin•35m ago
tsimionescu•34m ago
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.
Cider9986•30m ago
kibwen•22m ago
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