1
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ It would be easy to achieve this with IES; just make the symmetric encryption part be a AEAD method. $\endgroup$
    – poncho
    Mar 3, 2016 at 18:42
  • $\begingroup$ @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? $\endgroup$
    – D.W.
    Mar 3, 2016 at 18:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – poncho
    Mar 3, 2016 at 18:50
  • $\begingroup$ 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.) $\endgroup$
    – Mok-Kong Shen
    Mar 3, 2016 at 19:30
  • 1
    $\begingroup$ @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.) $\endgroup$
    – D.W.
    Mar 3, 2016 at 22:26

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.