Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Post-Quantum Future for Let's Encrypt

letsencrypt.org

Post reply on HN
Print view View original

41–50 of 175 posts

Re: A Post-Quantum Future for Let's Encrypt

#41

Post by saltcured »

some_furry wrote: post #30
3form wrote: post #27

Earlier quoted context omitted.

It seems to me you assumed that the poster that replied to you meant encrypting in parallel, while it seems pretty clear to me what they meant was c = E1(E2(p, k2), k1).

The thing is: Quantum computers don't break AES-GCM, ChaCha20-Poly1305, or any other modern authenticated cipher. Layering encryption or doing cipher cascades is pointless. The thing a cryptography-relevant quantum computer does is break RSA and elliptic curve cryptography, so that the underlying key (k1 or k2) is recoverable from its corresponding public component. Hybrid KEMs, such as mlkem768x25519 (a.k.a. X-Wing)…

Are you saying that a "hybrid KEM" is different in theoretical risk from chaining two KEMs? The change of jargon from "encryption" to "KEM" doesn't mean anything to most people talking about this post-quantum risk. To the extent we know what KEM is, we think it is just encrypting the key used for the rest of the bulk encryption.

Whether or not people understand the nuance of encrypting the block cipher keys or encrypting the blocks themselves, I think we all mean to stack the two encryption methods for defense-in-depth protection. They intuit having to open two locks in series to get to the valuable stuff, not adding two different access paths that each suffice for access.

Re: A Post-Quantum Future for Let's Encrypt

#42

Post by hylaride »

lukan wrote: post #2

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…

It's essentially the laws of physics. To oversimplify, Quantum computing can essentially do certain kinds of operations extremely fast (like factoring prime numbers) because it can calculate all the permutations almost instantly. But if you add intentional complexity to it in ways that all those states can't be "seen" then the quantum computer falls flat. That's one of the issues with adding post-quantum algorithms, they're by design less efficient in certain ways, meaning slower and/or with more overhead.

The way a quantum mechanics PhD explained it to me years ago in layman's terms is similar to nuclear science. We "knew" that a nuclear explosion was possible before a bomb was created and what conditions it would work. The Nagasaki bomb was a completely different type of bomb than the trinity test and Hirosima, plutonium instead of uranium, and it was never even tested before it's first use!

Re: A Post-Quantum Future for Let's Encrypt

#43

Post by tptacek »

kibwen wrote: post #32
Cider9986 wrote: post #9

Earlier quoted context omitted.

Would post-quantum encryption also be harder for regular computers to crack?

This is precisely the uncertainty that the commenter above was referring to when they mentioned complexity classes like BQP. We don't necessarily know the precise relationship between quantum complexity classes and their classical counterparts.

There is more certainty about the resilience of lattice cryptography to classical attack than there was about Curve25519's resilience when it was introduced. Lattice schemes weren't invented as PQC schemes; they were invented as faster classical schemes. In the 1990s, there was a live debate about whether lattices might be the successor to RSA, not curves.

Re: A Post-Quantum Future for Let's Encrypt

#44

Post by mswphd »

connorboyle wrote: post #22
tsimionescu wrote: post #8

Earlier quoted context omitted.

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 f…

Has there been "no progress" on classical prime factorization? What about the AKS primality test, a polynomial-time algorithm to test the primality of a number, published in 2002? (This is not my field of expertise; I'm genuinely curious if there's a good reason to discount this as progress towards efficient prime factorization)

Primality testing was essentially solved in the 70s with Miller-Rabin. AKS made that (randomized) algorithm deterministic, albeit at much higher (polynomial) running-time.

For your overall question, the current record-holders for integer factorization wrote a paper on this a few years ago that is probably a good reference

https://hal.science/hal-03691141/file/cryptography.pdf

The (rough) outline of the paper is that

1. theoretically there's been no progress on factoring in ~30 years

2. practically, there have been both improved hardware + efficient implementations driving the progress. They estimate that current nation-states can (classically) break RSA-1024. The cost would be approximately 500,000 core-years of computation. At current cloud prices this is doable on aws for 3. attacks against factoring use a technique ("index calculus") that can also be used to attack finite-field discrete logarithm. There were significant advances on that problem in the 2010s (at least for certain parameters, namely the "small characteristic" setting). An easy way to communicate this is that the RSA factoring record is ~830 bits, while the binary-field discrete logarithm record is > 30,000 bits. These significant advances have not been able to be ported over to factoring, nor have they been ported over to medium/large-characteristic discrete logarithm. It is a (very upsettingly) large open question of whether similar-magnitude improvements are possible more generally for index calculus algorithms.

Re: A Post-Quantum Future for Let's Encrypt

#45

Post by mswphd »

Cider9986 wrote: post #9
tsimionescu wrote: post #8

Earlier quoted context omitted.

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 f…

Would post-quantum encryption also be harder for regular computers to crack?

It's not particularly related. We have efficient quantum algorithms for RSA and discrete logarithms. Both are solved by viewing them as instances of the "hidden subgroup problem" over an abelian group.

Some well-known other problems are also HSP instances over non-abelian groups, for example

1. the learning with errors assumption (the main PQ thing people like) is a HSP instance over the dihedral group, and

2. graph-isomorphism is a HSP instance over the symmetric group.

LWE appears to be quite hard classically (SOTA attacks are 2^{~0.3n} time and exponential memory). Graph isomorphism is a famously easy problem outside of P, namely it is in quasi-polynomial time. So the fact that both are not in BQP doesn't say much about their relative classical difficulty.

Re: A Post-Quantum Future for Let's Encrypt

#46

Post by kibwen »

zeroonetwothree wrote: post #21
kibwen wrote: post #12

Earlier quoted context omitted.

> 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

Isn’t one time pad just a simple version of secret sharing?

I would say that SSS is a generalization of OTP, but OTP in practice is so dramatically and unbelievably simpler than SSS that it's not practically useful to consider it as "just" a special-case of SSS. Which is to say, if you were implementing OTP, you would not just implement SSS and then set the right parameters; you would use an entirely distinct implementation.

Re: A Post-Quantum Future for Let's Encrypt

#47

Post by mswphd »

zeroonetwothree wrote: post #21
kibwen wrote: post #12

Earlier quoted context omitted.

> 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

Isn’t one time pad just a simple version of secret sharing?

you can sort-of view it that way, but it's not particularly useful. There are settings where you can view (steps of) a cryptographic algorithm as applying a one-time pad with a pseudorandom pad (say counter-mode encryption for the most obvious example, though it appears elsewhere as well).

Alternatively, shamir's secret sharing can be extended to threshold settings pretty easily. So you can write a generalized scheme where you only recover things when "enough people" (but perhaps not everyone) tries to reconstruct. This generalized scheme doesn't look particularly like the one-time pad.

So they end up coinciding in the 2-party case over F2 but it seems to be mostly a coincidence.

Re: A Post-Quantum Future for Let's Encrypt

#48

Post by tialaramex »

skmurphy wrote: post #34

We are truly living in a science fiction future where quantum code cracking is not a remote possibility but a near term risk we are planning for. In Vernor Vinge's novel "A Fire Upon the Deep" one of the most valuable commodities were one time pads that are physically transported to communication nodes to enable unbreakable communication. The pads are split into three pieces that are XORed to create the actual pad to…

But that's a miss, it's like one of those Neal Stephenson moments where the creator is using the right language (so it's not like reading William Gibson who clearly has no idea and knows it - he's going for the emotional feel not the technology) but they don't understand what's actually going on.

OTP is in theory the correct choice if you don't have working symmetric cryptography but in fact the "Quantum computer" approach barely dents our symmetric cryptography.

I've written about this before, DES was standardized in 1977, almost 50 years ago and you might think "Well but DES is broken". Yes, DES broke exactly the way it was designed to. Literally nothing went wrong, when it was standardized we knew the keys are too small (yup, you can break it by trying all the keys) and the blocks are too small (yup, you can "just" make duplicate blocks) and it was broken by leaning on these weaknesses with huge fast modern computers.

AES is an entirely different cryptosystem, but the two most important choices were that the keys are big enough (128-bit or 256-bit commonly) and the blocks are too (128 bits). And those may seem like a small upgrade, only 2-4x as big, who cares? Well those are bit lengths so that's an exponential increase, and your quantum computer barely helps (assuming it magically is the same price rather than incredibly expensive). It is not physically practical for the necessary computation to be done, AES is broken only if there's some mathematical backdoor we didn't know about.

"We'll crack AES with a quantum computer" is a Hollywood movie plot, it's not a thing that makes any actual sense.

[Edited: I wrote "Bruce Sterling" but I meant "William Gibson", I apologise to both people for muddling them, though not for my opinion]

Re: A Post-Quantum Future for Let's Encrypt

#49

Post by mswphd »

hylaride wrote: post #42
lukan wrote: post #2

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…

It's essentially the laws of physics. To oversimplify, Quantum computing can essentially do certain kinds of operations extremely fast (like factoring prime numbers) because it can calculate all the permutations almost instantly. But if you add intentional complexity to it in ways that all those states can't be "seen" then the quantum computer falls flat. That's one of the issues with adding post-quantum algorithms,…

this is not an accurate description/heuristic of how quantum computing works. It would predict quantum computers can solve problems that they cannot solve. For a more accurate account see e.g.

https://www.quantamagazine.org/thirty-years-later-a-speed-bo...

And the post-quantum algorithms are not by design less efficient either. For example, RLWE-based schemes are more cycle-efficient than elliptic curve schemes. They're not uniformly more efficient (key/ciphertext sizes are generally longer), but this has nothing to do with intentional design choices to make them post-quantum secure. Just different things are different.

Re: A Post-Quantum Future for Let's Encrypt

#50

Post by hylaride »

mswphd wrote: post #49
hylaride wrote: post #42

Earlier quoted context omitted.

It's essentially the laws of physics. To oversimplify, Quantum computing can essentially do certain kinds of operations extremely fast (like factoring prime numbers) because it can calculate all the permutations almost instantly. But if you add intentional complexity to it in ways that all those states can't be "seen" then the quantum computer falls flat. That's one of the issues with adding post-quantum algorithms,…

this is not an accurate description/heuristic of how quantum computing works. It would predict quantum computers can solve problems that they cannot solve. For a more accurate account see e.g. https://www.quantamagazine.org/thirty-years-later-a-speed-bo... And the post-quantum algorithms are not by design less efficient either. For example, RLWE-based schemes are more cycle-efficient than elliptic curve schemes. They…

Fair. I was quoting from memory from maybe 5 years ago.
Post reply on HN