Public-key encryption with associated data 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?
There are no schemes that I'm aware of that are specifically designed for this task, i.e. where this was advertised as feature in a description I've come across.

The most standard solution I can provide is McBits (PDF). McBits is based on XSalsa20-Poly1305 and thereby can natively supports the associated data interface if enabled by the implementation. However (good) implementations of McBits are rare, although they shouldn't be too hard given a (standard) McEliece implementation.

What you can also do, is take your generic (IND-CCA2 secure) public key encryption scheme (e.g. RSA-OAEP), encrypt a symmetric key with it and use that key for the AEAD scheme of your choice (e.g. AES-GCM) to encrypt and authenticate bulk data and to authenticate header data.

The more distinguished solution is to just take the KEM of your choice (like the one used by ECIES, DHIES or RSA-KEM), use that to derive the key and then continue normally with your AEAD scheme of choice (e.g. AES-GCM). McBits basically is this with the KEM being standard McEliece encryption of a random vector.