Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
Does this also have something to do with the common modulus attack? At least for RSA-like encryption. Basically, if p, q, and r are prime (and large), the integer pq is difficult to factor on its own, and so is the integer pr. But the GCD(pq, pr) is easy, and that breaks both keys, hence you can't reuse keys.
