Another question on Dilithium hints

[Mike Hamburg]

Hi all,

While I’m bugging everyone about Dilithium hinting, I have another few observations that may warrant changes. These ones aren’t really problems though. Please refer to Figure 4 of the Round 3 spec, or Algorithm 2 of the FIPS-204 draft.


Observation 1: The invocation of MakeHint could be written as MakeHint(ct0, w - cs2) instead of MakeHint(-ct0, w - cs2 + ct0). This produces the exact same answer, since MakeHint immediately adds its arguments and the ct0 cancels out.

Observation 2: unless I am miscalculating, for Dilithium-3 and Dilithium-5, we can never have |ct0| >= gamma2. So that check is only necessary for Dilithium-2.

Observation 3: Lemma 1 guarantees that UseHint gives the right answer if |ct0| <= gamma2. But tentative signatures are rejected if |ct0| >= gamma2. Shouldn’t it instead reject if |ct0| > gamma2, since the == case is OK per the lemma?

Alternative 3a: … or rather, perhaps it should reject if |ct0| > gamma2 + beta, which (again unless I’m miscalculating) is a sufficient check given that we already require |r0| < gamma2 - beta.

Alternative 3b: … or forget about bounding |ct0|: the signer could instead check that UseHint(h, r + ct0) == w1, since that’s the only reason we care anyway?

In my view, Observation 3 isn’t worth changing the spec over: it’s too late, and — again if I’m calculating correctly — using Observation 3b reduces the rejection rate from ~7.12e-12 to ~6.84e-12. But the other two might be worth addressing for the final FIPS-204, since they aren’t functional changes.

Regards,
— Mike

[Mike Hamburg]

Always read one more time before you post. The line “using Observation 3b reduces” should instead read “using Alternative 3a reduces”. Sorry for the spam. — Mike

> --
> You received this message because you are subscribed to the Google Groups "pqc-forum" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
> To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/C0F25477-7145-4950-A5C5-3C53A49DD30E%40shiftleft.org.

[Sophie Schmieg]

I can confirm observation 2, we noticed the same thing when putting together test vectors.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/BA4C7905-6D4B-4032-8EFD-35E9E6CDD53C%40shiftleft.org.

--

Sophie Schmieg | Information Security Engineer | ISE Crypto | ssch...@google.com

[Mike Hamburg]

Ah OK.  Do your test vectors exercise |ct0| >= gamma2 for Dilithium-2?  They’re actually not as rare as my calculation below indicates because (whoops) that probability is per coefficient.

Thanks, — Mike

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAEEbLAafPaKYkaOt5hTYJ_J2ie%3DjVP_8HiWTU8dj22LXkkRLfw%40mail.gmail.com.

[Sophie Schmieg]

We calculated a rejection in about 1 in 2^33, but I think we've so far only have test vectors for Dilithium3.

[Guillaume Endignoux]

Hi Mike,

To expand to what Sophie wrote:

Observation 1: that's exactly right.

For our implementation (draft in https://boringssl-review.googlesource.com/c/boringssl/+/63685), I've chosen to define the MakeHint function as taking the 3 raw parameters (ct0, cs2, w), and internally doing one subtraction and one addition.

That's more elegant implementation-wise, so the spec could be re-written in those terms, although I won't comment on which formula is more or less elegant mathematically.

Observation 2: I got the same result, using the fact that c has \tau coefficients in {-1, 1} and that t0 has coefficients <= 2^{d-1}.

So |ct0| is bounded by 2^{d-1} \tau, which is smaller than gamma2 for Dilithium-3 and 5.

It could be good indeed to adjust the spec to remove this check for the parameter sets where it doesn't matter. Although having the algorithm change based on the parameters may lead to confusion and implementation mistakes (e.g. if the check is removed when it shouldn't be) - hence the need for good test vectors.

At least, the spec could comment that this check is unnecessary for the two larger parameter sets, and that implementations are allowed to remove it as an optimization.

We haven't implemented test vectors for Dilithium-2 so far, so my estimation for the rejection sampling rate of 2^-33 (per coefficient) is again based on the fact that each coefficient of ct0 is a sum of \tau values each (approximately) uniformly distributed in [-4095, 4096].

Approximating this sum by a normal distribution (central limit theorem) gave a probability of 2^-33 to exceed gamma2 (which looks quite a bit larger than 7.12e-12), but I haven't confirmed that in practice.

I don't have much to say about observation 3, but perhaps 3b isn't ideal as calculating UseHint(h, r + ct0) == w1 is more computation for the signer than just |ct0|.

Best,

Guillaume