Paper 2020/967

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

Jintai Ding, Joshua Deaton, 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
CryptanalysisMultivariateLUOVPracticalNISTPost-Quantum
Contact author(s)
deatonju @ ucmail uc edu
History
2020-09-15: last of 2 revisions
2020-08-11: received
See all versions
Short URL
https://ia.cr/2020/967
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/967,
      author = {Jintai Ding and Joshua Deaton and Vishakha and Bo-Yin Yang},
      title = {The Nested Subset Differential Attack: A Practical Direct Attack Against LUOV which Forges a Signature within 210 Minutes},
      howpublished = {Cryptology ePrint Archive, Paper 2020/967},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/967}},
      url = {https://eprint.iacr.org/2020/967}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.