Recently, operators of public transportation in many countries started to roll out electronic tickets (e-tickets). E-tickets offer several advantages to transit enterprises as well as to their customers, e.g., they aggravate forgeries by cryptographic means whereas customers benefit from fast and convenient verification of tickets or replacement of lost ones. Existing (proprietary) e-ticket systems deployed in practice are mainly based on RFID technologies where RFID tags prove authorization by releasing spatio-temporal data that discloses customer-related data, in particular their location. Moreover, available literature on privacy-preserving RFID-based protocols lack practicability for real world scenarios. In this paper, we discuss appropriate security and privacy requirements for e-tickets and point out the shortcomings of existing proposals. We then propose solutions for practical privacy-preserving e-tickets based on known cryptographic techniques and RFID technology.
Electronic tickets (e-tickets) gain increasing popularity among operators of public transit networks. However, besides offering many advantages, e-tickets also introduce several risks, in particular concerning privacy of their users. Benefits of e-tickets. Transit enterprises benefit from e-tickets in various ways: First, e-tickets help to decrease maintenance costs. Second, the number of fare dodgers is expected to decrease if tickets can be verified efficiently. Moreover, cryptographic means help to aggravate the problem of ticket forgery.
From the user perspective, e-tickets allow for faster and more convenient verification. Moreover, an e-ticket system can automatically select the lowest fare, which saves the customer’s time and money. Finally, revocation of e-tickets enables transit enterprises to replace lost tickets, which is not possible for conventional paper-based ticket systems.
Threats. Besides their advantages, e-tickets also introduce several risks, in particular regarding the privacy of users. Since authentication of transit tickets typically involves spatio-temporal data, users are at risk to loose their privacy if this information is leaked to unauthorized parties. This means that e-tickets should ensure that no information on users (confidentiality ) or their movements (location privacy ) should be revealed to entities that are not trusted by the users. There are existing implementations of e-tickets that allow the creation of movement profiles and, in some cases, even disclose personal information of users (cf. Section 3). Moreover, since e-tickets contain digital data, they may be easily copied (cloning ). Additionally, the corresponding protocols to issue or verify e-tickets may be subject to different attacks (e.g., man-in-the middle or replay).
Current situation. Currently, there is a vast amount of existing proprietary solutions for e-tickets. Since the corresponding specifications are usually not publicly accessible, there is no publicly known solution in practice that explicitly considers the privacy of users. We stress that user privacy preservation has not been claimed among the features of such systems.
The preferred technology to implement electronic transit tickets is Radio Frequency IDentification (RFID), which enables fully automated wireless identification of objects. A typical RFID system consists of transponders and transceivers. The main component of a RFID system is the transponder, which consists of an integrated circuit that is connected to an antenna. Typically, transponders are integrated into plastic cards or stickers that can be attached to the object to be identified and thus are often called tags. Since transceivers are mainly used to read data from tags, they are called readers. RFID tags can be used to realize e-tickets that are issued and verified by readers. Thus, in the rest of this paper “e-ticket” refers to tickets based on RFID.
Related work. There is a large body of literature on different approaches to
realize privacy-preserving mechanisms for RFID (e.g., [
In [
Summing up, an e-ticket system is an authentication scheme that involves spatio-temporal information and the design and secure implementation of a privacy-preserving and usable system based on RFID, is currently an interesting open problem.
Our contribution. In this paper we study the levels of privacy that could be achieved in an e-ticket powered system. We point out the weaknesses of known solutions and explore how known cryptographic tools can be applied to realize anonymization of e-tickets with currently available RFID technology, while having the goal to obtain a usable system that ensures no information disclosure on the user or his location to entities that are not trusted by the user. Structure of the paper. In Section 2, we demonstrate the problems related to e-tickets by introducing the setting of electronic transit tickets, and define appropriate security requirements. In Section 3, we analyze several proposals from literature on how to realize anonymity for RF-tokens with limited capabilities and discuss their applicability to e-tickets. Section 4 describes how recent cryptographic tools can be applied in order to achieve the desired requirements. Finally, we conclude with Section 5 by describing some open problems and motivating further research. 2
To introduce the problems related to e-tickets for public transportation, we first give a short overview of the general application scenario and point out potential weaknesses. 2.1
General Application Scenario transit network verifier V inspectors issuer I 1. Request 2. Issue token T user U station X verifier Vin entrance to transit network token T
An e-ticket system as shown in Fig. 1 is a token-based authentication scheme whereas tickets are represented as tokens (e.g., RFID tags). It consists of at least one token issuing entity (issuer ), a set of users, tokens, and verifiers who verify whether tokens are valid.
Typically, a user U must buy a token from token issuer I. Therefore, U selects his desired ticket and pays it. Issuer I then checks whether U is eligible to obtain a token (e.g., whether U paid for the ticket), and, if applicable, issues a token T and passes it to U . From now on, U is able to use token T to prove that he is authorized to use the transit network. This means that every user who is in possession of a token that has been issued by a genuine issuer is considered to be an authorized user.
Now assume that, as shown in Fig. 1, user U wants to travel from a place X to some location Y . Before U is allowed to enter the transit system at X, he must first prove to a verifier Vin at the entrance of the transit network that he is authorized to access it. If Vin can successfully verify the user’s token, U is allowed to enter. Otherwise access will be denied. During his trip, U may encounter arbitrary inspections where he must prove that he is authorized to use the transit network. Thus, a verifier V may check the user’s token T . If verification of T is successful, U is allowed to continue his trip. Otherwise, U must leave the transit network and may be punished for using it without authorization. After arriving at Y , the user’s token T can be checked for a last time. Again, if T cannot be verified successfully, U may be punished.
Note that authentication is typically bound to some limitations. For instance, this may be some geographical or timely usage restrictions. Additionally, a token may be bound to the identity of its owner (i.e., the entity that bought the ticket). 2.2
Obviously, the main goal of a ticket system is to prevent ineligible users from using the transit system. Thus, the most prominent attack is to violate this goal. However, there are some other, subtle attacks which we are going to consider in the following.
Impersonation. The most obvious attack against e-ticket systems is motivated by unauthorized entities. The adversary must obtain or simulate a token that is accepted by an honest verifier. To achieve this, the adversary may perform various attacks including man-in-the-middle or replay attacks against the underlying authentication protocols, or he may attempt to create forged tokens, or to copy tokens of honest users.
Tracing. A more subtle attack aims at obtaining information on users and their movements within the transit network. For instance, the transit enterprise may be interested in information on the behavior of its customers. When using conventional authentication protocols, a token can be easily identified during verification. This enables verifiers to trace tokens within the transit network. Moreover, if a user uses an identifying payment method (e.g., a credit card) to buy a token, the issuer can link the token to the identity of its owner. Since the issuer and the verifiers are typically under the control of the same entity (e.g., the transit enterprise), this results in a complete loss of the user’s privacy. However, in this case user information is managed by the transit enterprise that is a known entity. Thus it can be subject by law to commit on the honest use of the collected user data and can be monitored by means of inspections (similar observations hold for credit card companies).
The concrete threat instead, comes from unknown adversaries. Tokens typically are wireless devices and thus all their communication can be eavesdropped or manipulated by an adversary. Moreover the adversary may unnoticeably interact with tokens. As a consequence, the user’s token may also be traced by entities different from the verifiers or the token issuer.
In summary, a primary goal is that the e-ticket system prevents disclosure of information on users or their movements to entities not trusted by the users. Denial-of-service attacks. Another type of adversary may want to harm (e.g., to blackmail) the transit enterprise by preventing honest users from accessing the transit network. As already mentioned, tokens are wireless devices that can be attacked unnoticeably. This means that an adversary may try to exploit deficiencies of the protocols such that a ticket is no longer accepted by an honest verifier.
Depending on the underlying business model, protocols for e-tickets must be carefully crafted to prevent some or all of these attacks. In Section 2.3, we introduce different reasonable trust and adversary models and set up a complete list of requirements for e-ticket systems in Section 2.4. 2.3
In an ideal setting, no entity must be trusted. However, in practice, the transit enterprise must at least trust issuer I to only create tokens for eligible users. Moreover, the transit enterprise must trust each verifier V to only accept tokens that have been issued by issuer I. These are reasonable assumptions since in practice, the token issuing entity and the verifiers are typically physically controlled by the transit enterprise.
Ideally, users should be anonymous to every entity, including issuer I and all verifiers V . However, due to technical restrains this is not always feasible in practice. Thus, a reasonable trust model for a practical solution is that users must at least trust issuer I and, dependent on the implementation, also all verifiers V . However, a trust model which only requires issuer I to be trusted is preferable.
To summarize, issuer I must trust all verifiers V . Moreover, all verifiers V must trust token issuer I. For users, there are three possible trust models:
TM 2: User U must only trust token issuer I.
TM 3: User U needs not to trust anyone.
TM 1 means that the e-ticket system must preserve privacy to all entities outside the system. This is the trust model primarily used for the solution presented in Section 4. Considering TM 2, the e-ticket system must additionally protect the user’s privacy to the verifiers. The solution presented in Section 4 can achieve this by assuming each verifier V to be connected to a remote server or to be equipped with a security module that is controlled by issuer I. However, these hardware assumptions may be difficult to achieve in practice. To realize TM 3, the e-ticket scheme must provide full anonymity. As discussed in Section 1, this seems to be possible only with high computational and communication resources, which is inappropriate for low-cost RFID devices.
It is also assumed that all communication that takes place during the process of creating a ticket cannot be eavesdropped or manipulated by an adversary. This is reasonable in practice since a user U may either use out-of-band communication or a secure channel to communicate to issuer I. However, following the traditional adversarial models, an adversary can eavesdrop all communication of a token T . Moreover, an adversary may perform active attacks on the corresponding protocols, which means that he can interact with all parties on the protocol level. Additionally, an adversary can corrupt tokens and verifiers (though this can only happen for a limited number of tokens and verifiers). The adversary is not allowed to corrupt the token issuer. 2.4
Authentication. As mentioned in Section 2.1, the most important security goal for transit enterprises is authentication. Thus no unauthorized user (i.e., who is not in possession of a valid token) should be able to convince an honest verifier that he is authorized to access the transit system.
Another major requirement for any token-based authentication scheme is the resilience to remote tampering with tokens, which would allow denial-of-service attacks.
We summarize the security goals concerning authentication as follows: Authentication: Only valid tokens are accepted by honest verifiers. Unforgeability: Emulation and copying of valid tokens should be infeasible. Availability: Unauthorized altering of token data must be infeasible. Privacy. Since e-tickets enable efficient detection and identification of a huge number of tickets, a detailed dossier about user profiles (e.g., personal data or movements) can be created. The problem aggravates if tickets can be associated with the identity of their corresponding users since this results in a complete loss of user privacy.
Thus, the security objectives concerning privacy are: Confidentiality: Unauthorized access to user-related data should be infeasible. Anonymity: Unauthorized identification of tokens should be infeasible. Location Privacy: Unauthorized tracing of tokens should be infeasible.
A stronger notion of location privacy considers traceability of tokens in case
the internal state (i.e., the secrets) of a token has been disclosed. To distinguish
traceability in past or future protocol runs, [
Backward traceability: Accessing the current state of a token should not allow to trace the token in previous protocol runs.
Forward traceability: Accessing the state of a token should not allow to trace the token in future protocol runs.
In addition to these security and privacy requirements it is important to consider functional requirements for a practical solution.
Functional requirements. The costs per e-ticket should be minimal. Therefore, in case each ticket is implemented as a physical token (e.g., as RFID tag), the computational and storage requirements to the token should be as low as possible.
Additionally, verification of tickets must be fast. For instance, it should be possible to verify an e-ticket while a user is walking by, or shortly holding his ticket near a verifying device (e.g., while entering a bus). Therefore, protocols for e-tickets must be designed carefully to minimize the amount of computation and communication that must be performed. Moreover, an e-ticket system must be able to handle a huge amount of tokens.
Therefore, the functional requirements to e-tickets are:
3
Most e-ticket systems are proprietary solutions whose specifications are not
publicly available. This section exemplary shows the most common approach of
implementing authentication of e-tickets in practice by the Calypso e-ticket system
[
Calypso e-ticket standard. Calypso is an e-ticket standard based on RFID
tokens that is widely used in Europe and North and South America [
Calypso implements a common approach to authenticate a low-cost RFID
token based on a simple challenge-response protocol. Each token has a symmetric
authentication key KT that can be computed as a function of the serial number
ST of the token and a global master secret. All verifiers are equipped with a
tamper-resistant security module (secure application module, SAM) that knows
and protects this master secret and can be used as a black-box to compute KT
from ST . To authenticate a token, a verifier sends a random challenge NV to
the token,which then computes HT f (KT ; NV ) where f is some one-way
function. Finally, the token returns (ST ; HT ) to the verifier who uses its SAM
to drive KT and then verifies HT . If verification is successful, the token has
been authenticated. Obviously, this approach cannot provide privacy since all
transactions of a token can be linked by its serial number ST that is transmitted
in clear in every protocol run. All subsequent transactions to update or to read
data from a Calypso token are authenticated this way but are not encrypted.
Other e-ticket systems. There are many other proprietary solutions for
etickets in practice. Most of them are based on widely used RFID transponders.
Prominent examples are FeliCa [
FeliCa [
MiFare is a family of contactless smartcards produced by Philips/NXP
Semiconductors. These transponders are widely used for different purposes including
e-tickets for public transportation. There were several publications on attacks
against MiFare Classic transponders [
The attacks on MiFare Classic transponders demonstrate a major problem of proprietary security solutions: Manufacturers of low-cost hardware try to find a compromise between speed and security of their products. Thus, they often implement proprietary lightweight crypto algorithms whose specifications are not public, and thus are typically not sufficiently evaluated. As the attack against MiFare Classic shows, these algorithms can often be reverse-engineered, which allows cryptanalysis or efficient key search by running the algorithms on more powerful hardware. In case of MiFare Classic, both ways enabled to break the security goals of these tags at a point in time where they were already widely used in practice. 3.1
In an ideal e-ticket system, verifiers should learn nothing from the verification
except that a token is genuine and valid. It is possible to realize this by
using privacy-preserving techniques like anonymous credential systems [
There is a large body of literature on different approaches to implement
privacypreserving mechanisms for low-cost RFID transponders. For instance, [
Basic tags. As basic tags cannot perform any cryptographic operations they
disqualify for authentication purposes. Tags that only provide wireless readable
memory can only forward the data stored in their memory and thus are subject
to replay and cloning attacks. This means that all data stored on such a tag can
be read and be used to create identical copies or to simulate the original tag to
an honest reader. Another problem related to cloning is swapping. This means
that an adversary can copy the data stored on tag A to another tag B and vice
versa and thus change the identities of these tags. Therefore, basic tags cannot
fulfill the requirement of unforgeability.
3 Near Field Communication (NFC) [
Moreover, many solutions to enhance privacy of basic tags require tags to
provide many-writable memory (e.g., [
Therefore, tags that provide no cryptographic functionality cannot be used in applications that require reliable authentication. Thus, it is inevitable to use tags that are capable of performing at least some cryptographic functions if authentication is of concern.
Symmetric-key tags. A general problem of implementing privacy-preserving
authentication based on symmetric keys is how to inform the other party which
key must be used. Apparently, a tag cannot disclose its identity before the reader
has been authenticated since this would violate its location privacy. Therefore,
the reader does not know which authentication key it should use, and thus
cannot authenticate to the tag. The basic idea to circumvent this problem has
been introduced by [
Let fK (m) be a keyed one-way function on message m using key K. To
authenticate to a reader, a tag first computes hT fKT (R) where KT is a
tagspecific key and R is a random value chosen by the tag. On receipt of (hT ; R),
the reader forwards this tuple to a trusted server that computes hi fKi (R)
for all keys Ki 2 K where K denotes the set of the keys of all authorized tags.
The server accepts if it finds a Ki 2 K such that hi = hT . Finally, the server
sends its decision whether to accept or reject the tag to the reader. Since R is
randomly chosen each time the tag is queried, it always emits a different tuple
(hT ; R) which cannot be linked to the tuples sent in previous protocol runs.
Moreover, the reader does not learn the identity (i.e., the key KT ) of the tag
since it only receives the response from the server. An obvious drawback of this
solution is that the computational costs for the server to verify a tag are linear
in the number of authorized tags. Therefore, this basic approach does not fulfill
the efficiency and scalability requirement. Another disadvantage of this solution
is that readers must have an online connection to the server, which, depending
on the use case, may not be practical. Moreover, the tag must trust the server
to respect its privacy since the server can identify the tag when it found the
right key. Furthermore, this solution provides no security against replay-attacks
and thus violates the unforgeability requirement. There is many subsequent work
(including [
Other approaches rely on updating the identity of a tag each time it has
been authenticated [
Section 4 provides a simple solution that allows anonymous authentication of tags with constant computational costs for the readers without the need for a permanent online connection. 4
RFID tags that are capable of performing public-key operations disqualify for practicable implementations of e-tickets because of their relatively high price and low performance. Thus, RFID tokens that are limited to symmetric-key cryptography (i.e., random number generation and hashing) are the most practical choice for e-tickets. However, as discussed in Section 3.2 the use of symmetrickey cryptography seems to have the drawback that at least the token issuer must be trusted not to disclose personal information or movement profiles of users. Thus, our solution is based on the trust and adversary model for e-tickets that we discuss in the following.
Trust and Adversary Model. Following Section 2.3, for e-tickets based on RFID tokens that are limited to symmetric cryptography, either trust model TM 1 or trust model TM 2 must be chosen. This means that a user U must at least trust token issuer I. Whether user U must additionally trust all verifiers V depends on the corresponding setup assumptions. This means that, if verifiers are considered to be untrusted, all operations that disclose user-related information must be dropped from the verifiers. For instance, these computations may be carried out on a local tamper-resistant4 security module as it is done by many implementations in practice (cf. Section 3). Another simple approach used by various anonymous symmetric-key-based authentication protocols, is to employ a remote trusted server (cf. Section 3.2).
Model for Anonymous E-Ticket Systems. As discussed in Section 2.2, to provide privacy of users it is necessary to prevent tracing of tokens. This means that all entities that are not trusted by the user of a token should not be able to decide whether the user’s token has been used in a protocol run (unlinkability ).
Therefore, it is necessary to employ some mechanism that hides the identity
of a token each time it is queried. This can either be some special hardware
(e.g., as proposed by [
Analogous to Section 2.1, an anonymous e-ticket system consists of at least one token issuer, a set of users, tokens, verifiers, and anonymizers. The token issuer creates tokens for users. These tokens can be used by users to prove to verifiers that they are authorized to use the transit system. Additionally, 4 Tamper-resistance means that the device will delete all its secrets when it detects any kind of physical tampering. anonymizers ensure anonymity of tokens. We say that tokens are anonymized. Fig. 2 illustrates the model for anonymous e-ticket systems.
Description of the Solution. In the following, we focus on solutions for privacypreserving authentication based on RFID tokens that are at most capable of performing symmetric cryptography.
The players are as shown in Fig. 2. The anonymizer is either a dedicated hardware device or a software running on a mobile computing device (e.g., the mobile phone) of the user. Note that, a separate anonymizer device may suffer from the same problems as discussed in Section 3.1. However, in case a user’s anonymizer runs out of power, the user will indeed loose some privacy until his anonymizer is operable again but he can still prove authorization using his RFID token. Moreover, since anonymizers can also be available in public places and their capabilities can be embedded in the verifiers (when this does not significantly affect the performance of the system), the user’s privacy is not completely lost.
Since our solution relies on symmetric-key-based authentication, the token
must store an authentication secret. To achieve the security requirement of
unforgeability, it should be impossible to determine this secret by attacking the
protocols involving the token, as well as by physically attacking the token. One
solution to counterfeit physical attacks is to employ physical protection
mechanisms that aggravate reading out the memory of the tag. However, this would
increase the price of tag such that it would be improvident to use them. Another
solution to prevent cloning can be implemented by means of a recent physical
cryptographic primitive: Physically Unclonable Functions (PUFs) [
Secure key storage with PUFs. A Physically Unclonable Function (PUF)
is an inherently unclonable function embedded into a physical object [
A PUF can be embedded into a microchip, e.g., by exploiting statistical
variations of delays of gates and wires within the chip. These deviations are
unique for every sample from a set of chips that implement the same circuit.
Therefore, in [
The adversary model for PUFs is that an attacker is assumed to know how
the PUF is challenged and how responses are measured. Moreover, the attacker
is allowed to know the exact challenges for deriving the secret stored in the PUF.
The requirements to the chip that incorporates a PUF to securely store a secret
are as follows [
The first requirement prevents an adversary from accessing the output of (and thus, the secret stored in) the PUF. The second prevents an adversary from collecting data that may help to create a clone or to set up a mathematical model of the PUF that can be used to obtain the secret. The third is to prevent any kind of attacks (e.g., side-channel attacks) that try to disclose the internal state of the PUF, the processing unit, or the volatile memory of the chip that may temporally contain parts of the secret. The fourth is to prevent cloning of the PUF. The fifth prevents invasive inspections, which means that any attempt to physically access or manipulate the chip or the PUF must destroy both of them. The last requirement prevents an attacker from injecting malicious code that may force the chip to disclose its secret.
Storing a secret in a PUF. To use a PUF as a secure key storage, a key K is generated and stored as follows: A trusted party (e.g., issuer I) first generates key K 2R f0; 1gl using an appropriate security parameter l. Then, it chooses a random challenge z to challenge the PUF. On receipt of response r, the trusted party computes some helper data w such that key K can later be recovered by evaluating PUF(z; w) and stores (z; w; K) in a database. The tuple (z; w) is stored in the (unprotected) memory of the chip.
Helper data w has two different purposes [
Reconstructing a secret from a PUF. To reconstruct secret K, the chip reads
(z; w) from its memory, challenges its PUF with (z; w) and obtains K.
Efficient implementation. According to [
Symmetric-key-based authentication. In order to authenticate tokens, standard authentication mechanisms based on symmetric-key cryptography that are secure against impersonation under passive (imp-pa) and active (imp-aa) attacks [4, p. 10] can be used. Since low-cost RFID tags are not capable of running multiple sessions, concurrent attacks (imp-ca) must not be considered. To provide confidentiality and location privacy, the authentication scheme must not disclose user-related information (e.g., user data or movement profiles).
As described in Section 3.2, the major problem of realizing anonymous
authentication based on shared secrets is how to inform the other party about
which secret should be used without revealing the own identity. This problem
can be solved by employing rerandomizable public-key encryption [
Use of rerandomizable encryption. Rerandomizable public-key encryption can be used to provide a symmetric authentication key to authorized communication partners (e.g., trusted verifiers) without disclosing the identity of the token to unauthorized entities. Moreover the computations performed by the token are still contained in the more efficient symmetric-key setting.
During creation of a token T , the token issuer encrypts the token authentication key KT of token T with a public encryption key pk V whose corresponding secret decryption key is known to all verifiers (or their security modules or the trusted server). The resulting ciphertext cT = EncpkV (KT ) is then stored in the memory of the token. Whenever token T engages a protocol run with a verifier, it first sends its ciphertext cT . In case the recipient knows the correct decryption key, it can decrypt KT and use it in a subsequent authentication protocol.
Since an honest verifier must verify that a token has been created by a genuine issuer, a digital signature scheme is used to certify the token authentication key. However, this signature is static data and thus cannot be transmitted to the verifier as plaintext since this would enable tracing of the token and thus violate location privacy. Therefore, the signature must be included into the rerandomizable ciphertext.
However, cT is a static ciphertext and must be frequently rerandomized in
order to provide location privacy. Therefore, anonymizers must read cT ,
rerandomize it to c0T Rand(cT ), and replace cT with c0T [
This would enable gapless location privacy while improving practicability.
However, all known rerandomizable public-key encryption schemes require
to compute public-key operations (e.g., exponentiations) in order to
rerandomize a ciphertext. Thus, this approach is not applicable to symmetric-key
tags.
2. Public anonymizers: Anonymizers may be public, which means that they
can be constructed and run by everyone. However, public anonymizers as
proposed by [
Authentication of anonymizers can be realized in the same way as described above for verifiers. Each token may be initialized with an additional rerandomizable ciphertext cA that encrypts a token-specific symmetric anonymizer authentication key KA under a public-key pk A whose secret key sk A is known to all anonymizers trusted to anonymize the specific token. Thus, only trusted anonymizers can decrypt cA to obtain KA and use it to authenticate to the token to be anonymized. 3. Anonymizers controlled by transit enterprise: Anonymizers may be controlled by the (trusted) transit enterprise. For instance, anonymizers may be included into verifiers or mounted at the stations or in the vehicles of the transit enterprise. 4. User-controlled anonymizers: Each user may own an anonymizer that can only be used to rerandomize his own tags. Therefore the user must provide the public key pk A of his anonymizer A to the token issuer during the process of issuing an e-ticket.
To summarize, the user must trust the anonymizer to respect his privacy. However, this is a reasonable assumption since the anonymizer is either under his control or managed by a trusted entity (e.g., the transit enterprise). The issue protocol. A user U requests token issuer I to create a token with his desired usage conditions T (e.g., ticket type, expiration date, geographical usage restrictions, etc.) and therefore provides public-key pk A of his anonymizer A. Issuer I then creates the token authentication key KT and anonymizer authentication key KA for token T . After that, issuer I derives the corresponding helper data (zT ; wT ) and (zA; wA) for the PUF of token T as described in Section 4.1. Then, issuer I creates a certificate T = SignskI (KT ; T ) and two rerandomizable ciphertexts cT = EncpkV (KT ; T ; T ) and cA = EncpkA (KA). Finally, issuer I writes the tuple (wT ; wA; cT ; cA) to the (unprotected) memory of token T and physically passes token T to user U .
The anonymize protocol. In order to anonymize a token T , anonymizer A broadcasts an anonymization request. On receipt of this request, token T uses its random number generator to create a random challenge NT , reads both ciphertexts cT and cA from its memory, and sends the tuple (NT ; cT ; cA) to anonymizer A that then uses the rerandomization function of the rerandomizable encryption scheme to rerandomize both ciphertexts (cT ; cA) to (c0T ; c0A). After that, anonymizer A uses its secret decryption key sk A to decrypt the anonymizer authentication key KA from ciphertext cA, uses KA to authenticate message (KA; c0T ; c0A; NT ), which A then sends to token T . On receipt of this message, token T recovers its anonymizer authentication key KA by reading helper data wA from its memory and challenging its PUF as described in Section 4.1. If token T can successfully verify the authenticity of tuple (KA; c0T ; c0A; NT ) w.r.t. to key KA, token T updates both ciphertexts (cT ; cA) stored in its memory to the ciphertexts (c0T ; c0A) received from anonymizer A. If the authenticity of the response of anonymizer A cannot be verified, token T aborts.
The prove protocol. To verify the authenticity of token T , a verifier V first broadcasts a verification request. On receipt of this request, token T reads ciphertext cT from its memory and sends it to the verifier V , who then uses its secret decryption key sk V to decrypt (KT ; T ; T ) from cT . Then, verifier V uses public verification key pk I of token issuer I to verify T . If verification of T fails or the usage conditions T associated with token T are violated, verifier V rejects. Otherwise, it continues by using KT to engage an symmetric-key based authentication protocol with token T . Token T can recover its token authentication key KT by reading helper data wT from its memory and challenging its PUF as described in Section 4.1. Verifier V accepts token T as authentic token if token T successfully completes the authentication protocol w.r.t key KT . If authentication fails, verifier V rejects token T .
This section informally analysis which of the requirements of Section 2.4 are
fulfilled by the solution presented in Section 4. We will provide formal proofs
in an extended version of the security and privacy model of [
Authentication. The solution presented in Section 4 fulfills all of the authentication requirements of Section 2.4: Authentication: Honest verifiers will only accept tokens whose token authentication key has been certified by a genuine token issuer.
Unforgeability: The properties of the PUF, the underlying authentication protocol, and the semantic security of the rerandomizable encryption scheme ensure that a valid token cannot be cloned or simulated by an adversary since its secrets cannot be extracted. Moreover, the security of the digital signature scheme guarantees that an adversary cannot create valid tokens on his own since he cannot forge signatures.
Availability: The token only updates its internal memory with data that has been authenticated by an authorized (i.e., trusted) anonymizer. Thus, an adversary cannot tamper with the data stored on the token.
Privacy. The solution presented in Section 4 fulfills the following privacy requirements of Section 2.4 w.r.t. to trust model TM 2 (or trust model TM 3 if verifiers are equipped with security modules or are connected to a remote trusted server) as described in Section 4: Confidentiality: Since the rerandomizable encryption scheme is required to be semantically secure, no information on the secrets of the token is revealed by the corresponding ciphertexts. Moreover, the underlying authentication scheme is required not to disclose any user-related information. Thus, an adversary cannot obtain any information on the token or the user. Location Privacy: Tokens can be traced between two randomizations. However, if an adversary misses only one rerandomization, he cannot trace a token any more because of the semantic security of the rerandomizable encryption scheme and the properties of the authentication scheme. Our framework currently does not provide backwards and forward traceability, and we leave this as an interesting open problem.
Functional requirements. The solution presented in Section 4 fulfills all of
the functional of Section 2.4:
Efficiency: Verification of a token requires to run a symmetric-key-based
authentication protocol between the token and the verifier. Moreover, a single
public-key decryption and a single signature verification must be performed
by the verifier. This computational effort is comparable to existing schemes
currently used in practice (e.g., [
Scalability: The solution does not depend on the number of tokens. 5
Summary of contribution. We analyzed the viability of current proposals for privacy-preserving e-tickets and examined the applicability of privacy-enhancing RFID-based protocols. We showed that existing approaches are not suited for the application scenario of e-tickets and presented a solution based on existing cryptographic tools and current RFID technology.
Open research problems. As discussed in Section 3.2, all currently known privacypreserving authentication schemes for tokens that are limited to symmetric cryptography seem to require the token issuer to be trusted. Therefore, it would be interesting to find a scheme based on symmetric cryptography but similar to the one that provides similar properties as anonymous credential systems.
Currently, our approach does not provide forward and backward security.
Forward and backward-secure anonymous symmetric-key based authentication
schemes require frequent update of the secrets of the tokens [
The work of the third authors has been also supported in part by the European Commission through the FP7 Information Communication Technologies programme, under Contract FET-215270 FRONTS (Foundations of Adaptive Networked Societies of Tiny Artefacts).