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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
It was called efficiently-orderable encryption in [6].
- 2.
In Chenette et al.’s work, they took M to be the minimum value, i.e. \(M = 3\), making the ciphertext size only \(\lceil n \cdot \log _2 3 \rceil \) bits.
- 3.
Note that \((\textsf{ch}, \textsf{rsp}_i) \) is a signature of the message \(\hat{u}_0 || \hat{u}_1\) with respect to the public key \(\textsf{pk}_i\), while the secret key is \(\textsf{sk}_i\) and the randomness is \(\hat{u}_i \cdot r_i\).
- 4.
Our implementation is available at https://github.com/cpeng-crypto/pORE.
References
Agrawal, R., Kiernan, J., Srikant, R., Xu, Y.: Order preserving encryption for numeric data. In: Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, pp. 563–574 (2004)
Arasu, A., et al.: Orthogonal security with cipherbase. In: CIDR (2013)
Bajaj, S., Sion, R.: Trusteddb: a trusted hardware-based database with privacy and data confidentiality. IEEE Trans. Knowl. Data Eng. 26(3), 752–765 (2013)
Bogatov, D., Kollios, G., Reyzin, L.: A comparative evaluation of order-revealing encryption schemes and secure range-query protocols. Proc. VLDB Endow. 12(8), 933–947 (2019)
Boldyreva, A., Chenette, N., Lee, Y., O’Neill, A.: Order-preserving symmetric encryption. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 224–241. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01001-9_13
Boldyreva, A., Chenette, N., O’Neill, A.: Order-preserving encryption revisited: improved security analysis and alternative solutions. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 578–595. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_33
Boneh, D., Kogan, D., Woo, K.: Oblivious pseudorandom functions from isogenies. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12492, pp. 520–550. Springer, Heidelberg (2020). https://doi.org/10.1007/978-3-030-64834-3_18
Boneh, D., Lewi, K., Raykova, M., Sahai, A., Zhandry, M., Zimmerman, J.: Semantically secure order-revealing encryption: multi-input functional encryption without obfuscation. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part II. LNCS, vol. 9057, pp. 563–594. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_19
Cash, D., Grubbs, P., Perry, J., Ristenpart, T.: Leakage-abuse attacks against searchable encryption. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pp. 668–679 (2015)
Cash, D., Liu, F.H., O’Neill, A., Zhandry, M., Zhang, C.: Parameter-hiding order revealing encryption. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018, Part I. LNCS, vol. 11272, pp. 181–210. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-030-03326-2_7
Chang, Z., Xie, D., Li, F.: Oblivious ram: a dissection and experimental evaluation. Proc. VLDB Endow. 9(12), 1113–1124 (2016)
Chenette, N., Lewi, K., Weis, S.A., Wu, D.J.: Practical order-revealing encryption with limited leakage. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 474–493. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-52993-5_24
Demertzis, I., Papadopoulos, S., Papapetrou, O., Deligiannakis, A., Garofalakis, M.: Practical private range search revisited. In: Proceedings of the 2016 International Conference on Management of Data, pp. 185–198 (2016)
Durak, F.B., DuBuisson, T.M., Cash, D.: What else is revealed by order-revealing encryption? In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 1155–1166 (2016)
Faber, S., Jarecki, S., Krawczyk, H., Nguyen, Q., Rosu, M.C., Steiner, M.: Rich queries on encrypted data: beyond exact matches. In: Pernul, G., Ryan, P.Y.A., Weippl, E.R. (eds.) ESORICS 2015, Part II. LNCS, vol. 9327, pp. 123–145. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-319-24177-7_7
Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM (JACM) 33(4), 792–807 (1986)
Grubbs, P., Lacharité, M.S., Minaud, B., Paterson, K.G.: Pump up the volume: practical database reconstruction from volume leakage on range queries. In: Lie, D., Mannan, M., Backes, M., Wang, X. (eds.) ACM CCS 2018, pp. 315–331. ACM Press (2018). https://doi.org/10.1145/3243734.3243864
Grubbs, P., Lacharité, M.S., Minaud, B., Paterson, K.G.: Learning to reconstruct: statistical learning theory and encrypted database attacks. In: 2019 IEEE Symposium on Security and Privacy, pp. 1067–1083. IEEE Computer Society Press (2019). https://doi.org/10.1109/SP.2019.00030
Grubbs, P., Sekniqi, K., Bindschaedler, V., Naveed, M., Ristenpart, T.: Leakage-abuse attacks against order-revealing encryption. In: 2017 IEEE Symposium on Security and Privacy, pp. 655–672. IEEE Computer Society Press (2017). https://doi.org/10.1109/SP.2017.44
Hirose, S.: Collision-resistant and pseudorandom function based on Merkle-Damgård hash function. In: Park, J.H., Seo, S.H. (eds.) ICISC 2021. LNCS, vol. 13218, pp. 325–338. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-08896-4_17
Kamara, S., Moataz, T.: Computationally volume-hiding structured encryption. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019, Part II. LNCS, vol. 11477, pp. 183–213. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-17656-3_7
Kellaris, G., Kollios, G., Nissim, K., O’Neill, A.: Generic attacks on secure outsourced databases. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, pp. 1329–1340. ACM Press (2016). https://doi.org/10.1145/2976749.2978386
Kerschbaum, F.: Frequency-hiding order-preserving encryption. In: Ray, I., Li, N., Kruegel, C. (eds.) ACM CCS 2015, pp. 656–667. ACM Press (2015). https://doi.org/10.1145/2810103.2813629
Kerschbaum, F., Schröpfer, A.: Optimal average-complexity ideal-security order-preserving encryption. In: Ahn, G.J., Yung, M., Li, N. (eds.) ACM CCS 2014, pp. 275–286. ACM Press (2014). https://doi.org/10.1145/2660267.2660277
Kiltz, E., Lyubashevsky, V., Schaffner, C.: A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model. In: Nielsen, J., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10822, pp. 552–586. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_18
Kiltz, E., Masny, D., Pan, J.: Optimal security proofs for signatures from identification schemes. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 33–61. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_2
Kornaropoulos, E.M., Papamanthou, C., Tamassia, R.: The state of the uniform: attacks on encrypted databases beyond the uniform query distribution. In: 2020 IEEE Symposium on Security and Privacy, pp. 1223–1240. IEEE Computer Society Press (2020). https://doi.org/10.1109/SP40000.2020.00029
Kornaropoulos, E.M., Papamanthou, C., Tamassia, R.: Response-hiding encrypted ranges: revisiting security via parametrized leakage-abuse attacks. In: 2021 IEEE Symposium on Security and Privacy, pp. 1502–1519. IEEE Computer Society Press (2021). https://doi.org/10.1109/SP40001.2021.00044
Lacharité, M.S., Minaud, B., Paterson, K.G.: Improved reconstruction attacks on encrypted data using range query leakage. In: 2018 IEEE Symposium on Security and Privacy, pp. 297–314. IEEE Computer Society Press (2018). https://doi.org/10.1109/SP.2018.00002
Lewi, K., Wu, D.J.: Order-revealing encryption: new constructions, applications, and lower bounds. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, pp. 1167–1178. ACM Press (2016). https://doi.org/10.1145/2976749.2978376
Markatou, E.A., Tamassia, R.: Full database reconstruction with access and search pattern leakage. In: Lin, Z., Papamanthou, C., Polychronakis, M. (eds.) ISC 2019. LNCS, vol. 11723, pp. 25–43. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-30215-3_2
Naveed, M., Kamara, S., Wright, C.V.: Inference attacks on property-preserving encrypted databases. In: Ray, I., Li, N., Kruegel, C. (eds.) ACM CCS 2015, pp. 644–655. ACM Press (2015). https://doi.org/10.1145/2810103.2813651
Pandey, O., Rouselakis, Y.: Property preserving symmetric encryption. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 375–391. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_23
Popa, R.A., Li, F.H., Zeldovich, N.: An ideal-security protocol for order-preserving encoding. In: 2013 IEEE Symposium on Security and Privacy, pp. 463–477. IEEE Computer Society Press (2013). https://doi.org/10.1109/SP.2013.38
Popa, R.A., Redfield, C.M., Zeldovich, N., Balakrishnan, H.: Cryptdb: protecting confidentiality with encrypted query processing. In: Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, pp. 85–100 (2011)
Teranishi, I., Yung, M., Malkin, T.: Order-preserving encryption secure beyond one-wayness. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 42–61. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45608-8_3
Acknowlegements
We thank the anonymous reviewers for their helpful discussion and feedback. The work was supported by the National Key Research and Development Program of China (No. 2022YFB3102400), the National Natural Science Foundation of China (Nos. U21A20466, 62325209, 62272350,62122092, 62032005, 62202485), and the Major Program(JD) of Hubei Province (No. 2023BAA027).
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
A More on the Leakage of Different ORE Schemes
A More on the Leakage of Different ORE Schemes
As shown by Cash et al. [10], \(\mathcal {L}_1\) leaks less information than the leakage caused by CLWW ORE (\(\mathcal {L}_2\)) and Lewi-Wu ORE. Below we will provide more details about these leakage profiles.
Comparison of different leakage profiles.
Smoothed CLWW Leakage. Considering the set \(\{0,4,5,10,11\}\) in 4-bit plaintext space, it can be viewed as leaves of a 4-level full binary tree. In Fig. 7, the ideal leakage \(\mathcal {L}_0\) refers to the numeric order-relation. After removing the irrelevant leaves/nodes, the CLWW leakage \(\mathcal {L}_2\) refers to the subtree structure, in which grey points mean the position of \(\textsf{msdb}\) and green nodes mean unleaked \(\textsf{msdb}\). Note that for some plaintexts such as \(\{2,6,7,12,13\}\), it would also have equivalent subtree w.r.t. \(\{0,4,5,10,11\}\). While for other plaintexts such as \(\{1,2,3,5,6\}\), there are significant differences between the two subtree structures, and these two plaintext sequences are distinguishable by the leakage \(\mathcal {L}_2\) of the ciphertext alone. Moreover, the comparator can know from the ciphertext that \(m_i = 4\) has the bit form “01-0”, where “-” indicates the unknown bits. Considering the leakage \(\mathcal {L}_1\) which leaks the equality pattern of \(\textsf{msdb}\), while the comparator can infer additional information (i.e., \(\textsf{msdb}\)(0,4) < \(\textsf{msdb}\)(5, 11)), green nodes in subtrees are unknown to the comparator as the positions of \(\textsf{msdb}\) are not determined. Also, the position of gray nodes can be moved up or down. So, one can see that \(\{0,4,5,10,11\}\) and \(\{1,2,3,5,6\}\) leak the same information under \(\mathcal {L}_1\). Note that inspired by the block-wise encryption [30], Cash et al. [10] also demonstrated that an enhanced level of leakage \(\mathcal {L}_1\) can be achieved by encrypting message blocks instead of individual bits.
Specific Applications of pORE. Cash et al. [10] show that pORE is particularly suitable for specific scenarios where the adversary lacks a strong estimate of the prior distribution of the data. In many settings, data often follows a known type of distribution, as exemplified by Cash et al. [10], where various physical, biological, and financial quantities approximate a normal distribution due to the central limit theorem. In these scenarios, the database entries are independently drawn from a distribution with a known “shape” (e.g., normal, uniform, Laplace, etc.), but the adversary does not possess the mean and variance information necessary to determine the shifting and scaling factors. Consequently, pORE can be employed to effectively conceal both the shifting and scaling information. Notably, it has been observed by Cash et al. [10] that CLWW ORE [12] and Lewis-Wu ORE [30] fail to achieve shift hiding and scale hiding simultaneously. Nonetheless, as acknowledged by Cash et al. [10], pORE specifically guarantees security when the sensitivity lies solely in the scale and shift of the underlying plaintext distributions, and it may not be sufficient in scenarios where the shape of the distribution itself is highly sensitive or when there are correlations with other available data that could be exploited by an attacker.
Rights and permissions
Copyright information
© 2024 International Association for Cryptologic Research
About this paper
Cite this paper
Peng, C., Chen, R., Wang, Y., He, D., Huang, X. (2024). Parameter-Hiding Order-Revealing Encryption Without Pairings. In: Tang, Q., Teague, V. (eds) Public-Key Cryptography – PKC 2024. PKC 2024. Lecture Notes in Computer Science, vol 14604. Springer, Cham. https://doi.org/10.1007/978-3-031-57728-4_8
Download citation
DOI: https://doi.org/10.1007/978-3-031-57728-4_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-57727-7
Online ISBN: 978-3-031-57728-4
eBook Packages: Computer ScienceComputer Science (R0)