Paper 2020/408

Speed up over the Rainbow

Nir Drucker and Shay Gueron

Abstract

Rainbow is a signature scheme that is based on multivariate polynomials. It is one of the Round-2 candidates of the NIST’s Post-Quantum Cryptography Standardization project. Its computations rely heavily on GF(2^8) arithmetic and the Rainbow submission optimizes the code by using AVX2 shuffle and permute instructions. In this paper, we show a new optimization that leverages: a) AVX512 architecture; b) the latest processor capabilities Galois Field New Instructions(GF-NI), available on Intel "Ice Lake" processor. We achieved a speedup of 2.43x/3.13x/0.64x for key generation/signing/verifying, respectively. We also propose a variation of Rainbow, with equivalent security, using a different representation of GF(2^8). With this variant, we achieve a speedup of 2.44x/4.7x/2.1x for key generation/signing/verifying, respectively.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
RainbowPost Quantum Signature schemeConstant-time implementationGF-NI
Contact author(s)
shay gueron @ gmail com
drucker nir @ gmail com
History
2020-04-13: received
Short URL
https://ia.cr/2020/408
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/408,
      author = {Nir Drucker and Shay Gueron},
      title = {Speed up over the Rainbow},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/408},
      year = {2020},
      url = {https://eprint.iacr.org/2020/408}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.