Traitor Tracing with N^(1/3)-size Ciphertexts and O(1)-size Keys from k-Lin

ePrint Report: Traitor Tracing with N^(1/3)-size Ciphertexts and O(1)-size Keys from k-Lin

Junqing Gong, Ji Luo, Hoeteck Wee

We present a pairing-based traitor tracing scheme for $N$ users with$$
|\mathsf{pk}| = |\mathsf{ct}| = O(N^{1/3}), \quad |\mathsf{sk}| = O(1).
$$This is the first pairing-based scheme to achieve ${|\mathsf{pk}|\cdot|\mathsf{sk}|\cdot|\mathsf{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 $\mathsf{pk},\mathsf{ct}$ in Boneh–Sahai–Waters [Eurocrypt '06] and the size of …

construction eprint report keys quad report result size tracing