5 ms·

> Edit distance is useful, but also very time-consuming to calculate. So I guess we will soon see a lot of crypto based on calculating edit distances?

• leni536 11y ago
  It's still polynomial though, I think it's not practical for crypto.
  • Dylan16807 11y ago
    n^100 is perfectly good for crypto. n^2 is insufficient, but 'polynomial' as a category is not necessarily bad. P=NP is not the end of the world, by itself.
    • dtech 11y ago
      Which order of n it is has no influence on crypto. The crux is whether there is a large difference in computing an answer and validating an answer. A technique which requires both n^100 for validation and computing is useless, a technique which requires n^2 for computation and log(log(n)) for validation would be fine (you just have to use sufficiently large n). It's just that problems with an exponential computation and polynomial validation provide an almost unbeatable cost-to-benefit ratio in terms of n. A n^2/log(log(n)) algorithm might require 10MB encryption keys to be secure, while a n^a/n algorithm like the current prime-based cryptosystems require ~4KB.
      • Dylan16807 11y ago
        Operations are not going to be sublinear. So that lower limit does make very small absolute orders matter. And I think it's implied that validation has to actually be possible on computers, so given that constraint an enormous number for brute-forcing will almost always be a solid option. So n^2/anything is going to suck. n^3/anything or n^4/anything may or may not suck. And n^100/n^small is great. Also RSA operations aren't n^a/n. They're sub-exponential to brute force, and n^3 to encrypt and decrypt. Unless you mean a different system.
• Sharlin 11y ago
  No. Quadratic speed is way too fast for crypto - besides, asymmetric cryptography relies on problems that are difficult to solve but candidate solutions are easy to validate! This is what the complexity class NP is about. As far as I know there's no way to check a solution for edit distance any faster than it takes to compute it in the first place. Also, the new proof just shows that edit distance is quadratic if P!=NP.
  • erikb 11y ago
    Yeah, don't know enough about it.
  • Scea91 11y ago
    I get what you mean but 'easy to validate' in the context of NP means 'can be validated in polynomial time'. It seems to me that you imply that edit distance is harder to validate than problems in NP. Edit distance itself is in NP since P is in NP.
    • bbrazil 11y ago
      The article says it's quadratic, which would put it in P as it's polynomial time.
      • Scea91 11y ago
        P is in NP.
    • Sharlin 11y ago
      I mean that there needs to be a fundamental difference between the difficulty of finding a solution and validating one. There's none in case of edit distance.
      • wolfgke 11y ago
        > I mean that there needs to be a fundamental difference between the > difficulty of finding a solution and validating one. There's none in > case of edit distance. If you consider the decision problem "Is the edit distance <= d?", there is (according to this result) a fundamental difference - though only a polynomial one. To see this, consider the following argument: Clearly the edit distance between strings of length m, n is bounded by m+n (>= d). So if we found a way to transform the string s1 into s2 using d steps, we can construct a certificate of length O(m+n) (worst case) steps, which can be verified in linear time. On the other hand (according to this result) you need Omega(m*n) (worst case) steps to find such a certificate.
• bbrazil 11y ago
  It's only quadratic, for asymmetric crypto you'd want something with a much higher complexity and preferably non-polynomial.
• tomelders 11y ago
  Hmmmm. That got me thinking about spam, and I went off on a tangent. What if an email could be parsed in such a way as to generate seed data for an an NP problem which the sender must solve and supply the answer in the in the email header... If the receiver can instantly dismiss any emails that provide an answer that can not be verified, then that could have a huge impact on the the spammers ability to send spam in the volumes they currently enjoy. A penalty of 5 seconds per email is unlikely to impact ordinary users, but would be a major pain for spammers. Also, could this be used to throttle user input to mitigate brute force attacks?
  • skosch 11y ago
    You're not the first one to think of this: https://en.wikipedia.org/wiki/Challenge%E2%80%93response_spam_filtering https://en.wikipedia.org/wiki/Challenge%E2%80%93response_spa...
  • Scea91 11y ago
    You would quickly run out of instances of a given NP problem that can be solved under 5 seconds.