International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Cryptanalysis of The Lifted Unbalanced Oil Vinegar Signature Scheme

Authors:
Jintai Ding , University of Cincinnati
Joshua Deaton , University of Cincinnati
Kurt Schmidt , University of Cincinnati
Vishakha , University of Cincinnati
Zheng Zhang , University of Cincinnati
Download:
DOI: 10.1007/978-3-030-56877-1_10 (login may be required)
Search ePrint
Search Google
Conference: CRYPTO 2020
Abstract: In 2017, Ward Beullens et al. submitted Lifted Unbalanced Oil and Vinegar (LUOV), 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 postquantum standardization competition.
Video from CRYPTO 2020
BibTeX
@inproceedings{crypto-2020-30494,
  title={Cryptanalysis of The Lifted Unbalanced Oil Vinegar Signature Scheme},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-56877-1_10},
  author={Jintai Ding and Joshua Deaton and Kurt Schmidt and  Vishakha and Zheng Zhang},
  year=2020
}