We present the Internet Computer Consensus (ICC) family of protocols for atomic broadcast (a.k.a., consensus), which underpin the Byzantine fault-tolerant replicated state machines of the Internet Computer. The ICC protocols are leader-based protocols that assume partial synchrony, and that are fully integrated with a blockchain. The leader changes probabilistically in every round. These protocols are simple and robust: in any round where the leader is corrupt (which itself happens with probability less than 1/3) or the network is asynchronous, each ICC protocol will effectively allow other parties to step in and propose blocks for that round and to move the protocol forward to the next round. In case there was no agreement on a single block in a round, a decision for this round will be taken in a later round with synchronous network behavior and an honest leader. The task of reliably disseminating the blocks to all parties is an integral part the protocol. We present three different protocols, along with various minor variations on each. The first of these protocols (ICC0) illustrates the combination of the main building blocks in a simplified manner for an easier presentation and analysis. Protocol ICC1 is designed to be integrated with a peer-to-peer gossip sub-layer, which reduces the bottleneck created at the leader for disseminating large blocks, a problem that all leader-based protocols must address. Our Protocol ICC2 addresses the same problem by substituting a lowcommunication reliable broadcast subprotocol (which may be of independent interest) for the gossip sub-layer.

We propose an ideal functionalityFCDand a construction ΠCDfor oblivious and updatable committed databases.FCDallows a proverPto read, write, and update values in a database and to prove to a verifierVin zero-knowledge (ZK) that a value is read from or written into a certain position. The following properties must hold: (1) values stored in the database remain hidden fromV; (2) a value read from a certain position is equal to the value previously written into that position; (3) (obliviousness) both the value read or written and its position remain hidden fromV.ΠCDis based on vector commitments. After the initialization phase, the cost of read and write operations is independent of the database size, outperforming other techniques that achieve cost sublinear in the dataset size for prover and/or verifier. Therefore, our construction is especially appealing for large datasets. In existing “commit-and-prove” two-party protocols, the task of maintaining a committed database betweenPandVand reading and writing values into it is not separated from the task of proving statements about the values read or written.FCDallows us to improve modularity in protocol design by separating those tasks. In comparison to simply using a commitment scheme to maintain a committed database,FCDallowsPto hide efficiently the positions read or written fromV. Thanks to this property, we design protocols for e.g. privacy-preserving e-commerce and location-based services whereVgathers aggregate statistics about the statements thatPproves in ZK.

Token payment systems were the first application of blockchain technology and are still the most widely used one. Early implementations of such systems, like Bitcoin or Ethereum, provide virtually no privacy beyond basic pseudonymity: all transactions are written in plain to the blockchain, which makes them linkable and traceable.

Vehicle-to-vehicle (V2V) communication systems are currently being prepared for real-world deployment, but they face strong opposition over privacy concerns. Position beacon messages are the main culprit, being broadcast in cleartext and pseudonymously signed up to 10 times per second. So far, no practical solutions have been proposed to encrypt or anonymously authenticate V2V messages. We propose two cryptographic innovations that enhance the privacy of V2V communication. As a core contribution, we introduce zone-encryption schemes, where vehicles generate and authentically distribute encryption keys associated to static geographic zones close to their location. Zone encryption provides security against eavesdropping, and, combined with a suitable anonymous authentication scheme, ensures that messages can only be sent by genuine vehicles, while adding only 224 Bytes of cryptographic overhead to each message. Our second contribution is an authentication mechanism fine-tuned to the needs of V2V which allows vehicles to authentically distribute keys, and is called dynamic group signatures with attributes. Our instantiation features unlimited locally generated pseudonyms, negligible credential download-and-storage costs, identity recovery by a trusted authority, and compact signatures of 216 Bytes at a 128-bit security level.

Certification of keys and attributes is in practice typically realized by a hierarchy of issuers. Revealing the full chain of issuers for certificate verification, however, can be a privacy issue since it can leak sensitive information about the issuer's organizational structure or about the certificate owner. Delegatable anonymous credentials solve this problem and allow one to hide the full delegation (issuance) chain, providing privacy during both delegation and presentation of certificates. However, the existing delegatable credentials schemes are not efficient enough for practical use.

The universal composability (UC) framework enables the modular design of cryptographic protocols by allowing arbitrary compositions of lower-level building blocks. Public-key encryption is unarguably a very important such building block. However, so far no UC-functionality exists that offers non-interactive encryption necessary for modular protocol construction. We provide an ideal functionality for non-committing encryption (i.e., public-key encryption secure against adaptive corruptions) with locally generated, and therefore non-interactive, ciphertexts. As a sanity check, we also provide a property-based security notion that we prove to be equivalent to the UC notion. We then show that the encryption scheme of Camenisch et al. (SCN '16) based on trapdoor permutations securely implements our notion in the random-oracle model without assuming secure erasures. This is the best one can hope to achieve as standard-model constructions do not exist due to the uninstantiability of round-optimal adaptively secure message transfer in the standard model (Nielsen, Crypto '02). We illustrate the modular reusability of our functionality by constructing the first non-interactive signcryption scheme secure against adaptive corruptions without secure erasures in the UC framework.

Membership revocation is essential for cryptographic applications, from traditional PKIs to group signatures and anonymous credentials. Of the various solutions for the revocation problem that have been explored, dynamic accumulators are one of the most promising. We propose Braavos, a new, RSA-based, dynamic accumulator. It has optimal communication complexity and, when combined with efficient zero-knowledge proofs, provides an ideal solution for anonymous revocation. For the construction of Braavos we use a modular approach: we show how to build an accumulator with better functionality and security from accumulators with fewer features and weaker security guarantees. We then describe an anonymous revocation component (ARC) that can be instantiated using any dynamic accumulator. ARC can be added to any anonymous system, such as anonymous credentials or group signatures, in order to equip it with a revocation functionality. Finally, we implement ARC with Braavos and plug it into Idemix, the leading implementation of anonymous credentials. This work resolves, for the first time, the problem of practical revocation for anonymous credential systems.

Personal information is often gathered and processed in a decentralized fashion. Examples include health records and governmental data bases. To protect the privacy of individuals, no unique user identifier should be used across the different databases. At the same time, the utility of the distributed information needs to be preserved which requires that it be nevertheless possible to link different records if they relate to the same user. Recently, Camenisch and Lehmann (CCS 15) have proposed a pseudonym scheme that addresses this problem by domain-specific pseudonyms. Although being unlinkable, these pseudonyms can be converted by a central authority (the converter). To protect the users' privacy, conversions are done blindly without the converter learning the pseudonyms or the identity of the user. Unfortunately, their scheme sacrifices a crucial privacy feature: transparency. Users are no longer able to inquire with the converter and audit the flow of their personal data. Indeed, such auditability appears to be diametral to the goal of blind pseudonym conversion. In this paper we address these seemingly conflicting requirements and provide a system where user-centric audits logs are created by the oblivious converter while maintaining all privacy properties. We prove our protocol to be UC-secure and give an efficient instantiation using novel building blocks.

The Trusted Platform Module (TPM) is an international standard for a security chip that can be used for the management of cryptographic keys and for remote attestation. The specification of the most recent TPM 2.0 interfaces for direct anonymous attestation unfortunately has a number of severe shortcomings. First of all, they do not allow for security proofs (indeed, the published proofs are incorrect). Second, they provide a Diffie-Hellman oracle w.r.t. the secret key of the TPM, weakening the security and preventing forward anonymity of attestations. Fixes to these problems have been proposed, but they create new issues: they enable a fraudulent TPM to encode information into an attestation signature, which could be used to break anonymity or to leak the secret key. Furthermore, all proposed ways to remove the Diffie-Hellman oracle either strongly limit the functionality of the TPM or would require significant changes to the TPM 2.0 interfaces. In this paper we provide a better specification of the TPM 2.0 interfaces that addresses these problems and requires only minimal changes to the current TPM 2.0 commands. We then show how to use the revised interfaces to build q-SDH-and LRSW-based anonymous attestation schemes, and prove their security. We finally discuss how to obtain other schemes addressing different use cases such as key-binding for U-Prove and e-cash.

When data maintained in a decentralized fashion needs to be synchronized or exchanged between different databases, related data sets usually get associated with a unique identifier. While this approach facilitates cross-domain data exchange, it also comes with inherent drawbacks in terms of controllability. As data records can easily be linked, no central authority can limit or control the information flow. Worse, when records contain sensitive personal data, as is for instance the case in national social security systems, such linkability poses a massive security and privacy threat. An alternative approach is to use domain-specific pseudonyms, where only a central authority knows the cross-domain relation between the pseudonyms. However, current solutions require the central authority to be a fully trusted party, as otherwise it can provide false conversions and exploit the data it learns from the requests. We propose an (un)linkable pseudonym system that overcomes those limitations, and enables controlled yet privacy-friendly exchange of distributed data. We prove our protocol secure in the UC framework and provide an efficient instantiation based on discrete-logarithm related assumptions.

We present a highly efficient cryptographic protocol to protect user passwords against server compromise by distributing the capability to verify passwords over multiple servers. Password verification is a single-round protocol and requires from each server only one exponentiation in a prime-order group. In spite of its simplicity, our scheme boasts security against dynamic and transient corruptions, meaning that servers can be corrupted at any time and can recover from corruption by going through a non-interactive key refresh procedure. The users' passwords remain secure against offline dictionary attacks as long as not all servers are corrupted within the same time period between refreshes. The only currently known scheme to achieve such strong security guarantees incurs the considerable cost of several hundred exponentiations per server. We prove our scheme secure in the universal composability model, which is well-known to offer important benefits for password-based primitives, under the gap one-more Diffie-Hellman assumption in the random-oracle model. Server initialization and refresh must take place in a trusted execution environment. Initialization additionally requires a secure message to each server, but the refresh procedure is non-interactive. We show that these requirements are easily met in practice by providing an example deployment architecture.

Password-authenticated secret sharing (PASS) schemes, first introduced by Bagherzandi et al. at CCS 2011, allow users to distribute data among several servers so that the data can be recovered using a single human-memorizable password, but no single server (or even no collusion of servers up to a certain size) can mount an off-line dictionary attack on the password or learn anything about the data. We propose a new, universally composable (UC) security definition for the two-server case (2PASS) in the public-key setting that addresses a number of relevant limitations of the previous, non-UC definition. For example, our definition makes no prior assumptions on the distribution of passwords, preserves security when honest users mistype their passwords, and guarantees secure composition with other protocols in spite of the unavoidable non-negligible success rate of online dictionary attacks. We further present a concrete 2PASS protocol and prove that it meets our definition. Given the strong security guarantees, our protocol is surprisingly efficient: in its most efficient instantiation under the DDH assumption in the random-oracle model, it requires fewer than twenty elliptic-curve exponentiations on the user's device. We achieve our results by careful protocol design and by exclusively focusing on the two-server public-key setting.

Establishing authentic channels has become a common operation on the Internet and electronic commerce would not be possible without it. Because traditionally authentication is based on identifying users, the success of electronic commerce causes rapid erosion of their privacy. Privacy-friendly authentication, such as group signatures or anonymous credential systems, could mitigate this issue minimizing the information released during an authentication operation. Unfortunately, privacy-friendly authentication systems are not yet deployed. One reason is their sophistication and feature richness, which is complicating their understanding. By providing a calculus for analyzing and comparing the requirements and goals of privacy-friendly authentication systems, we contribute to a better understanding of such technologies. Our calculus extends the one by Maurer and Schmid [18], by introducing: (1) pseudonyms to enable pseudonymous authentication, (2) a pseudonym annotation function denoting the information an entity reveals about itself, and (3) event-based channel conditions to model conditional release of information used for privacy-friendly accountability.

We extend the Camenisch-Lysyanskaya anonymous credential system such that selective disclosure of attributes becomes highly efficient. The resulting system significantly improves upon existing approaches, which suffer from a linear number of modular exponentiations in the total number of attributes. This limitation makes them unfit for many practical applications, such as electronic identity cards. Our novel approach can incorporate a large number of binary and finite-set attributes without significant performance impact. It compresses all such attributes into a single attribute base and, thus, boosts the efficiency of all proofs of possession. The core idea is to encode discrete binary and finite-set values as prime numbers. We then use the divisibility property for efficient proofs of their presence or absence. In addition, we contribute efficient methods for conjunctions and disjunctions. The system builds on the strong RSA assumption. We demonstrate the aptness of our method in realistic application scenarios, notably electronic identity cards, and show its advantages for small devices, such as smartcards and cell phones.

Using the Internet and other electronic media for our daily tasks has become common. Thereby a lot of sensitive information is exchanged, processed, and stored at many different laces. Once released, controlling the dispersal of this information is virtually impossible. Worse, the press reports daily on incidents where sensitive information has been lost, stolen, or misused - often involving large and reputable organizations. Privacy-enhancing technologies can help to minimize the amount of information that needs to be revealed in transactions, on the one hand, and to limit the dispersal, on the other hand. Many of these technologies build on common cryptographic primitives that allow for data to be authenticated and encrypted in such a way that it is possible to efficiently prove possession and/or properties of data revealing the data or side-information about it. Proving such statements is of course possible for any signature and encryption scheme. However, if the result is to be practical, special cryptographic primitives and proof protocols are needed.

We address the problem of privacy-preserving access control in distributed systems. Users commonly reveal more personal data than strictly necessary to be granted access to online resources, even though existing technologies, such as anonymous credential systems, offer functionalities that would allow for privacy-friendly authorization. An important reason for this lack of technology adoption is, as we believe, the absence of a suitable authorization language offering adequate expressiveness to address the privacy-friendly functionalities. To overcome this problem, we propose an authorization language that allows for expressing access control requirements in a privacy-preserving way. Our language is independent from concrete technology, thus it allows for specifying requirements regardless of implementation details while it is also applicable for technologies designed without privacy considerations. We see our proposal as an important step towards making access control systems privacy-preserving.

We conduct more and more of our daily interactions over electronic media. The EC-funded project PRIME (Privacy and Identity Management for Europe) envisions that individuals will be able to interact in this information society in a secure and safe way while retaining control of their privacy. The p roject had set out to prove that existing privacy-enhancing technologies allow for the construction of a user-controlled identity management system that comes surprisingly close to this vision. This paper describes two key elements of the PRIME identity management systems: anonymous credentials and policy languages that fully exploit the advanced functionality offered by anonymous credentials. These two key elements enable the users to carry out transactions, e.g., over the Internet, revealing only the strictly necessary personal information. Apart from presenting for the first time these two key results, this paper also motivates the need for privacy enhancing identity management, gives concrete requirements for such a system and then describes the key principles of the PRIME identity management solution.

Security and trust are core research issues for the further development of the Information Society and for 10 years have played, and continue to play, an integral part in the European Union’s Framework Programmes (FPs) for R&D. EU-supported collaborative research projects in trust and security bring together multi-partner stakeholders from industry (technology and service providers, system integrators and end-users), academic and research laboratories working in several interdisciplinary research fields. Sometimes, projects include actors from the legal, social and economic sectors. Together their joint efforts permit a better understanding of the conflicts and synergies between security, privacy and free market economics, as well as of the psychology and sociology of trust and security when building and deploying new technologies. The long term goal for funding this research effort is to convert the know-how of the EU in security, privacy and trust into economic advantages. In the period 1998–2002, under FP5, original and ground-breaking scientific & technological (S&T) work took place in ICT Trust and Security. Key S&T developments achieved at that period included significant advances in cryptology, smart cards and biometrics. EU-supported research also permitted the identification of new concepts in fields of work such as privacy, dependability and risk analysis. In the period 2002–2006, under FP6, research efforts in ICT security and trust have been further intensified. As part of the FP6-IST Programme, 37 R&D projects

Secure identity tokens such as Electronic Identity (eID) cards are emerging everywhere. At the same time user-centric identity management gains acceptance. Anonymous credential schemes are the optimal realization of user-centricity. However, on inexpensive hardware platforms, typically used for eID cards, these schemes could not be made to meet the necessary requirements such as future-proof key lengths and transaction times on the order of 10 seconds. The reasons for this is the need for the hardware platform to be standardized and certified. Therefore an implementation is only possible as a Java Card applet. This results in severe restrictions: little memory (transient and persistent), an 8-bit CPU, and access to hardware acceleration for cryptographic operations only by defined interfaces such as RSA encryption operations.

We present a protocol for anonymous access to a database where the different records have different access control permissions. These permissions could be attributes, roles, or rights that the user needs to have in order to access the record. Our protocol offers maximal security guarantees for both the database and the user, namely (1) only authorized users can access the record; (2) the database provider does not learn which record the user accesses; and (3) the database provider does not learn which attributes or roles the user has when she accesses the database.

We extend the Camenisch-Lysyanskaya anonymous credential system such that selective disclosure of attributes becomes highly efficient. The resulting system significantly improves upon existing approaches, which suffer from a linear complexity in the total number of attributes. This limitation makes them unfit for many practical applications, such as electronic identity cards. Our system can incorporate an arbitrary number of binary and finite-set attributes without significant performance impact. Our approach folds all such attributes in a single attribute base and, thus, boosts the efficiency of all proofs of possession. The core idea is to encode discrete binary and finite-set attribute values as prime numbers. We use the divisibility property for efficient proofs of their presence or absence. We additionally contribute efficient methods for conjunctions and disjunctions. The system builds on the Strong-RSA assumption alone. We demonstrate the applicability and performance improvements of our method in realistic application scenarios, such as, electronic identity cards and complex/structured credentials. Our method has crucial advantages in devices with restricted computational capabilities, such as smartcards and cell phones.

An electronic cash (e-cash) scheme lets a user withdraw money from a bank and then spend it anonymously. E-cash can be used only if it can be securely and fairly exchanged for electronic goods or services. In this paper, we introduce and realize endorsed e-cash. An endorsed e-coin consists of a lightweight endorsement x and the rest of the coin which is meaningless without x. We reduce the problem of exchanging e-cash to that of exchanging endorsements. We demonstrate the usefulness of endorsed e-cash by exhibiting simple and efficient solutions to two important problems: (1) optimistic and unlinkable fair exchange of e-cash for digital goods and services; and (2) onion routing with incentives and accountability for the routers. Finally, we show how to represent a set of n endorsements using just one endorsement; this means that the complexity of the fair exchange protocol for n coins is the same as for one coin, making e-cash all the more scalable and suitable for applications. Our fair exchange of multiple e-coins protocol can be applied to fair exchanges of (almost) any secrets.

User centricity is a significant concept in federated identity management (FIM), as it provides for stronger user control and privacy. However, several notions of user-centricity in the FIM community render its semantics unclear and hamper future research in this area. Therefore, we consider user-centricity abstractly and establish a comprehensive taxonomy encompassing user-control, architecture, and usability aspects of user-centric FIM. We highlight the various mechanisms to achieve the properties identified in the taxonomy. We show how these mechanisms may differ based on the underlying technologies which in turn result in different trust assumptions. We classify the technologies into two predominant variants of user-centric FIM systems with significant feature sets. We distinguish credential-focused systems, which advocate offline identity providers and long-term credentials at a user's client, and relationship-focused systems, which rely on the relationships between users and online identity providers that create short-term credentials during transactions. Note that these two notions of credentials are quite different. The former encompasses cryptographic credentials as defined by Lysyanskaya et al., in Selected Areas in Cryptography, LNCS, vol. 1758, and the latter encompasses federation tokens as used in today's FIM protocols like Liberty. We raise the question where user-centric FIM systems may go – within the limitations of the user-centricity paradigm as well as beyond them. Firstly, we investigate the existence of a universal user-centric FIM system that can achieve a superset of security and privacy properties as well as the characteristic features of both predominant classes. Secondly, we explore the feasibility of reaching beyond user centricity, that is, allowing a user of a user-centric FIM system to again give away user control by means of an explicit act of delegation. We do neither claim a solution for universal user-centric systems nor for the extension beyond the boundaries of user centricity, however, we establish a starting point for both ventures by leveraging the properties of a credential-focused FIM system.

We create a credential system that lets a user anonymously authenticate at most $n$ times in a single time period. A user withdraws a dispenser of n e-tokens. She shows an e-token to a verifier to authenticate herself; each e-token can be used only once, however, the dispenser automatically refreshes every time period. The only prior solution to this problem, due to Damgård et al. [29], uses protocols that are a factor of k slower for the user and verifier, where k is the security parameter. Damgård et al. also only support one authentication per time period, while we support n. Because our construction is based on e-cash, we can use existing techniques to identify a cheating user, trace all of her e-tokens, and revoke her dispensers. We also offer a new anonymity service: glitch protection for basically honest users who (occasionally) reuse e-tokens. The verifier can always recognize a reused e-token; however, we preserve the anonymity of users who do not reuse e-tokens too often.

Digital credentials and certificates can easily be shared and copied. For instance, if a user possesses a credential that allows her to access some service, she can easily share it with her friends and thereby let them use the service as well. While with non-anonymous credentials, this sharing can to some extend be detected by the fact that some credentials get used too often, such detection is not possible with anonymous credentials. Furthermore, the honest user is also at risk of identity theft: malicious software such as viruses and worms or phishing attacks can without too much difficulty steal her credentials.One solution to the problem is to use tamper-resistant hardware tokens to which a credential is bound such that a credential can only be used in connection with the token. Although this approach is sometimes taken for isolated high security applications, it is not used widely because of the organizational overhead to distribute such tokens. Moreover, such tokens are usually very application specific and hence cannot be used with different applications (from different service providers).Recently, however, manufacturers have started to embed into computers a tamper-resistant piece of hardware, called trusted platform modules (TPM), as specified by the Trusted Computing Group. In this paper we show that this module can in fact be used to secure anonymous as well as non-anonymous credentials. We provide a mechanism to insure that credentials can only be used with the TPM it got issued to. We then extend our solution to one that allows the use of credentials not only with the TPM they got issued to but also with other TPMs of the same user. Finally, we show how to secure a full-fledged anonymous credential system.

We introduce a new cryptographic primitive, called insubvertible encryption, that produces ciphertexts which can be randomized without the need of any key material. Unlike plain universal re-encryption schemes, insubvertible encryption prevents against adversarial exploitation of hidden channels, by including certificates proving that the ciphertext can only be decrypted by authorized parties.The scheme can be applied to RFID tags, providing strong protection against tracing. This enables post-sale applications of manufacturer-issued RFID tags while preserving the privacy of consumers. The functionality required of the RFID tags is minimal, namely that they be re-writable (many-writable). No cryptographic capabilities are required of the tags themselves, as the readers perform all necessary computations.

This paper describes the direct anonymous attestation scheme (DAA). This scheme was adopted by the Trusted Computing Group (TCG) as the method for remote authentication of a hardware module, called Trusted Platform Module (TPM), while preserving the privacy of the user of the platform that contains the module. DAA can be seen as a group signature without the feature that a signature can be opened, i.e., the anonymity is not revocable. Moreover, DAA allows for pseudonyms, i.e., for each signature a user (in agreement with the recipient of the signature) can decide whether or not the signature should be linkable to another signature. DAA furthermore allows for detection of "known" keys: if the DAA secret keys are extracted from a TPM and published, a verifier can detect that a signature was produced using these secret keys. The scheme is provably secure in the random oracle model under the strong RSA and the decisional Diffie-Hellman assumption.

Anonymous credential systems [8, 9, 12, 24] allow anonymous yet authenticated and accountable transactions between users and service providers. As such, they represent a powerful technique for protecting users' privacy when conducting Internet transactions. In this paper, we describe the design and implementation of an anonymous credential system based on the protocols developed by [6]. The system is based on new high-level primitives and interfaces allowing for easy integration into access control systems. The prototype was realized in Java. We demonstrate its use and some deployment issues with the description of an operational demonstration scenario.

We address the protection of mobile code against cheating and potentially malicious hosts. We point out that the recent approach based on computing with "encrypted functions" is limited to the case where only the code originator learns the result of the completion and the host running the code must not notice anything at all. We argue that if the host is to receive some output of the computation, then securing mobile code requires minimal trust in a third party. Tamper-proof hardware installed on each host has been proposed for this purpose. We introduce a new approach for securely executing (fragments of) mobile code that relies on a minimally trusted third party. This party is a generic independent entity, called the secure computation service, which performs some operations on behalf of the mobile application, but does not learn anything about the encrypted computation. Because it is universal, the secure computation service needs to be only minimally trusted and can serve many different applications. We present a protocol based on tools from theoretical cryptography that is quite practical for computing small functions.

Anonymity of the participants is an important requirement for some applications in electronic commerce, in particular for payment systems. Because anonymity could be in conflict with law enforcement, for instance in cases of blackmailing or money laundering, it has been proposed to design systems i n which a trustee or a set of trustees can selectively revoke the anonymity of the participants involved in a suspicious transaction. From an operational point of view, it can be an important requirement that such trustees are neither involved in payment transactions nor in the opening of an account, but only in case of a justified suspicion. In this paper we present an efficient anonymous digital payment systems satisfying this requirement. The described basic protocol for anonymity revocation can be used in on-line or off-line payment systems.

Many proposed payment systems allow the payer to remain anonymous during a transaction.However, this unconditional privacy protection could be misused by criminals, e.g. for blackmailing or money laundering.With a fair payment system, anonymous payments are still possible, but the anonymity can be removed with the help of a trusted party which need not be involved in the transaction itself.In this paper, we present an efficient fair payment system and we discuss its security.