search

newhopecrypto / newhope

Software of the NIST Post-Quantum submission NewHope
https://newhopecrypto.org
43 stars 9 forks source link

Pre-computed omega_bit_ table seem wrong #3

Closed cothan closed 5 years ago

cothan commented 5 years ago

Hi all,

In the specification, omega value = 49, psis = sqrt(49) = 7 However, when I tried to replicate the pre-computed table, i see there you was using psis = g = 7 to generate omegas_bitrev_montgomery table. 

 * omegas_bitrev_montgomery = lift(vector(n/2, i, g^(brv[i])*mont))
 * psis_bitrev_montgomery = lift(vector(n, i, g^(brv[i])*mont))

In addition, by looking at omega content, one can spot that omegas_bitrev_montgomery and psis_bitrev_montgomery share NEWHOPE_N/2, which mean psis_bitrev_montgomery include the omegas_bitrev_montgomery table.

Is it suppose to generate like this

 * omegas_bitrev_montgomery = lift(vector(n/2, i, g^(2*brv[i])*mont))
 * psis_bitrev_montgomery = lift(vector(n, i, g^(brv[i])*mont))

No security issue here obviously, is this an optimal implementation purpose ? Please let me know.

Thanks.

cryptojedi commented 5 years ago

Thank you very much, you're absolutely right! I pushed a change that fixes this with both changes to the script and the naming of the constants.