Trace-and-revoke schemes are challenging 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 encryption and secret tracing, and can be based on the sub-exponential hardness of the LWE problem (with a super-polynomial modulus-to-noise ratio). The ciphertext size in our construction scales logarithmically in the size of the identity space and linearly in the size of the revocation list. Our scheme leverages techniques from both combinatorial and algebraic constructions for traitor tracing.
Category / Keywords: public-key cryptography / traitor tracing, revocation Original Publication (with major differences): IACR-ASIACRYPT-2020 Date: received 28 Aug 2019, last revised 26 Aug 2020 Contact author: skim13 at cs stanford edu, dwu4 at virginia edu Available format(s): PDF | BibTeX Citation Version: 20200826:164100 (All versions of this report) Short URL: ia.cr/2019/984