5 ms·

I think, generally, the concern with quantum resistant cryptography is that, like homomorphic encryption schemes, it’s unworkably slow right now.

jason13579 7y ago
No, it’s not. Some implementations do even perform better than current public key crypto schemes.
- throwawaymath 7y ago
  Which post-quantum cryptosystems are more efficient than RSA?
  - jason13579 7y ago
    I did not claim that they outperform RSA in particular and I would not call RSA a state of the art public key cryptosystem. Actually, I would strongly suggest against using RSA without first having a deep dive into the field of number theory. However, for extreme RSA key sizes (e.g. 4096 bit) NewHope does actually outperform RSA and definitely outperforms some ECC counterparts.
    - hailwren 7y ago
      NewHope has not been proven to be quantum resistant. I think researchers generally believe that NewHope will be proven to be quantum resistant, but there is the problem of adapting Micciancio's regular lattice proof to ideal lattices.
      - jason13579 7y ago
        That’s right, it hasn’t. Just as almost every other candidate in the NIST competition. However, none of the currently employed public key crypto systems has even been proven to be secure against standard computers and they can definitely be broken by a (powerful) quantum computer. So I would still favor taking a scheme that most likely is secure against quantum computing over one that can definitely be broken by it, especially if their performance does not differ too much anymore.
      - c1own 7y ago
        Nothing can be "proven" to be quantum resistant. Even if we can show a tight reduction to LWE, and we believe that LWE is efficiently solvable (let's say LWE is not in BQP), it is still possible that the cryptosystem at the given parameters is broken. In the classical case, it doesn't matter whether or not the RSA problem is "hard" (more formally, the RSA problem is not in BPP), it matters if the RSA4096 problem has an efficient solution for many real world instances. So, yeah, the talk of "proving" security---while interesting---isn't very useful.
    - archgoon 7y ago
      >However, for extreme RSA key sizes (e.g. 4096 bit) NewHope does actually outperform RSA. Yep, it's definitely a scaling thing. If it weren't then we could simply use Daniel Bernstein's (et al) proposal for Post Quantum RSA. https://eprint.iacr.org/2017/351.pdf https://eprint.iacr.org/2017/351.pdf
c1own 7y ago
You're wrong. https://blog.cloudflare.com/the-tls-post-quantum-experiment/ https://blog.cloudflare.com/the-tls-post-quantum-experiment/
craftinator 7y ago
Have quantum computers managed to break any sort of cryptography at this point? Even schemes that have been broken by classical computers? I have heard so much speculation on this, for over a decade now, but I haven't seen anything close to application. Can anyone provide insight on this?
- mcpherrinm 7y ago
  We haven't gotten quantum computers to do anything faster than classical computers, except possibly contrived problems designed to be fast on quantum computers. We have factored some small numbers on quantum computers but nothing a classical one couldn't do in a split second. https://en.wikipedia.org/wiki/Integer_factorization_records https://en.wikipedia.org/wiki/Integer_factorization_records / https://arxiv.org/abs/1805.10478 https://arxiv.org/abs/1805.10478
  - jason13579 7y ago
    Quantum Computing is now at the stage that standard ICs have been at in the early sixties. Back than, chips where made of of a few dozen transistors and couldn’t really do anything. It will take a while for quantum computers to really become a threat to cryptography, though at some point they definitely will (in my opinion). Regarding the „except possibly contrived problems designed to be fast on quantum computers“ part: That’s their entire purpose. They cannot and will never be faster for all applications compared to a classical computer. They are designed to solve some very special problems efficiently, such as solving dlog and RSA using Shor‘s algorithm or database search using Grover.
    - buzzkillington 7y ago
      What's Moore's law like for quantum computers?
      - c1own 7y ago
        We have Neven's law: https://www.quantamagazine.org/does-nevens-law-describe-quantum-computings-rise-20190618/ https://www.quantamagazine.org/does-nevens-law-describe-quan... which states that quantum computers are getting doubly-exponentially better relative to classical computers. First, they are exponentially better than classical computers. Second, they are getting exponentially better. Hence, Neven's law. One needs to define "better" formally (with number of qubits, gate fidelities, coherence times,...) to graph progress, but the idea is that they can do more.
Ar-Curunir 7y ago
No, many schemes are acceptably fast. Eg isogenies, code based signatures, some lattice schemes, some hash based schemes. The key concern usually stems from the size of the primitive (signature size or public key size)

jason13579 7y ago

No, it’s not. Some implementations do even perform better than current public key crypto schemes.

throwawaymath 7y ago
Which post-quantum cryptosystems are more efficient than RSA?
- jason13579 7y ago
  I did not claim that they outperform RSA in particular and I would not call RSA a state of the art public key cryptosystem. Actually, I would strongly suggest against using RSA without first having a deep dive into the field of number theory. However, for extreme RSA key sizes (e.g. 4096 bit) NewHope does actually outperform RSA and definitely outperforms some ECC counterparts.
  - hailwren 7y ago
    NewHope has not been proven to be quantum resistant. I think researchers generally believe that NewHope will be proven to be quantum resistant, but there is the problem of adapting Micciancio's regular lattice proof to ideal lattices.
    - jason13579 7y ago
      That’s right, it hasn’t. Just as almost every other candidate in the NIST competition. However, none of the currently employed public key crypto systems has even been proven to be secure against standard computers and they can definitely be broken by a (powerful) quantum computer. So I would still favor taking a scheme that most likely is secure against quantum computing over one that can definitely be broken by it, especially if their performance does not differ too much anymore.
    - c1own 7y ago
      Nothing can be "proven" to be quantum resistant. Even if we can show a tight reduction to LWE, and we believe that LWE is efficiently solvable (let's say LWE is not in BQP), it is still possible that the cryptosystem at the given parameters is broken. In the classical case, it doesn't matter whether or not the RSA problem is "hard" (more formally, the RSA problem is not in BPP), it matters if the RSA4096 problem has an efficient solution for many real world instances. So, yeah, the talk of "proving" security---while interesting---isn't very useful.
  - archgoon 7y ago
    >However, for extreme RSA key sizes (e.g. 4096 bit) NewHope does actually outperform RSA. Yep, it's definitely a scaling thing. If it weren't then we could simply use Daniel Bernstein's (et al) proposal for Post Quantum RSA. https://eprint.iacr.org/2017/351.pdf https://eprint.iacr.org/2017/351.pdf

c1own 7y ago

You're wrong. https://blog.cloudflare.com/the-tls-post-quantum-experiment/ https://blog.cloudflare.com/the-tls-post-quantum-experiment/

craftinator 7y ago

Have quantum computers managed to break any sort of cryptography at this point? Even schemes that have been broken by classical computers? I have heard so much speculation on this, for over a decade now, but I haven't seen anything close to application. Can anyone provide insight on this?

mcpherrinm 7y ago
We haven't gotten quantum computers to do anything faster than classical computers, except possibly contrived problems designed to be fast on quantum computers. We have factored some small numbers on quantum computers but nothing a classical one couldn't do in a split second. https://en.wikipedia.org/wiki/Integer_factorization_records https://en.wikipedia.org/wiki/Integer_factorization_records / https://arxiv.org/abs/1805.10478 https://arxiv.org/abs/1805.10478
- jason13579 7y ago
  Quantum Computing is now at the stage that standard ICs have been at in the early sixties. Back than, chips where made of of a few dozen transistors and couldn’t really do anything. It will take a while for quantum computers to really become a threat to cryptography, though at some point they definitely will (in my opinion). Regarding the „except possibly contrived problems designed to be fast on quantum computers“ part: That’s their entire purpose. They cannot and will never be faster for all applications compared to a classical computer. They are designed to solve some very special problems efficiently, such as solving dlog and RSA using Shor‘s algorithm or database search using Grover.
  - buzzkillington 7y ago
    What's Moore's law like for quantum computers?
    - c1own 7y ago
      We have Neven's law: https://www.quantamagazine.org/does-nevens-law-describe-quantum-computings-rise-20190618/ https://www.quantamagazine.org/does-nevens-law-describe-quan... which states that quantum computers are getting doubly-exponentially better relative to classical computers. First, they are exponentially better than classical computers. Second, they are getting exponentially better. Hence, Neven's law. One needs to define "better" formally (with number of qubits, gate fidelities, coherence times,...) to graph progress, but the idea is that they can do more.

Ar-Curunir 7y ago

No, many schemes are acceptably fast. Eg isogenies, code based signatures, some lattice schemes, some hash based schemes. The key concern usually stems from the size of the primitive (signature size or public key size)