Is exposing hash of private key provably secure?

Question

Let's say we have an IND-CPA secure public key encryption scheme $\Pi = (\text{Gen}, \text{Enc}, \text{Dec})$. Construct a new PKE $\Pi' = (\text{Gen}', \text{Enc}', \text{Dec}')$ that behaves exactly as $\Pi$ except it additionally leaks the hash of the private key. For example, $\text{Gen}' = (sk, pk \vert \vert H(sk))$ where $(pk,sk) \xleftarrow{} \text{Gen}()$ and $H$ is a hash function (for concreteness let's say SHA256).

Is this new scheme "provably secure" in either the standard model (first preimage resistance, etc.) or random oracle model? That is, does $\Pi \text{ is IND-CPA secure } \land \text{ some assumptions on } H \implies \Pi' \text{ is IND-CPA secure}$?

Intuitively, it feels like a proof in the ROM should be possible. Naive intuition: if the hash of the private key looks like a random value to the adversary, it shouldn't be providing any additional information to breaking the PKE scheme. But I struggle to create a proof (possibly because I don't fully understand ROM proofs).

Here's a first pass.

• Let $\mathcal{A}$ be a PPT against $\Pi'$ with advantage $\epsilon$
• Construct adversary $\mathcal{B}$ against $\Pi$ using $\mathcal{A}$:
  • $\Pi$ challenger generates $(pk,sk)$ and sends $pk$ to $\mathcal{B}$
  • $\mathcal{B}$ generates a random value $r$, and starts $\mathcal{A}$ by sending it $pk \vert\vert r$
  • $\mathcal{A}$ makes some random oracle queries $x_i$, gets back random $r_i$
  • $\mathcal{A}$ submits messages $m_0, m_1$ for encryption
  • $\mathcal{B}$ forwards these messages to $\Pi$ challenger, which randomly chooses $b \xleftarrow{} (0,1)$, encrypts and returns $\text{Enc}(pk, m_b)$; $\mathcal{B}$ forwards this challenge encryption to $\mathcal{A}$
  • $\mathcal{A}$ outputs $\hat{b}$, and $\mathcal{B}$ outputs the same

I'm not sure how to reason about the success probability of $\mathcal{B}$ here. If $\mathcal{A}$ never actually queries the random oracle on $sk$, then $\mathcal{B}$ faithfully simulates a $\Pi'$ challenger to $\mathcal{A}$. However, if $\mathcal{A}$ does query the random oracle on $sk$, then it is going to get a random value instead of $H(sk)$ which it knows from the public key. This is an observable difference between a real $\Pi'$ challenger and the simulation of a $\Pi'$ challenger by $\mathcal{B}$. So I think I can't just conclude that the success probability of $\mathcal{B}$ is the same as the success probability of $\mathcal{A}$.

Any thoughts on if this proof can be made to work? :)

---

Note that I have seen the related question: Publicly exposed hash of private key. I believe the current question is asking for something more general and rigorous then that question. In particular, that question is specific to RSA and neither answer contains a proof.

Answer 1

With the question's statement, there is no insurance that $\Pi'$ is secure.

We build a counterexample $\Pi$ from ECIES on curve secp256r1. In this ECIES encryption system, the private key is any integer $d\in[1,n)$ where $n$ is some fixed 256-bit prime, and the public key is obtained from $d$. We modify ECIES into $\Pi$ by making the private key of $\Pi$ any 256-bit bitstring $\text{Priv}$, and computing ECIES's $d$ as $d\gets(H(\text{Priv})\bmod(n-1))+1$. This is done

• at key generation, to build $d$ and from that the public key of both ECIES and $\Pi$
• at decryption, to build $d$ from $\Pi$'s private key $\text{Priv}$ and then apply ECIES's decryption procedure.

Our $\Pi$ is secure, but $\Pi'$ is not, because given $h=H(\text{Priv})$ we can compute $d\gets(h\bmod(n-1))+1$ and decipher.

---

In order to make $\Pi'$ secure, we need to make $H$ a random oracle or PRF that's independent of anything used in $\Pi$.

Informal argument that $\Pi'$ is secure when $H$ is modeled by a "fresh" random oracle that is not invoked in the definition/use of $\Pi'$: compared to attacking $\Pi$, an adversary attacking $\Pi'$ additionally gets the value of $H(\text{sk})$, which is a random number; and oracle access to $H$. The only useful thing to do with such extra information "obviously" is to verify an exact guess of $\text{sk}$ obtained by other means. And if such guess could be made, $\Pi$ would be insecure.

Closer to formal: we could turn a PPT algorithm $\mathcal A'$ that breaks IND-CPA for $\Pi'$ into a PPTA $\mathcal A$ that breaks IND-CPA for $\Pi$, or breaks (first) premiage resistance for $H$, as follows:

• when $\mathcal A$ receives $\text{Pub}$ from the IND-CPA experiment and $h$ which first preimage is thought, start $\mathcal A'$ with $h$ instead of $H(\text{sk})$
• when $\mathcal A'$ passes some message $m$ to query the random oracle $H$
  • pass this $m$ to the oracle; if the oracle outputs $h$, stop with output: "a preimage of $h$ is $m$".
  • otherwise, draw a random message $m_0$, encipher it under $\text{Pub}$ yielding $c_0$ (with $m_0$ and $c_0$ optionally cached for subsequent reuse), and try to decipher $c_0$ with $m$ as the private key; if decryption succeeds and yields $c_0$, presumably $m$ is $\text{sk}$, or some $\text{sk}'$ as good as $\text{sk}$ when it comes to decryption (if the nature of the cryptosystem leaves any doubt about this, we can and should confirm it with a number of other random message $m_i$). From then on, no longer let $\mathcal A'$ run; rather, use knowledge of that $m$ usable as $\text{sk}$ to win the IND-CPA experiment with certainty.
  • otherwise (that is, $m$ passed by $\mathcal A'$ to the random oracle is neither a preimage of $h$ nor usable to decipher), let $\mathcal A'$ continue it's run giving it whatever the oracle returned.

The outcome "finding a preimage of $h$" has vanishingly low probability. Excluding that, the probability of success of $\mathcal A$ is at least that of $\mathcal A'$.

More precisely: Probability of finding a preimage of a random $b$-bit string by a fresh¹ random oracle with $b$-bit output is $\le q/2^b$ where $q$ is the number of queries to the oracle (regardless of other work). Thus any non-negligible probability of success of $\mathcal A$ would not come from stopping with a preimage, thus must come from winning the IND-CPA game (per one of the last two bullets). Whenever $\mathcal A'$ would wins the IND-CPA game, $\mathcal A$ also does. Thus if $\mathcal A'$ wins the IND-CPA game with non-negligible probability, so does $\mathcal A$.

---

¹ I think this is where the independence is necessary: if $H$ is part of the definition of $\Pi$, then the oracle may have been part of the key generation process and is not fresh.

Answer 2

The generic statement is false. You would need an additional assumption that $\Pi$ and $H$ are “sufficiently” independent.

Let's build a “silly” counterexample. From a public key encryption scheme $\Pi$, define a public encryption scheme $\Pi_H$ which is $\Pi$ except that what $\Pi_H$ calls its private key $k$ is hashed with $H$ before doing anything else. (If the output of $H$ is not long enough, use a PRF seeded with $H(k)$.) Revealing $H(k)$ (where $k$ is the private key of $\Pi_H$) is equivalent to revealing the private key of $\Pi$. So revealing a hash of the private key is definitely not secure for $\Pi_H$.

This may look silly at first glance, but it's actually pretty close to how EdDSA is defined.

---

If you need a “key hash” value, base it on the public key, not on the private key.

$H(S || k)$ where $S$ is some string that “doesn't appear” in the construction of $\Pi$ (so $H(S||\cdot)$ is a hash function that's “independent” from $\Pi$) is probably safe in practice, but I don't know how to formalize “doesn't appear”.

Answer 3

Your solution is almost there. Right now, the advantage of $\mathcal{B}$ is at least $$ \mathsf{Adv}^\Pi(\mathcal{B}) = \epsilon - \Pr[\mathsf{E}] $$ where $\epsilon = \mathsf{Adv}^{\Pi'}(\mathcal{A})$ and $\mathsf{E}$ is the event that $\mathcal{A}$ queries $H(sk)$. Of course, this lower bound isn't good enough, because $\mathsf{E}$ might somehow be very likely. Fortunately, $\mathcal{B}$ can actually benefit from $\mathsf{E}$ happening, and turn it into a win.

It does this with some polynomial loss. Let $\mathcal{B}$ log all of $\mathcal{A}$'s oracle queries. For each query $q$, let $\mathcal{B}$ attempt to decrypt the ciphertexts $c_0,c_1$ using $q$ as the secret key. If it gets back $m_b,m_{1-b}$, then $q$ might be the secret key. So $\mathcal{B}$ puts $b$ in its set of potential answers $S$. Finally, $\mathcal{A}$ returns its own guess $b'$, which $\mathcal{B}$ will also put in $S$. In the final step, $\mathcal{B}$ returns a uniformly selected element from $S$.

With this modification, if $\mathsf{E}$ happens, then $\mathcal{B}$ will win with probability at least $1/|S|$ (that is, the likelihood that $\mathcal{B}$ selects a $b$, times the likelihood that that $b$ came from the $\mathsf{E}$ event). Similarly, the likelihood that $\mathcal{B}$ chooses $b'$ and it's correct is at least $\epsilon/|S|$, independent of $\mathsf{E}$.

Thus, with the modification, by the law of total probability, \begin{align*} \Pr[\mathcal{B} \text{ wins}] &= \Pr[\mathsf{E}] \cdot \Pr[\mathcal{B} \text{ wins} \mid \mathsf{E}] + \Pr[\lnot\mathsf{E}] \cdot \Pr[\mathcal{B} \text{ wins} \mid \lnot\mathsf{E}] \\&\geq \Pr[\mathsf{E}] \cdot (1/|S|) + \Pr[\lnot\mathsf{E}] \cdot (\epsilon / |S|). \end{align*} So if $\Pr[\mathsf{E}]$ is noticeable, then $\mathcal{B}$ wins with noticeable probability by picking $sk$ (since $|S|$ is poly-sized). And if $\Pr[\lnot\mathsf{E}]$ is noticeable, then $\mathcal{B}$ wins with noticeable probability by outputting $b'$.

---

Update: This analysis is incomplete. It's not clear why the advantage of $\mathcal{B}$ is noticeable. Here's a failing example.

Consider the following $\mathcal{A}$. Say $\mathcal{A}$ makes two queries $q_0,q_1$ to $H$. In the case $b=1$ $\mathcal{A}$ will make $q_0$ decrypt the ciphertexts to $m_0,m_1$ and $q_1$ decrypt the ciphertexts to $m_1,m_0$. In the case $b=0$, then $\mathcal{A}$ will make both $q_0$ and $q_1$ decrypt the ciphertexts to $m_1,m_0$. Then \begin{align*} \Pr[\mathcal{B}(1) = 1] &= \frac{1 + 0 + \Pr[\mathcal{A}(1) = 1]}{3} \\\\ \Pr[\mathcal{B}(0) = 1] &= \frac{1 + 1 + \Pr[\mathcal{A}(0) = 1]}{3} \\\\ \mathsf{Adv}(\mathcal{B}) &= \left|\frac{\Pr[\mathcal{A}(1) = 1] - \Pr[\mathcal{A}(0) = 1] - 1}{3}\right| \\\\ &\geq |\mathsf{Adv}(\mathcal{A}) - 1/3| \end{align*} (the last ineq is reverse triangular inequality). This is not a lower bound we want, since it vanishes if $\mathcal{A}$'s advantage is $1/3$. The issue might have to do with the supposition that $\mathcal{A}$ can construct that many fake decryption keys, especially ones that decrypt to precisely the opposite thing. It's probably the case that the phrase "the private key" in the question is doing some heavy lifting.