Skip to Main content Skip to Navigation
Journal articles

Black-Box Trace&Revoke Codes

Hung Q. Ngo 1 Duong Hieu Phan 2 David Pointcheval 3
3 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : We address the problem of designing an efficient broadcast encryption scheme which is also capable of tracing traitors. We introduce a code framework to formalize the problem. Then, we give a probabilistic construction of a code which supports both traceability and revocation. Given N users with at most r revoked users and at most t traitors, our code construction gives rise to a Trace&Revoke system with private keys of size O((r+t)logN) (which can also be reduced to constant size based on an additional computational assumption), ciphertexts of size O((r+t)logN), and O(1) decryption time. Our scheme can deal with certain classes of pirate decoders, which we believe are sufficiently powerful to capture practical pirate strategies. In particular, our code construction is based on a combinatorial object called (r,s)-disjunct matrix, which is designed to capture both the classic traceability notion of disjunct matrix and the new requirement of revocation capability. We then probabilistically construct (r,s)-disjunct matrices which help design efficient Black-Box Trace&Revoke systems. For dealing with "smart" pirates, we introduce a tracing technique called "shadow group testing" that uses (close to) legitimate broadcast signals for tracing. Along the way, we also proved several bounds on the number of queries needed for black-box tracing under different assumptions about the pirate's strategies.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-00763979
Contributor : David Pointcheval <>
Submitted on : Wednesday, December 12, 2012 - 9:50:19 AM
Last modification on : Thursday, July 1, 2021 - 5:58:06 PM

Links full text

Identifiers

Citation

Hung Q. Ngo, Duong Hieu Phan, David Pointcheval. Black-Box Trace&Revoke Codes. Algorithmica, Springer Verlag, 2013, 67 (3), pp.418-448. ⟨10.1007/s00453-012-9702-y⟩. ⟨hal-00763979⟩

Share

Metrics

Record views

424