Top

Published in:

2018 | OriginalPaper | Chapter

Faster Privacy-Preserving Location Proximity Schemes

Authors : Kimmo Järvinen, Ágnes Kiss, Thomas Schneider, Oleksandr Tkachenko, Zheng Yang

Published in: Cryptology and Network Security

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In the last decade, location information became easily obtainable using off-the-shelf mobile devices. This gave a momentum to developing Location Based Services (LBSs) such as location proximity detection, which can be used to find friends or taxis nearby. LBSs can, however, be easily misused to track users, which draws attention to the need of protecting privacy of these users.

In this work, we address this issue by designing, implementing, and evaluating multiple algorithms for Privacy-Preserving Location Proximity (PPLP) that are based on different secure computation protocols. Our PPLP protocols are well-suited for different scenarios: for saving bandwidth, energy/computational power, or for faster runtimes. Furthermore, our algorithms have runtimes of a few milliseconds to hundreds of milliseconds and bandwidth of hundreds of bytes to one megabyte. In addition, the computationally most expensive parts of the PPLP computation can be precomputed in our protocols, such that the input-dependent online phase runs in just a few milliseconds.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

next chapter Computing Betweenness Centrality: An Efficient Privacy-Preserving Approach

https://www.eugdpr.org/.

https://github.com/herumi/mcl.

https://opensignal.com.

https://gsacom.com.

https://wifispc.com.

In the near future, today’s 4G mobile networks will be replaced by 5G, which will significantly reduce the average network latency (average expected latency in 5G networks is around 1 ms [18]). Therefore, in low-latency 5G networks \(\mathsf {ABY_{AY}}\) will potentially be most efficient (see Sect. 5.2).

Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer and extensions for faster secure computation. In: CCS, pp. 535–548. ACM (2013)

Atallah, M.J., Du, W.: Secure multi-party computational geometry. In: Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 2001. LNCS, vol. 2125, pp. 165–179. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44634-6_16CrossRef

Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: CCS (1993)

Bloom, B.H.: Space/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422–426 (1970)CrossRef

Boyar, J., Peralta, R., Pochuev, D.: On the multiplicative complexity of boolean functions over the basis (\(\wedge \), \(\oplus \), 1). TCS 235(1), 43–57 (2000)

Cheng, R., Zhang, Y., Bertino, E., Prabhakar, S.: Preserving user location privacy in mobile data management infrastructures. In: Danezis, G., Golle, P. (eds.) PETS 2006. LNCS, vol. 4258, pp. 393–412. Springer, Heidelberg (2006). https://doi.org/10.1007/11957454_23CrossRef

Damgard, I., Geisler, M., Kroigard, M.: A correction to ’efficient and secure comparison for on-line auctions’. IJACT 1(4), 323–324 (2009)MathSciNetCrossRef

Demmler, D., Schneider, T., Zohner, M.: ABY - a framework for efficient mixed-protocol secure two-party computation. In: NDSS (2015)

ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: CRYPTO (1984)

10.

Erkin, Z., Franz, M., Guajardo, J., Katzenbeisser, S., Lagendijk, I., Toft, T.: Privacy-preserving face recognition. In: Goldberg, I., Atallah, M.J. (eds.) PETS 2009. LNCS, vol. 5672, pp. 235–253. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03168-7_14CrossRef

11.

Finch, S.R.: Mathematical Constants, vol. 93. Cambridge University Press, Cambridge (2003)MATH

12.

Freni, D., Ruiz Vicente, C., Mascetti, S., Bettini, C., Jensen, C.S.: Preserving location and absence privacy in geo-social networks. In: CIKM (2010)

13.

El Gamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31(4), 469–472 (1985)MathSciNetCrossRef

14.

Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: STOC (1987)

15.

Hallgren, P.A.: Robust location privacy. Ph.D. thesis, Chalmers University of Technology (2017). http://www.cse.chalmers.se/research/group/security/pages/publications/perh-phd/phd-thesis.pdf

16.

Hallgren, P.A., Ochoa, M., Sabelfeld, A.: InnerCircle: a parallelizable decentralized privacy-preserving location proximity protocol. In: PST (2015)

17.

Hallgren, P.A., Orlandi, C., Sabelfeld, A.: PrivatePool: privacy-preserving ridesharing. In: CSF (2017)

18.

Johansson, N.A., Wang, Y.-P.E., Eriksson, E., Hessler, M.: Radio access for ultra-reliable and low-latency 5G communications. In: ICC Workshop (2015)

19.

Järvinen, K., Kiss, A., Schneider, T., Tkachenko, O., Yang, Z.: Faster privacy-preserving location proximity schemes. Cryptology ePrint Archive, Report 2018/694 (2018). http://ia.cr/2018/694

20.

Kolesnikov, V., Sadeghi, A.-R., Schneider, T.: Improved garbled circuit building blocks and applications to auctions and computing minima. In: Garay, J.A., Miyaji, A., Otsuka, A. (eds.) CANS 2009. LNCS, vol. 5888, pp. 1–20. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10433-6_1CrossRefMATH

21.

Kolesnikov, V., Schneider, T.: Improved garbled circuit: free XOR gates and applications. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5126, pp. 486–498. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-70583-3_40CrossRefMATH

22.

Li, M., Ruan, N., Qian, Q., Zhu, H., Liang, X., Yu, L.: SPFM: scalable and privacy-preserving friend matching in mobile cloud. IEEE IoT J. 4(2), 583–591 (2017)

23.

Menezes, A.J., Van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996)CrossRef

24.

Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: SODA, pp. 448–457. ACM/SIAM (2001)

25.

Narayanan, A., Thiagarajan, N., Lakhani, M., Hamburg, M., Boneh, D.: Location privacy via private proximity testing. In: NDSS (2011)

26.

Pagh, A., Pagh, R., Rao, S.S.: An optimal bloom filter replacement. In: SODA (2005)

27.

Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_16CrossRef

28.

Pohlig, S.C., Hellman, M.E.: An improved algorithm for computing logarithms over GF(p) and its cryptographic significance (corresp.). IEEE Trans. Inf. Theory 24(1), 106–110 (1978)CrossRef

29.

Šeděnka, J., Gasti, P.: Privacy-preserving distance computation and proximity testing on earth, done right. In: ASIACCS (2014)

30.

Šikšnys, L., Thomsen, J.R., Šaltenis, S., Yiu, M.L., Andersen, O.: A location privacy aware friend locator. In: Mamoulis, N., Seidl, T., Pedersen, T.B., Torp, K., Assent, I. (eds.) SSTD 2009. LNCS, vol. 5644, pp. 405–410. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02982-0_29CrossRef

31.

Siksnys, L., Thomsen, J.R., Saltenis, S., Yiu, M.L.: Private and flexible proximity detection in mobile social networks. In: MDM (2010)

32.

Yao, A.C.: Protocols for secure computations. In: SFCS (1982)

33.

Yu, W., Liu, Z., Chen, C., Yang, B., Guan, X.: Privacy-preserving design for emergency response scheduling system in medical social networks. Peer-to-Peer Netw. Appl. 10(2), 340–356 (2017)CrossRef

34.

Zahur, S., Rosulek, M., Evans, D.: Two halves make a whole. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 220–250. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_8CrossRefMATH

35.

Zheng, Y., Li, M., Lou, W., Hou, Y.T.: Location based handshake and private proximity test with location tags. IEEE Dependable Secure Comput. 14(4), 406–419 (2017)CrossRef

36.

Zhong, G., Goldberg, I., Hengartner, U.: Louis, lester and pierre: three protocols for location privacy. In: Borisov, N., Golle, P. (eds.) PET 2007. LNCS, vol. 4776, pp. 62–76. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-75551-7_5CrossRef

37.

Zhu, H., Wang, F., Lu, R., Liu, F., Fu, G., Li, H.: Efficient and privacy-preserving proximity detection schemes for social applications. IEEE Internet Things J. 5(4), 2947–2957 (2018). https://ieeexplore.ieee.org/document/8085131/CrossRef

Title: Faster Privacy-Preserving Location Proximity Schemes
Authors: Kimmo Järvinen
Ágnes Kiss
Thomas Schneider
Oleksandr Tkachenko
Zheng Yang
Publisher: Springer International Publishing
Book: Cryptology and Network Security
Print ISBN: 978-3-030-00433-0

Electronic ISBN: 978-3-030-00434-7

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-030-00434-7_1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner