Paper 2026/1028

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

Rupeng Yang, University of Wollongong

Man Ho Au, The Hong Kong Polytechnic University

Zuoxia Yu, University of Wollongong

Willy Susilo, University of Wollongong

Abstract

Anamorphic encryption introduced by Persiano et al. (Eurocrypt'22) enables covert communication through innocent-looking ciphertexts, even under strong censorship where a dictator has the power to compel citizens to surrender their private decryption keys. In this work, we study the asymmetric form of anamorphic encryption proposed by Catalano et al. (Eurocrypt'24), where the covert channel operates in a manner analogous to PKE. However, the commonly considered notion, fully asymmetric anamorphic encryption, fails to address collusion, where the dictator can corrupt a sender to additionally obtain the sender double key for encrypting covert messages. In this work, we resolve this gap by developing the first general framework for collusion-resistant asymmetric anamorphic encryptions. Our approach introduces a new cryptographic abstraction, witness PRF for PKE, which precisely captures the structure needed to embed secure covert channels under collusion. This abstraction allows us to reduce the construction of asymmetric anamorphic encryption schemes to a single primitive, providing a unified and conceptually clean methodology. Building on this framework, we obtain a generic construction of asymmetric anamorphic encryption for any PKE scheme with high min-entropy ciphertexts. In contrast to prior generic approaches proposed by Catalano et al. (Eurocrypt'25) which rely on indistinguishability obfuscation, our construction achieves stronger security in the collusion setting under assumptions believed to be weaker, thereby improving both theoretical foundations and feasibility. Beyond generic viability, we give direct and practical instantiations of our framework for widely deployed schemes, including ElGamal, Regev, and Paillier, without relying on heavy cryptographic mechanisms. These results demonstrate that the collusion-resistant asymmetric anamorphism is not only achievable in general, but also practical in standard encryption systems. Taken together, this paper establishes the first complete treatment of asymmetric anamorphic encryption under collusion, providing a principled pathway for constructing covert communication mechanisms with rigorous and realistic security guarantees.

@misc{cryptoeprint:2026/1028,
      author = {Zhikang Xie and Rupeng Yang and Man Ho Au and Zuoxia Yu and Willy Susilo},
      title = {Collusion-Resistant Asymmetric Anamorphic Encryption: Framework, Generic Construction, and Concrete Instantiations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1028},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1028}
}