Advanced KEM Concepts: (Hybrid) Obfuscation and Verifiable Decapsulation [CAW 2025]

Talk 5 at the Cryptographic Applications Workshop (CAW) 2025 affiliated with Eurocrypt 2025. Website: https://caw.cryptanalysis.fun/previous/2025.html Presenter: Felix Günther Slides: https://caw.cryptanalysis.fun/assets/pdf/2025/Advanced_KEM_Concepts_CAW_2025.pdf Talk abstract: Key encapsulation mechanisms (KEMs) allow two parties to establish a shared secret over a public network and are a cornerstone for making real-world crypto systems quantum-safe. Standardized schemes like ML-KEM however do not always satisfy the requirements of real-world protocols and securely implementing them can be brittle. This talk will discuss two advanced KEM concepts that address these issues. 1. (Hybrid) Obfuscation Some deployments require that KEM public keys or ciphertexts can be obfuscated to look like random bytestrings, e.g., via the widely-used Elligator encoding. These include protocols which hide metadata for user security and privacy (e.g., Tor's obfs4 pluggable transport) as well as password authenticated key exchange protocols (e.g., EKE). In this talk, we consider a replacement for Elligator in the post-quantum setting. We present Kemeleon: novel encodings that map ML-KEM public keys and ciphertexts to random bytestrings. Kemeleon is currently being considered for adoption by the CFRG. We further discuss how to combine traditional and post-quantum obfuscated KEMs. In contrast with hybrid key exchange where simple concatenation yields a secure solution, hybrid obfuscation is more subtle. We present a nested construction that allows provably-secure instantiations from deployed schemes. 2. Verifiable Decapsulation Cryptographic protocols often contain verification steps that are essential for security. Yet, faulty implementations missing these steps can easily go unnoticed, as the protocol might still function correctly. A prime example is Apple's goto fail; bug, erroneously skipping certificate verification. Similarly, an implementation flaw messing up the re-encryption check in FO-transformed KEMs (like ML-KEM) might be security-critical but could go undetected. This notably happened to HQC's reference implementation (and downstream users, such as liboqs), and was only noticed after 19 months. In this talk, we present an approach to make correct implementation of the re-encryption check in FO-based KEMs verifiable, with the aim to prevent such issues in the future. By including an unpredictable \"confirmation code\" from the encryption step into the key derivation, we ensure that re-encryption was indeed performed during decapsulation. We show how to apply this technique to ML-KEM and HQC with minimal overhead, and that it indeed catches the HQC bug through basic test cases.