# Zero-Knowledge proof for data being decryptable to a given hash preimage

Alice has $m$ which is the hash preimage of $h_m$, namely $\operatorname{SHA256}(m) = h_m$.

Consider the following protocol. Alice does the following: \begin{align*} r &:= \operatorname{Gen} \\ h_r &:= \operatorname{SHA256}(r) \\ \hat m &:= \operatorname{Enc}(m, r), \end{align*} where $\operatorname{Gen}$ is some secure random key generator and $\operatorname{Enc}$ is some symmetric encryption algorithm (say AES).

At this point, provided that Alice would give Bob $h_m$, $h_r$ and $\hat m$, can she prove to Bob using ZKP (e.g. zk-SNARKS) the following statement?

There exists $r$ such that $h_r = \operatorname{SHA256}(r)$ and $\operatorname{SHA256}(\operatorname{Dec}(\hat m, r)) = h_m$?

I know the first part is possible ("there exists $r$ such that $h_r = \operatorname{SHA256}(r)$") but I'm not sure about the second part, specifically the composition of $\operatorname{SHA256}$ and $\operatorname{Dec}$.

My intuition is that it is possible, since we can have a witness for that question which can be verified at polynomial time, and thus it's an NP language, but I'm not sure.

## 1 Answer

There has been some recent progress [1] on efficient zero-knowledge for such statements. Essentially they present a $\Sigma$-protocol to prove statements over general circuits. To prove the AND relation you state, you could essentially just build one large circuit which takes (the bits of) $r$ as input and outputs $h_r$ and $h_m$ so that $h_r = \operatorname{SHA256}(r)$ and $h_m = \operatorname{SHA256}(\operatorname{Dec}(\hat m, r))$, where $\hat m$ is hardcoded in the circuit.

The proofs above are of linear size in the number of AND gates in the circuit. If you want something more compact you might want to have a look at SNARKs.

References