Efficient Implementations of Rainbow and UOV using AVX2

A signature scheme based on multivariate quadratic equations, Rainbow, was selected as one of digital signature finalists for NIST Post-Quantum Cryptography Standardization Round 3. In this paper, we provide efficient implementations of Rainbow and UOV using the AVX2 instruction set. These efficien...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Kyung-Ah Shim, Sangyub Lee, Namhun Koo
Formato:	article
Lenguaje:	EN
Publicado:	Ruhr-Universität Bochum 2021
Materias:	Block Matrix Inversion Digital Signature Gaussian Elimination Multivariate-Quadratic Problem Post-Quantum Cryptography Precomputation Computer engineering. Computer hardware TK7885-7895 Information technology T58.5-58.64
Acceso en línea:	https://doaj.org/article/d8d48e28d4274e78b1f6578cda8244ba
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:d8d48e28d4274e78b1f6578cda8244ba
record_format	dspace
spelling	oai:doaj.org-article:d8d48e28d4274e78b1f6578cda8244ba2021-11-19T14:36:12ZEfficient Implementations of Rainbow and UOV using AVX210.46586/tches.v2022.i1.245-2692569-2925https://doaj.org/article/d8d48e28d4274e78b1f6578cda8244ba2021-11-01T00:00:00Zhttps://tches.iacr.org/index.php/TCHES/article/view/9296https://doaj.org/toc/2569-2925 A signature scheme based on multivariate quadratic equations, Rainbow, was selected as one of digital signature finalists for NIST Post-Quantum Cryptography Standardization Round 3. In this paper, we provide efficient implementations of Rainbow and UOV using the AVX2 instruction set. These efficient implementations include several optimizations for signing to accelerate solving linear systems and the Vinegar value substitution. We propose a new block matrix inversion (BMI) method using the Lower-Diagonal-Upper decomposition of blocks matrices based on the Schur complement that accelerates solving linear systems. Compared to UOV implemented with Gaussian elimination, our implementations with the BMI result in speedups of 12.36%, 24.3%, and 34% for signing at security categories I, III, and V, respectively. Compared to Rainbow implemented with Gaussian elimination, our implementations with the BMI result in speedups of 16.13% and 20.73% at the security categories III and V, respectively. We show that precomputation for the Vinegar value substitution and solving linear systems dramatically improve their signing. UOV with precomputation is 16.9 times, 35.5 times, and 62.8 times faster than UOV without precomputation at the three security categories, respectively. Rainbow with precomputation is 2.1 times, 2.2 times, and 2.8 times faster than Rainbow without precomputation at the three security categories, respectively. We then investigate resilience against leakage or reuse of the precomputed values in UOV and Rainbow to use the precomputation securely: leakage or reuse of the precomputed values leads to their full secret key recoveries in polynomial-time. Kyung-Ah ShimSangyub LeeNamhun KooRuhr-Universität BochumarticleBlock Matrix InversionDigital SignatureGaussian EliminationMultivariate-Quadratic ProblemPost-Quantum CryptographyPrecomputationComputer 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	Block Matrix Inversion Digital Signature Gaussian Elimination Multivariate-Quadratic Problem Post-Quantum Cryptography Precomputation Computer engineering. Computer hardware TK7885-7895 Information technology T58.5-58.64
spellingShingle	Block Matrix Inversion Digital Signature Gaussian Elimination Multivariate-Quadratic Problem Post-Quantum Cryptography Precomputation Computer engineering. Computer hardware TK7885-7895 Information technology T58.5-58.64 Kyung-Ah Shim Sangyub Lee Namhun Koo Efficient Implementations of Rainbow and UOV using AVX2
description	A signature scheme based on multivariate quadratic equations, Rainbow, was selected as one of digital signature finalists for NIST Post-Quantum Cryptography Standardization Round 3. In this paper, we provide efficient implementations of Rainbow and UOV using the AVX2 instruction set. These efficient implementations include several optimizations for signing to accelerate solving linear systems and the Vinegar value substitution. We propose a new block matrix inversion (BMI) method using the Lower-Diagonal-Upper decomposition of blocks matrices based on the Schur complement that accelerates solving linear systems. Compared to UOV implemented with Gaussian elimination, our implementations with the BMI result in speedups of 12.36%, 24.3%, and 34% for signing at security categories I, III, and V, respectively. Compared to Rainbow implemented with Gaussian elimination, our implementations with the BMI result in speedups of 16.13% and 20.73% at the security categories III and V, respectively. We show that precomputation for the Vinegar value substitution and solving linear systems dramatically improve their signing. UOV with precomputation is 16.9 times, 35.5 times, and 62.8 times faster than UOV without precomputation at the three security categories, respectively. Rainbow with precomputation is 2.1 times, 2.2 times, and 2.8 times faster than Rainbow without precomputation at the three security categories, respectively. We then investigate resilience against leakage or reuse of the precomputed values in UOV and Rainbow to use the precomputation securely: leakage or reuse of the precomputed values leads to their full secret key recoveries in polynomial-time.
format	article
author	Kyung-Ah Shim Sangyub Lee Namhun Koo
author_facet	Kyung-Ah Shim Sangyub Lee Namhun Koo
author_sort	Kyung-Ah Shim
title	Efficient Implementations of Rainbow and UOV using AVX2
title_short	Efficient Implementations of Rainbow and UOV using AVX2
title_full	Efficient Implementations of Rainbow and UOV using AVX2
title_fullStr	Efficient Implementations of Rainbow and UOV using AVX2
title_full_unstemmed	Efficient Implementations of Rainbow and UOV using AVX2
title_sort	efficient implementations of rainbow and uov using avx2
publisher	Ruhr-Universität Bochum
publishDate	2021
url	https://doaj.org/article/d8d48e28d4274e78b1f6578cda8244ba
work_keys_str_mv	AT kyungahshim efficientimplementationsofrainbowanduovusingavx2 AT sangyublee efficientimplementationsofrainbowanduovusingavx2 AT namhunkoo efficientimplementationsofrainbowanduovusingavx2
_version_	1718420099194421248

Efficient Implementations of Rainbow and UOV using AVX2

Ejemplares similares