Score:7

Are rejected Dilithium commitments secret?

cn flag

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?

swineone avatar
ru flag
I'm way out of my league here as I'm an implementation guy with weak formalism skills, but if the $w$s correspond to the to the actual $(\mathbf{z}, \mathbf{h})$ signature output by Dilithium, then the [specification](https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf) says, in the last paragraph of p. 4: "If $z$ were directly output at this point, then the signature scheme would be insecure due to the fact that the secret key would be leaked. To avoid the dependency of $z$ on the secret key, we use rejection sampling."
user5207081 avatar
cn flag
@swineone In the paper, $w$ corresponds to Dilithium's $\mathbf{w_1}$ and $z$ corresponds to Dilithium's $\mathbf{z}$. Leaky $z$s do clearly leak info about the secret key, but I am wondering, could "bad" $w$s also leak in some kind of way?
in flag
See the comments in section 3.2 of [Protecting Dilithium against Leakage Revisited Sensitivity Analysis and Improved Implementations](https://eprint.iacr.org/2022/1406). They decide not to mask $\mathbf{w}_1$ (equating it with a separate LWR problem in the rejected cases).
Score:1
us flag

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.

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

mangohost

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.