Forgot your password?
typodupeerror
Security Technology

Scientific American on Quantum Encryption 374

Posted by samzenpus
from the just-try-and-break-it dept.
prostoalex writes "Scientific American claims that advances in commercially available quantum encryption might obsolete the existing factorization-based solutions: "The National Security Agency or one of the Federal Reserve banks can now buy a quantum-cryptographic system from two small companies - and more products are on the way. This new method of encryption represents the first major commercial implementation for what has become known as quantum information science, which blends quantum mechanics and information theory. The ultimate technology to emerge from the field may be a quantum computer so powerful that the only way to protect against its prodigious code-breaking capability may be to deploy quantum-cryptographic techniques.""
This discussion has been archived. No new comments can be posted.

Scientific American on Quantum Encryption

Comments Filter:
  • by Jace of Fuse! (72042) on Thursday January 20, 2005 @02:37AM (#11417111) Homepage
    Someone needs to write a Encryption routine that uses the source text as the key. THAT will really show 'em!
  • by Engineer Andy (761400) on Thursday January 20, 2005 @02:38AM (#11417114) Journal
    As far as I can tell, no cats were harmed in the making of these quantum cryptographic devices, although if you look inside the box, the act of looking at the cat inside may (or may not) kill it
  • by Ziviyr (95582)
    Why does quantum computing threaten present encryption?
    • Re:Uhh... (Score:5, Informative)

      by k98sven (324383) on Thursday January 20, 2005 @02:41AM (#11417130) Journal
      Because you could implement Shor's factorization algorithm [senko-corp.co.jp].
      • So.. I really don't understand quantum computing. Why doesn't someone build a emulator that would allow a large grid of existing computers to run a "quantum computer"? Wouldn't it be just as easyto delegate a processor to six or seven bits at a time?

        *puzzled*.
        • Re:Uhh... (Score:5, Informative)

          by Anonymous Coward on Thursday January 20, 2005 @04:55AM (#11417595)
          The point with a quantum computer is as follows. Overly simplified.

          If you have a quantum byte, i.e. 8 quantum bits, you can load it with 256 different integers simultaneously. You can do a single computation on the byte, and this computation is done simultaneously on all the 256 integers. This can easily be emulated, with 256 computers, as you suggest.

          But, if you have a quantum computer with 256 quantum bits, you can do computations simultaneously on 2**256 integers. That's not easy to emulate with classical computers because we don't have enough of them.

          The main problem with constructing algorithms for quantum computers is to read the result. When you read the 256-bits you only get a single number among the 2**256 which are stored there. Each of 2**256 integers has a probability associated with it, what you read is governed by this probability. Once you read, the state of the computer collapses to what you read, all the other information is lost.

          Shor's algorithm solves this by ensuring that the result is periodic, the period being the solution to the problem. It then performs a Fourier transform on the state. Then reads it and gets the period with high probability.

        • Re:Uhh... (Score:3, Insightful)

          by HuguesT (84078)
          Because it is extremely inefficient to simulate the quantum world, as everything happens in parallel.

          In effect you go back to square one. To simulate N qbits roughly your quantum computer simulator must have the capacity to completely explore 2^N states. It quickly becomes unmanageable, and you revert to the original problem.

          Equivalently you can say that if you have the traditional computing power to solve the problems that a given quantum computer would be able to solve easily, then you approximately hav
        • Re:Uhh... (Score:3, Informative)

          by maxwell demon (590494)
          An n qubit computer is a general 2^n state quantum system. Now emulating an N state quantum system means manipulating vectors of N complex numbers.

          Let's try an example: Let's assume that we need only as much precision that we can use a fixed point numer format with a size of one byte. Then a complex number will need 2 bytes, and the vector to just store the quantum state of an n-bit quantum computer will therefore need 2^(n+1) bytes.

          According to Wikipedia, there are 6*10^79 atoms in the universe (taking t
    • Re:Uhh... (Score:4, Funny)

      by monkease (726622) on Thursday January 20, 2005 @02:44AM (#11417140) Homepage
      Quantum computing doesn't make threats.

      It makes promises.

      I'm not just gunna break yo' face, i'm going to quantum break yo' face, foo'!
    • Re:Uhh... (Score:5, Informative)

      by Dr. Weird (566938) on Thursday January 20, 2005 @02:45AM (#11417152)
      Encryption, as it stands now (the classical kind), relies on an asymmetric computational task. For example, it is much easier to check that the a list of numbers are the factors of another number than it is to factorize the number. In fact, the latter is, to the best of current computer science knowledge, exponentially slower than the first.

      Quantum computing provides an algorithm (Shor's), utilizing quantum mechanical manipulations, which factors numbers exponentially faster. Thus, factoring and checking factors takes the same amount of time.

      This leads to the undesirable conclusion that encryption and decryption (by an intercepting 3rd party) of a signal take the same amount of time (up to a polynomial equivalence). In other words, the encryption is breakable, since the interceptor need only invest roughly the same amount of computational effort as the sender in order to crack the message.

      That is why the creation of a quantum computer would "obsolete" present encryption. The point of quantum encryption is that it is not vulnerable to such attacks.

      • Re:Uhh... (Score:3, Informative)

        by Anonymous Coward
        But, as usual, the media hypes this too much. Presently only two useful algorithms for quantum computers are known. A search in an unordered set, which runs as sqrt(N) (as compared to N for traditional computers), and Shor's algorithm for factoring numbers. The most widely used public key cryptography (RSA) is based on the difficulty of factoring numbers, but it would not be technically difficult to replace it with another asymmetric scheme, e.g. based on elliptic functions. No quantum algorithms are kno
      • 1. Not all current public/private key schemes rely on factorization. RSA does though, as does DSA I think. But not ECC at least, I don't know so many other.

        2. To implement Shor's algorithm, quantum computers have to scale. I don't know how it works but it couldn't possibly check more than 2^n keys at once, where n is the number of qubits.

        Naturally if n is large, any key can be cracked. But I doubt that quantum effects scale well. So far it's been about a dozen qubits, and well... 2^12 at once is impressiv
    • Re:Uhh... (Score:3, Informative)

      by Omniscientist (806841) *
      Well with current encryption methods you usually have a public key and a secure key. Let's say I give everyone here my public key. Well then everyone can encrypt me messages, but only I can decode it with my secure key. However within that public keys lies the secrets of the secure key, but it would take an extremely long time to break the public key cipher. With quantum computing, which can perform really hard factorizations quickly, it would make the whole many current cryptographic schemes obsolete, beca
    • Re:Uhh... (Score:2, Funny)

      by vagabond_gr (762469)
      VERY rough explanation.

      Encryption algorithms rely on the fact that some problems need an exponential number of 'calculations' to be solved. If b is the number of bits in a key, breaking the encryption needs 2^b steps.

      On the other hand in traditional computers, if you have p processors and each can perform n calculations per time unit, then you can perform p.n calculation in total. Increasing p or n gives only a *linear* improvement in performance. This is not enough to match 2^b if b is big enough.

      On the
  • by chadw17 (308037) on Thursday January 20, 2005 @02:40AM (#11417127)
    The printer-friendly version puts it all on one nice and image free page.
    Article here [sciam.com]
  • Bah... (Score:2, Funny)

    by JohnPerkins (243021)
    tshtuatpptenaynrirragagcuoyomq
  • by g0dsp33d (849253)
    so long bits, hello tits.

    Trinary digITs here we come!
  • Good for telco's? (Score:2, Interesting)

    by afidel (530433)
    Will the need for an unbroken end-to-end light pipe finally lead to enough demand to light up some of that dark fibre that is sitting on the telco's books?
  • Baloney. (Score:5, Interesting)

    by Pendersempai (625351) on Thursday January 20, 2005 @02:49AM (#11417177)
    Quantum cryptography is a solution in search of a problem. It cannot implement public key/private key cryptography, and it can transmit only through a single uninterrupted fiber-optic cable, not over the internet at large. Given those limitations (which I don't think can be surmounted), one might as well use tremendous, digital one-time pads. Transmission of the pads to the relevant parties should be strictly easier than the quantum cryptographic solution: if nothing else, generate terabytes of noise, store it on a RAID, and put it in a car with ten intensely loyal guys. After you've done that, you can send up to that amount of data securely over the internet at large, and no amount of quantum hocus-pocus will be able to decode it.
    • Transmission of the pads to the relevant parties should be strictly easier than the quantum cryptographic solution: if nothing else, generate terabytes of noise, store it on a RAID, and put it in a car with ten intensely loyal guys.

      I like this proposal. Companies who can't find ten intensely loyal employees probably don't deserve to have secrets. ;-)
    • Re:Baloney. (Score:5, Insightful)

      by OzRoy (602691) on Thursday January 20, 2005 @04:12AM (#11417441)
      I quote the apropriate part from the article for the lazy parent who has not RTFA.

      Ultimately cryptographers want some form of quantum repeater--in essence, an elementary form of quantum computer that would overcome distance limitations. A repeater would work through what Albert Einstein famously called "spukhafte Fernwirkungen," spooky action at a distance. Anton Zeilinger and his colleagues at the Institute of Experimental Physics in Vienna, Austria, took an early step toward a repeater when they reported in the August 19, 2004, issue of Nature that their group had strung an optical-fiber cable in a sewer tunnel under the Danube River and stationed an "entangled" photon at each end. The measurement of the state of polarization in one photon (horizontal, vertical, and so on) establishes immediately an identical polarization that can be measured in the other.

      And it continues on this page http://www.sciam.com/article.cfm?chanID=sa006&arti cleID=000479CD-F58C-11BE-AD0683414B7F0000&pageNumb er=3&catID=2

      • Why do you assume the GP post is lazy. Perhaps they agree with Albert, I know I do. Mathematics can model reality extremely well. I think it breaks down when our Gravity Model says there can be an infinitely large mass in an infinitely small space. I also think QM breaks down with "spooky action".

        Because I think that, I also think research (particularly emprical reseach) into black holes and entanglement is a "good thing" regardless of it's potential value. Albert (who like slashdotters could not underst
        • I don't really understand your post. Albert Einstein made the "Spooky Action" thought experiment to show how ludicrous the Heisenberg Uncertainty principle is. He didn't believe it.

          However, the experiment has since been done, and the uncertainty principle still holds. The "Spooky Action" is an observable event.

          Now I don't understand exactly how, but they said that they can use this to create quantum relays in the transmission of the message.

    • > It cannot implement public key/private key cryptography

      In terms of cryptography only, quantum is next-gen. It obsoletes assymetric key crypto.

      > one might as well use tremendous, digital one-time pads.

      Except that OTPs are insecure without a quantum key exchange.

      > generate terabytes of noise, store it on a RAID

      Storing the key to a one-time pad would just be stupid.

      > no amount of quantum hocus-pocus will be able to decode it.

      An attacker won't need quantum hocus-pocus if you generate the ke
    • Given those limitations (which I don't think can be surmounted)

      Think outside of the box. Bounce the laser light off of a satellite. Directly communicate with planets and spaceships. That's where most of the communication will be occurring within 100 years.

    • Re:Baloney. (Score:2, Informative)

      by imagin8or (676287)
      In the world of cryptography, there is no greater problem than key distribution. If I have a bank, and I want a secure connection to the head office, I need a big enough one-time pad to cover all the transactions for, say, a month. This is nigh-on impossible, as the amount of data is too huge. It also creates a huge weak point in the whole operation in allowing someone to infiltrate the courier, block deliveries, copy the data, etc. Public key cryptography (mainly via RSA) was the answer to that problem. A
      • Re:Baloney. (Score:3, Interesting)

        by Twylite (234238)

        Hmm, I don't know who you work for, but I suggest hiring someone with a Clue.

        Banks, by and large, do not use asymmetric cryptography like RSA to secure their transactions. The standard for retail and wholesale banking environments is Triple DES, and it's not likely to change for some time, since they've only just finished moving there.

        Keys are distributed by loading them into secure, tamper-responsive devices in a trusted environment where no sniffing can occur; then the devices are sent to where they

    • We've got working photon transmission through 2km of air. I think that's only going to increase. Besides, there are plenty of people for whom a single absolutely secure fiber-optic cable is worthwhile. Banks, for example, could probably use a guaranteed secure link to their national headquaters.
  • "Jon, we have a situation. We need your to do your stuff."
  • Eventhough it looks as if it has been written for a layman , the article is quite cryptic (and IMHO nothing new).

    If someone tries to intercept this stream of photons--call her Eve--she cannot measure both modes, thanks to Heisenberg. If she makes the measurements in the wrong mode, even if she resends the bits to Bob in the same way she measured them, she will inevitably introduce errors. Alice and Bob can detect the presence of the eavesdropper by comparing selected bits and checking for errors.

    Ok, if yo

    • by Anonymous Coward on Thursday January 20, 2005 @03:20AM (#11417276)
      But in the current networks it'll only go around a couple of meteres at Max and you can't use an amplifier/repeater with this. So really, how are we going to use this in real life ?

      Who said using it on current networks? In real life, custom networks are used, of course.

      Sending information faster than light is likely not possible. The FAQ you linked to says that too. Currently, theory says no, and experiment can't tell. Some have chosen to interpret their experiments as supporting FTL transmission of information. But the majority do not agree with that interpretation.

      Using photons in computers in any form is so far off that suggesting it as a solution to current day problems like die size vs clock speed is ridiculous.
    • Ok, if you use a single photon to send the information , it cannot be eavesdropped. But in the current networks it'll only go around a couple of meteres at Max and you can't use an amplifier/repeater with this.

      Not so. My girlfriend [hw.ac.uk] is working on this. They have managed to send keys at large data-rates over conventional networks up to a distance of several tens of kilometers. In fibre networks, this distance approaches the pitch of the amplifiers.

      You are right about not being able to amplify the signal

    • by OzRoy (602691) on Thursday January 20, 2005 @08:15AM (#11418248)
      Quantum entanglment cannot be used to send information faster than light, as explained here [cornell.edu]
  • "...a quantum computer so powerful that the only way to protect against its prodigious code-breaking capability may be to deploy quantum-cryptographic techniques."

    scary stuff....however, a simpsons quote comes to mind:

    Alien 1: It seems the earthlings won.
    Alien 2: Did they? That board with a nail in it may have defeated us. But the humans won't stop there. They'll make bigger boards and bigger nails, and soon, they will make a board with a nail so big, it will destroy them all!
    [both alie
  • by Anonymous Coward

    If someone tries to intercept this stream of photons--call her Eve--she cannot measure both modes, thanks to Heisenberg.

    That's wrong. The Uncertainty Principle merely states that an observer cannot measure both position and momentum with arbitrary precision.

  • by Uhlek (71945) on Thursday January 20, 2005 @03:19AM (#11417272)
    Quantum encryption is a misnomer, it should be called (and is, in some circles) quantum key distribution. It's all about how the key is transmitted, not how the data is secured. The encryption method is independant of how the key is distributed. Contrary to popular belief, it typically cannot be a one-time pad, since the bandwidth on the "key" channel is very limited due to the exact nature of the transmission. It can be, though, a constantly shifting AES key, or other type of data, making the datastream as a whole effectively unbreakable.

    The problem lies in that you have to have a single, unbroken fiber optic connection between the two points, and this fiber optic connection is very limited in the amount of loss that it can withstand. That means you're geographically limited on how far the circuit might be able to travel. You're looking at a few hundred kilometers, at the absolute maximum.

    Considering the amount of money you'd spend on putting the circuit in place versus the amount of money you'd lose if the data was compromised, it's very unlikely that anyone, anywhere will have a practical use for QKD/QE. Government and defense, maybe, but then only in very limited applications.

    There is a chance that, should quantum computing become a reality and modern encryption algorithms can suddenly be cracked very, very easily that this method may see some use, and by no means is development a waste of time and effort. But, QC is still very much in the early stages, if a working system is ever developed at all.

    Thta being said, PKI and courier delivery of key material will continue to be the order of the day for quite some time.
    • PKI and courier delivery of key material will continue to be the order of the day for quite some time

      Unless you want to have a completely secure network of computers. Make a grid out of them and you cover the whole country. Every node will have to be as secure as the origin and destination, but likely these will be the nodes themselves, so no harm done. Also it may be possible to use layers of encryption, so that every node to node link carries message encrypted for some other node, and thus no single bre

    • We're making progress in QKD through the air though. It doesn't and probably won't have the range for global communications. But it could easily have the range for battlefield ones.
  • by whimsy (24742) on Thursday January 20, 2005 @03:35AM (#11417323)
    give it a shot.

    Particles that are treated best by quantum theory (such as photons, here) exhibit quantum states. Just think of them as metainformation about the particle, which is accurate to a first approximation and appropriate for this explanation. In this case, the light is polarized, which dictates some of its quantum metainformation.

    The Heisenberg principle, which you've probably heard about, says that you cannot know the position and momentum of a particle exactly, simultaneously. You can know one or the other exactly, you can know both with noninfinitesimal error, but you can't know both. For big, heavy things, like macroscopic objects, the uncertainty is so small as to be irrelevant.

    The quantum weirdness which results is as follows: an unobserved object simultaneously exists in a linear combination of multiple quantum states. That is, it exists as

    (x*A+y*B+z*C)/(x+y+z)

    Where A,B,C are quantum states and x,y,z are relative probabilities. If they add to 1, the x+y+z term falls out.

    This is where schrodinger's cat. If you wait exactly long enough that the probability of the cat dying is 50%, the cat is exactly equal parts dead and alive. It's accurate, but I think it's confusing because it confuses the fact that quantum states really only apply to very small things, except in isolated cases like this.

    Where the unbreakability of quantum encryption comes in is the observer. If you open the box, the cat is no longer both, it's just dead or alive. If you look at the photon, it's A,B, or C. You have destroyed the metainformation contained in the photon, because up until when you observed it, it was x parts A, y parts B, and z parts C.

    This is unavoidable and fundamental to quantum mechanics.

    For quantum encryption/communication not to work this way, we have to be wrong about quantum mechanics, and the fact that it's just so WEIRD is part of the reason I suspect it will work. It's so counterintuitive people have verified this many times.

    • by Anonymous Coward
      An observer does not have to be a sentient being. Anything can be an observer, including, other quantum particles.

      At any given moment, a quantum particle is having its wave equation collapsed by an interaction with another particle. The key to understanding this is that even though the wave has collapsed, it is not really collapsed and will continue to transmit and collapse.

      It is a HUGE misconception that the cat is equally alive or dead, being as those are two fundamentally mutually exclusive propertie
    • by yo303 (558777) on Thursday January 20, 2005 @05:20AM (#11417663)
      The sender, Alice, sends a string of bits, choosing randomly to send photons in either the rectilinear or the diagonal modes. The receiver, Bob , makes a similarly random decision about which mode to measure the incoming bits. If Eve tries to intercept this stream of photons she cannot measure both modes, thanks to Heisenberg.

      So the big question is: Why does Alice have so many secrets? Why does she feel compelled to tell Bob everything? And what is up with Eve, always budding in?

      Personally I think there's something going on between Eve and Bob, that they're not telling us. But damned if I can't break their code.

      yo.


  • In my job as a contractor for a government agency, I've had the opportunity to read a lot about the history of crytopgrahy and code breaking. If there's one thing I've learned, it's that one time pads are unbreakable (when properly created and handled). Does quantum computing affect this unbreakability?
    • No. But it can break anything based on the discrete logarithm problem or the factorisation of large numbers (which means RSA and most public-key stuff in use today), as well as any block cipher with a reasonably big bit of ciphertext (as it lets you check all possible keys very quickly).
  • Finally we can start research stating that P=NP without worry that our discovery would empty our accounts.
  • by tonywestonuk (261622) on Thursday January 20, 2005 @04:54AM (#11417588)
    Alice sends Bob a stream of photons. Each photon that is sent, Alice encodes a state of '1' or '0' on each photon.

    Unfortunately, Due to Quantum Mechanics, Bob only has a 50% chance of actually reading the state of the photon. 50% of the time he gets '0' or '1', and 50% of the time he gets 'Unknown', and the photon is destroyed..
    This is ok, because after receiving 1 million bits, Bob phones up Alice on an unsecured line and says I managed to read photon numbers 5,6,9,12,13,16....(+ approx 500,000 more), so I will use the state of these photons as a one time pad. Alice looks up the states she sent these photons, and now both parties have a one time pad to encrypt data.

    Now, lets say there was an intruder attempting to intercept the key exchange. The intruder is also constrained QM, and can only read 50% of the photons, with the other 50% Destroyed. Because, the 50% of photons the intruder would receive, would be different to the 50% bob had read, it is impossible for the hacker to use the information sent using by bob to Alice, via the unsecured phone call, to build an equivalent one time pad.

    Also, as the intruder is only able to forward a exact copy of just 50% of the photons to Bob, with the other 50%, now destroyed. He could replace this 50% of photons with his own set of random state photons, but this will be detected by Bob and Alice, as the one time pads would be different on this 50%, and the transmitted data using the pads would be corrupted.
    • Ummm... (Score:2, Interesting)

      by Kjella (173770)
      ...unless there's a flaw in this analogy, I don't see how this protects again a man-in-the-middle attack.

      Alice is sending a key to Bob. Hacker intercepts the key exchange and sends his own key to Bob. Bob tries to report back, but is also intercepted. He reports back to hacker which bits he got of the hacker's key, hacker reports back to Alice which bits he got of Alice's key. Then the hacker sits in the middle reencrypting on-the-fly.

      Personally, I thought it was only good to transfer messages securely. F
    • Except that when Bob talks to Alice, Alice happens to be Eve. Oops! And since there isn't any quantum authentication yet, the quantum crypto adds precisely nothing! (since security is only as strong as it's weakest link).

      I've said it a million times, and I guess I have to say a million times more: Quantum crypto doesn't protect against an active Monkey-in-the-middle attack! And thus it is not the perfect uncrackable holy grail everybody is so hyped up about.

      Nothing to see here, move along...
      --Blerik
  • I've known about id Quantique for a while, and have no relationship with them other than I think they rock. One of the more interesting things they sell is Quantum Random Number Generators. These babies work by sending a stream of photons at a half-silvered mirror. Each photon will be either transmitted or reflected, though it is impossible to tell which beforehand. A single photon detector on the other side of the mirror turns the reflection/transmission event into a bit. This bit is PURELY RANDOM. T
  • Before you'll know it the will be another hot-or-not spinoff called "is my cat dead-or-not" and it will be a bunch of blank pictures.
  • Technology VS. Laws (Score:3, Interesting)

    by Lepaca Kliffoth (850669) on Thursday January 20, 2005 @08:20AM (#11418271)
    Just a thought, maybe off-topic. I think articles like this one show the inherent flaw in anti-circumvention laws. While the american government says "if you put a lock on something it's unlawful to break it, develop something that breaks it, tell someone how to make something that breaks it etc. etc." we're all seeing where technology is going: quantum computing (sorry if this term is not the right one, have mercy, I'm italian, I mean the ability to compute using quantum mechanics principles) could very well break any kind of lock we know today. This is more proof that high-level, modern technology and copyright/anti-circumvention laws can't possibly coexist as long as copyright has the form and shape it has today. Either laws change or technology stops. Sorry if this comment was too much off-topic.
  • problem with making a quantum computer, you have to somehow isolate a bunch of particles so they have absolutely no interaction with each other or with anything else. Kinda hard to do. It's been done for very small numbers of particles, for very short times. And if the theory is correct, there are really steep limiting curves to how many and how long you can have particles in the proper state before they decohere. So I wouldnt expect to see a quantum computer at Wal-Mart for many many decades.
  • Question (Score:3, Insightful)

    by Woogiemonger (628172) on Thursday January 20, 2005 @10:46AM (#11419284)
    Is it possible to detect whether or not something quantum-encrypted is being transmitted? There's plenty of information you can garner from a transmission based on the start and stop time, frequency, source and destination, duration, etc. - Scott

Overdrawn? But I still have checks left!

Working...