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?


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.

  • $\begingroup$ Can you show you understand the answer to the linked question by listing the vectors in $desc(C)$ in your example above. You can edit this question. $\endgroup$ – kodlu Apr 26 '17 at 21:41

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.

  • 1
    $\begingroup$ @harry55 do you understand the answer? $\endgroup$ – kodlu May 6 '17 at 4:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.