Paper 2001/029

On multivariate signature-only public key cryptosystems

Nicolas T. Courtois


In a paper published at Asiacrypt 2000 a signature scheme that (apparently) cannot be abused for encryption is published. The problem is highly non-trivial and every solution should be looked upon with caution. What is especially hard to achieve is to avoid that the public key should leak some information, to be used as a possible "shadow" secondary public key. In the present paper we argument that the problem has many natural solutions within the framework of the multivariate cryptography. First of all it seems that virtually any non-injective multivariate public key is inherently unusable for encryption. Unfortunately having a lot of leakage is inherent to multivariate cryptosystems. Though it may appear hopeless at the first sight, we use this very property to remove leakage. In our new scenario the Certification Authority (CA) makes extensive modifications of the public key such that the user can still use the internal trapdoor, but has no control on any publicly verifiable property of the actual public key equations published by CA. Thus we propose a very large class of multivariate non-encryption PKI schemes with many parameters $q,d,h,v,r,u,f,D$. The paper is also of independent interest, as it contains all variants of the HFE trapdoor public key cryptosystem. We give numerous and precise security claims that HFE achieves or appears to achieve and establish some provable security relationships.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Hidden Field EquationsHFE problemHFEv-Quartzescrowed cryptographyshort signaturesexportable cryptography
Contact author(s)
courtois @ minrank org
2001-04-04: received
Short URL
Creative Commons Attribution


      author = {Nicolas T.  Courtois},
      title = {On multivariate signature-only public key cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 2001/029},
      year = {2001},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.