Traitor tracing - codeword properties

Question

Let $c ≥ 2$. A code $C ⊂ Q^n$ is a $c$-frameproof code if for any set $X ⊂ C$ with $|X| ≤ c$ we have desc$(X) ∩ C = X$. Thus the only codewords that a coalition of up to $c$ pirates is capable of producing are those that already belong to members of that coalition. To see a definition of desc$(X)$, see here.

What I want to know is, from the definition above can I say the following is not a 2-frameproof code?

$012,011,222,112$

As for example $012$ and $011$ agree in more than one position but I don't know if it must be the case that for any two of the codewords, they will have to agree in more than one position?? As $222$ and $112$ only agree in one position for example.

Answer 1

General method:

Let $X=\{222,112\}$ be a group of two traitors we focus on. Clearly (see my answer to your earlier question) $$\mathrm{desc}(X)=\{1,2\}\times \{1,2\}\times \{2\}=\{222,122,212,112\} $$ is the set of vectors these two users can create if they collude. Since $\mathrm{desc}(X)\cap C=X$, this is not a contradiction to the code being $2-$frameproof.

Edit: Intuitively, two users can compare their symbols at each position and choose to use either symbol, if their symbols are distinct. If by doing this they can generate a third user's codeword, they can frame him/her by using his/her codeword. The code symbol alphabet will be very large and you can think of code symbols as cryptographic keys, and the whole codeword as a concatenated key. Thus it is infeasible to brute force the keys except by learning them with pairwise sharing between coalitions of users (called traitors).

You need to do this for all sets $X$ made up of 2 codewords and verify the e equality holds. The overlap of codewords does not allow you a shortcut to decide if the code is $2-$frameproof.

For a small code:

Can we find two codewords that allow two traitors to build a third codeword thus frame a third user?

YES. Using $X=\{011,112\}$ we can build $012$ which is another codeword. So this code is not $2-$frameproof. Thus if Alice is the user who is assigned codeword $011$ and Bob is the user who is assigned the codeword $112$ they can generate the vectors in $desc(X)$ and in fact they can pretend to be Harry, the user who is assigned the codeword $012$, and frame him by, e.g. downloading a movie which will be charged to his account.