7 ms·

Post-quantum RSA

71 points by colinprince 9y ago

StavrosK 9y ago
> As part of the attack analysis, this paper introduces a new quantum factorization algorithm that is often much faster than Shor's algorithm Isn't that also huge news, depending on the definition of "often"?
- mr_overalls 9y ago
  IANAC (I am not a cryptographer), but this would seem to be big news, given the hardware to run it. I wonder if a quantum computing revolution would cause a resurgence of research into symmetric encryption algorithms? Because doesn't Shor's algorithm basically destroy asymmetric encryption (i.e., integer-factorization schemes like RSA are solvable in polynomial time), while symmetric encryption is only weakened? Namely, I think I remember reading that a quantum computer can search through a space of size 2^n in time 2^(n/2) for AES & friends.
  - devsigner 9y ago
    IANL (I am no lawyer), but it would seem to be all this elaborate crypto can be thwarted with a $5.00 wrench, as per XKCD 538[0] [0]: https://www.xkcd.com/538/ https://www.xkcd.com/538/
  - xoa 9y ago
    >Namely, I think I remember reading that a quantum computer can search through a space of size 2^n in time 2^(n/2) for AES & friends. I believe you're thinking of Grover's algorithm, which as you remember offers the ability to search for a value in a function domain in O(sqrt(N)). This is trivially countered just by doubling the key length, a 128-bit key probably couldn't be considered secure (average 2^64 evaluations) but a 256-bit would still average 2^128 and 512-bit 2^256. I vaguely recall there was some speculation that applied de Broglie–Bohm theory, if it was accurate, could allow a mild improvement but even then it only changed it to cube-root, which again could be countered with slightly larger keys (in practice 512-bit would still be plenty even then). At least for now there don't appear to be any major algorithmic implications for symmetrical encryption from a theoretical future scalable general purpose quantum computer. Granted, there may be some practical historical ones, and in a few cases they could be of significance. If agencies have archived data of interest encrypted with 128-bit in the past, they may gain the ability to gain access to it within the next decade or two. A lot of it might be well past its proverbial sell-by date but not all if those using it were counting on it last much longer then they'd be alive.
    - swordswinger12 9y ago
      There is a lower bound by Bennett et al. ("Strengths and weaknesses of quantum computing", SIAM JoComputing 1997) that shows Grover's algorithm is optimal for the generic search problem, so further lowering the asymptotic runtime is probably impossible. EDIT: Also note that quantum cryptanalytic attacks may be able to break specific symmetric ciphers by exploiting some structure specific to the cipher. But you're correct that QCs don't generically break symmetric cryptography.
  - AlyssaRowan 9y ago
    And indeed (from my skim-read, and please bearing in mind that I know very little about quantum computing) the paper seems to combine that same Grover's algorithm used to speed up just about any brute-force search with ECM, to find small primes more efficiently than Shor's algorithm in this case. Then it constructs a 1 terabyte RSA parameter, so big neither algorithm can currently attack it using a computer (quantum or otherwise) of practical size, as all known quantum attacks (including the new presented) would still need over a 2¹⁰⁰ workfactor; the 2³¹ factors they would need to find are each 4096 bits long themselves, if I'm reading it right? Needless to say, that is a trifle on the heavy side and definitely isn't your first practical choice (those would be lattice-, code- or hash-based primitives), but it is possible, and that's impressive (to me) by itself! Nice work.
- y7 9y ago
  Not really. Shor's algorithm is asymptotically still a lot faster than their new algorithm (polynomial vs exponential), although it might perform slower for primes up to some fixed size. This is generally less important in cryptography though, especially when determining your security gap. Also, while new, this result isn't really surprising. That Grover's algorithm can be applied to get a quadratic improvement over existing classical search algorithms has been known for a long time.
swordswinger12 9y ago
THIS PAPER IS: a nice, thought-provoking paper that is nevertheless purely speculative, and also more than a little tongue-in-cheek in parts. (Note that one of the keywords is "Make RSA Great Again".) It's basically pointing out that there is a small gap between the costs of legitimately using RSA and factoring via Shor's algorithm. With truly massive keys, this gap can be exploited to provide concrete security guarantees for RSA even in the presence of fast quantum computers. THIS PAPER IS NOT: a revolutionary new quantum factoring algorithm. They show how to apply quantum Grover search to a particular step of a known factorization algorithm based on elliptic curves. QUANTUM COMPUTING DOES: break public-key cryptosystems based on the hardness of factoring and finding discrete logarithms. Additionally, it gives a quadratic speedup in generic search problems (via Grover search) which effectively halves the key size of symmetric encryption schemes and yields faster algorithms for things like finding collisions in hash functions. QUANTUM COMPUTING (PROBABLY) DOES NOT: break all asymmetric cryptography. There is no known proof of this, but it's widely believed that asymmetric cryptosystems based on different hardness assumptions are not vulnerable to (non-generic) attacks by quantum computers.
- VLM 9y ago
  "With truly massive keys" My favorite quote from the paper on that topic is "Something expensive might nevertheless be useful if it is the least expensive way to achieve the user’s desired security goal" Post quantum crypto isn't the end of crypto, is the end of the meme that nation-state-proof cryptography is "too cheap to meter" (A nuclear power phrase from the old days) The pre-quantum landscape is cheap unbreakable algos implemented in easily breakable ways as a part of easily breakable systems, so there's quite a bit of criminal activity going on out there. The post-quantum landscape is very expensive unbreakable algos implemented by professionals because the cost (computational and financial) is large. The involvement of professionals indicates that criminal activity based on breaking crypto implementations is likely to drop. Its likely that Hollywood style multiple levels of crypto will soon exist. The days of being able to keep the NSA out of your wifi access point will be over unless you're willing to spend ridiculous amounts of money. However, for a very modest expense it'll still be possible to keep your neighbor off your wifi, wide open to nation states, sure. But my wifi leaching neighbor is a more realistic adversary than the entire NSA.
komali2 9y ago
> this paper introduces a new quantum factorization algorithm, GEECM, Am I blind or did they not include the actual algorithm in the paper? I'm not very knowledgeable in this sort of stuff so to be fair I was skimming for just a simple writeout of the algorithm, I may have just missed it.
- cwmma 9y ago
  page 7 has it

71 points by colinprince 9y ago

> As part of the attack analysis, this paper introduces a new quantum factorization algorithm that is often much faster than Shor's algorithm Isn't that also huge news, depending on the definition of "often"?

mr_overalls 9y ago
IANAC (I am not a cryptographer), but this would seem to be big news, given the hardware to run it. I wonder if a quantum computing revolution would cause a resurgence of research into symmetric encryption algorithms? Because doesn't Shor's algorithm basically destroy asymmetric encryption (i.e., integer-factorization schemes like RSA are solvable in polynomial time), while symmetric encryption is only weakened? Namely, I think I remember reading that a quantum computer can search through a space of size 2^n in time 2^(n/2) for AES & friends.
- devsigner 9y ago
  IANL (I am no lawyer), but it would seem to be all this elaborate crypto can be thwarted with a $5.00 wrench, as per XKCD 538[0] [0]: https://www.xkcd.com/538/ https://www.xkcd.com/538/
- xoa 9y ago
  >Namely, I think I remember reading that a quantum computer can search through a space of size 2^n in time 2^(n/2) for AES & friends. I believe you're thinking of Grover's algorithm, which as you remember offers the ability to search for a value in a function domain in O(sqrt(N)). This is trivially countered just by doubling the key length, a 128-bit key probably couldn't be considered secure (average 2^64 evaluations) but a 256-bit would still average 2^128 and 512-bit 2^256. I vaguely recall there was some speculation that applied de Broglie–Bohm theory, if it was accurate, could allow a mild improvement but even then it only changed it to cube-root, which again could be countered with slightly larger keys (in practice 512-bit would still be plenty even then). At least for now there don't appear to be any major algorithmic implications for symmetrical encryption from a theoretical future scalable general purpose quantum computer. Granted, there may be some practical historical ones, and in a few cases they could be of significance. If agencies have archived data of interest encrypted with 128-bit in the past, they may gain the ability to gain access to it within the next decade or two. A lot of it might be well past its proverbial sell-by date but not all if those using it were counting on it last much longer then they'd be alive.
  - swordswinger12 9y ago
    There is a lower bound by Bennett et al. ("Strengths and weaknesses of quantum computing", SIAM JoComputing 1997) that shows Grover's algorithm is optimal for the generic search problem, so further lowering the asymptotic runtime is probably impossible. EDIT: Also note that quantum cryptanalytic attacks may be able to break specific symmetric ciphers by exploiting some structure specific to the cipher. But you're correct that QCs don't generically break symmetric cryptography.
- AlyssaRowan 9y ago
  And indeed (from my skim-read, and please bearing in mind that I know very little about quantum computing) the paper seems to combine that same Grover's algorithm used to speed up just about any brute-force search with ECM, to find small primes more efficiently than Shor's algorithm in this case. Then it constructs a 1 terabyte RSA parameter, so big neither algorithm can currently attack it using a computer (quantum or otherwise) of practical size, as all known quantum attacks (including the new presented) would still need over a 2¹⁰⁰ workfactor; the 2³¹ factors they would need to find are each 4096 bits long themselves, if I'm reading it right? Needless to say, that is a trifle on the heavy side and definitely isn't your first practical choice (those would be lattice-, code- or hash-based primitives), but it is possible, and that's impressive (to me) by itself! Nice work.
y7 9y ago
Not really. Shor's algorithm is asymptotically still a lot faster than their new algorithm (polynomial vs exponential), although it might perform slower for primes up to some fixed size. This is generally less important in cryptography though, especially when determining your security gap. Also, while new, this result isn't really surprising. That Grover's algorithm can be applied to get a quadratic improvement over existing classical search algorithms has been known for a long time.

swordswinger12 9y ago

THIS PAPER IS: a nice, thought-provoking paper that is nevertheless purely speculative, and also more than a little tongue-in-cheek in parts. (Note that one of the keywords is "Make RSA Great Again".) It's basically pointing out that there is a small gap between the costs of legitimately using RSA and factoring via Shor's algorithm. With truly massive keys, this gap can be exploited to provide concrete security guarantees for RSA even in the presence of fast quantum computers. THIS PAPER IS NOT: a revolutionary new quantum factoring algorithm. They show how to apply quantum Grover search to a particular step of a known factorization algorithm based on elliptic curves. QUANTUM COMPUTING DOES: break public-key cryptosystems based on the hardness of factoring and finding discrete logarithms. Additionally, it gives a quadratic speedup in generic search problems (via Grover search) which effectively halves the key size of symmetric encryption schemes and yields faster algorithms for things like finding collisions in hash functions. QUANTUM COMPUTING (PROBABLY) DOES NOT: break all asymmetric cryptography. There is no known proof of this, but it's widely believed that asymmetric cryptosystems based on different hardness assumptions are not vulnerable to (non-generic) attacks by quantum computers.

VLM 9y ago
"With truly massive keys" My favorite quote from the paper on that topic is "Something expensive might nevertheless be useful if it is the least expensive way to achieve the user’s desired security goal" Post quantum crypto isn't the end of crypto, is the end of the meme that nation-state-proof cryptography is "too cheap to meter" (A nuclear power phrase from the old days) The pre-quantum landscape is cheap unbreakable algos implemented in easily breakable ways as a part of easily breakable systems, so there's quite a bit of criminal activity going on out there. The post-quantum landscape is very expensive unbreakable algos implemented by professionals because the cost (computational and financial) is large. The involvement of professionals indicates that criminal activity based on breaking crypto implementations is likely to drop. Its likely that Hollywood style multiple levels of crypto will soon exist. The days of being able to keep the NSA out of your wifi access point will be over unless you're willing to spend ridiculous amounts of money. However, for a very modest expense it'll still be possible to keep your neighbor off your wifi, wide open to nation states, sure. But my wifi leaching neighbor is a more realistic adversary than the entire NSA.

komali2 9y ago

> this paper introduces a new quantum factorization algorithm, GEECM, Am I blind or did they not include the actual algorithm in the paper? I'm not very knowledgeable in this sort of stuff so to be fair I was skimming for just a simple writeout of the algorithm, I may have just missed it.

cwmma 9y ago
page 7 has it