From: cguyeux Date: Wed, 30 Jan 2013 15:44:54 +0000 (+0100) Subject: Avancées X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/canny.git/commitdiff_plain/2eb9039105dddddb3543a90570df003e5ad4ac82?ds=sidebyside;hp=f30c909e10a0d758bd045352bc1163b1e4efed16 Avancées --- diff --git a/ourapproach.tex b/ourapproach.tex index 0bfe489..25defad 100644 --- a/ourapproach.tex +++ b/ourapproach.tex @@ -118,12 +118,14 @@ that is based on the Blum Blum Shub~\cite{DBLP:conf/crypto/ShubBB82} pseudorando for security reasons. It has been indeed proven~\cite{DBLP:conf/crypto/ShubBB82} that this PRNG has the cryptographically security property, \textit{i.e.}, -for any sequence $L$ of output bits $x_i$, $x_{i+1}$, \ldots, $x_{i+L-1}$, +for any sequence of $L$ output bits $x_i$, $x_{i+1}$, \ldots, $x_{i+L-1}$, there is no algorithm, whose time complexity is polynomial in $L$, and which allows to find $x_{i-1}$ and $x_{i+L}$ with a probability greater than $1/2$. -Thus, even if the encrypted message would be extracted, -it would thus be not possible to retrieve the original one in a +Equivalent formulations of such a property can +be found. They all lead to the fact that, +even if the encrypted message is extracted, +it is impossible to retrieve the original one in polynomial time. diff --git a/stc.tex b/stc.tex index 16fbfb3..1ed8b44 100644 --- a/stc.tex +++ b/stc.tex @@ -1,11 +1,11 @@ Let $x=(x_1,\ldots,x_n)$ be the $n$-bits cover vector of the image $X$, -$m$ be the message to embed and +$m$ be the message to embed, and $y=(y_1,\ldots,y_n)$ be the $n$-bits stego vector. -The usual additive embbeding impact of replacing $x$ by $y$ in $X$ +The usual additive embedding impact of replacing $x$ by $y$ in $X$ is given by a distortion function -$D_X(x,y)= \Sigma_{i=1}^n \rho_X(i,x,y)$ where the function $\rho_X$ -expressed the cost of replacing $x_i$ by $y_i$ in $X$. +$D_X(x,y)= \Sigma_{i=1}^n \rho_X(i,x,y)$, where the function $\rho_X$ +expresses the cost of replacing $x_i$ by $y_i$ in $X$. Let us consider that $x$ is fixed: this is for instance the LSBs of the image edge bits. The objective is thus to find $y$ that minimizes $D_X(x,y)$. @@ -34,7 +34,7 @@ The objective is to modify $x$ to get $y$ s.t. $m = Hy$. In this algebra, the sum and the product respectively correspond to the exclusive \emph{or} and to the \emph{and} Boolean operators. If $Hx$ is already equal to $m$, nothing has to be changed and $x$ can be sent. -Otherwise we consider the difference $\delta = d(m,Hx)$ which is expressed +Otherwise we consider the difference $\delta = d(m,Hx)$, which is expressed as a vector : $$ \delta = \left( \begin{array}{l} @@ -45,23 +45,23 @@ $$ \right) \textrm{ where $\delta_i$ is 0 if $m_i = Hx_i$ and 1 otherwise.} $$ -Let us thus consider the $j$th column of $H$ which is equal to $\delta$. -We denote by $\overline{x}^j$ the vector we obtain by -switching the $j$th component of $x$, +Let us thus consider the $j-$th column of $H$, which is equal to $\delta$. +We denote by $\overline{x}^j$ the vector obtained by +switching the $j-$th component of $x$, that is, $\overline{x}^j = (x_1 , \ldots, \overline{x_j},\ldots, x_n )$. It is not hard to see that if $y$ is $\overline{x}^j$, then $m = Hy$. -It is then possible to embed 3 bits in only 7 LSB of pixels by modifying -1 bit at most. -In the general case, when comunicating $n$ message bits in -$2^n-1$ pixels needs $1-1/2^n$ average changes. +It is then possible to embed 3 bits in only 7 LSBs of pixels by modifying +at most 1 bit. +In the general case, when communicating $n$ message bits in +$2^n-1$ pixels needs $1-1/2^n$ average changes. \CG{Phrase pas claire}. -Unfortunately, for any given $H$, finding $y$ that solves $Hy=m$ and that -that minimizes $D_X(x,y)$ has exponential complexity with respect to $n$. +Unfortunately, for any given $H$, finding $y$ that solves $Hy=m$ and +that minimizes $D_X(x,y)$ has an exponential complexity with respect to $n$. The Syndrome-Trellis Codes (STC) -presented by Filler et al. in~\cite{DBLP:conf/mediaforensics/FillerJF10} +presented by Filler \emph{et al.} in~\cite{DBLP:conf/mediaforensics/FillerJF10} is a practical solution to this complexity. Thanks to this contribution, the solving algorithm has a linear complexity with respect to $n$. @@ -71,11 +71,11 @@ to each other and shifted down by one row. Thanks to this special form of $H$, one can represent every solution of $m=Hy$ as a path through a trellis. -Next, the process of finding $y$ consists of a forward and a backward part: +Next, the process of finding $y$ consists of two stages: a forward and a backward part. \begin{enumerate} \item Forward construction of the trellis that depends on $\hat{H}$, on $x$, on $m$, and on $\rho$; -\item Backward determinization of $y$ which minimizes $D$ starting with -the complete path with minimal weight +\item Backward determination of $y$ that minimizes $D$, starting with +the complete path having the minimal weight. \end{enumerate}