Abstract
Order-Preserving Encryption (OPE) is an encryption preserving the order relationship of the plaintexts to support efficient range query on ciphertexts. Other than traditional symmetric encryption aiming at absolute security, OPE sacrifices some security for the ability to search on ciphertext. In this paper, we propose a new cryptographic primitive, Probability-p Order-Preserving Encryption (p-OPE), which preserves the order of plaintexts with probability p. When \(p=1\), p-OPE becomes OPE, thus p-OPE is an extension of OPE. We define and analyse the security and precision of the novel primitive, then we propose a construction of p-OPE and conduct experiments to show its performance. As shown in the theoretical analysis and experiment results, p-OPE can improve the security at the cost of some precision sacrifice.
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
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, SIGMOD 2004, NY, USA, pp. 563–574. ACM, New York (2004)
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). doi:10.1007/978-3-642-01001-9_13
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. LNCS, vol. 9057, pp. 563–594. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46803-6_19
Chen, C., Zhu, X., Shen, P., Hu, J., Guo, S., Tari, Z., Zomaya, A.Y.: An efficient privacy-preserving ranked keyword search method. IEEE Trans. Parallel Distrib. Syst. 27(4), 951–963 (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, CCS 2016, NY, USA, pp. 1155–1166 (2016). http://doi.acm.org/10.1145/2976749.2978379
Fu, Z., Huang, F., Sun, X., Vasilakos, A., Yang, C.N.: Enabling semantic search based on conceptual graphs over encrypted outsourced data. IEEE Trans. Serv. Comput. PP(99), 1 (2016)
Fu, Z., Ren, K., Shu, J., Sun, X., Huang, F.: Enabling personalized search over encrypted outsourced data with efficiency improvement. IEEE Trans. Parallel Distrib. Syst. PP(99), 1 (2015)
Fu, Z., Sun, X., Ji, S., Xie, G.: Towards efficient content-aware search over encrypted outsourced data in cloud. In: IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications, pp. 1–9, April 2016
Fu, Z., Wu, X., Guan, C., Sun, X., Ren, K.: Toward efficient multi-keyword fuzzy search over encrypted outsourced data with accuracy improvement. IEEE Trans. Inf. Forensics Secur. 11(12), 2706–2716 (2016)
Google: The encrypted bigquery client. https://github.com/google/encrypted-bigquery-client
Li, K., Zhang, W., Yang, C., Yu, N.: Security analysis on one-to-many order preserving encryption-based cloud data search. IEEE Trans. Inf. Forensics Secur. 10(9), 1918–1926 (2015)
Manning, C.D., Raghavan, P., Schütze, H., et al.: Introduction to Information Retrieval, vol. 1. Cambridge University Press, Cambridge (2008)
Martınez, S., Miret, J.M., Tomas, R., Valls, M.: Security analysis of order preserving symmetric cryptography. Appl. Math. Inf. Sci. (AMIS) 7(4), 1285–1295 (2013)
Naveed, M., Kamara, S., Wright, C.V.: Inference attacks on property-preserving encrypted databases. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS 2015, NY, USA, pp. 644–655. ACM, New York (2015)
Popa, R., Li, F., Zeldovich, N.: An ideal-security protocol for order-preserving encoding. In: 2013 IEEE Symposium on Security and Privacy (SP), pp. 463–477, May 2013
Popa, R.A., Redfield, C.M.S., Zeldovich, N., Balakrishnan, H.: Cryptdb: protecting confidentiality with encrypted query processing. In: Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, SOSP 2011, NY, USA, pp. 85–100. ACM, New York (2011)
Wang, C., Cao, N., Ren, K., Lou, W.: Enabling secure and efficient ranked keyword search over outsourced cloud data. IEEE Trans. Parallel Distrib. Syst. 23(8), 1467–1479 (2012)
Wozniak, S., Rossberg, M., Grau, S., Alshawish, A., Schaefer, G.: Beyond the ideal object: towards disclosure-resilient order-preserving encryption schemes. In: Proceedings of the 2013 ACM Workshop on Cloud Computing Security Workshop, CCSW 2013, NY, USA, pp. 89–100. ACM, New York (2013)
Xia, Z., Wang, X., Sun, X., Wang, Q.: A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data. IEEE Trans. Parallel Distrib. Syst. 27(2), 340–352 (2016)
Xia, Z., Wang, X., Zhang, L., Qin, Z., Sun, X., Ren, K.: A privacy-preserving and copy-deterrence content-based image retrieval scheme in cloud computing. IEEE Trans. Inf. Forensics Secur. 11(11), 2594–2608 (2016)
Xia, Z., Zhu, Y., Sun, X., Qin, Z., Ren, K.: Towards privacy-preserving content-based image retrieval in cloud computing. IEEE Trans. Cloud Comput. PP(99), 1 (2015)
Xia, Z., Xiong, N.N., Vasilakos, A.V., Sun, X.: EPCBIR: an efficient and privacy-preserving content-based image retrieval scheme in cloud computing. Inf. Sci. 387, 195–204 (2017). http://www.sciencedirect.com/science/article/pii/S0020025516321971
Zhangjie, F., Xingming, S., Qi, L., Lu, Z., Jiangang, S.: Achieving efficient cloud search services: multi-keyword ranked search over encrypted cloud data supporting parallel computing. IEICE Trans. Commun. 98(1), 190–200 (2015)
Acknowledgements
This work was supported in part by the Natural Science Foundation of China under Grant U1636201 and 61572452.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Yang, C., Zhang, W., Ding, J., Yu, N. (2017). Probability-p Order-Preserving Encryption. In: Sun, X., Chao, HC., You, X., Bertino, E. (eds) Cloud Computing and Security. ICCCS 2017. Lecture Notes in Computer Science(), vol 10603. Springer, Cham. https://doi.org/10.1007/978-3-319-68542-7_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-68542-7_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-68541-0
Online ISBN: 978-3-319-68542-7
eBook Packages: Computer ScienceComputer Science (R0)