Identity-Based Encryption for Fair Anonymity Applications: Defining, Implementing, and Applying Rerandomizable RCCA-Secure IBE

Yi Wang, Rongmao Chen, Xinyi Huang, Jianting Ning, Baosheng Wang, Moti Yung

TL;DR

This paper introduces a new security notion, ANON-ID-RCCA, for identity-based encryption (IBE) that balances recipient anonymity with the ability for authorities to revoke it when necessary. They present the first IBE construction that achieves this new security standard, along with universal rerandomizability, and demonstrate its utility by building an identity-based universal mixnet.

What Problem Does This Paper Address?

In many applications, we want to encrypt messages anonymously, meaning the recipient's identity is hidden. However, in some scenarios, a trusted authority needs to be able to reveal the recipient's identity if required (e.g., for abuse prevention). This is known as "fair anonymity." Identity-Based Encryption (IBE) is a natural fit for this, as it inherently involves a trusted authority for key generation.

The challenge arises when trying to combine fair anonymity with two crucial properties:

  1. Rerandomizability: The ability to transform a ciphertext into another one that decrypts to the same message but looks statistically different. This is vital for anonymity in systems like mixnets, where it helps break the link between incoming and outgoing messages.
  2. Active Adversary Security: Protection against sophisticated attackers who can actively manipulate ciphertexts. The standard security notion for IBE, IND-ID-CCA, is too strong and incompatible with rerandomizability.

Existing solutions for rerandomizable encryption often relax security to RCCA (Replayable Chosen-Ciphertext Attack), but adapting this to IBE while maintaining fair anonymity and rerandomizability has been an open problem.

Methods

The authors tackle this by:

  • Formalizing a New Security Notion (ANON-ID-RCCA): They define a new security game for IBE that is a relaxation of IND-ID-CCA. This new notion allows adversaries to "maul" ciphertexts (rerandomize them) and ensures recipient anonymity, while still allowing for fair anonymity (via the underlying IBE structure).
  • Constructing a Novel IBE Scheme: They propose the first IBE scheme that satisfies this new ANON-ID-RCCA security and is universally rerandomizable. This construction is based on extending the "double-strand paradigm" (used in prior work for PKE) to the Gentry-IBE construction. This extension is non-trivial and requires careful adjustments to maintain security.
  • Proving Security and Rerandomizability: They provide rigorous security proofs for their construction, demonstrating that it meets the ANON-ID-RCCA security definition and is rerandomizable.
  • Building an Application: They showcase the practical relevance of their work by constructing an identity-based universal mixnet. This mixnet leverages their new IBE scheme to provide strong unlinkability and fair anonymity without requiring public key distribution infrastructure.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The Trade-off Between Anonymity and Accountability: The paper highlights that achieving both strong anonymity and the ability to revoke it (fair anonymity) requires a careful balance, leading to the need for relaxed security notions like ANON-ID-RCCA.
  • Rerandomizability is Key for Anonymity in Mixnets: The work emphasizes that rerandomizability is not just a theoretical curiosity but a practical necessity for building robust anonymous communication systems like mixnets.
  • Adapting PKE Techniques to IBE is Non-Trivial: The paper demonstrates that directly applying techniques from public-key encryption (PKE) to the identity-based setting requires significant modifications and new insights, especially when dealing with properties like rerandomizability and specific security notions.
  • A Unified Framework for Fair Anonymity: The proposed ANON-ID-RCCA security notion and the corresponding IBE scheme offer a promising foundation for building various applications that require both privacy and accountability.

Key Results

  • Formalization of ANON-ID-RCCA: A new security definition for rerandomizable IBE that balances recipient anonymity with fair anonymity.
  • First ANON-ID-RCCA Secure and Universally Rerandomizable IBE: The paper presents the first construction that achieves both these properties.
  • Identity-Based Universal Mixnet: A practical application demonstrating the utility of their IBE scheme, providing strong unlinkability and fair anonymity.
  • Rigorous Security Proofs: The proposed IBE scheme is proven secure under the truncated decision q-ABDHE assumption.

Limitations and Future Work

  • Ciphertext Size: The authors acknowledge that the ciphertext size of their proposed IBE scheme is four times larger than the Gentry-IBE, which is a significant drawback. Reducing this size is identified as a top priority for future work.
  • Perfect Rerandomizability: The current scheme achieves computational rerandomizability. Achieving perfect rerandomizability (where the rerandomized ciphertext is indistinguishable from a fresh encryption) is suggested as an interesting future direction.
  • Optimizing Fair Anonymity Mechanisms: The paper mentions that the aspect of how authorities reveal receivers is assumed but not optimized, leaving room for future work.
  • Broader Applicability: The authors suggest their new notion can be applied to other rerandomizable RCCA-secure applications to eliminate public key infrastructure needs.

Summary updated

Abstract

Our context is anonymous encryption schemes hiding their receiver, but in a setting which allows authorities to reveal the receiver when needed. While anonymous Identity-Based Encryption (IBE) is a natural candidate for such fair anonymity (it gives trusted authority access by design), the de facto security standard (a.k.a. IND-ID-CCA) is incompatible with the ciphertext rerandomizability which is crucial to anonymous communication. Thus, we seek to extend IND-ID-CCA security for IBE to a notion that can be meaningfully relaxed for rerandomizability while it still protects against active adversaries. To the end, inspired by the notion of replayable adaptive chosen-ciphertext attack (RCCA) security (Canetti et al., Crypto'03), we formalize a new security notion called Anonymous Identity-Based RCCA (ANON-ID-RCCA) security for rerandomizable IBE and propose the first construction with rigorous security analysis. The core of our scheme is a novel extension of the double-strand paradigm, which was originally proposed by Golle et al. (CT-RSA'04) and later extended by Prabhakaran and Rosulek (Crypto'07), to the well-known Gentry-IBE (Eurocrypt'06). Notably, our scheme is the first IBE that simultaneously satisfies adaptive security, rerandomizability, and recipient-anonymity to date. As the application of our new notion, we design a new universal mixnet in the identity-based setting that does not require public key distribution (with fair anonymity). More generally, our new notion is also applicable to most existing rerandomizable RCCA-secure applications to eliminate the need for public key distribution infrastructure while allowing fairness.
BibTeX
@article{wang2021identity,
  author = {Yi Wang and Rongmao Chen and Xinyi Huang and Jianting Ning and Baosheng Wang and Moti Yung},
  title = {{Identity-Based Encryption for Fair Anonymity Applications: Defining, Implementing, and Applying Rerandomizable RCCA-Secure IBE}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2021},
  doi = {10.1007/978-3-030-92075-3\_15},
}
Figure