Is there a zero knowledge proof to show an encrypted blob is the key for a given public key?

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?

• I'm pretty new to zero knowledge proofs, so sorry if this is a well known thing. – David Grinberg Aug 7 at 17:04
• What key are you encrypting $x$ under? – Mark Aug 8 at 0:43
• @Mark A public key from any asymmetric encryption scheme which will work. – David Grinberg Aug 8 at 1:27
• 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 – 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.