+\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.
