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)
- 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
-
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}, url = {https://eprint.iacr.org/2020/967} }