[hdrcouchot.git] / main.tex

%% Use the standard UP-methodology class
%% with French language.
%%
%% You may specify the option 'twoside' or 'oneside' for
%% the document.
%%
%% See the documentation tex-upmethodology on
%% http://www.arakhne.org/tex-upmethodology/
%% for details about the macros that are provided by the class and
%% to obtain the list of the packages that are already included. 

\documentclass[french]{spimufchdr}
\usepackage{dsfont}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{tikz}
\usepackage{pgfplots}
\usepgfplotslibrary{groupplots}

%\usepackage[font=footnotesize]{subfig}
\usepackage[utf8]{inputenc}
\usepackage{thmtools, thm-restate}
\usepackage{multirow}
\usepackage{algorithm2e}
\usepackage{mathtools}

%\declaretheorem{theorem}

%%--------------------
%% Search path for pictures
\graphicspath{{images/},{path2/}}

%%--------------------
%% Definition of the bibliography entries
\declarebiblio{J}{Journaux internationaux avec comités de lecture}{mabiblio}

%%--------------------
%% Title of the document
\declarehdr{Modèles discrets pour la sécurité informatique: des méthodes itératives à l'analyse vectorielle}{XX Mois XXXX}
 
%%--------------------
%% Set the author of the HDR
\addauthor[couchot@femto-st.fr]{Jean-François}{Couchot}

 
%%--------------------
%% Add a member of the jury
%% \addjury{Firstname}{Lastname}{Role in the jury}{Position}
\addjury{First}{Name}{Rapporteur}{Professeur à l'Université de XXX}
\addjury{First}{Name}{Examinateur}{Professeur à l'Université de XXX}
 
%%--------------------
%% Change the style of the text in the list of the members of the jury.
%% \Set{jurystyle}{ style of the text}
%\Set{jurystyle}{\small}

%%--------------------
%% Set the University where HDR was made
\hdrpreparedin{Université Bourgone Franche-Comté}

 
%%--------------------
%% Set the English abstract
\hdrabstract[english]{
Thanks to its  conciseness, a discrete model may allow  to reason with
problems  that may  not be  handled  without such  a formalism.   Discrete
dynamical systems  (DDS) belong to this  computer science area.   In this
authorization  to direct  researches  manuscript,  we firstly  present
contributions on  convergence, convergence proof, and  a new iteration
scheme  of  such  systems.   We further  present  contributions  about
functions whose iterations  can be chaotic. We  particularly present a
set of methods leading to such  functions. One of them built over Gray
codes allows to obtain a Markov chain that is doubly stochastic.  This
last method permits to produce  a large number of Pseudorandom Number
Generators  (PRNG).   Theoretical  and  practical   contributions  are
presented   in  this   field.   Information   hiding  area   has  been
strengthened  in  this  manuscript  and some  contributions  are  thus
presented.  Instances  of  such  algorithms  are  given  according  to
functions  that can  achieve  a large  robustness.   Finally, we  have
proposed an new method to  build distortion functions
that can be embedded  in information hiding schemes  
with analysis gradient but  expressed in a
discrete way.}
 
%%--------------------
%% Set the English keywords. They only appear if
%% there is an English abstract
\hdrkeywords[english]{discrete dynamical systems, pseudorandom number 
generators, information hiding.}
 
%%--------------------     %%     Set      the     French     abstract
\hdrabstract[french]{  

Grâce à  leur concision, les modèle  discrets permettent d'appréhender
des  problèmes informatiques  qui ne  seraient parfois  pas traitables
autrement.  Les  systèmes dynamiques  discrets s'intègrent  dans cette
thématique.  Dans cette habilitation, nous montrerons tout d'abord des
contributions concernant  la convergence, la preuve  de convergence et
un  nouveau  mode  opératoire  de tels  systèmes.   Nous  présenterons
ensuite  un   ensemble  d'avancées  autour  des   fonctions  dont  les
itérations  peuvent  être   chaotiques.   Particulièrement,  plusieurs
méthodes permettant  d'obtenir de  telles fonctions  seront proposées,
dont une basée  sur les codes de Gray, permettant  d'avoir en plus une
chaîne de Markov doublement stochastique.  Cette dernière méthode nous
permettra notamment  d'engendrer une grande famille  de générateurs de
nombres  pseudo-aléatoires (PRNG).   Des  contributions théoriques  et
pratiques autour de ces PRNGs seront mises en avant.  La thématique de
masquage d'information  (déjà présente dans l'équipe)  a été renforcée
et des  avancées significatives sur  ce sujet seront  présentées.  Des
instances de  ces algorithmes  seront formalisées en  sélectionnant les
fonctions à  itérer pour garantir une  robustesse élevée.  Finalement,
nous  montrerons  qu'on  peut  construire de  nouvelles  fonctions  de
distorsion utilisables en masquage  d'information à l'aide de méthodes
d'analyse par gradient mais discret cette fois encore.

 }
 
%%--------------------
%% Set the French keywords. They only appear if
%% there is an French abstract
\hdrkeywords[french]{systèmes dynamiques discrets, générateurs de nombres
pseudo-aléatoires, masquage d'information.}

%%--------------------
%% Change the layout and the style of the text of the "primary" abstract.
%% If your document is written in French, the primary abstract is in French,
%% otherwise it is in English.
\Set{primaryabstractstyle}{\small}

%%--------------------
%% Change the layout and the style of the text of the "secondary" abstract.
%% If your document is written in French, the secondary abstract is in English,
%% otherwise it is in French.
%\Set{secondaryabstractstyle}{\tiny}

%%--------------------
%% Change the layout and the style of the text of the "primary" keywords.
%% If your document is written in French, the primary keywords are in French,
%% otherwise they are in English.
%\Set{primarykeywordstyle}{\tiny}

%%--------------------
%% Change the layout and the style of the text of the "secondary" keywords.
%% If your document is written in French, the secondary keywords are in English,
%% otherwise they are in French.
%\Set{secondarykeywordstyle}{\tiny}

%%--------------------
%% Change the speciality of the PhD thesis
\Set{speciality}{Informatique}
 
%%--------------------
%% Change the institution
%\Set{universityname}{Universit\'e de Technologie de Belfort-Montb\'eliard}

%%--------------------
%% Add the logo of a partner or a sponsor
%\addpartner{partner_logo}
\newcommand{\JFC}[1]{\begin{color}{green}\textit{#1}\end{color}}
\newcommand{\vectornorm}[1]{\ensuremath{\left|\left|#1\right|\right|_2}}
\newcommand{\ie}{\textit{i.e.}}
\newcommand{\Nats}[0]{\ensuremath{\mathbb{N}}}
\newcommand{\Reels}[0]{\ensuremath{\mathbb{R}}}
\newcommand{\Zed}[0]{\ensuremath{\mathbb{Z}}}
\newcommand{\Bool}[0]{\ensuremath{\mathds{B}}}
\newcommand{\rel}[0]{\ensuremath{{\mathcal{R}}}}
\newcommand{\Gall}[0]{\ensuremath{\mathcal{G}}}
\newcommand{\Sec}[1]{Section\,\ref{#1}}
\newcommand{\Fig}[1]{{\sc Figure}~\ref{#1}}
\newcommand{\Alg}[1]{Algorithme~\ref{#1}}
\newcommand{\Tab}[1]{Tableau~\ref{#1}}
\newcommand{\Equ}[1]{(\ref{#1})}
\newcommand{\deriv}{\mathrm{d}}
\newcommand{\class}[1]{\ensuremath{\langle #1\rangle}}
\newcommand{\dom}[0]{\ensuremath{\textit{dom}}}
 \newcommand{\eqNode}[0]{\ensuremath{{\mathcal{R}}}}


\newcommand {\tv}[1] {\lVert #1 \rVert_{\rm TV}}
\def \top {1.8}
\def \topt {2.3}
\def \P {\mathbb{P}}
\def \ov {\overline}
\def \ts {\tau_{\rm stop}}
\def\rl{{^{.}}}

\DeclarePairedDelimiter\abs{\lvert}{\rvert}%
\DeclarePairedDelimiter\norm{\lVert}{\rVert}%

% Swap the definition of \abs* and \norm*, so that \abs
% and \norm resizes the size of the brackets, and the 
% starred version does not.
\makeatletter
\let\oldabs\abs
\def\abs{\@ifstar{\oldabs}{\oldabs*}}
%
\let\oldnorm\norm
\def\norm{\@ifstar{\oldnorm}{\oldnorm*}}
\makeatother

\newtheorem{theorem}{Théorème}
\newtheorem{lemma}{Lemme}
\newtheorem{corollary}{Corollaire}
\newtheorem*{xpl}{Exemple}

\newtheorem{Def}{Définition}

\begin{document}

 

\tableofcontents

\chapter*{Introduction}

\input{intro}

\mainmatter

\part{Réseaux discrets}

\chapter{Iterations discrètes de réseaux booléens}\label{chap:sdd}

Ce chapitre formalise tout d'abord ce qu'est 
un réseau booléen (section~\ref{sec:sdd:formalisation}. On y revoit 
les différents modes opératoires, leur représentation à l'aide de 
graphes et les résultats connus de convergence).
Ce chapitre montre ensuite à la section~\ref{sec:sdd:mixage}
comment combiner ces modes pour converger aussi 
souvent, mais plus rapidement vers un point fixe. Les deux 
dernières sections ont fait l'objet du rapport~\cite{BCVC10:ir}.

\section{Formalisation}\label{sec:sdd:formalisation}
\input{sdd}

\section{Combinaisons synchrones et asynchrones}\label{sec:sdd:mixage}
\input{mixage}

\section{Conclusion}

Introduire de l'asynchronisme peut permettre de réduire le temps 
d'exécution global, mais peut aussi introduire de la divergence. 
Dans ce chapitre, après avoir introduit les bases sur les réseaux booléens,
nous avons exposé comment construire un mode combinant les
avantages du synchronisme en termes de convergence avec les avantages 
de l'asynchronisme en termes de vitesse de convergence.




\chapter{Preuve automatique de  convergence}\label{chap:promela}
\input{modelchecking}






\part{Des systèmes dynamiques discrets 
au chaos} 

\chapter[Caractérisation des systèmes 
  discrets chaotiques]{Caractérisation des systèmes 
  discrets chaotiques pour les schémas unaires et généralisés}\label{chap:carachaos}

La suite de ce document se focalise sur des systèmes dynamiques discrets qui ne 
convergent pas. Parmi ceux-ci se trouvent ceux qui sont \og chaotiques\fg{}.
La première section  de ce chapitre rappelle ce que sont les systèmes 
dynamiques chaotiques et leurs caractéristiques.
La section~\ref{sec:TIPE12}, qui est une reformulation de~\cite{guyeuxphd},
se focalise sur le schéma unaire. Elle est rappelée pour avoir un document se 
suffisant à lui-même.
La section~\ref{sec:chaos:TSI} étend ceci au mode généralisé. Pour chacun de ces modes, 
une métrique est définie. Finalement, la section~\ref{sec:11FCT}
exhibe des conditions suffisantes permettant d'engendrer 
des fonctions chaotiques selon le mode unaire.
Les sections~\ref{sec:TIPE12} et~\ref{sec:11FCT} ont été publiées 
dans~\cite{bcg11:ij,bcgr11:ip}.


\section{Systèmes dynamiques chaotiques selon Devaney}
\label{subsec:Devaney}
\input{devaney}

\section{Schéma unaire}\label{sec:TIPE12}
\input{12TIPE}

\section{Schéma généralisé}\label{sec:chaos:TSI}
\input{15TSI}


\section{Générer des fonctions chaotiques}\label{sec:11FCT}
\input{11FCT} 

\section{Conclusion}
Ce chapitre a montré que les itérations unaires sont chaotiques si
et seulement si le graphe $\textsc{giu}(f)$ est fortement connexe et 
que les itérations généralisées sont chaotiques si
et seulement si le graphe $\textsc{gig}(f)$ est aussi fortement connexe.
On dispose ainsi a priori d'une collection infinie de fonctions chaotiques.
Le chapitre suivant s'intéresse à essayer de prédire le comportement 
de telles fonctions. 


\chapter{Prédiction des systèmes chaotiques}\label{chp:ANN}
\input{chaosANN}




\part{Applications à la génération de nombres 
pseudo-aléatoires}




\chapter{Caractérisation des générateurs chaotiques}\label{chap:PRNG:chao}
\input{15RairoGen}

\chapter{Les générateurs issus des codes de Gray}\label{chap:PRNG:gray}
\input{14Secrypt}



\part{Application au masquage d'information}


\chapter{Des embarquements préservant le chaos}\label {chap:watermarking} 
\input{oxford}

\chapter{Une démarche de  marquage de PDF}\label{chap:watermarking:pdf}
\input{ahmad}

\chapter[STABYLO] {Une démarche plus classique de dissimulation: STABYLO}\label{chap:stabylo}
 \input{stabylo}

\chapter[Stéganographie par dérivées secondes]{Schémas de stéganographie: les dérivées secondes}\label{chap:th:yousra}
 \input{stegoyousra}



\part*{Conclusion et Perspectives}

\input{conclusion}









\appendix

\chapter{Preuves sur les réseaux discrets}

\section{Convergence du mode mixte}\label{anx:mix}
\input{annexePreuveMixage}


\section{Correction et complétude de la 
  vérification de convergence par SPIN}\label{anx:promela}
\input{annexePromelaProof}



\chapter{Preuves sur les systèmes chaotiques}


%\section{Continuité de $G_f$ dans $(\mathcal{X}_u,d)$}\label{anx:cont}
%\input{annexecontinuite.tex}


%\section{Caractérisation des fonctions $f$ rendant chaotique $G_{f_u}$ dans $(\mathcal{X}_u,d)$}\label{anx:chaos:unaire}
%\input{caracunaire.tex}

\section{Preuve que $d$ est une distance sur $\mathcal{X}_g$}\label{anx:distance:generalise}
\input{preuveDistanceGeneralisee}


\section{Caractérisation des fonctions $f$ rendant chaotique $G_{f_g}$ dans $(\mathcal{X}_g,d)$}\label{anx:chaos:generalise}
\input{caracgeneralise.tex}


\section{Conditions suffisantes pour un $\textsc{giu}(f)$ fortement connexe \label{anx:sccg}}
\input{annexesccg}


\chapter{Preuves sur les générateurs de nombres pseudo-aléatoires}\label{anx:generateur}
\input{annexePreuveDistribution}

\section{Codes de Gray équilibrés par induction}
\input{annexePreuveGrayEquilibre}

\section{Majoration du temps de mixage}
\input{annexePreuveStopping}

\chapter{Preuves sur le marquage de média}\label{anx:marquage}
\section{Le marquage est $\epsilon$-stégo-sécure}
\input{annexePreuveMarquagedhci}

\section{Le mode $f_l$ est doublement stochastique}\label{anx:marquage:dblesto}
\input{annexePreuveMarquagefldblement}

\section{Le marquage est correct et complet}\label{anx:preuve:marquage:correctioncompletue}
\input{annexePreuveMarquageCorrectioncompletude}

% \section{Complexités d'algorithmes de stéganographie}
% \label{anx:preuve:cplxt}
% \input{annexePreuvesComplexiteStego}



\bibliographystyle{alpha}
\bibliography{abbrev,biblioand}
\listoffigures
\listoftables

 
\end{document}