International Association for Cryptologic Research

International Association
for Cryptologic Research


Parameter-Hiding Order-Revealing Encryption without Pairings

Cong Peng , Wuhan University
Rongmao Chen , National University of Defense Technology
Yi Wang , National University of Defense Technology
Debiao He , Wuhan University
Xinyi Huang , Hong Kong University of Science and Technology
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2024
Abstract: Order-Revealing Encryption (ORE) provides a practical solution for conducting range queries over encrypted data. Achieving a desirable privacy-efficiency tradeoff in designing ORE schemes has posed a significant challenge. At Asiacrypt 2018, Cash et al. proposed Parameter-hiding ORE (pORE), which specifically targets scenarios where the data distribution shape is known, but the underlying parameters (such as mean and variance) need to be protected. However, existing pORE constructions rely on impractical bilinear maps, limiting their real-world applicability. In this work, we propose an alternative and efficient method for constructing pORE using identification schemes. By leveraging the map-invariance property of identification schemes, we eliminate the need for pairing computations during ciphertext comparison. Specifically, we instantiate our framework with the pairing-free Schnorr identification scheme and demonstrate that our proposed pORE scheme reduces ciphertext size by approximately 31.25\% and improves encryption and comparison efficiency by over two times compared to the current state-of-the-art pORE construction. Our work provides a more efficient alternative to existing pORE constructions and could be viewed as a step towards making pORE a viable choice for practical applications.
  title={Parameter-Hiding Order-Revealing Encryption without Pairings},
  author={Cong Peng and Rongmao Chen and Yi Wang and Debiao He and Xinyi Huang},