[HN Gopher] Breaking 256-Bit Elliptic Curve Encryption with a Qu...
___________________________________________________________________
Breaking 256-Bit Elliptic Curve Encryption with a Quantum Computer
Author : Sami_Lehtinen
Score : 96 points
Date : 2022-02-09 12:57 UTC (10 hours ago)
(HTM) web link (www.schneier.com)
(TXT) w3m dump (www.schneier.com)
| SimonTTTT wrote:
| I wrote about this, it's a long way away. The popular press are
| sucked into the idea that the technology is more capable than it
| is, the community can't shout the boosters down because it's all
| about perception.
|
| https://medium.com/gft-engineering/the-two-quantum-cultures-...
| dijit wrote:
| It's only 1 paragraph but to save someone the click: it's not
| happening soon.
| sliken wrote:
| Indeed, in fact I'd consider that an understatement of the
| situation.
| JulianMorrison wrote:
| Another way of putting it would be "pretty simple and quick -
| if you can achieve a completely infeasible number of qubits".
|
| That is to say, it's an algorithmic overhang, the knowledge how
| is available but held back by not knowing how to achieve the
| hardware needed.
|
| The risk being that someone could discover "how to make qubits"
| tomorrow, and although (because it's hardware) it might take a
| short while to turn that into an industrial qubit pipeline, we
| don't yet actually know yet that it's mechanically impossible
| to do.
| rmbyrro wrote:
| I wouldn't be so certain it's not happening " _anytime soon_ ".
|
| They speculated about one way to break it. There could be several
| ways of using QC to break EC.
|
| What is the chance that at least one of those other ways require,
| say only 1,000 qubits?
|
| Oops, it's a two year time frame now. It might be a small chance,
| but I don't think we can discard it. Better plan for the worse.
| dane-pgp wrote:
| It would be nice to have a probability distribution over how
| quickly quantum computers could reach the necessary level,
| using this paper as just one datapoint and looking at other
| examples of cryptographic breakthroughs and technological
| capability curves.
|
| By combining such a probability distribution with an estimate
| of how much damage could be done (or how much profit could be
| generated) by an enemy breaking elliptic curve encryption, it
| would then be possible to give a reasoned guess for how much to
| spend on bringing forward quantum-resistant cryptography.
| upofadown wrote:
| >What is the chance that at least one of those other ways
| require, say only 1,000 qubits?
|
| A thousand _physical_ qubits with current error rates? Pretty
| much impossible would be my guess.
| [deleted]
| c1ccccc1 wrote:
| Wow, this does not look like an exponentially large number of
| qubits. I thought elliptic curve cryptography was supposed to be
| secure against quantum computers, but this makes it seem like
| cracking is still polynomial, just with a larger constant in
| front than RSA has. Are there any public key techniques that are
| actually secure against quantum computers? (meaning they would
| take exponential time to break using the best known algorithms)
| hatsunearu wrote:
| ECC is more vulnerable to quantum computing than RSA is. That's
| the stated reason why the NSA wants the world to move away from
| ECC to "post quantum cryptography".
| c1ccccc1 wrote:
| Thanks for the correction, seems I was confused. And thanks
| for the pointer to post-quantum cryptography, widipedia has a
| nice list of algorithms.
| throawaybong wrote:
| > it would require 13 x 10^6 physical qubits
|
| It's 13 million qubits. It's weird they write it in scientific
| notation, it makes it look larger. If qubits got to the moore-
| like-bandwagon, that is not many multiplications away from
| current amount.
| dekhn wrote:
| scientific notation would look more like "1.3 x 10*5" (only one
| leading digit: https://en.wikipedia.org/wiki/Scientific_notatio
| n#Normalized...)
| VikingCoder wrote:
| Don't you mean 1.3 x 10 ^ 7?
| black6 wrote:
| Yes. It looks more like engineering notation (up to three
| digits to the left of the decimal and the power of 10
| divisible by 3).
| zinekeller wrote:
| Well, except that the approximate time for an additional
| "stable" qubit is currently plateauing, so outside a very lucky
| breakthrough, it's still unlikely. The official record for an
| actual running Shor's algorithm is 21 (not bits, just the
| number 21), which is still puny (there was an attempt to factor
| out 35 (again 35 as in 5x7), but it ended in failure due to
| quantum noise).
| mburee wrote:
| But Shor's algorithm is for prime factorization, right? Are
| there equally faster algorithms available for elliptic
| curves?
| zinekeller wrote:
| I don't believe there's a publicly-available algorithm
| that's faster than Shor's for breaking EC, and to clarify
| any misconception you can also use Shor's for EC (EC is
| actually easier to break with Shor's than RSA, but EC has
| the advantage of shorter keys for longer brute-forcing
| using known classical methods).
| tromp wrote:
| Shor's algorithm generalizes to any hidden subgroup problem
| for finite Abelian groups [1], which includes integer
| factoring and elliptic curve discrete log.
|
| [1] https://en.wikipedia.org/wiki/Hidden_subgroup_problem
| [deleted]
| sweis wrote:
| I think we are many, many years away from a quantum computer
| being able to break 256-bit ECC:
|
| https://sam-jaques.appspot.com/quantum_landscape
|
| https://www.bsi.bund.de/EN/Topics/Cryptography/QuantumComput...
|
| The current record in factoring with Shor's algorithm is 21. Yes.
| 3*7. That record has stood for 12 years and arguably is not even
| running Shor's because it required a priori knowledge of the
| factors.
|
| Even with "cheating" by using knowledge of the factors, in 20
| years we have seen seen a single bit of improvement.
|
| None of the new quantum computers from IonQ, Google, or QuEra
| with 32-256 qubits are even able to even replicate those early
| results. D-Wave claims 5000 qubits, but that is for adiabatic QC,
| which to my knowledge, cannot run Shor's algorithm.
|
| To be a threat, QCs need millions of qubits and orders of
| magnitude better error correction. I think people make the
| mistake of looking at the speed of progress of classical
| computers and thinking it applies to QC. It's just not happening.
| acchow wrote:
| Classical silicon chips got to exponential growth because chips
| were profitable - the profits could be poured back into R&D
| enabling a natural feedback loop. Profitability wasn't terribly
| difficult because computers were VERY fast at calculations
| compared to the next best thing - humans.
|
| For QC to hit natural exponential growth, it would need to be
| economically feasible compared to the next best thing -
| classical computers. Is there anything even a tiny QC can do
| better, faster, and cheaper than a classical computer?
| dnautics wrote:
| I think classical silicon also got exponential because
| getting better silicon meant better EDA tools.
| acchow wrote:
| This is an excellent point.
|
| I wonder if future QC design tools will require a QC to run
| effectively. Then we could get a similar feedback loop.
| proce55ing wrote:
| I thought Turing's Cathedral told the story leading up to
| that feedback loop quite well. The insignificant size of the
| grants that enabled the birth of a new industry stand out a
| bit.
|
| https://www.penguinrandomhouse.com/books/44425/turings-
| cathe...
| javajosh wrote:
| The most sensational, and arguably most valuable, use is
| breaking hard encryption, so QC has "nation state
| STEM/security funding" written all over it. Even if it's 1%
| likely to be used in this way, it makes sense for wealthy
| nations to spend on it. But yeah, it's not the same story as
| for the IC boom.
|
| _> Is there anything even a tiny QC can do better, faster,
| and cheaper than a classical computer?_
|
| This is a really good question, and I don't know the answer.
| If I were to try, I'd focus on QC efficient algorithms, and
| what you can do with that in an application. So, in your
| system a QC is a magic box that takes an O(n^2) algo and
| makes it O(n), say. But for ordinary humans, n is very small,
| so this won't matter. I don't think there is mundane problem,
| e.g. one dealing with ordinary productivity, that a QC can do
| better than classical. It's shaping up to be a nation-state
| funded capital intensive information superweapon against
| private communication. And you know what? Maybe if you can
| maintain the infrastructure and staff to build one, you
| deserve to have it! It's especially untroubling if it's
| capacity is limited, like being able to read 10 2048-bit RSA
| encrypted messages per day. That's a superpower, but a very
| limited and expensive one, which I am fine with.
| AlexCoventry wrote:
| > The most sensational, and arguably most valuable, use is
| breaking hard encryption, so QC has "nation state
| STEM/security funding"
|
| Large-scale electronic computers were first developed for
| exactly the same purpose, during WWII. The first commercial
| computers weren't available until a few years after the
| war, about five years after Colossus.
| javajosh wrote:
| Indeed, and it's fun to look at the remarkable
| differences, which are usually more visible in these
| early stages of development. It gets to the very heart of
| what "state" is; the beginning of computation really goes
| back further, to automata and Charles Babbage, where
| state is encoded into the position of a cog, and decoded
| by looking at the cog.
|
| For quantum computing, state is written into the wave
| function of an isolated particle, which is entangled with
| other isolated particles such that you can perform a read
| and get something useful out of it. (TBH I'm a little
| confused about how QC works at the physical level,
| because it seems like your program could require
| different patterns of entanglement, but AFAIK the pattern
| of qubit entanglement is determined by the hardware
| setup, and cannot be modified at runtime. Maybe there is
| a generally reusable "shape" that can be interacted with,
| cleared, setup for a new computation, etc by poking at
| the particles in some specific order. It's probably a
| really nice problem for physics folks who feared they'd
| never get to use their QM classes.)
| mikewave wrote:
| > D-Wave claims 5000 qubits, but that is for adiabatic QC,
| which to my knowledge, cannot run Shor's algorithm.
|
| https://www.hpcwire.com/2021/10/21/d-wave-embraces-gate-base...
| vbezhenar wrote:
| While I have no basis for my judgements, for some reason I
| think that "real" quantum computers just can't exist in our
| universe. May be it's not possible to correct enough errors or
| something like that. By "real" I mean those which can factor
| numbers that are outside of classical computing capabilities.
|
| And those computers that do exist - they're just glorified
| analog machines which were known long time ago.
| chasil wrote:
| This (non-technical) article asserts that statistical analysis
| of D-Wave (or another quantum annealer) might be used far
| before Shor's algorithm becomes a factor.
|
| https://www.forbes.com/sites/arthurherman/2021/06/07/q-day-i...
| errcorrectcode wrote:
| The timeline seems like an unknowable due to the nature of
| technological progress: discontinuous jumps that usually require
| discover manufacturing techniques in secret.
|
| Not as a UFO or conspiracy theory, but as a realization that
| there are some technologies intentionally kept secret to maintain
| military, political, or economic advantages.
|
| When that distance between in-the-pipeline reaches a magnitude
| delta of 2, then I'd be concerned about what's already being
| designed or kept in secret.
|
| Scaling QC is a difficult, unsolved problem of manufacturing.
| IndrekR wrote:
| Given that quantum computers double in size in time it takes to
| complete one PhD thesis, it is not too far fetched to reach such
| capacity within a reasonable time. So far this "law" has held.
| sp332 wrote:
| Well, what's the biggest one you've seen run Shor's algorithm?
| the_black_hand wrote:
| "No time soon". I'd be careful. I remember when Bill Gates said
| we would never need more than 128Kb memory. Crypto is giving huge
| incentive to speed up the development of quantum. We could get to
| 1 million qbits faster than many think.
| lrem wrote:
| Do you think any of the large players will get into crypto? Or,
| any of the crypto players will build a business steady enough,
| to try developing something so ambitious?
| bo1024 wrote:
| Another question is exactly how far ahead the NSA is.
| Remember their budget was estimated at $10 billion back in
| 2013, more than facebook's revenue at that time, twice what
| Twitter's is today. So picture two companies the size of
| Twitter working largely on breaking encryption.
| er4hn wrote:
| An indicator of that may be the fact that the NSA is in the
| process of finalizing their selection of quantum resistant
| algorithms. After that expect those algorithms to end up in
| the FIPS 140 certification process and percolating into
| requirements for government agencies to use.
|
| The NSA has an interest in making sure that classified
| information stays that way for as long as the
| classification lasts. That is at least 25 years,
| potentially up to 75 years (src: https://en.wikipedia.org/w
| iki/Classified_information_in_the_...) so one could infer
| that the NSA believes there is a reasonable chance quantum
| computers will exist and be able to break classical
| encryption within that timeframe.
| tromp wrote:
| The paper he discusses claims that Bitcoin private keys are only
| vulnerable for about 10 minutes, but that only applies to P2PKH
| (pay to public key hash) with never before used keys.
|
| However, millions of BTC are vulnerable with no quantum
| computation time limits. This includes about 1.75 M BTC in
| P2PK/raw multisig outputs, and over 4M BTC due to known pubkeys
| and scripts, revealed in the Bitcoin blockchain.
| shiado wrote:
| The 10 minutes also isn't accurate because the ability to
| obtain private keys from public keys would completely destroy
| the incentives of the Bitcoin network. Miners are incentivized
| and compensated for including transactions in a block due to
| fees. The ability to steal the coins from an incoming
| transaction would create incentives not to include transactions
| in a block and to instead spam the network with as many
| malicious nodes as possible to halt the proliferation of
| transactions.
| sgdjgkeirj wrote:
| This is not as comfortable a margin as it seems. If a direct
| implementation of the algorithm takes a few million qubits, it
| may well be that both better algorithms, better error correcting
| codes, and optimizing their combination to the hardware platform
| will shave a few orders of magnitude. So in 5 years to a decade
| this could get uncomfortably close to the danger zone.
|
| Main issue is that in cryptography (1) some secrets encrypted now
| will be secret in a decade (2) changing standard is very hard and
| takes a long time
| childintime wrote:
| Moore's law added 5 zeroes to the transistor count in 40 years.
| Deep learning compute does a similar feat in just 5 years. So my
| uninformed guess is encryption could be cracked before the decade
| is out, but if not still in most people's lifetime. Way before
| this happens BTC has either lost its value or its ECC has been
| dramatically upgraded.
| zucker42 wrote:
| If anyone would like to try their hand at predicting when this
| might happen, there's this Metaculus question[1]. Looks like the
| community median is 2047 right now.
|
| [1] https://www.metaculus.com/questions/8169/256-bit-ecc-to-
| be-b...
| hangonhn wrote:
| Does anyone know of a similar sort of estimates for AES? Do we
| know if Grover's algorithms can or cannot be applied to AES?
|
| Thanks.
| ahelwer wrote:
| It can but you only get a sqrt(n) speedup. Which is the same as
| halving the bits in the search space. Not trivial, but probably
| doesn't move it to tractable territory given appropriate key
| sizes.
___________________________________________________________________
(page generated 2022-02-09 23:01 UTC)