A High-Speed Public-Key Signature Scheme for 8-b IoT-Constrained Devices
Kyung‐Ah Shim, Cheol‐Min Park, Namhun Koo, Hwajeong Seo · IEEE Internet of Things Journal · 2020
More than 98% of all microprocessors sold worldwide are used in embedded devices, and will continue to accelerate due to the emerging applications in Internet of Things (IoT). Cryptographic algorithms based on multivariate quadratic (MQ) equations are suitable for low-cost IoT-constrained devices since they require only modest computational resources. In this article, we describe the design and implementations of a new public-key signature scheme based on MQ equations highly optimized for practicability. The novel scheme is obtained as a result of the combination of solvable systems of quadratic equations and sparse polynomials. We provide a security analysis of our scheme against known algebraic attacks and derive a concrete parameter. Performance of our scheme on an 8-b AVR microprocessor is the fastest among known signature schemes: signing of our scheme is about 36.4× faster than that of ECDSA-256 (NIST P-256), the most widely deployed international standard signature scheme. The signing of our scheme is about 8.6× and 11.0× faster than those of Rainbow and BLISS-BI, respectively. The secret size of our scheme has reduced by a factor of 87% compared to Rainbow. Our scheme requires signatures of 80 B which is comparable to ECDSA-256 of 64 B. We also implement a protected version of our scheme on the 8-b microprocessor to prevent the current side-channel attacks presented in CHES 2018. Even our protected version is the fastest singing among the known signature schemes.