Traitor Tracing with $$N^{1/3}$$-Size Ciphertexts and O(1)-Size Keys from k-Lin

We present a pairing-based traitor tracing scheme for N users with $$\begin{aligned} | \textsf{pk}| = | \textsf{ct}| = O(N^{1/3}), \quad | \textsf{sk}| = O(1). \end{aligned}$$ This is the first pairing-based scheme to achieve $$| \textsf{pk}| \cdot | \textsf{sk}| \cdot | \textsf{ct}| = o(N)$$ . Our construction relies on the (bilateral) k-Lin assumption, and achieves private tracing and full collusion resistance. Our result simultaneously improves upon the sizes of $$ \textsf{pk}, \textsf{ct}$$ in Boneh–Sahai–Waters [Eurocrypt '06] and the size of $$ \textsf{sk}$$ in Zhandry [Crypto '20], while further eliminating the reliance on the generic group model in the latter work.