Graded signatures

Aggelos Kiayias, Murat Osmanoglu, Qiang Tang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


Motivated by the application of anonymous petitions, we formalize a new primitive called “graded signatures”, which enables a user to consolidate a set of signatures on a message m originating from l different signers that are members of a PKI. We call the value l ∈ ℕ, the grade of the consolidated signature. The resulting consolidated signature object on m reveals nothing more than the grade and the validity of the original signatures without leaking the identity of the signers. Further, we require that the signature consolidation is taken place in an unlinkable fashion so that neither the signer nor the CA of the PKI can tell whether a signature is used in a consolidation action. Beyond petitions, we demonstrate the usefulness of the new primitive by providing several other applications including delegation of signing rights adhering to dynamic threshold policies and issuing graded certificates in a multi-CA PKI setting. We present an efficient construction for graded signatures that relies on Groth-Sahai proofs and efficient arguments for showing that an integer belongs to a specified range. We achieve a linear in the grade signature size and verification time in this setting. Besides, we propose some extension that can support the certificate revocation by utilizing efficient non-membership proofs.

Original languageEnglish (US)
Title of host publicationInformation Security - 18th International Conference, ISC 2015, Proceedings
EditorsJavier Lopez, Chris J. Mitchell
PublisherSpringer Verlag
Number of pages20
ISBN (Print)9783319233178
StatePublished - 2015
Externally publishedYes
Event18th International Conference on Information Security, ISC 2015 - Trondheim, Norway
Duration: Sep 9 2015Sep 11 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other18th International Conference on Information Security, ISC 2015

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Graded signatures'. Together they form a unique fingerprint.

Cite this