5 ms·

I disagree with the premise. There's no reason to assume that we can't implement a quantum-resistant asymmetric encryption system that is no more computationall

I disagree with the premise. There's no reason to assume that we can't implement a quantum-resistant asymmetric encryption system that is no more computationally expensive than what we already have. Hell, there's already work out there (http://eprint.iacr.org/2014/599.pdf http://eprint.iacr.org/2014/599.pdf) for a quantum-resistant key exchange algorithm that's fast enough to have only 21% less throughput than traditional elliptic Diffie-Hellman.

VLM 9y ago
Thats a good paper. I thought about it awhile and would retract my remarks of it being expensive and replace it with being expensive or risky. Also there's the problem of "what is the definition of post quantum" where a lot of people call 1995 or so after Shor "PQ", and maybe I'd retract that part of my comment and call it something like "way way long time in the future, which by whatever definition of post quantum, is also post quantum, lets call it 3000 AD" The trick in the big-key RSA paper is knowing how Shor works, because the average big-O is low for a randomly selected large number, but the maximal number of ops that could be required is extremely large and yet that number is "easily" constructible. So merely intentionally and methodically (and expensively) manufacture a "poison pill" composite that Shor can't possibly factor because that number was constructed specifically to make Shor algo fail, and you're RSA system will be good. The algo in your linked paper is very convenient. However its newer and not as seasoned and the wolves are snapping at its heels there was that paper around Thanksgiving last year (which did get retracted) claiming to partially quantum break LWE. https://arxiv.org/abs/1611.06999 https://arxiv.org/abs/1611.06999 I'd like to see a proof that there exists no possible theoretical quantum speedup against LWE. Yes I know there isn't one in currently described or implemented, I mean I can't find a proof that there cannot exist an attack against LWE. Or, a proof that a non-quantum attack against LWE cannot exist because in the end that would imply 1=2 or something invalid so by induction its unbreakable. In the year 3000 I think the odds are good that algos will still have a large ratio between the average ops when run against a random number vs the maximal ops when run against a constructable poison pill designed to require maximum number of ops. Yet in the year 3000 I would not put faith in any one algo that hadn't been broken by mid-2017 will never be broken. It seems better to bet on math as a field continuing to have algos with a wide spread, than to bet on any one algo. In that way I think it likely we'll get stuck with something like big key RSA over a long enough time period. While at the same time I can agree with you, yes in the post-quantum world starting in '94 and LWE starting in 2005 there was a post-quantum era from 2005 to at least mid 2017 where LWE was a fast unbroken post-quantum system. Will that end-date continue to 3000 AD? Right now I'm thinking about if the Shor trick could be applied to a theoretically quantum broken RLWE-KEX. Random Discrete Gaussian Sampling is random... Is it possible to calculate poison pill samples that would mess up a theoretically broken RLW-KEX (depending a lot on the characteristics of an imaginary break?) I found slides by Peikert online about how those samples are selected, which I haven't made sense of yet.
- openasocket 9y ago
  > "what is the definition of post quantum" where a lot of people call 1995 or so after Shor "PQ" I use the term quantum-resistant, which I think is more clear: crypto for which Grover's algorithm or Shor's algorithm cannot efficiently break it. > The algo in your linked paper is very convenient. However its newer and not as seasoned Totally agree, but it does show that you shouldn't just assume quantum-resistant crypto is necessarily computationally expensive. > I'd like to see a proof that there exists no possible theoretical quantum speedup against LWE. Don't hold your breath :). We don't even have a proof that integer factoring can't be broken in polynomial time in classical computers. We don't even know if one can make public key crypto unbreakable to classical computers (equivalent to P vs. NP problem). And the relationship of BQP (problems solvable in polynomial time on a quantum computer) to P and NP is still an open problem. It could turn out BQP=P, and quantum computers don't even give an asymptotic speedup over classical computers (I don't think that's likely, but it hasn't been proven one way or the other).
- tptacek 9y ago
  LWE isn't the only problem that's believed to be quantum-hard that can be used for a reasonably efficient DH primitive. Curve isogenies also appear to work, and they can take advantage of a tremendous amount of optimization work we've already done for curve math. There are also other CVP/SVP lattice problems. And this is sticking to problems that give us the same protocol-level interface; there are also quantum-hard public key algorithms that don't do that. The more important point here, though, is that there's nothing particularly "expensive" about this stuff. It's all slower than RSA and curves, but (in particular) curves have gotten much faster over the last 10 years, and obviously computers are getting faster and silicon offloads less expensive, so the performance setback here isn't that big. I'm also not sure why you have so much confidence in the conventional strength of RSA.
  - tptacek 9y ago
    ... not, by the way, that I'm willing to stipulate that LWE is all that risky; the underlying problems in LWE are also very well studied, preceding concerns about QC by a long time.

VLM 9y ago

Thats a good paper. I thought about it awhile and would retract my remarks of it being expensive and replace it with being expensive or risky. Also there's the problem of "what is the definition of post quantum" where a lot of people call 1995 or so after Shor "PQ", and maybe I'd retract that part of my comment and call it something like "way way long time in the future, which by whatever definition of post quantum, is also post quantum, lets call it 3000 AD" The trick in the big-key RSA paper is knowing how Shor works, because the average big-O is low for a randomly selected large number, but the maximal number of ops that could be required is extremely large and yet that number is "easily" constructible. So merely intentionally and methodically (and expensively) manufacture a "poison pill" composite that Shor can't possibly factor because that number was constructed specifically to make Shor algo fail, and you're RSA system will be good. The algo in your linked paper is very convenient. However its newer and not as seasoned and the wolves are snapping at its heels there was that paper around Thanksgiving last year (which did get retracted) claiming to partially quantum break LWE. https://arxiv.org/abs/1611.06999 https://arxiv.org/abs/1611.06999 I'd like to see a proof that there exists no possible theoretical quantum speedup against LWE. Yes I know there isn't one in currently described or implemented, I mean I can't find a proof that there cannot exist an attack against LWE. Or, a proof that a non-quantum attack against LWE cannot exist because in the end that would imply 1=2 or something invalid so by induction its unbreakable. In the year 3000 I think the odds are good that algos will still have a large ratio between the average ops when run against a random number vs the maximal ops when run against a constructable poison pill designed to require maximum number of ops. Yet in the year 3000 I would not put faith in any one algo that hadn't been broken by mid-2017 will never be broken. It seems better to bet on math as a field continuing to have algos with a wide spread, than to bet on any one algo. In that way I think it likely we'll get stuck with something like big key RSA over a long enough time period. While at the same time I can agree with you, yes in the post-quantum world starting in '94 and LWE starting in 2005 there was a post-quantum era from 2005 to at least mid 2017 where LWE was a fast unbroken post-quantum system. Will that end-date continue to 3000 AD? Right now I'm thinking about if the Shor trick could be applied to a theoretically quantum broken RLWE-KEX. Random Discrete Gaussian Sampling is random... Is it possible to calculate poison pill samples that would mess up a theoretically broken RLW-KEX (depending a lot on the characteristics of an imaginary break?) I found slides by Peikert online about how those samples are selected, which I haven't made sense of yet.

openasocket 9y ago
> "what is the definition of post quantum" where a lot of people call 1995 or so after Shor "PQ" I use the term quantum-resistant, which I think is more clear: crypto for which Grover's algorithm or Shor's algorithm cannot efficiently break it. > The algo in your linked paper is very convenient. However its newer and not as seasoned Totally agree, but it does show that you shouldn't just assume quantum-resistant crypto is necessarily computationally expensive. > I'd like to see a proof that there exists no possible theoretical quantum speedup against LWE. Don't hold your breath :). We don't even have a proof that integer factoring can't be broken in polynomial time in classical computers. We don't even know if one can make public key crypto unbreakable to classical computers (equivalent to P vs. NP problem). And the relationship of BQP (problems solvable in polynomial time on a quantum computer) to P and NP is still an open problem. It could turn out BQP=P, and quantum computers don't even give an asymptotic speedup over classical computers (I don't think that's likely, but it hasn't been proven one way or the other).
tptacek 9y ago
LWE isn't the only problem that's believed to be quantum-hard that can be used for a reasonably efficient DH primitive. Curve isogenies also appear to work, and they can take advantage of a tremendous amount of optimization work we've already done for curve math. There are also other CVP/SVP lattice problems. And this is sticking to problems that give us the same protocol-level interface; there are also quantum-hard public key algorithms that don't do that. The more important point here, though, is that there's nothing particularly "expensive" about this stuff. It's all slower than RSA and curves, but (in particular) curves have gotten much faster over the last 10 years, and obviously computers are getting faster and silicon offloads less expensive, so the performance setback here isn't that big. I'm also not sure why you have so much confidence in the conventional strength of RSA.
- tptacek 9y ago
  ... not, by the way, that I'm willing to stipulate that LWE is all that risky; the underlying problems in LWE are also very well studied, preceding concerns about QC by a long time.