Paper 2021/1070

Onyx: New Encryption and Signature Schemes with Multivariate Public Key in Degree 3

Gilles Macario-Rat and Jacques Patarin

Abstract

In this paper, we present a new secret trapdoor function for the design of multivariate schemes that we call ``Onyx'', suitable for encryption and signature. It has been inspired by the schemes presented in Ariadne Thread and Pepper: New mul-tivariate cryptographic schemes with public keys in degree 3. . From this idea, we present some efficient encryption and signature multivariate schemes with explicit parameters that resist all known attacks. In particular they resist the two main (and often very powerful) attacks in this area: the Gröbner attacks (to compute a solution of the system derived from the public key) and the MinRank attacks (to recover the secret key). Specific attacks due to the properties of the function and its differential are also addressed in this paper. The ``Onyx'' schemes have public key equations of degree 3. Despite this, the size of the public key may still be reasonable since we can use larger fields and smaller extension degrees. Onyx signatures can be as short as the ``birthday paradox'' allows, i.e. twice the security level, or even shorter thanks to the Feistel-Patarin construction, like many other signatures schemes based on multivariate equations.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
public-key cryptographypost-quantum multivariate cryptographyUOVHFEGröbner basisMinRank problemdifferential attacks.
Contact author(s)
gilles macariorat @ orange com
jpatarin @ club-internet fr
History
2021-12-16: last of 3 revisions
2021-08-23: received
See all versions
Short URL
https://ia.cr/2021/1070
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1070,
      author = {Gilles Macario-Rat and Jacques Patarin},
      title = {Onyx: New Encryption and Signature Schemes with Multivariate Public Key in Degree 3},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1070},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1070}},
      url = {https://eprint.iacr.org/2021/1070}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.