Universally Anonymous IBE Based on the Quadratic Residuosity Assumption

Giuseppe Ateniese, Paolo Gasti

TL;DR

This paper introduces UAnonIBE, the first identity-based encryption (IBE) scheme that is both universally anonymous and relies on the standard quadratic residuosity assumption, offering efficiency comparable to existing non-anonymous schemes. This advancement is crucial for enhancing privacy in digital communications by allowing ciphertexts to be anonymized without revealing the sender's identity, while maintaining strong security guarantees.

What Problem Does This Paper Address?

Identity-Based Encryption (IBE) allows users to encrypt messages using a recipient's identity (like an email address) instead of a public key. While practical IBE schemes exist, many lack anonymity, meaning an observer can potentially link a ciphertext back to the intended recipient. This is a significant privacy concern, especially for sensitive communications. Existing anonymous IBE schemes often rely on complex mathematical structures (like pairings) or are computationally expensive. The paper addresses the challenge of creating an IBE scheme that is:

  1. Universally Anonymous: Not only can the recipient decrypt messages, but anyone can anonymize ciphertexts using just the recipient's public key. This is a stronger form of anonymity than simple key-privacy.
  2. Efficient: Comparable in performance to existing, non-anonymous IBE schemes.
  3. Based on Standard Assumptions: Its security relies on the well-understood quadratic residuosity assumption, avoiding the need for more complex cryptographic primitives.

The goal is to bridge the gap between security, efficiency, and strong privacy guarantees in IBE.

Methods

The core of the paper is an extension of Cocks' IBE scheme, which is known for its efficiency and reliance on the quadratic residuosity assumption but lacks anonymity. The authors introduce a novel "masking" mechanism to achieve universal anonymity.

  • Cocks' IBE Foundation: The scheme builds upon Cocks' IBE, which uses standard RSA groups and the quadratic residuosity assumption. Cocks' scheme encrypts messages bit-by-bit, making it potentially bandwidth-intensive but efficient for encrypting short session keys.
  • Universal Anonymity Mechanism: To achieve universal anonymity, the authors introduce a complex masking procedure. This involves generating random values and using a modified version of Galbraith's test (a test for anonymity in Cocks' scheme) to ensure that the resulting ciphertext is indistinguishable from a randomly chosen one, regardless of the original plaintext or recipient identity. This masking process is designed to be performed by anyone, not just the sender or a trusted authority.
  • Efficiency Enhancements: The paper proposes two efficient variants to reduce ciphertext expansion and improve performance. These variants leverage random oracles to expand short seeds into necessary random values, balancing ciphertext size with computational cost.
  • Security Proofs: The security of the proposed scheme (UAnonIBE) is proven in the random oracle model, demonstrating its IND-ID-CPA (Indistinguishability under Chosen Plaintext Attack with Identity) and ANON-RE-CPA (Anonymity under Random Encryption Chosen Plaintext Attack) security. These proofs rely on the standard quadratic residuosity assumption.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and security proofs, with performance evaluations conducted on simulated cryptographic operations rather than specific datasets.

Key Insights and Ideas

  • Bridging Anonymity and Efficiency: The most significant insight is demonstrating that universal anonymity in IBE can be achieved without sacrificing efficiency or relying on complex cryptographic primitives like pairings, which was a major hurdle in prior work.
  • Leveraging Existing Weaknesses for Strength: The paper cleverly uses and extends Galbraith's test, originally identified as a weakness in Cocks' scheme (compromising anonymity), as a building block for their anonymity mechanism.
  • The Power of Masking: The introduction of a sophisticated masking technique allows for the transformation of an already secure but non-anonymous scheme into a universally anonymous one, highlighting the flexibility of cryptographic design.
  • Trade-offs in Practical Cryptography: The exploration of efficient variants underscores the importance of balancing security guarantees with practical considerations like ciphertext expansion and encryption/decryption speed, especially for real-world applications.

Key Results

  • UAnonIBE: The paper presents UAnonIBE, the first universally anonymous IBE scheme based on the quadratic residuosity assumption.
  • Efficiency: The scheme's efficiency and ciphertext expansion are comparable to Cocks' original (non-anonymous) IBE scheme.
  • Security: UAnonIBE is proven to be ANON-IND-ID-CPA-secure in the random oracle model under the quadratic residuosity assumption.
  • Performance: Experimental results show that the proposed efficient variants are practical and compare favorably to existing schemes, including those based on pairings, while offering the advantage of a standard security assumption. For instance, the optimized variant offers a ciphertext expansion close to Cocks' scheme.

Limitations and Future Work

  • Random Oracle Model: The security proofs are established in the random oracle model. While this is a common and accepted model for proving security of many cryptographic schemes, it's an idealized model. Real-world implementations would need to use concrete hash functions, which might introduce some security loss.
  • Ciphertext Expansion: While the paper presents efficient variants to reduce ciphertext expansion, it still has some overhead compared to the most basic non-anonymous schemes. The authors explore trade-offs to mitigate this.
  • Future Work: The paper suggests that their techniques could be used to simplify existing PEKS (Public Key Encryption with Keyword Search) constructions. They also implicitly point towards further research in optimizing the balance between anonymity, efficiency, and security assumptions in IBE and related cryptographic primitives. The authors also mention that their techniques could be used to simplify the PEKS construction in [15].

Summary updated

BibTeX
@article{ateniese2009universally,
  author = {Giuseppe Ateniese and Paolo Gasti},
  title = {{Universally Anonymous IBE Based on the Quadratic Residuosity Assumption}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2009},
  doi = {10.1007/978-3-642-00862-7\_3},
}
Figure