How to reconstruct low order bits of $t$ of CRYSTALS-Dilithium from a small number of signatures?

Question

In FIPS 204 (https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.ipd.pdf): "The vector $\textbf{t}$ is compressed in the actual public key by dropping the $d$ least significant bits from each coefficient, thus producing the polynomial vector $\textbf{t}_1$. This compression is an optimization for performance, not security. The low order bits of $t$ can be reconstructed from a small number of signatures and, therefore, need not be regarded as secret."

However, there is no any reference.

How can I reconstruct $\textbf{t}_0$ from a small number of signatures?

Answer 1

While this doesn't fully answer your question (and is only mildly more interesting than a comment), I think the Dilithium authors just assume the adversary knows $\mathbf{t}_0$. See for example Footnote 5, where it is stated

Since for security, we assumed that $\mathbf{t}_0$ is known to the adversary ...

What NIST says is (hopefully) true, but I haven't seen it mentioned elsewhere, and I doubt it is relevant for actual security analysis (though it motivates why one may assume that $\mathbf{t}_0$ is known to the adversary). One can motivate this in other ways though, for example because it only makes the adversary's job (potentially) easier.

The more interesting nuance is actually dealing with the "hints". By this, I mean that randomly throwing away part of the public key could ostensibly cause issues with correct protocol execution. If done naively, this can occur. The dilithum authors add various additional data (that they call "hints") to signatures to ensure that this doesn't happen. One needs to ensure that these hints do not leak information/break things. This is important, as another NIST submission (qTesla) did not check this carefully, leading to the Dilithium authors having an attack on qTesla variants with "hints".

I've tried looking around further for a source backing up NIST's claim (the term to search on is "public key compression" for Dilithium), but didn't find anything. It is possible if one looks at the hints long enough (namely line 23, page 4 of this), you'll see a way to go from many hints to some estimate of $\mathbf{t}_0$. This would require unpacking enough notation that I haven't tried doing it though, but if you're still interested in the justification for NIST's claim I imagine this is what it is (though I cannot verify it myself).

Answer 2

We have been studying the idea of linear programming for some weeks, and we can confirm that it works. However it requires more than "several signatures": we actually found out that 2 million signatures are needed for t0 to consistently be the unique solution of the system in the case of Dilithium2. We are finishing a preliminary paper (writing/gathering data) that we will upload on eprint in a few days.

Update 05/09: We put the paper on eprint: https://eprint.iacr.org/2024/1373

We are still working on optimizations that could save us a factor of 10 on the number of signatures compared with current results.

Answer 3

With enough signatures, one can check compatibility of a guess for $t_0$ (one $R_q$ coordinate at a time) with the collection of data $$ \{\mathsf{MakeHint}(-ct_0, w'_{\text{Approx}})=h\}. $$ However, this still seems difficult (large search space for each coordinate of $t_0$). [Perhaps the system of equations above can be turned into a system of inequalities that will have a unique solution, some linear programming problem?]

---

Here's a paper giving an algorithm to reconstruct $t_0$: "Uncompressing Dilithium's public key," https://eprint.iacr.org/2024/1373