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


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

  • 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