Is montgomery calculation is necessary?

[lizhirui]

There is much montgomery field calculation in latest version reference code(master and round 3 branch, ref/ directory).

And, key generated is seems in montgomery field too.

But specification documents(version 3.0, October 1, 2020 and 3.01/3.02 version)(in NIST submission package for round3(zip), Supporting_Documentation/kyber.pdf) don't show anything about montgomery(I mean algorithm specification except security problem), for example, "KYBER.CPAPKE.KeyGen(): key generation".

So, is montgomery calculation is necessary? If I do hardware implmentation, must I implement montgomery to keep key generated and ciphertext is compatible to software reference implementation?

[cryptojedi]

Using Montgomery representation for coefficients is not necessary.
The public key is in NTT domain, but the coefficients of the public key are not in Montgomery domain.

[lizhirui]

Using Montgomery representation for coefficients is not necessary. The public key is in NTT domain, but the coefficients of the public key are not in Montgomery domain.

But, in ntt.c, every element of zetas array geenerated by init_ntt function are multiplied by one or many MONTs:

tmp[0] = MONT;

for(i = 1;i <128;i++)
tmp[i] = fqmul(tmp[i - 1], MONT*KYBER_ROOT_OF_UNITY % KYBER_Q);

And in indacpa_keypair function of indcpa.c, skpv and e are converted by function polyvec_ntt calling ntt function which used twiddle factor including MONT.

and pkpv in indacpa_keypair also is generated by "polyvec_basemul_acc_montgomery" and "poly_TOMONT" function.

And after polyvec_add and polyvec_reduce, pkpv and skpv are packed. I didn't see any code of converting montgomery representation to normal representation.

It seems that public key and secret key are all in Montgomery domain.

[cryptojedi]

After the NTT, coefficients are in normal (i.e., non-Montgomery) domain.
In basemul we multiply those and (in the function fqmul) apply a Montgomery
reduction to the result. This brings the coefficients to "inverse Montgomery"
domain, i.e., they lack a Montgomery factor. The to_mont function re-applies
this Montgomery factor to bring coefficients back to normal domain.

[lizhirui]

After the NTT, coefficients are in normal (i.e., non-Montgomery) domain. In basemul we multiply those and (in the function fqmul) apply a Montgomery reduction to the result. This brings the coefficients to "inverse Montgomery" domain, i.e., they lack a Montgomery factor. The to_mont function re-applies this Montgomery factor to bring coefficients back to normal domain.

Thanks for your detail explaination, I will do some try to remove montgomery calculation code from reference code.