Paper 2001/029

On multivariate signature-only public key cryptosystems

Nicolas T. Courtois

Abstract

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.