# 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.

There has been some recent progress  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.