Are rejected Dilithium commitments secret?

Question

On 6 March, Yi Lee sent over the NIST mailing list an announcement of their submitted paper that found a flaw in the original security proof for Dilithium. In their manuscript, they fix the proof on paper, and they also verified whole proof using EasyCrypt. URL: http://ia.cr/2023/246

In Section 3.2, paragraph "The ‘Program once’ game hop", they bound the distance between $\mathcal{A}^\textsf{Prog}$ and $\mathcal{A}^\textsf{Trans}$, where $\textsf{Prog}$ is an oracle that programs $H$ for all inputs $(w, m)$ that were queried in the signature generation algorithm, and $\textsf{Trans}$ is an oracle that only programs $H$ for the $(w, m)$ input that was used in generating the accepted signature. This game hop adds a bias to $H$, biasing it towards $(w, m)$ tuples that correspond to accepting transcripts (as the only $(w,m)$ tuples programmed into $H$ are from accepted transcripts).

In the paper, it is mentioned that it is hard for $\mathcal{A}$ to notice this change, "because $w$ is chosen with high entropy and not revealed to $\mathcal{A}$. Conversely, leaking rejected $w$s breaks the security reduction. But now I am wondering:

Should the rejected $w$s considered to be secret? Or in other words, does leaking the rejected $w$s always break the zero knowledgeness property of Dilithium?

Or is there reason to believe that another security reduction could be constructed in a way that allows for the leaking of the rejected $w$s?

Answer 1

I can't make this into a full attack, but $\mathbf{w}_1$ (using the notation of the Dilithium spec) gives non-trivial information about the secret.

It seems to me like recovering $\mathbf{y}$ from $\mathbf{w}_1$ is a learning-with-rounding problem; I don't see that anywhere in the spec so I might be completely wrong but I suspect that this will be generally hard.

However, $\mathbf{w}_1$ gives you the inputs to $\mathbf{H}(\mu\Vert\mathbf{w}_1)$, which deterministically gives $c\in B_\tau$.

Suppose that $\Vert c\mathbf{s}_1\Vert_\infty= k$ and in fact the largest component has value $(-1)^{k_0}k$ (where $k_0\in\{0,1\}$ and we don't know it). Then the probability that $\mathbf{z}$ is accepted is the probability that all component of $\mathbf{y}$ are chosen to be below $\gamma_1 - \beta - (-1)^{k_0}k$; this will be $\left(\frac{\gamma_1 - \beta - (-1)^{k_0}k}{\gamma_1}\right)^N$ where $N$ is the number of components (should be the degree of the polynomial ring times the number of components of the module). Okay, technically this is slightly off if $c\mathbf{s}_1$ has a large negative component,

Running through the level 2 parameters, then the probability of being accepted if $k=70$ is 30% larger than the probability of being accepted if $k=35$ (if both are positive). In other words, whether or not the sample is rejected tells you some pretty good information about $\Vert c\mathbf{s}_1\Vert_\infty$ and the sign of this largest component.

To me this feels scary enough that I would regard this as insecure (definitely is not zero-knowledge!), even though I can't come up with an explicit attack. If you gave me a bunch of $c$ that were rejected I can think of some ad-hoc ways I would use them to recover $\mathsf{s}_1$, but I don't know how to make an explicit algorithm out of this.