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

Zhenhua CHEN 1,2,3,*,
• AcceptedSep 13, 2017
• PublishedJan 8, 2018
Share
Rating

### 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

Citations

Altmetric