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

 



Forgot your password?
typodupeerror
Encryption Security

Quantum Encryption Explained 126

angelos writes "New Scientist Magazine has an article discussing the theories of Quantum Encryption. Short and not too complicated an article, but makes for some interesting reading. " Very cool overview of the subject - takes a look at the potential future of encryption and why the curent system of encryption will not last.
This discussion has been archived. No new comments can be posted.

Quantum Encryption Explained

Comments Filter:
  • by dmaxwell ( 43234 ) on Friday October 01, 1999 @07:25AM (#1645221)
    It is probably true that random numbers cannot be generated by purely digital means as we have to use less than perfect methods to generate seeds. ANALOG electronics are another matter altogether. A truely random number can be built very inexpensively. A forward biased zener diode will produce white noise. White noise so produced is the result of electrons being forced the "wrong" way over a rather strangely doped p/n junction. I can think of no mathematical way to make this a deterministic system. This white noise should be immediately amplified so we can filter it and apply it to an A/D converter. We then use a spectrum analyzer to find out over what range(s) the noise produced is "flat". This is important because the noise produced may have higher or lower average amplitudes in spots. We then use a steep midpass filter to pass an appropriately large and flat part of the diodes output spectrum. This selectively filtered portion of the noise is then passed to a high quality A/D converter. Lo and behold, we now have a truely random number generator.
  • "To compensate for jitter, a pulse of light is sent 100 nanoseconds ahead of each photon."

    Uh, what exactly is the difference between "pulse of light" and "photon"? Just the amount of photons?
  • No, quantum bits can be any probabilistic combination of 0 and 1. You could have a qubit which was 50% 0 and 50% 1, or 90% 0 and 10% 1, or any other such combination. There's an infinite number of possible qubit values.
  • I thought it was pretty much a given that quantum computing devices would make factorization of primes a linear rather than an exponential problem, meaning that encryption based on primes will be obselete as soon as all the problems with Quantum Computing can be worked out.
  • I'd mug you coming out of your house, duct tape over your mouth, into the back of the black van, somewhere quiet where I could cut one of your fingers off every few minutes until you gave me the message.

    Holy man in the middle attacks, Batman...

  • What if Eve uses a polarizing filter that is not 45 degrees off the signal? What if she uses one that is at zero degrees? Then the photons will either pass through or be denied. Since she will never have a photon with a 50-50 chance of getting through, she will know *all* of the incomming polarizations and can simply retransmit that to Bob.

    I must be missing something here.
  • Isn't it Key Exchange not Crypto? Anyway, what would you do if a plane flew in the way of the photonstream? Assume Eve listened?

    Just my 2c

    - Ben Stewart
    NeuralAbyss Software
    http://get.to/neuralabyss.software
    - NeuralAbyss

    ~^~~~^~~~^~~~^~~~^~~~~^^^~~~~~~~~~~~~~~~
    Real programmers don't comment their code.

  • So how exactly does polarization get preserved in fiber optics? I never took any optics, but it seems to me like it'd get repolarized every time it hit a wall of the fiber.. What am I doing wrong?

    Also, how does it get retransmitted from the satellite? Or does it just get bounced? If the latter, again how does polarization get preserved? Don't mirrors also repolarize?

    I'm confused.
  • Erm. He did -- you didnt. Also, at least he was polite enough not to swear at the previous poster.
    Yes, it requires either much better algorithms, or possibly quantum computers to crack todays ciphers, but the article had nothing to do with quantium computing -- or breaking ANY form encryption at all.
    The article is about quantum encryption, which I have to say I find fascinating, even if daunting -- transmitting a single photon across 300km, without altering the polarisation.... wow.
    --
    David Taylor
    davidt-sd@xfiles.nildram.spam.co.uk
    [To e-mail me: s/\.spam//]
  • by Anonymous Coward
    I just love the way academica thinks -- these systems that are devised are 'perfect' for one reason or another, but then when faced with the real world fall flat on their faces. The schemes as described in the article are very careful to consider what an evesedropper could do, and then all the complecated steps that the system uses to detect wether or not the key has been compromised. By itself, that's fine - but they failed to realise that, for some purposes, denying two parties the abillity to communicate also could have value of it's own. For example, if the army used such a system for top secret communications, then it would be a tremendous battlefield advantage for the opposing army to disrupt these communications. Perhaps by flooding all these satalites with continous streams of photons. They don't have to break any code at all, simply forcing the key negotiation phase to fail is all that's needed for a win.

  • Whoahg! Light dawns opn marble head!
    I understand dit now!
    YEAH!
    COOL!
    I LOIKE IT!

    ok, check 9ut the table bwelow
    first columnis the angle of the filter Aloce (foxxy chick thst she is) uses to transmit her hard core pr0n to Bobby.

    2nd colum is the filter bobby uses the REceivne the photon. the result comlung is the result - yes means he gets it, no means it's clobked and maybe merans its in a quantum stat like Shcrindongers pussy, baybeeeee...


    Trans Rec Result
    ----- --- ------
    0 0 yes
    +45 0 maybe

    0 +45 maybe
    +45 +45 yes

    0 90 no
    +45 90 maybe

    0 -45 maybe
    +45 -45 no



    so i;m wrpng about the noninvqsive maninthemiddle attak, but not about the full mitm attack1

    Coming soon to a website mear ytou: WHEN MEN I~N THE ~MIDDLE ATTACK!~!

    Wow.. its amazxingwhat this amoumt of alcogol can fdo for one's emtna;l faculties.

    I stillthink it sucks, thiough..

    D. is for superca;lifrajizsmbegeckspiladiocious.
  • yep. you got it. However, one time pad design finally became public key crypto since one time pads were so inconvenient. i've no doubt a form of quantum encryption will be found similar to that of public key crypto...this is just the beginning of quantum encryption. In order to understand recursion one must understand recursion.
  • The article sez:

    In fact, background photons, detector noise and misalignment introduced an error rate of 1.6 per cent, but this isn't too serious. If Eve had been listening in, she would have caused an error rate more like 25 per cent, so Alice and Bob can still be confident that their key is secure.

    Okay, let's say Alice and Bob are sure that Eve has not interfered. Nonetheless, Alice and Bob disagree about 16 out of every 1000 bits in "their key", right? Doesn't that seem like a bit of a problem? They could try to use some sort of redundancy check in their communication, but it still seems entirely possible that Bob will be unable to decrypt a message from Alice with certainty.

    I'm no expert on this stuff. Am I missing something?

    -- Brian

  • Your question is answered in the article:

    "Bennett and Brassard proposed using photons polarised in different directions to represent 1 or 0. If Eve tried to intercept the key, she would have to measure the photons, which would effectively mean absorbing them. To avoid being spotted, Eve would have to retransmit the photon to Bob. However, because of the strange way that quantum particles work, Eve does not always measure the same polarisation that Alice sent. That in turn means that she cannot be sure that she is retransmitting the correct orientation. Thus Eve's interception will inevitably affect the transmission of the key, and Alice and Bob should be able to spot this, discard the key, and try again with a new one."
  • Please read the article. To measure the polarity of photons, Eve needs to use a filter (I believe any direct measurement falls under Heisenberg's uncertainty principle). The key point is that when a photon is blocked by Eve's filter, she doesn't know the polarization of the photon. This is because one of the filters has a 50-50 chance of blocking a photon. This randomness is the at the center of quantum mechanics and this approach. By transmitting enough photons, the chances that Eve can correctly reproduce her intercepted photons are reduced to statistical nothingness. Her incorrect reproductions are detected when the key is verified over an insecure channel, in which case Alice and Bob start over again (or call the cops). Thus, the key exchange is secure.
  • No. In space, there is no "up" or "down", so no part of the satellite is the back...

    (Score: -1, Unfunny)

    --
  • This encryption scheme sounds pretty good for direct connections, but it is totally useless for Internet communication. The whole idea behind IP is that packets are transmitted, received, and retransmitted from host to host until they reach their destination (hopefully). The problem is that this type of quantum encryption only works if the actual photons that were emitted by the sender are detected by the recipient.

    Of course, if every pair of hosts create a one-time pad in this manner for each IP packet that they exchange, it could work, but that would really suck up bandwidth since you need one bit of key for every bit of data. I suppose we could string fiber between all possible pairs of computers on the planet, or maybe just broadcast neutrinos directly. Not this month, though.

    Let's not quit working on mathematical encryption algorithms just yet.
  • The point is there is already an algorithm for a quantum computer that can factor numbers in O(n^3). The problem is it requires 3n quantum bits to use. So, to factor a 512 bit key you would need ~1500 quantum bits. This is a long ways off (largest computation has been done with 5 bits I believe), but there is no way to tell how far off it is. Most researchers in the field believe it is possible.

    On the other hand, quantum key distribution, is provably information secure. No amount of computation renders it insecure.

    By the way, this is mostly pure research, but there is a group at los alamos that have done quantum key distribution through 50 km of fiber, and 1/2 km of air, both with very small error rates (important for the security proof).
  • "Your question is answered in the article:"

    No, I don't think the quoted piece of the article covers authenticating Bob (or Alice). It deals with the quantum improbability of both intercepting and accurately duplicating the key. If Bob and Alice have a reliable communications channel they can detect Eve intercepting the key with a reliability proportional to the key length. But the protocol seems to be incomplete here -- they do not describe the channel that guarantees that Alice is talking to Bob or that they can detect an imposter. How does Alice authenticate Bob and vice versa? Why is this protocol not vulnerable to a man-in-the-middle attack?

    Yes, I understand that Eve can't both intercept the key and derive the values of each bit. That prevents Eve from simply intercepting and retransmitting the key undetected.

    My question was how does Alice know she is talking to Bob and not Eve if Eve intercepts the key and pretends to be Bob to Alice and pretends to be Alice to Bob? The article assumes that Alice and Bob have a reliable method to communicate and can know they are talking to each other (the phone call). What is that method? It would seem to be a critical piece of the whole protocol. The article doesn't cover a cryptographically secure method of authentication -- and it wouldn't be fair to use current methods, since the justification for quantum cryptography is presented as current methods being crackable. ;)
  • I don't see what the fuss is about taking this far enough to be able to establish a link to a satellite. You want end-to-end security, not end-to-satellite and satellite-to-end!

    Suppose Alice and Bob want to generate a shared key, and Alice is in NY, and Bob is in CA, and the satellite is over the US. Alice and the satellite generate a key A, and Bob and the satellite generate a key B. The satellite then sends Bob (A XOR B), which Bob uses to compute A. Assuming Bob and Alice can trust the satellite, they can communicate securely with key A.

    This technique is also useful for securely rekeying a satellite (e.g. changing the key HBO uses to encrypt their transmissions every month).

    I got this info from a presentation given by one of the guys from LANL a couple days ago...

  • One definitely does need a secure authentication scheme for quantum key exchange to work.

    Fortunately, secure authentication schemes exist even without quantum mechanics. For example, suppose you and I each already have a 20 bit key. I just ask you what it is and if you can tell me I know it was you. Obviously this is secure (up to a one in a million chance). Of course, there are two unavoidable problems with this. One, you may have handed over your key to someone else at gunpoint. Two, we'd better not use that same key again because Eve could have listened to it.

    Problem one cannot be solved. Problem two is solved by not reusing the key, but instead using new key that we exchange using the quantum key distribution. This makes denial of service attacks particulary annoying, since if we have to wait and try again later we'd better authenticate again using a new key and we might run out before we get to use quantum key exchange to make some more. Doh!

    The real situation is more complicated than this because I don't need to juse verify that I am talking to you at the start of the conversation, but rather must authenticate each bit of our conversation, without using up more key than we can get back by the quantum key distribution. This is also possible with a little more complexity.

  • Well, you need the secure channel to be sure that the intended recipient was indeed the person that recieved the transmission on the insecure channel. In this instance, the secure channel isn't a secure channel in the sense of sending communications, but secure in the sense that you are able to dicern who recieved the transmission. A phone call will do, so long as these aren't bank transfers or nuclear launch codes, and you can feel sure about the voice on the other end of the line.

    Or the secure channel can be simply the string of dedicated fiber optic cabling running from one building to the next, and therefore you assume that you trust who ever is on the other end of that line.

    I'm just saying you need a trust mechanism. PGP helps to provide that infrastructure. This does not, so far as I saw.
  • This is not saying that John Q Public would never have a computer. This is quantum physics here.

    It's simply impossible to send protons positioned as such through a switch or router (or twenty a la the internet) and be assured that they arrive at the other end in the same position that they were in when they left.

    If you string together two locations with dedicated lines, that's one thing, but John Q. Public CAN NOT benefit from this in the slightest way shape or form, in regards to e-commerce or other internet based transactions. Unless every vendor or potential vendor strings their own cable to their home, it's just not happening.
  • Hey, that's not fair! We academics know there is a denial of service attack and that it's a problem. At least some of us do. There are situations where it isn't that bad though. If a company is communicating with a branch office through a fiber and the denial of service happens, you just send the police out to see who dug up your fiber. Problem solved.
  • If you had bothered to read the article, you would have noticed that the work described is being done by the government. Last I checked, Los Alamos National Lab was still a government-run lab...
  • Well, you aren't the first to bring this up. In his paper "Quantum Cryptography: Public Key Distribution And Coin Tossing", Bennett himself acknowledges that one of the requirements is that the two parties have access to a medium that requires no active eavesdropping, such as a phone call. In this situation, the man in the middle would be quickly realized.
  • I've already responded to this type of post, but I believe that it was too far in a thread to be noticed.

    First, Bennett requires that Alice and Bob have access to a medium that cannot be actively (man-in-the-middle) monitored, such as a phone call. Any eavesdropping of a quantum channel is, thanks to Heisenberg, active. But with a passive-eavesdropping-only public channel, Alice and Bob can tell each other which photons were received and which weren't. Thus, if Eve becomes the "man" in the middle, she changes the polarisations of all of the photons she sends out according to that Heisenberg fellow.

    Secondly, Alice and Bob base the security of their system on error rates of photon transfers. They would notice an unusually high error rate, and avoid further communications from that line. And because all they did was send random one-time-pad information, Eve has gained absolutely nothing of use from all of her work.

    Quantum cryptography essentially provides effective key distribution for two people who have a passive-eavesdropping-only communications medium, so all the arguments about a man in the middle become moot.
  • > All Eve has to do is read the polarity of the
    > photons (i.e. pretend to be Bob), and then send > photons of the same polarity on to Bob

    Here's where quantum mechanics enters the game.
    There are two different kinds of polarization:
    • right or left circular
    • horizontal or vertical linear

    Now eve doesn't know whether the photon has
    been prepared the first or the second way. She
    has to measure one of both and then she replays what she got - fivty percent chance is that she
    measured linear polarization while she should
    have measured circular polarization or the other
    way round.

    After Alice and Bob have been quantum chatting
    for some time, Alice will reveal for some arbitrary photons the type of polarization she used and using this information Bob can detect Eve.

    So much about the good news, here's the bad news;
    • If Eve intercepts and manipulates said polarization type information, the
      scheme is broken: Eve will simply retransmit the
      polarization types she has transmitted instead of Alice's type of polarization.
    • if the photon source emits two instead of
      one photon, Eve could steal the second one,
      let the first pass and noone would realize.
    • An optical fiber like those
      in use today will carry the photons for
      approximately 10km and has amplifieres built
      in in order to carry the signals for longer distances. You need some kind of quantum
      repeater which will reshape your quantum signal.
      This is a current research topic. I'm not sure
      about security concerns regarding these quantum repeaters.
    • People have to distinguish between errors
      that Eve introduced and errors due to noise that happen even in the absence of Eve.
  • First of all, I need to clarify that my post was mostly in response to "Needed Soon, Quantum DEcryption may be here NOW!" by Cy Guy. I apologize for not posting it there.

    Secondly, in response to your post: would anyone have believed me if I had said in the mid 60s that the US government has an aircraft that easily travels at mach 3? Of course not, no one would have. The SR-71 wasn't declassified until the early 90s. It still holds records 35 years after it was built.

    My post wasn't intended to prove that such advanced technology as I claimed exists for certain, but rather point out that it is incredibly likely.

    -----
  • These calculations have been done, and the result is that the best achievable resolution is on the order of 10 centimeters. Enough to read tail numbers on airplanes, not enough to read license plates or newspapers.

    Not so fast.

    Astronomers have found a way to overcome the atmosphere's turbulence: adaptive optics. If I recall correctly, they shine a laser upwards to create an artificial star, and then by monitoring the twinkling of the artificial star, the telescope mirror is dynamically distorted hundreds of times per second to compensate.

    Such a mirror is now in place at Mauna Kea... the resolution rivals Hubble's, at a fraction of the cost. See Gemini North Sees the Light [skypub.com] (scroll down to "Friday, June 25"), or the media fact sheet from the Gemini Project [gemini.edu].

    See also this picture of Pluto and Charon [astronomynow.com].

    Now, the question is: can adaptive optics be used in the other direction, to observe the ground from space?

    Did astronomers actually invent adaptive optics, or is it just another Cold War technology spinoff? Makes you go Hmmmmm.....

  • The Times of London had a s tory [sunday-times.co.uk] Wednesday indicating an Isreali team has a hendheld quantum device that can crack 512-bit RSA keys in 12 MICROseconds.
  • No, Bob does QUOTE the bits he received to Alice... he says "I received bit #5, bit #17, bit #42," etc.) This doesn't give Eve any useful information, because she'd have to know what those bit values are, and if she knew that, Bob wouldn't have received them.

    --synaptik
  • Er, that should hav read, "Bob doesn't quote", not "Bob does quote". Damn fingers, did it to me again. :(

    --synaptik

  • Couldn't a man-in-the-middle attack theoretically be launched on this type of encryption?

    Obviously, the practicality of intercepting the photons between the ground station and sattelite are isn't the best (visions of NSA blimps), but, in theory, wouldn't this be possible, if we accept that PKC doesn't form part of the system?

    Also, what happens when the photons pass from, say, a fibre, to an uplink. Or when they pass through the sattelite? Won't they lose their polarisation?

    And, finally, what about a pure mathematical attack, based on probability and stochastic principles?

    I'm not a mathematician or cryptography expert, so I'm not just dissing this idea for the sake of it - it sounds really cool, but I'd like to know more.

    D.
    ..stands for Digital.

  • by Anonymous Coward
    What is called "quantum encryption" is in fact no encryption at all... It is just a powerful and effective key-sharing scheme for an one time pad. An one time pad is the "perfect" cryptosystem, that is it is a cryptosystem that is theoretically unbreakable... obviously there is a price to pay for this, and that is that the key as to be random (in mathematical terms, low out-of-phase correlation, roughly some number of 1's and 0's, and other more technical properties) and as long as the message. The problem is "how to produce/store/share such a beast?" [N.B. constructing a really random sequence is not possible if you are working with electronic devices only] The problem that makes one time pads unpractical for all but diplomatic use is the difficulty in agreeing and transmitting a key to the parties involved. Here it is where quantum mechanics comes to the resque: a quantum state "cannot be cloned" in the sense that it is not possible to take a quantum and get two quanta in exactly the same state (this follows from Heisemberg's indetermination principle). This means that an eavesdropper has to perturb the communication while it is listening to it, whence the possibility of knowing that who wants to communicate and to agree a key is being observed. In this scenario an attacker can only perform a DoS, but is quickly identified, hence the usefulness of using a quantum channel. The message, afterwords is transmitted using an one time pad encryption that is the safest possible in the sense that the only information one might get without the proper key is just the lenght of the message (unless the transmitter adds some padding, just for making also this an useless information).
  • "Bob could then call Alice on the telephone and tell her exactly which 25 photons he received. These would form the key for encrypting a subsequent message"

    seems like a lot of trouble to go through and end up your phone conversation being overheard. i suppose with the way the filters work the "Eve" wouldn't have much luck catching the same photon's. but we all should remember your trusty telephone (especially those cordless or cellular ones) are probably a lot less secure than even the most basic form of computer encryption. people seem to forget that a lot.


    tyler
  • The nice thing about Quantum encryption is that it will come in a lot sooner than Quantum computers and also qunatum computers can't 'crack' quantum encryption. Anyway the idea of a working quantum computer is still a long way away
  • The article answers every single question you ask! Read the article, THEN ask questions.

    --synaptik
  • To me, it seems that this should be "quantum key exchange" rather than "quantum encryption", because you still must use some existing method of encrypting your data. Of course this is super cool because you can use an unbreakable one-time pad and then securely share the pad with the receiver. But if you're afraid the NSA is going to sneak into your house and steal your hard drive, this method can't help because it can only protect a key in transit.
  • It doesn't matter if the phone call is overheard, since Bob only reveals the positions of the photons he received, not their values. As the article explains, it is likely that Alice has misread some of the photons.
  • The breezy assertions at the start of the article that modern cryptosystems are going to be cracked any moment now are totally unwarranted. Progress in solving problems like factorisation, ECDL etc has not been much different from what might have been predicted fifteen years ago, and we have no particular reasons to think that this will change. It's about as worthwhile as speculating that some as-yet-unknown discovery in physics might render quantum cryptography useless.

    Quantum crypto requires bizarre quantum properties of your message to be preserved from end to end - there's no possibility of an ordinary routing network. Furthermore, as the Dodger points out, it just pushes the problem into the authentication domain, and that's resting on precisely the same "untrusted" mathematics and a few social problems too. It's an interesting toy, but the public key crypto we already have - that we can do with straightforward hardware and the networks that already exist - will continue to be the workhorse for 99.99% of encrypted world communications, and don't let anyone try and tell you otherwise.

    I do wish people wouldn't mutter dark warnings about perfectly good systems in order to sound interesting: the field of security has enough FUD as it is.
    --
  • This seems like a very cool encryption scheme. However, it is not a foregone conclusion that an efficient factorization algorithm will eventually be found (it may not exist), as the article assumes. Furthermore, not all encryption schemes are based on prime factorization.
  • Actually, if you do a little research, the "quantum" device isn't very quantum. It's simply optoelectronic. It's called "TWINKLE"-- The Weizmann INstitute Key Locating Engine.

    The basic premise is this: the quadratic sieve needs to find numbers which are "smooth" (meaning that a number is the multiple of a certain number of primes stored on a list). These numbers are used (well, one of 'em is used, anyway) to figure out the factors of the large number (number theory omitted here, beyond my comprehension).

    Anyway, you make up a base of (say) 200000 primes. You assign each of these primes to an LED. You give each of these LEDs a little countdown timer, and hook it all up to a clock running at (say) 10 GHz. You set each countdown timer equal to the prime assigned to its attached LED. When the counter reaches zero, the LED flicks on and the timer resets. It flicks back off the next cycle.

    After X pulses (where X is a smooth number), all the LEDs that are supposed to represent the factors of X will turn on. A small photodetector will determine if enough light has been generated to consider the number interesting (has large enough or plain *enough* factors to have a decent probability of being useful). If it is determined interesting, the number is passed on to the computer.

    Since it's all running at 10 GHz, and the only outputs are few and far between (relatively speaking), the rest of the calculations can be done on a computer.

    I know that this does not even *begin* to cover a number of significant technical details-- please don't flame me.

    I also know that I'm not much of a number theory guy, but I think I get the basic premise (though I'm not great at explaining it). Please don't flame me-- I don't take Number Theory until next semester, okay?
  • "...avoiding...[a man-in-the-middle attack]...is, in my opinion, an implementation detail"

    Perhaps, but I would feel so much more comfortable with something that can be automated like contemporary public key protocols, which only require real authentication once and provide for public channel verification thereafter.

    That "implementation detail" would seem to be a bit more difficult in a world where current public key cryptography is no longer effective, as in the case where we resort to using quantum cryptography.
  • by Anonymous Coward
    Yes I think you're right. If we manage to wedge between on both the photon link and the phone link, then this scheme flies out the window. If we make the assumption that the phone call is a direct line between us (but others could be listening) , then just exchange public keys and use public key crypto instead of wasting money on all this flakey quantum junk.
  • Oh, damn, this is even worse: the device is handheld.

    "There is no surer way to ruin a good discussion than to contaminate it with the facts."

  • You don't have any evidence for your assertions here that you care to present, do you? Because you really are blowing smoke. (What did I expect from an AC, anyway?)

    You know all those cool satilite photos in the movies.. the ones where you can see the headlines of a newspaper lying on the ground? The US government had that technology in the 60s!

    Uh, no. All you have to do to prove this wrong is to figure out what the maximum resolution is, given

    • the largest mirror that can be sent into orbit (look at spacecraft diameters to calculate this)
    • The distance from the spacecraft to the ground;
    • The turbulence generated by the earth's atmosphere.
    These calculations have been done, and the result is that the best achievable resolution is on the order of 10 centimeters. Enough to read tail numbers on airplanes, not enough to read license plates or newspapers.

    And you don't think the RSA can cut 512 like butter? Of course they can, what else do you think all that money is used for?

    And your evidence for this is? So far, all you've got is hot air.

    Its not a bad thing that the US government posseses such power... its very good in fact. It won't be misused either...

    Uh huh. Past discussion here has shown how much we can trust the government to not misuse authority. No need to cover that ground again. Let's just say that you're view is hopelessly optimistic.


    ...phil

  • Who says Eve has to re-transmit the photon's she doesn't know the spin for? Couldn't Eve only re-transmit the photons she knows? The only side effect would be that Bob gets less photons but it seems like there could be any number of things that could make that happen, so maybe it could go unnoticed? Eve would be sending the correct polarization.
  • by Anonymous Coward
    The article doesn't bring this up, but...a quantum computer could break any length RSA in a matter of seconds. All you need is a QC with as many bits as your key length. Here's why: Each QC bit is put in an uncertain state--it's both one and zero. In this way, every combination of bits is checked at once. Every possible key is run through the device simultaneously, and the answer pops out. A couple years ago someone showed how a QC can be used to factor a large number. No new mathematical breakthrough is required, just this existing algorithm and a working QC.

    The only known way to keep your message secret, given the existence of QCs, is to use quantum key exchange as described in the article. Unfortunately, it seems to only be good for confidentiality. There are no quantum equivalents to digital signatures, digital cash protocols, etc.

  • If you have two channels of communication, one secure, and one insecure, you can transmit the key using the secure channel. If it's been intercepted, then the reciever would know and could tell the sender over the insecure channel to resend the key over the secure channel. If there's only one channel, then someone can sit in the middle subsituting messages to there hearts content and no one would evere know.

    While this may be a great thing for satelite communications and for closed networks, I don't see how it will ever evolve it's way down to the desktop. How will an electron maintain its' position as it travels through a switch or router? What about sending down a fibre optic line (cable modem) and then having the message relayed through a satelite, then back down to a fibre-optic cahnnel on the other side of the globe?

    No... Public key is here to stay. If it's compromised (via improved factoring attacks, TWINKLE, etc...) then we're back to square one... This isn't a subsitute that John Q. Public can use.
  • Posted by NJViking:

    Since Regular computing requires on or off bits (binary), and Quantum computing has bits that are on, off, or both..does this mean the Quantum computers work in Base-3 (tertiary) system?

    If so, we can forget about 2, 4, 8, 16, 32, 64, 128, 256 and all those "special" numbers everyone has memorized and start using 3, 9, 27, 81, 243, 729... :)

    Takes some getting used to, doesn't it?

    -= NJV =-
    ... waiting for his 531441 bit key
  • I don't see what the fuss is about taking this far enough to be able to establish a link to a satellite. You want end-to-end security, not end-to-satellite and satellite-to-end! What about rogue satellites run by Eve?

    Also, on a different note, the title of this story should have been ``quantum key exchange'' not ``quantum encryption''. I was misled into thinking that this would be about quantum computing rather than communication.

  • Eve could simply act as if she were Bob, randomly filtering photons and then letting Alice know which ones she got, imposing as Bob. Then creates her own quantum encryption key then sends it to Bob and intercepts Bob's reply to Alice trying to let Alice know which ones he got. As easy as that, any encryption is worthless if there is a man in the middle.
  • by Signal 11 ( 7608 ) on Friday October 01, 1999 @12:24PM (#1645300)

    ADVISORY: There is an Extremely Small but NonZero Chance that, through a Process Known as "Tunneling," this Post May Spontaneously Disappear from its Present Location and Reappear at any Random Place in the Universe, Including your Neighbor's Domicile. The Poster will Not Be Responsible for any Damages or Inconvenience that May Result.

    --

  • If you have two channels of communication, one secure, and one insecure, you can transmit the key using the secure channel.

    If you have a secure channel of communication, why aren't you transmitting the message itself via that as well?
  • You could probably bootstrap authentication with
    a shared secret since you have to go to the
    trouble of agreeing to timing and so on. So if
    any two parties intending to communicate can
    somehow get some shared secret across to both
    endpoints, they can update the shared secret at
    the beginning of every later successfully secured
    connection. This new shared secret could be used
    to authenticate the next time. This protects
    against MITM to the extent you can trust both the
    secrecy of the original shared secret and the
    unpredictability of later ones. However, this
    shared secret can be a lot smaller than an agreed
    to pad, since it's only used to authenticate.
  • Found the following Air Force press release [deja.com] on sci.space.news on Deja.com:

    " To show its commitment, the Air Force is investing 30 percent of its science and technology budget -- more than double its current figure -- to accelerate development of space operations vehicles, space-based radar and laser, and adaptive optics."

  • IIRC, it wouldn't make it a linear problem, it would make it a cubic problem. Much less than exponential, however.

    I think this is an interesting article, but as other posters have noticed, it doesn't provide an unconditionally secure authentication process to go along with the unconditionally secure key generation.

    Without authentication, the point is moot, because while you can be sure what you're saying is secure, you can't be sure that you're saying it to the right person.

    Also, given the rampant speculation on factoring methods in this discussion, I might as well point out the fact that elliptic curves are much harder to crack, for the main reason that they're not smooth. Therefore, TWINKLE wouldn't work on them. A lot of research needs to be done on EC crypto before they can be trusted to the extent that RSA is today.

    And all in all, RSA isn't the worst choice out there, as long as certain precautions (enumerated in Applied Cryptography, among other places) are taken. The RSA patent expires Sept. 20, 2000, which will be a Very Good Thing(tm). I'm keeping some chapagne on ice... well, not really, but I'll probably be pretty stoked.
  • Ah. Okay. I get what you're saying.

    But still...if they have that dedicated fiber for authentication and they know as a certainty that the party at the other end of it is who they're trying to send the message to and nobody else, why don't they just send the transmission over that? :P
  • Youre right...
    there's nothing wrong with using factorization as the idea is so simple yet powerful that no one will likely prove P=NP. We can estimate how infeasable a brute force attack would be.

    I'd be more hesitant to use quantum crypto since it depends on the uncertanty principle, which is still a theory.
  • This is of course the perfect encryption mechanism; no one on earth can crack it, only the satelite up in the sky, and who's taking care they get all the information that goes through it?

    You guessed it: the government. And then ask yourself: do you trust them with it?

    Quantum cryptography is great if you are in line of sight of the party you want to communicate with, and it may be a perfect way to communicate with your aunt on the mars colony; but the only other option is private high-grade fiber from every home to every home, and that's a hell of a lot of fiber. (I forgot to mention a big mirror-carrying satellite in the sky as another option, although I don't know enough quantum physics to know if it would still work after the photons are deflected)

    By the way, although the article is interesting, it isn't new, you can also find out about quantum crypto in Bruce Schneier's Applied Cryptography, 2nd edition, pages 554-557.

    EjB
  • Since photons reflect off the sides of optical fiber without changing polarity then reflecting off of a satellite would not change their polarity either.

    Er.. that was exactly my question.. and you didn't answer it at all.

    WHY don't they change polarity when reflecting off of the side of the fiber? I mean, the whole point of polarizing sunglasses is because sunlight gets polarized horizontally when they reflect off of the ground, so why doesn't it get repolarized when it hits the side of the fiber?

  • Here's the deal: It's a two part key-transmission protocol. The quantum channel is assumed to be actively eavesdropped (i.e. eavesdroppers are, without a doubt, changing something, thanks to that German guy). The regular channel can/is being passively eavesdropped (i.e. eavesdroppers aren't changing anything, just listening). The important thing is that they share only a few (not all) of the correctly receiveded bits so they can compare whether or not the error rates were correct. It's the error rate that matters, they can afford to sacrifice the values of a few bits. It doesn't matter if Eve can catch the photons; as long as Eve doesn't know the exact polarizations that Alice uses prior to Alice's transmission, it's guaranteed that Eve will screw a few up in her eavesdropping, and thus Bob will get wrong values, compare them with Alice, decide they were being eavesdropped, and they will cease communications on that channel.
  • I remember reading that in order to get the signal to go far enough to be usefull, they have to dope the fiber at intervals. Wouldn't this equate to a re-transmission? So the problem is getting an undoped fibre long enough to be usefull, and cheap enough to be affordable.

    Also, would Nortel's newly announced optical switch work? It uses refraction to switch the signals between fibers.

    Jason Pollock
  • Actually, it's even simpler.

    Alice doesn't transmit the key. She transmits a string of potential values to use in the key. Not until Bob recieves the values & they compare notes via the insecure channel do they decide upon the key. Because of this, any information that Eve recieved & didn't somehow retransmit would have no effect on the final key.
  • While this article introduced some cool sounding ideas, it seemed a bit thin on real information.

    First of all, it has turned its back on the neat solution of public key encryption which foils many of Eve's opportunities. And it assumed that "some mathematical genius" would eventually learn to factor numbers created by large primes. While this is, of course, a possibility, I am of the opinion that it is quite remote. Perhaps it was just the simple language used in the article, but the actual cryptographic evidence wasn't very robust.

    If some mathematical genius can break current public key encryption schemes, doesn't it seem just as likely that someone will be able to solve the problem of how to intercept the quantum encryption?

    ---

  • The thing with Quantum mechanics is that you just cannot 'listen' without changing the the object you are listening to. Heisenberg explained this best, imo.
    I did some researh work on this a few years back...I'd dig it up but I thought the article explained this. *shrug*
  • If our understanding of the physics is correct (pretty much certain) then this system is provably secure: no mathematical breakthrough will let you in.

    If you can intercept *all* communications between the two parties, direct and indirect, and substitute *all* messages for ones you've written yourself, then nothing at all will stop a MitM attack. You have to have some sort of authentication lever.

    However, you're right to say it's a particular weakness of this system, because the system depends on Bob sending Alice an authenticated message of what measurements he took. If Mallet can subvert this channel he can read the secret message. And QC doesn't provide provably secure authentication, since that's impossible - it's a social problem as much as anything else. Perhaps you could prove that the sender of a message knows a particular secret, but how will that help if you can't be sure who holds the secret?

    And you're also right that it's totally impractical for real use.
    --
  • Read the article. You're right, this whole process covers only the exchange of keys.

    But once you have a one-time pad, you only need to XOR it with your plaintext. Why would you need a complex encryption scheme? No key, no plaintext. One-time pads are the safest encryption method, period.

    "There is no surer way to ruin a good discussion than to contaminate it with the facts."

  • The Weizmann institute announced a design for a piece of opto-electronic kit called TWINKLE that could greatly speed factoring, though modern recommended key lengths (eg 1024 bits) are still *way* out of its reach. However, it hasn't been built yet, it's not handheld and it doesn't go at 12 microseconds.

    The UK Government are mulling over how to cripple domestic crypto without getting hit over the head at the moment, so scare stories about crypto are appearing all over the press at the moment, especially the Murdoch-owned press; apparently the crypto we all use is worthless, but the Bad Guys are using unbreakable crypto to hold up banks so it must be stopped, and we must go to the GCHQ (our NSA) for "consultancy" on what best to do about it.
    --

  • She doesn't need a "photon duplicator", although you're on the right track. All Eve has to do is read the polarity of the photons (i.e. pretend to be Bob), and then send photons of the same polarity on to Bob (i.e. pretending to be Eve).

    Then, even if she doesn't listen in on the conversation (or sniff the insecure ethernet), she probably has enough information (by having the entire list of photons and their bit-state, of which the key is a subset) to attack the message.

    I'm wrong - I've got to be. These guys have PhDs and stuff... I don't even have a degree. I just want to know where I've gone wrong, but I can't figure it out from the article. Admittedly, it's not exactly a white paper, so maybe it's leaving something out. Or maybe I'm just being particularly obtuse and stupid.

    D.
    ..is for Delinquent.

  • The problem is that there is no way to know whether the factorization problems are solvable. They are considered "hard", but there is no proof that someone won't come along and render the whole thing obsolete. And maybe someone already has...
  • What prevents Eve from completely spoofing as Bob?

    In other words, suppose Alice thinks she's sending to Bob but, in fact, Eve intercepts Alice's transmission and prentends to be Bob. Alice then goes through the whole protocol, thinking she's set up a connection with Bob. To keep Bob fooled, Eve sets up a bogus session with Bob to make him think he's talking with Alice. Eve then decrypts Alice's messages, reads them, then re-encrypts them and sends them on to Bob.

    This problem is solved by digital signatures with todays systems but it seems to me that there is no such thing for Quantum encryption yet.

  • The whole point of quantum cryptography is that it solves the problem of secure key transferral for a one-time pad. One-time pad has been proven unbreakable, given a truly random key.

    The article doesn't go into specifics, but quantum crypto has quite a few limitations, distance being the most important for day-to-day communications. The longest quantum channel I've heard of is about 2km. Photodetectors/emitters are also a problem. For quantum crypto to work completely, you have to be sending single photons(or photon pairs) out and detecting single photons. Current experiments are emits "small" numbers of photons. The problem is that Eve can split the group of photons and detect the spin in an undetectable manner.

    Quantum crypto has a ways to go before it is practical.
  • I'll add to this with a bit of sophmore-level physics on the subject...

    When a light signal with intensity I0 and initial polarization of, say, 0 deg is incident on a polarizer with rotation angle x, the transmitted intensity is given as I = I0*cos(x)*cos(x). Thus, if you intercept this signal with a polarizer rotated by 45 deg, you get I0*cos(45)*cos(45) = 0.5*I0 transmitted intensity.

    Using a single photon rather than a stream produces a 50% chance that the photon passes through. If Eve's polarizer blocks the photon, either the photon was initially transmitted at a 90 deg angle to her filter, or was transmitted at a 45 deg angle to her filter and failed the 50-50 chance. If her filter allows the photon through, she knows what the polarization was and can retransmit the photon. When that retransmitted photon gets to Bob, it may well fail the 50-50 chance, providing him no information (remember, you only get information on the photons that pass your filter).

    As an aside... if you transmit photons with a polarization angle of 0 into a filter with angle 90 deg, nothing comes through. If, however, you put a filter rotated an angle of 45 deg between the original two, you have a 50-50 chance of a photon passing the first filter, and being repolarized with a 45 deg angle, at which point, it has a further 50-50 chance of passing through the 90 deg filter (since the relative angle between the filter and the repolarized photon is now 45 deg).

    The point being that any detection of the photon stream between Alice and Bob will affect the overall signal, and simple error checking, as mentioned in the article, will detect the intrusion.

    --
  • by aheitner ( 3273 ) on Friday October 01, 1999 @07:15AM (#1645330)
    The problem of how to break something like RSA is a mathematical one: either some operation is easy to do in one direction and hard to do in another, or it's in fact easy in both directions. Factoring is one example of such an operation.

    The proposed quantum scheme relieson the fact that whether a photon will pass through a filter polarized at 45 degrees to the photon's own aligment is random at a quantum level, eg. can't be determined. Eve is screwed at a fundamental physics level. The only thing that could crack this would be major changes in our understanding of particle physics.

    It's open to debate whether this is more or less likely than finding a quick factoring method (or in the case of RSA, a quick way to find Phi(n) from n). . .
  • I'm unclear on whether they're dealing with a single photon. At the begining they're talking about spin, and obviously that involves using single photons. But when using polarity, do the same rules apply?

    If so, this seems extremely susceptable to man in the middle attacks. Sure, Eve will have problems listening in, but all she has to do is read the key and transmit a new one. She'll run into problems with verification (she'd have to fake that too) but that doesn't seem impossible.

    Maybe when transmitting the fake key she keeps saying it's wrong until Bob gets the same bits right she did. Then Bob will tell Alice to use the same keys Eve got right. That would certainly generate a lot retrys, though, which would make Bob suspicios if he's paying attention.

    Come to think of it, this must involve only a single photon, otherwise it'd be trivial divide up the light beam and send it through a set of filters in paralel. Then Eve could know the polarity without any of this nonsence... duh.

    Frankly, while this may, under certain controlled situations, be useful, I'm having a hard time seeing how it could be born out in the real world w/ noise and turbulence, and human error.
  • The problem I see with that, is that Bob would only receive part of the transmission. Eve will be intercepting the entire stream of photons, and then (in your suggestion) re-transmitting only part of the intercepted stream. Bob, in the end, would only receive a partial key. In which case, Mary and Bob would have to restart the transmission, using a new random key taken from the next page in the one-time pad. Of course, this all is based on the assumption that Mary and Bob would be smart/paranoid enough to transmit a new key _every_ single time they have to transmit, regardless of the reason why. After all, certain steps, aside from the technology being used, have to be taken to ensure a secure transmission. It's not all in the hands of the technology.

    You could have the most unbreakable/uncrackable (or whatever you want to call it) method of transmitting data. That won't mean squat* if the individuals using the technology aren't willing or knowledgeable enough to take certain precautions to ensure an adequate and/or secure usage of said technology.

    * squat - slang : the least amount : anything at all. Taken from diddly-squat.
  • by Anonymous Coward
    base-3 = ternary / trinary

    base-3 != tertiary
  • One-time pad through quantum encryption prevents Eve from listening into the conversation across the line or changing the signal. But it does nothing, as indeed it can't, to prevent her from capturing the unencrypted information on either Alice or Bob's end. Eventually, all cypher must be converted to plaintext, where it is susceptible to any number of attacks. Of course, Alice and Bob could be locked inside steel vaults, with no Internet connection and a room full of M-16s...
  • by Anonymous Coward
    The only way this would work obviously is if the satellite merely reflects the signal without intercepting it. This is the only way I can think of to preserve the polarization.

    Timing transmissions to the nanosecond is an easy way to insure an accurate destination. Just check the time of transmission and compare it to the time it takes light to travel the distance.
  • Something I didn't see mentioned here in questioning this was how exactly Eve is going to get into the stream of phontons without being detected. This is a POINT TO POINT transmission. It's not like a radio signal that comes off an antennae which propegates in all possible directions. A beam of photons will spread out over a certain distance (not a whole lot, a good laser won't spread out at more than maybe 1 degree), but from what I understand from this artice is that they are sending one photon at a time, thus the transmission line is almost perfectly defined. Clearly, if the photons are to hit an orbiting satellite with a photodetector 2" wide, Alice will have to know the exact position of the satellite. Thus the exact path of transmission is EXTREMELY well defined, and it is almost trivial to determine if something is in the path of transmission. Eve has no chance, even if she were able to detect, replicate, and figure out the key sequence. This looks pretty unstopable until we have airplanes with cloaking devices, not to mention getting around the heisenburg uncertainty principle.
  • The article is about quantum encryption, NOT quantum computing. The article was about using photons to securely transmit a one time pad using photons.

  • Most researcher do *not* believe it will happen. The techniques that reached 5 bits can't be extended very much further. No practical demonstrations of any extensible techniques exist at all. It's most likely that decoherence will render it impossible.
    --
  • Quantum encryption doesn't require quantum computers.

    If you'd read the article, you'd know that.

    LK
  • You can't have a photon duplicator. It's not the Heisenberg Uncertainty Principle so much as something more fundamental - the "No Clone Theorem". This theorem is what makes Quantum Cryptography work. It also means that when they invent Teleporters people won't be able to make illicit copies of you :-)
  • by Paul Crowley ( 837 ) on Friday October 01, 1999 @07:18AM (#1645342) Homepage Journal
    The conclusions of those "people out there" are not based on anything resembling a fact. If this sort of mindless, groundless pessimism puts even one person off encrypting just one email message with the best tools we have (PGP, GPG etc) then the NSA have done part of their job without spending a single compute cycle.

    Learn a little about how modern crypto works (The Cryptogram [counterpane.com] is a good place to start). Read the descriptions of some of the AES candidates: Serpent, RC6 or Rijndael might be good ones to start with. Even in the supremely unlikely case that the NSA can crack everything we use, it would still cost them something in compute cycles, and encrypting all the world's email would still put a significant barrier in the path of their intelligence-gathering activities.
    --
  • Couldn't a man-in-the-middle attack theoretically be launched on this type of encryption?
    "Bennett and Brassard proposed using photons polarised in different directions to represent 1 or 0. If Eve tried to intercept the key, she would have to measure the photons, which would effectively mean absorbing them. To avoid being spotted, Eve would have to retransmit the photon to Bob. However, because of the strange way that quantum particles work, Eve does not always measure the same polarisation that Alice sent. That in turn means that she cannot be sure that she is retransmitting the correct orientation. Thus Eve's interception will inevitably affect the transmission of the key, and Alice and Bob should be able to spot this, discard the key, and try again with a new one."

    Also, what happens when the photons pass from, say, a fibre, to an uplink. Or when they pass through the sattelite? Won't they lose their polarisation?
    "Ultimately, they want to be able to fire individual photons to hit a satellite's receiver, which is only a few centimetres across and orbits at an altitude of 300 kilometres. The photons must pass through the atmosphere without being absorbed--so that the signal is not simply lost--and they must not change their polarisation. It's easy enough to make sure that the photons are not absorbed. You just have to choose a wavelength that the molecules in the atmosphere ignore. Hughes's team has opted for 770 nanometres. Longer wavelengths also pass through the air unscathed, but are more susceptible to turbulence, which changes the local refractive index of the air and thus twists the orientation of the photon's polarisation. Turbulence typically occurs on a scale of tens of centimetres, so 770 nanometres is short enough to avoid this."

    And, finally, what about a pure mathematical attack, based on probability and stochastic principles?
    "This type (one-time pad) of code is impossible to crack because each element of Alice's key is random. Even if Eve were to use computational brute force to try every possible key, she'd find that many of them made some sort of sense, and wouldn't know how to choose between the alternatives. Bob, on the other hand, has a copy of the key, and can decipher the message by simply subtracting the key from the encrypted text."

    As you can see, all of the answers to your questions were in the article. It really is a very interesting article, but (IMO) you probably should have some type of basic understanding of cryptography before you read it. By "basic", I don't mean "what is cryptography?", or anything like that. Those kind of questions, to me, are on the same level as learning how to walk and talk, and as such, are below even "basic" level knowledge. One book that describes a lot about cryptography, even "what is cryptography" :), is called "Applied Cryptography, 2nd ed.", by Bruce Schneier. ISBN = 0-471-11709-0
  • Something the article didn't cover or I missed completely. How does Alice know she is talkin to Bob and not Eve's agent when verifying a valid key was transmitted? In other words, can't Eve simply intercept the entire transmission and emulate Bob to verify the key? While the cryptography logic seemed solid to me, I fail to understand why the phone system is so casually used as an integral part of this system. Note that if something other than the phone call is used to verify the key, the problem remains: how to authenticate Bob in the verification step?
  • I am not suprised at all by this... one of the only ways that Israel remains a soverign power is by being more technically advanced than its neighbors. They have to! And developing tools like this is just part of it. The Israelie government is very much like the US in this sense, however the US is even further ahead. You know all those cool satilite photos in the movies.. the ones where you can see the headlines of a newspaper lying on the ground? The US government had that technology in the 60s! And you don't think the RSA can cut 512 like butter? Of course they can, what else do you think all that money is used for? Its not a bad thing that the US government posseses such power... its very good in fact. It won't be misused either, because that risks revealing that they have it. Don't worry, all these are government toys... our 128 bit encryption is save in the civilian sector for quite a while yet.

    -----

This process can check if this value is zero, and if it is, it does something child-like. -- Forbes Burkowski, CS 454, University of Washington

Working...