Quantum Computing Regulation Already? 238
RMX writes "A new CNet article discusses the possibility of regulating quantum computing.
We already see our top tier US VCs investing in Quantum computing companies outside the country. Apparently the feds seem to think regulating the amount of technology that can be sent overseas will make the US safer." From the article: "Only rough prototypes of quantum computers presently exist. But if a large-scale model can be built, in theory it could break codes used to scramble information on the Internet, in banking, and within federal agencies. A certain class of encryption algorithms relies for security on the near-impossibility of factoring large numbers quickly. But quantum computers, at least on paper, can do that calculation millions of times faster than a conventional microprocessor. "
Catch 22 (Score:5, Funny)
Re:Catch 22 (Score:2, Funny)
(Prof. Farnsworth): No fair - you changed the outcome by observing it!
Re:Catch 22 (Score:2)
Re:Catch 22 (Score:2)
On Paper? (Score:5, Funny)
Wow, imagine what they can do on silicone!
Re:On Paper? (Score:5, Funny)
Though what they can do with silicone may be much more, uh, er, entertaining.
Re:On Paper? (Score:5, Informative)
I know you meant this humorously, but it's probably worth noting that in reality, the quantum computers that have been built are NOT in silicon either -- in fact, they're not really based on semiconductors at all.
They're currently (basically) a test-tube full of specially constructed "soup" of (for example) hydrogen and carbon-14 (yes, the same that's used for carbon dating) suspended in chloroform. The results from this are read using an NMR (Nuclear Magnetic Resonance) machine, essentially like those used in medical imaging.
Unfortunately, even the people doing research in this direction [qubit.org] admit that there's little likelihood of building NMR based quantum computers of more than a few (half a dozen or so) qubits, which is really too small to do much -- and the NMR-based reading of the results is also quite slow. OTOH, while they may not be particularly practical, they have managed to do real quantum computation this way.
--
The universe is a figment of its own imagination.
Waiter... (Score:2, Funny)
Which leads to the inevitable: Waiter, is that a Quantum Computer in my soup? I ordered noodles.
Re:On Paper? (Score:2, Interesting)
Silcone? Is a silicone computer like some women? They're fun to watch whilst they're running? (think about it)
{back to quantum computing}
So...exporting it is the only way to regulate it?
When PGP went on the Thou Shalt Not Export List early in its life (thirteen? fourteen? fifteen? years ago), I always imported my copies. That meant either: 1) someone from the US exported it; or, 2) someone outside the US imported it. I'm not sure you can prove someone accidentally left a copy unprotected on a server
Re:On Paper? (Score:2)
With quantum computing you may get a third option - the US does not emerge as the world leader in the field. These regulations sound a little cocky to me.
Re:On Paper? (Score:2)
He [msn.com] did !
QC can also heal (Score:2, Informative)
Quantum computers can compute on an entire state-space simultaneously, so in the first iteration of a brute-force decryption algorithm, they will find the values that satisfy the result.
If you double the number of bits, you square the size of the state-space, but you only double the size of one iteration, so it is an ineffective way of stopping quantum cracking. Because decryption time on a QC will always be proportional to encryption time.
But there
Re:On Paper? (Score:2)
Re:On Paper? (Score:2)
Re:On Paper? (Score:2, Funny)
Difference between silicon and silicone? Upgrade your computer with the former. Upgrade your old lady with the latter.
Re:On Paper? (Score:2)
Plus I'm pretty sure that the purpose of most breast implants is to increase size. Quantum-sized breasts just don't sound like they'd be very popular for some reason...
It won't be surprising when it's illegal to own (Score:5, Interesting)
Does this mean that I shouldn't bother with a 28 character bank password, since it's all going to be moot anyway?
Re:It won't be surprising when it's illegal to own (Score:2)
Any password - better than - no password
28 character password - better than - any password of shorter length.
29+ character password - better than - 28 character password
That's not to say someone driven enough couldn't crack your password, you just make it somewhat harder to
Re:It won't be surprising when it's illegal to own (Score:2)
I don't think it will keep it out of the hands of criminals, but it will make it possible for police to take it away from criminals when they are caught with it. It might also slow the spread of the technology to bad people, so that the slow government can keep up.
Re:It won't be surprising when it's illegal to own (Score:2)
Except for the bad people in the government
Re:It won't be surprising when it's illegal to own (Score:2)
While 28 characters is probably excessive for most people, I think that my bank limits the password to 13 characters, the answer to your question is no for the following reasons. First, the system which is accepting the password, i.e. the online banking website or the ATM, can only accept passwords so quickly so no matter how fast your quantum computer can generate the combinations they can o
Setec Astronomy (Score:3, Informative)
The summary is a bit fuzy on the details, but here's a telling excerpt from the IBM research article on their quantum computer (link here [ibm.com]):
This breakthrough completely renders useles the concept of the so-called one-way function [wikipedia.org], a function which can be executed in polynomial time, but whose inverse can be executed only in exponential time. Basically, this renders just about all public-key cryptographic functions obselete on one stroke.
Interesting times...
Re:Setec Astronomy (Score:4, Informative)
Not at all -- if you believe that quantum computers will actually work well enough to factor in the real world (many computer scientists don't -- the degree of precision required would be many orders of magnitude greater than any observations of any physical laws have ever been in a real experiment), you're only talking about making some particular one-way functions (in this case, factoring) useless.
In fact, part of the power of quantum computing is that (even without the somewhat less plausible factoring algorithm) we would have real secure encryption -- secure based not on the assumption that factoring is hard (which it may not be), but that quantum physics is true (which it may not be, but a lot of people seem more comfortable with this assumption, at least as far as cryptography is involved).
Re:Setec Astronomy (Score:5, Insightful)
Quantum cryptography isn't really cryptography - it is instead a method of transmitting data between two points without relays which can allow sender and receiver to determine whether the transmission was intercepted. In practice it can be used for symmetric key exchange (such as a one time pad). If the key wasn't intercepted you use it, if it was then you just keep trying until the interceptor (or you) gives up.
The problem with quantum crypto is that it requires a direct transmission of photons from Alice to Bob. You can't have a relay station in-between, unless you are willing to guarantee its security (any relay station would allow for interception of the signal when it isn't entangled - which cannot be detected).
The bottom line right now is that it only works for very sensitive communications via line of sight or fiber optic. Most people submitting their credit card numbers to a website don't have a direct fiber optic line without retransmission between them and the merchant.
My guess is that quantum crypto won't ever prove to be very practical for general use - except maybe in space (where lines of sight extend much farther).
Re:Setec Astronomy (Score:2, Interesting)
Not true: Google for "quantum repeater". [google.com]
Re:Setec Astronomy (Score:2)
I was not referring to quantum cryptography. I was referring, just as an example, to lattice-based cryptography, which is completely classical. And yet we don't know how to break it using quantum computers.
Re:Setec Astronomy (Score:2)
Re:Setec Astronomy (Score:2)
This is not true. The fault-tolerance threshold--the error threshold below which an arbitrarily long quantum computation can be performed to arbitrary precision with only polynomial overhead--is estimated to be anywhere from 10^-1 to 10^-7, depending on the physical system and the error model.
Now, 10^-7 is pretty hard to reach, but we most certainly have
What's your background? (Score:2)
Re:Setec Astronomy (Score:3, Insightful)
Settle down, and don't believe the hype.
So far, we don't know of any efficient quantum algorithms for solving the main problems on lattices. One-way functions and encryption schemes can be based on these lattice problems, too.
There is no general result that says "quantum computers can invert all functions." One-way functions are still believed to exist, even in the face of quantum computing.
Re:Setec Astronomy (Score:3, Informative)
Re:Setec Astronomy (Score:2)
However, QC is faster than you state:
To make a long story short, the number of steps to do factoring on a quantum computer is approximately the square root of the number of steps required on a classical computer.
It's must better than that: after all, if what you say is true, then factoring would go from subexponential-time (on a classical computer) to
The reality is that there is no general "speedup factor
Re:Setec Astronomy (Score:2)
You're abslutely right -- I'm not quite sure what I was thinking when I said that, but it was clearly wrong. My only excuse is that I must not have been entirely awake. I apologize.
--
The universe is a figment of its own imagination.
Re:Setec Astronomy (Score:2)
Funny you should mention the discrete logarithm problem, given the fact that this scheme has suffered the same fate as factoring [utoronto.ca].
From the article referenced in the link:
Why can't other countries develope their own? (Score:4, Insightful)
Re:Why can't other countries develope their own? (Score:5, Interesting)
Under the completely unresearched assumption that the U.S. currently has some lead in quantum computing, all restricting it can do is give some lead time before others catch up and then we have the same situation as we had with cryptography.
Though the article doesn't make it clear that export restrictions are going to be the main thrust. If they regulate quantum computers within the U.S... well, I can only imagine the justification (teh terrorists crack your bank account!), but the detrimental-to-U.S.-interests aspect will actually be amplified as the rest of the world uses the useful tool and the U.S. forbids it.
With any luck there will be an unexplainable outbreak of intelligence and sincerity in the government (or the appearance of such caused by commercial lobbyists) and no significant regulations come to pass.
Re:Why can't other countries develope their own? (Score:3, Funny)
PATENTS!!!
If you outlaw quantum computing (Score:3, Funny)
Re:If you outlaw quantum computing (Score:2, Funny)
"If you outlaw quantum computing,
only outlaws might have quantum computing."
Re:If you outlaw quantum computing (Score:2)
"If you outlaw quantum computing in US,
only outlaws might have and europeans&asians will have quantum computing."
And ofcourse we will kick the ass of american teams in distributed.net competitions!
ps. has idsoftware revealed when it's going to release QuantumDoom ?
Pah! (Score:4, Funny)
Like the Kansas Board of Education, we need to proactively discard these so-called "scientific theories" and go back to Intelligently Designed machines, like the abacus.
Re:Pah! -- Yes, it can't be real! (Score:3, Funny)
Yes, anything we can't see ourselves probably isn't real and can only be explained by a higher power. Nobody has seen 4 billion years of Evolution actually happen, so it probably didn't.
And everyone who looks at a Q-bit sees something different!
And if this works both ways? (Score:2)
Correct me if I'm wrong, but... (Score:4, Interesting)
Can't that same concept be applied to encrypting the data as well? I mean, if it can break current encryption easily, wouldn't the logic here be that it's capable of an encryption that would take even a quantum computer decades to crack? Or am I missing something here?
Re:Correct me if I'm wrong, but... (Score:4, Insightful)
Actually, no. The breakthrough here isn't just a much faster computer...if that was the cse, you'd be right...just increase the length of your encryption key to compensate. The breakthrough here is a computer capable of solving formerly exponentially-difficult functions in polynomial time, rather than exponential time. It completely rewrites the rules.
Re:Correct me if I'm wrong, but... (Score:2)
Specifically, the algorithm for factoring faster is Shor's [wikipedia.org] algorithm, although it's kinda tough to understand without some physics background.
Re:Correct me if I'm wrong, but... (Score:2, Informative)
Re:Correct me if I'm wrong, but... (Score:2)
Re:Correct me if I'm wrong, but... (Score:2)
The difference isn't a factor of 10 or 20 speedup, it's going from taking a number of seconds equal to all of the protons in the universe, to something like, the number of nails in the bin at HQ.
Think in these terms. If modern crypto (not an expert on crypto) takes 2^n seconds to crack on a conventional computer, it'll take n seconds to crack on one of these.
Re:Correct me if I'm wrong, but... (Score:2)
Re:Correct me if I'm wrong, but... (Score:2)
Are you sure that it would be linear time, and not polynomial time? There is a difference. For instance, linear time is always O(n), but polynomial time could be O(n^10) or more. If, for instance, cracking the key turns out to be O(n^3) (still polynomial time, but not linear time), the difference in time between a 1024-bit key and a 1-bit key would be roughly 1 billion.
Re:Correct me if I'm wrong, but... (Score:2)
QC in the US Only?? (Score:2)
What will they do if 3 researchers are working on this in the US,
Re:QC in the US Only?? (Score:2)
Re:QC in the US Only?? (Score:2)
That this comes out now suggests the NSA just got their first working model online. Maybe they can help the Brits so they don't have to hold people for 90 days without charge so they can fish in their hard drives.
Re:QC in the US Only?? (Score:2)
Re:QC in the US Only?? (Score:2)
Then the Fed will give/con/armtwist the researchers US Citizenship and then impose US Law on them.
They've done it before with Gerald Bull.
Re:QC in the US Only?? (Score:2)
The fact that the government is considering regulating the technology now does make me wonder whether the NSA, who has been throwing large sums of money at the problem for years, might not be farther along in developing a quantum computer than other people know.
Export restrictions has been a wrongheaded tack (Score:3, Insightful)
The solution, as it is in most cases of security, is to rely on methods that are simply and thoroughly uncrackable. As we saw the other day, the time to determine the factors of a 640 bit number is 5 months. As computers get faster and algorithms get better, that time will diminish. Once quantum computers arrive, those encryption algorithms will be obsolete.
So use encryption which is not vulnerable. Don't stop the free flow of information to hide your weaknesses.
Craziness (Score:2)
1. Quantum computing ends up destroying public-key encyrption, making online banking impossible.
In this case, what Congress is saying is that they want to shield US banks from having to switch back to physical security and authentication as soon as possible, and instead, want to allow banks a grace period, where determined criminals have an opportunity to steal citizen's money.
2. OR, online banking is still feasible
In which case, this was no big d
Re:Craziness (Score:2)
'Cause Prohibition *Always* Works so Well! (Score:3, Funny)
Re:'Cause Prohibition *Always* Works so Well! (Score:2)
How about this (primality-testing in O(1) - on a quantum computer, at least)?
I didn't test it, but it's pretty much just ripped from the Quantum::Superpositions [cpan.org] docs, so I suppose it should work, modulo any bugs I might have introduced.
You can't keep the cat in the bag (Score:4, Interesting)
Re:You can't keep the cat in the bag (Score:3, Insightful)
And what does "combinatorial ba
Re:You can't keep the cat in the bag (Score:2)
Nothing like regulation to kill something (Score:2)
Good luck with that (Score:4, Insightful)
It's the PGP Retardo Fed Fest all over again. Technology advances, you can only keep a secret for so long, especially depending on potentially hostile foreign governments making the devices or support devices. Particularly when those same potentially hostile governments have massive databases of information on US citizens conveniently supplied by US businesses outsourcing their data management.
Straining out a gnat while swallowing a camel. Deal with it and move along.
Re:Good luck with that (Score:2)
It is stupid for the outsourced countries to think that they suddenly became techonology leaders because they have hundreds of engineers wo
Re:Good luck with that (Score:2)
Nothing New (Score:2)
They are just trying to stay ahead of the curve this time, instead of after the horse has left the barn.
Paging Gen. Turgidson ... (Score:2)
Gen. Turgidson [shouting] : "We must not allow a quantum computer gap!"
I'm just waiting for the good doctor to try to restrain his right arm. Damn that was a funny (and thought-provoking) movie. Purity of essence ...
-paul
Doesn't even take a quantum computer (Score:2)
Re:Doesn't even take a quantum computer (Score:2)
Major factors influencing the U.S. edge (Score:4, Insightful)
The result of this, the dot-com bubble bursting and perhaps a few things I can't think of at the moment, there is a massive brain-drain in the US. According to what I've read, there are fewer people signing up for technical careers. Meanwhile, in other countries, they are building their intellectual base to the point of being emerging superpowers.
I remember the U.S. encryption export laws (are they still on the books?) and the supposed reason they were put into place. (Was it to prevent competing nations from getting our superior encryption technology or was it so we could charge people with an additional crime for trafficking in secrets using a more secure tech?) I guess it's not a really good parallel, but I do beleive this type or restriction is a bit too little and too late. The genie is out of the bottle. And unless some serious focus on science, technology and research is made, I believe the U.S. will have lost its last great commodity -- intelligence.
Apocalypse Now (Score:2, Flamebait)
Re: (Score:2)
Re:Apocalypse Now (Score:2)
You are the one projecting your own beliefs about Islam, as conveniently received from your local propaganda outlet (whether US corporate, Wahabi or both). Islam means "submission", as in "submission to the will of
Export regulations (Score:2)
One Giant Assumption (Score:4, Insightful)
In a world of outsourcing to other countries, as well as the fact that the USA doesn't have a monopoly on brain power, this whole idea could be rendered meaningless the moment someone decides to build their Q-puter[tm] in any other country with less onerous regulations!
Power to the People (Score:3, Interesting)
Instead, our Congress and White House are run by paranoid morons whose musclebound response to any crisis is to suppress and destroy. Which is just making us less safe, discrediting us, and funding our enemies and rivals. Fortunately, it's only 12 months until 1/3 of Congress is up for election. If we get rid of these dangerous morons, maybe we'll have a chance to keep an American brand on the future. Because the "Middle Ages" is a moving window that America is rapidly coming to define.
Quantum exporting (Score:2)
Assuming that the definition of exporting is shipping the object across the US border, there shouldn't be much of a problem. Just tell the authorities that the computer went from the place of manufacture to the foreign country without passing through the space between
No Moore's law for trite quantum hype tripe! (Score:2)
Calling All Encryption Experts (Score:2)
Accepted, although yet to be demonstrated in the real world on actual keys, that quantum computing may well easily compromise public key encryption systems that rely on the one-way difficulty of factoring the product of large primes. My question is, is AES (Advanced Encryption Standard) weakened in any way by quantum computers?
Perfect encryption already exists!!! (Score:2)
Now, many of you will say "There are logistics problems with one time pads that make them ineffective for things like ecommerce or cell phones etc.", and I agree. But banning the export of quantum computers isn't to protect ecommerce or cell phones... it is to protect high level diplomatic and military secrets. A U.S. embassy abroad can
When did progress become evil? (Score:3, Interesting)
However, now whenever we make progress, we try and chain it down as much as possible to avoid anything changing. The Internet and digital content is a great example. Inventing the equivalent of a global Library of Alexandria, where everyone has access to all information, and transferring and copying information from place to place was easy and cheap, should have been a cause for celebration. We should have all rejoiced that now humanity was free to share all its ideas and art with everyone on the planet. But instead, we get legal and technological attempts to hamper that ability as much as possible, because it upsets the status quo. I imagine the same thing would happen if someone had come up with "replicators" that could feed and clothe the needy - they would instantly be controlled and limited so that they didn't disrupt the way things were, despite the obvious boon to humanity.
Now it's the same thing with quantum computing - we've eliminated another scarcity (processing power) and instead of celebrating the freedom we go about trying hard to restrict it so that it's like we never made the breakthrough.
There's a part in 1984 where it's revealed that the endless war is really just a means for burning through the surplus of materials and labor that a technologically advanced society has, so that people can be kept poor and overworked. While I doubt there's a conspiracy behind these current restrictions (besides the conspiracy of the status quo) I think the parallels are interesting.
This, to me, is the number one compelling reason for progress - so we can get rid of all the people whose power depends on keeping us from progressing.
Re:What will the impact be on research? (Score:3, Interesting)
Re:What will the impact be on research? (Score:2, Interesting)
Unless the quantum computer research is regulated in a similar fashion (ie. basically setting up a secret "science town"), the peer-review process will suffer from the lack of contact with t
Re:What will the impact be on research? (Score:2)
Yes, I think you're right. What's more, I don't think it could happen again unless such a major event compelled scientists to flee Europe...
The results (very notable and solid independent discoveries
Re:What will the impact be on research? (Score:3, Insightful)
Re:What will the impact be on research? (Score:2)
Re:What will the impact be on research? (Score:2)
Those Belgians...they're so damned evil...after all, they share a border with the Dutch. ^_^
Re:Don't know a lot about cryptography, but (Score:3, Informative)
For current computers, adding a bit to the key makes it twice as hard to crack; so it's 2^n hard to crack where n is the number of bits.
For quantum computers, adding a bit to the key only adds a constant amount of time it'd take to crack.
128 bit encryption is 2^64 = (18,446,744,073,709,551,616) as hard to crack as 64 bit.
But with quantum computers, 128 bit would only be 128/64 = 2 times as hard to crack as 64 bit.
Re:Don't know a lot about cryptography, but (Score:2)
Re:Don't know a lot about cryptography, but (Score:2)
Re:Don't know a lot about cryptography, but (Score:2)
If they keep the qbits isolated from the outside world, as is required, how can we know what they are?
Re:Question About Discrete Logarithm (Score:3, Informative)
Found this snippet here [utoronto.ca]:
Re:Why dumb it down? (Score:2)
This isn't true, and is the exact point of public key cryptography. The encryption keys are public, but observers still can't read encrypted data since secret private keys are required to decrypt.
I think you're referring to a "man in the middle" attack, where you intercept one party's public key, then send your own public key to the intended recipient. You get any responses, which you now decrypt, save your copy, re-encrypt
Re:What, can't we have our Q-PlayStation at home? (Score:2)
Re:Lots of incorrect information (Score:2, Informative)