# USeHint and MakeHint in Dilithium

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 ?

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.