Identity-Set-based Broadcast Encryption supporting "Cut-or-Select" with Short Ciphertext

Yan Zhu, Xin Wang, Di Ma, Ruiqi Guo

TL;DR

This paper introduces a novel broadcast encryption (BE) scheme that efficiently supports both including and excluding specific users from receiving encrypted messages simultaneously. It achieves this with remarkably short ciphertexts and decryption keys, regardless of the size of the user set, by cleverly using cryptographic set membership functions.

What Problem Does This Paper Address?

Traditional broadcast encryption systems typically fall into two categories: those that encrypt for a specific subset of users (inclusion) and those that encrypt for all users except a revoked subset (exclusion). While both are crucial for large-scale systems (like email or content delivery), existing schemes often handle these separately. This paper addresses the challenge of creating a unified, efficient BE system that seamlessly supports both inclusion and exclusion modes simultaneously, especially for systems with a vast number of users. The core difficulty lies in securely and efficiently representing and querying set membership in a way that scales well and keeps ciphertexts small.

Methods

The paper's core innovation lies in its approach to "cryptographic set membership" using two novel aggregation functions: Zeros-based aggregation and Poles-based aggregation. These functions take a subset of user identities and compress their information into a single, constant-size element within a bilinear map group. This compressed representation allows for efficient checking of whether a user is in a designated set (inclusion) or not in a revoked set (exclusion).

The scheme is built upon the idea of representing user identities as points in a cryptographic space. A subset is then represented by a curve passing through the points of its members. The aggregation function computes a specific point on this curve, which acts as the cryptographic representation of the subset. This allows the broadcaster to encrypt messages in a way that can be decrypted by users whose identities satisfy the specified inclusion or exclusion criteria. The scheme also leverages the General Diffie-Hellman Exponent (GDHE) assumption for its security proof.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unified Inclusion/Exclusion: The ability to handle both "include this set" and "exclude this set" in a single, efficient BE scheme is a significant step towards more flexible broadcast systems.
  • "Cut-or-Select" Functionality: This term aptly describes the scheme's ability to precisely "cut" out revoked users or "select" intended recipients, offering fine-grained control.
  • Aggregation Functions as the Core: The paper highlights how novel aggregation functions can solve fundamental cryptographic problems like set membership efficiently.
  • Constant Ciphertext Size: Achieving O(1) ciphertext and decryption key sizes, irrespective of the number of users or the size of the subset, is a major performance breakthrough for large-scale applications.
  • Identity-Based Simplicity: Using user identities directly simplifies management and access control, making the system more user-friendly.

Key Results

  • The proposed Identity-Set-based Broadcast Encryption (SBE) scheme supports three modes: set-membership (Include-mode), all members (All-mode), and negative membership (Exclude-mode) simultaneously.
  • Ciphertexts and decryption keys are of optimal O(1) size, independent of the size of the user set or the subset.
  • The scheme is proven secure under the General Diffie-Hellman Exponent (GDHE) assumption, even with arbitrary large collusions of corrupted users.
  • Experimental results demonstrate the scheme's efficiency, with constant-size ciphertexts and reasonable computation times for aggregation functions, especially Zeros-based aggregation.

Limitations and Future Work

  • Performance of Poles-based Aggregation: While Zeros-based aggregation shows linear growth in computation cost with subset size, Poles-based aggregation's cost grows more rapidly. The authors suggest improving performance through parallel algorithms or fast elliptic curve techniques.
  • Practical Applications: The authors suggest future work in applying the scheme to practical scenarios like broadcasting, keyword searching, and voting.
  • Further Optimization: While the scheme is efficient, ongoing research into faster aggregation algorithms and optimizations for bilinear pairings could further enhance performance.

Summary updated

BibTeX
@article{zhu2015identity,
  author = {Yan Zhu and Xin Wang and Di Ma and Ruiqi Guo},
  title = {{Identity-Set-based Broadcast Encryption supporting "Cut-or-Select" with Short Ciphertext}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2015},
}

Loading related content...

Figure