TL;DR
This paper introduces a new cryptographic primitive called "one-sided probabilistic rank" that allows for the construction of predicate encryption schemes using only bilinear maps. This breakthrough enables efficient encryption for a wider range of functions than previously possible, including complex queries like "greater than" and "sparse set disjointness," which are crucial for real-world applications in data privacy and access control.
What Problem Does This Paper Address?
Predicate Encryption (PE) is a powerful cryptographic tool that allows an authority to encrypt data such that only users with specific "attributes" can decrypt it, provided a certain Boolean function f evaluates to true for their attribute and the data's attribute. For example, a credit card company could use PE to flag suspicious transactions based on attributes like location and amount, without revealing all transaction details.
While PE schemes exist, constructing them for complex functions using only standard cryptographic assumptions like bilinear maps has been a significant challenge. Previous methods were largely limited to functions that could be expressed as inner products. This paper tackles the problem of building PE for a broader class of functions, specifically those with "low one-sided probabilistic rank," using only bilinear maps.
Methods
The core innovation of this paper is the introduction of one-sided probabilistic rank. This is a relaxation of the "one-sided rank" concept, which allows for a small probability of error in the evaluation of a function f(x, y). Specifically, for a function f, they define a probabilistic rank d where:
- If
f(x, y) = 0(meaning decryption should be possible), the probability of a specific inner product being zero is at least1/poly(n). - If
f(x, y) = 1(meaning decryption should not be possible), the probability of the same inner product being zero is negligible (ε(n)).
This probabilistic approach, combined with existing techniques for inner product encryption (which are constructible from bilinear maps), allows them to build PE schemes for functions that were previously out of reach. They also leverage Arthur-Merlin (AM) communication protocols, showing that functions with low AM communication complexity (specifically, O(log n)) can be translated into functions with low one-sided probabilistic rank.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Probabilistic Rank as a Bridge: The key insight is that a small, controlled amount of error in rank calculations can be tolerated and even leveraged to construct PE schemes for complex functions, something deterministic rank couldn't achieve.
- AM Protocols as a Source of PE: The paper establishes a strong connection between the communication complexity of Arthur-Merlin protocols and the feasibility of constructing PE schemes. This opens up new avenues for designing PE for functions with known AM protocols.
- Bilinear Maps are Sufficient: The work demonstrates that powerful PE schemes can be built using only bilinear maps, a fundamental cryptographic tool, without needing more advanced assumptions like multilinear maps or LWE.
- Generalizing Inner Product Encryption: The paper shows how to extend PE beyond simple inner products to functions like "greater than" and "sparse set disjointness," which have significant practical implications.
Key Results
The paper presents several key results:
- Theorem 2: Assuming secure inner product encryption (constructible from bilinear maps), a PE scheme can be constructed for any function with efficient one-sided probabilistic rank. The complexity of the PE scheme is polynomial in the rank.
- New PE Constructions: The paper provides PE constructions for functions with low AM communication complexity, including:
- Greater-than function (GEQn): Previously, PE for this function required stronger assumptions. This work shows it can be achieved with bilinear maps and has a one-sided probabilistic rank of
poly(n), a significant improvement over its deterministic one-sided rank. - Sparse Set Disjointness: This construction allows for handling much larger universe sizes than previous methods.
- Approximate Matching: PE for functions like "Hamming distance at most k" is also enabled.
- Efficiency: The constructed PE schemes have ciphertexts of length
O(d log |R|), wheredis the one-sided probabilistic rank.
Limitations and Future Work
- Partial Correctness: The paper focuses on proving "partial correctness" for its PE schemes, which means decryption succeeds with high probability. A standard technique is then used to achieve "full correctness" (decryption succeeds with all but negligible probability), but this involves repeating the scheme, increasing ciphertext size.
- Security Proofs: The security proofs rely on the security of the underlying inner product encryption scheme and the properties of the one-sided probabilistic rank.
- Future Work: The authors suggest exploring extensions to functional encryption (FE), where attributes are hidden even upon successful decryption. They also ponder whether probabilistic rank expressions with negligible error on both sides are possible and what implications that would have. Investigating the use of probabilistic rank expressions with polynomial error on both sides is also mentioned as a future direction.
Summary updated