Sender-Anamorphic Encryption Reformulated: Achieving Robust and Generic Constructions

Yi Wang, Rongmao Chen, Xinyi Huang, Moti Yung

Sure, here's a blog-style summary of the paper:

TL;DR

This paper introduces "l-sender-anamorphic encryption" (l-sender-AME), a new cryptographic primitive that allows senders to embed hidden messages within ciphertexts, even when a malicious "dictator" might be monitoring communications. The authors provide generic constructions for this primitive and demonstrate its robustness and security, showing it can be used to build secure communication systems in challenging adversarial environments.

What Problem Does This Paper Address?

In secure communication, we usually assume that receivers keep their secret keys private (receiver privacy) and that senders can freely choose what messages to send (sender freedom). However, in some scenarios, a powerful entity, dubbed "the dictator," can violate these assumptions by accessing secret keys or censoring messages.

Anamorphic Encryption (AME) was introduced to address this. It allows for secure communication even when these assumptions are compromised. The paper focuses on sender-anamorphic encryption, which aims to preserve sender freedom. The original sender-AME had a limitation: it couldn't guarantee that messages would be reliably delivered or that an "abort" signal would be generated if something went wrong. This paper reformulates sender-AME to overcome these issues, introducing the concept of "l-sender-AME" and formalizing properties like robustness.

Methods

The authors propose a reformulated model for sender-anamorphic encryption, called l-sender-AME. The key innovations include:

  • Encoding across multiple ciphertexts: Instead of embedding a duplicate message into a single ciphertext, l-sender-AME allows this to be spread across l ciphertexts. This is crucial for robustness.
  • Robustness Definition: They define robustness to ensure that:
  • Decrypting normal ciphertexts in an anamorphic way results in an explicit abort signal.
  • Decrypting anamorphic ciphertexts with an incorrect duplicate secret key also results in an explicit abort signal.
  • Generic Constructions: They provide two general constructions for l-sender-AME:
  • Pseudo-random and Robust PKE: This construction leverages the properties of pseudo-random public-key encryption (PKE) and robustness to embed duplicate messages bit-by-bit.
  • Hybrid PKE with Special KEM: This construction builds upon hybrid PKE schemes (which combine Key Encapsulation Mechanisms (KEMs) and Data Encapsulation Mechanisms (DEMs)) and is instantiated with well-known schemes like ElGamal and Cramer-Shoup.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Robustness is Key: The paper highlights that simply achieving sender-anamorphic encryption isn't enough; it needs to be robust. This means explicitly signaling errors (like incorrect keys or non-anamorphic ciphertexts) to prevent misinterpretations.
  • l-Sender-AME as a Powerful Primitive: The authors show that a strongly secure l-sender-AME is a versatile primitive that implies other related concepts like receiver-anamorphic encryption, public-key stegosystems, and generalized algorithm-substitution attacks (ASA) on PKE.
  • Bridging Concepts: The work establishes novel connections between anamorphic encryption, public-key stegosystem, and algorithm-substitution attacks, showing how these seemingly disparate areas are interconnected.
  • Practicality through Genericity: By providing generic constructions, the paper shows that l-sender-AME can be realized using existing PKE schemes, making it potentially applicable in real-world scenarios.

Key Results

  • Formalization of l-Sender-AME: The paper formally defines l-sender-AME and its properties of strong security and robustness.
  • Two Generic Constructions: They present two constructions for secure and robust l-sender-AME: one based on pseudo-random PKE and another for hybrid PKE.
  • Implications for Related Primitives: The paper proves that strongly secure l-sender-AME implies:
  • Secure l-receiver-AME.
  • Secure public-key stegosystems.
  • Asymmetric generalized ASA on PKE.

Limitations and Future Work

  • Efficiency: While the constructions are generic, their practical efficiency (e.g., ciphertext size, computational overhead) is not the primary focus and might be a subject for future optimization.
  • Specific Instantiations: The paper focuses on generic constructions. Further research could explore specific, highly efficient instantiations of l-sender-AME with concrete PKE and KEM schemes.
  • Stronger Security Notions: The paper mentions that proving strongly secure l-sender-AME has challenges, particularly in relating it to other primitives. Future work could delve deeper into these connections.
  • Practical Deployment: The paper lays the theoretical groundwork. Real-world deployment would require careful consideration of implementation details and performance.

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},
}

Loading related content...

Figure