Paper 2016/1079

Revisiting the Cubic UOV Signature Scheme

Dung Hoang Duong, Takanori Yasuda, Albrecht Petzoldt, Yacheng Wang, and Tsuyoshi Takagi

Abstract

As recently been emphasized by NSA and NIST, there is an increasing need for cryptographic schemes being secure against quantum computer attacks. Especially in the area of digital signature schemes, multivariate cryptography is one of the main candidates for this. At Inscrypt 2015, Nie et al. proposed a new multivariate signature scheme called CUOV, whose public key consists both of quadratic and cubic polynomials. However, the scheme was broken by an attack of Hashimoto. In this paper we take a closer look on the CUOV scheme and its attack and propose two new multivariate signature schemes called CSSv and SVSv2, which are secure against Hashimoto's attack and all other known attacks on multivariate schemes. Especially our schemes are more efficient than CUOV and UOV and highly comparable to Rainbow.

Note: The previous version was published at ICISC 2016. In this version, we revisit the security of SVSv scheme and find that SVSv scheme is vulnerable to the HighRank attack. We then propose a way to fix it.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. ICISC 2016
Keywords
Post-Quantum CryptographyMultivariate CryptographySignature Schemes
Contact author(s)
duong @ imi kyushu-u ac jp
History
2017-02-14: revised
2016-11-21: received
See all versions
Short URL
https://ia.cr/2016/1079
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1079,
      author = {Dung Hoang Duong and Takanori Yasuda and Albrecht Petzoldt and Yacheng Wang and Tsuyoshi Takagi},
      title = {Revisiting the Cubic UOV Signature Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1079},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1079}},
      url = {https://eprint.iacr.org/2016/1079}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.