Recent Advances in the area of Trace and Revoke Schemes

Yevgeniy Dodis, New York University

A (public key) Trace and Revoke Scheme combines the functionality of
broadcast encryption with the capability of traitor tracing.
Specifically, (1) a trusted center publishes a single public key and
distributes individual secret keys to the users of the system;
(2) anybody can encrypt a message so that all but a specified subset
of ``revoked'' users can decrypt the resulting ciphertext; and (3) if
a (small) group of users combine their secret keys to produce a
``pirate decoder'', the center can trace at least one of the
``traitors'' given access to this decoder.

The problem was considered in the symmetric key setting by Naor, Naor
and Lotspiech [NNL01], and in the public key setting by Naor and
Pinkas [NP00], Tzeng and Tzeng [TT01]. We give first formal
definitions of trace and revoke schemes in the public key setting. We
also construct provably secure trace and revoke schemes which
considerably improve previous work. First, we construct the the _first
adaptive chosen ciphertext secure_ (CCA2) Trace and Revoke Scheme
(based on the DDH assumption). We remark that no CCA2-secure schemes
were previously known even in the symmetric key setting.  Our scheme
is also the first _adaptively secure_ scheme, while prior schemes did
not support this even for a much weaker chosen plaintext security.
Second, we resolve the main open question of Naor et al. [NNL01], who
presented a very efficient ``subset difference'' (SD) method in the
symmetric key setting, ask asked if it was possible to translate their
method to the public key setting. We resolve this question in the
affirmative, by using the notion of _hierarchical identity-based
encryption_ [Gentry-Silverberg'02]. The scheme achieves a slightly
weaker form of CCA1-security as compared to our CCA2-secure scheme,
and also has slightly larger storage per user. However, it achieves
constant public key size, constant decryption time, and potentially
unbounded number of revocations.

If time permits, more recent follow up work will be mentioned. Joint
work with Nelly Fazio from NYU.