5
$\begingroup$

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$.

$\endgroup$

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Feb 23, 2022 at 10:01
  • $\begingroup$ Possibly, though this would lead to functions that are injective for an input subspace and surjective for an output subspace (note that the dimensions alone are not enough to guarantee infectivity/surjectivity). The constructions that I can think of would then lead to a bijective function between an input subspace and an output subspace from which structure can likely be recovered. $\endgroup$
    – Daniel S
    Feb 23, 2022 at 10:08
  • $\begingroup$ Actually I saw this remark on page 171, Multivariate public key cryptography Volume 80, Ding et al book. Can you please explain your above comment in more detail. I would be grateful to you. Thank you so much for responding. $\endgroup$ Feb 23, 2022 at 10:12
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.