TY - GEN
T1 - Cryptanalysis of the lifted unbalanced oil vinegar signature scheme
AU - Ding, Jintai
AU - Deaton, Joshua
AU - Schmidt, Kurt
AU - Vishakha,
AU - Zhang, Zheng
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2020.
PY - 2020
Y1 - 2020
N2 - In 2017, Ward Beullens et al. submitted Lifted Unbalanced Oil and Vinegar (LUOV) [4], 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.
AB - In 2017, Ward Beullens et al. submitted Lifted Unbalanced Oil and Vinegar (LUOV) [4], 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.
UR - http://www.scopus.com/inward/record.url?scp=85089720603&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-56877-1_10
DO - 10.1007/978-3-030-56877-1_10
M3 - Conference Proceeding
AN - SCOPUS:85089720603
SN - 9783030568764
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 279
EP - 298
BT - Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, Proceedings
A2 - Micciancio, Daniele
A2 - Ristenpart, Thomas
PB - Springer
T2 - 40th Annual International Cryptology Conference, CRYPTO 2020
Y2 - 17 August 2020 through 21 August 2020
ER -