IEEE Access (Jan 2020)

An Efficient MQ-Signature Scheme Based on Sparse Polynomials

  • Kyung-Ah Shim,
  • Cheol-Min Park,
  • Namhun Koo

DOI
https://doi.org/10.1109/access.2020.2970608
Journal volume & issue
Vol. 8
pp. 26257 – 26265

Abstract

Read online

Multivariate quadratic (MQ) equations-based cryptography is one of the most promising alternatives for currently used public-key cryptographic algorithms in the post-quantum era. It is important to design practical public-key signature schemes on embedded processors and resource-constrained devices for emerging applications in Internet of Things. The MQ-signature schemes are suitable for low-cost constrained devices since they require only modest computational resources. In this paper, we propose an efficient MQ-signature scheme, SOV, using sparse polynomials with a shorter secret key and give its security analysis against known algebraic attacks. Compared to Rainbow, the secret key of SOV has reduced by a factor of 90% without increasing the public key size. In particular, SOV requires signatures of 52 bytes, while ECDSA-256 requires signatures of 64 bytes.

Keywords