Petr Dzurenda

Florian Jacques

Manon Knockaert

Maryline Laurent

) Lukas

Raimundas Matulevičius

Qiang Tang

Aimilia Tasidou

Privacy-Preserving Solution for Vehicle Parking Services Complying with EU Legislation

Nowadays, a lot of modern cities adopt online smart parking services as best practices. Citizens can easily access these services using their smartphones or the infotainment panels in their cars. These services' primary objective is to give drivers the ability to quickly identify free parking slots, which should reduce parking time, save fuel, and relieve traffic in urban areas. However, the privacy offered by these services should be comparable to that of the standard paper-based parking solutions offered by parking ticket machines. On the other hand, a privacy-preserving smart parking service's design may raise a number of issues, including how to prevent double or multiple uses of parking tickets, how to prevent user tracking and profiling, how to revoke malicious users, how to handle data statistics without violating users' privacy, and how to comply with regulations like the General Data Protection Regulation (GDPR). In this article, we present multidisciplinary research on a comprehensive vehicle parking system that protects users' privacy. The research includes a range of topics, from the examination of regulatory compliance to the design of privacy-preserving parking registration and vehicle parking services to the implementation of privacy-preserving parking data processing features for data analysts. We provide a security analysis of our concept as well as several experimental results.

Introduction

In future smart cities, smart parking solutions will be more and more integrated with city services and used by numerous citizens via their smartphones or infotainment panels in their vehicles. The main goal of smart parking services is to provide drivers the efficient detection of vacant slots that should shorten the time during parking, save fuel and decrease congestion in cities. Parking in city streets and parking lots is usually for specific fees according to different zones, periods, and daily times. Therefore, parking services usually have to collect these fees from users. Using parking lot terminals with tollgates should help with a payment collection, and only users who paid for the service should get access to the parking lots. Nevertheless, using prepayment and intelligent detection of free slots via mobile applications causes that users have to interact remotely with a smart parking system in advance. These systems should ideally provide a similar level of privacy as the traditional paper-based parking solutions with parking ticket machines. The design of a privacy-preserving smart parking service may open several issues such as how to prevent double/multiple spending of parking tickets, how to prevent user tracking and linking, how to revoke malicious users, how to handle data statistics without privacy breaches and how to be compliant with regulations such as General Data Protection Regulation (GDPR).

In this paper, we proposed a novel privacy-preserving solution for vehicle parking services which is complying with European Union (EU) legislation, especially with privacy and security requirements defined by current regulations and directives. The system protects users' privacy and their digital identities. Furthermore, it also allows third parties such as research institutions to run statistical analyses on parking data. This analysis can be done without impacting the privacy of both, i.e. users (no personal data or linkable information about users are disclosed) and analysts (no information about what they are searching for is revealed). To do so, we had to answer three main Research Questions (RQ):

• RQ1: What are the legal instruments, issues, and requirements for the deployment of such a system?

• RQ2: How to build a privacy-preserving system which meets the requirements from RQ1? Which Privacy-Enhancing Technology (PET) can be used in order to protect users' privacy during using the system, i.e., reservation of parking slots and parking vehicle actions?

• RQ3: How to allow third parties to perform statistical analyses on the parking transaction data, in a privacy preserving way? Which PET can be used to support this task?

The paper is organized as follows. Section 1 analyzes the recent research on security and privacy in smart cities with a focus on parking service applications. Section 2 introduces a high-level architecture description of our parking system, security and privacy requirements. Section 3 presents the different legal instruments relevant for the deployment of vehicle parking systems. Section 4 outlines the used notation needed to understand the cryptographic design of our parking system. Section 5 introduces our privacy-preserving parking system, its security analysis, and experiment results. Section 6 presents our solution for privacy-preserving parking data processing, its security analysis, and experimental results. In Section 7, we conclude this work.

Related Work

In many existing works, smart parking services are usually considered as the part of smart cities or intelligent infrastructures. There are several works that deal with general security and privacy issues in smart cities and deal partially with parking services, such as [START_REF] Martınez-Ballesté | The pursuit of citizens' privacy: a privacy-aware smart city is possible[END_REF][START_REF] Al-Turjman | Smart parking in IoT-enabled cities: A survey[END_REF][START_REF] Al-Turjman | An overview of security and privacy in smart cities' IoT communications[END_REF][START_REF] Indra | Smart Parking in Smart Cities Using Secure IoT[END_REF]. Further, privacy-preserving smart parking solutions and parking related problems in cities have been introduced in recent works such as [START_REF] Garra | A privacy-preserving pay-by-phone parking system[END_REF], [START_REF] Chatzigiannakis | A privacy-preserving smart parking system using an IoT elliptic curve based security platform[END_REF], [START_REF] Huang | Secure Automated Valet Parking: A Privacy-Preserving Reservation Scheme for Autonomous Vehicles[END_REF], [START_REF] Zhu | ASAP: An anonymous smart-parking and payment scheme in vehicular networks[END_REF], [START_REF] Borges | Parking tickets for privacy-preserving pay-by-phone parking[END_REF], [START_REF] Al | Privacy-preserving smart parking system using blockchain and private information retrieval[END_REF], [START_REF] Fang | Blockchain-based privacy-preserving valet parking for self-driving vehicles[END_REF], [START_REF] Dzurenda | Privacy-Preserving Online Parking Based on Smart Contracts[END_REF] and [START_REF] Khalid | From smart parking towards autonomous valet parking: A survey, challenges and future Works[END_REF].

For example, [START_REF] Garra | A privacy-preserving pay-by-phone parking system[END_REF] proposed a practical privacy-preserving pay-by-phone parking system based on periodical e-coin micro-payments for short intervals. The proposal deploys Hash-Based Message Authentication Codes (HMAC), RSA signatures, Chaum's blinded signatures based on RSA introduced in [START_REF] Chaum | Blind signatures for untraceable payments[END_REF] and ECDSA signatures. The drawback of the proposal can be technical issues such as lack of coverage, low battery, etc.

In [START_REF] Borges | Parking tickets for privacy-preserving pay-by-phone parking[END_REF], the authors claimed that it has solved these technical disadvantages in their proposal of a privacy-preserving pay-by-mobile parking system. Their e-coin based proposal offered the same privacy as the traditional paper-based approach. Users' privacy is preserved without requiring a trusted party. The proposal deploys the Chaum's blinded signatures based on RSA and DSA. Later, [START_REF] Borges | An efficient privacy-preserving payby-phone system for regulated parking areas[END_REF] presented an upgraded and more efficient solution than in [START_REF] Borges | Parking tickets for privacy-preserving pay-by-phone parking[END_REF]. Nevertheless, both solutions digitally collect also car plate numbers (licenses) by parking officers.

[16] investigated privacy-preserving smart parking systems using IoT platform. They adopted Elliptic Curve Cryptography (ECC) as an attractive alternative to RSA-based solutions. They showed how to deploy zero-knowledge proofs (ZKP) using ECC that should preserve users' privacy. Moreover, they created a real-world outdoor IoT testbed and analyzed the execution time on various IoT platforms. Their work did not provide a tailored proposal but offered interesting practical results. [START_REF] Huang | Secure Automated Valet Parking: A Privacy-Preserving Reservation Scheme for Autonomous Vehicles[END_REF] presented a secure and privacy-preserving reservation/parking solution for automated valet parking systems without a trusted third party. Their solution is based on zero-knowledge proofs proposed by [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF], geo-indistinguishable mechanism published in [START_REF] Andrés | Geo-indistinguishability: Differential privacy for location-based systems[END_REF], proxy re-signatures designed by [START_REF] Libert | Multi-use unidirectional proxy resignatures[END_REF], and bloom filter data structure. Their parking reservation costs almost 3 seconds due to deploying the heavy cryptographic operations. [START_REF] Zhu | ASAP: An anonymous smart-parking and payment scheme in vehicular networks[END_REF] focused on smart parking in cities and presented the anonymous smart-parking and payment scheme in vehicular networks. Their solution is based on the Pointcheval-Sanders random-izable signature designed by [START_REF] Pointcheval | Short randomizable signatures[END_REF] and using a trusted authority. For generating a parking query, one driver has to compute several exponentiations, multiplications, additions, and hash.

[2] presented a privacy-preserving smart parking system using blockchain and private information retrieval. A shared ledger should increase security, transparency, and availability. The system preserves drivers' location privacy by using the private information retrieval of parking offers from the blockchain nodes and deploying short randomizable signatures proposed in [START_REF] Pointcheval | Short randomizable signatures[END_REF] allow drivers to anonymously reserve available parking slots. The reservation time is around 1 ms at 1.2 GHz Processor with 160-bits MNT curve and SHA-2. Similarly, [START_REF] Fang | Blockchain-based privacy-preserving valet parking for self-driving vehicles[END_REF] presented a blockchain-based privacy-preserving valet parking protocol. The solution is based on a new variant of Pointcheval-Sanders group signature, and it is secure in the random oracle model. Blockchain-based privacy-preserving decentralized parking recommendation solutions has been also proposed by [START_REF] Li | PriParkRec: Privacy-preserving decentralized parking recommendation service[END_REF]. Their solution employs a private blockchain, a bulletin board, a re-randomized homomorphic encryption scheme, zero-knowledge protocols and oblivious pseudorandom functions. Recently, [START_REF] Dzurenda | Privacy-Preserving Online Parking Based on Smart Contracts[END_REF] have proposed the privacy-preserving online parking system based on blockchain and smart contracts. The system deploys provable secure cryptographic primitives such as revocable anonymous credential proposed in [START_REF] Hajný | Privacy ABCs: Now Ready for Your Wallets![END_REF] and partially blinded signature proposed in [START_REF] Abe | Provably secure partially blind signatures[END_REF]. The system provides a full set of privacy-enhancing features such as user anonymity, untraceability, and unlinkability. Furthermore, the authors involve blockchain and smart contracts technologies in the payment and verification phases to make the system more transparent, decentralized, and resistant against cyberattacks.

The complex taxonomy of smart parking and autonomous valet parking solutions has been presented in the recent survey by [START_REF] Khalid | From smart parking towards autonomous valet parking: A survey, challenges and future Works[END_REF]. This survey studies many aspects of parking solutions, where security and data privacy processing have been detected as ones from challenges and future directions.

Few related works have also studied legal challenges and regulations in smart cities and parking services. For example, [START_REF] Weber | A regulatory view on smart city services[END_REF] provides a regulatory view on smart city services where smart parking systems are integrated, and [START_REF] Michael | The Internet of Things and the Smart City: Legal challenges with digital forensics, privacy, and security[END_REF] deals with legal challenges in smart cities. Nevertheless, a detailed study focusing on the regulation requirements of smart parking systems is still missing.

In this paper, we focus on a complex spectrum of problems in privacypreserving smart parking including legal and technical perspectives in order to cover various layers (authentication, secure communication, data processing, and other aspects). Our multidisciplinary work presents a comprehensive privacy-preserving proposal for parking services that covers privacy-preserving parking requests, privacy-preserving data statistics, regulation compliance, and other privacy issues related to communication and system settings.

Parking Scenario Description

In this section, we present a high-level system architecture, and we define the system entities, the parking scenario phases, and the privacy and security re-quirements.

System Architecture

Three types of entities interact in our privacy-preserving vehicle parking system:

• Parking Service Provider (PSP): The PSP generates cryptographic parameters and keys. It also registers new users and revokes/identifies the malicious ones. Furthermore, the PSP mediates communication between users and the PLT and enrolls new PLTs in the system. The communication with the PSP takes place fully via an Internet connection. We assume that the PSP is a semi-trusted party which honestly runs the algorithms but could be curious.

• Parking Lot Terminal (PLT): The PLT represents the system controlling access to the specific parking lot. It is responsible for issuing the parking permits to users and verifying the presented parking permits by users. The communication with the PSP takes place via an Internet connection during the parking permit issue phase (reservation parking in the parking lot) and via Bluetooth connection during the parking permit verification phase (accessing the parking lot).

• User Device: The user is represented by its device, typically a smartphone. These devices allow storing users' parking permits issued by the PLT through the PSP and presenting these permits to the PLT when users access the parking lot. Furthermore, this device holds system parameters, generates and stores user cryptographic keys, communicates with PSP via Internet connection (i.e., Wi-Fi, Long Term Evolution (LTE)) and with PLT via the Bluetooth Low Energy (BLE) interface.

The privacy-preserving parking system with all involved entities and protocols is depicted in Figure 1. The proposal also involves a trusted third party -IDentity Provider (IDP) that manages user identity and associated identity attributes.

Trust Assumptions

We assume that communication between all communication parties is secured. In particular, the communication between users and the PSP and the communication between the PSP and PLTs is secured by Transport Layer Security (TLS) protocol. The whole system is based on a trust chain, i.e., we expect the existence of Public Key Infrastructure (PKI) and trusted certification authorities. Besides the privacy-enhancing protocols used in our parking system in each scenario phase described in Section 5.1, we need to consider also other privacy issues which can impact users privacy:

• Anonymous Payment Methods: The payment to PLT can be done privately by deploying the improved e-payment 3D-Secure protocol [START_REF] Plateaux | An e-payment architecture ensuring a high level of privacy protection[END_REF] or by using popular wallets on mobile devices that support privacy-preserving cryptocurrencies, i.e., Monero [START_REF] Noether | Ring SIgnature Confidential Transactions for Monero[END_REF], Zcash [START_REF] Kappos | An empirical analysis of anonymity in zcash[END_REF], and DASH [START_REF] Duffield | Dash: A privacycentric cryptocurrency[END_REF]. The security and privacy of popular Android wallets have been studied in [START_REF] Biryukov | Security and privacy of mobile wallet users in Bitcoin, Dash, Monero, and Zcash[END_REF].

• Anonymous Communications in Wide Area Network (WAN):

Privacy-preserving communication in WAN can be achieved by mature onion routing protocols and techniques such as ToR [START_REF] Dingledine | Tor: The secondgeneration onion router[END_REF]. Then, users are able to privately communicate with PSP via Internet during their registration and issuing parking permit. On one hand, users' source addresses and actual locations are hidden to PSP and observers because the ToR protocol applies at least 3 randomly-selected servers (onion routers) as relays and encrypts the communication (creating the onion layers). On the other hand, communication via ToR can cause delays due to encryption operations and using more hops.

• Anonymous Communications in Personal Area Network (PAN):

For PAN, one typical technology is Bluetooth Low Energy (BLE). By design, BLE provides a reasonable level of privacy protection with features like address randomization [START_REF] Cäsar | A survey on Bluetooth Low Energy security and privacy[END_REF] and it has been widely used in contact tracing for COVID-19, e.g., [START_REF] Tang | Another Look at Privacy-Preserving Automated Contact Tracing[END_REF]. Therefore, we can assume that BLE provides a sufficient level of anonymity/privacy guarantee in our application.

• Surveillance Minimization: Surveillance security systems with cameras are usually deployed in parking lots and garages in order to increase security against various physical attacks, vandalism, and thefts. Moreover, some solutions are based on using Automatic Number Plate Recognition (ANPR) or Licence Plate Recognition (LPR) to detect concrete vehicles that prepaid a service. Nevertheless, these camera systems could conflict with users' privacy and GDPR. Thus, it is necessary to use records and basic functionality of ANPR only for security purposes and not to store records for longer periods or non-permitted tracking.

Scenario Phases

Our parking scenario consists of the following phases:

1. Register user phase: The digital identity of the user is created in this phase, as illustrated in Figure 2. First, the users download the mobile application of the parking system, e.g., using Google Play (see, 1.1. Download mobile parking application). Second, the users use the application to create their own digital identity in the parking system. To do so, we suggest involving a trusted third party that will manage user identity and associated identity attributes (see, 1.2. Create digital identity (through trusted third party)). This party is called IDentity Provider (IDP). Thanks to using the IDP, we do not need to store sensitive user data, such as name, surname, address, age, gender. Otherwise, these data can directly identify the user and can be a target of cyberattacks. Therefore, we suggest to deploy one from these following methods to create a digital identity in the parking system: • Payment card binding: The users have to add their bank cards to the parking application. The PSP does a pre-authorization charge to make sure the payment card used by the user is valid. If so, the PSP will create the digital identity of the user. The digital identity is represented by the payment card number provided by the user. The PSP learns no more information about the user. If the user commits fraud, the PSP will query disclosing the user identity to the bank that issued the payment card.

• Mobile number binding: The users have to add their phone number to the parking application. The PSP sends an authorization code to this phone number to make sure the phone number provided by the user is valid. If so, the PSP will create the digital identity of the user. The digital identity is represented by the phone number provided by the user. The PSP learns no more information about the user. If the user commits fraud, the PSP will query disclosing the user identity to the mobile operator. In this case, it is necessary to have a registered telephone number, such as in some European Union (EU) countries. For example, all SIM cards in Spain need to be registered by law.

• Electronic identification (eID) binding: The user has to use trusted Identity Provider (IDP) supported by the PSP and according to the EU electronic identification and trust services (eIDAS) Regulation. For example, in the Czech Republic, we can find the eObčanka application. The PSP learns no more information about the user. If the user commits fraud, the PSP will query disclosing the user identity to the organization delivering public digital services in an EU member state.

When the digital identity of the user is created, the PSP runs the Register algorithm (see, 1.3. Register user ). In particular, the PSP generates the user access credential Λ and user secret key sk U . To do so, the PSP will use group signature [START_REF] Hajny | Anonymous Data Collection Scheme from Short Group Signatures[END_REF]. The credential and the secret key are sent to the user's device (see, 1.4.Send user credentials) where they are securely stored (see, 1.5. Store credentials and secret key). Furthermore, the secret key is also stored in the PSP Revocation Database (RD) (see, 1.6. Store secret key). The PSP can use this database to revoke or identify malicious users. The user revocation is possible only in collaboration with the PLT. The user identification requires also the involvement of IDP.

Issue parking permit phase:

The parking reservation is made through the PSP. The PSP acts as a gateway between the user and the PLT, as illustrated in Figure 3. The PSP does not interfere with the Issue algorithm. It only forwards the communication between communicating parties. The Issue algorithm is run between the user device and the PLT. First, the user sends a parking request to the PLT (see, 2.1. Send parking request). Basically, this information is where, when, and for how long the user wants to park. No sensitive, personal, or other linkable data are provided. This information is sent in a clear way, and therefore both the PSP and the PLT know them. Furthermore, the reservation request also includes the user access credential Λ issued by the PSP. This credential is blinded, and therefore, the PSP nor PLT can learn it in this phase. Additionally, the access credential Λ is randomized with a session credential key sk Cred . This key is generated by the user for each new reservation phase, and therefore, it differs for all user's parking permits. Second, af-ter the payment for the parking is done (see, 2.3. Perform payment), the PLT generates parking permit ID (see, 2.5. Generate parking permit) and computes a partially blind signature [START_REF] Abe | Provably secure partially blind signatures[END_REF] on parking request data (both, clear and blind information) and sends it to the user (see, 2.6. Send parking permit). The user uses the partially blind signature from the PLT to reconstruct the parking permit CRED. The PSP and the PLT do not see the whole parking permit. They see only its public data, i.e. parking permit ID (PPID), parking location (PLTid), parking time (time duration) and information about parking time extension (EPT).

Figure 3: Issue parking permit.

Park vehicle phase:

The user accesses the parking lot in this phase as illustrated in Figure 4. To get access, the user must authenticate to the PLT first (see, 3.1. Authenticate and 3.2. Confirm). During the parking vehicle phase, the user communicates directly with the PLT, for example, via a Bluetooth communication interface. First, the user sends the parking permit to the PLT (see, 3.3. Send parking permit). The PLT checks the parking permit data and verifies the signature on the permit using PLT's public key pk P LT (see, 3.4. Verify signature). If the parking permit is valid, the users must prove that the parking permit belongs to them (see, 3.5. Check user authentication proof ), i.e., the permit includes the access credential Λ issued by the PSP and randomized by the user with the credential key sk Cred . To do so, the user and the PLT run the Verify algorithm. The PLT checks the user's authentication proof using PSP's public key pk P SP . If the proof is valid, the user is allowed to access the parking lot and the barrier is opened (see, 3.6. Allow vehicle to enter and Enter PLT and park vehicle). The parking permit includes user access credential Λ which can be used for linking the parking permit to the real identity of the user. However, this access credential is randomized with different credential keys in all issued user's parking permits. Therefore, the PLT cannot link two different parking permits to the one user, and therefore, the user access parking lot anonymously and unlinkably. This prevents the possibility of profiling and tracking users across the system. The PLT is not able to get any information on how often users park their vehicles in the parking lot. Issue parking permit and Figure 3). The Issue algorithm is run after the payment for the extended parking time is made.

Privacy and Security Requirements

This section introduces general security and privacy requirements on the parking reservation system. In particular, we have the following system security requirements:

• Authentication: Parking permits from PSP should be granted only to valid non-revoked users who use them in the parking phase. The users should stay in anonymity but should prove that they hold valid parking permits (based on reservation) to PLT when the user arrives at a parking lot.

• Data confidentiality: All sensitive and personal data, e.g., Vehicle Plate Number (VPN) or vehicle IDs, should be secured. Data eavesdropping and exposure should be prevented by data encryption. The system should not reveal any sensitive personal data during issuing the parking permit and the park vehicle phase.

• Data authenticity and integrity: All exchanged data (e.g., parking permits, information about available slots, notifications) should be secured against their tampering by unauthorized parties.

Furthermore, we identify the following system privacy requirements:

• Data privacy: All stored and exchanged data should not be exposed to undesired parties and eavesdroppers, e.g., user's vehicle ID, user parking history, and user profiles.

• Pseudonymity: A user should be pseudonymous and should be identifiable only in case of certain conditions by PSP. Users should not be identifiable while using the parking system by external and internal parties (PLTs) or other users.

• Unlinkability: PSP, PLTs, and other users should not be able to link together the parking actions of the same user (vehicle). The system should not scan VPNs.

• Conditional traceability: PSP should not be able to trace users' credentials and their parking actions if the users are honest. PSP should be able to open a user's identity from the parking permit only in case of serious fraud and by cooperation with PLT.

• Revocation: PSP should be able to conditionally open the parking permit credentials and identify the user. In a serious incident, PSP can remove a user from the system or remove the user's anonymity. To do so, PSP should collaborate with PLT or, where appropriate, with other trusted third parties.

For data processing, it is necessary that the parking transaction records produced during the system use are stored and processed in a privacy-preserving manner at the PSP under the control of the PLT, thus leading to the following additional security and privacy requirements:

• Data minimisation: The transaction data items stored should be reduced only to the necessary data items for service usage analysis.

• Index and document privacy: The encrypted data used for statistics extraction should not reveal any sensitive information about the plaintext data and keywords (used for statistics purpose), to any unauthorized entities including the storing PSP.

• Query privacy: The type of statistics being performed should remain confidential, to the storing PSP.

• Access pattern privacy: No additional information should be revealed from the search results about the data involved.

• Query authorization: Statistics extraction should be limited to authorized entities and authorized keywords only.

Legal Issues

The objective of this section is to present the different legal instruments relevant for the deployment of such a service in order to answer the first research question, i.e., RQ1: What are the legal instruments, issues, and requirements for the deployment of such a system? After an explanation of the legal framework surrounding user identification 1 , the second section focuses on the security requirements in the scenario presented. The legal instruments studied relate to (i) use and deployment of Intelligent Transport Systems (ITS) [START_REF] Eu | [END_REF] (ii) consumer protection [START_REF] Eu | [END_REF], [START_REF]771 of the European Parliament and of the Council of 20 May 2019 on certain aspects concerning contracts for the sale of goods, amending Regulation (EU)[END_REF], and (iii) safety requirement for market placement of vehicles and their components [START_REF]2144 of the European Parliament and of the Council of 27 November 2019 on type-approval requirements for motor vehicles and their trailers, and systems, components and separate technical units intended for such vehicles, as[END_REF], [START_REF]UN Regulation No 155 -Uniform provisions concerning the approval of vehicles with regards to cybersecurity and cybersecurity management system[END_REF].

Smart parking scenario and data protection requirements

The GDPR applies to any processing of personal data [START_REF]679 of the European Parlament and of the Council of 27 April 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data[END_REF], Art. 4. In its guidelines on connected vehicles, the European Data Protection Board (EDPB) states that: "Even if data collected by a connected car are not directly linked to a name, but to technical aspects and features of the vehicle, it will concern the driver or the passengers of the car" [START_REF] Edpb | of connected vehicles and mobility related applications[END_REF], page 5. Under GDPR, personal data is therefore a broad notion [START_REF] Purtova | The Law of Everything. Broad Concept of Personal Data and Future of EU Data Protection Law[END_REF]. Thus, in the scenario studied, there will be different ways of identifying data subjects, in particular through vehicle identification and payment service. Hence, use of such information fall under the material scope of GDPR.

In the scenario studied, additionally to the requirements of lawfulness [31] Art. 5, of transparency [START_REF]679 of the European Parlament and of the Council of 27 April 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data[END_REF] Art. 12, of data accuracy [START_REF]679 of the European Parlament and of the Council of 27 April 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data[END_REF] Art. 5.1, d) and the data storage limitation [START_REF]679 of the European Parlament and of the Council of 27 April 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data[END_REF] Art. 5.1, e) [START_REF] Knockaert | Privacy-by-Design in Intelligent Infrastructures[END_REF] 2 , a fundamental question is the appropriateness of identifying the service user. Indeed, the EU places at the heart of personal data protection the principle of protection by default and by design [START_REF]679 of the European Parlament and of the Council of 27 April 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data[END_REF] Art. 25 3 . To be compliant, one prior question is the need for user identification [START_REF]679 of the European Parlament and of the Council of 27 April 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data[END_REF] Art. 5.1, c). This implies determining, at each stage of the development of the service and according to the activities of the PSP and 1 The reader should bear in mind that the following lines are not intended to provide a detailed analysis of the application of the EU General Data protection Regulation (GDPR) in the scenario presented.; Regulation (EU) 2016/679 of the European Parliament and of the Council on the protection of natural persons with regard to the processing of personal data and on the free movement of such data, and repealing Directive 95/46/EC, 27 April 2016, OJ L119/1. Far from being exhaustive, we draw attention to the existence of EDPB guidelines on connected vehicles [START_REF] Edpd | context of connected vehicles and mobility related applications[END_REF]. In this paper, we will not focus on the Directive 2009/136 and the E-privacy proposal. It should be noted that a connected vehicle might be interpreted as a terminal equipment under the EDPB guidelines on connected vehicles (Guidelines 01/2020). This means that the E-privacy Proposal could then be applied when it is necessary to access the information stored in the vehicle (e.g. when presenting the parking permit to the Parking Lot Terminal (PLT). Moreover, depending on the purpose, consent may or may not be required in the sense of the E-privacy proposal PLT, whether it is necessary to identify the person. Even if an identification is possible by the PSP with personal information such as mobile phone number, bank card and the credential, the minimisation principle is facilitated by the use of a third party, such as IDentity Provider (IDP), to avoid the collection of unnecessary personal data by the PSP. Additionally, each entity (IDP, PSP, and PLT) has no access to the same personal data.

Secondly, if identification is necessary, each entity responsible for the processing must favour the use of pseudonymisation [START_REF]679 of the European Parlament and of the Council of 27 April 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data[END_REF] (Art. 4.5) techniques. Indeed, the user is identified only in some situations by the PSP and the pseudonymisation is favoured for the PLT. The same credential than the one created by the PSP is pseudonymised for the PLT because these privacy-enhancing technique is sufficient to fulfil its purpose. The pseudonymisation is reinforced by unlikability parameters (PSP, PLTs or other users should not be able to link together parking actions of the same user if the parking permit is not recorded for a long period of time by the PLT (principle of storage limitation contained in Art. 5 [START_REF]679 of the European Parlament and of the Council of 27 April 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data[END_REF]). Finally, it is important to stress that the principle of minimisation is not only about the need or not to identify the data subject, but also about the need to determine an access policy to the personal data processed. Article 25.2 of the GDPR specifies that the control of accessibility to personal data is an integral part of the default data protection principle and states that: "In particular, such measures shall ensure that by default personal data are not made accessible without the individual's intervention to an indefinite number of natural persons". In this respect, the parking space reservation service and the payment service should be able to log who accessed to the data subject's data and the possibility to determine whether they have consulted or modified the information are two security measures that should be implemented [START_REF] Dumortier | La sécurité des traitements de données, les analyses d'impact et les violations de données[END_REF] 4 .

The EDPB states that: "the plurality of functionalities, services and interfaces (e.g., web, USB, RFID, Wi-Fi) offered by connected vehicles increases the attack surface and thus the number of potential vulnerabilities through which personal data could be compromised (• • • ) In addition, personal data stored on vehicles and/or at external locations (e.g., in cloud computing infrastructures) may not be adequately secured against unauthorized access" [23], pages 11-12 5 . According to article 32 of the GDPR, data controllers and data processors have to implement appropriate technical and organizational measures to ensure security of personal data, considering the state of the art, the costs of implementation, the type of personal data, and the potential risks. Several security measures are planned, notably for the communication between users and the PSP and the communication between the PSP and the PLT (see also Section 2.3 concerning the architecture and the protocols used and Section 5 regarding the cryptographic design). In particular, the cryptography and the pseudonymization technologies are cited by the GDPR as security measures making identification of data subjects more complex.

Additional privacy and security requirements

Deployment and use of intelligent transport systems

In Directive 2010/1024 on the framework for the deployment of ITS in the field of road transport, ITS are defined as "systems in which information and communication technologies are applied in the field of road transport (• • • ) and in traffic management and mobility management (• • • )" [START_REF] Eu | [END_REF], Art. 4.4. The provision of services for (i) information on parking places and (ii) reservation of parking places for trucks and commercial vehicles are two priority actions for the Directive [START_REF] Eu | [END_REF], Art. 3. Thus, if the smart parking service also targets commercial vehicles, the PSP might be qualified as provider of an ITS service for reservation of parking places. PSP and/or PLT may also be considered as providers of an ITS information service on parking places. Information on availability may indeed constitutes a preliminary step for reservation of a parking place.

ITS directive contains specific privacy and security requirements where personal data are processed for the operation of an ITS application or service [START_REF] Eu | [END_REF], Art. 10. First, data processing must be pursued in compliance with the GDPR. Second, personal data can be processed only where necessary for the performance of the application/service. Use of anonymous data is strongly suggested. Third, integrity and confidentiality of the data must be ensured. As explained above, personal data is indeed processed. Nevertheless, the data seems necessary in relation to the provided service and in accordance with a data minimization perspective.

Consumer protection rules

The definition of user used for the smart parking scenario is sufficiently broad to include consumer protection law. Indeed, consumer protection rules may apply if the user of the smart parking service is a natural person acting outside its professional activity (i.e., in Business-to-Consumer (B2C) relationships). In this context are especially relevant, (i) the Directive 2019/770 on contracts for supply of digital contents and services and (ii) the Directive 2019/771 on sale contracts of goods. The first Directive applies to conformity assessment of digital contents/services while the second applies to conformity assessment of good incorporating or interconnected with digital contents/services [START_REF]771 of the European Parliament and of the Council of 20 May 2019 on certain aspects concerning contracts for the sale of goods, amending Regulation (EU)[END_REF] [START_REF] Sein | Goods With Digital Elements" and the Interplay With Directive 2019/771 on the Sale of Goods[END_REF]. Directive 2019/771 also applies to digital content or services incorporated or interconnected to goods -and which are essential for the performance of the goods -provided under the sale contract of these goods.

In the case at hand, due to the two possibilities for users to interact with the parking system, both Directives may apply depending on the means used in order to initiate the parking permit request. When the reservation process is enabled with a standalone application available on the user's mobile phone, the PSP who serves as a software interface between the user and the PLT could be qualified as digital content or service provider under Directive 2019/770 [START_REF] Eu | [END_REF], recital 19. On the contrary, if the parking permit request process is triggered by a dedicated on-board unit, this device will meet the definition of good with digital elements according to Directive 2019/771 [START_REF] Carvalho | Sale of Goods and Supply of Digital Content and Digital Services -Overview of Directives 2019/770 and 2019/771[END_REF]. Both Directives highlight importance of security updates and requires that such updates are provided to the consumer in order to keep the good or digital contents/services conform [START_REF] Eu | [END_REF] Art. 8., [START_REF]771 of the European Parliament and of the Council of 20 May 2019 on certain aspects concerning contracts for the sale of goods, amending Regulation (EU)[END_REF] Art. 7.3, [START_REF] Beale | Digital Content Directive And Rules For Contracts On Continuous Supply[END_REF]. Both provisions highlight that provider of digital contents/services or sellers of goods will not be liable for lack of conformity if the consumer chooses not to install update, only if they have been informed of the importance of the updates to maintain conformity.

Vehicle safety requirements

In order to obtain EU type approval (i.e. homologation), manufacturers of vehicles, vehicles systems and components must comply with Regulation 2019/2144 (hereafter the "Vehicles General Safety Regulation"), [START_REF] Batura | Artificial intelligence in road transport: annex to cost of non-Europe report[END_REF]. Manufacturers must demonstrate compliance with several technical regulations adopted by the EU or the United Nations Economic Commission for Europe (UNECE), including on protection against cyberattacks [START_REF]2144 of the European Parliament and of the Council of 27 November 2019 on type-approval requirements for motor vehicles and their trailers, and systems, components and separate technical units intended for such vehicles, as[END_REF] Art 4.5 d. Even if the vehicles general safety Regulation applies primarily to vehicles manufacturer, it may still apply to the scenario studied depending on choices made for the specific architecture of the parking permit request process and the means used to initiate this process (e.g. if the reservation process is made through an on-board unit developed partly or wholly by the vehicle manufacturer).

Focus on UNECE Regulation n155 on vehicles cybersecurity: Through homologation, EU law imposes compliance with UNECE Regulation n 155 [START_REF] Ec | General Safety Regulation -Secondary Legislation[END_REF], which aims to ensure protection of vehicles and their functions against cyber threats to their electrical and electronical components (see Art. 2.2). This text requires that vehicles manufacturers have a CyberSecurity Management System (CSMS). This CSMS must go through a certification process and applies to the entire lifecycle of the vehicle types for which homologation is sought. Under this Regulation the notion of "Vehicle Type" designates vehicles that do not present differences for essential features of their electrical/electronical and external interface architecture. To this end, the Regulation contains requirements concerning the CSMS in general (i.e. independently from of the manufacturers' vehicles types) and requirements directed toward each vehicle type [START_REF] Goldstein | Understanding the UNECE WP.29 Cybersecurity Regulation (CSMS)[END_REF] (also see Articles 7.3 to 7.3.6 of UNECE Regulation for the requirements directed toward vehicle types). Only requirements relating to the CSMS of the manufacturer are presented below. Nevertheless, we highlight that, this Regulation imposes application of a risk identification process for each vehicle type. To that extent, critical elements of vehicles such as the one ensuring connectivity and the parts of the architecture enabling data exchange must be identified [START_REF]Proposals for Interpretation Documents for UN Regulation No. 155[END_REF]. The following lines explain the potential application of this Regulation within the context of this paper.

Cybersecurity management system requirements: In order to certify a CSMS, the approval authorities must verify that different processes are implemented by the vehicle manufacturer [START_REF]Proposals for Interpretation Documents for UN Regulation No. 155[END_REF] Art. 7.2 and 7.3. In order to identify the risks, threats and vulnerability to which vehicles of the manufacturer are exposed. An annex to the Regulation identifies high level threats/vulnerabilities and sub level threats/vulnerabilities (e.g. loss of data within cloud infrastructure, loss of data confidentiality/integrity) that must be covered by the CSMS. As specified by UNECE, risks linked to use of connected services are especially relevant in the process. Another requirement is the implementation of procedures to verify proper management of identified risks. To comply with this requirement, a list of mitigation measures, annexed to the Regulation, that include, among others, use of access control to personal data. Additionally, vehicle manufacturers must demonstrate to certification authorities, how the CSMS handles the dependencies and risks stemming from its supply chain 6 .

Application of UNECE Regulation n155 to the smart parking service:

Regarding the application of this Regulation in the context of this paper, different scenarios must be distinguished. First, the parking permit request process can be initiated by the user with an on-board unit integrated in the vehicle and developed by the vehicle manufacturer, i.e., the Original Equipment Manufacturer (OEM). Hence, this unit, as part of the vehicle, will be taken into account by the manufacturer within the assessment for compliance with the UNECE Regulation. Second, the on-board unit used to initiate the parking permit request might be developed by another entity (e.g. a tier one or tier two supplier) and integrated in the vehicle by the OEM. In this second scenario, the Regulation will create requirements for the OEM (e.g. assessing if the unit is a critical element of the vehicle). It will also apply to the supplier of the device which needs to cooperate with the manufacturer to handle supply chain related cyber risks (e.g., see ( [START_REF]Report -Automotive Cyber Threat Landscape in Light of New Regulations[END_REF], [65], [START_REF] Bittner | The Forgotten Threat of Voltage Glitching: A Case Study on Nvidia Tegra X2 SoCs[END_REF]). Third, the parking permit request may be enabled with a digital application developed by a third party (e.g. the PSP) in association with the vehicle OEM. This scenario raises the question of the qualification of the PSP in relation to the OEM's supply chain. In this context the European Union Agency for Cybersecurity (ENISA) considers that a software provider can be considered as a tier one provider when having direct contractual relationship with the OEM [START_REF]Cyber Security and Resilience of smart cars[END_REF]. Thus, if the digital application is developed in collaboration between the OEM and the application provider, the Regulation requirements linked to management of the supply chain related to cyber risks may apply. Consequently, where a relation exists between the OEM and the service provider (through the on-board unit or an application), the PSP shall be able to demonstrate that its security measures (e.g., Section 5) allow for the OEM to comply with the requirements mentioned above.

In a last scenario the mobile application used for the permit request process may be developed by the PSP or a third party at the demand of the PSP without involvement of the OEM. In absence of contractual agreement with the application provider, the application offered to the user might fall outside the scope of UNECE Regulation [START_REF] Enisa | Recommendations for the Security of Connected and Automated Mobility[END_REF]. However, according to ENISA "the UNECE Regulation (• • • ) applies to all Connected and automated mobility stakeholders (including Operators of Intelligent Transport System) who must ensure that their products and services conform to cybersecurity goal" [START_REF] Enisa | Recommendations for the Security of Connected and Automated Mobility[END_REF]. As stated above, the PSP may indeed be qualified of provider of an ITS.

As a preliminary conclusion and first response to RQ1, Table 1 identifies the legal instruments applicable to the scenario and the main data protection and security requirements to build a privacy-preserving system.

Cryptographic Preliminaries

We first outline the used notation needed to understand the cryptographic core of our privacy-preserving parking system. Then, we briefly introduce bilinear pairing maps and weak Boneh-Boyen (wBB) signature [START_REF] Boneh | Short signatures without random oracles and the SDH assumption in bilinear groups[END_REF] which are used throughout all our cryptographic design. Finally, we review the protocols on which our scheme is based, namely a short group signature (HDMR18) proposed by [START_REF] Hajny | Anonymous Data Collection Scheme from Short Group Signatures[END_REF], partially blind WI-Schnorr signature proposed by [START_REF] Abe | Provably secure partially blind signatures[END_REF], and searchable symmetric encryption scheme proposed by [START_REF] Gan | Dynamic Searchable Symmetric Encryption with Forward and Backward Privacy: A Survey[END_REF].

From now on, the symbol ":" means "such that", "|x|" is the bitlength of x and "||" denotes the concatenation of two binary strings. We write a ∈ R A when a is sampled uniformly at random from A. A secure hash function is denoted as H : {0, 1} * → {0, 1} κ , where κ is a security parameter. We describe the Proof of Knowledge (PK) and the Signature of Knowledge (SK) protocols using the notation introduced by [START_REF] Camenisch | Efficient group signature schemes for large groups[END_REF] (CS). In particular, the protocol for proving the knowledge of discrete logarithm of c with respect to g is denoted as P K{α : c = g α } and the protocol for proving the knowledge of discrete logarithm of c with respect to g and message m is denoted as SK{α : c = g α }(m).

Bilinear Pairing

Let G 1 , G 2 , and G T be cyclic groups of the same prime order n, p ∈ G 1 , q ∈ G 2 , and O is the point at infinity. G 1 and G 2 are additive groups and G T is a multiplicative group. By definition (q, G 1 , G 2 , G T , e, g 1 , g 2 ) is a bilinear group if it satisfies all below properties:

• Bilinearity: ∀x, y ∈ Z n , p ∈ G 1 , q ∈ G 2 : e(p x , q y ) = e(p, q) xy . Table 1: Smart parking: Privacy and security requirements.

GDPR, [START_REF]679 of the European Parlament and of the Council of 27 April 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data[END_REF] ITS directive, [START_REF] Eu | [END_REF] Consumer protection (directives 2019/770 and 2019/771), [START_REF] Eu | [END_REF], [START_REF]771 of the European Parliament and of the Council of 20 May 2019 on certain aspects concerning contracts for the sale of goods, amending Regulation (EU)[END_REF] Vehicle safety regulation (UNECE regulation No 155), [START_REF]2144 of the European Parliament and of the Council of 27 November 2019 on type-approval requirements for motor vehicles and their trailers, and systems, components and separate technical units intended for such vehicles, as[END_REF], [START_REF]UN Regulation No 155 -Uniform provisions concerning the approval of vehicles with regards to cybersecurity and cybersecurity management system[END_REF] Data • Non-degeneracy:

∀p ̸ = O ∃q ∈ G 2 : e(p, q) ̸ = 1 ∈ G T and ∀q ̸ = O ∃p ∈ G 1 : e(p, q) ̸ = 1 ∈ G T .
• Computability: There exists an efficient algorithm G(1 κ ) to compute e(p, q).

In this work, we consider the case G 1 ̸ = G 2 that is when e is an asymmetric bilinear map and the Decisional Diffie-Hellman (DDH) assumption holds.

Weak Boneh-Boyen Signature

The Weak Boneh-Boyen (wBB) signature scheme is a pairing-based short signature scheme. The scheme is provably secure and it is proven to be existentially unforgeable against a weak (non-adaptive) chosen message attack [START_REF] Boneh | Short signatures without random oracles and the SDH assumption in bilinear groups[END_REF]. The scheme can be easily combined with the zero-knowledge proofs as shown in [START_REF] Camenisch | Scalable revocation scheme for anonymous credentials based on n-times unlinkable proofs[END_REF]. This makes it possible to prove the authorship of signed messages in an unlinkable and anonymous manner. Below is a brief illustration of the wBB signature [START_REF] Boneh | Short signatures without random oracles and the SDH assumption in bilinear groups[END_REF]:

• (pk, sk, syspar) ← KeyGen ← (1 κ ): On the input of the security parameter κ, the algorithm generates system parameters syspar

= (q, G 1 , G 2 , G T , e, g 1 ∈ G 1 , g 2 ∈ G 2 ), computes pk = g sk 2 ,
where sk ∈ R Z q , and outputs sk as the private key and (pk, syspar) as the public key.

• (σ) ← Sign ← (m, syspar, sk): On the input of the message m ∈ Z q , the system parameters syspar and the secret key sk, the algorithm outputs the signature of the message σ = g

1 sk+m 1 .
• (1/0) ← Verify ← (σ, m, pk, syspar): On the input of the system parameters syspar, the public key pk, a signature σ and a message m, the algorithm returns 1 if and only if e(σ, pk) • e(σ m , g 2 ) = e(g 1 , g 2 ) holds, i.e. the signature is valid, or 0, otherwise.

Short Group Signature HDMR18

The article [START_REF] Hajny | Anonymous Data Collection Scheme from Short Group Signatures[END_REF] presents a short and fast group signature scheme (HDMR18) based on the wBB proposal. The signature allows a signer to generate an anonymous signature σ(sk i , m) on a message m, where sk i is the signer's private key. The protocol works as follows:

• (pk, sk m , spar) ← Setup ← (1 κ ): On the input of the security parameter κ, the algorithm generates the system parameters spar

= (q, G 1 , G 2 , G T , e, g 1 ∈ G 1 , g 2 ∈ G 2 ) satisfying |q| = κ.
It also generates the manager's private key sk m ∈ R Z q and computes the public key pk = g skm

2

. It outputs the (pk, spar) as a public output and the sk m as the manager's private output.

• (sk i , RD) ← KeyGen ← (id i , sk m ): On the input of manager's private key sk m and signer's private identifier id i , the protocol outputs the wBB signature sk i = g

1 skm+id i 1
to the signer and updates the manager's revocation database RD by storing id i .

• σ(sk i , m) ← Sign ← (m, id i , sk i ): On the input the signer's private identifier id i , signer's private key sk i , and the message m, the algorithm outputs the signature σ(sk i , m) = (g ′ 1 , sk ′ i , s k i , π), where:

-g ′ 1 = g r 1 :
The generator raised to a randomly chosen randomizer r ∈ R Z q .

sk ′ i = sk r i : The signers' private key raised to the randomizer. -s k i = sk ′ i -idi : The randomized private key raised to the signer identifier.

π = SK{(id i , r) :

s k i = sk ′ i -idi ∧ g ′ 1 = g r 1 }(m):
The proof of knowledge of r and id i signing the message m.

• (0/1) ← Verify ← (σ(sk i , m), m, pk, BL): On the input of the message m, its signature σ(sk i , m), a BlackList (BL), and the public key pk, the algorithm checks the proof of knowledge signature π and checks that the signature is valid with respect to the manager's public key using the equation e( s k i • g ′ 1 , g 2 )

?

= e(sk ′ i , pk). The collector also performs the revocation check sk ′ i ? = s k i idi for all id i values stored on the BL. If the revocation check equation holds for any value on the blacklist, the signature is rejected. Otherwise, the signature is accepted if all other checks pass.

Partially Blind WI-Schnorr Signature

A form of digital signature known as a "blind signature" conceals the message's content from the signer. The resulting blind signature can then be publicly verified against the original (unblinded) message and used as a regular digital signature. This technology is mostly utilized in privacy-enhancing protocols where the message's owner and signer are separate entities. In a partially blind signature, the signer may include common public information in the signature (for example, an expiration date). So, the verifier needs the message, the common information, and the signature in order to verify the signature's authenticity. The WI-Schnorr signature, which is a partially blind signature based on the Schnorr protocol and maintains the Witnesses Indistinguishability (WI), was proposed by [START_REF] Abe | Provably secure partially blind signatures[END_REF]. The WI-Schnorr signature is depicted in Figure 6. It is deemed that both the signer and the user have already agreed upon the public value "info".

Searchable Encryption: Outsourced Private Information Retrieval

A privacy enhancing technology that can facilitate privacy-preserving data processing is Searchable Encryption (SE), which enables storing a dataset in an encrypted form, while remaining searchable. This process relieves the service provider of the responsibility to maintain and protect the data from data breaches, as well as unauthorized use within the system. Structured Encryption (STE) is a searchable encryption variation that provides balance between efficiency, functionality and security [START_REF] Gan | Dynamic Searchable Symmetric Encryption with Forward and Backward Privacy: A Survey[END_REF], [START_REF] Kamara | Encrypted Search[END_REF]. Noninteractive STE schemes produce encrypted structures that can be queried using a single message containing a token, whereas in interactive schemes, queries User Signer are performed through an interactive two-party protocol. Searchable Symmetric Encryption (SSE) schemes are a special case of STE that specializes for keyword search. In this setting, a data owner creates a data structure with efficient search support, such as an inverted index. Each document in the dataset is then encrypted, forming the Encrypted DataBase (EDB) and outsourced to an external search service. This enables performing queries on the dataset without revealing information about the dataset or the queries to the search service. The encrypted dataset consists of a list of document identifier and keyword-set pairs. Queries are performed using a search token, generated by the data owner, that allows the server to search through the index. A search query returns the document identifiers that satisfy the query expression. In general, an SSE scheme includes the following main algorithms [START_REF] Gan | Dynamic Searchable Symmetric Encryption with Forward and Backward Privacy: A Survey[END_REF], [START_REF] Kamara | Boolean searchable symmetric encryption with worst-case sub-linear complexity[END_REF]:

(Message Owner) pk = g sk G, g, q sk ∈ Z q u, s, d ∈ R Z q z = (info) a = g u , b = g s z d a, b ← --------------- t 1 , t 2 , t 3 , t 4 ∈ R Z q z = (info) α = ag t1 pk t2 , β = bg t3 z t4 ε = (α, β, z, m) e = ε -t 2 -t 4 mod q e --------------→ S = e -d mod q R = u -S • sk mod q R, S, s, d ← ---------------- ρ = R + t 1 mod q ω = S + t 2 mod q σ = s + t 3 mod q δ = d + t 4 mod q
• (sk, ∆) ← Setup ← (1 κ , DB): Using a security parameter κ as input and a database DB, consisting of a list of document identifiers and keywords, it outputs the secret key sk and an encrypted data structure ∆ that will be outsourced to the data server. This algorithm varies depending on the specific SSE scheme and the data structures they use.

• (Γ) ← Token generation ← (sk, q): Using the secret key sk and the query q, it returns a query token Γ, to be used during search.

• (Φ) ← Search ← (sk, q, Γ, ∆): Using the secret key sk, the query q, and a search token Γ submitted by the user, the data server performs the search operations on encrypted data structure ∆, returning the matching documents. The algorithm outputs a set of encrypted documents Φ.

Depending on the SSE scheme, query expressiveness varies, supporting singlekeyword, conjunctive, disjunctive or boolean queries.

Privacy-Preserving Parking Solution

In this section, we show how to integrate security and privacy features to the vehicle parking scenario introduced in Section 2. Furthermore, we answer the second research question, i.e., RQ2: How to build a privacy-preserving system which meets the requirements from RQ1? Which Privacy-Enhancing Technology (PET) can be used in order to protect users' privacy during using the system, i.e., reservation of parking slots and parking vehicle actions?

Detailed Description of Our Algorithms

In this section, we instantiate the algorithms and protocols of the privacypreserving parking system presented in the previous section using the wBB signature [START_REF] Boneh | Short signatures without random oracles and the SDH assumption in bilinear groups[END_REF] the Schnorr-like zero-knowledge protocol for proving the knowledge of a discrete logarithm [START_REF] Camenisch | Efficient group signature schemes for large groups[END_REF] during the Parking vehicle phase. For the conversion from the proof of knowledge to the signature, we use the Fiat-Shamir heuristics [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF]. We present the concrete algorithm and protocol instantiations below. To make our protocols easier to follow, we provide several illustrative figures (namely Figures 7, 8, 9, and 10) describing our protocols algorithmically and which can be read from top to bottom.

Setup

(pk P SP , sk P SP , pk P LT , sk P LT , spar) ← Setup ← (1 κ ): The purpose of this algorithm is to generate and set system parameters and cryptographic keys of the system. On the input of security parameter κ , the algorithm generates the public system parameters spar (implicit input of all other algorithms), the public keys of the PSP and the PLTs shared by all users pk P SP , pk P LT and their private keys sk P SP , sk P LT which remain secret. The algorithm is run within the Setup phase, is initiated by the PSP, and runs between the PSP and all enrolled PSPs. The algorithms consists from two sub-algorithms, one run by PSP (called SetupPSP) and one run by PLT (called SetupPLT):

• (pk P SP , sk P SP , spar) ← SetupPSP ← (1 κ ): The algorithm inputs the security parameter κ and generates the bilinear group with parameters spar = (q, G 1 , G 2 , G T , e, g 1 , g 2 ) satisfying |q| = κ. It also generates the PSP's private key sk P SP ∈ R Z q and computes the public key pk P SP = g sk P SP

2

. It outputs the (pk P SP , spar) as a public output and the sk P SP as the PSP's private output. The algorithms is run by the PSP.

• (pk P LT , sk P LT ) ← SetupPLT ← (spar): The algorithm inputs the system parameters spar and generates the PLT's private key sk P LT ∈ R Z q and computes the public key pk P LT = g sk P LT

1

. It outputs the pk P LT as a public output and the sk P LT as the PLT's private output.

Register

(Λ, sk U , RD) ← Register ← (ID, sk P SP , spar): The purpose of this protocol is to add a new user to the system. The Register algorithm is presented in full notation in Figure 7. On the input of the PSP's private key sk P SP and the user's identifier ID, the algorithm outputs the user's private key sk U , user's access credential Λ and updates the PSP's revocation database RD. The algorithm is run within the Registration phase as an interactive protocol between the PSP and the user device. The system user is then able to require parking permits and access parking lots. The PSP inputs its private key sk P SP and the user inputs the identity ID. If the ID is valid, the protocol generates user's private key sk U ∈ R Z q and outputs the wBB signature Λ = g

User PSP

G1, G2, GT , g1, g2, e, q skP SP ∈ Zq ID --------------------- --------------------Store: Λ, skU

→ skU ∈R Zq Λ = g 1 sk U +sk P SP 1 Store: RD ← (ID||skU ) Λ, skU ←-

Issue

(sk Cred , CRED) ← Issue ← (Λ, sk P LT , pk P LT , P D, spar): The parking permit is issued after the payment is done. The algorithm is run within the Issue parking permit phase between the user device and the PLT through the PSP. The Issue algorithm is presented in full notation in Figure 8. The algorithm inputs the user's access credential Λ, user's parking data P D, the PLT's secret key sk P LT , the PLT's public key pk P LT and system parameters spar. It outputs the parking permit secret key sk Cred and the parking permit CRED that consists of the following elements (ρ||ω||σ||δ|| Λ||ĝ||P D):

• Λ: The user's access credential raised to a randomly chosen parking permit secret key sk Cred ∈ R Z q , i.e. Λ = Λ sk Cred .

• ĝ1 : The generator raised to a randomly chosen parking permit secret key sk Cred ∈ R Z q , i.e. ĝ1 = g sk Cred

1

.

• P D: The public parking data P D. The P D includes the PLT's identifier PLTid, parking time period time duration and information about extended parking time EPT. To sign data, the PLT uses its secret key sk P LT .

• (ρ||ω||σ||δ): The PLT's signature on the user's partially blinded message, i.e., blinded values Λ and ĝ, and the public parking data P D. First, the PLT commits to the public data P D by computing commitments a = g u 1 , b = g s 1 z d , where z = F(P D). Then, the user partially blinds the message. In particular, the user blinds the values Λ and ĝ and computes commitments α = ag t1 1 pk t2 P LT , β = bg t3 1 z t4 using the PLT's public key pk P LT , the PLT's commitments (a, b) and the public data z = F(P D). The user generates the hash ϵ on all these data, derives value e from ϵ, and sends it to the PLT. The PLT computes blind signature (R, S, s, d) on value e using its secret key sk P LT . Finally, the user unblind the blind signature and obtains the signature (ρ||ω||σ||δ).

The parking permit includes blinded user's access token Λ, and therefore, it cannot be used for user identification by PSP in this phase.

Verify

(0/1) ← Verify ← (sk U , sk Cred , Λ, CRED, pk P LT , pk P SP , spar): The parking is anonymous and unlinkable since the parking permit does not include any linkable or personal information. The algorithm is run within the Parking vehicle phase between the user device and the PLT. The Verify algorithm is presented in CS notation in Figure 9. The algorithm inputs the user's secret key sk U , the parking permit secret key sk Cred , the user's access credential Λ, the parking permit CRED, the PSP's public key pk P SP , the PLT's public key pk P LT , and system parameters spar. It checks that the signature on parking permit is valid under the PLT's public key using the equa-

tion ε = ω + δ ? = H(g ρ 1 pk ω P LT ||g σ 1 F(P D) δ ||F(P D)|| Λ|| Λ||ĝ).
If the signature is valid, the algorithm checks the proof of knowledge π and validity of the user's access credential Λ with respect to the PSP's public key using the equation e( Λ • ĝ1 , g 2 ) ? = e( Λ, pk P SP ). If all checks pass, the parking permit is accepted.

User PSP PLT

Λ, sk U ,pk ------------- s, d ← ----------------ρ = R + t 1 mod q ω = S + t 2 mod q σ = s + t 3 mod q δ = d + t 4 mod q Store: sk Cred , CRED = (ρ||ω||σ||δ|| Λ|| Λ||ĝ||P D) Otherwise, the parking permit rejected. The proof of knowledge protocol is run as follow:

P LT = g sk P LT 1 G 1 , G 2 , G T , g 1 , g 2 , e, q sk P LT ∈ Z q sk Cred ∈ R Z q Λ = Λ sk Cred Λ = Λ-sk U ĝ1 = g sk Cred 1 u, s, d ∈ R Z q P D = {PPID||PLTid||time duration||EPT} z = F(P D)) a = g u 1 , b = g s 1 z d a, b ← -
- t 1 , t 2 , t 3 , t 4 ∈ R Z q P D = {PPID||PLTid||time duration||EPT} z = F(P D) α = ag t1 1 pk t2 P LT , β = bg t3 1 z t4 ε = H(α||β||z|| Λ|| Λ||ĝ) e = ε -t 2 -t 4 mod q e ---------------→ S = e -d mod q R = u -S • sk P LT mod q R, S,
• The PLT generates random authentication challenge c ∈ R Z q and send it to the user.

• The user compute proof of knowledge π and sends it to PLT:

ρ SkCred , ρ SkU ∈ R Z q t = Λρ SkU g ρ SkCred 1 e = H( ĝ1 , Λ, Λ, t, c) s SkCred = ρ SkCred -e • sk Cred s SkU = ρ SkU + e • sk U π = (e, s SkCred , s SkU )
• The PLT verifies the proof of knowledge π: --------------------------------------- --------------------------------------------→ Check π e( Λ • ĝ1 , g 2 ) ? = e( Λ, pk P SP ) Figure 9: Verify algorithm.

t = ( Λ • ĝ1 ) e Λs SkU • g s SkCred 1 e ? = H( ĝ1 , Λ, Λ, t, c) User PLT sk U , sk Cred , Λ, CRED pk P LT = g sk P LT 1 , pk P SP = g sk P SP 2 G 1 , G 2 , G T , g 1 , g 2 , e, q CRED -

Update

(sk Cred , CRED) ← Update ← (sk U , sk Cred , Λ, CRED, pk P LT , pk P SP , sk P LT , EPT, spar): The purpose of this protocol is to extend parking time of a parking permit. The algorithm inputs the user's secret key sk U , the parking permit secret key sk Cred , the user's access credential Λ, the parking permit CRED, the PSP's public key pk P SP , the PLT's public key pk P LT , the PLT's secret key sk P LT , the extension parking time EPT, and system parameters spar. The algorithm is run in two steps.

1. (0/1) ← Verify ← (sk U , sk Cred , Λ, CRED, pk P LT , pk P SP , spar): The Verify algorithm is run first. The user specifies the parking permit CRED for extension parking time by sending PLTid and PPID information. The PLT finds corresponding parking permit CRED in its database and stars the Verify algorithm. If verification is successful, then the algorithm continues, ends otherwise.

2. (sk Cred , CRED) ← Issue ← (Λ, sk P LT , pk P LT , P D, spar): The Issue algorithm is run second. The user chooses and sends a new expiration parking time ETP to PLT. Then, the user and the PLT run together Issue algorithm using the P D from the old user's parking permit CRED and new ETP to create a new extended parking permit CRED.

Revoke

(ID) ← Revoke ← (CRED, RD, spar): Thanks to this algorithm, the PSP can identify malicious users from the parking permits using the revocation database RD. The algorithm is run within the Revocation phase by the PSP. The algorithm inputs parking permit CRED and PSP's revocation database RD.

It checks Λ ?

= Λ-sk U for all sk U in RD. The sk U that holds in the equation is linked with the user's identifier ID. By providing the ID to an identity provider, the PSP can revoke malicious users' anonymity and identify the users.

Optional Extension of the system supporting the nonrepudiation feature

The proposal of the parking system presented in Section 5.1 does not provide non-repudiation features. In fact, the PSP knows all secret keys sk U of all system users. Thanks to this knowledge, the PSP can revoke users by running the Revoke algorithm. On the other hand, the malicious PSP can forge valid parking permits for all system users, and therefore, falsely accused of committing a crime on anyone in the system. Due to this fact, the PSP must be trusted and honest. However, if the system implementer requires non-repudiation features, we have proposed a solution as well. The solution is based on using a secure two-party computation of wBB signature within the Register algorithm. We refer to [START_REF] Belenkiy | Randomizable proofs and delegatable anonymous credentials[END_REF] and [START_REF] Ricci | Privacy-Enhancing Group Signcryption Scheme[END_REF] for more details. Our extension impacts only Registration and Revoke algorithms presented in Section 5.1. The other algorithms remain unchanged. The extended Registration algorithm is depicted in Figure 10.

The algorithm takes on the input system parameters spar = (q, G 1 , G 2 , G T , e, g 1 , g 2 ) and parameters (g, h, n, g, h, n) [START_REF] Belenkiy | Randomizable proofs and delegatable anonymous credentials[END_REF], where n is RSA-modulus of size at least 2 3κ q 2 , κ is a security parameter, h = n + 1, g is an element of the order ϕ(n) mod n 2 , n is RSA modulus such that neither the user nor the PSP knows its factors (e.g., n can be provided by a TTP), h and g are two elements in Z * n such that log g h is unknown and g ∈ ⟨h⟩. The algorithm is run by the user and the PSP as in main scheme and allows computing user's access credential Λ = g 1/(sk P SP +sk U ) 1 without that the PSP reveals its private key User PSP G1, G2, GT , g1, g2, e, q , g, h, n, g, h, n sk P SP and the user its secret key sk U . The algorithm is based on homomorphism of Paillier cryptosystem [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]. Fist, the PSP homomorphicly encrypts its secret key sk P SP by computing e 1 = h n/2+sk P SP g r mod n 2 and computes commitment c 1 = g skm h r ′ mod n. Then, the PSP and the user run the PK protocol:

skP SP ∈ Zq ID ----------------------→ r ∈R Z ϕ(n) r ′ ∈R Z ϕ(n) e1 = h n/2+sk P SP g r mod n 2 c1 = g sk P SP h r ′ mod n e1, c1, π1 ← ----------------------- Check π1 skU ∈R Zq r1 ∈R Zq r2 ∈R {0, . . . , 2 κ q} r ∈R [0, n2 κ ] e2 = (e1/h n/2 ) r 1 h (n/2+sk U )r 1 +r 2 q g r mod n 2 c2 = g i h r mod n pkU = g sk U 2 e2, pkU , c2, π2 -----------------------→ Check π2 x = Dec(e2) -n/2 Λ * = g 1/x 1 Store: RD ← (ID||pk -1 U ) Λ * ← ---------------------- Λ = (Λ * ) r 1 = g 1 sk U +sk P SP 1 Store: Λ, skU
π 1 = P K{(sk P SP , r, r ′ ) : e 1 /h n/2 = h sk P SP g r mod n 2 ∧ c 1 = g sk P SP h r ′ mod n}
Proof. During the Issue parking permit phase, users provide their unique access credential Λ to the PLT through the PSP. This credential is blinded, and therefore, the PLT and the PSP can learn nothing about it. Furthermore, the access credential Λ is stored in the parking permit CRED, which is presented by the user to the PLT within the Park vehicle phase. However, in this case, the users' credentials are randomized, and therefore, mutually unlikable by the PLT.

The revocation is possible thanks to ( Λ|| Λ) values stored in the parking permit CRED. With these two values, the PSP can perform the Revoke algorithm and identify the users. Users traceability by the PSP is possible:

1. Main scheme (see Section 5.1): The PSP checks Λ ? = Λ-sk U ∈RD for all sk U ∈RD in RD. If any sk U ∈RD holds in the equation then sk U ∈RD = sk U and sk U ∈RD is linked with the user's identifier ID: U ∈RD is linked with the user's identifier ID:

Λ = Λ-sk U ? = Λ-sk U ∈RD
e( Λ, pk -1 U ∈RD ) = e( Λ, g -sk U ∈RD 2 ) = e( Λ, g 2 ) -sk U ∈RD ? = e( Λ, g 2 ) = e( Λ-sk U , g 2 ) = e( Λ, g 2 ) -sk U Lemma 5.2.
Non-traceable and unlinkable reservations: User's actions cannot be bound together by third parties.

Proof. The PLT is receiving anonymous blinded user's access credential within the Issue parking permit phase and anonymous randomized user's access credential within the Parking vehicle phase. No personal or other linkable information is provided during these processes. Due to this fact, the PLT cannot bind any subsequent parking reservation requests of the user. In the same vein, as user's revocable data ( Λ|| Λ) are stored in the parking permit CRED and only provided to the PSP in case of a fraud attempt, neither the PSP can link user's reservations. The parking permit is always anonymous and unlinkable due to the zero-knowledge property of the proof of knowledge protocol. Distribution of Λ, Λ, ĝ1 is random and uniform in Z q as sk Cred is selected randomly and uniformly from Z q :

Λ = Λ sk Cred Λ = Λ-sk U ĝ1 = g sk Cred 1
Lemma 5.3. Fraud avoidance: A user cannot be falsely inquired about not completing a payment process.

Proof. The Issue parking permit phase is run after the payment for parking is made. The parking permit CRED includes the paid parking time, so, any false accusation from the PLT can be denied.

Lemma 5.4. Non-repudiation and integrity: Evidences generated from entities interaction can be neither denied nor counterfeited.

Proof. The PLT proofs its identity by signing the parking permit CRED, the PSP proofs its identity by signing the user's access credential Λ, and the user proofs the possession of a valid secret keys sk U and sk Cred within the Parking vehicle phase. As a result of the Issue parking permit phase, only the user obtains complete parking permit CRED, containing the parking reservation details P D and revocable data ( Λ|| Λ). The PLT gets only partial information about CRED (namely P D consists of PPID, PLTid, time duration, EPT). The PLT signs P D with blind signature scheme. The signature validity can be verified by everyone, therefore, proofs' integrity is granted. The signature on a parking permit CRED is always accepted if a valid PLT's secret key is used in the signature:

ε = H(α||β||z|| Λ|| Λ||ĝ) ? = ω + δ ? = H(g ρ 1 pk ω P LT ||g σ 1 F(P D) δ ||F(P D)|| Λ|| Λ||ĝ) α = ag t1 1 pk t2 P LT ? = g ρ 1 pk ω P LT = g (R+t1) 1 pk (S+t2) P LT = g (u-(e-d)•sk P LT +t1) 1 pk (e-d+t2) P LT = g u 1 pk (-e+d) P LT g t1 1 pk (e-d+t2) P LT = ag t1 1 pk t2 P LT β = bg t3 1 z t4 ? = g σ 1 F(P D) δ = g (s+t3) 1 z (d+t4) = g s 1 z d g t3 1 z t4 = bg t3 1 z t4 ε = e + t 2 + t 4 ? = ω + δ = S + t 2 + d + t 4 = e -d + t 2 + d + t 4 = e + t 2 + t 4
The signature on randomized user's access credential Λ is always accepted if a valid PSP's secret key is used in the signature: 2 )

e( Λ • ĝ1 , g 2 ) ? = e( Λ, pk P SP ) e(Λ -sk U •sk Cred g sk Cred 1 , g 2 ) = e(Λ sk
e(Λ sk P SP •sk Cred , g 2 ) = e(Λ sk Cred , g sk P SP

2 ) e(Λ, g 2 ) sk P SP •sk Cred = e(Λ, g 2 ) sk P SP •sk Cred

The proof π = SK{(sk U , sk Cred ) : Λ = Λ-sk U ∧ ĝ1 = g sk Cred 1 }(c) is always accepted if valid user's secret keys sk U , sk Cred are used in the proof:

e = H( ĝ1 , Λ, Λ, t, c) ? = H( ĝ1 , Λ, Λ, t, c) t = Λρ SkU g ρ SkCred 1 ? = ( Λ • ĝ1 ) e Λs SkU • g s SkCred 1 = t = ( Λ-e•sk U • g e•sk Cred 1 ) Λ(ρ SkU +e•sk U ) • g (ρ SkCred -e•sk Cred ) 1 = Λρ SkU • g ρ SkCred 1

Experimental results

In this section, we provide our experimental results. In particular, we show the efficiency of our proposal on Android devices. We use the Android phones: Honor 8X (chip: Kirin 810, OS: Android 10, RAM: 4 GB) and OnePlus Nord 5G (chip: Snapdragon 765G, OS: Android 11, RAM: 8 GB). In order to perform cryptographic operations, we use the MCL [START_REF] Shigeo | Mcl library[END_REF] ++ library (using C++17 version of the ISO/IEC 14882 standard) and Android Native Development Kit (NDK). The Android NDK allows us to execute a program in C/C++ on Android devices instead of using Java libraries, and therefore, to achieve better performance results. The source code of the Android application is available online on the GitLab repository7 . Our benchmark test on both phones for different arithmetic operations and fields is presented in Table 2. We measure the time complexity of each MCL operation 10 times and then compute the median from these data. From the table, we can see that the time complexity of operations in F r is negligible. They take approximately 30 µs for the BN254 elliptic curve on OnePlus Nord 5G. A similar situation is in the case of operations in G 1 and G 2 . The most expensive operations are scalar multiplication mul1, mul2, modular exponentiation powT, and bilinear pairings pairT. These operations have a significant impact on the time complexity of the whole protocol. Note: F r represents finite field Z q , G 1 is cyclic additive group of order q generated by elliptic curve, G 2 is cyclic additive group of order q generated by elliptic curve, G T is the cyclic multiplicative group of order q.

To show the complexity of our system, we sum up the algebraic operations used in the cryptographic algorithm (i.e., Register, Issue, Verify, Update and Revoke) for each involved system entity and compute the execution time.

To do so, we used data from Table 2. In particular, we consider using the OnePlus Nord 5G Android device and the BN254 elliptic curve. Considering our results in the Table 3, the cryptographic core time complexity is negligible, since it takes ca. 6 ms for Issue, ca. 9 ms for Verify and ca. 14 ms for Update algorithm.

The complexity of the Revoke algorithm is linearly dependent on the number of users in the system. The time complexity of Revoke algorithm for both main scheme (see Section 5.1) and extended scheme (see Section 5.2) based on number of system user is depicted in Figure 11. The main algorithm requires performance of N operations of mul1, while the extended algorithm requires the performance of N operations of pairT), where N is a number of system users. If we consider OnePlus Nord 5G Android device and 1 million system users, the Revoke algorithm will need ca. 9 min (i.e., main algorithm) and

Privacy Preserving Data Processing for Statistics Analysis

During the use of the parking system, transaction data is produced, the processing of which could provide interesting information about the characteristics of the service and possible improvements. This processing, however, needs to be performed in a privacy-preserving way, in order to reap the benefits of this processing without compromising the privacy of the users. To solve this requirement, we need to answer the third research question, i.e., RQ3: How to allow third parties to perform statistical analyses on the parking transaction data, in a privacy preserving way? Which PET can be used to support this task? In the context of the parking scenario, data remain in a clear-text form during the course of a transaction, but once the transaction is completed, the transaction record is moved to long term storage in encrypted form for privacypreserving statistical analysis. Additionally, following the data minimisation principle, only the necessary data items for analysing the service use is stored in the transaction records. In particular, a parking transaction record includes the following data items:

• Vehicle classification: It defines official classification categories used in vehicle licenses.

• Vehicle type: It can represent the vehicle power supply, e.g. gas, electric, GPL.

• Parking spot type: It can represent the disability spot, premium spot, short duration spot, long duration spot, secure/closed spot.

• Services required: It can indicate washing, charging or any other needs.

• User affiliation: It can indicate affiliation with companies/venues, used for special pricing.

• Parking start timestamp: Time when parking started and the user has access to the parking lot.

• Parking end timestamp: Time when parking has ended and the user must leave the parking lot.

• Parking transaction cost: The price that the user must pay for the parking time in the selected parking lot.

Using these data items as search keywords, statistics can be extracted on parking spot demand, peak hours and availability. These statistics can facilitate decisions on pricing strategies and parking spots allocation and management, as well as possible custom offers and packages for specific companies/venues. The objective of our scheme is to support the following functional and efficiency requirements, additionally to the security and privacy requirements identified in Section 2.4, as they are desired for the SSE scheme and appropriate for the parking scenario:

• Multi-user functionality: Searching the dataset is possible for authorized third parties other than the data owner.

• Query expressiveness (boolean query support): Complex queries need to be supported to enable extracting useful statistics from the dataset.

• Efficiency: The search functionality needs to be efficient and scalable, in order for the solution to be applicable in practice.

We propose our MC-SSE scheme (for Multi-Client SSE scheme), which extends the efficient and expressive BIEX SSE scheme [START_REF] Kamara | Boolean searchable symmetric encryption with worst-case sub-linear complexity[END_REF] with the multi-user functionality, not supported by the original BIEX scheme. An open source library of the BIEX SSE scheme, known as Clusion8 , is publicly available, which is particularly attractive in the idea of proposing an extension with experimental results.

Our MC-SSE System Model and Overview

The following entities are interacting in the data processing system for the parking scenario, as illustrated in Figure 12: • The data owner (D): The data owner creates an encrypted dataset and outsources it. In our scenario the PLT acts as the data owner.

• The storage and query server (S): They handle the encrypted dataset storage and performs queries on it.

• Search clients (C): They are allowed to search on the encrypted dataset.

The PSP, other PLTs in the parking system, or any other interested stakeholder can act as a search client.

To achieve the multi-client extension of BIEX, the data owner provides Search clients an authorization token that enables them to create search tokens and submit queries to the Server limited by the keywords contained in the authorization token. With this extension the properties of the BIEX scheme are preserved, i.e. boolean query support with efficient search, while enabling multi-client functionality.

Refining the Security and Privacy Threat Model

As considered in classical SSE schemes, the Server S is honest-but-curious, thus fulfilling the search tasks over the database correctly, but attempting to collect as much data as possible. The Clients C are malicious and the data owner D is honest. We only consider internal attackers as all the channels between any interacting entities -D-S, D-C and S-C -are authenticated.

In the light of the system model of Section 6.1, additionally to the security and privacy requirements identified in Section 2. document privacy, query privacy, access pattern privacy, the query authorization requirement is revisited the multi-client SSE scheme as follows:

• Query authorization: Only authorized clients on authorized keywords are able to extract statistics from the server.

• Privilege escalation prevention, as a sublease of the query authorization issue: Clients must not be able to collude for generating a search token with a superset of combined keywords.

Our MC-SSE Algorithms

The Multi-Client SSE (MC-SSE) scheme consists of the following algorithms:

• (sk, EDX, EMM) ← Setup ← (κ, DB): Taking as input a security parameter κ and an index database DB, it outputs the secret key sk, an encrypted dictionary EDX, and an encrypted multi-map EMM. The algorithm is run by the data owner (D).

• (Γ) ← Authorization token generation ← (sk, W auth ): Using as input the secret key sk and a vector of keywords W auth = (w 1 , • • • , w q ), for each keyword w i in the vector, it creates a sub-token Γ i = (gtk i , dtk i , ltk j ) containing a global token gtk i , a dictionary token dtk i and for all keywords w j , with 1 ≤ j ≤ q and j ̸ = i, a local token ltk j . The algorithm is run by the data owner (D) and outputs authorization token Γ = (Γ 1 , ..., Γ q ).

• (γ) ← Search token generation ← (Γ, ∆): Using as input an authorization token Γ and a boolean query ∆, where ∆ is a query written in conjunctive normal form (CNF) as ∆ 1 ∧ • • • ∧ ∆ l , and where each ∆ i = w i,1 ∨ • • • ∨ w i,q is a disjunction, for the first disjunction ∆ 1 it calculates the disjunction IEX sub-token γ 1 as follows:

for each keyword w 1,j in ∆ 1 except the last, it creates the sub-token γ 1,j = ( ḡtk 1,j , dtk 1,j , ltk k,j ) containing the global token ḡtk 1,j , the dictionary token dtk 1,j and for all keywords w 1,k , with j + 1 ≤ k ≤ q ′ , the local token ltk k,j . Finally, for the last keyword w 1,q ′ only the global token ḡtk 1,q ′ is kept and the output is the search token

γ 1 = (γ 1,1 • • • γ 1,q ′ -1 , ḡtk 1,q ′ ).
For every following disjunction ∆ i , 2 ≤ i ≤ l it computes the sub-token γ i containing the local tokens between every keyword in ∆ 1 and every keyword of ∆ i , as follows:

for each keyword w 1,j in ∆ 1 it calculates the vector of local tokens ltk j,i = ( ltk j,i,k ), 1 ≤ k ≤ q ′ between the keyword w 1,j in the first disjunction and every keyword k in the i-th disjunction. Then the output is

γ i = ( ltk 1,i • • • ltk q ′ ,i ).
The algorithm is run by the search client (C) and the final output is a search token γ = (γ 1 , ..., γ q ′ ).

• (T ) Search ← (EDB, γ): Using as input EDB = (EDX, EMM) and a search token γ = (γ 1 , ..., γ q ′ ), for the first search sub-token

γ 1 = (γ 1,1 • • • γ 1,q ′ -1 , ḡtk 1,q ′ ),
the server performs the IEX search as follows:

-For every element γ 1,i = ( ḡtk 1,i , dtk 1,i , ltk k,i ), 1 ≤ i ≤ q ′ -1: * First it uses ḡtk 1,i to query the global multi-map EMM, to recover the set T 1,i of document identifiers containing w i . * Then it uses dtk 1,i to query the encrypted dictionary EDX to recover the local multi-maps for w i . * Finally, it uses the local tokens ltk k,i , with i+1 ≤ k ≤ q ′ to query the local multi-maps, to recover the set of document identifiers T ′ that contain both w i and w k and removes them from T 1,i .

-For the last element in γ 1 , ḡtk 1,q ′ , it recovers the document identifiers T 1,q ′ containing w q ′ .

-Finally, the server calculates the set of document identifiers T 1 , containing the document identifiers T 1,i through T 1,q ′ . For every following search sub-token γ i = ( ltk 1,i • • • ltk q ′ ,i ), i ≥ 2, the server:

-Uses dtk 1,i from γ 1 to query the encrypted dictionary EDX to recover the local multi-maps for w i .

-Then, it uses the local tokens ltk k,i , with 1 ≤ k ≤ q ′ to query the local multi-maps, to recover the set of document identifiers T k,i that contain both w i and w k .

Experimental results

The MC-SSE evaluation consisted of experiments with up to 1 M documents, containing synthetic parking transactions, resulting in 21 M document-keyword pairs. Experiments were conducted on both the original BIEX scheme and the MC-SSE scheme for the same dataset. The source code of the Clusion BIEX library is available online on the GitHub repository9 and the source code for the multi-client extension of the Clusion BIEX library is available on the on the GitHub repository 10 . A docker container with the multi-client library extension bundled with a web application for testing its functionality is also available online on the Docker Hub repository In particular, as illustrated in Figure 13, the efficiency of the search functionality for MC-SSE is consistent with the original BIEX performance, taking approximately 3-30 ms, to perform a boolean search over 1 M documents (21 M document-id pairs). Note that the query expression includes 2 disjunctions (sub-queries) with 2 keywords each, of the form ((w∨x)∧(y∨z)), with the search time depending on the selectivity of the first disjunction ((w ∨ x)) of the query, i.e., the number of documents returned by the first sub-query. The slightly smaller times in the MC-SSE search duration presented, mainly in higher values of the search times, is due to slight improvements in the Java code for the implementation of the search functions in the Clusion library.

In the multi-client version of the scheme, the main difference is the creation of the authorization token Γ, which includes a superset of all the sub-tokens for the included keywords, hence being larger in size compared to the equivalent BIEX search token. The experimental evaluation for the overhead introduced by the authorization token Γ consisted of creating authorization tokens and BIEX tokens for the same keywords and measuring the creation time and serialized size of the resulting tokens. For both types of tokens, the creation of tokens for keyword set sizes from N ∈ [1, • • • , 100] was evaluated, taking each time the N most frequent keywords in the dataset.

As illustrated in Figure 14, the creation of the authorization token Γ for the multi-client extension of BIEX, shows that the performance of the creation of the authorization token Γ displays the same general trend as the BIEX token creation, being exponential with the number of keywords in the token. Despite the creation time of the authorization token Γ being higher than the one of the 1,000 2,000 10,000 20,000 100,000 200,000 1,000,000

Selectivity of second disjunction (#) BIEX token, it is just a constant factor higher and remains reasonable in absolute terms. The increased creation time is expected, as the authorization token Γ includes approximately double the elements compared to the corresponding BIEX token for the same keyword set, as illustrated in Figure 15.

Concluding remarks

In this paper, we present multidisciplinary work on a comprehensive privacypreserving system. The work includes research areas starting from regulation compliance analysis, through the design of privacy-preserving parking registration and vehicle parking services to the deployment of privacy-preserving parking data processing features for data analysts. At the beginning of the article, we open up three research questions, namely RQ1, RQ2, and RQ3, which are discussed and addressed in the article. First, we address the research question RQ1: What are the legal instruments, issues, and requirements for the deployment of such a system? To do so, we provide legal analysis for parking scenarios in compliance with current EU regulations and directives. From a legal point of view, it is obvious that the use of connected objects in cars requires a lot of precautions. While the legislation governing the processing of drivers' personal data (GDPR) is a cornerstone, ad- ditional security obligations are enshrined in other European legislation. The key principle that drives the most privacy and security requirements is the privacy by design and by default obligation. This approach is accompanied by an appropriate security obligation regarding the risks incurred by users of the smart parking service. This scalable approach is completed by the ITS Directive. One has also to keep in mind that, depending on (1) the technical choices made for the implementation of the service and (2) the stakeholder involved, additional sectorial Regulations could apply. In particular, if a car manufacturer is engaged in the development of the device/application used to provide the service, application of the EU Regulation on Vehicles General Safety Regulation and UNECE Regulation n155 could be triggered. In such cases, an additional layer of technical and cybersecurity requirements should be met to ensure legal compliance of a smart parking service. Finally, we would like to insist on the fact that an optimal security also requires the implementation of more overall organisational measures.

Second, we address the research question RQ2: How to build a privacypreserving system which meets the requirements from RQ1? Which Privacy-Enhancing Technology (PET) can be used in order to protect users' privacy during using the system, i.e., reservation of parking slots and parking vehicle actions? Here, we base on privacy and security requirements identified from the legal analysis and we propose a novel privacy-preserving parking system. The system protects users' privacy and prevents tracking and profiling of users while using the system (i.e, during parking reservations and vehicle parking actions). On the other hand, the system allows revocation and de-anonymization of malicious users committing fraud. To do so, more system entities, namely PSP, PLT, and IDP, must collaborate. The cryptographic core of our system is built on provable secure PETs technologies such as group and blind signatures. We provide both security analysis of our system and experimental results.

Finally, we address the research question RQ3: How to allow third parties to perform statistical analyses on the parking transaction data, in a privacy preserving way? Which PET can be used to support this task? To do so, we deploy mechanisms for privacy-preserving data processing to our parking system. Completed parking transactions are stored in a dataset, containing only a subset of the data items concerning the transaction information, following the data minimization principle. Using a Searchable Symmetric Encryption (SSE) scheme, this dataset is outsourced to an external search service and stored as a searchable encrypted dataset. The existing efficient and secure BIEX SSE scheme [START_REF] Kamara | Boolean searchable symmetric encryption with worst-case sub-linear complexity[END_REF], with high query expressiveness support is extended to the multi-client setting, to allow for authorized parties to perform searches on the encrypted dataset. In this manner, queries can be submitted to the search server to produce statistics on the parking system usage. A security analysis is provided for the proposed solution and experimental results show the applicability and efficiency of the system.

To our knowledge, our work in this paper is the first to consider both compliance to regulations (e.g., GDPR) and privacy protection for parking solutions. Most existing solutions mainly focus on some particular technological aspects such as route planning or autonomous parking. Our work is also very comprehensive by presenting both a technical design and an implementation to demonstrate its feasibility. From the figures in Section 5.4, it is clear that our parking solution is efficient enough to be deployed in practice.

P

Figure 1 :

 1 Figure 1: Privacy-preserving parking system.

Figure 2 :

 2 Figure 2: Register user.

Figure 4 : 4 .

 44 Figure 4: Park vehicle.

Figure 5 :

 5 Figure 5: Extend parking time.

2

 2 Art. 29 Working Party, Opinion 8/2014 on the Recent Developments on the Internet of Things, 16.09.2017, WP 223.3 EDPB, Guidelines 04/2019 on Article 25-Data Protection by Design and by Default, 20 October 2020,[START_REF] Edpd | [END_REF]

Figure 6 :

 6 Figure 6: WI-Schnorr partially blind signature.

1

  sk U +sk P SP 1 and the secret key sk U to the user over a secure channel and updates the PSP's revocation database RD by storing ID||sk U .

Figure 7 :

 7 Figure 7: Register algorithm.

Figure 8 :

 8 Figure 8: Issue algorithm.

1 }

 1 → P D = {PPID||PLTid||time duration||EPT} ε = ω + δ ? = H(g ρ 1 pk ω P LT ||g σ 1 F(P D) δ ||F(P D)|| Λ|| Λ||ĝ) π = SK{(sk U , sk Cred ) : Λ = Λ-sk U ∧ ĝ1 = g sk Cred

Figure 10 :

 10 Figure 10: Register algorithm implementing non-repudiation feature to the parking system.

2 .

 2 Extended scheme (see Section 5.2): The PSP checks e( Λ, pk -1 U ∈RD ) ? = e( Λ, g 2 ) for all pk -1 U ∈RD in RD. If any pk -1 U ∈RD holds in the equation then the user used corresponding sk U and pk -1

2 ) 1 , g 2 ) 2 ) 1 , g 2 )

 212212 Cred , g sk P SP = e(Λ sk Cred , g sk P SP •sk Cred +sk U •sk Cred -sk U •sk Cred sk P SP +sk U = e(Λ sk Cred , g sk P SP

Figure 11 :

 11 Figure 11: Time complexity of Revoke algorithm.

Figure 12 :

 12 Figure 12: Multi-client SSE functionality.

Figure 13 :

 13 Figure 13: Boolean Search time.

Figure 14 :Figure 15 :

 1415 Figure 14: Token creation time.

Table 2 :

 2 Benchmark tests of MCL library operations (modular arithmetic and elliptic curve) on Android devices.

		Device:	OnePlus Nord 5G		Honor 8X
		Elliptic curve:	BN254 [ms] BLS12 381 [ms] BN254 [ms] BLS12 381 [ms]
		addF (addition)	0.051	0.040	0.036	0.130
		subF (subtraction)	0.029	0.023	0.035	0.032
	F r	mulF (multiplication)	0.025	0.019	0.027	0.023
		divF (division)	0.081	0.091	0.145	0.149
		negF (negation)	0.016	0.019	0.020	0.023
		add1 (addition)	0.021	0.046	0.054	0.120
		sub1 (subtraction)	0.022	0.034	0.037	0.058
	G 1	mul1 (multiplication)	0.537	1.056	0.576	0.115
		dbl1 (doubling)	0.020	0.024	0.066	0.023
		neg1 (negation)	0.016	0.018	0.020	0.020
		add2 (addition)	0.030	0.064	0.058	0.166
		sub2 (subtraction)	0.027	0.052	0.039	0.106
	G 2	mul2 (multiplication)	0.397	2.135	1.196	2.597
		dbl2 (doubling)	0.022	0.034	0.100	0.115
		neg2 (negation)	0.014	0.017	0.023	0.029
		powT (power)	1.545	2.843	2.070	3.667
	G T	mulT (multiplication)	0.040	0.061	0.102	0.142
		pairT (pairing)	2.808	7.527	3.025	9.687

Table 3 :

 3 Computation complexity of the cryptographic algorithms.

	Algorithm	User		PSP		Total
		Operations	Time [ms]	Operations	Time [ms] Time [ms]
	Register	-	-	1xmul1, 1xaddF	0.669	0.669
				1xdivF
	Algorithm	User		PLT		Total
		Operations	Time [ms]	Operations	Time [ms] Time [ms]
	Issue	7xmul1, 4xadd1	4.107	3xmul1, 1xadd1	1.715	5.821
		2xsubF, 4xaddF		2xsubF, 1xmulF
	Verify	2xmul1, 1xadd1,	1.225	3xmul1, 3xadd1	7.290	8.515
		1xaddF, 2xmulF		2xpairT
		1xsubF
	Update	9xmul1, 5xadd1,	5.331	6xmul1, 4xadd1	9.005	14.336
		5xaddF, 2xmulF		2xsubF, 1xmulF,
		3xsubF		2xpairT
	ca. 47 min (i.e., extended algorithm) to identify a malicious user. By using
	more powerful servers and palatalization techniques, the revocation time can be
	reduced significantly.

  11 . Experiments were executed on the Grid'5000 testbed12 with Intel Xeon Gold 6130 (Skylake, 2.10 GHz, 4 CPUs/node, 16 cores/CPU) processors and 60 GB of RAM, running Debian 11 (64-bit) OS. The experimental results confirm the correct functionality of the multi-client extension of the BIEX SSE scheme library. The performance evaluation of the MC-SSE library implementation shows that the properties of the original BIEX SSE scheme algorithm are retained, offering practical and efficient boolean search functionality.

EDPB, Guidelines 04/2019 on Article 25-Data Protection by Design and by Default, 20 October 2020, p.13 stating that "Access controls should be observed for the whole data flow during the processing". In the smart parking scenario, see for example the rules of access between the PSP and the PLT

ENISA, Cyber Security and Resilience of smart cars, December 2016, p.34 highlighting that in general, "the attack surface of a smart car is very large".

To comply with this requirement, vehicle manufacturers have to demonstrate the possibility to identify and manage cyber risks linked to their supply chains. This means, among others, being able to (i) identify risks associated to components or services of suppliers and (ii) manage the risks associated to providers of connected services on which vehicles may rely. To that extent, UNECE considers this requirement as implying implementation of information sharing process on cyber risks with suppliers and joint process of incident management. Use of contractual agreement defining cyber security requirements is heavily recommended. Hence, this requirement produces effects on suppliers as it creates a duty to collaborate with the vehicle manufacturers[START_REF]Proposals for Interpretation Documents for UN Regulation No. 155[END_REF]

https://gitlab.com/brno-axe/tacr-crypto/android-mcl-test

Clusion library: https://github.com/encryptedsystems/Clusion

https://github.com/encryptedsystems/Clusion

https://github.com/atasidou/MC-Clusion

https://hub.docker.com/r/atasidou/multi-client_clusion

Grid'5000 testbed: https://www.grid5000.fr/

Acknowledgments

This paper is partly supported in part by European Union's Horizon 2020 research and innovation program under grant agreement No 830892, project SPARTA, and in part by the Ministry of the Interior of the Czech Republic under grant VJ01030002. Author Florian Jacques has been partly supported by the project VIADUCT under the reference 7982 funded by Service Public de Wallonie (SPW), Belgium. The publication only reflects opinion of the authors. Experiments presented in Section 6 of this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).

If the proof π 1 is accepted by the user, the user homomorphicly encrypts its secret key sk U by computing e 2 = (e 1 /h n/2 ) r1 h (n/2+sk U )r1+r2q g r mod n 2 and computes commitment c 2 = g i h r mod n and its public key pk U = g sk U

2

. Then, the PSP and the user run the PK protocol: π 2 = P K{(sk U , r 1 , r 2 , sk ′ U , u, r) : e 2 /h n/2 = (e 1 /h n/2 ) r1 h sk ′ U (h q ) r2 g r mod n 2

∧ c 2 = g sk U h r mod n

If the proof π 2 is accepted by the PSP, the PSP decrypts (i.e., Paillier decryption) x = Dec(e 2 ) -n/2, computes Λ * = g ? = e( Λ, g 2 ) holds for any of pk U in its RD. If there exists an pk U for which this equation holds, pk U is linked with the user's ID, which is then sent to the corresponding identity provider to identify the user.

Security and Privacy Analysis

The proposed system is built on provable secure cryptographic primitives such as wBB signature [START_REF] Boneh | Short signatures without random oracles and the SDH assumption in bilinear groups[END_REF], group signature [START_REF] Hajny | Anonymous Data Collection Scheme from Short Group Signatures[END_REF], partially blind WI-Schnorr signature [START_REF] Abe | Provably secure partially blind signatures[END_REF] and secure two-party computation of wBB signature [START_REF] Belenkiy | Randomizable proofs and delegatable anonymous credentials[END_REF]. We refer to these papers for more details on their security analyses. In the security and privacy analysis of our proposal, we adopt the attacker model for the privacy-preserving parking system defined in [START_REF] Dzurenda | Privacy-Preserving Online Parking Based on Smart Contracts[END_REF] and apply it to our security and privacy requirements defined in Section 2. The attacker model considers both internal and external adversaries. In the case of internal attackers, the PSP and the PLT are considered honest-but-curious, while users can act maliciously. Entities omitting the proposed protocols to commit fraud are considered external attackers. Considering this adversary model, we get the security and privacy properties of our system and how they are fulfilled. Note that, we define four lemmas that are in line with our requirements from Section 2. See Section 2 for more details. Namely, Lemma 5.1 is in line with Conditional traceability and Revocation requirements, Lemma 5.2 is in line with Data confidentiality, Data privacy, Pseudonymity, and Unlinkability requirements, Lemma 5.3 is in line with Authentication requirement, and Lemma 5.4 is in line with Data authenticity integrity requirements.

Lemma 5.1. Revocable anonymity: Users' privacy is preserved as long as they do not try to commit fraud, in which case they can be identified.

-Then it calculates the union of all the common document identifiers

and finally replaces T 1 with the intersection of T i and T 1 .

At the end, the server outputs the remaining set of identifiers in T 1 , which is the resulting set of document identifiers for the query ∆.

The algorithm is run between the search client (C) and the storage and query server (S).

Note that the Setup and Search algorithms of the MC-SSE scheme are the same as the Setup and Search algorithms of the original BIEX scheme.

Security and Privacy Analysis

Our MC-SSE scheme is built over the BIEX scheme for which several SSE requirements have been proven. Based on the MC-SSE threat model presented in Section 6.2 and security and privacy requirements presented in Section 2.4, a security and privacy analysis is conducted below for each of the expected requirements: Lemma 6.1. Index and document privacy: S or any other entities are not able to deduce any sensitive information about the plaintext of the stored encrypted data, nor the associated keywords.

Proof. The resulting encrypted data obtained thanks to the MC-SSE Setup algorithm are exactly the same as the ones generated by the BIEX Setup algorithm. As a consequence, our MC-SSE scheme inherits from the requirement Index and document privacy of the BIEX scheme. Lemma 6.2. Access pattern privacy: S is not able to deduce any information about the data from the search results.

Proof. The search results obtained thanks to the MC-SSE Search algorithm are exactly the same as the ones obtained from the BIEX Search algorithm. As a consequence, our MC-SSE scheme inherits from the requirement access pattern privacy of the BIEX scheme. Lemma 6.3. Query privacy: S is not able to deduce the type of statistics being performed.

Proof. The search method applied by S thanks to the MC-SSE Search algorithm is the exact same method with the BIEX Search algorithm. As a consequence, our MC-SSE scheme inherits from the requirement access pattern privacy of the BIEX scheme. However, S is unable to deduce the type of performed statistics, is able to deduce that a client is doing the exact same request if C is reusing the same authorization token for the exact same request to S. To mitigate that issue, C must be careful not to reuse any elements of the authorization token to S, or should ask for a new authorization token to D (cf. Section 6.3). Lemma 6.4. Query authorization: Only authorized clients on authorized keywords only are able to extract statistics from S.

Proof. Our original MC-SSE scheme does not prevent itself against any client stealing an authorization token or a search token and issuing an illegitimate request to S. However, the unauthorized usage of tokens can be prevented as follows. D can issue a certificate of ownership for the authorized client. This certificate signed by D can be computed over a signed randomized accumulator Acc = g a i,j ∈Γ ai,j •ID C , where g is a group of prime order q, a i,j ∈ Z q are the elements of the authorization token Γ = (dtk i , gtk i , ltk j , gtk q ), and ID C ∈ Z q is the ID of search client (C). C receiving the certificate is then able to extract his own search token and to adapt the accumulator by removing the elements selected for his search token γ : Acc C = g a i,j ∈Γ\γ ai,j , where a i,j are all the elements of the authorization token Γ, excluding the elements of the search token γ itself. S can check the validity of the certificate issued for C by computing Acc a i,j ∈γ •ID C C and by checking that the signature is valid with regard to the resulting Acc C . Moreover, the underlying authenticated channel enables S to detect spoofing and replay attacks over the pair -certificate and search token. Lemma 6.5. Privilege escalation prevention: C is not able to collude with other clients to issue a valid search token over a superset of keywords which D did not authorize.

Proof. Suppose two clients C i and C j with authorization tokens Γ i authorizing keywords in vector W authi = (w i1 , • • • , w iq ) and Γ j authorizing keywords in W authj = (w j 1 , • • • , w j q ′ ), respectively (w j k are not elements of W authi ) try to collude to issue a new token for the superset of keywords authorized in Γ i and Γ j , to be able to perform cross-searches, i.e., queries combining keywords from the two disjoint authorization tokens. The resulting combined Γ ij for the keywords in W authij = (w i1 , • • • , w iq , w j 1 , • • • , w j q ′ ) will not be usable to perform cross-searches, as although Γ ij will contain the global tokens and dictionary tokens of all the combined keywords, it will not contain the local tokens for the combinations of keywords between the two authorization tokens. Therefore, authorization tokens could not be combined to authorize searches on combinations of keywords not already allowed by the initial authorization tokens, and the privilege escalation prevention is supported. Lemma 6.6. Data minimisation: The transaction data items stored are reduced only to the necessary data items for service usage analysis.

Proof. D needs to adequately select the set of keywords for limiting keywords to what is necessary for service usage analysis. The selection of keywords is a matter of regulation to respect and a matter of strategy for the company which needs relevant analysis results.