SSE Implementation of Multivariate PKCs on Modern x86 CPUs.
Journal
Lecture Notes in Computer Science
Journal Volume
5747
Pages
33-48
Date Issued
2009
Author(s)
Abstract
Multivariate Public Key Cryptosystems (MPKCs) are often touted as future-proofing against Quantum Computers. It also has been known for efficiency compared to "traditional" alternatives. However, this advantage seems to erode with the increase of arithmetic resources in modern CPUs and improved algorithms, especially with respect to Elliptic Curve Cryptography (ECC). In this paper, we show that hardware advances do not just favor ECC. Modern commodity CPUs also have many small integer arithmetic/logic resources, embodied by SSE2 or other vector instruction sets, that are useful for MPKCs. In particular, Intel's SSSE3 instructions can speed up both public and private maps over prior software implementations of Rainbow-type systems up to 4x. Furthermore, MPKCs over fields of relatively small odd prime characteristics can exploit SSE2 instructions, supported by most modern 64-bit Intel and AMD CPUs. For example, Rainbow over double-struck double-struck F31 can be up to 2x faster than prior implementations of similarly-sized systems over double-struck double-struck F16. Here a key advance is in using Wiedemann (as opposed to Gauss) solvers to invert the small linear systems in the central maps. We explain the techniques and design choices in implementing our chosen MPKC instances over fields such as double-struck double-struck F 31, double-struck F16 and double-struck F256. We believe that our results can easily carry over to modern FPGAs, which often contain a large number of small multipliers, usable by odd-field MPKCs. © 2009 Springer.
SDGs
Type
journal article