A New Variant of Unbalanced Oil and Vinegar Using Quotient Ring: QR-UOV

Hiroki Furue; Yasuhiko Ikematsu; Yutaro Kiyomura; Tsuyoshi Takagi

Paper 2020/1243

A New Variant of Unbalanced Oil and Vinegar Using Quotient Ring: QR-UOV

Hiroki Furue, Yasuhiko Ikematsu, Yutaro Kiyomura, and Tsuyoshi Takagi

Abstract

The unbalanced oil and vinegar signature scheme (UOV) is a multivariate signature scheme that has essentially not been broken for over 20 years. However, it requires the use of a large public key; thus, various methods have been proposed to reduce its size. In this paper, we propose a new variant of UOV with a public key represented by block matrices whose components correspond to an element of a quotient ring. We discuss how it affects the security of our proposed scheme whether or not the quotient ring is a field. Furthermore, we discuss their security against currently known and newly possible attacks and propose parameters for our scheme. We demonstrate that our proposed scheme can achieve a small public key size without significantly increasing the signature size compared with other UOV variants. For example, the public key size of our proposed scheme is 85.8 KB for NIST's Post-Quantum Cryptography Project (security level 3), whereas that of compressed Rainbow is 252.3 KB, where Rainbow is a variant of UOV and is one of the third-round finalists of the NIST PQC project.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published by the IACR in ASIACRYPT 2021
Keywords: post-quantum cryptography multivariate public key cryptography unbalanced oil and vinegar quotient ring.
Contact author(s): furue-hiroki261 @ g ecc u-tokyo ac jp
History: 2021-10-05: last of 3 revisions; 2020-10-09: received; See all versions
Short URL: https://ia.cr/2020/1243
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1243,
      author = {Hiroki Furue and Yasuhiko Ikematsu and Yutaro Kiyomura and Tsuyoshi Takagi},
      title = {A New Variant of Unbalanced Oil and Vinegar Using Quotient Ring: QR-UOV},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1243},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1243}},
      url = {https://eprint.iacr.org/2020/1243}
}