Lattice-based Signatures and Hashes

Question

Although many different lattice-based signature schemes exist, Hash and Sign signatures schemes, like [GPV08], are prevalent. On the other hand, it is well known that collision-resistant hash functions may be built out of lattice problems [SWIFFT08]. However, I've never seen a scheme that combines both; why? Such composition seems obvious, so I guess there is a good reason for its absence.

Can you help me on finding out why?

Details follow:

Briefly, [GPV08] like signatures may be instantiated on a polynomial ring $\mathcal{R}_q = \mathbb{Z}_q[X]/\langle X^N+1 \rangle$, by setting up a vector $\overrightarrow{\mathbf{a}} \in \mathcal{R}_q^k$ with a trapdoor $t$, and signing messages by sampling a vector $\overrightarrow{\mathbf{\sigma}} \in \mathcal{R}_q^k$, with a small norm, such that $\langle\overrightarrow{\mathbf{a}}, \overrightarrow{\mathbf{\sigma}}\rangle = H(m)$, with the help of the trapdoor $t$. Where $H(m) \in \mathcal{R}_q$ is the hash of the message $m$ parsed into a polynomial. The verification of the signature $\overrightarrow{\mathbf{\sigma}}$ is just the validation that $\langle\overrightarrow{\mathbf{a}}, \overrightarrow{\mathbf{\sigma}}\rangle = H(m)$ and that the norm of $\overrightarrow{\mathbf{\sigma}}$ is small.

On the other hand, the [SWIFFT08] hash function family is roughly defined by $H_b(m)= \langle \overrightarrow{\mathbf{b}}, \overrightarrow{\mathbf{m}}\rangle$, where $\overrightarrow{\mathbf{b}} \in \mathcal{R}_q^l$ is a uniform polynomial vector with coefficients in $\mathbb{Z}_q[X]$ and $\overrightarrow{\mathbf{m}} \in \mathcal{R}_q^l$ is a message polynomial vector with coefficients in {0,1}. So the message space is $2^{ln}$ bits.

For messages of at most $n$ bits, it seems that it would be trivial to join the two techniques, but I've never seen it. Does anyone know why?

[Edit] Lyubashevsky et al., in their original paper [SWIFFT08] pointed out that SWIFFT functions were not suitable to be used as random Oracles, because they are homomorphic under addition, and that can be used to construct a distinguisher, but nothing is said about signatures. In fact, given its strong collision-resistance property, SWIFFT functions seem ideal for the purpose.

Answer 1

Lyubashevsky et al., in their original paper [SWIFFT08] pointed out that SWIFFT functions were not suitable to be used as random Oracles, because they are homomorphic under addition, and that can be used to construct a distinguisher, but nothing is said about signatures.

Yes, but this homomorphic property still seems problematic. Namely, for $i\in[2]$ let $(\vec \sigma_i, \vec m_i)$ be SWIFFT signatures of $\vec m_0, \vec m_1$ such that $\vec m_0+\vec m_1\in\{0,1\}^{\ell n}$. Then, $(\vec \sigma_0+\vec \sigma_1, \vec m_0+\vec m_1)$ will also be valid SWIFFT signature.

If we substitute SWIFFT in for $H(\cdot)$ in Hash-and-Sign signatures, this means that given two Hash-and-Sign signatures satisfying $\langle \vec a^0, \vec \sigma^0\rangle = H_b(\vec m_0)$ and $\langle \vec a^1, \vec \sigma^1\rangle = H_b(\vec m_1)$, we can create another Hash-and-Sign signature satisfying $\langle \vec a^0+\vec a^1, \vec \sigma^0+\vec \sigma^1\rangle = H_b(\vec m_0+\vec m_1)$. It is possible that the norm check on $\vec \sigma^1+\vec \sigma^1$ will reject this forgery, but seems unlikely to happen all that often.

This is to say that the linearity in SWIFFT seems to directly enable the forgery of Hash-and-Sign (instantiated using SWIFFT) signatures.