From fd3c8d84472bbc887a48fc8e441bd3fafedf96a7 Mon Sep 17 00:00:00 2001
From: couchot <jf.couchot@gmail.com>
Date: Mon, 21 Sep 2015 11:37:56 +0200
Subject: [PATCH 1/1] ajout annexe

---
 annexePreuveMarquageCorrectioncompletude.tex | 64 ++++++++++++++++++++
 1 file changed, 64 insertions(+)
 create mode 100644 annexePreuveMarquageCorrectioncompletude.tex

diff --git a/annexePreuveMarquageCorrectioncompletude.tex b/annexePreuveMarquageCorrectioncompletude.tex
new file mode 100644
index 0000000..dd6ad42
--- /dev/null
+++ b/annexePreuveMarquageCorrectioncompletude.tex
@@ -0,0 +1,64 @@
+\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.
-- 
2.39.5