Paper 2026/2574

Broadcast and Trace from Lattices: Collusion-Resistant and Publicly Traceable

Abstract

A broadcast and trace scheme combines broadcast encryption with accountability. Specifically, broadcast encryption is augmented with an algorithm for tracing traitors within a specified set, even if the given pirate decoder is created by an arbitrary collusion of users. As in broadcast encryption, the size of the ciphertext should be sublinear in the total number of users $N$. In this work, we generically construct collusion-resistant broadcast and trace that supports public tracing from attribute-based encryption with succinct ciphertexts and lockable obfuscation, both of which are known from the decomposed LWE assumption. Our scheme has ciphertext size $\sqrt{N}\cdot\mathsf{poly}(\lambda, \log N)$, while the master public key and secret keys have size $\mathsf{poly}(\lambda, \log N)$. Previously, collusion-resistant broadcast and trace with public tracing required pairing-based assumptions, positional witness encryption, or indistinguishability obfuscation. In particular, we provide the first construction that relies on a simple and instance-independent lattice assumption. At the heart of our construction is a novel way to use nested lockable obfuscations, taking inspiration from the recent work of Nassar, Waters, and Wu that constructs positional witness encryption from indistinguishability obfuscation for null programs.