SSE Implementation of Multivariate PKCs on Modern x86 CPUs

Anna Inn-Tung Chen National Taiwan University, Taipei, Taiwan Ming-Shing Chen Academia Sinica, Taipei, Taiwan Tien-Ren Chen Academia Sinica, Taipei, Taiwan Chen-Mou Cheng National Taiwan University, Taipei, Taiwan Jintai Ding University of Cincinnati, Cincinnati, Ohio, USA Eric Li-Hsiang Kuo Academia Sinica, Taipei, Taiwan Frost Yu-Shuang Lee National Taiwan University, Taipei, Taiwan Bo-Yin Yang Academia Sinica, Taipei, Taiwan

TBD mathscidoc:2207.43044

CHES 2009, 33–48, 2009.9
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 4×. 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 F_{31} can be up to 2× faster than prior implementations of similarly-sized systems over F_{16}. 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 F_{31}, F_{16} and F_{256}. 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.
No keywords uploaded!
[ Download ] [ 2022-07-14 11:06:02 uploaded by dingjt ] [ 236 downloads ] [ 0 comments ]
@inproceedings{anna2009sse,
  title={SSE Implementation of Multivariate PKCs on Modern x86 CPUs},
  author={Anna Inn-Tung Chen, Ming-Shing Chen, Tien-Ren Chen, Chen-Mou Cheng, Jintai Ding, Eric Li-Hsiang Kuo, Frost Yu-Shuang Lee, and Bo-Yin Yang},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220714110602215882621},
  booktitle={CHES 2009},
  pages={33–48},
  year={2009},
}
Anna Inn-Tung Chen, Ming-Shing Chen, Tien-Ren Chen, Chen-Mou Cheng, Jintai Ding, Eric Li-Hsiang Kuo, Frost Yu-Shuang Lee, and Bo-Yin Yang. SSE Implementation of Multivariate PKCs on Modern x86 CPUs. 2009. In CHES 2009. pp.33–48. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220714110602215882621.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved