3
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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).

$\endgroup$

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.