Efficient schemes for anonymous credential with reputation support

Abstract

Anonymous credential is an important tool to protect the identity of users in the Internet for various reasons (e.g. free open speech) even when a service provider (SP) requires user authentication. Yet, misbehaving users may use anonymity for malicious purposes and SP would have no way to refrain these users from creating further damages.

Revocable anonymous credential allows SP to revoke a particular anonymous user based on the observed behavior of a session the user conducted. However, such kind of all-or-nothing revocation does not work well with the “Web 2.0” applications because it does not give a user a second chance to remedy a misconduct, nor rewards for positive behaviors. Reputation support is vital for these platforms.

In this thesis, we propose two schemes with different strengths that solve this privacy and reputation dilemma. Our first scheme, PE(AR)2, aims to empower anonymous credential based authentication with revocation and rewarding support. The scheme is efficient, outperforms PEREA which was the most efficient solution to this problem, with an authentication time complexity O(1) as compared with other related works that has dependency on either the user side storage or the blacklist size. PEREA has a few drawbacks that make it vulnerable and not practical enough. Our scheme fixes PEREA's vulnerability together with efficiency improvement. Our benchmark on PE(AR)2 shows that an SP can handle over 160 requests/second when the credentials store 1000 single-use tickets, which outperforms PEREA with a 460 fold efficiency improvement.

Our second scheme, SAC, aims to provide a revocation and full reputation support over anonymous credential based authentication system. With a small efficiency trade-o_ as compared with PE(AR)2, the scheme now supports both positive and negative scores. The scoring mechanism is now much more flexible, that SP could modify the rated score of any active sessions, or declare that no more rating should be given to it and mark it as finalized. SAC provides a much more elastic user side credential storage, there is no practical limit on the number of authentication sessions associated with a credential. Unlike other schemes, SAC make use of a combined membership proof instead of multiple non-membership proofs to distinguish if a session is active, finalized, or blacklisted. This special consideration has contributed to the reduction of efficiency-flexibility trade-off from PE(AR)2, making the scheme stay practical in terms of authentication time. Our benchmark on SAC shows that an SP can handle over 2.9 requests/second when the credentials store 10000 active sessions, which outperforms BLACR-Express (a related work based on pairing cryptography with full reputation support) with a 131 fold efficiency improvement.

Then we analyze the potential difficulties for adopting the solutions to any existing web applications. We present a plugin based approach such that our solutions could run on a user web browser directly, and how a service provider could instruct the plugin to communicate using our protocol in HTML context.

We conclude our thesis stating the solutions are practical, efficient and easy to integrate in real world scenario, and discuss potential future works.