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 efficient...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2021-11-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/TCHES/article/view/9296 |
| _version_ | 1811189700330782720 |
|---|---|
| author | Kyung-Ah Shim Sangyub Lee Namhun Koo |
| author_facet | Kyung-Ah Shim Sangyub Lee Namhun Koo |
| author_sort | Kyung-Ah Shim |
| collection | DOAJ |
| 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. |
| first_indexed | 2024-04-11T14:40:03Z |
| format | Article |
| id | doaj.art-d8d48e28d4274e78b1f6578cda8244ba |
| institution | Directory Open Access Journal |
| issn | 2569-2925 |
| language | English |
| last_indexed | 2024-04-11T14:40:03Z |
| publishDate | 2021-11-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj.art-d8d48e28d4274e78b1f6578cda8244ba2022-12-22T04:18:05ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252021-11-012022110.46586/tches.v2022.i1.245-269Efficient Implementations of Rainbow and UOV using AVX2Kyung-Ah Shim0Sangyub Lee1Namhun Koo2National Institute for Mathematical Sciences, Daejeon, Republic of KoreaNational Institute for Mathematical Sciences, Daejeon, Republic of Korea,Ewha Womans University, Seoul, Republic of KoreaA 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.https://tches.iacr.org/index.php/TCHES/article/view/9296Block Matrix InversionDigital SignatureGaussian EliminationMultivariate-Quadratic ProblemPost-Quantum CryptographyPrecomputation |
| spellingShingle | Kyung-Ah Shim Sangyub Lee Namhun Koo Efficient Implementations of Rainbow and UOV using AVX2 Transactions on Cryptographic Hardware and Embedded Systems Block Matrix Inversion Digital Signature Gaussian Elimination Multivariate-Quadratic Problem Post-Quantum Cryptography Precomputation |
| title | 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_short | Efficient Implementations of Rainbow and UOV using AVX2 |
| title_sort | efficient implementations of rainbow and uov using avx2 |
| topic | Block Matrix Inversion Digital Signature Gaussian Elimination Multivariate-Quadratic Problem Post-Quantum Cryptography Precomputation |
| url | https://tches.iacr.org/index.php/TCHES/article/view/9296 |
| work_keys_str_mv | AT kyungahshim efficientimplementationsofrainbowanduovusingavx2 AT sangyublee efficientimplementationsofrainbowanduovusingavx2 AT namhunkoo efficientimplementationsofrainbowanduovusingavx2 |