Cryptology ePrint Archive: Report 2019/984

Collusion Resistant Trace-and-Revoke for Arbitrary Identities from Standard Assumptions

Sam Kim and David J. Wu

Abstract: A traitor tracing scheme is a multi-user public-key encryption scheme where each user in the system holds a decryption key that is associated with the user's identity. Using the public key, a content distributor can encrypt a message to all of the users in the system. At the same time, if a malicious group of users combine their respective decryption keys to build a "pirate decoder," there is an efficient tracing algorithm that the content distributor can use to identify at least one of the keys used to construct the decoder. A trace-and-revoke scheme is an extension of a standard traitor tracing scheme where there is an additional key-revocation mechanism that the content distributor can use to disable the decryption capabilities of compromised keys.

Trace-and-revoke schemes are generally difficult to construct. Existing constructions from standard assumptions can only tolerate bounded collusions (i.e., there is an a priori bound on the number of keys an adversary obtains), have system parameters that scale exponentially in the bit-length of the identities, or satisfy weaker notions of traceability that are vulnerable to certain types of "pirate evolution" attacks. In this work, we provide the first construction of a trace-and-revoke scheme that is fully collusion resistant and capable of supporting arbitrary identities (i.e., the identities can be drawn from an exponential-size space). Our scheme supports public broadcast and secret tracing, and can be based on the sub-exponential hardness of the LWE problem (with a super-polynomial modulus-to-noise ratio). Our construction relies on a combination of both algebraic and combinatorial techniques for traitor tracing.

Category / Keywords: public-key cryptography / traitor tracing, revocation

Date: received 28 Aug 2019, last revised 28 Aug 2019

Contact author: skim13 at cs stanford edu,dwu4@virginia edu

Available format(s): PDF | BibTeX Citation

Version: 20190829:111841 (All versions of this report)

Short URL: ia.cr/2019/984