Adrien Coulet

Malika Smaïl-Tabbone

Mining Electronic Health Records to Validate Knowledge in Pharmacogenomics

Mining Electronic Health Records to Validate Knowledge in Pharmacogenomics. by Adrien Coulet and Malika Smaïl-Tabbone

The state of the art in pharmacogenomics (PGx) is based on a bank of knowledge resulting from sporadic observations, and so is not considered to be statistically valid. The PractiKPharma project is mining data from electronic health record repositories, and composing novel cohorts of patients for confirming (or moderating) pharmacogenomics knowledge on the basis of observations made in clinical practice.

Pharmacogenomics (PGx) studies how individual gene variations cause variability in drug

responses. A state of the art of PGx is available and constitutes a basis for implementing personalized medicine, i.e., medical treatment tailored to each patient taking into account his/her genomic context. However, most of the state of the art in this domain is not yet validated, and consequently not yet applicable to medicine. Most information results from studies that do not fulfil statistics validation standards and are difficult to reproduce because of the rarity of gene variations studied (making it hard to recruit sufficiently large cohorts) and of the multifactorial aspects of drug responses [START_REF] Ioannidis | To replicate or not to replicate: The case of pharmacogenetic studies[END_REF]. The increasing use of electronic health records (EHRs) generates large repositories that offer new opportunities, such as composing patient cohorts for the study of clinical hypotheses hard to test experimentally. Typically, EHR repositories make it possible to assemble cohorts of patients to study the impact of gene variations on drug responses on the basis of practice-based data [START_REF] Neuraz | Phenome-wide association studies on a quantitative trait: Application to TPMT enzyme activity and thiopurine therapy in pharmacogenomics[END_REF].

In October, 2015, The French National Research Agency (ANR) committed funding to a project called PractiKPharma (Practice-based evidence for actioning Knowledge in Pharmacogenomics). The project aims to validate or moderate PGx state-of-the-art (SOTA) knowledge on the basis of practice-based evidence, i.e., knowledge extracted from EHRs. Units of knowledge in PGx typically have the form of ternary relationships gene variantdrug-adverse event, and can be formalized to varying extents using biomedical ontologies. To achieve this goal, the PractiKPharma consortium will focus on four objectives, illustrated in Figure 1: (1) to extract SOTA knowledge from PGx databases and literature; (2) to extract observational knowledge (i.e., knowledge extracted from observational data) from EHRs; (3) to compare knowledge units extracted from these two origins, to confirm or moderate SOTA knowledge, with the goal of enabling personalized medicine; (4) Finally, to emphasize newly confirmed knowledge, omics databases will be investigated for molecular mechanisms that underlie and explain drug adverse events. This investigation will use and contribute to the biomedical Linked Open Data [START_REF] Dalleau | Suggesting valid pharmacogenes by mining linked data[END_REF].

The PractiKPharma consortium comprises four academic partners: two computer science laboratories, the LORIA (Laboratoire Lorrain de Recherche en Informatique et ses Applications, Nancy, France) in Nancy, the LIRMM (Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier, France) in Montpellier; and two University Hospitals, the HEGP (The Georges Pompidou European Hospital, Assistance Publique -Hôpitaux de Paris (AP-HP), France) in Paris, specialized in EHRs management and pharmacogenomics, and the CHU Saint-Etienne (University Hospital (CHU) of Saint Etienne, France), specialized in pharmacovigilance. PractiKPharma will have impacts both in computer science and biomedicine, including:

• the development of novel methods for knowledge extraction from text and EHRs;

• enabling multilingual semantic annotation of EHRs;

• methods for representing and comparing SOTA and observational knowledge;

• a database that maps genotypes to quantitative traits to facilitate the study of PGx with EHRs; • the completion and connection of Linked Open Data related to PGx;

• methods for hypothesizing on mechanisms of adverse events and validated PGx knowledge units. Overall, the final goal of PractiKPharma is to provide clinicians with actionable PGx knowledge to establish guidelines that when implemented in personalized medicine will reduce drug adverse events, and improve the quality of clinical care.

The PractiKPharma consortium will hire two PhD students, two post-docs, one pharmacist and one research engineer to contribute to the project. In addition, PractiKPharma will foster collaboration and dissemination throughout the EU to take into consideration EHRs of various populations and to establish international projects.

Link: PractiKPharma project: http://practikpharma.loria.fr

Figure 1 :

 1 Figure 1: Outline of the four objectives of the ANR PractiKPharma project.


Oksana Kulyk

Stephan Neumann

Karola Marky

Jurlind Budurushi

Melanie Volkamer

Coercion-resistant Proxy Voting

In general, most elections follow the principle of equality, or as it came to be known, the principle of "one man -one vote". However, this principle might pose difficulties for voters, who are not well informed regarding the particular matter that is voted on. In order to address this issue, a new form of voting has been proposed, namely proxy voting. In proxy voting, each voter has the possibility to delegate her voting right to another voter, so called proxy, that she considers a trusted expert on the matter. In this paper we propose an end-to-end verifiable Internet voting scheme, which to the best of our knowledge is the first scheme to address voter coercion in the proxy voting setting.

Introduction

Democratic elections represent an important value in many modern states. This is not limited to governments, also companies and other organizations are constituted in democratic elections. In general, most democratic elections follow the principle of equal elections, meaning that one person's vote should be worth as much as another's, i.e. one man -one vote [START_REF] Neumann | Modeling the german legal latitude principles[END_REF]. However, this principle often represents a challenge to voters, who are not sufficiently informed regarding the particular matter that is voted on. In order to address this issue, a new form of voting has been proposed, the so called proxy voting. In proxy voting, each eligible voter has the possibility to delegate her voting right to another eligible voter, so called proxy, that she considers a trusted expert on the matter.

There already exist few proxy voting implementations, provided by different organizations. Two widely known implementations are LiquidFeedback3 and Adhocracy 4 . Further proxy voting proposals are the approaches proposed in [START_REF] Tchorbadjiiski | Liquid democracy diploma thesis[END_REF] and [START_REF] Zwattendorfer | Secure and privacy-preserving proxy voting system[END_REF].

However, all existing proxy voting proposals fail to address the issue of voter coercion: namely, the case when the adversary threatens the voter to vote in a particular way, or to abstain from voting. This issue has been commonly considered for non-proxy Internet voting, and a number of Internet voting schemes have been proposed, that address the problem of coercion, e.g. by providing coercion resistance [START_REF] Juels | Coercion-resistant electronic elections[END_REF] or coercion evidence [START_REF] Grewal | Caveat coercitor: Coercionevidence in electronic voting[END_REF]. In this paper, we build upon [START_REF] Clarkson | Civitas: Toward a secure voting system[END_REF][START_REF] Juels | Coercion-resistant electronic elections[END_REF] and an extension proposed by Spycher et al. [START_REF] Spycher | A new approach towards coercion-resistant remote e-voting in linear time[END_REF] to propose a coercion resistant end-to-end verifiable Internet proxy voting scheme.

This paper is structured as follows: In section 2 we identify and derive security requirements that are relevant for proxy voting. Section 3 introduces the fundamentals used for our proposal, which we present in section 4. In section 5 we evaluate the security of our proposal with respect to the requirements. Section 6 summarizes our contributions and provides directions for future research.

Requirements for Proxy Voting

The following functional requirements should be provided by a proxy voting system: Delegation cancellation. If the voter for any reasons decides to vote herself, she should be able to cancel the delegation at any point of time before the tallying.

Delegation back-up. The voter can assign up to T priorities to her proxies. Only the vote from the proxy having highest priority will be included in the vote count. This functionality is useful if the voter wants to have a "back-up" delegation, in case her first choice of a proxy abstains from the election.

The security requirements in Internet voting have been thoroughly investigated in the literature, and both formal [START_REF] Delaune | Verifying privacy-type properties of electronic voting protocols: A taster[END_REF] and informal [START_REF] Langer | A taxonomy refining the security requirements for electronic voting: analyzing helios as a proof of concept[END_REF][START_REF] Neumann | A holistic framework for the evaluation of internet voting systems. Design, Development, and Use of Secure Electronic Voting Systems[END_REF] definitions have been proposed. In this work, we aim to address the following security requirements for the election.

Vote integrity. All votes cast by eligible voters should be included in the result.

Availability. It should be possible to compute election result even if some of the involved entities are faulty.

Vote secrecy for voters. The adversary should not be able to learn how a voter has voted.

We aim at achieving the following security requirements for the delegation process:

Delegation integrity. Only the proxy having a valid permit from the voter should be able to cast a vote on this voter's behalf. The proxy should not be able to alter the priority given to them by the voter.

Delegation availability. A proxy should not be selectively prevented from having the votes delegated to her.

Vote secrecy for proxies. The adversary should not be able to learn how a proxy has voted.

Delegation privacy. There should not be a link between a voter's identity and her selected proxy. Furthermore, it should not be possible to reveal whether a voter has delegated a vote or cast it herself.

Delegation unprovability. The proxy should not be able to prove to anyone how many votes have been delegated to her. Moreover, the proxy can not gain any knowledge about the actual number the incoming delegations.

Note, that as we want to ensure coercion resistance, we require that vote secrecy for both voters and proxies should be ensured also for the case when the adversary is capable of communicating with the voter or proxy.

Background

In this section we introduce the fundamentals used to design our coercionresistant verifiable proxy voting scheme.

Cryptographic Primitives

In the following we describe the cryptographic primitives our scheme relies on. Hereby, G q denotes a cyclic multiplicative group with order q and Z q denotes the cyclic additive group of integers modulo q.

Zero-knowledge proofs. In order to prove the correctness of statements within the voting scheme without revealing anything beyond the correctness zero-knowledge proofs are employed. For this sake, techniques such as proving the knowledge of discrete logarithm [START_REF] Schnorr | Efficient signature generation by smart cards[END_REF] or discrete logarithm equality [START_REF] Chaum | Wallet databases with observers[END_REF] are being used. These proofs can be made non-interactive by employing the strong version of the Fiat-Shamir heuristic suggested in [START_REF] Bernhard | How not to prove yourself: Pitfalls of the fiat-shamir heuristic and applications to helios[END_REF]. An important extension of such proofs are designated-verifier proofs described in [START_REF] Jakobsson | Designated verifier proofs and their applications[END_REF]. Given the verifier's public key, these proofs convince only the designated verifier about the correctness, rather than the general public.

Linear Encryption. In some parts of our scheme, we use a modified encryption scheme suggested in [START_REF] Boneh | Short group signatures[END_REF] (further denoted as LE-ElGamal ). This scheme is semantically secure under the DLIN assumption which is implied in groups where the DDH assumption holds. Namely, let pk = (g 1 , g 2 , h) ∈ G 3 q be the public keys of the encryption and (x 1 , x 2 ) ∈ Z q × Z q the private keys with g x1 1 = g x2 2 = h. If the keys are jointly generated by multiple parties with x 1 , x 2 as threshold-shared secrets, then, according to [START_REF] Bernhard | Towards a practical cryptographic voting scheme based on malleable proofs[END_REF] at least 2/3 of the parties have to be honest.

The message m ∈ G q is encrypted as follows: two random values (r 1 , r 2 ) ∈ Z q × Z q are chosen and then the encryption -denoted as

{{m}} pk ∈ G 3 q -is calculated as (c 1 , c 2 , c 3 ) = (g r1 1 , g r2 2 , m • h r1+r2 ). The decryption then proceeds as m = c 3 • c -x1 1 • c -x2 2
. Ciphertexts can then be reencrypted by multiplying a ciphertext by an encryption of 1 using a random value (r 1 , r 2 ) ∈ Z q × Z q .

Further operations used together with the ElGamal encryption, such as mix net shuffle, well-formedness proofs and plaintext equivalence tests can be adjusted for LE-ElGamal as well.

Plaintext Equivalence Tests. In order to check whether a given ciphertext c encrypts the same plaintext as another ciphertext c without revealing any additional information about plaintexts, plaintext-equivalence tests [START_REF] Jakobsson | Mix and match: Secure function evaluation via ciphertexts[END_REF] can be employed. This can be performed by the holders of an encryption secret key and consists of jointly decrypting the value (c/c ) r given a secretly shared random value r ∈ Z q which results in 1 in case the plaintexts are equal or in random value otherwise.

Proxy Reencryption. Let {m} pk1 be a ciphertext encrypting message m with ElGamal public key pk 1 = (g 1 , h 1 ). Given the knowledge of corresponding secret key x 1 = log g1 h 1 which can also be a shared secret between several participants the method described in [START_REF] Jakobsson | On quorum controlled asymmetric proxy re-encryption[END_REF] allows for computing a new ciphertext {m} pk2 , that encrypts the same message using a different ElGamal public key pk 2 .

Mix nets. Important components in electronic voting systems are mix net schemes which are used for anonymizing lists of ciphertexts e 1 , ..., e N . In addition to ensure the integrity of the shuffle a number of zero-knowledge proofs have been proposed in the literature. The most efficient schemes -up to now -are presented in [START_REF] Terelius | Proofs of restricted shuffles[END_REF] and [START_REF] Bayer | Efficient zero-knowledge argument for correctness of a shuffle[END_REF]. A modification of such proofs can be used to mix tuples of ciphertexts ( ē1 , ..., ēN ) with ēi = (e i,1 , ..., e i,k ) while preserving the ordering within the tuple.

JCJ/Civitas Scheme

For our goal to provide a scheme for coercion resistant proxy voting we chose the JCJ/Civitas voting scheme proposed in [START_REF] Juels | Coercion-resistant electronic elections[END_REF] and then extended and implemented in [START_REF] Clarkson | Civitas: Toward a secure voting system[END_REF] as basis. The coercion resistance of the scheme is based on the application of voting credentials. These credentials are used to authorize votes from eligible voters. In case a coercer demands the credential from a voter she can simply provide a fake credential which could not be distinguished from the real one by the coercer. We briefly outline the scheme below.

Setup and Registration. Prior to the election the election supervisor announces the different election authorities, namely the registrar, registration tellers and tabulation tellers and publishes their respective public keys on the bulletin board. The registrar publishes the electoral register which contains the identity, the public registration key, and the public designation key of each voter. Building upon a homomorphic cryptosystem the tabulation tellers generate an election key pair in a distributed manner and publish the respective public key pk on the bulletin board.

For each voter V i each registration teller j = 1, ..., N generates a credential share c i,j and publishes its encryption next to the respective voter's identity on the bulletin board from which the encryption of the voting credential

E i = {c i } pk = N j=1 {c i,j } pk
can be computed by multiplying all the individual credential shares. The shares c i,j in plaintext together with corresponding designated-verifier correctness proofs are then being forwarded to the voter. Now the voter can use them to compute their secret voting credential c i = N i=1 c i,j . Finally, the encrypted credentials E i are being shuffled via mix net.

Voting. The voters use anonymous channels for vote casting. As her vote, the voter casts a tuple

A i = {o} pk , C i = {c i } pk , σ
with o as a chosen voting option and σ as well-formedness proof for A i and proof of plaintext knowledge for C i . The tuple is sent to one of the available ballot boxes which stores the votes. In case the voter is forced to reveal her credential to a coercer she can give a fake credential c instead while the coercer is not able to distinguish it from a real one.

Tallying. The votes with invalid proofs are excluded and the plaintext-equivalence tests are used for identifying the votes with duplicated credentials which are handled according to the rules concerning vote updating. The remaining tuples A i , C i are being shuffled and of votes are being anonymized with mix net shuffling. Afterwards, plaintext-equivalence tests are applied for checking the validity of the voting credential by each C i with each authorized credential from the shuffled list E i . For the votes with valid credentials the voting options A i are being decrypted.

Security assumptions that JCJ/Civitas relies on:

1. The adversary is not capable of simulating the voters during the registration process. The adversary is also not present the registration phase. 2. At least one registration teller is trusted and the communication channel between this teller and the voter is untappable5 . 3. The voting client is trusted. 4. At least k out of n tabulation tellers do not fail during decryption. 5. At least n -k + 1 out of n tabulation tellers are trusted not to reveal their key shares. 6. The channels between voters and voting system used for vote casting are anonymous. 7. The DDH assumption and the RSA assumption hold an a random oracle is implemented via cryptographic hash function. 8. At least one ballot box to which the cast votes are submitted is correct.

In addition to the security requirements, it is assumed that the voters are capable of handling the credentials, e.g. by using some kind of secure credential management.

Proposed Proxy Voting Scheme

To tailor our JCJ/Civitas extension towards proxy voting we introduce a new kind of credentials, so called delegation credentials. In addition to a unique voter credential in JCJ/Civitas, each voter i obtains a list of prioritized delegation credentials. To delegate a vote with a certain priority j the voter selects the j-th credential from her list and forwards it to the intended proxy. Voters are allowed to forward different credentials with different priorities to different proxies. Throughout the tallying phase for each voter only the vote cast with the highest priority is counted. Due to the fact that delegation credentials are generated on the same principles as the voting credentials in the original scheme the security of our extension also relies on the fact that the delegating credentials can be faked by the voter in case of coercion.

Necessary Modifications

We describe the modifications to the JCJ/Civitas scheme that are needed for implementing the delegation while ensuring the requirements listed in Section 2.

Ballot Clustering. Within the JCJ/Civitas scheme coercion-resistance is achieved by breaking the link between a voter's identity and votes cast in her name, both real and fake votes. The introduction of prioritized delegation credentials requires a relation between different credentials being maintained throughout the vote tallying phase. Retaining such a relation might however cause vulnerabilities with regard to coercion. To address these challenges we build upon proposals from scientific literature. Spycher et al. [START_REF] Spycher | A new approach towards coercion-resistant remote e-voting in linear time[END_REF] present a JCJ extension towards linear tallying time. Therefore, the authors propose to assign identifiers to cast (real and fake) votes. During vote tallying after anonymization cast votes are only compared against the public credential assigned to their respective identifier. This reduces the tallying complexity from quadratic to linear regarding the number of cast votes. We build upon this approach: votes cast by the voter or delegated to different proxies share the same identifier such that within the set of votes sharing the same identifier the vote with the highest priority is tallied.

Delegation Server. Forwarding voting credentials to proxies results in a coercion vulnerability: The adversary might coerce a proxy to forward all received voting credentials. In order to test whether the proxy complies the adversary could anonymously delegate a credential to her and check whether this credential is being forwarded back to her. We address this problem by introducing a new entity -possibly implemented in a distributed way -that functions as delegation server (DS). The underlying idea is that proxies do not receive delegated credentials directly from the voter. Instead the voter blinds her credential and sends it to the DS (over an anonymous and untappable channel) which forwards an anonymization of the blinded credential to the proxy. The unblinding value is sent to the proxy over the private and anonymous channel.

Inclusion of Linear Encryption. To prevent unauthorized usage of voting credentials the JCJ/Civitas scheme forces the voter to include the plaintext knowledge proof for the ciphertext encrypting the credential. This solution, however, is inapplicable to the delegation process since the proxy does not get to know the value of the credential as outlined above. We address this challenge by publishing voting credentials (in the registration and voting phases) encrypted with linear encryption rather than ElGamal encryption. On the other hand for delegating her vote the voter encrypts their delegating credential with standard ElGamal using (g 2 , h) as an encryption key. The resulting tuple {c} pk = (a = g r 2 , b = ch r ) together with other necessary information (see Section 3.2) is being forwarded to the proxy. If the proxy wants to cast the vote she chooses a random value of s and computes (g s 1 , a, bh s ) which is an LE-ElGamal encryption of c with randomness values r, s for which the proxy also can prove the knowledge of s as log g1 g s 1 .

Scheme Description

In this section we provide a detailed description of our proposed scheme.

Preliminary Stage. During this stage the keys used for encrypting votes and/or credentials are generated. The DS generates ElGamal keys with pk D = (g D , h D ) as public key. The tabulation tellers distributively generate LE-ElGamal keys pk T = (g 1 , g 2 , h T ). We further denote {m} pk T as ElGamal encryption with (g 2 , h T ) as corresponding key and {{m}} pk T as LE-ElGamal encryption. The list of proxies D 1 , ..., D d is being made public together with their public keys used for signing and designated-verifier proofs. For the sake of simplicity we assume that each proxy is eligible to vote herself as well. Furthermore, anonymous channels that enable communication between the proxies and the delegation servers as well as between proxies and the rest of the voters are established.

Setup Phase. Opposed to the standard JCJ/Civitas scheme, each registration teller generates T credential shares at random for each voter. Analogously to the JCJ/Civitas scheme, the encrypted credentials are publicly assigned to the respective voters whereby the order of the credential shares is of central importance to the delegation process. A public identifier, e.g. the position of the respective voter in the electoral roll is assigned to each voter. After the setup phase the bulletin board contains T credentials for every voter V 1 , ..., V k (see Table 1) as well as individual credential shares from each of N registration tellers for each priority 1, ..., T . We consider the lower number to denote the higher priority.

Registration. The registration phase remains identical to the standard JCJ/ Civitas scheme except the fact that each registration teller releases T ordered credential shares to the voter. The voter can then verify whether the received shares from the tellers for a credential c (j) i correspond to the encrypted shares published on the bulletin board near id i and priority j.

ID Priority

Credential shares id1 1 {{c 1,1 1 }} pk T , . . . , {{c 1. Content of the bulletin board after the setup phase of the extended scheme.

Before the voting, the voter merges her N • T credential shares as follows:

c (1) i = c 1,1 i • c 1,2 i • . . . • c 1,N i . . . . . . c (T ) i = c T,1 i • c T,2 i • . . . • c T,N i
Voting. To cast a vote (without considering delegation) for voting option o voter i prepares the following tuple:

{{id i }} pk T , {{c (j)
i }} pk T , {{o}} pk T , σ Here σ signifies both the well-formedness proofs for o as well as proof of randomness knowledge for {{c

(j) i }} pk T : namely, given {{c (j) i }} pk T = (c 1 , c 2 , c 3 ) = (g r1 1 , g r2 2 , c (j)
i h r1+r2 ) the voter proves the knowledge of randomness r 1 as log g1 c 1 . The value of j is chosen depending on the voter's delegations where we distinguish the following cases:

1. If the voter does not intend to delegate her vote at a later point in time she sets j = 1. 2. If the voter might intend to delegate her vote at a later point in time she sets j as the lowest available priority: that is j = T in case she did not delegate any vote yet or j = j d -1 if j d is the highest priority that was already delegated.

Additionally, the voter i casts her identifier id i in an encrypted manner which later serves for clustering ballots from the same voter with different credentials.

Delegating. To delegate her vote with priority j = 2, . . . , T to the proxy D k the following protocol (see Figure 1) is executed.

1. The voter i chooses a random value x and sends the following tuple to one or more of the DS:

{{id i }} pk T , {(c (j) i ) x } pk D , σ, id D k Here c (j) i
is the j-th credential from her credential list (c

(1) i , . . . , c (T )
i ), id i is the voter's index, σ is the proof of plaintext knowledge for {(c (j) i ) x } pk D and id D k is the identifier, e.g. the public key, of the chosen proxy. The voter also sends x, {{id i }} pk T to D k over a private channel.

The DS computes {(c

(j) i ) x } pk T from {(c (j) i )
x } pk D using proxy reencryption scheme and a designated-verifier proof using the public designated-verifier key of D k that both {(c X }} pk T = (g s 1 , c 1 , c 2 h s ). Then She encrypts her voting option o and prepares her ballot according to the voting process outlined above.

(j) i ) x } pk T and {(c (j) i ) x } pk D encrypt
Cancelling a delegation. If the voter intends to withdraw one or several vote delegations (but not excluding delegation in general), she issues the highest prioritized unused credential, overriding all previously cast votes on her behalf.

Obfuscating the number of cast votes. The fake votes intended to hide the number of votes cast by a specific voter or her proxy are added accordingly to Spycher et al.. For each identifier id i the tabulation tellers cast a random number of votes of the following form:

{{id i }} pk T , {{r}} pk T , {{o}} pk T , σ
Here r denotes a fake credential randomly drawn for each fake vote, a random valid voting option o, and the respective zero knowledge proofs σ. The number of fake votes for each voter is secret and is distributed as outlined in [START_REF] Spycher | A new approach towards coercion-resistant remote e-voting in linear time[END_REF].

First anonymization. After all the votes have been cast, votes with invalid proofs are removed and excluded from further tallying. Thereafter, tuples of the form {{id}} pk T , {{c}} pk T , {{o}} pk T are anonymized by the application of a mix net.

Ballot clustering. After anonymizing the tuples the values of id are decrypted. For any index id i appearing within at least one anonymized tuple the respective ordered list of credentials ({{c

(1) 1 }} pk T , . . . , {{c (T )
1 }} pk T ) is obtained from the bulletin board. All tuples sharing the same id i are clustered. The ordered of credentials is attached to each cluster, and the value id i is removed from all tuples.

Second anonymization. All lists of resulting tuples together with the respective list of attached credentials are anonymized by the application of a mix net. Note that the order of ciphertexts within the tuples is preserved so that the priority order of delegation credentials remains intact.

Extracting votes to be counted. In addition to weeding out the votes with invalid credentials our goal is to tally only the vote with the highest priority in case delegation took place. In order to do this for any element of the cluster -namely a list of tuples and public credentials -the list of tuples is matched on the basis of plaintext equivalence tests (PET) in decreasing order against the list of public credentials. Starting with the highest priority credential c 1 PETs are executed between all credentials of submitted tuples until a match is found. If a match is found the value {{o}} pk T is extracted from the matching tuple. Once the process has been terminated for all tuples a list of encrypted voting options ({{o 1 }} pk T , . . . , {{o n }} pk T ) has been extracted.

Third anonymization and result calculation. The list of encrypted voting options is anonymized by the application of a mix net. Eventually, the anonymized encrypted voting options are decrypted and the result is determined.

Security of the Proposed Scheme

In this section we consider the security evaluation of our scheme. We first summarize the security assumptions that need to be made, and then provide an informal security argument regarding the requirements given in Section 2.

Security Assumptions

We summarize the security assumptions specific to our scheme in the list below:

1. More than 2/3 of all tabulation tellers are trusted not to disclose private key shares to the adversary. 2. At least 1/3 of all tabulation tellers does not fail during decryption. 3. At least one of DS does not fail to forward the delegated votes to the proxy. 4. The DS does not disclose private information to the adversary. 5. The public key infrastructure for the proxies is trustworthy. 6. The private signing and designated-verifier keys of the proxy is not leaked. 7. Communication channels between the voters and the proxies are private.

Security Evaluation

We hold on to the assumptions of the original scheme which we provide in Section 3.2. The security properties of our scheme and the additional assumptions that are needed for them can then be evaluated as follows:

Vote integrity. The assumptions on integrity for voters remain the same as in the original scheme.

Availability. The election results can be computed under the assumption that at least k = 1 3 n tabulation tellers participate in the decryption.

Vote secrecy for voters. The system provides probabilistic coercion resistance, as there are two scenarios where the coercer can tell whether the voter has obeyed. The first scenario occurs if the number of fake votes for some voter equals the known minimal number. The probability of this can be controlled with the choice of an appropriate distribution function for fake votes. In the second attack, the coercer requests all the delegation credentials from the voter, and casts a vote with priority j that is unknown to the voter. In that case, unless there is a vote cast with the same priority from another voter, the coercer knows whether the credential given to her was real. The success probability of such an attack can be reduced with a smaller value of T . For example, with T = 3 the voter can either vote herself, delegate once or choose one back-up proxy, which we assume to be sufficient functionality for most of the elections. Outside of these scenarios, the system provides vote secrecy, and with it coercion resistance for the voters under the same assumptions as the original scheme with k ≤ 1 3 n. Since the delegating credentials are generated and distributed in the same way as the voting credentials the voter can cheat the coercer who acts as a proxy by providing a fake credential instead. Even if the coercer is watching the voter directly during the delegation, the voter can input a random value as her delegating credential so that the coercer cannot distinguish it from the real one.

Delegation integrity. Casting a delegated vote without voter's permission or a delegated vote with a higher than given priority would require the knowledge of the corresponding credential c (j) i for the voter i and priority j. Given that each one of those credentials is generated in the same way as the voter credentials in the original scheme it holds that they are not leaked under the same assumptions. Another way to break the delegation integrity would be to intercept the value x used for blinding the credential forwarded to the proxy which requires control over the communication channel between voter and proxy. Furthermore, it must be assumed that the public key infrastructure for the proxies is trustworthy so that impersonation of a proxy to a voter is infeasible.

Delegation availability. The proxy receives the credential from the DS accompanied by the designated verifier proof. In case no credential is sent the voter gets no confirmation and thus is able to repeat the delegation by choosing another DS. For this it must be assumed that the proxy's private key is not leaked and the confirmation cannot be sent by someone else. However, the DS is capable of submitting an invalid credential if it can fake the designated verifier proof. Therefore, it must be assumed that the private designated-verifier key of the proxy is not being leaked.

Vote secrecy for proxies. Given an anonymous channel between the proxies and the bulletin board the secrecy of votes cast by proxies corresponds to the vote secrecy for the voters. An additional assumption is required that the DS is not collaborating with the adversary. In this case using a designated-verifier proof the proxy can fake the credentials resulting from the delegation process and present them to the coercer if forced to do so. Delegation privacy. The proxy could be capable of learning the identity of the delegating voter in following ways: 1) by identifying the message's origin via network, 2) by learning the voter's ID, 3) by being able to assign the given delegating credential to the voter's identity. The communication channels between voters and proxies are anonymous, the voter ID is sent encrypted and only decrypted after anonymization. The delegating credentials are not otherwise leaked which is similar to the voter's credentials in the original scheme. This implies that the proxy is incapable of determining the identity of voters delegating to her. In case of a coerced proxy the coercer would not have a possibility of knowing whether the credential passed to them is valid and whether the voter has cast another vote herself. This corresponds with the coercion-resistance properties of the original scheme.

Delegation unprovability. Given the anonymous communication channels between the DS and the voters a proxy cannot prove for given credentials that they come from actual voters and are not simulated by the proxy herself. Moreover, due to the coercion resistance properties of the original scheme and its credential generation process the proxy herself cannot verify whether the credential she received is valid. This implies that the proxy is incapable of constructing a convincing proof of possessing any amount of delegated votes.

Conclusion

Proxy voting constitutes a new voting mode in which voters are able to delegate their right to vote on issues beyond their expertise. At the same time, it also opens new attack vectors as there is a legitimate possibility to transfer a vote to another person who could be a coercer. To address these issues we created an Internet proxy voting scheme which focuses on coercion resistance and is based on the well-known JCJ/Civitas scheme. It provides functionality that enables vote delegation while at the same time ensuring the security of the delegation.

As our extension introduces additional credentials for delegation, which might overwhelm voters, an important part of future work would be to improve usability of the scheme. In the future, we will consider the proposal by Neumann and Volkamer [START_REF] Neumann | Civitas and the real world: Problems and solutions from a practical point of view[END_REF] to address the credential handling in coercion-resistant proxy voting.

Fig. 1 .

 1 Fig. 1. Delegation of the voter idi to the proxy D k , with zero-knowledge proofs omitted.

http://liquidfeedback.org/, last accessed January, 7, 2016.

https://adhocracy.de/, last accessed January, 7, 2016.

That is, the adversary is incapable of reading the messages sent over the channel.

This can be done via a two-way anonymous channel or by publishing the signature on {(c (j) i ) x } pk D on the bulletin board.

Acknowledgements

This project (HA project no. 435/14-25) is funded in the framework of Hessen ModellProjekte, financed with funds of LOEWE -Landes-Offensive zur Entwicklung Wissenschaftlich-ökonomischer Exzellenz, Förderlinie 3: KMU-Verbundvorhaben (State Offensive for the Development of Scientific and Economic Excellence).

This paper has been developed within the project 'VALID' -Verifiable Liquid Democracy -which is funded by the Polyas GmbH.


Sérgio Câmara
email: smcamara@inmetro.gov.br

Dhananjay Anand
email: dhananjay.anand@nist.gov

Victoria Pillitteri
email: victoria.pillitteri@nist.gov

Luiz Carmo

Multicast Delayed Authentication For Streaming Synchrophasor Data in the Smart Grid

Keywords: Multicast authentication, Smart Grid, synchrophasors, Wide Area Monitoring Protection and Control } d Keychain m-1 Keychain m Keychain m+1

Multicast authentication of synchrophasor data is challenging due to the design requirements of Smart Grid monitoring systems such as low security overhead, tolerance of lossy networks, time-criticality and high data rates. In this work, we propose inf -TESLA, Infinite Timed Efficient Stream Loss-tolerant Authentication, a multicast delayed authentication protocol for communication links used to stream synchrophasor data for wide area control of electric power networks. Our approach is based on the authentication protocol TESLA but is augmented to accommodate high frequency transmissions of unbounded length. inf -TESLA protocol utilizes the Dual Offset Key Chains mechanism to reduce authentication delay and computational cost associated with key chain commitment. We provide a description of the mechanism using two different modes for disclosing keys and demonstrate its security against a man-in-the-middle attack attempt. We compare our approach against the TESLA protocol in a 2-day simulation scenario, showing a reduction of 15.82% and 47.29% in computational cost, sender and receiver respectively, and a cumulative reduction in the communication overhead.

Introduction

Smart Grids are large critical cyber-physical infrastructures and are being transformed today with the design and development of advanced real-time control applications [START_REF] Patel | Real-time application of synchrophasors for improving reliability[END_REF]. The installation of Phasor Measurement Units (PMUs) as part of world-wide grid modernization is an example of major infrastructure investments that require secure standards and protocols for interoperability [START_REF] Greer | NIST Framework and Roadmap for Smart Grid Interoperability Standards[END_REF].

PMUs take time-synchronized measurements of critical grid condition data such as voltage, current, and frequency at specific locations that are used to provide wide area visibility across the grid.The synchrophasor data aggregated from multiple PMUs are used to support real-time analysis, planning, corrective actions, and automated control for grid security and resiliency. Currently, high-speed networks of PMUs are being used for Wide Area Monitoring Protection and Control (WAMPAC) applications to provide situational awareness in the Eastern and Western Interconnection of North America, in China, Canada, Brazil and across Europe [START_REF] Patel | Real-time application of synchrophasors for improving reliability[END_REF]. Before the installation of PMUs, the lack of widearea visibility is one of the factors that prevented early fault identification of the 2003 Northeast America and 2003 Italy blackouts [START_REF]Union for the Coordination of the Transmission of Electricity[END_REF] [START_REF] Liscouski | Final report on the August 14, 2003 blackout in the United States and Canada: Causes and recommendations[END_REF]. Malicious PMU data or deliberate attacks could result in inaccurate decisions detrimental to grid safety, reliability, and security, that said, PMUs need information authentication and integrity, while confidentiality may be considered optional.

Authentication schemes in the Smart Grid must be able to efficiently support multicast. Current standard solution, suggested by IEC 62351 [START_REF]International Electrotechnical Commission: IEC TS 62351-1 Power systems management and associated information exchange -Data and communications -Part 1: Communication network and system security-Introduction to security issues[END_REF], comprises HMAC authentication algorithm for signing the synchrophasors. However, sharing only one symmetric key across a multicast group cannot guarantee adequate security, and this approach suffers from the scalability problem. The use of asymmetric cryptography and digital signatures for multicast authentication raises concerns about the impact on cost and microprocessor performance. One-Time Signature schemes can enable multicast authentication, however they suffer from communication and storage overhead, and complicated key management [START_REF] Wang | Cyber security in the Smart Grid: Survey and challenges[END_REF].

Although some previous literature works assume, in general, that delayed authentication is not suitable for real-time applications [START_REF] Law | Comparative study of multicast authentication schemes with application to wide-area measurement system[END_REF] [START_REF] Li | Multicast authentication in the smart grid with one-time signature[END_REF], such method is still eligible for some monitoring and control applications that permit relatively larger delay margins (e.g. wide-area oscillation damping control application) [START_REF] Zhu | Examination of data delay and packet loss for wide-area monitoring and control systems[END_REF]. For more considerations on this topic, see Section 2. Moreover, delayed authentication presents advantages over cited issues by supporting multicast data streaming, symmetric and lightweight cryptography, corrupt data and attack detection. Also it allows scalable solutions and key management, tolerates packet loss, and provides low communication overhead and high computational efficiency.

The primary objective of this work is to propose a multicast delayed authentication protocol called inf -TESLA in order to provide measurement authentication in a WAMPAC application within the Smart Grid. Also, we design the Dual Offset Key Chains mechanism which is used by our protocol to generate the authenticating keys and to provide long-term communication without the need of key resynchronization between the sender and receivers. A description of two different modes for disclosing keys and a demonstration of a man-in-the-middle attack attempt against our mechanism are also provided.

Section 2 presents an overview of the network architecture used for wide area aggregation of PMU data as well as some delay constraints and authentication infrastructure. In Section 3 we discuss prior work in the area of packet based authentication protocols for streaming communication, and then in Section 4 we present the inf -TESLA protocol and describe the Dual Offset Key Chains mechanism along with its security properties and conditions. In Section 5 we evaluate our approach against the original TESLA protocol. Finally, we summarize our results and propose future works in Section 6.

Scenario Characteristics

The network architecture considered for this work is as follows. Each communication link in the infrastructure comprises one PMU sender node S capable of multicasting packets to m receivers R k applications, where 1 ≤ k ≤ m. PMU S sends time-stamped synchrophasor data packets at a rate of 10 to 120 packets per second and that can be dropped in the way to the receivers. The network has several n intermediate nodes between S and R k , n > 0, called Phasor Data Concentrators (PDCs). PDCs can chronologically sort received synchrophasors as well as aggregate, repackage and route data packets to the set of higher level PDCs (Super PDCs). When packets are missing or lost, PDCs may (with due indication) interpolate measurements in order to retain the communication link.

There are different wide-area monitoring and control applications that consume synchrophasor data and have different time delays and quality requirements. For instance, Situational Awareness Dashboard, Small-Signal Stability Monitoring, and Voltage Stability Monitoring/Assessment accept up to 500 milliseconds in communication latency, other applications such as Long-term stability control, State Estimation, and Disturbance Analysis Compliance can handle up to 1000 ms. For the entire list, see [START_REF] Tuffner | Phasor Measurement Unit Application Data Requirements[END_REF].

Zhu et al. [START_REF] Zhu | Examination of data delay and packet loss for wide-area monitoring and control systems[END_REF] simulates the latency for monitoring applications over the Smart Grid network architecture and obtained results within a range of 150-220 ms. For centralized control applications, the latency was well below 500 ms. From the delayed authentication perspective, the minimum delay of the authentication confirmation by R k is approximately twice the latency of the network. Still, delayed authentication protocols are able to attend the requirements for the above cited applications.

When utilizing multicast communication, IEC 61850-90-5, the standard for communication networks and systems for power utility automation, requires a Key Distribution Center (KDC), which provides the symmetric key coordination between S and R k . We assume that each S is its own KDC, which is also endorsed by the standard. Furthermore, as our scheme demands that S prove its identity to R k once during communication initialization, each receiver is required to validate a digital signature from S and maintaining a copy of its public key certificate. For this purpose, we assume that a Public-Key Infrastructure (PKI) is also available.

Security Considerations

We assume that attacks are accordingly aligned, via a man-in-the-middle, to either manipulate data values or masquerade as a legitimate PMU. Using the attack model from [START_REF] Wang | Time valid one-time signature for time-critical multicast data authentication[END_REF], the adversary is not limited by network bandwidth and has full control to drop, resend, capture and manipulate packets. Although his computational resources can be large, it is not unbounded and he cannot invert a pseudorandom function with non-negligible probability. Each receiver R k is able to authenticate both the content and source of synchrophasor payloads after a delay of d N M ax using our delayed authentication scheme presented in Section 4. However, if a packet fails authentication at time t, then an attack that has been active and undetected since t-d N M ax represents the maximum threat exposure.

The security primitives used throughout this paper are as follows:

-One-way hash function H operates on an arbitrary length input message M , returning h = H(M ). H can be implemented with SHA-2 family algorithms. -Message Authentication Code M AC(K, M ) provides a tag that can verify authenticity and integrity of message M given a shared key K. HM AC(K, M ) is a specific construction which includes an underlying cryptographic hash function to create the authenticating tag. -Hash chain H n (M ) denotes n successive applications of cryptographic hash function H to message M .

Related Work

Multicast authentication is an active research field in recent years and has been applied to a wide range of applications. In Smart Grids, it is being used for monitoring, protection and information dissemination [START_REF] Wang | Cyber security in the Smart Grid: Survey and challenges[END_REF]. In this section, we review all the TESLA-based multicast authentication schemes and other multicast authentication schemes used for electrical power systems.

To address the challenge of continuous stream authentication for multiple receivers on a lossy network, Timed Efficient Stream Loss-tolerant Authentication (TESLA) was introduced by Perrig et al [START_REF] Perrig | Efficient Authentication and Signing of Multicast Streams over Lossy Channels[END_REF]. Based on the Guy Fawkes protocol [START_REF] Anderson | A new family of authentication protocols[END_REF] and requiring loose time synchronization between the senders and receivers, TESLA is a broadcast authentication protocol considering delayed disclosure of keys used for authentication of previous sent messages and packet buffering by the receiver. This protocol supports fixed/dynamic packet rate and delivers packet loss robustness and scalability. Benefits of TESLA include a low computation overhead, low per-packet communication overhead, arbitrary packet loss is tolerated, unidirectional data flow, high degree of authenticity and freshness of data. Further work proposed several modifications and improvements to TESLA, allowing receivers to authenticate packets upon arrival, improved scheme scalability, reduction in overhead, and increased robustness to denial-ofservice attacks [START_REF] Perrig | Efficient and secure source authentication for multicast[END_REF].

Studer et al. describe TESLA++ [START_REF] Studer | Flexible, extensible, and efficient VANET authentication[END_REF], a modified version of TESLA resilient to memory-based DoS attacks. They combine TESLA++ and ECDSA signatures to build an authentication framework for vehicular ad hoc networks.

µTESLA [START_REF] Perrig | Spins: Security protocols for sensor networks[END_REF] adapts TESLA to make it practical for broadcast authentication in severely resource-constrained environments; like sensor networks. Some of these adaptations include the use of only symmetric cryptography mechanisms, less frequent disclosure of keys and restriction on the number of authenticated senders. Liu and Ning [START_REF] Liu | Multilevel µTESLA: Broadcast Authentication for Distributed Sensor Networks[END_REF] reduce the overhead needed for broadcasting key chain commitments and deal with DoS attacks. Their Multilevel µTESLA protocol considers different levels of key chains to cover the entire lifespan of a sensor.

Other methods include the One-Time Signatures family which gained popularity recently and is applicable to multicast authentication and also for WAMPAC applications. The author in [START_REF] Perrig | The BiBa one-time signature and broadcast authentication protocol[END_REF] describes a one-time signature based broadcast authentication protocol based on BiBa. BiBa uses one-way functions without trapdoors and exploits the birthday paradox to achieve security and verification efficiency. Its drawbacks include a large public key and high overhead for signature generation.

HORS [START_REF] Reyzin | Better than BiBa: Short One-Time Signatures with Fast Signing and Verifying[END_REF] is described by Reyzin et al. as an OTS scheme with fast signing and signature verification using a cryptographic hash function to obtain random subsets for the signed message and for verifying it, but it still suffers from frequent public key distribution. TSV [START_REF] Li | Multicast authentication in the smart grid with one-time signature[END_REF] multicast authentication protocol generates smaller signatures than HORS and has lower storage requirement at the cost of increased computations in signature generation and verification. TSV+ [START_REF] Law | Comparative study of multicast authentication schemes with application to wide-area measurement system[END_REF], a patched version of TSV, uses uniform chain traversal and supports multiple signatures within an epoch. SCU [START_REF] Ugus | A rom-friendly secure code update mechanism for wsns using a stateful-verifier τ -time signature scheme[END_REF] is a multicast authentication scheme designed for wireless sensor networks and SCU+ [START_REF] Law | Comparative study of multicast authentication schemes with application to wide-area measurement system[END_REF] adapts it for power systems using uniform chain traversal as well. TV-HORS [START_REF] Wang | Time valid one-time signature for time-critical multicast data authentication[END_REF] uses hash chains to link multiple key pairs together to simultaneously authenticate multiple packets and improves the efficiency of OTS by signing the first l bits of the hash of the message. As a downside, TV-HORS has a large public key of up to 10 Kbytes.

Proposed Solution

In this section, we propose inf -TESLA, a TESLA based scheme. At first, we review TESLA to give some background and then present our scheme.

TESLA

Timed Efficient Stream Loss-tolerant Authentication (TESLA) [START_REF] Perrig | Efficient Authentication and Signing of Multicast Streams over Lossy Channels[END_REF] [13] [15] [START_REF] Perrig | Timed efficient stream loss-tolerant authentication (TESLA): Multicast source authentication transform introduction[END_REF] is a broadcast authentication protocol with low communication and computation overhead, tolerates packet loss and needs loose time synchronization between the sender and the receivers.

TESLA relies on the delayed disclosure of symmetric keys, therefore the receiver must buffer the received messages before being able to authenticate them. The keys are generated as an one-way chain and are used and disclosed in the reverse order of their generation. At setup time, the sender must first set n as the index of the first element K n . For generating the key chain, the sender picks a random number for K n and using a pseudo-random function f , he constructs the one-way function F : F (k) = f k (0). So, the sender generates recursively all the subsequent keys on the chain using K i = F (K i+1 ). By that, the last element of the chain is K 0 = F n (K n ), and all other elements could be calculated using

K i = F n-i (K n ).
Each K i looks pseudo-random and an adversary is unable to invert F and compute any K j for j > i. In the case of a lost packet containing K i , a receiver can calculate K i given any subsequent packet containing K j , where j < i, since K j = F i-j (K i ). As a result, TESLA tolerates sporadic packet losses.

The stream authentication scheme of TESLA is secure as long as the security condition holds: A data packet P i arrived safely, if the receiver can unambiguously decide, based on its synchronized time and maximum time discrepancy, that the sender did not yet send out the corresponding key disclosure packet P j .

TESLA also supports both communication with fixed or dynamic packet rate. For fixed rate, the sender discloses the key K i of the data packet P i in a later packet P i+d , where d is a delay parameter set and announced by the sender during setup phase. The sender determines the delay d according to the packet rate r, the maximum tolerable synchronization uncertainty δ tM ax and the maximum tolerable network delay d N M ax , setting d = (δ tM ax + d N M ax )r . In this mode, the scheme can achieve faster transfer rates. For dynamic rate, the sender pick one key per time interval T int . Each key is assigned to a uniform interval of duration T int , T 0 , T 1 ,..., T n , that is, key K i will be active during the time period T i . The sender uses the same key K i to compute the MAC for all packets which are sent during T i , on the other hand, all packets during T i disclose the key K i-d . In this case, d = (δ tM ax + d N M ax )/T int . We use the designation d and d for fixed and dynamic rates respectively.

For each new receiver that joins the communication network, the sender initially creates an authenticated synchronization packet. This packet contains parameters such as interval information, the disclosure lag and also a disclosed key value -which is a commitment to the key chain. The sender digitally signs this packet to each new receiver before starting the streaming communication.

inf -TESLA

inf -TESLA, short for infinite TESLA, is a multicast authentication protocol based on TESLA suitable for use in long term communication at high packet rates. As in TESLA, inf -TESLA relies on the strength of symmetric cryptography and hash functions and on the delayed disclosure of keys as a means to authenticate messages from the sender. Also, it requires only loose time synchronization between the sender and the receiver and can operate under both dynamic and fixed packet rates.

By using fixed packet rate mode, there is no need for setting specific time intervals for MACing and disclosing keys. Each autheticating key is used once for the actual message and disclosed d packets later. Although this operational mode can achieve maximum speed on authenticating previous packets, it has a drawback of quickly consuming the authenticating key chain, depending on the frequency of the packets.

Since we use one-way hash functions to build independent key chains, every time one of the key chains comes to an end (meaning that it was fully used in the authentication process) the sender must automatically build, store and utilize a new key chain in its place. In the original TESLA a sender would have to reassign a new synchronization packet as the current key chain comes to an end, inflicting non-negligible network and computational overhead by digitally signing a synchronization packet at the end of each key chain.

inf -TESLA addresses this issue by using the Dual Offset Key Chains mechanism. This mechanism uses a pair of keys for each message and guarantees continuity of the multicasting authentication process without the need for signing and sending a new synchronization packet. The mechanism creates two offset key chains so that a pair of active key chains are always available and, as the main principle, a key chain m always straddles the substitution of key chain m -1 with m + 1. Figure 1 illustrates the Dual Offset Key Chains mechanism by which key chain m supports the substitution of key chain m -1 for key chain m + 1 without the need for resynchronization. A detailed description of the Dual Offset Key Chains mechanism is presented on Section 4.2.

The overall initialization setup is similar to TESLA. Before the data streaming begins, the sender first determines some fundamental information about the network status, d N M ax ), and time synchronization, δ tM ax , and builds its first two key chains. We assume that both sender and receiver are time synchronized by a reliable time protocol (e.g. PTP). After that, the sender S chooses the delay parameter d (Section 4.1) that will base the decision of the receiver R k to either accept a packet from S. This condition is Security Condition-1 for inf -TESLA.

For bootstrapping each new receiver, S constructs and sends the synchronization (commitment) packet to the new incomer. For a dynamic packet rate, this packet contains the following data [START_REF] Perrig | Efficient and secure source authentication for multicast[END_REF]: the beginning time of a specific interval T j along with its id I j , the interval duration T int , the key disclosure delay d , a commitment to the key chain K m i and key chain K m+1 i (i < j -d where j is the current interval index).

For a fixed packet rate r, let j 1 and j 2 be the current key from key chains m and m + 1 respectively. The synchronization packet contains: delay d and the commitment for the key chains K m i1 and K m+1 i2 (i 1 < j 1 -d and i 2 < j 2 -d). We will focus on fixed packet rate in this paper for the sake of brevity and convenience of notation. While a fixed packet rate is potentially more likely for the streaming applications we address, our approach is compatible with both dynamic and fixed rates.

Dual Offset Key Chains mechanism. The Dual Offset Key Chains mechanism enables continuity in streaming authentication without the periodic resynchronization between S and R k ∈ R required by TESLA. Two key chains, offset in alignment, are used simultaneously by the mechanism to authenticate messages. For every packet, there are always two active key chains and, from each chain, one non-used key available for MACing.

For constructing the two key chains, first the sender chooses n, the total number of elements on a single key chain. Let l m be the current number of remaining elements on the key chain m. Here we assume that all created keys are deleted just after being used for authenticating messages. Let M be the maximum available memory for storing the key chains, assuming that M is big enough for storing two key chains, m and m + 1, at any time. The value of n must be chosen accordingly to the following constraints: (i) n ≥ l m-1 + 2(d + 1) and (ii) n ≤ M 2 + d. The the first constraint sets a minimum value for n, that is the minimum initial size of a key chain. During the initialization setup of the first receiver synchronization, we consider l m-1 = 0 for constructing the first key chain. The second constraint restricts the maximum number of elements in a key chain. If a key chain m does not meet this limit, key chain m + 1 will not be long enough to meet the security condition for the key chain exchange procedure (see Section 4.2). In practice, it may not be feasible to calculate a whole key chain in the time taken to send two data packets and so S may compute and store key chain m + 1 well before the end of key chain m -1.

A packet P j sent by S is formed by the following data

P j = {M j , i 1 , i 2 , K m i1-d , K m+1 i2-d , M AC(K m i1 ||K m+1 i2
, M j )}. Every packet carries the actual message M j , the current sequence number of each key chain i 1 and i 2 , the disclosed authenticating keys K m i1-d and K m+1 i2-d (discussed later in Section 4.2) and the MAC of the message resultant from an operation that uses the concatenation of current keys from both key chains. In particular, at the beginning of a key chain m + 1, the notation K m+1 i2-d may refer to the last keys in the key chain m -1.

Disclosure of keys. inf -TESLA has two modes of operation for disclosing keys: 2-keys and Alternating. In the 2-keys mode (or standard mode, as previously described), each packet P j discloses two authentication keys, one from each key chain, for the same message M i , that is packet P j has the following information,

P j → K m i1-d , K m+1 i2-d .
The Alternating mode discloses one key from each key chain alternatively in each data packet. Formally, two consecutive packets would have the following information about keys, P j → K m i1-d and P j+1 → K m+1 i2+1-d , where indexes i 1 -d and i 2 -d correspond to the keys of both key chains to be disclosed in the same data packet in 2-keys mode of operation. Figure 2 shows the key chains in time and the two modes for disclosing keys. In Section 5, we present a more detailed comparison of these two modes in relation to communication overhead, computational cost and authentication delay.

The disclosure delay d for the keys is directly affected by the maximum tolerable network delay d N M ax , so each receiver R k will present a different delay value. Sender S must set d as the largest expected delay in order to meet security condition-1. Dual Offset Key Chains mechanism security. Key chain security is based on the widely used cryptographic primitive: the one-way chain. One-way chains were first used by Lamport for one-time password [START_REF] Lamport | Password authentication with insecure communication[END_REF] and has served many other applications in the literature.

The Security Condition-2 for inf -TESLA concerns the key chain exchange procedure. This condition states that both key chains cannot be substituted within a time interval d/r (or within d packets). If this happens, the receiver must drop the following packets and request for resynchronization with the sender. This protocol restriction assures the authentication inviolability of inf -TESLA and must be observed at all times by the receiver. The receiver is solely responsible for monitoring the key chain exchange procedure and accepting, or rejecting, the new key chain.

In Figure 3, we show an example of a man-in-the-middle attack attempt on the Dual Offset Key Chains mechanism and the importance of the security condition-2. For this example, we consider d = 9 as minimum number packets the sender has to wait to disclose a key, the last element n = 50 for all key chains, and the asterisk symbol indicates an item maliciously inserted by the attacker. The packets are presented without indices "i" for cleaner presentation.

We first illustrate how this attack can work on a single key chain mechanism without commitment packets as follows: When the attacker senses a change in the key chain by testing every disclosured key (a), he inserts M * 0 as the first manipulated message and MACs it using the first element K * 0 of a forged key chain of his own. The attacker continues faking the messages and its MACs till the last authentic key used for MACing is disclosured. After that point, the attacker is able to take complete control of the communication without being detected (b). For the second part of Figure 3, the same attack is attempted against our mechanism. Also the attacker is able to sense when a disclosured key chain comes to an end and can also substitute the messages and the MACs in the packets. However, when he tries to take complete control of the key chain by forcing the forged key K * * 0 over the key chain m = 2, this indicates for the receiver a violation of the security condition-2 for the key chain exchange procedure.

Another concern is how many consecutive packets could be lost by the receiver without actually being an attack. Following the security condition for key chain substitution, there must not be two different key chain substitutions within a period of d/r, so the receiver must be aware that the limit for consecutive packets lost is at maximum d. If, for some reason, more than d packets are lost/dropped, the receiver must assure that the following disclosed keys are authentic elements of at least one of the existing key chains, otherwise the receiver will not be able to authenticate any of the next received packets. From this point, the receiver must refuse this stream and request for a new synchronization with the sender.

Another security issue can occur when the last key K n in the key chain's sequence is lost, that can cause a total lack of authentication of a previous packet P n . When some K i is lost, it can be computed from any subsequent key in the key chain through function F (Section 4.1), however when i = n there is no subsequent key. This issue can be extended for the last d elements of the key chain, meaning that in this scenario some packets may not be authenticated and then must be dropped by the receiver. For the Alternating mode for disclosing keys, the receiver would drop d+1 packets in the worst case. This issue concerning the last keys of the key chain is a vulnerability of the original TESLA as well.

Elaborate attacks, like selective drop of packets, can cause even more authentication delay without being noticed. For instance, in the case of the Alternating keys disclosure mode, one attacker can induce an alternating drop of packets preventing the sender to authenticate some sequential packets. To mitigate these attacks, the receiver must set an upper limit for the maximum number of non authenticated packets to ignore before resynchronizing with the sender.

Evaluation against TESLA

For the following comparison evaluation, we check for communication overhead, authentication delay and computational cost on a long term communication for each of the following schemes: original TESLA, inf -TESLA 2-keys (two disclosured keys per packet) and inf -TESLA alt (alternating key chain disclosure). Due to PMUs' operational settings, we are only considering a fixed packet rate mode. Also, we assume the following constraints for the simulation: key chains for evaluating OTS multicast schemes. However, as inf -TESLA must build approximately 4 times the number of key chains as TESLA for the same number of packets, comparisons are done for fixed simulation duration rather than number of key chains. Still, for the given constraints, TESLA needs an approximate number of 1024 key chains to operate.

Table 1 shows the formulas to calculate all security related communication overhead of each of the 3 schemes. Let C be the number of commitments (signed packets), P the total number of transmitted packets and sKey, sM ac and sSig be the size of a cryptographic key, the size of the MAC tag and the size of a signature tag respectively. inf -TESLA 2-keys presents the higher communication overhead due to two disclosed keys per packet, while TESLA and inf -TESLA alt present a slightly, but negligible, difference on the overhead during two days of operation.

For calculating the computational cost overhead of each scheme, we use the formulas shown in Table 2. The processing cost in cycles per each operation of hashing, macing, signing and verifying is represented by cHash, cM ac, cSig and cV er respectively. From the graph in Figure 4, we can observe the higher computational cost of the sender and receiver operating TESLA over inf -TESLA, due to constant signing and verification operations.

For two days of simulation in this configuration, a sender running TESLA protocol on fixed packet rate mode has to sign up to 1036 commitment packets and spends on average 0.373117 gigacycles/hour, while running inf -TESLA he would spend 0.314087 gigacycles/hour of operation, which means a reduction of 15.82% in computational cost for the sender. On the receiver side, a TESLA receiver spends in average 0.596289 gigacycles/hour, while inf -TESLA needs 0.314303 gigacycles/hour, meaning a reduction of 47.29% in computational cost for the receiver. All values of cycles/operation of the security primitives are referenced from the Crypto++ Library 5.6.0 Benchmarks [START_REF] Dai | Crypto++ 5.6. 0 benchmarks[END_REF].

Although the alternating keys disclosure mode showed good results on the two previous evaluations, this mode increases the authentication delay of a packet P i by one packet. That is because the second key needed for authenticating P i , i.e. K m+1 i2 , will only be disclosed on P j+1 where j > i + d. Also, if P j+1 happens to be lost, the authentication of P i will be only achieved when receiver has the disclosed key included in P j+3 . On both other schemes, the authentication of a packet P i is normally achieved after receiving P j , j > i + d, and if P j is lost, the missing keys can be recovered from the contents in P j+1 . Also regarding authentication delay evaluation, necessary time overhead for generation and verification of digital signatures during key chains exchange may affect TESLA's continuous flow on higher frequencies of streamed data.

Although TESLA protocol is an efficient protocol and has low security overhead, it was not originally designed for long-term communication at high packet rates. We observe that inf -TESLA, in alternating disclosure mode, can deliver a slightly lower communication overhead and, for both modes, result in a sig- nificant reduction in computational overhead over the original protocol for the given conditions. In general, inf -TESLA scheme also provides great suitability for key storage and computational constrained devices, such as in Wireless Sensor Networks (WSNs).

Conclusion

In this work, we present inf -TESLA, a multicast delayed authentication protocol for streaming synchrophasor data in the Smart Grid, suitable for long-term communication and high data rates scenarios. To authenticate messages from the sender, inf -TESLA uses two keys to generate the MAC of the message and discloses both keys after a time frame d/r, on a fixed packet rate of operation. We also design the Dual Offset Key Chains mechanism to produce the authenticating keys and provide a long-term communication without the need of frequently signing resynchronization packets containing commitments to the new key chains, which ensures continuity of the streaming authentication. We prove our mechanism against a man-in-the-middle attack example and describe the security conditions that must be observed at all times by the receiver. inf -TESLA enables two different modes for disclosing keys, 2-keys (or standard) and Alternating keys. We present a comparison between this two modes against TESLA within a WAMPAC application, and our protocol shows even more efficiency when compared to the original. Although the Alternating key disclosure mode increases the authentication delay by one packet, it provides less impact on communication overhead and a reduction of 15.82% and 47.29%, sender and receiver respectively, in computational cost during operational time. Generally, inf -TESLA shows promise and suitability for key storage and computational constrained devices.

In future work, we intend to do a further analysis on the trade-off between key storage size in devices and protocol performance, and on the possible (minimum/maximum/average) values for the authentication delay by simulating our protocol in a WAMPAC network.

Fig. 1 .

 1 Fig. 1. An illustration of dual offset key chains as used for inf -TESLA.

Fig. 2 .

 2 Fig. 2. Two modes for disclosing keys: 2-keys and alternating.

Fig. 3 .

 3 Fig. 3. Example of a man-in-the-middle attack on a single hash chain without commitment and on the Dual Offset Hash Chains mechanism.

Fig. 4 .

 4 Fig. 4. Computational cost for TESLA and inf -TESLA over 2 days of streaming data.

Table 1 .

 1 Communication overhead. Phasor data frame size of 60 bytes, according to the C37.118 standard[START_REF] Zhu | Examination of data delay and packet loss for wide-area monitoring and control systems[END_REF], over UDP transport layer protocol.-HMAC function and f function implementation as HMAC-SHA-256-128.Both HMAC tag size and key size of 128 bits (truncated). -Digital signature implemented as ECDSA over GF(p) of 256 bits. Although TESLA considers RSA signatures, for comparison purposes we use ECDSA.The keys and signatures sizes are based on the NIST SP 800-131A[START_REF] Barker | Recommendation for transitioning the use of cryptographic algorithms and key lengths[END_REF] for recommendations on use of cryptographic algorithms and key lengths. -Maximum number of keys n that can be stored at a time in the cache memory of a device is 10,000 keys. -Sender's packet rate (frequency) of 60 packets/sec. -Simulation time of 2 days. Past references[START_REF] Law | Comparative study of multicast authentication schemes with application to wide-area measurement system[END_REF] established a baseline of 1024

		Formula
	TESLA (fixed)	C * (sKey + sSig) + P * (sKey + sM ac)
	Inf -TESLA 2-keys 2 * sKey + sSig + P * (2 * sKey + sM ac)
	Inf -TESLA alt	2 * sKey + sSig + P * (sKey + sM ac)
		2-day simulation (MBytes)
	TESLA (fixed)	331,825
	Inf -TESLA 2-keys	497,664
	Inf -TESLA alt	331,776
	-

Table 2 .

 2 Computational cost calculation. C * cV er + P * (cM ac + cHash) Inf -TESLA (both) cV er + 2 * P * (cM ac + cHash)

		Sender
	TESLA (fixed)	C * cSig + P * (cM ac + cHash)
	Inf -TESLA (both) cSig + 2 * P * (cM ac + cHash)
		Receiver
	TESLA (fixed)

This work is supported in part by grants from H2020 EU-BR SecureCloud (Grant No. 2568).