> 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?
So I guess we will soon see a lot of crypto based on calculating edit distances?
> 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.
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.
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?
n^2 is insufficient, but 'polynomial' as a category is not necessarily bad.
P=NP is not the end of the world, by itself.
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.
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.