Frameproof (FP) code

Frameproof (FP) code[1,2]

Description

A block code designed to prevent a group of users from framing another user outside of the group for creating an unauthorized copy of data. FP codes help to provide software protection from the illegal distribution and copying of computer software and copyrighted materials. These codes help protect products of distributors as well as other naive users from being framed for illegal activity [3].

A $c$-separating code has the property that, for any two disjoint sets that each contain at most $c$ code words, there is at least one position where the set of symbols of each set are disjoint [4]. Separating codes are, equivalently, codes with the secure FP (SFP) property [2].

Let us define $\Gamma = \{w^{(1)}, \dots, w^{(n)}\} \subseteq GF(2)^{l}$ as an ( $l,n$ )-code. Each codeword $w^{(i)}$ correlates to a user $u_i$. Let $C$ be a group of users. A bit in position $i$ is undetectable for the group $C$ when the words assigned to the users in the group match at the same position $i$. The feasible set of the group $C$, denoted $F(C;\Gamma)$ or $F(C)$, for some user $u \in C$ contains all of the codewords that match the group's set of undetectable bits. Finally, if every subset $S \subset \Gamma$ of size at most $c$ satisfies $F(S)\cap\Gamma = S$, then $\Gamma$ is a $c$-FP code [3].

Any $c$-FP code must be of length at least $c$ [3]. A length-$l$ $q$-ary $c$-FP code has at most $tq^{\lceil l/c \rceil} + O(q^{\lceil l/c \rceil - 1})$ codewords, where $t$ is an integer between $1$ and $c$, and $t \equiv 1$ modulo $c$ [5].

Rate

FP codes tend to have large minimal distance and low rate [3]. Specifically, for any positive integers $n$ and $c$, if $l = 16c^{2}\log n$, then there exists a $c$-FP $ (l,n) $-code which has rate $n/l$ [3]. See Ref. [6] for other bounds on FP codes.

Realizations

FP codes are utilized in digital fingerprinting and watermarking [5].

Parent

Block code

Child

Identifiable parent property (IPP) code — A $t$-IPP code is a $t$-SFP code, which further implies it is a $t$-FP code; see [8][7; Sec. I.C].

Cousins

Evaluation AG code — Asymptotic bounds on FP codes can be formulated using evaluation AG codes [9,10]. A sufficient condition for an evaluation AG code to be FP can be recast as an instance of the Riemann-Roch equation [11; Sec. 15.8.2].
Kerdock code — Kerdock codes of sufficient order are separating [12,13].

References

[1]: D. Boneh and J. Shaw, “Collusion-secure fingerprinting for digital data”, IEEE Transactions on Information Theory 44, 1897 (1998) DOI
[2]: D. R. Stinson, T. van Trung, and R. Wei, “Secure frameproof codes, key distribution patterns, group testing algorithms and related structures”, Journal of Statistical Planning and Inference 86, 595 (2000) DOI
[3]: D. Boneh and J. Shaw, “Collusion-Secure Fingerprinting for Digital Data”, Advances in Cryptology — CRYPT0’ 95 452 (1995) DOI
[4]: M. Fernandez and J. J. Urroz, “A study of the separating property in Reed-Solomon codes by bounding the minimum distance”, Designs, Codes and Cryptography 90, 427 (2022) DOI
[5]: S. R. Blackburn, “Frameproof Codes”, SIAM Journal on Discrete Mathematics 16, 499 (2003) DOI
[6]: C. Shangguan, X. Wang, G. Ge, and Y. Miao, “New Bounds For Frameproof Codes”, (2014) arXiv:1411.5782
[7]: J. N. Staddon, D. R. Stinson, and Ruizhong Wei, “Combinatorial properties of frameproof and traceability codes”, IEEE Transactions on Information Theory 47, 1042 (2001) DOI
[8]: R. Ahlswede and N. Cai, “Codes with the identifiable parent property and the multiple–access channel”, Electronic Notes in Discrete Mathematics 21, 143 (2005) DOI
[9]: Chaoping Xing, “Asymptotic bounds on frameproof codes”, IEEE Transactions on Information Theory 48, 2991 (2002) DOI
[10]: H. Randriambololona, “(2,1)-separating systems beyond the probabilistic bound”, (2012) arXiv:1010.5764
[11]: W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[12]: Krasnopeev, A., and Yu L. Sagalovich. "The Kerdock codes and separating systems." Eight International Workshop on Algebraic and Combinatorial Coding Theory. Vol. 7. No. 7.2. 2002.
[13]: T. H. Helleseth, H. G. Schaathun, T. H. Helleseth, and H. G. Schaathun, “On the&lt;tex&gt;$”, IEEE Transactions on Information Theory 50, 3312 (2004) DOI

Page edit log

Raley Roberts (2024-03-15) — most recent
Victor V. Albert (2024-03-15)

Cite as:

“Frameproof (FP) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/frameproof

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/properties/block/copyright/frameproof.yml.