3
$\begingroup$

Suppose someone has figured out how to factor integers in polynomial time, thus breaking the RSA system. Also suppose this person does not want to reveal the secret of how to factor integers in polynomial time, only to prove he or she has broken it (or at least give evidence that he has broken it). One way to do this would be to present factors of the RSA numbers https://en.m.wikipedia.org/wiki/RSA_numbers

My question is are there other ways of giving zero knowledge proofs that one has broken a cryptosystem?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

Sure! For example, you could prove in zero-knowledge that you know the prime factors of $n$, where $n$ is an online RSA challenge (i.e. something we know for sure you did not create yourself).

Such a zero-knowledge proof would look as follow: you commit to the two prime factors $p, q$. You prove that the commitments contain primes, and you prove that their product is $n$.

This is actually a relatively common zero-knowledge proof in cryptography, but in a different context: it is used to prove, when you generate an RSA key $n$, that you generated it correctly and that it has the right structure. The seminal paper describing a zero-knowledge proof for this task is this one.

In general, for any cryptosystem which you have broken, you can always be challenged to e.g. prove that you know the plaintext of a challenge ciphertext, or prove thar you know the secret key associated to a public key. For essentially all cryptosystems in use, this statement is an NP statement, hence it admits a zero-knowledge proof of knowledge (if one-way functions exist).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Are there any public challenges for other crypto systems like the RSA number challenge? $\endgroup$
    – Craig Feinstein
    Dec 23, 2022 at 1:48
  • 1
    $\begingroup$ There are probably tons of discrete logarithm challenges out there (solving discrete logarithm would break ElGamal, another famous cryptosystem). I'm pretty sure there are challenges somewhere for symmetric cryptosystems, but this is not something I'm knowledgeable about. In any case, creating a challenge is straightforward: anyone who wants to be convinced can generate a key pair and ask you to prove that you can break the scheme. $\endgroup$
    – Geoffroy Couteau
    Dec 23, 2022 at 1:53

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.