5 ms·

The notions of hardness for practical cryptography are a bit different than ones in complexity theory. One difference is obviously the asymptotics. Just becaus

The notions of hardness for practical cryptography are a bit different than ones in complexity theory. One difference is obviously the asymptotics. Just because something is in P (generally considered "easy" in complexity theory) does not mean it is feasible to compute - maybe the complexity is N^256 or even N^2 but with a huge constant. OTOH even if we show that something is "harder than P", it does not mean it is infeasible to compute - strictly speaking P is only about deterministic complexity and worst case. So a problem where 99% instances are practically easy to compute can still be harder than P, yet too easy for crypto.

Vervious 5y ago
Just wanted to emphasize your point about "worst case hardness" -- even if 3SAT turns out to be hard (due to P != NP), it is only hard in the worst case (for a very small subset of all possible 3SAT problems). Most 3sat problem instances are (probably?) easy. In crypto, we need to sample "average case hard" problems, where on average, a random problem that we sample is hard. This is in contrast to, for instance, uniformly sampling from the set of all 3SAT instances, which gives an easy problem on average. A continuation of this line of research essentially looks at turning worst case hard problems into average case hard problems. Asymptotics are already way on the backburner since we are in theory world. (Note that a One way function is average case hard)
zarzavat 5y ago
Difficulty in cryptography is boolean. Is there an attack which has fewer steps than the brute force constant? If no? you’re good. If Yes? add more rounds, etc.
- Ar-Curunir 5y ago
  No, that’s not true. Plenty of cryptography is asymptotic.
- MauranKilom 5y ago
  By that specific notion, any hash where you can shave a hair of complexity off the first round (e.g. via SAT) is insecure, because it takes ever-so-slightly less effort to brute force it that way than pure brute force. Adding more rounds doesn't change that.
  - zarzavat 5y ago
    Sure if you want to be pedantic. However even if you double the number of rounds, the number of operations required to brute force increases by only a factor of 2. Since the number of operations is likely to be a very large number already, such a change is insignificant and we can consider the brute force cost to be independent of the number of rounds which is usually a small integer.
    - naniwaduni 5y ago
      The only difference between 1 and 2^128 is 128 small constant factors of 2.
Ar-Curunir 5y ago
Yes, that’s the difficult part that the research is tackling.
ravi-delia 5y ago
I believe, though I haven't done much with real complexity theory, that most feel P=BPP, and problems like the one you describe can be converted into more typical BPP problems. It's unproven, like most of the fun problems, but it's suspected. Regardless, this definitely isn't a result with much to say about practical cryptography, and it wasn't trying to be one. Just another, very interesting link in a field with lots of "if pigs could fly" proofs.

Vervious 5y ago

Just wanted to emphasize your point about "worst case hardness" -- even if 3SAT turns out to be hard (due to P != NP), it is only hard in the worst case (for a very small subset of all possible 3SAT problems). Most 3sat problem instances are (probably?) easy. In crypto, we need to sample "average case hard" problems, where on average, a random problem that we sample is hard. This is in contrast to, for instance, uniformly sampling from the set of all 3SAT instances, which gives an easy problem on average. A continuation of this line of research essentially looks at turning worst case hard problems into average case hard problems. Asymptotics are already way on the backburner since we are in theory world. (Note that a One way function is average case hard)

zarzavat 5y ago

Difficulty in cryptography is boolean. Is there an attack which has fewer steps than the brute force constant? If no? you’re good. If Yes? add more rounds, etc.

Ar-Curunir 5y ago
No, that’s not true. Plenty of cryptography is asymptotic.
MauranKilom 5y ago
By that specific notion, any hash where you can shave a hair of complexity off the first round (e.g. via SAT) is insecure, because it takes ever-so-slightly less effort to brute force it that way than pure brute force. Adding more rounds doesn't change that.
- zarzavat 5y ago
  Sure if you want to be pedantic. However even if you double the number of rounds, the number of operations required to brute force increases by only a factor of 2. Since the number of operations is likely to be a very large number already, such a change is insignificant and we can consider the brute force cost to be independent of the number of rounds which is usually a small integer.
  - naniwaduni 5y ago
    The only difference between 1 and 2^128 is 128 small constant factors of 2.

Ar-Curunir 5y ago

Yes, that’s the difficult part that the research is tackling.

ravi-delia 5y ago

I believe, though I haven't done much with real complexity theory, that most feel P=BPP, and problems like the one you describe can be converted into more typical BPP problems. It's unproven, like most of the fun problems, but it's suspected. Regardless, this definitely isn't a result with much to say about practical cryptography, and it wasn't trying to be one. Just another, very interesting link in a field with lots of "if pigs could fly" proofs.