Cryptology ePrint Archive: Report 2020/967

The Nested Subset Differential Attack: A Practical Direct Attack Against LUOV which Forges a Signature within 210 Minutes

Jintai Ding and Joshua Deaton and Vishakha and Bo-Yin Yang

Abstract: In 2017, Ward Beullenset al.submitted Lifted Unbalanced Oil andVinegar, which is a modification to the Unbalanced Oil and Vinegar Schemeby Patarin. Previously, Dinget al.proposed the Subfield Differential Attack which prompted a change of parameters by the authors of LUOV for the sec-ond round of the NIST post quantum standardization competition. In this paper we propose a modification to the Subfield Differential Attack called the Nested Subset Differential Attack which fully breaks half of the pa-rameter sets put forward. We also show by experimentation that this attack ispractically possible to do in under 210 minutes for the level I security param-eters and not just a theoretical attack. The Nested Subset Differential attack isa large improvement of the Subfield differential attack which can be used inreal world circumstances. Moreover, we will only use what is called the "lifted"structure of LUOV, and our attack can be thought as a development of solving"lifted" quadratic systems.

Category / Keywords: secret-key cryptography / Cryptanalysis, Multivariate, LUOV, Practical, NIST, Post-Quantum

Date: received 8 Aug 2020, last revised 14 Sep 2020

Contact author: deatonju at ucmail uc edu

Available format(s): PDF | BibTeX Citation

Version: 20200915:013039 (All versions of this report)

Short URL: ia.cr/2020/967


[ Cryptology ePrint archive ]