Please create an account to participate in the Slashdot moderation system

 


Forgot your password?
Close
typodupeerror
×
Encryption Security Science

Quantum Cryptography Gets Nanotube Boost 209

Posted by timothy from the sending-secret-stuff dept.
c1ay writes "In an article at the ScienceDaily News it is reported that two researchers at the University of Rochester have discovered a new property of carbon nanotubes, ideal photon emission. "The emission bandwidth is as narrow as you can get at room temperature," says Lukas Novotny, professor of optics at Rochester and co-author of the study. Such a narrow and steady emission can make such fields as quantum cryptography and single-molecule sensors a practical reality. RSA and Elliptic Curve wouldn't stand a chance against this unbreakable encryption."
This discussion has been archived. No new comments can be posted.

More

Comments Filter:

  • distributed.net (Score:5, Funny)

    by Anonymous Coward on Tuesday September 09, 2003 @02:04AM (#6907457)
    When will they have a quantum encryption cracking competition? Go Team Slashdot!
  • Any cryptographer would know that.. it just might take 10^19 years to crack a key!
    • A one time pad is 'unbreakable'
      • That is true only if the numbers are completely random and never repeat. If a one-time pad's numbers ever repeat, even by chance, then hypothetically it can be broken. So if you have a true, perfect random-number generator, you may be correct.
        • Some repetition is a feature of randomness - as the string of random numbers gets larger, is beomes more and more likely that there will be a repetition somewhere. A very long string of numbers in which no sequence was repeated would be astronomically unlikely, and therefore not 'really' random.
          • How about a non-terminating, non repeating decimal expansion of a number? Pi? sqrt(2)? The square root of 2, in particular, has been shown to be an irrational number. This means that it cannot be written as the form m/n, where m and n are integers.

            This means that it can't be repeating (0.454545... = 45/99) and it can't terminate (0.3453 = 3453/10000). This was proved [maths.org] back in pythagorean times (second yellow box as you scroll down the page).

            Note that most square roots, cube roots, 4th roots, etc are g
            • Yeah, that's all true. Maybe I misunderstood what the original poster meant by "repetition".

              What I meant was that repetition of any particular string of digits, eg 228634254 or whatever, is inevitable in any truly random sequence if you keep churning out the numbers long enough. In fact, if your evesdropper knew that you were filtering out such repetitions, then he could use this redundancy in the keystream to have a go at brute-forcing the pad.

              I read somewhere that this is one of the reasons it's har
      • A one time pad is 'unbreakable'

        You can still brute-force a one-time pad.

        • Re:No cryptography is unbreakable... (Score:2, Insightful)

          by Anonymous Coward
          Troll?

          Of course you can't brute force a one-time pad, not usefully. Each key is equally likely, and you never know if your "decrypted" message is the correct one.

          This assumes, of course, that the key is truly random.
          • Well if you brute force with all combinations, one will give the plaintext...so in a sense you have cracked the code.

            Nevermind, that was just stupid, I'm going back to bed now.
            • "if you brute force with all combinations, one will give the plaintext...so in a sense you have cracked the code."

              Yeah, it cracks me up that a larger portion of sd will reply with statistical assumptions based on textual logic, when finding useful information in collected in encrypted streams (disected by best guesses with 'fun in bruting') is more like looking for a rainbow in an Irish field, rather than looking for genetic sequences in a massive punnett square. It seems even smart people have a problem

              • Re:No cryptography is unbreakable... (Score:4, Interesting)

                by aziraphale ( 96251 ) on Tuesday September 09, 2003 @10:20AM (#6909438)
                You seem to be under the impression that decrypting a one time pad is just a case of trying different keys and watching the results for output that makes sense. That is laughably incorrect.

                Brute forcing is a method you use to decrypt a known ciphertext using a known algorithm. It involves trying every possible key in the algorithm, and examining what plaintext would result. Given, say, 1024 bits of ciphertext, and a simple symmetric algorithm with a little 56 bit key, you could run the decryption with each of the 2^56 possible keys, giving you 2^56 possible different plaintext renderings of that 1024 bit message. Out of all the possible messages that 1024 bits could communicate (2^1024 of them), we've narrowed down the field to just 2^56 - in other words, we've reduced the field by a factor of 2^968 (that's about a googol cubed). Assuming the message was originally written in in a natural human language, like English, there is a lot of redundancy built in to the message. On average, one character of English communicates 1.4 bits of information - encoded in ASCII, that means you've only got 1.4 bits of actual data encoded in every byte of the original message. So, of the 2^1024 possible messages the ciphertext could encode, only 2^(1024/8*1.4) of them - about 2^179 - contain the right proportions of characters to make any kind of sense in English. But remember, we eliminated 1-(1/googol^3) of the possible messages by examining which messages could possibly be generated by a valid key. So, the odds of more than one of those 2^179 messages making any kind of sense are somewhat less than one in a googol squared.

                But with a one-time-pad as your algorithm, the key is exactly the same length as the message. So, to bruteforce it, your 2^1024 bits of ciphertext has to be decrypted using 2^1024 different one time pads. Again, only 2^179 of the possible decrypts will actually make any kind of sense. But because we've tried 2^1024 different keys, we obtained 2^1024 different candidate plaintexts - which means that 2^179 of them look like they might make sense. In other words, we've got almost a googol different English language plaintexts - all of which could have been encrypted to make the same ciphertext, depending on the one time pad used. It's a little like saying 'A CD is just a stream of numbers. If we burned every possible CD, starting from 0000000..(50 odd million bits)...000001 up to 11111....11111, one of them will contain the next album Hendrix would have made if he'd lived'. It's true, but somewhat useless.

                So, one time pads are, indeed, completely non-brute-forceable.

                They can be cracked if they aren't used correctly or if they aren't generated correctly. Take two messages accidentally encrypted with the same one time pad, and the game's up - both messages will be revealed. If the pad isn't truly random, then the keyfield gets reduced. You only need to reduce the keyfield by a factor of, oo, about 2^179 (well, it'll vary depending on the length of the ciphertext), to start getting to the point where the number of plausible plaintexts generatable from any valid key is small enough to be interesting. If you generate your random numbers with a pseudorandom generator, the key size is effectively reduced to the size of the key used to seed the generator.
        • That doesn't make sense in the context of a OTP. The OTP is as long as your plaintext input, and every bit of the input is XOR'd with the OTP. You can't tell the difference. How do you propose to brute force that?

        • Re:No cryptography is unbreakable... (Score:4, Informative)

          by _LFTL_ ( 409654 ) on Tuesday September 09, 2003 @02:16AM (#6907505)
          You can still brute-force a one-time pad.

          Maybe you were being sarcastic, but to those who don't know you can't brute force a one-time pad. When you look at all possible results for brute forcing a one-time pad; it's all possible plain text combinations for that length of message. So there could be 1000s of message that "make sense" but you'll never be able to tell which is the right one unless you already know a lot about the message being sent.

          • Re:No cryptography is unbreakable... (Score:4, Funny)

            by sessamoid ( 165542 ) on Tuesday September 09, 2003 @03:16AM (#6907710)
            >You can still brute-force a one-time pad. Maybe you were being sarcastic, but to those who don't know you can't brute force a one-time pad.

            You can indirectly "brute force" break a one-time pad, however. It works like this:

            1) Intercept the message.
            2) Go to the person who sent the message.
            3) Beat him repeatedly in pain-sensitive areas until he agrees to give you the one-time pad.
            4) Profit?

            Voila! One-time pad.... broken!

            • You can indirectly "brute force" break a one-time pad, however. It works like this: 1) Intercept the message. 2) Go to the person who sent the message. 3) Beat him repeatedly in pain-sensitive areas until he agrees to give you the one-time pad. 4) Profit? Voila! One-time pad.... broken!

              No. You can't actually crack a one-time pad that way! Why? Because it is possible to create a key which will cause the ciphertext to decrypt to any plaintext you wish! So if you are being tortured you simply hand over

        • brute force in the sense of trying just tons of combinations, but with a true one time pad any one result is just as likely as any other so there is no determinant way to truly break a true one time pad. You couldn't ever tell if a 5 character piece encrypted with a one time pad would say "Hello" or "bitch" because the possible combinations with an unknown one time pad are just as likely

        • Re:No cryptography is unbreakable... (Score:4, Funny)

          by Ignis Flatus ( 689403 ) on Tuesday September 09, 2003 @02:37AM (#6907574)
          You can still brute-force a one-time pad.

          Maybe so, but he still won't talk. All our one-time pads are equiped with a special cyanide-filled tooth to bite down on, just in case they are captured.

        • Re:No cryptography is unbreakable... (Score:5, Informative)

          by Tom ( 822 ) on Tuesday September 09, 2003 @07:06AM (#6908209) Homepage Journal
          You can run a brute-force attack against it. But you have no way of knowing that what you decrypt is the actual plain text. Any text of the correct length is a valid plain text.

          Here's a string encrypted with a one-time pad:

          FJERZFTHWRTUWZNE

          Depending on my OTP, it can decrypt to either "SlashdotForever!", or "OneTimePads=Good". Actually, it's neither. It's my credit-card number. If you can decrypt it, it's yours.
          • I strongly suspect your random number generator is flawed. There is way too much repetition. 12 letters come in pairs, out of a total of 16 letters. 8 out of 16 letters are on the top row of a qwerty keyboard. Also, 5 out of 10 unique letters are on the top row of the keyboard. There are a few other patterns, but I'll leave that as an exercise for the reader.
        • Wow... 20% Troll, 20% Informative, 20% Funny. The mods don't know their arse from a hole in the ground.

          I guess next time I should add a smiley or something? :)

      • I wonder why... (Score:5, Interesting)

        by imsabbel ( 611519 ) on Tuesday September 09, 2003 @06:20AM (#6908119)
        Noone has ever created a One time Pad plugin for outlook.

        Think about it. Create a random one time Pad of a few hundred MB. Burn it on 2 cd-r. Put one in your safe and hand the other to BOB in person.

        Now just use the pad piece by piece for your secure transmissions. It should last for years if you dont sent porn or warez....

        As long as you use every part of the pad only once, even if the attacker gets the plaintext of one message the others wont be compromised.

    • Re:No cryptography is unbreakable... (Score:3, Interesting)

      by Anonymous Coward
      Not in this case. It's one of the deeply ingrained features of quantum cryptography, that the act of reading the message, even in the encrypted form, changes the content. It is in fact unbreakable, on a very elementary physical level.
    • To skip right to the heart of it, from the article, here's how it can be broken:

      "Quantum cryptographic techniques provide no protection against the classic bucket brigade attack (also known as the ``man-in-the-middle attack''). In this scheme, an eavesdropper, E (``Eve'') is assumed to have the capacity to monitor the communications channel and insert and remove messages without inaccuracy or delay." http://www.cs.dartmouth.edu/~jford/crypto.html [dartmouth.edu]

      Not exactly "unbreakable". Thanks to whoever posted th
      • from what I can tell.. the Quantum Key Exchange can be compromised IF "eve" is able to "insert and remove messages without inaccuracy or delay." Now, simply by reading the photons at a certain polarization, Eve is screwing up the transmission.. So it's only compromised in this way if each bit of a key is transmitted using a burst of photons instead of just one. Then maybe eve could snatch only one.. and then maybe store it until she found out what the polarization scheme was. THEN she could record which dir

      • Re:No cryptography is unbreakable... (Score:5, Informative)

        by menscher ( 597856 ) <menscher+slashdotNO@SPAMuiuc.edu> on Tuesday September 09, 2003 @03:08AM (#6907671) Homepage Journal
        It's rather unfortunate that that article is getting so much attention, considering it's wrong.

        The link you provide assumes that Eve can monitor the communications channel and insert/remove messages. Yes, those are the prerequisites for a MITM attack. But those are also precisely the things that quantum crypto protects you against.

        The link assumes that photons will be sent in bursts, rather than one at a time. This is not the case. They are actually sent fairly infrequently, in order to avoid the possibility that two could be sent simultaneously. Also, even if more than one were sent, it is unlikely to be helpful to an attacker, since multiple photons would not necessarily have the same characteristics.

        The link furthermore makes the assertion that Eve could somehow duplicate a photon. This makes it clear that the author is a CS grad student and not a physics grad student. The Heisenberg uncertainty principle prevents this duplication.

        In short, don't believe everything you read... especially if it's on the web.

        • Re:No cryptography is unbreakable... (Score:1, Informative)

          by Anonymous Coward
          I am sorry, while you are completely right that this is in practice unfeasible, photon number splitting (PNS) attacks are well studied attacks. If you want some serious information about it, have a look at quant-ph/0302037. There are analysis for PNS attacks with actual (and good) parameters for photon emission, which show that e.g. BB84 over 50km would be insecure against these attacks.

          Basically you don't want to duplicate photons, you just steal a photon. If there are losses on the quantum channel (which
        • True, you can't duplicate a quantum state. If you could, then you could duplicate a particle's state and exactly measure the position of one copy and the momentum of the other. That's how the Heisenberg uncertainty principle applies to duplication.

          The (theoretical) problem is that real equipment today is built around attenuated lasers and really does tend to send bursts of multiple photons through the same polarizer. The theory depends on sending single photons at a time, which is why the promise of contro
      • The key distribution problem can be partially solved by quantum mechanics using the idea of quantum key distribution (QKD). The first and best-known protocol, usually called "BB84" because it was published in 1984 by Charles Bennett and Gilles Brassard,6 is described in the box below. In a prototypical QKD protocol, Alice sends some nonorthogonal quantum states to Bob, who makes some measurements. Then, by talking on the phone (which need not be secure), they decide if Eve has tampered with the quantum stat
  • they discovered this interesting phenomenon while playing with their bucky balls.

  • Before no one can read it: (Score:5, Informative)

    by windex82 ( 696915 ) on Tuesday September 09, 2003 @02:09AM (#6907476) Homepage
    Nanotubes Surprise Again: Ideal Photon Emission

    Sept 5, 2003 -- Carbon nanotubes, recently created cylinders of tightly bonded carbon atoms, have dazzled scientists and engineers with their seemingly endless list of special abilities--from incredible tensile strength to revolutionizing computer chips. In today's issue of Science, two University of Rochester researchers add another feat to the nanotubes' list: ideal photon emission.

    "The emission bandwidth is as narrow as you can get at room temperature," says Lukas Novotny, professor of optics at Rochester and co-author of the study. Such a narrow and steady emission can make such fields as quantum cryptography and single-molecule sensors a practical reality.

    The emission profile came as a surprise to Todd Krauss, assistant professor of chemistry at the University, and Novotny. They had set out to simply define the emission, or fluorescence, of a single carbon nanotube. By using a technique called confocal microscopy, the team illuminated a single nanotube with a strongly focused laser beam. The tube absorbed the light from the laser and then re-emitted light at new frequencies that carried information about the tube's physical characteristics and its surroundings.

    The light emitted from the nanotube was in precise, discrete wavelengths, unlike most objects like molecules that radiate into a broader (i.e. more "fuzzy") range of wavelengths at room temperature.

    But a greater surprise was in store for the team.

    "The emission wasn't just perfectly narrow, it was steady as far as we could measure," says Krauss. In a strange quirk of quantum physics, molecules usually emit their photons for a certain time and then cease, only to resume again later, like a telegraph signal. The tubes that Krauss and Novotny measured, however, remained steady beacons to the limits of their instruments' sensitivity. "This is very exciting because for any application in quantum optics, you want a steady and precise photon emitter," says Novotny.

    Narrow emissions and a complete absence of blinking have tempting implications for single photon emitters--devices needed to dependably release a single photon on command. The U.S. Department of Defense is very interested in developing quantum cryptography, a theoretically unbreakable method of coding information, which necessitates a reliable way to deliver single photons on demand.

    Other applications come in the form of sensors so sensitive they can detect a single molecule of a substance. For example, when a biological molecule such as a protein binds to a nanotube, the nanotube's perfect emission changes, revealing the presence and characteristics of the molecule. Detecting the change would be impossible if it weren't for the remarkably steady nature of the nanotube emission, because a researcher wouldn't know for certain if a sudden change in the emission was just a blink, or was meant to indicate the presence of the target molecule.

    Until just a few months ago, determining the emission characteristics of a nanotube was impossible. Carbon nanotubes cannot be made individually-rather they come as a jumble like a pile of spaghetti. Trying to measure the photon emission of a tube in the jumble is impossible because the tube will pass the photons it absorbs to other tubes instead of re-emitting them in its telltale fashion. What scientists end up with is a sort of average of what the collection of tubes will emit--not the emission characteristics of a single tube. Only within the past few months have researchers figured out how to remove a single nanotube from the pile of spaghetti in order to study its properties as an individual.

    Krauss and Novotny are now devising experiments to test the steadiness of the nanotube fluorescence beyond the range of the initial experiments, and are pursuing studies aimed at determining the ultimate minimum possible emission bandwidth at ultracold temperatures.

    This work was funded by the National Science Foundation, the U.S. Department of Energy, the Research Corporation, and the New York State Office of Science and Academic Research.

    Editor's Note: The original news release can be found here.

    This story has been adapted from a news release issued by University Of Rochester.
    • Could someone give a break down on how all this "nano-stuff" is going to actually help me one day? Ive heard talk of self replicating devices to repair things and the like, but that seems a LONG time away. When (and if currently how) are these "nano-anythings" going to help me out in my day to day life? In the hospital? At work?

      Dont get me wrong im not implying that if its not helping me they shouldnt be working on it, id just like to know what and when its going to be usefull.

      • Re:Before no one can read it: (Score:5, Informative)

        by forkboy ( 8644 ) on Tuesday September 09, 2003 @02:35AM (#6907567) Homepage
        Well, here's one example...in the article they mentioned that they can do something like detect one molecule of a substance. The implications this has on analytical chemistry are staggering.

        For instance, when your body has certain ailments, it will generate chemicals that are not normally present in the metabolism. These chemicals are often released in VERY small amounts when you exhale. There are prototypes of tests now that can detect the presence of these chemicals at a certain level, but really it is only useful when the ailment is near the chest cavity. (lung / breast cancer) Something that can detect molecules on a "parts per trillion" or even lower range could easily find even smaller trace amounts from illnesses in other parts of the body.

        How does this help you? Imagine knowing that you were ABOUT to get cancer rather than finding out 6 months after it had spread to every major organ in your body. Much easier to treat it that way, and your chances of survival are increased a hundred-fold because of a quick, easy, cheap breath test your doctor could administer.

        Environmental laboratories could detect pollutants on a smaller level, and measure small changes in concentrations, thereby preventing a problem before it occurs. Mercury, for instance, can't be detected by analytical equipment until it reaches concentrations in the "parts per billion" or 1 mercury atom per billion water atoms. (about the size of a mist particle or dew drop) Imagine being able to detect a single drop of mercury in the equivalent of a swimming pool. Doesn't sound like much, but now think of being able to tell that the concentration doubled each month for the last 12 months. It's still way below current detection standards, but you've found now found a trend and have some time to locate the source of contamination.

        Is that a good enough start for ya?

        • Re:Before no one can read it: (Score:4, Interesting)

          by Insightfill ( 554828 ) on Tuesday September 09, 2003 @11:46AM (#6910741) Homepage
          Privacy implications are equally staggering.

          Imagine being able to administer a drug test to an employee by simply swabbing the mouse or keyboard after hours. Suddenly, being in the same room as someone who had smoked some pot recently. (A recent famous drug case found cocaine traces on the paper currency in the pockets of many people in the court room - even the judge.)

          Imagine being able to screen people for EVERYTHING as they pass through a "metal" detector at the airport. If you even touch a firearm within a few days of take-off, you'll have residue on your fingers.

          If this can be tuned for genetic testing, then films like GATTACA will be more science and less fiction.

          OK, now I've got to go scrub my hands for an hour.

          • A recent famous drug case found cocaine traces on the paper currency in the pockets of many people in the court room - even the judge

            This is really, really stange that they would test this, because it is commonly known [halfbakery.com] that most currency contains traces of cocaine. It is thought that it is usually distributed through a few contaminated bill in contact will other bills in an ATM machine.

            • This is really, really stange that they would test this, because it is commonly known that most currency contains traces of cocaine.

              Actually, the point is that "commonly known" doesn't come into play often enough in courts. It actually had to be hammered home in study after study before courts stopped using the "dog smelled cocaine in his wallet" test for arrest, RICO seizures, etc. Prior to the "commonly known" point, it was pretty common to use it as evidence in court.

              This Urban Legends [urbanlegends.com] article has

        • Detecting cancer before it starts is not profitable.

          Allowing patients to get cancer, and subjecting them to millions of dollars worth of surgery, chemicals, and radiation therapy ARE profitable.

          Which solution do you think the big pharmaceutical companies are going to fund research for?

  • Quantum Cryptography Tutorial (Score:5, Informative)

    by Stuttgart ( 704324 ) on Tuesday September 09, 2003 @02:10AM (#6907478)
    http://www.cs.dartmouth.edu/~jford/crypto.html

  • From Quantum Cheating to Quantum Security (Score:5, Informative)

    by Phoenixhunter ( 588958 ) on Tuesday September 09, 2003 @02:10AM (#6907479)
    http://www.aip.org/pt/vol-53/iss-11/p22.html

    Mostly a theoretical breakdown of the advantages of quantum encryption, in fairly easy to understand language.
  • When will they invent something faster than the speed of light ? It's 2:23am and I still can't get a first post because of the latency!

  • Unbreakable, bah (Score:4, Insightful)

    by dmiller ( 581 ) <[gro.tordnim] [ta] [mjd]> on Tuesday September 09, 2003 @02:25AM (#6907533) Homepage
    So-called "quantum encryption" may be unbreakable, but it is ignorant to portray it as a competitor to something like RSA. Quantum encrypton is a link-layer technique - something one would use to prevent eavesdropping on a single fibre hop (which is hardly a problem anyway).

    Worse, it is hardly practical for real networks anyway - with routers, repeaters, EBFAs or Raman amps everywhere. If it ever makes it out of the lab, it may be useful for military systems (where money is no object), but it won't help you pirate music anonymously.

    • Re:Unbreakable, bah (Score:3, Informative)

      by Izago909 ( 637084 )
      Observing the state of a photon would change it. This makes quantum encryption perfect for evesdropping situations. You will know if someone has seen your data. Also, you can't be sure of it's exact path. The thing about those pesky subatomics is that you can't know their exact position and path at the same time.

      • Re:Unbreakable, bah (Score:4, Informative)

        by Bronster ( 13157 ) <slashdot@brong.net> on Tuesday September 09, 2003 @02:56AM (#6907632) Homepage
        Observing the state of a photon would change it. This makes quantum encryption perfect for evesdropping situations. You will know if someone has seen your data. Also, you can't be sure of it's exact path. The thing about those pesky subatomics is that you can't know their exact position and path at the same time.

        Pity anyone can install a sniffer on the router where's it's decoding the packets from one quantum cable and adding them to the next.. ..fine if you can afford end-to-end links with everyone you want to communicate with of course, but not so good if you're switching along the way (as the parent you so cleverly responded to made quite clear, really)
    • According the the Sep. 6th issue of The Economist [economist.com] there is a company in Massachusetts called MagiQ [magiqtech.com]in the final stages of testing a system which it plans to release commercially in the next few months.

      "The scheme devised by MagiQ, called Navajo, does not use quantum effects to transmit the secret data. Instead, it is the keys used to encrypt the data that rely on quantum theory. If these keys are changed frequently (up to 1000 times a second in Navajo's case), the risk that an eavesdropper without the ke
      • Just add another wheel to the Enigma machine Hermann. Those dim-witted English shopkeepers vill never figure it out...

        We didn't figure it out; we had to get the Poles to steal one and give it to us. And we relied on pinching code books from captured U boats to crack the naval version of Enigma. As usual, it was human failure (to destroy the code books, to not re-use wheel settings day to day, etc.) that compromised Enigma.

        Jon

      • Sounds like BS to me... Unless the key is longer than the message, you can brute force it. Now, the chance of being able to decrypt the data in 10 years might be 10^-5678 - but that isn't zero. The chance of breaking the code given infinite time and resources is always 1 - unless it is a one-time-pad - then it is 0.

        And how are these 1000 keys a second exchanged? Most key-exchange systems are vulnerable to quantum computing - so if you just save the ciphertext and key-exchange transmissions for a decade

    • Quantum Crypto vs. Quantum Computing (Score:5, Informative)

      by billstewart ( 78916 ) on Tuesday September 09, 2003 @05:16AM (#6907990) Journal
      Sigh. People keep mixing up the two areas, just because they're both related to deep magic stuff :-)

      Quantum cryptography is a method for using quantum physics to make sure nobody reads your bits. Technically cool, but seldom practical. If you happen to have direct fibers connecting you with the people you want to talk to, it might be useful, though it's probably more useful and certainly cheaper to just run Gigabit Ethernet and use conventional encryption, such as AES.

      Quantum computing is a totally different animal. It uses Quantum Black Magic to create a computer which can collapse a waveform and have it land at the solution of some classes of NP or similarly problems with at least some significant probability of success, thereby cheating on the fact that it normally takes an exponential or at least superpolynomial number of guesses to find a correct answer. One problem that can theoretically be solved if you have a quantum computer of sufficient resolution is factoring - which means that if such a device were developed, it would break RSA and several other public-key algorithms, whose strength depends on them being exponentially hard if you don't have the key and low-order polynomially hard if you have it. For some other classes of algorithms, it doesn't totally break them, but reduces their strength to half the number of bits, i.e. square-root as hard as before, so you'd need to use twice as many key bits. For algorithms like Elliptic Curve, it's not clear whether they'd be broken, but they'd be a lot more dodgy.

      The implications of breaking them are that right now, public key lets you build a lot of very useful communication models. It's hard to replicate signatures without PK, but the privacy applications could be replaced by going back to the old Key Distribution Center models, e.g. Kerberos, which are much less socially powerful.

      Building a useful quantum computer requires building something that can detect states with sufficient precision. We currently have the technology to make simple quantum computers (one famous one was able to factor the number 15 into 3x5) but nobody knows how to get high precision yet. One question I don't know is whether a QC would be limited by the Heisenberg Uncertainty Principle (i.e. you've got one variable with a resolution that's never better than Planck's Constant, about 10**-47, which is slightly annoying cryptographically but not fatal because you can use longer keys), or whether it can be built by coupling together a number of units, each of which only needs enough precision to get N bits of the output and you get longer numbers of bits by using more units (that would be much more annoying.) We're nowhere near this yet, but it's the one technology that doesn't run into the typical exponential cryptography "brain the size size of the planet of a planet waiting for the Restaurant at the End of the Universe and still don't have an answer, I'm so depressed" kind of limits that we can easily create otherwise.

    • Re:Unbreakable, bah (Score:4, Informative)

      by misterpies ( 632880 ) on Tuesday September 09, 2003 @06:26AM (#6908131)
      That's not quite true; quantum cryptographic signals are not used to exchange messages, but only to guarantee a secure exchange of keys. These keys are then used to generate an unbreakable one-time pad encryption of the message, which can be broadcast publically without fear since only someone holding the key can decrypt it.

      The one-time pad is one of the simplest encryption algorithms there are: you generate a random key as the same length as your message, then add the two together. You end up with something statistically indistinguishable from a random string of bits, which can only be decoded by someone who has the same key. The big drawback of the one-time pad is that somehow you have to get the recipient a copy of the key, which via non-quanum methods (eg a courier) are always open to interception.

      Quantum key exchange uses entanglement to ensure that the sender and recipient can exchange keys, and be sure with arbitrary accuracy that no-one has intercepted the key -- because any attempt to intercept the key leaves a tell-tale sign. So it doesn't exactly prevent someone from stealing the key -- it just prevents them from doing so without you knowing.

      It's true that at present this key exchange can only be done over a fibre-optic network, but there's no fundamental reason why it couldn't be done by other means. For example, when quantum computing becomes practical, it might be possible to use entangled qubits -- you and I could each have a "memory stick" of billions of entangled electron pairs, and when we wanted to exchange a message we'd just use up entangled pairs as needed.

      Moreover because it's a key exchange, it could be possible to set up "key distribution centers", linked by fibre-optic networks. Then when we want to exchange a message, we first head down to our local centre and generate a key. Of course that's slightly less physically secure since maybe you'll be mugged on the way home, but it's stills secure against electronic eavesdropping. Even without such centres, it's obvious that many commercial establishments -- eg banks and stock exchanges -- could set up private fibre networks to guarantee secure data exchange.

      However one shortcoming of current quantum crypto algorithms is that they're only useful for one-to-one communication -- you can't securely ditribute a key to many people. That's probably enough to make it useless for "common" online applications like filesharing -- but how important is truly unbreakable cryptography for that (as opposed to mere unbreakable-within-the-lifetime-of-the-universe) ?

  • Hmmm, I bet we will be soon buying Carbon Nano Tube Protected(C) music. It won't play in some CD players, but the discs will be clearly labeled so we, the customers, won't be wasting our money.

  • newer isn't better (Score:3, Insightful)

    by Anonymous Coward on Tuesday September 09, 2003 @02:31AM (#6907555)
    RSA and elliptic curve are able to provide encryption safe from a man in the middle attack, as well as authentication of where a message came from (signing). This is far ahead of what quantum encryption offers.

    The only security quantum encyption has is that the message can only be read by one viewer - this prevents covert surveillance of the message, but not a man in the middle attack, nor a total interception.

    Pragmatically you bundle quantum encryption with other authentication techniques, but RSA on it's own is far more useful and secure than quantum encryption on its own.

    It's not time to throw RSA and Elliptic curve out just yet.

  • Doesn't address the real problem (Score:5, Insightful)

    by Mrs. Grundy ( 680212 ) on Tuesday September 09, 2003 @02:34AM (#6907561) Homepage
    RSA and Elliptic Curve wouldn't stand a chance against this unbreakable encryption."

    And crackers don't really stand a chance against the algorithms we have now. Although I'm happy to see them inventing cool stuff and cryptography os definitely neat, will this makes us more secure? Sure computers keep getting better and you need to stay ahead of the curve if you are someone like the NSA, but are people the loosing the security game because their 128 bit RSA keys keep getting cracked ? No. They are insecure because they have nanotube-size brains and use their birthday for their password or they leave a laptop with the vice president's agenda at a convenience store.

    • 128bit RSA isn't secure at all, since the attacks against it perform much better than brute force. 512 bit is more typical. Some use 1024 or 2048, but many see the latter as a bit excessive.

      128bit is secure for most symmetric ciphers, but not public key ciphers.

      Damn, I've gotta change my bank account password again. And some of my other passwords are still blank. It's a matter of work vs risk I guess.
    • Something like 2048 RSA is for all practical purposes unbreakable, so currently there is no real practical advantage to using quantum cryptography (or more precisely quantum key exchange) for material you want to protect for the next decade or so. The fear is that in the future, when quantum computation becomes feasible, huge numbers will become factorable very quickly, rendering any size RSA useless. In a sense quantum cryptography and quantum computation are "competing" on parallel paths, and it is good
      • Keep in mind that 1940's atomic bomb experimental results are still highly guarded secrets. Unless we anticipate anybody with a machine shop being able to fabricate nuclear weapons it will probably stay that way for quite a long time. If any of those 1940's documents were transmitted encrypted back then, they'd have been broken already. Hence, when transmitting really important secrets it is important to encrypt your data well, put it on a CD, and put it in a diplomatic bag carried by a guy with a gun un
        • Actually, if you have a good enough machine shop, good knowledge of physics, a lot of computer time and usable fuel if wouldn't be really difficult. Of course, this is the kind of comment that gets you locked away for a long, long time recently...
      • As far as I've heard, quantum computing will reduce an applicable problem's complexity to its square root, e.g. something that takes O(n^2) now takes O(n). In other words, your 2048 bit keys will still have a relative 1024-bit strength, which for all intents and purposes is still computationally impossible.

  • Quantum encryption isn't encryption (Score:5, Insightful)

    by Cardbox ( 165383 ) on Tuesday September 09, 2003 @02:34AM (#6907562) Homepage

    What we normally mean by "encryption" is "the transformation of readable stuff into stuff that can be seen by evil people without them able to understand anything". Encrypted data are a stream of bits just like anything else. Thus you can store your encrypted message on a disk, or write it down, or transmit it over a wire, or broadcast it.

    In this sense "quantum encryption" isn't encryption at all. Quantum encryption is something that can only happen as part of the act of transmission. There is no such thing as "quantum-encrypted data" that can be recorded or written down or transmitted over conventional media. The act of doing any of those things collapses the wave packet and destroys communication just as effectively as interception would.

    I'm not going to argue that we should start calling quantum encryption something else, the name is too snappy and too useful for getting research grants, but let's not get confused into comparing it with public-key or even private-key encryption: they're completely different animals.

  • RSA and Elliptic Curve wouldn't stand a chance against this unbreakable encryption.

    Huh? Are RSA and Elliptic Curve some method for breaking encryption? Yeah I know what he meant, just worded funny.
  • I thought Elliptic Curve only existed in Uplink until I read this article :p

  • RSA and eliptic would crush it! (Score:5, Interesting)

    by gessel ( 310103 ) on Tuesday September 09, 2003 @03:04AM (#6907662) Homepage
    Quantum cryptography is very interesting--an absolutely bizarre manifestation of one of the most spooky and anti-intuitive features of quantum mechanics. The very premise gave Einstein fits.

    But where RSA is used (and, barring an as of yet undiscovered in the open world weakness, elliptic curve cryptography) quantum cryptography has no application.

    Quantum cryptography is built on the quantum entanglement of photon pairs, who's wave function must remain un-collapsed by measurement or perturbation until decode. This feature is both quantum cryptography's strength and weakness:

    It's a strength because any Eve eavesdropping is irrefutably revealed.

    It's a weakness because it limits the applications to such Alices and Bobs where between actual original photons may be reliably transmitted.

    RSA and various other "Newtonian" cryptographic schemes make use of mathematical transforms rather than physical properties of individual particles and survive re-transmission with their essential properties intact; for example, over a packet switched network.

    What RSA may not ultimately stand a chance against are quantum computers, which according to a variation of Moore's law I might have been the first to state (at DEFCON 9 [dis.org]), will within a decade surpass then available classical computers and will (in theory) be exceptionally good at cracking encrypted documents.

    Assuming the NSA doesn't already have a good working quantum computer...

    And assuming it's possible to continue adding entangled qubits...

    Anyway, Moores law says the power of classical computers increases as 2^(Y/1.5), where Y is years. So far, roughly, quantum computers are increasing in power as 2^2^(Y/2), which should make em about 10^225 times as powerful as today's classical computers in 2 decades, and if that turns out to be so, then RSA really won't stand a chance. It might be a bummer for some: 4096 bit PGP keys are assumed to be safe against, for example, the combined efforts of all computers to be built according to Moores law between now and any normal lifetime, or at least well past the statute of limitations. But if quantum computer development continues apace, that assumption may be problematically flawed.

    But it's not quantum encryption that's the threat, it's quantum computers. Quantum encryption isn't any more unbreakable than whatever data method underlays it, though it's a fine way to transmit a stream of random numbers. The "key" is that it is, apparently, physics-ally impossible to intercept the stream of photons without causing a measurable effect. So Alice and Bob can be absolutely sure their one time pad is known only to them...

    as long as no one is looking over their shoulders...
    • [...]
      Assuming the NSA doesn't already have a good working quantum computer...

      And assuming it's possible to continue adding entangled qubits...

      Anyway, Moores law says the power of classical computers increases as 2^(Y/1.5), where Y is years. So far, roughly, quantum computers are increasing in power as 2^2^(Y/2), which should make em about 10^225 times as powerful as today's classical computers in 2 decades.
      [...]

      Given that one decade is 10 years, then for 2 decades:
      Y=20
      2^(2^(Y/2)) = 1.8*10^308
      (2^2)^(Y/2)
      • Rounding.

        OK - lame - I just read it off my own graph. Going to 20 years, excel barfs. At 19 years it's 10^224, 225 seems rounder, two decades is less specific than 19 years. I used increments of decades rather than years as an admission of wide tolerance.

        span . . .. 2^(D/.15). 2^(2^(D/.2))
        1 decades . 1.0x10^2 . 4.3x10^9
        2 decades . 1.0x10^4 . 1.8x10^308
        3 decades . 1.0x10^6 . 1.4x10^9864

        And yes, it's a massive IF. Of course. But I think a rather interesting if, as such things go. Thus far QC is on t

    • what's a quantum computer?

      Thanks!

      Sivaram Velauthapillai
    • It's a weakness because it limits the applications to such Alices and Bobs where between actual original photons may be reliably transmitted.

      There is some reason to suspect that quantum states are transmissible from one photon to the next ad infinitum. (Don't forget that all forms of data transmission involve direct physical linkage, even in the form of waves.) I would not rule out the ability of future quantum computers to be able to suss out such subtle states by the use of markers in data. Given the

    • "And assuming it's possible to continue adding entangled qubits...

      That's a really big ASSumption.

      Don't forget the other ASSumption, that you can maintain the quantum states long enough to do useful computations with them. OK, perhaps some day, but not in 10 years.

    • quantum computers, which according to a variation of Moore's law I might have been the first to state (at DEFCON 9 [dis.org]), will within a decade surpass then available classical computers and will (in theory) be exceptionally good at cracking encrypted documents.

      There isn't yet (after three decades of futile attempts) a loophole free two photon Bell experiment to prove that the entangled pair distant state collapse exists at all. With the "loophole" (euphemism used by believers, meaning in plain langu

  • Great... (Score:2, Insightful)

    by mikeg22 ( 601691 )
    Now we are one step closer to giving people the false impression that they can be idiots with their data because this particular magic bullet (QC) will be completely secure.

  • How about a new monitor design? (Score:4, Interesting)

    by Ignis Flatus ( 689403 ) on Tuesday September 09, 2003 @03:39AM (#6907776)
    All this talk about cryptography sure is sexy, but how about something practical, like a computer monitor with resolution so high you can't even see the pixels? I want a screen that is indistinguishable from a sheet of paper.

  • Be afraid, be very afraid (Score:3, Funny)

    by flopsy mopsalon ( 635863 ) on Tuesday September 09, 2003 @04:03AM (#6907848)
    Back when high-bit encryption was becoming popular, there was a great effort on the part of the government to control its use, especially the "export" of encryption technology.

    With the advent of unbreakable quantum encryption, we are clearly in for more of the same. If you think the line at the arirport is long now, just wait until security starts searching people for nanotubes. Me, I'm seriously considering driving everywhere.

  • Oh yeah..... (Score:4, Interesting)

    by ssimpson ( 133662 ) <<slashdot> <at> <samsimpson.com>> on Tuesday September 09, 2003 @04:03AM (#6907849) Homepage

    RSA and Elliptic Curve wouldn't stand a chance against this unbreakable encryption

    Oh yeah, that cheap and easy cryptography technology that can be performed on a CPU in a wristwatch or smartcard and be can used for encryption, signing, PKI infrastructure, n of m schemes etc will be instantly replaced by a system that's only good to transmit bits with a guarantee that the recipient will be able to detect if someone else is reading the traffic. Yawn.

    • a system that's only good to transmit bits with a guarantee that the recipient will be able to detect if someone else is reading the traffic.

      It's more than that. If the person snooping on the flow of photons "views" the stream, they will completely destroy any information that may be passing through the system. Not only that, but there is no chance of the malicious user guessing the correct viewing angles for the photons, and therefore is completely secure. When quantum computing comes, and it eventua

  • single photons? (Score:2, Interesting)

    by hephro ( 166117 )
    I thought you needed single photon sources for the well-known quantum-cryptography protocols... AFAIK, the "photon splitting attacks" are among the weakest points in current implementations and good single photon sources are a hot research area...

    Can anybody comment on whether this new result applies to generating single photons?

  • Wouldn't quantum computers break it ? (Score:3, Interesting)

    by master_p ( 608214 ) on Tuesday September 09, 2003 @08:23AM (#6908409)
    I am wondering what will happen with security everywhere when quantum computers step into every day life. Classic methods like RSA will be solved in a minute. What about quantum cryptography ? does it stand a chance against quantum computers ? and what will be the effect on society, if nothing can be encrypted any more ?
    • No. The term "quantum cryptography" is grossly misleading. QC doesn't encrypt anything -- it encodes the message in such a way that any eavesdropper will be detected, period. It is impossible to sniff a quantum channel without being detected.

      That doesn't mean you don't need a traditional cryptosystem on top of it. An attacker could compromise the receiving end of the line and read the message without detection. You still need crypto to protect against this.

      Can a quantum computer defeat quantum "cryptogr

  • huh? (Score:3, Funny)

    by cygnus ( 17101 ) on Tuesday September 09, 2003 @08:51AM (#6908604) Homepage
    RSA and Elliptic Curve wouldn't stand a chance against this unbreakable encryption.
    huh? do the different encryption algorithms get together and fight periodically?

    i don't know if you know this, but that's not how encryption works... :)

  • Excellent! I get "Quantum," "Cryptography," and "Nanotube".

    All I need now is "String Theory" and I win!

  • And people will still (Score:3, Funny)

    by BigGar' ( 411008 ) on Tuesday September 09, 2003 @03:21PM (#6913406) Homepage
    tape their passwords to their monitors.

Slashdot Top Deals

Elliptic paraboloids for sale.

Close