KeyGen: `t` is not reduced before `Power2Round`

Hi, I'm opening this issue because I found a small error in your KeyGen() function. Indeed, when calculating t (L.5 KeyGen FIPS204), you do:

// 5: t ← NTT−1(cap_a_hat ◦ NTT(s_1)) + s_2    ▷ Compute t = As1 + s2
let t: [R; K] = {
    let s_1_hat: [T; L] = ntt(&s_1);
    let as1_hat: [T; K] = mat_vec_mul(&cap_a_hat, &s_1_hat);
    vec_add(&inv_ntt(&as1_hat), &s_2)
};

The output of &inv_ntt(&as1_hat) is reduced mod $q$ (i.e., coefficients are in $\{0, 1, ..., q-2, q-1\}$), while $s_2$ has coefficients in $[-\eta ; \eta]$. The result of vec_add(&inv_ntt(&as1_hat), &s_2) will therefore have coefficients in $\{-\eta, -\eta+1, ..., q-1+\eta\}$.

However, the Power2Round function expects a vector with coefficients in $\mathbb{Z}_q$ as input, so you will sometimes have coefficients out of bounds, and then, after Power2Round, some incorrect $t_0$, $t_1$'s coefficients.

Moreover, your assert_debug! on line 19 of low_high.rs should be:

debug_assert!(
    r.iter().flat_map(|row| row.0).all(|element| 0 <= element && element < Q),
    "power2round input"
);

and not:

debug_assert!(
    r.iter().flat_map(|row| row.0).all(|element| element < (i32::MAX - (1 << D))),
    "power2round input"
);

Otherwise, it's normal that you don't notice it :smile: I have implemented the fix in a fork, see: https://github.com/skilo-sh/fips204-temp-fork

integritychain / fips204

KeyGen: `t` is not reduced before `Power2Round` #2