Talk:Fast syndrome-based hash

	This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography articles
???	This article has not yet received a rating on the importance scale.
	This article is supported by WikiProject Computer science.

Is it me, or are there some problems with the example? s = 010011, so n = 6 and w = 3. The first paragraph says H is an r*n matrix, but the example uses a 4*12 matrix instead of a 4*6 matrix. --Skrapion (talk) 17:36, 29 April 2010 (UTC)[reply]

A cryptographic hash function can't be proved as hard as an NP-Complete problem

It might be able to be a single instance/case of a problem which is known to be NP-Complete (better to say NP-Hard IMO as the actual decoding problem may not be in NP, unsure). But that says nothing about it being hard in that specific case, only in the worst case. DemocraticLuntz (talk) 13:09, 23 March 2017 (UTC)[reply]

This is a valid comment, and the article's claim about hardness should be elaborated on, or removed. That some problem is NP-hard, does not say anything at all about any instances of that problem. Huge instances of the SAT problem are routinely solved, even though SAT is NP-hard. Same could hold of any "provably secure" cryptographic hash function: particular uses of the hash function could actually be easy to break, even when the general problem were NP-hard. NP-hardness as an indication of "hardness" only means that the "there appear to be lots of instances that take an exponential time to solve", while lots and lots of instances could be trivial at the same time. — Preceding unsigned comment added by 130.233.97.85 (talk) 10:56, 19 August 2019 (UTC)[reply]