Speeding Up Revocable Group Signature with Compact Revocation List Using Vector Commitments

Abstract

In ID-based user authentications, a privacy problem can occur, since the service provider (SP) can accumulate the user's use history from the user ID. As a solution to that problem, group signatures are researched. One of important issues in the group signatures is the user revocation. Previously, an efficient revocable scheme with signing/verification of constant complexity was proposed. In this scheme, users are managed by a binary tree, and a list of revoked user information, called a revocation list (RL), is used for revocation. However, the scheme suffers from the large RL. Recently, an extended scheme has been proposed, where the RL size is reduced by compressing RL. On the other hand, there is a problem that some overhead occurs in the authentication as a price for reducing the size of RL. In this research, we propose an extended scheme where the authentication is sped up by reducing the number of zero-knowledge proofs. Furthermore, we implemented it on a PC and shows the effectiveness. The verification time is about 30% shorter than the previous scheme.