6 ms·

> I don't think that follows from the published attack at all. Maybe not - but from a layman perspective, the fact that a supposedly quantum-computing-proof al

> I don't think that follows from the published attack at all. Maybe not - but from a layman perspective, the fact that a supposedly quantum-computing-proof algorithm isn't even classical-computing-proof does sound worrying. Imagine someone said a cage is tiger-proof but then a house cat goes and destroys it in an hour :) I guess the field will take a long time to mature, which is OK since practically useful quantum computers are probably far from being available.

Karellen 4y ago
> then a house cat goes and destroys it or just squeezes out between the bars. "Wait, that's cheating..."
RHSeeger 4y ago
I read all this more as > We should try to come up with Tiger-proof cages > This one might work > Nope, it fails in this way > Ok, onto the next idea....
gizmo686 4y ago
In some sense, the field of classical cryptography has never matured. Outside of some very simple and limited applicability systems (e.g. one time pads), the field has never really moved beyond 'propose a cipher, and act as if it is secure until proven otherwise'. For all we know, all of the algorithms that are weak to quantom computers are also vulnerable to classical ones as well.
- Karellen 4y ago
  If the fact that no-one has yet come up with a way to either solve a particular mathematical problem (e.g. factorisation in polynomial-or-better time), or to prove that no such solution exists, means that a field has never matured, then you could say that the entire field of mathematics has never matured, because e.g. the Goldbach Conjecture has never been either proven or disproven. Taking that line of reasoning further, given Godel's Incompleteness Theorem you could say that mathematics as a field will never have matured.
  - jancsika 4y ago
    It doesn't seem elucidating to make an analogy between a thing-- math-- and it's own subset-- crypto. Worse, crypto is defined by essentially having the added requirement to at least not be the weakest link in keeping jewels locked in a safe. In that sense the addition of axioms becomes a liability in a way they are not in broad math. Put another way, math as a field was able to mature because it lacked this hard requirement that crypto has. If mathematicians suddenly decided add this requirement of jewel-keeping to math broadly then-- bam-- math instantly becomes the same "immature" field that crypto currently is.
    - Shorel 4y ago
      Well, math was that "immature" field in the XVI century: https://www.quantamagazine.org/the-scandalous-history-of-the-cubic-formula-20220630/ https://www.quantamagazine.org/the-scandalous-history-of-the...
- credit_guy 4y ago
  That's not how it works. The central tenet is that you consider a cipher secure if you can prove mathematically that breaking that cipher is equivalent to solving a difficult problem, such as the factorization of a large composite number.
  - gizmo686 4y ago
    We don't even know if difficult problems exist; at least in a way that is useful to cryptography (e.g. become easy once you know a small shared secret). We have some problems (factorization, and discrete log) that no one has found a way to efficiently solve on a Turing machine; but we don't really have a solid reason to think these problems are difficult. All we know is that our best mathamaticians have been stuck on them for generations. The bigger problem is that even these reductions to assumed difficult problems represent only a small portion of cryptography. We prove things like AES and SHA512 are secure by publishing them and waiting a few years to see if anyone publishes a break. No meaningful reduction to well researched problems, just a hope that we wont discover we missed something after making it a standard.
Nomentatus 4y ago
Yes it's worrying, but math is shockingly empirical because new and surprising discoveries happen (and did in this case re a novel genus-1 and genus-2 curve relationship.) Which means that the risk mentioned isn't limited to these particular new systems for cryptography. But I'll take your side to some extent - there are provably unbreakable systems such as one-time pads (with heavy trade-offs!) and other angles that we should probably be considering using more than we do.
thomaslord 4y ago
The tiger / housecat analogy is great for this context! Even if a tiger fit in the housecat's cage it could easily rip it apart, while a housecat could slip between the bars of a tiger's cage easily.

Karellen 4y ago

> then a house cat goes and destroys it or just squeezes out between the bars. "Wait, that's cheating..."

RHSeeger 4y ago

I read all this more as > We should try to come up with Tiger-proof cages > This one might work > Nope, it fails in this way > Ok, onto the next idea....

gizmo686 4y ago

In some sense, the field of classical cryptography has never matured. Outside of some very simple and limited applicability systems (e.g. one time pads), the field has never really moved beyond 'propose a cipher, and act as if it is secure until proven otherwise'. For all we know, all of the algorithms that are weak to quantom computers are also vulnerable to classical ones as well.

Karellen 4y ago
If the fact that no-one has yet come up with a way to either solve a particular mathematical problem (e.g. factorisation in polynomial-or-better time), or to prove that no such solution exists, means that a field has never matured, then you could say that the entire field of mathematics has never matured, because e.g. the Goldbach Conjecture has never been either proven or disproven. Taking that line of reasoning further, given Godel's Incompleteness Theorem you could say that mathematics as a field will never have matured.
- jancsika 4y ago
  It doesn't seem elucidating to make an analogy between a thing-- math-- and it's own subset-- crypto. Worse, crypto is defined by essentially having the added requirement to at least not be the weakest link in keeping jewels locked in a safe. In that sense the addition of axioms becomes a liability in a way they are not in broad math. Put another way, math as a field was able to mature because it lacked this hard requirement that crypto has. If mathematicians suddenly decided add this requirement of jewel-keeping to math broadly then-- bam-- math instantly becomes the same "immature" field that crypto currently is.
  - Shorel 4y ago
    Well, math was that "immature" field in the XVI century: https://www.quantamagazine.org/the-scandalous-history-of-the-cubic-formula-20220630/ https://www.quantamagazine.org/the-scandalous-history-of-the...
credit_guy 4y ago
That's not how it works. The central tenet is that you consider a cipher secure if you can prove mathematically that breaking that cipher is equivalent to solving a difficult problem, such as the factorization of a large composite number.
- gizmo686 4y ago
  We don't even know if difficult problems exist; at least in a way that is useful to cryptography (e.g. become easy once you know a small shared secret). We have some problems (factorization, and discrete log) that no one has found a way to efficiently solve on a Turing machine; but we don't really have a solid reason to think these problems are difficult. All we know is that our best mathamaticians have been stuck on them for generations. The bigger problem is that even these reductions to assumed difficult problems represent only a small portion of cryptography. We prove things like AES and SHA512 are secure by publishing them and waiting a few years to see if anyone publishes a break. No meaningful reduction to well researched problems, just a hope that we wont discover we missed something after making it a standard.

Nomentatus 4y ago

Yes it's worrying, but math is shockingly empirical because new and surprising discoveries happen (and did in this case re a novel genus-1 and genus-2 curve relationship.) Which means that the risk mentioned isn't limited to these particular new systems for cryptography. But I'll take your side to some extent - there are provably unbreakable systems such as one-time pads (with heavy trade-offs!) and other angles that we should probably be considering using more than we do.

thomaslord 4y ago

The tiger / housecat analogy is great for this context! Even if a tiger fit in the housecat's cage it could easily rip it apart, while a housecat could slip between the bars of a tiger's cage easily.