Paper 2020/1243
A New Variant of Unbalanced Oil and Vinegar Using Quotient Ring: QR-UOV
Hiroki Furue and Yasuhiko Ikematsu and 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, so various methods have been proposed to reduce its size. In this paper, we propose a new variant of UOV with the public key represented by block matrices whose components are represented as an element of a quotient ring. We discuss how the irreducibility of the polynomial used to generate the quotient ring affects the security of our proposed scheme. Furthermore, we propose parameters for our proposed scheme and discuss their security against currently known and possible attacks. We show that our proposed scheme can reduce the 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 66.7 KB for NIST's Post-Quantum Cryptography Project (security level 3), while that of cyclic Rainbow is 252.3 KB, where Rainbow is a variant of UOV and one of the third round finalists of NIST PQC project.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- post-quantum cryptographymultivariate public key cryptographyunbalanced oil and vinegarquotient 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