Implementing minimized multivariate PKC on low-resource embedded systems

Bo Yin Yang*, Chen Mou Cheng, Bor Rong Chen, Jiun Ming Chen

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

34 Scopus citations


Multivariate (or MQ) public-key cryptosystems (PKC) are alternatives to traditional PKCs based on large algebraic structures (e.g., RSA and ECC); they usually execute much faster than traditional PKCs on the same hardware. However, one major challenge in implementing multivariates in embedded systems is that the key size can be prohibitively large for applications with stringent resource constraints such as low-cost smart cards, sensor networks (e.g., Berkeley motes), and radio-frequency identification (RFID). In this paper, we investigate strategies for shortening the key of a multivariate PKC. We apply these strategies to the Tame Transformation Signatures (TTS) as an example and quantify the improvement in key size and running speed, both theoretically and via implementation. We also investigate ways to save die space and energy consumption in hardware, reporting on our ASIC implementation of TTS on a TSMC 0.25μm process. Even without any key shortening, the current consumption of TTS is only 21 μA for computing a signature, using 22,000 gate equivalents and 16,000 100-kHz cycles (160 ms). With circulant-matrix key shortening, the numbers go down to 17,000 gates and 4,400 cycles (44 ms). We therefore conclude: besides representing a future-proofing investment against the emerging quantum computers, multivariates can be immediately useful in niches.

Original languageEnglish
Title of host publicationSecurity in Pervasive Computing - Third International Conference, SPC 2006, Proceedings
PublisherSpringer Verlag
Number of pages16
ISBN (Print)3540333762, 9783540333760
StatePublished - 2006
Externally publishedYes
Event3rd International Conference on Security in Pervasive Computing, SPC 2006 - York, United Kingdom
Duration: 18 04 200621 04 2006

Publication series

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


Conference3rd International Conference on Security in Pervasive Computing, SPC 2006
Country/TerritoryUnited Kingdom


  • Digital signature schemes
  • Efficient implementation
  • Embedded system
  • Motes
  • Multivariate public-key cryptosystem
  • Sensor networks


Dive into the research topics of 'Implementing minimized multivariate PKC on low-resource embedded systems'. Together they form a unique fingerprint.

Cite this