Slashdot Mirror
The Possible Effects of Quantum Computing
craigj0 asks: "When quantum computers become more possible it will destroy our current encyption schemes but create a new type. My question is will it destroy non-factoring based encryption? And if it does what will the world be like during the transition stage from classic computers to quantum computers? How will the internet work when not all people have quantum technology and still want their digital privacy? Perhaps quantum plugin devices may be used to create hybrid computers?" Interesting issue here: What futures does Slashdot forcast when Quantum Computing becomes a reality?
Adoption of quantum computing will be delayed in the financial arena by early bugs:
Plaintive customer: "My account can't be empty, I checked the balance this morning and it had over $1000 in it..."
...been up too long, sorry.
Quantum computers are at least a decade away, and by the time they're mass-produced, privacy will be a thing of the past. We're heading that way now, and it's only a matter of years before privacy advocates are viewed in the same way the tin-foil-helmet brigade are viewed today. I'm not just talking about echelon and other such programmes; every aspect of life is coming under supervision as the technology allows it.
People only view privacy as a right because in the past the powers that be (be they PHBs or government spooks) hadn't got the wherewithal to spy on us all.
If you work on a computer, your email can be monitored, as well as your keystrokes and your high scores in tetris. If you walk through any city centre, you're probably on camera for 90% of the time.
Quantum computing will be the final nail in the coffin; encryption will let people hold out for a while, but once your VA Quark comes online, you can bend over and kiss your privacy goodbye.
Abacus to Thinking machine
ENAIC to PIII 700
Ipv4 to IPv6
no encryption to 128 bit encryption
All have something in common... dramatic change.
But, all of them happened in phases... I don't
think quantum would be used by poeple like you and me in the first go. Most probably banks... then it would, over the years, permeate over to the public... it would be gradual... might take 5 to 10 years.... I don't think we should be afriad of change.
rkt
I first read about quantum encryption in some long lost article about three or four years ago. The basic premise involves polarizing photons as they travel down a strand of fibre optic cable.
Okay, I just did a quick search on Google and turned up a recent article in New Scientist describing the process and the issues facing practical, widespread implementation. Still, it looks quite promising.
Cheers.
It seems that if quantum computers ever become a reality (if they haven't already...), they will be the toys of nuclear powers and their favorite universities for quite a while--like the bomb and Berkeley. After a bit, large corporations will be able to afford the technology, and a few will find uses that warrant the tremendous cost. There will be an effort from day one to bring the technology to the home user, but quantum physics are pretty out there, and the devices will be doubtless very hard to miniaturize.
So, most of us will be forced to use RSA, even when we know the the echelon system can crack our 4096-bit export-restricted keys in all of 2.3 ns (give or take a few orders of magnitude).
This will lead privacy-concerned Americans to do what is becoming popular in countries where strong crypto is illegal: we will turn to steganography. For those slashdotters who haven't read Simon Singh and aren't up on their cryptic (no pun intended) english, that's the art of hiding messages. We sometimes call it security through obscurity. We all know that it's not really no security. If I'm correct, it'll be the best security available to us.
I actually got to ask Simon Singh this question at a recent book reading, and his reply was quite interesting. He pointed out that in addition to the inroads on personal privacy and financial security, the real danger might lie in the realm of world politics. He suggested that the presence of governments that basically posess information omnipotence could drastically alter the balances of world power that we currently have. We all know that the Allied crack of the German cryptosystem was crucial to our victory in WW2. International-conspiracy theorists/prophets should have a field day with the possibilities.
in this interview he gave with /.
" And when it becomes a reality, it does not destroy all cryptography. Quantum computing reduces the complexity of arbitrary calculations by a factor of a square root. This means that key lengths are effectively halved. 128-bit keys are more than secure enough today; 256-bit keys are more than secure enough against quantum computers. "
It has taken years of research just to build a two or three bit machine, and increasing a RSA or DH key by just a few bits would require doubling the number of "parallel universe computing cells" that are required to crack it. I can't see massive, secret research on this being funded well enough - particularly as it is "cheaper" in most senses to use other methods to defeat keys (most of which require physical intrusion to the machine in question or subversion of trusted personnel, but that has always been a standard operating procedure).
At worst, I think we will see the minimum key sizes considered secure increase, maybe by an order of magnitude, but without a change to the fundamental schemes in use - after all, with QC we are talking faster application of existing techniques, not a entirely new field.
--
-=DaveHowe=-
What futures does Slashdot forcast when Quantum Computing becomes a reality?
Ubiquitous spell checking... I hope.
First, I'd like to point out that quantum computation and quantum encryption are two almost completely separate concepts. Quantum encryption is based on the fact that quantum states cannot be measured without altering. The most common example is the polarization of a photon, but it will work for any quantum state, so long as there exist, effectively, two unique states that can transmit the data.
Quantum computation, however, is much more complex and much more interesting. Quantum computers are based on the concept of quantum entanglement, the ability of a quantum state to exist in a superposition of all of its mutually exclusive states: It's a 1 and a 0. However, this is not as easy to use as one might think. While it's true that if you have n quantum logic gates you have the ability to input 2^n data values simultaneously (as opposed to only 1 piece of data if you have n digital logic gates), this is not going to be the end of classical computing for a few reasons. First, quantum computers have to be perfectly reversible. That means for every output there's an input and vice versa. And there has to be no way of knowing the initial states of the data. You don't process data, you process probabilities in a quantum computer; if you know exactly what any one value is throughout the computation, you can find out all of the values: the superposition ends and you're stuck with a useless chunk of machinery. This means YOU CAN ONLY GET ONE RESULT FROM ANY QUANTUM COMPUTATION, THE END RESULT. You can't see what the data in the middle is or the computer becomes useless. (Landauer's principle makes heat loss data loss. When your processor gets hot, it's losing data. If the same thing happened to a quantum computer, it wouldn't be quantum anymore.) Decoherence is what happens when you randomly lose data to the environment by design, not by choice, and the superposition ends. This is bad for Q.C. Oh, and quantum computers can only do *some* things faster, like prime factorization and discrete logarithms. Not multiplication or addition. Plus, the circuits that would do basic arithmetic would be bigger and slower than what you've currently got.
So what does this all mean? It means that quantum computers are going to provide some advantages (real quick big number factorization), and some disadvantages (that whole RSA standard). The most realistic initial use of quantum computers will be as add-ons to existing super-computers to resolve certain types of NP-Complete headaches that regular math can't simplify yet. At best they will someday be an add-on to your PC; but they will never replace the digital computer.
- HyLander
If you want more info, check out http://www.qubit.org, it's got some decent tutorials, or email me at hylander42@hotmail.com.
An mistake all too easy, my fellow earwickers. Quantum encryption requires direct access to the fiber-optic line on both ends, it provides an eavesdrop-proof channel since something (i dunno) will be skewed about the way the incoming photons are polarized. Quantum encryption is based on the properties of photons and really has very little computing going on for it. It is, in our current models of physics, perfect. Perhaps trusted key distribution centers for the future that are linked by quantum encryption can serve as one-time-pad sharing sites.
First time I heard of quantum encryption, I thought that they were considering Bell's theorem: get random pad information by manipulating a pair of twins. Though you cannot communicate using the twins themselves, the random noise that you can get by analyzing states (simultaneously?) can be used as a one-time-pad.
Quantum computing will not break symmetric ciphers. It can, however, search key space much faster, reduce complexity by the factor of a square root. That is, once it becomes feasible... Stupid quanta are not cooperating.
With assymetric ciphers, including El Gamal-type elliptic log thingies, RSA's large primes, and all those broken and ready-to-be broken knapsack problem, quantum computing will be far more effective. Ideally, QC will be able to reduce these NP complete and NP-hard problems to solvable in polynomial time.
Also, I'd like to point out that the complexity of RSA does not double with each additional bit... 4096 bit encryption RSA does not have 2^3968 or so more possible keys than 128 bit TwoFish... It supports large prime products as big as 4096 bits (or was it large primes?) The spacing of primes at big numbers and our almost-decent sieving schemes...bla bla bla.
Now, if quantum computing can reduce the amount of power used by my puters, or if it allows me to build either a quantum death ray or time machine, I think its time for me to transform into a rabid koala.
Back to reading Parzifal...
As some one with an active interest in the field, here are some answers. Yes, quantumn computing allows for efficient factoring of numbers: but that is not the end of the world. Quantum Cryptography is at least a decade old and is a thriving research area amongst theorecical computer scientists, physicists and mathematicians. In fact these protocols are *provably* secure unlike RSA etc whose security in the classical world is based on unproven assumptions. This will guarantee unprecedented privacy over the internet or otherwise. There is nothing to worry on this count.
Also, we do have a reasonable idea on what can and cannot be done using quantumn computing. For example, it is unlikely that it can solve NP-complete problems such as the travelling salesman problem. (Ok, I will not be too shocked if somebody discovered a way to solve NP-complete problems using a qm/c... but it cannot do much "more".)
How far are we? Quite far from replacing the current chips, we are currently able to experiment with about 100-200 gates. Maybe in ten years, we can hope to have a reasonable machine which can do useful things.
In the future, things will be even more secure than they are now. If anything, it's PHBs that are holding back encryption, simply because they don't understand it.
Having things 'online' is in itself still relatively new. Back in the 80's you could hack most places simply by dialing in! They didn't see the need for things like passwords, etc. Why, back when Bellsouth was first discovering major hacks done to it's system, they couldn't understand that people would want to abuse their system like that. It was all wide open then. In the future, things will be more like "Gee grandpa, you mean most of your transmissions were done in plaintext?" and "JETSON! Stop using such a fraggin weak encryption! I don't care if it's just an email to your hottie wife!"
The simple fact of the matter is this: Quantum computers are different tools, and they have different applications. Coincidentally, some of those applications are ``hard problems'' to regular computers.
It's like quantum mechanics: if you want to explain the motions of planets about the sun, I don't suggest you try to solve Schordinger's equation for all the particles in the system. That's a really hard problem in QM. But it converges to Newton's laws in the macroscopic, so using these ``classical'' techniques becomes not only faster, but correct.
Additionally, QCs will need glue to talk to the world; I assume eventually people will want to connect them to networks, and IP addresses are not superpositions. So we will use ``classical computers'' for a long time, just as we still use ``classical mechanics'' for problems which crack well under their scrutiny.
Eric
--My stack runneth over.
I find this of interest: A straight line on a standard Euclidean distance metric can pass through an infinite number of algebraic numbers, that being, numbers that are a combination of a finite number of finite roots of primes. Whereas a line in contact with this algebraic line may pass through an infinite number of transendental numbers (ie. pi). These two lines may not differ by a real amount, ie. any number added to one or the other results in something larger than the difference of any two points on either line (respectively the same distance from the origin).
Anyway, I think it's neat because one can create a transendental number, extract points at some finite distance down the line (ie. 2^120,000) of it's digits, and you may have a unique number sequence. Without knowing the transendental number, it is quite a difficult problem to solve. But it can be approximated . . . for now, SFAIK.
All algebraic numbers can be expressed as the roots of primes. With finite precision numbers, transendental numbers can be approximated as the roots of primes.
Interesting, nonetheless . . .
Most of todays crypto algorithms rely upon the fact that given f(x,y) it can be difficult to find x and y. Multiplication is O(N) wheren N is the number of bits you're working with. The computational complexity of factoring is not known, though it seems to be in a class of problems which we call NP - using nondeterministic methods they can solved in polynomial time (indeed, for factoring, linear), or in otherwords, if you could try all of the possible answers at once, in would only take you O(N) to tell which one is right.
Currently the best we can do is solve NP problems in exponential time - we just try all the answers serially (sure, we can exclude a lot of possibilities, but not enough to REALLY get things fast). It hasn't been proven that NP problems cannot be solved determinisitically in less than exponential time, but most people think it's probably true.
The whole reason to switch over to quantum computing is that it provides nondeterminism. That doesn't mean we can theoretically calculate anything we couldn't before (this is proven), just that some calculations may get easier. Such as NP problems, which by their very definitions are solvable in polynomial time, using nondeterminstic techniques.
Any encryption algorithm that relies on NP problems being extremely difficult to solve will be broken by quantum computing. I'm no crypto-whiz or nuthin' but it seems likely to me that all common crypto relies on this assumption.
There are computational problems that are harder than NP problems, but they're not all that common, and really hard, so they haven't gotten a whole lot of attention. I imagine that if quantum computing took off, these would see a lot more research.
Trees can't go dancing
So do them a big favor
Pretend dancing stinks!
Question: Just because a Quantum computer can (it seems, by this discussion) process all possible inputs and outputs at once, how does it know which output is the correct answer?
It is interesting that quantum computing will substitute in place of "correct answer" the notion of "most probably correct answer". This is because quantum mechanics is basically a form of probability theory (using probability amplitudes--one amplitude represents the "prepared state" and the other represents the measurement apparatus).
As a physicist interested in the foundations of quantum theory, I am bothered by a lot of the literature I have seen on quantum computing--not all that much, but I've spent a morning reading through a site here and another morning reading through a site there, etc. There is a lot of overly literal adherence to the pretty old fashioned Copenhagen interpretation, which a lot of people have serious differences about. (Not that this should affect the results when they are finally obtained, but it seems that possibly faulty mental models of what is going on may hinder progress.)
One of the more interesting possibilities is that there are methodologies related to the present quantum computing paradigm which may be more immediately accessable. For instance, encryption can be thought of as a series of translations and dilations of the number system--take the number representing some item of information and subject it to a series of addition and multiplication processes. The study of invariance under translations and dilations in ordianry data is usually undertaken with wavelet analysis. Wavelet analysis uses similar mathematical tools to quantum theory (expansions in overcomplete sets of basis vectors), and in fact you can analyze at least some quantum state vectors using wavelet analysis in a fully quantum compatible formalism. )I.e., a probabilistic formalism results.)
There are a lot of mathematical tools out there which have never been (publicly) used in the crypto context, and it may be that quantum computing may ultimately result in an awareness of methods equivalent to quantum computing which are easier to implement. Thus, rather than technologically challenging q-computers, there may be algorithms which enable you to implement a non-sequential computation algorithm (i.e., avoid the von Neumann bottleneck, as well as completely rewrite the concepts of computability and even decidability) on a sequential device. It may thus be possible to do something like an integer wavelet transform on a signal, put up some kind of display, and **look** for visual patterns in the display which would indicate a complete or possible partial solution, etc., reducing computation time from millenia to hours.
"Some will own a Quantum Computer and offer free (quantum) encryption (in return for banner ads). "
Hmm, not at first. The economics of the thing will probably preclude this form of "free" usage - ie you pay only for downloading the banner. If you charge a nominal fee, say a few quid a month, it will prevent the masses from _really_ wanting it - I don't think people on the net as a whole _really_ understand what's at risk. Still, give it a few years, and maybe the populace will be more privacy-savvy - we can only hope...
Strong data typing is for those with weak minds.
Spammers will be able to send their email to all possible addresses simultaneously. You'll open a new account and your mailbox will already be full. You'll also get spam from spammers in parallel universes trying to get you to visit porn sites featuring improbable alien teenage life-forms in hot steamy action. Forward this message to an infinity of other life-forms and receive good luck forever. Send this message to Microsoft and receive more $$$s than there are atoms in the Universe. Hit Reply to be removed from future mailings.
(I'll go lie down now.)
Regards, Ralph.
How the computer operates is beside the point. The people who use them are still going to be assholes to the people who keep them running. So it sucks in quantum amounts; it still sucks. So we'll have "F1rst QuAnTuM P0st!" articles instead. Spam will come in multiple flavors: up, down, strange, charm...
All hardware sucks. All software sucks. Everybody is considered a jerk by somebody. Lusers get LARTed, BOFHs get drunk. The sun rises, the sun sets, the Sun crashes. It is the way of things.
-A Sysadmin Having a Bad Day
You cannot apply a technological solution to a sociological problem. (Edwards' Law)
Do you actually know what you are talking about, or are you just making this up?
Last time I looked at quantum algorithms it was far from clear that random search problems can be sped up like that. Some forms of database search go from O(n) to O(sqrt(n)), but that's not a fenomenal speedup for searching encryption keys.
RSA is in trouble, of course, since there actually exists an efficient algorithm for factoring.
As I understand it, the tricky part of quantum computing is to actually extract useful information when you finally observe your quantum state. Just being able to operate on a vast number of initial states gives you nothing if you can't extract something at the end.
If you have a reference to the result you claim I'd be very interested.
Not to mention the difficulting in finding some ICR (Invisible Character Recognition) software.
Working quantum computers with a reasonable number of qubits will render all current public-key encryption techniques useless, regardless of the key length used. Peter Shor has exhibited explicit algorithms for solving the factorization and discrete logarithm problems in polynomial time using a quantum computer. Since all major current public-key systems (El Gamal, RSA, Diffie-Hellman) are based on one of these two problems (sometimes a generalization of dicrete log to elliptic curves) they are all then breakable in polynomial time. Which means breaking them is a very easy problem given fast quantum computers, not much more difficult than encrypting/decrypting a message using them. The algorithms involved use some nifty randomization techniques, quantum Fourier transforms, and basic group theory; see the paper on quant-ph if you're interested.
As far as symmetric ciphers go, I don't know of any algorithms to break them using a quantum computer. It doesn't seem to be an especially difficult problem, however, and I wouldn't be surprised if the NSA or someone had already written up a few to crack 3DES, Blowish, etc.
Quantum encryption will possibly provide a secure alternative; basically the idea here is that the two parties involved use a shared quantum source to generate identical one-time pads. Artur Ekert showed that the parties involved can use the Bell inequality to detect any interference in the shared quantum data; it appears this is generally true for any sort of interference in the commonly generated data. Now quantum encryption is provably impossible to break as it provides a completely random one-time pad; and it seems likely that if quantum computers become a reality we will have stable enough quantum systems to make quantum encryption a reality.
So the net result of the whole quantum thing will probably be the destruction of all previous cryptographic schemes and the use of quantum cryptography. That's assuming we ever build a useful quantum computer, which is by no means assured, given the large difficulties currently faced in the field.
Also, it's unlikely that quantum computers will ever become a device for common use; simply because they're not a replacement for the classical computer. A quantum computer would require a ridiculous amount of classical control and error-correction hardware to run at all. Also, you wouldn't be able to just program it. Quantum computation requires special algorithms that can be parallelized correctly to work at all; it takes people who know quantum very well to come up with these algorithms.... you can't just plug a program into a quantum computer and expect it to run quickly.
So most likely, even if they become widespread, quantum computers will just be used as an "add-on" sort of module to do massively parallelizable computationally intensive things, like Fourier transforms, prime factorization, etc.
A great deal of the usefulness of quantum computers depends on whether they can solve NP-complete problems. This is as yet unknown, but some preliminary work indicates that using special nonlinear aspects of quantum behavior, systems may be developed which can do this. There is evidence indicating standard quantum computers will not be able to generally solve NP-complete problems.
Ali Soleimani
alis@caltech.edu
Caltech Phys/Math
Tom Swiss | the infamous tms | my blog
You cannot wash away blood with blood
I don't know of anything that's nearly as convenient as RSA or DH for privacy/key exchange, except maybe Maurer's scheme where you need a satellite that transmits random bits to the world, and every receiver gets its own noisy copy.
Just to play devil's advocate for a second....
The tools still need to exist (in Law Enforcement's eyes) in order to decode encrypted data upon issuance of a warrant. But just because those tools do or could exist does not mean that they will automatically be abused.
As more and more of the world goes digital (or whatever term you care to use), and especially as it pertains to "white collar" crime, pretty much all the evidence linked to a crime could end up being encrypted. For instances like that, there needs to be a means to access that data in relation to an investigation.
So long as you're not doing anything wrong, then there isn't any reason why anyone in a position to use such a machine would want to see what you've been reading or writing. If you are doing something wrong, then... tough luck, i guess.
Now don't get me wrong here. I value my privacy as much as everyone else. I just think that just because something can allow something to happen, doesn't automatically mean its going to be abused.
I'm sure we've gone over this many a time on Slashdot, but OTP (in my mind at least) is essentially useless when mentioned in a conversation concerning public key crypto. If i have to revert to physically handing a CD of padding material to everyone I wish to commincated with, then basically it's useless compared to what PK has been for many years.
And besides, "anything thats important to encrypt...". My thought says you shouldn't do it that way. Just encrypt everything so as not to have anything jump out as automatically being the "interesting" file....
Or something. quantum quantum quantum (trying to increase the quantum content of this post.)
Hey, who hasn't slept in days? It's me! ;)
>I wouldn't be surprised at that point if supercomputers were to become classed as munitions,like strong crypto is now.
Actually, it wasn't that long ago that it was illegal to export any computer that rated over 500MIPS out of the US... Of course, once everday desktops hit these barriers, it seemed kinda silly, but when only the massive machines could rate that high (on an admittedly semi-bogus scale), it almost made sense. With computing power still scaling near Moore's law, it's tough to put a reasonable limit on it, seeing that by the time it gets through Congress, it will already be as outdated as the hardware it was trying to protect...
"It's tough to be bilingual when you get hit in the head."
Well, there is LinuxPPC and I believe an older port for 68ks, and OpenBSD runs on just about anything more powerful than a Casio wristwatch 8^)
An industry-standard PCI QPU-card could be used with either platform (and let's not forget Alphas, either). The card itself doesn't usually care about the OS / host CPU, as long as the appropriate drivers / access methods are used.
Just my $(0.0004)^.5
"It's tough to be bilingual when you get hit in the head."
If I recall correctly, you have to structure your quantum algorithm so that the solutions to the problem enforce one another and the anti-solutions?? interfere. Exactly how this is done I am not sure.
Wow. Cool. I was serious, too... :-)
/am/ a sysadmin, and I /am/ having a bad day, and that /is/ how we look at advances in computer technology. Not something to be avoided, nor something to be feared, just something that will cause more fscking lusers to waste our time and make money off of us without helping.
I forgot to give attribution to the Sysadmin Rant ("...the way of things.") part at the end of my post, though (Steve Conley).
I
You cannot apply a technological solution to a sociological problem. (Edwards' Law)
So far as I am aware the proposed use of quantum cryptography is to use it to pass, say, a 3DES key and then carry out the rest of the protocol using symmetric key encryption.
Oops, I meant quantum *computation* can be used to render the factorisation problem tractable.
Working quantum computers with a reasonable number of qubits will render all current public-key encryption techniques useless, regardless of the key length used.
What do you mean, "reasonable number"? You are talking about at least 4 kilobytes, right? 16,000 bits / 3 for error correction / 2+ for Schor's factoring algorithm heck of a lot of qbits.
Assuming "forseeable breakthroughs", QC is probably going to be expensive and slow. Chances are, you're going to have serious cooling infrastructure, and radiation shielding, and possibly massive magnetic fields if you're using spin-based quantum states. You're going to have effective number of bits cut by at least a factor of three through error correction (and there's really NO way around that). In order to move data from place to place, you're probably going to have to either physically move something around or actually transfer data through a long chain of intervening bits from source to destination. And there are reasons why you won't want the clock rate to get too high.
Even assuming that we do get kilobyte- or megabyte- quantum computing, I don't think encryption would be useless. If "polynomial time" means "6 hours on a million-dollar machine", then I think it's still worth encrypting things. And if Moore's law holds for QC (I doubt it will; QC is too specialized a need to bring to bear the societal resources that have caused Moore's law) we wouldn't have QC on that scale for 20-40 years.
[A year or so ago, I amused myself by projecting Moore's law outwards for both classical and quantum computing. I believe both halves of this projection are overoptimistic, but it's fun. The answer I got was that the first time you would ever be able to solve any problem more cheaply using QC was in 2026.]
The last paragraph of the parent to this comment, though, is very important. We haven't even built linear quantum QC's yet, and already it's looking as if they'll only buy us a square root on NP-complete problems. When it comes to nonlinear quantum QC's, the algorithms are an order of magnitude more mindbending. This is really, really hard stuff, and nobody really knows what's possible. It may be that nonlinear effects make simple error correction exponentially hard, and then you're back where you started.
Preferential Voting: easy as 1-2-3
The major cryptographic interests w.r.t. quantum computing in this area is the ability to calculate transendental numbers to a given precision such that algebraic approximation is no longer a viable option. The question is the method of transendental number generation.
The area has interest.