Paper 2021/655

On the Effect of Projection on Rank Attacks in Multivariate Cryptography

Morten Øygarden, Daniel Smith-Tone, and Javier Verbel

Abstract

The multivariate scheme HFEv- used to be considered a promising candidate for a post-quantum signature system. First suggested in the early 2000s, a version of the scheme made it to the third round of the ongoing NIST post-quantum standardization process. In late 2020, the system suffered from an efficient rank attack due to Tao, Petzoldt, and Ding. In this paper, we inspect how this recent rank attack is affected by the projection modification. This modification was introduced to secure the signature scheme PFLASH against its predecessor's attacks. We prove upper bounds for the rank of projected HFEv- (pHFEv-) and PFLASH under the new attack, which are tight for the experiments we have performed. We conclude that projection could be a useful tool in protecting against this recent cryptanalysis.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. PQCrypto 2021
Keywords
post-quantum cryptographymultivariate cryptographyminrank
Contact author(s)
morten oygarden @ simula no
daniel smith @ nist gov
Javier Verbel @ tii ae
History
2021-05-20: received
Short URL
https://ia.cr/2021/655
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/655,
      author = {Morten Øygarden and Daniel Smith-Tone and Javier Verbel},
      title = {On the Effect of Projection on Rank Attacks in Multivariate Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2021/655},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/655}},
      url = {https://eprint.iacr.org/2021/655}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.