Paper 2025/370

Simple Asymmetric Anamorphic Encryption and Signature using Multi-Message Extensions

Abstract

Anamorphic encryption enables covert communication over public cryptographic channels while preserving the apparent correctness and security of the underlying cryptographic scheme, even against adversaries with access to secret keys. Classical formulations of anamorphic encryption emphasize zero-latency channels, where an anamorphic message is embedded within a single ciphertext; however, recent works show that achieving such guarantees typically requires highly structured constructions or strong, non-black-box assumptions. In this work, we explore a complementary point in the design space by relaxing strict zero-latency and introducing µ-message asymmetric anamorphic encryption (AAE), where a single anamorphic payload is distributed across a small number µ of ordinary cryptographic objects. Our first contribution is a general abstraction of µ-message AAE, which captures the ability of a cryptographic primitive to jointly encode hidden information across multiple independently generated objects, while remaining indistinguishable from honestly generated ones. We formalize corresponding security notions, including indistinguishability, and resistance to key exposure, and show how these notions naturally support asymmetric anamorphic settings where the encryption-side anamorphic key may be leaked without compromising the covert channel. Our second contribution is to demonstrate that relaxing strict zero-latency enables simple, black-box, and CCA-secure constructions of AAE from widely deployed cryptographic primitives, avoiding the need for specialized algebraic structure. In particular, we show how µ-message extensions can be instantiated in several representative and practically relevant settings: – We construct µ-message AAEs from standard PKE schemes, including ElGamal and Dual-Regev, without relying on additional group- or lattice- specific sampling algorithms and achieve strong security even against adversaries with full access to secret keys. – We show that µ-message extensions compose naturally with Fujisaki–Okamoto–style transforms, yielding the first generic approach to CCA-secure AAEs from a broad class of CPA-secure schemes satisfying mild pseudorandomness properties. – We extend the µ-message framework to the identity-based encryption (IBE) and signature settings by introducing IBAE and asymmetric anamorphic signatures (AAS), illustrating that asymmetric anamorphism can be realized even in centralized, authority-driven systems and in authentication-only settings. Finally, we introduce stream anamorphism notifiers, lightweight mechanisms that allow a receiver to efficiently locate and extract anamorphic content from a stream of cryptographic objects. Overall, our results highlight a clear trade-off between latency, deployability, and security, and show that relaxing zero-latency yields a practically relevant and theoretically clean pathway to strong anamorphic guarantees.

Note: We added security proofs against stronger adversaries for PKAE and IBAE. We introduced stream anamorphism notifiers to efficiently locate and extract anamorphic content from a stream of cryptographic objects.