Jean-Michel Combes

Keywords: mobile services, privacy, group signature, proxy re-encryption, TEE, credential migration

Notation xi

La croissance rapide de l'utilisation des applications et services mobiles ainsi que l'aspect sensible et privé des données manipulées par ces applications, produisent une situation attrayante pour les attaquants. Un attaquant peut être un utilisateur frauduleux, une entité externe, ou bien un fournisseur de service ou d'application malveillant. Les attaques qui peuvent être effectuées par ces attaquants sont soit contre le service, soit contre Dans ce contexte, nous cherchons à étudier et améliorer les fonctions de sécurité offertes par cette nouvelle famille d'environnements mobiles. Nous avons identifié deux problèmatiques. Tout d'abord, l'architecture du TEE ainsi que celle de son écosystème ne sont pas suffisamment spécifiées: le TEE est généralement considéré comme une boîte noire et seuls les API sont définies. Deuxièmement, dans un environnement multiappareils (l'utilisateur a plusieurs appareils), l'utilisateur ne peut pas facilement et en toute sécurité migrer ses services d'un TEE à un autre. Dans cette thèse, nous montrons qu'actuellement, les protocoles de migration de TEE présentent des problématiques de confidentialité et de sécurité. Nous proposons ensuite une nouvelle architecture du Le chapitre 8 décrit un protocole de migration de TEE, sécurisé et respectant la vie privée.

Le chapitre 9 présente des conclusions, résume nos principales contributions et discute les perspectives, les défis et les futures orientations du travail de cette thèse.

Chapter 8 provides a secure and privacy-preserving TEE migration protocol.

Chapter 9 draws conclusions, summarizes our major contributions and discusses perspectives, challenges and future work directions.

A serial number of a m-ticket having k as an index

Tick k A m-ticket of index k Pr[R 1 ,..., R n :E]
The probability of the event E after the execution of events R 1 ..., R n A Adversary C Challenger A(keys, DB: oracles) An adversary who receives the keys "keys", has only read access to the databases "DB " and can query the oracles "oracles"

Introduction

(The english version is below)

Plusieurs études, telles que par exemple celles effectuées par International Data Corporation (IDC), montrent que le marché des appareils mobiles ne cesse de se développer et que le nombre d'applications téléchargées augmente de manière exponentielle. L'IDC prévoit que 1,5 milliards de smartphones seront vendus d'ici la fin de 2017 [3] et que les téléchargements d'applications atteindront 178 milliards en 2017 [4].

De même, la multiplicité des services pour les utilisateurs mobiles augmente de façon spectaculaire. Presque tout peut être fait via des applications mobiles. On peut distinguer deux types majeurs d'applications mobiles: les applications d'entreprise et les applications personnelles. Les applications d'entreprise permettent à un utilisateur d'avoir accès aux services de l'entreprise comme l'accès à des documents confidentiels de cette entreprise. Quant aux applications personnelles, elles offrent divers services quotidiens à l'utilisateur.

Parmi les applications personnelles les plus répandues, on trouve celles dédiées au divertissement. Un utilisateur peut télécharger une application mobile pour jouer à un jeu, écouter de la musique, regarder des vidéos et ainsi de suite. Il peut également utiliser une application mobile comme un moyen de communication, que ce soit en voix, vidéo ou à travers les réseaux sociaux. Outre ces applications, il existe aussi des applications bancaires. Ces dernières sont téléchargées par l'utilisateur soit pour surveiller son compte bancaire en temps réel soit pour effectuer des transactions de paiement en utilisant son smartphone. Dans ce cas, ces applications peuvent interagir avec un serveur distant et manipuler les informations bancaires de l'utilisateur, son identité ainsi que de nombreuses autres données privées comme les journaux de transactions effectuées.

Parmi les applications mobiles émergentes, on compte aussi les applications dédiées au transport. En utilisant la possibilité d'effectuer des transactions sans contact des smartphones actuels, elles permettent à l'utilisateur d'acheter et de valider un titre de transport dématérialisé, comme un carnet de billets ou un abonnement. Comme les applications bancaires, les applications de transport public manipulent des données privées de l'utilisateur telles que son identité, des attributs associés à son âge, sa situation, par exemple, un étudiant ou une personne handicapée, le type de son titre de transport etc.

l'utilisateur. Ci-après, nous détaillons les problématiques liées à chaque type d'attaques et nous donnons un aperçu de nos objectifs et nos contributions.

Les attaques contre l'utilisateur sont principalement liées aux problématiques de respect de la vie privée. Un attaquant externe peut essayer de capturer des données privées et des secrets de l'utilisateur. De même, un fournisseur de services peut essayer de traquer les utilisateurs dans leur vie quotidienne en fonction de leur utilisation du service. Par exemple, dans les transports publics, des violations contre la vie privée sont fréquemment soulevées. En 2012, le transporteur belge STIB a reçu le prix Big Brother pour sa carte sans contact (MoBIB) [5]. En effet, ce prix met en avant les entreprises et les gouvernements qui portent atteinte à la vie privée. Un autre exemple marquant illustre ce problème: certains avocats spécialisés dans le divorce ont utilisé les registres de paiement de l'E-ZPass et Fast Lane afin de poursuivre les maris de leurs clientes et prouver qu'ils ont triché sur leurs localisations à un moment et une date donnés [START_REF] Hager | Divorce Lawyers Using Fast Lane To Track Cheaters[END_REF].

Étant donné que plusieurs solutions industrielles déployées pour les infrastructures de transport public présentent d'importants problèmes liés au respect de la vie privée, les scientifiques se sont penchés sur cette question. Beaucoup de solutions cryptographiques ont été proposées afin d'assurer la protection de la vie privée, principalement pour garantir l'intraçabilité des voyages de l'utilisateur. Cependant, ces solutions ont généralement négligé les exigences fonctionnelles du service. En effet, la validation du titre de transport (billet ou abonnement électronique) doit être réalisée en moins de 300 ms [7]. Cette contrainte de temps devient difficile à respecter sur des plateformes d'implémentation très sécurisées ayant des ressources limitées à l'instar des cartes SIM.

Dans ces circonstances, nous avons choisi de construire un service de transport réaliste, respectant la vie privée, et se basant sur de nouveaux outils cryptographiques améliorés. Dans cette thèse, nous commençons par montrer les obstacles pour construire des protocoles qui respectent la vie privée. Nous étudions les travaux liés au service de transport public en normalisation, dans les solutions industrielles et dans la littérature. En particulier, nous détaillons une vulnérabilité que nous avons découverte dans le protocole de Rupp et al. qui a été publié à la conférence FC 2013 [2]. Ensuite, nous présentons l'architecture du mobile ainsi que les hypothèses de sécurité associées à chaque composant. Ensuite, nous distinguons deux cas d'usage dans le service de transport public:

(1) le cas d'usage "m-pass" (abonnement) où un utilisateur peut utiliser le système de transport d'une manière illimitée, mais pendant une période de temps donnée, et (2) le cas d'usage "m-ticketing" (billetterie) où un utilisateur a un accès limité au réseau de transport en fonction du nombre de ses m-tickets (billets électroniques sur mobile). Nous commençons par la formalisation des exigences en termes de sécurité et de respect de la vie privée du cas d'usage "m-pass", et nous définissons aussi ses exigences fonctionnelles. Plus tard, nous présentons notre solution d'abonnement intraçable, basée sur les schémas de signature de type Camenisch-Lysyanskaya, et prouvons formellement qu'elle satisfait toutes les exigences définies précédemment. Pareillement, nous formalisons les exigences en termes de sécurité et de respect de la vie privée du cas d'usage "m-ticketing", et définissons ses exigences fonctionnelles. Malgré les ressemblances que peuvent avoir les exigences du cas d'usage "m-ticketing" avec celles du cas d'usage "m-pass", elles doivent être mises en oeuvre différemment puisque le cas d'usage "m-ticketing" présente plus de contraintes: l'anonymat et l'intraçabilité des m-tickets séparément en plus de l'anonymat et l'intraçabilité du carnet des m-tickets. Ensuite, nous présentons notre solution de billetterie intraçable basée sur les schémas de signature Boneh-Boyen et les preuves d'appartenance à un ensemble. Notre protocole assure également le post-paiement. Lorsqu'on active ce mode, la vie privée de l'utilisateur ne doit pas être remise en cause. En outre, le système doit être en mesure d'empêcher, ou au moins de détecter, toute tricherie de l'utilisateur. Enfin, nous prouvons formellement que notre solution satisfait toutes les exigences définies précédemment.

TEE, organisée en différents domaines de sécurité avec des droits différents, et un nouvel écosystème avec de nouveaux rôles. Avec ce nouvel écosystème et architecture du TEE, nous présentons notre protocole de migration qui assure la confidentialité des TEEs transférés et qui est basé sur un schéma de proxy de rechiffrement. Ensuite, nous le validons à l'aide d'un outil de validation automatisé de protocoles de sécurité, AVISPA [START_REF] Armando | The avispa tool for the automated validation of internet security protocols and applications[END_REF].

Cette thèse est organisée en neuf chapitres.

Le chapitre 2 fournit une introduction aux services mobiles sans contact. Il détaille également le service de transport public et ses exigences. Ensuite, il décrit l'architecture d'un mobile actuel ainsi que ses moyens de sécurité.

Dans le chapitre 3, nous détaillons les composantes de base et les hypothèses cryptographiques que nous utiliserons dans les chapitres suivants.

Nous introduisons au chapitre 4 une nouvelle preuve d'appartenance à un ensemble.Cette preuve est plus efficace car elle ne nécessite pas de calcul de couplage côté prouveur.

Dans le chapitre 5, nous donnons plus de détails sur les travaux liés aux solutions de transport public et décrivons l'architecture du mobile qui constitue un cas d'utilisation dans la suite de la thèse.

Le chapitre 6 introduit une solution d'abonnement mobile respectant la vie privée dans le cadre du service de transport public avec son implémentation sur une carte SIM.

Le chapitre 7 introduit une solution de billetterie mobile, efficace et respectant la vie privée, pour les services de transports publics. Ce protocole utilise pleinement les résultats du chapitre 4. Nous montrons aussi comment est assuré un post-paiement sécurisé. Nous terminons ce chapitre en présentant les mesures de performance de notre implémentation sur une carte SIM.

Chapter 1

Introduction

Studies such as International Data Corporation (IDC) ones, show that the market of mobile devices is continuously increasing along with the number of downloaded applications. The IDC expects that 1.5 billion smartphones will be sold by the end of 2017 [3] and that application downloads will reach 178 billion by 2017 [4].

Likewise, the multiplicity of services for mobile users is dramatically increasing. Nearly everything can be done via mobile applications. Figure 1.1 gives a subset of mobile services and applications. There are two major types of mobile applications: corporate applications and personal ones. The corporate applications enable a user to have access to corporate services like the access to confidential documents of the company in which he works. Regarding the personal applications, it offers various daily services to the user.

Some of the most famous personal applications are for entertainment. A user can download a mobile application to play a game, listen to music, watch videos and so forth. He may also use a mobile application as a mean of communication, either voice and video or through social networks. Besides these applications, there are banking applications as well. The latters are downloaded by the user either to monitor his banking account in real-time or to perform payment transactions using his smartphone. In such a case, these applications may remotely interact with a back-end server and would handle the banking information of the user, his identity as well as many other private data like transactions logs. Other emerging applications are the transport ones. They enable the user to buy and validate, using a smartphone enabling contactless transactions, a mobile transport product, i.e., tickets or pass. Similar to banking applications, transport applications handle private user data such as his identity, attributes associated to his age, situation, e.g., a student or a disabled, the kind of his transport product and so on.

The rapid growth of the mobile applications and services use, along with the critical and private aspect of the data being handled by these applications, produce an attractive situation for attackers. An attacker can be a fraudulent user, an external entity, a malicious service or application provider. The attacks that can be performed by these attackers are either against the service or against the user. Hereafter, we detail the issues related to every type of attack as well as an overview of our objectives and contributions with respect to it.

Attacks against the user include privacy issues. An external attacker may try to capture the user's private data and secrets. Likewise, a service provider may try to track users in their daily life based on their use of the service. For instance, in public transport, privacy violations are frequently raised. In 2012, the Belgium transport operator STIB has received the Big Brother awards for its contactless card (MoBIB) [5]. Another example is the divorce lawyers who used the E-ZPass and Fast Lane toll records to track their clients husbands and prove that they were cheating about their location at a given time and date [START_REF] Hager | Divorce Lawyers Using Fast Lane To Track Cheaters[END_REF].

Given the serious privacy problems of the deployed industrial solutions for transport systems, scientists have looked into this issue. Many cryptographic solutions have been proposed in order to ensure the privacy requirements, namely the unlinkability of the user's trips. However, these solutions have usually overlooked the functional requirements of the service. In a nutshell, the validation of the transport product (mobile pass or mobile ticket) must occur in less than 300 ms [7]. However, the user's device, in particular the SIM card, is resource constrained.

In these circumstances, we chose to build a practical and privacy-preserving transport service based on new and enhanced cryptographic tools. In this thesis, we begin by showing the barriers to build privacy-preserving protocols. We study the related work to public transport service in standardization work, industrial solutions and literature.

In addition, we provide details of an attack we discovered against Rupp et al. protocol which has been published at FC 2013 [2]. Then, we present our mobile architecture and trust assumptions with respect to the mobile components. Afterwards, we distinguish two use cases of the public transport service: (1) the mobile pass use case where a user can use the transport system in a limitless way but for a given period of time, and (2) the mobile ticketing use case where a user has a limited access to the transport network according to the number of his m-tickets. We start by formalizing the security and privacy requirements of the m-pass use case, and define its functional requirements. Later, we introduce our untraceable mobile pass solution based on Camenisch-Lysyanskaya signature schemes and formally prove that it satisfies the requirements previously defined.

Similarly to the mobile pass, we formalize the security and privacy requirements of the mobile ticketing use case, and define its functional requirements. These requirements, even though they look similar to the mobile use case, must be set up differently since the mobile ticketing use case presents more constraints: the privacy of the m-tickets separately in addition to the privacy of the book of m-tickets. Then, we introduce our untraceable mobile ticketing solution based on Boneh-Boyen signature schemes and setmembership proofs. Our protocol also enables post-payment. When enabling this mode, the user's privacy must not be questioned. In addition, the system must be able to prevent, or at least detect, any user cheating. Finally, we formally prove that it satisfies the requirements previously defined.

In order to achieve our objectives regarding the untraceable mobile ticketing use case, we propose several cryptographic optimizations to the set-membership proofs. Our scheme enables a prover to prove, in a zero knowledge way, that he holds a secret belonging to a given public set without requiring pairing computations, mainly at the prover side. Indeed, in the previous constructions of set-membership proofs, the prover requires pairing computations which are costly, especially for resource constrained devices like the SIM card. This contribution is of independent interest and can be used for other purposes where such a proof is required in a resource constrained environment.

In addition to the design and formalization of the privacy-preserving transport protocols, we propose an implementation of these protocols on a SIM card and show that it satisfies the functional requirements, in particular the stringent time constraint.

Regarding the attacks against the service, they aim at introducing troubles into the service. An external attacker may try to disrupt the service or even make it unavailable. This can occur, for instance, by remotely controlling the user's device through a malware within it. Likewise, a malicious user may try to compromise the mobile application, and hence compromise the security of the service, in order to cheat. For instance in a service giving access to a transport system, he may try to change the amount of a journey or double spend the same ticket. The security issues described previously are achievable because the mobile environments, hosting the mobile applications, are vulnerable. Different types of deficiencies are frequently detected. In 2013, Kaspersky Security analysis indicates that 148.778 mobile malware were detected [START_REF] Funk | Kaspersky Security Bulletin[END_REF]. In these circumstances, a new family of mobile environments, called Trusted Execution Environments, is emerging in order to provide more protection to applications, and hence, the services they provide. A Trusted Execution Environment is defined as a secure Operating System running alongside the standard Operating System, also called Rich Execution Environment and has its own CPU and memories. The Trusted Execution Environment should host Trusted Applications like banking or transport applications that provide secure services to mobile applications running within the Rich Execution Environment.

In this context, we aim at investigating and improving the security features provided by this new family of mobile environments. We identified two issues. First, the TEE architecture and ecosystem are not finely detailed: the TEE is usually considered as a black box and only APIs are defined. Second, in a multidevice environment (the user has many devices), the user cannot easily and securely migrate his TEE services from a device to another one. In this thesis, we show that current TEE migration protocols do have privacy and security issues. We then propose a new TEE architecture organized into different security domains with different rights and define a new TEE ecosystem with new entities roles. With the new TEE ecosystem and architecture, we present our TEE migration protocol that ensures the confidentiality of the transferred TEE and is based on proxy re-encryption scheme. Next, we validate this protocol using the automated security protocol validation tool, AVISPA.

This thesis is organized into nine chapters.

Chapter 2 provides an introduction to contactless mobile services. It also details the public transport service and its requirements. Then, it describes the current mobile architecture along with its security features.

In Chapter 3, we detail the cryptographic assumptions and building blocks that we will use in the following chapters.

We introduce a new practical set-membership proof that does not require pairing computations at the prover side, as shown in Chapter 4.

In Chapter 5, we give details on works related to transport solutions and describe the mobile architecture that we will consider for our proposals.

Chapter 6 introduces a privacy-preserving mobile pass solution in the context of public transport service together with its implementation on a SIM card.

Chapter 7 introduces a practical and privacy-preserving mobile ticketing solution for public transport services. This protocol utilizes the new set-membership proof introduced in Chapter 4. We also show how to enable a secure post-payment mode. We end this chapter by presenting the performance measurements of our SIM card implementation.

Chapter Dans ce chapitre, nous nous intéressons aux services mobiles sans contact. Après avoir donné un aperçu des différents services, nous nous concentrons au domaine d'application des transports publics car ils présentent des contraintes opérationnelles fortes, particulièrement lorsque l'objectif est d'en élaborer une version sans contact. Nous détaillons les deux cas d'usage spécifiques, c'est-à-dire, l'abonnement et la billetterie électronique. Sachant que les services mobiles vont être implémentés sur des téléphones, il convient donc de comprendre l'architecture d'un téléphone afin de mieux cerner les enjeux de sécurité. Nous décrivons donc l'architecture d'un téléphone mobile. Nous détaillons, plus précisément, la technologie de communication à champ proche (Near Field Communication, NFC), les cartes SIM et les environnements d'exécution mobiles, en particulier les environnements d'exécution de confiance (Trusted Execution Environment, TEE).

Introduction

Since mobile devices are becoming widespread, service providers have adapted their services in order to maintain their consumers and attract new ones. Many services have been, and many others will be, made available via the user's mobile device. That is not all. Service providers make use of all the available mobile technologies in order to provide a better user experience, and hence attract more users. Consider, for instance, the Near Field Communication technology, it has been used in the deployment of contactless mobile services.

In this chapter, we aim to shed light on the context of contactless mobile services. We identify three areas: the contactless technology namely the Near Field Communication technology, the relevant services and the mobile devices. We begin by describing the history of the Near Field Communication technology, starting from its ancestors (contactless cards) to its beginnings, while identifying the issues that followed its expansion. Later, we give further details about the functioning of this technology and its main relevant services. As a user needs a (NFC-enabled) mobile in order to use a NFC service, we felt that it is important to study the mobile architecture and investigate the current mobile security features.

This chapter is organized as follows. In Section 2.2, we give a brief history about the Near Field Communication (NFC) technology and an overview of the contactless mobile services. In Section 2.3, we focus on the mobile public transport service: we detail its phases, entities and challenges. Finally, we describe the smartphone architecture in Section 2.4 and conclude the chapter in Section 2.5.

Contactless Mobile Services

Contactless services first appeared with transit contactless smart cards in Seoul, South Korea (1995) [START_REF](KSCC), and The Seoul Metropolitan Government. 4th Asian Transport Revenue Collection Forum[END_REF] and in Hong Kong with the Octopus card (1997) [START_REF]Octopus History[END_REF]. These cards have the size of a current banking card and contain a chip that communicates with the reader in proximity through electromagnetic induction. Then, in 2003, Gemplus introduced the first contactless card, GemCombiXplore, for mobile handsets [12]. This card has the same format as a SIM card and communicates through a RFID (Radio Frequency Identification) antenna embedded within the mobile device. GemCombiXplore has been adopted for e-purse, debit/credit, loyalty and contactless mobile payment applications for instance in public transport services. This enables users to replace the paper-based tickets with their mobile devices equipped with the GemCombiXplore card. This card is among the contactless implementations introduced before 2004 which presented a huge success. However, these implementations still present a major drawback: compliance and interoperability issues. Therefore, in 2004, NXP Semiconductors, Sony and Nokia founded the NFC Forum [START_REF] Vanderkay | Nokia, Philips And Sony Establish The Near Field Communication (NFC) Forum[END_REF], a non-profit industry association in order to ensure the interoperability between devices and services by promoting the standardization of the Near Field Communication technology (NFC for short).

The NFC is a short-range wireless technology [START_REF]NFC and Contactless Technologies[END_REF]. It can be seen as the radio-frequency identification (RFID) successor by providing a shorter range for security purposes. Indeed, NFC standards are based on existing RFID standards including ISO/IEC 14443 [START_REF]Information technology, Subcommittee SC 17 and Cards and personal identification[END_REF] and cover communications protocols and data exchange formats [START_REF]NFC Forum Technical Specifications[END_REF]. On the market, the NFC had a relatively slow start. The first NFC enabled mobile was brought to market in 2006 [START_REF] Nfc | History of Near Field Communication[END_REF]. It is the Nokia 6131. Four years later, Samsung commercialized the Samsung Nexus S, the first NFC enabled Andoid smartphone [START_REF] Nfc | History of Near Field Communication[END_REF]. Afterwards, the NFC market has dramatically increased to reach 416 million units in 2014 [START_REF]NFC-Enabled Cellphone Shipments to Soar Fourfold in Next Five Years[END_REF].

According to Information Handling Services (IHS) Technology, this trend will continue. It is estimated that, from 2013 to 2018, NFC-enabled mobiles will rise by 325 percent [START_REF]NFC-Enabled Cellphone Shipments to Soar Fourfold in Next Five Years[END_REF]. In other words, by 2018, two mobiles in three will be NFC-enabled compared to the one in four at the moment. The IHS study continues by pointing out a major challenge for the current NFC market: the development of NFC services and applications.

The main NFC services are presented in Figure 2.1. In all these services, a NFC-enabled device becomes the way to use the service: a mobile application replaces the credit card, the identity card, the professional card, the transport pass, the paper-based tickets, and so forth. We identify three main families of NFC services: mobile commerce (mcommerce), identification, and corporate services.

Corporate services include physical access control, time attendance, and secure PC logon. In these services, a user, using his NFC-enabled device, has access to corporate resources such as a building, a lab or an internal network. Indeed, at the entrance of the company building, a lab or when attempting to use the internal network of the company, the NFC-enabled device, with some credentials, would exchange with a NFC reader in order to prove the legitimacy of the user. This kind of services has two major security issues:

1. proving the legitimacy of the user: a malicious user may try to use his credentials in order to access a resource without authorization, 2. and proving that the user is the owner of the used credentials: a malicious user may try to forge credentials or use the credentials of another user. In identification services, a user may use his NFC-enabled device as an identity authentication tool. Similarly to the corporate services, the user's NFC-enabled device, with some credentials, would exchange with a NFC reader. However, in these cases unlike the corporate services, the device reader exchanges enable to authenticate the identity of the user. The security issues of the identification services have some kind of similarities with corporate services issues:

1. proving that the used identity is not spoofed: the user is the right owner of the used identity, hence the used credentials, 2. and proving that the used identity, hence the used credentials, is not tampered.

In addition, some identification use cases may bring out privacy issues especially when the service requires only a part of the user's identity.

M-Commerce services involve sale and purchase transactions using a NFC-enabled mobile device. We distinguish three main use cases: Mobile payment, Loyalty and couponing, and Public transport. In all these use cases, like the services described previously in this section, the user's NFC-enabled device, with some credentials, would exchange with a NFC reader. This latter can be within the payment equipment (the mobile payment use case), within the tradesman device (the loyalty and couponing use case) or within the turnstile located at the entrance of a public transport station (the public transport use case). Moreover, the public transport use case is more expanded than the other use cases and will continuously grow up [START_REF]Gemalto security to be free. Why the future of ticketing is mobile[END_REF]. Therefore, in this thesis, we give further attention to the public transport use cases. Hereafter, we give further details about it.

Mobile Transport Service

A public mobile transport service involves two main entities: a transport operator and a user. The user benefits from a transport service using his transport product (a mobile pass (m-pass) or a book of mobile tickets (m-tickets)). The transport operator encompasses: the transport back-end server and a validator. The transport back-end registers the users to the transport service and provides them with the necessary transport products. The validator contains a NFC reader and initiates a control with the smartphone of the user when he is traveling in the transport system, in order to check the authenticity and the validity of his transport product.

After downloading the transport application on the user's mobile device, the user performs three main phases, as described in Figure 2.2.

User registration and application setup. During this phase, a user gives a proof of his identity (e.g., a student card, an identity card or a passport) to the transport operator. If this verification succeeds, the transport operator will register the user at the transport service.

Product provisioning. A user chooses a product (e.g., a monthly transport pass or a book of 10 m-tickets) and the related personal attributes (e.g., the age of the user) in order to load the product into his smartphone. Additionally, if such a choice is possible in the transport system, the user chooses the geographical area of his product and the associated validity period. The product is then loaded onto the user's device.

Product validation. The user shows his smartphone at the entrance gate of the transport system in order to validate the product. To achieve this, the validator initiates a communication with the user's smartphone. Then, the validator checks the authenticity of the product and grants or denies access to the user. If a validation conflict occurs (two products are eligible to be validated), then the user has to be involved in selecting the adequate product. Finally, the smartphone and the validator record the event. The major security requirements for a public transport service are the correctness, the unforgeability and the non frameability. In a system which behaves correctly and in a secure manner, a user, who owns a valid transport product, should be able to access the transport network. In an unforgeable system, it should be impossible for anyone to forge fake products. In a non frameable system, no one can spoof the identity of a honest user and falsely accuse him of having used his transport product.

In addition to the security requirements, privacy requirements are also needed especially because of the privacy violations described previously in Chapter 1. Considering the privacy of a user requires that he remains anonymous in his daily use of the transport system. However, under exceptional circumstances, e.g., a fraud or a murder, it should be possible to lift his anonymity, thus providing a form of revocable anonymity. Moreover, a privacy-preserving transport system should also ensure the unlinkability of the user's actions. In particular, the transport operator might be tempted to link all the trips performed by the same user, even if these trips are "anonymous". If the different actions of a user can be linked, then there is a high risk of profiling. Some of these actions combined together might play the role of quasi-identifiers, thus leading to a potential de-anonymization of the user. For instance, existing technologies such as U-prove may fail to provide the unlinkability property if the user does not go online regularly to refresh his pseudonym [START_REF] Baldimtsi | Anonymous credentials light[END_REF]. This was further confirmed by a study of Vives-Guasch and co-authors [START_REF] Mut-Puigserver | A survey of electronic ticketing applied to transport[END_REF], which shows that most of current proposals in the literature use pseudonyms in order to achieve revocable anonymity but do not prevent the tracking of these pseudonyms. Furthermore, the transport service has a stringent functional requirement: the total transaction time of a product validation should not exceed 300 ms [7].

Previously in this section, we made abstraction of the transport product which can be a mobile pass (m-pass) or a book of mobile tickets (m-tickets). This is because whatever the product is, the entities, the phases and the major security, privacy and functional requirements are the same. However, ensuring these requirements in the case of the m-pass is completely different from the m-ticketing case. Moreover, according to the product, other requirements may arise.

In Table 2.1, we detail the differences between the m-pass and the m-ticketing use cases. The way of usage and the structure of the transport product vary between the m-pass and m-ticketing use cases. On the one hand, one m-pass can infinitely be used during a given period of time. On the other hand, a book of N m-tickets enables a user to have N trips. The granularity of the m-ticketing use case implies more privacy issues compared to the m-pass use case. Indeed, a m-ticket is identified by an index n ∈ N and a serial number. In order to ensure the same privacy level in the m-pass and m-ticketing use cases, we must ensure the anonymity of a m-ticket index in addition to the unlinkability of the m-tickets and the user's anonymity.

M-pass M-ticketing Type

Access control Access control

User's privacy Whether in the m-pass or m-ticketing use case, we assume that the user has an NFCenabled smartphone that will host the transport application. Knowing that current mobile environments are vulnerable and that an attacker or a malicious user may attempt to compromise the transport application in order to make the service unavailable or to cheat, it is important to secure the running code of the transport application. Therefore, in the following section, we investigate the current available security features that can be provided by a smartphone. We then investigate the differences between a TEE and a SIM card in order to get a feel for the implementation of our transport application in these environments

Secure Mobile Architecture

Near Field Communication

The Near Field Communication technology enables wireless interactions between devices within a range less than 4 centimeters with a maximum communication speed of 424 kbps [START_REF]NFC and Contactless Technologies[END_REF]. The NFC technology proposes three communication modes: Reader/Writer mode, Peer-to-peer mode and Card emulation mode.

Reader/Writer mode [START_REF]What It Does[END_REF] enables NFC-enabled devices to read or write information from or to inexpensive NFC tags. The NFC tag is powered by a magnetic field in order to answer the request of the mobile device. In the reader mode, the NFC tag turns back the stored data that usually consists on a URL address or a couponing service. In the writer mode, the mobile device writes data on the NFC tag. If the tag already contains any data, it will be overwritten. The NFC tags are usually embedded in smart posters and displays such as in cinemas in order to get information about a film, or in a museum to get information about a monument.

Peer-to-peer mode [START_REF]What It Does[END_REF] enables two NFC-enabled devices to communicate with each other in order to exchange information such as business cards or share files like private photos. This mode can also be used between users in order to transfer money or tickets between wallets. The two devices communicate over a bidirectional half duplex channel which enables only one device to transmit information at a given time: when one device is transmitting, the other one has to listen and can start the transmission after the first one finishes.

Card emulation [START_REF]What It Does[END_REF] mode enables NFC-enabled devices to act like a traditional contactless smart cards. A NFC-enabled device is able to embed multiple smart card applications: credit card, loyalty card, access card, transit card or tickets. This mode is advantageous for such use cases in particular for large scale deployment. Indeed, when using this technology, no renewal of the service infrastructure, such as the payment equipments, is needed. Currently supported communication interfaces for the card emulation mode are ISO/IEC 14443 Type A and Type B, and FeliCa.

Universal Integrated Circuit Card

According to ETSI TR 102 216 [START_REF][END_REF], a Universal Integrated Circuit Card (UICC) is a smart card that conforms to the specifications written and maintained by the ETSI Smart Card Platform project. This smart card is used for mobile telecommunications. GlobalPlatform specified a smartcard architecture [START_REF][END_REF] which is valid for UICC. According to the GlobalPlatform Card specification [START_REF][END_REF], a smart card is organized into isolated areas called Security Domain (SD) as presented in Figure 2.4. A security domain is defined as an on-card representative of an off-card entity that provides security services such as encryption and decryption for the applications of the off-card entity. Three types of security domains, hence three types of off-card entities, are defined by the specifications: Issuer Security Domain (ISD) which is the on-card representative of the Card Administrator, Supplementary Security Domains (SSD) which are the on-card services / applications providers such as the bank or the transport operator and Controlling Authority Security Domain (CASD) which is a Supplementary Security Domain with particular rights. CASD has a neutral role in the card and contains the card private key. It also performs operation for other Security Domains in the card. If it exists, it would enforce the security of the card and the trust relationship with off-card entities. Finally, the SIM card (UICC) is considered as a secure element that can resist high physical attacks as it could be certified Common Criteria Evaluation Assurance Level 4 Augmented (EAL4+) [START_REF]SIM Java Card Platform Protection Profile Basic and SCWS Configurations-Evolutive Certification Scheme for (U)SIM cards[END_REF]. With this certification, we are assured that a running code within a SIM card has the highest levels of protection.

In addition to the SIM card, a mobile phone encompasses another secure environment called Trusted Execution Environment. We give further details about it in the following section.

Trusted Execution Environment

A Trusted Execution Environment [START_REF] Samuel | White paper: The trusted execution environment: Delivering enhanced security at a lower cost to the mobile market[END_REF] (TEE for short) is a hardware environment with a Secure Operating System which is isolated and completely separated from the mobile platform. This new family offers a complete execution environment; more secure than the traditional mobile Operating Systems (also called Rich OS, or REE for Rich Execution Environment), with sufficient memory and storage capabilities. In other words, TEE is a separate execution environment that runs alongside the REE and provides security services to this rich environment. 4) Interfaces to communicate with tamper resistant components such as Secure Element or NFC-enabled Secure Element. The Trusted OS is not only a holder of the Trusted Applications which run on top of it but also a supporting facility provider for application developers. In order to guarantee the root of trust of the TEE, it is authenticated and then isolated from the Rich OS during the secure boot process. A Trusted Application (TA), called also Trustlet [START_REF] Samuel | White paper: The trusted execution environment: Delivering enhanced security at a lower cost to the mobile market[END_REF], is an application running inside the TEE which provides security services to Client Applications, i.e., applications running in top of the REE. A Trusted Application may be a DRM application, a payment application, a corporate application, or a transport application. Regarding the TEE APIs, we distinguish two classes: public and private. Public APIs, i.e.,TEE Client API and TEE Functional API, provide a communication interface to Client Application which enables exchanges with TEE. However, Private APIs, i.e., TEE Internal API, TEE Secure Element API (TEE SE API) and Trusted User Interface (TUI), provide communication interfaces to Trusted Applications enabling exchanges with Secure Element Applications and usage of TEE resources. Finally, the TEE is about to be certified EAL2.

Additional details about TEEs can be found in [START_REF] Arfaoui | Trusted Execution Environments: A Look under the Hood[END_REF], [START_REF] Asokan | The untapped potential of trusted execution environments on mobile devices[END_REF].

Comparison

Compared to the SIM card, the TEE is worthwhile only with respect to the memory size, hence, the computing speed. The TEE platform should provide roughly some mega bytes of memory, unlike the SIM card which cannot exceed a dozen of kilobytes. Indeed, the TEE would use the smartphone infrastructure which makes it more efficient compared to the SIM card which is a resource constrained component. Using the smartphone infrastructure can also be considered as a major drawback: the TEE cannot run when the smartphone is off or when the battery is flat. On the other hand, a NFC-enabled SIM card can run (slowly) and exchange with a NFC reader even if the smartphone is off. This is because it can be powered by the reader. Functioning in any kind of situation is important in services such as public transport: the user must be able to use his mobile ticket or pass even if he has no battery. Regarding the security level, the SIM card offers more security to the software running within it as it is a tamper-resistant secure element which can be certified EAL4+. This would enable the integrity of the running code and stored credentials. Finally, another issue of TEE remains in their implementation. TEE is an emerging environment, hence, its implementations are very unstable and the developing tools are not always available. Because the SIM card offers the highest security, can run even when the smartphone battery if off or down and presents more development easiness, we choose to implement our transport application within a NFC-enabled SIM card. We would like to emphasize that even if in the context of this phD, we did our implementations on a SIM card, the proposed protocols can be easily implemented on a TEE (if available).

Conclusion

In this chapter, we described the contactless mobile services and their main security challenges. Then, we focused on the public transport service as it is the most expanded. We detailed its main phases along with the relevant, security, privacy and functional issues. We distinguished two use cases of the public transport service: the m-pass and m-ticketing which presents more constraints that the m-pass.

In this thesis, we aim to build a secure and privacy-preserving public transport system. Regardless of the use case, the system must ensure its security and a high privacy level for users while fulfilling the stringent time constraint (transport product validation < 300 ms). The security requirements encompass the unforgeability of the transport product, the correctness and non-frameability of the system. The privacy requirements consist of the user's anonymity and the unlikability of a user's trips. We also choose to implement our protocols within a NFC-enabled SIM card. This choice is made owing to the study of the smartphone security feature in the previous section. Indeed, the SIM card enables a higher protection for its running code and is operational even if the smartphone battery is down or off (this would enable the use of the transport product even when the battery is down or off).

Our implementations also comply with a TEE platform. However, unlike the SIM card, the TEE cannot be physically moved from one smartphone to another one. In such circumstances, a new problem arises: how can the user securely migrate his credentials, if the service is implemented within a TEE and he changes his smartphone? We give a solution to this problem in Chapter 8.

In next chapter, we present the cryptographic building blocks that we will use later in our constructions in Chapters 4, 6, 7 and 8.

Chapter 3

Cryptographic Foundations and Basic Protocols Contents

Introduction

In this chapter, we first provide an introduction to some mathematical and cryptographic tools that will be used later in this thesis. Then, we announce the computational assumptions on which relies the security of our protocols. Finally, we present the basic cryptographic schemes, that we will use in our protocols in Chapter 4, Chapter 6, Chapter 7, and Chapter 8. Readers familiar with these topics may skip this chapter.

Preliminaries

In this section, we describe some algebraic tools, namely groups, fields, finite fields, elliptic curves and bilinear maps, that we will use in this thesis.

Mathematical Tools

Groups

Definition 1 (Group). A group G, * is a nonempty set G along with an operation " * " that maps G × G to G. This mapping satisfies the following properties:

• Associativity: ∀(x, y, z) ∈ G 3 , (x * y) * z = x * (y * z).
• Identity element: ∃! e ∈ G / ∀x ∈ G, x * e = e * x = x. e is called identity element of G.

• Inverse: ∀x ∈ G, ∃! y x ∈ G / x * y x = y x * x = e. y x is called inverse of x.
Moreover, * may be commutative: ∀(x, y) ∈ G 2 , x * y = y * x. In this case, the group is called abelian or commutative.

A group G is called finite if |G| is finite. |G| is called the order of G, * (or simply of G). A group is called cyclic if: ∃g ∈ G such that ∀x ∈ G, ∃n ∈ Z / x = g * g * g * ... * g * g n times
g is called a generator of G. If G is finite and has a prime order, all the elements of the group except the identity element are generators of G.

There are two possible notations: additive and multiplicative notations. The additive notation is used only if * is commutative.

In the additive notation, the symbol" * " is replaced by "+", the identity element is denoted by "0", and the inverse of an element x is denoted by -x.

In the multiplicative notation, the symbol " * " is replaced by "×" or ".", the identity element is denoted by "1", and the inverse of an element x is denoted by x -1 .

In this thesis, we consider a specific abelian group which is an elliptic curve. We give further details about this latter in Section 3.2.1.3. In order to finely define the elliptic curves, we first introduce the concepts of field, finite field and field characteristic.

Fields

Definition 2 (Field). A field K, +, . is a nonempty set K along with two operations "+" (called addition) and "." (called multiplication) that map K×K to K. This mapping satisfies the following properties:

• K, + is an abelian group of identity element denoted by "0".

• K * , . is a group of identity element denoted by "1" and where K * denotes K -{0}.

• The additive identity element "0" and the multiplicative identity element "1" are distinct (0 = 1).

• Moreover, "." may be commutative. In this case, the field is called commutative.

A field characteristic is defined as the smallest number n such that 1 + 1 + ... + 1 (n times) is equal to 0. If this sum never reaches 0, the field is said to have a characteristic equal to zero.

A field K is called finite if |K| is finite. |K| is called the order of the field.

Any finite field K, +, . satisfies the following properties:

• K is commutative.

• The multiplicative group K * , . is cyclic.

• The order of K is in the form p n , where p is the characteristic and is prime, and n is an integer 1. Conversely, for any prime integer p and any integer n 1, there exists one and only one field (up to isomorphism) such that |K| = p n . This field is denoted by F p n .

Elliptic Curves

The elliptic curves over finite fields have been introduced in cryptography by Miller in 1985 [START_REF] Victors | Use of elliptic curves in cryptography[END_REF] and by Koblitz [29] in 1987. Compared to multiplicative groups of a finite field, these curves offer the same security level with smaller elements. Moreover, the implementations based on elliptic curves require less resources which make it suitable for resource constrained environments like the SIM cards.

It is defined as follows:

Definition 3 (Elliptic curve over a finite field). Let K be a finite field. The elliptic curve E(K) over K is the set of couples (x, y) verifying the Weierstrass equation: E: y 2 + a 1 xy + a 3 y = x 3 + a 2 x 2 + a 4 x + a 6 where a 1 , a 2 , a 3 , a 4 , a 6 ∈ K, together with the "point at infinity" O.

Hence, E(K)={(x, y) ∈ K 2 , y 2 + a 1 xy + a 3 y = x 3 + a 2 x 2 + a 4 x + a 6 } ∪ {O} If K has a characteristic different from 2 or 3, the Weierstrass equation for E may be expressed in the following short form: E: y 2 = x 3 + ax + b where a, b ∈ K and 4a 3 + 27b 2 = 0.

As mentioned previously, an elliptic curve has the structure of an abelian group. Indeed, we can define a point addition law, denoted "+", and consider the point at infinity O as the identity element. We can apply the tangent and secant method to geometrically perform addition of two points on the curve.

In the sequel, we use the short form of Weierstrass equation.

Definition 4 (Addition law -tangent and secant method). For all points P and Q on the elliptic curve E(K), the addition of P and Q meets the following rules:

• -O = O • Q = -P implies that Q + P = O
• O + P = P and P + O = P

• P = (x 1 , y 1 ) = O implies that -P = (x 1 , -y 1 )
• If P, Q = O and Q = -P, the tangent and secant method enables to define the point P+Q as follows:

-If P = Q, let R be the unique third intersection point (when accounting for multiplicity) of the line containing P and Q, and E(K).

-If P = Q, let R be the second intersection point of the tangent line to the curve at this point and E(K).

then P + Q = -R, as described in Figure 3.1a and Figure 3.1b.

The addition law of (E(K), +) can be described algebraically as well as geometrically.

If K has a characteristic different from 2 or 3, the addition of the points P = (x P , y P ) and

Q = (x Q , y Q ) is denoted R = (x R , y R
) and defined as follows if we consider the short Weierstrass equation.

x R = λ 2 -x P -x Q y R = λ(x P -x R ) -y P
where λ is defined as follows:

• If P = ± Q and P , Q = O, λ = y Q -y P x Q -x P . • If P = Q and P = O, λ = 3x 2 P +a 2y P .
For further details about the elliptic curves, we refer to the book of Silverman [START_REF] Joseph | The Arithmetic of Elliptic Curves[END_REF]. This book also details bilinear maps on elliptic curves that we use in the construction of our protocols and present below.

Bilinear Maps

Early in the nineties, bilinear maps have been used as means of attacking cryptosystems [START_REF] Menezes | Reducing elliptic curve logarithms to logarithms in a finite field[END_REF][START_REF] Menezes | Reducing elliptic curve logarithms to logarithms in a finite field[END_REF]. Later in 2000, Joux [START_REF] Joux | A one round protocol for tripartite diffie-hellman[END_REF] presented the first cryptographic protocol using such maps. This protocol is a tripartite variant of the Diffie-Hellman protocol. It enables an efficient key exchange between three participants using only one exchange. Since then, new cryptographic systems appeared and are now able to provide new properties that were either unachievable or very costly.

In the following, we give the definition of a bilinear map.

Definition 5 (Bilinear map). Let p be a prime number and G 1 , G 2 and G T be multiplicative groups of order p. The map e : G 1 × G 2 → G T is said bilinear if it satisfies the following properties:

• Bilinearity: For all g 1 ∈ G 1 , g 2 ∈ G 2 and a, b ∈ Z p , e(g a 1 , g b 2 ) = e(g 1 , g 2 ) ab .
• Non-degeneration:

For g 1 = 1 G 1 and g 2 = 1 G 2 , e(g 1 , g 2 ) = 1 G T .
• Computability: e is efficiently computable. (Efficiency will be defined in Section 3.2.2.2.)

In cryptography, there are two pairings that are used for the design of bilinear maps: the Weil pairing [START_REF] Weil | Sur les fonctions algébriques de constantes finies[END_REF] introduced by André Weil in 1940 for other purposes than the cryptography and the Tate pairing [START_REF] Frey | A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves[END_REF]. This latter is twice as fast as the Weil pairing.

It is also used on more curves than the Weil pairing and even on non elliptic curves. By misuse of language, the bilinear maps based on pairings are often called pairings.

Usually, the groups are chosen as follows. G 1 is a sub-group of an elliptic curve on a finite field. G 2 is a sub-group of the multiplicative group of a finite field.

We would like to emphasize that, in this thesis, we use the pairing as a "black box". Moreover, when designing a cryptographic system using pairings, it is important to check that the used curves provide the functionalities required by this system.

Basic Functions

In this section, we start by defining the Turing machines that will be used in complexity definitions. Then, we define some basic functions that we will use later in this thesis.

Turing Machines

The Turing machines have been introduced by Turing in 1937 [START_REF] Turing | On computable numbers, with an application to the entscheidungsproblem[END_REF]. These machines can be used to simulate any computer algorithm and are formally defined as follows.

Definition 6 (Turing Machine). A Turing machine is defined by a 7-tuple (Σ, Q, σ, δ, ∆, q 0 , F) where:

• Σ is a finite and non empty set of alphabet symbols.

• Q is a finite and non empty set of states.

• σ: Q × Σ → Σ is the writing function.

• δ: Q × Σ → Q is the state changing function.

• ∆: Q × Σ → {L, R} is the transition function where L is a left shift and R is a right shift.

• q 0 ∈ is the initial state.

• F ⊂ Q is the set of final states.

On an input I, a Turing machine can have various types of complexity. In this thesis, we focus on Time Complexity, denoted by TM(I). It is commonly estimated by counting the number of Turing machine steps from the initial to the final state. In addition, it is often desirable that a Turing machine runs in polynomial time. In the subsequent section, we give further details about this complexity time class.

Basic complexity definitions

In this section, we give the definitions of polynomial time complexity, negligible function and, negligible and overwhelming probability.

A Turing machine (or an algorithm) is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size, n, of the input for the algorithm. Formally speaking, a polynomial time complexity is defined as follows:

Definition 7 (Polynomial Time Complexity). Let M be a Turing machine. We note T M (n) = sup{T M(I) , |I| = n}.

The time complexity of M is called polynomial if

∃n 0 ∈ N, ∃c ∈ N * , ∀n ≥ n 0 , T M (n) ≤ n c
In literature, polynomial time is often synonym of efficient and a problem is called hard if there is no known polynomial time algorithm to solve it.

Definition 8 (Negligible Function). A function ν :

N → R + is called negligible, if ∀c ∈ N * , ∃k c ∈ N \ ∀k k c , ν(k) < k -c
We can define the concept of negligible and overwhelming probability using the negligible functions.

Definition 9 (Negligible and Overwhelming Probability). Let P be a probability depending on a positive integer k (called security parameter). P is said negligible if it is a negligible function of k. P is said overwhelming if the probability 1-P is negligible.

One-Way Function

One way functions are a fundamental tool for cryptography. Indeed, it is a function that is easy to compute, but hard to invert. Its definition is based on negligible functions, i.e., functions that are asymptotically smaller than the inverse of any polynomial.

Definition 10 (One-way function). Let f : {0, 1} * → {0, 1} * be a function. f is called a one-way function if it satisfies the following requirements:

• There is an efficient algorithm, that when has x ∈ {0, 1} * on input, outputs f (x).

• There is no efficient algorithm that can inverse f . Formally speaking, for any efficient algorithm A and for all k sufficiently large, the probability Pr

[x ← {0, 1} k ; y ← f (x); x ← A(1 k , y) : f (x ) = f (x)] is negligible.
Among the families of the one-way functions, there are hash functions which are frequently used in cryptography. Therefore, we give further details about then in the following section.

Hash Function

Originally, hash functions were used, in computer science, for data storing. They also enable to map binary strings of arbitrary finite length to reduce any message into a particular set, e.g., an elliptic curve, a multiplicative group of a finite field... Informally speaking, a hash function is defined as follows:

H: {0, 1} * → F where F is a set such that |F | 2 k with k small enough. For instance, F can be the set {0, 1} k .

In this thesis, we use a specific kind of hash functions: cryptographically secure hash functions. These functions ensure some particular security properties.

Definition 11 (Cryptographically secure hash function). A cryptographically secure hash function H is a hash function which satisfies the following properties:

• One-way: H is a one-way function.

• Weak collision resistant: For a given m ∈ {0, 1} * , it is hard to find m = m such that H(m) = H(m ) [START_REF] Naor | Universal one-way hash functions and their cryptographic applications[END_REF]. In other words, for a given m ∈ {0, 1} * and for any efficient algorithm A, the probability P r[m ← A :

H(m) = H(m ) ∧ m = m] is negligible.
• Strong collision resistant: It is hard to find m and m ∈ {0, 1} * with m = m such that H(m) = H(m ) [START_REF] Bjerre | Collision free hash functions and public key signature schemes[END_REF]. In other words, for any efficient algorithm A, the probability P r[m, m ← A :

H(m) = H(m ) ∧ m = m] is negligible.
Another useful building block in cryptography is the pseudo-random function. We give its definition in the following section.

Pseudo-Random Function

A function is called pseudo-random if there is no efficient algorithm that can distinguish between an output of this function and a random value.

Definition 12 (Pseudo-random function family). Let m and l be two polynomial functions, k be a security parameter and R k be the set of functions: {0, 1} m(k) → {0, 1} l(k) . F k = {F s } s∈{0, 1} k is the set of functions with an index s (F k ⊆ R k ). F k is called a pseudo-random function family if it has the following properties:

• Efficiency: Consider s and x, there is an efficient algorithm that can assess F s (x)

• Pseudo-random: For any adversary A such that the number of its requests to F is polynomially limited, for all k, the probability

| P r s∈{0,1} [A(F s ) = 1] -P r R∈R k [A(R) = 1]| is negligible.

Commitment

A commitment allows a party to commit to a message m (secret) to another party. Later, the commitment can be opened by having the issuer of the commitment send additional information to the party to which he has committed to. Formally speaking, we define a commitment as follows.

Definition 13 (Commitment). A commitment scheme considers the three algorithms:

• Setup: a probabilistic algorithm that generates the parameters and keys. It takes on input an integer k and outputs the public parameters and key params. (params) ← Setup(1 k ).

• Commit: the commitment algorithm that takes on input the public parameters params, a message m and the public key of the scheme. It outputs the commitment C of the message m and the data about the decommitment r. (r, C) ← Commit(params)

• Decommit: the decommitment algorithm that takes on input a commitment C, a message m and the data r. It outputs 1, if C is a commitment of m, otherwise, it outputs 0. {0, 1} ← Decommit(C, m, r)

A commitment scheme must satisfy the following security properties:

• Hiding property : the commitment C does not reveal any information on the secret message m to the other party.

• Binding property : the commitment prevents the committing party from changing the message, that he has committed, at a later stage.

Cryptographic Primitives

In this section, we formally define the main cryptographic primitives that we will use later in this thesis. We also describe and classify the attacks that can occur against these primitives. The definitions provided in this section only refer to the so called public key cryptography. We start by the concept of public key encryption and digital signature that have been introduced by Diffie and Hellman in their paper "New directions in cryptography" [START_REF] Diffie | New directions in cryptography[END_REF]. Then, we present the proof of knowledge.

Public Key Encryption

In cryptography, the encryption enables a user A to transform a message such that only the authorized user B can read it. The key used for encryption, the public key of the user B, can be published, while the key used for decryption, the secret key of the user B, must be kept secret.

Any user can send a ciphertext to the user B provided that he knows the public key of the user B. Only the user B can retrieve the plaintext from the ciphertext.

Definition 14 (Public key encryption scheme). A public key encryption scheme is defined by three algorithms:

• Setup: a probabilistic algorithm that takes on input an integer k and outputs the public parameters params, a public key pk and its relevant private key sk.

(params, pk, sk) ← Setup(1 k )

• Enc: this algorithm is often probabilistic. It takes on input a message m ∈ {0, 1} * and a public key pk and outputs a ciphertext c. c ← Enc(params, m, pk)

• Dec: a deterministic algorithm that takes on input a ciphertext c and a private key sk and outputs the encrypted message m. m ← Dec(params, c, sk)

Any encryption scheme must satisfy the two following security properties:

• Validity: a message encrypted using a public key pk must be properly decrypted using the corresponding private key sk.

• Confidentiality: Given a ciphertext, no information can be revealed regarding the encrypted message without the knowledge of the private key.

In this thesis, we use a particular refinement of encryption called proxy re-encryption. This notion first appeared in 1998 when Blaze et al [START_REF] Blaze | Divertible Protocols and Atomic Proxy Cryptography[END_REF] introduced the notion of "atomic proxy cryptography", in which a semi-trusted proxy computes a function that converts ciphertexts for Alice (computed under Alice's public key pk A ) into ciphertexts for Bob (ciphertexts can be opened using the private key of Bob sk B ) without seeing the underlying plaintext. Later, many works such as [START_REF] Canard | Improving the Security of an Efficient Unidirectional Proxy Re-Encryption Scheme[END_REF] have been done in order to improve the security and the performance of this kind of schemes.

Definition 15 (Proxy re-encryption scheme). A proxy re-encryption scheme is defined by the following algorithms:

• Setup: a probabilistic algorithm that takes on input an integer k and outputs the public parameters params, a public key pk and its relevant private key sk.

(params, pk, sk) ← Setup(1 k )

• ReKeyGen: let D i be a set that consists of the public key pk i of the user i or the private key sk i of the user i or (pk i , sk i ). This algorithm takes on input the public parameters params, D Source • Enc: this algorithm is often probabilistic. It takes on input a message m ∈ {0, 1} * and a public key pk and outputs a ciphertext c pk for this public key. c pk ← Enc(params, m, pk)

• Re-enc: this algorithm takes on input the public parameters params, the reencryption key R A→B and the ciphertext c pk A of the user A. It outputs a ciphertext c pk B of the same message (without knowledge of the message content) for the user B or ⊥ it the ciphertext is not valid (for the re-encryption key). {c pk B , ⊥} ← Re-enc(params, R A→B , c pk A )

• Dec: a deterministic algorithm that takes on input a ciphertext c pk and a private key sk and outputs the encrypted message m or ⊥ if the ciphertext is not valid. {m, ⊥} ← Dec(params, c pk , sk)

A proxy re-encryption scheme has additional security properties which are:

• Non-transitive: The proxy, alone, cannot re-delegate decryption rights. For example, from R A→B and R B→C , he cannot produce R A→C .

• Non-transferable: The proxy and a set of colluding delegatees cannot re-delegate decryption rights. For example, from R A→B , D B , and D C , they cannot produce R A→C .

The security of an encryption scheme (or any cryptographic scheme) also depends on the attackers goals and capabilities. An attacker chooses his victim (a user) and gets the public key of this victim. If the attacker aims to retrieve the plaintext corresponding to some cirphertext, we can distinguish two types of attacks:

• Total break: given the public key of the victim, the attacker deduces the private key of the victim. He can then decrypt any ciphertext of this victim.

• Partial break: the attacker retrieves a plaintext corresponding to a given ciphertext without knowing the private key of the victim. Thus, he may not be able to decrypt other ciphertext.

Instead of retrieving the plaintext corresponding to a ciphertext, an attacker may just try to retrieve some information about the plaintext. in such a case, he would attack the following properties:

• Non-Malleability (NM): an attacker is not able to transform a ciphertext c of an unknown message m into another ciphertext c of a known message m such that m and m are bound in a certain way.

• Semantic security: given only a ciphertext, an attacker can not determine any information on the plaintext.

• Indistinguishability (IND): an attacker can not differentiate two ciphertext of two different messages.

Attacks may also be classified based on what type of information the attacker has:

• Chosen Plaintext Attack (CPA): the attacker can obtain the ciphertexts for plaintexts that are previously chosen. This is possible as the encryption key is public.

• Chosen Ciphertext Attack (CCA1): the attacker has a system that enables him to retrieve the decryption of chosen ciphertexts under an unknown key. Using these information, the attacker may try to retrieve the private key used for the decryption.

• Adaptative Chosen Ciphertext Attack (CCA2): this is an interactive form of chosen-ciphertext attack. The ciphertexts to be decrypted may change during the attack.

Usually, a scheme having the security property XX with respect to the attack YY is called XX-YY. For instance, an indistinguishable encryption scheme against the adaptative chosen ciphertext attack is IND-CCA2.

Digital Signature

Informally, a digital signature ensures the authenticity and integrity of a message. On one hand, anyone must be able to verify a signature when given the public key of the signer and the message. On the other hand, only the signer, i.e., the party that knows the secret key, must be able to compute a signature.

Definition 16 (Digital signature scheme). A digital signature scheme is defined by the following algorithms:

• Setup: a probabilistic algorithm that takes on input an integer k and outputs the public parameters params, a public key pk and its corresponding private key sk.

(params, pk, sk) ← Setup(1 k ).

• Sign: this algorithm is often probabilistic. It takes on input a message m ∈ {0, 1} * and a private key sk, and outputs a signature σ of m. σ ← Sign(param, m, sk).

• Verify: a deterministic algorithm that takes on input a signature σ, a message m and a public key pk. It outputs 1 if σ is s signature of m, otherwise it outputs 0. {0, 1} ← Verify(params, σ, m, pk)

Any type of the signature scheme must satisfy the two following security properties:

• Validity: a signature of a message using a private key sk can be verified by anyone using the corresponding public key pk.

• Integrity: the signature of a message prevents any change of the message at a later stage. Indeed, any change of the message after the signature invalidates the signature.

• Non-repudiation: a signer that has signed a message cannot at a later time deny having signed it.

In this thesis, we use a particular refinement of signature, called group signature. Using this type of signature, a member of a group can anonymously sign a message on behalf of the group. However in case of a dispute, the anonymity of a group signature can be lifted by one or several designated trusted authorities (called revocation authorities). This concept has been introduced by Chaum and van Heyst [START_REF] Chaum | Group signatures[END_REF] in 1991.

A variant of group signature, called list signature, has been introduced by Canard and his co-authors [START_REF] Canard | List signature schemes[END_REF]. With a list signature scheme, it becomes possible, when specific conditions are met, to link signatures produced by a member of the group. In particular, this link becomes possible if the signatures have been produced during a given sequence of time, i.e., a specific time period. A similar technique has later been used in [START_REF] Brickell | Direct anonymous attestation[END_REF] and is called Direct Anonymous Attestation (DAA). The main difference between DAA and list signatures is that in DAA, the role of the signer is split between a main signer with limited computational and memory capabilities, e.g., a Trusted Platform Module (TPM) or a SIM card, and an assistant signer, who is computationally more powerful but is considered less secure, e.g., a mobile phone containing the SIM card.

Definition 17 (Group signature scheme). A group signature scheme considers three type of participants:

• A group manager that registers a user to the group.

• A member of a group who firstly requires registration of the group manager. Once registered, a member of a group can sign anonymously on behalf of the group.

• A revocation authority that is able to lift the anonymity of a given signature.

A group signature scheme is a signature scheme defined by five algorithms.

• Setup: a probabilistic algorithm that takes on input an integer k and outputs the public parameters params, the group's public pk G , a group manager private key sk M G , the revocation authority's key sk RA .

(params, pk G , sk M G , sk RA ) ← Setup(1 k )

• Join: an interactive protocol between a user and a group manager. At the end of this protocol, the user becomes a member of the group and gets secret key sk U and a membership certificate to the group.

• Sign: a probabilistic algorithm that takes on input a message m, a membership certificate to a group and a secret key sk U , and outputs a signature σ of m. σ ← Sign(param, m, sk U )

• Verify: a deterministic algorithm that takes on input a message m, a signature σ and a group's public key pk G , and outputs 1 if the signature is valid, otherwise, it outputs 0. {0, 1} ← Verify(params, σ, m, pk G )

• Open: an algorithm that takes on input a message m, a valid signature σ, a group's public key pk G and the revocation authority's key sk RA , and outputs the identity of signer. ID U ← Open(m, σ, pk G , sk RA )

A group signature scheme has additional security properties which are:

• Soundness and completeness: this property is a variant of the validity property mentioned above. A signature generated by a group member can be verified by anyone using the group public key.

• Anonymity: no one, except the revocation authority, can lift the anonymity of a signature and retrieve the identity of the signer.

• Unlinkability: given two messages and their corresponding signatures, no one, except the revocation authority, can decide whether the signatures have been generated by the same user or not.

• Non-framebility: no one can falsely accuse a group member of signing a message.

• Coalition resistance: any valid signature must be linked to group member.

Like the encryption scheme, the security of a signature scheme depends on the attackers goals and capabilities. We can distinguish four types of attacks:

• Total break: like in the encryption scheme, the attacker deduces the private key from the public key of the victim.

• Universal forgery: the attacker can generate a valid signature σ of any given message m without knowledge of the private key.

• Existential forgery: the attacker can generate at least one message/signature pair (m, σ), where σ was not produced by the victim and without knowledge of the private key.

• Selective forgery: the attacker can generate a message/signature pair (m, σ) where m has been chosen by the adversary prior to the attack and without knowledge of the private key. m must be fixed before the start of the attack and may be chosen to have interesting mathematical properties with respect to the signature algorithm.

Attacks may also be classified based on what type of information the attacker has:

• Attack with no message: the attacker has only the public key of the victim.

• Known Message Attack (KMA): the attacker has the public key of the victim and a set of message/signature.

• Adaptive Chosen Message Attack (CMA): the attacker has the public key of the victim and can get the signature of any message of his choice. The messages are progressively selected.

Proofs of Knowledge

In cryptography, a proof of knowledge (POK) is an interactive proof that enables a prover to prove that he has a given data. In 1986, Fiat and Shamir proposed a heuristic method to transform a three steps protocol in a non-interactive knowledge signature [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF]. Indeed, the challenge sent by the verifier is replaced by the hash of the public parameter and a commitment. We focus on a variant called Zero-knowledge proof of knowledge.

Zero-knowledge proof of knowledge In a zero-knowledge proof, a prover convinces interactively a verifier that he knows a set of secret values (α 1 , α 2 , ..., α n ) verifying a given relation without revealing anything else. Such a proof will be denoted, in the sequel:

ZKP K((α 1 , α 2 , ..., α n ) : (α 1 , α 2 , ..., α n )).
A ZKPK should satisfy the following properties:

• Complete: a valid prover is accepted with overwhelming probability.

• Sound: a false prover should be rejected with overwhelming probability.

• Zero-knowledge: no information about the secret is revealed.

These ZKPK can be made non-interactive using the generic transformation introduced by Fiat and Shamir [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF]. The resulting non-interactive proofs, sometimes called signatures of knowledge [START_REF] Camenisch | An efficient fair payment system[END_REF]. Such a signature of knowledge, for the relation , will be denoted:

SOK((α 1 , α 2 , ..., α n ) : (α 1 , α 2 , ..., α n )).

Security

Proving the security of a cryptographic protocol is a major interest because it is a requirement to validate the protocol. In public key cryptography, proving the security of a scheme follows three steps:

• defining the security properties to be ensured.

• defining the computational assumption to be considered.

• presenting a reduction of the scheme security to a hard problem already defined in a computational assumption.

In this section, we recall the computational assumptions that we use later in this thesis and present the different models in which an adversary can be placed to conduct attacks.

Computational Assumptions

The security of our protocols, described in the next chapters, relies on the difficulty of mathematical problems resulting from the Number theory. In the following, we present the Discrete Logarithm (DL) assumption, the Decisional Diffie-Hellman (DDH) assumption, the eXternal Diffie-Hellman (XDH) assumption, the q-Strong Diffie-Hellman (q-SDH) assumption, the q-Decisional Diffie-Hellman Inversion (q-DDHI) assumption, the Decisional Composite Residuosity (DCR) assumption and the Lysyanskaya, Rivest, Sahai and Wolf (LRSW) assumption.

Discrete Logarithm (DL) Assumption

Definition 18 (Discrete Logarithm (DL) Assumption). Let G be a cyclic group of prime order q, g be a generator of G and y be an element of G, Discrete Logarithm assumption states that it is hard to find the integer x ∈ Z q such that y = g x holds. The integer x is called the discrete logarithm of y in the base g and denoted log g (y).

References for the discrete logarithm problem and the existing algorithm for solving include the survey of Odlyzko [47] and McCurley [START_REF] Mccurley | The discrete logarithm problem[END_REF].

Symmetric Discrete Logarithm (SDL) Assumption

The Symmetric Discrete Logarithm (SDL) Assumption has been formalized in [START_REF] Bichsel | Get shorty via group signatures without encryption[END_REF].

Definition 19 (Symmetric Discrete Logarithm (SDL) Assumption). Let G 1 and G 2 be two cyclic groups of prime order q, G 1 be an element of G 1 , and G 2 be an element of G 2 , Symmetric Discrete Logarithm Assumption states that it is hard to find the integer x given a tuple (G

1 , [x]G 1 , G 2 , [x]G 2 ).

One-more Discrete Logarithm (OMDL) Assumption

The One-more Discrete Logarithm (OMDL) Assumption has been introduced and formalized by Bellare, Namprempre, Pointcheval and Semanko in [START_REF] Bellare | The one-more-rsa-inversion problems and the security of chaum's blind signature scheme[END_REF].

Definition 20 (One-more Discrete Logarithm (OMDL) Assumption). Let G be a multiplicative group of prime order p, OMDL assumption states that given a random generator g ∈ G, a challenge oracle that produces a random group element Y i when queried and a discrete logarithm oracle (with respect to g), it is hard to find, after t queries to the challenge oracle (where t is chosen by the adversary) and at most t -1 queries to the discrete logarithm oracle, the discrete logarithms of all t elements Y i .

Decisional Diffie-Hellman (DDH) Assumption

The Decision Diffie-Hellman problem was first mentioned in [START_REF] Brands | An efficient off-line electronic cash system based on the representation problem[END_REF] where Stephan Brands presented a offline electronic payment system, even though there are earlier cryptographic systems that implicitly rely on the hardness of this problem (e.g. [START_REF] Chaum | Undeniable signatures[END_REF][START_REF] Chaum | Zero-knowledge undeniable signatures (extended abstract)[END_REF]).

Definition 21 (Decisional Diffie-Hellman (DDH) Assumption). Let G be a cyclic group of prime order p, DDH assumption states that given a random generator g ∈ G, two random elements g a , g b in G, and a candidate X ∈ G, it is hard to decide whether X = g ab or not.

eXternal Diffie-Hellman (XDH) Assumption

This assumption was firstly introduced by Boneh, Boyen and Shacham in the long version of [START_REF] Boneh | Short Group Signatures[END_REF] to prove the security of the presented scheme (a group signature scheme).

Definition 22 (eXternal Diffie-Hellman (XDH) Assumption). Let G 1 , G 2 and G T be three cyclic groups, and e : G 1 × G 2 → G T a bilinear map, XDH assumption states that DDH assumption holds in G 1 .

q-Strong Diffie-Hellman (q-SDH) Assumption

This assumption has been introduced by Boneh and Boyen in [START_REF] Boneh | Short Signatures Without Random Oracles[END_REF] in order to prove the security of the presented scheme (a group signature scheme).

Definition 23 (q-Strong Diffie-Hellman (q-SDH) Assumption). Let G 1 be a cyclic group, q-SDH assumption states that it is hard, given (g, g y , g y 2 ,...,g y q ) ∈ G q+1 1 , to output a pair (x, g 1/(y+x) ).

q-Strong Diffie-Hellman I (q-SDH-I) Assumption

Definition 24 (q-Strong Diffie-Hellman I (q-SDH-I) Assumption). Let G 1 be a multiplicative group of prime order p, q-SDH-I assumption states that given three random generators (g 0 , g 1 , h)∈ G 3 1 , a value W = g γ 0 , an oracle O that on input a value s ∈ Z p outputs a pair (r, A = (g s 1 h) 1/(γ+r) ) with r ∈ Z p , it is hard to output a new triplet (r , s , A = (g s 1 h) 1/(γ+r ) ), with (r , s ) ∈ Z 2 p such that s has never been queried to O.

3.3.1.8 q-Decisional Diffie-Hellman Inversion (q-DDHI) Assumption Definition 25 (q-Decisional Diffie-Hellman Inversion (q-DDHI) Assumption).

Let G be a multiplicative group of prime order p, q-DDHI assumption states that, given a random generator g ∈ G and the values (g, g α , g α 2 , ..., g α q ) ∈ G q+1 , for a random α ∈ Z p and a candidate X ∈ G, it is hard to decide whether X = g 1/α or not.

The Decisional Composite Residuosity (DCR) Assumption

This assumption has been introduced by Paillier [START_REF] Paillier | Low-cost double-size modular exponentiation or how to stretch your cryptoprocessor[END_REF] in order to prove the security of the proposed encryption scheme.

Definition 26 ( Decisional Composite Residuosity (DCR) Assumption).

DCR assumption states that it is hard to distinguish

Z n n 2 from Z * n 2 , where Z n n 2 = {z ∈ Z * n 2 , ∃y ∈ Z * n 2 : z = y n modn 2 }.

LRSW Assumption

This assumption has been introduced by Lysyanskaya, Rivest, Sahai and Wolf [START_REF] Lysyanskaya | Pseudonym systems[END_REF] in order to prove the security of the proposed scheme.

Definition 27 ( LRSW Assumption). Let G be cyclic group of prime order q and g be a generator of G. the assumption LRSW states that, given X = g x , Y = g y and an oracle O LRSW X,Y that takes on input a message m ∈ Z q and outputs A = (a, a y , a x+mxy ) such that a is randomly chosen, it is hard to compute A = (a , a y , a x+mxy ) for another value a , if m has not been given as input to the oracle.

After defining our computational assumption, we move to the third step of the process "proving the security of a scheme" which is "presenting a reduction of the scheme security to a hard problem".

Provable Security

In this section, we present the concept of reductionist security and the different security models that can be used to prove the security of a cryptographic scheme.

Reductionist Security

The main idea of the reductionist security is to formally prove that if an adversary A breaks a security property of a scheme, he can be used to solve a hard problem like those we have stated in the previous section. The first precepts of provable security have been introduced by Goldwasser and Micali [START_REF] Goldwasser | Probabilistic encryption[END_REF] in 1984 for encryption. Later with Rivest, they defined this new concept for signature [START_REF] Goldwasser | A "paradoxical" solution to the signature problem[END_REF][START_REF] Goldwasser | A digital signature scheme secure against adaptive chosen-message attacks[END_REF]. Though polynomial, the proposed reductions had a computational high cost. Later several improvements occurred. In 1996, Bellare and Rogaway introduced the exact security approach [START_REF] Bellare | The exact security of digital signatures-how to sign with rsa and rabin[END_REF] where the estimate of computational complexities of adversarial tasks is more accurate than what we would have with polynomial equivalence. Then, Ohta and Okamoto introduced the concrete security approach [START_REF] Ohta | On concrete security treatment of signatures derived from identification[END_REF] enabling more efficiency. More recently, Pointcheval, in 2001, introduced the concept of practical security [START_REF] Pointcheval | Practical security in public-key cryptography[END_REF].

If we consider an adversary A reaching his goal in time t and a reduction that solves the hard problem in time f (t), we can define three security concepts:

• Asymptotic security, if f is polynomial (bounded by a t polynomial).

• Exact security, if f is explicit.

• Practical security, if f is "small", e.g., linear.

If the reduction is polynomial, attacking the protocol is said to be hard as solving the hard problem.

In order to have the best possible reduction, we should precisely define the goals of the attacker. Therefore, we describe, in the following section, the different security models that can be used to define the environment where an attacker can perform his attack.

Security Models

In this section, we distinguish two security models: the Random Oracle Model and the standard Model.

Random Oracle Model

In cryptography, random oracles can be used as an ideal replacement for hash functions in schemes where strong randomness assumptions are needed of the hash function's output. In such a case, the attacker cannot deduce any information from the hash values that it has already been obtained and it can not build hashes for new values. In such a model, the security of the scheme does not depend of the specified hash functions. A scheme is secure if an attacker solves a hard problem in order to break it. The concept of random oracles has been introduced by Fiat and Shamir [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF] in 1986 and then modeled by Belleare and Rogaway [START_REF] Bellare | Random oracles are practical: A paradigm for designing efficient protocols[END_REF] in 1993.

Standard Model

The Random Oracle model has been criticized as very restrictive, even if it is widely used. Canetti, Goldreich and Halevi [START_REF] Canetti | The random oracle methodology, revisited (preliminary version)[END_REF][START_REF] Canetti | On the random-oracle methodology as applied to length-restricted signature schemes[END_REF] demonstrated that there are secure schemes under the random oracle model such that any implementation of the oracles makes them insecure. Bellare, Boldyreva and Palacio made proposals, in [START_REF] Bellare | An uninstantiable random-oracle-model scheme for a hybrid-encryption problem[END_REF], that ensure some properties only in the random oracle model. This assumption implies that the security of the scheme cannot be proven. In order to mitigate such problem, a new model has been introduced: Standard model. Unlike the random oracle model, the standard model does not consider any assumption regarding the used hash functions.

Cryptographic Schemes

In this section, we present cryptographic schemes that we will use in our constructions of the thesis.

Pseudo-Random Function

In this thesis, we use a pseudo-random function (Definition 12) that has been introduced by Dodis and Yampolskiy [START_REF] Dodis | A verifiable random function with short proofs and keys[END_REF][START_REF] Dodis | Efficient Construction of (Distributed) Verifiable Random Functions[END_REF]. Their construction works as follows. Let G be a cyclic group with prime order p, g t a generator of G, s ∈ Z p a private secret. The pseudorandom function (PRF for short) F s takes as input a message k ∈ Z p and outputs

F s (k) = g 1/(s+k+1) t .
The properties of this construction, given in definition 12, are ensured under the q-DDHI assumption in G.

Pedersen Commitment

In this thesis, we use a commitment scheme that has been introduced by Pedersen in [START_REF] Pedersen | Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing[END_REF]. This commitment scheme provides perfect hiding and satisfies the binding property under the DL assumption.

Setup The parameters are:

• G a cyclic group with prime order p.

• g 1 and h T are generators of G.

Commit

• Let m be the message to be committed.

• Choose a random value ν ∈ Z * p • Compute C = g m 1 × h ν T
C is a commitment of the message m.

Public Key Encryption

In this thesis, we use two public key encryption schemes (Definition 14), i.e., the ElGamal encryption scheme and the Paillier encryption scheme. Actually, we apply the threshold version of these schemes. We also utilize a proxy re-encryption scheme (Definition 15) based on ElGamal cryptosystem.

In this section, we detail the ElGamal and Paillier encryption schemes. We give the definition of a threshold cryptosystem and describe the proxy re-encryption scheme based on ElGamal cryptosystem.

ElGamal

The ElGamal [START_REF] El | A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms[END_REF] encryption scheme is a public key algorithm based on the Diffiehellman [START_REF] Diffie | New directions in cryptography[END_REF]. The variant, that we use it in our m-ticketing system, works as follows.

Setup

The parameters are:

• G a cyclic group with prime order p.

• g T a random generator of G.

The private key is formed by x ∈ Z * p and the corresponding public key consists of the elements (g T , h = g x T )

Enc

The ElGamal ciphertext of a message m ∈ G is computed as follows:

• Choose a random number r ∈ Z * p .

• Compute C 1 = g r T and C 2 = m × h r
The encryption of m is (C 1 , C 2 ).

Dec

The decryption of the ciphertext (C 1 , C 2 ) is obtained through the following computation:

m = C 2 /C x 1
The ElGamal cryptosystem is semantically secure under the Decisional Diffie-Hellman (DDH) assumption.

Paillier

We use the Paillier encryption scheme [START_REF] Paillier | Low-cost double-size modular exponentiation or how to stretch your cryptoprocessor[END_REF] in our m-ticketing system. It works as follows.

Setup

The parameters are:

• a and b random primes such that a, b > 2, a = b, |a| = |b| and gcd(ab, (a -1)(b -1)) = 1

• n = ab

• Π = lcm(a -1, b -1)
• K = Π -1 mod n

• g P = (1 + n)
The public key is pk = (n, g P ) and the corresponding secret key is sk = (a, b).

Enc

To encrypt a message m ∈ Z n , a user performs the following operations:

• Choose a random number r ∈ Z * n • Compute C = g m P r n mod n 2
The encryption of the message m is C.

Dec

The decryption algorithm is as follows:

m = ((C ΠK mod n 2 ) -1)/n mod n 2
The Paillier cryptosystem, described above, provides semantic security against chosenplaintext attacks (IND-CPA) under the Decisional Composite Residuosity (DCR) assumption.

Threshold Cryptosystem

In a threshold version, the ElGamal public key and its corresponding private key [START_REF] Yvo | Threshold cryptosystems[END_REF] (respectively the Paillier public key and its corresponding private key [START_REF] Fouque | Fully distributed threshold RSA under standard assumptions[END_REF]) are cooperatively generated by n parties; however, the private key is shared among the parties. In order to decrypt a ciphertext, a minimal number of t (the threshold) out of n parties is necessary.

Proxy Re-Encryption Scheme

We use the proxy re-encryption building block in our TEE migration protocol. Blaze et al. introduced the notion in [START_REF] Blaze | Divertible Protocols and Atomic Proxy Cryptography[END_REF]. These approach is based on the ElGamal cryptosystem and it works as follows.

Setup

The parameters are:

• G a cyclic group with prime order q.

• g a generator of G.

• a and b randomly chosen in Z * q .

The private and public key of Alice are (a, g a ) and the private and public key of Bob are (b, g b ).

ReKeyGen

The re-encryption key is computed as follows: R A→B = b/a = ba -1 mod q

Enc

To encrypt a message m ∈ G that can be decrypted by Alice, a user does the following operations:

• Choose a random integer r ∈ Z * q .

• Compute g r m.

• Compute g ar .

The ciphertext of Alice is

C A = (g r m, g ar ) Re-enc To re-encrypt the ciphertext of Alice (C A ), in other words, to convert a ciphertext of Alice (C A ) to a ciphertext of Bob (C B ), the proxy re-encryption computes (g ar ) R A→B . (g ar ) R A→B = (g ar ) b/a = g br
The ciphertext of Bob is C B = (g r m, g br ).

Dec

Bob can retrieve the plaintext corresponding to the ciphertext C B = (g r m, g br ) by computing m = g r m (g br ) 1/b .

Digital Signature

In this thesis, we use group signature scheme (Definition 17) namely Boneh-Boyen signature and Camenisch-Lysyanskaya signature. We also utilize the RSA signature.

In this section, we detail these signature schemes.

RSA

The RSA signature schemes has been introduced together with the RSA encryption scheme [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF]. It is based on the hash and sign concept and it is secure owing to the Full Domain Hash [START_REF] Bellare | Random oracles are practical: A paradigm for designing efficient protocols[END_REF].

Setup

The parameters are:

• p, q ∈ N two prime integers.

• n = pq.

• e an integer co-prime with φ(n) = (p-1)(q -1) where φ is Euler's totient function.

• d = e -1 mod φ(n).

• H : {0, 1} * → Z n a hash function.

The private key is d and the public key is (n, e).

Sign

To sign a message m ∈ Z n , a user carries the following operations:

• Compute m = H(m). • Compute σ = m d mod n
The signature of the message m is σ.

Verify

The signature σ is valid if H(m) = σ e mod n.

Boneh-Boyen Signature

Based on the scheme proposed by Boneh and Boyen [START_REF] Boneh | Short Group Signatures[END_REF][START_REF] Boneh | Short Signatures Without Random Oracles[END_REF][START_REF] Boneh | Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups[END_REF], it is possible to prove knowledge of a signature on a message, without revealing the signature nor the message.

There are two variants of this signature scheme: with and without pairing. We detail these variants in the sequel.

Boneh-Boyen Signatures with pairings Setup

The parameters are:

• G a cyclic group with prime order p.

• e a bilinear pairing.

• g 1 and g 2 two generators of G.

• y ∈ Z p .
The private key is y and the public key is Y = g y 2 .

Sign

The signature of a message m ∈ Z p is obtained by computing σ = g 1/(y+m) 1

.

Verify A signature σ of m is valid if: e(σ, Y g m 2 ) = e(g 1 , g 2 ).
Boneh-Boyen Signature without pairings Setup

• G is a cyclic group with prime order p.

• e is a bilinear pairing.

• g 1 and g 2 two generators of G.

• y ∈ Z p .
The private key is y and the public key is Y = g y 2 .

Sign Similarly to Boneh-Boyen signatures with pairings, the signature A of a message m ∈ Z p is obtained by computing

A = g 1/(y+m) 1 . This implies that A y = g 1 A -m .

Verify

The signature A of the message m is valid if the proof π is valid where π proves that the discrete logarithm of (g

1 A -m ) in the base A is equal to the discrete logarithm of Y in the base g 2 : ZKP K(y : Y = g y 2 ∧ A y = g 1 A -m
). Such a proof of equality of discrete logarithms has been introduced in [START_REF] Chaum | Wallet databases with observers[END_REF].

Theorem 1. The Boneh-Boyen (BB for short) signature scheme without pairings is existentially unforgeable under a weak chosen message attack under the q-Strong Diffie-Hellman (q-SDH) assumption, in the random oracle model.

Proof 1 (sketch). Under the q-Strong Diffie-Hellman assumption, it is impossible to find a message m (which was not given to the signing oracle) and a value A such that A = g 1/(y+m) 1

, as proved in [START_REF] Boneh | Short Signatures Without Random Oracles[END_REF][START_REF] Boneh | Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups[END_REF]. Moreover, in the random oracle model, the proof of knowledge π is unforgeable [START_REF] Boneh | Short Signatures Without Random Oracles[END_REF][START_REF] Boneh | Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups[END_REF], which concludes the proof.

Camenisch-Lysyanskaya signatures

The signature schemes, proposed by Camenisch and Lysyanskaya [START_REF] Camenisch | Signature schemes and anonymous credentials from bilinear maps[END_REF], are equipped with protocols providing various properties.

One of these protocols allows a signature to be issued on the messages that are not known to the signer, but to which the signer only knows a commitment. Informally, in a protocol for signing a committed value, we have a signer with public key pk, and the corresponding secret key sk, and a user who queries the signer for a signature. The common input to the protocol is a commitment C on secret values (m 1 , m 2 , . . . , m l ) known only by the user. At the end of this protocol, the user obtains a valid CL-signature = Sign(m 1 , m 2 , . . . , m l ) and the signer learns nothing about (m 1 , m 2 , . . . , m l ).

Setup

The parameters are:

• G and G are cyclic groups of prime order p.

• g is a generator of G and g is a generator of G.

• e is a bilinear map e : G × G → G.

• x ∈ Z p . • y ∈ Z p .
• z i ∈ Z p where 1 i l.

• X = g x .
• Y = g y .

• Z = g z i where 1 i l where l is the number of user's secret values.

• W i = Y z i where 1 i l. The values W i will be used to prove the knowledge of the signature.

The private key is sk = (x, y, {z i }) where 1 i l and the public key is pk = (p, G, G, g, g, e, X, Y, {Z i }, {W i }) where 1 i l.

Sign

The signature protocol is an interactive protocol between a user U who has on input (m 0 , ..., m l ) and a signer S who has on input the private key sk = (x, y, {z i }).

1. U computes a commitment M on the messages (m 0 , ..., m l )

M = g m 0 Π l i=1 Z m i i .
2. U sends a zero-knowledge proof of knowledge of the opening of the commitment P OK((µ 0 , ..., µ l ) :

M = g µ 0 Π l i=1 Z µ i i ).
3. S computes the signature σ = (a, {A i }, b, {B i }, c) where

• α ∈ Z p .
• a = g α .

• A i = a z i such that 1 i l.

• b = a y .

• B i = A y i such that 1 i l. • c = a x M αxy .

S sends the signature σ

Verify

To verify a signature σ = (a, {A i }, b, {B i }, c) on the messages (m 0 , ..., m l ), the user checks that

• {A i } were formed correctly: e(a, Z i ) = e(g, A i ).

• b and {B i } were formed correctly: e(a, Y ) = e(g, b) and e(A i , Y ) = e(g, B i ) such that 1 i l.

• c is formed correctly: e(X, a).e(X, b)

m 0 .Π l i=1 e(X, B i ) m i = e(g, c).
This protocol is secure under the LRSW assumption.

Another protocol allows to prove knowledge of a signature σ = (a, {A i }, b, {B i }, c) on a tuple of messages (m 1 , m 2 , . . . , m l ) without releasing any information on the corresponding signature. Each message can either be revealed to the verifier, sent in a committed form or he might have no information about it. The prover 1. Computes and sends a blinded version of his signature σ: Choose random r, r 0 ∈ Z p , and blind the signature to form σ = (ã,

{ Ãi }, b, { Bi }, ĉ, 1 i l) such that • ã = a r • b = b r • Ãi = A r i where 1 i l. • Bi = B r i where 1 i l. • ĉ = c rr 2. let v x , v xy , v s and V (xy,i) such that v x = e(X, ã), v xy = e(X, b), v s = e(g, ĉ) and V (xy,i) = e(X, Bi )
3. The prover and verifier compute these values (locally) and then carry out the following zero-knowledge proof protocol: P OK((µ 0 , ..., µ l ), ρ :

(v s ) ρ = v x (v xy ) µ 0 l i=1 )(V (xy,i) ) µ i 4.
The verifier accepts the proof above if:

• { Ãi } were formed correctly: e(ã, Z i ) = e(g, Ãi ).

• b and { Bi } were formed correctly: e(ã, Y ) = e(g, b) and e(ã, Y ) = e(g, Bi ) such that 1 i l.

• the proof is correct.

Another appealing feature of some of these CL-signature schemes is that the signatures, they produce, can be randomized. Indeed, given a valid CL-signature σ on a message m, anyone can compute σ , another valid signature on m. Moreover, σ and σ are unlinkable under the Decision Diffie-Hellman (DDH) assumption (i.e., given σ and σ (but not m), it is hard to decide whether these two signatures have been issued on the same message).

Finally, CL-signatures have been widely used to design anonymous credentials or DAAlike schemes.

Set-Membership Proof

A set-membership proof allows a prover to prove, in a zero-knowledge way, that his secret lies in a given public set. Such proofs can be used, for instance, in the context of electronic voting, where the voter needs to prove that his secret vote belongs to the set of all possible candidates.

Recent propositions of set-membership proofs [START_REF] Chaabouni | A Non-interactive Range Proof with Constant Communication[END_REF][START_REF] Canard | New Results for the Practical Use of Range Proofs[END_REF] follow the same idea:

• Let Φ be a public set.

• Let CA be a designated authority that owns a pair of signature keys (sk CA , pk CA ), produces public signatures σ i = SIGN sk CA (i) on each element i of the public set Φ (and only on these elements).

• Let Σ be the public set of the signatures σ i .

• The proof of knowledge of a secret i ∈ Φ consists in proving the knowledge of a (public) signature on the secret i (which will be only possible if i belongs to the interval Φ) without revealing i or the used signature.

P OK(i, r, σ i : C = g i h r ∧ σ i = SIGN sk CA (i))
Solutions in [START_REF] Chaabouni | A Non-interactive Range Proof with Constant Communication[END_REF][START_REF] Canard | New Results for the Practical Use of Range Proofs[END_REF] require the prover to perform pairing computations. However, these cryptographic tools are not often convenient for many constrained platforms like Secure Elements, SIM cards, etc. Indeed, these computations require many resources, hence, much time.

Conclusion

In this chapter we began by presenting some mathematical and cryptographic tools that we need in this thesis. Then, we specified the computational assumptions on which relies the security of our constructions. Finally, we described some cryptographic schemes like group signature schemes that are usually used in e-poll and e-ticketing systems in order to ensure users' privacy, namely anonymity and unlinkability, when using the service.

In such use cases, usually the user has a resource constrained device, however, privacyenhancing cryptographic tools are usually costly. In the next chapters, we introduce optimizations and adaptations of these cryptographic tools in order to find the right balance between privacy and efficiency.

At the end of this chapter, we described set-membership proofs. Current implementations are very costly as it requires pairing computations at the prover side (user's device). In the next chapter, we introduce a practical set-membership proof that does not require pairing computations at the prover side. This implementation will be used later in our m-ticketing protocol.

Introduction

In this chapter, we present a new set-membership proof protocol. Our set-membership proof is a zero knowledge proof of knowledge which allows a prover to convince any verifier that a committed integer k lies in a public discrete set Φ. This zero knowledge proof of knowledge can be made non-interactive using the Fiat-Shamir heuristic and the random oracle model [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF]. The commitment scheme that we use is the one proposed by Pedersen [START_REF] Pedersen | Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing[END_REF].

Our set-membership proof bears some similarities with the protocol proposed by Camenisch et al. [START_REF] Camenisch | Efficient Protocols for Set Membership and Range Proofs[END_REF]. Yet, our set-membership proof does not require the prover (a SIM card and/or a smartphone in our setting) nor the verifier (in a specific scenario) to perform pairing computations which are quite costly, in the order of seconds, e.g. for the following microprocessors: 17.9s on an ATmega [START_REF] Szczechowiak | NanoECC: Testing the Limits of Elliptic Curve Cryptography in Sensor Networks[END_REF], 2.5s on a Philips HiPerSmart TM MIPS [START_REF] Devegili | Implementing Cryptographic Pairings over Barreto-Naehrig Curves[END_REF], 1.9s on an MSP430X [START_REF] Porto | Efficient software implementation of public-key cryptography on sensor networks using the MSP430X microcontroller[END_REF]. Our set-membership proof is also more efficient and conceptually simpler than the recent one proposed by Canard et al. at EuroPKI 2013 [START_REF] Canard | New Results for the Practical Use of Range Proofs[END_REF]. Their scheme which involves several verifiers, who share a decryption key, seems to be tailored to specific applications like e-voting where the verifiers (tallying authorities) own such a key to open ballots. As regards our set-membership proof, we will use it in the construction of our m-ticketing protocol (Chapter 7) in order to efficiently prove that a ticket index belongs to the public set of indexes.

This chapter is organized as follows. In Section 4.2, we detail the new set-membership proof. Then, we prove the security of our implementation in Section 4.3. We draw the conclusion of this chapter in Section 4.4.

Set-Membership Proof Protocol

The public parameters of our set-membership proof are

• G 1 , G 2 , G T : three (multiplicative) bilinear groups of prime order p.

• e: a bilinear map such that e :

G 1 × G 2 → G T .
• g, g 1 and h T : three generators of G 1 .

• g 3 : a generator of G 2 .

• H: a hash function, for instance, SHA-256.

Our protocol considers a designated authority, a verifier and a prover. The designated authority (which may or may not be the verifier) randomly chooses a value y ∈ Z * p (its private key) and publishes the corresponding public key Y = g y 3 . After generating its key, this designated authority can issue BB-signatures on each element of the public set Φ. Let k denote an element of the set Φ and A k the BB-signature on the value k, i.e., A k = g 1/(y+k) . The set of all message-signature pairs (k, A k ), that we denote by , is published by the designated authority.

Φ = {k}, = {(k, A k )} k∈Φ = {(k, g 1/(y+k) )} k∈Φ
In Figure 4.1, we detail our new protocol that enables to prove that a value k committed by the prover in the commitment Com belongs to the set Φ. This comes down to proving knowledge of the BB-signature A k .

Remark 1: Proving knowledge of a valid BB-signature

A k = g 1/(y+k) on a value k committed in Com = g k 1 h
ν T , without revealing either k or the signature and without using pairings on the prover's side can be done as follows.

The prover first randomizes A k by choosing a random value l ∈ Z * p and computing y+k) this implies that: B = A l k = (g l ) 1/(y+k) and then that B y+k = g l . If we note B 1 = B -1 and D = B y , it implies that:

B = A l k . Since A k = g 1/(
D = B k 1 g l .
As a result, in order to prove that the value k committed in Com belongs to the set Φ, the prover just has to send B and D to the verifier and compute the following zero knowledge proof of knowledge:

Π = P OK(k, ν, l : Com = g k 1 h ν T ∧ D = B k 1 g l ).
Prover Verifier Public input: public parameters, sets Φ and Public Input: public parameters, sets Φ and

Private Input: k Private Input: y Pre-computations Choose ν ∈ Z * p Compute: Com = g k 1 h ν T
Pick the valid BB signature corresponding to the element k :

A k = g 1/(y+k) Choose l ∈ Z * p Compute(see remark 1): B = A l k ; B 1 = B -1 ; D = B k 1 g l Choose k 1 , l 1 , r 1 ∈ Z * p Compute: Com 1 = g k 1 1 h r 1 T ; D 1 = B k 1 1 g l 1 Real time computations Compute: ch -------Choose ch ∈ Z * p (A random challenge) c = H(Com, B, D, Com 1 , D 1 , ch); s 1 = k 1 + c × k mod p; s 2 = r 1 + c × v mod p s 3 = l 1 + c × l mod p; Π = Com, B, D, s 1 , s 2 , s 3 Π ------Check that B = 1 G 1
• If the verifier and the designated entity are the same entity. This implies that the verifier holds the private signature key y (First case). Hence the prover does not send the value D.

The verifier can compute it: D = B y and goes to (*)

• Otherwise, if the verifier doesn't know the private signature key y (Second case), then, it checks that e(D, g 3 ) = e(B, Y ) and goes to (*)

(*) Compute: C = g s 1 1 h s 2 T Com -c and D = B s 1 1 g s 3 D -c
Check that: c = H(Com, B, D, C, D, ch) The computation of the zero knowledge proof of knowledge Π is described in Figure 4.1.

Upon receiving Π, the verifier proceeds to the verification. We distinguish two cases.

In the first case, the verifier and the designated authority are the same. Thus, the verifier holds the private signature key y. Consequently, the verification of Π occurs without requiring any pairing computations. This implies that our set-membership proof does not require pairing computations for both the prover and the verifier.

In the second case, the verifier does not have the private signature key y of the designated authority. Then, the verifier needs to perform some pairing computations in order to verify Π. Nevertheless, the prover still has no pairing computations to perform. This is particularly interesting for the m-ticketing use case.

Security Analysis

Theorem 2. If the |Φ|-SDH assumption holds, then the protocol in Figure 4.1 is a zero-knowledge argument of set-membership for a set Φ.

Proof 2 (sketch).

The completeness of the protocol follows by inspection.

The soundness follows from the extraction property of the underlying proof of knowledge and the unforgeability of the underlying signature scheme. In particular, the extraction property implies that for any prover P * that convinces V with probability , there exists an extractor which interacts with P * and outputs a witness (k, v, l) with probability poly( ). Moreover, if we assume that the extractor input consists of two transcripts: {Y, , Com, B, D, c, c, s 1 , s1 , s 2 , s2 , s 3 , s3 } the witness can be obtained by computing (all the computations are done mod p):

k = (s 1 -s1 )/(c -c), ν = (s 2 -s2 )/(c -c), l = (s 3 -s3 )/(c -c)
The extractor succeeds when (c -c) is invertible in Z p . If the following check D = B y holds , this implies that:

D = B y = B k 1 g l and then B y B k = g l .
Let us denote by A k = B 1/l . Note that we necessarily have l = 0, otherwise this would imply that the prover knows the secret value y (which would be equal to -k mod p). We therefore have A y+k k

= g and consequently that

A k = g 1/(y+k) So the prover knows a valid BB signature on the value k. This implies that k ∈ Φ. Also note that if D = B y then this implies that the Prover P only knows one representation of D in the base B 1 and g. Otherwise this would imply that P knows the private key y. Indeed, suppose that P knows two representations of D in the base B 1 and g. Let us denote by (k, l) and ( k, l) these two representations. Since G 1 is a prime order group and B 1 = 1 and g = 1, this implies that k = k and l = l. Since ly) . Since G 1 is a prime order group this implies that y = -k -lỹ.

D = B k 1 g l = B k 1 g l, this implies that B k- k 1 = g l- l and that B (k-k)/(l-l) 1 = g. Let us denote by ỹ = (k -k)/(l -l). then D = B y = B k 1 g l = B -k B -(
If k / ∈ Φ, then P * can be directly used to mount a weak-chosen attack against the BB signature scheme with probability poly( ) of succeeding. Thus must be negligible.

Finally, to prove (honest-verifier) zero-knowledge property, we construct a simulator Sim that will simulate all interactions with any (honest verifier) V * .

1. Sim retrieves Y and from V * .

2. Sim randomly chooses k ∈ Φ and l ∈ Z * p and computes

B = A l k , B 1 = B (-1) and D = B k 1 g l . 3. Sim randomly chooses c, s 1 , s 2 , s 3 ∈ Z * p and computes Com 1 = g s 1 1 h s 2 T Com -c and D 1 = B s 1 1 g s 3 C -c . 4. Sim outputs S = {Com, B, D, Com 1 , D 1 , c, s 1 , s 2 , s 3 }
Since G 1 is a prime order group, then the blinding is perfect in the first two steps and S and V * 's view of the protocol are statistically indistinguishable.

Conclusion

In this chapter, we introduced a new set-membership proof that enables a prover to prove that he owns an element of a public set without revealing it. Unlike the previous constructions, this proof does not require pairing computations at the prover side. However, when the verifier does not know the designated authority private key (the verifier and the designed authority are distinct), the verifier may need to do some pairing computations. We will use our new set-membership proof in the construction of our m-ticketing protocol in Chapter 7. Prior that, we outline the related work to public transport service in the next chapter.

Introduction

In this Chapter, we detail related work on privacy-preserving solutions for public transport service. We begin by describing the CALYPSO standard in Section 5.2. In Section 5.3, we present some commercial mobile contactless solutions for transport service while showing to which extent they guarantee the users' privacy. We review proposed privacy-preserving transport systems in the literature in Section 5.4. These studies have helped us to identify the important security and privacy properties required to build privacy-preserving mobile solutions for transport system. We give further details about the Rupp et al. [2] attack that we discovered in Section 5.5. In Section 5.6 and Section 5.7, we give an overview of our transport system. We present the architecture overview and the entities of the system as well as the trust model. We also recall the main phases of a transport system. These phases will be personalized according to the use case, i.e., m-pass or m-ticketing use case. Section 5.8 concludes the chapter.

Standardization

The CALYPSO standard [START_REF]Calypso handbook v1.1[END_REF][START_REF]Functional card application v1.4[END_REF] (ISO 24014-1:2007 norm) introduced the contactless aspects across a European consortium composed of transport operators such as the Belgium STIB and the French RATP. CALYPSO specifies the details of all the transactions related to e-ticketing for contactless transport services from the purchase of the ticket/pass to their uses. This standard is very precise, in particular when describing operations such as the card authentication, the validator authentication and the messages exchanged between these two entities. Moreover, performance issues such as the computational time are also included in this standard, particularly for contactless smartcards.

Commercial Transport Solutions

Many commercial mobile transport solutions have recently emerged. For instance, the service Touch and Travel (T&T) [START_REF]The project Touch and Travel[END_REF] has been proposed by the German federal railways Deutsche Bahn since 2008 and the mobile contactless public transport service based on the Octopus card [START_REF]Info. Mobile payment services using nfc sims equipped with sony felica TM technology to begin in hong kong[END_REF][START_REF] Gematlo | Gemalto enables commercial mobile nfc transport and payment roll-out in hong kong[END_REF] has been proposed by PCCW-HKT, one of Hong Kong's major mobile network operators and Octopus Cards Limited (OCL) since 2013.

The T&T service is one of the first contactless mobile ticketing services. A user must start the T&T application upon departure. Once he reaches his destination, the user must indicate the end of his trip. Designating departure and arrival stations can be performed by using a touchpoint if one is available at the station, relying on the GPS as captured by his smartphone or based on the network cell location.

Regarding the Octopus card, it is a popular contactless smart card used for public transport and retail payment in Hong Kong. Such cards, which can be seen as electronic purses, have unique identifier for all the user's transactions [START_REF] Lee | Security analysis of the octopus system, visited the 31th[END_REF].

The solutions mentioned above do not satisfy all the privacy requirements. they are limited to only protect the users' privacy against outsiders and not against the transport authority. Indeed, they suffer from the linkability issue, as it enables the transport authority to track users.

Mobile Privacy-Preserving Solutions for Public Transport

In this section, we give an overview of solutions for NFC transport services in the literature. Most of them do not address the anonymity and unlinkability issues, and the few who do either are not yet efficient enough to cope with the constraint of running in less than 300 ms, or present privacy weaknesses.

In the follow-up papers [START_REF] Ekberg | Mass transit ticketing with NFC mobile phones[END_REF][START_REF] Tamrakar | Tapping and tripping with nfc[END_REF], Tamrakar and Ekberg proposed a contactless m-ticketing transport service. The main idea of this service is that a user, who has already subscribed to the service, can buy some credits and then purchases tickets. The ticketing application is authorized to locally generate a ticket before then charging the user account. Like for T&T service, the user has to specify the departure and arrival stations. Depending on the trust assumptions that are made, the authors propose two architectures relying or not on a trusted execution environment [START_REF] Arfaoui | Trusted Execution Environments: A Look under the Hood[END_REF]. While this solution complies with the main functional requirements of public transport service, a user's anonymity and the unlikability of his trips are not ensured. Indeed, the user personal data, such as his identifier and location, are protected against outsiders but revealed to the service provider.

Heydt-Benjamin et al. were the first to propose a cryptographic framework for transport service [START_REF] Thomas | Privacy for public transportation[END_REF]. The authors' approach uses e-cash, anonymous credentials, and proxy reencryption [START_REF] Blaze | Divertible Protocols and Atomic Proxy Cryptography[END_REF]. They discuss the challenges that a privacy-preserving transit system should solve. Using cryptographic transit tickets should not disable basic capabilities like cloning detection, virtual ticket backups or transfers, ticket revocation. The efficiency of the use of a virtual ticket, especially over contactless technologies, is also important.

Derler et al., authors of [START_REF] Derler | Anonymous ticketing for nfc-enabled mobile phones[END_REF], have analyzed the efficiency of a selective disclosure protocol in the latest smartphones. In a nutshell, a selective disclosure protocol allows a user to reveal that he possesses some property linked to his identity, but without revealing his identity itself or any unnecessary information. With respect to the ticketing use case, they used a one time-show protocol, which is the Brands DSA-based protocol [START_REF] Brands | Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy[END_REF][START_REF] Glenn | A description of protocols for private credentials[END_REF]. Thanks to this protocol, during the product validation phase, the user is able to prove the validity of his credentials without disclosing them. Even though this system provides anonymous tickets, the m-tickets, hence the users' trips, remain linkable. Moreover, the ability to recover the identity of a user (by an independent entities such as a judge) is not provided. In the other hand, Derler et al. implementation introduces an important delay (2 -15s) even if it is shared between a mobile (Nokia 6131) and a secure element (an embedded G&D smart card). This is because their group signature implementation uses pairing based cryptography.

In [START_REF] Isern-Deya | A secure automatic fare collection system for time-based or distance-based services with revocable anonymity for users[END_REF], Isern-Deya and his co-authors proposed an automatic fare collection system for temporal and spatial services, which is based on the BBS group signature [START_REF] Boneh | Short Group Signatures[END_REF][START_REF] Boneh | Short Signatures Without Random Oracles[END_REF]. Thus, they provided revocable anonymity and unlinkability for the users of the service.

The main drawback of this solution is that although it has been implemented on a smartphone, the waiting time at the entrance and exit of the transport network is still prohibitive, i.e., in the order of seconds.

More recently, Rupp et al. [2] proposed at FC 2013 a privacy preserving pre-payment protocol with refund for public transport. The main goal of Rupp et al. is to minimize the number of coins a user needs to pay for a trip. This would minimize the number of computationally expensive spending transactions. To this end, the user withdraws a single coin be worth the most expensive ride in the coin credential. Then, the user will be refunded. The verification procedure (of the refund) is too costly to handle on constrained devices. The lack of verification could lead to serious privacy weaknesses: a malicious transport authority could link users' trips. We detail the Rupp et al. protocol and its privacy weakness in the following section in order to illustrate the difficulty to build a protocol ensuring a high level of privacy.

In Table 5.1, we classify the analyzed proposals depending on:

1. Anonymity: the ability to identify users during the use of the transport service by outsiders or by the transport authority, To summarize, balancing users' privacy with efficiency and security needs of the transport authority is not an easy task. In the next section, we give further details about the privacy weakness of Rupp et al. protocol, published in FC 2013, that we discovered.

The Privacy Weakness of Rupp et al. Solution

In this section, we give further details about the payment protocol for public transport proposed by Rupp et al. at FC 2013 [2] and called P4R. Then, we present an attack that enables a malicious transport authority to break users' privacy.

At first, the user buys a trip authorization token (T AT i ) which consists of an (extended) coin in Brands' scheme [START_REF] Brands | Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy[END_REF][START_REF] Glenn | A description of protocols for private credentials[END_REF]. This token enables the user to perform one trip. Then, the user receives a fresh refund token RT .

RT = SN RT such that SN RT ← G
The user sets a variable R to 1 and υ to 0. R will be used to aggregate blinding factors and υ is the refund amount. At the entry turnstile, the user shows a T AT i and proves its ownership. Right after this, the user receives a refund calculation token (RCT i ) which consists of a MAC on T AT i , a timestamp and the reader ID. At the turnstile of the exit, the user shows his RCT and proves the ownership of the T AT i contained within it. In addition, he collects refund on his RT , as described in Figure 5.1. A refund value ω is represented as a ω-times BLS signature [98] SN d ω RT such that d is the secret BLS signature key of the transport authority. Later, the user redeems his RT . This consists on sending a blinded version of his RT (RT = RT r ), SN RT , R and the collected amount υ to the transport authority. The latter checks the validity of both SN RT and the signature, In [2], Rupp et al. assume that, for efficiency reasons, users don't verify their RTs. Indeed, verifications of refund tokens (step 1 in Figure 5.1) is too costly and can not be handled by constrained devices such as SIM cards. This lack of verification could lead to serious privacy weaknesses: a malicious transport authority could link users' trips.

e(SN R RT , h d υ ) ? = e(RT , h) (2). Collecting Refund User Exit turnstile r ← Z * p ω ← ---------- Determine the refund ω based on the received information in RCT RT = RT r RT -----------→ υ = υ + ω, R = Rr mod p, RT = RT RT ← ----------- RT = RT d ω (1) Redeeming Refund User Transport authority r ← Z * p , RT = RT r , R = Rr mod p SN RT ,RT ,υ,R -----------→ check validity of SN RT , υ < p -1, e(SN R RT , h d υ ) ? = e(RT , h) (2)
More precisely, for a given station, the transport authority is able to identify all the users who left at this station. To this end, in step (1) in Figure 5.

RT

where j corresponds to the number of times the user left the targeted station, R is the product of all the variables r and υ is the sum of all the refunds ω. At the redeeming refund step, upon receiving the serial number SN RT , the blinded version of the refund token RT , the refund amount υ, and the aggregate blinding factor R, the transport authority will as usual check the validity of SN RT and whether the amount is within the allowed range [0, p -1]. Now, in order to verify the signature and distinguish users who exited at the relevant station, the transport authority starts by checking the relation (2). If (2) holds, this implies that the user did not left the targeted station. Otherwise, the transport authority checks:

e(SN t j R RT , h d υ ) = e(SN RT , h) t j Rd υ = e(SN t j Rd υ RT , h) = e(RT , h) (3)
To do so, the transport authority will repeat the computations with different values of j until the relation (3) holds. When e(SN t j R RT , h d υ )

? = e(RT , h) (3) holds, this implies that the user left the targeted station j times.

In order to monitor several stations at the same time, the transport authority will have a list of variables t, e.g., t A for station A, t B for station B, etc. At the redeeming refund step, the transport authority will test different values of t until it finds the ones that satisfy the relation e(SN

t jx x R RT , h d υ ) ? = e(RT , h) (4)
where t x characterizes a station x and j x represents the number of exits at the station x. For instance, if the user left the station A four times, the station B twice and the station M once, relation (4) will be as follows:

e(SN t 4 A t 2 B t 1 M R RT , h d υ ) ? = e(RT , h).
In this way, the transport authority will be able to identify the users that left a pool of targeted stations but also the number of times they exited at these stations: this clearly implies that users' trips are linkable.

However, solving relation ( 4) and finding the right tuples (t x , j x ), becomes quickly a complex and unmanageable task when the number of targeted stations increased (more than three for example). To mitigate this, a malicious transport authority could only monitor two stations at the same time and periodically change these monitored stations. In this way, the transport authority will be able to monitor a large number of stations and will have a global overview of the users' journeys which breaks the privacy property of Rupp et al. system. We would like to emphasize that privacy holds in P4R if we assume that the transport authority is "honest but curious", i.e., it will not deviate from the refund protocol, but such an assumption is too strong in the context of transport systems [START_REF] Geuss | Japanese railway company plans to sell data from e-ticket records[END_REF].

In order to mitigate this issue, the user should check the received refund (Step (1) in Figure 5.1). This verification implies pairing computations. However, in constraint environments such as the SIM card, this is not feasible yet. A straightforward solution would be to delegate these computations to the smartphone. Such a solution, however, has two main drawbacks. On the one hand, delegating computations to an untrusted environment, i.e., the smartphone which could be compromised by spywares, will affect the user's privacy. On the other hand, verifying the received refund token would lead to inefficient transactions at exit turnstiles.

This attack shows how difficult is to construct an efficient protocol (validation time less than 300 ms) over a resource constrained device like the SIM card while ensuring the highest privacy level.

Architecture

In this section, we give the different entities of our public transport system. These entities are the same for both the m-pass and m-ticketing use cases. Then, we detail our architecture. Finally, we recall the main phases in a public transport service.

In our public transport system, i.e., m-pass or m-ticketing system, we consider three different entities. The user (U) is the owner of an NFC-enabled smartphone and wants to use the transport service via a transport application. The transport authority (TA) is the manager of the transport service. Besides these two entities, we consider a third actor which is a revocation authority (RA). It can revoke the transport products, i.e., mpass or m-ticket, and users' anonymity, and is completely independent of the transport authority. This role may be split between several authorities in such a way that they should all agree and cooperate before recovering a user's identity.

At the user's side, as shown in Figure 5.2, we consider an untrusted mobile platform (smartphone) with an incorporated trusted secure element. We use a SIM card as a tamper resistant secure element since it could be certified EAL4+ [START_REF]SIM Java Card Platform Protection Profile Basic and SCWS Configurations-Evolutive Certification Scheme for (U)SIM cards[END_REF]. Using a SIM card will ensure the integrity of the implementation. Indeed, the transport cardlet manages the cryptographic credentials of the transport application and executes required cryptographic computations. The main phases of a public transport service, i.e., m-pass service and m-ticketing service, are system initialization, user registration, product request and product validation.

• System initialization: during this phase, the transport authority initializes the public parameters and keys of the transport system.

• User registration: during this phase, the user will register himself to transport service.

• Product request: during this phase, the user will get his transport product from the transport authority, e.g., a monthly m-pass, a set of 10 m-tickets. if the transport system is functioning in a pre-payment way, the user must pay his product during this phase. Otherwise, the transport service operates in a post-payment way. In this case, the user will be charged later.

• Product validation: during this phase, the user has to interact with the validator in order to prove the authenticity of his transport product.

Trust Model

In this section, we informally describe the attacker model in a public transport service. We give more details in Chapter 6 with respect to the mobile pass use case and in Chapter 8 for the m-ticketing use case.

We assume that the attacker has full control over communication channels. He has the ability to compromise any user's smartphone, i.e., mobile operating system. Moreover, the attacker can compromise one or more users. In such a case, he can read / modify keys stored on or read / modify programs running within the SIM card of the corrupted user. However, we assume that he is not able to read / modify keys stored on or read / modify programs execution that take place within the SIM card of an uncorrupted user.

We also suppose that the attacker can compromise the transport authority but not the revocation authorities.

Conclusion

In this chapter, we presented the related work to transport system and showed, through the privacy attack against the Rupp et al. protocol, that it is not obvious to find the right balance between the user's privacy and the solution's efficiency. We also described our mobile platform architecture and recall the transport service phases. We informally defined the attacker model as well. This model will be formally and finely specified in Chapter 6 for the m-pass use case and in Chapter 7 for the m-ticketing use case.

In the next chapter, we introduce our m-pass solution together with its formal security analysis and performance results. Dans ce chapitre, nous présentons les résultats [START_REF] Arfaoui | A Privacy-Preserving NFC Mobile Pass for Transport Systems[END_REF] qui ont été publié dans la revue "ICST Trans. Mobile Communications Applications". Nous proposons un service mobile sans contact respectant la vie privée des utilisateurs: l'identité d'un utilisateur ne peut pas être liée à ses actions lors de l'utilisation du système de transport. Notre protocole est basé sur une variante de schéma de signature de groupe: les signatures Camenisch-Lysyanskaya. Même si un utilisateur est censé rester anonyme et ses actions intraçables, nous avons conçu une technique pour lever son anonymat dans des circonstances exceptionnelles. Nous avons également implémenté un prototype qui démontre que notre solution répond aux principales exigences fonctionnelles des systèmes de transport: à savoir que la validation d'un titre de transport doit s'effectuer en moins de 300 ms, et ce, même si la batterie du smartphone est épuisée. En outre, nous avons formellement validé la sécurité de notre protocole dans le modèle de l'oracle aléatoire.

Introduction

In this chapter, we propose a privacy-preserving contactless mobile pass solution, in which a user's identity cannot be linked to his trips when using the transport system. In particular, an eavesdropper and the transport provider are not able to track the journeys of the user. To achieve this objective, we have developed a privacy-preserving protocol for a contactless mobile pass, whose security is based on the combination of a secure element in a smartphone and on a privacy-enhancing cryptographic protocol. Even if a user should remain anonymous and his actions unlinkable in his daily journeys, we have designed a technique for lifting his anonymity in extreme circumstances. This exceptional procedure can be called for instance under the order of a judge, in case of a fraud or a murder. This chapter is organized as follows. At first, we detail the framework of our m-pass system in Section 6.2 and our protocol in Section 6.3. Then, we introduce our functional requirements and formalize the security and privacy requirements in Section 6.4. We show that our protocol meets the requirements, that we set previously, in Section 6.5. Finally, we give details about the performance results of our solutions in Section 6.6 and conclude this chapter in Section 6.7.

Framework of an M-Pass System

We model our m-pass system onto four phases. Besides the phases described in Section 5.6, we introduce a new phase called "revocation" phase.

First of all, the m-pass system parameters and keys are initialized during the System initialization phase. Then, the user registers to the transport service (user registration) and retrieves his m-pass credentials (product request) during the Registration phase. In the validation phase, the user proves his legitimacy to use the transport service without disclosing his identity. Finally, the revocation phase consists in revoking a user (i.e., retrieving a user's identity based on an anonymous m-pass) and revoking an m-pass (i.e., denying access to the transport service based on a user's identity).

Next, we model these phases with various algorithms and protocols (Figure 6.1) executed by the entities described in Section 5.6. In the m-pass protocol, we rename the revocation authorities by Opening authorities (OA).

System initialization

Setup(1 λ ): This probabilistic algorithm outputs pp, a description of the system parameters. We assume that pp are implicit to the other algorithms, and that they include λ, the security parameter. They are also an implicit input to the adversary, we will then omit them.

Keygen(pp): This probabilistic algorithm outputs the two following secret/public key pairs: (sk o , pk o ) for the opening authorities and (sk t , pk t ) for the transport authority.

The system public key gpk is eventually set as (pp, pk t , pk o ).

Registration

UKeygen(gpk, ID U ): This probabilistic algorithm outputs a secret key sk u for a user's identifier ID U .

Register(U(gpk, sk u , ID U ), OA(gpk, sk o , DB o )): This is an interactive protocol between a new user with his identifier ID U and his private key sk u , and the opening authorities that take on input its private key sk o and its secured database DB o where the user will be registered. If the user accepts the protocol, he gets a registration proof µ. If the opening authorities accept the protocol, the user's identity, i.e., his identifier and a commitment of his private key, will be stored within the database DB o .

GetMPass(U(gpk, sk u , µ), TA(gpk, sk t , DB t )): This is an interactive protocol between a registered user with his private key sk u and his registration proof µ, and the transport authority with its private key sk t and DB t . If the transport authority accepts the protocol, its output is a CL-certificate (A, B, C, D) and a commitment C 1 of the user's secret key sk u . C 1 and the user identifier are stored within the database DB t .

Validation

SignMPass(gpk, sk u , bsn, rc): This is a probabilistic algorithm that takes as input a registered user private key sk u , a time slot bsn and a random challenge rc. It outputs a signature σ.

VerifyMPass(gpk, σ, bsn, rc): This is a deterministic algorithm that outputs 0 if the signature σ with respect to bsn and rc is valid. Otherwise, it outputs ⊥.

Revocation

AntiPassBack(σ 1 , σ 2 ): This is a deterministic algorithm that takes on input two valid signatures σ 1 and σ 2 (which have been generated during the execution of the algorithm SignMPass). If σ 1 and σ 2 have been generated by the same user during the same time slot bsn, it outputs 0. Otherwise, it outputs ⊥.

IdentUser(σ, DB o , DB t ): This is a deterministic algorithm that takes as input a signature σ (which has been generated during the execution of the algorithm SignMPass), the secured database of the opening authorities DB o and the secured database of the transport authority DB t . It outputs the identifier ID U of the registered user who generated the signature σ. If the user who generated the signature σ is not registered, it outputs ⊥.

IdentMPass(C 1 , σ, bsn, rc): This is a deterministic algorithm that takes on input C 1 a commitment of sk u (a user's secret), a signature σ (which has been generated during the execution of the algorithm SignMPass), a time slot bsn, and a message rc. It outputs 0, if σ is a signature on bsn and rc, and corresponds to committed secret on C 1 . Otherwise, it outputs ⊥.

Untraceable Mobile Pass

The main idea of our solution is to use a DAA scheme in order to enable an enrolled user to be anonymous inside the group of other subscribers of the m-pass service. More precisely, our solution is based on the DAA scheme of Brickell et al. [START_REF] Brickell | Direct anonymous attestation[END_REF], which we adapted in order to handle revocation features. For the sake of simplicity in this section, we define our protocol by taking into account only one group of subscribers (e.g., subscribers for an m-pass valid in zone 1 of Paris.): the group of persons having an m-pass for using the public transport system. We treat the generic case of several groups later.

M-Pass Protocol

System initialization The transport authority considers two hash functions, H and H 1 , modeled as random oracles:

H : {0, 1} * → {0, 1} k , H 1 : {0, 1} * → G 1 .
Then, he picks up randomly a generator G 1 (respectively G 2 ) of G 1 (respectively G 2 ):

G 1 $ ← G 1 , G 2 $ ← G 2 .
The public parameters of the group are gpp such that:

gpp ← (G 1 , G 2 , G T , H, H 1 , e, G 1 , G 2 ).
(recall that e is a bilinear map and G T is a multiplicative cyclic group of order p, cf. Chapter 3). The transport authority generates his public and private keys (pk t , sk t ) to sign messages such that:

sk t ← (x, y) $ ← -Z p × Z p , pk t ← (X, Y ) ← ([x]G 2 , [y]G 2 ) .
Similarly, the opening authorities generate its public and private signature keys (pk o , sk o ) and its public and private Paillier encryption keys (pk p , sk p ) such that:

pk p ← (n, g p ) , sk p ← (a, b)
where a, b, n and g p are computed as in Section 3.4.3.2.

In consequence, the group public key pk g is set up such that: pk g = (gpp, pk t , pk o , pk p ) where gpp is the public parameters of the group. The keys pk t and pk o are used to verify signatures issued respectively by the transport authority and the opening authorities.

The key pk p is used for encryption.

Regarding the user, his private key sk u is the sum of two random secret values: s and s . s is randomly chosen by the m-pass cardlet from Z p . s is randomly chosen by the opening authorities from Z p then securely sent to the m-pass cardlet. In such a way, no computation in G 2 will be required to the cardlet (as the cardlet cannot do such computations). Moreover, neither the smartphone nor the Opening authorities have the user's private key. In Figure 6.2, we detail the generation protocol of a user's private key sk u . User registration During the registration phase, described in Figure 6.3, the m-pass cardlet establishes two secure channels with the opening and transport authorities.

Smartphone

← Z * p , s --- s $ ← Zp Compute: B 2 = [r 2 ]G 2 , C 2 = [s ]G 2 , c 2 = H(C 2 , B 2 ), s 2 = r 2 -c 2 s mod p, Π 2 = SOK(s : C 2 = [s ]G 2 ) = (c 2 , s 2 ) C 2 ,Π 2 ------ C 2 ,Π 2 ------ Compute: B 2 = [c 2 ]C 2 + [s ]G 2 If c 2 ? = H(C 2 , B 2 ) then, s $ ← Zp else abort. Compute: C 2 = [s ]G 2 , then, C 2 = C 2 + C 2 = [s ]G 2 + [s ]G 2 = [s + s ]G 2 Compute: C 2 ,s ----- = [sku]G 2 sku = s + s
First, the registration of the user to the opening authorities consists of two steps. (1) The m-pass cardlet computes a commitment C 1 on the private key sk u of the user and a signature of knowledge Π 1 proving the knowledge of the private key sk u used to compute C 1 . Then, it sends C 1 , C 2 , Π 1 along with B 1 (this value enable the verification of Π 1 ), to the opening authorities.

The opening authorities verify that these computations are correct. If this verification succeeds, it means that C 1 and C 2 are commitments on the same secret value (sk u here) known by the user. In this case, the opening authorities send back a signature µ of C 1 and stores the triplet (C 1 , C 2 , µ) in the database DB o , which has to remain private and secure.

(2) Then, upon receiving the signature µ, the m-pass cardlet sends C 1 , µ, C 0 (the Paillier encryption of the user's private key sk u ) and a signature of knowledge Π 1 proving that the user knows the secret encrypted in C 0 and used to compute C 1 , to the transport authority, which then checks the validity of the signature (using pk o ) and the proof. If the verifications are successful, the transport authority computes and sends a blind CL-certificate [START_REF] Camenisch | Signature schemes and anonymous credentials from bilinear maps[END_REF] (A, B, C, D) on the private key of the user (recall that CL-signature schemes allow a signature to be issued on messages that are not known to the signer, but to which the signer only knows a commitment). We would like to mention that for a given sk u , a user can have only one m-pass (one blind CL-certificate (A, B, C, D)

B 1 = [r]G 1 C 1 = [sku]G 1 c = H(C 1 , B 1 ) s = r -c skumod p Π 1 = SOK(sku : C 1 = [sku]G 1 ) = (c, s) C 1 ,C 2 ,Π 1 -------- Compute: B1 = [c]C 1 + [s]G 1 If c ? = H(C 1 , B 1 )
and e(C 1 , G 2 )

? = e(G 1 , C 2 ) Then Compute: µ = Signature(sko, C 1 ) µ -------- Store (C 1 , C 2 ,
C 0 = g sku p j n mod n 2 Π 1 = SOK(sku : C 1 = [sku]G 1 ∧ C 0 = g sku p j n mod n 2 ) C 0 ,C 1 ,µ,Π 1 ---------
If verify(pko, µ) and verify Π 1 Then Compute a signature on C 1 : The databases DB o and DB t will be used only for de-anonymizing or blacklisting of users as detailed later in Section "Countermeasures". Once the registration phase is completed, user's registration data are stored in both the transport and opening authorities databases. He is now allowed to use his m-pass application to access the transport service.

a $ ← -Zp A = [a]G 1 B = [y]A C = [x](A + D) D = [a.y]C 1 A,B,C,D --------- Store (user, C 1 ) in DBt

M-pass validation

The validation of the m-pass, described in Figure 6.4, is used by the user to prove that he is entitled to use the transport service without disclosing his identity. The process is split into two parts: the first part (called precomputation in Figure 6.4) can be performed in advance (before the actual validation) while the second part (called m-pass validation in Figure 6.4) should be done during the validation itself at the gate.

When the validation at the gate occurs, the validator sends a random challenge rc and a time slot bsn to the m-pass cardlet that will respond with a DAA σ on these ,S,T,W,K,c,Compute: challenges. The bsn message is constant during a fixed period of time (typically 5 minutes) and enables the implementation of the anti-pass back feature described in Section "Countermeasures". During the validation phase, the m-pass cardlet has very few computations to perform, only the ones that involve the secret key sk u , the basename bsn and the challenge rc. The m-cardlet first computes J = H 1 (bsn) and a commitment K on sk u with respect to the base J: K = [sk u ]J. It then computes a signature of knowledge (c, s) proving that it knows the discrete logarithm of K with respect to the base J. Afterwards, it communicates the DAA signature σ on rc and bsn to the gate. This DAA σ consists of a randomized CL-certificate (R, S, T, W ), pre-computed by the m-pass application, along with J, K, c, and s. Roughly speaking, the DAA signature σ is a signature of knowledge (cf. Section 3.2.3.3) on rc and bsn, proving that (R, S, T, W ) is a CL-certificate on the secret value committed in K and that the m-pass cardlet knows this committed value. Then, the validator verifies that the signature σ is valid and is not blacklisted. If the verification is successful, the validator grants access to the user to the transport network.

$ ← Zp Compute: R = [l]A, S = [l]B, T = [l]C and W = [l]D k $ ← Zp Compute: R2 = [k]S M-pass validation Compute: rc, bsn ----------- rc $ ← {0, 1} γ J = H1(bsn) R1 = [k]J K = [sku]J c = H(J, K, R, S, T, W, R1, R2, rc) s = k + c.sku modp σ=(R
J = H1(bsn) R1 = [s]J -[c]K, R2 = [s]S -[c]W Verify: e(R
Groups A group of users is defined by a group public key pk g . We suggest to regularly update this key to ensure that it has only a limited validity period. Indeed, the users have to update their CL-certificate every time the group public key is updated. A user, who did not update his certificate accordingly, will not any more be considered as a member of the group and thus will not be able to generate a valid signature during the validation phase. Moreover, by regularly updating the group public key, we limit the size of the blacklist containing the revoked m-passes.

For the sake of simplicity, we have considered so far a single group of users (i.e., a unique group public key), in order to distinguish a legitimate user from an illegal one.

In practice, we have to distinguish different kinds of m-passes and consequently different groups of users. A m-pass is often characterized by its type (e.g., student, senior, disabled) and its fare zones (i.e., holders of such fare zone are entitled to travel on.). Thus, potentially a validator gate may embed several group public keys. For example, in the situation in which three groups of users exist: {student, fare zone 1-2}, {student, fare zone 1-5} and {student, fare zone 2-3}, a validator located in a zone 3 station will accept the users of the groups {student, fare zone 1-5} and {student, fare zone 2-3}. Thus, in order to verify the validity of all types of m-passes, a validator may have to store several group public keys.

If the number of groups is huge, storing their respective group public keys will be quite inefficient. We therefore propose that, during the validation phase, the m-pass cardlet sends to the validator the group it belongs to. In this way, the verification time will be constant even if the number of group public keys is large.

Countermeasures

In order to ensure the security of our privacy-preserving m-pass solution, we provide, in this section, an "anti-passback" feature prohibiting consecutive uses of the same m-pass in the same place and during a given period of time, a "de-anonymization" protocol to retrieve the identity of a user in case of emergency or fraud as well as a revocation solution which allows to revoke m-passes.

Anti-passback The anti-passback feature of a transport service denies the access to a user that has already used the m-pass during the previous minutes or seconds depending on how the system is configured. For example, the entrance gate should deny the access if two users try to enter consecutively using the same transport pass.

During the validation phase, the validator stores the signature σ 1 for a time slot bsn. If the user tries to re-use his m-pass during this time slot, the m-pass cardlet will compute and send a new signature σ 2 . The validator is able to detect that σ 1 and σ 2 are computed by the same m-pass cardlet by comparing the two parameters K of the signatures σ 1 and σ 2 . If they are the same, this means that the two signatures σ 1 and σ 2 originate from the same m-pass cardlet.

When the gate changes the value of bsn, two DAA signatures cannot be linked any more using K. Thus, renewing bsn frequently is mandatory in order to guarantee that the actions of users cannot be linked by the transport authority.

De-anonymization The de-anonymization procedure, described in Figure 6.5, is an implementation of the algorithm IdentUser. It allows the transport authority to identify the m-pass (and consequently the holder of this pass) that has generated a particular signature. For instance, in case of a fraud, the logs contained in a gate can be used to identify the corresponding malicious users. Of course the transport authority cannot de-anonymize users on his own, which would otherwise harm their privacy. Thus, the revocation of the anonymity of a signature cannot be done without the consent and the cooperation of the opening authorities.

First, the transport authority sends the targeted signature σ = (R, S, T, W, J, K, c, s) to the opening authorities. Based on this signature and the secret database DB o , the opening authorities search for the triplet (C 1 , C 2 , µ) such that e(J, C 2 ) matches with e(K, G 2 ). If the equality holds, this means that C 2 and K are two commitments on the same secret value (i.e., sk u in this case). Then, it replies with the corresponding C 1 . Finally, based on the database DB t and the received C 1 , the transport authority finds out the identity of the user ID user .

Blacklist management

The blacklisting procedure, described in Figure 6.6, uses the IdentMPass algorithm. It allows the transport authority to revoke an m-pass such that it cannot access anymore to the transport service. For example, a user that has lost his smartphone can ask the transport authority to blacklist his m-pass, or in case of a fraud the de-anonymized m-pass can be blacklisted by the transport authority.

If the transport authority wants to exclude a user, the authority seeks for the relevant commitment, C 1 , of the user in the database DB t and sends it to the opening authorities. Upon receiving C 1 , the opening authorities retrieve the corresponding commitment C 2 and computes (for all bsn starting from the time the m-pass has been blacklisted): e(H 1 (bsn), C 2 ). The number of values e(H 1 (bsn), C 2 ) computed could appear to be large, but it stays limited as we propose to renew regularly the group public keys to implement the validity duration of all m-passes. Thus, depending on the frequency of changes of bsn and of group public keys, the size of the computed set can vary.

Finally, the set of computed values e(H 1 (bsn), C 2 ) is sent back to the transport authority that forwards it to all the validators of the transport system. Thus during the validation phase, the validator will receive a signature σ = (R, S, T, W, J, K, c, s) from an m-pass. It will check the validity of the signature and that the m-pass is not blacklisted. To this end, the validator will check whether e(K, G 2 ) matches with one of the computed values e(H 1 (bsn), C 2 ). If the equality holds, this means that C 2 and K are two commitments on the same secret value (i.e., sk u in our context), and thus the user is blacklisted and the validator denies access to this user. The validator will then typically send a specific message to the m-pass cardlet to lock it. Clearly, this locking message has to be authenticated to thwart denial-of-service attacks. ---------∀bsn, Compute e(H1(bsn), C2) such that e(K, G2) = e(H1(bsn), C2), the validator denies the access to the user.

Requirements

We consider three types of requirements: functional requirements which are "efficiency" and "versatility", security requirements which consist in "correctness", "traceability" and "Non-frameability", and privacy requirements which comprises "unlinkability".

Functional Requirements

Efficiency An m-pass systems must fulfill functional requirements imposed by transport operators [7], in particular the validation of an m-pass must be performed in less than 300ms. We must consider that a SIM card has limited computation capabilities. In particular, pairing APIs are not available on current SIM cards.

Versatility The user smartphone and the validator cannot be assumed to be connected to a back-end server during the validation phase. This enables the user to use his m-pass in any kind of situation, especially in areas with low connectivity, e.g., underground, or if the battery of his mobile is flat.

Security and Privacy Model

We formally define the security and privacy properties (except the correctness property) of our m-pass protocol in which the attack capabilities of a probabilistic polynomial time adversary A are modeled by providing him access to some oracles. In the sequel, HU will denote the set of honest users and MU the set of corrupted users. We assume that A receives all the exchanged messages in our system. A acts as an active adversary as regards to the messages issued by malicious users and as a passive adversary with respect to honest users.

ORegister HU is an oracle that will be used by an adversary in order to register honest users. By calling this oracle with ID U as argument, the adversary adds a new user. The oracle runs sk u ← UKeygen(gpk, ID U ) and adds ID U to the set HU. The private key sk u is kept secret and a commitment of sk u is returned to the adversary.

ORegister M U is an oracle that will be used by an adversary in order to register malicious users. The adversary calls this oracle with argument the identifier ID U of a user and sets his private key to sk u . The identity ID U is added to the set MU.

OCorruptU ser(ID U ) is a user secret key oracle enabling the adversary to obtain the private key sk u of a user ID U ∈ HU. The oracle sends sk u to A.

OGetM P ass U is an oracle that runs the user's side in the GetMPass protocol. This oracle will be used by an adversary playing the role of a malicious TA. The adversary gives to the oracle an identity ID U of an honest registered user. If the user accepts the protocol, the adversary gets a CL-certificate of the user.

OGetM P ass T is an oracle that runs the transport authority side in the GetMPass protocol. This oracle will be used to simulate the execution of the protocol between a user (corrupted or not) and an honest TA.

OSignM P ass(ID U , bsn, rc) is an oracle that takes as input the identifier ID U of an honest and registered user (he has one valid CL-certificate), a fresh time slot bsn and a challenge rc, and outputs a signature σ on bsn and rc. The oracle records (ID U , σ, bsn, rc) in a list Set.

OIdentU ser(σ) is an oracle that takes on input a signature σ and outputs the identifier ID U of the user who generated the signature σ.

OIdentM P ass(C 1 , σ, bsn, rc) is an oracle that takes on input C 1 a commitment of sk u (a user's secret, a valid signature σ (which has been generated during the execution of the algorithm SignMPass), a time slot bsn and a message rc. It indicates whether the signature has been generated on bsn and rc, and using the committed secret on C 1 .

Correctness Informally speaking, our protocol is correct if (1) a valid m-pass enables to generate valid signatures, (2) honestly generated signatures are accepted, (3) a validated signature enables opening authorities to identify the user who generated it, (4) opening authorities can link all the signature generated by a given registered user that obtained a valid m-pass, and (5) valid signatures generated by the same user during the same time slot bsn are linkable.

Unlinkability Informally speaking, it should be impossible, except for the opening authorities, to track an m-pass obtained by a user, in particular, to distinguish which of users produced a given signature for every bsn to link two signatures validated by the same user. For this, an adversary has full control over the transport authority (in particular it owns the private key sk t ) and all the users except two honest users i 0 and i 1 . The adversary can initiate the IdentUser protocol over any signature and can get the user's identity behind it, except for the signatures generated by i 0 and i 1 . He can also initiate the IdentMPass protocol for all the users except for i 0 and i 1 . We define the unlinkability experiment Exp unlink A (1 λ ) in Figure 6.7. The scheme is unlinkable if for any probabilistic polynomial time adversary A, the advantage Adv unlink-b

A (1 λ ) = |P r[Exp unlink-b A (1 λ ) = b] -1/2| is negligible.

Traceability

Informally speaking, it should be impossible for anyone to validate an m-pass, i.e., generate a valid signature σ, such that the algorithm IdentUser returns ⊥, i.e., an identifier ID U that doesn't appear in the transport authority database DB t . We formally define the traceability experiment Exp trac A (1 λ ) in Figure 6.8. The scheme is traceable if for any probabilistic polynomial time adversary A, the probability Pr[Exp trac A (1 λ ) = 1] is negligible.

Exp trac A (1 λ ) 1. pp ← Setup(1 λ ); HU ← ∅; MU ← ∅ 2.
(gpk, skt, sko) ← Keygen(pp)

3. (σ, bsn, rc) ← A(gpk: ORegister HU , ORegister M U , OCorruptU ser, OGetM P ass T ).

4. If VerifyMPass(gpk, σ, bsn, rc) =⊥ then return 0.

5. If IdentUser(σ, DBo, DBt) =⊥ return 1 else return 0.

Figure 6.8: Traceability Security Experiment

Non-Frameability Informally speaking, it should be impossible for anyone to falsely accuse a honest user of having used his m-pass. We formally define the non-frameability experiment Exp N f ra A (1 λ ) in Figure 6.9. The scheme is non-frameable, if for any probabilistic polynomial time adversary A, the probability

Pr[Exp N f ra A (1 λ )=1] is negligible. Exp N f ra A (1 λ ) 1. pp ← Setup(1 λ ); HU ← ∅; MU ← ∅; Set ← ∅

Security Analysis

We prove that our m-pass protocol provides the security and privacy properties defined in Section 6.4.

Forking Lemma. We use the Forking Lemma [START_REF] Pointcheval | Security arguments for digital signatures and blind signatures[END_REF] in our proofs, to prove that an adversary A is not able to produce a new valid signature σ (see Figure 6.4) unless he knows the secret sk u corresponding to the valid CL-certificate (R, S, T , W ) and the discrete logarithm of K in the base J.

Using the notation of [START_REF] Pointcheval | Security arguments for digital signatures and blind signatures[END_REF], if an adversary is able to produce a valid signature σ (rc, bsn, σ 1 , h, σ 2 ) where

σ 1 = (J, K, R, S, T , W , R 1 , R 2 , rc), h = H(J, K, R, S, T , W , R 1 , R 2 , rc)
, and σ 2 = s then an adversary A can produce two valid signatures (rc, bsn, σ 1 , h, σ 2 ) and (rc, bsn, σ 1 , h , σ 2 ) such that h = h .

Theorem 3 (Unlinkability). Our m-pass protocol satisfies the unlinkability requirement, in the random oracle model, under the XDH assumption.

Proof 3 (sketch). We give a security proof as a sequence of games, using Shoup's methodology [START_REF] Shoup | Sequences of games: a tool for taming complexity in security proofs[END_REF]. We will only give a high-level description of the initial game (Game 0) and brief descriptions of the modifications between successive games.

Game 0: This is the original attack game with respect to a given efficient adversary A.

The Challenger C can construct the public parameter gpp for A. It also chooses the keys for the Paillier encryption scheme and the ones for the transport and opening authorities.

C sends gpp and sk t to A and answer his requests as follows:

• ORegister HU requests: the Challenger C randomly chooses sk u ∈ Z * p , computes

C 1 = [sk u ]G 1 and, C 2 = [sk u ]G 2 , returns (C 1 , µ) to the adversary A and stores (C 1 , C 2 = [sk u ]G 2 , µ) in DB o .
• ORegister M U requests: C randomly chooses s ∈ Z * p and sends it to A along with a signature µ on the commitment

C 1 = [s + s ]G 1 provided by A (where s is a secret value chosen by A). C stores (C 1 , C 2 = [s + s ]G 2 , µ) in DB o .
• OCorruptU ser requests: the Challenger C retrieves sk u and gives it to A.

• OGetM P ass U requests: C retrieves sk u and proceeds normally to obtain a certificate on sk u

• OSignM P ass requests: the Challenger C has all the values (sk u , A, B, C, D) that has been issued in OGetM P ass U / ORegister HU requests. Therefore, C can generate signatures on any bsn and rc.

• OIdentU ser(σ) requests: the Challenger C uses the algorithm IdentUser to identify the user who generated σ.

• OIdentM P ass(C 1 , σ, bsn, rc) requests: the Challenger uses the algorithm IdentMPass to determine whether σ has been generated using the committed secret in C 1 or not.

Challenge phase:

The adversary A outputs two honest users (i 0 , i 1 ), a message rc, and a basename bsn. C randomly chooses a value b from {0, 1} and issues a valid signature σ b on rc and bsn on behalf of i b . The goal of A is to guess the value b. After having received its challenge, A can query ORegister HU , ORegister M U , OCorruptU ser, OGetM P ass U , OSignM P ass, OIdentU ser and OIdentM P ass but with the following restrictions: it cannot query:

• the OCorruptU ser oracle on i 0 or i 1 ,

• OSignM P ass oracle on i 0 or i 1 ,

• OIdentU ser oracle on σ b ,

• OIdentM P ass oracle on (i 0 , σ b , bsn, rc) or (i 1 , σ b , bsn, rc)

At the end of the game, the adversary A outputs a bit b , its guess. Let S 0 be the event that b = b in this game and S i the event that b = b in the game i. We have,

|P r[S 0 ] -1/2| = Adv unlink-b A = |P r[Exp unlink-b A (1 λ )] -1/2|
Game 1: this game is the same as Game 0 except that we replace the value K = [sk i b ]J in the signature σ b by a random value of the group G 1 and simulate the "signature of knowledge" σ b . Such a simulated proof can be easily done in the random oracle model using standard techniques. Under the XDH assumption, the adversary A cannot detect this change. Indeed, we can easily construct an XDH distinguisher D, as proven below in Claim 1 (further details about Claim 1 are given after the unlinkability proof), with XDH-advantage satisfying:

|P r[S 0 ] -P r[S 1 ]| q H × q R × Adv XDH D (1 λ ) (1)
where Adv XDH D (1 λ ) is the XDH-advantage of D in solving the XDH problem and q H (respectively q R ) a bound on the number of hash queries (respectively ORegister HU requests). In the sequel, we will use the simplified notation Adv XDH to denote the XDH-advantage of some efficient algorithm in solving the XDH problem.

Game 2: This is the same game as Game 1 except that we replace the CL-certificate (R, S, T , W ) on sk i b by a CL-certificate on a random value and then simulate the "signature of knowledge" σ b . Such a simulated proof can easily be done in the random oracle model using standard techniques. Under the XDH assumption, A cannot detect this change. Indeed, we can easily construct an XDH distinguisher D, as proven below in Claim 2 (further details about Claim 2 are given after the unlinkability proof), with XDH-advantage satisfying:

|P r[S 1 ] -P r[S 2 ]| q R × Adv XDH (2)
In the Game(2), the unlinkability-challenger C gives no information (in a strong information theoretic sense) to A about the bit b (since the CL-certificate and the "tag" K have been replaced by random values). Therefore we have: P r[S 2 ] = 1/2

We can now give an upper bound for Adv unlink-b A (1 λ ):

Adv unlink-b A (1 λ ) = |P r[Exp unlink-b A (1 λ )] -1/2| = |P r[S 0 ] -P r[S 2 ]| We have: |P r[S 0 ] -P r[S 2 ]| = Σ j=1 j=0 |P r[S j ] -P r[S j+1 ]| ≤ q H × (q R + 1) Adv XDH Therefore under the XDH assumption Adv unlink-b A (1 λ ) is negligible.
We can then conclude that our proposed m-pass protocol satisfies the unlinkability requirement, in the random oracle model, under the XDH assumption.

Claim 1: |P r[S 0 ] -P r[S 1 ]| ≤ q H × q R × Adv XDH
Proof of Claim 1 (sketch): let A be an adversary who breaks the unlinkability requirement of our m-pass protocol with non-negligible advantage. We will construct an algorithm D, using A as an oracle, which solves the XDH problem. Let X be D's challenger in the XDH-game. X selects a bit d and sends to D an XDH-triplet if d = 1 and a random one if

d = 0. Let (G 1 , A = [a]G 1 , B = [b]G 1 , C = [c]G 1 )∈ G 4
1 be D's XDHchallenge. D has to decide whether d = 1 (i.e. c ≡ ab mod p) or not. D first defines the public parameters gpp of the m-pass protocol from the ones of the XDH-challenge, where H and H 1 are random oracles under the control of D. D also chooses the keys for the Paillier encryption scheme and the ones for the transport and opening authorities. D randomly selects i * in [1; q R ] and j * in [1; q H ]. D sends gpp and sk t to A and answers its requests as follows:

• ORegister HU requests: for the i-th request, D will acts as follows:

1. if i = i * , then it randomly chooses sk u ∈ Z * p , computes C 1 = [sk u ]G 1 and, C 2 = [sk u ]G 2 , returns (C 1 , µ) to the adversary A and stores (C 1 , C 2 = [sk u ]G 2 , µ) in DB o . 2. if i = i * , D randomly chooses α and β in Z * p , computes C 1 = [αa]G 1 + [β]G 1 = [αa + β]G 1 (
where [a]G 1 comes from the XDH challenge) and returns (C 1 , µ) to the adversary A.

• ORegister M U requests: D randomly chooses s ∈ Z * p and sends it to A along with a signature µ on the commitment

C 1 = [s + s ]G 1 provided by A (where s is a secret value chosen by A). D stores (C 1 , C 2 = [s + s ]G 2 , µ) in DB o .
• OCorruptU ser requests: if ID U i = ID U i * , D retrieves sk u i and gives it to the adversary A and aborts otherwise.

• OGetM P ass U requests: if

ID U i = ID U i * , D
(bsn) = [b]G 1 + [γ]G 1 = [b + γ]G 1
, where [b]G 1 comes from the XDH challenge. If bsn has already been queried then D returns the same output as the first request.

• OSignM P ass requests: upon receiving a query on (ID U , rc, bsn), D proceeds as usual if ID U i = ID U i * , else we distinguish the two following cases:

1. If bsn is the one that was requested in the j * -th hash request then D aborts.

2. Else, it chooses a fresh value δ ∈ Z * p (if bsn has not already been queried), computes

H 1 (bsn) = [δ]G 1 and K=[δ]C 1 =[δ(αa + β)]G 1 .
D simulates the signature of knowledge σ (which is possible in the random oracle model), outputs σ and stores (σ, rc, bsn) in Set.

• OIdentU ser(σ) requests: upon receiving a query on (σ, rc, bsn), D checks if (σ, rc, bsn) belongs to Set. If so, it returns ID U i * . Else it uses the IdentUser algorithm, to identify the user who generated σ.

• OIdentM P ass(C 1 , σ, bsn, rc) requests: D checks if (σ, rc, bsn) belongs to Set. If so, it returns "1" to A, which means that the signature comes from ID U i * .

Otherwise, it uses the algorithm IdentMPass to determine whether σ has been generated using the committed secret on C 1 or not.

Challenge phase: A outputs two honest identities ID i 0 and ID i 1 , a message rc and a basename bsn. If a hash request on this basename was already submitted during the j-th request then D aborts if j = j * . D randomly selects a bit b and aborts if

ID i b = ID U i * .
Else, it issues a signature σ b on rc and bsn on behalf of i b as follows: if no hash request was submitted on bsn, then it selects γ ∈ Z * p and outputs

H 1 (bsn) = [b]G 1 + [γ]G 1 = [b + γ]G 1 . It randomly chooses l ∈ Z * p to randomize the blind CL-certificate (A, B, C, D) on C 1 = [αa + β]G 1 : (R = [l]A, S = [l]B, T = [l]C, W = [l]D). It then computes K = [α]C + [β]B + [αγ]A + [βγ
]G 1 and simulates the "signature of knowledge" σ b = (R, S, T , W , K). Note that if c ≡ ab mod p, the signature σ b issued by D in the challenge phase is indistinguishable from an original one; else it is a random one.

After the Challenge phase, D proceeds as in the previous phase. At the end of the game, the adversary outputs a bit b , its guess. If b = b, then D returns 1 to X and 0 otherwise. Let F be the event that D did not abort. We have

P r[d = 1/d = 1] = P r[S 0 ∧ F ] and P r[d = 1/d = 0] = P r[S 1 ∧ F ] therefore: |P r[S 0 ] -P r[S 1 ]| ≤ q H × q R × Adv XDH D (1 λ ) Claim 2: |P r[S 1 ] -P r[S 2 ]| q R × Adv XDH
Proof of Claim 2 (sketch): the proof is similar to the proof of Claim 1; only the construction of the signature σ b differs in the two proofs. We will construct an algorithm D, using A as an oracle, which solves the XDH problem. Here again, let us denote by X D's challenger in the XDH-game and by (G

1 , A = [a]G 1 , B = [b]G 1 , C = [c]G 1 )∈ G 4
1 its XDH-challenge. D has to decide whether d = 1 (i.e. c ≡ ab mod p) or not. D first defines the public parameters gpp of the m-pass protocol from the ones of the XDH-challenge, where H and H 1 are random oracles under the control of D. D also chooses the keys for the Paillier encryption scheme and the ones for the transport and opening authorities. In particular, D knows sk t = (x, y) the private key of the transport authority. Let q R be a bound on the number of ORegister HU requests. D randomly selects i * in [1; q R ], sends gpp and sk t to A, and answers its requests as follows:

• ORegister HU requests: for the i-th request, D will acts as follows:

1. if i = i * , then it randomly chooses sk u ∈ Z * p , computes C 1 = [sk u ]G 1 and, C 2 = [sk u ]G 2 , returns (C 1 , µ) to the adversary A and stores (C 1 , C 2 = [sk u ]G 2 , µ) in DB o . 2. if i = i * , D randomly chooses α and β in Z * p , computes C 1 = [αa]G 1 + [β]G 1 = [αa + β]G 1 (
where [a]G 1 comes from the XDH challenge) and returns (C 1 , µ) to the adversary A.

• ORegister M U requests: D randomly chooses s ∈ Z * p and sends it to A along with a signature µ on the commitment

C 1 = [s + s ]G 1 provided by A (where s is a secret value chosen by A). D stores (C 1 , C 2 = [s + s ]G 2 , µ) in DB o .
• OCorruptU ser requests: if ID U i = ID U i * , D retrieves sk u i and gives it to the adversary A and aborts otherwise.

• OGetM P ass U requests: if ID U i = ID U i * , D retrieves sk u i and proceeds normally to obtain a certificate on sk u i . Else, it randomly chooses a value C 0 ∈ Z n 2 and simulates the proof Π 1 (this is possible in the random oracle model) and obtains a blind CL-certificate (A, B, C, D) on

C 1 = [αa + β]G 1 .
• Hash requests: upon receiving the j-th request on bsn, D proceeds as follows: if no previous request was made on bsn, then D selects δ ∈ Z * p and outputs H 1 (bsn) = [δ]G 1 . If bsn has already been queried then D returns the same output as the first request.

• OSignM P ass requests: upon receiving a query on (ID U , rc, bsn), D proceeds as usual if

ID U i = ID U i * , else, if bsn has not been queried, it chooses a fresh value δ ∈ Z * p , computes H 1 (bsn) = [δ]G 1 and K=[δ]C 1 =[δ(αa + β)]G 1 .
D simulates the signature of knowledge σ (which is possible in the random oracle model), outputs σ and stores (σ, rc, bsn) in Set.

• OIdentU ser(σ) requests: upon receiving a query on (σ, rc, bsn), D checks if (σ, rc, bsn) belongs to Set. If so, it returns ID U i * . Else, it uses the IdentUser algorithm, to identify the user who generated σ.

• OIdentM P ass(C 1 , σ, bsn, rc) requests: D checks if (σ, rc, bsn, rc) belongs to Set. If so, it returns "1" to A, which means that the signature comes from ID U i * .

Otherwise, it uses the algorithm IdentMPass to determine whether σ has been generated using the committed secret in C 1 or not. ). It then randomly chooses K in the group G 1 and simulates the "signature of knowledge" σ b = (R, S, T , W , K). Note that if c ≡ ab mod p, the blind CL-certificate (R, S, T , W ) on C 1 issued by D in the challenge phase is indistinguishable from an original one; else it is a CL-certificate on a random one.

After the Challenge phase, D proceeds as in the previous phase. At the end of the game, the adversary outputs a bit b , its guess. If b = b, then D returns 1 to X and 0 otherwise. Let F be the event that D did not abort. We have

P r[F ] ≥ 1/q R
We also have:

P r[d = 1/d = 1] = P r[S 1 ∧ F ] and P r[d = 1/d = 0] = P r[S 2 ∧ F ] therefore: |P r[S 1 ] -P r[S 2 ]| ≤ q R × Adv XDH D (1 λ )
Theorem 4 (Traceability). Our m-pass protocol satisfies the traceability requirement, in the random oracle model, under the LRSW assumption.

Proof 4 (sketch). Let C be the Challenger of the adversary A in the traceability experiment. C will use A to break the LRSW assumption. The Challenger C has access to a CL-certificate oracle. The Challenger has on input the public key of transport authority pk t . C chooses also the keys for Paillier encryption scheme. It can, then, construct the public parameters gpp for A and answer the requests of the adversary A as follows:

• ORegister HU requests: the Challenger C randomly chooses sk u and computes

C 1 = [sk u ]G 1 , and C 2 = [sk u ]G 2 .
• ORegister M U requests: the Challenger C randomly chooses s and sends this value to A. It then sends a signature µ on the value C 1 provided by A.

• OCorruptU ser requests: C gives sk u to the adversary A.

• OGetM P ass T requests: if ID U ∈ HU, C retrieves sk u . If ID U ∈ MU, C decrypts C 0 and retrieves sk u . The Challenger C then calls the CL-certificate oracle with the input sk u . The CL-certificate oracle returns (A, B, C, D). C gives (A, B, C, D) to the adversary.

• OSignM P ass requests: the Challenger C has all the values (sk u , A, B, C, D) that has been issued in ORegister HU / OGetM P ass T requests. Therefore, C can generate signatures on any bsn and rc.

Eventually, the adversary A outputs a valid signature σ = ( R, S, T , W , K, c, s) on a challenge rc and a basename bsn such that the algorithm IdentUser on σ does not return an ID of a registered user (ID does not match with the databases DB t , DB o ), and consequently, the CL-certificate ( R, S, T , W ) certifies an unknown value sk u that has not been requested to the CL-certificate oracle Using the Forking Lemma, the replay technique and the soundness property, the Challenger can extract sk u from σ, and ( R, S, T , W ) is a valid CL-certificate on sk u . This is a forgery because the value sk u has (by definition) never been asked to the CL-certificate oracle. Thus, C breaks the LRSW assumption.

Therefore, our m-pass protocol is traceable under the LRSW assumption.

Theorem 5 (Non-Frameability). Our m-pass protocol satisfies the non-frameability requirement, in the random oracle model, under the SDL assumption.

Proof 5 (sketch). Let A be an adversary against the non-frameability requirement. We construct a reduction C using A against SDL problem challenges.

Let (G 1 , C1 = [s]G 1 , G 2 , C2 = [s]G 2 )
be the SDL challenge. The Challenger C must output s.

Let q R be the bound on the number of ORegister HU requests.

C selects i * ∈ [1, q R ],
construct the public parameters gpp for A as in the initialisation phase, and answers its queries as follows.

A chooses the keys for the opening and transport authorities.

• ORegister HU requests: when A makes the i th ORegister HU query to register a user, C will run the user's private key generation protocol with a fresh value s if i = i * . When i = i * , C sets C 2 = C2 and simulates the proof Π 2 (this is possible in the random oracle model). It then computes

C 2 = C2 + [s ]G 2 =[s + s ]G 2 where s is provided by A. Let C 1 = C1 + [s ]G 1 .
C simulates the proof Π 1 and obtains from A a signature µ.

• ORegister M U requests: C does not need to do anything.

• OCorruptU ser requests: C returns the corresponding sk u of the user ID U i if i = i * and aborts otherwise.

• OGetM P ass U requests: C acts normally if ID U i = ID U i * . Otherwise, it randomly chooses C 0 , simulates the non-interactive proof Π 1 , and obtains from A a valid CL-certificate (A, B, C, D) on sk u = s + s .

• OSignM P ass(ID U , bsn, rc) requests: the challenger C acts normally if

ID U i = ID U i * . Otherwise, C picks a random value β in Z * p , computes J = H 1 (bsn) = [β]G 1 (this is possible in the random oracle model), and then K = [β]C 1 = [β(s + s )]G 1 = sk u J. C then simulates the non-interactive proof σ.
Eventually, the adversary A outputs a valid signature σ = ( R,S,T ,W ,K,c,s)) on a challenge rc and a basename b sn such that:

• the algorithm IdentUser on σ returns an an identifier Ĩ D U ∈ HU, and

• the oracle OSignM P ass has not been called to generate this signature,

If Ĩ D U = ID U i * then C aborts.
Using the Forking Lemma, the replay technique and the soundness property, the Challenger can extract sk u from σ. As sk u = s + s mod p, s = sk u -s mod p. C is then able to solve the SDL problem since it will not abort with a probability 1/q R . Therefore, our m-pass protocol is non-frameable under the SDL assumption.

Implementation

In this section, we describe the prototype implementing our mobile pass system. The software components involved in the transport service are represented in Figure 5.2. The validator is simulated by a Java swing application connected to an NFC reader using the ISO14443B protocol. The cardlet is embedded within a SIM card. We used a regular Galaxy S3 smartphone running Android 4.1.2. The Android system does not need any modification as the Seek for Android patch [START_REF]Seek for Android[END_REF] has been already added by Samsung in order to access secure elements. In the following, we give more technical details about the validator and the SIM card, the used cryptographic parameters, and the performance results as well.

Validator Details

The validator has been developed over a PC, i.e., an Intel(R) Xeon(R) with a E5-1620 CPU with 4 cores running at 3.70GHz under a 64-bit Linux OS, in Java and Scala.

The Java software uses a native library for EC scalar multiplications and pairings. This library depends on libGMP for big integers computations and benefits from its assembly optimizations. Furthermore, computations are distributed between threads (at JVM level) to benefit from the multi-core architecture of the PC. Regarding the NFC reader of the validator, we used is an Omnikey 5321 dual interfaces.

SIM Card Details

The SIM card handles requests from the validator using the NFC contactless interface.

Our SIM card is compliant with

• Global Platform Card specifications version 2.2.1,
• Javacard version 2.2.2 and

• Javacard virtual machine version 3.0.1 classic.

Those features allow to develop Java Card Applets so-called cardlets, to load them on the SIM Card and to execute them thanks to the Java Card virtual machine. In order to provide a very efficient signature computation, we chose a SIM Card equipped with an arithmetic coprocessor. Thanks to this latter, we were able to meet the timing performances required by the transport operators (typically less than 300 ms), by offering non standardized Java Card APIs to the transport cardlet. Those APIs allow to compute efficiently:

• modular operations on large integers like addition, subtraction, multiplication, exponentiation, etc.,

• arithmetic operations on elliptic curves like scalar multiplication and point addition.

Those customized APIs are mapped to assembly subroutines that drive the arithmetic co-processor directly.

Curve and Pairing Parameters

We used a 256-bit Barreto-Naehrig curve [104] over F q since this family of curves provides an optimal size for G 1 and G 2 while preventing the MOV attack [START_REF] Menezes | Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field[END_REF] due to their embedding degree of 12. G 1 is the group of F q -rational points of order p and G 2 is the subgroup of trace zero points in E(F q 12 )[p]. Our pairing is of type-3 [START_REF] Galbraith | Pairings for cryptographers[END_REF].

The curve and pairing parameters that we used in the implementation of our protocols are:

q = 82434016654300907520574040983783682039467282927996130024655912292889294264593 p = 82434016654300907520574040983783682039180169680906587136896645255465309139857 b = 5

Performance Results

The validation of an m-pass occurs in two phases: pre-computations and real-time computations. The pre-computations consists in randomizing the CL-certificate (A, B, C, D). Regarding the real-time computations, it occurs when the user taps the validator with his smartphone. After detecting the smartphone and selecting the m-pass cardlet, the validator sends the basename bsn and the challenge rc to the m-pass cardlet. The signature, computed by the cardlet, is sent back to the validator that checks it and displays the result.

Pre-Computations

Some pre-computations operations are delegated to the transport application within the smartphone after receiving A, B, C and D from the cardlet. The smartphone application then generates a pool of pre-computed tokens by multiplying each variable A, B, C and D by a random l. Then, the pool of generated tokens is sent back to the cardlet.

1 signature 20 signatures 175 ms 3.47 s Table 6.1: M-Pass Pre-Computation Timings

The elements that the card has to store for one signature are one Z p element and 5 uncompressed points (such that four of them we store also one byte for compression). The total size of these elements is 356 bytes. In our implementation, we did pre-computations for 20 signatures. Regarding the timings, detailed in Table 6.1, the pre-computations for preparing one signature occurs in average in 175 s.

Real-Time Computations

Table 6.2 gives timings (average over more than 60 trials and standard deviation between parentheses) for all real-time computations (the whole validation protocol) which include the signature generation and verification. The timings include as well the NFC exchanges duration. The performance of our solution is critical for the validation of the m-pass. The whole validation process takes in average 205.27 ms, which is quite efficient. It enables to add the authentication of the validator into a window of time of 300 ms.

We denote by "Battery-Off" a powered-off phone either by the user, or because the battery is flat. It is possible to use the service even if the smartphone has run out of battery. Indeed, the m-pass application hosted in Android is involved only in the precomputation phase. Once this step is done, the validator interacts with the smartcard via the NFC controller and sends the energy via the NFC magnetic field. In this case, the smartcard runs the signature with lower performances. We measured a total transaction time of 596.81 ms. The signature generation consists in computing a signature σ = (R, S, T , W , K, c, s) and the NFC communication time. The considered operations for generating the signature are only one hash value and lightweight operations in Z p . The size of the computed signature is 229 bytes (sent by 1 APDUs). Regarding the communication between a SIM card and a reader, it is slow, but the whole process (Signature+NFC) remains very fast, i.e., 184.24 ms on average.

Signature+NFC

Conclusion

In this chapter, we proposed a privacy-preserving mobile pass solution for transport service that can be embedded into an NFC-enabled smartphone. This solution enables users to use the transport service in an anonymous and unlinkable manner, preventing in particular the risk of being tracked by the transport authority. However, in exceptional circumstances (e.g., under the injunction of a judge), the identity of the user associated to an anonymous validation can be de-anonymized and his rights to access the transport network revoked. Thus, this solution is flexible enough to ensure the standard security properties while providing a high level of privacy to users.

The cryptographic protocol behind our mobile pass solution is based on group signatures that are used when authenticating with the entrance gates of the transport network. When a user authenticates to the validator, he signs on a challenge on behalf of a group, thus hiding his identity from the transport operator. The unlinkability of the different actions of the user is obtained by changing regularly the challenge sent by the validator.

In the situation in which a malicious service operator deliberately refuses to renew the challenge, we suggest to detect such an attack by collecting the received challenge using an Android application for implementing the detection.

The functional requirements of a transport use case mainly consist of the validation time constraint and the operating when the smartphone battery is flat. In this chapter, we showed that the proposed protocol fulfill these functional requirements whilst using strong security parameters. This is by implementing a prototype using a standard NFCenabled SIM card and gathering the validation timing over more than 60 trials. The m-pass validation can be completed in 205.27 ms when the mobile is switched on, and in 596.81 ms when the mobile is switched off or its battery is flat.

In the next chapter, we address the privacy problem of the mobile ticketing use case.

Although this use case has similarities with the mobile pass use case, it presents more granularity and hence, preserving the same privacy level requires a new cryptographic solution.

Chapter 7

A Practical and Privacy-Preserving Ticketing Service [START_REF] Arfaoui | A Practical Set-Membership Proof for Privacy-Preserving NFC Mobile Ticketing[END_REF] qui ont été publiés dans la revue "Proceedings on Privacy Enhancing Technologies (PoPETs)" de la conférence PETS 2015. Nous concevons un protocole sécurisé pour le cas d'usage billetterie mobile (m-ticketing) sans contact (NFC) pour un service de transport public. Ce protocole respecte l'anonymat des utilisateurs et empêche les opérateurs de transport de tracer leurs clients. À cette fin, nous utilisons la nouvelle preuve d'appartenance à un ensemble, introduite dans le chapitre 4, et proposons également plusieurs optimisations du schéma de signature Boneh-Boyen, permettant l'amélioration de sa performance lors des transactions sans contact (NFC). Notre protocole permet également la révocation de l'anonymat d'un utilisateur ou d'un billet. Cette option est uniquement possible pour les autorités de révocation. Le protocole de m-ticketing offre aussi une plus grande flexibilité par rapport aux solutions précédentes car il permet le post-paiement et la validation hors ligne des m-tickets. Nous avons formellement validé la sécurité de notre protocole dans le modèle de l'oracle aléatoire. Par ailleurs, nous montrons que notre protocole remplit l'exigence fonctionnelle imposée par les transporteurs: à savoir la validation d'un m-ticket doit se dérouler en moins de 300 ms, tout en utilisant des paramètres cryptographiques (taille des clés) adéquats. En effet, nous mettons en place un prototype utilisant une carte SIM NFC. La validation d'un m-ticket peut être complétée en 184.25 ms lorsque le mobile est allumé, et en 266.52 ms lorsque le mobile est éteint ou la batterie est vide.

Dans ce chapitre, nous présentons une partie des résultats

Introduction

The second use case of the transport service is the mobile ticketing. Although this use case has some similarities with the m-pass use case, it has more granularity which applies new privacy issues. A user holds a book of max ticket m-tickets that enables him to have max ticket trips. Every m-ticket is identified by an index k ∈ [1..max ticket ] and a serial number. In order to ensure a high privacy level, we must ensure the anonymity of the m-tickets indexes in addition to the user's anonymity and the unlinkability of the m-tickets serial numbers. The reader can note that the index problem does not exist in the mobile pass use case. Indeed, the m-pass use case can been seen as a simplification of the m-ticketing use case, and hence, ensuring the same privacy level is simpler. In Table 7.1, we summarize the major differences between both use cases.

M-pass M-ticketing

User's privacy In this chapter, we propose a new cryptographic protocol for the m-ticketing use case that provides strong authentication, strict anonymity, and unlinkability properties, whilst remaining efficient when implemented in constrained environments like SIM cards. Towards this goal, we use the new set-membership proof introduced in Chapter 4. The new set-membership proof does not require provers nor verifiers (but in a specific scenario for verifiers) to perform pairing computations, especially on the prover side. It is therefore particularly suitable for our (ticketing) setting where provers hold SIM cards that do not support such costly computations. We also propose several optimizations of Boneh-Boyen signature schemes which are of independent interest and increase the performance and efficiency of BB-signatures. Based on these cryptographic primitives, our m-ticketing protocol enables to securely validate an m-ticket without disclosing any personal information to the transport operator, even if the latter is malicious. We push forward a strict privacy requirement when using one of the numbered m-tickets: for example, if the user uses the m-ticket number 3 from the book of m-tickets [1..10], the transport operator will only be able to check that the used m-ticket is one among the ten m-tickets [1..10].

This Chapter is organized as follows. In Section 7.2, we detail the framework of our m-ticketing system. We describe our protocol and show how we ensure a secure postpayment in Section 7.3. Then, we formalize our functional, security and privacy requirements in Section 7.4 and formally demonstrate that our protocol ensures these requirements in Section 7.5. Finally, we give details about the performance results of our protocol in Section 7.6 and conclude in Section 7.7.

Framework of an M-Ticketing System

We recall that we consider three different entities in our m-ticketing system. The user (U) is the owner of an NFC-enabled smartphone and wants to use the transport service.

The transport authority (TA) is the manager of the transport service. The revocation authority (RA) can revoke m-tickets and users' anonymity, and is completely independent of the transport authority. This role may be split between several authorities in such a way that they should all agree and cooperate before recovering the identity of an m-ticket holder.

An m-ticketing system consists of six different phases in our protocol. ( 1) The mticketing system parameters and keys are initialized during the initialization.

(2) The registration phase enables a user to register to the transport service. (3) In the permission token request phase, a user gets a permission token allowing him to generate max ticket m-tickets. ( 4) The validation phase consists in generating and validating an m-ticket.

(5) The revocation phase enables to retrieve the identity of a user who generated a given m-ticket and the m-tickets obtained by a given user. Finally, ( 6) the reporting phase enables a user to report his usage (i.e. the m-tickets that he did not use) to the transport authority and the transport authority to detect any duplication of m-tickets (i.e., mtickets that have been validated several times). In the sequel, these phases are modeled with various algorithms and protocols (Figure 7.1) executed by the above entities.

Initialization

Setup(1 λ ): This probabilistic algorithm outputs pp a description of the system parameters. We assume that pp are implicit to the other algorithms, and that they include λ, the security parameter, and max ticket , the number of m-tickets that each book of m-tickets contains. They are also an implicit input to the adversary, we will then omit them.

Keygen(pp):

This probabilistic algorithm outputs the two following secret/public key pairs: (rsk, rpk) for the revocation authority and (tsk, tpk) for the transport authority.

The system public key gpk is eventually set as (pp, tpk, rpk).

Registration

UKeygen(gpk, ID U ): This probabilistic algorithm outputs a secret/public key pair (usk, upk) for a user identifier ID U .

Register( U (ID U , upk), T A(DB REG )): This is an interactive protocol between a new user that takes as input his identity ID U and his public key upk, and the TA that takes as input the database DB REG where the identifiers of the registered users will be stored.

If TA accepts the protocol, the user's identity and public key are stored within DB REG .

Permission token request

TokenRequest( U(upk, gpk), TA(tsk, gpk, DB REG )): This is an interactive protocol between a user that takes as input (upk, gpk), and the TA that takes as input (tsk, gpk, DB REG ). If the user accepts the protocol, his output is a permission token τ that will enable him to generate/validate a book of max ticket m-tickets. If TA accepts the protocol, its output is a transcript view of the protocol.

Validation

GenTicket(gpk, τ ): This probabilistic algorithm takes as input a user's permission token τ and outputs an m-ticket T ick k with a serial number

B k such that k ∈ [1..max ticket ].
ValidateTicket(gpk, T ick k ): This deterministic algorithm takes as input a ticket T ick k .

If T ick k is valid, it outputs 1 and T ick k is stored within the database DB U sedT ickets that will be used to detect the m-tickets that have been used several times. Otherwise, it outputs 0.

Revocation

IdentUser(rsk, DB REG , T ick k ): This deterministic algorithm takes as input the private key of the revocation authority, rsk, the registration database of TA, DB REG , and a valid m-ticket T ick k . It outputs the identifier ID U of the registered user who obtained T ick k . If ID U does not belong to DB REG , it outputs ⊥.

IdentTicket(rsk, view, ID U ): This deterministic algorithm takes as input the private key rsk, a user's identifier ID U and a transcript view of an execution of TokenRequest with this user. It outputs all the m-tickets that can be generated from the token obtained after the execution of the TokenRequest protocol that led to view.

Reporting

ReportTicket(τ ): This algorithm is executed by a user with his permission token τ .

The user generates all the unused m-tickets and collects them in a usage report R. R is then sent to the transport authority.

IdentDuplicate(B k , DB U sedT ickets ): This deterministic algorithm takes as input B k the serial number of a valid m-ticket T ick k and DB U sedT ickets , and outputs the number of occurrences of B k in DB U sedT ickets .

Untraceable Mobile Ticketing System

At the beginning, as shown in Figure 7.2, the user registers at the transport service. Then, he retrieves a permission token A from the transport authority. This token enables the generation of max ticket m-tickets (an m-ticket book 1 ). The token A is a BB signature on a secret s known only by the user. The secret s identifies a type of m-tickets book.

At the validation phase, the user authenticates the validator and sends an m-ticket T ick k : (B k , E, Π). B k is a unique serial number of the m-ticket, E is an ElGamal encryption of g s 1 , and Π is a ZKPK. Π proves that (1) the user has a valid BB signature on s without revealing neither s nor the signature A, (2) E is an encryption of g s 1 without revealing s and (3) k belongs to [1..max ticket ] without revealing k. (3) is based on the new set-membership proof detailed in Chapter 4.

Finally, the user post-pays by regularly reporting unused m-tickets, i.e., by revealing the unused m-ticket serial numbers B k to the TA. This enables to detect any malicious behaviour, i.e., validating more m-tickets than what were obtained, without breaking the user's privacy. Additional countermeasures allows to recover the user's identity and retrieve his m-tickets, with the agreement of the authorities.

M-ticketing Protocol

Our protocol is divided in four phases: system initialization, user registration, permission token request and validation. The later includes the validator authentication and the m-ticket validation.

System Initialization In the sequel, we consider, except when it is explicitly mentioned, bilinear maps e : G 1 × G 2 → G T where all groups G 1 , G 2 and G T are multiplicative and of prime order p. Let g, g 0 , g 1 , g t , g T , g U , h, G, H be nine generators of G 1 and g 2 , g 3 two generators of G 2 . The user's SIM card will perform computations only in G 1 (note that current SIM cards are not designed to handle pairing computations nor computations in G 2 or G T .).

The revocation authorities set two pairs of keys: a private and public keys of the threshold ElGamal cryptosystem (pk RG , sk RG ) and a private and public keys of the threshold Paillier cryptosystem (pk RP , sk RP ).

We assume that the private keys are shared among the revocation authorities (e.g., using the technique proposed in [START_REF] Gennaro | Secure Applications of Pedersen Distributed Key Generation Protocol[END_REF] for El Gamal and the technique proposed in [START_REF] Fouque | Fully distributed threshold RSA under standard assumptions[END_REF] for Paillier). In order to decrypt a ciphertext, a minimal number t (the threshold) of these authorities should cooperate.

The public key, pk RG , consists of the elements (g T , h T = g x T T ), where g T is a random generator of G 1 , and the corresponding private key, sk RG , is formed by x T ∈ Z * p . Let a and b be random primes for which a, b > 2, a = b, |a| = |b| and gcd(ab, (a-1)(b-1)) = 1; let n = ab, Π = lcm(a -1, b -1), K = Π -1 mod n, and g P = (1 + n); then the public key, pk RP , is (n, g P ) and the secret key, sk RP , is (a, b).

The transport authority (TA) sets for each group, i.e., a type of m-tickets book, a key pair of the BB signature scheme. The private key is a random element γ ∈ Z * p and the corresponding public key is W = g γ 0 and W = g γ 2 . The transport authority sets another key pair of the BB signature scheme which will be used for the set-membership proof. The private key is a random element y ∈ Z * p and the corresponding public key is Y = g y 3 .

The user owns a public/private key pair (x U ∈ Z * p , h U = g x U U ). During the permission token request, the user obtains from TA a token A = (g s 1 h) 1/(γ+r) . The value s is jointly chosen by TA and the user (but only known by the user) whereas r is known by both entities.

User Registration We denote by ID U a user's identity and DB REG the database where the TA saves the identities of registered users. First, the user sends his public key h U and his identity ID U to TA. Then, he signs, using Schnorr signature scheme [START_REF] Schnorr | Efficient signature generation by smart cards[END_REF], a random challenge rc received from TA, using his private key x U . If the signature is valid, TA saves the tuple (ID U , h U ) in DB REG . Then, the user securely introduces his banking credentials in order to be subsequently charged.

Permission Token Request

The permission token request phase is detailed in Figure 7.3. A permission token (A = (g s 1 h) 1/(γ+r) , r) consists of an (extended) BBsignature [START_REF] Camenisch | Signature schemes and anonymous credentials from bilinear maps[END_REF] on s (the secret member group key only known by the user, whereas r is

M-ticket Validation An m-ticket T ick k (indexed k) is characterized by a serial number B k = g 1/(s+k+1) t along with an ElGamal encryption E = (C 1 = g a T , C 2 = g s 1 × h a T ) of g s 1 .
To prove the validity of a m-ticket, the user must prove that:

• k belongs to Φ = [1..max ticket ] using our new set-membership proof (described in Chapter 4),

• He knows a valid BB signature A = (g s 1 h) 1/(γ+r) on s (without revealing s and the signature),

• E is an encryption of g s 1 .

Therefore a m-ticket T ick k is represented by (B k , E, Π) where Π = P OK(k, a, s, r, A :

B k = g 1/(s+k+1) t ∧ A = (g s 1 h) 1/(γ+r) ∧ C 1 = g a T ∧ C 2 = g s 1 × h a T ∧ k ∈ [1..max ticket ]).
Remark 2 (BB optimizations): Proving the knowledge of a valid BB-signature A = (g s 1 h) 1/(γ+r) on a value s, without revealing s or the signature and without using pairings on the prover's side can be done as follows:

The prover first randomizes A by choosing a random value α ∈ Z * p and computes γ+r) and then that:

B 0 = A α . Since A = (g s 1 h) 1/(γ+r) this implies that B 0 = A α = (g αs 1 h α ) 1/(
B γ+r 0 = g αs 1 h α (7.1)
Let us note by B = B -1 0 and C = B γ 0 . From (7.1), we have:

C = g αs 1 × h α × B r (7.2)
As a result, in order to prove that he knows a BB-signature A on the value s, without revealing s nor the corresponding signature, the prover just has to send B 0 and C (that he can compute using (7.2)) to the verifier and prove that he knows the representation of C with respect to (g 1 , h, B ): Π BB = P OK(α, s, r :C = g αs 1 × h α × B r ). The proof consists in B 0 , C and Π BB (and no pairing computations are needed on the prover's side to compute Π BB ). The verifier will have to check that B 0 = 1 G 1 , that C = B γ 0 (via pairing computations or by using the key γ if it owns this key) and that Π BB is valid. If all the verifications hold, the verifier will be convinced that the prover knows a valid BB-signature.

As described in Figure 7.4, the validator verifies the proof Π, saves the date and time of the operation DT , the serial number of the validated m-ticket B k , the El Gamal encryption E (of g s 1 ) and the proof Π. These verifications can be done in two ways. In the first case, the validator holds the private keys γ (the private key of TA) and y (the private key used during the set-membership2 ). Hence, he can perform the verification of Π without executing any pairing computations. In such a case, the protocol is run without any pairing computations either on the user side (SIM card) or on the validator side. In the second case, the validator does not hold the private keys γ and y. Therefore, in order to perform the verification of Π, the validator would execute pairing computations. We still achieve our goal, i.e., no pairing computations at the user side (SIM card).

M-ticketing cardlet

Validator Public input: The public parameters and the public keys of the revocation and transport authorities h T , W, Y Public Input: The public The sets Φ = [1..max ticket ] and = {A 1 , A 2 , ..., Amax ticket } where A i = g 1/(y+i) for i ∈ Φ

The sets Φ and Private Input: A = (g s 1 h) 1/(γ+r) , k(The index of the ticket that will be used), s Private Input: The private signature keys γ and y (in some scenario) D day: validity end date of the permission token Pre-computations:

Compute B k = g 1/(s+k+1) t Choose a ∈ Z * p and Compute: C 1 = g a T , C 2 = g s 1 × h a T
Computation of elements involved in the proof that the user knows a valid signature on s Choose α ∈ Z * p and Compute (see remark 2):

B 0 = A α ; B = B -1 0 ; C = g αs 1 × h α × B r Choose r 2 , r 3 , r 4 , a 1 , d 1 , b 1 , α 1 , t, t 1 , t 3 , t 4 , t 5 , ν, d , f ∈ Z * p Compute: T = G s H r 2 ; β = αs; T = T α H r 3 ; r 5 = r 3 + αr 2 (mod p); Com = g k 1 h ν T
Pick the valid BB signature corresponding to the element k:

A k = g 1/(y+k) Choose l ∈ Z * p and Compute: B = A l k ; B 1 = B -1 ; D = B k 1 g l Choose k 1 , l 1 , r 1 ∈ Z * p and Compute: Com 1 = g k 1 1 h r 1 T ; D 1 = B k 1 1 g l 1 δ = s + k; f = a + ν; K = gtB -1 k = B s+k k = B δ k ; L = C 2 Com = g s+k 1 h a+ν T = g δ 1 h f T Computation of the witnesses Compute: C 1 = g a 1 T ; C 2 = g d 1 1 × h a 1 T ; R = G d 1 H t 1 ; R = T α 1 H t 3 ; C = g b 1 1 h α 1 B t ; T 4 = G b 1 H t 5 ; K = B d k ; L = g d 1 × h f T

Real time computations Validator authentication

Choose RC V ∈ Z * p and Check that the number of used m-tickets < max ticket RC V ----------T S = getTimeStamp() and Compute: Signature RSA , the RSA signature on RC V Verify Signature RSA and Check that T S < D

Signature RSA -----------and T S m-ticket Validation Compute: c= H(C, C 1 , C 2 , B 0 , T , T , Com, B, D, K, C 1 , C 2 , R , R , C , T 4 , Com 1 , D 1 , K , L , ch) ch ---------- Choose ch ∈ Z * p s 1 = k 1 + c × k mod p; s 2 = r 1 + c × ν mod p Check that B = 1 G 1 s 3 = l 1 + c × l mod p; ω 1 = a 1 + c × a mod p
• If The validator holds the private signature keys y and γ (First case), the prover does not send the value D and C. The verifier can compute it: D = B y , C = B γ 0 . Then goes to (*)

ω 2 = d 1 + c × s mod p; ω 3 = t 1 + c × r 2 mod p ω 4 = b 1 + c × β mod p; ω 5 = α 1 + c × α mod p ω 6 = t + c × r mod p; ω 8 = t 3 + c × r 3 mod p ω 10 = t 5 + c × r 5 mod p; ω 11 = d + c × δ mod p ω 12 = f + c × f mod p
• Otherwise, if the validator doesn't know the private signature key y and γ (Second case), then, check that e(D, g 3 ) = e(B, Y ); e(C, g 2 ) = e(B 0 , W ) and goes to (*)

Let E = (C 1 , C 2 ) and the proof Π = (C, B 0 , T , T , Com, c, B, D, s 1 , s 2 , s 3 , ω 1 , ω 2 , ω 3 , ω 4 , ω 5 , ω 6 , ω 8 , ω 9 , ω 10 , ω 11 , ω 12 ) B k , E, Π (*) Compute: C=g s 1 1 h s 2 T Com -c ; D=B s 1 1 g s 3 D -c ; C1 =g ω 1 T C -c 1 ; C2 =g ω 2 1 h ω 1 T C -c 2 ; R =G ω 2 H ω 3 T -c ; C =g ω 4 1 h ω 5 B ω 6 C -c ; R =T ω 5 H ω 8 T -c ; T4 =G ω 4 H ω 1 0 T -c ; K =B ω 11 k K -c ; L =g ω 1 1 1 h ω 1 2 T L -c Check c= H(C, C 1 , C 2 , B 0 , T , T , Com, B, D, K, C1 , C2 , R , R , C , T 4 , C, D, K , L , ch)
Send (B k , E, Π, ID V , DT ) to TA in order to be saved within the secured database DB U sedT ickets ; ID V is the identity of the validator and DT is the date and time of the transaction. We emphasize that owing to our improvements on Boneh-Boyen based Camenisch-Lysyanskaya signature scheme, all the computations (required to validate an m-ticket) are performed by the SIM card. We do not need to outsource part of the computations to the powerful but untrusted mobile phone. Consequently, the user's privacy is ensured with respect to the smartphone itself. Even a compromised mobile, e.g., containing a spyware, cannot collect any information about our m-ticketing application computations.

At the end of a successful m-ticket validation, the validator sends (B k , E, Π) to TA in order to be saved within a centralized and secured database DB U sedT ickets jointly with his identity ID V and the date and time of the transaction DT . In such a way, the TA will detect any malicious behaviour such that a multiple usage or cloning (cf. Paragraph "Countermeasures"). Theorem 6. The protocol in Figure 7.4 is a ZKPK of a permission token (A, r, s) and a value k such that

B k = g 1/(s+k+1) t , k ∈ [1..max ticket ] and E = (C 1 , C 2 ) is an El Gamal encryption of g s 1 .
Proof 6 (Sketch proof ). As mentioned in Chapter 3, a zero knowledge proof of knowledge must be complete, sound and zero-knowledge.

The completeness follows by inspection.

Soundness: roughly speaking, the whole proof Π can be divided in three sub-proofs Π 1 , Π 2 and Π 3 , where:

Π 1 = P OK(α, s, r, r 2 , r 3 , r 5 , a : C = g αs 1 × h α × B r ∧ T = G s H r 2 ∧ T = T α H r 3 = G αs H r 5 ∧ C 1 = g a T ∧ C 2 = g s 1 × h a T ) Π 2 = P OK(k, ν, s, r 2 : Com = g k 1 h ν T ∧ T = G s H r 2 ∧ K = g t B -1 k = B s+k k ) Π 3 = P OK(k, ν, l : Com = g k 1 h ν T ∧ D = B k 1 g l )
If the verifier accepts the proof Π this means that: D = B y (1) and C = B γ 0 (2).

Note that the proofs Π 1 , Π 2 and Π 3 are classical variants of Schnorr's proof of knowledge. Using the "extractors" of these proofs of knowledge, we can retrieve k, α, s, r, l.

From (1) we have: D = B y = B k 1 g l . This implies that B y B k = g l . Let us denote by A k = B 1/l . (Note that l = 0, otherwise this would imply that the prover knows the secret value y). We therefore have A y+k k = g and therefore that A k = g 1/(y+k) . So the prover knows a valid BB signature on the value k. This implies that k ∈

[1..max ticket ]. From (2) we have that C = B γ 0 = g αs 1 × h α × B r . This implies that B γ+r 0 = g αs 1 × h α . Let us denote by A = B 1/α 0 , this implies that A γ+r = g s 1 ×
h (Note that α = 0, otherwise this would imply that the prover knows the secret value γ). So A = (g s 1 h) 1/(γ+r) . The prover therefore knows a valid permission token (A, r, s).

In conclusion, the prover knows a permission token (A, r, s) and a value k such that

B k = g 1/(s+k+1) t , k ∈ [1..max ticket ] and E = (C 1 , C 2 ) is an El Gamal encryption of g s 1 .
(Honest-verifier) Zero-Knowledge: since Π 1 , Π 2 and Π 3 are classical ZKPK, we can easily construct simulators Sim1, Sim2 and Sim3 (respectively) for such proofs. From these simulators, it is straightforward to construct a simulator Sim that will simulate all interactions with any (honest) verifier V * . Since G 1 is a prime order group, then the blinding would be perfect and the output of Sim and V * 's view of the protocol would be statistically indistinguishable.

Revocation We distinguish two levels of revocation: the user's anonymity revocation and the m-tickets revocation. In the first case, the transport authority would like to get the user's identity corresponding to a given m-ticket. In the second case, the transport authority would like to revoke all the m-tickets of a given user, e.g., upon the request of the user further to the theft of his smartphone.

In order to recover a user's identity based on a used m-ticket T ick k = (B k , E, Π), TA sends E to the revocation authorities. Together, the revocation authorities decipher E and retrieve the commitment of s (g s 1 ). By using DB REG the database of registered users and g s 1 , TA will find the user's identity in the tuples (A, C 0 , s 2 , c, µ, ID U , h U ).

In order to retrieve the m-tickets of a user based on his identity ID U , first of all, TA must find the tuple (A, C 0 , s 2 , c, µ, ID U , h U ) from DB REG such that ID U = ID U . Then, TA sends C 0 (The Paillier encryption of s 1 ) to the revocation authorities. Similarly to the first case, the revocation authorities decipher together C and retrieve s 1 . Upon receiving s 1 , TA computes s = s 1 + s 2 , hence, it can retrieve all the m-tickets (B k = g 1/(s+k+1) t

) of the user.

A Secure Post-Payment Process

One novelty of our m-ticketing protocol, in addition to the respect of users' privacy, is to give the ability to charge a user after the usage of m-tickets.

Regular Reporting In a post-payment approach, the m-ticketing application must report unused m-tickets to the back-end server, before the pre-defined D day. Thus, the regular reports does not question the privacy of the user. The following example gives further clarification. Suppose that the user retrieved a permission token of 5 m-tickets. Before D day, he used 4 m-tickets, i.e., m-tickets number 1, 2, 3 and 4. On D day, the m-ticketing application will report to the back-end server the m-ticket number 5 using a network connection. The report contains B 5 = g 1/s+5+1 t and the proof Π = P OK(k, s, r, A :

B 5 = g 1/(s+5+1) t ∧ A = (g s 1 h) 1/(γ+r) ∧ 5 ∈ [1..5]).
Regularly revealing the unused m-tickets enables the transport authority to (1) charge the user, (2) check the reliability and accuracy of the reports without questioning the user's privacy. Indeed, the unlinkability of user's m-tickets (B k = g 1/(s+k+1) t

, E, Π), both during the use of the service and during the reporting phase, is ensured owing to the q-DDHI and DDH assumptions (cf. unlinkabililty proof in Section 7.5).

Countermeasures A malicious user's goal simply consists on not paying or paying less than what he is supposed to. To do so, he may try to block the reporting or attack the cardlet of the SIM.

If the user blocks network communications in order to block reporting, the SIM cardlet will refuse to issue m-tickets for a permission token after reaching the limit of max ticket , or the limit of the time window controlled by D. This countermeasure C relies on the security of the SIM card.

If the user performs a successful physical attack against the SIM card, which is extremely difficult [START_REF]SIM Java Card Platform Protection Profile Basic and SCWS Configurations-Evolutive Certification Scheme for (U)SIM cards[END_REF], he may try to (1) defeat the countermeasures C and never do reports, or (2) use the same m-ticket several times or (3) report a used m-ticket. In the first case, the TA will notice that the user did not respect the D day limitation (reporting his usage before the D day). In the other cases, this will be detected in DB U sedT ickets (two m-tickets with the same serial number). TA can, then, decide to break the user's anonymity and retrieve all his m-tickets usage history.

Thus, the user is forced to report his consumption and renew his permission token lest the service is unusable or TA breaks his anonymity.

Note that forging an m-ticket is not possible, even with a compromised SIM because of the unforgeability property.

Requirements

Similarly to the m-pass system, we consider three types of requirements: functional requirements which are "efficiency" and "versality", security requirements which consist in "correctness", "unforgeability" and "Non-frameability", and privacy requirements which comprises "unlinkability".

Obviously, the two transport system use cases, namely m-pass and m-ticketing, share the same requirements. However, as shown in what follows, these requirements are differently interpreted.

Functional Requirements

Efficiency Similarly to the m-pass system, a m-ticketing system must fulfil functional requirements imposed by transport operators [7], in particular the validation of an mticket must be performed in less than 300ms. We must consider that a SIM card has limited computation capabilities. In particular, pairing APIs are not available on current SIM cards.

Versatility The mobile phone and the validator cannot be assumed to be connected to a back-end server during the validation phase. This enables the user to use an m-ticket in any kind of situation, especially in areas with low connectivity, e.g., underground, or if the battery of his mobile is flat. Moreover, the m-ticketing system must support both pre-payment and post-payment modes, i.e., an m-ticket can be prepaid or charged later (after its use and before a given date that we denote later by D day). In the post-payment mode, the transport authority must learn the total number of m-tickets used by each customer in order to charge them. This is not an easy task especially for anonymous and unlinkable m-tickets.

Security and Privacy Model

Besides the correctness property, we formally define three security and privacy properties of our m-ticketing protocol in which the attack capabilities of a probabilistic polynomial time adversary A are modeled by providing him access to some oracles. In the sequel, HU will denote the set of honest users and MU the set of corrupted users. We assume that A receives all the exchanged messages in our system. A acts as an active adversary as regards to the messages issued by malicious users and as a passive adversary with respect to honest users.

ORegister HU is an oracle that will be used by an adversary in order to register honest users. By calling this oracle with ID U as argument, the adversary adds a new user. The oracle runs (upk, usk) ← UKeygen(gpk, ID U ) and adds ID U (along with upk) to the set HU. The private key usk is kept secret and public key upk is returned to the adversary.

ORegister M U is an oracle that will be used by an adversary in order to register malicious users. The adversary calls this oracle with argument the identifier ID U of a user and sets his public key to upk and his private key to usk. The identity ID U (along with upk) is added to the set MU.

OCorruptU ser is a user secret key oracle enabling the adversary to obtain the private key usk of a user ID U ∈ HU. The oracle transfers ID U to MU and returns usk.

OT okenRequest U is an oracle that runs the user's side in the TokenRequest protocol. This oracle will be used by an adversary playing the role of a malicious TA. The adversary gives to the oracle an identity ID U of an honest user and his public key upk. If the user accepts the protocol, the adversary is given a transcript view of the protocol.

OT okenRequest T is an oracle that runs the transport authority side in the TokenRequest protocol. This oracle will be used to simulate the execution of the protocol between a user (corrupted or not) and an honest TA.

OGenT icket(ID U , view) is an oracle that takes as input the identifier ID U of an honest user and a transcript view of an execution of the TokenRequest protocol with this user and outputs an m-ticket T ick k using a fresh index k that has not been used in a previous query of OGenT icket on ID U and view. The oracle records (ID U , T ick k ) in a list Set.

OIdentT icket T (ID U , view) is an oracle that takes as input the identifier of a user ID U and a transcript view of an execution of TokenRequest with this user and outputs all the m-tickets that this user is able to generate.

OIdentU ser T (T ick k ) is an oracle that returns the identifier ID U of the user who generated an m-ticket T ick k .

OReportT icket(ID U , view) is an oracle that takes as input the identifier ID U of an honest user and a transcript view of a TokenRequest execution with this user and outputs the set of unused m-tickets. For each unused m-ticket T ick k , the oracle records (ID U , T ick k ) in Set.

Correctness Informally speaking, our protocol is correct if (1) a valid permission token enables to generate valid m-tickets, (2) honestly generated m-tickets are accepted, (3) a validated m-ticket enables revocation authorities to identify the user who generated it and (4) revocation authorities can retrieve all the m-tickets generated by a given registered user that obtained a valid permission token.

Unforgeability Informally speaking, it should be impossible for anyone [START_REF][END_REF] to validate more m-tickets than what he obtained i.e. an adversary who retrieved N tokens τ (N books of max ticket m-tickets) should not be able to generate more that N * max ticket m-tickets; (2) to validate m-tickets such that the algorithm IdentUser returns ⊥, i.e., an identifier ID U that doesn't appear in DB REG . We formally define the unforgeability experiment Exp unf org A (1 λ ) in Figure 7.5. The scheme is unforgeable if for any probabilistic polynomial time adversary A, the probability Pr[Exp unf org

A (1 λ ) = 1] is negligible. Exp unf org A (1 λ ) 1. pp ← Setup(1 λ ); HU ← ∅; MU ← ∅ 2. (gpk, tsk, rsk) ← Keygen(pp) 3. ({T ick j k j } j=l j=1 , {R i } i=f i=1 ) ← A(gpk: ORegister HU , ORegister M U , OCorruptU ser,
OT okenRequest T , OGenT icket, OReport T icket). An R i corresponds to a "usage report", i.e., a set on unused m-tickets.

4. Let DB be an empty database.

5. For j from 1 to l do {If ValidateTicket(gpk, T ick j k j

) then store T ick j k j in DB}.

6. For i from 1 to f do {Validate the m-tickets of the report R i and store valid unused m-tickets in DB} Non-Frameability Informally speaking, it should be impossible for anyone to falsely accuse an honest user of having spent an m-ticket. We formally define the non-frameability experiment Exp N f ra A (1 λ ) in Figure 7.6. The scheme is non-frameable, if for any probabilistic polynomial time adversary A, the probability Unlinkability Informally speaking, it should be impossible, except for the revocation authorities, to trace the m-tickets obtained by a user, in particular: (1) to link m-tickets obtained during the permission token request phase to the validated/used ones; (2) to link two m-tickets validated by the same user or to decide whether two validated mtickets have the same number/index or not; (3) to link validated m-tickets to non-used m-tickets reported by the user to the transport authority. For this, an adversary has full control over the transport authority (in particular it owns the private key tsk) and all the users except two honest users i 0 and i 1 . The adversary can initiate the IdentUser protocol over any m-ticket and can get the user's identity behind it, except for the mtickets generated by i 0 and i 1 . He can also initiate the IdentTicket protocol for all the users except for i 0 and i 1 . We define the unlinkability experiment Exp unlink A (1 λ ) in Figure 7.7. The scheme is unlinkable if for any probabilistic polynomial time adversary A, the advantage Adv unlink-b

Pr[Exp N f ra A (1 λ )=1] is negligible. Exp N f ra A (1 λ ) 1. pp ← Setup(1 λ ); HU ← ∅; MU ← ∅; Set ← ∅
A (1 λ ) = |P r[Exp unlink-b A (1 λ ) = b] -1/2| is negligible. Exp unlink-b A (1 λ ) 1. pp ← Setup(1 λ ); HU ← ∅; MU ← ∅ 2. (gpk, tsk, rsk) ← Keygen(pp) 3. (i 0 , k 0 , i 1 , k 1 ) ← A(gpk, tsk, DB REG , DB U sedT ickets : ORegister HU , ORegister M U , OCorruptU ser, OT okenRequest U OGenT icket OIdentT icket T OIdentU ser T OReport T icket) 4. If i 0 or i 1 ∈ MU then output ⊥.

5.

(a) let i 0 and i 1 run the protocol TokenRequest and get the permission tokens τ 0 and τ 1 and output view 0 and view 1 .

(b) T ick k b ← GenTicket(gpk, τ 0 ) and T ick k 1-b ← GenTicket(gpk, τ 1 ), with b ∈ {0, 1} 6. b ← A (gpk, tsk, DB REG , DB U sedT ickets , T ick k j , T ick k 1-j : ORegister HU , ORegister M U , OCorruptU ser, OT oken Request T OGenT icket OIdentT icket T OIdentU ser T OReport T icket), with j ∈ {0, 1}
7. If OCorruptU ser was requested on i 0 or i 1 , or OIdentT icket T was requested on (i 0 , view 0 ) or (i 1 , view 1 ) then output ⊥.

If

OIdent U ser T was requested for T ick k j or T ick k 1-j , output ⊥.

9. If OReportT icket was requested for i 0 or i 1 and i 0 and i 1 did not validate the same number of m-tickets then output ⊥.

Security Analysis

In this section, we prove that our m-ticketing protocol provides the security and privacy properties defined in Section 7.4.

Lemma 1. If the q-SDH assumption holds in G 1 then the q-SDH-I assumption holds in G 1 .

Proof. See for example [START_REF] Fuchsbauer | Transferable constant-size fair e-cash[END_REF] for a proof of this Lemma.

Remark:

The triplet (r , s , A ) corresponds to a permission token of our m-ticketing protocol. In the sequel, we will call the oracle O a BB-signature oracle and the value s the permission token secret (or token secret for short).

Forking Lemma. We use the Forking Lemma [START_REF] Pointcheval | Security arguments for digital signatures and blind signatures[END_REF] in our proofs, to prove that an adversary A is not able to produce a new valid m-ticket T ick k (respectively a Schnorr's signature µ, see Figure 7.3) unless he knows all the underlying secrets (a, s, r, A, k) (respectively the secret x U ).

Using the notation of [START_REF] Pointcheval | Security arguments for digital signatures and blind signatures[END_REF], if an adversary is able to produce a valid ticket T ick k (k, σ 1 , h, σ 2 ) where

σ 1 =(C, C 1 , C 2 , B 0 , T , T , Com, B, D, K, C 1 , C 2 , R , R , C , T 4 , Com 1 , D 1 , K , L , ch), h=H(C, C 1 , C 2 , B 0 , T , T , Com, B, D, K, C 1 , C 2 , R , R , C , T 4 , Com 1 , D 1 , K , L , ch)
and

σ 2 =(s 1 , s 2 , s 3 , ω 1 , ω 2 ,..., ω 12 )
then it can produce two valid m-tickets (k, σ 1 , h, σ 2 ) and (k, σ 1 , h , σ 2 ) such that h = h .

Theorem 7 (Unforgeability). Our m-ticketing protocol satisfies the unforgeability requirement, in the random oracle model, under the q-SDH assumption. The proof is detailed below.

Proof 7 (sketch of proof ). Let A be an adversary who breaks the unforgeability requirement of our m-ticketing protocol with non-negligible probability. We will construct an algorithm B, using A as an oracle, which breaks the q-SDH-I assumption. B receives on input from its challenger (G 1 , g 0 , g 1 , g U h, W = g γ 0 ) the public parameters of the q-SDH-I challenge and has access to a BB-signature oracle. The other generators of the m-ticketing system are randomly chosen.

B also chooses the keys for the Paillier encryption scheme. It sends W and the public key of the Paillier scheme to A. The private and public keys of the El Gamal cryptosystem can be chosen either by A or B. B is therefore able to construct the public parameters pp for A and can answer to its requests as follow:

• ORegister HU requests: B randomly chooses x U ∈ Z p and computes h U = g x U U .

• ORegister M U requests: B does not need to do anything.

• OCorruptU ser requests: B gives x U to A.

• OT okenRequest T requests: B plays as follows: B first receives a Paillier encryption C 0 . It decrypts it (recall that B chose the private key for the Paillier encryption scheme) and retrieve the corresponding plaintext s 1 . It then queries the BB-signature oracle on s where s = s 1 + s 2 and s 2 is randomly chosen by B.

The BB-signature oracle sends back a pair (r, A = (g s 1 h) (1/(y+r) with r ∈ Z p , and B transmits it to A along with the value s 2 . So B perfectly simulates the OT okenRequest T for A.

• OGenT icket(ID U , view) requests: since B knows the values of all the tokens (A, r, s) that have been issued during OT okenRequest T requests, it can easily answer to OGenT icket queries. The simulation of this oracle is perfect.

• OReportT icket(ID U , view) requests: B proceeds as in an OGenT icket request for each unused m-ticket.

We differentiate two types of adversaries:

• Type-1 Forger: an adversary that outputs a valid m-ticket T ick k which cannot be linked to a registered user (corrupted or not).

• Type-2 Forger: an adversary that outputs more valid m-tickets than he obtained.

We show that both Forgers can be used to solve the q-SDH-I problem. However, the reduction works differently for each Forger type. Therefore, initially B chooses a random bit c mode ∈ 1, 2 that indicates its guess for the type of forgery that B will output.

If c mode = 1
Eventually, B outputs, with non-negligible probability, a valid m-ticket T ick k = (B k , E , Π ) such that the algorithm IdentUser, on the input T ick k , returns an unknown identifier ID (i.e., does not appear in DB REG ).

First case: c = g s 1 (the plaintext encrypted in E ) has been queried during an OT okenRequest T request but no corresponding signature µ has been produced. This means that the adversary didn't receive the value s 2 (where s = s 1 + s 2 ) from the OT okenRequest T oracle. We know from the Forking Lemma and the proofs Π and Π 1 that A necessarily knows s and s 2 . Since only g s 2 1 has been revealed by this oracle during the OT okenRequest T , A could be used to extract Discrete Logarithms. Therefore under the DL assumption, this first case could only occur with negligible probability.

Second case: E is an encryption of a commitment c = g s 1 of a value s that has not been queried during a OT okenRequest T request. Therefore s has not been queried to the BB-signature oracle either. Using the Forking Lemma and the soundness property of the proof Π 1 , B is able to extract with non-negligible probability the secrets (a , s , r , A , k ) underlying the m-ticket T ick k . B outputs the triplet (r , s , A ) to its challenger of the q-SDH-I assumption and therefore breaks it.

If c mode = 2

Eventually, A outputs, with non-negligible probability ξ, L = N × max ticket + 1 valid m-tickets 3 {T ick j k j } j=L j=1 , where N is the number of calls to the OT okenRequest T oracle, max ticket is the number of authorized m-tickets by token and T ick j k j = (B k j , E, Π). Let us denote by (s 1 , s 2 ,..., s N ) the N token secrets submitted to the BB-signature oracle. W.l.o.g, we may assume that all these values are different (recall that a token secret s is jointly computed by A and B). We therefore have N × max ticket distinct token pairs (s i , k) with i ∈ {1, ..., N } and k ∈ {1, ..., max ticket }. Let Γ be the set containing all these token pairs and T ick i j the m-ticket corresponding to the token pair (s i , j).

Among the L m-tickets output by A, there is at least one m-ticket T ick k * for which the corresponding token pair (s * , k * ) does not belong to Γ. Otherwise this would mean that two m-tickets among these L m-tickets, e.g., T ick ∈ Γ this implies that k * / ∈ {1, ..., max ticket }. Such a case will happen with negligible probability under the q-SDH assumption (see Theorem 2). Therefore s * / ∈ {s 1 , s 2 , ..., s N } and consequently has not been queried to the BB-signature oracle (A is in fact a Type-1 Forger). B then picks a random m-ticket T ick k among the L m-tickets output by A. With probability 1/L, it has chosen T ick k * . Using the Forking Lemma and the soundness property of the proof Π, B is able to extract with non-negligible probability the secrets (a , s , r , A , k ) underlying the m-ticket T ick k . B outputs the triplet (r , s , A ) and therefore breaks the q-SDH-I assumption with non-negligible probability ξ/L.

To complete the proof, we need to clarify why we discard duplicates in Exp unf org A (1 λ ). We consider that T ick k = (B k , E, Π) and T ick k = (B k , E , Π ) are duplicates if their serial numbers are equal. Let us denote by (s, k) (respectively (s , k )) the token pair corresponding to the ticket T ick k (respectively T ick k ). Since B k = B k , we have s + k = s + k mod p.

First case: (s, k) = (s , k ) This implies that T ick k and T ick k are in fact the same tickets. We can therefore discard one of them.

Second case: (s, k) = (s , k ) Case 2.1 : s or s / ∈ {s 1 , s 2 , ..., s N }. This implies that A is a Type-1 Forger. Under the q-SDH-I assumption, this case will occur with negligible probability.

Case 2.2 : s and s ∈ {s 1 , s 2 , ..., s N }. This implies that k and k ∈ {1, ..., max ticket }. Otherwise A could be used to break the q-SDH assumption (see the proof of Theorem 2). Since s and s have been randomly chosen (they are jointly computed by A and B), the probability that s + k = s + k mod p is negligible. Therefore Case 2.2. will occur with negligible probability either.

Consequently, under the q-SDH assumption, only the first case could occur and we only discard tickets that come from the same token secret.

Theorem 8 (Non-Frameability). Our m-ticketing protocol is non-frameable, in the random oracle model, under the q-DDHI assumption. The proof is detailed below.

Proof 8 (sketch of proof ). We assume that the challenger C in the experiment Exp N f ra A (1 λ ) receives a random instance (g x 1 , g x 2 ,...,g x l ) of the one-more DL problem where g is a random generator in G 1 . C will run the adversary A as a subroutine and act as A's challenger in the non-frameability experiment. Because C is against the one-more DL assumption, he has access to a DL oracle. C picks three random values ξ 1 , ξ 2 and ξ 3 in Z p and computes g 1 = g ξ 1 , g U = g ξ 2 and G = g ξ 3

1 . The other generators of the m-ticketing system are randomly chosen. A chooses the keys tsk for the transport authority and rsk for the revocation authority and C chooses the key sk RP for the Paillier encryption scheme. C is therefore able to construct the public parameters pp for A and can answer to its requests in the following way:

• ORegister HU requests: C answers using his input of the one-more DL problem. C puts

h U i = (g x i ) ξ 2 = g x i U
• ORegister M U requests: C does not need to do anything.

• OCorruptU ser requests: C uses the DL oracle to give the corresponding x i to the adversary.

• OT okenRequest U requests: C first uses his input of the one-more DL problem to compute the commitment Com: C puts Com= (g x j ) ξ 1 = g

x j

1 . If the protocol doesn't abort then we put s=x j +s 2 mod p and c = g s 1 , where x j is unknown to C and s 2 is provided by A. In the random oracle model, C is able to perfectly simulate the proof of knowledge Π 1 as well as the Schnorr's signature µ.

• OGenT icket(ID U , view) requests: All the values involved in the computation of an m-ticket T ick k can be easily simulated by C except T and B k . To compute T = G s H r 2 where r 2 is a random value chosen by C, it proceeds as follows:

T = (Com × g s 2 1 ) ξ 3 H r 2 = G s H r 2 .
As C does not know the value s it cannot compute or simulate the value B k = g 1/(s+k+1) t . It will therefore choose a random value R and define B k as R. In the random oracle model, C can simulate the proof of knowledge Π using standard techniques. The simulation is not perfect since we replace the value B k by a random value R. However A will not detect this change unless he can solve the q-DDHI problem.

• OReportT icket(ID U , view) requests: C proceeds as in an OGenT icket request for each unused m-ticket. Now, we assume that the adversary A manages to produce a valid m-ticket T ick k such that it breaks the non-frameability of our m-ticketing protocol and it mades t requests to the OCorruptU ser oracle. This means that this m-ticket has not been obtained on a OGenT icket query and the IdentUser algorithm on T ick k outputs an identifier ID U which is in HU along with a Schnorr's signature µ that proves that this m-ticket comes from a permission token obtained by this user 4 .

It follows from the Forking Lemma that if A is able to produce a valid m-ticket T ick k (k, σ 1 , h, σ 2 ) where

σ 1 =(C, C 1 , C 2 , B 0 , T , T , Com, B, D, K, C 1 , C 2 , R , R , C , T 4 , Com 1 , D 1 , K , L , ch), h=H(C, C 1 , C 2 , B 0 , T , T , Com, B, D, K, C 1 , C 2 , R , R , C , T 4 , Com 1 , D 1 , K , L , ch) and σ 2 =(s 1 , s 2 , s 3 , ω 1 , ω 2 ,.
.., ω 12 ) then it can produce two valid m-tickets (k, σ 1 , h, σ 2 ) and (k, σ 1 , h , σ 2 ) such that h = h . Using the technique of replay and the soundness property of the proof Π, one is able to extract all the secret values (a, s, r, A, k).

First case: the value s corresponds to a permission token obtained during an O T okenRequest U on ID U i (i.e., g s 1 is equal to the value c produced during such a request). C outputs the t values x i that comes from the requests to the DL oracle plus the value x j = s -s 2 mod p and so breaks the one-more DL assumption.

Second case: the value s does not correspond to a permission token obtained during an OT okenRequest U on ID U i (meaning that all the values c generated during such requests are different from g s 1 ). We know by the definition of the experiment that no

OCorruptU ser oracle query (and consequently no DL oracle query) has been made on this identity. Therefore the public key h U i corresponding to ID U i is in the one-more DL problem input. It follows from the Forking Lemma that if A is sufficiently efficient to produce such a signature µ, then there exists an algorithm A' which can produce two Schnorr's signatures with non-negligible probability. Using the techniques of replay and soundness, C is able to extract the private key x U used to generate the signature µ. C outputs the t values x i , coming from the requests to the DL oracle, plus the value x U i and so breaks the one-more DL assumption.

We prove the non-frameability under the q-DDHI and one-more discrete logarithm assumptions [START_REF] Bellare | The one-more-rsa-inversion problems and the security of chaum's blind signature scheme[END_REF]. We use in fact the OMDL assumption to get a better reduction, but the proof can also be done under the discrete logarithm assumption. As the q-DDHI assumption implies the DL one, we can conclude that our m-ticketing protocol is nonframeable, in the random oracle model, under the q-DDHI assumption.

Theorem 9 (Unlinkability). Our m-ticketing protocol satisfies the unlinkability requirement, in the random oracle model, under the q-DDHI and DDH assumptions. The proof is detailed below.

Proof 9 (sketch of proof ). We prove the unlinkability under a slightly weaker model than the one presented in Section 7.4. Indeed, we consider a slightly different experiment in which the adversary cannot query the revocation oracle OIdentU ser T . We rename this new requirement Unlinkability*. We would like however to emphasize that the access to revocation functionalities will likely be carefully controlled in a real deployment of an m-ticketing system. Therefore, unlinkability* is a reasonable model to consider.

Anyway, in order to satisfy the original unlinkability requirement, we just need to replace the ElGamal encryption scheme, which only satisfies IND-CPA security, by an IND-CCA2 encryption scheme. It is well-known that by double encrypting the same message under an IND-CPA scheme and using a simulation sound proof of equality of plaintexts, we obtain an IND-CCA2 scheme. Therefore, by using the double ElGamal encryption scheme, which was proved IND-CCA2 in [START_REF] Fouque | Threshold cryptosystems secure against chosen-ciphertext attacks[END_REF], our m-ticketing protocol would satisfy the original unlinkability requirement.

Let A be an adversary who breaks the unlinkability requirement of our m-ticketing protocol. W.l.o.g. we will consider that a query to the OReportT icket oracle on (ID U , view ) for the report of j unused m-tickets is equivalent to j queries to the OGenT icket on (ID U , view ).

Let m = max ticket . We will say that an adversary A against our unlinkability experiment Exp unlink-b

A

(1 λ ) is a Type-(i, j) distinguisher, with i ≤ m -1 and j ≤ m -1, if A after having received its challenge (from its Exp unlink-b A (1 λ )-challenger) makes at most i queries to the OGenT icket oracle on (i 0 , view 0 ) and j queries to the OGenT icket oracle on (i 1 , view 1 ). We can remark that a Type-(i, j) distinguisher, with i ≤ m -1 and j ≤ m -1, is also a Type-(m -1, m -1) distinguisher. We may therefore, without loss of generality, restrict our attention to Type-(m -1, m -1) distinguishers. In the sequel, we will thus assume that A is such an adversary. More precisely, we will suppose that after receiving T ick k b and T ick k 1-b , A arbitrarily queries the ORegister HU , ORegister M U , OCorruptU ser, OIdentT icket T and OT okenRequest U oracles and then queries the OReportT icket oracle on (i 0 , view 0 ) and (i 1 , view 1 ).

We give a security proof as a sequence of games, using Shoup's methodology [START_REF] Shoup | Sequences of games: a tool for taming complexity in security proofs[END_REF]. We will only give a rather high-level description of the initial game (Game 0) and brief descriptions of the modifications between successive games.

Game 0: This is the original attack game with respect to a given efficient adversary A.

The challenger C randomly chooses g, g 0 , g 1 , g t , g T , g U , h, G, H nine generators of G 1 and g 2 , g 3 two generators of G 2 . It also chooses the keys for the Paillier encryption scheme as well as the ones for the transport authority and revocation authorities. C sends gpk and tsk to A. C answers to A's requests as follows:

• ORegister HU requests: C randomly chooses x U ∈ Z p and computes h U = g x U U .

• ORegister M U requests: C does not need to do anything.

• OCorruptU ser requests: C gives x U to A.

• OT okenRequest U requests: C chooses a random value s 1 to obtain a valid permission token (A, r, s) and uses x U to generate the signature µ.

• OGenT icket(ID U , view) requests: C uses its permission token (A, r, s) and a fresh index k that has not been used in a previous query of OGenT icket on ID U and view and computes a ticket T ick k = (B k , E, Π).

• OIdentT icket T (ID U , view) requests: C computes the m-tickets T ick k based on the secret s corresponding to the user identifier ID U and gives them to A.

• OReportT icket(ID U , view) requests: C proceeds as in a OGenT icket request for each unused m-ticket.

The adversary chooses two honest users i 0 and i 1 , and two indexes k 0 and k 1 . C runs the protocol TokenRequest with i 0 and i 1 , and outputs the corresponding views, view 0 and view 1 , to A. It then generates two valid m-tickets: At the end of the game, the adversary outputs a bit b , its guess. Let S 0 be the event that b = b in this game and S i the event that b = b in game i. We have

T ick k b = (B k b , E b , Π b ) for i 0 and T ick k 1-b = (B k 1-b , E 1-b , Π 1-b )
: |P r[S 0 ] -1/2| = Adv unlink-b A (1 λ ) = |P r[Exp unlink-b A (1 λ ) = b] -1/2| Let {T ick i k i b = (B i k i b , E i k i b , Π i k i b )} i=m-1 i=1
denote the m -1 unused (reported) m-tickets of

i 0 and {T ick i k i 1-b = (B i k i 1-b , E i k i 1-b , Π i k i 1-b )} i=m-1 i=1
the ones of i 1 , where the k i b 's and the k In the sequel we will used the simplified notation Adv DDH (respectively Adv q-DDHI ) to denote the DDH-advantage (respectively the q-DDHI advantage) of some efficient algorithm in solving the DDH (respectively q-DDHI) problem. • Game(0,0,b): This is the same game as Game(0,1-b) except that we replace the serial number B k b by a random value and then simulate the proof Π b . Such a simulated proof can easily be done in the random oracle model using standard techniques. Under the q-DDHI assumption, A cannot detect this change. Indeed, we can easily construct a q-DDHI distinguisher D with q DDHI-advantage satisfying:

|P r[S (0,1-b) ] -P r[S (0,0,b) ]| ≤ Adv q-DDHI (3)
• Game(0,0,1-b): This is the same game as Game(0,0,b) except that we replace the serial number B k 1-b by a random value and then simulate the proof Π 1-b . Such a simulated proof can easily be done in the random oracle model using standard techniques. Under the q-DDHI assumption, A cannot detect this change. Indeed, we can easily construct a q-DDHI distinguisher D with q DDHI-advantage satisfying:

|P r[S (0,0,b) ] -P r[S (0,0,1-b) ]| ≤ Adv q-DDHI (4)

Let Game 1 be the same game as Game(0,0,1-b)

Combining ( 1), ( 2), ( 3) and (4), we obtain:

|P r[S 0 ] -P r[S 1 ]| ≤ 2Adv DDH + 2Adv q-DDHI
We then proceed similarly for each unused m-ticket of i 0 and i 1 :

{T ick i k i b = (B i k i b , E i k i b , Π i k i b )} i=m-1 i=1 and {T ick i k i 1-b = (B i k i 1-b , E i k i 1-b , Π i k i 1-b )} i=m-1 i=1
.

For i = 1 to m -1, we define the following game.

• Game(i,b): This is the same game as Game i = Game(i-1,0,1-b) except that we replace the El Gamal ciphertext E i b by an encryption of a random value and then simulate the proof Π i b .

• Game(i,1-b): This is the same game as Game(i,b) except that we replace the El Gamal ciphertext E i 1-b by an encryption of a random value and then simulate the proof Π i 1-b .

• Game(i,0,b): This is the same game as Game(i,1-b) except that we replace the serial number B i k i b by a random value and then simulate the proof Π i b .

• Game(i,0,1-b): This is the same game as Game i,0,b) except that we replace the serial number

B i k i 1-b
by a random value and then simulate the proof Π i 1-b .

Let Game i + 1 be the same game as Game(i,0,1-b). We obtain as above

: |P r[S i+1 ]- P r[S i ]| ≤ 2Adv DDH + 2Adv q-DDHI
Using our notation, Game m is the same game as Game(m-1,0,1-b). In the latter game, the unlinkability-challenger gives no information (in a strong information theoretic sense) to A about the bit b (since all the El Gamal ciphertexts have been replaced by encryptions of random values and all serial numbers have been replaced by random values). Therefore we have: P r[S m ] = 1/2.

We can now give an upper bound for Adv unlink-b

A (1 λ ) : Adv unlink-b A (1 λ ) = |P r[Exp unlink-b A (1 λ ) = b] -1/2| = |P r[S 0 ] -P r[S m ]| We have: |P r[S 0 ] -P r[S m ]| ≤ Σ j=m-1 j=0 |P r[S j ] -P r[S j+1 ]| ≤ 2m × (Adv DDH + Adv q-DDHI )
Therefore under the DDH and q-DDHI assumptions, the advantage Adv unlink-b

A

(1 λ ) of a Type-(m -1, m -1) distinguisher is negligible (and consequently the one of a Type-(i, j) distinguisher, with i ≤ m -1 and j ≤ m -1, is also negligible).

We can then conclude that our proposed m-ticketing protocol satisfies the unlinkability* requirement, in the random oracle model, under the DDH and q-DDHI assumptions.

Implementation

In this section, we give further details about the prototype implementing our m-ticketing system in addition to the performance results of the m-ticket validation phase.

Prototype Details

The m-ticketing development platform is the same as the m-pass development platform. The validator is simulated by a Java swing application connected to an NFC reader using the ISO14443B protocol. The cardlet is embedded within a SIM card. We used a regular Galaxy S3 smartphone running Android 4.1.2. For more details about the validator and SIM card details, the reader can refer to Section 6.6.1 and Section 6.6.2.

We also use the same cryptographic parameters (curve and pairing) like in the m-pass use case. Further details can be found in Section 6.6.3

Validation Measurements

The validation of a m-ticket consists of two sub-phases. The transport cardlet has some pre-compuations in the first sub-phase. This sub-phase occurs in off-line for instance before arriving to station. Then, the second sub-phase comprises real-time computations. Indeed, these computations occur when the user taps his smartphone on the validator in order to enter the transport network.

Pre-Computations

The pre-computations consists in computing elements involved in proving that the user knows a valid signature on his secret s. The elements that the card has to store for one signature are 24 Z p elements, 10 compressed points and one digest output. The total size of these elements is 1130 bytes. In our implementation, we did pre-computations for 10 signatures (A set of 10 m-tickets). Regarding the timings, detailed in Table 7.2, the pre-computations for preparing one signature occurs in 1.7 s. which include the validator authentication, the signature generation and an m-ticket verification. The timings of the signature generation include as well the NFC exchanges duration. We denote by "Battery-Off" a powered-off phone either by the user, or because the battery is flat. In this situation, as stated by NFC standards, NFC-access to the SIM card is still possible, but with degraded performances.

Regarding the validator authentication, timings in Table 7.3, we chose to use RSA with a 1984 bits key (this is the greatest size supported by the SIM card.) and a short public verification exponent v (v = 65537). The validator asks the card for a challenge (RC V ). Then, he sends back his response to this challenge, his own challenge (ch) (32 bytes) and the current date (T S) (6 bytes).

Battery-On 56.98 ms (0.70) Battery-Off 76.55 ms (7.46) For the signature verification by the validator, timings in Table 7.5, we distinguish two cases: the validator holds the private signature keys (y, γ), or not. The extra pairing computations performed in the second case do not add an important delay to the verification step. This is because a regular desktop PC can efficiently achieve such computations.

(

) 1

Conclusion

In this chapter, we designed a secure m-ticketing protocol that prevents a malicious transport authority from linking users' trips. Moreover, as the entire computations are done within the SIM card, we enhance the user's privacy with regards to a compromised smartphone. Owing to regular reports of unused m-tickets, the user is able to securely post-pay for his m-tickets without disclosing any information about the performed trips. Moreover, we planned countermeasures against m-ticket cloning and multiple usage. Our proposal also satisfies the validation time constraint: an m-ticket validation can be completed in 184.25 ms when the mobile is switched on, and in 266.52 ms when the mobile is switched off or its battery is flat.

As mentioned previously our mobile services, i.e., mobile pass and mobile ticketing, are implemented within a SIM card, but, it can be implemented within a TEE as well. Using the TEE as a development platform have advantages as well as drawbacks. On one hand, it will provide more computational capabilities which will enable more efficiency. On the other hand, a functionality like the ability to validate a transport product when the smartphone is off will no longer be available. Moreover, a new technical issue arises. Indeed, if a user changes his smartphone, he obviously would like to have the same services within the new smartphone. If the application providing the service is running within the SIM card, the service can be easily and securely transfered from a smartphone to another (unplug / plug the SIM card). This is not the same case for the TEE. Therefore, we have worked on the problem of migration of services between two TEE and proposed, in the next chapter, a new secure TEE migration protocol.

Trusted Execution Environment (TEE for short). A TEE could have its own CPU and memory, and hosts isolated Trusted Applications (TA for short) that provide secure services to the applications running within the REE. These TAs belong to diverse service providers. Each TA manipulates a profile, constituted of secret credentials and user's private data.

The TEE has been standardized by GlobalPlatform, however, to the best of our knowledge, there is no specification or research work that models the TEE internal architecture or ecosystem. For instance, comparing to smart cards, the GlobalPlatform Card Specifications [START_REF][END_REF] have worked on such a model and it is now widely deployed and accepted by all the stakeholders. This is why we propose to study in which extent we can apply it for the TEE context: we identified the limitations of the GlobalPlatform Card model, in the TEE context, when the user wants to migrate its profile from one TEE to another one.

A user, who has many devices or gets a new one, shall be able to securely migrate his TEE profiles from a TEE to another compliant TEE. This problem of migration is currently poorly addressed by TEE implementations, standardization and only few papers have worked on designing TEE migration protocols [START_REF] Marforio | Secure enrollment and practical migration for mobile trusted execution environments[END_REF][START_REF] Kari Kostiainen | Towards user-friendly credential transfer on open credential platforms[END_REF]. Two main solutions can be considered: the straightforward solution, which consists in encrypting the profile (by TEE source), transferring it and decrypting it (by target TEE), or a Trusted Server based solution. These solutions present privacy weaknesses, as discussed in the next sections.

In this chapter, we propose a new approach to transfer the TEE profiles from a TEE to another compliant TEE while preserving its privacy. For this purpose, we propose to organize the TEE into security domains (SD) with different roles and privileges. This chapter is organized as follows. In Section 8.2, we present the TEE technology and describe the problem of profile migration. Then, in Section 8.3, we describe the previous works and discuss how different are our objectives. We define our assumptions and requirements in Section 8.4. Then, in Section 8.5, we give a detailed description of our transfer protocol. We give the security analysis of our protocol in Section 8.6. Finally, in Section 8.7, we present the validation of our protocol and we conclude in Section 8.8.

Backgrounds and Problem Statement

Before using a service of the TEE, which is provided by a service provider, several steps should occur.

1. User enrollment: the user registers to the service provided by the SP, using a secure channel. This step allows to associate the user identity to a dedicated TA inside the device.

2. The TA is personalized inside the TEE by the SP. The necessary application in the REE is also installed. After this step, the service is active.

3. The user could acquire a new device and wish to securely transfer its TEE profiles from the first device to the new one.

4. The user may want to destroy its profile, also defined as disabling credentials [START_REF] Kostiainen | Credential Disabling from Trusted Execution Environments[END_REF].

In this chapter we focus on step 3, the migration of a TEE profile. Like step 1, step 3 can be threatened by an external attacker. If we suppose that an attacker may have compromised the rich OS or control the network connection of the smartphone, then the enrollment or migration steps become challenging tasks. Indeed, as shown in Figure 8.1, as the interactions with a TEE crosses the REE, the attacker may succeed to migrate the user's profile from a victim to the attacker's smartphone. This attack may succeed because the service provider has no insurance about the TEE security and the user-to-TEE binding. In the next section, we describe the solutions already proposed in the literature in order to show their limitations and motivate a new way of migrating TEE profiles.

Related Work

The first papers that studied the security of TEE credentials tried to guarantee its local (within the TEE) confidentiality and integrity. For instance in [START_REF] Areno | Securing Trusted Execution Environments with PUF Generated Secret Keys[END_REF], authors proposed to protect TEE data using a unique PUF (Physical Unclonable Functions) AES encryption key for each device. In [START_REF] Kostiainen | Key Attestation from Trusted Execution Environments[END_REF], authors proposed a TEE key attestation protocol proving that a TEE key has been generated inside the TEE and never left this TEE.

Later, scientists have been interested in the enrollment problem (mainly user-device binding) while assuming that there is no operator responsible for the management of the TEE. For instance, Marforio et al. [START_REF] Marforio | Secure enrollment and practical migration for mobile trusted execution environments[END_REF] explained that the user's identity can be bound to the device using a password or a SMS or by collecting the device's IMEI. Unfortunately, an attacker that controls the Rich OS can intercept the protocol exchanges. Thus, Marforio et al. proposed some hardware and software modifications in order to secure the enrollment process. Others, like in [START_REF] Kari Kostiainen | Towards user-friendly credential transfer on open credential platforms[END_REF], assumed that the smartphone is safe at the first use. This would enable to store a secret password in the TEE.

The problem of credential migration first appears for Trusted Platform Module (TPM), which is in some way the TEE ancestor. The commands of key migration have been specified in TPM specifications [START_REF]TPM Main Specification[END_REF] and have undergone many improvements. Later, Sadeghi et al. [START_REF] Sadeghi | Property-based tpm virtualization[END_REF] proposed a property based TPM virtualization in order to have a solution that supports software update and migration. The shortcoming of this solution consists in omitting the service provider during the virtual TPM migration. However, some credential migration requires service provider fresh and explicit agreement.

In the specific context of TEE, the first attempt to address the problem of migration in the TEE has been proposed by authors of [START_REF] Kari Kostiainen | Towards user-friendly credential transfer on open credential platforms[END_REF]. Kari et al. have proposed a credential migration protocol in open credential platforms [START_REF] Kari Kostiainen | Towards user-friendly credential transfer on open credential platforms[END_REF]. They proposed to make the credential migration user-friendly based on delegated-automatic re-provisioning. The credentials are backup in clear in a trusted server. Then, the migration process is a reprovisioning from the backup, protected by a secret password only known by the user. The main weakness of this solution lies in the fact that its security, including to user's privacy, is entirely based on a the trustworthy of the trusted server (TS). This latter, as third party, has full access to TEE credentials and user's private data while it is not its owner or provisioner. This proposal implies privacy issues that we want to address in this thesis.

GlobalPlatform specifications related to smartcards have been interested in credential management in secure elements (smart cards). However, it seems that the credential privacy in some cases has been overlooked. In GlobalPlatform card specifications [START_REF][END_REF], the smart card is organized into fully isolated areas called Security Domains (SD). There are a root security domain called ISD for Issuer Security Domain and many Supplementary Security Domains (SSDs) for the different Service Providers. Let us call SPSD the security domain for a given SP. For instance, the ISD could be owned by the Mobile Network Operator (MNO) and the SPSD could be owned by a bank. Once, the SPSD created, there are two modes to manage the content of this SPSD: either directly from SP to SPSD, or through ISD. In the first case, the credential migration process would be naturally implemented in the application of the SP within the smart card: encryption with the target public key, transfer and decryption, provided that the MNO initiates the SP space in the target smart card. In the second case, the MNO plays the role of firewall and proxy for the SPSD without having access to the content between SP and its SSD (SPSD). SPSDs do not have any code enabling to perform a credential transfer.

If we adopt the first model for the TEE, the TEE profile migration would be processed like in the smart card: the TEE profile migration process would be naturally implemented in the TA of the SP: encryption with the target public TEE key, transfer and decryption, provided that the TEE admin -MNO initiates the SP space in the target TEE. As a consequence, each service provider would have to implement a migration process for its service.

If we adopt the second model for the TEE, TEE admin will serve as the single entry point to transfer point-to-point credentials: implementing the migration process would imply privacy issues similarly to the Kari et al. [START_REF] Kari Kostiainen | Towards user-friendly credential transfer on open credential platforms[END_REF] solution. TEE admin would have full access to the SP credentials and user's data in order to encrypt and transfer it. In this chapter, we propose a new migration protocol, while adopting the second model, where the TEE Admin plays the role of proxy without having access to SP credentials. We consider the following properties:

• As trusted application profile contains credentials and also personal data (statistics, usage data of the service), during the migration, the profile shall be accessible only by legitimate entities: the SP and the user;

• A special third party, the TEE admin should be responsible of the role of installation, deletion and migration of trusted profiles;

• The trusted application of the SP should not contain any code dedicated to the migration protocol. All the migration software components should be handled by the TEE admin.

Attacker Model and Requirements

We assume that the enrollment, provisioning and personalization processes are already achieved: the trusted application is provisioned to the TEE and has access to its credentials and the user's personal data. By the profile, we mean the credentials (allowing the access to the service) and private data (related to personalization and the use of application/service).

We consider three different actors: the user (the devices' owner), the Service Provider (e.g. the bank) and a TEE admin (e.g., Mobile Network Operator or smartphone manufacturer). Informally speaking, an attacker will attempt to access the transferred profile. We model it as follows:

A1: Communication control. We consider that we have a Dolev-Yao [START_REF] Dolev | On the security of public key protocols[END_REF] attacker model: an attacker has full control over communication channels.

A2: TEE control. We consider that TEEs are enough resistant to physical attacks according the Protection Profile proposed by GlobalPlatform [START_REF]TEE Protection Profile Version 1.2, Public Release[END_REF] which is EAL2+ certified.

A3: REE control. Given the possible vulnerabilities of the rich OS, we assume that an attacker can compromise the REE of a user's device.

A4: Entities control and trustworthy. We assume that (i) an attacker cannot spoof the SP, cannot compromise its dedicated spaces within the TEE and the SP is honest, (ii) an attacker cannot spoof the TEE Admin and cannot compromise its dedicated spaces within the TEE, however the TEE Admin can be honest-butcurious and, (iii) the user is honest.

While keeping in view the above discussions, we define the security requirements that a migration protocol shall meet as follows:

R1: Integrity. During the migration process, the integrity of the TEE profile should be ensured. For a given profile, only the user and the relevant service provider should be able to eventually modify the profile content.

R2: Confidentiality. During the migration process, the confidentiality of the TEE profile should be ensured. For a given profile, only the user and the relevant service provider should be able to eventually read the profile content.

TEE Migration Protocol

Considering the previous requirements, attacker model, and the GlobalPlatform Card Specifications [START_REF][END_REF], we introduce a new approach for deploying services in a TEE where:

TAs of a service provider are hosted in a Security Domain (SD) and a new actor, called TEE admin, has a special SD and implements the migration functionalities. With such a new software architecture, we build a protocol that allows to securely transfer a TEE profile from one device to another one.

Architecture Overview

We organize the TEE into Security Domains (SD) [START_REF][END_REF]. Every SD can contain one or many Trusted Applications (TA) from the same Service Provider. A SD is a fully isolated zone. This functionality could be ensured by memory protection mechanisms, firewall functionalities, data isolation techniques implemented at OS level of the TEE, such as the ones used for Linux systems (SELinux, AppArmor,...). For example, in the commercialized TEE solution of Trustsonic, such an architecture can be implemented using containers. A SD manipulates cryptographic keys which are completely separated from any other SD. These keys enable code execution integrity, credentials and user's private data integrity and confidentiality when using a service. Consequently, a SD must not cipher his credentials or user's private data using any external keys whatever is the case, e.g., transfer. We define two types of SD, represented in Figure 8.2a:

1. SD without management rights (many per TEE): SP-SD (in green). They contain the trusted applications of a service provider.

Protocol Overview

In order to migrate a TEE profile from a source device to a target one, the user gets the two devices nearby each other in order to establish a wireless communication, such as NFC or bluetooth. Then, the user starts the migration application, noted Migrate-SD in Figure 8.2a, within the ROOT-SD of the TEE source. In order to do this, the user must be authenticated in both source and target TEEs. Owing to the authentication procedure, the TEEs check that only the user enrolled by the TEE admin can start the migration process. This authentication can be done through the "Trusted User Interface" [START_REF]GlobalPlatform Device technology[END_REF], or by using the password or the pin code setup at the enrollment phase, or by using a biometry peripheral if available. The next steps of the protocol that involve the two TEEs are presented in Figure 8.2b and described in the following.

Step 1. An authenticated key agreement takes place between the ROOT-SD of TEE source and the ROOT-SD of target TEE. This prevents the TEE source from disclosing critical information to a malicious environment and prevents the target TEE from accepting malicious data.

Step 2. The TEE source requires a migration authorization from all service providers that have a SD within the TEE source. If a service provider does not agree with the migration of his relevant SD, the migration cannot take place. The migration authorization is temporary and unique per pair of devices, per transfer and per service provider. Indeed, the authorization is related to the date and time of the request that has been initiated. Thus, it is valid only for a given period of time.

Step 3. At that time starts the groundwork for the authorization. First, the service provider checks with the TEE admin whether the target TEE is stated compromised (its corresponding keys have been revoked). Then, the service provider checks that the target TEE is not already a client containing a service provider SD. Finally, the service provider asks the TEE admin to set up a specific SD within target TEE, and updates the SD credentials in order to be the unique master of this SD.

Step 4. Finally, the service provider replies to the TEE source with the authorization and necessary migration credentials. The authorization consists of a service provider signature proving his agreement regarding the migration of his SD. The credentials consist of a re-encryption key [START_REF] Blaze | Divertible Protocols and Atomic Proxy Cryptography[END_REF][START_REF] Canard | Improving the Security of an Efficient Unidirectional Proxy Re-Encryption Scheme[END_REF]. Using this re-encryption key, the Migrate-SD application will be able to perform the transfer without having access to SD profile. In order to send source profile to the target SD, the source SD provides its profile, encrypted with its public key, to the TA, Migrate-SD, that should re-encrypt it with the re-encryption key. In such a case, even if the TEE Admin is honest-but-curious, it cannot eavesdrop the SD profile.

Step 5. The target TEE must check the validity of the received authorization. At this time, the migration can start.

TEE Profile Migration Protocol

In the following, we introduce the notations and cryptographic keys used in our protocol. Later, we detail the phases of our protocol: Authenticated key agreement, Service Provider authorization and TEE Profile migration.

Cryptographic keys and notations

We denote (sk src , pk src , cert src ) (resp. (sk tgt , pk tgt , cert tgt )) the TEE private root key and the certified TEE public root key of the source (resp. target) ROOT-SD. These keys are used to authenticate the TEE and set up a key session with an authenticated TEE. A TEE admin is characterized by a private and public key pair (sk Admin , pk Admin ). It controls the ROOT-SD and certifies TEE root keys. A Security Domain SP-SD is characterized by a root keys set (sk sd , pk sd , cert sd ). This is an encryption keys set that enables to securely store SD profile. We denote SP -SD src (resp. SP -SD tgt ) the service provider SD within TEE source (resp. target TEE). Consequently, the tuple (sk SP -SDsrc , pk SP -SDsrc , cert SP -SDsrc ) (resp. the tuple (sk SP -SDtgt , pk SP -SDtgt , cert SP -SDtgt )) is the root keys set of SP -SD src (resp. SP -SD tgt ). A service provider is characterized by (sk sp , pk sp ) and a unique identifier ID SP . It provides the security domains root keys and is responsible of the re-encryption key and transfer authorization generation.

In the following, we denote by Signature A , the signature on the message sent with the signature using the private key of A.

Authenticated Key Agreement The authenticated key agreement (AKA, step 1 in Figure 8.2b) occurs in order to establish a secure session between two TEEs after a mutual authentication. The AKA can be a password based key agreement [START_REF] Coron | Supplemental Access Control (PACEv2): Security Analysis of PACE Integrated Mapping[END_REF] or a public key authenticated Key agreement [START_REF] Coron | SPAKE: A Single-Party Public-Key Authenticated Key Exchange Protocol for Contact-Less Applications[END_REF] and must be a two ways authentication. In the first case, we can use the password or PIN or biometric data introduced by the user during the authentication phase and in the second case, we can use the TEEs root keys. At the end of this phase, the source and target TEEs will share a couple of ephemeral keys (eK t , eK m ) to secure the migration. eK t is the private session key, whereas eK m is used for MAC computations.

Service Provider Authorization

The TEE source requires a migration authorization from all service providers having trusted applications within the TEE source (step 2 in Figure 8.2b). This protocol is described in Figure 8.3. For the sake of simplicity, we consider only one service provider.

( 11) Once the SP -SD tgt installed, the service provider proceeds to the update of SP -SD tgt credentials in order to have the exclusive control over SP -SD tgt [START_REF][END_REF].

Finally, the service provider generates the migration authorization. It consists of a reencryption key K proxy and a signature P ERM . The signature P ERM is computed on the SP identifier ID SP , source and target TEE public keys as well as a timestamp: P ERM = {ID SP , cert src , cert tgt , T imeStamp} sk SP . The re-encryption key K proxy is used to re-encrypt the SD -SP src content such that the result will be understandable only by SP -SD tgt : K proxy = rekeygen(pk SP -SDtgt , sk SP -SDsrc ). In the literature [START_REF] Blaze | Divertible Protocols and Atomic Proxy Cryptography[END_REF][START_REF] Canard | Improving the Security of an Efficient Unidirectional Proxy Re-Encryption Scheme[END_REF], K proxy is called a proxy key. (12,[START_REF] Vanderkay | Nokia, Philips And Sony Establish The Near Field Communication (NFC) Forum[END_REF] The authorization is sent to the TEE Admin who signs it and transmits it (with its signature) to ROOT -SD src .

TEE Profile Migration

Using the re-encryption key, the confidentiality and integrity of the migration phase is guaranteed. Any outsider cannot eavesdrop the SP -SD src profile and a honest-but-curious TEE Admin has no visibility about the SP -SD src profile. The migration occurs as follows.

As described in Figure 8.4, M igrate -SD src re-encrypts the protected profile of SP -SD src (P ) using the proxy key K proxy to obtain the cipher A. Only SP -SD tgt is able to decrypt A. Afterwards, M igrate -SD src computes B and C. B is the encryption of A and the identifier of the service provider owning SP -SD src (ID SP ) using the transfer key eK t . Regarding C, it is the MAC of A and ID SP using eK m . At the end of these computations, M igrate -SD src sends A, B, C and P ERM to M igrate -SD tgt . that proceeds to the verifications of P ERM and C. The verification of P ERM corresponds to the verification of a signature, its freshness and that its parameters contain the right cert src and cert tgt . Next, M igrate -SD tgt decrypts B in order to retrieve A and ID SP . Based on the retrieved ID SP , M igrate -SD tgt transmits A to SP -SD tgt .

When the migration finishes, we have two possibilities. On the one hand, the security policy of the service admits to conserve the TEE profile in the source. In such a case, M igrate -SD tgt simply acknowledges that the TEE profile migration is completed successfully (Signed Ack). On the other hand, the security policy of the service admits to conserve only one profile. The TEE profile in the source should be destroyed. In order to ensure a fair exchange, exchanges between M igrate -SD src and M igrate -SD tgt must be performed via the service provider. M igrate-SD tgt acknowledges that the TEE profile migration is completed successfully (Signed Ack). At this time, M igrate-SD src asks the trusted application Destroy -SD src to destroy the SD corresponding to ID SP . When the operation finishes, M igrate -SD src informs the service provider that the transfer is accomplished. Hence, the service provider will not consider any more TEE source as a client and revoke its corresponding keys. -------------------------→ (2) Verify(pk Admin , certsrc)

Verify(pk Admin , certtgt) ------------------------→ Decrypt(eKt, B) Retrieve ID SP Verify(pk SP , PERM)

Verify(pksrc, Signature ROOT -SDsrc ) certsrc, certtgt / ∈ {CompromisedT EE} 3) IN IT (pk SP -SDsrc ,certsrc, cert tgt ) ----------------------→ (4) certsrc ∈ {Clients} certtgt / ∈ {Clients} (5) SD-Create RQ(cert tgt ) ← ----------------------- (6) SD-Create() -------------------------------------------→
← ------------------------------------------- Signature ROOT -SD tgt (9)Verify(pktgt, Signature ROOT -SD tgt ) (10) P aram ------------------------→ (
Verify(eKm, C)

A --------------------→ Signed Ack ← ------------------------ Destroy SP -SDsrc Inform the SP

Performance Remarks

As current TEE implementation does not give access to low level cryptographic primitives we cannot implement the whole protocol. To give an idea of performances, the reader should note that TEEs exploit the CPU of the smartphone with an amount of RAM of some MBs. Thus performance are comparable with what can be obtained in the Rich OS. For example, a RSA computation is achieved in 20 ms on a Galaxy SIII smartphone. Our reencryption scheme needs lower than a RSA computation: we measured, on a Galaxy SIII a reencryption time of about 4 ms.

Security Analysis

User Identification During a TEE profile migration, it is important to ensure that the target TEE (target device) belongs to the owner of the source TEE (source device). In our model, this is guaranteed by the concept of demonstrative identification [START_REF] Balfanz | Talking to strangers: Authentication in ad-hoc wireless networks[END_REF]. Indeed, we proposed to run the migration protocol over a wireless proximity technology (NFC).

Requirements Analysis During the migration, an outsider or a curious TEE Admin must not be able to read or modify the transferred TEE profile (R1, R2). This is ensured by using the cryptographic re-encryption method. Indeed, the migration authorization, delivered by the service provider, consists of two components: K proxy and P ERM . P ERM is a signature computed by the service provider on (ID SP , cert src , cert tgt , timeStamp). An attacker would not be able to replay this authorization because of the timestamp. Moreover, the transfer process would fail if cert src (resp. cert tgt ) does not correspond to the certified root public key used by source TEE (resp. target) during the AKA phase. Regarding the re-encryption key K proxy , it is computed based on the private key of the source SD and the public key of the target SD. This means that a cipher text of source SD, if encrypted using K proxy , will be converted to a cipher text of target SD. Thus, only source SD, target SD and the service provider have access (read / modify) to the TEE profile. If the re-encryption key K proxy is improperly computed, the attacker cannot get the TEE profile content.

TEE Admin Trustworthy

Besides the cryptographic solution, our approach relies on the trustworthy of the TEE Admin. We assume that a TEE Admin can only be honest-but-curious and not malicious (compromised). Indeed, a malicious TEE Admin can get access to service provider credentials and user's private data. However, we estimate that the assumption of a honest-but-curious TEE Admin is reasonable. This is because a malicious TEE Admin (when detected) risks not only huge financial damages but also his reputation. Knowing that this role should be played by the device manufacturer or the mobile network operator. In our opinion, this risk is far from being taken.

Protocol Validation

We validated our protocol using the AVISPA [START_REF] Armando | The avispa tool for the automated validation of internet security protocols and applications[END_REF] tool web interface. AVISPA is an automated tool for the validation of security protocols. It takes as input a protocol modelled in High-Level Protocol Specification Language (HLPSL). This latter is translated into Intermediate Format (IF) and forwarded to the back-end analyser tools.

In Appendix A, we show (the core subset of) our migration protocol model written in HLPSL. In this validation model, we mainly focused on Service Provider authorization protocol (Figure 8.3) and Profile transfer protocol (Figure 8.4). Therefore, we assumed that the user authentication and AKA steps have been successfully achieved. Moreover, for the sake of simplicity, we did not consider the SP -SD tgt root key personalization.

We modeled our transfer protocol into six roles in addition to two standard roles (i.e. "session" and "environment"). First, the role "sdSrc" (resp. "sdTgt") refers to the SP -SD src (resp. SP -SD tgt ). Then, the role "src" (resp. "tgt") represents the Migration TA within TEE source (resp. target TEE). At last, "teeAdmin" and "sp" respectively correspond to the entities TEE admin and Service Provider. Every role is modelled into a state transition system. A state represents the reception and/or the transmission of a message from our protocol. For instance, "State = 0" in the role "teeAdmin" corresponds to the reception of IN IT RQ by the TEE administrator in Figure 8.3. Regarding the role called "session", it represents a single session of our protocol where all the other roles are instantiated.

All the roles communicate over Dolev-Yao [START_REF] Dolev | On the security of public key protocols[END_REF] channels (channel(dy)), i.e., an adversary can fully control the communication channels (A1). The attacker knowledge is defined by the set of constants or variables of the intruder knowledge set in the main role (environment) (A2, A3). Then, the intruder actions are modeled by the combination of several sessions where the intruder may take part of the sessions running. On the subject of our protocol, besides the initialization of intruder knowledge, we modeled our attacker by the variable i (i for intruder). We note that the attacker i did not compromise the SP and the TEE Admin nor their SDs (A4-i / A4-ii) because the roles "sdsrc", "sdtgt" and "spagent" are not played by the attacker in the initialized session (Line 198).

The migration authorization, delivered by the service provider, consists of two components: K proxy and P ERM . P ERM is a signature computed by the SP on (ID SP , cert src , cert tgt , timeStamp). Regarding K proxy , it is not a standard cryptographic tool. Thus, AVISPA does not have its predefined predicate. Our model must manually put up all its features. We designed the proxy re-encryption concept owing to the predicate ∧equal({EncSD} KProxy, {SDCred} PKSDtgt) at the end of the role "sdSrc". This predicate models the equality between "the encryption of EncSD (the encryption of SDCred using the public key of the source SD) using the proxy key" and "the encryption of SDCred using the public key of the target SD". If this equality does not hold, it means that K proxy is a fake key from an attacker which should be assimilated to a denied authorization of the SP.

The HLPSL language provides four predicates to model security requirements. The predicate secret(E, id, S) declares the information E as secret shared by the agents of set S. This security goal will be identified by id in the goal section. In addition, witness, request and wreuqest are used to model authentication goals. Regarding the security requirements R1 (integrity) and R2 (confidentiality with respect to outsiders and a curious TEE Admin), we defined them in one goal owing to the predicate secret(SDCred, sec S DCred, {SDsrc, SP, SDtgt}) at the end of the role "sdSrc". This predicate expresses that the content of an SD should remain secret between the SD of TEE source, the service provider and the SD of the target TEE.

We successfully validated our protocol with two AVISPA back-ends (AtSe and OFMC). The AtSe back-end extracts attacks that defeat the security properties by translating the model in constraints on the adversary's knowledge. Using a unification algorithm it integrates at each step of the protocol the new constraints. As our protocol is loop free, the search of possible attacks is complete. Regarding the OFMC back-end, it builds the infinite tree defined by the protocol analysis problem in a demand-driven way.

Conclusion

In this chapter, we have introduced a TEE architecture based on security domains. The root security domain is controlled by the TEE admin and the other security domains isolate the service providers trusted applications. With such an architecture, we have proposed a practical and privacy-preserving TEE profile migration protocol. This protocol requires the dynamic interaction of the service provider and the TEE admin. Owing to the security and functional characteristics of the used re-encryption method, the integrity and the confidentiality of the TEE profile, with respect to external attackers and TEE Admin, are guaranteed. Finally, we successfully validated our protocol using the AVISPA tool.

Chapter 9

Conclusion and Perspectives

(The french version is below)

In this thesis, we presented contributions related to contactless mobile services. In addition to a secure TEE migration protocol, we presented three privacy-preserving contributions, i.e., a new set-membership proof scheme and two new privacy-preserving protocols for the public transport service.

We first introduced a new set-membership proof enabling a prover to prove in a zeroknowledge way that he holds a secret belonging to a public set. The main idea is to prove that the user knows a public signature on this secret without revealing neither the secret nor the signature. Unlike the previous constructions, our set-membership proof does not require pairing computations at the prover side and in certain use cases at the verifier side too. This is very advantageous for resource constrained environments like the SIM cards as we will show in the implementation of our prototypes.

Then, we proposed a privacy-preserving mobile pass protocol based on Direct Anonymous Attestation and Camenisch-Lysanskaya signature schemes. This protocol enables a user to use the transport service without being tracked by the transport authority. We adapted the existing schemes in order to provide a revocation option. Owing to this property, the anonymity of a user can be lifted in extreme circumstances such as a judge request or a fraud. We also provided other security features like the anti-pass back or the black list management.

Afterwards, we provided a new privacy-preserving mobile ticketing protocol. Our protocol enables a user to use a book of m-tickets while ensuring the unlinkability of his trips. To this end, we used our new set-membership proof and provided several optimizations of Boneh-Boyen signatures in order to make it more efficient. Our protocol ensures a strict anonymity: even the index of a m-ticket must not be revealed during a m-ticket validation. We also defined a new feature: a secure post-payment mode where a user can post-pay his usage without questioning his privacy. Moreover, we proposed countermeasures against m-tickets cloning and double spending.

After building these protocols, for every one, we specified a framework, defined the security and privacy requirements in a game-based model, and proved their security in the random oracle model.

In addition to security and privacy requirements, that we specified in the security models, the transport service imposes a stringent time constraint, i.e., the validation time of a transport product must be less than 300 ms. We therefore implemented our protocols on a NFC-enabled SIM card in order to verify that our proposals satisfy this functional requirement. Indeed, we respected the time constraint regarding the validation time of the m-pass and the m-ticketing protocols. Our prototypes also have a major asset: they work, with a limited degradation of performance, even when the smartphone is off or the battery is flat.

Finally, the protocols previously presented can be implemented on TEE. Therefore, we focused on the security of TEE data and software. We presented a new TEE ecosystem and internal architecture in addition to a new approach to securely transfer TEE credentials and private data from a TEE to another one. Indeed, we organized the TEE into isolated security domains and introduced a new role, i.e., a TEE Admin who manages the TEE security by handling the creation and deletion of security domains, the download and installation of packages in SDs, and also the migration of SDs from a TEE to another compliant TEE. The main idea of the migration protocol is the use of a proxy re-encryption scheme. We validated our protocol using an automated security protocol validation tool.

Other interesting issues related to TEE security or privacy in mobile contactless services remain to be addressed.

We think that it is important to look at issues related to TEE credential attestation (external / internal). Indeed, as mentioned previously trusted applications within the TEE offer secure services to applications within the standard mobile OS. In order to perform their functions, the trusted applications handle secrets and credentials. If the credentials of a trusted application have been compromised, the offered service is not any more secure and trustworthy. Therefore, it is important to be able to prove that the used credentials have been generated and kept within the TEE, have not been revoked, and that the trusted application using these credentials is authorised to use them, i.e., the used credentials do not belong to another trusted application.

As regards to users' privacy, many privacy enhancing cryptographic tools exist, like the group signature schemes used in this thesis. It would be interesting to apply the optimizations introduced in this thesis in the context of other services like e-voting. Such application bears security requirements and constraints similar to the public transport use case. Indeed, in an e-voting system, voters must be authenticated (to verify that they are entitled to vote) while keeping their votes secret. This is quite alike to what is required in a transport service where subscribers should be authenticated whilst ensuring the anonymity of their transport product. Besides to these basic requirements, in evoting system, two additional properties should be satisfied: voters should be able to verify that not only their own votes have been taken into account in the final tabulation but also those of other voters. Moreover, they should not be able to prove how they voted in order to render useless any attempt of bribery or coercion. Although these properties do not have their counterparts in the transport context, the last one (coercionresistance) is usually obtained by using "anonymous credentials", which are generally based on group signatures. We believe that our optimizations on group signatures could significantly enhance the efficiency of coercion-resistant voting schemes.

Conclusion et perspectives

Dans cette thèse, nous avons présenté plusieurs contributions liées aux services mobiles sans contact, à savoir, une nouvelle preuve d'appartenance à un ensemble, deux nouveaux protocoles permettant de préserver la vie privée d'usagers des transports publics ainsi qu'un protocole sécurisé de transfert de secrets d'un TEE à un autre.

Notre première contribution consiste en une nouvelle preuve, à divulgation nulle de connaissance, permettant à un prouveur de convaincre un vérifieur que son secret, dont il a révélé une mise en gage, appartient à un ensemble public. L'idée principale est de prouver que l'utilisateur connaît une signature publique sur ce secret sans révéler ni le secret ni la signature. Contrairement aux constructions précédentes, notre preuve d'appartenance à un ensemble ne nécessite pas de calculs de couplages du côté du prouveur voire dans certains cas du côté du vérifieur. Ceci est très avantageux pour les environnements à ressources limitées comme les cartes SIM, comme cela a été illustré à travers l'implémentation de nos différents prototypes.

Nous avons ensuite proposé une carte d'abonnement aux transports publics, similaire au passe Navigo de la RATP mais offrant de meilleures garanties en termes de sécurité et de respect de la vie privée. Le détenteur d'une telle carte peut aussi prouver à une borne de transport qu'il dispose d'un titre de transport valide sans être tracé par l'autorité de transport. Nous nous somme appuyés pour cela sur des accréditations anonymes et des schémas de signature de type Camenisch-Lysanskaya. L'anonymat d'un usager peut toutefois être levée dans des circonstances exceptionnelles à la demande d'un juge par exemple ou bien en cas de fraude.

Nous avons également proposé un système de billetterie électronique pour les transports publics. Ce système est fondé sur l'utilisation de carnet de tickets anonymes et intraçables. Pour ce faire, nous avons utilisé notre nouvelle preuve d'appartenance à un ensemble et fourni plusieurs optimisations des signatures Boneh-Boyen. Notre système garantit un niveau d'anonymat élevé, même l'indice d'un m-ticket n'est pas révélé lors de sa validation. Nous offrons également une nouvelle fonctionnalité inédite pour ce type de systèmes: le post-paiement. Un utilisateur peut ainsi payer à postériori l'utilisation de ses m-tickets sans que cela ne remette en cause sa vie privée. En outre, nous avons proposé des contre-mesures contre le clonage de billets et les dépenses multiples.

Pour chacun de ces systèmes (carte d'abonnement et m-ticketing), nous avons spécifié le modèle de sécurité et formellement prouvé leur sécurité dans le modèle de l'oracle aléatoire.

Les services de transport imposent un cahier des charges très contraignant, en particulier, le temps de validation d'un titre de transport doit être inférieur à 300 ms. Nous avons donc implémenté nos protocoles sur une carte SIM NFC afin de vérifier que nos différentes propositions satisfont bien cette exigence fonctionnelle. Pour les deux cas, nos prototypes confirment que nous respectons bien cette contrainte de temps. Nos prototypes ont aussi un atout majeur: ils fonctionnent, avec une certaine dégradation limitée des performances, même lorsque le mobile est éteint ou que sa batterie est déchargée.

Enfin, les protocoles présentés précédemment peuvent être aussi implémentés sur le TEE. Par conséquent, nous nous sommes concentrés sur la sécurité des secrets dans le TEE. Nous avons présenté un nouvel écosystème du TEE et une nouvelle architecture interne en plus d'une nouvelle approche pour le transfert sécurisé de secrets d'un TEE à un autre. Nous avons organisé à cet effet le TEE en domaines de sécurité isolés et introduit un nouveau rôle, à savoir, un "TEE Admin" qui gère la sécurité du TEE notamment la création et la suppression des domaines de la sécurité, le téléchargement et l'installation de paquets dans un domaine de sécurité, et aussi la migration des domaines de sécurité d'un TEE à un autre TEE. L'idée principale du protocole de migration réside dans l'utilisation d'un système de proxy de re-chiffrement. Nous avons validé la sécurité de notre protocole en utilisant un outil automatique de vérification de protocole de sécurité. D'autres questions intéressantes liées à la sécurité du TEE ou bien au respect de la vie privée dans les services mobiles sans contact se posent.

Nous pensons qu'il est important d'examiner les questions liées à l'attestation des secrets du TEE (interne / externe). En effet, comme mentionné précédemment les applications de confiance du TEE offrent des services sécurisés aux applications de l'environnement mobile standard. Afin d'assurer leurs fonctions, les applications de confiance manipulent des secrets et des données privées. Si les secrets d'une application de confiance ont été compromis, le service offert n'est plus sûr. Par conséquent, il est important d'être en mesure de prouver que les secrets utilisés ont été générés et conservés dans le TEE, n'ont pas été révoqués, et que l'application de confiance qui les utilise est autorisée à le faire, autrement dit, les secrets utilisés n'appartiennent pas à une autre application de confiance.

En ce qui concerne le respect de la vie privée des utilisateurs, beaucoup d'outils cryptographiques existent, comme les schémas de signature de groupe utilisés dans cette thèse. Il serait intéressant d'appliquer les optimisations introduites dans cette thèse dans le contexte d'autres services comme le vote électronique (e-vote). Cette application a des exigences de sécurité et des contraintes similaires à celles d'un service de transport en commun. En effet, dans un système de vote électronique, les électeurs doivent être authentifiés (pour vérifier qu'ils sont autorisés à voter) mais leur vote doit rester secret. Ceci est tout à fait semblable à ce qui est requis dans un service de transport, où les abonnés doivent être authentifiés, sans compromettre l'anonymat de leurs titres de transport. Outre ces exigences de base, dans un système de vote électronique, deux autres propriétés de sécurité doivent être satisfaites: les électeurs devraient être en mesure de vérifier que non seulement leurs propres votes ont été pris en compte dans le dépouillement final, mais aussi ceux des autres électeurs. En outre, ils ne devraient pas être en mesure de prouver comment ils ont voté afin de déjouer toute tentative de coercition ou de corruption. Bien que ces propriétés n'aient pas d'équivalent dans le contexte du transport, la dernière (la propriété de résistance à la coercition) est généralement obtenue en utilisant des " accréditations anonymes ", qui sont souvent basées sur les signatures de groupe. Nous pensons donc que nos optimisations sur les signatures de groupe pourraient améliorer considérablement l'efficacité des systèmes de vote proposant des contre-mesures aux les tentatives de coercition ou de corruption.

Thesis Publications

International Journal

Figure 1 . 1 :

 11 Figure 1.1: Mobile Services and Applications

2. 4 . 4

 44 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

Figure 2 . 1 :

 21 Figure 2.1: Contactless Mobile Services

1 (Figure 2 . 2 :

 122 Figure 2.2: Public Transport Service Phases

1. Anonymity of the user 2 .

 2 Unlinkability between the different mpass usages 1. Anonymity of the user 2. Unlinkability between the serial numbers of different m-tickets 3. Anonymity of a m-ticket index Structure 1 m-pass N m-tickets Trips ∞ 1 ticket per trip

Figure 2 .

 2 Figure 2.3 gives an overview of the current smartphone architecture. Besides to the NFC component, the UICC (i.e., SIM card) and the mobile environment (Mobile OS), today, a new family of embedded environments, usually called Trusted Execution Environments (TEE), has emerged. Further, we give further details about the NFC technology provided by the NFC component and the security features of the mobile device, i.e., SIM card and TEE. We then investigate the differences between a TEE and a SIM card in order to get a feel for the implementation of our transport application in these environments

Figure 2 . 4 :

 24 Figure 2.4: Smart Card Architecture [1]

Figure 2 . 5 :

 25 Figure 2.5: TEE Software Architecture

  Distributive multiplication over addition: ∀a, b, c ∈ K, a.(b + c) = (a.b) + (a.c) and (a + b).c = (a.c) + (b.c)

Figure 3 . 1 :

 31 Figure 3.1: Addition Operations on an Elliptic Curve

A

  of the user A and D T arget B of the user B and outputs the re-encryption key R A→B from A to B. R A→B ← ReKeyGen(params, D Source A , D T arget B )

Figure 4 . 1 :

 41 Figure 4.1: A New Efficient Set-Membership Proof

Figure 5 . 1 :

 51 Figure 5.1: The refund protocols of Rupp et al. solution[2]

Figure 5 . 2 :

 52 Figure 5.2: Architecture Overview

Figure 6 . 1 :

 61 Figure 6.1: M-Pass Framework Overview

Figure 6 . 2 :

 62 Figure 6.2: User's Private Key Generation Protocol

Figure 6 . 3 :

 63 Figure 6.3: Registration Protocols

  J , K, R, S, T, W, R1, R2, rc) If the user is blacklisted, then access is denied. Otherwise, access is granted.

Figure 6 . 4 :

 64 Figure 6.4: SignMPass / VerifyMPass -Validation Protocol

1 -

 1 Public input: pkg, DBt, σ Public Input: pkg Private Input: skt Private Input: sko, DBo σ ------Find (C1, C2, µ) in DBo such that: e(J, C2) = e(K, G2) Knowing C1 C ------Find (IDuser, C1) in DBt

Figure 6 . 5 :

 65 Figure 6.5: IdentUser -User De-Anonymization Protocols

Figure 6 . 6 :

 66 Figure 6.6: Protocol for Blacklisting a User.

Figure 6 . 7 :

 67 Figure 6.7: Unlinkability Security Experiment

2 .

 2 (gpk, skt, sko) ← Keygen(pp) 3. (σ, bsn, rc) ← A(gpk, skt, sko, DBt, DBo: ORegister HU , ORegister M U , OCorruptU ser, OGetM P ass U , OSignM P ass) 4. If VerifyMPass(gpk, σ, bsn, rc) =⊥ or IdentUser(σ, DBo, DBt) =⊥ then return 0 5. If IdentUser(σ, DBo, DBt) = ID U ∈ HU and (ID U , σ, bsn, rc) / ∈ Set then return 1 else return 0.

Figure 6 . 9 :

 69 Figure 6.9: Non-frameability Security Experiment

  Challenge phase: A outputs two honest identities ID i 0 and ID i 1 , a message rc and a basename bsn. D randomly selects a bit b and aborts if ID i b = ID U i * . Else it issues a signature σ b on rc and bsn on behalf of i b as follows: if no hash request was submitted on bsn, then it selects δ ∈ Z * p and γ ∈ Z * p and outputs H 1 (bsn) = [δ]G 1 . It then computes the values (R, S, T , W , K) of the signature σ as follows: R = [b + γ]G 1 (where [b]G 1 comes from the XDH challenge), S = [y(b + γ)]G 1 , T = [x](R + W ) and W = [y]([α]C + [β]B + [αγ]A + [βγ]G 1

Contents 7 . 1

 71 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Framework of an M-Ticketing System . . . . . . . . . . . . . 7.3 Untraceable Mobile Ticketing System . . . . . . . . . . . . . 7.3.1 M-ticketing Protocol . . . . . . . . . . . . . . . . . . . . . . . . 7.3.2 A Secure Post-Payment Process . . . . . . . . . . . . . . . . . . 7.4 Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4.1 Functional Requirements . . . . . . . . . . . . . . . . . . . . . 7.4.2 Security and Privacy Model . . . . . . . . . . . . . . . . . . . . 7.5 Security Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 7.6 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 7.6.1 Prototype Details . . . . . . . . . . . . . . . . . . . . . . . . . . 7.6.2 Validation Measurements . . . . . . . . . . . . . . . . . . . . . 7.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1. Anonymity of the user 2 . 1 .

 21 Unlinkability between the different mpass usages Anonymity of the user 2. Unlinkability between the serial numbers of different m-tickets 3. Anonymity of a m-ticket index Structure 1 m-pass N m-tickets Trips ∞ 1 ticket per trip

Figure 7 . 1 :

 71 Figure 7.1: M-Ticketing Framework Overview

  {B k } of size max ticket Transport Authority Validator (ID V ) DB REG DB U sedT ickets Registration: (ID U , h U ) st o re Permission Token: A (A, C 0 , s 2 , c, µ) st or e Reporting unused B k c h e c k Verification of Π ch T ick k : (B k , E, Π) s t o r e ( B k , E , Π , I D V , D T ) Ticket Validation RSA Signature of T S: timestamp RC V : challenge RSA(RC V , T S)

Figure 7 . 2 :

 72 Figure 7.2: The M-Ticketing Protocol Overview

Figure 7 . 4 :

 74 Figure 7.4: The validation Protocol

7 .

 7 For all T ick k in DB do {b = IdentDuplicate(B k , DB) where B k is the serial number of the m-ticket T ick k If b¿1, then delete all the duplicates of the m-ticket T ick k . If IdentUser(rsk, DB REG , T ick k ) outputs ⊥ then return 1 and aborts. } 8. If L the number of m-tickets that remained within DB is greater that N * max ticket (L > N * max ticket ) where N is the number of calls of the oracle OT okenRequest T and max ticket is the number of authorized m-tickets by token, then return 1 else return 0

Figure 7 . 5 :

 75 Figure 7.5: Unforgeability Security Experiment

2 .

 2 (gpk, tsk, rsk) ← Keygen(pp) 3. (T ick k ) ← A(gpk, tsk, rsk, DB REG , DB U sedT ickets : ORegister HU , ORegister M U , OCorruptU ser, OT okenRequest U , OGen T icket, OReportT icket) 4. If ValidateTicket(gpk, T ick k ) = 0 or IdentUser(rsk, DB REG , T ick k ) =⊥ then return 0 5. If IdentUser(rsk, DB REG , T ick k ) = ID U ∈ HU and (ID U , T ick k ) / ∈ Set then return 1 else return 0.

Figure 7 . 6 :

 76 Figure 7.6: Non-frameability Security Experiment

10. Return b Figure 7 . 7 :

 b77 Figure 7.7: Unlinkability Security Experiment

  i 1-b 's belongs to {1, ..., m}. • Game(0,b): This is the same game as Game 0 except that we replace the El Gamal ciphertext E b by an encryption of a random value and then simulate the proof Π b . Such a simulated proof can easily be done in the random oracle model using standard techniques. Under the DDH assumption, A cannot detect this change. Indeed, we can easily construct a DDH distinguisher D with DDH-advantage satisfying: |P r[S 0 ] -P r[S (0,b) ]| ≤ Adv DDH D (1 λ ) (1) where Adv DDH D (1 λ ) is the DDH-advantage of D in solving the DDH problem.

•

  Game(0,1-b): This is the same game as Game(0,b) except that we replace the El Gamal ciphertext E 1-b by an encryption of a random value and then simulate the proof Π 1-b . Such a simulated proof can easily be done in the random oracle model using standard techniques. Under the DDH assumption, A cannot detect this change. Indeed, we can easily construct a DDH distinguisher D with DDHadvantage satisfying: |P r[S (0,b) ] -P r[S (0,1-b) ]| ≤ Adv DDH (2)

Figure 8 . 1 :

 81 Figure 8.1: The Life Cycle of a TEE-based Service

2 .

 2 SD with management rights (only one per TEE): ROOT-SD (in orange). It is responsible of creating and deleting SDs, downloading and installing packages in SDs, and also migrating SDs from a TEE to another compliant TEE.

Figure 8 . 2 :

 82 Figure 8.2: Architecture and Protocol Overview

11 )Figure 8 . 3 :

 1183 Figure 8.3: Service Provider Authorization Protocol

Figure 8 . 4 :

 84 Figure 8.4: Profile Migration Protocol

  : a g e n t , PKSDsrc , PKTgtTEE , PKTEEAdmin : p u b l i c k e y , SK : s y m m e t r i c k e y , SND, RCV : c h a n n e l ( dy ) ) p l a y e d b y TgtTEE d e f= l o c a l S t a t e : nat , SDCred , Param : t e x t , Ack , SDCreate : message , Kproxy : p u b l i c k e y i n i t S t a t e :=0 t r a n s i t i o n 1 . S t a t e = 0 /\ RCV( SDCreate ' . { SDCreate ' } i n v ( PKTEEAdmin ) ) =|> S t a t e ' : = 1 /\ Param ' : = new ( ) /\ SND( Ack . Param ' . { Ack . Param ' } i n v ( PKTgtTEE ) ) 2 . S t a t e = 1 /\ RCV( { { { SDCred ' } PKSDsrc } Kproxy ' } SK ) =|> S t a t e ' := 2 /\ Ack ' : = new ( ) /\ SND( { Ack ' } SK ) /\ SND( { { SDCred ' } PKSDsrc } K p r o x y ) end r o l e r o l e sdTgt ( SDtgt , TgtTEE : a g e n t , PKSDsrc : p u b l i c k e y , SND, RCV : c h a n n e l ( dy ) ) p l a y e d b y SDtgt d e f= l o c a l S t a t e : nat , SDCred : t e x t , Kproxy : p u b l i c k e y i n i t S t a t e :=0 t r a n s i t i o n 1 . S t a t e = 0 /\ RCV( { { SDCred ' } PKSDsrc } Kproxy ' ) =|> S t a t e ' := 1 end r o l e r o l e s e s s i o n ( SDsrc , SrcTEE , TgtTEE , TEEAdmin , SP , SDtgt : a g e n t , PKSDsrc , PKSrcTEE , PKTgtTEE , PKTEEAdmin , Kproxy , PKSDtgt : p u b l i c k e y , SK : s y m m e t r i c k e y ) d e f= l o c a l SND0 , SND1 , SND2 , SND3 , SND4 , SND5 , RCV0 , RCV1 , RCV2 , RCV3 , RCV4 , RCV5 : c h a n n e l ( dy ) c o m p o s i t i o n s d S r c ( SDsrc , SrcTEE , SDtgt , SP , PKSDsrc , Kproxy , PKSDtgt , SND0 , RCV0) /\ s r c ( SrcTEE , SDsrc , TgtTEE , TEEAdmin , PKSDsrc , PKSrcTEE , PKTgtTEE , PKTEEAdmin , SK , SND1 , RCV1) /\ teeAdmin ( TEEAdmin , SrcTEE , TgtTEE , SP , PKSDsrc , PKTEEAdmin , PKSrcTEE , PKTgtTEE , SK , SND3 , RCV3) /\ s p ( SP , TEEAdmin , PKSDsrc , PKSrcTEE , PKTgtTEE , Kproxy , SND4 , RCV4) /\ t g t ( TgtTEE , SrcTEE , TEEAdmin , PKSDsrc , PKTgtTEE , PKTEEAdmin , SK , SND2 , RCV2) /\ sdTgt ( SDtgt , TgtTEE, PKSDsrc , SND5 , RCV5) end r o l e r o l e e n v i r o n m e n t ( ) d e f= c o n s t s d s r c , s r c t e e , t g t t e e , t e e a d m i n , s p a g e n t , s d t g t : a g e n t , s e c S D C r e d : p r o t o c o l i d , p k s d s r c , k p r o x y , p k s r c t e e , p k t g t t e e , p k t e e a d m i n , p k s d t g t : p u b l i c k e y , s k : s y m m e t r i c k e y i n t r u d e r k n o w l e d g e = { s d s r c , s r c t e e , t g t t e e , t e e a d m i n , s p a g e n t , s d t g t , k p r o x y , p k s d s r c , p k s r c t e e , p k t g t t e e , p k t e e a d m i n , p k s d t g t } c o m p o s i t i o n s e s s i o n ( s d s r c , s r c t e e , t g t t e e , t e e a d m i n , s p a g e n t , s d t g t , p k s d s r c , p k s r c t e e , p k t g t t e e , p k t e e a d m i n , k p r o x y , p k s d t g t , s k ) end r o l e g o a l s e c r e c y o f s e c S D C r e d end g o a l e n v i r o n m e n t ( )

Table 2 .

 2

1: Comparison between the M-Pass and M-Ticketing use cases

Table 2 .

 2

2: Comparison between a REE, a TEE and a NFC-enabled SIM Card

Table 5 .

 5

	Ref. Tamrakar et al. [91, 92] Heydt-Benjamin et al. [93] Derler et al. [94] Isern-Deya et al. [97] Rupp et al. [2]	Anonymity × √ √ √ √	Unlinkability × √ × √ ×	Hardware Mobile / TEE × Mobile and Secure Element Mobile Secure Element	Efficiency √ × × × ×

2. Unlinkability: the ability to track a user either over one journey (entrance and exit of the journey) or over different journeys, by outsiders or the transport authority, 3. Hardware: the hardware that has been used for the implementation, if the proposal has been implemented, and 4. Efficiency: a proposal is efficient if the validation time is less than 300ms. 1: Comparison of the analyzed proposals

  Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 6.4.1 Functional Requirements . . . . . . . . . . . . . . . . . . . . . 69 6.4.2 Security and Privacy Model . . . . . . . . . . . . . . . . . . . . 69 6.5 Security Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

	Chapter 6
	A Practical and
	Privacy-Preserving Mobile Pass

Contents 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 6.2 Framework of an M-Pass System . . . . . . . . . . . . . . . . 61 6.3 Untraceable Mobile Pass . . . . . . . . . . . . . . . . . . . . . 63 6.3.1 M-Pass Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . 63 6.3.2 Countermeasures . . . . . . . . . . . . . . . . . . . . . . . . . . 67 6.4 72 6.6 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 79 6.6.1 Validator Details . . . . . . . . . . . . . . . . . . . . . . . . . . 79 6.6.2 SIM Card Details . . . . . . . . . . . . . . . . . . . . . . . . . . 79 6.6.3 Curve and Pairing Parameters . . . . . . . . . . . . . . . . . . 80 6.6.4 Performance Results . . . . . . . . . . . . . . . . . . . . . . . . 80 6.7

  ). If

		Register: Registration within the database of the opening authorities
	Smartcard cardlet	Opening authorities
	Public input: pkg, C 2	Public Input: pkg
	Private Input: sku	Private Input: sko, DBo
	r	$ ← Z *

p Compute:

  µ) in DBo

		GetMPass: Registration within the database of the transport authority
	Smartcard cardlet	Transport authority
	Public input: pkg, µ	Public Input: pkg
	Private Input: sku	Private Input: skt, DBt
	j	$ ← Z *

n Compute:

  retrieves sk u i and proceeds normally to obtain a certificate on sk u i . Else, it randomly chooses a value C 0 ∈ Z n 2 and simulates the proof Π Hash requests: upon receiving the j-th request on bsn, D proceeds as follows: if no previous request was made on bsn, then we distinguish two cases: if j = j * , then D selects δ ∈ Z * p and outputs H 1 (bsn) = [δ]G 1 . Else, it selects γ ∈ Z * p and outputs H 1

1 (this is possible in the random oracle model) and obtains a blind CL-certificate (A, B, C, D) on C 1 = [αa + β]G 1 .

•

Table 6 . 2

 62

: M-Pass -Timings of Real-Time Operations

Table 7 .

 7

1: M-Pass vs M-Ticketing

  k 1 and T ick k 2 , have the same token pair (since L > N × max ticket . Let us denote by (s * 1 , k 1 ) (respectively (s * 2 , k 2 )) the token pair corresponding to T ick k 1 (respectively T ick k 2 ). Therefore the serial number B * k 1 of T ick k 1 would be equal to B * k 2 the one of T ick k 2 : B * k 1 = g Without loss of generality, we do not make any distinction between a m-ticket and an unused m-ticket. = B * k 2 . This case cannot occur since all duplicates (i.e. m-tickets which have the same serial numbers) are discarded in the experiment Exp unf org A (1 λ ). Suppose now that s * ∈ {s 1 , s 2 , . . . , s N }. Since (s * , k * ) /

	1/(s * 1 +k 1 +1 t	= g	1/(s * 2 +k 2 +1 t

3

  for i 1 and send them to A. The goal of A is to guess the value of b. After having received its challenge, A can queries the ORegister HU , ORegister M U , OCorruptU ser, OT okenRequest U , OGenT icket, OIdentT icket T and OReportT icket oracles but with the following restrictions: it cannot query the O CorruptU ser oracle on i 0 or i 1 or the OIdentT icket T oracle on (i 0 , view 0 ) or (i 1 , view 1 ) and cannot query the OReport T icket oracle on (i 0 , view 0 ) or (i 1 , view 1 ) if both users did not validate the same number of m-tickets (otherwise it can easily win this game).

Table 7 .

 7

	1 m-ticket 10 m-tickets
	1.7 s	17 s
	2: M-Ticketing -Timings of Pre-Computations
	7.6.2.2 Real-Time Computations
	Tables 7.3, 7.4, 7.5 and 7.6, give timings (average over 50 trials and standard devia-
	tion between parentheses) for all real-time computations (the whole validation protocol)

Table 7 .

 7 3: M-Ticketing -Timings of the Validator Authentication

Table 7 .

 7 4 gives the duration of a signature generation (computing an m-ticket B k , E and Π) and the NFC communication time. The considered operations for generating the signature are only one hash value and lightweight operations in Z p . The size of the computed signature is 778 bytes (sent by 4 APDUs). Regarding the communication between a SIM card and a reader, it is slow (≥ 85ms), but the whole process (Signature+NFC) remains very fast, i.e., 123.01 ms on average.

	Battery-On 123.01 ms (3.24)
	Battery-Off 185.28 ms (18.68)

Table 7 .

 7 4: M-Ticketing -Timings of the Card Signature and NFC Connections

Table 7 .

 7 5: M-Ticketing -Timings of the Signature Verification

Table 7 .

 7 [START_REF] Hager | Divorce Lawyers Using Fast Lane To Track Cheaters[END_REF] gives the total duration of a m-ticket validation. In total, it occurs for the first case (without pairing at the verifier side) in 184.25ms on average and in 191.80ms for the second case (with pairing at the verifier side). When the battery is flat, the validation occurs in at most 272, 55ms on average.

		(1) without pairing	(2) with pairing
	Battery-On	184.25 ms (3.43)	191.80 ms (4.73)
	Battery-Off 266.52 ms (17.91) 272.55 ms (25.73)

Table 7 . 6 :

 76 M-Ticketing -Timings of Real-Time Computations

  ) The migration application within ROOT -SD src sends the request IN IT RQ with its signature noted Signature ROOT -SDsrc to the service provider through the TEE admin. The request includes the identity of the service provider (ID SP ), the public key of SP -SD src (pk SP -SDsrc ) and the certified TEE public root keys of source and target TEE (cert src , cert tgt ). (2) When receiving the request, TEE admin checks the certificates (cert src , cert tgt ), the signature and freshness of the request and a timestamp (Signature ROOT -SDsrc ) 1 . It should also check whether source or target TEE are compromised 2 for example using the remote attestation protocols of Baiardi et al.[START_REF] Baiardi | Measuring Semantic Integrity for Remote Attestation[END_REF]. (3) If checks are successful, the TEE admin transmits the request (IN IT ) to the relevant service provider based on the ID SP received within the request.(4) With the received request, the service provider checks if the TEE source (resp. target TEE) has (resp. has not) an associated SP-SD by checking if cert src (resp. cert tgt ) is registered in its database. Then, (5) the service provider inquires TEE admin to create a SP-SD within the recipient TEE via the SD -Create RQ(cert tgt ) command.[START_REF] Hager | Divorce Lawyers Using Fast Lane To Track Cheaters[END_REF] The TEE admin signs the command (the signature Signature T EE Admin is performed on the command and a timestamp) and forwards it to the trusted application Create -SD tgt in order to create SP -SD tgt .(7,[START_REF] Funk | Kaspersky Security Bulletin[END_REF][START_REF] Armando | The avispa tool for the automated validation of internet security protocols and applications[END_REF][START_REF](KSCC), and The Seoul Metropolitan Government. 4th Asian Transport Revenue Collection Forum[END_REF]. The creation is acknowledged by Ack and P aram that are returned to the service provider (through the TEE Admin) in order to let him be able to personalize SP -SD tgt , as done classically when personalizing TEE security domains. (

  IN IT RQ(ID SP ,pk SP -SDsrc , certsrc,cert tgt ), Signature ROOT -SDsrc

	ROOT -SDsrc	T EE Admin	SP	ROOT -SDtgt
	(sksrc, pksrc, certsrc)	(sk Admin , pk Admin )	(sksp, pksp) (sktgt, pktgt, certtgt)
	(1)

•

  Ghada Arfaoui, Guillaume Dabosville, Sébastien Gambs, Patrick Lacharme, and Jean-François Lalande. A Privacy-Preserving NFC Mobile Pass for Transport Systems. EAI Endorsed Transactions on Mobile Communications Applications, 14(5), 2014. doi:10.4108/mca.2.5.e4. • Ghada Arfaoui, Jean-François Lalande, Jacques Traoré, Nicolas Desmoulins, Pascal Berthomé, and Saïd Gharout. A Practical Set-Membership Proof for Privacy-Preserving NFC Mobile Ticketing. Proceedings of Privacy Enhancing Technologies (PoPETs), 2015.2 : 25-45, June 2015. doi:10.1515/popets-2015-0019 International Conferences • Ghada Arfaoui, Sébastien Gambs, Patrick Lacharme, Jean-François Lalande, Roch Lescuyer, and Jean Claude Paillès. A Privacy-Preserving Contactless Transport Service for NFC Smartphones. In Mobile Computing, Applications, and Services -5th International Conference, MobiCASE 2013, Paris, France, November 7-8, 2013, Revised Selected Papers, pages 282-285, 2013. doi:10.1007/978-3-319-05452-0 24. • Ghada Arfaoui, Saïd Gharout, and Jacques Traoré. Trusted Execution Environment. In The International Workshop on Trusted Platforms for Mobile and Cloud Computing (TPMCC) held at Mobile Cloud Computing, Services, and Engineering (MobileCloud), 2014 2nd IEEE International Conference on, pages 259-266, Oxford, UK, April 2014. doi:10.1109/MobileCloud.2014.47. • Ghada Arfaoui, Saïd Gharout, Jean-François Lalande, and Jacques Traoré. In Information Security Theory and Practice -9th IFIP WG 11.2 International Conference, WISTP 2015 Heraklion, Crete, Greece, August 24-25, 2015 Proceedings, pages 153-168, 2015. doi:10.1007/978-3-319-24018-3 10. Ghada Arfaoui and Jean-François Lalande. A Privacy Preserving Post-Payment Mobile Ticketing Protocol for Transports Systems. In Atelier sur la Protection de la Vie Privée, APVP 2014, Cabourg, France, June 2014. l o c a l S t a t e : nat , Param : t e x t , PERM, SDCreate : message i n i t S t a t e :=0 t r a n s i t i o n 1 . S t a t e = 0 /\ RCV( PKSDsrc . PKSrcTEE . PKTgtTEE ) =|> S t a t e ' := 1 /\ SND( SDCreate . PKTgtTEE ) 2 . S t a t e = 1 /\ RCV( Param ' ) =|> S t a t e ' := 2 /\ SND( Kproxy .PERM) end r o l e r o l e t g t ( TgtTEE , SrcTEE , TEEAdmin

	National Conferences
	•

Afin d'atteindre nos objectifs dans le cas d'usage "m-ticketing", nous proposons plusieurs optimisations cryptographiques aux preuves d'appartenance à un ensemble. Notre système permet à un prouveur de prouver, sans divulgation de données, qu'il détient un secret appartenant à un ensemble public donné. Ces preuves sont faites sans nécessiter de calculs de couplage, principalement du côté du prouveur. En effet, dans les constructions précédentes de preuves d'appartenance à un ensemble, le prouveur a besoin d'effectuer des calculs de couplage qui sont coûteux, en particulier pour les dispositifs à ressources limitées comme la carte SIM. Cette contribution est d'un intérêt indépendant et peut être utilisée à d'autres fins lorsqu'une telle preuve est nécessaire dans un contexte où les ressources sont limitées.En plus de la conception et de la formalisation des protocoles de transport respectant la vie privée, nous proposons une implementation de ces protocoles sur une carte SIM et montrons qu'ils satisfont les exigences fonctionnelles, notamment la stricte contrainte de temps.En ce qui concerne les attaques contre le service, elles visent à introduire des troubles dans le service. Un attaquant externe peut essayer de perturber le service ou même le rendre indisponible. Cela peut se produire, par exemple, en contrôlant à distance l'appareil de l'utilisateur à travers un malware. De même, un utilisateur malveillant peut tenter de compromettre l'application mobile, et donc compromettre la sécurité du service, afin de tricher. Par exemple, dans un service donnant accès à un système de transport, il peut essayer de modifier le montant d'un voyage ou de dépenser plusieurs fois le même billet. Les problèmes de sécurité décrits précédemment sont réalisables, car les environnements mobiles, hébergeant les applications mobiles, sont vulnérables. Différents types de failles sont fréquemment détectés. En 2013, l'analyse de Kaspersky Security a indiqué que 148,778 malwares mobiles ont été détectés[START_REF] Funk | Kaspersky Security Bulletin[END_REF]. Dans ces circonstances, une nouvelle famille d'environnements mobiles, appelé environnements d'exécution de confiance, est en train d'émerger afin de fournir une plus grande protection aux applications, et donc, aux services fournies. Un environnement d'exécution de confiance (Trusted Execution Environment, TEE) est défini comme un système d'exploitation sécurisé s'exécutant parallèlement au système d'exploitation standard, appelé également environnement d'exécution riche (Rich Execution Environment, REE), et possédant ses propres CPU et mémoires. Le TEE devrait héberger des applications de confiance, comme les applications bancaires ou de transport, qui fournissent des services sécurisés à des applications mobiles fonctionnant au sein du REE.

This situation does not question the security of our protocol because the validator belongs to the transport authority trusted area.

We would like to emphasize that since the output of IdentUser can be publicly verifiable, a wrong IdentUser procedure is statistically negligible (even for a powerful adversary).

TEE implementations like TrustZone offer access to trusted clocks for this usage.

This is already the case for SIM card where MNOs checks if a SIM has been revoked.

Acknowledgments

First of all, I would like to express my gratitude to my advisors: Professor Pascal Berthomé, Doctor Saïd Gharout, Doctor Jean-François Lalandes and Doctor Jacques Traoré. I appreciate all your contributions of time and ideas in order to make my Ph.D experience productive. Thank you for all your priceless advices on my research or my career.

Besides to my advisors, my thanks also go to the members of my PhD committee.

Abbreviations

known by the user and TA). Thanks to his permission token, the user will be able to use max ticket m-tickets. The value of max ticket is set by TA and linked to the key pair (γ, W = g γ 2 ) used by TA during the permission token request protocol. TA will use a different pair of keys for each possible value of max ticket , i.e., for each group associated to each type of m-tickets book.

At the end of this phase, TA saves in DB REG the view (A, C 0 , s 2 , c, µ) where C 0 is the Paillier encryption of s 1 such that the secret s = s 1 + s 2 and (c, µ) are the commitment and signature by the user of his secret s.

User

Transport Authority Public input: The public parameters Public Input: The public parameters Private Input:

Validation

In this phase, the validator is authenticated, the permission token is verified and finally the m-ticket is validated.

Validator Authentication

The validator authentication consists of a challenge / response protocol. The user sends a Random Challenge RC V to the validator gate. Upon receiving RC V , the validator replies with the RSA signature on a timestamp (T S) and the received challenge (we use a short public verification exponent v in order to have a fast verification in the SIM card).

Then, the m-ticketing cardlet checks the received signature. If it succeeds, the mticketing cardlet checks the validity of the permission token based on the timestamp (T S) sent by the validator. Indeed, if T S is lower than D (T S < D), the permission token is still valid. Then, the cardlet checks whether the number of used m-tickets reached max ticket , the number of authorized post-paid m-tickets. If a check fails, the m-ticketing cardlet aborts and the m-ticketing application displays a message to ask the user to renew the permission token. Dans ce chapitre, nous présentons les résultats [START_REF] Arfaoui | Practical and privacy-preserving TEE migration[END_REF] qui ont été publiés à la conférence WISTP 2015. Nous décrivons notre perception du déploiement et de la mise en oeuvre d'un environnement d'exécution de confiance (TEE): nous organisons le TEE en domaines de sécurité avec différents rôles et privilèges. Nous appelons profil TEE les secrets et données privées appartenant à l'utilisateur et manipulés par les applications s'exécutant dans le TEE. En se basant sur le nouveau modèle, nous construisons un protocole de migration de profils TEE assurant la confidentialité et l'intégrité de ce dernier. À cette fin, nous utilisons une clé de re-chiffrement et un jeton d'autorisation par couple de mobile, par fournisseur de service et par transfert. Nous avons également validé notre protocole avec AVISPA, un outil automatisé de validation de protocoles de sécurité.

Introduction

Like mentioned in Chapter 2, in the last years, a secure mobile operating system running alongside the standard Rich Execution Environment (REE for short), has emerged: the Mots clés : services mobiles, respect de la vie privée, signature de groupe, proxy de rechiffrement, TEE, migration de secrets

Design of privacy preserving cryptographic protocols for mobile contactless services

Summary:

The increasing number of worldwide mobile platforms and the emergence of new technologies such as the NFC (Near Field Communication) lead to a growing tendency to build a user's life depending on mobile phones. This context brings also new security and privacy challenges. In this thesis, we pay further attention to privacy issues in NFC services as well as the security of the mobile applications private data and credentials namely in Trusted Execution Environments (TEE).

We first provide two solutions for public transport use case: an m-pass (transport subscription card) and a m-ticketing validation protocols. Our solutions ensure users' privacy while respecting functional requirements of transport operators. To this end, we propose new variants of group signatures and the first practical set-membership proof that do not require pairing computations at the prover's side. These novelties significantly reduce the execution time of such schemes when implemented in resource constrained environments. We implemented the m-pass and m-ticketing protocols in a standard SIM card: the validation phase occurs in less than 300ms whilst using strong security parameters. Our solutions also work even when the mobile is switched off or the battery is flat. When these applications are implemented in TEE, we introduce a new TEE migration protocol that ensures the privacy and integrity of the TEE credentials and user's private data. We construct our protocol based on a proxy re-encryption scheme and a new TEE model. Finally, we formally prove the security of our protocols using either game-based experiments in the random oracle model or automated model checker of security protocols.