Paper 2026/1059

Threshold Traitor Tracing with Partial-Insider Resilience

Abstract

Threshold traitor tracing (Boneh et al. Crypto'24) addresses collusion in threshold encryption by tracing parties who collude to build illegal decryption devices called decoders. However, the original definition does not capture settings where adversaries can access partial decryptions published during normal system operation. In such settings, decoders sold to external buyers could depend on inputting additional partial decryptions from honest parties. Moreover, colluders may exploit observed partial decryptions when constructing a decoder to evade tracing, or even frame honest parties. Recently, Bormet et al. (EPrint'26) addressed this by introducing threshold traitor tracing in the presence of partial insiders. Their construction, however, works only in a weaker model, where decoders are assumed to output the full decryption, and colluders are assumed to observe only partial decryptions of valid ciphertexts. Additionally, they use a trusted dealer for key generation. In this work, we present the first construction resilient against partial insiders in the stronger model of distinguishing decoders. Furthermore, our construction does not rely on a trusted dealer and remains traceable when colluders have access to a partial decryption oracle. As part of this, we show how to generically lift traceability under a partial decryption oracle for valid ciphertexts to traceability under a partial decryption oracle for arbitrary ciphertexts using NIZK-PoKs. This transform is of independent interest, directly strengthening prior results that consider only valid-ciphertext partial decryption oracles, and allowing future analyses to focus on the simpler valid-ciphertext setting.