3
$\begingroup$

Let's assume we are using the textbook RSA where $Sig(x)=x^d$. Alice has public key $(e,N)$, and private key $(d,p,q)$.

Now, if Alice sends $Sig(5)$ and $Sig(10)$ to Bob, where $5$ and $10$ is just numbers, is there a way to combine them on Bob's side to get $Sig(15)$?

If this is not possible in RSA, is it possible in other schemes like, for example, ElGamal) ?

Please note that I'm looking for a solution to handle this via "addition", not "multiplication".

$\endgroup$
8
  • $\begingroup$ It is likely meant $Sig(x)=x^d\bmod N$. Hint: Bob [or Carol impersonating Alice to Bob] knowing the public key, $Sig(5)$ and $Sig(10)$, can obtain $Sig(50$). $\endgroup$
    – fgrieu
    Commented May 28, 2017 at 9:24
  • $\begingroup$ Yes, thank you for your comments, it is easy to do with multiplication, however, I asking for addition. $\endgroup$ Commented May 28, 2017 at 9:53
  • $\begingroup$ In theory you could be able to compute $Sig(15)$ just with multiplication (because the products wrap around $\bmod N$). However if you found an efficient algorithm to do that I think you would have discovered an efficient way to turn textbook RSA into a fully homomorphic encryption scheme (as we are pretty sure that RSA isn't an efficient FHE scheme, it will be hard for you to find such an algorithm). $\endgroup$
    – SEJPM
    Commented May 28, 2017 at 9:59
  • 1
    $\begingroup$ @SEJPM Intent seems to be explained by that digital-cash tag... so, think crypto-currency (digital ledgers like blockchains et al). At least, that's what explains it to me (unless I'm misinterpreting something). $\endgroup$
    – e-sushi
    Commented May 28, 2017 at 10:46
  • 3
    $\begingroup$ This paper on homomorphic digital signatures might be useful; It states that additively homomorphic signature schemes must be insecure. $\endgroup$
    – Ella Rose
    Commented May 28, 2017 at 16:08

1 Answer 1

6
$\begingroup$

No, in textbook RSA signature with $\operatorname{Sig}(x)=x^d\bmod N$, there is no method to deduce $\operatorname{Sig}(15)$ from $\operatorname{Sig}(5)$ and $\operatorname{Sig}(10)$.


It is possible to deduce $\operatorname{Sig}(50)$, by using the general fact that in textbook RSA signature, if $x$ and $y$ are positive integers (with $xy$ below the limit for messages that can be signed, if any), then $\operatorname{Sig}(xy)\;=\;\operatorname{Sig}(x)\operatorname{Sig}(y)\bmod N$. But notice that being able to obtain an admissible signature for a message from the signature of other messages is considered a break of a signature scheme. That's why textbook RSA signature with $\operatorname{Sig}(x)=x^d\bmod N$ is not a secure signature scheme (rather, it is a building block towards one).

Further, if we have a signature scheme such that $\operatorname{Sig}(x+y)$ can be deduced from $\operatorname{Sig}(x)$ and $\operatorname{Sig}(y)$, then the signature of any message $x>0$ can be deduced from $\operatorname{Sig}(1)$ with $O(\log(x))$ deductions. That's why the literature tends to consider such additively homomorphic signature schemes only to repel them.


If we really want an additively homomorphic signature scheme, we can define one related to RSA, as $\operatorname{Sig'}(x)=\operatorname{Sig}(g^x\bmod N)=(g^x\bmod N)^d\bmod N=(g^d\bmod N)^x\bmod N$ for some fixed public $g$ generator of the groups $\mathbb Z_p^*$ and $\mathbb Z_q^*$ (it is easier and best that $(p-1)/2$ and $(q-1)/2$ are primes). In order to verify the alleged signature $s$ of $x$ per this system, it is checked that $s$ is the textbook RSA signature for $g^x\bmod N$, that is $0\le s<N$ and $s^e\bmod N\,=\,g^x\bmod N$. For all non-zero $a$ and $b$ and messages $x$ and $y$ it holds that $\operatorname{Sig'}(ax+by)\;=\;\operatorname{Sig'}(x)^a\operatorname{Sig'}(y)^b\bmod N$. This is comes at the price of extreme insecurity: revealing the signature of $x$ and $y$ allows the efficient computation of the signature of any multiple of $\gcd(x,y)$.

$\endgroup$
2
  • 2
    $\begingroup$ You may want to note that as per your reasoning such a scheme at least violates the UF-KMA security definition. $\endgroup$
    – SEJPM
    Commented May 28, 2017 at 12:18
  • $\begingroup$ To complete @SEJPM 's comment: For example, given the signature on message $1$, say $\sigma = \operatorname{Sig'}(1)$, the signature on any message $x$ can be obtained as $\operatorname{Sig'}(x) = \sigma^x \bmod N$. $\endgroup$
    – user94293
    Commented May 29, 2017 at 21:20

Your Answer

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

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