Cryptology ePrint Archive: Report 2021/084
Ariadne Thread and Salt: New Multivariate Cryptographic Schemes with Public Keys in Degree 3
Gilles Macario-Rat and Jacques Patarin
Abstract: In this paper, we present two new perturbations for the design of multivariate schemes that we call ``Ariadne Thread'' and ``Salt''. 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 Salt can also be seen as new ``perturbations'' that we can use to enforce many multivariate schemes. The ``Salt'' 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.
Category / Keywords: public-key cryptography / public-key cryptography, post-quantum multivariate cryptography, UOV, HFE, AES
Date: received 23 Jan 2021, last revised 15 Feb 2021
Contact author: gilles macariorat at orange com,jpatarin@club-internet fr
Available format(s): PDF | BibTeX Citation
Version: 20210215:140335 (All versions of this report)
Short URL: ia.cr/2021/084
[ Cryptology ePrint archive ]