Graded encryption, or how to play “who wants to be a millionaire?” Distributively

Aggelos Kiayias, Murat Osmanoglu, Qiang Tang

Research output: Chapter in Book/Report/Conference proceedingChapter

1 Scopus citations


We propose a new identity-based cryptographic primitive which we call graded encryption. In a graded encryption scheme, there is one central (mostly offline) authority and a number of sub-authorities holding master keys that correspond to different levels. As in identitybased encryption, a sender can encrypt a message using only the identity of the receiver (plus public parameters) but it may also specify a numerical grade i. Users may decrypt messages directed to their identity at grade i as long as they have executed a key-upgrade protocol with subauthorities 1,..., i. We require a grade i ciphertext to be secure in a strong sense: as long as there is one sub-authority with index j ≤ i that is not corrupted, the plaintext should be hidden from any recipient that has not properly upgraded her identity.

Graded encryption is motivated by multi-stage games (e.g., “who wants to be a millionaire”) played in a distributed fashion. Players unlock ciphertexts that belong to a certain stage i only if they have met all challenges posed by sub-authorities {1,..., i}. This holds true even if players collaborate with some of the sub-authorities. We give an efficient construction that has secret key and ciphertext size of a constant number of group elements. We also demonstrate further applications of graded encryption such as proving that a certain path was followed in a graph.

Original languageEnglish (US)
Title of host publicationInformation Security - 17th International Conference, ISC 2014, Proceedings
EditorsSherman S.M. Chow, Jan Camenisch, Lucas C.K. Hui, Siu Ming Yiu
PublisherSpringer Verlag
Number of pages11
ISBN (Electronic)9783319132563
StatePublished - 2014
Externally publishedYes

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

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Graded encryption, or how to play “who wants to be a millionaire?” Distributively'. Together they form a unique fingerprint.

Cite this