This paper introduces two-party protocols for various operations on two integer intervals that are privacy-preserving in the semi-honest model. Specifically, this work proposes new protocols for determining whether two intervals overlap; computing the boundaries and size of the overlap; and selecting a random sub-interval within the overlap. The protocols are presented both for homomorphic encryption and for secret sharing as basic secure multi-party computation techniques. Moreover, this paper presents a comprehensive performance evaluation of the newly-developed protocols.
R.Agrawal, R.Srikant and D.Thomas, Privacy preserving OLAP, in: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, ACM, 2005, pp. 251–262. doi:10.1145/1066157.1066187.
2.
G.Asharov and Y.Lindell, A full proof of the BGW protocol for perfectly-secure multiparty computation, Report 2011/136, IACR Cryptology ePrint Archive, 2011, available from: http://eprint.iacr.org/2011/136.
3.
G.R.Blakley, Safeguarding cryptographic keys, in: Proceedings of the AFIPS National Computer Conference, Vol. 48, 1979, pp. 313–317.
4.
D.Bogdanov, Sharemind, programmable secure computations with practical applications, PhD thesis, University of Tartu, 2013.
5.
D.Boneh and B.Waters, Conjunctive, subset, and range queries on encrypted data, in: Theory of Cryptography: 4th Theory of Cryptography Conference, TCC 2007, Springer, Berlin, 2007, pp. 535–554. doi:10.1007/978-3-540-70936-7_29.
6.
E.F.Brickell, Some ideal secret sharing schemes, in: Advances in Cryptology – EUROCRYPT ’89: Workshop on the Theory and Application of Cryptographic Techniques, Springer, Berlin, 1990, pp. 468–475.
7.
M.Burkhart, Enabling collaborative network security with privacy-preserving data aggregation, PhD thesis, ETH, Zurich, 2011.
8.
M.Burkhart, M.Strasser, D.Many and X.Dimitropoulos, SEPIA: Privacy-preserving aggregation of multi-domain network events and statistics, in: Proceedings of the 19th USENIX Conference on Security, USENIX Association, 2010.
9.
R.Canetti, Security and composition of multi-party cryptographic protocols, Journal of Cryptology13(1) (2000), 143–202. doi:10.1007/s001459910006.
10.
I.Damgard, M.Fitzi, E.Kiltz, J.Nielsen and T.Toft, Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation, in: Theory of Cryptography: 3rd Theory of Cryptography Conference, TCC 2006, Springer, Berlin, 2006, pp. 285–304. doi:10.1007/11681878_15.
11.
E.De Cristofaro, A.Durussel and I.Aad, Reclaiming privacy for smartphone applications, in: IEEE International Conference on Pervasive Computing and Communications (PerCom), 2011, pp. 84–92.
12.
E.De Cristofaro and G.Tsudik, Practical private set intersection protocols with linear complexity, in: Financial Cryptography and Data Security: 14th International Conference, Springer, Berlin, 2010, pp. 143–159.
13.
F.Foerg, D.Mayer, S.Wetzel, S.Wueller and U.Meyer, A secure two-party bartering protocol using privacy-preserving interval operations, in: Twelfth Annual International Conference on Privacy, Security and Trust (PST), 2014, pp. 57–66.
14.
P.-A.Fouque, G.Poupard and J.Stern, Sharing decryption in the context of voting or lotteries, in: Financial Cryptography: 4th International Conference, Springer, Berlin, 2001, pp. 90–104. doi:10.1007/3-540-45472-1_7.
15.
M.J.Freedman, K.Nissim and B.Pinkas, Efficient private matching and set intersection, in: Advances in Cryptology – EUROCRYPT 2004: International Conference on the Theory and Applications of Cryptographic Techniques, Springer, Berlin, 2004, pp. 1–19. doi:10.1007/978-3-540-24676-3_1.
16.
O.Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, 2009.
17.
B.Hore, S.Mehrotra and G.Tsudik, A privacy-preserving index for range queries, in: Proceedings of the Thirtieth International Conference on Very Large Data Bases, VLDB Endowment, 2004, pp. 720–731.
18.
C.Jost, H.Lam, A.Maximov and B.Smeets, Encryption performance improvements of the Paillier cryptosystem, Report 2015/864, Cryptology ePrint Archive, 2015, available from: http://eprint.iacr.org/2015/864.
19.
J.Katz and Y.Lindell, Introduction to Modern Cryptography, Chapman & Hall/CRC, 2007.
20.
S.Laur, J.Willemson and B.Zhang, Round-efficient oblivious database manipulation, in: Information Security: 14th International Conference, ISC 2011, Springer, Berlin, 2011, pp. 262–277. doi:10.1007/978-3-642-24861-0_18.
21.
A.X.Liu and F.Chen, Collaborative enforcement of firewall policies in virtual private networks, in: Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing, ACM, 2008, pp. 95–104. doi:10.1145/1400751.1400766.
22.
M.E.Locasto, J.J.Parekh, A.Keromytis and S.J.Stolfo, Towards collaborative security and P2P intrusion detection, in: Proceedings from the Sixth Annual IEEE SMC Information Assurance Workshop, 2005, pp. 333–339. doi:10.1109/IAW.2005.1495971.
23.
D.Mayer, Design and implementation of efficient privacy-preserving and unbiased reconciliation protocols, PhD thesis, Stevens Institute of Technology, 2012.
24.
D.A.Mayer, D.Teubert, S.Wetzel and U.Meyer, Implementation and performance evaluation of privacy-preserving fair reconciliation protocols on ordered sets, in: Proceedings of the First ACM Conference on Data and Application Security and Privacy, ACM, 2011, pp. 109–120.
25.
A.E.Nergiz, M.E.Nergiz, T.Pedersen and C.Clifton, Practical and secure integer comparison and interval check, in: IEEE Second International Conference on Social Computing, 2010, pp. 791–799.
26.
G.Neugebauer, Design and implementation of efficient multi-party protocols for privacy-preserving reconciliation, PhD thesis, RWTH Aachen University, 2014.
27.
G.Neugebauer and U.Meyer, SMC-MuSe: A framework for secure multi-party computation on multisets, Technical Report AIB-2012-16, RWTH Aachen, 2012.
28.
T.Nishide and K.Ohta, Multiparty computation for interval, equality, and comparison without bit-decomposition protocol, in: Public Key Cryptography – PKC 2007: 10th International Conference on Practice and Theory in Public-Key Cryptography, Springer, Berlin, 2007, pp. 343–360. doi:10.1007/978-3-540-71677-8_23.
29.
NIST, SP 800-57 Part 1 Revision 3: Recommendation for key management, 2012.
30.
P.Paillier, Public-key cryptosystems based on composite degree residuosity classes, in: Advances in Cryptology – EUROCRYPT ’99: International Conference on the Theory and Application of Cryptographic Techniques, Springer, Berlin, 1999, pp. 223–238.
31.
A.Shamir, How to share a secret, Communications of the ACM22 (1979), 612–613. doi:10.1145/359168.359176.
32.
E.Shi, J.Bethencourt, T.-H.H.Chan, D.Song and A.Perrig, Multi-dimensional range query over encrypted data, in: IEEE Symposium on Security and Privacy, 2007, pp. 350–364.
33.
T.Veugen, F.Blom, S.J.A.de Hoogh and Z.Erkin, Secure comparison protocols in the semi-honest model, Journal of Selected Topics in Signal Processing9(7) (2015), 1217–1228. doi:10.1109/JSTSP.2015.2429117.
34.
L.Wang, Y.Li, D.Wijesekera and S.Jajodia, Precisely answering multi-dimensional range queries without privacy breaches, in: Computer Security – ESORICS 2003: 8th European Symposium on Research in Computer Security, Springer, Berlin, 2003, pp. 100–115. doi:10.1007/978-3-540-39650-5_6.
35.
S.Wueller, U.Meyer, F.Foerg, S.Wetzel and U.Meyer, Privacy-preserving conditional random selection, in: Thirteenth Annual Conference on Privacy, Security and Trust (PST), 2015, pp. 44–53.
36.
S.Wueller, U.Meyer, F.Foerg, S.Wetzel and U.Meyer, Privacy-preserving conditional random selection – Extended version, 2015.
37.
B.Zhang, Generic constant-round oblivious sorting algorithm for MPC, in: Provable Security: 5th International Conference, ProvSec 2011, Springer, Berlin, 2011, pp. 240–256. doi:10.1007/978-3-642-24316-5_17.
