Kemeleon: Elligator-like Obfuscation for ML-KEM

In this talk, we will present Kemeleon: new encodings that map ML-KEM public keys and ciphertexts to
random bytestrings. In addition, since many post-quantum protocol migrations deploy hybrids of classical
and post-quantum algorithms, we consider the question of hybrid obfuscation. Unlike the Elligator encoding
for ECDH, our Kemeleon encodings for ML-KEM are not statistically indistinguishable from random
bytestrings: they depend on the decision module-LWE assumption. As a result, subtleties emerge in the
security properties of hybrid obfuscation, in contrast with the basic key indistinguishability goal for hybrid
key exchange where simple concatenation does yield a secure solution. We present an efficient obfuscated key
encapsulation mechanism (KEM) combiner which operates sequentially, encrypting one KEM’s ciphertext
under a key derived from the other KEM’s shared secret. We discuss some applications of hybrid obfuscated
KEMs, including how to hybridize deployed obfuscated key exchange protocols such as Tor’s obfs4 protocol
and uses in hybrid password authenticated key exchange protocols.