Do all AEAD implementations use symmetric key ciphers in practice?

Question

Everything I've seen so far in modern implementations (the Linux Kernel AEAD API, JVM crypto provider (AES-GCM), RFC 8439, libsodium, etc) seems to imply that only symmetric key block ciphers are used in practice for AEAD. Are there asymmetric key algorithms that ensure authenticated encryption?

Answer 1

When people say "AEAD", they have symmetric schemes in mind. But conceptually, authenticated encryption is not restricted to symmetric keys. It is just the case that public key variants have not received much attention both in the literature and in practice. But there are implementations. For example, NaCl has an API for public-key authenticated encryption, based on security notions by Jee Hea An 2001. The construction is based on public-key encryption and MACs. This shows that AE in the asymmetric setting is fundamentally different from simply signing encrypted messages, as explained in the NaCL API docs:

The crypto_box function is not meant to provide non-repudiation. On the contrary: the crypto_box function guarantees repudiability. A receiver can freely modify a boxed message, and therefore cannot convince third parties that this particular message came from the sender. The sender and receiver are nevertheless protected against forgeries by other parties. In the terminology of https://groups.google.com/group/sci.crypt/msg/ec5c18b23b11d82c, crypto_box uses "public-key authenticators" rather than "public-key signatures."

Users who want public verifiability (or receiver-assisted public verifiability) should instead use signatures (or signcryption).

Apparently this API and the formalization in the paper do not include the "additional data" (AD) part of AEAD but I don't think there is a fundamental limitation. AEAD as a single primitive in the symmetric setting became popular only after 2001, so I believe Jee Hea An simply didn't think about "additional data" as a useful feature back in 2001.

I can only speculate but I believe one reason why authenticated public-key encryption has not received much attention is that (even unauthenticated) public-key encryption itself is a rarely used primitive. Public-key encryption is useful in a setting where the sender and the receiver are not online at the same time. The prominent example is e-mail encryption but unfortunately e-mail encryption never took off for various reasons (Johnny Still, Still Can't Encrypt), and protocols for e-mail security such as PGP/GPG and S/MIME conceptually separate confidentiality and authentication and implement them via public-key encryption and digital signatures (and not MACs!). Of course these can be combined ("sign-then-encrypt", "encrypt-then-sign" or "encrypt-and-sign") but the responsibility for doing so correctly is mostly pushed down to the user, and the 2001 paper shows that all of these constructions are insufficient. (One reason why PGP and S/MIME wanted signatures explicitly is that you can still have authentication for public emails, e.g., posts to public mailing lists.)

The success of the idea that we should consider authenticated encryption as single primitive with a single misuse-resistant API whose users do no need to be cryptography experts came only later in the symmetric setting after people screwed up in endless ways with constructions like "encrypt-then-MAC", "MAC-then-encrypt", "encrypt-and-MAC", which are the symmetric counterparts to the modes mentioned above. Note however that the symmetric and asymmetric settings are hard to compare when it comes to authentication, e.g., due to the mentioned subtleties with repudiability and public verifiability. MACs and signatures are very different beasts.

Answer 2

AEADs are symmetric BY DEFINITION. What's more they are the base point from which we can argue the security of protocol designs.

Asymmetric authenticated encryptions schemes are known as signcrypt schemes, and PGP is probably the best-known example.

Answer 3

Do all AEAD implementations use symmetric key ciphers in practice?

Yes, but that's more by definition than because of unwillingness it seems.

Please note that you do require two key pairs, one for encryption and one for signing to achieve the confidentiality and message integrity / authenticity that an AEAD scheme offers. That means that any AEAD scheme for asymmetric ciphers needs to be significantly more complex than for the symmetric sense (the paper pointed to by real-or-random shows this complexity as well). Then there is the issue of trusting the public keys which may require an entire PKI. Therefore I think things like asymmetric encryption & signature generation are handled at the protocol level.

For symmetric ciphers it made sense to specify AEAD ciphers as some kind of secure drop: use this and you get authenticity for free, using a single key (mostly). Moreover, with an AEAD cipher such as GCM or one that uses Poly1305 you get a nice speedup compared to HMAC as well. That's a rather different proposition than what is required to perform authenticated encryption using asymmetric primitives.