SCIENTIA SINICA Informationis, Volume 48, Issue 2: 187-204(2018) https://doi.org/10.1360/N112017-00025

Fully privacy-preserving determination of point-range relationship

More info
  • ReceivedJun 13, 2017
  • AcceptedSep 13, 2017
  • PublishedJan 8, 2018


The privacy-preserving determination of point-range relationship is widely applied to range queries. However, most existing solutions only protect one party's privacy but not the other party's; moreover, they only cover integers or rational numbers. Focusing on these problems, we design two protocols with the notion of secure multiparty computation. We first present the fully privacy-preserving protocol 1,łinebreak which can determine whether an integer is in a discrete integer interval using the 0-1 coding in combination with the Goldwasser-Micali homomorphic encryption. Subsequently, we present the fully privacy-preserving protocol 2,łinebreak which can determine whether a real number is in a continuous real number interval using the monotonic function in combination with Paillier's homomorphic encryption. Finally, we present a practical example based on our protocol. Theoretical and experiential analyses show that both of our protocols achieve a low communication cost, while preserving the full privacy of two parties. In addition, protocol 2 in this paper first gives a solution to privately determine whether a real number is in a continuous real number interval, while showing higher efficiency and better performance.

Funded by






[1] Yao A C. Protocols for secure computations. In: Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, Chicago, 1982. 160--164. Google Scholar

[2] Freudiger J, Rane S, Brito A E, et al. Privacy preserving data quality assessment for high-fidelity data sharing. In: Proceedings of the ACM Workshop on Information Sharing and Collaborative Security. New York, 2014. 21--29. Google Scholar

[3] Li X Y, Jung T. Search me if you can: privacy-preserving location query service. In: Proceedings of IEEE INFOCOM, Turin, 2013. 2760--2768. Google Scholar

[4] Yang J, Zhao J S, Zhang J P. A privacy preservation method for high dimension data mining. Acta Electr Sin, 2013, 41: 2187--2192. Google Scholar

[5] Samanthula B K, Elmehdwi Y, Howser G. A secure data sharing and query processing framework via federation of cloud computing. Inf Syst, 2015, 48: 196-212 CrossRef Google Scholar

[6] Kerschbaum F. Privacy-preserving computation. In: Annual Privacy Forum. Berlin: Springer, 2014. 41--54. Google Scholar

[7] Boneh D, Waters B. Conjunctive, subset, and range queries on encrypted data. In: Proceedings of Theory of Cryptography Conference. Berlin: Springer, 2007. 535--554. Google Scholar

[8] Wen M, Lu R, Zhang K. PaRQ: A Privacy-Preserving Range Query Scheme Over Encrypted Metering Data for Smart Grid. IEEE Trans Emerg Top Comput, 2013, 1: 178-191 CrossRef Google Scholar

[9] Cramer R, Damgard I, Schoenmakers B. Proofs of partial knowledge and simplified design of witness hiding protocols. In: Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, 1994. 174--187. Google Scholar

[10] Boudot F. Efficient proofs that a committed number lies in an interval. In: Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques, Bruges, 2000. 431--444. Google Scholar

[11] Camenisch J, Chaabouni R, Shelat A. Efficient protocols for set membership and range proofs. In: Proceedings of the 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, 2008. 234--252. Google Scholar

[12] Chaabouni R, Lipmaa H, Zhang B. A non-interactive range proof with constant communication. In: Proceedings of International Conference on Financial Cryptography and Data Security, Kralendijk, 2012. 179--199. Google Scholar

[13] Guo Y M, Zhou S F, Dou J W, et al. Efficient privacy-preserving interval computation and its applications. Chinese J Comput, 2017, 40: 1664--1679. Google Scholar

[14] Paillier P. Public-key cryptosystems based on composite degree residue classes. In: Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques, Prague, 1999. 223--238. Google Scholar

[15] Goldwasser S, Micali S. Probabilistic encryption. J Comput Syst Sci, 1984, 28: 270-299 CrossRef Google Scholar

[16] Goldreich O. Foundations of Cryptography: Basic Applications. London: Cambridge University Press, 2004. 599--729. Google Scholar

[17] Du W, Zhan Z. A practical approach to solve secure multi-party computation problems. In: Proceedings of the 2002 Workshop on New Security Paradigms. New York: ACM, 2002. 127--135. Google Scholar

[18] Shundong L, Daoshun W, Yiqi D. Symmetric cryptographic solution to Yao's millionaires' problem and an evaluation of secure multiparty computations. Inf Sci, 2008, 178: 244-255 CrossRef Google Scholar

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