6 ms·

By everything you mean every public key scheme? Aren't symmetric crypto schemes based on strong shared secrets secure from quantum computers? With Optalysys an

by Cieplak 10y ago

By everything you mean every public key scheme? Aren't symmetric crypto schemes based on strong shared secrets secure from quantum computers? With Optalysys and D-Wave, I expect quantum computing to become mainstream within the next ten years.

tptacek 10y ago
Every real-world cryptosystem in current use, possibly excepting some experimental pq systems like the RingLWE that Google's playing with.
- Cieplak 10y ago
  Symmetric encryption is weakened; namely, a quantum computer can search through a space of size 2n in time 2n/2. This means that a 128-bit AES key would be demoted back to the strength of a 64-bit key ... [1] http://security.stackexchange.com/questions/48022/what-kinds-of-encryption-are-not-breakable-via-quantum-computers http://security.stackexchange.com/questions/48022/what-kinds...
  - tptacek 10y ago
    I'm really not interested in how well PSK AES schemes fare post-quantum, because PSK isn't a realistic solution to any of the problems we use cryptography to address. I suggested, upthread, not using RSA (which depends on the hardness of factoring) and using ECC instead. How AES does post-quantum is not responsive to that advice.
    - Cieplak 10y ago
      You suggested ECC over RSA, implying that ECC offers greater security than RSA in the context of easy prime factorization. ECC's security relies on the hardness of the discrete logarithm. Yet, both prime factorization and the discrete logarithm are both special cases of the hidden subgroup problem over an Abelian group. In short, cracking RSA means cracking ECC, too. Am I wrong? Were you just joking?
      - tptacek 10y ago
        If I understand your argument properly, then I believe you to be wrong about the idea that tenably factoring 1024 or 2048 bit moduli implies a solution to the elliptic curve discrete modulus problem, yes.
      - Cieplak 10y ago
        @tptacek > I believe you to be wrong about the idea that tenably factoring 1024 or 2048 bit moduli implies a solution to the elliptic curve discrete modulus problem Probably. This mathy stuff is way over my head. I'm just repeating what I read in Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer [1] published by Peter W. Shor on behalf of AT&T Research in 1995. Supposedly his proof is valid, predicated on the existence of quantum computers. Quantum computers actually exist [insert epistemological joke here]. [1] https://arxiv.org/abs/quant-ph/9508027v2 https://arxiv.org/abs/quant-ph/9508027v2
        sdevlin 10y ago
        You are talking about quantum attacks, whereas tptacek is talking about classical attacks.
  - Filligree 10y ago
    So we'll take a performance hit, but it's fairly straightforward (relatively, very relatively) to extend the key sizes for symmetric crypto. The lack of any usable asymmetric algorithms is a much greater concern.

by Cieplak 10y ago

tptacek 10y ago

Every real-world cryptosystem in current use, possibly excepting some experimental pq systems like the RingLWE that Google's playing with.

Cieplak 10y ago
Symmetric encryption is weakened; namely, a quantum computer can search through a space of size 2n in time 2n/2. This means that a 128-bit AES key would be demoted back to the strength of a 64-bit key ... [1] http://security.stackexchange.com/questions/48022/what-kinds-of-encryption-are-not-breakable-via-quantum-computers http://security.stackexchange.com/questions/48022/what-kinds...
- tptacek 10y ago
  I'm really not interested in how well PSK AES schemes fare post-quantum, because PSK isn't a realistic solution to any of the problems we use cryptography to address. I suggested, upthread, not using RSA (which depends on the hardness of factoring) and using ECC instead. How AES does post-quantum is not responsive to that advice.
  - Cieplak 10y ago
    You suggested ECC over RSA, implying that ECC offers greater security than RSA in the context of easy prime factorization. ECC's security relies on the hardness of the discrete logarithm. Yet, both prime factorization and the discrete logarithm are both special cases of the hidden subgroup problem over an Abelian group. In short, cracking RSA means cracking ECC, too. Am I wrong? Were you just joking?
    - tptacek 10y ago
      If I understand your argument properly, then I believe you to be wrong about the idea that tenably factoring 1024 or 2048 bit moduli implies a solution to the elliptic curve discrete modulus problem, yes.
    - Cieplak 10y ago
      @tptacek > I believe you to be wrong about the idea that tenably factoring 1024 or 2048 bit moduli implies a solution to the elliptic curve discrete modulus problem Probably. This mathy stuff is way over my head. I'm just repeating what I read in Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer [1] published by Peter W. Shor on behalf of AT&T Research in 1995. Supposedly his proof is valid, predicated on the existence of quantum computers. Quantum computers actually exist [insert epistemological joke here]. [1] https://arxiv.org/abs/quant-ph/9508027v2 https://arxiv.org/abs/quant-ph/9508027v2
      - sdevlin 10y ago
        You are talking about quantum attacks, whereas tptacek is talking about classical attacks.
- Filligree 10y ago
  So we'll take a performance hit, but it's fairly straightforward (relatively, very relatively) to extend the key sizes for symmetric crypto. The lack of any usable asymmetric algorithms is a much greater concern.