Slashdot Mirror
Quantum Security
Triode writes "In this months issue of Physics Today there is a very
interesting read entitled 'From Quantum Cheating to Quantum Security' which delves into encryption. Talks about ads and
disads of popular encryption (keys, public keys, DES etc), the
size of current encryption and why it is not (theoretically) good.
Quantum computers could make breaking our current methods of encryptoin easy, so we need to start now with methods of encrytption that would not be so easy. A pretty basic example of a implementation of the B92 protocol is given using a single photon source over a 48km optical fiber. Worth a read.
Check it out at the AIP website."
This is the best walk-through of quantum encryption I've seen, and one of the few that points out the flaws and unknowns which could plague a completed system in the real world. And depressingly enough, there is a note on the Physics Today main page which reads: "All editorial content from the magazine is available on the Web. In the near future, restrictions will apply." As a selfish site junkie, I hope this only means NYT-style registration, not WSJ-type subscribers-only service.
University of Montreal with Gilles Brassard
or
McGill University (also in Montreal) with Claude Crepeau
Both have fairly well known Theoretical Cryptographs in their CS departments that do research in Quantum Cryptography. However, the Quantum physics part is mainly left up to you; That is: you don't need a College Degree in physics to do Quantum Cryptography (some would say it would help). Quantum Cryptography at its core is still only algorithmics like Classical Cryptography but based on a different set of tools then what you're used to.
Mr. Brassard just finished writing a book on quantum cryptography; I'm not sure but I believe it's out on the market currently.
Your second question was to whether or not its more suited to a Math major. Both of these gentleman will tell you that Maths are a big part of any crypto. Having a strong background in math is definitively a plus; in the last few years, doing a double major Math-CS or Math-Physics has been the typical path for people that work with them.
Your third question was to whether or not there were job openings with such requirements. The answer is: Yes, in academia; More or less in large companies' research labs (i.e. IBM labs, Lucent, MS, NEC, etc.); pretty much No anywhere else (there might be a few expections.
However, doing grad studies in CS can hardly be considered a waste of time and you should have no problem finding a job after. Whether or not you'll still do Quantum Crypto is another question.
For what it's worth, they both also work or have worked on other fields of crypto such as Zero-Knowledge proofs (nothing to do with the company that ripped the name from this field of study) and other VERY theoretical aspects of crypto.
Hope this helps.
It just means a possible end to current security. Maybe this will force us to create a better form of security that we overlooked because the encryption method was so easily the first step.
The Idea.org
A system can only be cracked if it is economically feasible. A cracker is not going to spend money to crack a system, the more expensive things get, the smaller the chance of a crack occuring.
For example,
using a quantum computer, all encription (below a certain level) becomes obsolete. However the cost and knowledge of maintaining a quantum computer, is really very high. An NMR machine, several SUN computers, and three people (a full time technician, a full time PhD chemist and a full tiem PhD engineer/physicist). It's very pricey, I know there is an NMR where I work doing materials research and we are trying to get a quantum computer up and running by Summer 2001.
At the moment only 5 bits can be used, it's going to be quite a while before a 128 bit computer is produced. So, (for a decade anyway) we are not going to see home quantum computers.
In fact Quantum computers will be crap at everyday tasks and practically useless to most people, so it's unlikely we'll ever see them on the shelves at K-Mart.
I am a man, not a toy.
It isn't as bad as all that. According to the article, a quantum codebreaking machine will have to perform a computation of order O(sqrt(n)), where n is the number of possible keys, in order to solve the problem. Classical brute-force searches are, of course, O(n)
This is a quantum method of breaking DES encryption. The method for breaking RSA and other schemes based on factoring being difficult offers an improvement from exp(O(n^1/3 (log n)^2/3)) to 0(n^2 log(n) log(log(n)) ) which is gigantic.
"If computers that you build are quantum,
Then spies everywhere will all want 'em.
Out codes will fail,
And they'll read our email,
Til we get crypto that's quantum and daunt 'em."
(Jennifer and Peter Shor)
:wq
For anyone who wants to know what the EPR "paradox" is, or any other basic information concerning quantum encryption, I suggest you check out the comments to one of the past articles on quantum computing or quantum encryption, such as this one.
Otherwise, we'll have the usual ten people making misinformed comments being responded to by the usual ten karma whores writing the usual ten paragraph responses on "spooky action at a distance" and the Schrodinger Cat paradox.
Or better yet, pick up a good book on the subject.
Oops, bad copy-paste! That's the link I intended; sorry to all others for the misunderstanding. While we're at it, there's also this one; while Thompson certainly doesn't seem to have "what it takes" (as Trevor Marshall does), her site is also quite interesting.
To the editors: your English is as bad as your Perl. Please go back to grade school.
UBU
The net effect is that a quantum computer in the hands of an eavesdropper halves the effective keylength - a 128-bit key is reduced to 64 bits of effectiveness. 64 bits is, of course, not enough security to defend against government-level surveillance resources, but all that has to be done to solve the problem is to increase the keylength to 256 bits.
One of the requirements for the AES candidates was that the algorithm support 256-bit operation. Rijndael, the heir apparent to DES, does support 256-bit operation modes.
I've always argued this point. Seriously, aren't we going a bit overboard. I can understand protecting nuclear secrets and stuff like that, but having infinity-bit encryption so Alice can protect her porn files is just plain silly.
I think privacy activists walk a fine line between "practical" and "paranoid". Yes, I like encryption. Yes, if it's something I don't want others to read, I click the little "encryption" box in NTFS5 to enable it. But would I really care if they read it? I mean, honestly?
The only people I think truly need quantum encryption are doctors, lawyers and people working with hazardess materials. Everyone else can do just fine with public keys. (And if you're going to tell me that the government would actually use quantum computers to break into Joe Schmoe's porn files, you have another coming.)
- I don't care if they globalize against free speech. All my best free thoughts are done in my head.
Cryptography is essential to our future.
When you purchase something online, chances are when you enter your credit card number, it will be sent encrypted. When people want privacy of their online sessions, encryption is necessary. In the age of being able to get anyone's phone number across the nations, to send someone a document in under 15 seconds; that is sitting in Europe. Where some child sitting in front of a $400 computer can cause millions in damage; can keep himself anonymous, and out of trouble; increased security in our world is essential.
We as humanity are losing trustworthiness, which in return makes cryptography an everyday necessity. Humanity is evolving, we are growing more and more controlled by wealth and money, instead of human life. We now need cryptography and we have not scratched the surface of what it will become.
When we as a culture use money, as we do in today's world; we need a way to keep our numbers secure, to keep our money out of unwelcome hands. Encryption is a need we must have now, and before new technology comes out we need to guarantee the security of current encryption, and we must welcome the changes to it when the need arises.
Quantum Cryptography will shatter our current methods, so we must develop better methods, today, for tomorrow.
Now are you ready for it?
Grover's Algorithm is a method for searching an unstructured list, it offers an improvement from O(n) to (O(sqrt n)) over classical computers.
Shor's algorithm is a quantum algorithm for factoring integers. It is able to do this in O(n^2 log(n) log(log(n)) ) whereas the best classical method for doing so is the number field sieve which takes exp[O(n^1/3 (log n)^2/3] which is pretty impressive.
Breaking DES encryption involves just brute force looking for the keys so a quantum computer would use grover's algorithm here, but breaking RSA (which is probably what your encryption software uses) reduces to the problem of factoring integers and so Shor's algorithm is what has all the white hats worried.
:wq
...would be to double major in something like EE or CSE and quantum fizzicks. Has anyone ever done this? Were you successful in getting a job that related to both fields? I know that the two departments at my school (Univ. of Washington) would basically not cooperate to let me do this. Maybe this cryptography application would be better suited to a math major - that might be easier to combine with a physics degree.
It seems that half of the world is trying to develop new methods of encryption, wheras the other half is busily trying to break them.
Wouldn't it save everyone a whole lot of effort if everyone sent everything in clear?
I think that having the administrators definately helps out. We generally have to go talk to people in other faculties(eng,math) since they are the ones making the decisions. I think the main reason for this is that in science they are desperate for more students while in eng and math they are constantly over-cramming their classes. I know for a fact that most of the electives in physics are made to attract students from other departments - just so we can get more funding based on enrolement. I wonder if it's like this in most comprehensive schools?
I know that the math faculty definately looks down on letting people into their 'priviledged' classes - most of the cs courses offered to non-mathies are watered down versions of the honours classes and don't really get into the real interesting stuff. I know they offer a CS minor for us but it seems like a complete waste of time as far as I'm concerned - I know lots of people in physics are doing it, but it doesn't go into the real interesting theoretical aspects of computing, just the typical database management/buisness aspects of computing that will let you get an IT job or something like that more easily (kind of like general level high school classes). They used to allow people to do a double math/physics major, but now that's pretty much gone down the tubes, I only know one person who's doing a minor in applied math in our class and it definately has disrupted his schedule.
As for the summer terms it's pretty sad. We have 2 in a row in physics co-op and last summer I ended up pretty much wasting 2 classes on mundane subjects since I'd allready taken anything else that was relatively interesting. Getting into eng classes is pretty hard - the task of equating pre-requisites is very difficult, but the scheduling problem is the worst. Since they only offer 1 of each core physics class a term we don't have any option of juggling our table around, so often the only engineering courses that would be of use are inaccessible. One of the problems with our physics program is that it is engineered to just push us down the path to getting our BSc - our department is so streamlined now that it doesn't offer too many electives that go into inter-disciplinary topics - probably the only one that I have found interesting is the 3rd year computational physics class (P339), and unfortunately they don't offer anything higher, so I probably won't be taking any computational courses for the rest of my undergraduate degree.
UBU
Yes, but assymettric encryption does allow that the third party does not have to be present execept at the initial trusted event. This is important for applications that wish to trust someone, but cannot talk to the authority, because they are on a non-networked device, like a DVD player or a Coke machine.
-no broken link
This reminds me of a conversation I had awhile back with a fellow geek. He thought that new quantum computers would make an entirely new class of 'haves' and 'have nots', based on the ability to encrypt your information
In a nutshell, once these computers are actually in production, the government will be the first to have them. No current X86 (or such) system will be able to make an unbreakable cypher anymore. No countries, no indivduals, or such. The only people able to make such will be those with these quantum computers, which will most likely be regulated.
The entire idea behind 'privacy through encyrption' will be a thing of the past. True, most crackers won't have access to this equipment. But the NSA, CIA, etc will, and they will be albe to crack any encryption you can throw at it.
Maybe we DID take the blue pill. You wouldn't remember anyway.
The article states that a quantum algorithm has been written that will reduce the number of steps required to break RSA from O(N) to O(N^1/2). (That's from big O of N, to big O of root N).
:-)
So that means it could break a 2^56 bit key in the time that normal algorithms take to break a 2^28 bit key. But what difference does that make? My (admittedly old) copy of PGP quite happily does keylengths up to 2^2048 - so this quantum algorithm would reduce that to 2^1024. This is still a HUGE key. Taking centuries to crack, even on some machine that tries trillions of keys a second.
Or am I missing something? Let me know
--Remove SPAM from my address to mail me
Vintage computer games and RPG books available. Email me if you're interested.
Pr0n perhaps not, but there's plenty of people who have a legitimate and real need to protect themselves from intelligence gathering from governments, including the US government.
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
We could start by misspelling everything, thus making our communications harder to understand. Slashdot has employed this encryption method for years.
--
``Life results from the non-random survival of randomly varying replicators.'' -- Richard Dawkins
Quantum computers are NOT magic. Using Shor's algorithm you only get a sqrt(N) speed-up in cracking keys of symmetric algorithms. That means that 256-bit keys will be as secure against cracking on a QC as 128-bit keys on a classical computer. The article said this, but didn't spell it out clearly.
Quantum computers do not mean the end of classical cryptography. They may mean the end of asymmetric crypto, but that means that we wind up having to use trusted third party symmetric encryption a la kerberos. This is probably a good idea, anyway, because without a trusted third party there is no way to protect against man-in-the-middle attacks against asymmetric crypto anyway.
First of all, I'm not giving an "argument by Einstein" (chuckle). I'm not an Einstein-worshipper either, but I'm just wondering: what if the old fella was right where QM is concerned? Trevor Marshall and others certainly seem to think so. And if you dismiss these people's point straight away, merely because so many scientific geniuses of the 20th century developed QM, then you're the one who's pulling an "argument by Feynman" (or by Heisenberg, or by Pauli)...
Frankly, I never liked the Copenhagen Interpretation at all (it certainly justifies the name "quantum magic", and gives the entire scientific enterprise a bad name), and maybe all of QM is based upon a faulty foundation. Yes, it'd be a monumental error, but if there's ever been a community that could make it, it's today's physics community. (I've seen it from the inside; if you have too, you know what I'm talking about. The mutual reinforcing of dogma; the unwillingness to test, experiment, reformulate, or do anything that even smacks of real science; the lack of intellectual honesty; the cargo-cult science; the mental laziness; the rigid structure of academia which requires one to conform to the dogma to get respected, or even to be acknowledged at all; the general subscription to Bohr & co.'s distorted (not to mention depressing and counterproductive) idea of what science is... Feynman is certainly rolling on his grave - as is Einstein.)
To the editors: your English is as bad as your Perl. Please go back to grade school.
Sum things sint in plane tekst arnt readibble, evin withuot incripshun. Yer artikkel for exampil.
I just bought a drum of 50km of fiber optic and this evening i'll blow my tv's tube to get a photon source. The rig seems easy to set up for any decent overclocker d00d. :)
I will start a souceforge page for the project and if enough developers join soon we'll have: "ssh -c B92" and "ssh -c BB84"
--
1% APY, No fees, Online Bank https://captl1.co/2uIErYq Don't let your $$$ sit in a no-interest acct.
The law that gives the doubling time for the number of qubits on a single device is know as Qbert's law. It is based upon the quantum chances of Qbert making it to all the squares on the board and successfully avoiding all the nasty snakes and bad guys without leaping off the edge.
=P
There are a thousand forms of subversion, but few can equal the convenience and immediacy of a cream pie -Noel Godin
Current encryption is strong, but not infallible. Because of quantum mechanics, you would be able to write perfect public/private key crypto that is not interceptable. To the best of my understanding, quantum crypto has to do with sending photons with specific polarities across a pipe. It works because anybody who wants the information (photon) would have to bother the photon to get it's polarity. So getting the information messes the information and invalidates it(it would be coupled with message integrity checks and public/private key crypto)
As the linked article points out, the quantum methods mean you can guarantee the transmission is secure, but not a lot else. These cryptographic methods have all the security of other methods and then some. The only weakness (and I really mean only) is that the keys are still subject to theft if you aren't very careful.
Ever since I've been studying cryptography, poor Alice has been trying to talk to Bob without having that bitch Eve eavesdrop. Why can't Eve just let them be, for chrissakes?!? Then, as a side benefit, distributed.net would be able to redirect their efforts to something rather more worthwhile, such as looking for imaginary little green men.
On a side note, ever consider the possibility that Einstein was right all along and quantum magic really is bogus? If the linked-to people, currently disregarded by the scientific community as crackpots and throwbacks, end up proven right, that would be damned funny... "Hello? Yes, this is Mr Scientist Man, who is calling? Ah, the NSF? Yes, I know you've been giving us research grant money for the last 50 years to build huge particle accelerators and develop O(1) code-breaking for the NSA... you want to know why our prototype won't work? Well, it turns out that spooky action-at-a-distance is a measurement error, the Bell inequalities were never violated, and the universe is really fundamentally deterministic... sorry about that. See your money back? Not unless the NSF operates in the Bahamas too..."
It's like they say, nobody ever got fired for believing in Einstein...
One last thing... timothy, learn to close your italics.
To the editors: your English is as bad as your Perl. Please go back to grade school.