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?
well, two things...first, goodbye moore's law.. secondly, this kind of reminds me of the mr. fusion in back to the future: it's one of those things that you can't really imagine being around until you actually get one, or see one, etc...almost like some kind of weird outer limits episode....who would have thought 10, even 5 years ago, that people would be talking about having quantum computers in the short term. oh well. guess that's just technology. i never thought i'd see 1ghz pcs, but that's just me.
Quantum Computers are not going to be something the general public is going to have access to - more likely, there's going to be some servers here and there, where people can rent time (I guess cycles won't work). Possibly HUGE systems that fex. resembles the Ray/Client stuff from Sun.
Unable to read configuration file '/bigassraid/htdig//conf/14229.conf'
Geocrawler error message.
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 Computing permits acting upon every possible input to an algorithm simultaneously. It'll render all current crypto-systems (save for know-if-they're-eavesdropping systems like Quantum Crypto, which isn't really encryption, exactly) obsolete. A brute-force attack would be down to two steps, each of which would take a trivial amount of time: 1) generate all possible keys and 2) run them through your algorithm and see what comes out. Folks have already developed database searching algos for Quantum Computers, which would make brute-force attacks (even on wicked-big RSA keys) a breeze (noting that you'd have to save every output that every key generated, and then check those for being possibly meaningful text rather than garbage. Again, a trivial job, time wise.) The only real problem, then, is nailing down memory of sufficient size to hold your temporary files and results.
Much Love,
"S"HM
*****
(I refuse to spellcheck out of contempt for your belief system)
Why not just go backto invisible ink on plain old paper? Sure as hell beats all this quantum crap, and it's cheaper too!
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.
In all likelyhood, if this stuff comes to pass our manufacturing technology for miniture systems will be so far ahead of what it is now that you'll get a quantum computer for $0.99 with the purchase of a McDonalds Happy Meal. At least this will be the case by the time anyone manages to get a qubit-based computer to do anything worthwhile that actual results can be pulled from.
Quantum compu's: 1, 0 and something in between, I just can't get a good picture of what kind of effect that should have, My hole electronic world is binari, and I think that your's is to!
I'll just have to (crys) wait and see;-(
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.
I don't see this as too much of a problem. Most of the traffic on the web is unencrypted.
Eventually some enterprising young scalawag will put go and put one of these new-fangled devices on a PCI card and solve all of our problems. Until then, the people that want to secure their data will just have to go back to good old-fashioned physical security.
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.
100 years from now computers will be twice as powerful, 10000 times larger, and so expensive that only the five richest kings of europe will own them.
-professor frink, the simpsons
icq:=22921393;
It'll render all current crypto-systems (save for know-if-they're-eavesdropping systems like Quantum Crypto, which isn't really encryption, exactly) obsolete.
I just don't get how it could render one-time pads obsolete. Not that they'd be really useful, but the outcome is essentially 'real random noise'. You'd have to test against guesses based on the nature of the pad generator used.
I think, therefore thoughts exist. Ego is just an impression.
The only real problem with Quantum Computing is that as as every single possible answer to a query is computer, windows will crash in an infinite number of ways in no time whatsoever! ARGH! there you go see, dont really care about encryption also, saying that Quantum computers will only ve available for rent or for temporary use is like what the people in the 50s and 60s thought when they first heard of the "Super Computers" i also think that moores law will never be truly accurate, but rather it will change over time and adapt to the current technology. There will always be downsides with quantum computing, most of which would be power constraints and the general reliability, as Quantum physics is not really a proiven thing, but rather a theory that is heavily supported :) I'm off Please, dont mind the typos i am using a bad keyboard at (ugh) school
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.
When the time comes that quantum computers are common enough to destroy today's common encryption systems, then we will simply have to rely on uncrackable encryption. Although I'm sure many of you will disagree, anything that is actually important enough to encrypt should use a PAD encryption scheme anyway. Less convenient? Yes. Completely secure (save physical theft)? Yes. Take a look at Hardened Criminal Software for those of you interested in learning more. Who needs quantum computers. Just use encryption that's uncrackable!
A number of people have posted how cost will cause have/have-nots. How do you justify this? Qubit-based computers will NOT be expensive to produce. The research will (and does cost a lot), but a lot of it is being done by the government anyway, who doesn't need to recoup shareholder value. The problem with QC wont be cost, the problem will be that no one really knows what we can do with them. Its kind of like having an infinite number of monkeys typing..Sure, one will produce the greatest written work man has ever seen, but how the fuck do you sort through all of the results to get to the answer? Nobody has any answers for that with regards to QC, and it might just be a dead-end in terms of usefulness.
First of all, there is a difference between Quantum Cryptography and Quantum Computing. Quantum Cryptography involves sending a particle (a qubit) to the other party you are communicating with. By knowing a specified property of this qubit, you can detect whether the particle has been measured in its journey, which means someone is eavesdropping. This is all quantum cryptography does, and it has been done already by several companies.
Quantum computing is a whole different ball game. It uses qubits as well, but several of them. The most qubits that have been used successfully as far as I know is 8. The qubits work like binary bits, except they can be both on and off at the same time. This allows all possible outcomes of a computation to be detected at once. The advantage that quantum computing will have for cryptography is the ability to factor extremely large numbers REALLY quickly. More quickly than any current computer. I recall from a book that a quantum computer with a relatively small number of qubits (32 or something) could factor a number in minutes, that would take a supercomputer millions of years to do. There are lots of great books on the subject too.
Hey I'm a big Slashdot fan but give me a break! This has to be the most obtuse, irrelevant, uninteresting "Ask slashdot" I've seen yet.
The slashdot community barely uses PGP and quantum encryption is... what?... 15 years down the road? And how many slashdot users are sufficiently knowledgable in the science associated with these two technologies, much less the sociological impact?
It would sure be handy to be able to moderate the editorial judgement of the posters....
Just my two cents...
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.
Ironically, I was having this same conversation with Juris Hartmanis the other day. When he was heading the NSF study on the future of computing, everyone was going nuts about the forecast of quantum computers destroying our current infrastructure. However, he was confident that no one alive today will ever see a quantum computer. If we make leaps and strides in physics, we may be able to build a 100 million dollar one, but that's about as practical it will get in our lifetime.
However, it's an interesting problem in computer science to think that there could be a computer that is fast enough to shred even our most "secure" algorithms. But, realize that even non-factoring-based encryption methods will be vulnerable, for a quantum computer could essentially solve any problem by brute force. However, there are computer scientists studying truly "quantum" encryption methods. The basis behind these algorithms, though, is the assumption that we have super-fast networks, too. For, I assume, they require a much, much larger cyphertext-to-text ratio.
So, instead of relying on our hardware to be slow, we will need to establish good theory (and software) to provide security and privacy.
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!
Shor's algorithm allows factorisation with cubic effort on a quantum computer, so RSA would be vulnerable. A simmilar algorithm can be used to break certification schemes based on discrete logarithms.
As for symmetrical encrytion schemes, Grovers database search algorithm allows to serach N items in O(sqrt(N)) steps, which would require the key-lengths to double to prevent a brute-force known plaintext attack. This should apply to all block encryption schemes, but as the effort remains exponential in key-size the consequences aren't as severe as with factorisation-based public-key methods.
Keep in mind, however, that quantum computing is a relatively new discipline which up to now has mainly been carried out by physicist and not by crypto experts, so the actual potential for quantum crypto analysis cannot even be estimated right now.
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.
Despite popular beliefs, quantum computing won't solve all of our computing problems. As noted previously, quantum encryption is completely different from classical encryption techniques.
While quantum computers will be able to factor large primes very quickly, they still won't threaten modern encryption based on other techniques.
A good example of encryption that will never be compromised regardless of computing power is the one time pad. Using completely random noise (music CDs are a good source) makes it impossible for even the world's most powerful computer to crack because there is no mathematical way to decipher it. Random values can not be calculated. They can be guessed, but in the end you'd be left with numerous "guesses" that may or may not make sense.
One time pads, because they are completely random, have an infinite amount of possibilites. Modern crypto based on algorithms has a finite number of possibilities, which is a major weakness when talking about the possibilities of supercomputers, quantum computers and the like.
--the Fourth Amendment
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.
The obvious comparison is to the Sidney Harris cartoon showing a professor who has written on a blackboard: 1)[complicated equation] 2)"Then, A Miracle Happens", 3)[another complicated equation].
In view of the difficulties experienced to date in setting up quantum computers to solve trivially easy problems, has it been proven that the entire quantum computing process is in fact easier than classical computing?
/.
/. If the government wants us to respect the law, it should set a better example.
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)
Easy enough for a human to understand, but a pain the butt for computers - and with that kind of scheme, they'd be likely to get multiple "possible" unencrypted messages if their dictionary allowed this kind of stuff.
Of course, they can just read directly off my monitor as it is anyway. :^)
Who Wants To Date A Norwegian?
It is easy to demonstrate that the cardinality of the algebraic numbers is equivilant to that of the integers, so the cardinality of the transendental numbers is equivilant to that of the continuum. However, it is also not to hard to prove that the cardinality of all numbers describable in a finite language is equivilant to that of the integers. This includes not only every number that every human has thought of and every number that every computer has computed, but every number that any human or computer might ever consider. So for cryptographic purposes, the existance of a lot of transendental numbers is useless, beceause no human or computer will ever access them.
The fact that our theories about real number lead us to believe that numbers exist that we cannot access has troubled a lot of people. Weil rejected the class of number unaccessble to humans. Cantor thought that as he theorized about bigger and bigger infinite sets he was learning to understand God.
please correct me if I'm wrong but doesn't quantumencryption require both parties to have a quantum device - to be able to measure the polarisations of photons in either the X or the + scheme, thus making the code used as a one time pad?
How could
"Some will own a Quantum Computer and offer free (quantum) encryption" work. I.E. how would the user transmit data to the "free encription service" offered above... by conventional encription surely....
and this will not be safe.
AntiNeutrino
aron.fischer@gmx.net
I can't even remember what it was I came here to get away from - Bob Dylan
I think we have to be more worried about the advances in nanotechnology rather than quantum computing. Like others have said, quantum computing could kill cryptosystems based on products of large primes, but it seems it wouldn't neccessarily help on something like DES with a super wicked-huge keysize.
In Nanosystems, Drexler showed that it is possible to create a nanometer scale CPU that runs at 1 GHz, but fits into a 400 nm cube. According to my handy dandy TI pocket calculator, that means we could fit approximately 4.03225 * 10^13 of those little CPUs in a one inch square (which isn't exactly true, as you would have to connect them all, give them memory to use, etc., which I have not allowed for, but it gives you a very loose, ballpark figure), and that's only putting them one layer deep. Think about that. OVER FORTY TRILLION CPUs, all running at 1 GHz, all networked together, doing a distributed attack on a keyspace, and all of it fits in a square inch. With one of those suckers, you could crack any current encryption scheme using brute force, and it would most likely take less than a second (or at least, so I guess).
Granted, eventually the public would have such machines at their disposal (although we're talking a long way off here, as it would be quite a while before even a prototype could be built), but the NSA would always have the ability to build them much much much bigger (if they already have rooms full of Crays, imagine rooms full of these nanoprocessors!), and you know that they definitely would have them first, being that the kind of money it would take to design such a beast would be prohibitive for anyone else. By the time the design is done, surely we will have molecular manufacturing, and such a machine will cost nearly nothing to build, and the NSA could start churning them out by the thousands. Scary.
Mechanik
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
If anyone is interested I have been studying an underground operation called Grav-net that have been working on quantum computers and quantum encryption. They have some very startling news they have discovered in their experiments. Much of the technical information describes a blend of fractal theory, quantum mechanics, and neural networks. This is stuff that has been going on for quite some time. I'm not sure if the public is aware of it or not. E-mail me if yer interested. GRAPTOLITE@mindspring.com
Perhaps they will even become self-aware.
The real issue is whether this new life form, which will very quickly evolve far ahead of humans, will be recognized and respected as life.
A brute-force attack would be down to two steps, each of which would take a trivial amount of time: 1) generate all possible keys and 2) run the through your algorithm and see what comes out.
Nice guess, but no. With the keysizes people are using now there are more possible keys than there are atoms in the universe (dark matter excluded? i forget) Your planning on generating, storing then inputting all these keys at once?
good luck.
-lib
Create a QPU-card to put in an expansionport. ;)
Not only does it enable quantum operations, but it also sounds cool.
(At least, most hardware-companies seem to think Z X and Q are cool letters.)
Seriously though, that concept seem to work for Mac and Amiga.
They've both got PPC processor expansions though they originally used MC680x0.
Also, that should be the way to go, since most people will demand x86 compatability in the beginning to run their Wintel/Lintel platforms until Windows and Linux have been ported.
By the way: Shouldn't quantum processors be exceptionally fast?
Or is that only in certain computations?
Maybe quantum processing will be implemented as an extension of the FPU inside a normal CPU.
/.Mattsson - My native language is not English, so please don't whine over linguistic errors. (That's lame anyway...)
"The Feynman Processor", by Gerard Milburn and Paul Davis
:)
Perseus Books
ISBN: 0738201731
-johnny
My Opinion of QC is probably a bit off... It seems
to me that people tend to flock over the newest
toys, buzzwords, etc. QC is hyped and light years
away. (10 years ago, what kind of computer did you
have?? I though my sun3/50 kicked ass). I would
expect MPP FPGA machines to be abundant before
QC systems.
Who remembers the "3d optical storage cubes"
that IBM developed?
What happened to them? They were the next big thing. Oh well, the tide of popularty ebbs
and flows. Rest assured that if QC was actually
called "Shav Computing" or "Pigs Blood Congee
Computing" we would NOT be seeing this reaction.
Not to say that shav or pig's blood congee is bad
(*cough*)
John Wheeler, a wonderful man linked to QC through
Feynman, did a Miraculous thing when he named
'Gravitationally completely collapsed objects'
'black holes'. The name, he reminds us, is almost
as important to the eyes of the public as the thing named. We humans like buzzwords, and I am sure that the allure of "quantum computing" is at least partly due to the name. It is a difficult thing for your average joe (Or CPA who decided to become a "security expert" in the Big Five) to grasp. So it must be the name... Boy that book sure looks good in the shelf... not a spine creased in the whole wall... except for that MBA at home study guide...
Bitter? Nah
-johnny
All of this "should" have happened consequent to Hamilton's discovery of the symmetry between changes in the state of the observer and the observed in physical systems (all the other key insights were in place by that time thanks to guys like Gauss and Maupertuis). But then, humans are social animals and rarely find themselves capable of departing far from the prevailing modes of perception.
Seastead this.
And steganography isn't the same thing as "security through obscurity". Steganography is the art of hiding one message inside another; "security through obscurity" is doing stupid things like XORing stored passwords with the programmer's birthday and hoping nobody notices. :)
If you're interested in alternatives to crypto, you should also check out chaffing and winnowing -- it's a bit complex (and I don't claim to understand it completely) but basically it involves mixing real information with garbage in such a way that the receiving system will automatically be able to tell the difference but an eavesdropper won't. No keys required, ergo, no government-mandated "key recovery" schemes.
-- Some things are to be believed, though not susceptible to rational proof.
Hey uh somebody already mentioned some good resources in the previous posts, but could somebody direct me to some good newbie resources on Quantum Computing? It really sound like some keen gear.
Why?
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)
The two computers have to be directly linked by a fiber optic. The problem is that fiber has some length limit, so you need repeaters to regenerate the signal. And i think that screw the Quantum encryption. (Since the repeater 'observe' the data.)
What is a LONG way off? They said the same from y2k and see. And with the current speed IPv4 is doomed within 10 years. 10 years is not al long time for this stuff, specialy when you know it would be taken 40 or 50 years before we're capable for fusion. So the timing is great now IBM (for over a year now) has a starting working model of a quantum computer, and when you know how it works.
Oops, I meant quantum *computation* can be used to render the factorisation problem tractable.
Quantum computing offers an even more secure method of data transfer than we have right now.
You have it all wrong. Quantum computing does not allow you to 'try everytyhing at once' but rather to use the superposition principle indirectly to solve certain well defined problems. For example, we cannot just 'try all the factors' to factor a number, but must use Shor's algorithm which involves finding this period of a certain function and then using that indirectly to factor the number. Thus quantum computing applications will be very limited. It's not at all as easy as it looks. For more info check out OpenQubit
I thought I saw the answer a little bit back right here on slashdot. An algorithm was published (and proved to be optimal) for brute-force searches. It ended up having a complexity the square root of a conventional brute force search. Therefore, in order to make a conventional cipher secure against quantum search, simply double the number of bits in the key. (This assumes that "quantum math" does not reveal some new kind of analysis, which would at best attack *some* ciphers.) Do the math. If 128 bits is secure today, use 256 bits for tomorrow. 256 bits is already required for the NIST challenge, so there will be plenty of ciphers to choose from. Note that factoring is not of exponential complexity (only quadratic or so); taking the square root here gives you linear (or thereabouts) complexity. Figures.
Didn't have enough time to sift through all the posts to see if anyone has explained this, but some ppl have recently asked me about quantum devices and their susceptibility to eavesdropping. Eavesdropping is (dare I say it given our current knowledge of physics) *virtually* impossible to do on quantum channels of communication. Best way to explain the whys and hows would be to understand why its possible to eavesdrop on current day technology. Information today is transmitted in measurable physical properties of a signal. Classical physics allows eavesdropping to take place because the signal's properties can be measured by an external source without disturbing the system. This would not be entirely true according to Quantum Theory. Quantum theory applies to all physical objects regardless of size, however, funny things begin to happen when applied to small objects like subatomic particles. Quantum devices will use photons of light and abide by 'Heisenburg's Uncertainty Principle' whereby, an attempt to measure a quantum system will disturb it, resulting in incorrect or incomplete information about its original state. In other words, its original state cannot be accurately determined because the attacker would introduce errors in transmission which can be easily detected by the parties involved. So far, quantum key distribution systems that have been proposed rely upon the polarisation of photons. A sender will transmit a photon with a certain polarisation and the receiver will randomly choose a method of measurement (either rectilinear or diagonal) and make it public, but keep the result private. Any attempt to eavesdrop will change the polarisation of the particle making any measurments by the eavesdropper invalid. ---------------- Forgive me if this is all incorrect, I have yet to take a formal physics course.
I don't see where the idea that the foundation of public-key ciphers dies if quantum computers exist. From what I can see, quantum circuitry will yield really-really fast computers that can crack current ciphers very quickly. The idea that quantum computers can solve any problem in nil time really bothers me. Let's say a public-key cipher takes order n*x to encrypt and n^x to crack with the n being a number about the size of the key (sloppy, but fairly clear). You need to find a way to solve that cipher in faster time than n^x to have any hope of cracking it since whoever's making the cipher will always be ahead of the game. Even if a quantum computer can throw trillions of processors at a problem, the codemaker likely will have a computer powerful enough to confound the codebreaker. The confrontation would be similar to a PC doing 2048 bit RSA versus a bunch of Crays trying to crack it.
Isnt reality a quantum computer?
Could someone please use it to
decrypt my wife, I might understand
her then...
Sometime ysidro@usa.net
For a change.
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
It was demonstrated by Paul Cohen that the question
was independant of the normal axioms used for set theory (e.g. Zermelo-Frankel). There are some models of these axioms in which it is true, others in which it is false -- it depends on which model you use -- not the axioms.On BBC World last weekend there was a programme called the Time Lords (no not those from Doctor Who but Doctor Who made in to the show in a coffin however!), where they explained that if we get Quantum computing and stuff like quantum teleportation to work we would be able to send a message faster than the speed of light and it would be received before it was sent. Some points: wouldn't this be like the reverse tachyon beam in the last Star Trek TNG episode produced (All good things come to an end) - when they invented the technobabble called 'antitime'. Wouldn't this make a confusion in discussions where the replies precede the questions. Isn't it all just nonsense.
At http://www.msnbc.com/news/339196.asp MSNBC has something on quantum computing.
Rajiv Varma
If a quantum computer capable of handling a significant number of qubits practically is invented by a US (or by extension, anyone in G7) scientist, it is quite doubtful that we will ever hear about it at all. The NSA and other US Government intelligence agencies will either kill the inventor or recruit him (under threat of death) and classify the technology a million times higher than the hydrogen bomb or Stealth. And yes, it IS possible for a quantum computer to trouble non-factoring-based encryption schemes. There is Grover's algorithm, which is capable of unordered searches in O(sqrt(N)), which has proved useful in improved heuristics for the solution of NP-complete problems. It can't completely ward off NP-completeness, but it is enough to raise the infeasibility threshold somewhat. DES will definitely fall apart as the ~1e16 possible keys goes down to as little as a hundred million operations with Grover's algorithm. And who knows; someone may actually find a polynomial-time quantum algorithm for the satisfiability problem...
--
Qu'on me donne six lignes écrites de la main du plus honnête homme, j'y trouverai de quoi le faire pendre.