Slashdot is powered by your submissions, so send in your scoop

 


Forgot your password?
Close
typodupeerror
×
Encryption Security

The Possible Effects of Quantum Computing 153

Posted by Cliff from the what-would-happen? dept.
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?
This discussion has been archived. No new comments can be posted.

The Possible Effects of Quantum Computing More

The Possible Effects of Quantum Computing

Comments Filter:
  • 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.
  • My guess is that companies will pop up here and there. Some will own a Quantum Computer and offer free (quantum) encryption (in return for banner ads).

    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.

  • 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.
  • 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.
  • 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 [newscientist.co.uk] 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.
  • More specifically, you would know how much money you had, or what account it is in, but not both...

    :)

  • Ramblings on the Quantum ramifications (Score:3)

    by Brecker ( 66870 ) on Tuesday November 23, 1999 @05:15AM (#1510535)
    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.
  • 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.

  • Oh NO! (Score:1)

    by Anonymous Coward
    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 [slashdot.org] 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. "

  • Factorisation of Very Large values (Score:3)

    by DaveHowe ( 51510 ) on Tuesday November 23, 1999 @05:32AM (#1510541)
    Hmmm. I doubt we will see a major advance in quantum code-breaking in the next (say) twenty years.
    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.
    --

  • Quantum Computing permits acting upon every possible input to an algorithm simultaneously. It'll render all current crypto-systems obsolete

    Not as I understand the situation (which isn't perfect, I'll happily admit). By taking advantage of quantum mechanics, you can devise a system in which there is no theoretical way to eavesdrop on the communication succesfully (see the New Scientist article referenced elsewhere around here).

    But I may be wrong :-)

    Phil

  • What futures does Slashdot forcast when Quantum Computing becomes a reality?

    Ubiquitous spell checking... I hope.

  • The true effects of quantum computers (Score:5)

    by HyLander42 ( 67074 ) on Tuesday November 23, 1999 @05:36AM (#1510544)

    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! [cornell.edu]
  • 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.

  • Wrong. (Score:2)

    by Griim ( 8798 )
    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!"
  • A few thoughts:

    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

  • Exactly. As it is we have been able to lookup almost anything about anyone online for the past five years or so and more information is coming online all the time. Sure people pass privacy laws but as with all Internet laws they just don't work. I just assume everything I do is being videotaped and broadcast on the 11'o clock news and go on with my life. My best defense is that I'm just not that interesting to watch. Anyone who has been a system admin knows that after the first thrill of power it gets pretty old watching people. My basic question is the future of money and other forms of intellectual property in a future where encryption is at most a minor hassle. The opensource movement and nanotechnology are popping along here at the same time. Will be interesting to see capitalism stretched to the extreme and inversed. At the stock market level isn't this already prevalent? I mean if you think about it everyone's worth goes up the more people buy the stocks which is somewhat similar to how OSS works. If a lot of people suddenly pull everything they got out of the market then bang it all goes to hell. Sounds very close to a gift culture to me. It's just undercover.
  • In this case faster application of existing techniques is tantamount to it being a whole new field. The major limiting factor that makes any modern cryptosystem secure is time. Once we get beyond our current, Micky Mouse qubit limitations, adding one more bit will be trivial. While 41-bit crypto is currently exponentially more difficult to crack than 40-bit, for a QC it will not increase the difficulty at all. Adding bits to the key size, under QC, is analogous to adding another lock to your front door that uses the same combination. I.e., it takes a lot more effort for you to implement the new-lock (sawing, drilling, trips to the hardware store...) then it takes an intruder to enter that same comnination a second time.
    -"S"HM

  • Ironically, I was having this same conversation with Juris Hartmanis [nsf.gov] 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.
  • It is very possible that cryptography will move from the relatively finite world of integers and prime numbers to the much more infinite :) world of irrationals.

    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 . . .

  • Maybe we could use the computing power to remove spelling Nazis (and typo Nazis) from the world.

    That's a future I could be proud to live in.

  • LOL Well said. But then it'd take years and LOTS of ink to transcribe the byte-sequence of a JPEG file, and hours of wrist-wrenching typing to reconstruct the file on the receiving end! :-)

  • 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.
  • quantum physics are pretty out there, and the devices will be doubtless very hard to miniaturize.

    Nah, the core of a quantum crypto system is supercooled atoms arranged in a line, just a handful of microns.

    The real problem is that serious QC might be impossible. In theory, a QC can crack an X-bit key in seconds, you just need an equal number of Qubits (laser-excited atoms) in the line. In practice, building a large QC might be exponentially difficult -- if it gets twice as hard to keep things straight every time you add one Qubit, then QC will never be usable.

    governments that basically posess information omnipotence could drastically alter the balances of world power that we currently have.

    Depends. QC could do arbitrarily horrible things to any E-commerce that uses standard encryption. Which only means that if QC ever works, the banking industry will pay whatever it takes to get quantum encryption. But there are still plenty of valid ways to protect information. Aside from one time pads, groups could keep their important data on privately owned fibre. Can't crack what you can't access.

    For example, the US government already has information omnipotence relative to countries like Yugoslavia or Iraq. I'm confident that the NSA can crack any encryption scheme they use. Nevertheless, we still can't track down Iraqi anthrax, or blow up Milosevic in his sleep. All the computers under Fort Meade can't read a sheet of paper in a sealed envelope in an officer's pocket.

  • 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?

  • Re:Most probable answers (Score:2)

    by Anonymous Coward
    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...
  • You know it's ironic that the Supreme Court can manufacture a "right to privacy" from the Constitution (it must be in Article XIII, or perhaps Article XLII) to allow it to rule that abortion is legal, a connection that is tenuous at best and completely non sequitir in my opinion, yet the legislature and courts seem strangely silent when it comes to matters of actual privacy.

    Hello, U.S. government, which way is it?



  • 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 way a quantum computer works is: 1)You define a problem, 2)You configure a set of quantum-entangled qbits in such a way that their quantum state will collapse into the solution to that problem (rather than any of the other 2^n possible configurations of n collapsed qbits), 3)You observe the result of the collapsed-state qbits.

    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?
    /.

  • Doesn't Matter (Score:4)

    by devphil ( 51341 ) on Tuesday November 23, 1999 @06:54AM (#1510571) Homepage
    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
  • 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.
  • ...because no human is going to actually read every single unencryption attempt, the computer will most likely rely on a dictionary of some sort to determine if the key was right. S0 4ll y0 h4f t0 d0 1s t' r1t3 l1k 215h, & 23y w0nt h4x t. J05t = 5ur !tb c0ns15tn'.

    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. :^)

  • The interesting thing about transendental numbers is that there are a lot more of them than there are algebraic numbers. (For those unfamiliar with infinite cardinality, this is about as bizzare as it sounds. There are an infinite number of both transendental and algebraic numbers, the algebraic numbers are just more infinite.)

    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.

  • A few corrections are required here. Cuthalion says "factoring ... seems to be in a class of problems which we call NP". In fact, factoring *is* in NP. Contrary to popular belief, NP doesn't necessarily mean hard. All deterministic polynomial time algorithms (the kind you actually use) are in NP, by definition. NP just means that there are short, easy to verify proofs of the correct answer. For example, if you claim than x is a factor of y, I can simply divide x into y to verify that your claim is true. Some problems in NP *seem* to be hard. The hardest problems in NP are the NP-complete problems. No one has ever shown that factoring is NP-complete. It might be NP-intermediate (hard but not NP-complete). Also,no one has shown that quantum computers can solve NP-complete problems. Contrary to what appears to be a popular belief among slashdot readers, quantum computers can not do arbitrary exponential parallelism. (If they could, they could easily solve NP-complete problems just by trying all solutions at once.) Indeed, Shor's algorithm would be trivial (and not have the justified fame that it has) if it was simply a matter of trying all possible factors at once. Quantum computations have to be describable by a Hermitian operator, at it is non-obvious just what you can do with such operators.
  • 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
  • Not to mention the difficulting in finding some ICR (Invisible Character Recognition) software.
  • The richest ressource on quantum computing is the LANL e-print archive on quantum physics [lanl.gov]. A more structued site dedicated only to QC is the Oxford Centre for Quantum Computation [qubit.org]. My own stuff can be found here [tuwien.ac.at].

  • Multiplication is O(N^2), O(N^lg(3)) (and
    ranges inbetween) and O(n log n) using
    the fast fourier transform technique.

    There is no multiplication algorithm that is O(N)
    for the general case.

  • As far as QC applies to cryptography, the big gain is not in database searches, but in factoring algorithms. Peter Shorr (of IBM I believe) developed a factoring algorithm for QC's several years ago. Factoring on a current computer is an exponential time process. The time to factor scales exponentially with the size of the key. On a QC using Shorr's algorithm the time is polynomial. So for a small key there is probably going to be little difference. But, as key sizes increase, the QC speed advantage becomes more and more apparent. With Shorr's algorithm, the extracting of data at the end is done by looking at the total configuration space of the setup. The factors appear as much more probable configurations. I can't remember the exact details, but I have notes somewhere around here from a talk on QC given by some of IBM's researchers a few years back.
  • "SPOOOOON!" -the tick.
    "there is no spoon" -Neo
    "there simultaneously IS and IS NOT a spoon." -Schoedinger.

    I wish I had a nickel for every time someone said "Information wants to be free".
  • 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
  • A couple comments:

    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 [lanl.gov] 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

  • Ummmm.... NO. No matter how fast a CPU or how many of them you get, factorization/discrete log is still exponential. So you can factor a trillion times as fast -- just increase the keyspace by log(40trillion) or about 40 bits. Voila. Your encryption is now that much stronger. Of course it'll take longer to encrypt, but given your 40trillion CPUs this shouldn't take very long at all. :) The key point of quantum computers is that they change the time complexity of the problem, not just provide a faster CPU. :)

    Ali Soleimani

  • This is an extremely naive position. A computer could easily detect your above text as being the clear text (or one of a small number of potential clear texts) simply by virtue of all the characters being 7-bit ASCII (i.e. highest-order bit is always zero). For a message of n bytes, there is only a 1 in 2^n chance that a given key will result in a legal 7-bit ascii message. Your string was 84 characters long, so if you were using a 128 bit key, you could expect about 2^44 potential plaintexts, which would be much simpler to brute force. And this is using a very naive plaintext recognition method- a more sophisticated method would also, say, put more weight on the occurrence of whitespace, and require a certain minimum number of whitespace characters to qualify.

    A better method might be to compress the text first, but then you are vulnerable to attacks on the formatting used by the compression method (looking at the headers, symbol tables, etc).
  • I just don't get how it could render one-time pads obsolete.
    It doesn't. OTPs remain secure, and "quantum cryptography" provides a secure means for Alice and Bob to agree on a pad.
  • I think you misunderstood a bit. What I meant was that given that quantum computing can render any cryptosystem based on factorization obsolete, but that it doesn't really help on any other cryptosystems, we should really worry more about things that can affect those other cryptosystems instead.

    The nanoscale processors to which I am referring are not QCs at all... just simple RISC machines. Their power lies in sheer numbers... if you have a roomful of those little suckers (read: more processors than you can possibly imagine), you can crack pretty much anything you want. Granted, if the public has such powerful machines too they can use more and more complex encryption algorithms (read: larger keysizes), but the NSA will always have the money and resources to build something bigger that can crack that too. If they do things really cleverly, the nanoscale manufacturing robots would just keep building and building and building, adding more and more processors to the network 24 hours a day, with only a miniscule cost in raw materials required. That's the power of molecular manufacturing; once you set things in motion, the systems build themselves, and practically for free.

    The public can only play leapfrog with the NSA to a certain point... a nanometer scale CPU is basically as small as you can get, and the only way to make a more powerful machine is to network more processors together. It's not very feasible for Joe Public to have a computer the size of a gymnasium that could run an encryption algorithm that the NSA couldn't crack without a computer the size of a city, as Joe Public simply doesn't have the space and other resources required (especially money). If you start building a computer that big in your backyard (assuming you have one... many urbanites don't), Someone In Power is going to notice, and probably is going to come and ask you why the heck you think you need a computer that big. I wouldn't be surprised at that point if supercomputers were to become classed as munitions, like strong crypto is now.

    Mechanik
  • As others pointed out: QC will not kill off symmetric cryptography. It will also not kill off public key cryptography that is not based on number-theoretic assumptions. A good example is Lamport's one-time signature scheme, which combined with Merkle's authentication trees can yield workable digital signature schemes. The signatures tend to be a bit big (in the order of a few Kbytes for practical parameters, no big deal in this day and age). The public keys are small, one hash value, and validation is fast.

    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.

  • Quantum encryption is based on the fact that quantum states cannot be measured without altering.

    I would like for someone to explain to me what is stopping a potential eavesdropper from listening in to the communication while stopping its continuation, then re-transmitting. Sure, since he measured the signal he distorted it. So what? If he "removes" the signal (think brick wall), and re-transmits the observed data, he would be 100% invisible. Wouldn't he?

  • 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
  • One thing to remember is that one-time pads are still secure, no matter how fast the cracking machine is. But then you still have to have a secure means of transmitting one-time pads.

    Nothing preventing you from making a bunch of CD's with one-time pads on them and giving them out to your co-conspirators. Of course, now you're vulnerable to real-world cracking (by compromising one of the CD's or perhaps one of your fellow conspirators), but at least your on-line communications will be safe.
    --
  • 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.
  • Whew! That's all right then. Thank goodness our wonderful leaders would never infringe anything we consider as our rights, even when they have the ability.
  • 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....
  • 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.

  • I've read through the article, (VERY interesting. I'm always amazed at what we think of next) but I think I see a flaw in the entire quantum encryption scheme. According to the article, there are two things preventing someone from intercepting the key: 1) photons change their polarization as they travel. 2) Eve cannot know which filter Bob is going to use to check the photon.

    The answer to 2 is easy. If Eve captures a photon, all she has to do is somehow copy the photon (assuming this is possible, of which I'm not sure) and send it a few times to a 0 and a 45 degree filter of her own. The photons will not pass at all through one and randomly trickle through the other one. Thus Eve knows what Bob will know for every single photon. When Bob tells Alice which photons he got, Eve will be listening and therefore has the key.

    This leads to number 1 though, in which Eve cannot be certain that she is correctly retransmitting the photon at the correct polarization. To which I answer with this, how much do we really know about Quantum Physics? If I understand correctly, it is a very dynamic field, full of changes. The article itself says "...because of the strange way that quantum particles work". I'm not sure if the scientists even know what is causing this shift in polarization (I'll admit I'm fairly ignorant on Quantum Physics, I'm just going on what I'm reading here.) What's to say that someone in the near future will not discover exactly how these polarities are shifting? If this happens, they will be able to faithfully retransmit the intercepted photons with Bob being none the wiser.

    My point is this encryption is relying on unproven science. Since when has that stopped us though? Humans have been doing this for years. Back in ancient Rome, people drank from lead-line cups. Supposedly lead was good somehow for the cups, but they didn't know that lead killed people. A recent example is cell phones. Cell phones seem like a good technology, but recent research suggests that they are a cause of brain cancer and short-term memory loss.

    I'll admit this argument is not based in today's science, but in the future possibility of something being discovered. The technology seems solid today though, if it will work exactly as described.
  • I think what'll happen is that someone will offer a Free Quantum Computer, and all you have to do is sign up for 3 years of quantum-ISP service (offering 56k connections that you always connect at 38.6k to), or maybe there'll be a 2" border around your screen that displays quantum ads.

    Or something. quantum quantum quantum (trying to increase the quantum content of this post.)

    Hey, who hasn't slept in days? It's me! ;)

  • Cantor thought that as he theorized about bigger and bigger infinite sets he was learning to understand God.

    Yeah, but Cantor was a nut case, and everybody knows it. Don't get me wrong, set theory is my favorite branch of mathematics, so I am fascinated by Cantor, but he had mental problems his whole life. Maybe only a crazy man could come up with stuff like that.

  • Today's ECommerce relies heavily on encryption of some sort. Since Quantum computing will be handling the flow of money (banks) in the "near" future and then, presumedly, the internet, I'd say this makes quantum encryption very relevant in the field of quantum computing.
  • Some will own a Quantum Computer and offer free (quantum) encryption (in return for banner ads).

    I don't think so. As far as I understand it, quantum encryption is not simply a new layer of information that can be transmitted over standard channels. It involves the quantum state of the medium of information transfer, which can't be examined without modifying it (thus allowing one to be sure the information either has or hasn't been evesdropped on). Since existing modems, network cables, and so on don't preserve quantum state, quantum encryption can't work over them. You need something like fiber optics, where you can test the quantum state of the light as well as draw the encoded information out of it.

    Brad
  • >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...
  • Im not an expert at all, but ill relay what i know, or think that i know. The idea behind quantum encryption, which i think that is what you are talking about, is that the key is sent bit by bit, and you can not see what that bit is unless you disturb it. So, if Bob and Joe were to need to exchange data, Bob, the sender, would randomly creat a key. he would then, while randomly switching between the different polarizing filters, pass the, in this case a photon, but i think it can be almost any particle, through the polarizing filter. If some thing passes though the filter, then Bob "writes down" what filter he was using, and thus knows what that the spin on the photon was. As the single photon passes down the fiber to Joe, if some one were to try and eavesdrop on the transmission, say Mike, he would have to put a filter in the path of the photon. The filter would no have to be random, but using the same filter would only test for the same spin on the photon. Im not sure how many different spins a photon can have, i remember reading it has 2. If by chance Mike, the eavesdropper, uses the right filter he can "write down" what the spin of that photon was. By using thw right filter, neither Bob nore Joe would know that some one is listening. The photon then keeps going untill Joe gets it, and then he puts a filter in front of the photon, if it passes through he writes down the filter being used and he knows what the spin is. If the photon is blocked by Bob, then he just sends another, and uses a different filter. If Mike blocks it, then Bob and Joe will know that there is some one listening in. If the photon gets to Joe, he uses a filter, if it is blocked, he tells Bob to resend the photon. There is no way to intercept the transmission of the key being used to encrypt the message, and then resend it without anyone knowing that the photon has been changed. Using this method, it would be safe to exchange the key, because any interception would alter it. The message, encrypted with, im guessing, any encryption algorithm, could be sent non-quantomly, ie. on paper of in an email. The second way to send the message would be to encrypt it, as stated, and then send the encrypted message as the kay was, with the same use of filters....But this is where i get confused, if all I have stated is true, why cant Mike, just sit using his filter, and get they key used? If Mike spends long enough he will, by probability get the correct filter for each photon(way #1 would be him sitting there as each blocked one is resent, or #2 by pure luck he uses the cortrect filter, and he never blocks a photon, which is very unlikely, but possible). If i understand this crrectly, then the photon has 2 spins, and thus Mike would have a 1 in 4 chance of using the right filter, if he selects filters randomly. I think i read about this in Scientific American, in the past 3-4months i think, but im not sure. Im not not an expert on this at all, so if any one knows if i am correct please tell me.

  • First: what this means with respect to quantum encryption is that if someone's eavesdropping, you'll know they're eavesdropping because the error rates of your communication with the other person will skyrocket, and you'll know something's up.

    Second, what you've described is the man-in-the-middle approach to defeating encryption. Charles Bennett, the researcher who proposed the current quantum encryption algorithm, states that you have to have two communication lines: one that is quantum, and one that is public, and you cannot have a man-in-the-middle on the public line. Why would this change anything? Well, you use the public line to exchange information in the data initiation sequence. You say "I sent this data and it was like this", and the other person notes it and corrects their data translation, and vice versa. Then, if someone intercepts it from then on, error rates go up. Otherwise, the person will have been there BEFORE they initiated contact. This means all the data they get will make NO SENSE WHATSOEVER, and they'll abandon the data line before they use it. But Bennett knew a man-in-the-middle in the public channel would screw this up, that's why he said avoid it. If that didn't clear anything up, lemme know.
  • 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
  • Even the most educated minds of technological civilization have yet to penetrate the essential weirdness of the universe, recognized by folk lore throughout mankind's existence. What quantum computing will do, by bringing quantum weirdness into the realm of technology, is infuse technologists with a change in the perception of time and causality similar to the change in the perception of 'up' and 'down' that occurs when one "ascends" to orbit. Time will still exist, of course, but it will be perceived as relative to information structures that underly natural phenomena, just as 'up' and 'down' are now perceived relative to structures of mass.

    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.

  • Given the immense computational power quantum computers will possess, it is only a matter of time before algorithm and systems breakthroughs allow them to far surpass human analytical faculties. Perhaps they will even become self-aware.

    Only a matter of time. And it may not even require quantum computation, though QC would probably help. Do our brains depend on quantum computation? I doubt it.

    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.

    Um, if it "evolves far ahead of humans", the real issue is, will it recognize and respect us as life.

  • If you read the /. interview with Bruce Schneier [slashdot.org] a few weeks ago you'll see that he points out that quantum computing isn't a magic skeleton key; it reduces the complexity of calculation but doesn't eliminate it. Mathematically, it effectively halves your key length. So a 2048-bit PGP key (or 256-bit RSA key) is still secure even against quantum computers.

    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 [mit.edu] -- 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.

  • 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.
  • "Quantum encryption is based on the properties of photons and really has very little computing going on for it." I'm not sure this is a correct thing to say. Quantum encryption is a special case of quantum computing. You can write quantum encryption protocols and algorithms as quantum computer programs. Just like quantum computing you represent binary messages as spin states of electrons, photons or whatever other particle you have to hand and you perform unitary operations on them. These unitary operations are the same building blocks that quantum computers are built from.
  • 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.
  • Thats anoying, I must have hit post anonymously or something. That was actualy posted by me, not an Anonymous Coward.
  • Actualy there are O(N) multiplication algorithms. Take a look in Knuth Vol. 2 (Seminumeric Algorithms). Section 4.3.3 has an algorithm that does it in exactly N steps (not O(N)). It's really cool, its called a bit-serial-multiply and each bit only has to talk to its two neighbors at each step. It also starts clocking out an answer one clock cycle after you start clocking in the operands.
  • I believe Mr. Schneier was referring to symmetric cyphers, for which currently there are only improvements of O(sqrt(n)) from O(n). Public-key systems have been broken in polynomial time.
  • You are absolutely correct.
    Quantum computers will never replace the digital machines that we have now. You really can't run "software" on a quantum computer, just basically NP type stuff and the like.
    However, to switch gears slightly, probably one thing that is up and coming is molecular computing.
    This has the potential to possibly replace the digital computer because it still involves the same logic gates, but they are so much faster.
    But alas I think it is still 5-10 years away, so I guess we will just have to live with our gigahertz machines for now...
  • The funny thing is we are hitting a goofy barrier like that again. The US gov't calls any computer that can do a gigaflop a "supercomputer;" Apple's G4 and Sony's Playstation2 can do just that. Of course, the classification was made a good 10 years or so ago. It basically adds up to silly marketing for Apple. On the subject of nanocomputers, I would have to agree that they are a bit scarier than quantum computers. A quantum computer could tell that 2+2 *probably* equals 4, but given the Heisenburg Uncertainty Principle, it's hard to say. And solve problems that conventional computers can't. A nanocomputer would tackle conventional tasks, and do them really really fast. How similar to today's computers would a nanocomputer be in basic architecture? I have read a lot of people saying that sooner or later, the microprocessor will not be able to continue on it's current path, i.e. getting faster while getting smaller and cheaper. I think the reason given was that the transistors wouldn't be able to get any smaller. Does this factor into nanocomputers at all? Or are they built differently enough so that it doesn't matter?
  • except that if "pretty much all the evidence linked to a crime could end up being encrypted", they don't know if I'm "doing anything wrong" unless they ALREADY HAVE broken my encryption.

    pretty far from there not being any reason for them to want to see what I've been reading or writing.

    not that that makes it ok. if they can do their best to access my _PRIVATE_ data, I can do my best to keep that data private. as a programmer (and someone who knows where GPG is), I expect to win.
  • Wow. Cool. I was serious, too... :-)

    I forgot to give attribution to the Sysadmin Rant ("...the way of things.") part at the end of my post, though (Steve Conley).

    I /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.

  • 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.)
  • 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.

    As far as I can see quantum computers are not a huge threat to symmetric ciphers, which can only be attacked statistically, not by solving a set mathematical problem. The defining feature of public key cyphers is what makes them vulnerable - since everyone knows the public key, the attacker (Eve) has enough information for a break without any intercepts of cipertext. Once she knows the public key, in principle she can determine the secret key with pencil and paper. Quantum computers just make it practical.

    This is not the case for symmetric cyphers - Eve knows nothing until she has some ciphertext, and with most cyphers that plaintext could in theory have been encrypted with any key. The only reason symmetric ciphers can be broken at all is that Eve can guess characteristics of the plaintext, and might discover some way these are reflected in characteristics of the ciphertext. If she doesn't have enough plaintext, or it doesn't have enough structure, then even in principle there is no way for her to break the cipher, since the ciphertext she has could be the result of encrypting many different messages with different keys. Symmetric cypher designers have a large space to explore to find ciphers where the cyphertext does not reveal characteristics of the plaintext, and say with DES it took decades before any attacks better than brute force were revealed in public. For short enough messages, even a substitution cypher is secure.

    It is hard to see how a quantum computer would significantly speed up the statistical calculations used to break symmetric cyphers. Grover's search algorithm could speed up brute force searches, but only by a square root, doubling the key length would make the cypher as secure as it would be otherwise. With the attack on RSA, doubling the key length would only increase the difficulty of attack by a constant factor, which doesn't do you much good.

  • Bruce Schneier was talking about symmetric key cryptography. Quantum cryptography can be used to render the factorisation problem tractable, and so break RSA encryption. It may not do this for other proposed assymmetric schemes, such as those based upon elliptic curves. (BTW a PGP key is an RSA key).


    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 (Score:2)

    by Chalst ( 57653 )
    Oops, I meant quantum *computation* can be used to render the factorisation problem tractable.
  • It is as yet unknown whether or not digital computers can solve NP hard problems...
  • Once we get beyond our current, Micky Mouse qubit limitations, adding one more bit will be trivial.
    I must admit to having trouble discovering where this massive breakthrough will come from - you are claiming that you can increase the number of parallel universe "ops" practically without limit and at very low cost, which even to my limited understanding seems unlikely.
    --
  • 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

    I dunno, but I have a hard time visualizing this. There are about 10^80 protons in the visual part of the universe. 10^80 is less than 2^300. I would like to know how you would generate all possible keys of a 300 bit keylength in trivial amount of time.

    -- Abigail

  • Whilst I accept that English is not everyone's first language, that people type quickly/in a rush, etc.,etc., and therefore accept that user comments might not always be 100% gramatically correct and might 'feature' a few spelling anomalies, I don't think that it's much to ask for the _actual stories_ to be given the once over with a spell checker, or at least proof read!

    j.
  • If Mike spends long enough he will, by probability get the correct filter for each photon(way #1 would be him sitting there as each blocked one is resent, or #2 by pure luck he uses the cortrect filter, and he never blocks a photon, which is very unlikely, but possible).

    If Mike blocks a proton, Joe isn't getting it. He tells Bob, so Joe and Bob will know the line is being eaves dropped on. Only if Joe and Bob are stupid, they will continue using the line.

    -- Abigail

  • The nanocomputers Drexler talks about in Nanosystems aren't electronic at all, but mechanical. Instead of transistors and such, you have logic rods instead. All logic in the computer is represented by the displacement of these rods... a small displacement might be a zero, while a large displacement would be a 1.

    In terms of architecture, they are just like any other RISC machine... the only difference is that the logic of the components is mechanical rather than electronic. You still have gates, you still have a bus, you still have registers, only all of these things are built mechanically rather than electronically.

    Sorry if this is a brief reply, but Drexler wrote an entire book on this sort of thing, and it's really way too much info to condense into a post.

    Mechanik
  • http://www.newscientist.com/ns/19991002/quantumcon .html

    has a nice explanation of quantum "crypto". I prefer one-time-pads distributed through q. entanglement, if that is feasible...

    well... off to the supermarket and movies... life of the slacker high school senior...

    oh. if q. computers can decrypt stuff like:

    Fennsense, fnnsonse, aworn! Tuck upp those wide shorts. The pink of the busket for sheer give. Peeps. Stand up to hard ware and step into style. If you soil may, puett, guett me prives...

    i offer my soul and any others that i can get my claws on
  • I bet you could run a bitchin Beowu -- *WHAMWHAMWHAMWHAMWHAM*

    Damn, they just keep popping up. 'scuse me, gotta clean my bat.
  • 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.
  • That was the passing argument -- there are transendental numbers that we will never see. We can approximate many with algebraics, and we can take transendentals and perform algebraic operations on them.

    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.

Slashdot Top Deals

Those who can, do; those who can't, write. Those who can't write work for the Bell Labs Record.

Close