Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Time Running Out for Public Key Encryption

Zonk posted more than 7 years ago | from the interesting-times-are-upon-us dept.

Security 300

holy_calamity writes "Two research teams have independently made quantum computers that run the prime-number-factorising Shor's algorithm — a significant step towards breaking public key cryptography. Most of the article is sadly behind a pay-wall, but a blog post at the New Scientist site nicely explains how the algorithm works. From the blurb: 'The advent of quantum computers that can run a routine called Shor's algorithm could have profound consequences. It means the most dangerous threat posed by quantum computing - the ability to break the codes that protect our banking, business and e-commerce data - is now a step nearer reality. Adding to the worry is the fact that this feat has been performed by not one but two research groups, independently of each other. One team is led by Andrew White at the University of Queensland in Brisbane, Australia, and the other by Chao-Yang Lu of the University of Science and Technology of China, in Hefei.'"

Sorry! There are no comments related to the filter you selected.

Tor like oatmeals! (-1, Offtopic)

Anonymous Coward | more than 7 years ago | (#20591555)

Tor like oatmeals

Re:Tor like oatmeals! (5, Interesting)

Anonymous Coward | more than 7 years ago | (#20591947)

Re:Tor like oatmeals! (3, Informative)

julesh (229690) | more than 7 years ago | (#20592217)

To moderators who marked this offtopic, you may wish to read the linked article first.

More like the Chinese gov (0, Flamebait)

Anonymous Coward | more than 7 years ago | (#20591565)

More like the Chinese government wants to break the encryption so they can more easily hack other governments data. They just post it under "Research".

Re:More like the Chinese gov (4, Insightful)

multisync (218450) | more than 7 years ago | (#20591745)

More like the Chinese government wants to break the encryption so they can more easily hack other governments data. They just post it under "Research".


Yeah, the Chinese government is the only government that would like to do that.

Re:More like the Chinese gov (4, Funny)

Roofus (15591) | more than 7 years ago | (#20592385)

Right! Well, them and a former college age hacker turned Mob IT manager turned world saviour.

Think of it Marty. No more rich people, no more poor people, everybody's the same

Re:More like the Chinese gov (1)

newgalactic (840363) | more than 7 years ago | (#20591953)

What the heck do you think the Australians are doing? And Yes, the US is doing this too, along with every other country/corporation/constituent group that can.

Re:More like the Chinese gov (4, Interesting)

Nos. (179609) | more than 7 years ago | (#20591981)

The thing I worry about, is, regardless of which government or group is working on it is this, if this is what they're releasing to the public, how much farther ahead are they behind closed doors.

Re:More like the Chinese gov (1)

Maximum Prophet (716608) | more than 7 years ago | (#20592007)

I think you can pretty much assume the NSA and perhaps the former KGB (what's their new name?) can already do this. Does anyone know the name of the Chinese equivalent of the CIA, KGB and MI6?

Re:More like the Chinese gov (4, Funny)

koh (124962) | more than 7 years ago | (#20592073)

Chinese secret services are so secret they don't even have a name. Actually, they don't even need one.

Re:More like the Chinese gov (1)

hoggoth (414195) | more than 7 years ago | (#20592397)

> Chinese secret services are so secret they don't even have a name

The name of the Chinese secret service is so secret you can't even pronounce it.

Umm, well, you probably can't pronounce most Chinese words...

Re:More like the Chinese gov (1)

fr4nk (1077037) | more than 7 years ago | (#20592115)

I think that would be the National Security Bureau [wikipedia.org] .

Re:More like the Chinese gov (1)

moderatorrater (1095745) | more than 7 years ago | (#20592265)

I personally think the NSA's had a quantum computer for a couple of years. All the theoretical groundwork was laid a long time ago, it was mostly an engineering problem and developing entangling techniques, etc. These are all things that a group of people with a massive, massive budget could overcome.

Re:More like the Chinese gov (5, Funny)

Anonymous Coward | more than 7 years ago | (#20592327)

Does anyone know the name of the Chinese equivalent of the CIA, KGB and MI6?

Jet Li.

That is nothing (4, Funny)

MyLongNickName (822545) | more than 7 years ago | (#20591569)

I have developed an algorithm to efficiently decrypt ROT-26. You will need to use it to read this encrypted message.

MOD PARENT DOWN (-1, Troll)

Anonymous Coward | more than 7 years ago | (#20591927)

I have developed an algorithm to efficiently decrypt ROT-26. You will need to use it to read this encrypted message.
I have developed calling for unfunny attempts at "funny" posts to be moderated downwards. You will need to browse at -1 to read the parent message.

Re:That is nothing (4, Funny)

syrinx (106469) | more than 7 years ago | (#20592203)

I have developed an algorithm to efficiently decrypt ROT-26. You will need to use it to read this encrypted message.

The joke is on you: I've already upgraded all my encryption to ROT-52.

Re:That is nothing (4, Funny)

ookabooka (731013) | more than 7 years ago | (#20592337)

ROT52 is radically different than ROT26 and has its own problems, triple ROT26 (3ROT26) is much more feasible with today's technology and far easier to implement.

bigger keys? (1)

doublefrost (1042496) | more than 7 years ago | (#20591583)

Wouldn't making the keys bigger solve that problem?

Re:bigger keys? (1)

Spy der Mann (805235) | more than 7 years ago | (#20591725)

Remember it's quantum computers we're talking about. Quantum computers solve this kind of problems instantly.

Re:bigger keys? (3, Insightful)

brunascle (994197) | more than 7 years ago | (#20591777)

not really. they can still use the same algorithm, it'll just take longer. it might work for a while, but it's not a long term solution.

plus, cryptography is very resource-intensive, growing exponentially with key size. there comes a point when it's just not practical to use a key that large, as it will take too long to encrypt/decrypt/generate the key.

not quite... (2, Informative)

dollargonzo (519030) | more than 7 years ago | (#20591921)

Encryption/decryption grows linearly in the length of the key, and cracking is [considered] exponential in the length of the key. the problem is that shor's algorithm on a quantum computer is also (IMHO) linear in the length of the key. Hell, even if it was a decent order polynomial in the length of the key you could never be "faster" (in the tractable vs. intractable sense). so, no, you can't even do it for now

Re:not quite... (2, Informative)

snowgirl (978879) | more than 7 years ago | (#20592303)

The calculation space is O(log N), so it grows even less than linear. You would have to double the bit size just to double the processing time to crack it. That fits fairly neatly into your "it doesn't meet intractable standards."

Fortunately, symetric keys are still fine, Quantum Computers can calculation square roots faster, but this only halves the execution time, which is easily accounted for by double the key size. Even with a Quantum Computer cracking AES 512, or 2048 is intractable.

Re:not quite... (4, Informative)

cperciva (102828) | more than 7 years ago | (#20592419)

Encryption/decryption grows linearly in the length of the key

No. With classical algorithms, RSA encryption and signature verification are O(n^2), while RSA decryption and signing are O(n^3).

and cracking is [considered] exponential in the length of the key

No. All modern factorization algorithms are subexponential; this is why a 1024 bit RSA key is roughly as secure as an 80 bit symmetric encryption key.

Re:not quite... (5, Informative)

smallfries (601545) | more than 7 years ago | (#20592493)

Although you are theoretically correct what you have said is wrong in practice. If I want to run a classical algorithm on a larger piece of data then I can just simulate a larger computer (to the extent that I page things in or out of memory, implement 64bit operations in 32bit etc). For a quantum computer I need a bigger computer. I can't simulate a 8-qubit machine on a 4-qubit machine with just a polynomial slowdown.

I can't read the actual article at home so I don't know how large their machine is. Shor's algorithm has actually been run on a 4-qubit machine before so the summary is incorrect. I believe that the number they factored was 15. The point being that I need a quantum machine large enough to factor the RSA number. As building a 8-qubit machine is not as simple as slapping two 4-qubit machines together (because of problems with quantum coherence) there will always be a state-of-the-art for how large a Quantum Computer can be, and public crypto with keys significantly larger than that will be safe until a larger machine is developed. Sort of a faster version of the battle between cryptographers and cryptoanalysts that we see at the moment.

You'll notice that nobody made the same claims when EPFL sieved a 1024-bit number recently - instead everyone said use larger keys. The situation is likely to be the same as Quantum Computers increase in size. Lastly, not all public key crypto is shafted, only things that rely on factorisation as a problem. ECC will be quite safe until (if?) somebody develops a quantum algorithm for discrete logs.

Disclaimer: I don't do research in quantum - I work in cryptography, but the quantum guys have an office down the corridor and occasionally I understand what they are talking about. Ashley, don't beat me around the head for getting the details wrong :)

Re:bigger keys? (2, Interesting)

CastrTroy (595695) | more than 7 years ago | (#20592005)

They mention this is a threat to public key cryptography, but what about private key (aka symmetric) encryption? How is that affected by quantum computers, and these algorithms?

Re:bigger keys? (1)

tftp (111690) | more than 7 years ago | (#20592215)

IMO, not directly affected. One-time pads are still useful.

The only catch might exist if there is an algorithm for a quantum computer to find a [secret, shared] key that produces a plaintext in a human language. That's probably the only way to break the OTP (aside from stealing the key.) However this is also easy to obscure - roughly speaking, create a ZIP file and apply a OTP to it. If the OTP's plaintext is not recognizable as such there is no way to accept the key and start working on the second layer of encryption.

Re:bigger keys? (1)

archen (447353) | more than 7 years ago | (#20592565)

Totally different problem so this algorithm is irrelevant. The power of quantum computers is slightly more troubling than current super computer tech, but not overly so. Two or so years ago the claim of IDEA encryption was that it would take 1000 computers more than the lifetime of the universe to break it by brute force (or something to that effect). AES 256 is at least that strong. The problem with public key crypto is that its strength is indirectly proportional to how fast computers can do math.

Re:bigger keys? (0)

Anonymous Coward | more than 7 years ago | (#20591791)

No.

Re:bigger keys? (2, Insightful)

geekgirlandrea (1148779) | more than 7 years ago | (#20592125)

No, the problem is that Shor's algorithm can factor in polynomial time. To make keys big enough to be impractical to factor with it, they'd also have to be too big to practically use. Public-key cryptosystems depend on the ratio of the time to break the key to the time to use it scaling exponentially with key size.

Prime number factoring is easy (1, Informative)

mark-t (151149) | more than 7 years ago | (#20591587)

The two factors are 1 and the number itself. Now prime number FACTORIZATION.... that's hard for large numbers that have only a couple of factors.

I'm not sure how big of a deal this is. (1)

pclminion (145572) | more than 7 years ago | (#20591591)

Well-funded governments or criminal organizations could take advantage of this, but I guarantee you that J-random-cracker in his basement is NOT going to be able to build a quantum computer.

This poses a big threat to governments, and possibly financial institutions, but not individuals. Nobody is going to spend millions of dollars to build a working quantum computer just so they can steal your credit card number. If I had a quantum computer I would use it to blackmail entire governments, not harass the little folk.

Re:I'm not sure how big of a deal this is. (2, Insightful)

jellomizer (103300) | more than 7 years ago | (#20591657)

Well Students of colleges (Perhaps undgrads, or people pretending to be an actual student) can have access to such systems. 10-20 years down the line when such systems become obsolete they get in the hands of the public. Or engineering Quantum Computers becomes more feasable then everyone may have one.

Re:I'm not sure how big of a deal this is. (4, Funny)

MarkovianChained (1143957) | more than 7 years ago | (#20591711)

"In other news, man with quantum computer reported missing...."

Re:I'm not sure how big of a deal this is. (5, Funny)

zippthorne (748122) | more than 7 years ago | (#20591815)

...His velocity, however, is known precisely.

Re:I'm not sure how big of a deal this is. (1)

lazy_playboy (236084) | more than 7 years ago | (#20591893)

+5 funny, surely? :-/

Re:I'm not sure how big of a deal this is. (0, Offtopic)

Poromenos1 (830658) | more than 7 years ago | (#20592025)

I wholeheartedly agree. I wish my +1, Funny moderation on the GP hadn't evaporated with the posting of this comment.

Re:I'm not sure how big of a deal this is. (1)

dapsychous (1009353) | more than 7 years ago | (#20592205)

Congratulations! You have inspired me to change my sig.

Re:I'm not sure how big of a deal this is. (2, Funny)

russ1337 (938915) | more than 7 years ago | (#20592285)

>>> ""In other news, man with quantum computer reported missing....""

From the account of witnesses, Police believe the man may be traveling inside a box and there is a possibility he is now dead, and alive.

Re:I'm not sure how big of a deal this is. (0)

Anonymous Coward | more than 7 years ago | (#20591751)

I'm not worried about a regular hacker stealing my money, I would be worried about governments that can take a quick peek at anything they want without strong oversight. Just because you have nothing to hide doesn't mean you should want it to be easy for them to watch your every action :) If that still doesn't concern you, I'm sure it will concern the markets - which do have an impact on most everyone.

Re:I'm not sure how big of a deal this is. (1)

Frosty Piss (770223) | more than 7 years ago | (#20591753)

Well-funded governments or criminal organizations could take advantage of this...

Most governments will have the "funds" for this, should they have the interest, I'm not sure "well funded" has anything to do with it. The knowledge for building monster computers from PC hardware ("imagine a Beowulf cluster of those...") is public these days, and a team of mercenary computer scientists is a financial drop in the bucket. Our "enemies" such as Russia, China, and Iran have almost certainly already been working hard on this, it's just that they don't announce their findings in the journals.

Re:I'm not sure how big of a deal this is. (1)

foobsr (693224) | more than 7 years ago | (#20591803)

Well-funded governments or criminal organizations could take advantage of this, ...

... rendering your encryption shields worthless, and, besides, what is the difference?

CC.

Re:I'm not sure how big of a deal this is. (2, Interesting)

brunascle (994197) | more than 7 years ago | (#20591841)

Nobody is going to spend millions of dollars to build a working quantum computer just so they can steal your credit card number.
with a universal cryptography-breaking-device, there are much bigger targets than individuals. if you find the right target, it could be very profitable.

Re:I'm not sure how big of a deal this is. (2, Insightful)

Vellmont (569020) | more than 7 years ago | (#20591959)


This poses a big threat to governments, and possibly financial institutions, but not individuals.

As an individual, I consider threats to governments and financial institutions "a big deal".

Re:I'm not sure how big of a deal this is. (4, Informative)

Maximum Prophet (716608) | more than 7 years ago | (#20592253)

Governments still use one-time pads for the really sensitive stuff.

See http://en.wikipedia.org/wiki/Numbers_station [wikipedia.org]

The one-time pad is in no danger of being broken by quantum computers or anything else because it's provably unbreakable. (Unless there is operator error, and sometimes that's the case)
The Good Guys(tm) want to have this so that they know what The Bad Guys(tm) might have, and that way they can change their systems before they are cracked. I could imagine some crime syndicate paying the millions for a working quantum computer and the PhD talent to run it so that they could break into international banking systems.
On the flip side, pressing exactly two HD-DVDs with random data, and distributing these to your bankings sites for the most sensitive information is getting more and more cost effective.

Meet Guido (1)

dazedNconfuzed (154242) | more than 7 years ago | (#20592465)

See "Rubber Hose Cryptography".

A phisher's dream (1)

davitf (522408) | more than 7 years ago | (#20592473)

If this algorithm can be used to find the private corresponding key given a public key, someone would just need to get the private key for a certification authority (say, VeriSign), and they would then be able to create fake certificates at will. Of course the key would be revoked when the compromise is discovered, but a lot of interesting stuff could be done in the meantime. It would be very handy for creating phishing sites, among other uses.

Well... (4, Insightful)

morgan_greywolf (835522) | more than 7 years ago | (#20591601)

It doesn't necessarily mean the end of public key cryptography, it just means we'll have to come up with something other than prime factoring to compute the keys.

What this does mean is that there's going to be a lot of money to be made replacing public-key cryptograhy in custom code ala Y2K.

Re:Well... (1)

morgan_greywolf (835522) | more than 7 years ago | (#20591639)

s/factoring/factorization

Re:Well... (0)

Anonymous Coward | more than 7 years ago | (#20592281)

Dork.

Re:Well... (1)

Watson Ladd (955755) | more than 7 years ago | (#20591775)

Well, the problem is that Shor's algorithm can solve discreet logs in any group. This makes ECC unsafe as currently implemented. No one has come up with secure methods that will not fall to Shor's algorithm.

Re:Well... (0)

Anonymous Coward | more than 7 years ago | (#20591797)

Personally,

I'd demand one MILLION dollars!

What? Have I got a crumb on my face?
There, did I get it? What?

Dr. Evil.

Well...On both hands. (0)

Anonymous Coward | more than 7 years ago | (#20592625)

"It doesn't necessarily mean the end of public key cryptography, it just means we'll have to come up with something other than prime factoring to compute the keys."'

There's more to it than that. What one takes away, it can also restore. Quantum hardware and the corresponding algorithms will be the basis for future encryption. It's called an arms race for a reason.

how hard is it to build a quantum computer? (1, Interesting)

Anonymous Coward | more than 7 years ago | (#20591615)

it's a bit like nuclear weapons, in that you can pretty much "know" how a bomb works, but even if you had detailed plans, it's pretty much only governments who can build them.

of course, it's not such a good thing for governments to have unfettered access to all communications and banking details, but in general it won't be like your neighbours can spy on all of your banking transactions?

Re:how hard is it to build a quantum computer? (2, Interesting)

pclminion (145572) | more than 7 years ago | (#20591731)

it's a bit like nuclear weapons, in that you can pretty much "know" how a bomb works, but even if you had detailed plans, it's pretty much only governments who can build them.

I'm actually somewhat surprised that governments haven't passed laws banning the construction of quantum computers except under very tightly controlled circumstances. Kind of like how the ciphers themselves used to be classified as "munitions" in the United States.

Re:how hard is it to build a quantum computer? (3, Insightful)

Tanman (90298) | more than 7 years ago | (#20592079)

It is illegal. You just aren't allowed to see the law because the government has classified it "secret." If people were allowed to read the law, the justice department believes it would provide insight to enemies of the state on a possible exploitable vulnerability.

by the way, I'm just making this up, but I bet you believed me. Sad state of affairs we're in.

Re:how hard is it to build a quantum computer? (1)

Don853 (978535) | more than 7 years ago | (#20592239)

I thought you sounded like a clancy novel personally, but then again, /. has lots of paranoia running around.

Re:how hard is it to build a quantum computer? (1)

bdjacobson (1094909) | more than 7 years ago | (#20592163)

Now why would they do that? They'd lose all chances to use these quantum computers for their own means.

Re:how hard is it to build a quantum computer? (1)

aminorex (141494) | more than 7 years ago | (#20592235)

That would be quixotic, and irrelevant. Once the techniques are known, quantum computers can be built by anyone with the will and budget. It would be trivial to build an anonymous web-service to do decryptions with your home-built device -- and highly profitable -- so it will, inevitably, be done, if the market is created by an artificially imposed abolition.

Re:how hard is it to build a quantum computer? (1)

aminorex (141494) | more than 7 years ago | (#20592367)

Ah but, you have overlooked one crucial point: The "triviality" of building an anonymous web service depends on public-key cryptography, which is, upon your assumptions, a foundation of sand. Quantum decryptors will track you
down with the fearless inevitability of a pack of ravenous velociraptors.

Non-subscription link (4, Informative)

Anonymous Coward | more than 7 years ago | (#20591675)

http://www.huliq.com/34160/qubits-poised-to-reveal-our-secrets [huliq.com] seems to be a copypasta of the article.

Yeah, but... (1)

greenbird (859670) | more than 7 years ago | (#20591687)

Yeah, but who filed the patent first. That's all that matters.

Re:Yeah, but... (5, Funny)

Selfbain (624722) | more than 7 years ago | (#20591967)

Depends on the observer.

Big numbers (1)

Nonillion (266505) | more than 7 years ago | (#20591793)

Hmmm, guess I'd better start using a 1024 septendecillion or larger bit key.

Not the end (5, Insightful)

drabgah (1150633) | more than 7 years ago | (#20591801)

The quantum computer referenced in the summary managed the immense feat of finding the factors of the number 15. While it is true that factoring numbers of the magnitude used in cryptography is now a "matter of engineering", there are profound difficulties involved in scaling quantum computing. The fundamental problem is called "decoherence" and describes the tendency of quantum systems to become entangled with their environment, and the consequent loss of pure quantum states. The issues involved in quantum computation connect to deep issues of thermodynamics and entropy, and research on quantum computation has potentially great significance for fundamental physics. Cryptography may have to develop and implement new, extended standards as computational techniques evolve, but the encryption sky is not yet falling.

Re:Not the end (4, Funny)

Anonymous Coward | more than 7 years ago | (#20592185)

The quantum computer referenced in the summary managed the immense feat of finding the factors of the number 15.
...well come on then, tell us, what are they?

Re:Not the end (1)

tietokone-olmi (26595) | more than 7 years ago | (#20592243)

Indeed. At best, quantum computing will provide a different tradeoff from what is available right now. Perhaps it'll be a tradeoff into physical space.

Right now, it takes rather much physical space (racks of computers, cooling apparatuses, etc) and plenty of power to factor a single 1024-bit RSA key. Even then it takes enough time to be impractical as a routine operation. Certainly it can be scaled up to shorten the time, but diminishing returns apply and at the far end you end up banging your head against the limits of the interconnect used.

So yeah. The sun isn't setting on RSA quite yet. My current 2048-bit public key expires in 2012; given how fucking fast computers have got these past few years, I guess my next one is going to be at least 4096 bits. How much space and time is factoring one of those going to take, even with quantum computers?

Re:Not the end (1)

SkyFalling (1115231) | more than 7 years ago | (#20592321)

but the encryption sky is not yet falling.

Damn, guess I need to choose a new nick.

Re:Not the end (0)

Anonymous Coward | more than 7 years ago | (#20592537)

That depends.. are you a quantum computer?

What does the article actually say? (1)

mark-t (151149) | more than 7 years ago | (#20591811)

The first article linked to in the summary requires a subscription to read anything more than the synopsis.

post-quantum cryptography (4, Informative)

Spy der Mann (805235) | more than 7 years ago | (#20591821)

I googled (surprise!) and found this result:

"PQCrypto 2006: International Workshop on Post-Quantum Cryptography"
http://postquantum.cr.yp.to/ [cr.yp.to]

From The link:

Will large quantum computers be built? If so, what will they do to the cryptographic landscape?

Anyone who can build a large quantum computer can break today's most popular public-key cryptosystems: e.g., RSA, DSA, and ECDSA. But there are several other cryptosystems that are conjectured to resist quantum computers: e.g., the Diffie-Lamport-Merkle signature system, the NTRU encryption system, the McEliece encryption system, and the HFE signature system. Exactly which of these systems are secure? How efficient are they, in theory and in practice?

PQCrypto 2006, the International Workshop on Post-Quantum Cryptography, will look ahead to a possible future of quantum computers, and will begin preparing the cryptographic world for that future.

Very cool (1)

Kythe (4779) | more than 7 years ago | (#20592021)

Very interesting to know there are other algorithms which might resist quantum computing attacks.

It's also very good that the cutting edge of this technology is (presumably) being done and reported on publicly, so people will know if and when they can no longer protect their communications using certain methods.

Elliptic curve cryptography (5, Informative)

4of11 (714557) | more than 7 years ago | (#20591843)

Elliptic curve public crypto does not rely on the difficulty of factorization, so this specific attack wouldn't affect it, but I don't know if there are applicable quantum computing attacks. Too bad software patents are such an issue for it in the US.

Re:Elliptic curve cryptography (0)

Anonymous Coward | more than 7 years ago | (#20592503)

The answer to that question is that no-one knows. I believe that Elliptic curve is NP complete, but quantum computers have not been shown to solve NP problems in P time yet. Factoring known to be no harder than Elliptic curve, known NP intersect co-NP. Of course... we still don't kno if P=NP, but for now we can assume no-one else has the proof either.

new decryption methods == new encryption methods (2, Insightful)

jgarra23 (1109651) | more than 7 years ago | (#20591873)

This means that people will come up with new encryption methods that I couldn't possibly imagine (not much of a stretch). Based off these newly powerful methods people will find new impregnable methods. Sort of like how when people came up with the idea of wooden shields, someone came up with a way to pierce them so someone came up with metallic armor and then someone came up with the idea of a combustion-powered missile (gun) and someone came up with Kevlar and so on...

Re:new decryption methods == new encryption method (1)

Mattintosh (758112) | more than 7 years ago | (#20592069)

So what you're saying is...

Necessity is the mother of invention.

Right?

I think we all already knew this.

Of course the obvious solution... (1)

mark-t (151149) | more than 7 years ago | (#20591913)

Is to just use quantum encryption whenever transmitting encrypted data... supposedly, that's unbreakable (or at least not breakable without alerting the sender or receiver that you broke it), right?

Re:Of course the obvious solution... (1)

Phroon (820247) | more than 7 years ago | (#20592249)

I heard some fellow undergraduates of mine give a talk on "quantum encryption" last year. It took me a while to notice, but quantum 'encryption' isn't really encryption at all. It is just a secure way to distribute to exactly two people the same random data. You then leverage this security to make a one-time use pad that's (almost) as practically secure as it theoretically is. You still have to keep the pad a secret at both ends, but the transmission is foolproof.

No big deal (3, Insightful)

jd (1658) | more than 7 years ago | (#20591961)

RSA uses primes. This leaves the ones that don't: HFE, NTRU, ECC, XTR, Paillier, ElGamal, ....

Not PK encryption per se, the RSA implementation (3, Insightful)

ishmalius (153450) | more than 7 years ago | (#20591969)

The general handshaking mechanism itself is not in danger. It is the prime factor-based RSA algorithm. There might be other key algorithms in danger as well, but this doesn't reflect on the PK framework.

I work in the field and i have to comment, (5, Informative)

drolli (522659) | more than 7 years ago | (#20591991)

that it will be a really long time before QC are cheaper in terms of factorizing numbers than the equivalent classical machine. If they work at all. The common beliefs about the different QC other implementations in the field usually are said to be

-NMR: Most advanced no decoherence, but severe scalability problems. Nobody knows if they can ever put more than 10 qubits (
-Quantum Dots: Nice but Semiconductors have a hell of excitaions and decoherence
-Spintronics: Interesting, but it will take a time until it is under control
-Ions: well advanced, good control, some scalability problem (not necessarily IMHO)
-Atoms: advancing (-> Atom Chip), could be fine
-Superconducting qubits: Right now decoherence problems, which may be solved.

Quantum physics giveth... (1)

Atario (673917) | more than 7 years ago | (#20591999)

...and quantum physics taketh away. Looks like it'll be a race between quantum computing and quantum cryptography to see whether we're all left with a gap where everyone's vulnerable...

some perspective... (1, Insightful)

Anonymous Coward | more than 7 years ago | (#20592017)

Let me share a quote that my Complexity Theory professor at Carnegie Mellon said about this back in 1999:

"Quantum computing has the potential to change everything, no doubt about it. However, I won't get excited about it until they can factor a number larger than, oh, let's say, FIFTEEN. Until then, everything in this class about turing machines, P, NP, etc is still the world we live in."

That's the quote as best as I can remember it, and the number he said was really close to 15 if I recall. Bottom line, what he said is still true--this is fascinating, fascinating stuff, but we really need to see it happen for larger numbers!

-Jaro

Missing import facts about shors algorithm (1, Informative)

Anonymous Coward | more than 7 years ago | (#20592081)

Shors algorithm make use of probability functions that come from quantum mechanics, along with some other useful features such as the massive parallel processing you can get from qbits http://en.wikipedia.org/wiki/Qubit [wikipedia.org] ( you will see the probability functions in how they define qbits). Example you can't tell exacting where an electron around an atom is really at but you can say the statement like "80% probability that the electron is there." Shors algorithm makes use of probability functions such that incorrect answers tend to cancel themselves out without you doing a bunch of computations. You can't think of Shors algorithm in the traditional sense that f(x)=y, it is a probability function like the dirac equation http://en.wikipedia.org/wiki/Dirac_equation [wikipedia.org] .

sigh (4, Funny)

Ant P. (974313) | more than 7 years ago | (#20592091)

I finally went and figured out gpg just this week and it's already about to be obsoleted...

What Codes? (2, Insightful)

segedunum (883035) | more than 7 years ago | (#20592095)

It means the most dangerous threat posed by quantum computing - the ability to break the codes that protect our banking, business and e-commerce data - is now a step nearer reality.
It might just show how sadly cynical I am regarding many companies' attitudes towards security, but I looked at that sentence and and thought "This would actually make a difference?"

I'm skeptical (4, Informative)

Fnkmaster (89084) | more than 7 years ago | (#20592101)

This sounds like some serious breathless bullshit to me.

There have been quite a few different methods of quantum computing developed that take advantage of several types of quantum processes in nature. I worked on bulk-spin-resonance QC as a research assistant at MIT.

To the best of my knowledge, every method so far developed runs into coherence and noise limitations that make it very difficult to scale them up. It's usually not too hard to build a 3- or 4- qubit quantum computer, but scaling up the size seems to itself have an exponential characteristic to the problem. Basically, it's very hard to build a practical quantum computer that works on the scale necessary to factor even modest sized numbers. The engineering challenges to make any of these methods at all practical are bafflingly hard - the underlying science and math are pretty straightforward on the other hand, and the algorithms are undoubtedly cool as hell.

I understand these days the interesting work is on trapped-ion approaches and semi-conductor approaches.

Anyway, Shor's algorithm has been around for years. The theory behind QCs is fairly well understood, the experimental difficulties are huge.

Basically, unless this represents a real breakthrough, i.e. a technique that is not just scalable in theory but can be demonstrated practically to be linearly more difficult to scale up the number of qubits, then it's not a breakthrough that anybody needs to worry about yet.

Without seeing this article's full text though, it's hard to really know, but I gather optical approaches have been tried before and haven't gotten any further than anybody else has.

Quantum cryptography (1)

shentino (1139071) | more than 7 years ago | (#20592159)

Read about this in a book. Wouldn't this be a solution? They say it's fundamentally unbreakable, even WITH quantum computing. An idle boast? Or the solution we've finally been looking for?

Re:Quantum cryptography (0)

Anonymous Coward | more than 7 years ago | (#20592287)

That's not cryptography, it's just a way to tell if someone's snooping.

Shor's algorithm (1, Informative)

Anonymous Coward | more than 7 years ago | (#20592227)

Scott Aaronson has a wonderful explanation of how it works (including why it's so much faster with quantum) at http://scottaaronson.com/blog/?p=208 [scottaaronson.com] .

Therefore... Quantum Computing Illegal in US? (2, Insightful)

zrgn (169645) | more than 7 years ago | (#20592329)

So can I guess an American university has not been able to do this because they would be put in jail (DMCA). "I'm sorry we can't cure your cancer because the technology used to do this could circumvent digital property rights and encryption algorithms."

Quantum Computing Is Pure Unmitigated Bullshit (1, Troll)

MOBE2001 (263700) | more than 7 years ago | (#20592345)

How much do you want to bet that this is pure bullshit and that nothing will ever come out of it? This is just another plea for funding. Quantum computing is the biggest scientific hoax/bullshit in the history of science. Physicists have no clue as to why nature is probabilistic and yet, they feel qualified to claim (without any evidence to back it up) that certain quantum states are superposed. What they are are claiming is that states are suppoerposed but you can never observe supperposition because, as soon as you do, it causes a collapese of the wave fucntion and the superposition disappears. This reminds me of a kid who insisted that he could jump as high as a mountain but only when nobody was looking. Yeah, sure. Whatever happened to empiricism? Voodoo physics is all this crap is.

So yeah, go ahead and mark me as a troll but I am right, goddamnit! It's all bullshit.

Re:Quantum Computing Is Pure Unmitigated Bullshit (1)

n6kuy (172098) | more than 7 years ago | (#20592483)

> This reminds me of a kid who insisted that he could jump as high as a mountain ...

Well I can jump HIGHER than a mountain!
But that's because mountains can't jump...

the inverse? (2, Interesting)

j00r0m4nc3r (959816) | more than 7 years ago | (#20592359)

Can quantum computers be used to create encryption keys that other quantum computers cannot solve in linear time? Perhaps computers will someday each include a QPU (quantum processing unit) that would be dedicated to performing such tasks.

No more secrets (1)

InlawBiker (1124825) | more than 7 years ago | (#20592369)

Are Robert Redford and Sidney Poitier somehow involved in this?

Just RSA, actually (5, Interesting)

geekgirlandrea (1148779) | more than 7 years ago | (#20592399)

*sigh*

This doesn't break "public-key cryptography". Even if you could build a Shor-factorization machine big enough to use against real-world keys (and that's a *big* if), it's only good against RSA. Elliptic-curve cryptosystems, for example, would be entirely unaffected. In general, the question of whether general-purpose quantum computers would break all public-key cryptography is a really hard one. It's equivalent to whether there are any trapdoor one-way functions which are in P [caltech.edu] but with inverses not in BQP [caltech.edu] . Even the existence of non-trapdoor one-way functions is still an open question; they would have to have inverses in , and proving that would also imply P != NP. All the existence of Shor's algorithm really shows about that problem is that there is at least one problem, integer factorization, which is in BQP but (probably) not in P. [caltech.edu]

Anyway, it's a long way from running Shor's algorithm to factor 15 to being able to factor a 4096-bit RSA key. Remember that because of the no-cloning theorem you can't build a flip-flop for qubits, so quantum circuits are all combinatorial logic. Applying Shor's algorithm to real-world RSA keys would require building a complete modular exponentiator combinatorially out of quantum logic gates, wide enough to deal with the biggest key sizes practical for anyone to use (and the cost of RSA encryption/decryption only scales linearly with the key size). We couldn't even build that out of regular non-quantum logic.

Brain's Alzheimer disease algorithm. (2, Funny)

Neanderthal Ninny (1153369) | more than 7 years ago | (#20592501)

I'm going to use my brain's Alzheimer disease algorithm to encrypt everything since in a few years I won't able to remember anything and therefore no one would be able to get it, ever. Now where the heck I put my car keys at...

So you're saying that... (1)

jpellino (202698) | more than 7 years ago | (#20592627)

Pretty soon, even if I make sure the cute little lock (ah! there it is!) is on on my browser, someone will be able to klaJADf llkqjwer wlkertuidf hjaidf adfy ajsdf yadsfhjm, werl sdfi iughj ajkajhsdfdk ?

Thssag!

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?