5 ms·

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 demo

by 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

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.