Anonymous Credential Systems based on Signature Schemes and Standard Certification Infrastructures

PhD. thesis

Author: V. Benjumea.

Advisors: J. Lopez and J.M. Troya


This work focus on two security services for internet applications: authorization and anonymity. Traditional authorization solutions are not very helpful for many of the Internet applications; however, public key and attribute certificates proposed by ITU-T seems to be well suited and provide adequate solution. On the other hand, special attention is paid to the fact that many of the operations and transactions that are part of Internet applications can be easily recorded and collected, being an amportant threat against individial's privacy. Consequently, anonymity has become a desirable feature to be added in many cases.

This work analyses several cryptographic schemes based on digital signatures that provide a suitable mechanism supporting anonymous authentication and authorization, as well as their incorporation into standard certification infrastructures. Thus, it designs a new cryptographic scheme for digital signatures that provides a suitable support for anonymity, it defines the necessary mechanisms to incorporate this new cryptographic primitive into the x.509 standard, and provides the infrastructure necessary to support anonymous authorization based on privileges. Moreover, the system also introduces some mechanisms to revert the anonymity under special circumstances, such as dishonest behavior or under court order, under the hierarchy of the supervision authorities. Likewise, it also defines a metric suitable to model and analize this kinds of systems.

Keywords: Anonymous authentication, X.509 certificates, group signatures, ring signatures, traceable signatures


Usually, when remote transactions take place on the Internet, users are identified and must prove that they have enough privileges to perform a particular task. Each time a user carries out a transaction, sensitive information such as identity, privileges and actions is revealed. This information is processed and stored by servers and it can later be cross-referenced to create very comprehensive user profiles. Such profiles are essentially a record of the main activities of users during their daily life.

As the number of remote transactions grows, the amount of personal information that organizations collect also increases. In the near future, the majority of transactions that users can perform in their daily lives (e-government, e-bank, e-commerce, e-library, e-services, etc.) will be done remotely. This, together with the fact that information systems are able to collect, and cross reference large amounts of data, implies that the Internet will effectively become the largest surveillance system ever devised.

Therefore, on the one hand, anonymity can play a fundamental role in this scenario since it breaks the correlation between the user's identity and the sensitive information disclosed. Firstly, it is important that the communication channel is anonymous, since it is possible to identify the addresses of the hosts involved in the communication. Further, from these addresses it is usually easy to identify the user who performed the transaction. In this sense, many interesting proposals have arisen, such as mixnets, onion routing, crowds and hordes among others. Secondly, it is also important for users to be able to prove that they have enough privileges to perform a given transaction. At the same time, their identity should remain concealed and, in this way, protect their privacy. Solutions at this level (user level) have received not enough attention, though anonymous credentials have emerged as a means of supporting the anonymous proof of privileges. However, approaches are usually specialized closed systems whose technology has not reached practical open systems.

On the other hand, digital signatures are widely used to authenticate entities because they establish a secure and non-repudiable means to guarantee that a remote entity is indeed who it claims to be. And, closely related to digital signatures, X.509 public key and attribute certificates concepts have been developed as a standard and secure way of conveying users' identity and authorization information, respectively. They are a widely used means of providing suitable support for entity authentication and authorization in open systems. Nevertheless, they have been (originally) designed to support identities, and anonymity has not been considered in their design.

New signature schemes oriented towards providing support for anonymity have been designed from a purely cryptographic point of view. These signature schemes focus on anonymity from different points of views, with many interesting features such as those provided by group signatures, ring signatures, and traceable signatures, among others. In spite of those interesting features, they have not yet been transferred to practical open systems, nor has it been studied in which available systems the framework can be well supported.

Precisely, this thesis has looked at supporting anonymity at the user level, though designing and transferring these technologies to practical and open systems. We believe that standard frameworks, and more specifically, those proposed by ITU-T, provide a good means to do so. Actually, one of our main goals has been to find a suitable technology that can be embedded into standard frameworks while providing suitable support for anonymity in open and general scenarios for real world applications.

After acquiring the necessary experience in the field, we have been able to specify the set of requirements that a system should satisfy to support anonymity in a general and open environment such as that generally supported by standard frameworks. Given that ITU-T frameworks rely on digital signatures as a suitable mechanism for authentication, and that some new digital signature schemes have been designed to support anonymity in different ways, we also have studied in this thesis a number of those schemes in order to infer if they could support anonymity and how they could be eventually merged with ITU-T standards.

However, realizing that even with some suitable and interesting features none of the schemes fully satisfied the requirements specified for our general scenario, we have specified and designed a new cryptographic primitive providing the required anonymity support. Furthermore, we have analyzed how this new primitive could be incorporated into ITU-T frameworks and how the resulting anonymity feature could be integrated into X.509 authentication and authorization infrastructures.

Finally, we have defined some metrics that have allowed to model anonymous systems, providing a tool to analyze their features and fine tune some aspects that could influence in the anonymity of the system.


This dissertation introduces preliminary approaches and elaborate on a firm and final approach to the problem of protecting individuals' privacy in those scenarios where users are granted with different privileges to perform remote electronic transactions.

The first preliminary approach is based on the fair blind signature cryptographic primitive as a basic building block to support anonymity. This primitive allows the correlation to be broken between an identified user and the anonymous credentials that the user obtains. It has also been the first scheme in the literature which presents a suitable solution to the problem within a standard framework, the ITU-T X.509 framework. This fact is very relevant since has triggered the transfer of anonymity technology to ITU-T standards, what would facilitate its deployment in real world applications. The system also includes some mechanisms to reverse and trace anonymous actions. However, this approach has two main weaknesses which make the system suitable only under certain conditions. The main inconvenience of this approach arises from the fact that different usages of the same anonymous credentials are correlatable, what in general degrades and diminishes the degree of anonymity that users can obtain, and can even break their anonymity. The second inconvenience arises from the fact that it does not address the sharing of anonymous credentials by users, which leaves an open door for fraud. Another less significant drawback of this approach is that anonymity is obtained as the result of a two step process, and the interleaving of these steps affects the probability distribution of anonymity.

The second preliminary approach uses the traceable signature cryptographic primitive as a basic building block to support anonymity. In this scheme, all members of a group have the same probability of having been the issuer of a signature, and also the signature is indistinguishable from and unlinkable to any other. Therefore, this scheme is a very suitable tool for supporting anonymity. It also includes some mechanisms to reverse and trace anonymous actions. This cryptographic primitive is incorporated into the X.509 standard framework in the same way as the first approach. Though this approach is an improvement on the first one, it still has some inconveniences that make it only suitable for some restricted scenarios. The main snag is that the group manager has too much power. In this case, the manager can authorize group membership, and can reverse and trace anonymous actions, a feature which is an important drawback in real world scenarios. Another inconvenience, like in the previous case, is that it does not address the sharing of anonymous credentials by users. Furthermore, it has an added shortcoming in the sense that the reversal and tracing of anonymous actions is not based on non repudiable proofs. However, the approach is improved by intermixing the traceable signature with the fair blind signature schemes, although it remains still not close from solving all these deficiencies for general and open scenarios.

The aforementioned preliminary approaches represent partial solutions to the problem, and they are of much help, though under specific circumstances and restricted scenarios.

As aforementioned, the traceable signature scheme presents an appropriate basic tool for supporting anonymity, although it has some weaknesses. Thus, in order to provide suitable support for anonymity in open and general environments, we have designed in this thesis a new cryptographic primitive, the fair traceable multi-group signature, scheme based on the traceable signature scheme. In this one, the main strengths are kept, but its deficiencies have been corrected in order to provide a suitable support for anonymity in non-restricted scenarios. This new primitive, in addition to the main features of traceable signatures, provides the following improvements: (i) it incorporates two orthogonal and complementary mechanisms to preclude users from sharing their anonymous credentials; (ii) it splits the duties of group management, that is, on the one hand the group manager is now only responsible for joining new members to the group, and on the other hand the anonymity breaking procedures (open and reveal/trace) are under the control of the fairness authorities; (iii) they now are based on non-repudiable proofs.

However, the goal of this thesis has gone much beyond the creation of the new cryptographic primitive supporting anonymity. Our main aim has been to create a global anonymity solution for open scenarios. And for this reason we have elaborated on a four levels complete solution that is able to model different aspects of security and system design. Precisely, the first one has been the basic cryptographic level dealing with the signature schemes as described above.

The second level conveys security information within a standard framework, which makes possible the interoperability in open and heterogeneous systems. Interoperability and integration in existing systems is one of the goals of this work, and standard frameworks provide a suitable starting point for such purpose. This level allows integration of the aforementioned fair traceable multi-group signature cryptographic primitive, as well as ring, group and traceable signatures, into the X.509 standard framework, though the same approach can also be applied to incorporate these cryptographic primitives into other standards, such as the SPKI framework. This level also allows those signature schemes to be integrated into public key certificates, and they can therefore be used transparently just like any other signature scheme already supported by the framework. Thus, it makes possible the intermixing and integration of these anonymous signature schemes with existing ones. As a direct and important consequence, the X.509 framework incorporates anonymity as a new feature, and anonymous systems can benefit from the interoperability that the framework provides. The concept of authentication is extended with a new kind of authentication: anonymous authentication. Additionally, attribute certificates are bound to public key certificates, and therefore this new approach also supports anonymous authorization in a transparent way.

The third level of our solution deals with security aspects, such as establishing a secure communication channel between a client and an authenticated server. It also manages client authorization by means of a general authorization level. This level establishes a secure communication channel with an authenticated server by means of TLS, on which it defines a general authorization layer for client authorization. It uses standard certificates as well as the aforementioned extended ones, and therefore provides suitable support for identified and anonymous client authorization. It follows a user centric approach, where the authorization policy specifies the privileges that authorized users must own and the client authentication mode, and the user decides how and what information to disclose. In this sense, it fits into the Identity 2.0 initiative, while the anonymity takes it a step further. This layer deals with all aspects related with authorization, relieving the application layers from the burden of dealing with authentication and authorization.

The fourth level designs the architecture and high level protocols that support the infrastructure. It specifies the requirements that this kind of systems must fulfill, from the point of view of system requirements as well as from the anonymity requirements perspective. From an architecture point of view, it defines the main actors and application protocols that support the infrastructure. These application protocols are on top of the aforementioned authorization layer, and provide a suitable support for all the different aspects dealing with authentication and authorization, and especially with those ones related with anonymity as well as revocation, reversal and tracing of anonymous actions, in addition to the normal identified actions. This level defines the protocols to support the main goal of the infrastructure, however specific application protocols must be implemented by application layers on top of the authorization layer. The infrastructure is easily extensible to deal with new signature schemes as well as with new authentication and authorization paradigms. The proposed system fulfills all the requirements previously mentioned and provides suitable support for identified as well as for anonymous client authorization, under normal circumstances.

Additionally, a prototype of the system has been developed, which shows the feasibility of the infrastructure. The prototype has been implemented in Java, and supports both identified as well as anonymous client authorization. The traceable signature scheme has been used to support anonymity, instead of the fair traceable multi-group signature scheme, and therefore the prototype does not fully resemble the final proposed architecture and does not have the same properties, though it shows the feasibility of the proposed model.

Finally, the thesis presents a formal framework to analyze and compare the degree of anonymity that different solutions may reach as well as their degree of adequacy when compared with the potential as specified by the authorization policy. This formal framework, allows us to adjust anonymous systems to get to the maximum degree that they can reach. Thus, when this formal framework is applied to the global anonymity solution proposed in this work, one can observe that the solution achieves a very high degree of anonymity and adequacy.