We revisit recent results from the area of collusion-resistant traitor tracing, and show how they can be combined and improved to obtain more efficient dynamic traitor tracing schemes. In particular, we show how the dynamic Tardos scheme of can be combined with the optimized score functions of to trace coalitions much faster. If the attack strategy is known, in many cases the order of the code length goes down from quadratic to linear in the number of colluders, while if the attack is not known, we show how the interleaving defense may be used to catch all colluders about twice as fast as in the dynamic Tardos scheme. Some of these results also apply to the static traitor tracing setting where the attack strategy is known in advance, and to group testing.
Recently, @cite_8 showed that the celebrated binary static scheme of Tardos @cite_10 can be converted into a dynamic binary scheme, with a code length of the order @math . Together with the divide-and-conquer construction of @cite_1 , allowing for a linear trade-off between the alphabet size and the code length, this allows one to build @math -ary schemes with a code length of the order @math , for arbitrary values of @math . For large @math , this approaches the result of Fiat and Tassa, both in the alphabet size and in the number of segments needed.
@cite_1 @cite_10 @cite_8
1991439166 2087879325 2145102561 1637999745
We give a generic divide-and-conquer approach for constructing collusion-resistant probabilistic dynamic traitor tracing schemes with larger alphabets from schemes with smaller alphabets. This construction offers a linear tradeoff between the alphabet size and the codelength. In particular, we show that applying our results to the binary dynamic Tardos scheme of leads to schemes that are shorter by a factor equal to half the alphabet size. Asymptotically, these codelengths correspond, up to a constant factor, to the fingerprinting capacity for static probabilistic schemes. This gives a hierarchy of probabilistic dynamic traitor tracing schemes, and bridges the gap between the low bandwidth, high codelength scheme of and the high bandwidth, low codelength scheme of Fiat and Tassa. We study the Tardos' probabilistic fingerprinting scheme and show that its codeword length may be shortened by a factor of approximately 4. We achieve this by retracing Tardos' analysis of the scheme and extracting from it all constants that were arbitrarily selected. We replace those constants with parameters and derive a set of inequalities that those parameters must satisfy so that the desired security properties of the scheme still hold. Then we look for a solution of those inequalities in which the parameter that governs the codeword length is minimal. A further reduction in the codeword length is achieved by decoupling the error probability of falsely accusing innocent users from the error probability of missing all colluding pirates. Finally, we simulate the Tardos scheme and show that, in practice, one may use codewords that are shorter than those in the original Tardos scheme by a factor of at least 16. For the Tardos traitor tracing scheme, we show that by combining the symbol-symmetric accusation function of ? with the improved analysis of Blayer and Tassa we get further improvements. Our construction gives codes that are up to four times shorter than Blayer and Tassa's, and up to two times shorter than the codes from ? Asymptotically, we achieve the theoretical optimal codelength for Tardos' distribution function and the symmetric score function. For large coalitions, our codelengths are asymptotically about 4.93 of Tardos' original codelengths, which also improves upon results from We describe a new class of list decodable codes based on Galois extensions of function fields and present a list decoding algorithm. These codes are obtained as a result of folding the set of rational places of a function field using certain elements (automorphisms) from the Galois group of the extension. This work is an extension of Folded Reed Solomon codes to the setting of Algebraic Geometric codes. We describe two constructions based on this framework depending on if the order of the automorphism used to fold the code is large or small compared to the block length. When the automorphism is of large order, the codes have polynomially bounded list size in the worst case. This construction gives codes of rate @math over an alphabet of size independent of block length that can correct a fraction of @math errors subject to the existence of asymptotically good towers of function fields with large automorphisms. The second construction addresses the case when the order of the element used to fold is small compared to the block length. In this case a heuristic analysis shows that for a random received word, the expected list size and the running time of the decoding algorithm are bounded by a polynomial in the block length. When applied to the Garcia-Stichtenoth tower, this yields codes of rate @math over an alphabet of size @math , that can correct a fraction of @math errors.