Paper 2023/059

Oil and Vinegar: Modern Parameters and Implementations

Ward Beullens, IBM Research - Zurich
Ming-Shing Chen, Academia Sinica
Shih-Hao Hung, National Taiwan University
Matthias J. Kannwischer, Academia Sinica
Bo-Yuan Peng, Academia Sinica, National Taiwan University
Cheng-Jhih Shih, Academia Sinica
Bo-Yin Yang, Academia Sinica
Abstract

Two multivariate digital signature schemes, Rainbow and GeMSS, made it into the third round of the NIST PQC competition. However, either made its way to being a standard due to devastating attacks (in one case by Beullens, the other by Tao, Petzoldt, and Ding). How should multivariate cryptography recover from this blow? We propose that, rather than trying to fix Rainbow and HFEv- by introducing countermeasures, the better approach is to return to the classical Oil and Vinegar scheme. We show that, if parametrized appropriately, Oil and Vinegar still provides competitive performance compared to the new NIST standards by most measures (except for key size). At NIST security level 1, this results in either 128-byte signatures with 44 kB public keys or 96-byte signatures with 67 kB public keys. We revamp the state-of-the-art of Oil and Vinegar implementations for the Intel/AMD AVX2, the Arm Cortex-M4 microprocessor, the Xilinx Artix-7 FPGA, and the Armv8-A microarchitecture with the Neon vector instructions set.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published by the IACR in TCHES 2023
Keywords
Oil and VinegarIntel AVX2Arm NeonArm Cortex-M4Xilinx Artix-7
Contact author(s)
WBE @ zurich ibm com
mschen @ crypto tw
matthias @ kannwischer eu
bypeng @ crypto tw
cs861324 @ gmail com
by @ crypto tw
History
2023-04-10: revised
2023-01-19: received
See all versions
Short URL
https://ia.cr/2023/059
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/059,
      author = {Ward Beullens and Ming-Shing Chen and Shih-Hao Hung and Matthias J. Kannwischer and Bo-Yuan Peng and Cheng-Jhih Shih and Bo-Yin Yang},
      title = {Oil and Vinegar: Modern Parameters and Implementations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/059},
      year = {2023},
      url = {https://eprint.iacr.org/2023/059}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.