Paper 2021/084

Ariadne Thread and Pepper: New Multivariate Cryptographic Schemes with Public Keys in Degree 3

Gilles Macario-Rat and Jacques Patarin


In this paper, we present two new perturbations for the design of multivariate schemes that we call ``Ariadne Thread'' and ``Pepper''. From these ideas, we present some efficient multivariate encryption and signature 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 cleartext from a ciphertext) and the MinRank attacks (to recover the secret key). Ariadne Threat and Pepper can also be seen as new ``perturbations'' that we can use to enforce many multivariate schemes. The ``Pepper'' perturbation works only for public key equations of degree (at least) 3. Similarly at present the ``Ariadne Thread'' perturbation seems to be particularly powerful with public keys of degree 3. Despite this, the size of the public key may still be reasonable since we can use larger fields (and also maybe non dense equations). Ariadne Thread perturbation seems to be particularly interesting for encryption. This is unusual since in multivariate cryptography encryption is generally more difficult than signatures.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
public-key cryptographypost-quantum multivariate cryptographyUOVHFEAES
Contact author(s)
gilles macariorat @ orange com
jpatarin @ club-internet fr
2021-08-16: last of 6 revisions
2021-01-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gilles Macario-Rat and Jacques Patarin},
      title = {Ariadne Thread and Pepper: New Multivariate Cryptographic Schemes with Public Keys in Degree 3},
      howpublished = {Cryptology ePrint Archive, Paper 2021/084},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.