6 ms·

Just to be clear, this has barely anything to do with any crypto-currency organization. It is a really regrettable framing for an event that should be of great

Just to be clear, this has barely anything to do with any crypto-currency organization. It is a really regrettable framing for an event that should be of great interest to anyone dealing with cryptography, not just the fairly restricted group of crypto-currentcy enthusiasts. If scalable quantum computers can be built (which seems probable, as we are progressing fast in the number of qubits we can keep together), then certain restricted types of public key encryption will be broken by quantum hardware (all currently used public key encryption actually). We know other public key encryption algorithms exist that can run on classical computers and still not be broken by quantum computers. In many ways they are less tested and less practical, so for a while NIST has been sponsoring the development of such quantum-resistant running-on-classical-computers public-key algorithms. The usual name for this is post-quantum encryption.

olliej 7y ago
That list is still going though I don’t have it handy (I’ll try to update with the mailing list). There are a number of problems that are well established with strong security proofs vs classical and quantum algorithms - the problem is that the key and message sizes are fairly terrible for practice currently. On the plus side all the current symmetric ciphers are still pretty solid against quantum machines (Grover’s search is a sqrt improvement so would simply require a doubling in key size, but I suspect in practice not necessary)
Causality1 7y ago
We seem to be getting better at using quantum computers for hard math. What I'm curious about is when we'll be able to use them for easy math. How many qubits do we need to run Doom Quantum?
- krastanov 7y ago
  Quantum computers are (conjectured to) outperform classical computers in a very restricted set of problems. These problems happen to be extremely important (e.g. protein folding and some forms of linear algebra), but for tasks that are already efficiently solved by classical computers you probably will never use a quantum computer (maybe in many decades this will change, when it becomes as "trivial" to construct quantum CPUs as it is to construct classical CPUs)
  - marcus0x62 7y ago
    Or the subset of users who need what a quantum computer can offer add something analogous to a GPU to their general purpose computer.
ridewinter 7y ago
The only truly safe encryption is quantum encryption. Any classical encryption algorithm should be breakable with quantum computers, even if we haven’t figured it out yet like with Shor’s.
- zazagura 7y ago
  Citation needed? Symmetric encryption algorithms like AES (with at least 256 bit key) are considered safe even against quantum computers, based on some reasonable math/qm assumptions.
  - zrm 7y ago
    Not only that, there are asymmetric encryption algorithms not vulnerable to Shor's algorithm, we're just not using them yet (because they're slower and haven't been as well-studied as RSA or ECC).
  - charleslmunger 7y ago
    Yeah, so far as I know the only algorithm that provides an asymptomatic speedup (for AES or similar symmetric key crypto) over a classical computer is Grover's algorithm. That would reduce a 256 bit key to 128, which is hardly disastrous.
  - ridewinter 7y ago
    All of that seems to only be “medium” secure in face of future quantum computing. “It's been estimated that 6,681 qubits would be required to run use Grover's algorithm to break AES-256 bit encryption.” https://www.theregister.co.uk/2019/03/14/quantum_encryption_debunking/ https://www.theregister.co.uk/2019/03/14/quantum_encryption_...
- mikeash 7y ago
  Obvious counterexample: one-time pads. Even if you don’t go that extreme, there’s no indication that e.g. AES is breakable.
- kokx 7y ago
  What do you mean with quantum encryption? QKD (Quantum Key Distribution)? Though the concept seems nice, it has quite a few issues in practice. Such as distance between coupled devices, and the need to have a dedicated physical communication line. Oh and before you think you can just chain several devices to get longer distances: this opens you up to classical MitM attacks. Source: https://www.nature.com/articles/npjqi201625 https://www.nature.com/articles/npjqi201625
tialaramex 7y ago
> which seems probable, as we are progressing fast in the number of qubits we can keep together Are we? Every so often I check back to see how well they're doing with actually running Shor's algorithm. In 2012 they managed to find that 21 = 3 x 7. And today... 21 = 3 x 7. That doesn't sound like progressing fast. Quantum annealing is doing well for itself, but it isn't any sort of threat to encryption.
- sweeneyrod 7y ago
  Damn, looks like I should stop using 21 as my PK then.
  - nielsole 7y ago
    Not sure what algorithm you use for encryption, but 21 doesn't look like a prime. Maybe run a Miller Rabin test on it? ;)
    - sweeneyrod 7y ago
      It's the modulus of my RSA PK, so the product of two large primes rather than a prime itself. Of course, I can't say what the factors are, otherwise anyone could crack it even if they don't have a quantum computer!
  - neuralzen 7y ago
    Just XOR 21 times, problem solved!
    - myle 7y ago
      Always with the same mask, to make sure it is applied well.
- krastanov 7y ago
  We definitely are getting closer. Look at any graph of "qubit lifetime" and you will see how we have orders of magnitude improvements. (a quick google search gives me page 9 of https://hpcuserforum.com/presentations/tuscon2018/QCOverview_Rigetti_UFTucson2018.pdf https://hpcuserforum.com/presentations/tuscon2018/QCOverview...). We still need a couple more orders of magnitude before the qubits are useful, but the signs of exponential progress are unmistakable. I would not take any experiment performing Shor's algorithm today or in the past particularly seriously, since they would probably be showing something fine tuned for the particular instance of the problem (e.g. 21). We do not have anything that can be called an "error-corrected logical qubit", and we need this before we can make serious claims about running algorithms like Shor's.
The_rationalist 7y ago
> which seems probable, as we are progressing fast in the number of qubits we can keep together Probable? Ridiculous: ×there are still no hardware implementation of a single logic gate despite what? 40 years of research? ×stability of qubits are pathetic. ×no software stack (almost) ×Number of qubits are ridiculous and 40 years of research can't even make a consensus on how much qubits are needed for beating a CPU on at least one task. Even if quantum could(I strongly doubt that and quantum speedup has never been shown empirically) reduce complexity on some algorithms, the constant factor has no way to be handled with 50qbits, more like 1000000 qbits at minimum. ×no sign of needed breakthrough in error correcting codes. I consider quantum speedup to be theoretically flawed, based on an interpretation of quantum mechanics needing "parallel worlds" which necessitate a misunderstanding of causality to make sense. I consider quantum speedup to be flawed in practice too as order of magnitude of order of magnitude progress is needed and the trend is: no progress or very slow progress. Thus quantum computing is like a vaporware, which take funds that would be far better allocated at e.g medicine, AGI, or ASICS.
- semi-extrinsic 7y ago
  While I agree that QC is far from cracking any encryption today or in the near future; this > theoretically flawed, based on an interpretation of quantum mechanics needing "parallel worlds" is patently false. There is nothing in QC that would stop working under the good ole' Copenhagen interpretation. In fact, if there was even a theoretical possibility that a QC experiment would work only in some QM interpretations, they would no longer be interpretations, but falsifiable hypotheses.
  - im3w1l 7y ago
    Copenhagen postulates collapse, no? If collapses turn out to happen at problematic times or because of problematic conditions, it could potentially doom quantum computers. In contrast, many worlds says basically: There is no collapse. Ever. The fact that no one has found what triggers collapse yet is to me evidence that Copenhagen is false. Pilot wave theory on the other hand is, afaiu completely equivalent to many worlds, but less philosophically convincing. Where many worlds says there is only the wave function, pilot wave says there is a wave function but also the material world. And material world is a sort of "view" of the wave function. Continuously rederived from it. But the interesting thing is, this material world has no causal consequences. All causality stems from the wave function and its evolution. This is the compromise to get same predictions as many worlds.

olliej 7y ago

That list is still going though I don’t have it handy (I’ll try to update with the mailing list). There are a number of problems that are well established with strong security proofs vs classical and quantum algorithms - the problem is that the key and message sizes are fairly terrible for practice currently. On the plus side all the current symmetric ciphers are still pretty solid against quantum machines (Grover’s search is a sqrt improvement so would simply require a doubling in key size, but I suspect in practice not necessary)

Causality1 7y ago

We seem to be getting better at using quantum computers for hard math. What I'm curious about is when we'll be able to use them for easy math. How many qubits do we need to run Doom Quantum?

krastanov 7y ago
Quantum computers are (conjectured to) outperform classical computers in a very restricted set of problems. These problems happen to be extremely important (e.g. protein folding and some forms of linear algebra), but for tasks that are already efficiently solved by classical computers you probably will never use a quantum computer (maybe in many decades this will change, when it becomes as "trivial" to construct quantum CPUs as it is to construct classical CPUs)
- marcus0x62 7y ago
  Or the subset of users who need what a quantum computer can offer add something analogous to a GPU to their general purpose computer.

ridewinter 7y ago

The only truly safe encryption is quantum encryption. Any classical encryption algorithm should be breakable with quantum computers, even if we haven’t figured it out yet like with Shor’s.

zazagura 7y ago
Citation needed? Symmetric encryption algorithms like AES (with at least 256 bit key) are considered safe even against quantum computers, based on some reasonable math/qm assumptions.
- zrm 7y ago
  Not only that, there are asymmetric encryption algorithms not vulnerable to Shor's algorithm, we're just not using them yet (because they're slower and haven't been as well-studied as RSA or ECC).
- charleslmunger 7y ago
  Yeah, so far as I know the only algorithm that provides an asymptomatic speedup (for AES or similar symmetric key crypto) over a classical computer is Grover's algorithm. That would reduce a 256 bit key to 128, which is hardly disastrous.
- ridewinter 7y ago
  All of that seems to only be “medium” secure in face of future quantum computing. “It's been estimated that 6,681 qubits would be required to run use Grover's algorithm to break AES-256 bit encryption.” https://www.theregister.co.uk/2019/03/14/quantum_encryption_debunking/ https://www.theregister.co.uk/2019/03/14/quantum_encryption_...
mikeash 7y ago
Obvious counterexample: one-time pads. Even if you don’t go that extreme, there’s no indication that e.g. AES is breakable.
kokx 7y ago
What do you mean with quantum encryption? QKD (Quantum Key Distribution)? Though the concept seems nice, it has quite a few issues in practice. Such as distance between coupled devices, and the need to have a dedicated physical communication line. Oh and before you think you can just chain several devices to get longer distances: this opens you up to classical MitM attacks. Source: https://www.nature.com/articles/npjqi201625 https://www.nature.com/articles/npjqi201625

tialaramex 7y ago

> which seems probable, as we are progressing fast in the number of qubits we can keep together Are we? Every so often I check back to see how well they're doing with actually running Shor's algorithm. In 2012 they managed to find that 21 = 3 x 7. And today... 21 = 3 x 7. That doesn't sound like progressing fast. Quantum annealing is doing well for itself, but it isn't any sort of threat to encryption.

sweeneyrod 7y ago
Damn, looks like I should stop using 21 as my PK then.
- nielsole 7y ago
  Not sure what algorithm you use for encryption, but 21 doesn't look like a prime. Maybe run a Miller Rabin test on it? ;)
  - sweeneyrod 7y ago
    It's the modulus of my RSA PK, so the product of two large primes rather than a prime itself. Of course, I can't say what the factors are, otherwise anyone could crack it even if they don't have a quantum computer!
- neuralzen 7y ago
  Just XOR 21 times, problem solved!
  - myle 7y ago
    Always with the same mask, to make sure it is applied well.
krastanov 7y ago
We definitely are getting closer. Look at any graph of "qubit lifetime" and you will see how we have orders of magnitude improvements. (a quick google search gives me page 9 of https://hpcuserforum.com/presentations/tuscon2018/QCOverview_Rigetti_UFTucson2018.pdf https://hpcuserforum.com/presentations/tuscon2018/QCOverview...). We still need a couple more orders of magnitude before the qubits are useful, but the signs of exponential progress are unmistakable. I would not take any experiment performing Shor's algorithm today or in the past particularly seriously, since they would probably be showing something fine tuned for the particular instance of the problem (e.g. 21). We do not have anything that can be called an "error-corrected logical qubit", and we need this before we can make serious claims about running algorithms like Shor's.

The_rationalist 7y ago

> which seems probable, as we are progressing fast in the number of qubits we can keep together Probable? Ridiculous: ×there are still no hardware implementation of a single logic gate despite what? 40 years of research? ×stability of qubits are pathetic. ×no software stack (almost) ×Number of qubits are ridiculous and 40 years of research can't even make a consensus on how much qubits are needed for beating a CPU on at least one task. Even if quantum could(I strongly doubt that and quantum speedup has never been shown empirically) reduce complexity on some algorithms, the constant factor has no way to be handled with 50qbits, more like 1000000 qbits at minimum. ×no sign of needed breakthrough in error correcting codes. I consider quantum speedup to be theoretically flawed, based on an interpretation of quantum mechanics needing "parallel worlds" which necessitate a misunderstanding of causality to make sense. I consider quantum speedup to be flawed in practice too as order of magnitude of order of magnitude progress is needed and the trend is: no progress or very slow progress. Thus quantum computing is like a vaporware, which take funds that would be far better allocated at e.g medicine, AGI, or ASICS.

semi-extrinsic 7y ago
While I agree that QC is far from cracking any encryption today or in the near future; this > theoretically flawed, based on an interpretation of quantum mechanics needing "parallel worlds" is patently false. There is nothing in QC that would stop working under the good ole' Copenhagen interpretation. In fact, if there was even a theoretical possibility that a QC experiment would work only in some QM interpretations, they would no longer be interpretations, but falsifiable hypotheses.
- im3w1l 7y ago
  Copenhagen postulates collapse, no? If collapses turn out to happen at problematic times or because of problematic conditions, it could potentially doom quantum computers. In contrast, many worlds says basically: There is no collapse. Ever. The fact that no one has found what triggers collapse yet is to me evidence that Copenhagen is false. Pilot wave theory on the other hand is, afaiu completely equivalent to many worlds, but less philosophically convincing. Where many worlds says there is only the wave function, pilot wave says there is a wave function but also the material world. And material world is a sort of "view" of the wave function. Continuously rederived from it. But the interesting thing is, this material world has no causal consequences. All causality stems from the wave function and its evolution. This is the compromise to get same predictions as many worlds.