Can I use zero-knowledge proofs on pre-image of symmetric encryption?

Let $$e_x$$ be a symmetric encryption function in regards to key $$x$$. Let $$y_1 = e_1(x_1), y_2 = e_2(x_2)$$.

My goal is to prove that: $$x_1 = x_2$$ Is there a way of proving this using ZKP? I can't seem to find anything on zero-knowledge proofs on symmetric encryption.

My ultimate goal involves a hash function $$H$$ and $$y_1 = e_1(x_1), y_2 = e_2(H(x_2))$$ where I want to prove that $$x_1 = x_2$$, but that may be too much to ask for right now.

• As long as the statement is in NP (which is your case), it can be proved in zero-knowledge, but this would involve "generic" solutions (e.g., GMR construction). Coming up with more efficient solutions would require looking at the specific encryption scheme in question. Aug 7 '20 at 18:47
• First of all, you need to decide what the ZKP actually proves. Does it mean "given a one way function of the keys $F(k_1), F(k_2)$ and the values $y_1, y_2$, we have $y_1 = e_{k_1}(x)$ and $y_2 = e_{k_2}(x)$ for some $x$"? Or, is it a proof that I know keys $k_x, k_y$ such that $d_{k_x}(y_1) = d_{k_y}(y_2)$ (where $d_k$ is the symmetric decryption function)? Aug 7 '20 at 19:34
• For an example of zero-knowledge proofs about block ciphers, you could look at Picnic: microsoft.github.io/Picnic Aug 8 '20 at 8:23
• @Occams_Trimmer I'm not sure in this case the statement would be in NP, because even if I were to give the value of $x_1$ (or $x_2$), the verifier cannot verify the solution in polynomial time since they do not have access to any of the secret symmetric keys.
– Fred
Aug 10 '20 at 8:31
• @poncho What I want to prove is: given $y_1, y_2$, I want to prove that $\exists k_1, k_2, x$ such that: $y_1 = e_{k_1}(x), y_2 = e_{k_2}(x)$
– Fred
Aug 10 '20 at 8:34