Privacy-Preserving Billing for Local Energy Markets (Long Version)
Eman Alqahtani Mustafa A. Mustafa










E. Alqahtani and M. Mustafa



The University of Manchester, Manchester, UK 
eman.alqahtani@postgrad.manchester.ac.uk
 COSIC, KU Leuven, Leuven, 3001, Belgium
 FCIT, KAU, Jeddah, 1589, Saudi Arabia


Privacy-Preserving Billing for Local Energy Markets
    Eman Alqahtani1,3 Mustafa A. Mustafa1,2

    April 29, 2024
===================================================




 We propose a privacy-preserving billing protocol for local energy markets (PBP-LEMs) that takes into account market participants' energy volume deviations from their bids. PBP-LEMs enables a group of market entities to jointly compute participants’ bills in a decentralized and privacy-preserving manner without sacrificing correctness. It also mitigates risks on individuals’ privacy arising from any potential internal collusion. We first propose a novel, efficient, and privacy-preserving individual billing scheme, achieving information-theoretic security, which serves as a building block. PBP-LEMs utilizes this scheme, along with other techniques such as multiparty computation, Pedersen commitments and inner product functional encryption, to ensure data confidentiality and accuracy. Additionally, we present three approaches, resulting in different levels of privacy and performance. We prove that the protocol meets its security and privacy requirements and is feasible for deployment in real LEMs. Our analysis also shows variations in overall performance and identifies areas where overhead is concentrated based on the applied approach.








§ INTRODUCTION

In the quest of a sustainable energy future, the use of renewable energy sources (RESs) has increased widely, facilitating carbon emissions reduction. However, the inherent unpredictability and intermittency of their output poses challenges in existing traditional markets, leading to the emergence of local energy markets (LEMs). These markts enable prosumers – individuals who consume and produce energy – to actively participate in open markets, supporting direct trading of surplus energy with others. This contrasts with the traditional practice of selling excess energy to contracted suppliers at a feed-in-tariff (FiT) price, which is often lower than retail market prices (RP). Such a transition allows prosumers to optimise their profits by securing better prices and offers consumers the opportunity to reduce their expenses <cit.>.


LEMs typically require their participants to submit bids before the actual trading periods (ranging from 30
minutes to a day in advance) <cit.>. Therefore, market participants need to forecast the necessary bid volumes, indicating the amount of energy they intend to trade. This prediction relies on historical data and estimated consumption, making it inherently prone to errors and challenging to achieve absolute accuracy. Whether due to intentional actions or inaccuracies in predictions, participants may commit to trading specific energy volumes but subsequently fail to fulfill these commitments. 

As this failure can disrupt grid stability and increase balancing costs, market participants should be accounted for their deviations from their committed bid volumes during the billing process <cit.>. This consideration would incentivise the participants to reduce their deviations and, subsequently, the negative effect they cause on the grid. Furthermore, a market participant's deviation may cause a different level of effect on the grid depending on what part of the grid the participant resides in. As a result, some might bear higher costs for their deviations compared to others, not only due to their deviation amounts but also because of their specific locations on the grid. For example, the total deviation of households (i.e., market participants) connected to a particular distribution line may result in a total deviation of zero. That means the positive deviations of the households on that line compensate for the negative deviations. As such, it is rational not to account those individuals for their deviations regardless of the total deviation of the entire market area. 


The computation and settlement of bills and rewards for participants in LEMs, while considering their energy deviations from their bids, requires critical private information, such as individual bid volumes and meter readings for each trading period. Such information are closely associated with individuals' consumption patterns, which have been shown to pose potential risks to their privacy <cit.>. For example, personal details such as presence at home, sleep patterns or even the detection of particular appliance activation could be inferred from the amount of energy traded at a particular period <cit.>.

A number of previous studies have already addressed the privacy concerns of market participants during billing and settlement, employing techniques such as anonymization <cit.>, perturbation <cit.>, and homomorphic encryption <cit.>. However, the majority have primarily suggested payment approaches based only on bid commitments, assuming perfect fulfillment of the bid volumes. A very limited number of the privacy-preserving billing studies have considered establishing a billing mechanism based on the actual amount of produced/consumed energy by the market's participants <cit.> or to additionally account for their deviations <cit.>. However, the billing process is coordinated or executed by a single party <cit.>, assuming trustworthiness and honesty from that party in performing the billing process, disclosing some or all of the individuals private data to that trusted party and potentially imposing a high computational cost on a single party. All of the above raise questions about the applicability or scalability of their solutions in realistic scenarios. In contrast to the previously mentioned works, the solutions proposed by <cit.>, do not rely on a single entity for carrying out billing calculations. Instead, they involve a group of entities working together to compute individual bills/rewards privately. However, they are vulnerable to the risk of internal collusion, potentially leading to the disclosure of highly sensitive data such as individuals' meter readings and bid volumes. Additionally, market participants were uniformly charged for their deviations in all of the aforementioned works, irrespective of their positions on the grid, and the grid usage cost was not considered.





To address these limitations, in this paper, we propose a privacy-preserving billing protocol, considering participants' deviations and their locations on the grid. This work is an improvement on our previous study <cit.> to mitigate the impact of internal collusion on individuals' privacy. Specifically, the contributions of this paper are threefold:



  * We propose a novel efficient and privacy-preserving individual billing scheme (EPIBS) that achieves an information theoretic security which forms a building block for PBP-LEM. 

  * We design PBP-LEM - a privacy-preserving billing protocol that enables suppliers to obtain bills for their contracted customers in LEMs. PBP-LEM takes into account participants' energy volume deviations, their locations on the grid, and distribution network usage cost, all without revealing any individual participant's private data to any party. It involves a collaboration of different entities performing bill computation with verification of correctness. It also mitigates the potential impact on individuals' privacy resulting from internal collusion. We utilise our proposed scheme, EPIBS, as well as various cryptographic primitives, namely Pedersen commitments, multiparty computation (MPC), and function-hiding inner product encryption (FHIPE), to compute individual bills. We propose three different approaches, resulting in different levels of privacy and performance. 

 
  * We evaluate the computation and communication complexity of PBP-LEM under two security settings (honest-majority and dishonest-majority MPC) to demonstrate its feasibility in real-world settings. Our analysis shows variations in the overall performance and identifies parts where the overhead is majorly focused, depending on the employed approach. The implementation is publicly available at: <https://github.com/EmanAlqahtani/ZPPB-LEM2>.










 The rest of the paper is organised as follows. Section <ref> covers the related work. Section <ref> introduces our system model and its requirements. Section <ref> explains the utilised building blocks. Section <ref> describes PBP-LEM. Section <ref> provides security analysis, while Section <ref> evaluates the performance of PBP-LEM. Finally, Section <ref> concludes the paper.



§ RELATED WORK

Concerns regarding security and privacy in LEMs have been previously highlighted [13], prompting the proposal of several solutions using anonymization, perturbation, and homomorphic encryption techniques. Only a few of these solutions have considered applying their privacy approach to a billing mechanism based on the actual amount of exported/imported energy by market participants, as recorded by their smart meters (SMs) <cit.>. The work in <cit.> have also considered the participants' deviations from bid commitments.





The authors of <cit.> proposed a dynamic one-to-many accounts mapping technique to hide participant's trading distribution when their transactions are being recorded on blockchain. A key part of their works is a trusted entity, token bank, responsible for assigning each participant to multiple accounts based on a dynamically-styled bound that achieves the effect of deferential privacy. a major drawback of applying both <cit.> and <cit.> works in the real world  is the reliance on trusted identity management having access to user's accounts mappings and their transactions (i.e., which party could take this role in the real world and whether users are willing to reveal their transactions to them).

The works of <cit.> and <cit.> mainly focused on protecting the privacy of market participants during the market clearance phase. The employed FHIPE enabling a market operator to execute the market and perform peer matching on encrypted bids without accessing their details. To hide individuals' participation in the market, participants (both sellers and buyers) are anonymised, and a new identifier (pseudonym) is generated for every new session to prevent linkability. However, after the market is executed, the distribution system operator takes on the responsibility of invoicing participants. In doing so, it gains access to the bid contents, and the correspondence between real identities and the one-time identifiers utilised in each session. This results in a similar limitation to that found in the works of  <cit.>, where there is a reliance on a party to handle the billing process, revealing both the real identities and bid details to that party.


The studies conducted by <cit.> are the only ones that have considered imperfect fulfilment of bid volumes. The work in <cit.> proposed a privacy-preserving protocol for the three billing models outlined in <cit.> by utilizing the Paillier homomorphic encryption technique. This protocol enables a trading platform (market operator) to compute individuals' bills/rewards without revealing their most sensitive data. In detail, during each trading period, each SM encrypts its meter reading and the deviation from its bid volume using the homomorphic public key of their contracted suppliers. Subsequently, it sends the encrypted data, along with other less sensitive information (e.g., the type of individuals' participation), to the trading platform. The platform then calculates individuals' bills privately in accordance with one of the billing models and sends the results to the suppliers, which in turn decrypts them. However, this work has certain shortcomings. Firstly, some of the participants' private data, such as the type of participation (i.e., whether a user is selling or buying energy) and whether the bid was accepted or rejected, is disclosed to the trading platform. Secondly, the protocol requires a full trust in a single party – the trading platform – for accurate computation of bills/rewards for all market participants without any verification of correctness. 


Similar to the approach taken by <cit.>, the work in <cit.> used the Paillier homomorphic encryption technique to implement a privacy-preserving billing model, accounting for participants' deviations from their commitments. However, in contrast to <cit.>, this solution does not rely on a single party for executing the billing calculations. Instead, a randomly chosen set of market participants collaboratively computes individual bills/rewards in a private manner as follows: Individual private data are homomorphically encrypted using the supplier's keys and then transmitted to the chosen set, which, in turn, performs the computation privately. The solution also incorporates a referee to verify the correctness of bills/rewards computation simultaneously and intervene to resolve any disputes. The referee then sends the resultant encrypted bills/rewards to the supplier for decryption. However, a considerable limitation of this work is that it does not provide protection against collusion. For instance, any individual in the chosen set can collude with the supplier by providing it with others' encrypted individual data, subsequently enabling the supplier to decrypt the data and compromise the individuals' privacy. Another limitation is similar to that found in <cit.>, wherein the type of individual participation is disclosed. 





Our previous work <cit.> leveraged MPC technique to apply a privacy-preserving billing model considering participants' deviations from their bid volumes. Instead of relying on a single trusted party for computing the bills, our approach employs three parties to jointly compute individual bills while ensuring the confidentiality of all the market participants' data, 

including their types of participation. The solution has also been evaluated under malicious and dishonest majority settings, implying that the presence of at least one honest party is sufficient to detect errors during bill calculations, even if the other two parties were malicious. Nevertheless, even though the probability of collusion among all three parties is low, given that each is controlled by a different entity, 
any such occurrence could lead to the disclosure of highly sensitive data. 





Unlike the aforementioned works, PBP-LEM integrates the following features: (i) it charges for market participants who fail to fulfil their bid commitments, (ii) it incorporates the participants' locations on the grid to distribute deviation costs fairly and accounts for distribution network usage fees in the participants' bills, (iii) it does not rely on a single trusted party to compute individual bills, (iv) it mitigates the impact of potential collusion among internal parties by ensuring that only less sensitive data might be revealed in the event of such collusion, and (v) it protects all participants' private data including their types of participation.









§ SYSTEM MODEL AND REQUIREMENTS

In this section, we describe the system model, threat model as well as the functional and privacy requirements that PBP-LEM needs to satisfy.


 §.§ System Model

As shown in Fig. <ref>, our system model consists of the following entities. SMs are devices that measure and communicate the volumes of imported and exported energy by households in nearly real-time. Users are household owners supported by SMs and potentially RESs. They engage in a LEM to increase their profits and minimise their expenses. They submit bids (consisting of energy volume and offered price) to the LEM to sell surplus energy to others at a price higher than the Feed-in Tariff (FiT) price or buy energy at a price lower than the retail price (RP). Local Energy Market Operator (LEMO) executes the LEM, identifying both the trading price and the approved bids for trading in each trading period. Suppliers provide energy to all users in need. They buy electricity from the wholesale market and distribute it to their contracted customers in the retail market (RM) at RP determined by suppliers. They also purchase electricity injected by their customers that is not traded in the LEM at FiT price. Additionally, they generate and manage their customers' (i., users) bills based on their participation in the LEM. RM Regulators (RMRs) are entities that set FiT prices that users pay to their contracted suppliers for the energy they sell in the RM. Distribution System Operator (DSO) manages and maintains the distribution network of a particular area. It divides the LEM area into small zones based on the physical network specifications and historical data that estimate each zone state for each time period. DSO also sets energy importing and exporting fees for each zone. It also coordinates the redistribution of payments to/from the LEM between users performed through their suppliers. Computational Severs (CS) calculate the required deviation cost information (e.g., total global deviation) according to the zone-based billing model with universal cost split (ZBUCS) introduced in <cit.> which is a modification of the billing model proposed in <cit.>. To avoid collusion, the parties should have conflicting interests. We assume that one party is controlled by suppliers, one by users, and a third by the DSO. Key Authority (KA) generates the required encryption/decryption keys and provides them to the designated entities.









 §.§ Threat Model and Assumptions

LEMO, RMRs and suppliers are assumed to be semi-honest. They follow PBP-LEM honestly, but they may try to infer sensitive individual data. Suppliers may attempt to learn individual bids, meter readings, rewards/bills within the LEM for a particular trading period, or may try to access the bills of users who are contracted with other suppliers. In addition, the correctness of bill settlements performed by suppliers must be verified by DSO. Users are considered to be malicious. They may try to learn or manipulate their own (or other users') data (i.e., bid volumes, meter readings and deviations) to increase their profits or reduce their bills. External entities are also malicious. They may eavesdrop or modify transmitted data to disturb the billing process in LEM. 

We assume two different security settings for CS: honest majority and dishonest majority with active (malicious) adversaries. For the former, one of the three parties can be corrupted while the later allows the presence of two malicious parties. The corrupted parties may try to infer information about users' data (bids, meter readings, bills and deviations) or deviate from the protocol, for example, by sending faulty data during the computations to distort the result. In the case of deviation, honest parties should abort the execution. 

As the focus of this work is on protecting users' privacy, we make the following assumptions. The communication channels are private and authentic. All entities are time-synchronized. SMs are tamper-proof and sealed, meaning any attempt to tamper with them will be readily detected. 
 




 §.§ Functional Requirements




    
  * Each supplier should learn each of their customers' aggregated bills/rewards generated from their participation in LEM per billing period (e.g., monthly). 
    
  * Each supplier should learn its income balance incurred from selling (buying) the deviation shares to (from) their customers per trading slot. 
    
  * Each user should learn their own LEM bill/reward per billing period. 
 



 §.§ Security and Privacy Requirements

PBP-LEM should satisfy the following requirements:
  
      
  * Privacy preservation: exact users' locations, their participation in LEM, and the type of participation (selling or buying) should be hidden from all parties.
      
  * Confidentiality: users' bid volumes, meter readings, deviations, and bills/rewards per trading period from LEM should be hidden from all parties.  
      
  * Authorisation: aggregated users' bills and rewards from participating in LEM should be accessed only by their contracted suppliers.
      
  * Collusion Impact Mitigation: users' highly sensitive data (i.e., bid volumes and meter readings) should not be revealed in the event of internal collusion.
      
  * Accountability: reported capital exchanged within the LEM through each supplier should be verified for accuracy to ensure correct bill settlement.   
  



§ BUILDING BLOCKS

This section describes the foundational cryptographic techniques and building blocks utilized by PBP-LEM: function-hiding inner product functional encryption, pedersen commitment and multiparty computation. 



 §.§ Multiparty Computation

Multiparty Computation (MPC) enables a group of parties to jointly compute a function on their private inputs, revealing only the computation results and keeping individual data confidential <cit.>. This can be achieved through various cryptographic techniques such as secret sharing, oblivious transfer, and homomorphic encryption. The security provided by these techniques can either be perfect, offering unconditional security against adversaries, or computational/conditional, ensuring security given computational limitations on adversaries. Information-theoretic protocols such as BGW provide perfect security <cit.>, while protocols relying on public key primitives such as garbled circuits <cit.> and SPDZ <cit.> offer conditional security.

An essential property of MPC protocols is how many parties can be corrupted. While information-theoretic protocols offer stronger (perfect) security, they require an honest majority <cit.>. In contrast, computationally secure protocols can tolerate a dishonest majority; however, they tend to be more complex and expensive <cit.>. 
The MPC protocols employed in our work for each security setting are as follows:



  * Honest-Majority Setting: In this setting, we utilize an optimized secret sharing approach from <cit.> based on replicated secret sharing, specifically designed for three parties. This protocol minimizes communication and computation costs as every party sends only one element for each multiplication gate using pseudo-random zero sharing. To achieve malicious security, we use the protocol proposed by <cit.>, which uses information-theoretic tags as in SPDZ protocol to check for computation correctness. The protocol supports security with abort, aiming for high efficiency.

  * Dishonest-Majority Setting:
In this setting, we adopt the MASCOT protocol <cit.> for the malicious model. It is an improvement of the original SPDZ protocol, replacing the costly somewhat homomorphic encryption used for computing Beaver triples with oblivious transfer.





 §.§ Pedersen Commitments

One of the core techniques used by PBP-LEM is Pedersen Commitments. In essence, it allows one party to commit to a secret value and later reveal the committed value in such a way that it becomes hard to change the initially committed value <cit.>. Operating over a cyclic group G and based on the discrete logarithmic problem, Pedersen Commitments involve two fundamental functions:


  * Commit(m,r)→ c: takes a value m and a random value r. It generates a commitment c. Mathematically, let g and h be generators of G, then c= g^m . h^r mod p.

  * Open(c,m,r)→ true/false: takes a commitment c, a value m and a random value r. It generates true if c is a commitment of m and false otherwise. 

Pedersen Commitment has three main properties. It ensures hiding, where given only a commitment c, it is computationally infeasible to determine the original value m. It upholds binding; that is, given c, m and r, it is computationally infeasible to find a value m̅≠ m and a matching value r̅ such that Open(c,m̅,r̅) returns true. Finally, it satisfies a useful property known as homorphism, in which the product of two commitments equals the commitment to the sum of two initially committed values. 

    Commit(m_1,r_1) * Commit(m_2,r_2) = Commit(m_1+m_2,r_1+r_2)




 §.§ Inner Product Functional Encryption

Functional encryption (FE) is a special type of public key cryptography that allows the performance of some computations over encrypted data. In FE schemes, the owner of the master key (i.e., key distribution centre) can generate secret keys for parties wishing to learn only outputs of specific functions over secret inputs and nothing else <cit.>. In formal terms, given a ciphertext C corresponding to a plaintext x and a functional decryption key sk related to a function f, a decryptor can obtain the results
of f(x) without learning anything about x. 



  
Inner product functional encryption (IPE) is a a special scheme of FE, where data x is represented as a vector, functional decryption key sk_y is associated to a vector y. Then, given the ciphertext Ct_x of x, the owner of sk_y can evaluate <x.y> without learning x, which is the inner product of the vectors x and y. Function-hiding IPE (FHIPE) provides an additional property in which both x and y are kept secret from the function evaluator (i.e., the decryptor). In this work, we adopt the practical FHIPE scheme proposed in <cit.>. The original formulation of IPE schemes involves four algorithms: Setup, KeyGen, Encrypt, and Decrypt <cit.>. However, for some cases, a more intuitive representation suggests KeyGen be referred to as LeftEncrypt and Encrypt as RightEncrypt, as discussed in <cit.>. A theoretical description of the algorithms is given below. For technical details, please refer to the original work of <cit.>.



  * IPE.Setup(1_λ,S)→ (pp,msk) given a security parameter λ, Setup initializes the system and outputs the public parameters pp and  master key msk.

  * IPE.LeftEncrypt(msk,α,x)→ Ct_x given the master key msk, a vector x and a uniformly random element α, LeftEncrypt outputs a ciphertext Ct_x.

  * IPE.RightEncrypt(msk,α,y)→ Ct_y given the master key msk, a vector y and a uniformly distributed element β, RightEncrypt outputs Ct_y, 

  * IPE.Decrypt(pp,E_l(x),E_r(y)) → z given the public parameters pp, a ciphertext Ct_x. and a ciphertext Ct_y,  Decrypt outputs a message z such that z=<x,y>.





 §.§ Dual Binary Encoding for Integer Comparison Using Inner Products
 

In this work, we utilise a dual binary encoding scheme proposed by <cit.>. The scheme converts two integer numbers, x and y, into arrays of vectors with a limited number of elements to enable comparing these two numbers by means of multiple inner products. More specifically, x and y undergo two different encoding methods:

    
  * f_x(x)  → (X_v_l, X_v_g): on input a number x, the method f_x output two encoded arrays of vectors X_v_l=[x_0,l,x_1,l,...,x_N,l] and X_v_g= [x_0,g,x_1,g,...,x_N,g].
    
  * f_y(y) → Y_v: on input a number y, the method f_y output one encoded array of vector Y_v = [y_0,y_1,...,y_N]. [For technical details about the encoding processes, please refer to the work of <cit.>] 

By performing the inner products operations of <X_v_l,Y_v> and <X_v_g,Y_v> simultaneously, the results are interpreted as follows: 

    
  * If <x_n,l,y_n> = 0 is satisfied first, it indicates that x<y.
 
  * If <x_n,g,y_n> = 0 is satisfied first, it indicates that y<x.
 
  * If none of the above conditions is satisfied, this means x=y. 




 









§ PRIVACY-PRESERVING BILLING PROTOCOL FOR LOCAL ENERGY MARKET

In this section, we propose PBP-LEM, considering the deviations cost. PBP-LEM is designed based on the billing model with a universal deviation cost split proposed in <cit.>, which was later modified in our previous work <cit.> to incorporate users' locations on the grid. The main idea revolves around having the RM as a backup market to compensate for users' deviations, which could come at a cost. The zone-based billing model with universal cost split, ZBUCS, introduced in <cit.> splits the total deviation cost among market participants whose deviations are in the same direction as the total deviation while considering the zones to which the participants belong on the grid. Prosumers (consumers) then pay (get paid by) their contracted suppliers for their total deviation share according to FiT (RP) rather than the LEM price, which is less beneficial. Please refer to the work of <cit.> and  <cit.> for more details. 

It is important to note that this research specifically focuses on the billing phase of the LEM. The issue of preserving users' privacy during the market clearance phase has been addressed in earlier research, as referenced in <cit.>. Our assumption is that user privacy during LEMO's market execution is protected by the adoption of privacy-preserving solutions outlined in previous studies, such as <cit.>. Consequently, the transmission of data by LEMO in PBP-LEM does not imply unrestricted access to individual user data by the entity. Instead, it only requires forwarding the securely protected data (e.g., bid volumes) to the computing parties after the market is executed to compute individual bills/rewards.
 
The section begins by proposing an efficient and privacy-preserving individual billing technique (Section  <ref>), which in turn is utilized by PBP-LEM (Section <ref>). Table <ref> lists the notation used throughout the paper.



 §.§ Efficient and Privacy-Preserving Individual Billing Scheme

In this section, we propose an efficient and privacy-preserving individual billing scheme, EPIB, that achieves information-theoretic security and forms a building block for PBP-LEM. 

Initially, let's assume that a set of encryption keys S_i = {sk_i^tp_1,…,sk_i^tp_N_k} is generated for every user, corresponding to trading periods {tp_1, …, tp_N_k} within one billing period, bp_u. Each encryption key sk_i is a randomly generated number over a finite field modulo q (z_q). Then, our privacy-preserving individual billing technique operates over z_q as follows. 

After each trading period, tp_k, each user, i, encrypts its recorded meter reading, m_i, during tp_k using the corresponding sk_i^tp_k by simply computing: 



    mc_i^tp_k = m_i^tp_k + sk_i^tp_k
 

Given the identified market trading price, TP^tp_k, to compute the encrypted individual bill/reward, one performs the following computation:



    bc_i^tp_k = mc_i^tp_k * TP^tp_k
 

Including the deviation cost and distribution network usage cost in users' bills/rewards based on ZBUCS requires knowledge of the user's type of participation, d_i^tp_k – that is, whether the user offered to produce or consume energy during tp_k. To protect d_i^tp_k, we begin by encoding it into two distinct values, d_i,p^tp_k and d_i,c^tp_k, each representing a binary state of the user's type participation at tp_k. For example, if the user is buying energy at tp_k, then d_i,p^tp_k=1 and d_i,c^tp_k=0. Conversely, if the user is consuming energy, then d_i,p^tp_k=0 and d_i,c^tp_k=1. Let S_i^p= {sk_i,p^tp_1, …, sk_i,p^tp_N_k} and S_i^c={sk_i,c^tp_1, …, sk_i,p^tp_N_k} represent two sets of randomly generated keys over z_k, corresponding to the trading periods {tp_1, …, tp_N_k} within bp_u. For each tp_k, each user masks d_i,p^tp_k and d_i,c^tp_k using sk_i,p^tp_k and sk_i,c^tp_k, respectively.


    dc_i,p^tp_k = d_i,p^tp_k + sk_i,p^tp_k
 

    dc_i,c^tp_k = d_i,c^tp_k + sk_i,c^tp_k
 

Let NF_p^tp_k and NF_c^tp_k represent the distribution network fee for exporting and importing energy in zone z, respectively. Let dev_p^tp_k denote the cost to be paid by certain prosumers to their suppliers due to deviations based on a condition, C_i,p^tp_kp, and dev_c^tp_k denote the compensation to be received by specific consumers from their suppliers for deviations based on a condition, C_i,c^tp_k, as defined in ZBUCS. Then, for each tp_k, the addition of dev_p^tp_k and dev_c^tp_k to bc_i^tp_k is as follows:

    bc_i^tp_k = bc_i^tp_k + mc_i^tp_k  *  ( (dc_i,p^tp_k * NF_p^tp_k) + (dc_i,c^tp_k * NF_c^tp_k) )  
    
     + [C_i,p^tp_k](dc_i,p^tp_k * dev_p^tp_k) + [C_i,c^tp_k](dc_i,c^tp_k * dev_c^tp_k)


Here, the notation [C_i,p^tp_k] and [C_i,c^tp_k] represents Iverson brackets, where [C] is equal to 1 if condition C is true, and 0 otherwise. 










The decryption key for tp_k is then computed as:


    dk_i^dev,tp_k = [C_i,p^tp_k](sk_i,p^tp_k * dev_p^tp_k) + [C_i,c^tp_k]( sk_i,c^tp_k * dev_c^tp_k)
 


    dk_i^tp_k = (sk_i^tp_k * TP^tp_k) + (sk_i,p^tp_k *  NF_p^tp_k) + ( sk_i,c^tp_k *  NF_p^tp_k) + dk_i^dev,tp_k
 

For every bp_u, the encrypted monthly bill BLc_i^bp_u is calculated by summing the results bc_i^tp_k of each tp_k: BLc_i^bp_u = ∑_k=1^N_k bc_i^tp_k. Similarly, the decryption key DK_i^bp_u for bp_u is computed by summing the results dk_i^tp_k for every tp_k: DK_i^bp_u = ∑_k=1^N_k dk_i^tp_k. Finally, to decrypt, one simply computes: 


    BL_i^bp_u =  BLc_i^bp_u - DK_i^bp_u
 

The above scheme guarantees the protection of m_i^tp_k and d_i^tp_k. Its security comes from the fact that if sk_i^tp_k, sk_i,p^tp_k and sk_i,c^tp_k are fresh random numbers generated for every tp_k, then the scheme can be seen as equivalent to one-time pad.  



 §.§ Privacy-Preserving Billing Protocol

This section provides a detailed description of PBP-LEM considering the deviations cost. PBP-LEM consists of five steps: input data generation and distribution, bills computation per trading period, bills computation and distribution per billing period, individual deviations verification, and bills settlement and verification. We first discuss some prerequisite steps that should be performed. We will then discuss the five protocol steps in detail in the remainder of the section. The discussion includes a description of three different approaches applied in PBP-LEM, leading to varying degrees of privacy and performance. In the subsequent sections of this paper, the square brackets [x] denote that x is secretly shared, and the angles ⟨ x ⟩ denote a Pedersen commitment to x. 






  §.§.§ Prerequisites

Before engaging in the LEM trading, users are required to register with the key authority, KA. Each user sends a registration request along with the tuple (Id_i,SId_j,ZId_z) containing their unique identifiers, Id_i, their contracted supplier identifiers, Sid_j, and the zone to which the user belongs, ZId_z, to the KA. Subsequently, KA generates three sets S_i, S^c_i and S^p_i of random keys, following EPIB. It also generates a master key, msk_i^tp_k, and public parameters, pp_i^tp_k, using Setup method of the IPE scheme <cit.>. KA then transmits the tuple (S_i, S^c_i, S^p_i,msk_i^tp_k,pp_i^tp_k) to the user's SM. For every bp_u, KA regenerates new sets of S_i, S^c_i and S^p_i for each user. 



Additionally, we make the following assumptions: bid volumes, b_i^tp_k, are encoded using f_x of the dual-binary encoding scheme <cit.> into two arrays of vectors, B^tp_k_i,v_r and B^tp_k_i,v_l.  LEMO possesses the encryption of B^tp_k_i,v_g and B^tp_k_i,v_l using msk_i^tp_k and pp_i^tp_k with the IPE.RightEncrypt, denoted by Bc_i,v_r^tp_k and Bc_i,v_l^tp_k, respectively, which it receives from users before the market clearance phase to execute the market privately, as in <cit.>. Please note that the above assumption is required only for approach 1 in step 2. We also assume that users send dc_i,p^tp_k, dc_i,c^tp_k and Pedersen commitments to the negative inverse of their bid volumes, ⟨ -b_i^tp_k⟩, to LEMO along with their submitted bids before the market execution. Next, we discuss the five steps of PBP-LEM.




         


  §.§.§ Step 1: Input Data Generation and Distribution

After each trading period tp_k, tuples are prepared by users, their respective SMs, and LEMO. These tuples are then shared with CS and suppliers, enabling collaborative computation of the users' bills and rewards from the LEM, inclusive of their deviations cost. In detail, every user in every zone calculates their deviation v_i^z,tp_k by subtracting m_i^tp_k from b_i^tp_k. Each user then generates a tuple (Id_i,SId_j,ZId_z,[v]_i^z,tp_k,[d]_i^z,tp_k) which contains shares of the computed deviations, [v]_i^tp_k,z and shares of their type of participation [d]_i^z,tp_k (i.e., a prosumer or consumer) and send it to the CS. 

 


In addition, every SM encodes m_i^tp_k into an array of vectors, M_i^tp_k, using f_y method of the dual binary encoding scheme <cit.>. The SM then encrypts M_i^tp_k with msk_i^tp_k and pp_i^tp_k using IPE.LeftEncrypt, Mc_i^tp_k. The SM also encrypts m_i^tp_k with sk_i^tp_k using EPIB, mc_i^tp_k. It also computes a pedersen commitment to m_i^tp_k, ⟨ m_i^tp_k⟩. Upon completion, the SM prepares the tuple (Id_i, ZId_z, mc_i^tp_k,Mc_i^tp_k, ⟨ m_i^tp_k⟩) and transmit it to the supplier. Additionally, LEMO forwards the following tuple (Id_i,Bc_i,v_r^tp_k,Bc_i,v_l^tp_k,⟨ -b_i^tp_k⟩,dc_i,p^tp_k,dc_i,c^tp_k) for each user to the supplier. Please note that in the following step, we will present three different approaches where Mc_i^tp_k, Bc_i,v_r^tp_k and Bc_i,v_l^tp_k are only required by approach 1.
      



  §.§.§ Step 2: Bills Computation Per Trading Period

Upon the receipt of the tuples, firstly, CS jointly computes what is required to include users' deviations cost in their bills/rewards. The CS then sends the results to the suppliers, which subsequently continue the computations to calculate users' total bills/rewards per tp_k  in a data oblivious fashion. In detail, once the CS receives (Id_i,SId_j,ZId_z,[v]_i^tp_k,[d]_i^tp_k) from users, they evaluate the total deviation, [t_z]^tp_k, number of consumers, [nc_z^tp_k], and number of prosumers, [np_z]^tp_k, per zone obliviously as shown in algorithm <ref>. The CS then reconstruct t_z^tp_k, nc_z^tp_k and np_z^tp_k for each zone using their shares in order to compute the total global deviation, T^tp_k, and the zonal deviation weight, W^tp_k, which help to distribute the total global deviation proportionally between the zones (For more details about the calculation of W^tp_k, please refer to our previous work of <cit.>). Once completed, the CS, publish the set of N_z tuples ZN =  (t_z^tp_k, nc_z^tp_k, np_z^tp_k), resulting from algorithm <ref>, as well as (T^tp_k, W^tp_k) tuple to all suppliers, users and KA.





 

Upon receiving the necessary data from the CS, suppliers can begin calculating LEM bills and rewards for the users, who are their contracted customers in the RM. Initially, suppliers need to determine a binary value, s_i^tp_k, for each of their customers, indicating if the user must pay a deviation cost (the part of the user's production/consumption they have to sell (buy) to (from) their suppliers according to FiT or RP rather than TP_tp_k) based on ZBUCS. s_i^tp_k is equal to 1 if the user has to pay a deviation cost and 0 otherwise.




  §.§.§ Approach 1: s_i^tp_k Identification Performed by Suppliers

In this approach, suppliers identify s_i^tp_k by themselves without knowledge of m_i^tp_k or b_i^tp_k. They utilize the dual binary encoding scheme, integer comparison using multiple inner products <cit.> and IPE <cit.>. Specifically, for each user, using Bc_i,v_l^tp_k, Bc_i,v_r^tp_k obtained from LEMO and Mc_i^tp_k received from the SM, the supplier compares m_i^tp_k and b_i^tp_k values and determine s_i^tp_k in an oblivious manner as shown in algorithm <ref>.  




  §.§.§ Approach 2: s_i^tp_k Identification by CS

In this approach, the CS takes charge of identifying s_i^tp_k instead of leaving it to the suppliers. The CS continues to perform computations on [v_i^tp_k] by executing comparisons as detailed in algorithm <ref>. Subsequently, the CS sends the resultant shares to the designated supplier according to SId_j, allowing them to recover s_i^tp_k.

 
        


  §.§.§ Approach 3: Individual Deviations Disclosed to Suppliers

As individual deviations are less sensitive data, we may allow their disclosure to suppliers, enabling them to compare the values in clear. Accordingly, each user simply sends a tuple (id_i,v_i^tp_k) to its corresponding supplier. This avoids the significant overhead caused by parties performing comparisons on the encrypted or secretly shared data. Disclosing users' deviations would reveal some information about users. However, critical sensitive data such as meter readings and bid volumes should still not be inferred.

After identifying s_i^tp_k, suppliers proceed with the computation of users' bills/rewards per tp_k, using EPIB as shown in Algorithm <ref>. Specifically, for each user, their respective supplier calculates bc_i^tp_k based on mc_i^tp_k received from the SMs, and dc_i,p^tp_k and dc_i,c^tp_k obtained form LEMO (line 1). The supplier then modifies bc_i^tp_k to incorporate the deviation cost (lines 6 and 10). In addition, the supplier updates its income balance resulting from users' deviations, denoted as SBal_j^tp_k, by adding revenue and subtracting expenditures incurred from selling (or buying) the deviations costs to (or from) users (line 7 and 11). Upon completion, the supplier reports C_i,c^tp_k and C_i,p^tp_k to KA which in turn computes dk_i^dev,tp_k and dk_i^tp_k using  sk_i^tp_k, sk_i,p^tp_k and sk_i,c^tp_k based on EPIB. 



       
   


  §.§.§ Step 3: Bills Computation and Distribution Per Billing Period

At the end of the billing period bp_u, suppliers finalize the computation of users' bills/rewards using EPIB. For each user, their corresponding supplier aggregates bc_i^tp_k for all trading periods within bp_u: BLc_i^bp_u = ∑_k=1^N_k bc_i^tp_k. Simultaneously, KA computes DK_i^bp_u using all previously computed dk_i^tp_k during bp_u: DK_i^bp_u = ∑_k=1^N_k dk_i^tp_k. KA then sends the user's DK_i^bp_u to the designated supplier according to Sid_j. Upon receiving DK_i^bp_u from KA, the supplier decrypts BLc_i^bp_u using EPIB to obtain the user's bill/reward ,BL_i^bp_u, which is then sent to the user. As each user has all the required information (e.g., T^tp_k and W) to compute its individual bill/reward, the user accepts BL_i^bp_u only if it is identical to its locally computed bill. Additionally, for subsequent verification, each user calculates its total deviation cost, BL_i^bp_u,dev, representing the cost of selling/buying the total deviation share to/from their contracted suppliers per bp_u. The user then deducts BL_i^bp_u,dev from BL_i^bp_u to determine the value dedicated solely to the LEM, BL_i^bp_u,LEM.



  §.§.§ Step 4: Individual Deviations Verification

The purpose of this step is to verify the accuracy of the individual deviations [v]_i^tp_k computed by each user and transmitted to the CS.
Before getting into details, it is important to stress that this is an ongoing process conducted for every tp_k and at the end of bp_u. Pedersen commitment is employed to verify the accuracy of [v]_i^tp_k for each user. For every tp_k, given ⟨ m_i^tp_k⟩ received from an SM and ⟨ -b_i^tp_k⟩ received from LEMO, the designated supplier exploits the homomorphism property of Pedersen commitment to obtain a commitment to v_i^tp_k:


    ⟨ v_i^tp_k⟩ = ⟨ m_i^tp_k⟩ . ⟨ -b_i^tp_k⟩


At the end of bp_u, utilising the same homomorphism property, the supplier computes a commitment to the aggregated v_i^tp_k during bp_u by means of multiplication: 


    <∑_k=1^N_k v_i^tp_k> = ∏_k=1^N_k⟨ v_i^tp_k⟩


Concurrently, the CS aggregates all [v_i]^tp_k values during bp_u, for each user:
 
    [V_i^bp_u] = ∑_k=1^N_k [v_i^tp_k]
 
The CS then retrieves the result, V_i^bp_u, by reconstructing their shares and sends it to the designated supplier according to SId_j. Additionally, each SM sums all the random numbers, R_i^bp_u = ∑_k=1^N_k r_i^tp_k, used earlier in its previous commitments (i.e., ⟨ m_i^tp_k⟩ and ⟨ -b_i^tp_k⟩) and sends the total R_i^bp_u to the designated supplier. Finally, the supplier checks that V_i^bp_u is correct if opening the commitment <∑_k=1^N_k v_i^tp_k> using V_i^bp_u and R_i^bp_u returns true. 

    Open(<∑_k=1^N_k v_i^tp_k>,V_i^bp_u,R_i^bp_u)→ true
 This, in turn, indicates that all previous v_i^tp_k shared by user i with the CS were correct.




  §.§.§ Step 5: Bills Settlement and Verification

In this final step, suppliers settle billing period bills with users who are their contracted customers, ensuring that any payments to or from the LEM, sent or received by these customers, are appropriately allocated among other suppliers.  Specifically, each supplier conducts billing with their customers based on BL_i^bp_u, which encompasses both LEM payments/rewards and deviations share payments/rewards dedicated to the suppliers. The supplier, then, separates these two values. First, the supplier computes its accurate income balance for tp_k using ∑_i=1^N_u dk_i^dev,tp_k received from KA: 

    SBal_j^tp_k = SBal_j^tp_k - ∑_i=1^N_u dk_i^dev,tp_k

The supplier, then, subtract its income balance during bp_u from its aggregate customers bills to compute the remaining capital exchanged within the LEM through it.


 

    SCap_j^bp_u = ∑_i=1^N_u BL_i^bp_u - ∑_k=1^N_k SBal_j^tp_k


SCap_j^bp_u values are redistributed among other suppliers through the coordination of the DSO. The sum of these values should be zero, indicating that all the LEM transactions have been accounted for legitimately. In the case of a non-zero sum, the DSO should intervene to verify the correctness of each SCap_j^bp_u value. To do so, the DSO collects tuples (BL_i^bp_u,LEM, Sid_j) from all users. The DSO then segregates and aggregates BL_i^bp_u,LEM values based on their supplier correspondence Sid_j, such that SCap_j^bp_u,DSO represents the leftover capital traded at the LEM and computed by the DSO. The DSO then validates every SCap_j^bp_u value by comparing it with SCap_j^bp_u,DSO. Any mismatch indicates that supplier j has been dishonest in submitting an invalid SCap_j^bp_u value. 





§ SECURITY ANALYSIS

We analyse the security of PBP-LEM under the Universal Composability (UC) framework <cit.>. The framework provides a strong security gurantees by which a protocol proven secure in this framework is assured to maintain its security when it is run sequentially or concurrently with other protocols.  The framework consists of the real world (i.e. the real protocol), ideal world and an environment. In the ideal world, the parties do not communicate with each other. Instead they have access to an ideal functionality (i.e., “trusted party”) that is defined to capture the desired security requirements of the real protocol. Then, security of the real protocol is implied if no environment can computationally distinguish between the two worlds. 



 A real protocol π UC-realizes an ideal functionality ℱ if for any real-world adversary 𝒜, there exists a simulator 𝒮 such that no environment 𝒵 is able to distinguish with a non-negligible probability between an interaction with 𝒜 and real parties running protocol π and an interaction with 𝒮 and dummy parties accessing ℱ, i.e., REAL_π,𝒜,𝒵≈ IDEAL_ℱ,𝒮,𝒵.


 
Let ρ, φ, and π be protocols such that φ is a subroutine of π, ρ UC-emulates φ, and π UC-realizes an ideal functionality ℱ, then protocol π^φ→ρ UC-realizes ℱ.


We assume the presence of the following ideal functionalities: secure computation ideal functionality ℱ_SecComp for MPC and IPFE; and a commitment ideal functionality ℱ_COM.  ℱ_SecComp receives private inputs from users, preform computation on the inputs and reveal the results upon parties agreement. ℱ_COM receives values to be committed from users, stores them in its internal state and reveal them upon request.  We also construct an ideal functionality for EPIB ℱ_EPIB as shown in Fig. <ref>. For simplicity, the functionality solely captures the computation of individual bills with no inclusion of the deviations cost. 






    Let π_EPIB be the billing protocol employing EPIB, excluding the consideration of the deviations cost.  Then the protocol π_EPIB securely emulates the functionality ℱ_BLEM.


PROOF. We construct a simulator 𝒮 such  that no environment 𝒵 can distinguish between an ideal and real execution. 𝒮 executes a simulated copy of 𝒜 and imitates an interaction with parties running π_EPIB to make the simulation of internal protocol interactions consistent with the real execution. 
𝒮 proceeds as follows: upon receiving (Id_i,l(m_i^tp_k+sk_i^tp_k), l(sk_i,p^tp_k), l(sk_i,c^tp_k)) from ℱ_EPIB, 𝒮 mimics the encryption operations of EPIB on behalf of the smart meter. It defines mc_i^tp_k, dc_i,p^tp_k, dc_i,c^tp_k to be random values Δ_mc_i^tp_k, Δ_dc_i,p^tp_k, Δ_dc_i,c^tp_k from the appropriate space given l(m_i^tp_k+sk_i^tp_k), l(sk_i,p^tp_k), l(sk_i,c^tp_k). 𝒮 then feeds 𝒜 with the defined values Δ_mc_i^tp_k, Δ_dc_i,p^tp_k and Δ_dc_i,c^tp_k. 
 
Now given that sk_i^tp_k, sk_i,p^tp_k and sk_i,c^tp_k are truly random numbers, it implies that mc_i^tp_k, dc_i,p^tp_k and dc_i,c^tp_k based on EPIB, are uniformly distributed. This indicates perfect indistinguishably as it is impossible to distinguish between mc_i^tp_k and Δ_mc_i^tp_k (since the distribution over the ciphertext is the same in every case as in one-time pad). Therefore , we can conclude that the output of the of the real world and ideal world executions are indistinguishable. 
 






 
Given a set of input tupples (Id_i,SId_j,ZId_z,v_i^z,tp_k,d_i^z,tp_k) from users and a set of tupples (Id_i, ZId_z, m_i^tp_k) from their SMs and a set of tupples (Id_i,b_i^tp_k) from LEMO, the ideal functionality ℱ_EPIB computes 
BL_i^bp_u and SCap_j^bp_u for all users and suppliers and return the results to the designated parties. 



Next we show that all three approaches of PBP-LEM securely realise ℱ_BLEM. 


    Let π_App1,π_App2 and π_App3 be PBP-LEM employing Approach 1, 2 and 3 , respectively.  Then the protocols π_App1,π_App2 and π_App3 securely emulate the functionality ℱ_BLEM in the {ℱ_SecComp, ℱ_COM, ℱ_EPIB}-hybrid model.

PROOF. Assuming the presence of concrete implementations of the underlying functionalities ℱ_SecComp <cit.> and ℱ_COM <cit.>, the proof is a straightforward application of the composition theorem.  Since the protocols π_App1,π_App2 and π_App3 compromise only ℱ_SecComp, ℱ_COM and ℱ_EPIB, which can be substituted by their universally composable implementations. 



  
Authorisation and Collusion Impact Mitigation: authorisation is achieved by allowing aggregated users' bills to be retrieved by their contracted suppliers only. This is simply accomplished through the use of SId_j, which ensures that the relevant parties (KA, LEMO, and CS) forward the individual data necessary for bill computation only to the designated suppliers.

Regarding the collusion impact mitigation, it is achieved by ensuring that any potential collusion between computing parties in the market does not result in the disclosure of critical fine-grained private data (e.g., b_i^tp_k and m_i^tp_k). Specifically, in the case of an honest-majority CS, it is sufficient for two computational servers to collude to reveal private individual data, whereas in the case of a dishonest majority CS, all three servers must collude for malicious collusion to occur. However, in either scenario, the only private data CS are capable of retrieving are d_i^tp_k and v_i^tp_k, which reveal significantly less sensitive information about users compared to b_i^tp_k and m_i^tp_k. Additionally, collusion between CS and suppliers has no higher impact since all private data in the possession of users' suppliers is encrypted (using EPIB and IPFE).




§ PERFORMANCE EVALUATION

This section evaluates the performance of PBP-LEM in terms of computational and communication complexity, while considering the three proposed approaches. 



 §.§ Computational Complexity

The most computationally demanding operations in PBP-LEM are IPE methods (specifically IPE.LeftEncrypt, IPE.RightEncrypt, and IPE.Decrypt), multiplication, and comparison operations performed by CS, followed by Pedersen commitment methods (Commit and Open). The computation cost of all remaining operations, including EPIB operations, is negligible.



For all approaches, for every tp_k, each SM computes one Commit over its recorded meter reading; each user computes one Commit over its bid volume and each supplier computes two homomorphic additions on the commitments for each of its contracted user: N_u^s × 2 × HomoAdd. Moreover, for every bp_u, every supplier performs one commitment opening for each corresponding user:  N_u^s × Open. If approach (1) is adopted,  in addition to the previously mentioned operations, each SM computes N_v × IPE.LeftEncrypt; every user computes N_v × 2 × IPE.RightEncrypt and each supplier computes N_u^s × N_v × 2 × IPE.Decrypt in the ultimate worst case scenario. Here, N_v is the number of vectors required to encode each bid volume and meter reading using dual binary encoding scheme methods (i.e. f_y and f_x) <cit.>. Please note that suppliers may perform N_v × 2 × IPE.Decrypt for each user in the worst-case scenario, which occurs when the bid volume and meter reading values are equal. However, in most cases, the values result in a better cost, as the “for" loop in Algorithm(<ref>) may exit before iterating N_v times. In the case of approach (2), CS additionally performs one comparison and one multiplication for each user in the market: N_u × Comp + N_u × Mult. In case approach (3) is employed, no additional  computationally heavy operations are to be performed. 

We also conducted experiments to test the performance of PBP-LEM. CS, supplier and KA were implemented on a 64-bit Linux server equipped with 16 cores single thread Intel Xeon processors and 64 GB of memory. We run all the parties on the same server, therefore, network latency is not considered. Users and SMs operations were evaluated on a laptop with Intel Core i7 CPU and 8 GB of memory. CS algorithms were executed using the MP-SPDZ framework <cit.>, which supports the underlying primitives and MPC protocols employed by PBP-LEM (Section <ref>). All other entities' algorithms were implemented in python. IPE modules was adopted from  <cit.>.




We followed the same random generation approach used in <cit.> –based on a realistic dataset from <cit.> – to simulate bid volumes and meter readings over a 30-minute trading period, typical for Local Energy Markets (LEMs). To facilitate accurate and efficient private bills computation, values are represented as integer numbers. Upon the completion of bills calculation, correct bills are retrieved by performing the necessary conversions. RP of the suppliers, FiT, TP and network fees for exporting and importing energy in all zones are set to .3£/Wh, .1£/Wh, .2£/Wh, .05£/Wh and .04£/Wh, respectively. We assume that each trading period is 30 minutes long and each billing period is one month, meaning that a single billing period consist of 1440 trading periods. We initiated our experiments with 1000 users participating in a LEM for one trading period and gradually increased the number to 4000 users. The user distribution comprised an equal split between prosumers and consumers, resulting in 500 users of each type for every 1000 users. We assumed that there are 6 different suppliers and four zones in the market, allocating users equally among them. 

Based on the generated bid volumes and meter reading values ranges, we set N_v to 12 for Approach (1), allowing the representation of 4095 different integer values according to the dual binary encoding scheme <cit.>. Our results indicate that each Commit costs 2.10 ms; HomoAdd costs 0.124812 ms; Open costs 0.25 ms; N_v × IPE.LeftEncrypt costs 25.40 ms; N_v × IPE.RightEncrypt costs 164.10 ms; .2 × N_v × IPE.Decrypt costs 622 ms. 




Figure <ref> illustrates the computational cost per tp_k for each entity in the market with respect to each of the three approaches. Approach (1) incurs additional costs for the resource-constrained market entities (i.e., SMs and users) compared to the other approaches, as it involves more intensive operations during Step (1). Nevertheless, none of the three approaches impose significant computational demands on SMs and users. For instance, in approach (1), the overall computational time per tp_k for each SM and user is 27.56 ms and 330.14 ms, respectively. 
Regarding suppliers and CS, the selected approach during Step (2) determines which entity should handle the most computationally intensive operations to incorporate deviation costs in bill calculations. This costs arises from Algorithm (<ref>) performed by CS in approach (2) or Algorithm (<ref>) executed distributively by users' respective suppliers in approach (1). Please note that, as we evenly distributed the number of users among suppliers, they all share similar costs. However, in a more realistic scenario, some suppliers might bear higher costs than others based on the number of their contracted users. In approach (3), users' privacy has been relaxed in exchange for eliminating heavy computations, resulting in a trivial cost for both suppliers and CS.












Figure <ref> displays the total computation time for bill calculation per tp_k in all approaches, as well as PPBSP by <cit.> for benchmarking. Please note that the figure accounts for CS's computation time, considering the offline phase of the underlying MPC primitives. Clearly, Approach (3) stands out as the most efficient, attributed to privacy loosening—specifically, disclosing individual deviations to the suppliers. If such leakage is not tolerated by users, the decision between approaches (1) and (2) becomes less straightforward, given our parameter assumptions. In the case of a malicious majority CS, the overall computational time for bill computation in approaches (1) and (2) is comparable, and the key difference lies in the part of the market where the cost is concentrated, i.e., CS or suppliers. However, considering only the online phase of CS would give preference to approach (2). Another crucial factor to consider is the number of suppliers in the market and the distribution of users among them. For instance, assuming that over 20% of market users are associated with a single supplier would result in a slower bill computation time for those users in Approach (1) compared to Approach (2). In the scenario of an honest-majority CS, Approach (2) is preferable, providing a more private solution than Approach (3) and significantly greater efficiency than Approach (1).



Compared to PPBSP, PBP-LEM excels only in the case of Approach (3) and Approach (2) with an honest-majority CS, taking into account the offline phase. Nevertheless, bill computation per tp_k in all approaches can be completed maximally in less than 5 minutes for 4000 users, demonstrating the feasibility of PBP-LEM for real LEM deployment.















       

 
      



 
 
 
		  
        
         











 §.§ Communication Complexity

In evaluating communication complexity, we focus specifically on the costs associated with implementing privacy techniques and measures within PBP-LEM. Table <ref> provides a summary of the communication complexity in PBP-LEM for different approaches, where, |X| represents the size of a single value, |[X]| the size of a share, |<X>| the size of a Pedersen commitment, |C| the size of a ciphertext using EPIB, |R| the size of a random value used in Pedersen commitments, |CT_l| the size of a ciphertext using IPE.LeftEncrypt, |CT_r| the size of a ciphertext using IPE.RightEncrypt, |CN| a boolean value, and |K| the size of a random key generated for EPIB.

|CT_l| and |CT_r| have been evaluated to be 550 and 1650 bytes, respectively, considering that the number of elements in each vector is N_v + 1, i.e., 12. Measuring the communication cost between CS using MP-SPDZ and setting |[X]| = 64, |<X>| = |R|= 256, |K| = 128, |X| = |C| = 32, |CN| = 1 bits, we present the communication cost of PBP-LEM (using the three approaches) and PPBSP <cit.>.


PBP-LEM outperforms PPBSP only in the case of the relaxed privacy approach, i.e., Approach 3. Comparing PBP-LEM's approaches, as expected, Approach 3 exhibits the significantly lowest communication cost due to the disclosure of individual deviations. This indicates that the major communication overhead arises from the protection of individual deviations that requires private comparison to determine whether each user has to pay for their deviations. With regards to the choice between Approach 2 and Approach 3, the decision depends on the chosen security model of the CS. For an honest-majority CS, the communication cost of Approach 2 is almost half that of Approach 1. However, in the case of a dishonest-majority CS, Approach 2 incurs a significantly higher cost concentrated between CS parties.











       


      









           
















§ CONCLUSION

We introduced a privacy-preserving billing protocol for LEMs (PBP-LEM) based on a novel scheme and other cryptographic techniques. PBP-LEM considers imperfect bid fulfillment and distributes bill computation among different parties (i.e., CS and suppliers) while protecting users' private data (e.g., bid volumes, smart meter readings, deviations, and locations) with mitigation of internal collusion impact. Furthermore, we presented three approaches that offer varying degrees of privacy and performance. We also proved that PBP-LEM fulfill its security and privacy requirements. Finally, we analysed the associated computation and communication costs of all our approaches under different security settings. The results demonstrate the variations in performance between the approaches and indicate the feasibility of PBP-LEM for a setting based on real LEMs.





splncs04


