Organic chemistry

Public-key cryptography

Key (lock)

Signature (topology)

Mathematics

Mathematical analysis

Group signature

Encryption

Chemistry

Programming language

Geometry

Constant (computer programming)

Group key

Group (periodic table)

Computer science

Scheme (mathematics)

Theoretical computer science

Computer security

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

Lots of revocable group signature schemes have been proposed so far. In one type of revocable schemes, signing and/or verifying algorithms have O(N) or O(R) complexity, where N is the group size and R is the number of revoked members. On the other hand, in Camenisch-Lysyanskaya scheme and the followers, signing and verifying algorithms have O(1) complexity. However, before signing, the updates of the secret key are required. The complexity is O(R) in the worst case. In this paper, we propose a revocable scheme with signing and verifying of O(1) complexity, where any update of secret key is not required. The compensation is the long public key of O(N). In addition, we extend it to the scheme with O(√N)-size public key, where signing and verifying have constant extra costs.

Revocable Group Signature Schemes with Constant Costs for Signing and Verifying