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

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.