In the symmetric-key world, we have authenticated encryption with associated data (AEAD). I'm looking for something similar, but for public-key encryption: public-key encryption with associated data (PKEAD?).
Here's how it should work. Given a message $m$ and a header $h$, let $E(m,h)$ denote the public-key encryption of $m$, bound to the data $h$. Similarly, given a ciphertext $c$, let $D(c,h)$ denote decryption of $c$ under the corresponding private key, bound to $h$. We want $D(E(m,h_0),h_1)$ to be $m$ if $h_0=h_1$, or $\bot$ (failure) if $h_0 \ne h_1$. There is no requirement to provide confidentiality for $h$ (we assume it is public) and no need to include $h$ in the ciphertext (he assumption is that the header $h$ will be transmitted via some out-of-band means). This binds the ciphertext $E(m,h)$ to $h$, so that decryption will succeed only if the sender and receiver have the same value of $h$ and the adversary hasn't tampered with $h$ in transit.
Also, I want the public-key encryption to be IND-CCA2 secure.
Are there any schemes designed for this task?
I can think of some trivial constructions, but I suspect they are not optimal. One simple scheme is to let $E(m,h)$ be the public-key encryption of $m||H(h)$ under some standard public-key encryption scheme. Then $D(c,h)$ decrypts $c$ to get some $m||d$, and returns $m$ if $H(h)=d$ or fails otherwise. However, this causes message expansion (alternatively, it reduces the maximum length of the message $m$ that can be encrypted). I suspect one can avoid any message expansion. Has anyone designed schemes for this task?