Become a fan of Slashdot on Facebook

 


Forgot your password?
Close
typodupeerror
×
Science

Quantum Security 90

Posted by timothy from the entangling-bits dept.
Triode writes "In this months issue of Physics Today there is a very interesting read entitled 'From Quantum Cheating to Quantum Security' which delves into encryption. Talks about ads and disads of popular encryption (keys, public keys, DES etc), the size of current encryption and why it is not (theoretically) good. Quantum computers could make breaking our current methods of encryptoin easy, so we need to start now with methods of encrytption that would not be so easy. A pretty basic example of a implementation of the B92 protocol is given using a single photon source over a 48km optical fiber. Worth a read. Check it out at the AIP website."

This is the best walk-through of quantum encryption I've seen, and one of the few that points out the flaws and unknowns which could plague a completed system in the real world. And depressingly enough, there is a note on the Physics Today main page which reads: "All editorial content from the magazine is available on the Web. In the near future, restrictions will apply." As a selfish site junkie, I hope this only means NYT-style registration, not WSJ-type subscribers-only service.
This discussion has been archived. No new comments can be posted.

Quantum Security More

Quantum Security

Comments Filter:
  • If you would've read the article, you'd understand.

    The problem is not your credit card, it is the government's secrets (they mention nuclear secrets)

    I could have stored the transmission of an encrypted message, and thirty years later it is as important as the day it was transmitted.

    If quantum computers hit the streets, no past encrypted message is safe.

    As a person that dosen't even own a credit card (therefore I cannot make online purchases,) my concern is not with my personal security, but with our national security. But then India & China might blow us up before we finalize quantum decryption.

  • Re:Great education opportunity.... (Score:3)

    by Anonymous Coward on Sunday November 05, 2000 @01:00PM (#647486)
    University of Montreal with Gilles Brassard

    or

    McGill University (also in Montreal) with Claude Crepeau

    Both have fairly well known Theoretical Cryptographs in their CS departments that do research in Quantum Cryptography. However, the Quantum physics part is mainly left up to you; That is: you don't need a College Degree in physics to do Quantum Cryptography (some would say it would help). Quantum Cryptography at its core is still only algorithmics like Classical Cryptography but based on a different set of tools then what you're used to.

    Mr. Brassard just finished writing a book on quantum cryptography; I'm not sure but I believe it's out on the market currently.

    Your second question was to whether or not its more suited to a Math major. Both of these gentleman will tell you that Maths are a big part of any crypto. Having a strong background in math is definitively a plus; in the last few years, doing a double major Math-CS or Math-Physics has been the typical path for people that work with them.

    Your third question was to whether or not there were job openings with such requirements. The answer is: Yes, in academia; More or less in large companies' research labs (i.e. IBM labs, Lucent, MS, NEC, etc.); pretty much No anywhere else (there might be a few expections.

    However, doing grad studies in CS can hardly be considered a waste of time and you should have no problem finding a job after. Whether or not you'll still do Quantum Crypto is another question.

    For what it's worth, they both also work or have worked on other fields of crypto such as Zero-Knowledge proofs (nothing to do with the company that ripped the name from this field of study) and other VERY theoretical aspects of crypto.

    Hope this helps.
  • Where I might be able to find a product that integrates as easily with all my PIM's and email clients like PGP, only utilizes a key larger then 4096 bits? My company does use PGP pretty much all over the place, as we deal with the stockmarket and the SEC requires it for certain things. But Id like to use a larger key, Im talking like 5,228,000,000 bytes or so. Something of that size ought to make it virtually unbreakable even to the Quantum computers. Any ideas folks?

    ----------------------------------
  • It just means a possible end to current security. Maybe this will force us to create a better form of security that we overlooked because the encryption method was so easily the first step.
  • A system can only be cracked if it is economically feasible. A cracker is not going to spend money to crack a system, the more expensive things get, the smaller the chance of a crack occuring.

    For example,
    using a quantum computer, all encription (below a certain level) becomes obsolete. However the cost and knowledge of maintaining a quantum computer, is really very high. An NMR machine, several SUN computers, and three people (a full time technician, a full time PhD chemist and a full tiem PhD engineer/physicist). It's very pricey, I know there is an NMR where I work doing materials research and we are trying to get a quantum computer up and running by Summer 2001.

    At the moment only 5 bits can be used, it's going to be quite a while before a 128 bit computer is produced. So, (for a decade anyway) we are not going to see home quantum computers.

    In fact Quantum computers will be crap at everyday tasks and practically useless to most people, so it's unlikely we'll ever see them on the shelves at K-Mart.
  • Ok, now that I read that I think its time to go back school and figure out what they said. :o)

  • I never did quantum mechanics at university, so I've probably missed something.

    The problem with cryptography based around the physical state of photons is that I don't see how it can work with the existing equipment. This has been pointed out before on Slashdot (not by me)...

    Think about it, you can secure communication between any two points in a network, however that's not the problem. The problem is that you can't trust the routers between you and your destination. You may be able to have secure communications between you and the first router, but what about the rest of them between you and the other end?

    Other problems. How does this interact with standard fiber that is doped to increase the distance? How about optical switches? All of these systems will affect the spin of the photon (either by re-emitting it, or by looking at it), making the whole system report false wiretaps.

    Or am I missing something entirely

    Jason Pollock

  • Re:quantum security and the new elite (Score:1)

    by Anonymous Coward
    No current X86 (or such) system will be able to make an unbreakable cypher anymore.

    Well, a one-time pad is unbreakable even if you have infinite resources, so sure as hell it stays unbreakable with quantum computing. However, one-time pads have severe practical limitations.

    The current encryption methods are in NP: RSA is not even known to be NP-complete. Others are pointed out that the current quantum algorithms only drop the complexity from O(2^n) to O(2^(n/2)) which is still exponential. However, even if a polynomial time quantum algorithm for a NP-complete problem is found, it doesn't spell an end to encryption. You just have to move higher up the complexity hierarchy.

    The complexity class BQP is considered to be the highest "practical" class for quantum computers. It is the class of problems where you can get a correct answer over half the time with a polynomial quantum algorithm. It has been proved that BQP is in PSPACE, the class of the problems that can be solved with classical computers in polynomial space.

    So, you just base the encryption system in, say, an EXPTIME-complete problem, and you should be safe. Of course, constructing an encryption algorithm on top of an EXPTIME problem is not easy, but there are no theoretical reasons why it couldn't be done

  • Re:quantum security and the new elite (Score:3)

    by nihilogos ( 87025 ) on Sunday November 05, 2000 @03:54PM (#647493)
    It isn't as bad as all that. According to the article, a quantum codebreaking machine will have to perform a computation of order O(sqrt(n)), where n is the number of possible keys, in order to solve the problem. Classical brute-force searches are, of course, O(n)

    This is a quantum method of breaking DES encryption. The method for breaking RSA and other schemes based on factoring being difficult offers an improvement from exp(O(n^1/3 (log n)^2/3)) to 0(n^2 log(n) log(log(n)) ) which is gigantic.

    "If computers that you build are quantum,
    Then spies everywhere will all want 'em.
    Out codes will fail,
    And they'll read our email,
    Til we get crypto that's quantum and daunt 'em."
    (Jennifer and Peter Shor)
  • For anyone who wants to know what the EPR "paradox" is, or any other basic information concerning quantum encryption, I suggest you check out the comments to one of the past articles on quantum computing or quantum encryption, such as this one. [slashdot.org]

    Otherwise, we'll have the usual ten people making misinformed comments being responded to by the usual ten karma whores writing the usual ten paragraph responses on "spooky action at a distance" and the Schrodinger Cat paradox.

    Or better yet, pick up a good book on the subject.
  • I'm currently taking Comp.Eng. at the University of Waterloo, with a Physics option. When you take the physics option, you're given a bit of choice as to what you want to specialize in. I happen to be taking all of the quantum courses offered by my university, but, IIRC, you can also take courses on astrophysics, thermodynamics, and a few others.
  • Oops, bad copy-paste! That [demon.co.uk]'s the link I intended; sorry to all others for the misunderstanding. While we're at it, there's also this one [aber.ac.uk]; while Thompson certainly doesn't seem to have "what it takes" (as Trevor Marshall does), her site is also quite interesting.
  • N ist not defined as length of the key, but as number of possible keys for the given key length L (in bits):

    N = 2^L

    If an algorithm requires (worst case) to check all 2^L possible keys it is O(N). If an improved algorithm is O(N^1/2) = O( (2^L)^1/2 ) = O( 2^(L/2) ) it means it is as fast as checking only 2^(L/2) keys, i.e. equivalent to having a reduced key length of L/2.
    And that's exactly what seizer said.

  • Too bad it's not the other way around. I'm doing physics at UW and unfortunately our options are limited. For the most part I've accepted taking almost every physics course offered up to third year and I find that if I want to study the extras (math, cs and engineering concepts) I more or less have to do it on my own time since the faculties seem to look down on letting outsiders into their classes (something that physics doesn't mind, however). It's fairly restrictive. Have you found there to be much of a problem with co-op? The summer school terms are horrible, there is nothing offered. I just figure that if I nail down enough physics then I shouldn't have much of a problem moving into other areas.

    • I think pgp only supports up to 2048 bits keys, 2^2048 seems a bit too much...
    • The 2048 bit encryption is for the asymetric (public/private) keypair. I haven't seen any software supporting more than 512bits for symmetric encryption... (See the sci.crypt faq for more info.)
  • You got me. It's been a long day, doh.

    --Remove SPAM from my address to mail me

  • Re:quantum security and the new elite (Score:3)

    by David Price ( 1200 ) on Sunday November 05, 2000 @12:09PM (#647501)
    It isn't as bad as all that. According to the article, a quantum codebreaking machine will have to perform a computation of order O(sqrt(n)), where n is the number of possible keys, in order to solve the problem. Classical brute-force searches are, of course, O(n).

    The net effect is that a quantum computer in the hands of an eavesdropper halves the effective keylength - a 128-bit key is reduced to 64 bits of effectiveness. 64 bits is, of course, not enough security to defend against government-level surveillance resources, but all that has to be done to solve the problem is to increase the keylength to 256 bits.

    One of the requirements for the AES candidates was that the algorithm support 256-bit operation. Rijndael, the heir apparent to DES, does support 256-bit operation modes.

  • Why can't Eve just let them be, for chrissakes?!?

    I've always argued this point. Seriously, aren't we going a bit overboard. I can understand protecting nuclear secrets and stuff like that, but having infinity-bit encryption so Alice can protect her porn files is just plain silly.

    I think privacy activists walk a fine line between "practical" and "paranoid". Yes, I like encryption. Yes, if it's something I don't want others to read, I click the little "encryption" box in NTFS5 to enable it. But would I really care if they read it? I mean, honestly?

    The only people I think truly need quantum encryption are doctors, lawyers and people working with hazardess materials. Everyone else can do just fine with public keys. (And if you're going to tell me that the government would actually use quantum computers to break into Joe Schmoe's porn files, you have another coming.)

  • Cryptography is essential to our future.

    When you purchase something online, chances are when you enter your credit card number, it will be sent encrypted. When people want privacy of their online sessions, encryption is necessary. In the age of being able to get anyone's phone number across the nations, to send someone a document in under 15 seconds; that is sitting in Europe. Where some child sitting in front of a $400 computer can cause millions in damage; can keep himself anonymous, and out of trouble; increased security in our world is essential.

    We as humanity are losing trustworthiness, which in return makes cryptography an everyday necessity. Humanity is evolving, we are growing more and more controlled by wealth and money, instead of human life. We now need cryptography and we have not scratched the surface of what it will become.

    When we as a culture use money, as we do in today's world; we need a way to keep our numbers secure, to keep our money out of unwelcome hands. Encryption is a need we must have now, and before new technology comes out we need to guarantee the security of current encryption, and we must welcome the changes to it when the need arises.

    Quantum Cryptography will shatter our current methods, so we must develop better methods, today, for tomorrow.

    Now are you ready for it?
  • Professor Clark (of said SRC for Quantum Computing) was saying at a talk here at the University of Queensland and said that when discussing this with Intel they showed him one of their prototype coolers which (a) cools to about 4K and (b) fits inside a coke can.

    And quantum computers, since adding another qubit doubles the number of possible states they can work with, can keep pace with Moore's Law by adding a qubit every year. :P
  • Seattle -- Nov. 4, 2000. The world's richest man today informed the world of a break in to the Microsoft beta server, which uses quantum security as a firewall.

    "Our security has been compromised," said Gates at the hastily called press conference. "Oh, wait, no we haven't. Hold on: yes we have. Damn, these dual quantum states."

    After a tantrum, the Uber-geek stomped away from the podium in a huff and would not return this reporter's calls. Spinal Tap rules.
  • We as humanity are losing trustworthiness, which in return makes cryptography an everyday necessity. Humanity is evolving, we are growing more and more controlled by wealth and money, instead of human life. We now need cryptography and we have not scratched the surface of what it will become.

    Maybe so, but maybe the reason for this "losing of trustworthiness" is due to our increasing reliance on encryption. I believe that our world will become more like a "better for humanity" instead of "better for me and my wealth" within the next 50 years... after of course the American economy collapses because some _smart_ hacker destroys the stock market. Believe it or not, America will be a better place without an money being exchanged as it is now. But this process won't happen until technology relieves many people of work such as flipping burgers at mcdonalds.... When technology can repair itself and live as a "being" then humanity will be ready to explore the universe and sciences instead of yelling and screaming "I want more money."
  • We've discovered that people who read both Slashdot and the WSJ are notorious low-spenders (they have no disposable income anyhow) and in fact many of them are itinerant peddlers who can't even afford an ISP account and are locked most of the time in state hospitals for the totally insane.

    To that end, we're instituting an access-by-subscription plan. You'll still see ads, but we know you won't read them.

    Please remit your payment to:

    Timothy Lord
    c/o his Pappy
    P.O. Box 356
    Jefferson City, TN
    37760

    Thanks!

    timothy
  • Your argument would hold water if it wasn't for the fact that current crypto wasn't basically the same as plaintext when quantum algos are used..

    It's a bit of an arms race you could say. Once the technology can reach everyone, everyone demands better. Soon it'll reach the point where no matter how strong you make your RSA/DES keys, they may as well be ROT13. After that, well, its no longer privacy unless you break out the quantum.
  • Grover's Algorithm is a method for searching an unstructured list, it offers an improvement from O(n) to (O(sqrt n)) over classical computers.

    Shor's algorithm is a quantum algorithm for factoring integers. It is able to do this in O(n^2 log(n) log(log(n)) ) whereas the best classical method for doing so is the number field sieve which takes exp[O(n^1/3 (log n)^2/3] which is pretty impressive.

    Breaking DES encryption involves just brute force looking for the keys so a quantum computer would use grover's algorithm here, but breaking RSA (which is probably what your encryption software uses) reduces to the problem of factoring integers and so Shor's algorithm is what has all the white hats worried.
  • 1st) I doubt you could find one that handles much bigger than 4096. 2nd) 4096 is excellent cryptography for todays computers, that would take decades with todays technology to break. 3rd) It would be immpossible for todays computers to generate a set of keys that large, and even if you did, decoding something and encoding something would take months.
  • I wasnt being serious about the 5MB key, but I want to go above (well the company) 4096 bit key. Hell, that size key takes me maybe 2 seconds to generate the pair, Id feel safer if it took, say, a minute to generate it. *shrug* Just being curious as to how high I can take the encryption really

    ----------------------------------
  • I wish things were that simple. If everyone was trustworthy our society would be better, but there is always a few rotten apples that want to spoil everyone's fun. Have you ever read Aldous Huxley's Brave New World [amazon.com]? In that world they would not have a need for encryption, of any kind, because everyone is programmed, and they would just have to program the idea of "if you see something with the words do not read at the top, do not read it", but we do not program our children, to not read something that should be kept secret. Yes america might be a better place if money was not exchanged as it was now, but would you be willing to give up your computer, your lifestyle, and throw all money in a fire? Our economy has thrived due to money and the ability to trade it for goods and services, we are one of the quickest growing nations in the world, and we turn out more new technology because the way our country was founded, and why our country was founded. For society to change would be a bad thing for a few more centuries, but there will always be a means of exchanging goods and services, and money satisfies this for me.
  • Why the excitement?

    1. Quantum computers can do things more efficiently that the classical computer you have in front of you. One word: economic considerations!

    2. Quantum cryptography is a secure way to distribute random keys.

    3. We don't really understand why quantum information possesses different computational properties. Researchers have some decent intuition about quantum algorithms, but it is such a new field that no one really knows where boundaries between the power of quantum and classical information lies. Of course the goal of science is to understand such questions as "what makes a quantum computer more powerful" and who knows what interesting insights about (1) computation, (2) physics will arise from quantum computation?

    As to your second question: there is a ton of money being spent on building an actual quantum computer and there are more than half a dozen different proposals for such machines. Some examples of these models are using traped ions, neutral atoms in optical lattices, single electron spins on quantum dots, and much more.

    And when you think the press to impact on society ratio is too high just remember good old Lord Kelvin:

    "Heavier-than-air flying machines are impossible." --Lord Kelvin, president, Royal Society, 1895.

    dabacon
  • Would someone please explain something to me. How can you decrypt something if you don't know what the message is?? How do you know when a file is succesfully decrypted?? I know many of the 'break my new RSA Giga-bit encryption and win 1 gazillion dollars' tell you what the first few words are. If you don't know them ... how do you know the file was successfully encrypted??

    And another thing, if I were to encrypt something twice, after the first decryption, wouldn't you get back something and have to decrypt that also??? I would think that if you encrypted a file several thousands times using different mehtods, wouldn't that make it pretty hard to break?? Or maybe I don't have the slightest idea how these things work and need a little education (URL's anyone)??

    Is the question mark overused in this post???
  • Can you use a one time pad to transmit the code book for your next one time pad? If the receiver & I agree (securely) on an initial one time pad (call it pad #1), then within my first message to the receiver I also encrypt a new one time pad (pad #2) for the reply. The receiver then uses pad #1 to decrypt the message, pad #2 to encrypt a reply, and also includes a pad #3 for my reply.

    I realize this would be difficult from an implementation stand point, but I was just wondering if transmission of a new pad is secure within a one time pad.

  • I haven't found many problems at all in terms of taking the physics courses. Of course, there are administrators who co-ordinate the options for engineering students, so if you are having problems, all you have to do is go and talk to them. They're generally fairly helpful in getting everything you want onto your schedule. Of course, this physics option means that I have to take an extra course every term, and I had to challenge for credit in Calc4 (pre-req) because it wouldn't fit in my schedule anywhere.

    Last summer I took Quantum I, along with all of my CompEng courses. I only have one other summer term, in 4A I think, so I don't forsee any more difficulties there.

    What problems are you having getting into the Eng courses? Is it overcrowding, scheduling, or pre-reqs? I know that most of our courses have *way* too many students in them for the number of TA's, labtime etc. Also, most of the courses that I take require a string of pre-reqs that goes back to year one. I can see that being a bit of a problem for someone who wants to take *somewhat* advanced/interesting eng courses, but hasn't been in engineering from the ground up.
  • All current implementations and proposed implementations of quantum cryptography have a major weakness: storage of envrypted data. I started looking into this about ten years ago and although there has been a lot of progress in the development of error correcting codes for short-term storage (quantum computing, etc.), there is no conceivable way that I have seen to store a quantum key or quantum-encrypted information for more than a few hours.

    The problem is that one must maintain phase-coherence between the basis states of the entangled states and the enemy is thermal noise. There is simply no feasible way today to insulate a quantum system from heat baths well enough to maintain phase-coherence for more than a few hours.

    The world's record as far as I know is held by Dave Wineland's ion storage laboratory [nist.gov] at NIST [nist.gov], who maintain trapped laser cooled ions in coherent superposition states for around ten minutes before significant phase decoherence sets in, mostly due to collisions with background gas (See D.J. Wineland et al., "Experimental Issues in Coherent Quantum-State Manipulation of Trapped Atomic Ions [nist.gov]," Journal of Research of the National Institute of Standards and Technology, Vol. 103, pp. 259-328 (1998)).

    Thus, while quantum encryption may be useful for transmitting data where there is not a good way to distribute a secret key, such as a one-time pad, it holds little promise for storing sensitive information.

  • Great education opportunity.... (Score:4)

    by Amnesiak ( 12487 ) on Sunday November 05, 2000 @11:22AM (#647518) Homepage
    ...would be to double major in something like EE or CSE and quantum fizzicks. Has anyone ever done this? Were you successful in getting a job that related to both fields? I know that the two departments at my school (Univ. of Washington) would basically not cooperate to let me do this. Maybe this cryptography application would be better suited to a math major - that might be easier to combine with a physics degree.

  • What a huge wast of effort (Score:4)

    by 91degrees ( 207121 ) on Sunday November 05, 2000 @11:28AM (#647519) Journal
    It seems that half of the world is trying to develop new methods of encryption, wheras the other half is busily trying to break them.

    Wouldn't it save everyone a whole lot of effort if everyone sent everything in clear?
  • Here n refers to the bitlength (128, 256, etc.) and NOT to the integer size (2^128... you get the picutre).

    On the other hand, we always ignore the constants when we use big-O notation (they say it's negligible). If that c is the lifetime of the universe, it's not negligible. I would laugh my ass off if the quantum computer got assembled only to find that it is an impractical method of computation for even simple factoring (6 = 2*3).

  • In related news, IBM said "I think their is a world market for maybe five quantum computers." :)

    I'm just thinking of how people are saying that these won't be on desktops because they aren't as practical as classical computers...that 1943 quote from IBM Chairman Thomas Watson comes to mind.

  • (One more needed)
  • You took Q1 last summer - 2000? If you took it in 99 you were probably in my class ;)

    I think that having the administrators definately helps out. We generally have to go talk to people in other faculties(eng,math) since they are the ones making the decisions. I think the main reason for this is that in science they are desperate for more students while in eng and math they are constantly over-cramming their classes. I know for a fact that most of the electives in physics are made to attract students from other departments - just so we can get more funding based on enrolement. I wonder if it's like this in most comprehensive schools?

    I know that the math faculty definately looks down on letting people into their 'priviledged' classes - most of the cs courses offered to non-mathies are watered down versions of the honours classes and don't really get into the real interesting stuff. I know they offer a CS minor for us but it seems like a complete waste of time as far as I'm concerned - I know lots of people in physics are doing it, but it doesn't go into the real interesting theoretical aspects of computing, just the typical database management/buisness aspects of computing that will let you get an IT job or something like that more easily (kind of like general level high school classes). They used to allow people to do a double math/physics major, but now that's pretty much gone down the tubes, I only know one person who's doing a minor in applied math in our class and it definately has disrupted his schedule.

    As for the summer terms it's pretty sad. We have 2 in a row in physics co-op and last summer I ended up pretty much wasting 2 classes on mundane subjects since I'd allready taken anything else that was relatively interesting. Getting into eng classes is pretty hard - the task of equating pre-requisites is very difficult, but the scheduling problem is the worst. Since they only offer 1 of each core physics class a term we don't have any option of juggling our table around, so often the only engineering courses that would be of use are inaccessible. One of the problems with our physics program is that it is engineered to just push us down the path to getting our BSc - our department is so streamlined now that it doesn't offer too many electives that go into inter-disciplinary topics - probably the only one that I have found interesting is the 3rd year computational physics class (P339), and unfortunately they don't offer anything higher, so I probably won't be taking any computational courses for the rest of my undergraduate degree.

  • Yes, but assymettric encryption does allow that the third party does not have to be present execept at the initial trusted event. This is important for applications that wish to trust someone, but cannot talk to the authority, because they are on a non-networked device, like a DVD player or a Coke machine.
  • Simple as this. If a message can be decrypted, it can be cracked. No one encryption method is perfect. If a person can make it, a person can break it. I personally use a 4096 bit pgp key, but even that isnt unbreakable. More of a thing to stall snoopers then to stop them. People are thinking that they will be invincible if they encrypt their data with a 1024 bit key, just because they see it has more bits then they can count (no im not joking about that). IMHO, the only truely secure place is buried deep in your memory, but encryption will stall your average snooper long enough if applied properly.
  • Anyone ever get sick of this guys "arguement by Einstein". Because, of course, Einstein was always right (do the words "static universe" mean anything to you?) Not that I think that Einstein wasn't a man of amazing genius (I mean both special AND general relativity, come on, you've got to be kidding!), but I'm not such a great worshiper of the "older" Einstein.

    Yes, the world could be made of cheese. But I prefer to think that the many generations of millions of scientists have got closer to the truth when they told me the world isn't made of cheese. (Feynmann probability 99.99999%)

    dabacon

  • quantum security and the new elite (Score:4)

    by lonesome phreak ( 142354 ) on Sunday November 05, 2000 @11:28AM (#647527) Journal

    This reminds me of a conversation I had awhile back with a fellow geek. He thought that new quantum computers would make an entirely new class of 'haves' and 'have nots', based on the ability to encrypt your information

    In a nutshell, once these computers are actually in production, the government will be the first to have them. No current X86 (or such) system will be able to make an unbreakable cypher anymore. No countries, no indivduals, or such. The only people able to make such will be those with these quantum computers, which will most likely be regulated.

    The entire idea behind 'privacy through encyrption' will be a thing of the past. True, most crackers won't have access to this equipment. But the NSA, CIA, etc will, and they will be albe to crack any encryption you can throw at it.

  • Isn't the situation analogous to the problem of using charge leaking tiny capacitors to store bits of data, (aka DRAM)? If so, then the indicated solution is to continously refresh the data before coherence is lost. For security this could be done at a hardware level specifcally designed to be inaccessable to software. Or is the problem this: without a key the quantum state cannot be read and copied even in encrypted form?

    Inquiring minds want to know.
  • The article states that a quantum algorithm has been written that will reduce the number of steps required to break RSA from O(N) to O(N^1/2). (That's from big O of N, to big O of root N).

    So that means it could break a 2^56 bit key in the time that normal algorithms take to break a 2^28 bit key. But what difference does that make? My (admittedly old) copy of PGP quite happily does keylengths up to 2^2048 - so this quantum algorithm would reduce that to 2^1024. This is still a HUGE key. Taking centuries to crack, even on some machine that tries trillions of keys a second.

    Or am I missing something? Let me know :-)

    --Remove SPAM from my address to mail me
  • Yeah, I don't think big O notation works quite like that. My understanding is that big O refers only to the degree of the relationship between sample size (in this case keylength) and time. Going from a situation where it takes x*2^N seconds (where x is an arbitary scaling factor, and N is the length in bits of the key) to one whre it taxes x*N seconds is HUGE! Currently a 1025 bit key would take TWICE as long to factor as a 1024 bit key, with this quantum technique it only takes slightly longer. A 2048 bit key currently would take 2^1024= ~10^300 times as long, using quantum math it would only take twice as long. To put it another way, if a 2-bit key takes one full second to calculate, a 2048 bit key would take just over 15 minutes. Thats obviously a far cry from the microseconds to centuries relationship under traditional methods. Since quantum computers may never be a consumer product, it's safe to say that no mere mortal would be able to make a reasonable secure code using public key anymore.

  • Re:Even so... (Score:1)

    by Anonymous Coward
    You read it wrong. That O(N^.5) algorithm was for finding a particular element from a set of N elements. So it can be used to speed-up decoding any kind of crypto-system. But the RSA-breaking algorithm was mentioned in one paragraph before that (Peter Shor's factoring algorithm) and it's much faster. Basically, that algorithm can decode RSA about as fast as you can encode, therefore rendering the RSA codes practially useless. Like the articles says, the key to this algorithm is the huge parallel computation induced by the super-position of qubit states. Hope that helps clarify.
  • At MIT this is possible -- I did a double major in physics and electrical engineering / computer science. There was not a whole lot of overlap, though a few of the physics classes were accepted by the eecs department and I would've done it in 4 years without killing myself, except that I stuck around an extra year to get a master's in eecs also (yay 5-year master/bachelor programs). In reality, there is a lot of overlap between these fields, it's just not as apparent at the undergrad levels, and in some schools, I wouldn't be surprised if the reasons for not helping with such combinations are largely political. Go academia yeah.

    Now that I'm employed, I'm doing a pretty regular eecs job, but that's because I was kind of burned out on physics. In a year or two, I may see what is available.

    But there really are a lot of overlaps, and not only in quantum computing/error correction/cryptography. Especially as frequencies get higher, linewidths get narrower, etc, understanding the physics gets more important just from a practical engineering point of view. There is a lot of research, eg, in the areas of nonlinear dynamics, where computer science and physics overlap heavily. Thinking about computation as a physical process can be useful, as can thinking about physical processes as computation.

    Anyway, I would strongly recommend combining majors like this, or at least using elective classes to effectively learn what you need as the basis for graduate work or maybe even industry work in these areas. Undergrad programs tend to be heavy on the traditional fields, since a solid grounding is a good idea, but there is a lot of exciting interdisciplinary research going on. Check out the Physics and Media group [mit.edu] at the MIT media lab for some examples and pointers to other research.

  • This kind of reminds me of Legalism, a Chinese School of thought.
    They believed Humans were untruthful and war-like by nature, and shouldn't be trusted (they didn't last long either, they severly beat the whole family of someone if they commited a crime).
  • It's not fair, the good witch wasn't the math major. I guess now I will have to use my public keys only once to send a longer symmetrical key.
  • jeez, have a cup of humour. his post was NOT a troll, it was a case of tongue-in-cheek humour.
  • My physics department (Melbourne University) is running a collaboration which might see a quantum computer on silicon in the next year or so. I believe that the only real difficulty in getting this kind of thing into the innards of a normal computer is the liquid helium cooling system.. Of course, some wouldn't mind having this anyway! The usefulness of a quantum computer is dependant on the number of quantum bits (qubits), and this would probably be a one-qubit proof of principle device at first. Timescale for multiple qubit devices is a few years. (quick quiz: What is the law which gives the doubling time for the number of qubits on a single device?) However, this may not work out, so as usual, grains of salt are required.
  • Why can't Eve just let them be, for chrissakes?!?
    It's kinda the same way that all computer programmers are closet pagans, always saying hello to Mother Gaia.

  • All the talk that quantum physics can help us build ultra secure communication channels solved just half of our problems -- it can only be used for communication, but in practice encryption is used to keep data secure through both space (i.e., secure communication) and time (i.e., secure data storage). All quantum cryptography literatures I have seen seemed to have said nothing about building the ultra secure data storage system. And let's not forget, unless information exchange is always done in real time, they got to be stored somehow, somewhere in the process of communication. Anybody have insights into this one?

  • And if you're going to tell me that the government would actually use quantum computers to break into Joe Schmoe's porn files, you have another coming.

    Pr0n perhaps not, but there's plenty of people who have a legitimate and real need to protect themselves from intelligence gathering from governments, including the US government.

  • I helped develop a small symmetric encryption program that would handle, well lets just say we never found the top of what it would handle. We commonly used it to encrypted small messages back and forth at 16384, we never built it into any PIM's it was only a linux program, we did have a perl GUI interface on it at one time, but the program has fallen to shambles, and freshmeat wouldnt post it.

  • I have a solution (Score:5)

    by ScottMaxwell ( 108831 ) on Sunday November 05, 2000 @07:49PM (#647541) Homepage
    Quantum computers could make breaking our current methods of encryptoin easy, so we need to start now with methods of encrytption that would not be so easy.

    We could start by misspelling everything, thus making our communications harder to understand. Slashdot has employed this encryption method for years.

    --

  • have you read anything aout quantum computers? the description of them given in "The Code Book" makes key length irrelevant. it could check all possible keys in 1 second.
  • Yes we are programmed, but not like they did in the Brave New World. We are programmed by our parents, and our community, not by an organization, or a government.

    In our world some of us are programmed that to succeed we need money, wealth, and everything in our way will not stop us. Some are programmed by the slums, that to get anywhere you have to sell drugs. I was programmed to treat my elders with respect, no matter who they are, no matter what they say, because they have been around a few more years than I. I was also programmed to try my best at everything, to attend college, and to value my privacy, of which our economy needs to succeed as we see and use it today.

    Now anonymous coward, dont let your main idea(ie 1st sentence) be longer than the highest number you can count to, and read more than just conservationist propaganda bullshit.

  • Go and buy a copy of The Code Book by Simon Singh, it should answer most of your questions©

    You'll find it on Amazon

  • incorrect assumption (Score:2)

    by Anonymous Coward
    If we can produce quantum computers that are big enough and fast enough to set them to work cracking crypto, that does not mean that "No current X86 (or such) system will be able to make an unbreakable cypher anymore." Symmetric algorithms (e.g. AES, blowfish, twofish, DES, etc) of 256-bit keys will still be unbreakable.

    Quantum computers are NOT magic. Using Shor's algorithm you only get a sqrt(N) speed-up in cracking keys of symmetric algorithms. That means that 256-bit keys will be as secure against cracking on a QC as 128-bit keys on a classical computer. The article said this, but didn't spell it out clearly.

    Quantum computers do not mean the end of classical cryptography. They may mean the end of asymmetric crypto, but that means that we wind up having to use trusted third party symmetric encryption a la kerberos. This is probably a good idea, anyway, because without a trusted third party there is no way to protect against man-in-the-middle attacks against asymmetric crypto anyway.

  • First of all, I'm not giving an "argument by Einstein" (chuckle). I'm not an Einstein-worshipper either, but I'm just wondering: what if the old fella was right where QM is concerned? Trevor Marshall and others certainly seem to think so [demon.co.uk]. And if you dismiss these people's point straight away, merely because so many scientific geniuses of the 20th century developed QM, then you're the one who's pulling an "argument by Feynman" (or by Heisenberg, or by Pauli)...

    Frankly, I never liked the Copenhagen Interpretation at all (it certainly justifies the name "quantum magic", and gives the entire scientific enterprise a bad name), and maybe all of QM is based upon a faulty foundation. Yes, it'd be a monumental error, but if there's ever been a community that could make it, it's today's physics community. (I've seen it from the inside; if you have too, you know what I'm talking about. The mutual reinforcing of dogma; the unwillingness to test, experiment, reformulate, or do anything that even smacks of real science; the lack of intellectual honesty; the cargo-cult science; the mental laziness; the rigid structure of academia which requires one to conform to the dogma to get respected, or even to be acknowledged at all; the general subscription to Bohr & co.'s distorted (not to mention depressing and counterproductive) idea of what science is... Feynman is certainly rolling on his grave - as is Einstein.)

  • There has been a lot of talk about quantum crypto forcing us to replace pgp with secure one-time-pad key distribution.

    However, there's a whole other side to the "potential consequences of quantum computing" thing, which I haven't seen much discussion about. What interests me more than the possibility of perfect one-time-pad distributions is the IMPOSSIBILITY of quantum bit-commitment, which to me seems to rule out anonymous digital cash. This, of course, would rule out a host of other slashdottish schemes, such as Assasination Politics... and the cypherpunk mainstay that the breakdown of the modern nation state will be hastened by secure untraceable digital cash depriving tax collectors of the information they need to collect transaction (i.e. income and sales) tax. (I posted a comment late into the last quantum-crypto discussion, but the thread wasn't picked up.)

    In fact, if we ever somehow got a nanotech society with "quantum crypto for the masses" it seems to me that the only way to continue capitalism as we know it would be for every transaction to clear through some kind of centralized database. Perfect privacy for personal communications, but for economic transactions no privacy whatsoever.

    For SDers unsure of what this bit commitment thing is, I'll try to explain. Personally, I found the concept somewhat difficult, but I think I get it now. (Incidentally I've worked my way through many of Hoi Kwong Lo's technical abstracts in the hard core physics press, as well as the current article... this despite a liberal artsy educational background. :) )

    OK, so here's my little intro.

    Secure digital cash schemes all are basically glorified digital signature protocols. When the U.S. government churns out a dollar, it signs it. If it was a Panamanian private bank churning out an anonymous e-dollar it would sign it as well. Only it would sign it in such a way that the legitimacy would be transferrable EXACTLY ONCE. This would prevent double spending. That's how anonymous digital cash works, in theory. (There are no working anonymous digital cash schemes right now, probably because nation states fear the cypherpunks might be right about the dilution of tax revenues). For details see http://www.aci.net/kalliste or search for +"stephan brands" +"digital cash" or +"david chaum" +"digital cash"

    To put it in a nutshell, signatures are a form of bit commitment. In other words, in bit commitment, you don't scramble the data, but stamp it in such a way that's verifiable by outsiders, but only producible if you possess an encryption key. Internet ID verification protocols are also bit commitment situations; and like the last paragraph says, so is e-money.

    The interesting thing about using crypto for ID verification rather than scrambling your data is that... with quantum crypto, there is no way to do it!

    OK, I just realized that any further explanation as to why is beyond my capabilities. But it's pretty much laid out in the article, though Hoi Kwowng Lo doesn't mention digital cash specifically if I remember correctly.

    Thoughts?

  • Why the hard-on for this ethereal vaporware which we call "quantum computing"? Is there even enough of a model available to implement "quantum computing" in any sort of traditional way, or is this entirely a religious belief?

    -Nev
  • You can always use the one-time pad algorithm to encrypt any given plaintext, in which case, even with quantum-computing, you couldn't break it because you won't know the difference between what is the right or wrong plaintext once you've deciphered it into whatever looks "logical" to you. When you use this method however, you'll have to worry about distribution of the key, which I believe is a lot less to worry about than encrypting your message with Blowfish and having the government break it with their e.g. 32 bit quantum computer ;-), right?

    --

  • Routers ??? For God's sake the technology doesn't exist yet! Any speculation as to how quantum technology will interact with existing ones is probably irrelevent. The techs are just completely different. We will probably first see QC in the same sort of tasks as we first saw mainframes ... big data crunching machines. Their application in crypto will at first be useful only in physically securing data (host data encryption) not in key exchanges (..its certainly debatable but ... there's no such thing as secure key exchange through an untrusted line)and not in secure transmission. As another thought keep in mind that your government is approximately 10 years ahead of academia in crypto research ...
  • Stop wasting precious bandwidth (and making me waste it which is worse) dont get down on people for their spelling. We're NOT professionals here ... we're geeks, and geeks often type things quickly, get the message across, then move on. Just chill and remember Shakespeare couldn't spell "spurious" if his life depended on it.
  • how long until quantum computers become usable? the whole point of cryptology is to make something unreadable for a certain period of time. Who cares if Joe Blob of the NSA can decrypt me credit card number 10 years after I bought a book online from amazon.com?

    Is there any reason why a person like me, who only uses encryption to securely purchase something online, should care about this?
    -theman2

  • You are wrong. The N here is the 2^56, not the 56. (2^56)^(1/2)==2^(56*(1/2))==2^28.
  • obviously.....i mean, why else was the first protocol (Charles Bennett and Gilles Brassard's "BB84") for quantum key distribution created in 1984!!! :0)

  • I have a feeling that the physics needed to just go out and make your own nuclear bomb has got to be easier than that needed to make a quantum decryptor and then decode nuclear secrets. Especially when you can just photocopy the Feburary 1979 issue of the Progressive [bc.edu] for a pretty good head start.
  • The first classical computers were government projects, available only to government institutions. One of the first such machines was Britain's Collossus, which was exclusively capable of cracking codes. Even today, I'd bet that the NSA/CIA/etc have better code breaking machines than most of us do... maybe even beowulf clusters of them...

    As long as there is wide research to develop these machines, they will eventually become publicly available. There may be a lag before the price drops to the point where you can have PQCs (personal quantum computers), just as it took a third of a century to go from ENIACesque systems to affordable home machines. But there are enough huge corporations that would like to protect their secrets that I bet the developments will take place in the public sector.

    Of course, be on the lookout for anti-QC laws to prevent this. After all, unless you're a criminal distributing kiddie porn photos and terrorist information, you wouldn't mind Big Brother reading your private communications, would you?

  • Ok, you are troll: open source, meth-labs, and Microsoft all in one short post.

    It doesn't matter how many people "abuse" encryption, anymore than it matters how many people "abuse" free speech. We (in the USA) have a right to anonymous speech, and the right to free association. We don't need to register what we say with the government. We don't need to register lists of people with whom we associate. If you don't like this, change the constitution.

  • This is not a troll,.....

    Nice try troll boy. I hope no one is stupid enough to bite this one.
  • Sum things sint in plane tekst arnt readibble, evin withuot incripshun. Yer artikkel for exampil.
  • ... we ever have to pay for information on the web.

    As a selfish site junkie, I hope this only means NYT-style registration, not WSJ-type subscribers-only service.

    The Wall Street Journal has to generate revenue somehow.

  • There are two major reasons we should be motivated to research Quantum Crypto:

    Quantum Computing, when feasible, will instantly make today's encryption techniques useless yatta, yatta, yatta...

    If/when some crazy math guy proves P=NP, our encryption will be useless. Only QC will provide security from non-deterministic machines.

    Either way, only one of these breakthroughs is the only thing needed to turn the country's deepest darkest ciphertext into plain old plaintext. I realize that most mathematicians are confident that P!=NP (I myself think this problem is probably in Goedel's indecidable domain), still I have to admit that all this makes me a little nervous.

  • I just bought a drum of 50km of fiber optic and this evening i'll blow my tv's tube to get a photon source. The rig [physicstoday.org] seems easy to set up for any decent overclocker d00d.
    I will start a souceforge page for the project and if enough developers join soon we'll have: "ssh -c B92" and "ssh -c BB84" :)
    --
  • It is undeniably true that no form of machine encryption is truly unbreakable, I don't think that anyone can argue that. Even one-time pads can be at least partially broken if a poor (i.e., predictable) random-number generator creates the pads. In fact, one-time pads merely shift the burden of security even further onto the key-holders, and it can be a lot harder to hold onto your pads in the real world than to remember a password in your head. The government (or whoever) can subpoena your pads, but they can't pluck passwords out of your brain.

    However, encryption doesn't ever have to be perfect, it only has to be good enough. That is, the algorithm only needs to be able to protect the information encrypted beyond the span of its relevance/usefulness. Don't forget that 129 bit encryption is an order of magnitude harder to break than 128. 4096 bits should keep even the most paranoid slashdotters happy well into the next century.

    Of course, if you're truly paranoid, you wouldn't just encrypt. You'd use some form of steganographic file-system to hide the fact that you even have encrypted data to begin with. Don't forget that someone who wants to read your data doesn't have to crack your codes. You could be required by law to reveal your keys. Britain's new Regulation of Investigatory Powers (RIP) bill now makes it a prisonable offence to withold decryption keys from a legal authority (even worse, it's up to you to prove that you never had them! Guilty until proven innocent).

    The bottom line is that no security of any kind is perfect, you only need it to be good enough(tm) to outlast the purpose to which you put it. It might also help your case if it's hard to prove you're securing it in the first place.

    Matt

  • and as we all know - the NSA can get into DES anyday they want to anyway.
  • Two problems I can see right away with this kind of encryption.

    As one person already pointed out, the actual encryption used here is a one time pad - which naturally needs to be kept secret and secure and known only to the correct two people for the scheme to work. The safe transmission of this key is what is being addressed in this article, not the creation of a new encryption scheme. Naturally this only ensures safe transmission from one point to another, but security of either end still remains an issue.

    The second problem I see is this - this is a good point to point transmission scheme, but it says nothing for the kind of transmission that would occur over the internet for example. I would like to know more about the system they described that could be set up to reliably transmit such keys over a LAN or WAN, but from what I can tell from the principle of the thing this isn't really practical.

    If the passive presence of Eve, the eavesdropper is sufficient to alter the quantum states of the particles enough that the snooping would be detectable, then certainly the actions of any network switch or router would completely destroy this carefully balanced sequence of quantum states. Unless of course, one was to install routers at every point along the network that would allow the correct checking and validation of these codes - but of course that opens up the issue of tampering and monitoring at each of these hops between bob and alice.

    And if you consider the kind of security that is very easily implemented when you have the resources for a secure dedicated line directly from point a to point b, then I must question, what additional security does this really give the users? Even within the largest governments, setting up dedicated lines such as this is so costly and high in maintenance that it can only be practically used for the most important transmissions.

    so, yes its a nice idea - but I question its valid uses. the best systems seem to be those that transmit directly through the air - ground to satellite etc. but of course you've got to have line of sight from point a to point b - ordinary people could never use this practically - you could try bouncing signals off satellites, but again you have the insecurity of the satellite itself - you'd have to trust those who build and maintain the satellite that it would accurately report to both end points its own internal validations without doing any snooping or tampering of its own, the satellite is essentially just a router in space.

    If anyone knows where I'm going wrong with this logic, please let me know, but it doesn't seem to me that this is a very practical form of encryption for anybody but the most powerful of institutions, and even then only for their most important of operations.
  • The law that gives the doubling time for the number of qubits on a single device is know as Qbert's law. It is based upon the quantum chances of Qbert making it to all the squares on the board and successfully avoiding all the nasty snakes and bad guys without leaping off the edge.
    =P
  • Ok,
    On the multiverse theory they say that one universe is spawn for each possible state of each particle, and by that we can design a computer that does parallel processing in the diverse universes...

    ... Now, what puzzles me is what makes them sure that the right answer comes out at Our universe?
    And how do you add the solutions from different universes?

    This is creepy!
  • The problem with quantum computers is that they do everything in parallel, so if you increase the key rate, they just have to increase the number of particles...
    In the end the answer should come almost instantly

  • The link doesn't seem to reflect to the information, you were hoping for. This [demon.co.uk] does.

    Totally off-topic, but certainly interesting stuff ...

  • There's gotta be a way... (Score:3)

    by KernelBloat ( 229770 ) on Sunday November 05, 2000 @11:46AM (#647570)
    Current encryption is strong, but not infallible. Because of quantum mechanics, you would be able to write perfect public/private key crypto that is not interceptable. To the best of my understanding, quantum crypto has to do with sending photons with specific polarities across a pipe. It works because anybody who wants the information (photon) would have to bother the photon to get it's polarity. So getting the information messes the information and invalidates it(it would be coupled with message integrity checks and public/private key crypto)
  • A maths degree would definitely be the way to go. The basic algorithms you'd need probably wouldn't require a full CS course, and the maths would easily stand you in good stead to make learning the quantum mechanics you need easy, and you might even find it on the course as part of applied maths or something.

  • Re:Security is only as good as its inventor (Score:3)

    by DoubleEdd ( 178052 ) on Sunday November 05, 2000 @11:51AM (#647572)
    This isn't true in this case. We're talking about the transmission of One-Time Pads here, and they are unbreakable. The problem is keeping the pads secure, as although the keys can't be guessed in this case, they can still be stolen after the transmission.

    As the linked article points out, the quantum methods mean you can guarantee the transmission is secure, but not a lot else. These cryptographic methods have all the security of other methods and then some. The only weakness (and I really mean only) is that the keys are still subject to theft if you aren't very careful.

  • Re:What a huge wast of effort (Score:1)

    by Anonymous Coward
    A very insightful observation. But it's analogous to basically all human struggles, so asking for everyone to send everything 'in the clear' is implausible.

    It seems like a waste of effort (and lives) that East Timor would be invaded by a hostile government and resisted by the people, wouldn't it be easier not to fight? Yes, certainly, but when someone threatens your freedom, you apply effort to ensure it, and usually the aggressor pushes back. This is essentially the nature of struggle.

    There is of course the argument that without struggle, there isn't really anything worth doing. An analogous view would be that if everything we would have to say were sent in clear text, we would lose out on the most important of information.

    It's interesting to see the parallel among the various denizens of slashdot on the one hand promoting use of encryption for individuals and on the other deploring its use by corporations. The arguments are similar in structure and meaning to philosophical arguments about use-of-force. Encryption is necessary to protect oneself, but information should be free.

    We are caught in this apparent contradiction in the same way that revolutionaries are caught in apparent contradiction when they use violence against their oppressors in reaction to violence. Of course, there is really no contradiction at all, the key is making a distinction between the action and reaction. Violent action against people can be justifiably fought with violence. And use of encryption/invasive information gathering can be used in reaction to parties which use these against us.

  • This is crazy (Score:3)

    by Kaufmann ( 16976 ) <rnedal&olimpo,com,br> on Sunday November 05, 2000 @11:53AM (#647574) Homepage
    Ever since I've been studying cryptography, poor Alice has been trying to talk to Bob without having that bitch Eve eavesdrop. Why can't Eve just let them be, for chrissakes?!? Then, as a side benefit, distributed.net would be able to redirect their efforts to something rather more worthwhile, such as looking for imaginary little green men [setiathome.org].

    On a side note, ever consider the possibility that Einstein was right all along and quantum magic really is bogus [phys.rug.nl]? If the linked-to people, currently disregarded by the scientific community as crackpots and throwbacks, end up proven right, that would be damned funny... "Hello? Yes, this is Mr Scientist Man, who is calling? Ah, the NSF? Yes, I know you've been giving us research grant money for the last 50 years to build huge particle accelerators and develop O(1) code-breaking for the NSA... you want to know why our prototype won't work? Well, it turns out that spooky action-at-a-distance is a measurement error, the Bell inequalities were never violated, and the universe is really fundamentally deterministic... sorry about that. See your money back? Not unless the NSF operates in the Bahamas too..."

    It's like they say, nobody ever got fired for believing in Einstein...

    One last thing... timothy, learn to close your italics.

Slashdot Top Deals

"God is a comedian playing to an audience too afraid to laugh." - Voltaire

Close