annexePreuveMarquageCorrectioncompletude.tex

   1 \begin{theorem}
   2 La condition de l'algorithme de marquage est nécressaire et suffisante
   3 pour permettre l'extraction du message du média marqué.
   4 \end{theorem}
   5
   6 \begin{proof}
   7 For sufficiency, let $d_i$ be the last iteration (date) the element $i \in \Im(S_p)$
   8 of $x$ has been modified:% is defined by
   9 $$
  10 d_i = \max\{j | S^j_p = i \}.
  11 $$
  12 Let $D=\{d_i|i \in \Im(S_p) \}$.
  13 The set $\Im(S_c)_{|D}$ is thus
  14 the restriction of  the image of $S_c$ to $D$.
  15
  16
  17 The host that results from this iteration scheme is thus
  18 $(x^l_0,\ldots,x^l_{\mathsf{N}-1})$ where
  19 $x^l_i$ is either $x^{d_i}_i$ if $i$ belongs to $\Im(S_p)$ or $x^0_i$ otherwise.
  20 Moreover, for each $i \in \Im(S_p)$, the element $x^{d_i}_i$ is equal to
  21 $m^{d_i-1}_{S^{d_i}_c}$.
  22 Thanks to constraint \ref{itm2:Sc}, all the indexes
  23 $j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ belong to
  24 $\Im(S_c)_{|D}$.
  25 Let then $j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ s.t.
  26 $S^{d_i}_c=j$.
  27 Thus we have all the elements $m^._j$ of the vector $m$.
  28 Let us focus now on some  $m^{d_i-1}_j$.
  29 Thus the value of $m^0_j$ can be  immediately
  30 deduced by counting in $S_c$ how many
  31 times the component $j$ has been switched
  32 before $d_i-1$.
  33
  34 Let us focus now on necessity.
  35 If $\Im(S_c)_{|D} \subsetneq
  36 \llbracket 0 ;\mathsf{P} -1 \rrbracket$,
  37 there exist some $j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ that
  38 do not belong to $\Im(S_c)_{|\Im(S_p)}$.
  39 Thus $m_j$ is  not present in $x^l$ and the message cannot be extracted.
  40 \end{proof}
  41
  42 When the constraint \ref{itm2:Sc} is satisfied, we obtain a scheme
  43 that always finds the original message provided the watermarked media
  44 has not been modified.
  45 In that context, correctness and completeness are established.
  46
  47
  48 Thanks to constraint~\ref{itm2:Sc}, the cardinality $k$ of
  49 $\Im(S_p)$ is larger than $\mathsf{P}$.
  50 Otherwise the cardinality of $D$  would be smaller than $\mathsf{P}$
  51 and similar to the cardinality of $\Im(S_c)_{|D}$,
  52 which is contradictory.
  53
  54 One bit of index $j$ of the original message $m^0$
  55 is thus embedded at least twice in $x^l$.
  56 By counting the number of times this bit has been switched in $S_m$, the value of
  57 $m_j$ can be deduced in many places.
  58 Without attack, all these values are equal and the message is immediately
  59 obtained.
  60  After an attack,  the value of $m_j$ is obtained as mean value of all
  61 its occurrences.
  62 The scheme is thus complete.
  63 Notice that if the cover is not attacked, the returned message is always equal to the original
  64 due to the definition of the mean function.