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

Junqing Gong; Ji Luo; Hoeteck Wee

Paper 2023/256

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

Junqing Gong, East China Normal University, Shanghai, China, Shanghai Qi Zhi Institute, Shanghai, China

Ji Luo

, University of Washington, Seattle, USA

Hoeteck Wee, NTT Research, Sunnyvale, USA

Abstract

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 $\mathsf{sk}$ in Zhandry [Crypto '20], while further eliminating the reliance on the generic group model in the latter work.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in EUROCRYPT 2023
Keywords: traitor tracing pairing
Contact author(s): jqgong @ sei ecnu edu cn
luoji @ cs washington edu
wee @ di ens fr
History: 2023-02-22: approved; 2023-02-22: received; See all versions
Short URL: https://ia.cr/2023/256
License: CC BY

BibTeX

@misc{cryptoeprint:2023/256,
      author = {Junqing Gong and Ji Luo and Hoeteck Wee},
      title = {Traitor Tracing with N^(1/3)-size Ciphertexts and O(1)-size Keys from k-Lin},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/256},
      year = {2023},
      url = {https://eprint.iacr.org/2023/256}
}