4
$\begingroup$

Is RSA-signing a given challenge $x$ a zero-knowledge proof of holding the RSA private key, for the modern definition of zero-knowledge proof (which I don't know!)

Assume public and genuine RSA public key $(n,e)$, secret RSA private key $(n,e,d,p,q\ldots)$ with distinct secret primes $p$ and $q$, that the factorization of $n$ can't be found from the public key or from access to a textbook RSA signature oracle, and that the RSA assumption holds.

If necessary, distinguish between

  • textbook RSA signature $x\mapsto x^d\bmod n$
  • RSA signature with deterministic padding, e.g. RSA-FDH, or RSASSA-PKCS1-v1_5
  • RSA signature with random padding, e.g. RSASSA-PSS

Motivation is this question, and specifically this answer.

Update: I'm reading the answers to a similar question (on signature in general) as no. But I'd like an answer based on a definition of zero-knowledge proof.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ This question is still bugging me as well. On the other hand, this answer (crypto.stackexchange.com/a/35185/58690) seems to show that such a protocol isn't necessarily ZK? Taking into account that ZKP is supposed to reveal nothing else, I wonder if for RSA (e.g.: FDH), the singer is additionally revealing $e'th$ roots? $\endgroup$
    – Marc Ilunga
    Jun 9, 2022 at 12:23
  • 1
    $\begingroup$ It's relatively easy to see that textbook RSA signatures would not lead to a ZK protocol. A simulator would have to be able to invert the RSA TDP on a significant fraction of the domain, which would simply break the RSA assumption. (It's probably also no a proof of knowledge of anything, at least I don't see how the extractor should work.) But that's not a secure signature scheme, so that seems kind of irrelevant. It is HVZK I think. Just compute the transcript backwards. $\endgroup$
    – Maeher
    Jun 9, 2022 at 13:17
  • 1
    $\begingroup$ Obviously, if a ZKP is supposed to reveal nothing other than the truth of the assertion, signing a challenge message is not ZK - after all, in addition to the statement "the prover knows the private key", the challenger also learns "what is a valid signature for message $x$?" $\endgroup$
    – poncho
    Jun 9, 2022 at 15:26
  • $\begingroup$ My comment on FDH RSA was actually incorrect. We can't reprogram at that point in a deterministic signature scheme. For a randomized version of FDH it would work. $\endgroup$
    – Maeher
    Jun 9, 2022 at 15:41
  • $\begingroup$ @poncho that's not the definition of ZK though. That's an intuitive description of what it's supposed to achieve and it often leads people astray. $\endgroup$
    – Maeher
    Jun 9, 2022 at 15:42

1 Answer 1

Reset to default
2
$\begingroup$

Firstly, we do not not know that any of the signature schemes is proof of holding the RSA secret key $d$. They would be proof of possession of an RSA decryption oracle/method corresponding to the exponent $e$, but we don't know if this necessarily implies knowledge of $d$. This is related to the unanswered question as to whether the RSA problem is as hard as factoring. If we know $d$, we could factor the modulus and so if access to a decryption oracle implies knowledge of $d$ then the RSA problem is equivalent to factoring.

However, if someone can produce arbitrary text book RSA signatures for any exponent $e$ rather than just a fixed one, then this would imply knowledge of $d$ because this "generic" RSA problem is known to be equivalent to factoring (see Aggarwal and Maurer Breaking RSA Generically is Equivalent to Factoring).

Producing signatures for uniform random inputs in textbook RSA is zero-knowledge because the transcripts can be simulated simply by choosing a uniform random output and raising to the power $e$. More structured outputs cannot easily be simulated and a supplied challenge would need to be randomly blinded to guarantee zero-knowledge.

Improve this answer
$\endgroup$
1

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.