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

• It would be easy to achieve this with IES; just make the symmetric encryption part be a AEAD method. Mar 3 '16 at 18:42
• @poncho, nice! Can you do something similar for any KEM-based method? (basically, any use of hybrid crypto, where the public-key part is used to exchange a symmetric key, and then the symmetric key is used to encrypt the message) Does that work in general?
– D.W.
Mar 3 '16 at 18:47
• I don't see why it wouldn't work. I would expect any KEM method works by generating a symmetric key, and the symmetric key is used to encrypt the message. I can't see any reason why we couldn't insert an AEAD method to do the actual encryption. Mar 3 '16 at 18:50
• I use RSA to encrypt blocks of plaintext in the way of block cipher with PCBC block-chaining. There is an IV that is pseudo-randomly generated with a session key and there is also an integrity check. IMHO that IV meets your requirement of h. In case that's indeed true, please look at Example 3 in the Appendix of s13.zetaboards.com/Crypto/topic/7234475/1/ (Please kindly tell, should I have misunderstood your post.) Mar 3 '16 at 19:30
• @SEJPM, poncho, this is great stuff. Turn it into an answer? (For many public-key schemes, this is a clean solution that avoids any message expansion. For some other schemes, it's suboptimal -- for instance, RSA-KEM+AES-GCM will have more message expansion than RSA-OAEP, so I suspect that something better should be possible. But this does provide an answer to my question by showing some examples, so if it sounds good to you, I'll post a separate follow-up asking about RSA.)
– D.W.
Mar 3 '16 at 22:26