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 proceedingConference contribution

Abstract / Description of output

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 identity-based 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 sub-authorities 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
Title of host publicationInformation Security
Subtitle of host publication17th International Conference, ISC 2014, Hong Kong, China, October 12-14, 2014. Proceedings. Lecture Notes in Computer Science 8783, Springer 2014
PublisherSpringer International Publishing
Number of pages11
ISBN (Electronic)978-3-319-13257-0
ISBN (Print)978-3-319-13256-3
Publication statusPublished - 2014

Publication series

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


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