Question about polynomial compression

[randombit]

The code in polyvec.c KYBER_POLYVECCOMPRESSEDBYTES choses different compression formats based on the value of KYBER_POLYVECCOMPRESSEDBYTES == (KYBER_K * N) for N in {256,288,320,352}. However the Kyber paper only seems to describe case 352 (which is what is set by default in params.h). If I try other values for KYBER_POLYVECCOMPRESSEDBYTES everything seems to work (in that test_kyber does not complain, obviously I understand that these variants are not compatible with the NIST submission).

My questions is, are these variants described anywhere? It seems useful to have smaller public keys and ciphertexts so I am curious why you chose the 352 byte encoding. Perhaps this adversely affects the error rate to the point the smaller keys are not worthwhile?

Another comment, for N=256 actually the tests all failed for me, so there may be some problem in the code for that case.

[cryptojedi]

Jack Lloyd <notifications@github.com> wrote:

The code in `polyvec.c` KYBER_POLYVECCOMPRESSEDBYTES choses different compression formats based on the value of `KYBER_POLYVECCOMPRESSEDBYTES == (KYBER_K * N)` for N in {256,288,320,352}. However the Kyber paper only seems to describe case 352 (which is what is set by default in `params.h`). If I try other values for `KYBER_POLYVECCOMPRESSEDBYTES` everything seems to work (in that `test_kyber` does not complain, obviously I understand that these variants are not compatible with the NIST submission).

Indeed they are not. When designing Kyber we experimented with different values and then left the code in there; maybe we should just delete the parts that are not used anymore.

My questions is, are these variants described anywhere? It seems useful to have smaller public keys and ciphertexts so I am curious why you chose the 352 byte encoding. Perhaps this adversely affects the error rate to the point the smaller keys are not worthwhile? Another comment, for N=256 actually the tests all failed for me, so there may be some problem in the code for that case.

If they are *always* failing, this would indeed suggest that there is a problem with the compression code, but if there are only occasional errors, this might be due to the drastically increased failure rate. For the moment, I wouldn't put too much effort into this code because this might change with round-2 tweaks

[randombit]

Thank you for clarification.

I did not check if it always failed, but the self-tests reported many round trip errors. Since only 10000 self-tests are performed, seeing many dozens of errors suggests the error rate in that case is >> 2^-10 which would make it unsuitable even for passive secure KEM.

For the moment, I wouldn't put too much effort into this code because this might change with round-2 tweaks

Good to know, thank you. IIRC the tweaks are due in mid March, right? I will wait until then before spending more time on this.

[cryptojedi]

Jack Lloyd <notifications@github.com> wrote:

Good to know, thank you. IIRC the tweaks are due in mid March, right? I will wait until then before spending more time on this.

Yes, correct: March 15.