Slashdot Mirror
Quantum Encryption Explained
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.
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.
The part of the article where they state that "the key could be intercepted via their phone conversation, yet would be useless to Eve beacause she didn't know which filter they were using" intrigues me. Aren't there only two filters? Doesn't this give Eve a 50/50 chance of intercepting the message (assuming she knows the key) on the first try? Of course, if she choses the wrong filter, she would obviously be detected.
True but it would be expensive to replace bob's satellite without bob noticing, the signal distance orbital distance is tracked to the millimeter.
Uh, what exactly is the difference between "pulse of light" and "photon"? Just the amount of photons?
(define (weak-link) 'MS plan for world domination)
there is now....
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.
If you want to get rid of the bathwater, you've got to throw out a few babies.
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'm trying to teach myself to set people on fire with my mind... Is it hot in here?
Holy man in the middle attacks, Batman...
I'm trying to teach myself to set people on fire with my mind... Is it hot in here?
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.
I remember reading something about that in Wired a few months back about some work IBM was doing. However that was about all i had ever heard of it, i had no idea how far it had progressed.
I dont know much about quantum physics, but i'm amazed at how far they have gotten at being able to transmit a photon w/o altering its polarzation.
One thing, how long does it take to transmit a key?
-Hawk
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//]
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.
According to the article the photons can be transmitted through optical fiber and if they don't have to go through a repeater they maintain their polarity. (not practical for internet just yet)
Since photons reflect off the sides of optical fiber without changing polarity then reflecting off of a satellite would not change their polarity either.
This system only works point to point for establishing a key. The nanosecond timing and carefull aiming determines the exact coordinates of the origin point, the satellite reflector, and destination point down to the millimeter.
Since the communication path is exactly known along with the exact time of communication it is extremely unlikely that anyone can intercept the key carrying signal without Bob or Alice knowing about it.
This system is designed to work within a secure environment. Obviously if one is to get this degree of aiming accuracy it is likely that the geographical area of both parties will be known and secure.
No as even more than one state at the same time is possible. It requires a slightly different way of thinking or, better perhaps, forget all what you know about computers.
Practically speaking it would have to be an awfully precise mirror to reflect light with a wavelength of 700 nanometers to a target 300 Km or more below with that accuracy. As mentioned in a prior post quoting a LANL source this technique would be used to rekey the satellite, but there would still be a transfer within the satellite necessary before sending a key back to earth.
another article can be found at: http://www.exe.co.uk/articles/articlepull.asp?page =sep99/quantum.html
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.
Yeah, can some real physicists do a back-of-the-napkin calcuation of this one? By which I mean taking into account the properties of the photons, how "prescice" do the mechanical properties of the transmission and receiving appratus have to be? How does that compare to the most prescice methods currently available (I mean, it makes sense that the mechanical dimension has been entirely overlooked in the calculations, and may induce limitations the designers hadn't anticipated.)
The article sez:
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
The most rabid believers in American Exceptionalism are the exact same people whose policies are destroying it.
What's the diff between quantum computing's variable bits and an organic neural nets pudding of (basically) randomly charged and excitement-leveled neurons?
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)
--
Xenu loves you!
Indeed, the idea is that the key can be agreed on a "public channel" (the phone line) after the quantum transmission has been done. The authentication bit is not included in the simplified model presented, but is still going to be required. Still, you have to remember that all the quanta that are being trasmitted have to have been sent by the impersonator, rather than by Bob (otherwise you get a nice DoS, but nothing more)... sniffing the quantum link is to destroy the communication... obviously if you are not sure about who you are talking with in the first place, then... (but still even nowadays one has to trust a party before doing a secure transaction: the CA are supposed to garantee that who you are dealing with is actually who he claims to be, but still...) The quantum key exchange scheme, in fact, is aimed at situations where both parties might verify easily who they are. A "man in the middle" attack would assume this man to both being intercepting the quantum and the private channel, posing as Bob to Alice and as Alice to Bob... avoiding (or making quite low) this possibility is, in my opinion, an "implementation detail"
Bob and Alice are busted!
Duh, next quiz please.
By the time I had waded through the article, my disbelief had turned to laughter. A sample of this unbounded common sense:
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. [Aside from the fact that Eve owns the satelite, the problem is:] 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.
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.
That's "Mr. Soulless Automaton" to you, Bub.
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).
jabber: johnynek@jabber.org
But it's now possible to repeatedly detect a single photon. Soon, it may be possible for Eve to add a detection stream across the communication channel and impart zero net energy to the key photons.
"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.
Geeky modern art T-shirts
but some of the photons sent to bob may be at 45 degrees, and would still have only a 50/50 chance of getting through
Remember, Alice sends signals that are either polarized at 0 degrees (0's) or at 45 degrees (1's), so using a filter that is at 0 degrees would be 45 degrees off the signal for the 1's. Likewise using a filter that is 45 degrees will be 45 degrees off the signal for the 0's.
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...
.... and with that reasoning, John Q. Public would never have a computer on the desktop in the first place.
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.
"Read the article. You're right, this whole process covers only the exchange of keys."
If the person is right, why tell them to read the article??? Obviously either the person read the article or has an intuitive grasp of exactly what the article states.
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.
I'm no expert on encryption, but it seems to me that there are a couple of issues: 1. Security of one-time pads relies precisely in that they are one-time. But with the proposed scheme, the key will have to be used at least twice: once for "verification" of the key (i.e. getting to know which photons were correctly detected) and once for the real transmission of the message. This is a problem, especially because a method of verification has to be agreed between Alice and Bob. If Eve gets to know this method, maybe she could get the key from the verification transmission. 2. If I remember correctly, current quantum physics does not guarantee that the polarization of a photon cannot be accurately measured; it's only that no method to do that is known. If Eve discovered such a method, so she could know the polarization of photons with certainity, she could tap the transmission very easily and without being detected. So, you are exchanging the risk of a discovery in number theory for the risk of a discovery in quantum physics. Number theory has been way more widely investigated than quantum physics, so the mathematical method of encryption seems safer to me. Again, I'm no expert on this, so corrections would be appreciated.
> a quantum state "cannot be cloned" in the sense > that it is not possible to take a quantum and g > et two quanta in exactly the same state (this
> follows from Heisemberg's indetermination
> principle).
So what if you were to send it the photon through a laser gain media, and thereby amplifying it. Then the resulting beam could be split in to any number of beams and then detected. I don't see how the gain would destroy the original polarizasiton.
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.
Of course this does not improve physical security. It only protects the exchange of keys from man-in-the-middle attacks. The plaintext message is still vulnerable to all traditional methods of human intelligence gathering. In that sense this method is only useful to governments and large organizations that have good physical security. It might change the balance of espionage from SIGINT to more traditional human intelligence though. You know, James Bond and all ;-)
> 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:
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;
scheme is broken: Eve will simply retransmit the
polarization types she has transmitted instead of Alice's type of polarization.
one photon, Eve could steal the second one,
let the first pass and noone would realize.
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.
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.
-----
Do you even know anything about perl? -- AC Replying to Tom Christiansen post.
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 (scroll down to "Friday, June 25"), or the media fact sheet from the Gemini Project.
See also this picture of Pluto and Charon.
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.....
There are a lot of people out there who think that the NSA might already be capable of doing just this sort of thing. It's scary to think that our own government might have technology like Quantum computers and just isn't saying anything. With that sort of stuff lying around, most of our "unbreakable" encryption isn't worth the bytes in memory that it takes up.
The Times of London had a s tory Wednesday indicating an Isreali team has a hendheld quantum device that can crack 512-bit RSA keys in 12 MICROseconds.
Work for Change & GET PAID!
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
HSJ$$*&#^!#+++ATH0
NO CARRIER
Er, that should hav read, "Bob doesn't quote", not "Bob does quote". Damn fingers, did it to me again. :(
--synaptik
HSJ$$*&#^!#+++ATH0
NO CARRIER
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
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.
314-15-9265
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.
--
Xenu loves you!
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.
Geeky modern art T-shirts
How do you know there is no back door in the satellite?
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.
"There is no surer way to ruin a good discussion than to contaminate it with the facts."
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
...phil
"For a list of the ways which technology has failed to improve our quality of life, press 3."
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.
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.
"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?)"
That was "emmons" not an AC. I AM an AC which is why I am free to say you are a giant asshole with a big butt.
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.
--
This system is a simple reflected optical satellite link. The communication is timed to the nanosecond thus giving the distance from Bob up to the satellite then back down to Alice As well as Alice and Bobs exact uplink/downlink coordinates to the millimeter.
There is no time available for a middleman attack.
Think of the transmittion origin/target coordinates and transmission time in nanoseconds as an extremely accurate parity check or signature if you like.
Not only does Eve have to be in the middle of the transmission, she has to spoof a photon transmission to Bob the exact nanosecond he expects to recieve it. To top that - on a seperate communication line - she has to convince Bob that she (Eve) is Alice AND convince Alice that she (Eve) is Bob.
And if Eve can do all that, then clearly Bob is dating the wrong geek.
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.
P = NP? I think not. This writer's sweeping intro statements reflect his ignorance of the nature of factorization algorithms. Although, I do find the applications of quantum encryption intriguing.
photons are light particles do Eve can put a sheet of paper in between the transmitters and Alice and Bob are screwed. Eve can't read the messeges but Alice and Bob will then have to use a breakable form of encryption.
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?
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 PollockWhile 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?
---
I hope you're not pretending to be evil while secretly being good. That would be dishonest.
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.
--
Xenu loves you!
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.
--
Xenu loves you!
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.
--
"I'm too old to use Emacs." -- Rod MacDonald
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.
--
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.
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...
-----------------------------------------------
how much bandwidth has been wasted by this sig?
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.
"Hi. This is my friend, Jack Shit, and you don't know him." - Lord Kano
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.
--
Xenu loves you!
Quantum encryption doesn't require quantum computers.
If you'd read the article, you'd know that.
LK
"Hi. This is my friend, Jack Shit, and you don't know him." - Lord Kano
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 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.
--
Xenu loves you!
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?
Geeky modern art T-shirts
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.
-----
Do you even know anything about perl? -- AC Replying to Tom Christiansen post.