Score:5

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

us flag

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

Score:5
ru flag

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.

Shweta Aggrawal avatar
us flag
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.
Daniel S avatar
ru flag
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.
Shweta Aggrawal avatar
us flag
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.
Score:-1
mx flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.