ApplicationofRNG.tex

   1 \chapter{Applications in cryptology}
   2 \label{Application Example}
   3 \minitoc
   4
   5 \section{Application example of the use of the proposed PRNG}
   6 \label{An application example of the proposed PRNG}
   7
   8 Cryptographically secure PRNGs are fundamental tools to communicate through the Internet.
   9 % In this section is given an simple example of use of the Old CIs PRNG: an encryption is realized by using the bitwise exclusive or (XOR) between the given image and the above PRNG.
  10 Original and encrypted image are shown in Figures~\ref{Distribution of original image}(a) and
  11 ~\ref{Distribution of encrypted image}(a), whereas Figure~\ref{Distribution of original image}(a) and ~\ref{Distribution of encrypted image}(b) depict their histograms.
  12 Obviously the distribution of the encrypted image is very close to the uniform distribution, which improves the protection against statistical attacks.
  13
  14
  15
  16
  17
  18 \begin{figure*}
  19 \begin{minipage}[b]{.48\linewidth}
  20 \centering
  21 \centerline{\epsfig{figure=images/lena.eps,width=5cm}}
  22 \centerline{(a) Original image.}
  23 \end{minipage}
  24 \hfill
  25 \begin{minipage}[b]{0.48\linewidth}
  26 \centering
  27 \centerline{\epsfig{figure=images/Histogram_lena.eps,width=8cm}}
  28 \centerline{(b) Histogram.}
  29 \end{minipage}
  30 \caption{Distribution of original image}
  31 \label{Distribution of original image}
  32 \end{figure*}
  33
  34 \begin{figure*}
  35 \begin{minipage}[b]{.48\linewidth}
  36 \centering
  37 \centerline{\epsfig{figure=images/lena_crypt.eps,width=5cm}}
  38 \centerline{(a) Encrypted image.}
  39 \end{minipage}
  40 \hfill
  41 \begin{minipage}[b]{0.48\linewidth}
  42 \centering
  43 \centerline{\epsfig{figure=images/Histogram_lena_crypt.eps,width=8cm}}
  44 \centerline{(b) Histogram.}
  45 \end{minipage}
  46 \caption{Distribution of encrypted image}
  47 \label{Distribution of encrypted image}
  48 \end{figure*}
  49
  50 Figure~\ref{Correlation distributions of two horizontally adjacent pixels in the original image and the encrypted image}
  51 shows the correlation distribution of two horizontally adjacent pixels, both in the original and in
  52 the encrypted images.
  53 Correlation coefficients in the horizontal, vertical, and diagonal directions concerning these two images are presented in Table~\ref{Correlation coefficients of two adjacent pixels in the original image and the encrypted image}.
  54 Obviously, the correlation is important in the original image, whereas it is low and can be ignored in the encrypted image.
  55 These simple illustrations tend to prove that the use of Old CIs PRNG for cryptographic applications can be studied, to determine whether this chaotic generator is cryptographically secure or not.
  56 This study has been partially initiated in \cite{guyeuxTaiwan10,bgw10:ip}, in which our generators have been used as a component of a watermarking scheme.
  57 The robustness of this scheme has been evaluated, which has led to results as good as possible, thus reinforcing our opinion that these generators would probably be useful in cryptographic applications.
  58 The question of whether Old CIs PRNGs are cryptographically secure or not, will thus be raised in our next work.
  59
  60 \begin{figure*}
  61 \begin{minipage}[b]{.48\linewidth}
  62 \centering
  63 \centerline{\epsfig{figure=images/Correlation_distribution_of_the_original_image.eps,width=8cm}}
  64 \centerline{(a) Original image.}
  65 \end{minipage}
  66 \hfill
  67 \begin{minipage}[b]{0.48\linewidth}
  68 \centering
  69 \centerline{\epsfig{figure=images/Correlation_distribution_of_the_encrypted_image.eps,width=8cm}}
  70 \centerline{(b) Encrypted image.}
  71 \end{minipage}
  72 \caption{Correlation distributions of two horizontally adjacent pixels}
  73 \label{Correlation distributions of two horizontally adjacent pixels in the original image and the encrypted image}
  74 \end{figure*}
  75
  76 \begin{table*}
  77 \renewcommand{\arraystretch}{1.3}
  78 \caption{Correlation coefficients of two adjacent pixels in the original image and the encrypted image}
  79 \label{Correlation coefficients of two adjacent pixels in the original image and the encrypted image}
  80 \centering
  81 \begin{tabular}{ccc} \toprule
  82 \textbf{Direction} &\textbf{Original image} & \textbf{Encrypted image} \\ \midrule
  83 Horizontal &0.9245 &-0.0059 \\
  84 Vertical &0.9617 &-0.0048 \\
  85 Diagonal &0.8967 &-0.0052 \\ \bottomrule
  86 \end{tabular}
  87 \end{table*}
  88
  89
  90 \section{Introduction}
  91
  92 Information hiding is now an integral part of Internet technologies. In the field of social search engines, for example, contents like pictures or movies are tagged with descriptive labels by contributors, and search results are determined by these descriptions. These collaborative taggings, used for example in Flickr~\cite{Frick} and Delicious~\cite{Delicious} websites, contribute to the development of a Semantic Web, in which every Web page contains machine-readable metadata that describe its content. Information hiding technologies can be used for embedding these metadata. The advantage of its use is the possibility to realize  social search without websites and databases: descriptions are directly embedded into media, whatever their formats. Robustness is required in this situation, as descriptions should resist to modifications like resizing, compression, and format conversion.
  93
  94 The Internet security field is also concerned by watermarking technologies. Steganography and cryptography are supposed to be used by terrorists to communicate through the Internet. Furthermore, in the areas of defense or in industrial espionage, many information leaks using steganographic techniques have been discovered. Lastly, watermarking is often cited as a possible solution to digital rights managements issues, to counteract piracy of digital work in an Internet based entertainment world~\cite{Nakashima2003}.
  95
  96
  97 \section{Definition of a Chaos-Based Information Hiding Scheme}
  98 \label{sec:Algo}
  99
 100 Let us now introduce our information hiding scheme based on New CIs generator.
 101
 102
 103 \subsection{Most and least significant coefficients}
 104
 105 Let us define the notions of most and least significant coefficients of an image.
 106
 107 \begin{definition}
 108 \label{definitionMSC}
 109 For a given image, most significant coefficients (in short MSCs), are coefficients that allow the description of the relevant part of the image, \emph{i.e.}, its richest part (in terms of embedding information), through a sequence of bits.
 110 \end{definition}
 111
 112 For example, in a spatial description of a grayscale image, a definition of MSCs can be the sequence constituted by the first four bits of each pixel (see Figure~\ref{fig:MSCLC}). In a discrete cosine frequency domain description, each $8\times 8$ block of the carrier image is mapped onto a list of 64 coefficients. The energy of the image is mostly contained in a determined part of themselves, which can constitute a possible sequence of MSCs.
 113
 114 \begin{definition}
 115 \label{definitionLSC}
 116 By least significant coefficients (LSCs), we mean a translation of some insignificant parts of a medium in a sequence of bits (insignificant can be understand as: ``which can be altered without sensitive damages'').
 117 \end{definition}
 118
 119 These LSCs can be, for example, the last three bits of the gray level of each pixel (see Figure~\ref{fig:MSCLC}). Discrete cosine, Fourier, and wavelet transforms can be used also to generate LSCs and MSCs. Moreover, these definitions can be extended to other types of media.
 120
 121
 122
 123
 124 \begin{figure}[htb]
 125
 126 \begin{minipage}[b]{1.0\linewidth}
 127   \centering
 128  \centerline{\epsfig{figure=images/lena512.eps,width=4cm}}
 129   \centerline{(a) Lena.}
 130 \end{minipage}
 131
 132 \begin{minipage}[b]{.48\linewidth}
 133   \centering
 134  \centerline{\epsfig{figure=images/lena_msb_678.eps,width=4cm}}
 135   \centerline{(b) MSCs of Lena.}
 136 \end{minipage}
 137 \hfill
 138 \begin{minipage}[b]{0.48\linewidth}
 139   \centering
 140  \centerline{\epsfig{figure=images/lena_lsb_1234_facteur17.eps,width=4cm}}
 141   \centerline{(c) LSCs of Lena ($\times 17$).}
 142 \end{minipage}
 143 %
 144 \caption{Example of most and least significant coefficients of Lena.}
 145 \label{fig:MSCLC}
 146 %
 147 \end{figure}
 148
 149
 150 LSCs are used during the embedding stage. Indeed, some of the least significant coefficients of the carrier image will be chaotically chosen by using our PRNG. These bits will be either switched or replaced by the bits of the watermark. The MSCs are only useful in case of authentication; mixture and embedding stages depend on them. Hence, a coefficient should not be defined at the same time as a MSC and a LSC: the last can be altered while the first is needed to extract the watermark.
 151
 152 \subsection{Stages of the scheme}
 153
 154 Our New CIs generator-based information hiding scheme consists of two stages: (1) mixture of the watermark and (2) its embedding.
 155
 156 \subsubsection{Watermark mixture}
 157
 158 Firstly, for security reasons, the watermark can be mixed before its embedding into the image. A first way to achieve this stage is to apply the bitwise exclusive or (XOR) between the watermark and the New CIs generator. In this paper, we introduce a new mixture scheme based on chaotic iterations. Its chaotic strategy, which depends on our PRNG, will be highly sensitive to the MSCs, in the case of an authenticated watermarking.%For the detail of this stage see Sections \ref{Geometric} below.
 159
 160 \subsubsection{Watermark embedding}
 161
 162 Some LSCs will be switched, or substituted by the bits of the possibly mixed watermark. To choose the sequence of LSCs to be altered, a number of integers, less than or equal to the number $\mathsf{M}$ of LSCs corresponding to a chaotic sequence $U$, is generated from the chaotic strategy used in the mixture stage. Thus, the $U^{k}$-th least significant coefficient of the carrier image is either switched, or substituted by the $k^{th}$ bit of the possibly mixed watermark. In case of authentication, such a procedure leads to a choice of the LSCs which are highly dependent on the MSCs~\cite{guyeux10}.
 163
 164 On the one hand, when the switch is chosen, the watermarked image is obtained from the original image whose LSBs $L = \mathds{B}^{\mathsf{M}}$ are replaced by the result of some chaotic iterations. Here, the iterate function is the vectorial boolean negation,
 165 \begin{equation}
 166 f_0:(x_1,...,x_\mathsf{M}) \in \mathds{B}^\mathsf{M} \longmapsto (\overline{x_1},...,\overline{x_\mathsf{M}}) \in \mathds{B}^\mathsf{M},
 167 \end{equation}
 168 the initial state is $L$, and the strategy is equal to $U$. In this case, the whole embedding stage satisfies the topological chaos properties~\cite{guyeux10}, but the original medium is required to extract the watermark. On the other hand, when the selected LSCs are substituted by the watermark, its extraction can be done without the original cover (blind watermarking). In this case, the selection of LSBs still remains chaotic because of the use of the New CIs generator, but the whole process does not satisfy topological chaos~\cite{guyeux10}. The use of chaotic iterations is reduced to the mixture of the watermark. See the following sections for more detail.
 169
 170 \subsubsection{Extraction}
 171
 172 The chaotic strategy can be regenerated even in the case of an authenticated watermarking, because the MSCs have not changed during the embedding stage. Thus, the few altered LSCs can be found, the mixed watermark can be rebuilt, and the original watermark can be obtained. In case of a switch, the result of the previous chaotic iterations on the watermarked image should be the original cover. The probability of being watermarked decreases when the number of differences increase.
 173
 174 If the watermarked image is attacked, then the MSCs will change. Consequently, in case of authentication and due to the high sensitivity of our PRNG, the LSCs designed to receive the watermark will be completely different. Hence, the result of the recovery will have no similarity with the original watermark.
 175
 176 The chaos-based data hiding scheme is summed up in Figure~\ref{fig:organigramme}.
 177
 178 \begin{figure}[htb]
 179 \centerline{\epsfig{figure=images/organigramme22.eps,width=8.cm}}
 180 \caption{The chaos-based data hiding decision tree.}
 181 \label{fig:organigramme}
 182 \end{figure}
 183
 184
 185
 186 \section{Experimental protocol}
 187
 188
 189 In this subsection, a concrete example is given: a watermark is encrypted and embedded into a cover image using the scheme presented in the previous section and New CIs(XORshift, XORshift). The carrier image is the well-known Lena, which is a 256 grayscale image, and the watermark is the $64\times 64$ pixels binary image depicted in Figure~\ref{Original images}.
 190
 191
 192 \begin{figure}[!t]
 193 \centering
 194 \subfigure [The original image]{\includegraphics[scale=0.23]{images/lena512.eps}}
 195 \hfil
 196 \subfigure[The watermark]{\includegraphics[scale=0.4]{images/invader1.eps}%
 197 }
 198 \caption{Original images}
 199 \label{Original images}
 200 \end{figure}
 201
 202
 203 \begin{figure}[!t]
 204 \centering
 205 \subfigure [Differences with the original]{\includegraphics[scale=0.42]{images/lenaDiff2.eps}%
 206 }
 207 \hfil
 208 \subfigure [Encrypted watermark]{\includegraphics[scale=0.4]{images/invader_chiffre1.eps}%
 209 }
 210 \caption{Encrypted watermark and differences}
 211 \label{Encrypted watermark and differences}
 212 \end{figure}
 213
 214 The watermark is encrypted by using chaotic iterations: the initial state $x^{0}$ is the watermark, considered as a boolean vector, the iteration function is the vectorial logical negation, and the chaotic strategy $(S^{k})_{k\in \mathds{N}}$ is defined with New CIs(XORshift, XORshift), where initial parameters constitute the secret key and $N=64$. Thus, the encrypted watermark is the last boolean vector generated by these chaotic iterations. An example of such an encryption is given in Figure~\ref{Encrypted watermark and differences}.
 215
 216
 217 Let $L$ be the $256^3$ booleans vector constituted by the three last bits of each pixel of Lena and $U^k$ defined by the sequence:
 218 \begin{equation}
 219 \left\{
 220 \begin{array}{lll}
 221 U^{0} & = & S^{0} \\
 222 U^{n+1} & = & S^{n+1}+2\times U^{n}+n ~ [mod ~ 256^3]%
 223 \end{array}%
 224 \right.
 225 \end{equation}
 226 The watermarked Lena $I_w$ is obtained from the original Lena, whose three last bits are replaced by the result of $64^2$ chaotic iterations with initial state $L$ and strategy $U$ (see Figure~\ref{Encrypted watermark and differences}).
 227
 228 The extraction of the watermark can be obtained in the same way. Remark that the map $\theta \mapsto 2\theta $ of the torus, which is the famous dyadic transformation (a well-known example of topological chaos~\cite{Dev89}), has been chosen to make $(U^{k})_{k \leqslant 64^2}$ highly sensitive to the strategy. As a consequence, $(U^{k})_{k \leqslant 64^2}$ is highly sensitive to the alteration of the image: any significant modification of the watermarked image will lead to a completely different extracted watermark, thus giving a way to authenticate media through the Internet.
 229
 230
 231 Let us now evaluate the robustness of the proposed method.
 232
 233
 234 \section{Robustness evaluation}
 235
 236 In what follows, the embedding domain is the spatial domain, New CIs(XORshift,XORshift) with parameters $....$ has been used to encrypt the watermark, MSCs are the four first bits of each pixel (useful only in case of authentication), and LSCs are the three next bits.
 237
 238 To prove the efficiency and the robustness of the proposed algorithm, some
 239 attacks are applied to our chaotic watermarked image. For each attack, a
 240 similarity percentage with the watermark is computed, this percentage is the
 241 number of equal bits between the original and the extracted watermark, shown
 242 as a percentage. Let us notice that a result less than or equal to $50\%$
 243 implies that the image has probably not been watermarked.
 244
 245 \subsubsection{Zeroing attack}
 246
 247 In this kind of attack, a watermarked image is zeroed, such as in Figure \ref{fig:LenaAttack}(a). In this case, the results in Table 1 have been obtained.
 248
 249 \begin{figure}[htb]
 250 \begin{minipage}[b]{.48\linewidth}
 251   \centering
 252  \centerline{\epsfig{figure=images/lennaDecoupe100px,width=3.3cm}}
 253   \centerline{(a) Cropping attack}
 254 \end{minipage}
 255 \hfill
 256 \begin{minipage}[b]{0.48\linewidth}
 257   \centering
 258  \centerline{\epsfig{figure=images/lennaTourne25d.eps,width=3.3cm}}
 259   \centerline{(b) Rotation attack}
 260 \end{minipage}
 261 \caption{Watermarked Lena after attacks.}
 262 \label{fig:LenaAttack}
 263 \end{figure}
 264
 265
 266
 267
 268 \begin{center}
 269 \begin{footnotesize}
 270 \begin{tabular}{|c|c||c|c|}
 271 \hline
 272 \multicolumn{2}{|c||}{UNAUTHENTICATION}  & \multicolumn{2}{c|}{AUTHENTICATION}\\
 273 \hline
 274 Size (pixels) & Similarity & Size (pixels) & Similarity \\
 275  \hline
 276 10 & 99.08\% & 10 & 91.77\% \\
 277 50 & 97.31\% & 50 & 55.43\% \\
 278 100 & 92.43\% & 100 & 51.52\% \\
 279 200 & 70.75\% & 200 & 50.60\% \\
 280 \hline
 281 \end{tabular}
 282 \end{footnotesize}\\
 283 \vspace{0.5cm}
 284 \textbf{Table. 1}. ~Cropping attacks
 285 \end{center}
 286
 287
 288 In Figure \ref{fig:Dechiffrement_invader}, the decrypted watermarks are shown after a crop of 50 pixels and after a crop of 10 pixels, in the authentication case.
 289
 290 \begin{figure}[htb]
 291 \begin{minipage}[b]{1.0\linewidth}
 292   \centering
 293  \centerline{\epsfig{figure=images/invaderDechiffreDecoupe100px.eps,width=2cm}}
 294   \centerline{(a) Unauthentication ($50\times 50$).}
 295 \end{minipage}
 296 %
 297 \begin{minipage}[b]{.48\linewidth}
 298   \centering
 299  \centerline{\epsfig{figure=images/invaderDechiffreDecoupeAuth100px.eps,width=2cm}}
 300   \centerline{(b) Authentication  ($50\times 50$).}
 301 \end{minipage}
 302 \hfill
 303 \begin{minipage}[b]{0.48\linewidth}
 304   \centering
 305  \centerline{\epsfig{figure=images/invaderDechiffreDecoupeAuth50px.eps,width=2cm}}
 306   \centerline{(c) Authentication  ($10\times 10$).}
 307 \end{minipage}
 308 %
 309 \caption{Extracted watermark after a cropping attack.}
 310 \label{fig:Dechiffrement_invader}
 311 %
 312 \end{figure}
 313
 314
 315 By analyzing the similarity percentage between the original and the
 316 extracted watermark, we can conclude that in case of unauthentication, the
 317 watermark still remains after a zeroing attack: the desired robustness is
 318 reached. It can be noticed that zeroing sizes and percentages are rather
 319 proportional.
 320
 321 In case of authentication, even a small change of the carrier image (a crop
 322 by $10\times 10$ pixels) leads to a really different extracted watermark.
 323 In this case, any attempt to alter the carrier image will be signaled, the
 324 image is well authenticated.
 325
 326 \subsubsection{Rotation attack}
 327
 328 Let $r_{\theta }$ be the rotation of angle $\theta $ around the center $%
 329 (128, 128)$ of the carrier image. So, the transformation $r_{-\theta }\circ
 330 r_{\theta }$ is applied to the watermarked image, which is altered as in Figure \ref{fig:LenaAttack}. The results in Table 2 have been obtained.
 331
 332
 333 \begin{center}
 334 \begin{footnotesize}
 335 \begin{tabular}{|c|c||c|c|}
 336 \hline
 337 \multicolumn{2}{|c||}{UNAUTHENTICATION}  & \multicolumn{2}{c|}{AUTHENTICATION}\\
 338 \hline
 339 Angle (degree) & Similarity & Angle (degree) & Similarity \\
 340  \hline
 341 2 & 96.44\% & 2 & 73.40\% \\
 342 5 & 93.32\% & 5 & 60.56\% \\
 343 10 & 90.68\% & 10 & 52.11\% \\
 344 25 & 78.13\% & 25 & 51.97\% \\
 345 \hline
 346 \end{tabular}
 347 \end{footnotesize}\\
 348 \vspace{0.5cm}
 349 \textbf{Table. 2}. ~Rotation attacks
 350
 351 \end{center}
 352
 353
 354
 355
 356 The same conclusion as above can be declaimed: this watermarking method
 357 satisfies the desired properties.
 358
 359 \subsubsection{JPEG compression}
 360
 361 A JPEG compression is applied to the watermarked image, depending on a
 362 compression level. Let us notice that this attack leads to a change of
 363 the representation domain (from spatial to DCT domain). In this case, the results in Table 3 have been obtained.
 364
 365 \begin{center}
 366 \begin{footnotesize}
 367 \begin{tabular}{|c|c||c|c|}
 368 \hline
 369 \multicolumn{2}{|c||}{UNAUTHENTICATION}  & \multicolumn{2}{c|}{AUTHENTICATION}\\
 370 \hline
 371 Compression & Similarity & Compression & Similarity \\
 372  \hline
 373 2 & 85.76\% & 2 & 56.42\% \\
 374 5 & 67.62\% & 5 & 52.12\% \\
 375 10 & 62.43\% & 10 & 48.22\% \\
 376 20 & 54.74\% & 20 & 49.07\% \\
 377 \hline
 378 \end{tabular}
 379 \end{footnotesize}\\
 380 \vspace{0.5cm}
 381 \textbf{Table. 3}. ~JPEG compression attacks
 382 \end{center}
 383
 384 A very good authentication through JPEG attack is obtained. As for the
 385 unauthentication case, the watermark still remains after a compression level
 386 equal to 10. This is a good result if we take into account the fact that we
 387 use spatial embedding.
 388
 389 \subsubsection{Gaussian noise}
 390
 391 Watermarked image can be also attacked by the addition of a Gaussian noise, depending on a standard deviation. In this case, the results in Table 4 have been obtained.
 392
 393
 394 \begin{center}
 395 \begin{footnotesize}
 396 \begin{tabular}{|c|c||c|c|}
 397 \hline
 398 \multicolumn{2}{|c||}{UNAUTHENTICATION}  & \multicolumn{2}{c|}{AUTHENTICATION}\\
 399 \hline
 400 Standard dev. & Similarity & Standard dev. & Similarity \\
 401  \hline
 402 1 & 81.14\% & 1 & 55.57\% \\
 403 2 & 75.01\% & 2 & 52.63\% \\
 404 3 & 67.64\% & 3 & 52.68\% \\
 405 5 & 57.48\% & 5 & 51.34\% \\
 406 \hline
 407 \end{tabular}
 408 \end{footnotesize}\\
 409 \vspace{0.5cm}
 410 \textbf{Table. 4}. ~Gaussian noise attacks
 411 \end{center}
 412
 413
 414 Once again we remark that good results are obtained, especially if we keep in
 415 mind that a spatial representation domain has been chosen.