On Locational Privacy in the Absence of Anonymous Payments

In this paper we deal with the situation that in certain contexts vendors have no incentive to implement anonymous payments or that existing regulation prevents complete customer anonymity. While the paper discusses the problem also in a general fashion, we use the recharging of electric vehicles using public charging infrastructure as a working example. Here, customers leave rather detailed movement trails, as they authenticate to charge and the whole process is post-paid, i.e., are billed after consumption. In an attempt to enforce transparency and give customers the information necessary to dispute a bill they deem inaccurate, Germany and other European countries require to retain the ID of the energy meter used in each charging process. Similar information is also retained in other applications, where Point of Sales terminals are used. While this happens in the customers’ best interest, this information is a location bound token, which compromises customers’ locational privacy and thus allows for the creation of rather detailed movement profiles. We adapt a carefully chosen group signature scheme to match these legal requirements and show how modern cryptographic methods can reunite the, in this case, conflicting requirements of transparency on the one hand and locational privacy on the other. In our solution, the user’s identity is explicitly known during a transaction, yet the user’s location is concealed, effectively hindering the creation of a movement profile based on financial transactions.

1. 1.

   Andrew J. Blumberg and Peter Eckersley, On Locational Privacy, and How to Avoid Losing it Forever, technical report (Electronic Frontier Foundation, 2009), accessed February 4, 2013, https://www.eff.org/wp/locational-privacy.

2. 2.

   E.g. David Chaum, “Security without identification: transaction systems to make big brother obsolete,” Commun. ACM 28, no. 10 (October 1985): 1030–1044, ISSN: 0001-0782, doi:10.1145/4372.4373, http://doi.acm.org/10.1145/4372.4373; David Chaum, Amos Fiat, and Moni Naor, “Untraceable Electronic Cash” in Advances in Cryptology—CRYPTO (1988); Stefan Brands, “Electronic cash systems based on the representation problem in groups of prime order” in CRYPTO (1993); Jan L. Camenisch, Jean-Marc Piveteau, and Markus A. Stadler, “An efficient electronic payment system protecting privacy,” in ESORICS (1994).

3. 3.

   David Chaum, “Blind Signatures for Untraceable Payments,” in Advances in Cryptology: Proceedings of CRYPTO ’82 (1982).

4. 4.

   Pike Research, Electric Vehicle Market Forecasts, http://www.pikeresearch.com/research/electric-vehicle-market-forecasts, 2013, accessed January 29, 2013.

5. 5.

   cars21.com, EU proposes minimum of 8 million EV charging points by 2020, http://beta.cars21.com/news/view/5171, 2013, accessed January 29, 2013.

6. 6.

   George Danezis, Roger Dingledine, and Nick Mathewson, “Mixminion: Design of a type III anonymous remailer protocol,” in IEEE Symposium on Security and Privacy, (2003).

7. 7.

   Ulf Möller et al., Mixmaster Protocol | Version 2, http://www.abditum.com/mixmaster-spec.txt, 2003.

8. 8.

   Roger Dingledine, Nick Mathewson, and Paul Syverson, “Tor: the second-generation onion router,” in 13th USENIX Security Symposium (2004).

9. 9.

   https://www.e-clearing.net/; http://www.hubject.com.

10. 10.

    David Chaum and Eugène van Heyst, “Group Signatures” in EUROCRYPT (1991), 257–265.

11. 11.

    We recall once again that user identities have to be known to the verifier for a proper billing process. Thus it is not possible to anonymize user identities in the bills.

12. 12.

    Cécile Delerable and David Pointcheval, “Dynamic Fully Anonymous Short Group Signatures" in VIETCRYPT (2006), 193–210.

13. 13.

    Dan Boneh, Xavier Boyen, and Hovav Shacham, “Short Group Signatures” in CRYPTO (2004), 41–55.

14. 14.

    Mihir Bellare, Haixia Shi, and Chong Zhang, “Foundations of Group Signatures: The Case of Dynamic Groups” in CT-RSA (2005), 136–153.

15. 15.

    Kitae Kim et al., “Batch Verification and Finding Invalid Signatures in a Group Signature Scheme,” I. J. Network Security 13, no. 2 (2011): 61–70.

16. 16.

    The batch verifier of Kim et al. uses the so-called small exponent test. Mihir Bellare, Juan A. Garay, and Tal Rabin, “Fast Batch Verification for Modular Exponentiation and Digital Signatures” in EUROCRYPT (1998), 236–250.

17. 17.

    Jan Camenisch and Anna Lysyanskaya, “Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials" in CRYPTO (2002), 61-76; Lan Nguyen, “Accumulators from Bilinear Pairings and Applications,” in CT-RSA (2005), 275–292.

18. 18.

    Boneh, Boyen, and Shacham, “Short Group Signatures.” in CRYPTO (2004).

19. 19.

    Moni Naor and Moti Yung, “Universal One-Way Hash Functions and their Cryptographic Applications,” in STOC (1989).

20. 20.

    Melissa Chase and Anna Lysyanskaya, “On Signatures of Knowledge,” in CRYPTO (2006), 78–96.

21. 21.

    Kim et al., “Batch Verification and Finding Invalid Signatures in a Group Signature Scheme”; Delerable and Pointcheval, “Dynamic Fully Anonymous Short Group Signatures.”

22. 22.

    Tibor Jager et al., “On the Security of TLS-DHE in the Standard Model” in Advances in Cryptology—CRYPTO (2012).

23. 23.

    Kim et al., “Batch Verification and Finding Invalid Signatures in a Group Signature Scheme”; Delerable and Pointcheval, “Dynamic Fully Anonymous Short Group Signatures.”

24. 24.

    http://iperf.sourceforge.net/.

25. 25.

    Chris Y.T. Ma et al., “Privacy vulnerability of published anonymous mobility traces,” in MobiCom ’10 (2010).

26. 26.

    Yves-Alexandre de Montjoye et al., “Unique in the Crowd: The privacy bounds of human mobility”, Scientific Reports, 2013, http://www.nature.com/srep/2013/130325/srep01376/full/srep01376.html

27. 27.

    John Krumm, “Inference Attacks on Location Tracks”, in Pervasive Computing (Pervasive 2007).

28. 28.

    Reza Shokri et al., “Quantifying Location Privacy,” in 2011 IEEE Symposium on Security and Privacy (SP) (May 2011), doi:10.1109/SP.2011.18

29. 29.

    Ian Jackson, “Anonymous addresses and confidentiality of location”, in Information Hiding (1996).

30. 30.

    Alastair R. Beresford and Frank Stajano, “Location privacy in pervasive computing”, IEEE Pervasive Computing 2, no. 1 (March 2003): 46–55, issn: 1536-1268, doi: 10.1109/MPRV.2003.1186725

31. 31.

    Raluca Ada Popa et al., “Privacy and accountability for location-based aggregate statistics”, in ACM CCS (2011).

32. 32.

    Jean-Pierre Hubaux, Srdjan Capkun, and Jun Luo, “The security and privacy of smart vehicles,” Security & Privacy, IEEE 2, no. 3 (2004): 49–55; Florian Dötzer, “Privacy Issues in Vehicular Ad Hoc Networks,” in Privacy Enhancing Technologies (2006); Julien Freudiger et al., “Mix-zones for location privacy in vehicular networks,” in Win-ITS (2007); K. Sampigethaya et al., “AMOEBA: Robust Location Privacy Scheme for VANET,” IEEE Journal on Selected Areas in Communications 25, no. 8 (October 2007): 1569–1589, issn: 0733-8716, doi: 10.1109/JSAC.2007.071007; Zhendong Ma, Location Privacy in Vehicular Communication Systems: a Measurement Approach (PhD thesis, University of Ulm, 2011).

33. 33.

    Thomas S. Heydt-Benjamin et al., “Privacy for Public Transportation", in Privacy Enhancing Technologies (2006); Erik-Oliver Blass et al., “PSP: private and secure payment with RFID,” in WPES (2009); Foteini Baldimtsi et al., “Pay as you go,” in HotPETs (2012).

34. 34.

    Josep Balasch et al., “PrETP: Privacy-Preserving Electronic Toll Pricing,” in 19th USENIX Security Symposium (2010).

35. 35.

    Sarah Meiklejohn et al., “The Phantom Tollbooth: Privacy-Preserving Electronic Toll Collection in the Presence of Driver Collusion,” in 20th USENIX Security Symposium (2011).

36. 36.

    Xihui Chen et al., “A Group Signature Based Electronic Toll Pricing System,” in ARES (2012).

37. 37.

    Raluca Ada Popa, Hari Balakrishnan, and Andrew Blumberg, “VPriv: protecting privacy in location-based vehicular services,” in USENIX Security Symposium (2009).

38. 38.

    Chao Li, Anonymous Payment Mechanisms for Electric Car Infrastructure, (master’s thesis, LU Leuven, 2011).

39. 39.

    Jan Camenisch, Susan Hohenberger, and Anna Lysyanskaya, “Compact E-Cash,” in Advances in Cryptology—EUROCRYPT (2005).

40. 40.

    Joseph Liu et al., “Enhancing Location Privacy for Electric Vehicles (at the right time),” in ESORICS (2012).

41. 41.

    Mark Stegelmann and Dogan Kesdogan, “Design and Evaluation of a Privacy-Preserving Architecture for Vehicle-to-Grid Interaction,” in EuroPKI (2012).

42. 42.

    https://gmplib.org/.

43. 43.

    https://crypto.stanford.edu/pbc/.

44. 44.

    https://code.google.com/p/gperftools/.

Authors and Affiliations

1. Horst Görtz Institute for IT-Security, Ruhr-University Bochum, Bochum, Germany

   Tilman Frosch, Sven Schäge, Martin Goll & Thorsten Holz

Corresponding author

Correspondence to Tilman Frosch .

Editors and Affiliations

1. Law, Science, Technology and Society (LSTS), Faculty of Law and Criminology, Vrije Universiteit Brussel, Brussels, Belgium

   Serge Gutwirth

2. Tilburg Institute for Law, Technology, and Society, Tilburg University, Tilburg, The Netherlands

   Ronald Leenes

3. Law, Science, Technology and Society, Faculty of Law and Criminology, Vrije Universiteit Brussel, Brussels, Belgium

   Paul De Hert

Appendix 1: Implementation Details

The current source code is a makefile project, written in C. We chose the language C, as the external routines and the libraries we rely on are also written in C, hence the whole project and its dependencies are written in one language. We implemented XSGS as a library. This XSGS library uses the GNU Multiple Precision Arithmetic Library1^{Footnote 42} for the basic arithmetic operations, the Pairing-Based Cryptography Library2^{Footnote 43} (PBC) for the curve and pairing-based arithmetic operations, the optimized reference implementation of the authors for the SHA3 hash algorithm (Keccak3) and the OpenSSL Library4 for RSA signature and certificate support.

At compile time one can choose between the TCMalloc Library^{Footnote 44} for a fast and multithreaded malloc() or the GNU C Library memory allocation, which will be linked to the XSGS library.

Appendix 2: Cryptographic Parameters

The PBC library defines a variety of pairing types, of which our XSGS implementation uses either type D, F, or G, respectively. The type can be chosen at compile time. The group order is ~300 bits, the curve parameters are as follows: r > = 160, q >=1024/k, k = 6 (type D) 12 (type F) 10 (type G).

Where Paillier’s operations are used, the modulus is of 1024 bit; RSA can by chose at compile time to use key lengths of either 1024, 2048, or 4096. The cryptographic hash function used throughout the XSGS implementation is the SHA3 contest winner Keccak with 256 bit hash length.

Reprints and permissions

© 2016 Springer Science+Busines Media Dordrecht

Policies and ethics