4 ms·

> RSA (and Rabin) and conventional DH, both of which are looking increasingly sketchy in 2013. May I ask why you say this? (Not agreeing nor disagreeing, just

by pbsd 13y ago

> RSA (and Rabin) and conventional DH, both of which are looking increasingly sketchy in 2013. May I ask why you say this? (Not agreeing nor disagreeing, just curious.)

sillysaurus 13y ago
Elliptic curve cryptography isn't vulnerable to quantum computing. EDIT: This is mistaken. I was thinking of lattice-based cryptography, which isn't currently vulnerable to quantum computing. In the video game Final Fantasy, there's a spell called "Doom" which places a countdown over your head. When it reaches 0, you die. RSA is Doomed in exactly that sense: it's just a matter of time before RSA offers zero security, whereas elliptic curve cryptography remains (for now) unbroken.
- pbsd 13y ago
  It is [1]. Quantum computers, using Shor's algorithm, polynomially break any specialization of the abelian hidden subgroup problem; see [2] for a fairly complete list. Whatever reason to prefer elliptic curves over integer factorization or discrete log-based schemes must be classical. [1] http://arxiv.org/abs/quantph/0301141 http://arxiv.org/abs/quantph/0301141 [2] http://pqcrypto.org/quantum.html http://pqcrypto.org/quantum.html
  - sillysaurus 13y ago
    Oh. Then which (if any) algorithm is currently believed to be safe from quantum computing? I think I was thinking of lattice-based cryptography.
    - tptacek 13y ago
      There's a bunch of them. There's no known quantum algorithm for quickly decoding binary linear codes, so McEliece is one. The Clostest Vector Problem in linear algebra is another trapdoor that may be QC-resistent. You didn't ask, but it's worth saying: block ciphers, stream ciphers and hash functions aren't thought to be fundamentally threatened by QC the way IFP and DLP number theoretic cryptosystems are.
- damarquis 13y ago
  "it's just a matter of time before RSA offers zero security" This is not the only possible outcome. Scalable quantum computing could turn out to be impractical due to cost. Or new physics could be found that rules out scalable quantum computing. Personally, I find both of these outcomes unlikely, the second more than the first, but they do exist.
- tptacek 13y ago
  It's easy-ish to move from RSA to ECC schemes, because they have significantly smaller key sizes and gain efficiency. The same isn't true of lattice schemes, which have significantly larger keys. A switch to lattice or code-based crypto seems unlikely in the near future.
tptacek 13y ago
Daniel Bernstein has been talking about advances in IFP, particularly the batch numeric field sieve, for several years now; the question seems to be when, not if, 1024 bit RSA keys will be arbitrarily attackable. Meanwhile, over the past couple of months, there's been a flurry of activity on the DLP, particularly Antoine Joux' work on the index calculus approach. The IFP and DLP are intertwined problems, but RSA also depends on the hardness of the DLP, as does (obviously) DH and ElG. The advances we're currently seeing do not appear to threaten the elliptic curve discrete log problem. Quantum computing is an issue, but it looks like a far-off issue. The record for quantum factorization right now is 27, right? If you believe QC is a near-term threat, no mainstream number-theoretic (public key / key agreement) cryptosystem helps you; you need to be working with code-based or lattice-based crypto; nothing does this now. The problems motivating the shift from RSA to ECC are near-term, not far-off like QC. Shit, I didn't look who I was responding to. Ignore the tone; assume I'm addressing the thread, not you.
- pbsd 13y ago
  No problem. Agree that quantum is not really something to worry about, though it's a good thing that someone out there is thinking of alternatives. By the way, the Batch NFS has seemingly fallen out of favor. Despite being significantly faster in the usual RAM computational model, it has worse AT complexity than factoring integers one by one (see section 5 of [1]), due to its crazy storage requirements. It doesn't change the fact, of course, that RSA-1024 doesn't have much shelf life left. [1] http://eprint.iacr.org/2012/318 http://eprint.iacr.org/2012/318
- deleted 13y ago
  [deleted]

by pbsd 13y ago

> RSA (and Rabin) and conventional DH, both of which are looking increasingly sketchy in 2013. May I ask why you say this? (Not agreeing nor disagreeing, just curious.)

sillysaurus 13y ago

Elliptic curve cryptography isn't vulnerable to quantum computing. EDIT: This is mistaken. I was thinking of lattice-based cryptography, which isn't currently vulnerable to quantum computing. In the video game Final Fantasy, there's a spell called "Doom" which places a countdown over your head. When it reaches 0, you die. RSA is Doomed in exactly that sense: it's just a matter of time before RSA offers zero security, whereas elliptic curve cryptography remains (for now) unbroken.

pbsd 13y ago
It is [1]. Quantum computers, using Shor's algorithm, polynomially break any specialization of the abelian hidden subgroup problem; see [2] for a fairly complete list. Whatever reason to prefer elliptic curves over integer factorization or discrete log-based schemes must be classical. [1] http://arxiv.org/abs/quantph/0301141 http://arxiv.org/abs/quantph/0301141 [2] http://pqcrypto.org/quantum.html http://pqcrypto.org/quantum.html
- sillysaurus 13y ago
  Oh. Then which (if any) algorithm is currently believed to be safe from quantum computing? I think I was thinking of lattice-based cryptography.
  - tptacek 13y ago
    There's a bunch of them. There's no known quantum algorithm for quickly decoding binary linear codes, so McEliece is one. The Clostest Vector Problem in linear algebra is another trapdoor that may be QC-resistent. You didn't ask, but it's worth saying: block ciphers, stream ciphers and hash functions aren't thought to be fundamentally threatened by QC the way IFP and DLP number theoretic cryptosystems are.
damarquis 13y ago
"it's just a matter of time before RSA offers zero security" This is not the only possible outcome. Scalable quantum computing could turn out to be impractical due to cost. Or new physics could be found that rules out scalable quantum computing. Personally, I find both of these outcomes unlikely, the second more than the first, but they do exist.
tptacek 13y ago
It's easy-ish to move from RSA to ECC schemes, because they have significantly smaller key sizes and gain efficiency. The same isn't true of lattice schemes, which have significantly larger keys. A switch to lattice or code-based crypto seems unlikely in the near future.

tptacek 13y ago

Daniel Bernstein has been talking about advances in IFP, particularly the batch numeric field sieve, for several years now; the question seems to be when, not if, 1024 bit RSA keys will be arbitrarily attackable. Meanwhile, over the past couple of months, there's been a flurry of activity on the DLP, particularly Antoine Joux' work on the index calculus approach. The IFP and DLP are intertwined problems, but RSA also depends on the hardness of the DLP, as does (obviously) DH and ElG. The advances we're currently seeing do not appear to threaten the elliptic curve discrete log problem. Quantum computing is an issue, but it looks like a far-off issue. The record for quantum factorization right now is 27, right? If you believe QC is a near-term threat, no mainstream number-theoretic (public key / key agreement) cryptosystem helps you; you need to be working with code-based or lattice-based crypto; nothing does this now. The problems motivating the shift from RSA to ECC are near-term, not far-off like QC. Shit, I didn't look who I was responding to. Ignore the tone; assume I'm addressing the thread, not you.

pbsd 13y ago
No problem. Agree that quantum is not really something to worry about, though it's a good thing that someone out there is thinking of alternatives. By the way, the Batch NFS has seemingly fallen out of favor. Despite being significantly faster in the usual RAM computational model, it has worse AT complexity than factoring integers one by one (see section 5 of [1]), due to its crazy storage requirements. It doesn't change the fact, of course, that RSA-1024 doesn't have much shelf life left. [1] http://eprint.iacr.org/2012/318 http://eprint.iacr.org/2012/318
deleted 13y ago
[deleted]