Cryptology ePrint Archive: Report 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.

Category / Keywords: implementation / Rainbow, Post Quantum Signature scheme, Constant-time implementation, GF-NI

Date: received 10 Apr 2020

Contact author: shay gueron at gmail com,drucker nir@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200413:103105 (All versions of this report)

Short URL: ia.cr/2020/408


[ Cryptology ePrint archive ]