]> AND Private Git Repository - HindawiJournalOfChaos.git/blob - IH/iihmsp11.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
abstract
[HindawiJournalOfChaos.git] / IH / iihmsp11.tex
1
2
3 \section{Steganography: a Class of Algorithms having Secure Properties~\cite{bcg11b:ip}}
4
5
6 This section summarizes~\cite{bcg11b:ip}, in which
7  a new class of non-blind information hiding
8 algorithms based on chaotic iterations has been proposed, and
9 its stego-security and topological security has been proven.  
10
11 \subsection{Introduction}\label{sec:intro}
12
13 The work~\cite{bcg11b:ip} focuses on non-blind  binary information hiding scheme: 
14 the  original host  is  required  to  extract the  binary hidden
15 information. This  context is indeed not
16 as restrictive as it could primarily appear.
17 Firstly, it allows to prove 
18 the authenticity of a document sent  through the  Internet 
19 (the original document is stored whereas the stego content is sent). 
20 Secondly, Alice and Bob can establish an hidden channel into a
21 streaming video 
22 (Alice and Bob both have the same movie, and  Alice hide information into 
23 the frame number $k$  iff the binary digit
24 number $k$ of its hidden message is  1).
25 Thirdly, based on a similar idea, a same
26 given image can be marked  several times by using various secret parameters
27 owned both by Alice and Bob. Thus more than one bit can be embedded into a given
28 image  by using  dhCI  dissimulation. Lastly,  non-blind watermarking  is
29 useful in  network's anonymity and intrusion  detection \cite{Houmansadr09}, and
30 to protect digital data sending through the Internet \cite{P1150442004}.
31
32 Before~\cite{bcg11b:ip},  stego-security~\cite{Cayre2008} and topological security 
33 were only proven 
34 on the spread spectrum watermarking~\cite{Cox97securespread,HuangFang},
35 and on the dhCI algorithm, which is notably based on iterating  
36 the negation function (see Section~\ref{sec:iihmsp10}).
37 We argued in~\cite{bcg11b:ip} that other functions can provide algorithms as secure as the dhCI one.
38 This work has then generalized the algorithm recalled in Section~\ref{sec:iihmsp10} and formalized all
39 its stages. Due to this formalization, it has then been possible to adress the proofs of the two
40 security properties for a large class of steganography approaches in~\cite{bcg11b:ip}.  
41
42
43
44
45
46 \subsection{Formalization of Steganographic Methods}
47 \label{sec:formalization}
48
49
50 The data hiding scheme presented in previous works does not constrain media to have 
51 a constant size. It is indeed sufficient to provide a function and a strategy 
52 that may be  parametrized with the size of the elements to modify. 
53 Parametrized strategies have already been introduced in a previous 
54 section, leading to the notion of \emph{strategy-adapter}. 
55 The \emph{mode} notion defined below achieves the same goal
56 but for the iteration function~\cite{bcg11b:ip} (until now, only the negation function
57 has been regarded).  
58
59 \begin{Def}[Mode]
60 \label{def:mode}
61 A map $f$, which associates to any $n \in \mathds{N}$ an application 
62 $f_n : \mathds{B}^n \rightarrow \mathds{B}^n$, is called a \emph{mode}.
63 \end{Def}
64
65 For instance, the \emph{negation mode} is defined by the map that
66 assigns to every integer $n \in \mathds{N}^*$ the function 
67 ${\neg}_n:\mathds{B}^n \to \mathds{B}^n, 
68 {\neg}_n(x_1, \hdots, x_n) \mapsto (\overline{x_1}, \hdots, \overline{x_n})$.
69
70
71 We now use the previously introduced \emph{signification function} 
72 to attach a weight to each term defining a digital media,
73 w.r.t. its position $t$, leading to the following notion of
74 a decomposition function~\cite{bcg11b:ip}.
75
76
77
78 \begin{Def}[Decomposition function]
79 Let $(u^k)^{k \in \mathds{N}}$ be a signification function, 
80 $\mathfrak{B}$ the set of finite binary sequences,
81 $\mathfrak{N}$ the set of finite integer sequences, 
82 $m$ and $M$ be two reals s.t. $m < M$.  
83 Any host $x$ may be decomposed into 
84 \[
85 (u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})
86 \in
87 \mathfrak{N} \times 
88 \mathfrak{N} \times 
89 \mathfrak{N} \times 
90 \mathfrak{B} \times 
91 \mathfrak{B} \times 
92 \mathfrak{B} 
93 \]
94 where
95 \begin{itemize}
96 \item $u_M$, $u_m$, and $u_p$ are coefficients defined in Definition  
97 \ref{def:msc,lsc};
98 \item $\phi_{M} = \left( x^{u^1_M}, x^{u^2_M}, \ldots,x^{u^{|u_M|}_M}\right)$;
99  \item $\phi_{m} = \left( x^{u^1_m}, x^{u^2_m}, \ldots,x^{u^{|u_m|}_m} \right)$;
100  \item $\phi_{p} =\left( x^{u^1_p}, x^{u^2_p}, \ldots,x^{u^{|u_p|}_p}\right) $.
101  \end{itemize}
102 The function that associates the decomposed host to any digital host is 
103 the \emph{decomposition function}. It is 
104 further referred as $\textit{dec}(u,m,M)$ since it is parametrized by 
105 $u$, $m$ and $M$. Notice that $u$ is a shortcut for $(u^k)^{k \in \mathds{N}}$.
106 \end{Def} 
107
108
109 \begin{Def}[Recomposition]
110 Let 
111 $(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p}) \in 
112 \mathfrak{N} \times 
113 \mathfrak{N} \times 
114 \mathfrak{N} \times 
115 \mathfrak{B} \times 
116 \mathfrak{B} \times 
117 \mathfrak{B} 
118 $ s.t.
119 \begin{itemize}
120 \item the sets of elements in $u_M$, elements in $u_m$, and 
121 elements in $u_p$ are a partition of $\llbracket 1, n\rrbracket$;
122 \item $|u_M| = |\varphi_M|$, $|u_m| = |\varphi_m|$, and $|u_p| = |\varphi_p|$.  
123 \end{itemize}
124 One may associate the vector 
125 \[
126 x = 
127 \sum_{i=1}^{|u_M|} \varphi^i_M . e_{{u^i_M}} +  
128 \sum_{i=1}^{|u_m|} \varphi^i_m .e_{{u^i_m}} +  
129 \sum_{i=1}^{|u_p|} \varphi^i_p. e_{{u^i_p}} 
130 \]
131 \noindent where 
132 $(e_i)_{i \in \mathds{N}}$ is the usual basis of the $\mathds{R}-$vectorial space $\left(\mathds{R}^\mathds{N}, +, .\right)$.
133 The function that associates $x$ to any 
134 $(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ following the above constraints 
135 is called the \emph{recomposition function}.
136 \end{Def}
137
138 The embedding consists in the replacement of the values of 
139 $\phi_{m}$ of $x$'s LSCs  by $y$. 
140 It then composes the two decomposition and
141 recomposition functions seen previously. More formally~\cite{bcg11b:ip}:
142
143
144 \begin{Def}[Embedding media]
145 Let $\textit{dec}(u,m,M)$ be a decomposition function,
146 $x$ be a host content,
147 $(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ be its image by $\textit{dec}(u,m,M)$, 
148 and $y$ be a digital media of size $|u_m|$.
149 The digital media $z$ resulting on the embedding of $y$ into $x$ is 
150 the image of $(u_M,u_m,u_p,\phi_{M},y,\phi_{p})$
151 by  the recomposition function $\textit{rec}$.
152 \end{Def}
153
154 We have thus been able in~\cite{bcg11b:ip} to reformulate the \emph{dhCI} information hiding scheme, as follows:
155
156 \begin{Def}[Data hiding dhCI]
157  \label{def:dhCI}
158 Let $\textit{dec}(u,m,M)$ be a decomposition function,
159 $f$ be a mode, 
160 $\mathcal{S}$ be a strategy adapter,
161 $x$ be an host content,\linebreak
162 $(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ 
163 be its image by $\textit{dec}(u,m,M)$,
164 $q$ be a positive natural number,  
165 and $y$ be a digital media of size $l=|u_m|$.
166
167
168 The \emph{dhCI dissimulation}  maps any
169 $(x,y)$  to the digital media $z$ resulting on the embedding of
170 $\hat{y}$ into $x$, s.t.
171
172 \begin{itemize}
173 \item We instantiate the mode $f$ with parameter $l=|u_m|$, leading to 
174   the function $f_{l}:\mathds{B}^{l} \rightarrow \mathds{B}^{l}$.
175 \item We instantiate the strategy adapter $\mathcal{S}$ 
176 with parameter $y$ (and some other ones eventually). 
177 This instantiation leads to the strategy $S_y \in \llbracket 1;l\rrbracket ^{\mathds{N}}$.
178
179 \item We iterate $G_{f_l}$ with initial configuration $(S_y,\phi_{m})$.
180 \item $\hat{y}$  is the $q$-th term.
181 \end{itemize}
182 \end{Def}
183
184
185 To summarize, iterations are realized on the LSCs of the
186 host content
187 (the mode gives the iterate function,  
188 the strategy-adapter gives its strategy), 
189 and the last computed configuration is re-injected into the host content, 
190 in place of the former LSCs.
191
192
193 \begin{figure}[h!]
194 \centering
195 \includegraphics[width=10cm]{IH/organigramme22.pdf}
196 \caption{The dhCI dissimulation scheme}
197 \label{fig:organigramme}
198 \end{figure}
199
200
201 We are then left to show how to formally check
202 whether a given digital media $z$ 
203 results from the dissimulation of $y$ into the digital media $x$~\cite{bcg11b:ip}. 
204
205 \begin{Def}[Marked content]
206 Let $\textit{dec}(u,m,M)$ be a decomposition function,
207 $f$ be a mode, 
208 $\mathcal{S}$ be a strategy adapter, 
209 $q$ be a positive natural number,  
210 and  
211 $y$ be a digital media, 
212 \linebreak $(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ be the 
213 image by $\textit{dec}(u,m,M)$  of  a digital media $x$. 
214
215 Then $z$ is \emph{marked} with $y$ if
216 the image by $\textit{dec}(u,m,M)$ of $z$ is 
217 $(u_M,u_m,u_p,\phi_{M},\hat{y},\phi_{p})$ where 
218 $\hat{y}$ is the right member of $G_{f_l}^q(S_y,\phi_{m})$.
219 \end{Def}
220
221
222 Various decision strategies are obviously  possible to determine whether a given
223 image $z$ is  marked or not, depending  on the eventuality
224 that the considered image may have  been attacked.
225 For example, a  similarity percentage between $x$
226 and  $z$ can  be  computed, and  the result  can  be compared  to a  given
227 threshold. Other  possibilities are the use of  ROC curves or
228 the definition of a null hypothesis problem.
229 The next section, always extracted from~\cite{bcg11b:ip}, 
230 recalls some security properties and shows how the 
231 \emph{dhCI dissimulation} algorithm verifies them.
232
233
234
235
236
237 \subsection{Security Analysis}\label{sec:security}
238
239
240 We have proven in~\cite{bcg11b:ip}, using the stochastic matrix theorem, that,
241
242 \begin{Th}\label{th:stego}
243 Let $\epsilon$ be positive,
244 $l$ be any size of LSCs, 
245 $X   \sim \mathcal{U}\left(\mathbb{B}^l\right)$,
246 $f_l$ be an image mode s.t. 
247 $\Gamma(f_l)$ is strongly connected and 
248 the Markov matrix associated to $f_l$ 
249 is doubly stochastic. 
250
251 In the instantiated \emph{dhCI dissimulation} algorithm 
252 with any uniformly distributed (u.d.) strategy-adapter 
253 which is independent from $X$,  
254 there exists some positive natural number $q$ s.t.
255 $|p(X^q)- p(X)| < \epsilon$. 
256 \end{Th}
257
258
259 \begin{Pre}   
260 See~\cite{bcg11b:ip}.
261  \end{Pre}
262
263 Since $p(Y| K)$ is $p(X^q)$ the method is then stego-secure.
264 We have then focused on topological security properties, and have deduced
265 from the characterisation recalled in Theorem~\ref{Th:Caracterisation des  IC chaotiques} that,
266
267 \begin{Prop}
268 Functions $f  : \mathds{B}^{n} \to
269 \mathds{B}^{n}$ such that the graph $\Gamma(f)$ is strongly connected lead to topologically secure 
270 \emph{dhCI dissimulation} algorithms.
271 \end{Prop}
272
273
274
275
276 %\subsection{Instantiation of  Steganographic Methods}
277 \label{instantiating}
278
279 Theorem~\ref{th:stego} relies on a u.d.   
280 strategy-adapter that is independent from the cover, and on an image mode 
281 $f_l$ whose iteration graph  $\Gamma(f_l)$ is strongly
282 connected and whose  Markov matrix 
283 is doubly stochastic. 
284 We have shown in~\cite{bcg11b:ip} that the CIIS strategy 
285 adapter~\cite{gfb10:ip} has the required 
286 properties and have mentioned that \cite{wcbg11:ip} has presented an iterative approach 
287 (which has been recalled in Section~\ref{sec:prac})
288 to 
289 generate image modes $f_l$ such that  
290 $\Gamma(f_l)$ is strongly connected.
291 Among these maps, it is obvious to check which verifies or not
292 the doubly stochastic constrain. 
293
294
295 % \subsection{Conclusion}\label{sec:concl}
296
297 % This work has presented a new class of information hiding
298 % algorithms which generalizes 
299 % algorithm~\cite{gfb10:ip} reduced to the negation mode.
300 % Its complete formalization has allowed to prove the stego-security 
301 % and topological security properties.
302 % As far as we know, this is the first time a whole class of algorithm 
303 % has been proven to have these two properties. 
304
305 % In future work, our intention is to study the robustness of this class of 
306 % dhCI dissimulation schemes.
307 % We are to find the optimized parameters (modes, stretegy adapters, signification coefficients, iterations numbers\ldots) giving 
308 % the strongest robustness 
309 % (depending on the chosen representation domain), theoretically and practically
310 % by realizing comprehensive simulations.
311 % Finally these algorithms will be compared to other existing ones, among other
312 % things by regarding whether these algorithms are chaotic or not.
313
314