Quantum Computing Regulation Already?

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. "

Comments

Setec Astronomy

[TripMaster Monkey]

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):

A quantum computer gets its power by taking advantage of certain quantum properties of atoms or nuclei that allow them to work together as quantum bits, or "qubits," which serve simultaneously as the computer's processor and memory . By directing the interactions between qubits while keeping them isolated from the external environment, scientists enable a quantum computer to perform certain calculations, such as factoring, exponentially faster than conventional computers. When factoring large numbers using a conventional computer, each added digit roughly doubles the time to find the factors. In contrast, the quantum factoring time increases by only a constant increment with each additional digit.

This breakthrough completely renders useles the concept of the so-called one-way function, 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

[Garse Janacek]

This breakthrough completely renders useles the concept of the so-called one-way function

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

[Weezul]

Actually, there is some sort of result which shows that quantum computers can invert a function given as a quantum black box faster than any known classical algorithm. I think that like 8 years ago, when I read up on quantum computers, this algorithm was the ONLY speed up which was provable with lowerbounds, i.e. factoring might still be easy on an ordinary computer, but inverting a black box provably isn't. BUT the catch is that this result only provided a polynomial improvment (square root?) where as all the exciting stuff like factoring was exponential.

Re:Setec Astronomy

[Anonymous Coward]

Wrong. There are several public-key encryption schemes that don't rely on the difficulty of factoring large numbers. One example of this is ElGamal ecryption (http://en.wikipedia.org/wiki/Elgamal), which is based on the discrete logarithm problem. As far as I know, quantum computing is not yet known to provide any benefits in solving this problem; hence ElGamal encryption is still secure (for now).

Re:Correct me if I'm wrong, but...

[spot35]

Sort of. There is a branch of Quantum computing that will detect any eavesdropping called Quantum Cryptography. As soon as the eavesdropper is detected, whatever they see is rendered useless by the uncertainty principle (I think ... someone more intelligent than me will probably explain it better)

Re:Don't know a lot about cryptography, but

[Anonymous Custard]

As someone posted above...

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:On Paper?

[Jerry Coffin]

Or even on silicon!

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 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.

Re:Question About Discrete Logarithm

[TripMaster Monkey]

Found this snippet here:

A major breakthrough in understanding the power of quantum computers came in 1994, when Shor showed how, with a quantum computer, one can factor large numbers using a number of computational steps comparable to the number of steps needed to multiply two numbers. In other words, if we allow quantum computational steps, we can factor efficiently. Many public-key encryption systems in use today require that factoring large numbers is exponentially harder than multiplying. That is, we need that encoding the information is roughly as easy as multiplying, but cracking the code is exponentially harder and thus infeasible. Another widely used class of public-key encryption systems assumes that finding discrete logarithms in various mathematical groups is hard, but Shor also came up with an efficient algorithm for finding discrete logarithms. This algorithm can easily be generalized in order to crack any of the discrete logarithm based cryptographic systems. Shor won the 1999 Godel prize for this work. His factoring algorithm was the topic of his first distinguished lecture.

Looks like the algorithm has already been found...just waiting for the hardware to run it on at this time.

QC can also heal

[Anonymous Coward]

Someone else alluded to this, but I'll add to the picture:

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 are some more interesting security mechanisms that are actually promised by QC; perfect protection against Man-In-The-Middle attacks for one. If you send a message as a quantum state, and someone reads it on the way to its destination, then it is intrinsically changed, and so when that guy tries to pass it on, it will be garbled.

So Banks will set up quantum communication channels, and if anyone tries to tamper with them, both ends will know immediately and know to safeguard data that was discussed during the compromization period until a clear connection is established. I wouldn't be surprised if this sort of 'perfect communication' isn't more critical to the government's interests in QC, because it makes covert message interception impossible.

It's not all sponge-cakes and panzies though, because the internet is primarilly an electronic system, it will take a while to switch over to 'quantum-secure' mechanisms, and until then, your fancy-shmancy SSL is compromised.

Re:Lots of incorrect information

[DMiax]

Quite right in all the point, except one: factoring is polynomial in QComputing, so you go from time 2^N to time C*N^2. Of course C will be very high in the first times... The hard work is realizing a scalable system, as you say...

Re:Correct me if I'm wrong, but...

[Anonymous Coward]

since nobody answered the actual question, yes this can be used to make better encryption.

Quantum computers allow exponential time algorithms to be solved in constant time. They do NOT allow super-exponential problems to be solved in constant time.

So O(a^b) -> O(n). O(A^b^c) -> O(n^m).

I don't know of any super-exponenetial encryption technique, but it possible in theory to develop such an algorithm.

You might end up with a algorithm that takes exponential time to make a key, but super-exponential time to decrypt it. Then you would need a quantum computer to encrypt the data, but could not decrypt it with any known method.

Quantum Entanglement would be a better way to go:
http://en.wikipedia.org/wiki/Quantum_cryptography