Lattice-based Signatures and Hashes

Carlos Ribeiro

10/24/23, 10:26 PM

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.

1 + 0

lattice-crypto

hash-signature

Score:3

Crypto

Mark

10/24/23, 11:56 PM

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.

+ 1

Carlos Ribeiro

10/25/23, 6:43 AM

Thank you, @Mark. You are absolutely right. This is not EUF-CMA, not even close.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Lattice-based Signatures and Hashes

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.