[Resource Topic] 2001/029: On multivariate signature-only public key cryptosystems

Welcome to the resource topic for 2001/029

On multivariate signature-only public key cryptosystems

Authors: 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.

ePrint: https://eprint.iacr.org/2001/029

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .