Slashdot Mirror
Scientific American on Quantum Encryption
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.""
Someone needs to write a Encryption routine that uses the source text as the key. THAT will really show 'em!
"Everything you know is wrong. (And stupid.)"
Moderation Totals: Wrong=2, Stupid=3, Total=5.
As far as I can tell, no cats were harmed in the making of these quantum cryptographic devices, although if you look inside the box, the act of looking at the cat inside may (or may not) kill it
"And we have seen and do testify that the Father sent the Son to be the Savior of the World" 1 John 4:14
The printer-friendly version puts it all on one nice and image free page.
Article here
Because you could implement Shor's factorization algorithm.
Quantum computing doesn't make threats.
It makes promises.
I'm not just gunna break yo' face, i'm going to quantum break yo' face, foo'!
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.
*I'm not just gunna break yo' face, i'm going to quantum break yo' face, foo'!*
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"
world was created 5 seconds before this post as it is.
tshtuatpptenaynrirragagcuoyomq
so long bits, hello tits.
Trinary digITs here we come!
lol: You see no door there!
And then I'll quantum-borrow the cop's glock and quantum-unload a clip into the box.
I quantum-love science!
Well with current encryption methods you usually have a public key and a secure key. Let's say I give everyone here my public key. Well then everyone can encrypt me messages, but only I can decode it with my secure key. However within that public keys lies the secrets of the secure key, but it would take an extremely long time to break the public key cipher. With quantum computing, which can perform really hard factorizations quickly, it would make the whole many current cryptographic schemes obsolete, because it would be so easy to crack the public key. Therefore the only solution to this is the introduction of quantum cryptography, which would theoretically be able to avoid being cracked easily, RTFA for more.
Quantum cryptography is a solution in search of a problem. It cannot implement public key/private key cryptography, and it can transmit only through a single uninterrupted fiber-optic cable, not over the internet at large. Given those limitations (which I don't think can be surmounted), one might as well use tremendous, digital one-time pads. Transmission of the pads to the relevant parties should be strictly easier than the quantum cryptographic solution: if nothing else, generate terabytes of noise, store it on a RAID, and put it in a car with ten intensely loyal guys. After you've done that, you can send up to that amount of data securely over the internet at large, and no amount of quantum hocus-pocus will be able to decode it.
"Jon, we have a situation. We need your to do your stuff."
The real advantage of using entangled photons would be in sending information faster than light. Entangled Photons in Computers actually might solve all the copper issues in speed we're having in chip DIE size vs clock speed (as in how to get a signal from one end of the chip to the other in a single clock signal).
Quidquid latine dictum sit, altum videtur
"...a quantum computer so powerful that the only way to protect against its prodigious code-breaking capability may be to deploy quantum-cryptographic techniques."
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 aliens laugh evilly, for quite some time]
This sig contains repetition and redundancy.
I think [..] Eventually, we will have quantum computers capable of brute-forcing even quantum encryption...
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. 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)
If someone tries to intercept this stream of photons--call her Eve--she cannot measure both modes, thanks to Heisenberg.
That's wrong. The Uncertainty Principle merely states that an observer cannot measure both position and momentum with arbitrary precision.
God, I love when slashdot covers advanced scientific stuff... then people like you who have no idea what they are talking about get to be mod'ed 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.
Quantum encryption is a misnomer, it should be called (and is, in some circles) quantum key distribution. It's all about how the key is transmitted, not how the data is secured. The encryption method is independant of how the key is distributed. Contrary to popular belief, it typically cannot be a one-time pad, since the bandwidth on the "key" channel is very limited due to the exact nature of the transmission. It can be, though, a constantly shifting AES key, or other type of data, making the datastream as a whole effectively unbreakable.
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 think that the NSA has substantially better quantum encryption / computing than the rest of us. My main line of evidence is that they are still throwing enormous gobs of money at unclassified research into quantum computing.
One such example is the innocuously named "Laboratory for Physical Sciences". 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.
give it a shot.
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.
If my understand is correct, which I think it might be, then you are completely wrong.
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.
Selling software wont make you money, selling a service will.
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.
Classical methods are not just as good.
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.
But, as usual, the media hypes this too much. Presently only two useful algorithms for quantum computers are known. A search in an unordered set, which runs as sqrt(N) (as compared to N for traditional computers), and Shor's algorithm for factoring numbers. The most widely used public key cryptography (RSA) is based on the difficulty of factoring numbers, but it would not be technically difficult to replace it with another asymmetric scheme, e.g. based on elliptic functions. No quantum algorithms are known which obsoletes this.
VERY rough explanation.
Encryption algorithms rely on the fact that some problems need an exponential number of 'calculations' to be solved. If b is the number of bits in a key, breaking the encryption needs 2^b steps.
On the other hand in traditional computers, if you have p processors and each can perform n calculations per time unit, then you can perform p.n calculation in total. Increasing p or n gives only a *linear* improvement in performance. This is not enough to match 2^b if b is big enough.
On the other hand with q Qbits you can perform 2^q calculations simultaneously (nature's miracle). Take b Qbits and you're done (I said rough explanation, remember). The only problem is that its VERY dificult to tie QBits together.
Alice sends Bob a stream of photons. Each photon that is sent, Alice encodes a state of '1' or '0' on each photon.
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.
Nope, the grandparent post is correct. Most of the encryption proposals for quantum encryption so far have involved only sending a key to be used with a symmetric cypher. The reason is similar to why the same thing is done with PKI: throughput. In PKI it's governed by the high computational costs of PK en/decryption. I'm not sure what the governing factor is in QCrypto, maybe it's due to the device physics needing to limit the density of entangled photon pairs to avoid unwanted interactions, or maybe it's because the key transmission is done by interspersing the key bit photon pairs with others carrying random data and identifying the relevant bits/pairs on a secondary classical channel.
Currently QC
a) is only good for point-to-point links. (Photonic switches would likely break the entanglement)
b) is just exchanging symmetric keys for use on a secondary channel
Now, even if we develop repeaters that decode and re-encode the symmetric key and perform routing, unless you're willing to trust the phone company's repeaters (the Chinese factory where they will likely be built, the code they are running, the administrators managing them, the physical integrity where the repeaters are located, and the ethics of the company directors preventing industrial espionage on competitors), you're still back to square one. If you need to run point to point lines, then you might as well ship a 200GB drive full of symmetric keys or a striped multi-Terabyte one-time pad. It will be a lot cheaper than running new fiber without the distance limitation and by the time this is necessary, 200GB will probably fit on a USBv4 key).
On the other hand, the grandparent is incorrect that breaking RSA via Quantum Computing is unrelated. The only reason why you would bother going to this is because you expect that factoring could be done in O(f(n bits)) - where f(n) is less than exponential - with Quantum Computers. I haven't heard any indication that quantum computers could be used to break symmetric cyphers.
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.
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.
If you have the quantum equipment anyway, it's no problem to generate true random numbers. Just produce vertically polarized photons and then measure them in diagonal direction. This guarantees complete independence of the resulting bits from each other (i.e. no correlation), and for perfect vertical and diagonal arrangement also equal probability of 0 and 1. But it's the independence which is really crucial; it's simple to create an unbiased random bit stream from a biased one if the individual bits are independent: Just split the original bit stream into pairs of bits, then throw away all pairs where both bits are the same, and for the remaining pairs always take the first bit. For a stream of independent bits, this guarantees a stream of equally probable independent bits. The bias of the original stream just affects the data rate.
The Tao of math: The numbers you can count are not the real numbers.
Does NSA secretly have a quantum computer that can do that? I'd say its extremely unlikely...
Actually, they do! And the infinite improbability field that it generated is the true reason behind the November election results.
Because it is extremely inefficient to simulate the quantum world, as everything happens in parallel.
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 have the capacity to simulate this quantum computer (give or take an order of magnitude perhaps).
Your approach wouldn't work. Perhaps a given fast computer would, say, be able to simulate 7 qbits. Then 2 such computers would only be able to simulate 8 qbits, not 14 ; a thousand such computers would only be able to simulate 17 qbits, and so on.
BTW, some people say that the reason why we haven't been able to produce a strong AI yet is that some quantum effects happen in the brain. Roger Penrose in particular is a big proponent of this idea.
On the other hand some AI people say that the only reasons why we haven't got strong AI yet is (a) we don't really know how the brain works yet, and (b) we need more computing capacity. More research is needed for (a), and Penrose would agree with this, but eventually we'll have all the computing capacity we need.
However if thought is based on quantum processes then we might require quantum computers to simulate it, who knows. This could mean that strong AI is some years away.
An n qubit computer is a general 2^n state quantum system. Now emulating an N state quantum system means manipulating vectors of N complex numbers.
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 the upper limit of the range given there). That's about 2^265. Now assume we would build a classical computer which stores one (classical) bit in every atom of the whole universe, then our universe-sized classical computer would have 2^262 Bytes of memory. This would be just enough to emulate a quantum computer with only 261 qubits. Now, take a key length of more than 261 bits, and you are completely safe from that universe-sized classical computer.
But not only the memory requirements scale exponentially, also the calculation time does. Given that the simple brute-force algorithm for factorization also has exponential time, I guess that bute-force would probably consistently beat an emulated quantum computer.
However, if someone built a real quantum computer with 261 qubits, he'd just need 261 atoms for storing the state (assuming 1 qubit/atom), and the calculation time would be far from exponential.
The Tao of math: The numbers you can count are not the real numbers.
So what you're saying, basically, is that you can't tap into quantum encryption without destroying the communication/ randomizing the bits in the process and that the nsa isn't THAT far ahead of current public research and that , oh hang on
Mongrel News all the news that fits and froths
Even if it is untappable, wouldn't it be vulnerable to a man-in-the-middle attack?
Before you'll know it the will be another hot-or-not spinoff called "is my cat dead-or-not" and it will be a bunch of blank pictures.
I don't get it.
This is the point. We're not talking about 'engineering'. This is physics. Well they may had discovered the 'yellow holes' in universe, and nobody knows that, or whatever. Anyway, even in the atomic bomb project, which was really a huge and secret one, the physics of it was universally known before they started building paloa lto. The can be as far as you want in 'engineering', but what is needed here is physics, and is much more profitable for them to keep their ears open till some discover shows up in the public scientisc community, and use it, and put zillios of engineers on it.
Still, a quantum computer turns crypto back into an arms race again.
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, which aren't prone to cracking by quantum computers, but which are less practical to use.
If quantum computers come out, then RSA is basically dead. Sure, you'll be able to use 1 million bits, for a few years, until somebody adds a few more qbits to their machines and improves their implementation. It could potentially lower the utility of crypto in general unless you're protecting a secret for only a few years.
Just a thought, maybe off-topic. I think articles like this one show the inherent flaw in anti-circumvention laws. While the american government says "if you put a lock on something it's unlawful to break it, develop something that breaks it, tell someone how to make something that breaks it etc. etc." we're all seeing where technology is going: quantum computing (sorry if this term is not the right one, have mercy, I'm italian, I mean the ability to compute using quantum mechanics principles) could very well break any kind of lock we know today. This is more proof that high-level, modern technology and copyright/anti-circumvention laws can't possibly coexist as long as copyright has the form and shape it has today. Either laws change or technology stops. Sorry if this comment was too much off-topic.
No, what he's attempting to do is describe entanglement - the presently baffling feature of quantum mechanices. As Heisenberg would tell you, any attempt to measure the state of a photon (an entangled pair of a photon in this case) will in fact alter the state of the photon itself and consequently sound an alarm bell if the data (many photons!) is corrupt at the other end. However, a sub-atomic group in Paris - ENS- have made progress in findinf ways to not measure the magnitude of a photon, but rather measure the phase shift of tiny rubidium rods as they pass through a photon. This still makes a change of course but a change that is even more difficult to detect! It's fascinating stuff and arguably the future of communication and computing, and who knows even replication...
What I meant was, what's the point if I can just cut the fibre and put a transmitter/receiver pair in the middle?
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.
Is it possible to detect whether or not something quantum-encrypted is being transmitted? There's plenty of information you can garner from a transmission based on the start and stop time, frequency, source and destination, duration, etc. - Scott
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 if QCs do arrive, that doesn't mean quantum key distribution will take off as well. As you said, it will be a whole lot cheaper and just as effective to ship a storage device full of symmetric keys to whoever you're communicating with. RSA and quantum encryption are independent technologies; the downfall of one will not necessarily lead to the rise of the other.
Democracy is two wolves and a sheep voting on lunch.