SSE implementation of multivariate PKCs on modern x86 CPUs

Anna Inn Tung Chen; Ming Shing Chen; Tien Ren Chen; Chen Mou Cheng; Jintai Ding; Eric Li Hsiang Kuo; Frost Yu Shuang Lee; Bo Yin Yang

doi:10.1007/978-3-642-04138-9_3

SSE implementation of multivariate PKCs on modern x86 CPUs

Anna Inn Tung Chen, Ming Shing Chen, Tien Ren Chen, Chen Mou Cheng, Jintai Ding, Eric Li Hsiang Kuo, Frost Yu Shuang Lee, Bo Yin Yang

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

85 Citations (Scopus)

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 F₃₁ can be up to 2x faster than prior implementations of similarly-sized systems over double-struck double-struck F₁₆. 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 ₃₁, double-struck F₁₆ and double-struck F₂₅₆. 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.

Original language	English
Title of host publication	Cryptographic Hardware and Embedded Systems - CHES 2009 - 11th International Workshop, Proceedings
Pages	33-48
Number of pages	16
DOIs	https://doi.org/10.1007/978-3-642-04138-9_3
Publication status	Published - 2009
Externally published	Yes
Event	11th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2009 - Lausanne, Switzerland Duration: 6 Sept 2009 → 9 Sept 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5747 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2009
Country/Territory	Switzerland
City	Lausanne
Period	6/09/09 → 9/09/09

Keywords

ℓIC
Multivariate public key cryptosystem (MPKC)
Rainbow
SSE2
SSSE3
TTS
Vector instructions
Wiedemann

Access to Document

10.1007/978-3-642-04138-9_3

Cite this

Chen, A. I. T., Chen, M. S., Chen, T. R., Cheng, C. M., Ding, J., Kuo, E. L. H., Lee, F. Y. S., & Yang, B. Y. (2009). SSE implementation of multivariate PKCs on modern x86 CPUs. In Cryptographic Hardware and Embedded Systems - CHES 2009 - 11th International Workshop, Proceedings (pp. 33-48). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5747 LNCS). https://doi.org/10.1007/978-3-642-04138-9_3

Chen, Anna Inn Tung ; Chen, Ming Shing ; Chen, Tien Ren et al. / SSE implementation of multivariate PKCs on modern x86 CPUs. Cryptographic Hardware and Embedded Systems - CHES 2009 - 11th International Workshop, Proceedings. 2009. pp. 33-48 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f0dab2b2f1ed4a15a4f610e0bd550c42,

title = "SSE implementation of multivariate PKCs on modern x86 CPUs",

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.",

keywords = "ℓIC, Multivariate public key cryptosystem (MPKC), Rainbow, SSE2, SSSE3, TTS, Vector instructions, Wiedemann",

author = "Chen, {Anna Inn Tung} and Chen, {Ming Shing} and Chen, {Tien Ren} and Cheng, {Chen Mou} and Jintai Ding and Kuo, {Eric Li Hsiang} and Lee, {Frost Yu Shuang} and Yang, {Bo Yin}",

year = "2009",

doi = "10.1007/978-3-642-04138-9_3",

language = "English",

isbn = "364204137X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "33--48",

booktitle = "Cryptographic Hardware and Embedded Systems - CHES 2009 - 11th International Workshop, Proceedings",

note = "11th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2009 ; Conference date: 06-09-2009 Through 09-09-2009",

}

Chen, AIT, Chen, MS, Chen, TR, Cheng, CM, Ding, J, Kuo, ELH, Lee, FYS & Yang, BY 2009, SSE implementation of multivariate PKCs on modern x86 CPUs. in Cryptographic Hardware and Embedded Systems - CHES 2009 - 11th International Workshop, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5747 LNCS, pp. 33-48, 11th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2009, Lausanne, Switzerland, 6/09/09. https://doi.org/10.1007/978-3-642-04138-9_3

SSE implementation of multivariate PKCs on modern x86 CPUs. / Chen, Anna Inn Tung; Chen, Ming Shing; Chen, Tien Ren et al.
Cryptographic Hardware and Embedded Systems - CHES 2009 - 11th International Workshop, Proceedings. 2009. p. 33-48 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5747 LNCS).

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

TY - GEN

T1 - SSE implementation of multivariate PKCs on modern x86 CPUs

AU - Chen, Anna Inn Tung

AU - Chen, Ming Shing

AU - Chen, Tien Ren

AU - Cheng, Chen Mou

AU - Ding, Jintai

AU - Kuo, Eric Li Hsiang

AU - Lee, Frost Yu Shuang

AU - Yang, Bo Yin

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

KW - ℓIC

KW - Multivariate public key cryptosystem (MPKC)

KW - Rainbow

KW - SSE2

KW - SSSE3

KW - TTS

KW - Vector instructions

KW - Wiedemann

UR - http://www.scopus.com/inward/record.url?scp=70350604666&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-04138-9_3

DO - 10.1007/978-3-642-04138-9_3

M3 - Conference Proceeding

AN - SCOPUS:70350604666

SN - 364204137X

SN - 9783642041372

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 33

EP - 48

BT - Cryptographic Hardware and Embedded Systems - CHES 2009 - 11th International Workshop, Proceedings

T2 - 11th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2009

Y2 - 6 September 2009 through 9 September 2009

ER -

Chen AIT, Chen MS, Chen TR, Cheng CM, Ding J, Kuo ELH et al. SSE implementation of multivariate PKCs on modern x86 CPUs. In Cryptographic Hardware and Embedded Systems - CHES 2009 - 11th International Workshop, Proceedings. 2009. p. 33-48. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-04138-9_3

SSE implementation of multivariate PKCs on modern x86 CPUs

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this