International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Kemeleon: Elligator-like Obfuscation for Post-Quantum Cryptography

Authors:
Felix Günther
Michael Rosenberg
Douglas Stebila
Shannon Veitch
Download:
Search ePrint
Search Google
Presentation: Slides
Abstract: Elligator is widely used to encode elliptic-curve public keys in protocols that require random-looking bytestrings. These include password authenticated key exchange protocols (e.g., EKE) as well as protocols which attempt to avoid fingerprinting (e.g., Tor's obfs4 pluggable transport). We consider a replacement for Elligator in the post-quantum setting. We present Kemeleon: novel encodings for ML-KEM public keys and ciphertexts into bytestrings which are computationally indistinguishable from random. Kemeleon includes variants that allow for optimized implementations or deterministic encodings. We then consider how to combine traditional and post-quantum obfuscated key encapsulation mechanisms (KEMs). In contrast with hybrid key exchange where simple concatenation yields a secure solution, hybrid obfuscation is more subtle, and can require a nested construction when computational assumptions are involved. From Kemeleon and hybrid obfuscated KEMs, we show how to construct obfuscated key exchange as well as the first known hybrid password authenticated key exchange protocol which is secure in the adaptive-corruptions model.
Video: https://youtu.be/CvFCYUq5rGg
BibTeX
@misc{rwc-2025-35869,
  title={Kemeleon: Elligator-like Obfuscation for Post-Quantum Cryptography},
  note={Video at \url{https://youtu.be/CvFCYUq5rGg}},
  howpublished={Talk given at RWC 2025},
  author={Felix Günther and Michael Rosenberg and Douglas Stebila and Shannon Veitch},
  year=2025
}