Let's say I have a private key x with a corresponding public key y. If I encrypt x as E(x), is there a zero knowledge proof I can use to show that E(x) contains the private key for y?

  • $\begingroup$ I'm pretty new to zero knowledge proofs, so sorry if this is a well known thing. $\endgroup$ – David Grinberg Aug 7 at 17:04
  • $\begingroup$ What key are you encrypting $x$ under? $\endgroup$ – Mark Aug 8 at 0:43
  • $\begingroup$ @Mark A public key from any asymmetric encryption scheme which will work. $\endgroup$ – David Grinberg Aug 8 at 1:27
  • $\begingroup$ This is possible. You can first start off by looking at how to prove that the prover knows the pre-Image for a given digest. Ie “I know x such that y =h(x)” Then you can look how one proves that I know a private key p such that K=pG” where G is a generator and K is the corresponding pubkey. Putting both of these schemes together and you should be able to get your desired proof statement. You would need to replace the hash function with your encryption scheme, however it is generally the same from a higher level $\endgroup$ – user679128 Aug 15 at 9:47

I am assuming that you are encrypting $x$ under a different public key from potentially a different scheme. The answer is yes, since every language in NP can be proven in zero knowledge. The question, of course, is can this be done efficiently. The answer to that depends on the schemes involved.

  • $\begingroup$ Thanks. This is still just an idea that is wracking around my head, so I haven't settled yet on any particular encryption schemes. Do you know if there are any practical schemes (e.g. not ROT-13) which can be done in a practical amount of time? $\endgroup$ – David Grinberg Aug 8 at 2:53
  • $\begingroup$ Most symmetric systems can be implemented as an arithmetic circuit, and be used in e.g. Bulletproofs. I have a Keccak-f[1600] implementation laying around, and it'd be quite trivial to build a Ketje cipher or something alike on top. One Keccak-f[1600] permutation takes about 60 seconds to prove, the rest of Ketje should be quite fast. AES circuits might even be faster. $\endgroup$ – Ruben De Smet Aug 8 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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