research-article

Public Access

P3: Privacy Preserving Positioning for Smart Automotive Systems

Authors:

Siam Umar Hussain,

Farinaz KoushanfarAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 23, Issue 6

Article No.: 79, Pages 1 - 19

https://doi.org/10.1145/3236625

Published: 28 November 2018 Publication History

Abstract

This article presents the first privacy-preserving localization method based on provably secure primitives for smart automotive systems. Using this method, a car that is lost due to unavailability of GPS can compute its location with assistance from three nearby cars, while the locations of all the participating cars including the lost car remain private. Technological enhancement of modern vehicles, especially in navigation and communication, necessitates parallel enhancement in security and privacy. Previous approaches to maintaining user location privacy suffered from one or more of the following drawbacks: trade-off between accuracy and privacy, one-sided privacy, and the need of a trusted third party that presents a single point to attack. The localization method presented here is one of the very first location-based services that eliminates all these drawbacks. Two protocols for computing the location is presented here based on two Secure Function Evaluation (SFE) techniques that allow multiple parties to jointly evaluate a function on inputs that are encrypted to maintain privacy. The first one is based on the two-party protocol named Yao’s Garbled Circuit (GC). The second one is based on the Beaver-Micali-Rogaway (BMR) protocol that allows inputs from more than two parties. The two secure localization protocols exhibit trade-offs between performance and resilience against collusion. Along with devising the protocols, we design and optimize netlists for the functions required for location computation by leveraging conventional logic synthesis tools with custom libraries optimized for SFE. Proof-of-concept implementation of the protocol shows that the complete operation can be performed within only 355ms. The fast computing time enables localization of even moving cars.

References

[1]

Mikhail Atallah and Wenliang Du. 2001. Secure multi-party computational geometry. In Algorithms and Data Structures. Springer, 165--179.

Digital Library

[2]

Paramvir Bahl and Venkata N. Padmanabhan. 2000. RADAR: An in-building RF-based user location and tracking system. In Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’00), Vol. 2. IEEE, 775--784.

[3]

Donald Beaver, Silvio Micali, and Phillip Rogaway. 1990. The round complexity of secure protocols. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing. ACM, 503--513.

Digital Library

[4]

Mihir Bellare, Viet Tung Hoang, Sriram Keelveedhi, and Phillip Rogaway. 2013. Efficient garbling from a fixed-key blockcipher. In Proceedings of the IEEE Symposium on Security and Privacy. IEEE, 478--492.

Digital Library

[5]

Aner Ben-Efraim, Yehuda Lindell, and Eran Omri. 2016. Optimizing semi-honest secure multiparty computation for the internet. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security. ACM, 578--590.

Digital Library

[6]

Alan Bensky. 2016. Wireless Positioning Technologies and Applications. Artech House.

Digital Library

[7]

Jan Blumenthal, Ralf Grossmann, Frank Golatowski, and Dirk Timmermann. 2007. Weighted centroid localization in zigbee-based sensor networks. In Proceedings of the IEEE International Symposium on Intelligent Signal Processing (WISP’07). IEEE, 1--6.

[8]

Michael Brenner, Henning Perl, and Matthew Smith. 2013. hcrypt SFE project. Retrieved from https://github.com/hcrypt-project/yao.

[9]

D. Brown, Geoffrey Cooper, Ian Gilvarry, Anand Rajan, Alan Tatourian, Ramnath Venugopalan, David Wheeler, and Meiyuan Zhao. 2015. Automotive security best practices. Retrieved from http://www.intel.com/content/www/us/en/automotive/automotive-security-best-practices-white-paper.html.

[10]

Reynold Cheng, Yu Zhang, Elisa Bertino, and Sunil Prabhakar. 2006. Preserving user location privacy in mobile data management infrastructures. In Lecture Notes in Computer Science, Vol. 4258. Springer, 393--412.

Digital Library

[11]

Chris Clifton, Murat Kantarcioglu, Jaideep Vaidya, Xiaodong Lin, and Michael Y. Zhu. 2002. Tools for privacy preserving distributed data mining. In Sigkdd Explorations Newsletter, Vol. 4. ACM, 28--34.

Digital Library

[12]

Gabriel Ghinita, Panos Kalnis, Ali Khoshgozaran, Cyrus Shahabi, and Kian-Lee Tan. 2008. Private queries in location-based services: Anonymizers are not necessary. In Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM, 121--132.

Digital Library

[13]

Lewis Girod, Vladimir Bychkovskiy, Jeremy Elson, and Deborah Estrin. 2002. Locating tiny sensors in time and space: A case study. In Proceedings of the IEEE International Conference on Computer Design: VLSI in Computers and Processors. IEEE, 214--219.

Digital Library

[14]

Bar Ilan Cryptography Research Group. 2016. Semi-Honest-BMR. Retrieved from https://github.com/cryptobiu/Semi-Honest-BMR.

[15]

Bar Ilan Cryptography Research Group. 2017. libscapi. Retrieved from https://github.com/cryptobiu/libscapi.

[16]

Marco Gruteser and Dirk Grunwald. 2003. Anonymous usage of location-based services through spatial and temporal cloaking. In Proceedings of the 1st International Conference on Mobile Systems, Applications and Services. ACM, 31--42.

Digital Library

[17]

Andy Harter, Andy Hopper, Pete Steggles, Andy Ward, and Paul Webster. 2002. The anatomy of a context-aware application. In Wireless Networks, Vol. 8. Springer-Verlag, New York, 187--197.

Digital Library

[18]

Y. Huang, D. Evans, and J. Katz. 2012. Private set intersection: Are garbled circuits better than custom protocols? In Proceedings of the Network and Distributed Security Symposium (NDSS’12).

[19]

Yan Huang and Roopa Vishwanathan. 2010. Privacy preserving group nearest neighbour queries in location-based services using cryptographic techniques. In Proceedings of the Global Telecommunications Conference (GLOBECOM’10). IEEE, 1--5.

[20]

Jean-Pierre Hubaux, Srdjan Capkun, and Jun Luo. 2004. The security and privacy of smart vehicles. In Proceedings of the IEEE Symposium on Security and Privacy, Vol. 2. IEEE, 49--55.

Digital Library

[21]

Siam U. Hussain and Farinaz Koushanfar. 2016. Privacy preserving localization for smart automotive systems. In Proceedings of the Design Automation Conference (DAC’16). ACM, 26--31.

Digital Library

[22]

Synopsys Inc. 2015. Design Compiler. Retrieved from https://www.synopsys.com/implementation-and-signoff/rtl-synthesis-test/dc-ultra.html.

[23]

Intel. 2015. Atom Processor E3845. Retrieved from ark.intel.com/products/78475.

[24]

Panos Kalnis, Gabriel Ghinita, Kyriakos Mouratidis, and Dimitris Papadias. 2007. Preventing location-based identity inference in anonymous spatial queries. In Transactions on Knowledge and Data Engineering, Vol. 19. IEEE, 1719--1733.

Digital Library

[25]

Ali Khoshgozaran and Cyrus Shahabi. 2007. Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy. In Advances in Spatial and Temporal Databases. Springer, 239--257.

Digital Library

[26]

Vladimir Kolesnikov and Thomas Schneider. 2008. Improved garbled circuit: Free XOR gates and applications. In Automata, Languages and Programming. Springer, 486--498.

Digital Library

[27]

Benjamin Kreuter, Abhi Shelat, Benjamin Mood, and Kevin RB Butler. 2013. PCF: A portable circuit format for scalable two-party secure computation. In Proceedings of the USENIX Security Symposium. USENIX, 321--336.

Digital Library

[28]

Paweł Kułakowski, Javier Vales-Alonso, Esteban Egea-López, Wiesław Ludwin, and Joan García-Haro. 2010. Angle-of-arrival localization based on antenna arrays for wireless sensor networks. In Computers 8 Electrical Engineering, Vol. 36. Elsevier, 1181--1186.

Digital Library

[29]

Moni Naor and Benny Pinkas. 2005. Computationally secure oblivious transfer. In Cryptology, Vol. 18. Springer, 1--35.

Digital Library

[30]

Moni Naor, Benny Pinkas, and Reuban Sumner. 1999. Privacy preserving auctions and mechanism design. In Proceedings of the 1st ACM Conference on Electronic Commerce. ACM, 129--139.

Digital Library

[31]

Panagiotis Papadimitratos, Levente Buttyan, Tamás Holczer, Elmar Schoch, Julien Freudiger, Maxim Raya, Zhendong Ma, Frank Kargl, Antonio Kung, and Jean-Pierre Hubaux. 2008. Secure vehicular communication systems: Design and architecture. In IEEE Communications Magazine, Vol. 46. IEEE.

Digital Library

[32]

Aanjhan Ranganathan, Nils Ole Tippenhauer, Boris Škorić, Dave Singelée, and Srdjan Čapkun. 2012. Design and implementation of a terrorist fraud resilient distance bounding system. In Proceedings of the European Symposium on Research in Computer Security. Springer, 415--432.

[33]

Kasper Bonne Rasmussen and Srdjan Capkun. 2010. Realization of RF distance bounding. In Proceedings of the USENIX Security Symposium. 389--402.

Digital Library

[34]

Peng Rong and Mihail L. Sichitiu. 2006. Angle of arrival localization for wireless sensor networks. In Proceedings of the IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON’06), Vol. 1. IEEE, 374--382.

[35]

Ye Shang, Zhigang Liu, Jinkuan Wang, and Xianda Xiao. 2012. Triangle and centroid localization algorithm based on distance compensation. In Proceedings of the International Conference on Information Science and Control Engineering. IET.

[36]

ITS Standards Fact Sheets. 2009. IEEE 1609—Family of Standards for Wireless Access in Vehicular Environments (WAVE). Retrieved from standards.its.dot.gov/factsheets/factsheet/80.

[37]

E. M. Songhori and S. U. Hussain. 2017. TinyGarble. Retrieved from https://github.com/siamumar/TinyGarbled.

[38]

Ebrahim M. Songhori, Siam U. Hussain, Ahmad-Reza Sadeghi, and Farinaz Koushanfar. 2015. Compacting privacy-preserving k-nearest neighbor search using logic synthesis. In Proceedings of the Design Automation Conference (DAC’15). ACM, 36--42.

Digital Library

[39]

Ebrahim M. Songhori, Siam U. Hussain, Ahmad-Reza Sadeghi, Thomas Schneider, and Farinaz Koushanfar. 2015. Tinygarble: Highly compressed and scalable sequential garbled circuits. In Proceedings of the IEEE Symposium on Security 8 Privacy. IEEE, 411--428.

Digital Library

[40]

U.S. Department of Defense. 2008. Global positioning system standard positioning service performance standard. Retrieved from https://www.gps.gov/technical/ps/2008-SPS-performance-standard.pdf.

[41]

Andrew Chi-Chih Yao. 1986. How to generate and exchange secrets. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science. IEEE, 162--167.

Digital Library

[42]

Samee Zahur, Mike Rosulek, and David Evans. 2015. Two halves make a whole: Reducing data transfer in garbled circuits using half gates. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 220--250.

[43]

Jijun Zhao, Qingwei Zhao, Zhihua Li, and Yunfei Liu. 2013. An improved weighted centroid localization algorithm based on difference of estimated distances for wireless sensor networks. In Telecommunication Systems, Vol. 53. Springer, 25--31.

Digital Library

[44]

Jungang Zheng, Chengdong Wu, Hao Chu, and Peng Ji. 2010. Localization algorithm based on RSSI and distance geometry constrain for wireless sensor network. In Proceedings of the International Conference on Electrical and Control Engineering. IEEE, 2836--2839.

Digital Library

[45]

Ge Zhong, Ian Goldberg, and Urs Hengartner. 2007. Louis, lester and pierre: Three protocols for location privacy. In Proceedings of the International Workshop on Privacy Enhancing Technologies. Springer, 62--76.

Digital Library

Cited By

Huang CLiu DYang ALu RShen X(2024)PPRP: Preserving Location Privacy for Range-Based Positioning in Mobile NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2024.336634023:10(9451-9468)Online publication date: Oct-2024
https://doi.org/10.1109/TMC.2024.3366340
Yuan YHuang YYuan Y(2023)PrSLoc: Sybil Attack Detection for Localization with Private Observers using Differential PrivacyComputers & Security10.1016/j.cose.2023.103289(103289)Online publication date: May-2023
https://doi.org/10.1016/j.cose.2023.103289
Yan ZQian XLiu SDeng R(2022)Privacy Protection in 5G Positioning and Location-based Services Based on SGXACM Transactions on Sensor Networks10.1145/351289218:3(1-19)Online publication date: 30-Aug-2022
https://dl.acm.org/doi/10.1145/3512892
Show More Cited By

Index Terms

P3: Privacy Preserving Positioning for Smart Automotive Systems
1. Security and privacy
  1. Security services
    1. Privacy-preserving protocols

Recommendations

Privacy preserving localization for smart automotive systems
DAC '16: Proceedings of the 53rd Annual Design Automation Conference

This paper presents the first provably secure localization method for smart automotive systems. Using this method, a lost car can compute its location with assistance from three nearby cars while the locations of all the participating cars including the ...
Two-Round MPC: Information-Theoretic and Black-Box
Theory of Cryptography
Abstract
We continue the study of protocols for secure multiparty computation (MPC) that require only two rounds of interaction. The recent works of Garg and Srinivasan (Eurocrypt 2018) and Benhamouda and Lin (Eurocrypt 2018) essentially settle the ...
Reducing Garbled Circuit Size While Preserving Circuit Gate Privacy
Progress in Cryptology - AFRICACRYPT 2024
Abstract
This paper investigates efficient and confidential circuit garbling techniques. The primary contribution of this research is the introduction of GPGRR2 (Gate Privacy preserving Garbled Row Reduction), a technique aimed at constructing garbled ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 23, Issue 6

Special Issue on Internet of Things System Performance, Reliability, and Security

November 2018

288 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/3291062

Editor:
Naehyuck Chang
Korea Advanced Institute of Science and Technology, Korea

Issue’s Table of Contents

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 28 November 2018

Accepted: 01 June 2018

Revised: 01 June 2018

Received: 01 October 2017

Published in TODAES Volume 23, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Office of Naval Research
National Science Foundation
Semiconductor Research Corporation
Multidisciplinary Research Program of the University Research Initiative

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
414
Total Downloads

Downloads (Last 12 months)86
Downloads (Last 6 weeks)13

Reflects downloads up to 23 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Huang CLiu DYang ALu RShen X(2024)PPRP: Preserving Location Privacy for Range-Based Positioning in Mobile NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2024.336634023:10(9451-9468)Online publication date: Oct-2024
https://doi.org/10.1109/TMC.2024.3366340
Yuan YHuang YYuan Y(2023)PrSLoc: Sybil Attack Detection for Localization with Private Observers using Differential PrivacyComputers & Security10.1016/j.cose.2023.103289(103289)Online publication date: May-2023
https://doi.org/10.1016/j.cose.2023.103289
Yan ZQian XLiu SDeng R(2022)Privacy Protection in 5G Positioning and Location-based Services Based on SGXACM Transactions on Sensor Networks10.1145/351289218:3(1-19)Online publication date: 30-Aug-2022
https://dl.acm.org/doi/10.1145/3512892
Liu SYan Z(2022)Efficient Privacy Protection Protocols for 5G-Enabled Positioning in Industrial IoTIEEE Internet of Things Journal10.1109/JIOT.2022.31611489:19(18527-18538)Online publication date: 1-Oct-2022
https://doi.org/10.1109/JIOT.2022.3161148
Walter JAbendroth B(2020)On the role of informational privacy in connected vehiclesTelematics and Informatics10.1016/j.tele.2020.10136149:COnline publication date: 1-Jul-2020
https://dl.acm.org/doi/10.1016/j.tele.2020.101361

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents