We also show that the following constraint satisfaction problem is $\np$-hard. The constraints are restricted to being XOR constraints, or Majority constraints on at most three variables each. The instances are further restricted by requiring that the constraints can be listed in a sequence C_1, C_2,...,C_m, such that for every constraint C_i, two of the variables in it occur only in constraints C_j, with |j-i|< 48. This problem is similar to the problem modeling the one-way function property of SHA-1.
Category / Keywords: Hash Functions, Linear Codes, minimum distance, CSPs, oneway functions Date: received 3 Oct 2005, last revised 28 Nov 2005 Contact author: csjutla at us ibm com Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation Version: 20051128:230646 (All versions of this report) Short URL: ia.cr/2005/350