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 $\mathcal{P}$ works in the extension field of degree $r$ of $\mathbb{F}_2$, the coefficients of $\mathcal{P}$ come from $\mathbb{F}_2$. This is done to significantly reduce the size of $\mathcal{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},
      note = {\url{https://eprint.iacr.org/2019/1490}},
      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.