I'm reading FSB cryptographic hash function and the authors say that security of this function depends on NP-Complete Problem: "Decoding Linear Code Unlike most other cryptographic hash functions in use today" and I'm agree with the first part of claim. But I have a doubt respect to conventional hash functions for example the family SHA. The security of these functions depend of any NP-Complete Problem? According my understanding this hash function will be able to express than multivariate polynomials equations and solve multivariate polynomial equations is proved NP-Complete. Then a question is: Am I right?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
That Wikipedia article is full of errors and false claims. Most importantly, FSB has not been proven to be as hard as an NP-complete problem. This is because the syndrome decoding problem is NP-hard in the worst case, but FSB uses random instances of the problem. Indeed, these random instances may be much easier to break than arbitrary instances. There is no guarantee that these random instances are actually hard, nor do we know how to generate NP-hard instances of decoding problems.
More generally, there is no known cryptographic primitive (of any kind) whose security is provably based on NP-hardness alone.
answered Sep 2, 2014 at 13:33
-
$\begingroup$ Then, Is a conclusion claim "We have proposed a family of fast and provably secure hash functions." in eprint.iacr.org/2003/230.pdf wrong? $\endgroup$– juaninfCommented Sep 2, 2014 at 16:38
-
$\begingroup$ The functions are "provably secure" assuming that the new syndrome decoding problems they define are hard in the average case (for the distributions they consider). But that is basically a vacuous statement: it says "the function is provably secure assuming it is provably secure." The new problems are NP-hard in the worst case, but this says nothing about their hardness on random instances, nor about the security of the hash function. The paper addresses this point but is not especially clear about it. $\endgroup$ Commented Sep 2, 2014 at 16:50