Trace and Revoke Schemes - Encryption for Digital Content - page 151

4.1 Revocation Game: Definitions

A trace and revoke scheme is based on a broadcast encryption scheme
BE = hKeyGen,Encrypt,Decrypti that supports revocation over a set of
receivers denoted by [n] = {1,...,n}. Referring the reader to Section 2.1 for
the basic definition of broadcast encryption, here we will consider the notion
of s-ary broadcast encryptions in general for which the Encrypt algorithm
prepares a ciphertext c on input a vector of messages M = hm 1 ,...,m s i∈M s .
The correctness given in Definition 2.1 can be enhanced to capture the case
of input-vector as in the Definition 3.1 of correctness for multiuser encryption
schemes. The security requirements can be discussed in a similar fashion with
the only difference in the security game the involvement of the input-vector
instead of a single message-input.
The objectives of tracing in a trace and revoke scheme are different than
in the case of traitor tracing. In the context of such a scheme our objective is
to disable the adversary in decrypting the transmission i.e., achieve the revo-
cation of the decryption algorithm that is represented by the adversary. This
may or may not necessarily require the identification of one of the traitors.
In order to capture this we will introduce a new type of game, called the re-
vocation game. As in the case of a tracing game it is an interaction between
two parties: the adversary and the tracer. The tracer has at its disposal the
encryption and the tracing key while the adversary has a set of corrupted
user keys. The ultimate objective of the tracer is to disable the decryption
algorithm that is represented by the adversary.
We recall the Definition 3.12 of a tracing game. In the revocation game
setting, we will specialize the set of random variables Q as well as the way the
predicate R responds on queries. Specifically, the game will be parameterized
by a revocation instruction ψ, and adhere to the following:

• The random variable Q Encryp ψ represents all ways to encrypt the plain-
texts with a pattern ψ from the language L of the broadcast encryp-
tion scheme. This means that Q Encryp ψ contains the random variables
Encrypt(ek,M,ψ) for any M = hm 1 ,...,m s i∈M s .
• R Encrypt is a predicate that on input ek,sk 1 ,...,sk n ,q,a, where q is dis-
tributed according to Q Encrypt
ψ

, it returns 1 if and only if a ∈ M where

q = Encrypt(ek,M,ψ).

Based on the above, the revocation game is a triple hKeyGen,Q Encryp ψ ,
R Encrypt i for t-coalitions against σ-pirates with rules of engagement that are
as in the case of a tracing game, Definition 3.12 and 3.13 . We also define
the pair hA,Ti to be admissible for a revocation game in the same way that
admissibility is defined for tracing games.
Recall that an adversary in a broadcast encryption scheme is a decryption
algorithm represented by the adversary that has access to a set of corrupted
user keys {sk u } u∈T . This adversary, in principle, is capable (but not obliged) to