Paper 2026/1028

Collusion-Resistant Asymmetric Anamorphic Encryption: Framework, Generic Construction, and Concrete Instantiations

Abstract

(Receiver) anamorphic encryption enables covert communication through innocent-looking ciphertexts, even against a dictator that compels users to surrender their private decryption keys. In this work, we study the asymmetric form, where the covert channel operates in a manner analogous to PKE. However, a generic construction achieving collusion-resistance (where the dictator can corrupt a sender to additionally obtain the sender double key) under only mild restrictions on the underlying PKE remains lacking. To address the problem, we develop a general framework for constructing collusion-resistant asymmetric anamorphic encryptions from a new cryptographic abstraction called witness PRF for PKE. The framework works in the anamorphic extension setting, which enables covert communication from (already deployed) public keys. Importantly, our security model addresses the shortcomings of prior collusion models. The first instantiation of our framework yields a generic asymmetric anamorphic extension for any PKE scheme with high min-entropy ciphertexts. In contrast to prior generic constructions of fully asymmetric anamorphic encryption, which rely on indistinguishability obfuscation and do not consider collusion, our construction achieves collusion-resistance under assumptions believed to be weaker. We also give practical instantiations for widely deployed PKE schemes, including ElGamal, Regev, Linear, and CSIDH-based encryptions, without relying on heavy cryptographic mechanisms. Notably, some of these extend the range of PKE schemes known to admit practical asymmetric anamorphism.

Note: Added constructions from Linear encryption and CSIDH-based encryption, and removed the construction from Paillier encryption (replacing it with a brief discussion).