# Lattice-based Signatures and Hashes

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?

 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.

Yes, but this homomorphic property still seems problematic. Namely, for $$i\in$$ 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.