\begin{theorem}
La condition de l'algorithme de marquage est nécressaire et suffisante
pour permettre l'extraction du message du média marqué.
\end{theorem}

\begin{proof}
For sufficiency, let $d_i$ be the last iteration (date) the element $i \in \Im(S_p)$
of $x$ has been modified:% is defined by 
$$
d_i = \max\{j | S^j_p = i \}.
$$ 
Let $D=\{d_i|i \in \Im(S_p) \}$.
The set $\Im(S_c)_{|D}$ is thus 
the restriction of  the image of $S_c$ to $D$.


The host that results from this iteration scheme is thus
$(x^l_0,\ldots,x^l_{\mathsf{N}-1})$ where 
$x^l_i$ is either $x^{d_i}_i$ if $i$ belongs to $\Im(S_p)$ or $x^0_i$ otherwise.
Moreover, for each $i \in \Im(S_p)$, the element $x^{d_i}_i$ is equal to 
$m^{d_i-1}_{S^{d_i}_c}$. 
Thanks to constraint \ref{itm2:Sc}, all the indexes 
$j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ belong to 
$\Im(S_c)_{|D}$.
Let then $j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ s.t.
$S^{d_i}_c=j$. 
Thus we have all the elements $m^._j$ of the vector $m$.
Let us focus now on some  $m^{d_i-1}_j$.
Thus the value of $m^0_j$ can be  immediately
deduced by counting in $S_c$ how many
times the component $j$ has been switched 
before $d_i-1$.  

Let us focus now on necessity. 
If $\Im(S_c)_{|D} \subsetneq 
\llbracket 0 ;\mathsf{P} -1 \rrbracket$,
there exist some $j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ that 
do not belong to $\Im(S_c)_{|\Im(S_p)}$. 
Thus $m_j$ is  not present in $x^l$ and the message cannot be extracted.
\end{proof}

When the constraint \ref{itm2:Sc} is satisfied, we obtain a scheme
that always finds the original message provided the watermarked media 
has not been modified. 
In that context, correctness and completeness are established. 


Thanks to constraint~\ref{itm2:Sc}, the cardinality $k$ of
$\Im(S_p)$ is larger than $\mathsf{P}$. 
Otherwise the cardinality of $D$  would be smaller than $\mathsf{P}$ 
and similar to the cardinality of $\Im(S_c)_{|D}$,
which is contradictory.

One bit of index $j$ of the original message $m^0$
is thus embedded at least twice in $x^l$. 
By counting the number of times this bit has been switched in $S_m$, the value of 
$m_j$ can be deduced in many places. 
Without attack, all these values are equal and the message is immediately 
obtained.
 After an attack,  the value of $m_j$ is obtained as mean value of all 
its occurrences. 
The scheme is thus complete.
Notice that if the cover is not attacked, the returned message is always equal to the original 
due to the definition of the mean function.
