Geodesic
Modular arithmetic optimization in Kyber KEM
Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 162-166.

Voir la notice de l'article provenant de la source Math-Net.Ru

Kyber is a post-quantum key encapsulation mechanism that has been selected as a finalist in the third round of the NIST Post-Quantum Cryptography Competition. Today, Kyber is the only post-quantum key encapsulation mechanism recommended for standardization by NIST. The paper presents a new approach to optimize arithmetic operations in Kyber KEM. It reduces the number of modular reductions by increasing the bit size of numbers. The proposed optimization is appropriate for the general purpose systems with 32 or 64-bit CPUs. According to the benchmarking, our optimization speeds up the decapsulation algorithm by up to 1.83 times, the encapsulation algorithm — by up to 1.58 times, and the key generation — by up to 1.41 times.
Keywords: Kyber, modular arithmetic, post-quantum cryptography, lattice-based cryptography. 
@article{PDMA_2024_17_a41,
     author = {A. S. Zelenetsky and P. G. Klyucharev},
     title = {Modular arithmetic optimization in {Kyber} {KEM}},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {162--166},
     publisher = {mathdoc},
     number = {17},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2024_17_a41/}
}
TY  - JOUR
AU  - A. S. Zelenetsky
AU  - P. G. Klyucharev
TI  - Modular arithmetic optimization in Kyber KEM
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2024
SP  - 162
EP  - 166
IS  - 17
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2024_17_a41/
LA  - ru
ID  - PDMA_2024_17_a41
ER  - 
%0 Journal Article
%A A. S. Zelenetsky
%A P. G. Klyucharev
%T Modular arithmetic optimization in Kyber KEM
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2024
%P 162-166
%N 17
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2024_17_a41/
%G ru
%F PDMA_2024_17_a41
A. S. Zelenetsky; P. G. Klyucharev. Modular arithmetic optimization in Kyber KEM. Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 162-166. http://geodesic.mathdoc.fr/item/PDMA_2024_17_a41/

[1] Bos J., Ducas L., Kiltz E., et al., CRYSTALS — Kyber: a CCA-secure Module-Lattice-Based KEM, , 2017 https://eprint.iacr.org/2017/634.pdf

[2] Langlois A. and Stehle D., “Worst-case to average-case reductions for module lattices”, Des. Codes Cryptogr., 2015, no. 3, 565–599 | DOI | MR | Zbl

[3] Liang Z. and Zhao Y., Number Theoretic Transform and its Applications in Lattice-based Cryptosystems: A Survey, arXiv: 2211.13546 | DOI | MR

[4] Chung C.-M. M., Hwangt V., Kannwischer M. J., et al., “NTT multiplication for NTT-unfriendly rings: New speed records for Saber and NTRU on Cortex-M4 and AVX2”, IACR Trans. Cryptogr. Hardware Embedded Systems, 2021, no. 2, 159–188 | DOI

[5] Montgomery P. L., “Modular multiplication without trial division”, Math. Comput., 44 (1985), 519–521 | DOI | MR | Zbl

[6] Barrett P., “Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor”, LNCS, 263, 1987, 311–323 | MR