Slashdot Log In
Scientific American on Quantum Encryption
Posted by
samzenpus
on Thu Jan 20, 2005 01:35 AM
from the just-try-and-break-it dept.
from the just-try-and-break-it dept.
prostoalex writes "Scientific American claims that advances in commercially available quantum encryption might obsolete the existing factorization-based solutions: "The National Security Agency or one of the Federal Reserve banks can now buy a quantum-cryptographic system from two small companies - and more products are on the way. This new method of encryption represents the first major commercial implementation for what has become known as quantum information science, which blends quantum mechanics and information theory. The ultimate technology to emerge from the field may be a quantum computer so powerful that the only way to protect against its prodigious code-breaking capability may be to deploy quantum-cryptographic techniques.""
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
Unbreakable Encryption... (Score:5, Funny)
Re:Unbreakable Encryption... (Score:5, Funny)
Parent
Re:Unbreakable Encryption... (Score:3, Funny)
The only problem with this is that when you send your cipher text, the big bad corrupt government agency can easily show that your clear text was "I planted the bomb"
A pity, as it looked as though the cipher text would compress really well.
Re:Unbreakable Encryption... (Score:5, Funny)
But you still need to apply for an export licence if you use a encryption key greater than 128 bits in size.
Parent
n.b does not hurt cats unless you observe them (Score:5, Funny)
Re:n.b does not hurt cats unless you observe them (Score:2)
Uhh... (Score:2)
Re:Uhh... (Score:5, Informative)
Parent
Re:Uhh... (Score:5, Informative)
If you have a quantum byte, i.e. 8 quantum bits, you can load it with 256 different integers simultaneously. You can do a single computation on the byte, and this computation is done simultaneously on all the 256 integers. This can easily be emulated, with 256 computers, as you suggest.
But, if you have a quantum computer with 256 quantum bits, you can do computations simultaneously on 2**256 integers. That's not easy to emulate with classical computers because we don't have enough of them.
The main problem with constructing algorithms for quantum computers is to read the result. When you read the 256-bits you only get a single number among the 2**256 which are stored there. Each of 2**256 integers has a probability associated with it, what you read is governed by this probability. Once you read, the state of the computer collapses to what you read, all the other information is lost.
Shor's algorithm solves this by ensuring that the result is periodic, the period being the solution to the problem. It then performs a Fourier transform on the state. Then reads it and gets the period with high probability.
Parent
Re:Uhh... (Score:3, Insightful)
In effect you go back to square one. To simulate N qbits roughly your quantum computer simulator must have the capacity to completely explore 2^N states. It quickly becomes unmanageable, and you revert to the original problem.
Equivalently you can say that if you have the traditional computing power to solve the problems that a given quantum computer would be able to solve easily, then you approximately hav
Re:Uhh... (Score:3, Informative)
Let's try an example: Let's assume that we need only as much precision that we can use a fixed point numer format with a size of one byte. Then a complex number will need 2 bytes, and the vector to just store the quantum state of an n-bit quantum computer will therefore need 2^(n+1) bytes.
According to Wikipedia, there are 6*10^79 atoms in the universe (taking t
Re:Okay, so? (Score:3, Interesting)
Back in the days of enigma and such, when one side upped its computer technology, the other side added a wheel to its cipher machines. That would last a few years and then everybody is upgrading again.
RSA has been around since the 70's, and has remained stable the whole time. It made crypto practical to use, and ended the arms race by making crypto hundreds of orders of magnitude harder to crack. Ditto for modern symmetric ciphers, whi
Re:Uhh... (Score:4, Funny)
It makes promises.
I'm not just gunna break yo' face, i'm going to quantum break yo' face, foo'!
Parent
Re:Uhh... (Score:5, Funny)
so you gonna break his face and slam a cardboard box over his head? "no officer, his face is not smashed. however, if you take the box off it might cause it to be smashed or not"
Parent
Re:Uhh... (Score:2, Funny)
I quantum-love science!
Re:Uhh... (Score:5, Informative)
Quantum computing provides an algorithm (Shor's), utilizing quantum mechanical manipulations, which factors numbers exponentially faster. Thus, factoring and checking factors takes the same amount of time.
This leads to the undesirable conclusion that encryption and decryption (by an intercepting 3rd party) of a signal take the same amount of time (up to a polynomial equivalence). In other words, the encryption is breakable, since the interceptor need only invest roughly the same amount of computational effort as the sender in order to crack the message.
That is why the creation of a quantum computer would "obsolete" present encryption. The point of quantum encryption is that it is not vulnerable to such attacks.
Parent
Re:Uhh... (Score:3, Informative)
Re:Uhh... (Score:3, Informative)
Re:Uhh... (Score:2)
Great, so you can get quadrillions of improperly decoded versions and one good one, hidden in there somewhere. For any good encryption, I don't see how that helps much.
Re:Uhh... (Score:5, Insightful)
However, it is perfectly reasonable to borrow a large sieve with a water tray - which both work on all the grains simultaneously - and then the job becomes doable in hours.
Parent
Whole Article, One page (Score:4, Informative)
Article here [sciam.com]
Bah... (Score:2, Funny)
sweet upgrade (Score:2, Funny)
Trinary digITs here we come!
Good for telco's? (Score:2, Interesting)
Baloney. (Score:5, Interesting)
Re:Baloney. (Score:5, Insightful)
Ultimately cryptographers want some form of quantum repeater--in essence, an elementary form of quantum computer that would overcome distance limitations. A repeater would work through what Albert Einstein famously called "spukhafte Fernwirkungen," spooky action at a distance. Anton Zeilinger and his colleagues at the Institute of Experimental Physics in Vienna, Austria, took an early step toward a repeater when they reported in the August 19, 2004, issue of Nature that their group had strung an optical-fiber cable in a sewer tunnel under the Danube River and stationed an "entangled" photon at each end. The measurement of the state of polarization in one photon (horizontal, vertical, and so on) establishes immediately an identical polarization that can be measured in the other.
And it continues on this page http://www.sciam.com/article.cfm?chanID=sa006&arti cleID=000479CD-F58C-11BE-AD0683414B7F0000&pageNumb er=3&catID=2
Parent
Re:Baloney. (Score:3, Interesting)
Hmm, I don't know who you work for, but I suggest hiring someone with a Clue.
Banks, by and large, do not use asymmetric cryptography like RSA to secure their transactions. The standard for retail and wholesale banking environments is Triple DES, and it's not likely to change for some time, since they've only just finished moving there.
Keys are distributed by loading them into secure, tamper-responsive devices in a trusted environment where no sniffing can occur; then the devices are sent to where they
Wait till DVD Jon hears about this (Score:2, Funny)
TFA is quite ..umm.. cryptic (Score:2, Informative)
Ok, if yo
Re:TFA is quite ..umm.. cryptic (Score:4, Insightful)
Who said using it on current networks? In real life, custom networks are used, of course.
Sending information faster than light is likely not possible. The FAQ you linked to says that too. Currently, theory says no, and experiment can't tell. Some have chosen to interpret their experiments as supporting FTL transmission of information. But the majority do not agree with that interpretation.
Using photons in computers in any form is so far off that suggesting it as a solution to current day problems like die size vs clock speed is ridiculous.
Parent
Re:TFA is quite ..umm.. cryptic (Score:5, Informative)
Parent
what, me worry? (Score:2, Funny)
scary stuff....however, a simpsons quote comes to mind:
Alien 1: It seems the earthlings won.
Alien 2: Did they? That board with a nail in it may have defeated us. But the humans won't stop there. They'll make bigger boards and bigger nails, and soon, they will make a board with a nail so big, it will destroy them all!
[both alie
Quantum Encryption is Not Encryption (Score:5, Informative)
The problem lies in that you have to have a single, unbroken fiber optic connection between the two points, and this fiber optic connection is very limited in the amount of loss that it can withstand. That means you're geographically limited on how far the circuit might be able to travel. You're looking at a few hundred kilometers, at the absolute maximum.
Considering the amount of money you'd spend on putting the circuit in place versus the amount of money you'd lose if the data was compromised, it's very unlikely that anyone, anywhere will have a practical use for QKD/QE. Government and defense, maybe, but then only in very limited applications.
There is a chance that, should quantum computing become a reality and modern encryption algorithms can suddenly be cracked very, very easily that this method may see some use, and by no means is development a waste of time and effort. But, QC is still very much in the early stages, if a working system is ever developed at all.
Thta being said, PKI and courier delivery of key material will continue to be the order of the day for quite some time.
I don't know if I can make this clear, but I'll (Score:5, Informative)
Particles that are treated best by quantum theory (such as photons, here) exhibit quantum states. Just think of them as metainformation about the particle, which is accurate to a first approximation and appropriate for this explanation. In this case, the light is polarized, which dictates some of its quantum metainformation.
The Heisenberg principle, which you've probably heard about, says that you cannot know the position and momentum of a particle exactly, simultaneously. You can know one or the other exactly, you can know both with noninfinitesimal error, but you can't know both. For big, heavy things, like macroscopic objects, the uncertainty is so small as to be irrelevant.
The quantum weirdness which results is as follows: an unobserved object simultaneously exists in a linear combination of multiple quantum states. That is, it exists as
(x*A+y*B+z*C)/(x+y+z)
Where A,B,C are quantum states and x,y,z are relative probabilities. If they add to 1, the x+y+z term falls out.
This is where schrodinger's cat. If you wait exactly long enough that the probability of the cat dying is 50%, the cat is exactly equal parts dead and alive. It's accurate, but I think it's confusing because it confuses the fact that quantum states really only apply to very small things, except in isolated cases like this.
Where the unbreakability of quantum encryption comes in is the observer. If you open the box, the cat is no longer both, it's just dead or alive. If you look at the photon, it's A,B, or C. You have destroyed the metainformation contained in the photon, because up until when you observed it, it was x parts A, y parts B, and z parts C.
This is unavoidable and fundamental to quantum mechanics.
For quantum encryption/communication not to work this way, we have to be wrong about quantum mechanics, and the fact that it's just so WEIRD is part of the reason I suspect it will work. It's so counterintuitive people have verified this many times.
The big question.... (Score:4, Funny)
So the big question is: Why does Alice have so many secrets? Why does she feel compelled to tell Bob everything? And what is up with Eve, always budding in?
Personally I think there's something going on between Eve and Bob, that they're not telling us. But damned if I can't break their code.
yo.
Parent
Easy explination of Quantum Encryption.... (Score:5, Informative)
Unfortunately, Due to Quantum Mechanics, Bob only has a 50% chance of actually reading the state of the photon. 50% of the time he gets '0' or '1', and 50% of the time he gets 'Unknown', and the photon is destroyed..
This is ok, because after receiving 1 million bits, Bob phones up Alice on an unsecured line and says I managed to read photon numbers 5,6,9,12,13,16....(+ approx 500,000 more), so I will use the state of these photons as a one time pad. Alice looks up the states she sent these photons, and now both parties have a one time pad to encrypt data.
Now, lets say there was an intruder attempting to intercept the key exchange. The intruder is also constrained QM, and can only read 50% of the photons, with the other 50% Destroyed. Because, the 50% of photons the intruder would receive, would be different to the 50% bob had read, it is impossible for the hacker to use the information sent using by bob to Alice, via the unsecured phone call, to build an equivalent one time pad.
Also, as the intruder is only able to forward a exact copy of just 50% of the photons to Bob, with the other 50%, now destroyed. He could replace this 50% of photons with his own set of random state photons, but this will be detected by Bob and Alice, as the one time pads would be different on this 50%, and the transmitted data using the pads would be corrupted.
Technology VS. Laws (Score:3, Interesting)
Question (Score:3, Insightful)
Re:Quantum Encryption (Score:5, Insightful)
Well, you think wrong. Quantum encryption cannot be 'brute-forced'. Because it's not 'encryption' in the conventional sense but rather 'secure transmission'. The data is not encoded, but rather transmitted in a way which makes eavesdropping impossible. Since you can't intercept any 'coded message', there is nothing for you to brute-force.
And this holds as long as what we know of quantum mechanics holds.
(More specifically, the Bell inequality [ucr.edu]. Which was verified in the famous Aspect experiment.)
So no, nothing in quantum physics is going to invalidate quantum encryption. And I wouldn't get my hopes up for future theories, either, because this 'wierdness' of quantum mechanics so well-verified experimentally that it'd be unlikely that any future theory would change it. (But hopefully explain it)
Parent
Re:Quantum Encryption (Score:2)
No, we won't. It's an interesting thought, but it doesn't work that way. According to the laws of physics (as we currently understand them) quantum encryption, if done properly, is provably secure. That is, there is no way to break the encryption, unless quantum mechanics itself is flawed.
Of course, there are other attacks. For example, QC (quantum cryptography) requires you to pick the polarization basis r
Re:Don't verb adjectives (Score:5, Insightful)
OK, there's two very different uses of quantum technology when applied to crypto problems:
1. If you had a quantum computer some problems like factorization become easy; therefore things like RSA would be instantly decryptable. The gotcha is that the current "state of the art" for quantum computers are still absolutely tiny and there are HUGE engineering challenges towards building one large enough to factor a real key (I think they're at the point now where they can factor numbers like "12"... so they have a bit of scaling before they can start attacking 300-digit numbers)
Of course there could be a massive breakthrough in quantum computer design tomorrow which would throw the whole crypto world on its head. That makes this area really interesting for crypto people.
Does NSA secretly have a quantum computer that can do that? I'd say its extremely unlikely... I'm sure they have people looking into it but they would have to be AMAZINGLY far ahead of the public research community to have actually built a full-size one.
2. What this article is talking about is "quantum encryption" what's really "quantum" about it is making an untappable fiber line by signalling using the characteristics of single photons. By using Heisenberg's uncertainty principal you can make it impossible for anyone to tap the line (and thus observe the photon states) without also randomizing the bits. It's really hard to get your head around but it actually works.
Note that nowhere here did we use a "quantum computer"... this is all using technology that exists today (obviously, since you can buy it)
So basically even if your adversary has a trillion dollar budget to attack you with they CANNOT tap that fiber line without destroying the communication in the process. It's physically not possible with any technology.
So unless the NSA has a whole undiscovered field of physics that the world doesn't know about they don't have "quantum decyption" As we understand physics today it's literally impossible to build such a device.
Parent
Re:Don't verb adjectives (Score:3, Interesting)
Re:Don't verb adjectives (Score:3, Interesting)
Re:Don't verb adjectives (Score:5, Insightful)
So, you could send a key to the other end, but it wouldn't be the same key that you received, because the key is created during the exchange based on which photons were encoded in the same orientation they were measured. So, any protocol that uses this has to be designed to take advantage of this property to prevent man-in-the-middle attacks. Apparently the crypto boys and girls feel this is enough of an advantage to be done--I haven't inspected any protocols that do this, so I can't explain how it's achieved. But simply sending a long key and XORing the message with it isn't enough--the man in the middle could foil that by just generating a new key and reencrypting.
I'm sure someone has a good discussion of this up on the web. The question is if there's one that's accessible to the non-cryptographer.
Parent
Re:Don't verb adjectives (Score:4, Interesting)
One such example is the innocuously named "Laboratory for Physical Sciences [umd.edu]". Please note the rather conspicuous key-shaped logo. I toured their facility a few years back while looking for a job. At the time the NSA was buying them just about anything they wanted provided it might have applications in quantum computing. This included a rather sophisticated chip fabrication lab and clean room.
I don't know if we will ever really have quantum computers, but the NSA sure doesn't want to be late to the party if we do.
Parent
Re:Don't verb adjectives (Score:3, Interesting)
Re:Ridiculously overblown (Score:4, Insightful)
Quantum encryption is not about exchanging keys, its not even encryption in its normal sense. What it really is, is secure trasmission.
Secure meaning, nobody can read this data during transmission other than the reciever without it being physically impossible to notice.
Parent
Re:Ridiculously overblown (Score:3, Insightful)
There is no relation between quantum "encryption" and RSA. Quantum computers are a completely different technology than quantum key distribution. All you need for the latter is fiber optic cable, some photon counters, and polarizing filters. Quantum computers OTOH require quantum circuits, which are no more than lab toys ATM. It could be 50 years before we see sizable quantum computers, if ever.
Even
Re:Ridiculously overblown (Score:3, Informative)
Any public-private key encryption can be broken through brute force. What keeps them secure is that most of the time it takes a long time to break them.
With the development of quantum computers (which some people believe can be done within the next 20 years) it will only take a few seconds to break ANY public/private key encrypted message.
A message sent using quantum encryption cannot be broken by brute force.
Re:That's not what the Uncertainty Principle says (Score:5, Informative)
Parent