Paper 2026/1607
UFOs: A Very Efficient Multivariate Public Key Signature Scheme
, Orange ResearchAbstract
We present UFOs, a multivariate public-key signature scheme in the Unbalanced Oil and Vinegar (UOV) family. The scheme replaces generic quadratic polynomials with a structured subclass based on Frobenius-type quadratic forms, yielding a compressed public-key representation while retaining the efficient UOV signing procedure. We describe the key-generation, signing, and verification algorithms, and we detail the derivation of the public system from a compact secret description. We discuss security in the standard multivariate setting, including direct algebraic attacks and key-recovery approaches, and we formalize the underlying computational problems induced by the proposed structure. Finally, we report implementation results quantifying the costs of key generation, signing, and verification, as well as the resulting public-key and signature sizes.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- UOVpost-quantum signaturesmultivariate cryptographyFrobenius formsquadratic forms
- Contact author(s)
- gilles macariorat @ orange com
- History
- 2026-08-06: approved
- 2026-08-04: received
- See all versions
- Short URL
- https://ia.cr/2026/1607
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/1607,
author = {Gilles Macario-Rat},
title = {{UFOs}: A Very Efficient Multivariate Public Key Signature Scheme},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1607},
year = {2026},
url = {https://eprint.iacr.org/2026/1607}
}
