Private Trajectory Intersection Testing: Is Garbled Circuit Better than Custom Protocols?

Document Type : Original Article

Authors

1 Department of Computer Engineering, Amirkabir University of Technology, Tehran, Iran

2 Department of Mechanical Engineering, Payame Noor University, Tehran, Iran

Abstract

In this paper, two protocols are presented for private intersection detection of two moving objects’ trajectories. Assuming that the movement trajectory of an object can be described by a time-dependent polynomial function, the problem of finding the intersection points is simplified to the problem of finding the common roots of the corresponding polynomials. Thereafter, GrÖbner Basis is used to design a novel secure protocol of finding the common roots of the polynomials. Another protocol is also designed based on the distance computation of two trajectories’ curves.
Moreover, we present the complexity analysis of the protocol for private trajectory intersection testing of two moving objects, which is based on GrÖbner Basis. Then, we compare its complexity by the garbled circuit-based protocol for Euclidean Distance Computation of l points. We also prove the security of our proposed protocol, which is based on the distance computation of two curves.
Keywords: Private Trajectory Intersection Testing, GrÖbner Basis, Distance Computation, Complexity , Garbled Circuit, Euclidean Distance

Keywords

References

1.     Asadi Saeed Abad, F., and Hamidi, H., "An Architecture for Security and Protection of Big Data", International Journal of Engineering - Transaction A: Basics, Vol. 30, No. 10, (2017), 1479–1486. doi:10.5829/ije.2017.30.10a.08
2.     Yao, A. C., "Protocols for secure computations", 23rd Annual Symposium on Foundations of Computer Science (Sfcs 1982), (1982), IEEE, 160–164. doi:10.1109/SFCS.1982.38
3.     Goldreich, O., Micali, S., and Wigderson, A., "How to play ANY mental game", Proceedings of the Nineteenth Annual ACM Conference on Theory of Computing - STOC ’87, (1987), 218–229. doi:10.1145/28395.28420
4.     Hemenway, B., Lu, S., Ostrovsky, R., and Welser IV, W., "High-Precision Secure Computation of Satellite Collision Probabilities", In International Conference on Security and Cryptography for Networks, Springer, Cham, (2016), 169–187. doi:10.1007/978-3-319-44618-9_9
5.     Atallah, M. J., and Du, W., "Secure Multi-party Computational Geometry", In Workshop on Algorithms and Data Structures, Springer, Berlin, Heidelberg, (2001), 165–179. doi:10.1007/3-540-44634-6_16
 
6.     Frikken, K. B., and Atallah, M. J., "Privacy preserving route planning", Proceedings of the 2004 ACM Workshop on Privacy in the Electronic Society - WPES ’04, (2004). doi:10.1145/1029179.1029182
7.     Cheng, R., Zhang, Y., Bertino, E., and Prabhakar, S., "Preserving User Location Privacy in Mobile Data Management Infrastructures", In International Workshop on Privacy Enhancing Technologies, Springer, Berlin, Heidelberg, (2006), 393–412. doi:10.1007/11957454_23
8.     Mascetti, S., Freni, D., Bettini, C., Wang, X. S., and Jajodia, S., "Privacy in geo-social networks: proximity notification with untrusted service providers and curious buddies", The VLDB Journal, Vol. 20, No. 4, (2011), 541–566. doi:10.1007/s00778-010-0213-7
9.     Zhu, H., Wang, F., Lu, R., Liu, F., Fu, G., and Li, H., "Efficient and Privacy-Preserving Proximity Detection Schemes for Social Applications", IEEE Internet of Things Journal, Vol. 5, No. 4, (2018), 2947–2957. doi:10.1109/JIOT.2017.2766701
10.   Zheng, Y., Li, M., Lou, W., and Hou, Y. T., "Location Based Handshake and Private Proximity Test with Location Tags", IEEE Transactions on Dependable and Secure Computing, Vol. 14, No. 4, (2017), 406–419. doi:10.1109/TDSC.2015.2472529
11.   Järvinen, K., Kiss, Á., Schneider, T., Tkachenko, O., and Yang, Z., "Faster Privacy-Preserving Location Proximity Schemes", In International Conference on Cryptology and Network Security,Springer, Cham, (2018), 3–22. doi:10.1007/978-3-030-00434-7_1
12.   Pagnin, E., Gunnarsson, G., Talebi, P., Orlandi, C., and Sabelfeld, A., "TOPPool: Time-aware Optimized Privacy-Preserving Ridesharing", Proceedings on Privacy Enhancing Technologies, Vol. 2019, No. 4, (2019), 93–111. doi:10.2478/popets-2019-0060
13.   Farokhi, F., Shames, I., and Johansson, K. H., "Private routing and ride‐sharing using homomorphic encryption", IET Cyber-Physical Systems: Theory & Applications, Vol. 5, No. 4, (2020), 311–320. doi:10.1049/iet-cps.2019.0042
14.   Oleynikov, I., Pagnin, E., and Sabelfeld, A., "Where Are You Bob? Privacy-Preserving Proximity Testing with a Napping Party", In European Symposium on Research in Computer Security, Springer, Cham, (2020), 677–697. doi:10.1007/978-3-030-58951-6_33
15.   Chor, B., Kushilevitz, E., Goldreich, O., and Sudan, M., "Private information retrieval", Journal of the ACM, Vol. 45, No. 6, (1998), 965–981. doi:10.1145/293347.293350
16.   Siksnys, L., Thomsen, J. R., Šaltenis, S., and Yiu, M. L., "Private and Flexible Proximity Detection in Mobile Social Networks", 2010 Eleventh International Conference on Mobile Data Management, (2010), IEEE, 75–84. doi:10.1109/MDM.2010.43
17.   Šikšnys, L., Thomsen, J. R., Šaltenis, S., Yiu, M. L., and Andersen, O., "A Location Privacy Aware Friend Locator", In International Symposium on Spatial and Temporal Databases, Springer, Berlin, Heidelberg., (2009), 405–410. doi:10.1007/978-3-642-02982-0_29
18.   Zhong, G., Goldberg, I., and Hengartner, U., "Louis, Lester and Pierre: Three Protocols for Location Privacy", In International Workshop on Privacy Enhancing Technologies, Springer, Berlin, Heidelberg, (2007), 62–76. doi:10.1007/978-3-540-75551-7_5
19.   Narayanan, A., Thiagarajan, N., Lakhani, M., Hamburg, M., and Boneh, D., "Location Privacy via Private Proximity Testing",  In NDSS, Vol. 11, (2011).
20.   Chatterjee, S., Karabina, K., and Menezes, A., "A New Protocol for the Nearby Friend Problem", In IMA International Conference on Cryptography and Coding, Springer, Berlin, Heidelberg, (2009), 236–251. doi:10.1007/978-3-642-10868-6_14
21.   Magkos, E., Kotzanikolaou, P., Magioladitis, M., Sioutas, S., and Verykios, V. S., "Towards Secure and Practical Location Privacy through Private Equality Testing", In International Conference on Privacy in Statistical Databases, Springer, Cham, (2014), 312–325. doi:10.1007/978-3-319-11257-2_24
22.   Kotzanikolaou, P., Patsakis, C., Magkos, E., and Korakakis, M., "Lightweight private proximity testing for geospatial social networks", Computer Communications, Vol. 73, (2016), 263–270. doi:10.1016/j.comcom.2015.07.017
23.   Šeděnka, J., and Gasti, P., "Privacy-preserving distance computation and proximity testing on earth, done right", Proceedings of the 9th ACM Symposium on Information, Computer and Communications Security, (2014), 99–110. doi:10.1145/2590296.2590307
24.   Dehghan, M., and Sadeghiyan, B., "Privacy‐preserving collision detection of moving objects", Transactions on Emerging Telecommunications Technologies, Vol. 30, No. 3, (2019), e3484. doi:10.1002/ett.3484
25.   Huang, Y., Evans, D., and Katz, J., "Private set intersection: Are garbled circuits better than custom protocols?", In 19th Network and Distributed Security Symposium, San Diego, (2012), 1–15.
26.   Bellare, M., Hoang, V. T., and Rogaway, P., "Foundations of garbled circuits", Proceedings of the 2012 ACM Conference on Computer and Communications Security - CCS ’12, (2012), 784–796. doi:10.1145/2382196.2382279
27.   Rabin, M. O., "How To Exchange Secrets with Oblivious Transfer", IACR Cryptol. EPrint Arch., (2005).
28.   Yao, A. C.-C., "How to generate and exchange secrets", 27th Annual Symposium on Foundations of Computer Science (Sfcs 1986), (1986), IEEE, 162–167. doi:10.1109/SFCS.1986.25
29.   Naor, M., and Pinkas, B., "Efficient oblivious transfer protocols", In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, Washington DC (Vol. 1), (2001), 448–457. doi:10.1145/365411.365502
30.   Ishai, Y., Kilian, J., Nissim, K., and Petrank, E., "Extending Oblivious Transfers Efficiently", In Annual International Cryptology Conference, Springer, Berlin, Heidelberg, (2003), 145–161. doi:10.1007/978-3-540-45146-4_9
31.   Lindell, Y., and Pinkas, B., "A Proof of Security of Yao’s Protocol for Two-Party Computation", Journal of Cryptology, Vol. 22, No. 2, (2009), 161–188. doi:10.1007/s00145-008-9036-8
32.   Cox, D. A., Little, J., and O’Shea, D., Ideals, Varieties, and Algorithms, Cham, Springer International Publishing, (2015). doi:10.1007/978-3-319-16721-3
33.   Li, R., and Wu, C., "An Unconditionally Secure Protocol for Multi-Party Set Intersection", In International Conference on Applied Cryptography and Network Security, Springer, Berlin, Heidelberg, (2007), 226–236. doi:10.1007/978-3-540-72738-5_15
34.   Zahur, S., Rosulek, M., and Evans, D., "Two Halves Make a Whole", In Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, Berlin, Heidelberg, (2015), 220–250. doi:10.1007/978-3-662-46803-6_8
35.   Pinkas, B., Schneider, T., Smart, N. P., and Williams, S. C., "Secure Two-Party Computation Is Practical", In International Conference on the Theory and Application of Cryptology and Information Security, Springer, Berlin, Heidelberg, (2009), 250–267. doi:10.1007/978-3-642-10366-7_15
36.   Kolesnikov, V., and Schneider, T., "Improved Garbled Circuit: Free XOR Gates and Applications", In International Colloquium on Automata, Languages, and Programming, Springer, Berlin, Heidelberg., (2008), 486–498 Berlin, Heidelberg, Springer Berlin Heidelberg. doi:10.1007/978-3-540-70583-3_40
37.   Kolesnikov, V., Mohassel, P., and Rosulek, M., "FleXOR: Flexible Garbling for XOR Gates That Beats Free-XOR", In Annual Cryptology Conference, Springer, Berlin, Heidelberg, (2014), 440–457. doi:10.1007/978-3-662-44381-1_25
International Journal of Engineering
Volume 34, Issue 4
TRANSACTIONS A: Basics
April 2021
Pages 863-872

Files

Cited by

Share

How to cite

Statistics