Math of Hint usage in ML-DSA

[iambatmanandjoker]

Sorry for the long message , newbee here ? Would really appreciate if someone could help with some basics here. Thanks in advance

For Dilithium, I understand that

$$\text{HighBits}(\mathbf{Ay}) = \text{HighBits}(\mathbf{Ay} - c\mathbf{s_2}) = \text{HighBits}(A_z - c\mathbf{t})$$

The first term of the equation is performed on the signer side while the final term is done on verifier side.

But verifier does not have access to $\mathbf{t}$ but only $\mathbf{t_1}$ calculated during key generation. So at max calculate $y = \mathbf{Az} − c\mathbf{t_1} \cdot 2^d$. To get exact $\text{Highbits}$, we also need to subtract $c\mathbf{t_0}$ from $y$.
Now, $c\mathbf{t_0}$ is limited to $\gamma2$ during signing step. So, we need to just calculate the $\text{Highbits}$ of $y$ that shall be impacted by subtracting $c\mathbf{t_0}$ from it and this is the hint (i.e. bit position at which carry occurs are 1) that signer provides encoded in the signature.

My questions are related to how the hints are used, specifically to the math of the Algorithm 34 below.

1. Why is the return value $\pmod m$ in the algorithm below? It also mentions $r_1$ should be max $(q-1)/2 \cdot \gamma_2$ but the same is not checked for $\text{HighBits}(\mathbf{Ay})$ in signing step.
2. How does $\text{LowBits}(r_0)$ play a role here ? Any example that can explain this?
3. Why is the $\text{MakeHint}$ calculated like this https://github.com/open-quantum-safe/liboqs/blob/main/src/sig/ml_dsa/pqcrystals-dilithium-standard_ml-dsa-65-ipd_ref/rounding.c#L68 ? I understand calculating $\text{HighBits}(r)$ and $\text{HighBits}(r + z)$ and then marking hintbits but the above code is unclear to me.
4. FIPS 204 states calculating Hint on (-ct0,Ay-cs2+ct0) but calculation is done on Lowbits of (Ay-cs2) rather then complete value?

---

Algorithm 34 UseHint(h,r)
Returns the high bits of r adjusted according to hint h 
Input:boolean h, r ∈ Zq 
Output:r Z with 0 ≤ r q −1 
1 ∈ 1 ≤ 2 γ2
1: m ← (q−1)/(2γ2)
2: (r1,r0) ← Decompose(r)
3: if h = 1 and r0 > 0 return (r1 +1) mod m 
4: if h = 1 and r0 ≤ 0 return (r1 −1) mod m 
5: return r1

[SWilson4]

Hi @iambatmanandjoker, this is not really the proper forum for mathematical questions. OQS isn't involved with algorithm design: we collect implementations from upstream sources and package them up into (hopefully) usable libraries and projects. If you have questions related to usage of one of our projects we'll do our best to answer them.

[iambatmanandjoker]

@SWilson4 the questions are related to ML-DSA , the implementation of which is done by OQS team, i assume hence the questions.

[baentsch]

@iambatmanandjoker As @SWilson4 already pointed out, the OQS team is not implementing ML-DSA, but presently relies on the implementation by the PQCrystals team (https://github.com/open-quantum-safe/liboqs/blob/main/docs%2Falgorithms%2Fsig%2Fdilithium.md) which is not part of the OQS team. Hence please ask your question there