Cryptology ePrint Archive: Report 2019/1490

Cryptanalysis of The Lifted Unbalanced Oil Vinegar Signature Scheme

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

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 $\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.

Category / Keywords:

Date: received 27 Dec 2019

Contact author: jintai ding at gmail com,deatonju@mail uc edu,schmidku@mail uc edu,sharmav4@mail uc edu,zhang2zh@mail uc edu

Available format(s): PDF | BibTeX Citation

Version: 20191230:193523 (All versions of this report)

Short URL: ia.cr/2019/1490


[ Cryptology ePrint archive ]