1
$\begingroup$

My understanding of Dilithium is below

To sign, signer generates random vector y with coefficients under a given threshold. He calculates:

         w=HighBits(A∙y)

         c=HASH(m || w)

         z=y+c∙s

In this equation, s is the MLWE private key, A is the MLWE array, and m is the message to sign. The signer then verifies that all the coefficients of z are below a threshold, and that Lowbits of (A∙y-c∙e) are also below a (different) threshold (where e is the error vector used in generating the MLWE public key). If these conditions don’t hold, a new y is generated and the signer goes through the process again. Once a suitable z is generated, z and c are returned as the signature.

To verify, the verifier calculates

         w’=HighBits(A∙z-c∙b)

In this equation, b is the MLWE public key. If c=HASH(m || w’), and the coefficients of z are under the threshold, then the signature is valid.

But as per FIPS 204 specification, a hint is calculated and encoded in signature.

          h ← MakeHint(−⟨⟨ct0⟩⟩,w−⟨⟨cs2⟩⟩+⟨⟨ct0⟩⟩)

I am unable to understand how verifier uses this info before hashing with mu ? Is there a simple way to explain this ?

$\endgroup$

1 Answer 1

1
$\begingroup$

The signer never reveals the lower bits of $t$, but gives the verifier the upper bits in order to perform a partial computation of the signature. The signature is $z = y + c s_1$, which satisfies $Az - ct = Ay - c s_2$, $\tilde{c}$, and the hint, but the verifier doesn't have access to all of t, so it can only compute $Az - c t_1 2^d$, which doesn't satisfy the signature.

Because $c t_0$ is of bounded max value (we check, in the signing step), we know that subtracting it from $Az - c t_1 2^d$ can only cause rounding to change by moving away from the value it would have - e.g. 2.6 rounds to 3, but maybe subtracting $c t_1 2^d$ from it bumps this down to 2.4, so it rounds instead to 2. There's no way for 2.6 to grow to 3.6, so the hints tell you exactly how to modify this value after running $\textrm{Decompose}(Az - c t_1 2^d)$. The verifier doesn't just run HighBits, but also runs this "round the other way" scheme using the hint to guide it.

$\endgroup$
3
  • $\begingroup$ Thanks for the reply. My understanding is below , please feel to correct Verifier needs highbits of Az-ct but has access only to t1 and can calculate Az−ct12^d(say y) but we need to subtract ct0 from y and then get the exact high bits. Now,Az−ct12^d = Az-c(t-t0) = Az -ct + ct0 = Ay-cs2+ct0 So, Az−ct12^d - ct0 = (Ay-cs2+ct0) - ct0 and the above step is the hint calculated in Algo2, line 26 Please feel free to correct and add more info $\endgroup$
    – Gappu
    Commented Apr 29 at 10:11
  • $\begingroup$ Asked an detailed maths questions here :crypto.stackexchange.com/questions/111637/… feel free to check and reply $\endgroup$
    – Gappu
    Commented Apr 30 at 8:55
  • $\begingroup$ This looks correct to me! $\endgroup$ Commented May 7 at 23:04

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.