# In multivariate public key cryptography, why can not we use the same public key for both signature and encryption?

In multivariate public key cryptography, why can not we use the same public key for both signature and encryption?

I read that for signatures the public polynomial $$P:\mathbb{F}^n\rightarrow \mathbb{F}^m$$ has $$n\geq m$$ whereas for encryption $$m\geq n$$.

For a signature scheme, the function $$P$$ needs to be surjective i.e. for every element of the output space there exists at least one input that produces that output. This is so that the signer is able to sign data that corresponds to any output value i.e. for any given given target value $$h$$, the signer can find $$x$$ such that$$P(x)=h$$. If the function were not surjective, there would be some values for which the signer cannot produce valid signatures i.e. $$h$$ for which no $$x$$ exists. A simple counting argument shows that for this reason $$n\ge m$$ for a signature scheme.
For an encryption scheme, the function $$P$$ needs to be injective i.e. for every possible output, there is at most one input that produces it. This is so that a decryptor can unambiguously recover a message i.e. given $$m$$ find the unique $$x$$ such that $$f(x)=m$$. If the function were not injective it would be possible to produce messages that the decryption cannot uniquely decrypt i.e. there exist some messages $$m$$ for which $$f(x_1)=f(x_2)=m$$ and the decryptor has no way to tell whether the intended message is $$x_1$$ or $$x_2$$. Again a simple counting argument shows that $$m\ge n$$ for a public key encryption scheme.
We also see that to use $$P$$ for both signing and encryption, $$P$$ must be bijective (there exist $$P$$ with $$m=n$$ which are not bijective and so suitable for neither signing nor encryption). Whereas there do exist bijective multi-variate maps, it is very hard to find one for which we can hide the inverse map effectively and securely. For this reason the signing and encryption functions are usually separated.
• Can we use redundency in the plaintext (Example: if we take plaintext space to be $F^4$ and fixing 1 as the first component of the plaintext ie. $(1, a,b,c)$, then can we use signature public key to encrypt. Feb 23, 2022 at 10:01