3 ms·

Are there any blogs that talk about what’s required in a crypto algorithm to withstand quantum computing? Is a straightforward increasing the key size enough? O

Are there any blogs that talk about what’s required in a crypto algorithm to withstand quantum computing? Is a straightforward increasing the key size enough? Or are there new paradigms explored? Are these algorithms symmetric or asymmetric?

betterunix2 9y ago
PQ crypto has to be secure against a scalable quantum computer i.e. one that can be increased to attack arbitrarily large keysizes. Building a quantum computer with enough qbits to attack RSA2048 is not a problem if there is no known way to increase the number of qbits to attack RSA3072 -- but if you can keep adding more qbits, then we need a post-quantum algorithm. The interest in post-quantum crypto is mainly in public-key systems, because for symmetric key systems you can essentially double the key size to achieve the same security level. In other words, AES256 is as secure against a quantum computer as AES128 is against a classical computer. On the other hand, quantum algorithms break RSA and DLOG (include ECDLOG), so the research has been on new approaches to public key crypto that seem hard for quantum computers. For example, the Learning With Errors (LWE) problem: https://en.wikipedia.org/wiki/Learning_with_errors https://en.wikipedia.org/wiki/Learning_with_errors
- yalogin 9y ago
  Interesting. But an ec 512 bit key has a theoretically same strength as an aes 256 bit key. How is aes able to withstand it when ec and rsa can’t?
  - CiPHPerCoder 9y ago
    AES's security reduction in the quantum scenario comes from a sqrt(n) reduction in search time. It's an optimized brute force against the key. ECC gets broken because there is a quantum algorithm that solves the Elliptic Curve Discrete Logarithm Problem much faster than sqrt(n).
    - yalogin 9y ago
      Thanks. Looks like I have a wrong understanding of quantum computing. I thought QC increases the computing power by a lot there by making it easier or practical to compute the discrete log. So are you saying that the QC paradigm lends itself to a different class of algorithms?
      - CiPHPerCoder 9y ago
        Yes, look up Shor's Algorithm and Grover's Algorithm.
westurner 9y ago
This paper lists a few of the practical concerns for quantum-resistant algos (and proposes an algo that wasn't submitted to NIST Post-Quantum Cryptography Round 1): "Quantum attacks on Bitcoin, and how to protect against them" https://arxiv.org/abs/1710.10377 https://arxiv.org/abs/1710.10377 (~2027?) A few Quantum Computing and Quantum Algorithm resources: https://news.ycombinator.com/item?id=16052193 https://news.ycombinator.com/item?id=16052193 Responsive HTML (arxiv-vanity/engrafo, PLoS,) or Markdown in a Jupyter notebook (stored in a Git repo with a tag and maybe a DOI from figshare or Zenodo) really would be far more useful than comparing LaTeX equations rendered into PDFs.

betterunix2 9y ago

PQ crypto has to be secure against a scalable quantum computer i.e. one that can be increased to attack arbitrarily large keysizes. Building a quantum computer with enough qbits to attack RSA2048 is not a problem if there is no known way to increase the number of qbits to attack RSA3072 -- but if you can keep adding more qbits, then we need a post-quantum algorithm. The interest in post-quantum crypto is mainly in public-key systems, because for symmetric key systems you can essentially double the key size to achieve the same security level. In other words, AES256 is as secure against a quantum computer as AES128 is against a classical computer. On the other hand, quantum algorithms break RSA and DLOG (include ECDLOG), so the research has been on new approaches to public key crypto that seem hard for quantum computers. For example, the Learning With Errors (LWE) problem: https://en.wikipedia.org/wiki/Learning_with_errors https://en.wikipedia.org/wiki/Learning_with_errors

yalogin 9y ago
Interesting. But an ec 512 bit key has a theoretically same strength as an aes 256 bit key. How is aes able to withstand it when ec and rsa can’t?
- CiPHPerCoder 9y ago
  AES's security reduction in the quantum scenario comes from a sqrt(n) reduction in search time. It's an optimized brute force against the key. ECC gets broken because there is a quantum algorithm that solves the Elliptic Curve Discrete Logarithm Problem much faster than sqrt(n).
  - yalogin 9y ago
    Thanks. Looks like I have a wrong understanding of quantum computing. I thought QC increases the computing power by a lot there by making it easier or practical to compute the discrete log. So are you saying that the QC paradigm lends itself to a different class of algorithms?
    - CiPHPerCoder 9y ago
      Yes, look up Shor's Algorithm and Grover's Algorithm.

westurner 9y ago

This paper lists a few of the practical concerns for quantum-resistant algos (and proposes an algo that wasn't submitted to NIST Post-Quantum Cryptography Round 1): "Quantum attacks on Bitcoin, and how to protect against them" https://arxiv.org/abs/1710.10377 https://arxiv.org/abs/1710.10377 (~2027?) A few Quantum Computing and Quantum Algorithm resources: https://news.ycombinator.com/item?id=16052193 https://news.ycombinator.com/item?id=16052193 Responsive HTML (arxiv-vanity/engrafo, PLoS,) or Markdown in a Jupyter notebook (stored in a Git repo with a tag and maybe a DOI from figshare or Zenodo) really would be far more useful than comparing LaTeX equations rendered into PDFs.