Skip to content
 
If you can read this, either the style sheet didn't load or you have an older browser that doesn't support style sheets. Try clearing your browser cache and refreshing the page.

(ZDNet)   A quantum computer just solved a difficult problem 3 million times faster than a conventional computer. Public key cryptography is starting to look a little shaky   (zdnet.com) divider line
    More: Interesting, Computer, Computation, Universal quantum simulator, Quantum computer, Qubit, company D-Wave, Simulation, Nobel Prize  
•       •       •

889 clicks; posted to STEM » on 24 Feb 2021 at 5:19 PM (10 weeks ago)   |   Favorite    |   share:  Share on Twitter share via Email Share on Facebook



Voting Results (Smartest)
View Voting Results: Smartest and Funniest

 
2021-02-24 3:27:10 PM  
16 votes:
Cryptography is still safe. This was a D-Wave, which uses a niche approach (quantum annealing) that happens to be very effective for a certain class of problems that happen to be exceptionally difficult for an ordinary digital computer - primarily ones involving quantum simulations.
 
2021-02-24 4:18:04 PM  
14 votes:

HugeMistake: Cryptography is still safe. This was a D-Wave, which uses a niche approach (quantum annealing) that happens to be very effective for a certain class of problems that happen to be exceptionally difficult for an ordinary digital computer - primarily ones involving quantum simulations.


Just to put a slightly finer point on an excellent summary. There is no known way to map classic cryptographic problems into that space of problems that quantum annealing machines solve well, and it is unlikely there ever will be.
 
2021-02-24 3:28:34 PM  
9 votes:
I wonder how it does at Bitcoin mining.
 
2021-02-24 4:18:38 PM  
8 votes:
As already said, quantum computers are very good at some things. And very bad at other things.

This is one of the things they are very good at.
 
2021-02-24 4:28:08 PM  
6 votes:
I never thought I'd see the day when real honest-to-god quantum computers were solving useful real-world problems. I still don't.

/I keed, I keed
//no, they're great
///for me to poop on!
 
2021-02-24 6:12:54 PM  
2 votes:

leeksfromchichis: Until it runs Quantum Doom and loads Quantum Porn on a Quantum Private Mode Browser, I don't believe it's quantum.


You forgot quantum Crysis.
 
2021-02-24 5:24:27 PM  
2 votes:
Just wait until Alice and Bob hear about this....
 
2021-02-24 3:49:48 PM  
2 votes:
Oh boy.
 
2021-02-25 9:09:22 AM  
1 vote:

lifeslammer: Basically encryption is unsolvable problems even for a computer, and p v np is saying that any problem that can be quickly verified by a computer could also be quickly solved by a computer. So while right now it takes literal ages for a computer to brute force the equations that encryption is based on, a successful proof to solve that would basically make encryption as good as a fence with a hole in it


Sort-of.  My only quibble is "unsolvable problems even for a computer".   There is only one known unsolvable problem in cryptography, and that's breaking a properly implemented one-time pad system.  It's the only provably unbreakable system, simply because brute forcing it would just give you every possible message of the same length without being able to distinguish the correct one from all of the incorrect ones.

All of the others are *EXCEPTIONALLY* difficult.  While they are solvable from a theoretical standpoint with conventional computers, from a practical standpoint they aren't because of the huge amount of time it would take to solve them.

However, relying on the "Takes a huge amount of time to break" is a *VERY* weak leg to stand on.   It's the mistake the Nazi's made with the Engima.  They *KNEW* that Enigma wasn't unbreakable.  But they figured that even if you had an Enigma machine, or even dozens or hundreds, having people test all of the possibilities would take too long to break.  They didn't think about using machines with large numbers of parallel Enigma rotors all grinding away at high speed to break them.

Having said that, I believe that as early as mid-1943, and certainly by the fall of 1944, the Germans *KNEW* that Enigma was being broken, because they acted like it was.  Perhaps the two biggest things were the U-boat messages and the Ardennes Offensive.

In the fall of 1944, the Ubootwaffe started experimenting with giving each U-boat going on operational patrol it's own unique set of daily Enigma keys.  Prior to that, U-boats heading for the same operational areas would be given the same keys, so they could read each other's traffic.  So if U-89 hears U-372 report a convoy sighting, the commander of U-89 can start intercepting the convoy before getting an order from BdU* to do so.

The problem is that with a number of U-boats all reporting things like convoys, ship sightings, weather reports, and simply status reports, and messages from BdU requesting reports or ordering the U-boats to and fro, you can build up a lot of traffic in the same key, and that's bad.

With each U-boat having it's own key, there isn't anywhere near as much traffic, and by that time a lot of it was one-way traffic, because the U-boats spent most of their time submerged or snorkeling, so they couldn't transmit.  They could receive while underwater, though, via the powerful VLF transmitter at Nauen.

The Germans started this in the Fall of 1944, and by February 1945, all U-boats on war patrol had their own individual unique keys.  And the Allies were blacked out of U-boat Enigma traffic all the way to the end of the War, simply because each key for each U-boat had to be broken each and every day.   So even if you managed to  break U-897's key for March 3rd, 1945, that didn't help you with U-734's traffic, even if they were both operating in the same general area.

The other major event was the Ardennes Offensive.  The orders for the offensive were not transmitted over the airwaves, and certainly not by Enigma:  By that time, regulations stated that nothing classified could be sent over the air encrypted by Enigma, it had to be either via the secure teleprinter (which was ironically less secure than the Enigma), or via courier.   The orders for the Ardennes Offensive were sent via courier, which is part of the reason why the Allies were caught unaware.

Here is a very interesting NSA monograph on what the Germans knew about Allied efforts to break Enigma, and it comes *CLOSE* but not quite there to saying basically "Yeah, the Germans knew it wasn't secure, but couldn't switch horses midstream".

https://www.nsa.gov/Portals/70/docume​n​ts/news-features/declassified-document​s/tech-journals/der-fall-wicher.pdf


So the whole idea that with conventional means public key cryptography is safe just reminds me of the Germans saying that Enigma was safe, when in fact it had been broken years before WWII even started.

For all we know, the NSA broke public key cryptography years ago.  We wouldn't know about it, because it's classified.


*BdU = Befehlshaber der Unterseeboote, literally "Commander of U-boats", but basically U-boat HQ.
 
2021-02-25 8:08:57 AM  
1 vote:

Dave2042: lifeslammer: HugeMistake: Cryptography is still safe. This was a D-Wave, which uses a niche approach (quantum annealing) that happens to be very effective for a certain class of problems that happen to be exceptionally difficult for an ordinary digital computer - primarily ones involving quantum simulations.

You skipped over the most important part too


it has already been resolved by the 2016 winners of the Nobel Prize in Physics, Vadim Berezinskii, J. Michael Kosterlitz and David Thouless, who studied the behavior of so-called "exotic magnetism", which occurs in quantum magnetic systems.

Indeed.  All that's happened here is that D-Wave have claimed their box could have solved it really fast.
How much of that extra speed is really the box?  How much is an algorithm designed with the box in mind and knowing what the answer is?  Why focus on a solved problem rather than an unsolved problem - wouldn't the latter be much more impressive?
Company has a bit of a history of being vague about the details.


Regardless, the criticisms here are like pointing to an Apple II in 1981 and saying "What good is it?".  Not much, but that's besides the point.  It increased the ability to do calculations by orders of magnitude over previous manual methods, and it was still very limited in its capacity and power.

Quantum computing is in that stage right now, it's relative infancy, and it's showing improvements (if TFA is to be believed) of six whole orders of magnitude over conventional computing.

And yeah, if it's an algorithm designed specifically to take advantage of how quantum computers work, how is that a problem?  Do you think other algorithms won't be designed with that in mind?   And in fact, they already have:   https://en.wikipedia.org/wiki/Shor%2​7s​_algorithm

The idea behind public key cryptography is that there are functions that are easy to compute one way, and very difficult to reverse.   A sufficiently powerful quantum computer running Shor's algorithm can break pretty much all of the commonly used public key crypto used today in a reasonable time frame by being able to do the reverse calculation before the heat death of the Universe.

In this case, they demonstrated a machine using 2,000 qubits, which is designed for a specific problem not necessarily related to cryptography, but that doesn't mean you couldn't build one that is.

I mean, sure, you can look at the Bleriot IX and say "What use is it?", not imagining that something like the SR-71 is possible.
 
2021-02-25 12:30:26 AM  
1 vote:

Driedsponge: leeksfromchichis: Until it runs Quantum Doom and loads Quantum Porn on a Quantum Private Mode Browser, I don't believe it's quantum.

You forgot quantum Crysis.


That's still 20 years away...
 
2021-02-24 9:25:56 PM  
1 vote:
Or you could use a $5 hammer
 
2021-02-24 6:09:01 PM  
1 vote:
Until it runs Quantum Doom and loads Quantum Porn on a Quantum Private Mode Browser, I don't believe it's quantum.
 
2021-02-24 5:50:32 PM  
1 vote:

lifeslammer: HugeMistake: Cryptography is still safe. This was a D-Wave, which uses a niche approach (quantum annealing) that happens to be very effective for a certain class of problems that happen to be exceptionally difficult for an ordinary digital computer - primarily ones involving quantum simulations.

You skipped over the most important part too


it has already been resolved by the 2016 winners of the Nobel Prize in Physics, Vadim Berezinskii, J. Michael Kosterlitz and David Thouless, who studied the behavior of so-called "exotic magnetism", which occurs in quantum magnetic systems.


Indeed.  All that's happened here is that D-Wave have claimed their box could have solved it really fast.
How much of that extra speed is really the box?  How much is an algorithm designed with the box in mind and knowing what the answer is?  Why focus on a solved problem rather than an unsolved problem - wouldn't the latter be much more impressive?
Company has a bit of a history of being vague about the details.
 
Displayed 14 of 14 comments

View Voting Results: Smartest and Funniest

This thread is closed to new comments.

Continue Farking





On Twitter



  1. Links are submitted by members of the Fark community.

  2. When community members submit a link, they also write a custom headline for the story.

  3. Other Farkers comment on the links. This is the number of comments. Click here to read them.

  4. Click here to submit a link.