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.

  • $\begingroup$ 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. $\endgroup$ Aug 7 '20 at 18:47
  • $\begingroup$ 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)? $\endgroup$
    – poncho
    Aug 7 '20 at 19:34
  • 1
    $\begingroup$ For an example of zero-knowledge proofs about block ciphers, you could look at Picnic: microsoft.github.io/Picnic $\endgroup$ Aug 8 '20 at 8:23
  • $\begingroup$ @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. $\endgroup$
    – Fred
    Aug 10 '20 at 8:31
  • $\begingroup$ @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)$ $\endgroup$
    – Fred
    Aug 10 '20 at 8:34

Your Answer

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

Browse other questions tagged or ask your own question.