Paper 2026/1028

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

Abstract

(Receiver) 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 addition, we work with the notion of anamorphic extension proposed by Banfi et al. (Eurocrypt'24), where covert communication can be enabled directly from (already deployed) public keys. Via deniability, this formulation provides stronger security guarantees that are not captured by existing models for the collusion setting. Motivated by these observations, we develop the first general framework for collusion-resistant asymmetric anamorphic extensions. At the heart of our approach is a new cryptographic abstraction, witness PRF for PKE, which can be used to realize secure covert channels under our framework. This reduces the construction of asymmetric anamorphic encryption schemes to the realization of a single primitive, thereby providing a unified and conceptually clean methodology. Theoretically, we further show that any asymmetric anamorphic extension for a PKE scheme gives rise to a witness PRF for this PKE, indicating that our cryptographic abstraction is precise and well suited to the task. 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 collusion-resistant asymmetric anamorphism is not only achievable in general, but also practical in standard encryption systems.

Note: 1. Added a result in the opposite direction, showing that any asymmetric anamorphic extension for a PKE scheme gives rise to a witness PRF for this PKE. 2. Updated the names of some security models following the revision of Paper 2025/309.