2
$\begingroup$

I've been messing around with lattice based cryptography and came across the SWIFFT algorithm, a provably secure cryptographic hash function which has a security proof stating that finding collisions is as hard as reducing a lattice, a provably difficult problem, infeasibly difficult.

I could understand basically using an orphaned lattice public key with no private key as a one way hash function that is as difficult to REVERSE, but I don't understand how they can equate finding collisions to being as difficult as solving a difficult lattice problem.

So how is it that SWIFFT's proof of finding collisions being as hard as solving a lattice problem, and not just reversing the hash?

$\endgroup$

1 Answer 1

2
$\begingroup$

I could understand basically using an orphaned lattice public key with no private key as a one way hash function that is as difficult to REVERSE, but I don't understand how they can equate finding collisions to being as difficult as solving a difficult lattice problem.

One thing that might be worth clarifying are the bolded words. The underlying lattice problems are variants of the Short Integer Solution problem (specifically a ring variant, I will skip these details).

Short Integer Solution: Let $n, m, q\in\mathbb{N}$. For a uniformly random matrix $A\gets (\mathbb{Z}/q\mathbb{Z})^{n\times m}$, find an integer vector $\vec x$ that is both

  1. Short Integer: $\vec x\in\mathbb{Z}^m$ with $\lVert \vec x\rVert \leq \beta$", and
  2. Solution: such that $A\vec x\equiv 0\bmod q$.

Here, $\beta$ is a bound on the size of $\vec x$. Larger $\beta$ is an easier problem. $\beta\geq \lVert (q,q,\dots,q)\rVert= q\sqrt{m}$ is trivial. Note that you might want to measure sizes in another norm (say the $\ell_\infty$ norm), where $\beta\geq \lVert (q,q,\dots,q)\rVert_\infty =q$ is trivial.

Anyway, not every cryptographic problem has a well-defined "public" or "private" part to it. In particular, some problems are known to be sufficient to build "minicrypt primitives", which includes at most "private key" schemes (and digital signatures). SIS is such a problem --- explicitly, we do not know how to build public-key encryption from it.

This is all to say that there is no reasonable way to associate a "public" or "private" key with the SIS problem. You could attempt to modify it such that this makes sense (for example, using "trapdoor lattice basis" constructions), but then this is just a different thing.


As for how SWIFFT is connected to SIS, the high-level idea is that SWIFFT computes $H(x)$ by

  1. serializing $x\mapsto \mathsf{serialize}(x)$ to be "short" (maybe a bit vector, I forget, and one can easily change this to being a vector in $\{-B, \dots, B\}^m$ for suitable $B$), then
  2. computes $A\mathsf{serialize}(x)$ for a suitable random matrix $A$.

This only defines a compression function (you still need to turn it into a hash to deal with arbitrary long inputs), but suffices to explain how collisions $\implies$ solutions to SIS, and can likely apply a generic compression function to hash function transformation, so I will skip this detail.

Given a collision $H(x) = H(y)$, we have that $A\mathsf{serialize}(x) \equiv A\mathsf{serialize}(y)\bmod q\implies A(\mathsf{serialize}(x)-\mathsf{serialize}(y))\bmod q = 0$. As we serialize inputs to be short, we have that $\mathsf{serialize}(x)-\mathsf{serialize}(y)$ is still moderately short (at most a factor 2 larger), so is (if everything is parameterized correctly) a short integer solution, i.e. a solution to our lattice problem.

As mentioned before, SWIFFT actually is defined over polynomial rings ("Ring SIS"), so there is some additional complexity as a result of this, but it isn't fundamental, and instead is done for efficiency reasons (allowing one to compute the matrix-vector product $Ax$ efficiently using the FFT).

$\endgroup$
2
  • $\begingroup$ So you're saying finding suitably short basis vectors is enough to result in a hash collision? $\endgroup$
    – August H
    Commented Nov 14, 2022 at 15:53
  • $\begingroup$ Its the opposite actually. The above describes how one can convert any SWIFFT collision into a short vector in the SIS lattice. $\endgroup$
    – Mark Schultz-Wu
    Commented Nov 14, 2022 at 19:45

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.