TL;DR
This paper introduces "one-sided probabilistic rank," a new cryptographic tool that allows for more efficient predicate encryption schemes using bilinear maps. This breakthrough enables predicate encryption for a wider range of complex functions, including those previously thought impossible with these assumptions.
What Problem Does This Paper Address?
Predicate Encryption (PE) is a cryptographic primitive that allows an authority to encrypt data such that only users with specific "attributes" (represented by a secret key) can decrypt it, and only if a certain Boolean function f evaluates to true for the ciphertext's attribute and the user's key attribute. A key challenge in PE is constructing schemes that are efficient and support a broad class of functions, especially when relying on standard cryptographic assumptions like bilinear maps. Previous work often limited PE to functions that could be expressed as inner products. While some functions like "greater-than" were addressed, they required more complex assumptions or different approaches. This paper aims to bridge this gap by developing a new technique that expands the applicability of PE constructions based on bilinear maps.
Methods
The core innovation of this paper is the introduction of "one-sided probabilistic rank." This concept generalizes existing notions of rank by allowing for a controlled amount of "error" in the evaluation of a function. Specifically, for a Boolean function f(x, y), it guarantees that if f(x, y) = 0, then a certain inner product (g(x), h(y)) will be zero with a high probability (at least 1/poly(n)), and if f(x, y) = 1, then (g(x), h(y)) will be non-zero with high probability. This probabilistic nature, combined with the ability to handle "high error" in the f(x, y) = 0 case, is crucial.
The authors then show how this one-sided probabilistic rank can be used to construct PE schemes. They leverage existing PE schemes for inner products and combine them with their new rank construction. A key result is that if a function has a low one-sided probabilistic rank, it can be efficiently encrypted using PE with bilinear maps.
Furthermore, the paper connects this concept to Arthur-Merlin (AM) communication complexity. They demonstrate that functions with low AM communication complexity (specifically, O(log n)) can be shown to have a low one-sided probabilistic rank, thus enabling PE for these functions.
Datasets
Not discussed in the paper. The paper focuses on theoretical constructions and cryptographic primitives, not empirical evaluation on specific datasets.
Key Insights and Ideas
- One-Sided Probabilistic Rank: This is the central new concept. It's a clever way to "embed" complex functions into inner products with controlled, probabilistic errors, making them amenable to existing PE constructions. The allowance for high error in one case is a key differentiator.
- Bridging AM Communication and PE: The paper establishes a powerful link between the complexity of communication protocols (AM) and the feasibility of constructing PE schemes. This opens up new avenues for designing PE for functions that are hard to analyze in other ways.
- Expanding PE Capabilities: The work significantly broadens the class of functions for which PE can be constructed using standard bilinear map assumptions, including functions like "greater-than" and "sparse set disjointness" with improved efficiency.
- Inner Product Encryption as a Building Block: The paper highlights the versatility of inner product encryption as a fundamental primitive that, when combined with new techniques like probabilistic rank, can unlock more advanced cryptographic functionalities.
Key Results
- A general construction for predicate encryption for any function with efficient one-sided probabilistic rank, assuming secure inner product encryption.
- Demonstration that functions with
O(log n)Arthur-Merlin communication complexity have polynomial one-sided probabilistic rank, enabling PE for them. - Specific constructions for PE for functions like:
- Greater-than function (
GEQn) with polynomial rank (improving on previous exponential bounds for deterministic rank). - Sparse Set Disjointness.
- Functions computable by polynomial-size SYM SYM circuits.
- AND-OR circuits.
- The construction works over rings like
Zm, which is important for existing inner product encryption schemes.
Limitations and Future Work
- Functional Encryption (FE): The authors note that their current scheme does not achieve the stronger notion of Functional Encryption (FE), where attributes are hidden even when decryption is possible. They suggest that extending their approach to FE is a challenging but interesting future direction.
- Error Probability: While the paper handles high error in one direction, the possibility of constructing probabilistic rank expressions with negligible error in both directions is mentioned as a potential avenue for future research, though it's noted that this might lead back to deterministic rank expressions for which lower bounds are known.
- Generalizing Rank: The paper hints at exploring whether their approach can support rank expressions with polynomial error on both sides, similar to work by Bauer et al.
- Efficiency: While the constructions are efficient in terms of rank, the paper doesn't delve deeply into the concrete efficiency of the resulting PE schemes in terms of ciphertext size or decryption time, which would be a natural next step.
Summary updated