Paper 2019/1490

Cryptanalysis of The Lifted Unbalanced Oil Vinegar Signature Scheme

Jintai Ding, Joshua Deaton, Kurt Schmidt, Vishakha, and Zheng Zhang

Abstract

In 2017, Ward Beullens \textit{et al.} submitted Lifted Unbalanced Oil and Vinegar (LUOV)\cite{beullens2017field}, a signature scheme based on the famous multivariate public key cryptosystem (MPKC) called Unbalanced Oil and Vinegar (UOV), to NIST for the competition for post-quantum public key scheme standardization. The defining feature of LUOV is that, though the public key P works in the extension field of degree r of F2, the coefficients of P come from F2. This is done to significantly reduce the size of P. The LUOV scheme is now in the second round of the NIST PQC standardization process. In this paper we introduce a new attack on LUOV. It exploits the "lifted" structure of LUOV to reduce direct attacks on it to those over a subfield. We show that this reduces the complexity below the targeted security for the NIST post-quantum standardization competition.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Contact author(s)
jintai ding @ gmail com
deatonju @ mail uc edu
schmidku @ mail uc edu
sharmav4 @ mail uc edu
zhang2zh @ mail uc edu
History
2020-07-20: revised
2019-12-30: received
See all versions
Short URL
https://ia.cr/2019/1490
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1490,
      author = {Jintai Ding and Joshua Deaton and Kurt Schmidt and Vishakha and Zheng Zhang},
      title = {Cryptanalysis of The Lifted Unbalanced Oil Vinegar Signature Scheme},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/1490},
      year = {2019},
      url = {https://eprint.iacr.org/2019/1490}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.