SCIENCE CHINA Information Sciences, Volume 60, Issue 6: 062101(2017) https://doi.org/10.1007/s11432-016-0242-7

hOPE: improved order preserving encryption with the power to homomorphic operations of ciphertexts

More info
  • ReceivedJul 28, 2016
  • AcceptedSep 8, 2016
  • PublishedJan 21, 2017


Database applications that manage and utilize massive data must address the issues of {element comparisons}, the core operations in index accessing, {metric computations} and {metric comparisons}, and the core operations in result ranking. In the cloud era, to avoid private information leakage, encrypted data are subcontracted, and resolutions for the problems that arise in three operations over ciphertexts are urgently required. Indeed, it is possible to handle element comparison through {order preserving encryption/encoding} (OPE) or metric computation through {homomorphic encryption} (HE) directly over ciphertexts. Unfortunately, the simultaneous achievement of both goals (i.e., metric computation and comparison) by directly combining OPE and HE remains intractable. In this work, an improved OPE, named hOPE, is proposed to support homomorphic operations over ciphertexts in addition to comparisons. Based on hOPE, AhOPE and PhOPE are designed to support homomorphic addition and product, respectively. Both schemes are proved to be indistinguishable under operated and ordered chosen-plaintext attack (IND-O\textsuperscript{2}CPA) secure when the adopted HE algorithm provides indistinguishable under ordered chosen-plaintext attack (IND-OCPA secure). hOPE is a general construction that supports arbitrary HE algorithms and achieves consistent security. We deploy AhOPE and PhOPE in practice with a trusted/untrusted third party and compare the result with the state-of-the-art methods. The results show that our presented algorithms need few interactions and fill the gap between OPE and HE.

Funded by

National Natural Science Foundation of China(61472298)

China 111 Project(B16037)

National Natural Science Foundation of China(61262073)

National Natural Science Foundation of China(U1405255)

National Natural Science Foundation of China(61672408)

National Natural Science Foundation of China(61662009)

National High Technology Research and Development Program(2015AA016007)

National Natural Science Foundation of China(61472310)



The work was supported by National Natural Science Foundation of China (Grant Nos. 61472298, 61672408, 61262073, 61472310, U1405255, 61662009), National High Technology Research and Development Program (Grant No. 2015AA016007), and China 111 Project (Grant No. B16037).


[1] Agrawal R, Kiernan J, Srikant R, et al. Order preserving encryption for numeric data. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (ICDE), Paris, 2004. 563--574. Google Scholar

[2] Boldyreva A, Chenette N, Lee Y, et al. Order-preserving symmetric encryption. In: Proceedings of the 28th Annual International Conference on Advances in Cryptology: the Theory and Applications of Cryptographic Techniques, Cologne, 2009. 224--241. Google Scholar

[3] Popa R A, Li F H, Zeldovich N. An ideal-security protocol for order-preserving encoding. In: Proceedings of IEEE Symposium on Security and Privacy (S&P), Berkeley, 2013. 463--477. Google Scholar

[4] Teranishi I, Yung M, Malkin T. Order-preserving encryption secure beyond one-wayness. In: Advances in Cryptology---ASIACRYPT. Berlin: Springer, 2014. 42--61. Google Scholar

[5] Mavroforakis C, Chenette N, O'Neill A, et al. Modular order-preserving encryption, revisited. In: Proceedings of the ACM International Conference on Management of Data (SIGMOD), Melbourne, 2015. 763--777. Google Scholar

[6] Zhang H G, Han W B, Lai X J, et al. Survey on cyberspace security. Sci China Inf Sci, 2015, 58: 110101 Google Scholar

[7] Bentley J L. Multidimensional binary search trees used for associative searching. ACM Commun, 1975, 18: 509-517 CrossRef Google Scholar

[8] Bayer R, McCreight E. Organization and maintenance of large ordered indexes. Acta Inform, 1972, 1: 173-189 CrossRef Google Scholar

[9] Hartigan J A, Wong M A. Algorithm as 136: a k-means clustering algorithm. J Royal Stat Soc Ser C, 1979, 28: 100-108 Google Scholar

[10] Guttman A. R-trees: a dynamic index structure for spatial searching. In: Proceedings of the ACM International Conference on Management of Data (SIGMOD), Boston, 1984. 47--57. Google Scholar

[11] Rivest R L, Adleman L, Dertouzos M L. On data banks and privacy homomorphisms. In: Proceedings of Foundations of Secure Computation, Atlanta, 1978. 165--179. Google Scholar

[12] Paillier P. Public-key cryptosystems based on composite degree residuosity classes. In: Advances in Cryptology---EUROCRYPT'99. Berlin: Springer, 1999. 223--238. Google Scholar

[13] Gentry C. Fully homomorphic encryption using ideal lattices. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), Bethesda, 2009. 9: 169--178. Google Scholar

[14] Gentry C, Halevi S. Implementing gentry's fully-homomorphic encryption scheme. In: Advances in Cryptology---EUROCRYPT. Berlin: Springer, 2011. 129--148. Google Scholar

[15] Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, Cambridge, 2012. 309--325. Google Scholar

[16] Elmehdwi Y, Samanthula B, Jiang W. Secure k-nearest neighbor query over encrypted data in outsourced environments. In: Proceedings of IEEE 30th International Conference on Data Engineering (ICDE), Chicago, 2014. 664--675. Google Scholar

[17] Boneh D, Lynn B, Shacham H. Short signatures from the weil pairing. In: Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology. London: Springer, 2001. 514--532. Google Scholar

[18] Jiang Q, Wei F, Fu S, et al. Robust extended chaotic maps-based three-factor authentication scheme preserving biometric template privacy. Nonlinear Dynam, 2016, 83: 2085-2101 CrossRef Google Scholar

[19] Koblitz N, Menezes A. Pairing-based cryptography at high security levels. In: Proceedings of IMA International Conference on Cryptography and Coding, Cirencester, 2005. 13--36. Google Scholar

[20] Jiang Q, Ma J, Li G, et al. Improvement of robust smart-card-based password authentication scheme. Int J Commun Syst, 2015, 28: 383-393 CrossRef Google Scholar

[21] Kerschbaum F, Schroepfer A. Optimal average-complexity ideal-security order-preserving encryption. In: Proceedings of ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, 2014. 275--286. Google Scholar

[22] Curtmola R, Garay J, Kamara S, et al. Searchable symmetric encryption: improved definitions and efficient constructions. J Comput Secur, 2011, 19: 895-934 CrossRef Google Scholar

[23] Kuzu M, Islam M S, Kantarcioglu M. Efficient similarity search over encrypted data. In: Proceedings of the IEEE 28th International Conference on Data Engineering (ICDE), Washington, 2012. 1156--1167. Google Scholar

[24] Demertzis I, Papadopoulos S, Papapetrou O, et al. Practical private range search revisited. In: Proceedings of the ACM International Conference on Management of Data (SIGMOD), San Francisco, 2016. 185--198. Google Scholar

[25] Kerschbaum F. Frequency-hiding order-preserving encryption. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security (CCS), Denver, 2015. 656--667. Google Scholar

[26] Popa R A, Redfield C M S, Zeldovich N, et al. CryptDB: protecting confidentiality with encrypted query processing. In: Proceedings of the 23rd ACM Symposium on Operating Systems Principles, Cascais, 2011. 85--100. Google Scholar

[27] Tu S, Kaashoek M F, Madden S, et al. Processing analytical queries over encrypted data. Proc VLDB Endow, 2013, 6: 289-300 CrossRef Google Scholar

[28] Choi S, Ghinita G, Lim H S, et al. Secure kNN query processing in untrusted cloud environments. IEEE TKDE, 2014, 26: 2818-2831 Google Scholar

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1       京公网安备11010102003388号