TY - GEN
T1 - Frameproof codes and compressive sensing
AU - Colbourn, Charles
AU - Horsley, Daniel
AU - Syrotiuk, Violet
PY - 2010/12/1
Y1 - 2010/12/1
N2 - Fingerprinting of digital content is often employed to prevent a small coalition of legitimate users from constructing a copy whose fingerprint is registered to a user not in the coalition. Sets of fingerprints that prevent t or fewer users from framing another user in this way are frameproof codes. A frameproof code is termed secure when no fingerprint constructed by a coalition of t or fewer users can also be constructed by a disjoint coalition of t or fewer users. Secure frameproof codes are related to cover-free families arising in combinatorial group testing. Here a different connection is explored. Interpreting frameproof codes and secure frameproof codes as certain types of separating hash families, it is shown that each underlies a useful measurement matrix for compressive sensing. Indeed frameproof codes for coalitions of t users underlie measurement matrices that admit ℓ0-recoverability of t-sparse vectors, while secure frameproof codes for coalitions of t users underlie measurement matrices that admit ℓ1-recoverability of t-sparse vectors. Consequences for the construction of measurement matrices are briefly outlined, but the focus is on the combinatorial similarities of frameproof codes, separating and distributing hash families, and measurement matrices.
AB - Fingerprinting of digital content is often employed to prevent a small coalition of legitimate users from constructing a copy whose fingerprint is registered to a user not in the coalition. Sets of fingerprints that prevent t or fewer users from framing another user in this way are frameproof codes. A frameproof code is termed secure when no fingerprint constructed by a coalition of t or fewer users can also be constructed by a disjoint coalition of t or fewer users. Secure frameproof codes are related to cover-free families arising in combinatorial group testing. Here a different connection is explored. Interpreting frameproof codes and secure frameproof codes as certain types of separating hash families, it is shown that each underlies a useful measurement matrix for compressive sensing. Indeed frameproof codes for coalitions of t users underlie measurement matrices that admit ℓ0-recoverability of t-sparse vectors, while secure frameproof codes for coalitions of t users underlie measurement matrices that admit ℓ1-recoverability of t-sparse vectors. Consequences for the construction of measurement matrices are briefly outlined, but the focus is on the combinatorial similarities of frameproof codes, separating and distributing hash families, and measurement matrices.
UR - http://www.scopus.com/inward/record.url?scp=79952436420&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79952436420&partnerID=8YFLogxK
U2 - 10.1109/ALLERTON.2010.5707016
DO - 10.1109/ALLERTON.2010.5707016
M3 - Conference contribution
AN - SCOPUS:79952436420
SN - 9781424482146
T3 - 2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010
SP - 985
EP - 990
BT - 2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010
T2 - 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010
Y2 - 29 September 2010 through 1 October 2010
ER -