International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Jintai Ding , Tsinghua University
Joshua Deaton , University of Cincinnati
Vishakha , University of Cincinnati
Bo-Yin Yang , Academia Sinica
Download:
DOI: 10.1007/978-3-030-77870-5_12 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2021
Abstract: In 2017, Ward Beullenset al.submitted Lifted Unbalanced Oil and Vinegar [4], which is a modification to the Unbalanced Oil and Vinegar Schemeby Patarin. Previously, Ding et al.proposed the Subfield Differential Attack [20]which prompted a change of parameters by the authors of LUOV for the second round of the NIST post quantum standardization competition [3].In this paper we propose a modification to the Subfield Differential Attackcalled the Nested Subset Differential Attack which fully breaks half of the parameter sets put forward. We also show by experimentation that this attack is practically possible to do in under 210 minutes for the level I security parameters and not just a theoretical attack. The Nested Subset Differential attack is a large improvement of the Subfield differential attack which can be used in real 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.
Video from EUROCRYPT 2021
BibTeX
@inproceedings{eurocrypt-2021-30885,
  title={The Nested Subset Differential Attack: A Practical Direct Attack Against LUOV which Forges a Signature within 210 Minutes},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-77870-5_12},
  author={Jintai Ding and Joshua Deaton and  Vishakha and Bo-Yin Yang},
  year=2021
}