[HN Gopher] The impact of hardware specifications on reaching qu...
___________________________________________________________________
The impact of hardware specifications on reaching quantum advantage
Author : giuliomagnifico
Score : 36 points
Date : 2022-01-26 19:39 UTC (3 hours ago)
(HTM) web link (avs.scitation.org)
(TXT) w3m dump (avs.scitation.org)
| threshold wrote:
| AI will break SHA256. It's probably backdoored already look who
| made it.
|
| But crypto won't last long enough for that to be meaningful. I
| give bitcoin 3 months to the floor.
| HPsquared wrote:
| If that's possible, can't another AI make an algorithm
| resistant to that kind of attack? Encryption is generally
| easier than cracking.
| threshold wrote:
| Yes, but the problem becomes who can evaluate it? Inevitably
| another AI system because of the complexity. And who has the
| most powerful AI? And what is their agenda? Ah! another
| backdoored algorithm. But the real issue is the loss of
| confidence in the "blockchain technology". If bitcoin is
| cracked the cryptomania scam will be done for a generation.
| lvass wrote:
| What are you waiting to become rich? I'll long you 10x
| leverage.
| kyruzic wrote:
| This is perhaps one of the most ill-informed comments of all
| time.
|
| AI cannot magically make math not exist, but nice try.
| f154hfds wrote:
| Respectfully what math exactly protects SHA256?
| digitalsushi wrote:
| the same math that says without a map of my back yard,
| y'all aint finding the gold unless you grab a shovel for
| ten years
| avrionov wrote:
| SHA256 uses "one way function" - "easy" to compute, but
| "hard" to reverse.
|
| https://en.wikipedia.org/wiki/One-way_function
| f154hfds wrote:
| For a hash function to be mathematically secure, it needs
| to have a formal proof that the computational complexity
| of a preimage or collision attack (depending on the
| threat) meets some criteria. For example, [1]. As far as
| I'm aware, no such formalism exists for anything in the
| SHA family. This means in theory someday someone could
| discover a way to short circuit the desired complexity by
| taking advantage of some weakness in the algorithm, as
| they did to MD5 and SHA1 already.
|
| In principal, these attacks are getting to the complexity
| where any new discovery will probably be aided by some
| form of AI (using a pretty loose definition of AI,
| computer aided search through an attack space). I only
| comment because the OP seemed rather flippant about
| 'math' protecting SHA256 where unless I'm mistaken there
| is no such protection.
|
| [1] https://en.wikipedia.org/wiki/Security_of_cryptograph
| ic_hash...
| threshold wrote:
| and this is why we will all be very fortunate if this
| mania dies soon. Because the NSA won't promote an
| algorithm they can't break meaning SHA256 has a weakness
| intentionally installed that AI will certainly find in
| time. As crypto permeates the general market and becomes
| a dependency, SHA256 becomes an attack vector allowing
| foreign states to anonymously damage the US economy,
| which is unacceptable.
|
| I'm tired of this "something for nothing" self interested
| delusional lying mob frantically trying to control the
| narrative - and this headline is a perfect example. Who
| do they think they're fooling?
|
| https://i0.wp.com/transportgeography.org/wp-
| content/uploads/...
| f154hfds wrote:
| FWIW I'm not trying to say that SHA256 is broken by
| anyone. I personally believe it may never be broken. I'm
| merely saying it's not mathematically proven to be as
| robust as we assume it is, but our assumption is fine for
| now for all practical purposes.
| AlexAndScripts wrote:
| https://en.m.wikipedia.org/wiki/SHA-2
| threshold wrote:
| No, it's perfectly valid for an AI break an algorithm where a
| human cannot. You'll see
| ysangkok wrote:
| There is no encryption in Bitcoin. It uses asymmetric
| cryptography for signatures, and it uses hashing. Encryption
| might be used by wallets, but that is not part of the consensus
| layer and therefore not part of Bitcoin.
| DSMan195276 wrote:
| You don't consider asymmetric key cryptography to be
| encryption?
| drexlspivey wrote:
| There are more to cryptography than encryption, in this case
| it's just signature verification which is not encryption
| ninkendo wrote:
| I'm not an expert on BTC, but I'd guess that if you can
| derive the private key of a signature from its public key
| (which is what the paper is describing), you can use that
| to place transactions from said wallet on the blockchain
| (ie. spend that wallet's money), right? Genuinely curious
| if I understand this correctly, there's a lot I don't know
| about how bitcoin's protocol works.
| DSMan195276 wrote:
| But the signature is an _encrypted_ hash value, which is
| decrypted when verifying the signature. Maybe you could say
| signature verification as a concept is not encryption, but
| certainly Bitcoin 's implementation uses encryption, and I
| don't think there's any definition of 'asymmetric
| cryptography' that is not also some form of encryption.
| MattPalmer1086 wrote:
| Hashes are not encryption either. They're a one way
| function. Encryption has to be reversible.
| MattPalmer1086 wrote:
| No. Encryption is just one type of cryptography, used to make
| data unreadable without the secret key. Signatures are
| something else, used to prove that the holder of a secret
| signed the public data. Zero knowledge proofs are another,
| used to prove you know a secret without revealing it. It's a
| fascinating subject.
| DSMan195276 wrote:
| I'm not saying all cryptography is encryption, I'm not even
| really talking about signatures, I'm specifically talking
| about asymmetric cryptography. I don't see any example of
| "asymmetric cryptography" which is not just a usage of
| public-private key encryption.
| MattPalmer1086 wrote:
| Asymmetric cryptography just refers to cryptography that
| uses public/private key pairs.
|
| Encryption is just a sub type of cryptography. In fact,
| signatures are a more common use of asymmetric
| cryptography than asymmetric encryption.
| MattPalmer1086 wrote:
| If you're talking specifically about RSA, then it's true
| that encryption and signatures both use the same type of
| asymmetric math, but in opposite directions. But most
| asymmetric cryptography doesn't have this property.
| manojlds wrote:
| > asymmetric cryptography
|
| Isn't that...asymmetric encryption?
| HPsquared wrote:
| Isn't it just a bunch of hashing?
|
| Hashing isn't really the same as encryption; hashes can't be
| decrypted.
| neals wrote:
| Unless you have 130M physical qubits*
|
| *) https://avs.scitation.org/doi/10.1116/5.0073075
| ninkendo wrote:
| No I don't think the paper is talking about breaking
| hashing here, they're talking about breaking the 256-bit
| elliptic curve encryption of keys in the Bitcoin network.
|
| Hashing isn't really the same thing... you're not
| "encrypting" data when you hash it, you're putting it
| through a one-way function that produces a consistent
| fixed-size output, such that if you provide the same
| input again, you get the same output.
|
| Hashes aren't "reversible" in any reasonable sense of the
| word. Sure, you can keep guessing inputs until you
| produce one that has the same hash, but it's misleading
| to say that you're "decrypting" it. I'd instead say
| you're finding collisions.
|
| To me, "decryption" implies that there's some secret you
| have which can take the hash and turn it back into its
| original input in constant or linear time. Using the word
| "decryption" to describe "finding a hash collision" isn't
| really correct.
| nabla9 wrote:
| Let's read the article before commenting, please.
| nabla9 wrote:
| Assuming Moore's law applies for quantum circuits, time limited
| attacks against ECDSA described in the article might be possible
| in year 2058 or so.
|
| (it would require 317M qubits at minimum, title has a typo)
| [deleted]
| donclark wrote:
| What about Quantum computers?
| lvass wrote:
| They're cool, absurdly cool in fact.
| loopdoend wrote:
| To spoil the joke, qubits presently operate at like 1 Kelvin
| or -273 degrees Celsius.
| HPsquared wrote:
| Can someone give a quick rundown on why quantum computers so far
| only have small numbers of qubits? I remember reading something
| about errors creeping in somehow, and it's hard to build a large
| system, but don't really understand why.
|
| Edit: something to do with decoherence, I think:
| https://en.m.wikipedia.org/wiki/Quantum_computing#Quantum_de...
| scythe wrote:
| Current architectures aren't ready to operate enough gates
| fast/accurate[1] enough to attempt sustained (i.e. longer than
| milliseconds) protection of quantum data. So making more qubits
| would not be very useful until we can make them talk to each
| other.
|
| [1]: Qubits are always decohering, so fast and accurate are
| closely linked.
| dr_zoidberg wrote:
| Decoherence is the answer. Veeeeery long story short, qubits
| have to be isolated from the world as much as possible to
| maintain their "magical quantum properties". Decoherence is
| when those ideal conditions break, and the qubits no longer
| behave as needed for the quantum computer to work. The more
| qubits you have, thet harder it gets to fend off the
| inteference from the outside world that decoheres the qubits.
| amelius wrote:
| Ok, so it gets N times harder, but you get M times more
| compute power. Is there a relation between N and M? Is at
| least M larger than N? Will N get lower with more qubits?
| ben_w wrote:
| Thinking about things being N times harder is probably the
| wrong approach at the current time.
|
| We're so early in the engineering of these computers that
| it's "we _don't know how_ to make more than X usable qbits
| in this configuration at any cost" rather than "X+1 qbits
| is Y dollars more expensive".
|
| Worth noting that the value of X depends heavily on the
| configuration and the things holding the qbits; IIRC the
| D-wave design is scalable but also not a "universal"
| quantum computer. I'm unclear on the specifics of how and
| why.
| Animats wrote:
| Well, DWave claims 5,000 qbits. Unclear if they can work on this
| problem. So, if you had 100 of those, you could break Bitcoin
| wallets in a year. Retrieve all those lost coins from the early
| days.
| MattPalmer1086 wrote:
| Dwave don't make general purpose quantum computers. They do
| something called quantum annealing, which is only useful for a
| very specific set of problems.
| scythe wrote:
| >and a physical gate error of 10^-3.
|
| Before you get too excited, it's important to remember that
| existing qubit implementations do not achieve a physical gate
| error rate of 10^-3 (best right now is more like 10^-2).
| jacksondc wrote:
| 13 million, not 130 million, no?
| giuliomagnifico wrote:
| Oh yes sorry my mistake, I merged the two data and I made a bit
| of confusion, I thought it was 317 x 10(6) and 130 x 10(6),
| instead is 13 not 130. Sorry. By the way moderators have
| changed the title (but now I don't know who will understand
| what this post is about)
| martyvis wrote:
| Correct, article says 317M qubits to break encryption in an
| hour, 13M in a day. Title here is wrong.
| TheSocialAndrew wrote:
| If hypothetically this would happen, wouldn't gaining access to
| everyone's wallets render it useless since BTC would no longer
| have value? If so, the goal would just be to disrupt the
| financial markets, not necessarily to gain directly.
|
| Also, wouldn't we be able to restore everyone's wallets from the
| latest snapshot on a new blockchain?
| mNovak wrote:
| Still they could extract a fair amount of value before everyone
| catches on. Especially if you don't know the exact
| day/month/year that became possible; when would you take the
| snapshot? No one would accept transactions after that snapshot
| date either, if they worry it'll all get rolled back.
|
| Of course the market would just sink in the years leading up to
| that threshold, in anticipation of this (assuming no mitigation
| in this case).
| handmodel wrote:
| If I had ability to gain access to everyone's wallet I'd
| probably attempt to siphon off a few million dollars a day
| worth of bitcoin. If people catch on that all is lost after
| awhile oh well - I've already cashed out significantly.
| tims33 wrote:
| The Office Space approach
| yanmaani wrote:
| > wouldn't gaining access to everyone's wallets render it
| useless since BTC would no longer have value
|
| It would only be useful for the wallets with known public keys.
| That's mainly old bitcoins, new ones only have its hash written
| to the chain.
|
| This would certainly crash the price, but not to zero.
|
| > Also, wouldn't we be able to restore everyone's wallets from
| the latest snapshot on a new blockchain?
|
| Yes, but what good will it do you if the private key is leaked?
| sharkster711 wrote:
| Yes to the first question.
|
| For the second, it would depend on easy/hard it is to mine to
| get to the point where you can replicate a snapshot, and how
| easy/hard it is to continue mining on from that point. It is
| very unlikely the new protocol will hold the same value as BTC
| would have had.
| rndphs wrote:
| I think it's more that if someone builds a sufficiently large
| quantum computer for other purposes then it would also break
| bitcoin as a side effect.
| bubblecheck wrote:
| Indeed, a viable QC that can break existing widespread
| asymmetric crypto is worth far more than the total mkt cap of
| all "crypto" at their combined peak.
|
| Most likely this will be wielded by USA or China in secret
| (if not being done already)
| Klinky wrote:
| Likely the crypto methods would evolve well before the hardware
| caught up. It's unlikely that suddenly out of the blue someone
| would show up with a 13M qubit quantum computer that could
| crack all wallets.
| zenlikethat wrote:
| I gotta imagine you could probably sneak a good chunk of
| selling in before people noticed or the thing went to zero.
| You'll likely have time to plan after breaking it, so you could
| move quick, and there are many long inactive wallets with tons
| of BTC in them. Some have keys lost in landfills, some have
| dead or jailed owners, and so on.
|
| So I can see how you could pull it off before the price tanked,
| and even then, it's not a given that it'd go to zero. Just
| because a powerful actor can compromise your Bitcoin wallet
| doesn't _necessarily_ make it completely worthless -- just look
| at all the chains that are trivial to 51% attack which are
| still chugging along with small valuations. The price probably
| would collapse though.
| [deleted]
| tsimionescu wrote:
| The idea is that for the Bitcoin network "knowing the private
| key" is 1:1 entriely equivale to "being the legitimate owner of
| the wallet". Onve someone has found out the private key of a
| wallet, they have the exact same access to that wallet as
| anyone else who knows the private key.
|
| This is different from finding out someone's password or even
| password + MFA on a centralized service, say Gmail. There,
| Google and/or the court systems step in, ascertain the
| legitimate owner, reset the credentials to the account, and
| give only the legitimate owner access.
|
| There is no way to do this in Bitcoin, by design. Even if the
| US Supreme Court decided that you are the only legitimate owner
| of this wallet, there would be no way to prevent someone else
| who knows the private key from moving "your" Bitcoin. Of
| course, they could be punished for this, in principle, but it
| would be impossible to prevent it from happening.
| bananarchist wrote:
| Is that a lot of qubits? I have no frame of reference on this.
| Jyaif wrote:
| State of the art is in the order of a 100 qubits.
| lodovic wrote:
| I guess there isn't such a thing as Moore's Law for Quantum
| Computing
| MattPalmer1086 wrote:
| Not as such, that was only ever an empirical observation
| anyway, not a law of any kind.
|
| Having said that, IBM just unveiled a 127 qubit machine,
| and their roadmap is to to to scale to 433, and then 1121
| qubits in the not too distant future.
|
| https://newsroom.ibm.com/2021-11-16-IBM-Unveils-
| Breakthrough...
| dr_zoidberg wrote:
| Yes, that's a lot considering that large systems today have in
| the order of 100-1000 qubits. Mind you, the systems currently
| saying that are larger than 100 qubits are debated if they
| really are quantum computers in the broadest sense, or a subset
| (consensus is they are a subset of quantum computers, and not
| full fledged). So the largest, "really quantum computers" are
| in the order of ~100 qubits.
|
| Edit: for context, I'm referring to D-Wave, that some years ago
| said they had broken the 1000-qubit mark, but their systems
| aren't generic quantum computers, but rather computers tham
| implement quantum annealing.
| giuliomagnifico wrote:
| > Is that a lot of qubits?
|
| Yes. Now the most powerful quantum computers have less than 100
| qubits. We have to reach 130,000,000 qubits. Take a beer
| meanwhile =)
| bArray wrote:
| It wouldn't be that insane for a factory to be able to create
| so many qubits. Building one qubit is hard, building two qubits
| is not double the effort.
| ninkendo wrote:
| Right, and I don't understand why it took the industry so
| many decades for 64-bit computing to become dominant. If a
| factory is creating bits, it shouldn't take 64x the effort to
| create 64 of them versus 1 bit...
| bArray wrote:
| 64 bit computing became dominant because of the need to
| address memory larger than 32 bits. They have the
| capability to scale quite 'easily' to 128 bits or further
| if they wanted to, there just wouldn't be a benefit. The
| Play Station 2 for example has 128 bit SIMD [1], 128 bit
| computing has been possible for a long time.
|
| Once you have the ability to create a processor at 7nm with
| some bits, scaling is not so tough. Even if you cannot
| reliably create larger pieces of silicon, you just do
| something like AMD did with multiple dies connected by a
| fabric to mitigate risk. Absolutely worst case, you have a
| motherboard with multiple processors, or even computers in
| different buildings.
|
| In terms of qubits, it is very likely that the problem can
| be distributed over multiple quantum computers. A
| significantly incentivized actor could definitely pull it
| off. If you can reliably manufacture ~100 qubit quantum
| computers, it's just a matter of scale.
|
| [1] https://en.wikipedia.org/wiki/PlayStation_2_technical_s
| pecif...
| tsimionescu wrote:
| > In terms of qubits, it is very likely that the problem
| can be distributed over multiple quantum computers.
|
| No, this is very wrong. Qubits are only different from
| classical bits of they can communicate before becoming
| entangled with the environment (decoherence). You can't
| run some kind of "quantum cable" between two separate QCs
| in a rack and get twice the qubits - the interactions
| with the wire will break the entanglement between the
| qubits, and you will just have an unreliable classical
| computer with 100 bits of memory.
|
| To perform a quantum computation, ALL the qubits (all
| your memory) must be in an entangled state together -
| this is the massive problem. Even worse, this state must
| be maintained while applying different transformations on
| the qubits from the outside.
| bArray wrote:
| In the paper they suggest that spending ~24 hours more
| doing computation means you can divide the number of
| qubits by 24, indicating that at least in one sense it is
| linearly scalable.
|
| From my limited understanding, you process for a given
| amount of time, after which you can classically pull out
| an answer with some given probability, with some trade
| off with time and noise.
|
| I imagine it would be somewhat possible to have several
| quantum computers running in parallel which end early,
| each correctly deducing the answer with some given
| probability. If each of the N^x machines has a 1/N chance
| of having the correct answer, you could simply test each
| solution classically.
|
| And that assumes there is not some way to seed the search
| effort classically during the setup of the quantum
| circuit.
| tsimionescu wrote:
| > Building one qubit is hard, building two qubits is not
| double the effort.
|
| No, it's much, much more than double the effort to build a QC
| with twice the qubits. The problem is that you want the
| qubits to interact with each other, but to be entirely
| perfectly isolated from the outside world for as long as
| necessary for signals from one to reach the others. The
| difficulty of achieving this isolation even for an instant at
| all increases by something like n^2 or n^3 (surface/volume of
| the isolated space) with the number n of qubits. Then, the
| more qubits you have, the more time you need for them to
| interact, so you multiply by an additional factor.
|
| The numbers above are very handwavy, of course, but the point
| is that it's MUCH harder to build a bigger QC than a small
| one. So hard that it's not even clear if the current
| approaches can actually achieve this even in principle - we
| may need a different kind of qubit to scale up.
| [deleted]
| thebean11 wrote:
| I think the difficulty is putting them into one processor
| ALittleLight wrote:
| My, highly imperfect, complete layman understanding is that
| the challenge has nothing to do with the "manufacture" of
| qubits, but rather getting them to work in the same computer
| without interfering with each other. I believe it gets harder
| with each qubit, not easier.
| shepherdjerred wrote:
| Is it possible to scale it by building separate computers
| and using distributed computing techniques? e.g. would 100
| 1 qubit computers be equivalent to a single 100 qubit
| computer?
| ben_w wrote:
| No. Most of the benefits of quantum computing requires
| the qbits be entangled with each other, so, crudely
| speaking, the difference between 100 (1-qbit-computers)
| and 1 (100-qbit-computer) is ability to compute using the
| 2^100 different ways the latter qbits can be entangled.
| d_tr wrote:
| The set of qubits needs to be an isolated system while
| the quantum computation happens, so no. By taking the
| qubits apart you would only make this much harder, if not
| impossible.
___________________________________________________________________
(page generated 2022-01-26 23:02 UTC)