Private routing and ride-sharing using homomorphic encryption
- Author(s): Farhad Farokhi 1, 2 ; Iman Shames 2 ; Karl H. Johansson 3
-
-
View affiliations
-
Affiliations:
1:
CSIRO's Data61 , Docklands , Australia ;
2: Department of Electrical and Electronic Engineering at the University of Melbourne , Parkville , Australia ;
3: School of Electrical Engineering and Computer Science, KTH Royal Institute of Technology , Stockholm , Sweden
-
Affiliations:
1:
CSIRO's Data61 , Docklands , Australia ;
- Source:
Volume 5, Issue 4,
December
2020,
p.
311 – 320
DOI: 10.1049/iet-cps.2019.0042 , Online ISSN 2398-3396
- « Previous Article
- Table of contents
- Next Article »
A framework for private and secure communication and interaction between agents interacting in transportation services is developed. An agent, i.e. a user, can ask questions or submit queries regarding whether the other agents, i.e. drivers, use the desired road at specific times of the day in an encrypted fashion. The authors developed the framework using semi-homomorphic encryption (namely, the Paillier's encryption method) to enable the algebraic manipulation of plain data without the need for decryption using appropriate computations over the encrypted data. Strong privacy and security guarantees are proved for the agents. Subsequently, the semi-homomorphic encryption method is utilised to develop privacy-aware ride-sharing and routing algorithms without the need for disclosing the origin and destination of the user.
Inspec keywords: cryptography; driver information systems; vehicle routing; data privacy; symbol manipulation
Other keywords: privacy-aware ride-sharing; secure communication; homomorphic encryption; private routing; plain data; private communication; encrypted data; transportation services; algebraic manipulation; Paillier encryption method; queries; routing algorithms; security guarantees; semihomomorphic encryption method
Subjects: Cryptography; Traffic engineering computing; Data security
References
-
-
1)
-
56. Tran, J., Farokhi, F., Cantoni, M., et al: ‘Implementing homomorphic encryption based secure feedback control’, Control Eng. Pract., 2019. In Press.
-
-
2)
-
42. Cheon, J.H., Han, K., Hong, S.M., et al: ‘Toward a secure drone system: flying with real-time homomorphic authenticated encryption’, IEEE Access, 2018, 6, pp. 24325–24339.
-
-
3)
-
35. Aïvodji, U.M., Huguenin, K., Huguet, M.J., et al: ‘SRide: a privacy-preserving ridesharing system’. Proc. 11th ACM Conf. on Security & Privacy in Wireless and Mobile Networks, Stockholm, Sweeden, 2018, pp. 40–50.
-
-
4)
-
48. Kolesnikov, V., Schneider, T.: ‘Improved garbled circuit: free XOR gates and applications’. Int. Colloquium on Automata, Languages, and Programming, Reykjavik, Iceland, 2008, pp. 486–498.
-
-
5)
-
1. Besselink, B., Turri, V., van de Hoef, S.H., et al: ‘Cyber-physical control of road freight transport’, Proc. IEEE, 2016, 104, (5), pp. 1128–1141.
-
-
6)
-
5. Jaworski, P., Edwards, T., Moore, J., et al: ‘Cloud computing concept for intelligent transportation systems’. 2011 14th Int. IEEE Conf. on Intelligent Transportation Systems (ITSC), Washington, DC, USA., 2011, pp. 391–936.
-
-
7)
-
55. Dwork, C.: ‘Differential privacy: a survey of results’. Int. Conf. on Theory and Applications of Models of Computation, Xi'an, China, 2008, pp. 1–19.
-
-
8)
-
45. Yao, A.C.: ‘Protocols for secure computations’. 1982. 23rd Annual Symp. on Foundations of Computer Science (SFCS ’08), Chicago, Illinois, USA., 1982, pp. 160–164.
-
-
9)
-
2. Hoh, B., Gruteser, M., Herring, R., et al: ‘Virtual trip lines for distributed privacy-preserving traffic monitoring’. Proc. of the 6th Int. Conf. on Mobile Systems, Applications, and Services (MobiSys ’08), New York, NY, USA, 2008, pp. 15–28.
-
-
10)
-
52. Yi, X., Paulet, R., Bertino, E.: ‘Homomorphic encryption and applications’, ‘Springer briefs in computer science’ (Springer International Publishing, 2014).
-
-
11)
-
32. Rajendran, B., Pandey, A.K., Bindhumadhava, B.: ‘Secure and privacy preserving digital payment’. 2017 IEEE SmartWorld, Ubiquitous Intelligence & Computing, Advanced & Trusted Computed, Scalable Computing & Communications, Cloud & Big Data Computing, Internet of People and Smart City Innovation (SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI), 2017, pp. 1–5.
-
-
12)
-
22. Beresford, A.R., Stajano, F.: ‘Location privacy in pervasive computing’, IEEE Pervasive Comput., 2003, 2, (1), pp. 46–55.
-
-
13)
-
43. Damgård, I., Pastro, V., Smart, N., et al: ‘Multiparty computation from somewhat homomorphic encryption’. Advances in Cryptology (CRYPTO 2012), 2012, pp. 643–662.
-
-
14)
-
25. Kido, H., Yanagisawa, Y., Satoh, T.: ‘An anonymous communication technique using dummies for location-based services’. Proc. of Int. Conf. on Pervasive Services, Santorini, Greece, 2005, pp. 88–97.
-
-
15)
-
10. Kargl, F., Friedman, A., Boreli, R.: ‘Differential privacy in intelligent transportation systems’. Proc. of the Sixth ACM Conf. on Security and Privacy in Wireless and Mobile Networks, Budapest, Hungary, 2013, pp. 107–112.
-
-
16)
-
41. Alexandru, A.B., Pappas, G.J.: ‘Encrypted LQG using labeled homomorphic encryption’. Proc. 10th ACM/IEEE Int. Conf. on Cyber-Physical Systems, Montreal, Canada, 2019, pp. 129–140.
-
-
17)
-
29. Badsha, S., Yi, X., Khalil, I., et al: ‘Privacy preserving location recommendations’. Int. Conf. on Web Information Systems Engineering, Dubai, United Arab Emirates, 2017, pp. 502–516.
-
-
18)
-
7. Timpner, J., Schürmann, D., Wolf, L.: ‘Trustworthy parking communities: helping your neighbor to find a space’, IEEE Trans. Dependable Secur. Comput., 2016, 13, (1), pp. 120–132.
-
-
19)
-
30. Yang, S., Tang, S., Zhang, X.: ‘Privacy-preserving k nearest neighbor query with authentication on road networks’, J. Parallel Distrib. Comput., 2019, 134, pp. 25–36.
-
-
20)
-
37. Pagnin, E., Gunnarsson, G., Talebi, P., et al: ‘TOPPool: time-aware optimized privacy-preserving ridesharing’, Proc. Privacy Enhancing Technol., 2019, 2019, (4), pp. 93–111.
-
-
21)
-
38. Farokhi, F., Shames, I., Batterham, N.: ‘Secure and private cloud-based control using semi-homomorphic encryption’. Proc. Sixth IFAC Workshop on Distributed Estimation and Control in Networked Systems, Tokyo, Japan, 2016.
-
-
22)
-
53. Cormen, T.H., Leiserson, C.E., Rivest, R.L., et al: ‘Introduction to algorithms’ (MIT Press, USA., 2001).
-
-
23)
-
14. De-Montjoye, Y.A., Hidalgo, C.A., Verleysen, M., et al: ‘Unique in the crowd: the privacy bounds of human mobility’, Sci. Rep., 2013, 3, p. 1376.
-
-
24)
-
51. Paillier, P.: ‘Public-key cryptosystems based on composite degree residuosity classes’. Advances in Cryptology — 1999 Proc. Int. Conf. on the Theory and Application of Cryptographic Techniques (EUROCRYPT ’99), Prague, Czech Republic, 2–6 May 1999, pp. 223–238.
-
-
25)
-
31. Li, H., Dan, G., Borisov, N., et al: ‘Janus: privacy-preserving billing for dynamic charging of electric vehicles’ (University of Illinois at Urbana-Champaign, USA., 2019) Available at https://www.ideals.illinois.edu/handle/2142/104027.
-
-
26)
-
50. Farokhi, F., Shames, I., Johansson, K.H.: ‘Private and secure coordination of matchmaking for heavy-duty vehicle platooning’. Proc. IFAC World Congress, Toulouse, France, 2017.
-
-
27)
-
11. Canepa, E.S., Claudel, C.G.: ‘A framework for privacy and security analysis of probe-based traffic information systems’. Proc. Second ACM Int. Conf. on High Confidence Networked Systems, Philadelphia, Pennsylvania, USA., 2013, pp. 25–32.
-
-
28)
-
44. Gentry, C., Halevi, S., Smart, N.P.: ‘Homomorphic evaluation of the AES circuit’. Advances in Cryptology (CRYPTO 2012), 2012, pp. 850–867.
-
-
29)
-
17. Yi, X., Bertino, E.: ‘Private searching for single and conjunctive keywords on streaming data’. Proc. of the Tenth Annual ACM Workshop on Privacy in the Electronic Society, Chicago, Illinois, USA., 2011, pp. 153–158.
-
-
30)
-
13. Ogden, K.: ‘Privacy issues in electronic toll collection’, Transp Res C, Emerg Technol, 2001, 9, (2), pp. 123–134.
-
-
31)
-
16. Ostrovsky, R., Skeith, E.W.: ‘Private searching on streaming data’, J. Cryptol., 2007, 20, (4), pp. 397–430.
-
-
32)
-
60. Thierry, V.: ‘Handbook of mathematics’ (Books on Demand, Germany, 2015).
-
-
33)
-
28. Ardagna, C.A., Cremonini, M., di Vimercati, S.D.C., et al: ‘An obfuscation-based approach for protecting location privacy’, IEEE Trans. Dependable Secur. Comput., 2011, 8, (1), pp. 13–27.
-
-
34)
-
3. Fries, R.N., Gahrooei, M.R., Chowdhury, M., et al: ‘Meeting privacy challenges while advancing intelligent transportation systems’, Transp Res C, Emerg Technol, 2012, 25, pp. 34–45.
-
-
35)
-
59. Kamm, L., Willemson, J.: ‘Secure floating point arithmetic and private satellite collision analysis’, Int. J. Inf. Secur., 2015, 14, (6), pp. 531–548.
-
-
36)
-
4. Yu, R., Kang, J., Huang, X., et al: ‘Mixgroup: accumulative pseudonym exchanging for location privacy enhancement in vehicular social networks’, IEEE Trans. Dependable Secur. Comput., 2016, 13, (1), pp. 93–105.
-
-
37)
-
33. Aïvodji, U.M., Gambs, S., Huguet, M.J., et al: ‘Meeting points in ridesharing: a privacy-preserving approach’, Transp Res C, Emerg Technol, 2016, 72, pp. 239–253.
-
-
38)
-
57. Cavallar, S., Dodson, B., Lenstra, A., et al: ‘Factorization of RSA-140 using the number field sieve’. Int. Conf. Theory and Application of Cryptology and Information Security, Kobe, Japan, 1999, pp. 195–207.
-
-
39)
-
21. Myles, G., Friday, A., Davies, N.: ‘Preserving privacy in environments with location-based applications’, IEEE Pervasive Comput., 2003, 2, (1), pp. 56–64.
-
-
40)
-
40. Lin, Y., Farokhi, F., Shames, I., et al: ‘Secure control of nonlinear systems using semi-homomorphic encryption’. 2018 IEEE Conf. on Decision and Control (CDC), Miami Beach, FL, USA., 2018, pp. 5002–5007.
-
-
41)
-
39. Kogiso, K., Fujita, T.: ‘Cyber-security enhancement of networked control systems using homomorphic encryption’. Proc. 54th Annual Conf. on Decision and Control, Osaka, Japan, 2015, pp. 6836–6843.
-
-
42)
-
27. Kerschbaum, F., Lim, H.W., Gudymenko, I.: ‘Privacy-preserving billing for eticketing systems in public transportation’. Proc. 12th ACM Workshop on Privacy in the Electronic Society, Berlin, Germany, 2013, pp. 143–154.
-
-
43)
-
36. Hallgren, P., Orlandi, C., Sabelfeld, A.: ‘Privatepool: privacy-preserving ridesharing’. 2017 IEEE 30th Computer Security Foundations Symp. (CSF), Santa Barbara, CA, USA., 2017, pp. 276–291.
-
-
44)
-
34. Yu, H., Jia, X., Zhang, H., et al: ‘PSRide: privacy-preserving shared ride matching for online ride hailing systems’, IEEE Trans. Dependable Secur. Comput., 2019, DOI: 10.1109/TDSC.2019.2931295.
-
-
45)
-
15. Gao, J., Sun, L., Cai, M.: ‘Quantifying privacy vulnerability of individual mobility traces: a case study of license plate recognition data’, Transp Res C, Emerg Technol, 2019, 104, pp. 78–94.
-
-
46)
-
9. Cui, L., Xie, G., Qu, Y., et al: ‘Security and privacy in smart cities: challenges and opportunities’, IEEE Access, 2018, 6, pp. 46134–46145.
-
-
47)
-
18. Yi, X., Bertino, E., Vaidya, J., et al: ‘Private searching on streaming data based on keyword frequency’, IEEE Trans. Dependable Secur. Comput., 2014, 11, (2), pp. 155–167.
-
-
48)
-
12. Farokhi, F., Shames, I.: ‘Preserving privacy of agents in participatory-sensing schemes for traffic estimation’. Proc. 55th IEEE Conf. on Decision and Control, Las Vegas, NV, USA., 2016.
-
-
49)
-
58. Chaum, D., Crépeau, C., Damgard, I.: ‘Multiparty unconditionally secure protocols’. Proc. 20th Annual ACM Symp. on Theory of Computing, Chicago, Illinois, USA., 1988, pp. 11–19.
-
-
50)
-
49. Kreuter, B., Shelat, A., Shen, C.H.: ‘Billion-gate secure computation with malicious adversaries’. USENIX Security Symp., Bellevue, WA, USA., 2012, vol. 12, pp. 285–300.
-
-
51)
-
6. Hoh, B., Iwuchukwu, T., Jacobson, Q., et al: ‘Enhancing privacy and accuracy in probe vehicle-based traffic monitoring via virtual trip lines’, IEEE Trans. Mob. Comput., 2012, 11, (5), pp. 849–864.
-
-
52)
-
54. Even, S., Goldreich, O., Lempel, A.: ‘A randomized protocol for signing contracts’, Commun. ACM, 1985, 28, (6), pp. 637–647.
-
-
53)
-
23. Bamba, B., Liu, L., Pesti, P., et al: ‘Supporting anonymous location queries in mobile environments with privacygrid’. Proc. 17th Int. Conf. on World Wide Web, Beijing, China, 2008, pp. 237–246.
-
-
54)
-
20. Vora, A.V., Hegde, S.: ‘Keyword-based private searching on cloud data along with keyword association and dissociation using cuckoo filter’, Int. J. Inf. Secur., 2019, 18, (3), pp. 305–319.
-
-
55)
-
8. Troncoso, C., Danezis, G., Kosta, E., et al: ‘Pripayd: privacy-friendly pay-as-you-drive insurance’, IEEE Trans. Dependable Secur. Comput., 2011, 8, (5), pp. 742–755.
-
-
56)
-
19. Boneh, D., Waters, B.: ‘Conjunctive, subset, and range queries on encrypted data’. Proc. Fourth Theory of Cryptography Conf. (TCC 2007), Amsterdam, The Netherlands, 21–24 February 2007, pp. 535–554.
-
-
57)
-
47. Lindell, Y., Pinkas, B.: ‘An efficient protocol for secure two-party computation in the presence of malicious adversaries’. Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, Barcelona, Spain, 2007, pp. 52–78.
-
-
58)
-
46. Lindell, Y., Pinkas, B.: ‘A proof of security of Yao's protocol for two-party computation’, J. Cryptol., 2009, 22, (2), pp. 161–188.
-
-
59)
-
26. Paulet, R., Kaosar, M.G., Yi, X., et al: ‘Privacy-preserving and content-protecting location based queries’, IEEE Trans. Knowl. Data Eng., 2014, 26, (5), pp. 1200–1210.
-
-
60)
-
24. Yi, X., Paulet, R., Bertino, E.: ‘Nearest neighbor queries with location privacy’, ‘Homomorphic encryption and applications’ (Springer International Publishing, 2014), pp. 81–99.
-
-
1)

Related content
