Subset Sum Hashes

This link discusses something called a 'subset-sum hash function'. I'm having a little difficulty understanding the algorithm, and I can't seem to find any existing implementations to reference. Could someone point me to a reference implementation or explain how to construct M as per the first paper linked in that discussion:

If I'm understanding correctly, you initialize M as an array of d x m numbers mod p and then you map a string by going through the 16th row and multiplying the bits of x by the columns within that row? What's so special about the 16th row, or am I misunderstanding something? Also, if the input string has more than m bits, how would I hash that value to one output? Would hashing that in (m - log2(p))-bit blocks and then inputting the hash of the previous block concatenated with the next block to the hash function again work?

• Actually, I'm pretty sure that the 16 in the cited text is a reference to a footnote, and not a part of the formula. – poncho Jul 23 '20 at 15:47
• @poncho oops...In that case, what exactly do I do with the column of values then? Sum them? – Lev Knoblock Jul 23 '20 at 16:26

How are you supposed to interpret $$\sum_{i=1}^m x_iM(i)$$?

This is actually a matrix multiplication, multiplying the vector $$x$$ with the matrix $$M$$.

As for the notation they use, $$M(i)$$ stands for a vector of $$d$$ values. What you end up doing to evaluate $$x_iM(i)$$ is multiply each element of the vector by $$x_i$$ individually; this results in another vector of $$d$$ values (doing all this computation modulo $$p$$)

Then, to evaluate $$\sum_{i=1}^m x_iM(i)$$, you take the $$m$$ different vectors (for each of the possible $$i$$ values), and adding them together element-wise, coming up with yet another vector of length $$d$$ (which is the result).

Could someone point me to a reference implementation or explain how to construct M as per the first paper linked in that discussion

I don't have a reference implementation; however as to how to construct $$M$$, they stated that "The entries of $$M$$ should be drawn at random". They recommended using nothing-up-my-sleeve numbers; they gave an example of using the digits of $$\pi$$; an alternative way may be to use squeezed outputs from $$\text{Shake}( "\text{Subset sum hash}" )$$

Also, if the input string has more than m bits, how would I hash that value to one output? Would hashing that in (m - log2(p))-bit blocks and then inputting the hash of the previous block concatenated with the next block to the hash function again work?

Well, the iterated approach would give collision resistance (assuming that a single operation is collision resistant).

An alternative approach might be just increase $$m$$; that's one nice thing about using Shake to generate your $$M$$ matrix; it'll generate all the random-looking values you could want. I didn't think the subset problem became significantly easier as you increased $$m$$...

• Interpreting it as a matrix multiplication makes a lot more sense than what I was thinking. Thanks! – Lev Knoblock Jul 23 '20 at 17:46