I believe Mr. Schneier was referring to symmetric cyphers, for which currently there are only improvements of O(sqrt(n)) from O(n). Public-key systems have been broken in polynomial time.
Ummmm.... NO. No matter how fast a CPU or how many of them you get, factorization/discrete log is still exponential. So you can factor a trillion times as fast -- just increase the keyspace by log(40trillion) or about 40 bits. Voila. Your encryption is now that much stronger. Of course it'll take longer to encrypt, but given your 40trillion CPUs this shouldn't take very long at all.:) The key point of quantum computers is that they change the time complexity of the problem, not just provide a faster CPU.:)
Working quantum computers with a reasonable number of qubits will render all current public-key encryption techniques useless, regardless of the key length used. Peter Shor has exhibited explicit algorithms for solving the factorization and discrete logarithm problems in polynomial time using a quantum computer. Since all major current public-key systems (El Gamal, RSA, Diffie-Hellman) are based on one of these two problems (sometimes a generalization of dicrete log to elliptic curves) they are all then breakable in polynomial time. Which means breaking them is a very easy problem given fast quantum computers, not much more difficult than encrypting/decrypting a message using them. The algorithms involved use some nifty randomization techniques, quantum Fourier transforms, and basic group theory; see the paper on quant-ph if you're interested.
As far as symmetric ciphers go, I don't know of any algorithms to break them using a quantum computer. It doesn't seem to be an especially difficult problem, however, and I wouldn't be surprised if the NSA or someone had already written up a few to crack 3DES, Blowish, etc.
Quantum encryption will possibly provide a secure alternative; basically the idea here is that the two parties involved use a shared quantum source to generate identical one-time pads. Artur Ekert showed that the parties involved can use the Bell inequality to detect any interference in the shared quantum data; it appears this is generally true for any sort of interference in the commonly generated data. Now quantum encryption is provably impossible to break as it provides a completely random one-time pad; and it seems likely that if quantum computers become a reality we will have stable enough quantum systems to make quantum encryption a reality.
So the net result of the whole quantum thing will probably be the destruction of all previous cryptographic schemes and the use of quantum cryptography. That's assuming we ever build a useful quantum computer, which is by no means assured, given the large difficulties currently faced in the field.
Also, it's unlikely that quantum computers will ever become a device for common use; simply because they're not a replacement for the classical computer. A quantum computer would require a ridiculous amount of classical control and error-correction hardware to run at all. Also, you wouldn't be able to just program it. Quantum computation requires special algorithms that can be parallelized correctly to work at all; it takes people who know quantum very well to come up with these algorithms.... you can't just plug a program into a quantum computer and expect it to run quickly.
So most likely, even if they become widespread, quantum computers will just be used as an "add-on" sort of module to do massively parallelizable computationally intensive things, like Fourier transforms, prime factorization, etc.
A great deal of the usefulness of quantum computers depends on whether they can solve NP-complete problems. This is as yet unknown, but some preliminary work indicates that using special nonlinear aspects of quantum behavior, systems may be developed which can do this. There is evidence indicating standard quantum computers will not be able to generally solve NP-complete problems.
If you want to believe special relativity, EVERYTHING moves at most at the speed of light. Everything. Period. Gravity can indeed be characterized as bending or warping spacetime, but that doesn't exempt it at all. Information, in the form of gravity waves or whatever, cannot travel faster than the speed of light; if you allow any sort of transmission of information or energy (yes,gravity waves carry energy) faster than the speed of light you get yourself into really nasty paradoxes.
The idea is that gravity waves coming from far away will look like the same signal everywhere just delayed a bit, whereas interference from close by will only appear on a single detector or can else be triangulated to a nearby location. Hence we can filter out unwanted signals.
In general using space probes would be exceedingly difficult as you don't have nearly the control that you do when you're in an earth-based observatory. The way LIGO works is by detecting very small vibrations in very delicate suspended masses. Laser interferometry is the only way to get measurements on small enough distances to detect gravitational waves. We're not actually trying to measure the deflection of the beams, but rather the motion of these masses. There's an absurd amount of calibration and fine-tuning going on that's difficult to replicate in a space probe that's going to be launched off.
In fact, though, there are plans to set up a series of probes in space as part of LIGO to check for lower-frequency waves than the ground-based observatories will detect. I believe the first of the probes is supposed to be launched within a decade or so, but I can't recall all the details.
It's not the mail client; I never use anything in Netscape besides the browser; I'm not even sure if I have the mail client installed. This has happened to me only on potato, never on Redhat 5.x or 6.x. Could be glibc2.1, *but* I compiled and installed glibc2.1 on my redhat 5.2 system when it first came out, and never had the problem them. The most damn annoying bug I've had to deal with in a long time. If they had IE for linux, I think I'd switch now, too.
It's not FUD. Linux is not usable by most of the world's population, and it was never intended to be. Linux remains a technical, enthusiasts' OS; to use it to do almost anything at all requires a vast store of knowledge and familiarity with the functioning of the OS and programs. Think of all the concepts we understand and take for granted:.config files, libraries, multiple users, devices, mounting,... the list goes on and on.
This lends itself to more of a learning cliff than curve. Most of the world's population doesn't even want to know what a filesystem is. They just want to be able to press a button to send email to Jimmy. If they're going to use Linux as a desktop OS, they need to be abstracted from all the internals of the machine.
Linux, even pre-installed with KDE/Gnome, is nowhere close to this. I would never recommend Linux to a non-technical-enthusiant in a million years. If you had to give OS support to your clueless grandmother/uncle/neighbor, which you rather they use--Linux or 98?
The important question is: do we really want these people using linux, in any form? It's not as easy a question as it might sound. On one hand, pretty much all Linux users dislike Micro$oft. We're all happy to see a proprietary, closed, inferior OS get trashed by Linux. The rapid expansion and public hype has also benefited the Linux community immensely. A couple years ago you never would have seen useful things like QT, XFS, and Darwin open-sourced, major games on Linux, or graphics companies releasing Linux drivers... Such benefits will continue to flow as more people and hence desktop applications support linux.
But there are also dangers if this increasing popularization of Linux were to occur, more than just the irritation of having users that don't understand what a tarball is. The reason most people I know use Linux is because it's so complex. What first attracted me to Linux was its complexity, its power, and the ability to manipulate, control, and monitor the OS on a low level.
The problem is that while ease-of-use/idiotproofing and power can coexist, it's a difficult and unstable situation. As it stands now, most programs cater to advanced users -- text.config files, lots of command-line options, etc. The average user wants the opposite--simple gui, no questions. This does not lead to good security or powerful programs. If an idiotproof easy-to-use desktop environment is layered on top of Linux, it's likely that many companies releasing software for it would not include the power, behavior, and configurability we now expect . Also, programs might begin to depend on various functionalities of the user-friendly shell to do irritating things without telling us.
Programs that might otherwise be ported to Linux as it is now, with full functionality, could work only in user-friendly mode. Hard-core Linux users could face the unpleasant choice of either 1) contuining as they do now, compiling software, not using insecure features, and being unable to use most software out there, or 2) having to deal with many of the annoyances of Windows, except on Linux.
So think through the issue carefully before espousing Linux as the OS of the masses... do we really want Linux to be an OS usable by those who have no idea how it works? Or do we want to keep it an OS for technophiles, one that chooses power, flexibility, and security over ease-of-use and simplicity? I know why I use Linux; the choice is clear to me. There are enough tech-loving people around to make linux a viable, well-supported choice without opening it the masses.
Ali Soleimani Caltech math/physics undergrand alis@caltech.edu
Reading through the comments to this story, I've heard a lot of clamoring about the probably upcoming FUD from Microsoft about Linux's usability.
It's not FUD. Linux is not usable by most of the world's population, and it was never intended to be. Linux remains a technical, enthusiasts' OS; to use it to do almost anything at all requires a vast store of knowledge and familiarity with the functioning of the OS and programs. Think of all the concepts we understand and take for granted:.config files, libraries, multiple users, devices, mounting,... the list goes on and on.
This lends itself to more of a learning cliff than curve. Most of the world's population doesn't even want to know what a filesystem is. They just want to be able to press a button to send email to Jimmy. If they're going to use Linux as a desktop OS, they need to be abstracted from all the internals of the machine.
Linux, even pre-installed with KDE/Gnome, is nowhere close to this. I would never recommend Linux to a non-technical-enthusiant in a million years. If you had to give OS support to your clueless grandmother/uncle/neighbor, which you rather they use--Linux or 98?
The important question is: do we really want these people using linux, in any form? It's not as easy a question as it might sound. On one hand, pretty much all Linux users dislike Micro$oft. We're all happy to see a proprietary, closed, inferior OS get trashed by Linux. The rapid expansion and public hype has also benefited the Linux community immensely. A couple years ago you never would have seen useful things like QT, XFS, and Darwin open-sourced, major games on Linux, or graphics companies releasing Linux drivers... Such benefits will continue to flow as more people and hence desktop applications support linux.
But there are also dangers if this increasing popularization of Linux were to occur, more than just the irritation of having users that don't understand what a tarball is. The reason most people I know use Linux is because it's so complex. What first attracted me to Linux was its complexity, its power, and the ability to manipulate, control, and monitor the OS on a low level.
The problem is that while ease-of-use/idiotproofing and power can coexist, it's a difficult and unstable situation. As it stands now, most programs cater to advanced users -- text.config files, lots of command-line options, etc. The average user wants the opposite--simple gui, no questions. This does not lead to good security or powerful programs.
If an idiotproof easy-to-use desktop environment is layered on top of Linux, it's likely that many companies releasing software for it would not include the power, behavior, and configurability we now expect; also, programs might begin to depend on various functionalities of the user-friendly shell to do irritating things without telling us.
Programs that might otherwise be ported to Linux as it is now, with full functionality, could work only in user-friendly mode. Hard-core Linux users could face the unpleasant choice of either 1) contuining as they do now, compiling software, not using insecure features, and being unable to use most software out there, or 2) having to deal with many of the annoyances of Windows, except on Linux.
So think through the issue carefully before espousing Linux as the OS of the masses... do we really want Linux to be an OS usable by those who have no idea how it works? Or do we want to keep it an OS for technophiles, one that chooses power, flexibility, and security over ease-of-use and simplicity? I know why I use Linux; the choice is clear to me. There are enough tech-loving people around to make linux a viable, well-supported choice without opening it the masses.
Ali Soleimani Caltech math/physics undergrand alis@caltech.edu
Slashdot Mirror
I believe Mr. Schneier was referring to symmetric cyphers, for which currently there are only improvements of O(sqrt(n)) from O(n). Public-key systems have been broken in polynomial time.
Ali Soleimani
Working quantum computers with a reasonable number of qubits will render all current public-key encryption techniques useless, regardless of the key length used. Peter Shor has exhibited explicit algorithms for solving the factorization and discrete logarithm problems in polynomial time using a quantum computer. Since all major current public-key systems (El Gamal, RSA, Diffie-Hellman) are based on one of these two problems (sometimes a generalization of dicrete log to elliptic curves) they are all then breakable in polynomial time. Which means breaking them is a very easy problem given fast quantum computers, not much more difficult than encrypting/decrypting a message using them. The algorithms involved use some nifty randomization techniques, quantum Fourier transforms, and basic group theory; see the paper on quant-ph if you're interested.
As far as symmetric ciphers go, I don't know of any algorithms to break them using a quantum computer. It doesn't seem to be an especially difficult problem, however, and I wouldn't be surprised if the NSA or someone had already written up a few to crack 3DES, Blowish, etc.
Quantum encryption will possibly provide a secure alternative; basically the idea here is that the two parties involved use a shared quantum source to generate identical one-time pads. Artur Ekert showed that the parties involved can use the Bell inequality to detect any interference in the shared quantum data; it appears this is generally true for any sort of interference in the commonly generated data. Now quantum encryption is provably impossible to break as it provides a completely random one-time pad; and it seems likely that if quantum computers become a reality we will have stable enough quantum systems to make quantum encryption a reality.
So the net result of the whole quantum thing will probably be the destruction of all previous cryptographic schemes and the use of quantum cryptography. That's assuming we ever build a useful quantum computer, which is by no means assured, given the large difficulties currently faced in the field.
Also, it's unlikely that quantum computers will ever become a device for common use; simply because they're not a replacement for the classical computer. A quantum computer would require a ridiculous amount of classical control and error-correction hardware to run at all. Also, you wouldn't be able to just program it. Quantum computation requires special algorithms that can be parallelized correctly to work at all; it takes people who know quantum very well to come up with these algorithms.... you can't just plug a program into a quantum computer and expect it to run quickly.
So most likely, even if they become widespread, quantum computers will just be used as an "add-on" sort of module to do massively parallelizable computationally intensive things, like Fourier transforms, prime factorization, etc.
A great deal of the usefulness of quantum computers depends on whether they can solve NP-complete problems. This is as yet unknown, but some preliminary work indicates that using special nonlinear aspects of quantum behavior, systems may be developed which can do this. There is evidence indicating standard quantum computers will not be able to generally solve NP-complete problems.
Ali Soleimani
alis@caltech.edu
Caltech Phys/Math
Ummm... in short, no.
If you want to believe special relativity, EVERYTHING moves at most at the speed of light. Everything. Period. Gravity can indeed be characterized as bending or warping spacetime, but that doesn't exempt it at all. Information, in the form of gravity waves or whatever, cannot travel faster than the speed of light; if you allow any sort of transmission of information or energy (yes,gravity waves carry energy) faster than the speed of light you get yourself into really nasty paradoxes.
The idea is that gravity waves coming from far away will look like the same signal everywhere just delayed a bit, whereas interference from close by will only appear on a single detector or can else be triangulated to a nearby location. Hence we can filter out unwanted signals.
In general using space probes would be exceedingly difficult as you don't have nearly the control that you do when you're in an earth-based observatory. The way LIGO works is by detecting very small vibrations in very delicate suspended masses. Laser interferometry is the only way to get measurements on small enough distances to detect gravitational waves. We're not actually trying to measure the deflection of the beams, but rather the motion of these masses. There's an absurd amount of calibration and fine-tuning going on that's difficult to replicate in a space probe that's going to be launched off.
In fact, though, there are plans to set up a series of probes in space as part of LIGO to check for lower-frequency waves than the ground-based observatories will detect. I believe the first of the probes is supposed to be launched within a decade or so, but I can't recall all the details.
It's not the mail client; I never use anything in Netscape besides the browser; I'm not even sure if I have the mail client installed. This has happened to me only on potato, never on Redhat 5.x or 6.x. Could be glibc2.1, *but* I compiled and installed glibc2.1 on my redhat 5.2 system when it first came out, and never had the problem them. The most damn annoying bug I've had to deal with in a long time. If they had IE for linux, I think I'd switch now, too.
It's not FUD. Linux is not usable by most of the world's population, and it was never intended to be. Linux remains a technical, enthusiasts' OS; to use it to do almost anything at all requires a vast store of knowledge and familiarity with the functioning of the OS and programs. Think of all the concepts we understand and take for granted:
This lends itself to more of a learning cliff than curve. Most of the world's population doesn't even want to know what a filesystem is. They just want to be able to press a button to send email to Jimmy. If they're going to use Linux as a desktop OS, they need to be abstracted from all the internals of the machine.
Linux, even pre-installed with KDE/Gnome, is nowhere close to this. I would never recommend Linux to a non-technical-enthusiant in a million years. If you had to give OS support to your clueless grandmother/uncle/neighbor, which you rather they use--Linux or 98?
The important question is: do we really want these people using linux, in any form? It's not as easy a question as it might sound. On one hand, pretty much all Linux users dislike Micro$oft. We're all happy to see a proprietary, closed, inferior OS get trashed by Linux. The rapid expansion and public hype has also benefited the Linux community immensely. A couple years ago you never would have seen useful things like QT, XFS, and Darwin open-sourced, major games on Linux, or graphics companies releasing Linux drivers... Such benefits will continue to flow as more people and hence desktop applications support linux.
But there are also dangers if this increasing popularization of Linux were to occur, more than just the irritation of having users that don't understand what a tarball is. The reason most people I know use Linux is because it's so complex. What first attracted me to Linux was its complexity, its power, and the ability to manipulate, control, and monitor the OS on a low level.
The problem is that while ease-of-use/idiotproofing and power can coexist, it's a difficult and unstable situation. As it stands now, most programs cater to advanced users -- text
Programs that might otherwise be ported to Linux as it is now, with full functionality, could work only in user-friendly mode. Hard-core Linux users could face the unpleasant choice of either 1) contuining as they do now, compiling software, not using insecure features, and being unable to use most software out there, or 2) having to deal with many of the annoyances of Windows, except on Linux.
So think through the issue carefully before espousing Linux as the OS of the masses... do we really want Linux to be an OS usable by those who have no idea how it works? Or do we want to keep it an OS for technophiles, one that chooses power, flexibility, and security over ease-of-use and simplicity? I know why I use Linux; the choice is clear to me. There are enough tech-loving people around to make linux a viable, well-supported choice without opening it the masses.
Ali Soleimani
Caltech math/physics undergrand
alis@caltech.edu
It's not FUD. Linux is not usable by most of the world's population, and it was never intended to be. Linux remains a technical, enthusiasts' OS; to use it to do almost anything at all requires a vast store of knowledge and familiarity with the functioning of the OS and programs. Think of all the concepts we understand and take for granted:
This lends itself to more of a learning cliff than curve. Most of the world's population doesn't even want to know what a filesystem is. They just want to be able to press a button to send email to Jimmy. If they're going to use Linux as a desktop OS, they need to be abstracted from all the internals of the machine.
Linux, even pre-installed with KDE/Gnome, is nowhere close to this. I would never recommend Linux to a non-technical-enthusiant in a million years. If you had to give OS support to your clueless grandmother/uncle/neighbor, which you rather they use--Linux or 98?
The important question is: do we really want these people using linux, in any form? It's not as easy a question as it might sound. On one hand, pretty much all Linux users dislike Micro$oft. We're all happy to see a proprietary, closed, inferior OS get trashed by Linux. The rapid expansion and public hype has also benefited the Linux community immensely. A couple years ago you never would have seen useful things like QT, XFS, and Darwin open-sourced, major games on Linux, or graphics companies releasing Linux drivers... Such benefits will continue to flow as more people and hence desktop applications support linux.
But there are also dangers if this increasing popularization of Linux were to occur, more than just the irritation of having users that don't understand what a tarball is. The reason most people I know use Linux is because it's so complex. What first attracted me to Linux was its complexity, its power, and the ability to manipulate, control, and monitor the OS on a low level.
The problem is that while ease-of-use/idiotproofing and power can coexist, it's a difficult and unstable situation. As it stands now, most programs cater to advanced users -- text
If an idiotproof easy-to-use desktop environment is layered on top of Linux, it's likely that many companies releasing software for it would not include the power, behavior, and configurability we now expect; also, programs might begin to depend on various functionalities of the user-friendly shell to do irritating things without telling us.
Programs that might otherwise be ported to Linux as it is now, with full functionality, could work only in user-friendly mode. Hard-core Linux users could face the unpleasant choice of either 1) contuining as they do now, compiling software, not using insecure features, and being unable to use most software out there, or 2) having to deal with many of the annoyances of Windows, except on Linux.
So think through the issue carefully before espousing Linux as the OS of the masses... do we really want Linux to be an OS usable by those who have no idea how it works? Or do we want to keep it an OS for technophiles, one that chooses power, flexibility, and security over ease-of-use and simplicity? I know why I use Linux; the choice is clear to me. There are enough tech-loving people around to make linux a viable, well-supported choice without opening it the masses.
Ali Soleimani
Caltech math/physics undergrand
alis@caltech.edu