Neon NTT: Faster Dilithium, Kyber, and Saber on Cortex-A72 and Apple M1

We present new speed records on the Armv8-A architecture for the latticebased schemes Dilithium, Kyber, and Saber. The core novelty in this paper is the combination of Montgomery multiplication and Barrett reduction resulting in “Barrett multiplication” which allows particularly efficient modular o...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Hanno Becker, Vincent Hwang, Matthias J. Kannwischer, Bo-Yin Yang, Shang-Yi Yang
Formato:	article
Lenguaje:	EN
Publicado:	Ruhr-Universität Bochum 2021
Materias:	NIST PQC Armv8-A Neon Dilithium Kyber Saber Computer engineering. Computer hardware TK7885-7895 Information technology T58.5-58.64
Acceso en línea:	https://doaj.org/article/b2b6a32b59d74cc29aa0ddce37e21ace
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:b2b6a32b59d74cc29aa0ddce37e21ace
record_format	dspace
spelling	oai:doaj.org-article:b2b6a32b59d74cc29aa0ddce37e21ace2021-11-19T14:36:12ZNeon NTT: Faster Dilithium, Kyber, and Saber on Cortex-A72 and Apple M110.46586/tches.v2022.i1.221-2442569-2925https://doaj.org/article/b2b6a32b59d74cc29aa0ddce37e21ace2021-11-01T00:00:00Zhttps://tches.iacr.org/index.php/TCHES/article/view/9295https://doaj.org/toc/2569-2925 We present new speed records on the Armv8-A architecture for the latticebased schemes Dilithium, Kyber, and Saber. The core novelty in this paper is the combination of Montgomery multiplication and Barrett reduction resulting in “Barrett multiplication” which allows particularly efficient modular one-known-factor multiplication using the Armv8-A Neon vector instructions. These novel techniques combined with fast two-unknown-factor Montgomery multiplication, Barrett reduction sequences, and interleaved multi-stage butterflies result in significantly faster code. We also introduce “asymmetric multiplication” which is an improved technique for caching the results of the incomplete NTT, used e.g. for matrix-to-vector polynomial multiplication. Our implementations target the Arm Cortex-A72 CPU, on which our speed is 1.7× that of the state-of-the-art matrix-to-vector polynomial multiplication in kyber768 [Nguyen–Gaj 2021]. For Saber, NTTs are far superior to Toom–Cook multiplication on the Armv8-A architecture, outrunning the matrix-to-vector polynomial multiplication by 2.0×. On the Apple M1, our matrix-vector products run 2.1× and 1.9× faster for Kyber and Saber respectively. Hanno BeckerVincent HwangMatthias J. KannwischerBo-Yin YangShang-Yi YangRuhr-Universität BochumarticleNIST PQCArmv8-ANeonDilithiumKyberSaberComputer engineering. Computer hardwareTK7885-7895Information technologyT58.5-58.64ENTransactions on Cryptographic Hardware and Embedded Systems, Vol 2022, Iss 1 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	NIST PQC Armv8-A Neon Dilithium Kyber Saber Computer engineering. Computer hardware TK7885-7895 Information technology T58.5-58.64
spellingShingle	NIST PQC Armv8-A Neon Dilithium Kyber Saber Computer engineering. Computer hardware TK7885-7895 Information technology T58.5-58.64 Hanno Becker Vincent Hwang Matthias J. Kannwischer Bo-Yin Yang Shang-Yi Yang Neon NTT: Faster Dilithium, Kyber, and Saber on Cortex-A72 and Apple M1
description	We present new speed records on the Armv8-A architecture for the latticebased schemes Dilithium, Kyber, and Saber. The core novelty in this paper is the combination of Montgomery multiplication and Barrett reduction resulting in “Barrett multiplication” which allows particularly efficient modular one-known-factor multiplication using the Armv8-A Neon vector instructions. These novel techniques combined with fast two-unknown-factor Montgomery multiplication, Barrett reduction sequences, and interleaved multi-stage butterflies result in significantly faster code. We also introduce “asymmetric multiplication” which is an improved technique for caching the results of the incomplete NTT, used e.g. for matrix-to-vector polynomial multiplication. Our implementations target the Arm Cortex-A72 CPU, on which our speed is 1.7× that of the state-of-the-art matrix-to-vector polynomial multiplication in kyber768 [Nguyen–Gaj 2021]. For Saber, NTTs are far superior to Toom–Cook multiplication on the Armv8-A architecture, outrunning the matrix-to-vector polynomial multiplication by 2.0×. On the Apple M1, our matrix-vector products run 2.1× and 1.9× faster for Kyber and Saber respectively.
format	article
author	Hanno Becker Vincent Hwang Matthias J. Kannwischer Bo-Yin Yang Shang-Yi Yang
author_facet	Hanno Becker Vincent Hwang Matthias J. Kannwischer Bo-Yin Yang Shang-Yi Yang
author_sort	Hanno Becker
title	Neon NTT: Faster Dilithium, Kyber, and Saber on Cortex-A72 and Apple M1
title_short	Neon NTT: Faster Dilithium, Kyber, and Saber on Cortex-A72 and Apple M1
title_full	Neon NTT: Faster Dilithium, Kyber, and Saber on Cortex-A72 and Apple M1
title_fullStr	Neon NTT: Faster Dilithium, Kyber, and Saber on Cortex-A72 and Apple M1
title_full_unstemmed	Neon NTT: Faster Dilithium, Kyber, and Saber on Cortex-A72 and Apple M1
title_sort	neon ntt: faster dilithium, kyber, and saber on cortex-a72 and apple m1
publisher	Ruhr-Universität Bochum
publishDate	2021
url	https://doaj.org/article/b2b6a32b59d74cc29aa0ddce37e21ace
work_keys_str_mv	AT hannobecker neonnttfasterdilithiumkyberandsaberoncortexa72andapplem1 AT vincenthwang neonnttfasterdilithiumkyberandsaberoncortexa72andapplem1 AT matthiasjkannwischer neonnttfasterdilithiumkyberandsaberoncortexa72andapplem1 AT boyinyang neonnttfasterdilithiumkyberandsaberoncortexa72andapplem1 AT shangyiyang neonnttfasterdilithiumkyberandsaberoncortexa72andapplem1
_version_	1718420090914865152

Neon NTT: Faster Dilithium, Kyber, and Saber on Cortex-A72 and Apple M1

Ejemplares similares