est destinée au dépôt

The city of Tucson and the upper Santa Cruz River Valley are located in the Sonoran Desert of southeastern Arizona (USA), a region affected by both massive population growth and rapid climate change. As a consequence, its fragile arid ecosystem undergoes increasing pressure resulting in important land use / land cover (LULC) transformations. This paper proposes a generic and innovative method to fit the crucial need of monitoring and quantifying landscape evolution over several decades.

MATERIAL AND METHODS

We mobilized the tremendous computing capacities of Google Earth Engine (GEE) to create yearly LULC maps from 1986 to 2020, in a 5 steps workflow:

1. Data pre-processing, consisting of invalid pixels (e.g. clouds) masking, illumination (BRDF) and topographic corrections, and mosaicking of biseasonal LandSat imagery for each year;

Computation of ancillary data, including

RESULTS AND DISCUSSION

We achieved very good classification results (yearly Overall Accuracies ranging from 86.7% In 1986 to 96.3% in 2020), allowing us to precisely quantify trends LULC Changes dynamics over a 35 year period, and in the future.

Natural land covers (i.e., shrubs, grasslands, forests and barren washes) are highly dominant in the region as they cover ± 90% of the watershed. Shifts among natural LULC classes also make up the vast majority of identified changes (86.8%). Most commonly observed dynamics are temporary switches between natural land covers, which can be explained by different factors, notably climatic variations from one year to another, such as prolonged and persistent drought, or the wildfire and regeneration cycles impacting forested areas. Still, these LULC classes maintain a rough balance over the years at the watershed scale, as most transformations are compensated by opposite trends.

Regarding human-induced LULC changes, a few mining or agriculture lands have been newly established in some parts of our the region of interest, but their overall area has decreased as they are counterbalanced by the natural revegetation of abandoned lands. Albeit less frequent, anthropic LULC transformations are most often permanent, especially regarding conversion to built-up areas which is the main driver of persistent LULC changes in the Tucson area (2.9% of observed changes). Urban development has demonstrated a steady increase and has more than doubled (+118.7%) over the last 35 years, and this expansion is clearly oriented towards low-density development on new lands, mostly shrubs, rather than densification of existing urban areas (+143.2% vs. +79.1%). This leads to a leapfrog urbanization, with 60% this suburbanization occurring away from cities -but close major roads-in new housing communities, often accompanied by green recreational areas such as golfs.

These dynamics are putting an increasing pressure to the scarce water resources of this arid region and to its fragile ecosystems by fragmenting species habitats… We propose here an automated method for computing long time series of LULC maps, entirely hosted in GEE to quickly and easily process large amounts of data. While its performance has been clearly illustrated with the Tucson area example, this tool is adaptable to fit other regions of interest in order to provide critical and timely information on the dynamics of LULC change, with high temporal depth, to decision makers.

  Figure 1 -Google Earth Engine workflow scheme for yearly LULC classification

Figure 2 -

 2 Figure 2 -LULC change dynamics in the Upper Santa Cruz Watershed


Xavier Bultel

Cristina Onete

Pairing-free secure-channel establishment in mobile networks with fine-grained lawful interception

Keywords: Lawful interception, roaming, mobile networks, 5G

Modern-day mobile communications allow users to connect from any place, at any time. However, this ubiquitous access comes at the expense of their privacy. Currently, the operators providing mobile service to users learn call-and SMS-metadata, and even the contents of those exchanges. A main reason behind this is the Lawful-Interception (LI) requirement, by which serving networks must provide this (meta-)data to authorities, given a warrant. At ESORICS 2021, Arfaoui et al. pioneered a primitive called Lawful-Interception Key-Exchange, which achieves the best of both worlds: (provably) privacy-enhanced communications, and finegrained fine-grained, limited access to user data. Their work had two important shortcomings. First, their protocol required pairings which, while sufficiently efficient, might not always be available in the mobile setting. More importantly, that scheme was only applicable in a domestic setting, where the concerned users (Alice and Bob) were subject to the same LI authorities. The case of roaming was left as an open question. In this paper we answer that open question. We extend the framework of Arfaoui et al. to allow Alice and Bob (now subject to potentially two sets of authorities) to establish a secure channel that guarantees the strong properties afforded by the LIKE schemes of ESORICS 2021. Our construction is pairing-free, faster than that of Arfaoui et al., and its security relies on standard assumptions.

Introduction

End-to-end secure communication is one of cryptography's most fundamental and researched topics. In short, secure-channel establishment allows peers Alice and Bob to exchange messages over an open line, such that: no one but themselves can learn anything about the contents of those messages (confidentiality); they can verify the authorship of those messages (authenticity); even if their long-term secrets leak, past communications remain confidential and authentic (perfect forward secrecy -PFS). In the wake of Edward Snowden's revelations of mass surveillance on civilian conversations, these properties are particularly important.

People's awareness of and desire for the privacy of their communications (leading, e.g., to the adoption of applications advertizing privacy, like WhatsApp or Viber) is now stronger than ever. Commendable regulations, such as the EU's General Data Protection Regulation (GDPR3 ) or the new electronic privacy regulation (ePR 4 ) have revolutionized today's Web-browsing by limiting the personal data collected by clients and giving users the right to remove information which may harm them.

Yet, at the opposite end, law-enforcement agencies and governments have, for years, been pushing for less privacy in communications. We are often told this is in the name of (inter-)national security, preventing horrific crimes, such as child abuse, terrorism, or organ trafficking. Thus, while law-enforcement agencies advocate for privacy in communications, they also want "back doors": ways to exceptionally access data in order to prevent crime.

A recent, iconic case is that of FBI versus Apple5 , in which the FBI demanded a back door allowing them access to locked Apple phones. Apple refused, explaining that such back doors were unconstitutional, and that the resulting unrestrained access would set a dangerous precedent.

Yet, even staunch defenders of privacy like Abelson et al. [START_REF] Abelson | Keys under doormats[END_REF] agree that limited, well-regulated access to data may be useful and acceptable (when e.g., used to prevent the heinous crimes cited above). Whereas universal back doors do not discriminate between subpoenaed and un-subpoenaed sensitive information, fine-grained, exceptional access to data can be viewed as constructive.

The generic notion of key-escrow captures just such a fine-grained back door that targets a (set of) key(s). Despite extensive research, key-escrow has many limitations, due mostly to its wide-ranging application scenarios. For instance, it may be hard to "oblige" Alice and Bob to use a particular channel (with escrowed keys); moreover, many key-escrow protocols require parties that recover keys (the authorities) to be always online.

At ESORICS 2021 Arfaoui et al. introduced Lawful Interception Key-Exchange protocols (LIKE) as a way to provide punctual exceptional access to mobile conversations between users, while preserving the privacy of all users and conversations not targeted by a subpoena [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF]. This scenario, which naturally obliges Alice and Bob to converse over a specific channel via their serving networks, also comes with enforced security properties (non-frameability and honest operator) and does not require the authorities to be online.

The LIKE protocol of [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF] can work with multiple service providers, but not multiple sets of authorities. In other words, in contrast to LI requirements during roaming, the scheme of [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF] cannot guarantee LI access in both Alice's country and Bob's country. This limits the use of that protocol to domestic communications (featuring only one set of authorities) or to roaming scenarios for which one country agrees to forego its right of LI in favour of another country. As a second disadvantage, the protocol of [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF] requires pairings, which require specialized implementation libraries which might not always be readily available.

In this paper, we extend LIKE protocols to capture both domestic and roaming communications. Although this opens exceptional access from one to two sets of authorities, we note that this is a legal requirement of international communications. Our protocol, which is pairing-free and very fast, maximizes privacy within the bounds of the law, guaranteeing the same, strong properties pioneered by [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF], but with respect to two independent set of authorities.

The LIKE setup. Precisely defined by law and 3GPP standards, Lawful interception (LI) is the process by which exceptional access is given to a set of authorities, in possession of a warrant, to mobile data or metadata pertaining to a user.

In current architectures, when two mobile-users Alice and Bob decide to communicate, the data they share is forwarded by the operators serving the users. This allows operators to answer LI queries for (meta-)data of users, when queried by an accepted set of authorities. Unfortunately, the operators learn much more than just the data they forward, and are given access to enormous amounts of potentiallysensitive data. This damages user privacy and makes operators a target to entities wanting access to that data.

Arfaoui et al. present in [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF] a pairing-based alternative to this approach, in which Alice and Bob establish an end-to-end-secure channel that denies operators access to their data. Exceptional LI access is guaranteed by bilinearity, since Alice and Bob "embed" the product of a number of authority keys into the session key. During LI, each authority generates a trapdoor to the session key; by then using bilinearity and the set of all the trapdoors, the authorities recover the key.

A clear downside of the protocol is Alice and Bob must embed the same set of authorities into the session key, or compute distinct session keys. Thus, [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF] leaves LI in the presence of two sets of authorities as an open question.

Our protocol. We consider a LIKE setup in which Alice, currently in country A, is receiving mobile service from operator O A . Bob is in country B, receiving mobile service from another operator O B . When Alice and Bob communicate over the mobile network, O A and O B forward their data, but (as in [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF]) in encrypted form. Unlike [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF], we consider that Alice's communication will be subject to a set of authorities in country A, while Bob's may be opened by a different set of authorities, in country B.

In our protocol, users Alice and Bob (essentially) use signed Diffie-Hellman to establish their secure channel. The authority keys are no longer embedded in the session key; instead, the two endpoints enable LI by encrypting the session key with a function of the authority keys (akin to ElGamal encryption), providing the ciphertext and a proof of its well-formedness to the operators. The ciphertext and proof are only received and verified by the operator providing service to that endpoint. Our protocol's security relies on standard assumptions: the hardness of the Decisional Diffie-Hellman problem, the unforgeability of the signature scheme, and the security of simple proofs and signatures of knowledge. Our protocol is also fast, as we show through a proof-of-concept implementation described in Section 5.

Other related work. Though closely related to [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF], our work makes important original contributions: we extend LIKE to handle two different sets of authorities (an open question in [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF]), and provide a provably-secure, pairing-free construction achieving it.

We provide stronger guarantees than typical key-escrow [START_REF]Clipper chip[END_REF][START_REF] Denning | A taxonomy for key escrow encryption systems[END_REF][START_REF] Azfar | Implementation and Performance of Threshold Cryptography for Multiple Escrow Agents in VoIP[END_REF][START_REF] Wang | Key escrow protocol based on a tripartite authenticated key agreement and threshold cryptography[END_REF][START_REF] Shamir | Partial key escrow: A new approach to software key escrow[END_REF][START_REF] Bellare | Verifiable Partial Key Escrow[END_REF][START_REF] Chen | Key escrow in mutually mistrusting domains[END_REF][START_REF] Martin | Increasing Efficiency of International Key Escrow in Mutually Mistrusting Domains[END_REF][START_REF] Long | A dynamic threshold commercial key escrow scheme based on conic[END_REF][START_REF] Long | Adaptive Chosen Ciphertext Secure Threshold Key Escrow Scheme from Pairing[END_REF][START_REF] Fan | Key Escrow Scheme with the Cooperation Mechanism of Multiple Escrow Agents[END_REF][START_REF] Micali | Fair Public-Key Cryptosystems[END_REF][START_REF] Shamir | Identity-Based Cryptosystems and Signature Schemes[END_REF][START_REF] Ni | Escrowable identity-based authenticated key agreement protocol with strong security[END_REF][START_REF] Chen | Escrowable identity-based authenticated key agreement in the standard model[END_REF]. First, our chosen use-case (mobile communications) obliges participants to communicate via two serving networks which can now vouchsafe for Alice's and Bob's protocol-compliance. Moreover, our protocol can handle two independent sets of authorities simultaneously, one performing LI on Alice's end, and the other, on Bob's. Finally we guarantee Arfaoui et al.'s strong properties: fine-grained, sessionbased LI access; no central key-generation authority; no trust required in authorities; and finally, we do not require those authorities to be online except at LI opening.

A parallel line of research to ours [START_REF] Bellare | Translucent Cryptography -An Alternative to Key Escrow, and Its Implementation via Fractional Oblivious Transfer[END_REF][START_REF] Wright | Crypto crumple zones: Enabling limited access without mass surveillance[END_REF] aims to make LI possible, but computationally very expensive. Unfortunately, that approach contravenes the 3GPP requirement of a timely return of the subpoenaed content. This timeliness requirement affects the operator directly, creating an incentive for it to only adopt solutions that allow for speedy key-recovery.

Preliminaries

Notations. Throughout the paper, λ ∈ N will denote a security parameter. The notation x ← y signifies that a variable x is assigned a value y. We write x $ ← -A when x is sampled identically and uniformly at random from the set A, and, for an algorithm Alg, the notation y ← Alg(x) expresses the fact that, if run on input x, Alg outputs y.

Definition 1 (Decisional Diffie-Hellman (DDH) assumption). Let (G, p, g) be a prime order group. Then DDH holds when for any random tuple (x, y, z) ∈ (Z * p ) 3 , no probabilistic polynomial time (PPT) adversary can distinguish between (g x , g y , g x•y ) and (g x , g y , g z ) with non-negligible probability in |p|.

Definition 2 (Digital signatures). A digital signature scheme DS is a triplet (SGen, SSig, SVer) such that SGen takes in input 1 λ and outputs a pair (PK, SK), SSig takes in input a key SK and a message m and outputs a signature σ, and SVer takes as input a key PK, a message m, and a signature σ and outputs 1 if the signature is deemed valid, and 0 otherwise. A digital signature is existentially unforgeable against chosen message attacks (EUF-CMA) if no PPT adversary interacting with a signing oracle is able to forge a fresh and valid signature.

(Non-Interactive) Proof/Signatures of Knowledge [START_REF] Bellare | On defining proofs of knowledge[END_REF][START_REF] Chase | On signatures of knowledge[END_REF] (NIPoK and SoK) allow a prover to convince a verifier that it knows a witness to a particular statement, without revealing information about that witness. In Sok, the prover embeds the message to sign in the proof. We use the Camenisch/Stadler notation [START_REF] Camenisch | Efficient group signature schemes for large groups (extended abstract)[END_REF] to formalize both these primitives below.

Definition 3 (Signature/Proof of Knowledge). Let R be a binary relation and L be a language such that s ∈ L ⇔ (∃w, (s, w) ∈ R). A SoK for L is a pair of algorithms (SoK, SoKver) such that SoK m {w : (s, w) ∈ R} outputs a signature π and SoKver(m, s, π) outputs 1 for acceptance, 0 otherwise. The formal definition of NIPoK follows along similar lines -except NIPoKs do not require messages. In addition, a Zero-Knowledge (ZK) proof/signature of knowledge allows no additional information about the witness to leak.

LIKE protocols

Originally described by Arfaoui et al. [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF], LIKE protocols are principally meant to allow two users Alice (denoted A) and Bob (denoted B), whose mobile communication is forwarded by operators O A (providing mobile service to A) and O B (serving B), to establish a secure channel that can be exceptionally opened by some authorities.

In the original setting of [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF], at each connection Alice, Bob, and the operators must agree on the same subset of authorities. While this might be realistic for domestic mobile communications, it is not so for the case of roaming, in which Alice and her serving network are in a different country (thus affiliated to different authorities) than Bob and his serving network. In this work we extend the work of Arfaoui et al. to also cover roaming -an extension which will require small modifications to the primitive's syntax and security model.

Context and parties. Like [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF], we consider a set of user USERS, a set of operators OPS, and a set of authorities AUTH (the latter will include the set of all possible authorities, from all possible countries). Anticipating our setup, note that each protocol session will take place in the presence of two subsets of authorities, which might, or might not, have a non-void intersection.

The union USERS ∩ OPS ∩ AUTH is the set of parties. It is assumed that the user set is disjoint from the union of the other two sets: in other words, a user can never be an authority or an operator. Just like Arfaoui et al., we also assume that technically the operator and authority sets are disjoint. However, note that in reality, an operator can in fact also play a part in exceptional opening -in that case, we "split" the same moral identity into two separate ones which have knowledge of each other's keys: one entity plays the role of the operator, and the other, the role of the authority.

Protocol structure and intuition. Like [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF] we envision LIKE protocols as a sequence of steps: setup, key-generation, authenticated key-exchange, verification, and lawful interception (the latter step being made up of two algorithms). During setup, we generate some common public parameters (such as the description of a prime-order group). Then, each type of party (users, operators, and authorities) will use its own key-generation algorithm to generate credentials. These first two steps are depicted in Figure 1, and while we recall their syntax below, it is unchanged compared to [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF]. Once parameters are generated, two users and their respective serving networks engage in an authenticated key-exchange protocol (as depicted in Figure 2), requiring Alice and her serving operator to agree on one subset of authorities, while Bob and his operator must agree on a (possibly distinct) set of authorities. This is reflected in a slight modification of the syntax of our authenticated key-exchange algorithm below. During authenticated key-exchange, the two endpoints compute a session key, while the operators verify the fact that the transcript is protocol compliant, and finally each output a session state. The syntax of [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF] is permissive, allowing the two session states, corresponding to the two operator outputs in a single session, to differ. In the case of roaming (for two different sets of authorities), those states will always differ, since they include the authority public-key sets.

Each session state is publicly verifiable with respect to the validity of the transcript and the identities of both the participants that generated it, and the authorities that were considered. Once more, the syntax of [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF] can remain unchanged, although in practice we must verify the session state output by O A with respect to the authority set considered by A and her operator, while the session state output by O B is verified with respect to the authority set considered by B and his operator.

The final step is lawful interception, which consists of two algorithms. Using the session state output by one of the operators, the authorities with respect to which that session state was established will first generate some trapdoors. Using all the trapdoors in input, the opening algorithm will then yield the session key established by Alice and Bob (as depicted in Figure 3).

Notations. In both the formalization below and the model, we use dot notations to separate specific attributes of a party from the party owning it. For instance A.PK denotes Alice's public key, and Λ i .SK is the secret key of the i-th authority. The two operators are denoted O A and O B because they provide service to Alice and Bob respectively 6 . Parties A and O A agree to run the protocol in the presence of a subset of n A authorities, while parties B and O agree to run it in the presence of a possibly different subset of n B authorities. We note that the choice of authorities is thus limited to one of the two sides of the protocol.

Extending the LIKE definition. The only extension we make to the already-existing LIKE syntax of [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF] is to provide for two sets of authorities in the AKE protocol. The new formal syntax of this algorithm is as follows:

-AKE A(A.SK), O A (O A .SK), O B (O B .SK), B(B.SK) (PK A→B ) → (k A , sst A , sst B , k B ): An authenticated key- exchange protocol between users (A, B) ∈ USERS 2 and operators (O A , O B ) ∈ OPS 2 .
The parties each take as input a secret key, and have access to the same set of public values PK A→B containing: parameters pp, public keys (A.PK, B.PK), and two distinct vectors of authority public keys

(APK A , APK B ) = ((Λ A i .PK) n i=1 , (Λ B i .PK) m i=1 ) with Λ A i ∈ AUTH for all i ∈ 1, n and Λ B i ∈
AUTH for all i ∈ 1, m . Note that we place no restrictions on whether or not the same public key exists in both vectors. We also note that, while the syntax seems to require Alice to know the keys of the authorities on Bob's side, this is not really necessary for our protocol (Alice will never need those). In that sense, the use of a universal set PK A→B is only for convenience and legibility. At the end of the protocol, A (resp. B) returns a session secret key k A (resp. k B ) and the operator O A (resp. O B ) returns a (public) session state sst A (resp. sst B ). In case of failure, the parties output a special symbol ⊥ instead.

We make no modification to the remaining algorithms in the original framework of Arfaoui et al. [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF]. However, for completeness, we recall them here.

-Setup(1 λ ) → pp: Generates public system parameters pp.

-UKeyGen(pp) → (U.PK, U.SK): Used by mobile users to generate a public/private user key pair.

-OKeyGen(pp) → (O.PK, O.SK): Used by operators to generate a public/private operator key pair.

-AKeyGen(pp) → (Λ.PK, Λ.SK): Used by authorities (irrespective of country) to generate a public/private authority key pair. Note that, although we place no restrictions on the subsets of authorities used, they must use the same public system parameters (at least, the same per AKE session), regardless of their country in order to allow the protocol to work. -Verify(pp, sst, A.PK, B.PK, O.PK, APK) → b: Verifies if an input session state sst, is consistent with a session having been correctly run and authenticated by input operator O between users A and B for a set of authorities APK. If the verification succeeds the algorithm outputs 1. -TDGen(pp, Λ.SK, sst) → Λ.td: Generates a trapdoor Λ.td for a session state sst, using authority secret key Λ.SK. -Open(pp, sst, APK, T ) → k: Recovers a purported key for session with state sst, given authority public keys APK = (Λ i .PK) n i=1 and trapdoors T = (Λ i .td) n i=1 . If no key can be recovered, the output is ⊥.

Our protocol

For our scheme, we assume that both the operators and the users employ a digital signature scheme DS = (SGen, SSig, SVer) -namely, their long-term credentials will be used for signing messages. We will require two types of zero-knowledge proofs of knowledge:

-DLog: The first type of ZK NIPoK we require is a proof of knowledge of a discrete logarithm. We use this to prove that the authorities generated their long-term keys correctly; this is crucial in order to guarantee that exceptional opening occurs only when all the authorities in the session state's authority vector cooperate. We thus actively fine-grain lawful interception and prevent easy mass surveillance. -Equal exponent: The second type of ZK NIPoK we need is a proof of equality of discrete logarithms.

We use this in the trapdoor-generation algorithm, for which authorities need to prove that their trapdoors were generated using the same exponent as was used in their long-term credentials. This prevents malicious authority behaviour which might yield a different session key when opening than the key computed by Alice and Bob.

The signature of knowledge will also prove a knowledge of equal exponents, which assures the operator that Alice's and Bob's messages will allow the authorities to recover the key yielded by that protocol session. Note that in our protocol Alice's operator will check protocol compliance with respect to the set of authorities in Alice's country, and Bob's operator will check compliance with respect to the authorities in Bob's country.

In the following, we detail our protocol in terms of the syntax presented in the previous section.

Setup and Key Generation. As opposed to the protocol of Arfaoui et al. [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF], we do not require pairings. During setup we just fix the description of a group G of prime order p with some generator g. Both users and operators use the key-generation algorithm of the signature scheme in order to generate their credentials, whereas authorities generate an exponent in Z * p as their secret key, publish the public key corresponding to that exponent, and prove in zero-knowledge that the keys are well-formed.

-Setup(1 λ ): Based on λ, choose G a group of prime order p, a generator of g of G, and output pp = (λ, G, p, g). -UKeyGen(pp): Run (U.PK, U.SK) ← SGen(1 λ ) and return (U.PK, U.SK).

-OKeyGen(pp): Run (O.PK, O.SK) ← SGen(1 λ ) and return (O.PK, O.SK).

-AKeyGen(pp):

Pick Λ.SK $ ← -Z * p , compute Λ.pk ← g Λ.SK and Λ.ni ← NIPoK Λ.SK : Λ.pk = g Λ.SK , set Λ.PK ← (Λ.pk, Λ.ni). Return (Λ.PK, Λ.SK).
Authenticated key-exchange. The protocol AKE is instantiated as described in Figure 4.

This protocol presents a crucial difference in the key-computation compared to [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF]. Beyond being pairing-free, our scheme no longer embeds the authorities into the session key, thus allowing two distinct sets of authorities to open it.

As described in Figure 4, we require everyone to be sure, when using a particular authority public key, that it was generated according to protocol. This is why we have a precomputation phase in which the users and operators check the public keys of the authorities they are about to use. However, we note that this precomputation phase can be reused across sessions: once verified, a public key need never be verified again.

During the same precomputation phase, A and O A multiply the public keys of the involved authorities, thus obtaining an auxiliary value h A (and respectively h B ).

Our protocol relies on signed Diffie-Hellman, with the key being X y = Y x = g xy , within the group G. However, we also embed some elements into the protocol, which will later enable authorities on both sides to recover trapdoors to the AKE session. These additional elements are only exchanged between the user and its serving network; once they are verified, they are added by the operator to the session state, but not forwarded to the other operator. This is why the transcript of the protocol between O A and O B is that of the signed Diffie-Hellman protocol, while the one between A and O A (and B and O B respectively) contains additional elements.

In order to allow the authorities in APK A to recover the key, user A "encrypts" the session key (Y x ) with h x A , obtaining a ciphertext H A . Looking ahead, in order to "neutralize" h A and recover the key we require the contributions of all the parties whose public keys are in h A . Bob will do the same on his side, but for the authorities in APK B and respectively for h B ; the ciphertext obtained is H B .

Note that successful session opening depends on the well-formedness of the ciphertexts H A and H B . In order to prevent the users from cheating, we require them to provide a signature of knowledge on a message consisting of the identities of Alice, Bob, and the authorities, proving in zero-knowledge that they have used the same exponent in computing their H value and for their Diffie-Hellman key-share.

B i .pk, Λ B i .ni) m i=1 ; check all Λ A i .ni; ωA ← A B (Λ A i ) n i=1 ; hA ← n i=1 Λ A i .pk; check all Λ B i .ni; ωB ← A B (Λ B i ) m i=1 ; hB ← m i=1
Λ B i .pk; AKE session (reusing the authority data above) Notice that at no point in the execution of the protocol does Alice need to know the identities or public keys of Bob's authorities, nor vice-versa. This is a crucial feature of the protocol, which is essential in real life, since often the authorities in one country do not (and sometimes should not) know the identities of the relevant LI authorities in another country.

x $ ← -Z * p ; X ← g x ; X ------→ X ------→ X ------→ y $ ← -Z * p ; Y ← g y ; HB ← (hB • X) y ; sB ← (Y = g y ∧ HB = (hB • X) y ); niB ← SoKω B {y : sB}; Verify σ 1 B ; Y,σ 1 B ← ------ Verify σ 1 B ; Y,σ 1 B ← ------ Verify σ 1 B , niB; Y,σ 1 B ,H B ,ni B ←-------- σ 1 B ← SSig(B.SK, A B X Y ); HA ← (hA • Y ) x ; sA ← (X = g x ∧ HA = (hA • Y ) x ); niA ← SoKω A {x : sA}; τA ← X Y σ 1 B σA ← SSig(A.SK, A B τA); σ A ,H A ,ni A -------→ Verify σA, niA; σ A ------→ Verify σA; σ A ------→ Verify σA; Verify σ 2 B ; σ 2 B ← ------ Verify σ 2 B , niB; σ 2 B ← ------ Let τB ← X Y σ 1 B σA; DH ← (X Y ); DH ← (X Y ); σ 2 B ← SSig(B.SK, A B τB); SIG ← σ 1 B σA σ 2 B ; SIG ← σ 1 B σA
Verification. We note that verification is unilateral, in the sense that either we verify the session state on Alice's side of the conversation with respect to the identities of the participants and the authorities on her side, or we do the same on Bob's side, with respect to the authorities and session state on his side.

-Verify(pp, sst, A.PK, B.PK, O.PK, APK) → b: Parse APK as a set (Λ i .PK) n i=1 and parse each Λ i .PK as

(Λ i .pk, Λ i .ni), set ω ← A B (Λ i ) n i=1 and h ← n i=1 Λ i .pk. Parse sst as d ω X Y σ 1 B σ A σ 2 B H ni σ O and set Z 0 = X and Z 1 = Y . If σ A , σ 1 B , σ 2 B
, and σ O are valid signatures, ni and Λ i .ni for all i ∈ 1, n are valid signatures/proofs of knowledge, and ω = ω , then the algorithm returns 1, else it returns 0.

Lawful interception. Lawful interception consists of two stages. First, in an individual effort, each authority computes a trapdoor to the session key. Then, during opening, the trapdoors must be combined to retrieve the session key from the ciphertext provided by the endpoint users (either H A or H B , as the case may be).

For Alice's side, each authority computes as a first element of the trapdoor the group element X Λ.SK (where X is Alice's key-exchange element). The second element of the trapdoor is a proof of wellformedness from the part of the authority, namely demonstrating that the same private key was used to compute both the authority's long-term public key and the authority's first trapdoor element. The same is true for Bob, except that the authorities will compute Y Λ.SK .

The opening procedure begins with a verification of both the validity of the session state with respect to the expected participants and authorities, and soundness of the handshake, and a verification of the well-formedness of all the trapdoors used in input to the opening algorithm. On Alice's side, the session key is obtained from the ciphertext H A , by dividing it by the product of the trapdoors obtained by all the authorities agreed upon by Alice and O A . On Bob's side, the procedure is identical, using H B and the authorities on Bob's side.

-TDGen(pp, Λ.SK, sst):

Parse sst as (d ω X Y σ 1 B σ A σ 2 B H ni σ O ) and set Z 0 ← X, Z 1 ← Y , Λ.td 1 ← Z Λ.SK d , Λ.td 2 ← NIPoK Λ.SK : Λ.PK = g Λ.SK ∧ Λ.td 1 = Z Λ.SK
Λ i .td) n i=1 , sst as d ω X Y σ 1 B σ A σ 2 B H ni σ O , set Z 0 = X and Z 1 = Y , parse APK as (Λ i .pk) n i=1
, parse each Λ i .PK as (Λ i .pk, Λ i .ni), each Λ i .td as (Λ i .td 1 , Λ i .td 2 ) and verify that NIPoKver((g, Λ i .pk, Z d , Λ i .td 1 ), Λ i .td 2 ) = 1; if any verification fails, the Open algorithm returns ⊥. Compute and return k ←

The flexibility of our approach. We return here to some of the desirable features of LIKE schemes that we mentioned in Section 1. We have already discussed one of them: the complete independence of the LI processes on either side of the communication: Alice and her operator need know nothing about the lawful-interception process (including the names or public keys of the authorities) on Bob's side of the communication. There is also no cardinality requirement on the sizes of the two authority subsets: in other words, Alice's communication might be subject to more authorities than Bob's. We also note that Alice and her operator are never involved by the authorities on Bob's side, should Bob's side of the communication be subject to LI requirements (nor vice-versa). These properties are all novel to our scheme, making it much more useful (and realistic) in practice than previous work.

Our scheme also benefits from the flexibility of Arfaoui et al.'s protocol. The separation of the party set into disjoint sets (authorities, operators, and users) is not as restrictive as it appears. This separation is more about cryptographic data and ownership of keys. Thus, if in a given country an operator is, in fact, an authority, then two sets of keys are generated, and the operator uses its operator keys while functioning as an operator, and its authority keys for LI queries. If only some of the authorities need to recover the secret, then those authorities can create a secure channel and use that to publish their trapdoors (while the remaining authorities, who need not recover the secret, can just publish it outside that secure channel).

Implementation results

We implement a prototype of our protocol and the protocol of Arfaoui et al. [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF] using the Charm-Crypto framework [START_REF] Akinyele | Charm: A framework for rapidly prototyping cryptosystems[END_REF]; our code is available at [START_REF]Anonymized for submission[END_REF]. Since [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF] requires pairings, we need to use a pairing-friendly curve for the initial comparison -in our case, MNT159 with 159-bit base field from the PBC library, which ensures a security level of 80 bits and has fairly-fast pairing computations. However, our protocol does not, in fact, require pairings; thus, we can also run our protocol using the NIST/X9.62/SECG curve over a 192 bit prime field prime192v -for which our protocol gains a significant performance leap. We note that by using the second curve, we gain in security, as well as efficiency.

We use Schnorr-like protocols and signatures to instantiate the zero-knowledge proofs of knowledge, the signatures of knowledge, and the signature schemes. We run our script on Ubuntu 18.04.4 LTS (64 bits) using an Intel Core i5-8365U CPU @ 1.60GHz×8 processor.

In Figure 5 we summarize our implementation results, comparing the protocol of Arfaoui et al.

[3] and our protocol. We evaluate the computation cost of the precomputation phase, the key-exchange protocol for one entity (Alice, Bob or an operator), the active phase of the key exchange protocol (where the protocol steps are executed sequentially), the verification of sst, the trapdoor generation, and the extraction of the key. The first part of the table in Fig. 5 evaluates the number of exponentiations in the prime order groups and, optionally, the number of pairing-computations, which are the most costly operations of the protocols. Note that pairings are, in general, much less efficient than exponentations.

The second part of the table in Fig. 5 evaluates the execution time of the two protocols (for n = 3 authorities) 7 . We evaluate the performance of our protocol for the same setting as for Arfaoui et al. [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF] (MNT159), and then showcase its true potential by using the more appropriate prime192v curve. The lack of pairings provides an evident advantage in the prime192v setting, but is even present on MNT159 curves: indeed, on MNT159 the pairing takes input of the type (g, h) from G 1 × G 2 , and computations are much faster in G 1 than in G 2 . For the protocol of Arfaoui et al. we are obliged to perform exponentiations in both G 1 and G 2 on MNT159; however, for our scheme we can just use G 1 and its more efficient exponentiations throughout the protocol. The difference in performance between the two protocols is therefore more significant than expected from the theoretical analysis. depend on the number of authorities (n), the number of exponentiations in a prime order group (E), and the number of pairing computations (P ). Implementation results are averaged over 100 executions, for 3 authorities, using the settings MNT159 and prime192v.

The pre-computation, verification, and key-extraction steps depend on the number of authorities. In Figure 5, we fixed those numbers (to n for the theoretical analysis and for 3 for the implementation analysis). In Figure 6, we evaluate the performance of these algorithms as a function of the number of authorities (ranging from 2 to 15), highlighting the linear complexity of these algorithms and the significantly-increased efficiency of our approach.

The graph in Figure 6 clearly shows that the Arfaoui et al. remains the least efficient one of the three (the top curve in each of the graphs). The gap between the scheme in [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF] and our protocol in the MNT159 setting shows the advantage of not using pairings (the green curve is much lower than the red curve for the verification and extraction algorithms respectively). The vertical between the two curves is much more significant in the case of verification (for which we require two pairings and several operations in G 2 in [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF]) than for extraction (one pairing only). In the case of the precomputation algorithm, neither pairings nor operations in G 2 are needed for [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF] and therefore the two curves are very close.

The prime192v setting is even more advantageous to our protocol, since the exponentiations are much faster, and in addition, we require no pairings. This is depicted in Figure 6, in the bottom curve (the blue one), which not only starts out being faster, but shows a much less-steep linear progression as n increases. Arfaoui et. al.

Our protocol using prime192v1

Our protocol using MNT159 Fig. 6. Average execution time (in milliseconds, for 100 executions) of the precomputation (left), verification (middle), and extraction (right) algorithms respectively, as a function of the number of authorities. For each algorithm, we plot the graph for Arfaoui et al. [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF] in the MNT159 setting (red) and for our protocol using the settings MNT159 (green) and prime192v (blue).

To conclude, our evaluation shows that our protocol not only improves the functionality of LIKE protocols to allow them to function in two distinct countries, but also substantially improves its effectiveness in both theory and practice.

Security Analysis

Our protocol guarantees the following properties, formalized by Arfaoui et al. for domestic mobile communications [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF]:

-Key-Security (KS): The key computed by Alice and Bob is indistinguishable from random to anyone but Alice and Bob, as long as at least one of the authorities on Alice's side, and one of the authorities on Bob's side of the communication disagree with Lawful Interception. -Non-Frameability (NF): If a user has not taken part in a particular protocol session, no one can accuse that user of having done so. -Honest Operator (HO): If an operator has allowed a protocol session to run to completion, it is guaranteed that the key retrieved by lawful interception by the authorities used by the operator will yield the key extracted from Alice's and Bob's session state, i.e., the key Alice and Bob themselves should have computed.

The notions our protocol achieve are slightly different than those guaranteed by the scheme of Arfaoui et al., since we need to adapt the definitions to having two sets of authorities. We try to keep the modifications at a minimum. Due to page limitations, we leave the precise formalization, our proof of completeness, and our security proofs to a full version of our paper, published anonymously at [START_REF]Anonymized for submission[END_REF].

Conclusion and future work

In this paper, we described a provably-secure, pairing-free protocol that allows Alice and Bob to communicate securely over a mobile network, without either of their serving networks learning the contents of their exchanges. In accordance with mobile standards, we allow limited, fine-grained exceptional access to the data to a group of authorities.

The main contribution of our work is that it can provide those strong properties even in the case of roaming, when Alice's communication is susceptible to being opened by a different set of authorities than Bob's. A second virtue of our scheme is that it is pairing-free, much more efficient and scalable in the number of authorities compared to prior work, and its security relies on standard assumptions.

An interesting avenue for future work is investigating how this protocol could compose with current protocols used in mobile network (such as AKA).

A Preliminaries

A.1 Notations

Let λ ∈ N be a security parameter. We denote by x ← y the fact that a variable x is assigned a value y. We write x $ ← -A to indicate that x is sampled identically and uniformly at random from the set A, and, for an algorithm Alg, the notation y ← Alg(x) expresses the fact that, if run on input x, Alg outputs y.

Many of our algorithms are probabilistic polynomial time in the (implicit) security parameter λ, a fact we denote by "PPT".

Our LIKE construction in Section 4 will require the use of digital signatures, and proofs and signatures of knowledge. Its security relies mainly on the hardness of the Decisional Diffie-Hellman problem (DDH). We review the DDH assumption and our building blocks in this section.

A.2 Assumptions and building blocks

Definition 4 (Decisional Diffie-Hellman problem). Let (G, p, g) be a prime order group. Then the decisional Diffie-Hellman problem is hard if, for all PPT adversaries A, Adv DDH A (λ) is negligible in λ:

Adv DDH A (λ) = Pr (x, y) $ ← -(Z * p ) 2 ; b ← A(g x , g y , g x•y ) : b = 1 -Pr (x, y, z) $ ← -(Z * p ) 3 ; b ← A(g x , g y , g z ); : b = 1 .
We denote by Adv DDH (λ) the maximum advantage a PPT adversary can have to solve this problem (note that if DDH is hard, then Adv DDH (λ) will be negligible as a function of the security parameter).

Definition 5 (Digital signatures). A digital signature scheme DS is a triplet of algorithms (SGen, SSig, SVer). The randomized key-generation SGen takes in input 1 λ and outputs a public/secret key pair (PK, SK). On input SK and a message m, the randomized signing algorithm SSig outputs a signature σ.

The deterministic verification algorithm SVer takes as input the public key PK, the message m, and the signature σ, outputting 1 if the signature is deemed valid, and 0 otherwise. For all (SK, PK) ← SGen and m, we assume that 1 ← SVer(PK, m, SSig(SK, m)) (the signature scheme has perfect correctness).

Let DS = (SGen, SSig, SVer) be a digital signature scheme. Let Sig be an oracle which, given in input the message m, internally runs SSig(SK, m) to output a valid signature for m. The Existential Unforgeability against Chosen Message Attacks property is defined by means of the following experiment, where A is a PPT adversary with access to Sig:

Exp EUF-CMA DS (A): (PK, SK) ← SGen(1 λ ) (m, σ) ← A Sig(•) (PK) Return 1 if (m, σ) not output by Sig(•) and SVer(PK, m, σ) = 1, 0 otherwise.

Definition 6 (EUF-CMA).

A digital signature DS is existentially unforgeable against chosen message attacks if, for all PPT adversaries, Adv EUF-CMA DS,A

(λ) is negligible in λ, Adv EUF-CMA DS,A (λ) = Pr Exp EUF-CMA DS,A (λ) = 1 .
We denote by Adv EUF-CMA DS (λ) the maximum advantage obtainable by a PPT adversary A.

Signatures of Knowledge. For our construction we require two somewhat-similar primitives: noninteractive zero-knowledge proofs of knowledge [START_REF] Bellare | On defining proofs of knowledge[END_REF], and signatures of knowledge [START_REF] Chase | On signatures of knowledge[END_REF]. The former of these allows a prover to convince a verifier that it knows a witness to a particular statement, without revealing information about that witness. Signatures of knowledge allow a signer to bind knowledge of a witness to a statement, and a message, proving that the possessor of a valid witness to a specific statement has signed a particular message m. We use the Camenisch/Stadler notation [START_REF] Camenisch | Efficient group signature schemes for large groups (extended abstract)[END_REF] to formalize both these primitives below.

We consider a setup in which R is a binary relation, and L is a language such that s ∈ L ⇔ (∃w, (s, w) ∈ R). We call s a statement, while w is called a witness. A Non-Interactive Proof of Knowledge (NIPoK) allows a prover to convince a verifier (in possession of s) that it knows a witness w such that (s, w) ∈ R. In addition, a Zero-Knowledge (ZK) proof of knowledge allows no additional information about the witness to leak. We denote by NIPoK {w : (w, s) ∈ R} a proof of knowledge of w for the statement s, given the relation R.

In signatures of knowledge, signers use their witnesses w as private keys, while statements s become public keys. When signing, the user proves its knowledge of w, using the message m as a label to sign it. Signatures of knowledge are verifiable by any party in possession of the statement s. Such a signature is strongly unforgeable because the signer requires the perfect knowledge of the secret key w.

Definition 7 (Signature of Knowledge). Let R be a binary relation and L be a language such that s ∈ L ⇔ (∃w, (s, w) ∈ R). A Signature of Knowledge for L is a pair of algorithms (SoK, SoKver) such that:

SoK m {w : (s, w) ∈ R}: outputs a signature π. SoKver(m, s, π): outputs a bit b.

A signature of knowledge has the following properties:

-Completeness: For any statement/witness pair (s, w) ∈ R and message m, SoKver(m, s, SoK m {w : (s, w) ∈ R}) = 1. -Perfect Zero Knowledge: There exists a polynomial-time algorithm Sim called the simulator, such that Sim(m, s) and SoK m {w : (s, w) ∈ R} follow the same probability distribution. -Knowledge Extractor: There exists a polynomial-time knowledge extractor Ext and a negligible function SoK such that, for any algorithm A Sim(•,•) (λ) that outputs a fresh statement/ signature/ message tuple (s, π, m) with SoKver(m, s, π) = 1, such that A has access to a simulator that forges signatures for chosen statement/message pairs, the extractor Ext A (λ) outputs w such that (s, w) ∈ R having access to A(λ) with probability at least 1 -SoK (λ).

The definition of non-interactive zero-knowledge proofs of knowledge follows along similar linesexcept NIPoKs do not require/use messages.

A.3 Security model

The execution environment. We consider an environment in which the adversary will be able to interact with honest parties via oracles. Each property is formalized in terms of a security game, played by the adversary against a challenger, which manipulates the honest parties.

Each party is associated with a tuple (SK, PK), namely its long-term private and public keys (these keys are generated, depending on the type of party, by one of the UKeyGen, OKeyGen, or AKeyGen algorithms). Each party is also associated with a corruption flag γ, which is raised if the adversary queries the corruption oracle.

The users and operators run the authenticated key-exchange protocol in sessions. At each session, each of the four parties generates a new instance of itself. We quantify instances collectively, denoting by π i P the i-th instance generated during the experiment, where P denotes the corresponding party. Each instance stores a number of attributes, basically storing important information related to the session in which it took part, namely:

sid: a session identifier, including a number of session-specific values that are hopefully unique to a session. User instances running the same session should have the same session identifier. -PID: the identifiers of all the other users (i.e., , parties in the set USERS) running the same session as the given instance. -OID: the identifiers of all the other operators running the same session as the given instance.

-AID: the identifiers of all the authorities included by that instance in the given session. Note that, unlike for the protocol of Arfaoui et al., in our scheme an instance of Alice might have a different authority partner-set than the matching instance of Bob.

α: a flag that is raised upon a successful termination of the protocol run.

k: the session key, which is an attribute specific only to users, and not to operators.

sst: the session state: a set of values included in the instance's view of the session. This is an attribute specific only to operator instances. ρ: a reveal bit, specific only to users and set to 1 if the adversary queries the Reveal oracle on the instance's session key. -b: a bit chosen uniformly at random upon the creation of the instance.

τ : the transcript of the session.

For our security games, we will need to establish a correlation between session states and instances (rather than just between session states and parties, as is done in the verification algorithm). We adopt the same approach as Arfaoui et al. and require the existence of an auxiliary function IdentifySession(sst, π), which evaluates to 1 if the given instance has run a session with state sst and 0 otherwise.

A first modification: matching conversation. We need to redefine the concept of matching instances with respect to [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF], because in our case, they no longer have the same authority partner sets.

Definition 8 (Matching instances). For any (i, j) ∈ N 2 and (A, B) ∈ USERS 2 such that A = B, we say that π i A and π j B have matching conversation if all the following conditions hold: π i A .sid = ⊥ and π i

A .sid = π j B .sid. If two instances π i A and π j B have matching conversation, we say that π i A matches π j B .

Oracles. In the security games, the adversary will be able to query some or all of the oracles below (whose formal definition appears already in [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF]).

-Register(P, role, PK) → ⊥ ∪ P.PK: Creates a new party, adding it to one of the sets USERS, OPS, or AUTH, depending on the value of role (which can be user, authority, or authority. Credentials are also created, by using the appropriate Key Generation algorithm. -NewSession(P, PID, OID, AID) → π i P : Creates a new party or operator instance, with user partner set PID, operator partner set OID, and authority partner set AID.

-Send(π i P , m)→ m : Sends a message m to instance π i P and returns m according to protocol. -Reveal(π i P )→ k: Returns the session key (resp. the session state) if the input instance is an accepting user (resp. operator) instance, and sets that instance's reveal bit to 1.

-Corrupt(P)→ P.SK: Returns a party's long-term secret key and sets that party's corruption bit to 1:

P.γ = 1. -Test(π i P ) → k: This oracle can only be queried once. If the input instance belongs to a user, then, depending on the value of that instance's test bit, this oracle returns either the real key (for π i P .b = 0) or a random key from the same domain otherwise.

-RevealTD(sst, A, B, O, (Λ i ) n i=1 , l) → Λ l .td: This oracle will reveal the trapdoor that the l-th authority in the input set of authorities would have output for a session sst if, and only if, the parameters input to this oracle verify for sst (in terms of the algorithm Verify).

Second modification: key-freshness. The notion of key-freshness is fundamental in typical Bellare-Rogaway models of secure authenticated key-exchange. It captures the limitations of the security guarantee that can be proved for the protocol, eliminating "trivial attacks", i.e., simple attacks that the adversary can use to trivially break security. Ideally, the trivial attacks describe ways in which the protocol is meant to function: for instance even in a secure AKE protocol the two endpoints must know the session key.

The LIKE scenario defined by Arfaoui et al. is meant to function in a setting where only one set of authorities can exceptionally open a session key. In our case, that definition expands to two sets of authorities (the authorities on Alice's side, and those on Bob's side).

Informally, the key-freshness conditions in [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF] state that the session key may only be compromised by: Alice, Bob, and the union of all the authorities for which the AKE session was run 8 . In other words, if Alice, Bob, and at least one authority remain honest and uncorrupted, then the session key is secure.

In our new definition, keys may only be compromised by: Alice, Bob, the union of all the authorities on Alice's side or the union of all the authorities on Bob's side. More formally, we define key-freshness as follows.

Definition 9 (Key freshness). Let π j P be the j-th instance of party P ∈ USERS and let A be a PPT adversary against LIKE. Set P ← π j P .PID. The key π j P .k is fresh if all the following conditions hold: π j P .α = 1, P.γ = 0 when π j P .α became 1, and π j P .ρ = 0. if π j P matches π k P for k ∈ N, then: π k P .α = 1, P .γ = 0 when π k P .α became 1, and π k P .ρ = 0. if no π k P matches π j P , P .γ = 0. -∃ Λ ∈ AUTH and there is no RevealTD(sst, A, B, O, (Λ i ) n i=1 , l) query made by A such that: • Λ ∈ π j P .AID, Λ.γ = 0 and Λ = Λ l ; • IdentifySession(sst, π j P ) = 1. -∃ Λ ∈ AUTH such that for all k ∈ N such that π j P matches π k P , there was no RevealTD(sst, A, B, O, (Λ i ) n i=1 , l) query made by A such that:

• Λ ∈ π k P .AID, Λ .γ = 0 and Λ = Λ l ; • IdentifySession(sst, π k P ) = 1.
The security of LIKE with roaming. Since we have modified the definition of key-freshness to account for the presence of a second set of authorities, we can elegantly reuse the definition of key-security provided by Arfaoui et al., as well as that for Non-Frameability (which we briefly recall below). Looking ahead, we slightly modify the definition of the key-extractor, which is simplified with respect to that of [START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF] and then reuse the definition of the Honest-Operator property as is.

Key-Security. In the key-security experiment, the adversary plays the game in Figure 7 (left-hand side).

It has access to all the oracles presented earlier and eventually outputs a tuple made up of an index i, a party P, and a guess bit d. The adversary wins if d is indeed the test bit associated to instance π i P (which must be an instance of P), and if that instance is fresh in the sense of the key-freshness definition. The advantage of A against Exp KS LIKE,A (λ) is defined as:

Adv KS LIKE,A (λ) := Pr Exp KS LIKE,A (λ) = 1 - 1 2
Exp KS LIKE,A (λ): We call the LIKE scheme key-secure if all PPT adversaries have at most a negligible advantage to win.

Exp NF LIKE,A (λ): Exp HO LIKE,A (λ): pp ← Setup(1 λ ); pp ← Setup(1 λ ) pp ← Setup(1 λ ); OKS ←        Register(•, •, •), Send(•, •), NewSession(•, •, •), Reveal(•), RevealTD(•, •), Corrupt(•, •), Test(•)        ; ONF ← Register(•, •, •), Send(•, •), Reveal(•), NewSession(•, •, •), RevealTD(•, •), Corrupt(•, •) ; OHO ← Register(•, •, •), NewSession(•, •, •), Send(•, •), Reveal (
Non-Frameability. In the non-frameability game, A has access to all but the testing oracle, and it eventually outputs a session-state/party tuple. The adversary wins if party P never took part in (or never completed) the session that yielded sst. This is captured by the experiment in Figure 7. We define the advantage of A as

Adv NF LIKE,A (λ) = Pr Exp NF LIKE,A (λ) = 1 .
An LIKE scheme is non-frameable if all PPT adversaries have at most a negligible advantage to win the NF game.

Honest operator. In the HO game, the adversary wants to make the lawful-interception process performed on a specific completed session somehow fail (i.e., retrieve a different key than should be recovered, or not to retrieve a key at all). The definition depends on a simulator called the extractor, whose job is to retrieve, from a session state, the key that Alice and Bob should have computed. Note that, since in this game Alice and Bob are malicious, they cannot be compelled to compute -or in fact use -the key that is yielded by our scheme; however, we can compel them to run the protocol correctly to completion. This is the main task of the operators, who have to check all the signatures, as well as the proofs of well-formedness of H A and H B provided by the endpoints.

We present here our modified key-extractor definition, which takes into account the fact that opening procedures are somewhat unilateral. In addition, we have strengthened the key-extraction requirement so that the extractor must be able to recover the session key based only on transcript equality. ; it holds that for any P ∈ {A, B} and any instance π such that π.τ = τ P , then: Pr[Extract(π, PPK) = k] = 1 Notice that our extractor is unbounded, as it must be in order to preserve key security (otherwise the extractor would allow the operator to find the session key).

A scheme is honest-operator secure if there exists an extractor that makes the adversary's advantage in the honest-operator game (right-hand side of Figure 7) negligible as a function of λ. The advantage is defined as: Adv

A.4 Security statement

The theorem below quantifies the guarantees that our new protocol provides. We give the most complicated proof (key-security) in the appendix, but, due to space restrictions, only include sketches for the other two properties. Our full proofs can be found in our full paper [START_REF]Anonymized for submission[END_REF]. Henceforth, let sid := X Y , and define IdentifySession(sst, π j P ) for party P and j ∈ N as follows: parsing sst as (b

A B (Λ i ) n i=1 X Y σ 1 B σ A σ 2 B σ O H ni)
, then IdentifySession(sst, π j P ) returns 1 iff X Y = π i P .sid, and if π j P plays the role of Alice then P = A and π j P .PID = B, else π j P .PID = A and P = B.

Theorem 1. Assuming that we instantiate our protocol with an EUF-CMA-secure signature scheme. Then our scheme:

is non-frameable. Moreover, for all PPT A, making at most q r queries to Register, Adv NF LIKE,A (λ) ≤ q r • Adv EUF-CMA DS (λ).

is honest-operator secure if, additionally, the proofs and signatures of knowledge are zero-knowledge and extractable. Moreover, for all PPT adversaries A doing at most q r queries to the oracle Register, we have: Adv HO LIKE,A (λ) ≤ q r • ≤ q r • NIPoK (λ) + SoK (λ) + Adv EUF-CMA DS (λ) .

is key-secure if in addition the proofs and signatures of knowledge are extractable and zero-knowledge, and the DDH assumption holds. Moreover, for all PPT adversaries A making at most q r (resp. q ns , q s , and q t ) queries to Register (resp. NewSession, Send, and RevealTD):

Adv KS LIKE,A (λ) ≤ q 2 s p + q ns • q 2 r • Adv EUF-CMA DS (λ) + q ns • q 2 r •

(2 • q t + q s ) • SoK (λ) +q r • NIPoK (λ) + 3 • Adv DDH (λ) .

B Correctness

Correctness of LI. Let us examine the correctness of the algorithm on one side of the conversation, say on Alice's side. The ciphertext used in the opening algorithm is

H = H A = (h A • Y ) x = h x A • (Y x
). We substitute in the value of h A , which yields H = n i=1

Λ A i .pk x • k A = n i=1 Λ A i .pk x • k A = n i=1 g Λ A i .SK x • k A .
Note that we can switch the left-hand exponents, as g Λ A i .SK•x = g x•Λ A i .SK , and thus:

H = n i=1 (g x ) Λ A i .SK • k A = n i=1 X Λ A i .SK • k A .
During Lawful Interception, each authority Λ A i generates as its first trapdoor element

Λ A i .td 1 = X Λ A i .SK
(the second element is a proof of well-formedness of that trapdoor, with respect to the authority's private key). During opening, the key is retrieved as:

kA = H A n i=1 (Λ i .td 1 ) = H A n i=1 X Λ A i .SK = n i=1 X Λ A i .SK • k A n i=1 X Λ A i .SK = k A C Security Proofs C.

Key-security

Proof. Let LIKE denotes our protocol. We show that Adv KS LIKE,A (λ) is negligible for any PPT adversary A by using the following sequence of games: Game G 0 : This game is the same as Exp KS LIKE,A (λ). Game G 1 : This game is similar to G 0 , but aborts if the Send oracle returns twice the same element as X or Y . An abort only happens if two out of the q s queried instances choose the same randomness from G (which is of size p), yielding:

|Pr [A wins G 0 ] -Pr [A wins G 1 ] | ≤ q 2 s /p.
Let π i * P * denote a tested instance. Excluding collisions for X and Y implies that π i * P * now has at most one matching instance. Indeed, suppose two or more instances matching π i * P * exist. We parse π i * P * .sid as Z 0 Z 1 where Z i (for i ∈ {0, 1}) was generated by π i * P * . By Def. 8, all instances matching π i * P * must sample the same Z 1-i ∈ G -impossible after G 1 . Game G 2 : Let P i be the i-th party instantiated by Register. Game G 2 proceeds as G 1 except that it begins by choosing (u, v, w) $ ← -1, q ns × 1, q r 2 . If A returns (i * , P * , d * ) such that, given P * ← π i * P * .PID, we have i * = u or P * = P v or P * = P w , then G 2 aborts, returning a random bit (here, the challenger guesses the tested party instance, the associated party, and its purported partnering user). The adversary increases its winning advantage by a factor equalling the probability of guessing correctly:

|Pr [A wins G 1 ] -1/2| ≤ q ns • q 2 r |Pr [A wins G 2 ] -1/2|.

Fig. 1 .

 1 Fig. 1. The Setup and Key-Generation steps, for two users, two operators, and three authorities

Fig. 2 .

 2 Fig. 2. Authenticated key-exchange. The two left parties agree on a subset of authorities (3 in this example), while the two right parties agree on a different set of two authorities. The operators compute a session state, while the parties compute a session key.

Fig. 3 .

 3 Fig. 3. Lawful interception on Alice's side of the conversation. Note that, to recover the key, all the authorities stipulated during key-exchange must generate and use their trapdoors.

Fig. 4 .

 4 Fig. 4. The authenticated key-exchange step of our protocol AKE A(A.SK), O A (O A .SK), O B (O B .SK), B(B.SK) ( PK A→B ).

d

  and Λ.td ← (Λ.td 1 , Λ.td 2 ), and returns Λ.td.-Open(pp, sst, APK, T ): Parse T as (

Fig. 5 .

 5 Fig.5. Theoretical and implementation results for our protocol vs. that of Arfaoui et al.. Theoretical results depend on the number of authorities (n), the number of exponentiations in a prime order group (E), and the number of pairing computations (P ). Implementation results are averaged over 100 executions, for 3 authorities, using the settings MNT159 and prime192v.

Fig. 7 .

 7 Fig. 7. Games for key-security (KS, left), non-frameability (NF, middle), and honest-operator (HO, right).

  HO LIKE,A (λ) = Pr (k * , π O , PPK) ← Exp HO LIKE,A (λ); k ← Extract(π O , PPK) : k = ⊥ ∧ k * = ⊥ ∧ k = k * .

  Definition 10 (Key extractor). For any LIKE, a key extractor Extract(•, •) is a deterministic unbounded algorithm such that, for any integers n and m, users A and B, operators O A and O B , and vectors of authorities (Λ A i ) n i=1 and (Λ B i ) m i=1 , any set {pp, A.PK, A.SK, B.PK, B.SK, O A .PK, O A .SK, O B .PK, O B .SK, k, sst A , sst B , APK A = (Λ A (k, sst A , sst B , k) ← AKE A(A.SK), O A (O A .SK), O B (O B .SK), B(B.SK) (pp, A.PK, B.PK, APK A , APK B ); τ A is the transcript of the execution yielding sst A from O A 's point of view; τ B is the transcript of the execution yielding sst B from O B 's point of view; PPK ← {O A .PK, O B .PK, A.PK, B.PK} ∪ {Λ A i .PK} n i=1 ∪ {Λ B i .PK} m i=1

	i .PK) n i=1 , (Λ A i .SK) n i=1 , APK B = (Λ B i .PK) m i=1 , (Λ B i .SK) m i=1 , τ A , τ B , PPK}
	generated as follows:
	pp ← Setup(λ); (A.PK, A.SK) ← UKeyGen(pp);
	(B.PK, B.SK) ← UKeyGen(pp);
	(O

A .PK, O A .SK) ← OKeyGen(pp); (O B .PK, O B .SK) ← OKeyGen(pp); ∀i ∈ 1, n , (Λ A i .PK, Λ A i .SK) ← AKeyGen(pp); ∀i ∈ 1, m , (Λ B i .PK, Λ B i .SK) ← AKeyGen(pp);

See https://gdpr-info.eu/ for the full text.

See https://eur-lex.europa.eu/legal-content/EN/TXT/?uri=CELEX\%3A52017PC0010.

See https://epic.org/amicus/crypto/apple for a summary of that debate.

Note that this does not necessarily mean that Alice and Bob subscribe to those two particular operators.

H n i=1 (Λi.td1) . Once more we draw the reader's attention to the fact that the opening procedure only requires the trapdoors of the set of authorities stipulated in the given session state. In other words, if O A outputs a session state sst A that is then used for the lawful interception steps, then the opening does not require the contribution of the authorities on Bob's side of the conversation.

We note that the protocol of[START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF] only works for a single set of authorities on both sides (Alice's a Bob's sides, respectively). In our protocol, Alice's side could be opened by a different set of authorities than Bob's side. To make the comparison fair with respect to[START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF], we fix the number of authorities for the Arfaoui et al. protocol[START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF] to 3, and assume for our protocol that either Alice's or Bob's side features 3 authorities, and that this is the side that opens the protocol.

We generalize a little here: typical AKE models also feature a key-revealing oracle, which does not necessarily map to a compromise of Alice or Bob, but just to a partial state compromise for one particular session. Key-freshness in[START_REF] Arfaoui | How to (legally) keep secrets from mobile operators[END_REF] also stipulates of course that a session is no longer fresh if the key has been revealed.

Game G 3 : Let (i * , P * , d * ) be the adversary's test session that G 2 guessed. Let P * ← π i * P * .PID. Game G 3 works as G 2 , except that, if there exists no π k P * matching π i * P * , the experiment aborts and returns a random bit. For any adversary A:

Assume to the contrary that there exists an adversary A that wins G 2 with probability A (λ) by returning a guess (i * , P * , d * ) such that, setting P * ← π i * P * .PID, no k ∈ N exists such that π i * P * and π k P * match. Game G 2 demands P * ← P w (guessed by G 2 ); key-freshness (Def. 9) requires P w to be uncorrupted and ending in an accepting state. We use A to build a PPT adversary B that breaks the EUF-CMA security of DS with non-negligible probability. B receives the verification key PK, initializes L S ← ∅, and faithfully simulates G 2 to A, except for A's following queries: Oracle Register(P, role, PK): If P = P w with P.PK = ⊥, then B sets P.PK ← PK. Oracle Send(π i P , m): There are two particular cases: P = P w and P = P * . If P = P w , then B queries its Sig(•) oracle to answer A's queries. Depending on the role of P w and the protocol step, B runs one of:

Here, if P w is the initiator, A B = P w P w .PID; else A B = P w .PID P w . The message/signature pairs are stored in L S . Since sid = X Y , the elements X and Y , and the identities P w and π i Pw .PID are parts of the message signed in σ A , σ 1 B , and σ 2 B . If P = P * , i = i * , and

B wins if it sends its challenger a message/signature pair (M, σ) ∈ L S such that SVer( PK, σ, M ) = 1 with PK = P w .PK. We first argue that A must query Send on input P = P * , i = i * , and

B such that SVer(P w .PK, σ A , M B ) = 1. Indeed, if A does not, the (honest) target instance π i * P * rejects. Now we can assume that A has queried Send either with σ A or with σ B as above. We have two cases: the submitted message/signature pair is in L S , or it is not. If the latter happens, clearly B wins. Assume that the former happens, i.e., the signature σ 2 B or σ A are in L S (generated by B's oracle). We recall that by assumption A's challenge instance has no matching instance, i.e., there exists no π j Pw such that π j Pw .sid = ⊥ or π j Pw .sid = π i * P * .sid. However, if π j Pw .sid = π i * P * .sid, then then A must have somehow completed the target session (key-freshness) and used the forged signature as input to at least one Send message (for Alice's signature or for Bob's second sig, depending on the role of P * ). This message was not created/output by B, so it can't be in the list, so B also wins.

Thus, Adv EUF-CMA DS,B

(λ) = A (λ), concluding the proof. After G 2 , G 3 , either a unique instance π r Pw exists, matching π u Pv = π i * P * or the experiment returns a random bit. Game G 4 : Game G 4 runs as G 3 except that it begins by picking r $ ← -1, q ns (a guess for the matching instance). If A returns (i * , P * , d * ) such that π i * P * and π r Pw do not match, then the experiment returns a random bit. The advantage of A on G 4 increases w.r.t. that in G 3 by a factor equalling the correct guessing probability :

Game G 5 : Game G 5 proceeds as G 4 , except that it begins by picking (l 1 , l 2 ) $ ← -1, q r 2 . If the l 1 -th or the l 2 -th party queried to the oracle Register is not authority, or if it is an authority (we will denote it

and IdentifySession(sst, π r Pw .sid) = 1, then the experiment aborts by returning a random bit. Note that π u Pv is the tested instance and π r Pw is the unique instance that matches π u Pv so, by key-freshness (Def. 9), if no index l 1 and l 2 exists such that Λ * l1 and Λ * l2 are uncorrupted, and RevealTD has never been called on the query (sst, A, B,

and IdentifySession(sst, π u Pv .sid) = 1, and RevealTD has never been called on the query (sst, A, B, (Λ i ) n i=1 , l) such that Λ l = Λ * l2 and IdentifySession(sst, π r Pw .sid) = 1, then the experiment returns a random bit. Thus, the advantage of A in G 5 is superior to that in G 4 by a factor equalling the guessing probability:

Game G 6 : Let Ext denote the knowledge extractor of the signature of knowledge. This game is the same as G 5 except that it begins by initializing L[ ] ← ∅ and:

each time the Send oracle generates a SoK ni of an element

The difference between G 5 and G 6 is the possibility of the extractor failing when it is called. Since RevealTD requires 2 calls (for the verification of sst) and Send, one at each query,

From this step, for any non-simulated SoK ni (regardless of who generated it between the challenger and the adversary) on a statement (g 1 , D 1 , g 2 , D 2 ) and a message ω, the list L stores the corresponding secret d at the index (g 1 , D Once more, the difference between the games is the possibility that Ext fails in at least one of the calls to the registration oracle, yielding:

From this step, for any authority public key Λ.PK coupled with a non-simulated PoK ni (regardless of who generated it between the challenger and the adversary), the list L stores the corresponding secret key Λ.SK at the index Λ.PK. Game G 8 : This game is the same as G 7 except that during the session between π u Pv and π r Pw , the group element H Pv is chosen at random according to the uniform distribution on G, and the proof ni Pv is simulated. We claim that:

We prove this claim by reduction. We build a distinguisher B for a DDH instance (U * , V * , W * ).

In what follows, Sim NIPoK denotes the simulator of the proofs of knowledge and Sim SoK , the simulator of the signature of knowledge. For the sake of simplicity, and since it is often clear from the context, we use the same notation to refer to the simulators of the two different NIPoK systems (DLog and exponent equality) that we use in our protocol.

It sets pp ← (λ, G, p, g) and runs A(pp). It simulates G 7 to A as in the real game except for:

-

Pv .sid) = 1 and Λ l = Λ * l1 , then B aborts and returns a random bit, like in the key-freshness definition.

• If IdentifySession(sst, π u Pv .sid) = 1 and Λ l = Λ * l1 , then B knows the secret key of Λ l . It acts as in G 7 except that it computes

. In this case, since h = h * , then L[(g, Z b , h, H, ω, ni)] is always defined.

At the end of the game, A returns a bit b * , then if b * = π u Pv .b, then B returns 1, else it returns 0. Let (u * , v * ) be an element of (Z * p ) 2 such that U * = g u * and V * = g v * . We set Λ * l1 .SK ← u * . If P v plays the role of Alice in π u Pv , then we set x * ← v * . With these notations, we have X * = g x * and Λ * l1 .pk = g Λ * l 1

.SK . If W * = g u * v * , then W * = (Λ * l1 .pk) x * and:

In this case, G 7 is perfectly simulated for A, On the other hand, if W * is a random value, then G 8 is perfectly simulated for A. If P v plays the role of Bob in π u Pv , we can show in a symmetric way that if W * = g u * v * then G 7 is perfectly simulated for A, otherwise G 8 is perfectly simulated for A. We deduce that:

-

which concludes the proof of the claim.

Game G 9 : This game is the same as G 8 except that during the session between π u Pv and π r Pw , the group element H Pw is chosen at random in the uniform distribution on G, and the proof ni Pw is simulated. We claim that:

This claim can be proven in a similar way as for G 8 . Game G 10 : This game is the same as G 9 except that the oracle Test always returns a random value. We claim that:

We prove this claim by reduction. We build a distinguisher B against a DDH challenge (X * , Y * , Z * ). It sets pp ← (λ, G, p, g) and runs A(pp). It simulates G 8 to A as in the real game except for the following special cases:

-Send(π i P , m): If P = P v and i = u, or if P = P w and i = r, then: • if P plays the role of Alice, then B proceeds as in G 7 except that it sets X ← X * .

which concludes the proof of the claim. Finally, since G 10 do not depend on π u Pv .b, we have that Pr [A wins G 9 ] = 1 2 , cncluding the proof of the theorem.

C.2 Proof sketches: NF and HO

Due to space restrictions, we only provide sketch proofs for the non-frameability and honest-operator security statements.

Non-frameability. In the NF experiment, the adversary's goal is to make the verification algorithm believe that a given user, say Alice, has taken part in a session, although this is false. In our protocol, both Alice and Bob include at least one signature in the session state, and this signature is checked by the verification algorithm. Thus, except through forgeries, the adversary cannot win.

Honest operator. For the HO proof, we first have to provide a (non-polynomial) extractor for the key. This extractor recovers the key-shares X and Y and then finds, by exhaustive search, the discrete logarithm y of Y , using it to compute X y . We then have to show that no adversary can cause authorities to recover, from a given sst that verifies and represents a completed session, a key different than that recovered by the extractor. The proof first uses the unforgeability of the operator's signature, essentially making sure that the sst was validated by an operator. Then, the security of the NIPoKs and SoKs ensure that the two endpoints, Alice and Bob, have in fact embedded the same key-shares (and the correct authority keys) in their auxiliary strings H A and H B . Once this is true, the correctness of LI guarantees the final result.