Sender-Anamorphic Encryption Reformulated: Achieving Robust and Generic Constructions

Yi Wang, Rongmao Chen, Xinyi Huang, Moti Yung

Introduction

In a world where digital surveillance is ubiquitous, the ability to communicate securely is often under threat. Imagine a "dictator" scenario: a regime mandates the use of specific encryption software and demands copies of all secret keys. In such an environment, standard end-to-end encryption is insufficient because the monitor can decrypt every message.

Anamorphic Encryption (AME), presented at ASIACRYPT 2023, offers a solution. It allows a sender to hide a "duplicate" (secret) message inside a "forced" (normal-looking) ciphertext. While the dictator sees a benign message, the intended secret recipient can extract a hidden one.

The Challenge: Achieving Robustness

Previous iterations of sender-AME—where no pre-shared secret exists between the sender and the hidden recipient—suffered from a lack of "robustness." In these systems, if a recipient tried to decrypt a normal message as a secret one, or used the wrong key, the output was indistinguishable from random noise. This made reliable communication difficult, as the receiver had no way of knowing if a secret message was actually present.

The authors address this by introducing $\ell$-sender-AME. In this model, a secret message is spread across a sequence of $\ell$ ciphertexts. They define robustness as the system's ability to output an explicit "abort" signal if the ciphertexts are standard or if the decryption key is incorrect.

Proposed Constructions

The paper details two primary methods for achieving robust $\ell$-sender-AME:

  1. Pseudo-random and Robust PKE: This method employs "rejection sampling." To embed a secret bit, the sender repeatedly generates randomness for a standard encryption until the resulting ciphertext's hash matches the desired bit. While effective, this is computationally intensive.
  2. Hybrid PKE with Special KEM: This more generic approach utilizes the homomorphic properties of Key Encapsulation Mechanisms (KEMs). By subtly perturbing the randomness in a hybrid encryption scheme (like ElGamal), the sender embeds secret bits detectable only by the holder of a specific "duplicate" key.

A Unified Theoretical Framework

One of the paper's most significant contributions is the theoretical unification of several covert communication primitives. The authors demonstrate that a strongly secure $\ell$-sender-AME acts as a "master primitive," implying the existence of receiver-AME, public-key steganography, and generalized Algorithm-Substitution Attacks (ASA).

Relationships between $\ell$-sender-AME and other cryptographic primitives.

As shown in the diagram above, the paper establishes formal reductions (Theorems 9-12) between these concepts, which were previously studied in relative isolation. This hierarchy clarifies how different methods of covert communication relate to one another.

Key Results and Impact

The research provides the first formal definitions for security and robustness in the sender-AME setting without shared secrets. Crucially, the authors prove that widely-used cryptosystems, such as ElGamal and Cramer-Shoup, can be adapted into robust $\ell$-sender-AME schemes. This turns common encryption standards into potential channels for covert communication.

Limitations and Future Outlook

While groundbreaking, the current constructions face efficiency challenges. Rejection sampling is slow, and spreading messages across $\ell$ ciphertexts results in significant message expansion. Future work will likely focus on more efficient encoding techniques that allow for higher data rates within the hidden channel without compromising the "deniability" essential for evading detection.

Summary updated

BibTeX
@inproceedings{wang2023sender,
  author = {Yi Wang and Rongmao Chen and Xinyi Huang and Moti Yung},
  title = {{Sender-Anamorphic Encryption Reformulated: Achieving Robust and Generic Constructions}},
  booktitle = {ASIACRYPT},
  year = {2023},
  doi = {10.1007/978-981-99-8736-8\_5},
}
Figure