TL;DR
This paper introduces a new, more efficient method for "Parameter-Hiding Order-Revealing Encryption" (PORE), a cryptographic technique that allows range queries on encrypted data while protecting sensitive information about the data's distribution. By replacing computationally expensive pairing operations with a novel approach based on identification schemes, they achieve significant improvements in ciphertext size and speed.
What Problem Does This Paper Address?
Order-Revealing Encryption (ORE) is a powerful tool for enabling secure range queries on encrypted data. However, existing ORE schemes often reveal too much information about the underlying data, making them vulnerable to attacks, especially when the data distribution is known. A more advanced concept, Parameter-Hiding ORE (PORE), was introduced to address this by protecting information about the data's distribution parameters (like mean and variance). The challenge has been that existing PORE constructions rely on inefficient bilinear pairings, limiting their practical use. This paper tackles the problem of creating a PORE scheme that is both secure and efficient, specifically by eliminating the need for these costly pairing operations.
Methods
The core of this paper's contribution lies in developing a new PORE construction that avoids bilinear pairings. They achieve this by:
- Leveraging Identification Schemes: They introduce a new type of identification scheme with a "map-invariance" property. This property allows for secure comparisons without relying on pairings.
- Constructing Property-Preserving Hash (PPH) Schemes: Using their map-invariant identification schemes, they build a generic PPH scheme. PPH is a crucial primitive for PORE, enabling the comparison of encrypted data while preserving certain properties.
- Generic ORE Construction: They then use their PPH scheme to construct a generic ORE scheme with a specific leakage profile (smoothed CLWW leakage).
- Parameter-Hiding ORE: Finally, they adapt Cash et al.'s framework to convert their ORE scheme into a parameter-hiding ORE (PORE) scheme.
- Schnorr Identification Instance: They instantiate their generic PPH and ORE constructions using the pairing-free Schnorr identification scheme, which is a well-established cryptographic primitive.
Datasets
Not discussed in the paper. The paper focuses on theoretical constructions and experimental evaluation of their proposed cryptographic scheme, rather than training or evaluating on specific datasets.
Key Insights and Ideas
- Pairing-Free PORE is Achievable: The most significant insight is demonstrating that parameter-hiding ORE can be constructed efficiently without relying on computationally expensive bilinear pairings.
- Map-Invariance is Key: The introduction of the "map-invariance" property for identification schemes is a novel contribution that unlocks the ability to perform secure comparisons without pairings.
- Identification Schemes as Building Blocks: The paper highlights the versatility of identification schemes, showing they can be used as a foundation for constructing advanced cryptographic primitives like PPH and, subsequently, PORE.
- Efficiency Gains are Substantial: The proposed scheme offers a significant performance improvement over existing PORE constructions, making it more practical for real-world applications.
Key Results
The paper presents a new PORE scheme (Sch-ORE) that offers several advantages over the state-of-the-art PORE construction by Cash et al. [10]:
- Ciphertext Size Reduction: The ciphertext size is reduced by approximately 31.25%.
- Encryption Efficiency Improvement: Encryption speed is increased by nearly 2.6 times.
- Comparison Efficiency Improvement: Comparison speed is increased by more than 3 times.
- Security Level Maintained: The proposed scheme achieves the same security level (smoothed CLWW leakage) as the previous construction.
Limitations and Future Work
- Leakage Profile: While the scheme achieves parameter-hiding security, it still has a specific leakage profile (smoothed CLWW leakage). The authors acknowledge that for applications requiring extremely high security, even this level of leakage might be problematic.
- Future Work: The authors suggest exploring other hardness assumptions for their identification schemes to construct PPH and PORE. They also mention the potential for constructing post-quantum PORE schemes, noting that their pairing-free approach offers more flexibility for this than previous pairing-based methods.
Summary updated