2
$\begingroup$

I read that SWIFFT is a linear hash function, but I don't understand what this means. The obvious interpretation is that if you have inputs $X1, X2$ each of which is an array of 16 64-dimensional binary vectors, then $H(X1) + H(X2) = H(X1 + X2)$. But then that leaves me confused about what $X1 + X2$ represents. Are each of the 16 vectors in the two vector arrays added pairwise? If so, wouldn't that potentially result in a vector array whose scalar values are no longer binary? Which would be undefined since the function's domain is $(\{ 0,1 \}^{64})^{16}$? If each of the 16 vectors in the two vector arrays is added pairwise, are they added modulo 2 to preserve the binary-ness?

And finally, if I have data that I split into $N$ such vector arrays that I want to hash, how would I do that with SWIFFT? I guess, the obvious answer would be to compute $\sum_{i=1}^N H(Xi)$, but wouldn't that mean that every permutation of my $N$ chunks would yield the same hash? Is there a way to preserve linearity/homomorphism, while making the order of the chunks important?

$\endgroup$

1 Answer 1

3
$\begingroup$

SWIFFT's main definition is of a compression function. This can be converted to a hash function in many (standard) ways, e.g. the MD transform. The SWIFFT paper doesn't bother with discussion of this (routine) process.

The SWIFFT compression function may be written mathematically as

$$ (y_1(x),\dots,y_m(x))\mapsto\sum_{i=1}^{m}a_i(x)y_i(x). $$ where

  • $a_i(x)\in\mathbb{Z}_q[x]/(x^{2^k}+1)$ are public parameters, and
  • $y_i(x)$ are polynomials with binary coefficients, which encode the input to the compression function.

This expression is Equation (1) in the SWIFFT paper (rewritten to make the polynomials more explicit). I'll write $h(y_1,\dots,y_m)$ for the above function.

This function is linear in the sense that

$$ h(y_1,\dots,y_m) + h(y_1',\dots,y_m') = h(y_1+y_1', \dots, y_m+y_m') $$

Note that both $+$'s are addition in the polynomial ring $\mathbb{Z}_q[x]/(x^{2^k}+1)$. Note also that while the above identity holds mathematically, SWIFFT always parses its input to have binary coefficients, and $y_i(x)+y_i(x)'$ need not have binary coefficients, so it is not "totally linear". Instead, it is a linear function with a domain that is not a linear subspace (more properly "not a sub-module" of the domain but whatever).

This means your concerns like

If so, wouldn't that potentially result in a vector array whose scalar values are no longer binary

are valid. This will often not be the case for SWIFFT. I don't think there's an obviously useful application of its linearity, instead its linearity is "proof" that it is not a random oracle. This is because it satisfies $h(e_0) + h(e_1) = h(e_0+e_1)$ (where $e_i$ is an appropriate basis vector), which a random function does not satisfy with high probability.

If each of the 16 vectors in the two vector arrays is added pairwise, are they added modulo 2 to preserve the binary-ness?

I don't think so. It's also worth emphasizing that just because the SWIFFT compression function has a homomorphic property, does not mean that a hash function built using SWIFFT willl have this property.

Note that if you want a homomorphic hash function that is "actually homomorphic", there are candidates. Generally these are set homomorphic. In particular, if you have some database $\mathcal{D}$, there should be some way to

  1. compute $h = H(\mathcal{D})$, and
  2. efficiently update $h\mapsto h' := H(\mathcal{D}\cup \{d'\})$, without completely recomputing the hash.

See for example this paper. Separately, one could define a variant of SWIFFT that allows larger inputs $\{-B,-B+1,\dots, B-1, B\}^n$. This was (roughly) asked on this question, and Micciancio has written a paper on this. But again, the domain of such compression functions is not a sub-module, as it is not closed under addition. Simply put, given two inputs $\vec x, \vec x'$, there need not be an input $\vec x''$ such that

$$h(\vec x) + h(\vec x') = h(\vec x+\vec x').$$

My understanding is that this non-linearity is key to the proof of security, but this is from hearing someone talk about the construction in high-level terms, I haven't checked where in the security proof things would fail myself.

$\endgroup$
1
  • $\begingroup$ thankyou, again, for an amazing answer with more links to look at (i was the guy who asked the other question you referenced too) $\endgroup$ Commented Mar 28 at 6:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.