Zero knowledge proofs that one has broken a crypto system

Craig Feinstein

12/23/23, 12:14 AM

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?

730

1 + 0

zero-knowledge-proofs

Score:6

Crypto

Geoffroy Couteau

12/23/23, 1:31 AM

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

+ 2

Craig Feinstein

12/23/23, 1:48 AM

Are there any public challenges for other crypto systems like the RSA number challenge?

Geoffroy Couteau

12/23/23, 1:53 AM

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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Zero knowledge proofs that one has broken a crypto system

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.