2
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you, @Mark. You are absolutely right. This is not EUF-CMA, not even close. $\endgroup$ Oct 25, 2022 at 6:43

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.