Corso di Laurea Magistrale in Ingegneria delle
Telecomunicazioni
A PRIVACY-FRIENDLY
FRAMEWORK FOR
VEHICLE-TO-GRID INTERACTIONS
Advisor: Prof. Giacomo Verticale
Assistant advisor: Dr. Cristina Rottondi
Simone Fontana
Matr. Nr. 800747
from a cold steel rail? A smile from a veil? Do you think you can tell? Did they get you to trade your heroes for ghosts? Hot ashes for trees? Hot air for a cool breeze? Cold comfort for change? And did you exchange a walk on part in the war for a lead role in a cage? How I wish, how I wish you were here. We’re just two lost souls swimming in a fish bowl, year after year, running over the same old ground. What have we found? The same old fears. Wish you were here.
(Roger Waters)
To Mario, Flavio and Emilio.
The diffusion of electric vehicles (EV), mainly forested by their low CO2 emissions,
is increasing the interest of the research community because of their powerful po-tentialities for a close integration with the Smart Grid environment.
Several studies have been carried out on the possible market penetration of EVs and on the impacts of their potentially massive introduction: on one hand their impact on the Grid stability must be addressed due to the possibly huge number of simultaneous requests for their energy charge/discharge; on the other hand, the EVs’ batteries can be seen as an immense energy storage bank that can be used to fill the Grid’s demand in case of energy shortage, due e.g. to fluctuations in the energy production pattern of Renewable Energy Sources (RESes). This can be done by accumulating energy in case of excessive energy generation and transferring it back to the Grid, whenever needed.
This kind of relation is known in literature as Vehicles-to-Grid (V2G) interac-tion and is enabled by the introducinterac-tion of a third-party entity called aggregator, appointed to schedule the recharge/discharge requests of the EVs’ batteries accord-ing to both the user’s needs and the current energy availability of the grid.
Unfortunately the introduction of EVs in the Smart Grid environment also arises issues concerning user’s privacy: indeed plugging the vehicles in the recharging
information.
This work aims at designing a secure framework for privacy-friendly V2G interac-tions, which allows the load aggregator to schedule the EV’s battery charge/discharge without exploiting personal informations concerning neither the current battery level, the charge/discharge rate, nor the instants in which the EV is plugged/unplugged.
Our work relies on a communication protocol which uses the Shamir Secret Sharing (SSS) threshold cryptosystem as main building block. After describing our proposed scheduling infrastructure and the associated communication protocol, we discuss the security properties of our solution and compare its performance to the optimal schedule achievable by means of an Integer Linear Program (ILP). The scheduling strategy can be aimed either at maximizing the ratio between the amount of charged/discharged energy to/from the vehicles’ batteries and the total amount of energy availability/request from the grid or to the minimization of the maximum cost paid by the vehicles’ owners.
La diffusione pervasiva dei veicoli elettrici, dovuta prevalentemente alle caratteris-tiche di riduzione dell’inquinamento atmosferico attraverso basse emissioni di CO2,
sta stimolando l’interesse della comunit`a scientifica attraverso una serie di nuove sfide legate allo sviluppo di interessanti propriet`a di integrazione con le Smart Grid.
In questo contesto, le auto elettriche possono costituire un’enorme riserva di energia disponibile che pu`o essere utilizzata per far fronte a situazioni di deficit energetico dovuto alla non-costante produzione di energia da parte delle sorgenti di energia rinnovabile (RES) della Grid (come energia solare, eolica, etc..).
Queste tipologie di interazioni sono conosciute in letteratura come Vehicle-to-Grid (V2G) interactions e sono realizzabili nella pratica attraverso l’introduzione di un aggregatore incaricato di schedulare le richieste di carica/scarica delle batterie dei veicoli elettrici in funzione sia dei bisogni dell’utente (necessit`a di avere il veicolo carico entro un determinta ora, etc..) che della disponibilit`a energetica della Grid, la quale varia nel tempo proprio a causa della natura intermittente delle RES.
Purtroppo l’introduzione dei veicoli elettrici nelle Smart Grid genera per`o prob-lemi legati alla privacy dell’utente: collegare i veicoli a infrastrutture di ricarica potrebbe rivelare informazioni private, inerenti alla localizzazione dell’utente e alle sue abitudini (ora in cui lascia l’abitazione per andare al lavoro, orario di rientro,
sumi del singolo utente oppure furti nelle abitazioni in base alle informazioni relative alla permanenza, dedotte dall’attaccante malintenzionato.
Questo lavoro mira, quindi, alla creazione di un’infrastruttura sicura per inter-azioni di tipo V2G nel pieno rispetto della prvacy degli utenti, in grado di schedulare le richieste dei veicoli elettrici, in funzione della disponibilit`a energetica della Grid, senza rivelare informazioni inerenti al livello corrente di energia delle batterie, al quantitativo di energia effettivamente ricaricata o agli istanti di tempo nei quali il veicolo `e collegato ad un punto di ricarica.
Il protocollo crittografico su cui si basa il nostro lavoro `e il crittosistema a soglia Shamir Secret Sharing (SSS). Dopo aver progettato l’infrastruttura di scheduling e il protocollo di comunicazione associato, abbiamo valutato le propriet`a di sicurezza che essa `e in grado di soddisfare per un determinata tipologia di attaccante.
Infine, abbiamo confrontato i risultati delle schedulazioni ottenute dalla nostra soluzione con quelle ottime ottenute attraverso la risoluzione di un modello di pro-grammazione lineare a variabili intere.
La strategia di schedulazione adottata in prima istanza mira a massimizzare il rap-porto tra il quantitativo di energia caricata/scaricata dalle/alle batterie dei veicoli ed il totale di energia disponibile/richiesta dalla Grid.
Infine abbiamo valutato il costo sostenuto dagli utenti per la ricarica della bat-teria del proprio veicolo in base alla schedulazione ottenuta con il nostro algoritmo, confrontandolo con un benchmark di riferimento fornito da un secondo modello di programmazione lineare intera (ILP) con l’obbietivo di minimizzare il massimo costo di carica sostenuto dagli utenti su un intervallo temporale giornaliero.
List of Figures x
List of Tables xi
1 INTRODUCTION 1
2 STATE OF THE ART 5
2.1 Brief Overview on Electric Vehicles and their Impacts on Electric
Utilities . . . 5
2.2 The Vehicle-to-Grid Concept . . . 7
2.2.1 Ancillary Services . . . 8
2.2.2 Archtecture . . . 10
2.2.3 V2G System Communications . . . 12
2.3 Security in V2G system . . . 13
2.3.1 Location Privacy in V2G Environment . . . 14
2.4 Related Work . . . 18
3 BACKGROUND 22 3.1 Concept of secret sharing . . . 22
3.2 Foundations and properties of Shamir’s Secret Sharing Scheme . . . . 23
3.3 Secure Comparison Protocols . . . 24
4 THE PRIVACY-FRIENDLY V2G COMMUNICATION
FRAME-WORK 26
4.1 Introduction . . . 26
4.2 Anonymizer-centric Infrastructure . . . 26
4.2.1 Design and Assumptions . . . 27
4.2.2 Working Principles . . . 29
4.3 Anonymizer-free Infrastructure . . . 33
4.3.1 Description and new parameters . . . 33
4.3.2 Working principles . . . 34
5 SECURITY ANALYSIS 38 5.1 Introduction . . . 38
5.2 Attacker Model . . . 38
5.3 Blindness Property . . . 39
5.3.1 Blindness in the Anonymizer-centric Infrastructure . . . 39
5.3.2 Blindness in the Anonymizer free Infrastructure . . . 40
5.4 Obliviousness Property . . . 42
5.5 Correctness . . . 44
6 BENCHMARKS AND PERFORMANCE EVALUATION 45 6.1 Introduction . . . 45
6.2 ILP Model . . . 45
6.2.1 Cost-based Optimization Model . . . 48
6.3 Performance Evaluations . . . 50
6.3.1 Cryptographic Implementation . . . 50
6.3.2 Computational Complexity . . . 50
6.3.3 Numerical Results . . . 51
A DETAILS OF THE IMPLEMENTATION 61
B ARCHITECTURES AND PROTOCOLS ADOPTED 64
B.1 Foundations of the RSA-KEM Key Transport Algorithm . . . 64 B.2 A Generic Public Key Infrastructure for Securing Car-to-X
Commu-nication . . . 65
Bibliography 68
Ringraziamenti 73
2.1 Direct Vehicle-to-Grid architecture. . . 11 2.2 Indirect V2G system architecture involving several aggregators. . . . 12 2.3 Simplified V2G interaction model. . . 14 2.4 Battery model. . . 15 2.5 Example of a scenario in which battery information lead to privacy
issues. . . 16 2.6 Limits of anonymity due to battery information. . . 17 4.1 The privacy-friendly Anonymizer-centric scheduling infrastructure. . . 27 4.2 Data exchange during the battery charge/discharge scheduling
pro-cedure . . . 28 4.3 The privacy-friendly Anonymizer free scheduling infrastructure. . . . 34 4.4 Data exchange during the battery charge/discharge scheduling
pro-cedure . . . 35 6.1 An example on how the energy available to the fleet is calculated
per each epoch. It is the difference between the windfarm’s energy production and the energy consumed by the buildings participating our simulation. . . 53
6.2 Comparison of optimal vs privacy-friendly scheduled battery charg-ing/discharging. Positive values indicate that the grid provides en-ergy to recharge the EVs’ batteries, while negative values indicate that energy provided by the batteries is injected into the grid. . . 54 6.3 Example of the selling price of the energy trend (in Dollars per Watt
[$/W]) along a day. . . 56 6.4 Comparison between the privacy-friendly scheduling algorithm and
the optimal solution provided by the cost-based ILP which aims to minimize the users’ expenses. . . 56 6.5 Maximum daily recharge cost by users. . . 57 A.1 The block diagram describing the relations among the functions of
the simulation framework . . . 63 B.1 Public Key Infrastructure (PKI) for Car-to-X (C2X) Communication. 66
2.1 Characteristics of Electric Battery, Hybrid and Fuel Cell Vehicles . . 6 4.1 List of main symbols. . . 29 6.1 Number of input/output messages per node for a single scheduling
epoch . . . 50 6.2 Computational load at each node for the scheduling of a single service
request . . . 51 6.3 Detail of operation costs . . . 52 6.4 Comparison of the performance of ILP vs. privacy-friendly scheduling 54 6.5 Comparison of the performance of the cost-based ILP vs.
INTRODUCTION
In the last years the urban electricity network has been revolutionized, evolving from a traditional and centralized model to a Smart and distributed one: the so called Smart Grid. Among the motivations, the most important is the reduction of atmospheric pollution due to low CO2 emissions through the massive use of
Renewable Energy Sources (RESes) for the energy generation. For that reason, we have also seen an increasing diffusion of Electric Vehicles (EVs) in the Smart Cities, which are changing the automotive industry due to their synergies with both the environment and the Smart Grids. EVs promise to reduce carbon emissions by exploiting RESes for battery recharge.
The pervasive introduction of EVs and their significant impact on the energy consumption trend is being investigated in the research communities, which have developed the concept of Vehicle-to-Grid (V2G) interactions. A V2G system uses electric vehicles (battery/fuel cell-powered or hybrid) as a storage bank to support the energy market with the aim of optimizing the power transfers between these two systems, taking into account their different, but compatible, needs.
The most important role for V2G may ultimately be in fostering power markets to rely more on ”green” energy. In fact the two largest renewable sources that
can be managed either by backup or storage exploiting the EVs’ batteries. V2G interactions also enable ancillary services, such as voltage control, regulation reserve, spinning reserve, and non-spinning reserve [1], provided by both loads and generators and aimed at supporting reliability and power quality of the power system.
To enable these kind of services, the introduction of an aggregator capable of coordinating the charging/discharging process is needed: an aggregation agent for electric vehicles is a commercial middleman between the grid operator and plug-in EVs which both provides ancillary services and participates in the electricity market with supply and demand energy bids [2]. Therefore, the role of the aggregator is crucial for the success of the V2G concept.
Hence, it is also important to define and study business models for such aggrega-tors: several studies have appeared where the aggregator, typically, provides some sales or discounts in exchange for being able to use a fraction of the energy stored in the EVs’ battery [1]. This requires that a large number of small transactions involving each single vehicle, which have to be tracked by the aggregator and could be accomplished with on-board equipment of the vehicle. These transactions in-clude charging requests sent from the fleet and the scheduling result decided by the aggregator for each time instant.
Unfortunately, data sent by the vehicles discloses informations concerning the time periods in which the EVs are plugged-in at the recharging stations and details about the expected amount of energy to be recharged in order to fulfill the user’s travelling needs. This arises privacy concerns since, this way, the travelling habits of the vehicle owners can be deducted by the aggregator (e.g. presence in a certain
robberies, information about vehicle maintenance could be inferred and exploited for insurance and warranties, or companies could perform targeted marketing for car-related services. Further, through some basic analysis of these data, both home and the workplace location of the user could be revealed. It has been shown that these two simple informations, even at a coarse resolution, are often sufficient to uniquely identify the EVs’ owners [5].
Therefore, in this work we propose a privacy-friendly infrastructure for V2G interactions which allows multiple aggregators to cooperate in order to define the charging/discharging schedule of a fleet of EVs without learning sensitive informa-tion about them.
The principles are the following: every data is split by the EVs in w parts called shares by means of Shamir Secret Sharing (SSS) threshold cryptosystem and each share is given to a different aggregator. The aggregators cooperatively schedule these recharge requests and give back the results to the fleet. The protocol [6] ensures that collusion of less of t ≤ w aggregators cannot reconstruct the data.
Then, we evaluate our scheduling mechanism in terms of computational complexity, message number and length, and compare its performance to the optimal results ob-tained by means of an ILP formulation which assumes full knowledge of the user’s battery related information. The objective of the ILP formulation can be either the maximization of the ratio between the amount of charged/discharged energy to/from the vehicles’ batteries and the total amount of grid’s energy availability/request, or the minimization of the maximum daily cost paid by the vehicle owners.
The remainder of the thesis is organized as follows: Chapter 2 overviews both the state of the art and the related work on this topic, whereas some basics about
in Chapter 3. The architecture of the privacy-preserving framework and its associ-ated communication protocol for the collaborative scheduling of the battery charg-ing/discharging periods are presented in Chapter 4, while a security analysis of the model and its properties, the presentation of the benchmark models and the eval-uation of the performances and the numerical results are discussed, respectively in Chapter 5 and 6. Finally, Chapter 7 provides some conclusions.
STATE OF THE ART
In this chapter, we present the state of the art related to the current technology concerning Electric Vehicles and their impact on electric utilities, Vehicle-to-Grid (V2G) interactions and the security threats they expose. Finally, we show a survey of the related work out by academic researchers.
2.1
Brief Overview on Electric Vehicles and their
Impacts on Electric Utilities
With the advent of more stringent regulations related to emissions, fuel economy, and global warming, as well as energy resource constraints, electric, hybrid, and fuel-cell vehicles have attracted increasing attention from vehicle constructors, gov-ernments, and consumers. Research and development efforts have focused on de-veloping advanced and efficient energy systems. There are basically three kind of electric vehicles currently available:
Battery-powered electric vehicles (BEVs) seem like an ideal solution to deal with the energy crisis and global warming since they have zero oil consumption and zero emissions in situ. However, factors such as high initial cost, short driving range, and long charging time have highlighted their limitations.
Table 2.1: Characteristics of Electric Battery, Hybrid and Fuel Cell Vehicles
BEV HEV FCV
Propulsion Electric motor Electric motor Electric motor
drives drives drives
Internal combustion engine
Energy Battery Battery Battery
storage Supercapacitors Supercapacitors Hydrogen tank
subsystem Fossil or alternative Supercapacitors
fuels
Major Battery management Battery management Fuel cell cost
issues Charging Facilities Control, optimization Full cell life cycle
Cost and management of Cost
Battery lifetime multiple energy Distribution
sources infrastructure
Hybrid electric vehicles (HEVs) were developed to overcome the limitations of internal combustion engines vehicles and BEVs. An HEV combines a conventional propulsion system with an electrical energy storage system and an electric machine. When HEVs are driven in the electric mode, it is possible to obtain zero emissions, while a longer driving range is exploitable using the internal combustion engine.
Fuel cell vehicles (FCVs) use fuel cells to generate electricity from hydrogen and air. The electricity is either used to drive the vehicle or stored in an energy-storage device, such as a battery pack or supercapacitors. FCVs emit only water vapor and have the potential to be highly efficient.
Table 2.1 sums up some characteristics and major issues of electric vehicles. In general, EV battery capacity can range from 12 kW to 17 kW while the charge time is usually several hours.
The power demand for EVs recharge is a function of the voltage and current of the charger. The capacity of the battery then determines the length of charging time.
For example, a 120 V AC charger, depending on the battery pack sizes, charging time can range from 3 to 8 hours. Larger battery packs (for longer range) would require higher voltage or current to reduce the charging time.
Although the demand of an electric vehicle over whole power generation capacity may not be extremely significant, the possible impacts on power delivery systems, especially the distribution system, can be an issue if the charge is totally uncon-trolled. Specifically, they lead to possible power quality issues introducing harmonic distortion in the distribution system. This is due to the conversion of low voltage AC power to DC. Furthermore, the distribution transformer is designed for specific load carrying capability based on typical load consumption patterns. When EVs are deployed, the electric power demand pattern changes. The distribution system may not be capable of handling the new pattern and level of demand and the problem could lead to transformers degradation and failures.
2.2
The Vehicle-to-Grid Concept
The vehicle-to-grid (V2G) concept was introduced in 1997 by Kempton and Letendre [7]. Under this concept, whenever the charge is bidirectional (i.e., the infrastructure is both able to deliver power to the grid and also to charge the battery), the electrical network could receive power from a parked EV. This concept enhances the former paradigm where the vehicles were merely additional loads for charging batteries.
Most personal transportation vehicles sit parked more than 20 hours a day, dur-ing which time they represent an idle asset. Vehicles that incorporate electric propul-sion can be utilized as power sources while parked because their drive systems in-clude the fundamental elements for generating AC power. Utilizing idle vehicles to provide valuable electric power functions can produce a positive net revenue stream and create a powerful economic incentive to own an electrically-propelled vehicle.
The range of valued electric power services provided by electric vehicles is broad, and includes mobile AC power, backup power for homes or businesses, power gen-eration during peak demand periods, and grid ancillary services such as spinning reserves, regulation, automatic generation control, reactive power, and transmission stabilization. Most of these functions already have established economic value when procured from non-vehicular sources.
Kempton and Dhanju [8] computed the potential power of V2G for several coun-tries, assuming a maximum electrical plug capacity of 15 kW. For example, in Por-tugal, 5.8 millions of vehicles would lead to 87 GW, for an average load of 5 GW; Germany, with 44.6 million of vehicles has a potential of 670 GW, for an average load of 58 GW.
2.2.1
Ancillary Services
As mentioned before, a key benefit of a V2G power system is to facilitate and encourage EV participation in offering various ancillary services to the power grid through adequate communications. To start, in this section we overview different services that can potentially be offered in a V2G power system.
Reserve Power Supply
A large-scale V2G system can help maintain the balance between supply and demand in power grid by injecting power. For example, by simultaneously discharging their batteries, thousands of EVs will be able to provide the additional power required by a medium-size factory at a certain time period, acting similarly to a so-called spinning reserve power generation source in the existing power distribution system. While the supply capacity for each individual EV is small, a synchronized aggregated capacity can be both noticeable ad manageable by, for instance, an Aggregator.
Peak Shaving
In a nutshell, peak shaving is the process of reducing the amount of energy purchased from the utility company during peak hours when the charges are highest. A group of EVs can also participate in peak shaving by coordinating charging their batteries at off-peak hours and discharging them at peak hours.
Renewable Energy Source (RES) integration
Due to the stochastic and intermittent nature of solar and wind-power generation, their large-scale integration into the current power grid requires large-capacity stor-age system [1]. In our proposal, we consider wind power as renewable energy source: its variable nature in energy generation is mainly due to the changes of wind speed, since other on-site condition changes are relatively slow.
While a centralized control using a massive battery bank is very expensive, and thus may not always be practical, a distributed V2G power storage system can be implemented to solve this problem. In fact, with a distributed V2G storage system in place, the EVs can be charged at off-peak hours as a base load and discharged at peak hours to act as an extra power source to help the peaking generator, and thus reduce the cost of power generation.
Regulation
A V2G system can help to regulate frequency and voltage in a power grid. For instance, in the USA the grid frequency needs to be maintained very close to its nominal value of 60 Hz. Any deviation from this requires action by the grid operator [9]. If the frequency is too high, then there is too much power being generated with respect to load. Therefore, the load must be increased or the generation has to be reduced in order to keep the system in balance. EVs can thus help by charging their batteries and increasing the load demand.
system and the generation must me increased or reducing the load. This can be done by terminating charging or starting discharging a number of EVs connected to the grid.
Reactive Power Regulation
A large group of EVs can also help the power grid to regulate voltage. In the power system operation, voltage profile is strongly correlated with transmission and distribution system losses. This can cause damage to the grid equipments and user appliances. Voltage drops can be compensated by adjusting reactive power across the power grid. Interestingly, given the right power, EVs can help by changing their reactive and active power load, without any major impact on their battery life [10].
2.2.2
Archtecture
Various ancillary services, that we listed in Section 2.2.1, can be provided and man-aged using either direct or indirect V2G system architecture, as illustrated in Figure 2.1 and Figure 2.2 respectively. In a direct architecture, there exits a direct line of communication between the grid system operator and the vehicle, so that each vehi-cle can be treated as a deterministic resource to be commanded by the grid operator. Under this paradigm, each vehicle is allowed to individually bid and perform services while it is at the charging station. This architecture is conceptually simple but it has issues in terms of scalability.
In our proposal, we use an indirect V2G architecture which involves several aggregators that aggregates the ancillary services provided by individual EVs to handle them as a single controllable power source. This architecture is indirect as aggregators operate as middleman between the vehicles and the grid operator.
GRID OPERATOR V2G communication line
Figure 2.1: Direct Vehicle-to-Grid architecture.
and issues charging or discharging commands to contracted vehicles that are both available and willing to perform the required service. They are the key elements in a indirect V2G system architecture. In general, an aggregator may behave according to one of the following three roles:
• representing the grid operator to best serve the grid, for instance maximizing EV participation in providing ancillary services while minimizing the cost of obtaining such services;
• representing a group of EVs, for example in order to maximize their profit when offering ancillary services. In this case, to be successful the aggregator should assure efficiency and fairness among the participating EVS;
GRID OPERATOR V2G communication line
Figure 2.2: Indirect V2G system architecture involving several aggregators.
• acting as an independent entity, trying to maximize its own profit.
2.2.3
V2G System Communications
Communication in V2G system include message exchange between the grid operator and the aggregators and between each aggregators and its corresponding group of EVs.
Power-line Communication
Power-line communication is a technology that utilizes existing power line conduc-tors for data transmission: high-frequency data signals are superimposed on the top of the distribution voltage. Typically, transformers prevent Power-line
communica-tion signals propagating, thus making it difficult to use over high-voltage lines. The vehicle has to be plugged in to communicate using this technology.
Cellular Network
The cellular network is a widely available long-range wireless data transmission in-frastructure with high coverage, making it a good option for highly mobile devices such EVs [11]. With the cellular connectivity, Evs could communicate with aggre-gators wherever they are, even if are travelling. Our proposal relies on this kind of communication technology.
2.3
Security in V2G system
Security is a key challenge in V2G communications. In fact, although the two-way communication capabilities and distributed intelligence in V2G systems can improve efficiency and offer new opportunities such as users’ participation in the ancillary service market, these new features can also create new vulnerabilities in the power infrastructures if they are not accompanied with property security enforcements [12].
First, to assure user’s privacy, the charging status of the EVs’ locations should not be disclosed to any unauthorized third party. Second, it is crucial to avoid unauthorized discharging of vehicles’ batteries by potential intruders. Third, V2G systems need to be strictly protected against the so-called distributed Internet-based load-altering attack, in which an attacker uses malicious software to remotely access the EVs through the V2G communication infrastructure and to simultaneously trig-ger the charging phase for a large number of EVs in order to either degrade power quality, damage consumer equipment or even cause blackouts.
COMMUNICATION AGGREGATOR CHARGE STATION VEHICLE DATABASE
Figure 2.3: Simplified V2G interaction model.
2.3.1
Location Privacy in V2G Environment
In our work, we focus on the problem of ensuring a privacy-friendly framework which allows vehicles to perform operations in a V2G system. The communication of the vehicles’ locations and statuses to the aggregator is of key importance here. Such information can potentially reveal the travelling pattern of vehicle throughout a day and thus sensitive details about the personal life of its owner.
In practice, vehicles need a certain time to travel between two charging stations. Thus an aggregator can relate knowledge on needed travelling times to observed disconnection and reconnection events to reduce vehicle anonymity. Referring to the model proposed in [13], when a vehicle owner parks his electric-drive vehicle, he connects it to a charging station as depicted in Figure 2.3.
The vehicle then determines at which location it is connected to the grid and sets up communication with the responsible aggregator. The adversary’s goal is to identify vehicles at locations. He can do so either directly or by correlating distinct
0 C
t T
SoC
Figure 2.4: Battery model.
V2G connections, meaning by tracing a vehicle from location to location.
Generally, after the home, the workplace is arguably the second most easily identi-fiable location in a trace. Therefore, it is likely that over time in such profiles home and work locations will appear with a higher frequency than other locations and thus become identifiable. In [5], Golle and Partridge show that an individual’s pair of home and working location can reveal a person’s identity with high probability. Thus, anonymity does not only depend on network-layer anonymity but also on the unlinkability of V2G instances.
Battery Information and Anonymity
Before we analyse how battery information can affect privacy, let us discuss which information we need to consider. In theory, we can characterize a battery using two values, its capacity C and its State of Charge (SoC ). The latter, SoC ∈ [0, 1] indicates the charge left relative to C.
In practice, however, as shown in Figure 2.4, a battery’s SoC is commonly restricted by both an upper and a lower limit which we denote by T ∈ [0, 1] and t ∈ [0, 1] respectively.
S
4S
3D
2D
1l
4l
3l
2l
1Figure 2.5: Example of a scenario in which battery information lead to privacy issues.
battery lifetime [14].
The effect of battery information on anonymity
The question we want to answer is what the adversary can deduce about a vehicle’ movements from the observed battery information.
Let us consider the example depicted in Figure 2.5 comprising four locations and two vehicles for our analysis. During the time frame I = (i1, i2, i3, i4), the adversary
observes four events.
At i1, one vehicle is observed disconnecting from location l1 and at i2 a second
one from l2. Later, at i3, a vehicle connects at location l3 and at i4 a second one at
l4. The adversary does, however, not know which vehicle moved to which location.
Looking at the first event at starting location l1, we can see that the aggregator
learns amongst others both the vehicle’s state of charge SoC at i1, its t, and C.
S
4S
3D
2D
1l
4l
3l
2l
1Figure 2.6: Limits of anonymity due to battery information.
vehicle leaving l1. The vehicle cannot move beyond this limit without reconnecting
and recharging, which would lead to a new observation.
Without loss of generality, let us denote this vehicle by v1 and the other vehicle
by v2.
The aggregator can thus identify v1’s candidate destination charging stations. We
denote this set by D1, as shown in Figure 2.5. Analogously, for v2 leaving from
l2, he can identify a set D2. Note that these sets include all possible destinations
independent of detours or unscheduled stops.
Similarly, at the destinations l3 and l4, the aggregator observes SoC, T, and C of
the vehicles. From the respective values, he can calculate (T − SoC)C, the energy a vehicle can have used to drive to a charging station. The potential starting locations form the sets S3 and S4 (see Figure 2.5) which, again, describe absolute mobility
Referring to Figure 2.5, it is clear how an attacker can determine exactly, with such information, the trip of each vehicle through the intersection between arrival and destination sets.
In this case, it is clear that v1 drove from l1 to l4 while v2 drove from l2 to l3.
However, there could be situation in which it is not so trivial to identify the identity of the vehicles as we can see in Figure 2.6. Here, the adversary is unable to determine the individual vehicle trips if certain conditions hold. Formally, for the destinations l3 and l4 it must to hold that they are in the intersection of the
sets of possible destinations D1 and D2, as in Figure 2.6. Moreover, for the starting
locations l1 and l2 it must hold that they are in the intersection of the possible
starting locations S3 and S4.
Unfortunately, the adversary’s observations are not limited to battery infor-mation. He can, e.g., also exploit that vehicles need a certain time to travel from one charging station to another and can compare such times to the observed events. With these assumptions, under certain hypothesis listed in [13], it is pos-sible to demonstrate that even in such uncertain scenario, relations among charg-ing/discharging events to vehicles are possible (the reader is referred to [13] for further information about this latter case).
2.4
Related Work
The design of the Electric Vehicles (EVs) and their integration with the Electric Power Grid have been widely discussed and investigated in the last decade: Alec et al. [15] show that both battery and hybrid electric vehicles can efficiently support the Grid by providing a number of functions known collectively as ancillary services.
the issues of the integration within the power grid system have been addressed: Liu et al. [16] analyse deeply the impact of the introduction of EVs in the Smart Grid ecosystem. The authors conclude that, although their energy demand of the EVs may not be significant with respect to the overall power generation capacity, the possible impacts on power delivery systems (e.g. phase imbalance, transformer degradation and failure and so on), especially on the distribution system, can be an issue if the charging process is totally uncontrolled.
A complete overview of economical and technical models could be found in Bessa et al. [2] which provides a comprehensive bibliographic survey on the aggregator role in the power system operation and electricity market. The vehicle-to-grid (V2G) concept was, instead, introduced in 2001 by Kempton and Letendre [7]. Under this concept, the electrical network could receive power from a parked EV, and in this case the energy exchange is bidirectional (i.e. it is possible both to deliver power to the grid and to charge the battery). A complete survey on this concept is provided by Kempton et al. [1] which examine the systems and processes needed for the battery charge/discharge procedure and the implementation of V2G.
Numerous studies on optimal strategies for EV’s battery recharge have appeared: among those Han et al. [17] investigate a scenario where the charge station is modelled as an entity driven by its own profit. They formulate the interactions between the charge station and multiple EVs as a game with the aim of maximizing the charge station’s profit, in which two kinds of EVs (cooperative EVs and selfish EVs) are considered. We also categorize EVs in two sets: those whose battery current level of energy is below a certain minimum threshold, are classified as high priority vehicles and they must necessarily be charged, while low priority vehicles i.e. those whose current level of energy is above the minimum threshold can be either charged or discharged according to the current grid energy availability.
Mets et al. [18] present smart energy control strategies based on quadratic programming for charging EVs, aiming to minimize the peak load and flatten the overall load profile, both in presence or absence of information about the trend of local and neighborhood energy usage. Similarly, our scheduling algorithm assumes knowledge of energy’s grid availability in each instant of time thanks to dedicated hardware and software (e.g. as proposed Bychkovsky et al. in [19]).
Jawurek et al. [20] make a deep overview over the options for the privacy tech-nologies for Smart Grid: unfortunately only few works focus on the security and privacy concerns in the context of V2G interactions. Stegelmann and Kesdogan [13] discuss how an adversary can use information inherent to vehicles’ plug/unplug events to decrease the owner’s privacy. They also list the security properties that a V2G network should satisfy, under the assumption that the aggregator is an honest-but-curious entity. According to this adversarial model, the aggregator does not deviate from the protocol, but tries to analyse the information that it can observe at the charging stations and legitimately learn during V2G interactions. It then analyses this information with the aim of identifying the identity of the EV’s own-ers.
The same authors further refine such adversary model in [21], which assume that the aggregator also collects auxiliary informations concerning the vehicles. Specif-ically, they analyse the role of battery information and reveal how it can influence vehicle identification. Our attack scenario assumes the same adversary model, and our proposed protocol discloses to the aggregator no information regarding recharg-ing/discharging periods, the battery level and the amount of refilled energy. The only information available at the aggregators is a priority tag which declares whether the EV must be necessarily charged or could also be discharged, according to the current battery charge level, which remains undisclosed.
Yang et al. [22] propose a reward scheme in a V2G network with an honest-but-curious aggregator. They use a scheme based on blind signature techniques which enables a recipient to obtain the signature of a message without revealing this message to the signer. Our work relies instead on Shamir Secret Sharing (SSS) threshold cryptosystem, which is computationally less consuming, but requires the collaboration of multiple entities.
A payment mechanism for V2G interactions ensuring anonymity is discussed by Liu et al. in [23]: the authors provide a scheme to enhance location privacy of electric vehicles, by proposing an anonymous payment system with privacy protec-tion support. Their technique further allows traceability in case the cars are stolen. Similarly, Nicanfar et al. [24] propose a pseudonym-based authentication protocol that ensures untraceability of the users’ movements and assumes an external trusted entity in charge of recording the association between pseudonyms and real entities in order to provide accountability for billing purposes.
BACKGROUND
3.1
Concept of secret sharing
Secret sharing is a technique for protecting sensitive data (e.g. cryptographic keys). It is used to divide a secret value in a number of parts (shares) that have to be combined together to access the original value. Sharing a secret spreads the risk of compromising the value across several parties. To illustrate the concept of secret sharing, we use the following classical example [6]. Assume that there is a corpo-ration where the management needs to digitally sign cheques. The president can sign cheques on his/her own, the vice presidents need at least another member of the board to give a signature and other board members need at least two other managers to sign a cheque.
We can solve this problem by sharing the secret key needed for giving a signature with a 3-out-of-w threshold secret sharing scheme, where w is the required number of shares. We give the company president three shares, so he or she can sign the cheque alone. Vice presidents get two shares each, so that they need the agreement of another manager to give a signature. Other members of the board get one share per member, so that three of them are needed for a signature.
infor-mation. It requires the members of the board to provide three shares to retrieve the signature key. This key is used for a single signature and then forgotten so the next signature will again require three shares of the key. If a malicious adversary coerces one manager to sign a cheque, then it has to be the president of the corporation. Otherwise the adversary will have to persuade more than one member of the board. The first secret sharing schemes were proposed by Shamir and Blakley [25]. Our framework is based on the algorithm developed by Shamir in 1979.
3.2
Foundations and properties of Shamir’s
Se-cret Sharing Scheme
Shamir Secret Sharing (SSS) scheme [6] allows multiple collaborating entities to recover a secret previously divided in w shares and distributed among w participants. The secret can be easily reconstructed if at least t-out-of-w participants cooperate, where t ≤ w is an arbitrary integer design parameter. Knowledge of any t -1, or fewer, shares leaves the secret completely undetermined (i.e. all its possible values are equally likely). Such a scheme is called a (t,w) threshold scheme and it is ideally suited to applications in which a group of mutually suspicious individuals with conflicting interests must cooperate.
More specifically, the SSS scheme is based on polynomial1 interpolation and operates by choosing a prime number q, selecting t -1 integer random numbers ρ1, ρ2, ..., ρt−1 uniformly distributed in [0, q − 1], and splitting the secret m ∈ Zq
in w shares (xs, ys) such that 1 ≤ s ≤ w by calculating the s-th share as ys =
m + ρ1xs+ ρ2x2s + ... + ρt−1xt−1s mod q, where xs ∈ Zq is arbitrarily chosen.
Fi-nally, the secret m can be recovered in presence of t or more shares, by means of an interpolation algorithm.
1The polynomials can be replaced by any other collection of functions which are easy to evaluate
One of the most powerful properties of SSS is that, once shares are distributed, they can both be summed and multiplied together leading the same result that would be obtained by operating on the secret directly. This is due to the homomorphic property provided by SSS.
Definition 1. Let s and t be two values and [s] = [s1, ..., sw] and [t] = [t1, ..., tw]
be their shares. A secret sharing scheme is (⊕, ⊗)-homomorphic if shares [(s1 ⊗
t), ..., (sw ⊗ t)] uniquely determine the value s ⊕ t.
Since the addition and multiplication for a scalar are based on linear transfor-mations, a single participant can perform them autonomously. Unfortunately mul-tiplication between shares requires an interactive and collaborative protocol since it cannot be solved with the linear property of the transformation i.e. multiplying two polynomials with the same degree gives a polynomial with a double degree w.r.t. sources polynomials.
It follows that any function containing only additions and multiplications can be calculated without directly accessing the secrets. In particular, numerous collabo-rative procedures to compare two secret values have been proposed. In this work, we will adopt the comparison protocol presented in [26].
3.3
Secure Comparison Protocols
Secure Multiparty Computation (SMC) allows a number of mutually distrustful parties to carry out a joint computation of a function of their inputs, while preserv-ing the privacy of the inputs. We adopt an efficient secure comparison protocol, originally proposed in [26], to compute operations directly over the shares. This is possible thanks to the homomorphic properties (Definition 1) os SSS. However, while addition can be performed locally by an addition of the local (plaintext) shares,
Specifically, given a pair of input values m and m0, the objective of the secure comparison protocol is to compute the value of the boolean expression [m ≤ m0] ∈ {0, 1}, while ensuring that none of the parties gain knowledge of the actual input values. We further require the outputs to be private as well, i.e. the output bit is either encrypted or shared among the parties.
The main works as follows: each part, holding the s-th shares (xs, ys), (x0s, y 0 s)
of the secrets m and m0 to be compared, selects two big random numbers rs, r0s
which can multiplicatively hide2 m − m0, and a random bit b
s ∈ {0, 1}. The
collaborative protocol enables each party to obtain a share of the quantity c = (m − m0)Qt s=1(−1) bsr s − Pt s=1(−1) 1−bsr0
s. Then all parties collaboratively
recon-struct c and set a bit e either to 0 in case c > 0 or to 1 otherwise3. Finally, the following XOR operation ξ = e ⊕ b1⊕ ... ⊕ bt yields 0 if m > m0. Otherwise, in case
that m ≤ m0, ξ = 1 .
The correctness of the protocol can be argued as follow: let [m ≤ m0] = 0, i.e. m > m0. Given this, if e = 0 (i.e., c is positive), then it implies that the number of ”coins” flipped bi = 1 is even. As result, their XOR value is 0, which further XORed
with e = 0 and coins flipped bj = 0 is still 0 = [m ≤ m0]. Further details about the
collaborative procedure and its performance can be retrieved in [26].
2multiplicatively hiding consists of hiding a value d = m − m0 by multiplying it with a much
larger random number r
3Note that in a modulo n field negative numbers are represented by the upper half of the range
THE PRIVACY-FRIENDLY V2G
COMMUNICATION
FRAMEWORK
4.1
Introduction
In this section, we propose two different infrastructures for our framework. The first comprises an Anonymizer which acts as a interface between the fleet of Electric Vehicles and the Aggregators. Its main function is to substitute the real ID of each Vehicle with a pseudonym with the aim of preserving its privacy. However, in case of the Anonymizer fails, this approach exposes the entire system to reliability issues. Therefore, we propose a second infrastructure in which the Anonymizer is not used anymore. This is possible through the execution of the scheduling algorithm vehicle-side rather than by the Aggregator.
4.2
Anonymizer-centric Infrastructure
As depicted in Figure 4.1, our proposed architecture comprises a set of EVs, V, a set of Aggregators, A, which collaboratively schedule the charge/discharge of the EVs’ batteries, and an Anonymizer which collects the messages sent by the EVs and replaces their IDs with pseudonyms before forwarding the messages to the
PRIVACY-FRIENDLY SCHEDULING CONFIGURATOR RECHARGE REQUESTS AGGREGATORS aA SCHEDULED CHARGE/DISCHARGE ENERGY AVALIABILITY INFORMATION ELECTRIC VEHICLES ANONYMIZER ANONYMIZED RECHARGE REQUESTS DEANONYMIZED SCHEDULED CHARGE/DISCHARGE
Figure 4.1: The privacy-friendly Anonymizer-centric scheduling infrastructure.
Aggregators. The Anonymizer also receives the charge/discharge schedules from the Aggregators and communicates each of them to the addressed EV.
4.2.1
Design and Assumptions
We make the following assumptions:
1. Every EV can access the Internet both while travelling and being parked thanks to dedicated hardware and software (e.g., as described in [19], [27]). 2. A Configurator node is responsible for the setup of a suitable public-key
in-frastructure (see Appendix B.2 for further information).
corre-Vehicle, v Anonymizer Aggregator, a Aggregator, a IDv, EKa e(bvi||Sa(γvi)||K vi e ) IDv, EKa e(bvi||Sa(γvi)||K vi e ) Πvi, EKa e(bvi||Sa(γvi)||K vi e ) Πvi, EKa e(bvi||Sa(γvi)||K vi e ) collaborative scheduling Πvi, EKvi e (ΓΠvi) EKvi e (ΓΠvi)
Figure 4.2: Data exchange during the battery charge/discharge scheduling procedure
sponding decryption algorithm D(Kd, ·). The hybrid scheme is assumed to be
IND-CPA secure [28] (i.e., it ensures message indistinguishability under cho-sen plaintext attack) and uses state-of-the-art secure public key cryptography and symmetric cryptography to transmit messages of any size.
4. Each Aggregator a ∈ A has its own pair of public/private keys (Kea, Kda) and all the EVs know the public keys of the Aggregators.
5. All the communication channels between the EVs, the Anonymizer, and the Aggregators are confidential and authenticated.
We also assume that time is divided in a set of epochs I of a finite duration T (e.g., in the order of minutes) and that at the beginning of each epoch i ∈ I the system operator communicates the maximum amount gi of power it can
pro-vide to recharge the Vehicles or it would need to discharge in order to satisfy the demands generated by other categories of critical loads (e.g., non-deferrable appli-ance). Such power supply/request curve is supposed to be public and known to all the Aggregators.
Table 4.1: List of main symbols.
Notation Description
V set of Vehicles (v is an element of the set) A set of Aggregators (a is an element of the set)
I set of time epochs (i is an element of the set) rv battery charging rate of Vehicle v
bvi recharge priority indicator of Vehicle v at epoch i
lvi battery charge level of Vehicle v at epoch i
γvi requested battery charge/discharge indicator of Vehicle v at epoch i
tv battery threshold level below which no discharge is accepted by Vehicle
v Kvi
e , Kdvi ephemeral encryption/decryption key-pair generated by Vehicle v at
epoch i
IDv identifier of Vehicle v
Πvi pseudonym attributed to Vehicle v at epoch i
Si set of the pseudonyms Πvi at epoch i
Γvi scheduled battery charge/discharge indicator of Vehicle v at epoch i
The design goal is to schedule the charge/discharge times of the EVs’ batteries through a collaborative procedures in order to satisfy the customers’ recharge re-quests while minimizing the difference between the power supplied (requested) by the grid and the power charged (discharged) to (from) the batteries, without ex-ceeding the grid overall power availability (request).
A pictorial view of the exchanged messages between Vehicles and Aggregators is presented in Figure 4.2, while a list of the main symbols is provided in Table 4.1.
4.2.2
Working Principles
Whenever a new epoch i starts, each Vehicle v ∈ V initializes a parameter γvi either
0, in case it is unable or unwilling to be charged/discharged (for instance because it is currently travelling or because its battery is already full) or to rv, which indicates
the Vehicle’s charge/discharge rate. Moreover, v defines a threshold tv indicating
the level of charge below which no discharge is accepted by the customer. In a worst-case scenario, tv equals the level of full battery charge, meaning that the
customer does not allow for any discharge. Let lvi be the battery charge level of v
at the beginning of epoch i: if lvi < tv, v sets a priority bit bvi to 1, otherwise to 0.
Further, v generates an ephemeral keypair (Kvi
e , Kdvi), which is refreshed at every
epoch. Then, v divides γvi in shares using a (w, t)-SSS scheme with parameters
t = w = |A|, thus obtaining |A| shares S1(γvi), ..., S|A|(γvi), and concatenates the
priority bit bvi and the ephemeral encryption key Kevi to each share Sa(γvi). For
the sake of easiness, in this paper we set as SSS threshold t = w, meaning that all the Aggregators must collaborate to perform the charge/discharge scheduling procedure. However, to improve resiliency to faults and malfunctions, t could be lower than w1. Finally, v encrypts b
vi||Sa(γvi)||Kevi using the public key Kea for each
Aggregator a ∈ A and sends the pair IDv, EKa
e(bvi||Sa(γvi)||K
vi
e ) to the Anonymizer,
where IDv is the identity of the vehicle v.
Let ΓΠvi be the scheduling output of the Vehicle associated to the pseudonym Πvi, which can be set by the Aggregators either to 1 if the Vehicle is scheduled for
recharge, to -1 if it is scheduled for discharge. or to 0 otherwise. Moreover, let Pi
be a variable which records the amount of power required for the charge/discharge scheduled during the current epoch i: positive values of Pi indicate that the grid
must provide power to charge the batteries, while negative values indicate that the energy collected from the batteries is injected in the grid.
Initially, a designed Aggregator a sets Pi to 0, divides it in shares and distributed
the shares Sa(Pi) to the Aggregators. Once all the pseudonymized messages from
every EV have been received by the Aggregators, each Aggregator a decrypts the incoming message using its private key Ka
d and retrieves the triple bvi||Sa(γvi)||Kevi
for each Vehicle v, then it operates according to Algorithm 1 as follows:
Algorithm 1 The Privacy-Friendly Scheduling Algorithm
1: On input of the epoch number i and of Πvi, bvi, Sa(γvi), Kevi ∀v ∈ V
2: Si ← {Πvi ∀v ∈ V}, Vh ← {Πvi∈ Si: bvi = 1}, Vl ← {Πvi ∈ Si: bvi = 0}, ΓΠvi ← bvi ∀Πvi∈ Si 3: Sa(Pi) ← Sa(Pi) + P v : Πvi∈Vh(γvi) 4: for all Πvi ∈ Vl do 5: if gi > 0 then
6: collaboratively compare Pi+ rv and gi
7: if Pi+ rv < gi then
8: Sa(Pi) ← Sa(Pi) + Sa(γvi), ΓΠvi ← 1 {The grid provides enough energy to recharge v}
9: else
10: collaboratively compare Pi and gi
11: if Pi > gi then
12: Sa(Pi) ← Sa(Pi) − Sa(γvi), ΓΠvi ← −1 {v is discharged to reduce the amount of energy taken from the grid}
13: end if
14: end if
15: else
16: collaboratively compare Pi− rv and gi
17: if Pi− rv > gi then
18: Sa(Pi) ← Sa(Pi) − Sa(γvi), ΓΠvi ← −1 {v is discharged to inject energy from the battery to the grid}
19: else
20: collaboratively compare Pi and gi
21: if Pi < gi then
22: Sa(Pi) ← Sa(Pi) + Sa(γvi), ΓΠvi ← 1 {v is charged to reduce the exces-sive amount of energy provided by the batteries to the grid}
23: end if
24: end if
25: end if
all the pseudonyms associated to Vehicles with bvi = 1 which do not allow
battery discharge, while all the other pseudonyms are grouped in Vl. Note that
the Vehicles whose pseudonyms are in Vh are considered to have high charge
priority, meaning that they will always be scheduled for recharge, regardless to the energy availability of the grid. Conversely, the Vehicles belonging to Vl can be either charged/discharged or not, in order to meet the grid power
offer/demand.
2. The recharge of each Vehicle with pseudonym Πvi ∈ Vh is scheduled for the
epoch i by setting ΓΠvi to 1 and the total power amount Pi is updated by adding the corresponding share Sa(γvi). Note that the additions are performed
directly on the shares, therefore the Aggregator operates without knowing the values γvi. In case γvi = 0, i.e., v is not available for recharge/discharge,
adding Sa(γvi) to Sa(Pi) does not alter the current values of Pi.
3. For each Vehicle associated to a pseudonym Πvi ∈ Vl, if gi > 0 (i.e., the grid
has a power surplus which can be used to recharge batteries), the Aggregators collaboratively compare Pi+ γvi and gi by means of the comparison protocol
presented in [26]. Without loss of generality, we assume that the Aggregator a is elected as responsible of defining the order of service of the vehicles in Vl
(which is randomly chosen at every epoch) and to communicate it to the other Aggregators. If the current power amount (including the recharge of v) does not exceed gi, v is scheduled for recharge, otherwise a second collaborative
comparison between Pi and gi is performed: if Pi exceed gi (meaning that the
current energy used to serve the the Vehicles exceed the grid’s power avail-ability), the discharge of v is scheduled, otherwise no charge/discharge takes place. Analogously, for gi < 0, Pi − γvi and gi are collaboratively compared
Aggregators compare again Pi to gi and if Pi < gi (i.e., the total discharged
energy exceeds the grid’s needs), v is recharged. Conversely, in case Pi ≥ gi,
no action is scheduled.
Once the scheduling procedure is concluded, a sends to the Anonymizer the scheduling output EKvi
e (ΓΠvi) encrypted under the ephemeral encryption key of ve-hicle v and the corresponding pseudonym Πvi. The Anonymizer receives the identity
IDv of the Vehicle associated to Πvi, forwards EKvi
e (ΓΠvi) to v, which obtain ΓΠvi by decrypting the message with its private ephemeral key Kdvi and schedules its battery charge/discharge accordingly.
4.3
Anonymizer-free Infrastructure
The drawback of the above described framework is that the Anonymizer could be considered as a single point of failure i.e., in case of failure, it would compromise the correct functioning of the whole system. A malicious attacker could deny the service provided by the Anonymizer through for instance a Denial of Service Attack (DoS) aiming to make it unavailable to the Vehicles. For that reason we proposed a second framework which allows the Electric Vehicles EVs to directly interact with the Aggregators in an anonymous way.
4.3.1
Description and new parameters
We consider the sets of Electric Vehicles V and Aggregators A used in the previous framework and maintain the same assumptions listed in Section 4.2.1. Further,we assume that time is organized in a set of epochs I of duration T and that whenever a new epoch i ∈ I starts, the grid managers inform all the Aggregators about the maximum amount gi+1 of energy which is expected to be available for the battery
recharge during the next epoch, or which would be absorbed by the grid to balance the energy requests generated by non-deferrable loads. Moreover, each epoch i is
PRIVACY-FRIENDLY SCHEDULING CONFIGURATOR RECHARGE REQUESTS AGGREGATORS aA RECHARGING STATION SCHEDULED CHARGE/DISCHARGE ENERGY AVALIABILITY INFORMATION ELECTRIC VEHICLE
Figure 4.3: The privacy-friendly Anonymizer free scheduling infrastructure.
divided in |V| time slots of duration τ ≤ |V|T . A graphical representation of this framework is depicted in Figure 4.3.
4.3.2
Working principles
During an initial setup phase, a randomly chosen Aggregator a initializes a counter dv = 0, ∀v ∈ V, which records the cumulative amount of charged/discharged energy
for each vehicle v ∈ V and which can be used for billing purpose, divides dv = 0
in |A| shares using (w,t)-SSS scheme with parameters t = w = |A| and distributed each share Sa(dv) to a different Aggregator a ∈ A.
Vehicle, v Aggregator, a Aggregator, a Sa(kv,i+1) Sa(kv,i+1) collaborative comparison Sa(cv,i+1)||Sa(c0v,i+1) Sa(cv,i+1)||Sa(c0v,i+1) Execution of Algorithm 1 Sa(θv,i+1) Sa(θv,i+1) counters update Figure 4.4: Data exchange during the battery charge/discharge scheduling procedure
charging/discharging processes of each EV for the successive epoch i + 1. The message exchanged among Vehicles and Aggregators during the execution of the scheduling protocol are shown in Figure 4.4. Again, let us consider Pias the variable
recording the amount of power required for the charge/discharge scheduled during the current epoch i ∈ I.
Initially, the Aggregator a sets Pi+1 to 0, divides it in shares and distributes the
shares Sa(Pi+1) to the Aggregators. Then, it randomly assigns to each vehicle v ∈ V
one of the |V| time slots within epoch i. The assignment is refreshed at every epoch, in order to ensure fairness. During the time slot assigned to Vehicle v, the following steps are executed:
1. v initializes a parameter kv,i+1 either to 0, in case it is unable or unwilling
to be charged/discharged during the i+1-th epoch or to rv. Then it sets a
priority bit Bv,i+1 to 1 if the vehicle necessarily needs to be recharged during
the next epoch (e.g. because the current battery level is extremely low), or to 0 otherwise. In the latter case, the battery of v could be either charged or
Algorithm 2 The Privacy-Friendly Scheduling Algorithm
1: On input of (S1(cv,i+1), . . . , S|A|(cv,i+1)) and (S1(c0v,i+1), . . . , S|A|(c0v,i+1))
2: θv,i+1← 0
3: if Bv,i+1 = 1 then
4: θv,i+1 ← rv {recharge is scheduled regardless to the grid energy availability}
5: else
6: if gi+1> 0 ∧ Pi+1+ kv,i+1< gi+1 or gi+1 < 0 ∧ Pi+1 < gi+1 then
7: θv,i+1← kv,i+1 {recharge is scheduled if the grid energy availability exceeds
the current overall power load or if the total power injected into the grid exceeds the grid’s energy request}
8: else
9: if gi+1> 0 ∧ Pi+1> gi+1 or gi+1< 0 ∧ Pi+1− kv,i+1> gi+1 then
10: θv,i+1 ← −kv,i+1 {discharge is scheduled if the grid energy availability
is not sufficient to serve the current load experienced by the grid or if the total power injected into the grid does not satisfy the grid’s energy request}
11: end if
12: end if
13: end if
discharged, according to the energy availability of the grid. Finally, v divides kv,i+1 in |A| shares S1(kv,i+1), ..., S|A|(kv,i+1) and distributes them among the
|A| Aggregators, so that each Aggregator receives a different share.
2. Upon reception of the respective shares, in case gi+1 > 0 the Aggregators
engage two collaborative procedures (see Chapter 3) to compare Pi+1+ kv,i+1
to gi+1, and Pi+1 to gi+1. Conversely, in case gi+1 < 0, the Aggregators
compare Pi+1− kv,i+1 to gi+1, and Pi+1 to gi+1. A the end of the comparison
protocol, each Aggregator a obtain the shares of the two comparison results Sa(cv,i+1), Sa(c0v,i+1) and sends the message Sa(cv,i+1)||Sa(c0v,i+1) to v.
3. v reconstructs the results of the two comparisons and schedules the battery charge/discharge according to Algorithm 2, which produces the scheduling output θv,i+1 ∈ {−rv, 0, rv}. The scheduling principle is the following: if the
i + 1-th epoch, regardless of the grid conditions. Otherwise, the battery might be charged or discharged according to the grid energy availability/request, or no actions is scheduled in case the grid energy balancing has already been reached. Then, v divides θv,i+1 in shares S1(θv,i+1), ..., S|A|(θv,i+1) and
commu-nicates each share to respective Aggregator.
SECURITY ANALYSIS
5.1
Introduction
In this chapter we discuss the adversarial model, state definitions of the privacy properties of our scheduling mechanism and provide proofs that such properties are guaranteed by our framework.
5.2
Attacker Model
Our attack scenario assumes that each Aggregator is honest-but-curious, meaning that it honestly executes the scheduling algorithm, but tries to obtain further infor-mation about:
• the current battery levels of the EVs • the amount of refilled energy
• the periods in which they are plugged in
in order to deduce the travelling patterns of the EVs by performing any desired elaboration on the received data. Moreover, it might collude with other Aggregators and access the messages they receive.
5.3
Blindness Property
Let us define the property of blindness for both the infrastructures discussed in Chapter 4.
5.3.1
Blindness in the Anonymizer-centric Infrastructure
Considering the infrastructure described in Section 4.2, we say that:
Definition 1. The scheduling infrastructure provides blindness if during any set of epochs I a collusion of ˜A Aggregators of cardinality | ˜A| < |A| cannot relate bvi
to the identity IDv of the Vehicle which generated it during any set of epochs Iand
obtains no additional information with respect to what is implied by the knowledge of Sa(kv,i+1), Sa(cv,i+1), Sa(c0v,i+1), Sa(θv,i+1) for each Aggregator a ∈ ˜A.
More formally, we define the Blind experiment, involving a challenger C ling the Anonymizer node and a probabilistic polynomial-time adversary D control-ling the set of colluded Aggregators ˜A : | ˜A| < A:
1. D selects four sets of Vehicles V0h, V0l, V1h, V1l ⊆ V : bvi= 1 ∀i ∈ I, v ∈ V0h, V1h∧
bvi = 0 ∀i ∈ I, v ∈ V0l, V1l ∧ |V0h| = |V1h| ∧ |V0l| = |V1l|, the identifiers IDv, the
values γvi and the random numbers ρ1, ρ2, . . . , ρt−1 to be used to divide each
γvi in shares for each Vehicle in V0h, V0l, V1h, V1l, and communicates them to C.
2. C selects a random bit b = {0, 1}, generates the pseudonyms Πviand the shares
Sa(γvi) ∀i ∈ I, a ∈ ˜A, v ∈ Vbh, Vbl and communicates them to D.
3. D outputs a bit b0.
The architecture provides |A|-blindness if:
P (b0 = b | Πvi, Sa(γvi)∀i ∈ I, a ∈ ˜A, v ∈ Vbh, Vbl) = P (b 0
= b) = 1 2
The proof that our proposed infrastructure is blind descends from the property of perfect secrecy of the SSS scheme [30] and can be constructed by straightforwardly extending the one provided in [31, Theorem 3] for two sets of shares to a scenario with |I|(|Vl| + |Vh|) sets of shares.
Proof. The theorem proves that, given two secrets m0, m1, two sets of their
shares S0, S1 of cardinality t − 1 and a random bit b ∈ {0, 1}, the probability that
an adversary provided with mb, S0, S1 can guess the correct value of b is 1/2.
Thus, it follows that:
P (b0 = b | Sa(γvi)∀i ∈ I, a ∈ ˜A, v ∈ Vbh, Vbl) = P (b 0
= b) = 1 2
The proof is completed by noting that the pseudonyms Πvi are random numbers
refreshed at every epoch, therefore the knowledge of Πvi does not provide any
ad-vantage to D: in particular, from the point of view of the collusion ˜A, if bvi = 1 no
Vehicle v appears to be more likely to be the sender of bvi than any other Vehicle
v ∈ Vh
b. Analogously, if bvi = 0, all the Vehicles in V l
b are equally likely to have
generated bvi. It follows that the collusion ˜A obtains no information to reconstruct
the succession of bvi generated by a given Vehicle v during the succession of epochs
I.
5.3.2
Blindness in the Anonymizer free Infrastructure
Let us consider now the second infrastructure (Section 4.3). We keep the Definition 1 while define the Blind II experiment, which still involves a challenger C controlling the set of Vehicles V and a probabilistic polynomial-time adversary D controlling the set of colluded Aggregators ˜A:
1. D selects two vehicles v0, v1 ∈ V and the values kv0,i, kv1,i, θv0,i, θv1,i, gi, Pi, ∀i ∈ ˜I and communicates them to C.
2. C selects a random bit b and computes Sa(kvb,i), Sa(θvb,i), ∀i ∈ ˜I, a ∈ ˜A, runs
the comparative procedure according to the value of gito obtain Sa(cvb,i), Sa(c0vb,i),
∀i ∈ ˜I, a ∈ ˜A while storing two lists La(cvb,i), La(c0vb,i) of the messages
re-ceived/sent by each Aggregators a ∈ ˜A during the execution, and gives the result to D.
3. D outputs a bit b0.
The architecture provide |A| − blindness if: P (b0 = b|S
a(kvb,i), Sa(θvb,i),La(cvb,i), La(c0vb,i), Sa(cvb,i), Sa(c0vb,i)∀i ∈ ˜I, a ∈ ˜A) =
= P (b0 = b) = 1
2
(5.1) Theorem 1. Both the privacy-preserving scheduling described in Chapter 4 provide |A| − blindness
Proof. The proof is, again, a consequence of the property of perfect secrecy of the SSS scheme [6] and shows that the content of all the input/output messages received/sent by the colluded Aggregators ˜A during the scheduling procedure leak no information about b. For a single time epoch i:
let K0, K1, Θ0, Θ1 be the random variables indicating the value of the parameters
kv0,i, kv1,i, θv0,i, θv1,i of Vehicles v0, v1. Since the values of K0, Θ0 are completely determined by the knowledge of K1, Θ1, it follows that:
P (b = 0|Sa(kvb,i), Sa(θvb,i), La(cvb,i), La(c0vb,i), Sa(cvb,i), Sa(c0vb,i)∀i ∈ ˜I, a ∈ ˜A) = = P (K0 = kv0,i, K1 = kv1,i, Θ0 = θv0,i, Θ1 = θv1,i| Sa(kvb,i), Sa(θvb,i), La(cvb,i), La(c0vb,i), Sa(cvb,i), Sa(c0vb,i)∀i ∈ ˜I, a ∈ ˜A) = = P (K0 = kv0,i, Θ0 = θv0,i| Sa(kvb,i), Sa(θvb,i), La(cvb,i), La(c0vb,i), Sa(cvb,i), Sa(c0vb,i)∀i ∈ ˜I, a ∈ ˜A) (5.2)
