Ghada Arfaoui
email: ghada.arfaoui@orange.com

Jean-François Lalande
email: jean-francois.lalande@insa-cvl.fr

Jacques Traoré
email: jacques.traore@orange.com

Nicolas Desmoulins
email: nicolas.desmoulins@orange.com

Pascal Berthomé
email: pascal.berthome@insa-cvl.fr

Saïd Gharout
email: said.gharout@orange.com

A Practical Set-Membership Proof for Privacy-Preserving NFC Mobile Ticketing

Keywords: Set membership proof, zero-knowledge proof, m-ticketing, privacy, anonymity, unlinkability, post-

To ensure the privacy of users in transport systems, researchers are working on new protocols providing the best security guarantees while respecting functional requirements of transport operators. In this paper 1 , we design a secure NFC m-ticketing protocol for public transport that preserves users' anonymity and prevents transport operators from tracing their customers' trips. To this end, we introduce a new practical set-membership proof that does not require provers nor verifiers (but in a specific scenario for verifiers) to perform pairing computations. It is therefore particularly suitable for our (ticketing) setting where provers hold SIM/UICC cards that do not support such costly computations. We also propose several optimizations of Boneh-Boyen type signature schemes, which are of independent interest, increasing their performance and efficiency during NFC transactions. Our m-ticketing protocol offers greater flexibility compared to previous solutions as it enables the post-payment and the off-line validation of m-tickets. By implementing a prototype using a standard NFC SIM card, we show that it fulfils the stringent functional requirement imposed by transport operators whilst using strong security parameters. In particular, a 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.

Introduction

Near Field Communication (NFC) [36] is a highlypractical emerging technology [START_REF] Frost | NFC: When will be the real start?[END_REF]. Indeed, NFCenabled smartphones are being used in several domains, such as payment [START_REF]Proximity mobile payments: Leveraging NFC and the contactless financial payments infrastructure[END_REF], access control [START_REF] Dmitrienko | SmartTokens: Delegable Access Control with NFC-Enabled Smartphones[END_REF] and ticketing [START_REF] Derler | Anonymous Ticketing for NFC-Enabled Mobile Phones[END_REF]. In the following, we focus on mobile ticketing for public transport. Such a ticketing system is operated by a transport authority representing the transport service provider, and it usually consists of three phases [START_REF]NFC in Public Transport[END_REF]. First, the user registers (Registration). Secondly, the user obtains the product (a set of m-tickets) to be used (Provisioning). The last phase is the Validation, during which an m-ticket is validated by the transport authority using the NFC connection of a mobile phone. During this phase, the m-ticketing system must ensure the integrity and authenticity of the mticket. Another important aspect is that a network connection [START_REF] Chaumette | Architecture and comparison of two different user-centric NFC-enabled event ticketing approaches[END_REF] is sometimes required, either for the validator gate or for the smartphone itself. Moreover, the validation is subject to a hard time constraint imposed by the transport operators [START_REF]White Paper: Mobile NFC in Transport[END_REF]: the m-ticket validation must occur in less than 300 ms.

In the literature, many proposed solutions did not consider the security aspects. Even when security issues are addressed, the concept of user's privacy, that is users' anonymity and users' trips unlinkability with respect to the transport service provider, is often overlooked [START_REF] Ekberg | Mass Transit Ticketing with NFC Mobile Phones[END_REF][START_REF] Tamrakar | Tapping and Tripping with NFC[END_REF]. Some recent works [START_REF] Derler | Anonymous Ticketing for NFC-Enabled Mobile Phones[END_REF][START_REF] Rupp | P4R: Privacy-Preserving Pre-Payments with Refunds for Transportation Systems[END_REF] have shown a special interest in users' privacy. Although they managed to ensure user's anonymity, these solutions suffer from privacy weaknesses.

In this paper, we propose a new cryptographic protocol for m-ticketing that provides strong authentication, anonymity, and unlinkability properties, whilst remaining efficient when implemented in constrained environments such as SIM cards.

Towards this goal, we also make various cryptographic optimizations. In particular, we present a new efficient set-membership proof enabling a prover to prove, in a zero-knowledge way, that his secret belongs to a given public set. Unlike previous constructions, this proof does not require pairing computations, especially on the prover side, 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 HiPerS-mart™MIPS [START_REF] Devegili | Implementing Cryptographic Pairings over Barreto-Naehrig Curves[END_REF], 1.9s on an MSP430X [START_REF] Gouvêa | Efficient software implementation of public-key cryptography on sensor networks using the MSP430X microcontroller[END_REF]. We also propose several optimizations of Boneh-Boyen signature schemes. These results are of independent interest and increase the performance and efficiency of BBsignatures.

Based on these cryptographic primitives, our mticketing protocol enables to securely validate an mticket 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 set [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].

We implemented our system on a standard NFC SIM card. To the best of our knowledge, this is the first implementation of efficient and practical setmembership proofs and BB-signatures on SIM cards. The entire validation process can be performed without any connection to a back-end server or computations delegation to the smartphone hosting the SIM card. This avoids any tracking of the user by a malware installed in the smartphone. We also show that the validation process occurs, on average, in 184.25ms when the mobile is switched on and in 266.52ms when the mobile is switched off or its battery is flat (battery-Off). Moreover, we show that our protocol supports the post payment approach (which provides more flexibility) and give countermeasures to detect any misuse of the service owing to the regular reports of unused m-tickets.

The paper is structured as follows. Section 2 discusses related work on privacy-preserving m-ticketing schemes. In Section 3, we detail the framework of our mticketing protocol. Then, we introduce in Section 4 our assumptions and the desired security, privacy and functional requirements that an m-ticketing system should fulfil. In Section 5, we describe the cryptographic assumptions and building blocks required for the sequel. We introduce our new set-membership proof in Section 6 and our m-ticketing protocol in Section 7. Section 8 gives the security proofs. In Section 9, we present our implementation before concluding in Section 10.

Related work

Heydt-Benjamin et al. were the first to propose a cryptographic framework for transport service [START_REF] Heydt-Benjamin | Privacy for Public Transportation[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 the air, is also important. Later, many applied m-ticketing solutions have been proposed [START_REF] Blass | PSP: Private and secure payment with RFID[END_REF][START_REF] Derler | Anonymous Ticketing for NFC-Enabled Mobile Phones[END_REF][START_REF] Ekberg | Mass Transit Ticketing with NFC Mobile Phones[END_REF][START_REF] Isern-Deya | A Secure Automatic Fare Collection System for Time-Based or Distance-Based Services with Revocable Anonymity for Users[END_REF][START_REF] Rupp | P4R: Privacy-Preserving Pre-Payments with Refunds for Transportation Systems[END_REF][START_REF] Sadeghi | User Privacy in Transport Systems Based on RFID E-Tickets[END_REF][START_REF] Tamrakar | Tapping and Tripping with NFC[END_REF]. However, each proposal has some limitations that this paper tries to solve. We briefly describe these limitations in this section.

First, the RSA based m-ticketing solution proposed by Ekberg and Tamrakar [START_REF] Ekberg | Mass Transit Ticketing with NFC Mobile Phones[END_REF][START_REF] Tamrakar | Tapping and Tripping with NFC[END_REF], the RFID e-tickets proposed by Sadeghi et al. [START_REF] Sadeghi | User Privacy in Transport Systems Based on RFID E-Tickets[END_REF] and the ticketing solution proposed by Blass et al. [START_REF] Blass | PSP: Private and secure payment with RFID[END_REF] only protect user's privacy with respect to outsiders and not the transport authority. The transport authority is considered honest which is not anymore a reasonable hypothesis.

Second, the most recent protocols that include the expected level of privacy by protecting users' privacy even against the transport authority still have some efficiency problems. For instance, the BBS based protocol proposed by Isern-Deya et al. [START_REF] Isern-Deya | A Secure Automatic Fare Collection System for Time-Based or Distance-Based Services with Revocable Anonymity for Users[END_REF] validates a ticket with a duration of few seconds, even if the implementation has been done on a smartphone. Some recent solutions were close to find the right balance between efficiency and users' privacy. Derler et al. proposal [START_REF] Derler | Anonymous Ticketing for NFC-Enabled Mobile Phones[END_REF] provides anonymous tickets but users' trips are still linkable. Rupp et al. proposal [START_REF] Rupp | P4R: Privacy-Preserving Pre-Payments with Refunds for Transportation Systems[END_REF] provides a privacy preserving pre-payment protocol with refund for public transport with a refund verification procedure with a too high cost for constrained devices. Removing this verification makes possible to use the protocol, but it also enables a malicious transport authority to link users' trips, as detailed in Appendix A.

Our m-ticketing protocol tries to fill the remaining gap between efficiency and strong privacy. It can be used in very constrained devices, like SIM cards and offers a high level of privacy.

Framework of the protocol

In privacy-preserving 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. The transport authority (TA) is the man-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 set 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 (otherwise 0) 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.

Revocation.

IdentUser(rsk, DB REG , T ick k ): This deterministic algorithm takes as input the private key rsk, the database DB REG and a valid m-ticket T ick k . It outputs the identifier ID U of the 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 mtickets 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 .

Requirements

In this section, we first describe our trust assumptions. Then, we detail the requirements of our m-ticketing system. We consider two types of requirements, functional requirements, which are "efficiency" and "versatility" and security and privacy requirements, which consist in "correctness", "unforgeability", "unlinkability" and "non-frameability".

Trust assumptions

At the user's side, 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] Eznack | U)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 m-ticketing cardlet manages the cryptographic credentials of the m-ticketing application and executes required cryptographic computations without delegating any of them to the smartphone. Consequently, if the mobile application is compromised, the security will not be impacted because all the sensitive data and credentials are stored and managed in the SIM card. If the SIM card gets compromised, we planned countermeasures (cf. Section 7.4.2).

Functional requirements

Efficiency

M-ticketing systems must fulfil functional requirements imposed by transport operators [START_REF]White Paper: Mobile NFC in Transport[END_REF], in particular the validation of an m-ticket 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 the post-payment mode, i.e., charged later (after its use).

Security and privacy model

Besides the correctness property2 (which is obvious), 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. The adversary is then 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.

Exp N f ra A (1 λ ) 1. pp ← Setup(1 λ ); HU ← ∅; MU ← ∅; Set ← ∅.
2. (gpk, tsk, rsk) ← Keygen(pp). 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 .

(T ick

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.

In the sequel, we denote by A(keys, DB: oracles) an adversary who receives the keys "keys". This adversary has only read access to the databases "DB" and can query the oracles "oracles".

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 1. The scheme is nonframeable, if for any probabilistic polynomial time adversary A, the probability

Pr[Exp N f ra A (1 λ )=1] is negligible.

Unforgeability

Informally speaking, it should be impossible for anyone (1) to validate more m-tickets than what he obtained i.e. an adversary who retrieved N tokens τ (N sets 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 2. The scheme is unforge-

Exp unf org A (1 λ ) 1. pp ← Setup(1 λ ); HU ← ∅; MU ← ∅.
2. (gpk, tsk, rsk) ← Keygen(pp). (1 λ ) = 1] is negligible.

({T

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 m-tickets 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 m-tickets 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 3. 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. Exp unlink-b A (1 λ ) 1. pp ← Setup(1 λ ); HU ← ∅; MU ← ∅.
2. (gpk, tsk, rsk) ← Keygen(pp). 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 ⊥.

(i

0 , k 0 , i 1 , k 1 ) ← A(
10. Return b .

Fig. 3. Unlinkability security experiment

Remark: another basic requirement that our ticketing system should fulfill is the traceability meaning that revocation should succeed in the face of attacks by malicious users. In fact, our formulations of unforgeability and non-frameability capture this requirement. Indeed, an attacker who could produce a ticket which either (1) cannot be traced to a user or (2) identify an honest user who didn't obtain this ticket, would either break the unforgeability requirement (1) or the nonframeability requirement (2).

Cryptographic assumptions and building blocks

In this section, we introduce the notations, definitions and cryptographic tools used in the description of our set-membership proof and m-ticketing protocol.

Bilinear Maps

We consider throughout this document, 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. The mapping e satisfies the following properties:

∀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 F or g 1 = 1 G1 and g 2 = 1 G2 , e(g 1 , g 2 ) = 1 GT
e is efficiently computable.

Computational assumptions

Decisional Diffie-Hellman (DDH). For any multiplicative group G of prime order p, the 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). Given three groups G 1 , G 2 , G T , and a bilinear map e : G 1 × G 2 → G T , the XDH assumption states that DDH assumption holds in G 1 .

q-Strong Diffie-Hellman (q-SDH). The q-SDH assumption holds for some group G 1 if 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-Decisional Diffie-Hellman Inversion (q-DDHI). In any multiplicative group G of prime order p, the q-Decisional Diffie-Hellman Inversion assumption states that, given a random generator g ∈ G and the values (g, g α , g α 2 , ... , g α q ) ∈ G, 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 Assumption. There is no probabilistic polynomial time distinguisher for n-th residues modulo n 2 . In other words, there is no probabilistic polynomial time adversary that can distinguish S from Z * n 2 , where

S = {z ∈ Z * n 2 , ∃y ∈ Z * n 2 : z = y n mod n 2 }.

Zero-knowledge proof of knowledge

Roughly speaking, a zero knowledge proof of knowledge, denoted ZKPK, is an interactive protocol during which a prover convinces 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 P OK((α 1 , α 2 , ... , α n ) :

(α 1 , α 2 , ... , α n )). A ZKPK should be complete (a valid prover is accepted with overwhelming probability), sound (a false prover should be rejected with overwhelming probability) and 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], can be proven secure in the random oracle model of [START_REF] Bellare | Random Oracles Are Practical: A Paradigm for Designing Efficient Protocols[END_REF] (see [START_REF] Feigenbaum | Security Proofs for Signature Schemes[END_REF]). Such a signature of knowledge, for the relation , will be denoted

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

Camenisch-Lysyanskaya signatures

These signatures, proposed by Camesnich and Lysyanskaya [START_REF] Camenisch | Signature Schemes and Anonymous Credentials from Bilinear Maps[END_REF], are equipped with additional protocols. One of these protocols allows a signature to be issued on messages that are not known by the signer, but for 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, known by both parties, on secret values (x 1 , x 2 , ... , x n ) known only by the user. At the end of this protocol, the user obtains a valid CL -signature = Sign(x 1 , x 2 , ... , x n ) and the signer learns nothing about (x 1 , x 2 , ... , x n ).

Another protocol allows to prove knowledge of a signature on a tuple of messages (x 1 , x 2 , ... , x n ) without releasing any information on the corresponding signature. Each message can either be revealed to the verifier, sent in a committed form, or it may be such that the verifier has no information on it. In particular, it is possible to prove the knowledge of a CL-signature on committed values.

Set Membership Proofs

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] Canard | New Results for the Practical Use of Range Proofs[END_REF][START_REF] Chaabouni | A Noninteractive Range Proof with Constant Communication[END_REF] follow the same idea: a designated authority produces public signatures on each element of the public set Φ (and only on these elements). The proof of knowledge of a secret x ∈ Φ consists in proving the knowledge of a (public) signature on the secret x (which will be only possible if x belongs to the set Φ) without revealing x or the used signature. Solutions in [START_REF] Canard | New Results for the Practical Use of Range Proofs[END_REF][START_REF] Chaabouni | A Noninteractive Range Proof with Constant Communication[END_REF] require the prover to perform pairing computations. However, these cryptographic tools are not often convenient for many constrained platforms.

Boneh-Boyen Signatures

The signature scheme used by the designated authority (which could be the verifier) to sign each element of the set Φ is the one proposed by Boneh and Boyen [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][START_REF] Boneh | Short Group Signatures[END_REF]. Based on their scheme, which is secure under the q-SDH assumption, it is possible to prove knowledge of a signature on a message, without revealing the signature nor the message.

Boneh-Boyen Signatures with pairings.

Having a secret key y and two random generators

g 1 , g 2 of G 1 , the signature of a message m ∈ Z p is obtained by computing σ = g 1/(y+m) 1 . Given a bilinear pairing e, a signature σ of m is valid if e(σ, Y g m 2 ) = e(g 1 , g 2 )
, where Y = g y 2 is the signer's public key.

Boneh-Boyen Signatures without pairings.

Let G be a cyclic group with prime order p where the Decisional Diffie-Hellman (DDH) problem is assumed to be hard and g 1 , g 2 two random generators of G. The signer's private key is y ∈ Z p and its public key is Y = g y 2 .

Similarly to Boneh-Boyen signatures with pairings, the signature on a message m is the value A = g 1/(y+m) 1 . This implies that A y = g 1 A -m . Since we work in a group G not equipped with a bilinear map, the signer must additionally prove that the signature on m is valid, which is done by generating a ZKPK π 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 : SOK(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]. Finally, the signature A on m is valid if the proof π is valid.

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 assumption, in the random oracle model.

Proof (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.

Threshold Cryptosystems

The El Gamal cryptosystem [START_REF] Gamal | A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms[END_REF] works as follows. Let G be a cyclic group with prime order p where the Decisional Diffie-Hellman (DDH) problem is assumed to be hard. The public key consists of the elements (g

T , h T = g xT T )
, where g T is a random generator of G, and the corresponding private key is formed by In a threshold version, the El Gamal public key and its corresponding private key [START_REF] Desmedt | Threshold cryptosystems[END_REF] (resp. 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.

x T ∈ Z * p . The El Gamal ciphertext of a message m ∈ G is (C 1 = g r T , C 2 = m × h r T ), where r ∈ Z * p is a random number. The decryption of the ciphertext (C 1 , C 2 ) is obtained through the following computation: m = C 2 /C xT 1 . The El Gamal cryptosystem

Pseudo-random Function

A useful building block of our m-ticketing protocol is the pseudo-random function introduced by Dodis and Yampolskiy [START_REF] Dodis | Efficient Construction of (Distributed) Verifiable Random Functions[END_REF][START_REF] Dodis | A Verifiable Random Function with Short Proofs and Keys[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 pseudo-random 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
. This construction is secure under the q-DDHI assumption in G.

A new set membership proof

In this section, we present a new set membership protocol. Our set membership proof is a ZKPK which allows the prover to convince any verifier that the committed integer k lies in the public discrete set Φ. This ZKPK 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 | Advances in Cryptology -CRYPTO '91[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 ask the prover (a SIM card and/or a smartphone in our setting) nor the verifier (in a specific scenario) to perform pairing computations. 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 such as e-voting where the verifiers (tallying authorities) own such a key to open ballots.

Let G 1 , G 2 and G T be three (multiplicative) bilinear groups of prime order p and a bilinear map e : G 1 × G 2 → G T . Let g, g 1 and h T be three generators of G 1 and consider a generator g 3 of G 2 . A 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 BBsignature 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. H will denote a hash function, for instance, SHA-256.

In Figure 4, we propose a protocol enabling to prove that the value k committed by the prover in the com- Remark 1: Proving knowledge of a valid BBsignature A k = g 1/(y+k) on a value k committed in Com = g k 1 h ν T , without revealing neither k nor 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 computes B = A l k . Since A k = g 1/(y+k) this implies that B = A l k = (g l ) 1/(y+k) and then that B y+k = g l . It implies, if we note B 1 = B -1 and D = B y that 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 ZKPK: Π = P OK(k, ν, l :

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 and D 1 = B k 1 1 g l 1 Real time computations: Compute: c = H(Com, B, D, Com 1 , D 1 , ch) ch ---------Choose ch ∈ Z * p (A random challenge) s 1 = k 1 + c × k mod p; s 2 = r 1 + c × v mod p; s 3 = l 1 + c × l mod p; Check that B = 1 G 1 Π = Com, B, D, s 1 , s 2 , s 3 Π • If
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)
Com = g k 1 h ν T ∧ D = B k 1 g l ).
The computation of the ZKPK Π is described in Figure 4.

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 either the prover or 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 compu-tations to perform. This is particularly interesting for the m-ticketing use case.

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

Our m-ticketing protocol

This section begins with an overview of our protocol which main notations are summarized in Table 1, before moving to our m-ticketing protocol and its postpayment aspects.

Overview

We assume that m-tickets have a unique rate per area such as in Paris [START_REF]The Paris Convention and Visitors Bureau. Public transport in paris[END_REF], Berlin [START_REF]Tickets, fares and route maps[END_REF] and Moscow [38] undergrounds. The user can have different types of m-tickets sets such that every set is characterized by a rate, an area and the number of available m-tickets (max ticket ), e.g., a set of 10 m-tickets valid in area 1 and the price of one m-ticket is 1.30€.

As shown in Figure 5, at the beginning, 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 set). 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 set. 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 El-Gamal 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 of Section 6.

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.

Model

Setup of public parameters. 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 compu- Revocation authorities. 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 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 xT 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).

Transport authority. The transport authority (TA) sets for each group, i.e. a type of m-tickets set, 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 . User. The user owns a public/private key pair

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

User Transport Authority Public input: The public parameters

Public Input: The public parameters Private Input:

x U Private Input: γ, DB REG Choose s 1 ∈ Z * p , j ∈]0, n[ Compute: Com = g s 1 1 , C 0 = g s 1 P j n mod n 2 Π 1 = P OK(s 1 , j : Com = g s 1 1 ∧ C 0 = g s 1 P j n mod n 2 ) Com,Π 1 ,C 0 -------------Verify Π 1 Choose s 2 ∈ Z * p and Let s = s 1 + s 2 mod p, then Com × g s 2 1 = g s 1 1 g s 2 1 = g s 1 +s 2 1 = g s 1 = c Choose r ∈ Z * p and Compute: A = (g s 1 h) 1/(γ+r)
Verify Π 2 and Compute:

A,r,g s 2 1 ,Π 2 -------------and Π 2 = P OK(γ : W = g γ 0 ∧ A γ = c × hA -r ) c = g s 1 1 g s 2 1 = g s 1 +s 2 1 = g s 1 , µ = Sign(x U , A, g s 1 1 , g s 2 1 ) µ -------------Verify µ Compute: s = s 1 + s 2 s 2 -------------Save (A, C 0 , s 2 , c, µ) associated to (ID U , h U ) in DB REG
Fig. 6. The protocol of the permission token request

M-ticketing protocol

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

User registration phase

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 phase

The permission token request phase is detailed in Figure 6. A permission token (A = (g s 1 h) 1/(γ+r) , r) consists of an (extended) BB-signature [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 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 set.

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.

Validation phase

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 m-ticketing 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.

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 Section 6), -He knows a valid BB-signature A = (g s 1 h) 1/(γ+r) on s (without revealing both s and the signature), -E is an encryption of g s 1 .

Therefore T ick k = (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: Proving the knowledge of a valid BBsignature 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 B 0 = A α . Since A = (g s 1 h) 1/(γ+r) this implies that B 0 = A α = (g αs 1 h α ) 1/(γ+r) and then that:

B γ+r 0 = g αs 1 h α (1)
Let us note by B = B -1 0 and C = B γ 0 . From (1), we have:

C = g αs 1 × h α × B r (2)
As a result, in order to prove that he knows a BBsignature 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 (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 G1 , 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, 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 membership). 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).

We emphasize that owing to our improvements on Boneh-Boyen based Camenisch-Lysyanskaya signature scheme, all the computations (required to validate an mticket) 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.

Theorem 3. The protocol in Figure 7 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 .
The proof is detailed in Appendix C.

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. Section 7.4.2).

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.

M-ticketing cardlet

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

Compute: c = H(C, C 1 , C 2 , B 0 , T , T , Com, B, ch ------------Choose ch ∈ Z * p D, K, C 1 , C 2 , R , R , C , T 4 , Com 1 , D 1 , K , L , ch) 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). Hence 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
• Otherwise, if the validator doesn't know the private signature key y and γ (Second case), then, check that 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.

ω 12 = f + c × f mod p Let E = (C 1 , C 2
C = g s 1 1 h s 2 T Com -c ; D = B s 1 1 g s 3 D -c ; ω 1 , ω 2 , ω 3 , ω 4 , ω 5 , ω 6 , ω 8 , ω 9 , ω 10 , ω 11 , ω 12 ) B k , E, Π 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 ,

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).

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] Eznack | U)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 countermeasure C and never do reports, or (2) use the same m-ticket several times or (3) report a used m-ticket. This will be detected in DB U sedT ickets and TA can 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.

Security analysis

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

Theorem 4 (Non-frameability). Our mticketing protocol is non-frameable, in the random oracle model, under the q-DDHI assumption.

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

The proof is detailed is Appendix E. Theorem 6 (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 is Appendix E.

Performance results

We implemented the user side of our solution on a SIM card and the validator side in a regular PC (cf. Appendix D). We used a 256-bit Barreto-Naehrig curve [START_REF] Barreto | Pairing-Friendly Elliptic Curves of Prime Order[END_REF] 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]. More details are given in Appendix D. Pre-computations. The pre-computations for preparing one signature occurs in 1.7 s. It consists in computing elements involved in proving that the user knows a valid signature on his secret s. The total size of the elements that the card has to store for one signature is 1130 bytes (24 Z p elements, 10 compressed points and one digest output).

Validation phase. Table 2 gives timings (average over 50 trials and standard deviation between parentheses) for the whole validation protocol which includes the validator authentication, the signature generation and an m-ticket verification. The timings 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, 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).

The column "Card signature" gives the duration of real-time computations of a signature (computing an mticket 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 (≥ 85 ms), but the whole process (Signature+NFC) remains very fast, i.e., 123.01 ms on average.

For the signature verification by the validator, 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 because a regular desktop PC can efficiently achieve such computations.

In total, the m-ticket validation occurs for the first case (without pairing at the verifier side) in 184.25 ms on average and in 191.80 ms for the second case (with pairing at the verifier side). When the battery is flat, the validation occurs in at most 272.55 ms on average.

Conclusion

In this paper, we proposed various cryptographic enhancements: (1) optimizations of BB-signature schemes and ( 2) a new set-membership proof that does not require pairing computations at the prover side. These contributions enable to design efficient protocols over NFC. Then, based on these cryptographic primitives, 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. Finally, we prove that our protocol is completely off-line and efficient: the validation occurs in 184.25 ms and in 266.52 ms when the battery is flat.

A Privacy weakness of Rupp et al. protocol

In the following, we give further details about the payment protocol for public transport proposed by Rupp et al. at FC 2013 [44]. 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]. This token enables the user to perform one trip. Then, the user receives a fresh refund token (RT = SN RT such that SN RT ← G), 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

= RT r RT -----------→ υ = υ + ω, RT ← -----------RT = RT d ω (1) R = Rr mod p, RT = RT 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)
Fig. 8. The refund protocols of Rupp et al. [START_REF] Rupp | P4R: Privacy-Preserving Pre-Payments with Refunds for Transportation Systems[END_REF] described in Figure 8. A refund value ω is represented as a ω-times BLS signature [51] 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:

e(SN R RT , h d υ ) ? = e(RT , h) (3)
In [START_REF] Rupp | P4R: Privacy-Preserving Pre-Payments with Refunds for Transportation Systems[END_REF], Rupp et al. assume that, for efficiency reasons, users don't verify their RTs. Indeed, verifications of refund tokens (step 1 in Figure 8) 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. 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 8, instead of computing RT = RT d ω , the transport authority chooses a variable t ← Z * p and computes RT =RT td ω . The user will not detect that RT is improperly calculated because there is no verification on the user's side. The refund token RT will then carry on the exponent t till the redeeming refund step, i.e., RT = SN t j Rd υ 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 va-lidity 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 13). If equation (3) 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) (4)
To do so, the transport authority will repeat the computations with different values of j until the relation ( 4)

holds. When e(SN t j R RT , h d υ )

?

= e(RT , h) equation ( 4) 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 ( 5):

e(SN t jx x R RT , h d υ ) ? = e(RT , h) (5)
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 (5) 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 [START_REF] Blass | PSP: Private and secure payment with RFID[END_REF] and finding the right tuples (t x , j x ), becomes quickly a complex and unmanageable task when the number of targeted stations increases (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 (Rupp et al. system [START_REF] Rupp | P4R: Privacy-Preserving Pre-Payments with Refunds for Transportation Systems[END_REF]) 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 8). This verifi-cation 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 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.

B Proof of Theorem 2

Sketch of proof. 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, i.e., {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): l = (s 3 -s 3 )/(cc) and k = (s 1 -s1 )/(cc); ν = (s 2 -s2 )/(cc);

The extractor succeeds when (cc) is invertible in Z p . If the following check D = B y holds , this implies that: D = B y = B k 1 g l . Therefore, 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 lỹ) . 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) zeroknowledge, 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 com- putes Com 1 = g s1 1 h s2 T Com -c and D 1 = B s1 1 g s3 D -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.

C Proof of Theorem 3

Sketch of proof. 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 r2 ∧ T = T α H r3 = G αs H r5 ∧ 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 r2 ∧ 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 [START_REF] Bellare | The onemore-RSA-inversion problems and the security of chaum's blind signature scheme[END_REF] 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.

D Platform and implementation details D.1 SIM card details

We used Javacard 2.2 for developing all the cryptographic computations into the SIM card. In particular, the SIM card has access to the functions handling elliptic curves operations. The SIM card handles requests from the validator using the NCF contactless interface.

D.2 Validator details

The validator has been developed 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. The PC is an Intel(R) Xeon(R) with a E5-1620 CPU with 4 cores running at 3.70GHz under a 64-bit Linux OS. The NFC reader of the validator is an Omnikey 5321 dual interfaces.

D.3 Curve and Pairing Parameters

The curve and pairing parameters that we used in the implementation of our m-ticketing system are: q = 8243401665430090752057404098378368203946728292799613002 4655912292889294264593 p = 8243401665430090752057404098378368203918016968090658713 6896645255465309139857 b = 5

E Security proofs E.1 Preliminaries

Discrete Logarithm (DL). For any multiplicative group G of prime order p, the DL assumption states that given a random generator g ∈ G and a candidate Y ∈ G, it is hard to find an integer y mod p such that Y = g y .

One-more Discrete Logarithm (OMDL) [START_REF] Bellare | The onemore-RSA-inversion problems and the security of chaum's blind signature scheme[END_REF]. For any multiplicative group G of prime order p, the 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 .

q-Strong Diffie-Hellman I (q-SDH-I). For any multiplicative group G 1 of prime order p, the 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.

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

Proof. See [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.

Forking Lemma. We use the Forking Lemma [START_REF] Maurer | 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 6) unless he knows all the underlying secrets (a, s, r, A, k) (respectively the secret x U ).

Using the notation of [START_REF] Maurer | 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 [START_REF] Canard | New Results for the Practical Use of Range Proofs[END_REF] ), then it can produce two valid m-tickets (k, σ 1 , h, σ 2 ) and (k, σ 1 , h , σ 2 ) such that h = h .

σ 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 , ..., ω

E.2 Proof of non-frameability

Sketch of proof. We assume that the challenger C in the experiment Exp N f ra A (1 λ ) receives a random instance (g x1 , g x2 , ..., 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. If the protocol does not 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 r2 where r 2 is a random value chosen by C, it proceeds as follows: T = (Com × g s2 1 ) ξ3 H r2 = G s H r2 . 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 nonframeability 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 OT okenRequest U on ID Ui (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 = ss 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 Ui (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 Ui corresponding to ID Ui 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 Ui 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 onemore-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 tickets, e.g., T ick k1 and T ick k2 , have the same token pair (since L > N × max ticket ). Let us denote by (s (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.

E.4 Proof of unlinkability

Sketch of proof. We prove the unlinkability under a slightly weaker model than the one presented in Section 4.3.3. 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 wellknown 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. We then proceed similarly for each unused m-ticket of i 0 and i 1 : 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.

{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
We can now give an upper bound for Adv 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.

4 .Fig. 1 .

 41 Fig. 1. Non-frameability security experiment

  is semantically secure under the DDH assumption. The Paillier cryptosystem [40] works as follows. 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). The public key is pk = (n, g P ) and the secret key is sk = (a, b). To encrypt m ∈ Z n , the user chooses r ∈ Z * n and C = EncryptP ai pk (m, r) = g m P r n mod n 2 . The decryption algorithm is given by DecryptP ai sk (C) = ((C ΠK mod n 2 ) -1)/n mod n 2 = m. The Paillier cryptosystem is secure under the Decisional Composite Residuosity assumption 3 .

Fig. 4 .

 4 Fig. 4. A new efficient set membership proof

Fig. 5 .

 5 Fig. 5. The m-ticketing protocol overview

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

  ) and the proof e(D, g 3 ) = e(B, Y ); e(C, g 2 ) = e(B 0 , W ) and goes to (*) Π = (C, B 0 , T , T , Com, c, B, D, s 1 , s 2 , s 3 , (*) Compute:

Fig. 7 .

 7 Fig. 7. The validation protocol

  --------Determine the refund ω based on the received information in RCT RT

  C puts h Ui = (g xi ) ξ2 = g xi U -ORegister M U requests: C does not need to do anything. -OCorruptU ser requests: C uses is 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 xj ) ξ1 = g xj 1 .

  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 xU 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: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 )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 OCorruptU 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).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:|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 unused (reported) m-tickets of i 0 and {T ick i i 1 ,where the k i b 's and the k 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. In the sequel, we will use 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,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) -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 DDHIadvantage 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

- 1 i=1.

 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,1b) 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

  ) = |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).

  k ) ← A(gpk, tsk, rsk, DB REG , DB U sedT ickets : ORegister HU , ORegister M U , OCorruptU ser, OT okenRequest U , OGenT icket, OReportT icket).

  gpk, tsk, DB REG , DB U sedT ickets : DB REG , DB U sedT ickets , T ick k j , T ick k 1-j : ORegister HU , ORegister M U , OCorruptU ser, OT okenRequest 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 ⊥. 8. If OIdentU ser T was requested for T ick k j or T ick k 1-j , output ⊥.

	ORegister HU ,	ORegister M U ,	OCorruptU ser,
	OT okenRequest U ,	OGenT icket,	OIdentT icket T ,
	OIdentU ser T , OReportT icket).
	4. If i 0 ∈ MU 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,

  the verifier and the designated entity are the same entity, it 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:

G 1 ,G 2 ,G T Multiplicative groups of prime order p g,g 0 ,g 1 ,g t , g T ,g U ,h,G,H Generators of G 1 (x T , h T ) ElGamal private and public keys of the revoca- tion authorities ((a, b), (n, p P )) Pailler private and public keys of the revocation authorities (γ, (W, W )) BB-signature scheme private and public keys of the transport authority (y, Y ) BB-signature private and public keys of the transport authority for set membership proof (x U , h U ) Private and public key of the user A A permission token ID U The identity of the user T ick k The k th m-ticket B k The serial number of the k th m-ticket E The ElGamal encryption of the user secret cor- responding to his set of m-tickets Π A proof (POK) ch A challenge DB REG The TA secure registration database DB U sedT ickets A secure database where the TA centralises the used m-ticketsTable 1 .

 1 Notation used in the m-ticketing protocol

Table 2 .

 2 Timings of m-ticket validation protocol including validator authentication (ms)

		Validator	Card Signature	Verification by PC	Total
		authentication + NFC connection (1) without pairing (2) with pairing	(1)	(2)
	Battery-On Battery-Off	56, 98(0.70) 76.55(7.46)	123.01(3.24) 185.28(18.68)	4.43(1.32)	12.19(3.20)	184.25(3.43) 266.52(17.91) 272.55(25.73) 191.80(4.73)

  * 1 , k 1 ) (respectively (s * 2 , k 2 )) the token pair corresponding to T ick k1 (respectively T ick k2 ). Therefore the serial number B * k1 of T ick k1 would be equal to B * , 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

	one of T ick k2 : B * k1 = g	1/(s * 1 +k1+1) t	= g	1/(s * 2 +k2+1) t	k2 the = B * k2 .
	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 * ) / ∈ Γ this implies that k * / ∈ {1, ... , max ticket }.
	Such a case will happen with negligible probability un-
	der the q-SDH assumption (see Theorem 2). There-
	fore s * / ∈ {s 1

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.

We use Paillier encryption scheme in our system in order to satisfy the unforgeability requirement even in a concurrent setting, where the adversary is allowed to interact with the transport authority, during the permission token request phase, in an arbitrarily interleaving (concurrent) manner (see[START_REF] Hufschmitt | Fair Blind Signatures Revisited[END_REF]).

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).

Without loss of generality, we do not make any distinction between a m-ticket and an unused m-ticket

The work has been supported by the ANR-11-INS-0013

protocol is non-frameable, in the random oracle model, under the q-DDHI assumption.

E.3 Proof of unforgeability

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 BBsignature 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. 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 did not 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 s2 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 nonnegligible probability ξ, L = N × max ticket + 1 valid mtickets 5 {T ick j kj } 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 kj = (B kj , 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-