logo

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

Abstract

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

国家自然科学基基金(61272435)

信息安全国家重点实验室开放课题基金(2016-MS-19)

广西可信软件重点实验室研究课题资助(kx201614)

陕西省自然科学基础研究计划面上项目(2017JM6069)


References

[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

  • Figure 1

    Monotonous function

  • Figure 2

    (Color online) Comparison of computation cost between our protocol 1 and protocol 1 in [13]

  • Figure 4

    Relationship between point $P$ and irregular region $S$

  • Figure 5

    Relationship between point $P$ and matrix $M_i$

  • Table 1   $x\oplus~y$
    $x$ $y$ $x~\oplus~y$
    0 0 0
    0 1 1
    1 0 1
    1 1 0
  • Table 2   0-1 coding
    Original data 0-1 coding
    $x=4$ $a=\{0,0,0,1,0,0,0\}$
    $y=2$ $b=\{0,1,1,1,1,1,1\}$
    $y+l=5$ $c=\{0,0,0,0,1,1,1\}$
  • Table 3   xor concatenation
    Original data xor concatenation
    $x=4$ $a=\{0,0,0,1,0,0,0\}$
    $y=2$ $b=\{0,1,1,1,1,1,1\}$
    $y+l=5$ $c=\{0,0,0,0,1,1,1\}$
    $a\oplus~b$ $\{0,1,1,0,1,1,1\}$
    $a\oplus~c$ $\{0,0,0,1,1,1,1\}$
    $(a\oplus~b)\parallel(a\oplus~c)$ $\{0,1,1,0,1,1,1\parallel0,0,0,1,1,1,1\}$
    $b~\parallel~c$ $\{0,1,1,1,1,1,1\parallel0,0,0,0,1,1,1\}$
  • Table 4   Concatenation xor
    Original data Concatenation xor
    $x=4$ $a=\{0,0,0,1,0,0,0\}$
    $y=2$ $b=\{0,1,1,1,1,1,1\}$
    $y+l=5$ $c=\{0,0,0,0,1,1,1\}$
    $a\parallel~a$ $\{0,0,0,1,0,0,0\parallel0,0,0,1,0,0,0\}$
    $b\parallel~c$ $\{0,1,1,1,1,1,1\parallel0,0,0,0,1,1,1\}$
    $(a\parallel~a)\oplus(b\parallel~c)$ $\{0,1,1,0,1,1,1\parallel0,0,0,1,1,1,1\}$
  • Table 5   Transferring real into integer
    Original data Corresponding integer
    $x=4.27$ $t=4270$
    $y_1=3.348$ $t_1=3348$
    $y_2=51.3$ $t_2=51300$
  • Table 6   Efficiency comparison between our protocols and the protocols in
    Protocol Computation cost Communication overhead
    Protocol 1 in [13] $12M_{N^2}$ 5
    Protocol 2 in [13] $8M_{N^2}$ 6
    Protocol 1 in ours $2nM_N$ 3
    Protocol 2 in ours $4M_{N^2}$ 3
  • Table 7   Performance comparison between our protocols and the protocols in
    Protocol (I) (II) (III) (IV) (V)
    Protocol 1 in [13] checkmark checkmark checkmark checkmark $\times$
    Protocol 2 in [13] $\times$ checkmark checkmark checkmark $\times$
    Protocol 1 in ours checkmark checkmark checkmark checkmark $\times$
    Protocol 2 in ours checkmark checkmark checkmark checkmark checkmark
  • Table 8   Average time cost per modular exponentiation
    $p,~q$ (bit) $M_N$ (ms) $M_{N^2}$ (ms)
    128 1.847 5.857
    256 14.000 36.857
    300 16.857 59.571
    350 26.142 88.000
    400 35.142 131.142
    450 51.857 186.857
    512 71.000 273.142
    800 209.429 949.714
    1024 482.143 2126.429

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

京ICP备18024590号-1