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

vocation (broadcast encryption) and traitor tracing. Combining these two
functionalities of tracing and revoking in a single system is not straightfor-
ward. This was identified in [ 90 ] and explored further in [ 37 ].
The trace and revoke schemes for stateless receivers proposed by Naor,
Naor and Lotspiech [ 87 ] were the first e cient constructions that are capable
of dealing with the problem of disabling pirate decoders while supporting
unbounded revocation. In this work the subset cover framework was put forth,
that we laid out in Chapter 2 ; a large number of works, including [ 53 , 122 ,
50 , 6 , 55 , 56 , 57 ], can be described within this framework.
Regarding the overall effectiveness of the revocation game, a relevant prop-
erty is “bifurcation”. It was put forth in [ 87 ] and suggests that splitting any
subset S ∈ Φ can be done in two roughly equal sets. In the terminology of this
chapter, bifurcation enables one to bound the length of the longest chain in the
partial order of revocation instructions SC to be logarithmic in the number
of users. It is worth noting that one may trade bifurcation for weaker, more
unbalanced splits, to increase other e ciency parameters of a scheme. This
behavior is exhibited for example by the layered Subset Difference method of
[ 53 ].
Regarding the public-key setting, Dodis and Fazio[ 35 ] showed how the
subset cover framework can be used to make e cient public-key schemes. A
more recent trace and revoke scheme in the public key setting was proposed
by Boneh et al. in [ 24 ], and further improved by Furukawa and Attrapadung
in [ 44 ].
All the above schemes were designed for tracing in the black-box setting
and it is not straightforward how to add revocation on top of known traitor
tracing schemes for pirate rebroadcasting. To see why the straightforward ap-
proach fails suppose one decides to combine a broadcast encryption at the
decoder level with, say, a traitor tracing scheme pirate for rebroadcasting by
combining the two encryption functions (e.g., via a 2-out-of-2 secret-sharing
schem e 1 ) . This means that legitimate decoders will have to possess indepen-
dent sets of keys from both schemes, i.e., one set of keys for the encryp-
tion/decryption involved in the traitor tracing layer that binds the marked
content to a receiver and one set of keys for the encryption/decryption involved
in the broadcast encryption layer. It is easy to see that a pirate possessing
the key material of as few as two traitor users can evade revocation at the
decoder level by simply employing the keys of one user for decrypting the trai-
tor tracing layer and the keys of the other user for decrypting the broadcast
encryption layer. In this attack scenario, the traitor tracing scheme will suc-
cessfully recover the identity of one of the traitors but subsequently revoking
the recovered user will have absolutely no effect in the decryption capability
of the pirate decoder (which will continue to operate due to the fact that it
1 A 2-out-of-2 secret-sharing scheme enables the split of a secret to two parts so that
both are needed to recover the secret and each one individually is independent
from the secret.