Graded Signatures

Aggelos Kiayias, Murat Osmanoglu, Qiang Tang

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

Abstract / Description of output

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∈Nl∈N , 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
Title of host publicationInformation Security: 18th International Conference
Subtitle of host publicationISC 2015, Trondheim, Norway, September 9-11, 2015, Proceedings
EditorsJavier Lopez, Chris J. Mitchell
Place of PublicationCham
PublisherSpringer International Publishing
Number of pages20
ISBN (Electronic)978-3-319-23318-5
ISBN (Print)978-3-319-23317-8
Publication statusPublished - Aug 2015

Publication series

NameLecture Notes in Computer Science (LNCS)
PublisherSpringer International Publishing
ISSN (Print)0302-9743


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

Cite this