5
$\begingroup$

Currently there are only 4 direct candidates left that provide KEM. Generally performance seems to be "OK" for those candidates. However, the key and encapsulated key sizes (i.e. the output size of the algorithm) may require some interesting tweaks in the protocols.

I could not directly find these sizes on the Internet, so are they known (for the different levels of security required by the NIST competition)?

The round 3 candidates are:

  • Classic McEliece
  • CRYSTALS-KYBER
  • NTRU
  • SABER

I'm only interested in the sizes of the dynamic values in minimum number of bits as well as any encoded sizes - if an encoding has been specified. Domain parameters - assuming that they are static - may be excluded from the calculation.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
7
$\begingroup$

Throughout this answer the following conventions are used:

  • CT = Ciphertext or transmitted output of the encapsulation algorithm
  • PK = Public key or transmitted output of the key generation algorithm
  • Cat 1 / 3 / 5 = NIST security categories with the following specification:

Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 128/192/256-bit key

The following table gives you the tools to calculate the desired sizes from the given parameter sets - wherever I could figure out the relevant formulas from the supporting documentation PDF.

Scheme PK size CT size Additional Notes
Classic McEliece $mt\lceil k/8\rceil$ $\lceil mt/8\rceil+\lceil\ell/8\rceil$ $k=n-mt,\ell=256$
Kyber $12kn/8+32$ $d_ukn/8+d_vn/8$
NTRU $\lceil(n-1)\log_2q/8\rceil$ $\lceil(n-1)\log_2q/8\rceil$
SABER ? ? Sizes pre-computed

Unfortunately the SABER documentation was rather unclear on how the sizes are computed (it appears they want one to infer them from the sizes of the packed objects). Fortunately the relevant sizes are already precomputed in a table in their paper.

For NTRU there were two models of computation given, for the sake of comparability I have chosen the weaker ("local") model of computation as the other one didn't have a single named parameter set with category 5 security.

The following table uses the above formulas to compute the sizes for the smallest specified parameter sets that satisfy a given security category as assigned in the supporting documentation of the submission.

Scheme Cat1 CT Cat1 PK Cat3 CT Cat3 PK Cat5 CT Cat5 PK
Classic McEliece 128B 261,120B 188B 524,160B 240B 1,044,992B
Kyber 768B 800B 1,088B 1,184B 1,568B 1,568B
NTRU 699B 699B 930B 930B 1,230B 1,230B
SABER 736B 672B 1,088B 992B 1,472B 1,312B
Improve this answer
$\endgroup$
4
  • $\begingroup$ It took some time for me to realize that those keys sizes are in bytes, as I'm so used to bits for them - although bytes make more sense for encoding of keys. It's actually not as bad as I expected, other than McEliece starting off at around 261KB. $\endgroup$
    – Maarten Bodewes ♦
    Dec 22, 2020 at 14:51
  • $\begingroup$ Why there are questions marks? $\endgroup$
    – kelalaka
    Dec 22, 2020 at 19:37
  • 1
    $\begingroup$ @kelalaka because I couldn't figure out the formulas and didn't want to invest the time given that they also tabled the relevant values. $\endgroup$
    – SEJPM
    Dec 22, 2020 at 19:41
  • $\begingroup$ For Saber, the pk size is l * 256 * log(p) / 8 + 32, since the vector b is composed by l polynomials of 256 coefficients, of p bits each, and 32 is the size of the matrix A seed. For the ciphertext, another vector b' of size l * 256 * log(p) / 8 is generated, together with the message-encoding polynomial c_m which has 256 coefficients of T bits each. Note that for all security levels, p^10 and T=4. The only value that changes if l, ranging from 2 to 4. $\endgroup$
    – Andrea
    Mar 26, 2021 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.