Floriane Collin

Vincent Laurain

Gérard Bloch

Jean-Luc Noisette

Arturo Yusuf

Valentin

Paul

Asma, Dawid, Quentin Carlo Sabra

pleines de nouvelles connaissances

détaillé de la thèse

La synchronisation a été un sujet important en automatique depuis des années. Rigoureusement parlant, le terme synchronisation désigne des comportements similaires ou corrélés de deux ou plusieurs entités qui sont connectées par des réseaux virtuel ou physique. Au cours de ces derniers siècles, des scientifiques ont tenté d'expliquer l'existence de l'ordre à travers le concept de synchronisation. C Huygens est considéré comme un des pionniers à s'intéresser à ce sujet en 1665. On peut citer un nombre remarquable de phénomènes synchronisés que l'on peut observer que ce soit dans la nature, la biologie, les neurosciences, la physiologie et plus récemment dans les réseaux sociaux.

. De tels chiffreurs peuvent être conçus à partir de générateurs obtenus en utilisant des systèmes dynamiques. Ces systèmes dynamiques, dans le contexte de la cryptographie, opèrent sur des corps finis tout en générant des séquences qui sont assez complexes pour brouiller des informations qui doivent être transmises dans le secret. Ces séquences générées doivent toutefois être auto-synchronisantes afin de garantir correctement le déchiffrement de l'information transmise.

Dans cette thèse on s'intéresse à l'utilisation des SSSCs en cryptographie d'un point de vue de la théorie du contrôle en automatique. Le principal résultat réside dans le concept de la platitude qui combiné à des notions utilisées en théorie du graphe offre une approche constructive et systématique de classes plus générales de SSSCs.

R ÉSUM É D ÉTAILL É DE LA TH ÈSE

Cette fonction n'est rien d'autre que la transformée de Fourier des transformées de Fourier des fonctions ϕ et g. Elle peut donc être calculée aisément à l'aide d'un algorithme de calcul de transformée de Fourier rapide ou Fast Fourier Transform algorithm en anglais (voir [22]). Ce qui offre une complexité de calcul quasi linéaire en la taille n des mots binaires traités, soit

. Cependant, les expériences réalisées sur l'algorithme SSSC basé sur un système LPV plat montre qu'il est difficile de retrouver les sous clés qui sont utilisées en entrée des boîtes S de l'algorithme. Cette difficulté étant liée à la façon dont sont effectuées les opérations qui font intervenir les boîtes S.

Je souhaiterais avant tout, adresser mes sincères remerciements et gratitude à mes deux directeurs de thèse Gilles MILLERIOUX et Philippe GUILLOT. Ils m'ont donné une grande opportunité de réaliser cette thèse dans le cadre d'un projet ANR qui a regroupé plusieurs partenaires. Je leur suis très reconnaissant de la confiance qu'ils m'ont accordée sur un tel projet. Leurs idées, leur conseils et parfois leurs exigences m'ont permis d'accomplir avec succès cette thèse. Ils m'ont transmis les idées clés qui sont à l'origine de l'élaboration fructueuse des travaux de la thèse. Je remercie également le directeur du laboratoire CRAN, M. Didier WOLF par qui mon acceptation en tant que doctorant au sein du laboratoire a été possible.

Je tiens également à remercier les membres du jury de thèse qui ont accepté d'examiner mes travaux. Un grand merci à mes deux rapporteurs de thèse pour le grand intérêt qu'ils ont porté à mes travaux ainsi que l'attention particulière qu'ils ont porté à la lecture de mon manuscrit. Leur conseil et correction me sont d'une grande utilité pour la suite de ma carrière.

Je ne saurai oublier tous les autres membres du laboratoire, et plus précisément du département CID, Hugues GARNIER avec qui j'ai découvert les vraies activités sportives.

Le Chapître 1 de la thèse aborde donc les notions et concepts de la théorie du contrôle qui sont utiles pour la construction des SSSCs. Il illustre l'intérêt potentiel des systèmes dynamiques LPV plats pour répondre à des problématiques en cryptographie. En effet ces systèmes LPV sont des systèmes linéaires dont la représentation d'état dépend d'un vecteur de paramètres qui varient dans le temps. Ils sont utilisés depuis bien des années en contrôle [START_REF] Apkarian | A convex characterization of gainscheduled H ∞ Controllers[END_REF][START_REF] Farhood | Control of nonstationary LPV systems[END_REF][START_REF] Lee | Output feedback model predictive control for LPV systems using parameter-dependent Lyapunov-function[END_REF][START_REF] Leith | Survey of gain scheduling analysis and design[END_REF][START_REF] Packard | Theory and application of linear parameter-varying control techniques[END_REF][START_REF] Scherer | LPV control and full block multipliers[END_REF] et dans le domaine de l'observation ou filtrage [START_REF] Bara | Parameter-dependent state observer design for affine LPV systems[END_REF][START_REF] Heemels | Observer-based control of discretetime LPV systems with uncertain parameters[END_REF][START_REF] Sato | Filter design for LPV systems using quadratically parameter-dependent lyapunov functions[END_REF][START_REF] Toth | Discrete time LPV I/O and state-space representations, differences of behavior and pitfalls of interpolation[END_REF]. Les modèles LPV peuvent être par exemple utilisés pour construire des contrôleurs programmables utilisés par exemple dans le contrôle de l'espace aérien [START_REF] Rugh | Research on gain scheduling[END_REF] ou le contrôle de véhicules [START_REF] Sename | Robust Control and Linear Parameter Varying Approaches, Application to Vehicle Dynamics[END_REF]. En outres, ces modèles LPV peuvent représenter des systèmes non linéaires sous certaines conditions bien définies. Ceci a i R ÉSUM É D ÉTAILL É DE LA TH ÈSE fait l'objet d'études dans [START_REF] Bruzelius | Linear Parameter-Varying Systems: an approach to gain scheduling[END_REF] ou dans [START_REF] Millerioux | Considering the attractor structure of chaotic maps for observer-based synchronization problems[END_REF].

Un système linéaire à paramètre variant à une seule entrée et une seule sortie ou Single Input Single Output (SISO) en anglais noté Σ ρ et défini sur un corps fini F est décrit par la représentation d'espace d'état suivant:

Σ ρ : x k+1 = A ρ(k) x k + B ρ(k) u k y k = C ρ(k) x k + D ρ(k) u k (1)
où k ∈ N correspond au temps discret, x k ∈ F n correspond au vecteur d'état, u k ∈ F correspond à l'entrée, y k ∈ F correspond à la sortie. Les matrices A ∈ F, B ∈ F n×1 , C ∈ F 1×n et D ∈ F 1×1 correspondent respectivement à la matrice dynamique, la matrice d'entrée, la matrice de sortie et la matrice de transfert direct. Comme on peut donc le voir dans l'Equation (1) caractéristique d'un système LPV, le vecteur d'état dépend linéairement de l'entrée et de la sortie du système. Cependant, les matrices A, B, C et D dépendent d'un vecteur de paramètres ρ(k) = ρ 1 (k), ρ 2 (k), ..., ρ Lρ (k) ∈ F Lρ qui confèrent une dynamique non linéaire au système. Ici L ρ désigne le nombre total de coefficients (éventuellement variables) non nuls des matrices. En effet les paramètres variants ρ i (k) sont définis comme des fonctions non linéaires ϕ i en la sortie y k :

ρ i (k) = ϕ i (y k , y k-1 , • • • ).
Une fois la définition des systèmes dynamiques LPV établie, on va établir ensuite une correspondance avec les SSSCs à travers la notion de platitude que l'on définit ci-après. On définit avant tout, pour tout entier positif k 0 , une réalisation que l'on notera par ρ, toute séquence {ρ(k 0 ), ρ(k 0 + 1), . . .} de paramètres à temps variant. La définition d'un système LPV est donc donnée d'un point de vue générique i.e pour presque toute réalisation ρ. Définition 1 On dit que le système [START_REF]FIPS publication 197 -advanced encryption standard[END_REF] est génériquement plat, si pour presque toute réalisation ρ, il existe une variable y k , appelée sortie plate, telle qu'on puisse exprimer toutes variables du système comme fonction des itérés antérieurs et ultérieurs de cette sortie plate. En d'autres termes, il existe deux fonctions F ρ et G ρ paramétrisées par ρ telles que:

x k = F ρ y k+k F , . . . , y k+k F u k = G ρ y k+k G , . . . , y k+k G ( 2
)
avec k F , k F , k G et k G des valeurs entières de Z.
La platitude est cependant une notion importante qui admet de divers et variés domaines d'application comme dans la planification de trajectoire [START_REF] Chamseddine | Flatnessbased trajectory planning/replanning for a quadrator unmanned aerial vehicle[END_REF][START_REF] Meurer | Flatness-based trajectory planning for diffusion-reaction systems in a parallelepipedon -a spectral approach[END_REF], en contrôle prédictif ou encore dans la gestion de contraintes [START_REF] De Donà | A flatness-based iterative method for reference trajectory generation in constrained NMPC[END_REF][START_REF] Fliess | Toward a module theoretic approach to discrete-time linear predictive control[END_REF][START_REF] Kandler | A differential flatness based model predictive control approach[END_REF]. Dans cette thèse, on va s'intéresser, au-delà d'une simple vérification des sorties plates d'un système LPV, à la construction des systèmes LPV qui admettent des sorties plates. Ceci revient donc d'après la définition 1, à construire des systèmes LPV dont les variables s'expriment comme fonction de la sortie.

Il existe plusieurs approches qui permettent de caractériser les sorties plates d'un système LPV. On peut citer: Résumé détaillé de la thèse l'approche directe: elle consiste à exprimer par itérations successives les variables du système comme fonction de la sortie. Il en résulte cependant que cette approche est onéreuse même pour des systèmes de petite dimension et devient presque impossible à adopter pour des systèmes de grande dimension.

l'approche basée sur le système inverse: il s'agit d'une approche qui utilise, lorsqu'il existe, le système inverse à gauche du système LPV [START_REF]FIPS publication 197 -advanced encryption standard[END_REF]. Ce système inverse admet dans ce cas une matrice dynamique notée P et qui s'exprime en fonction des matrices A, B, C et D du système LPV.

Une caratérisation de la sortie plate basée sur le système inverse a été proposé pour les systèmes linéaires switchés dans [START_REF] Millérioux | Flatness of switched linear discrete-time systems[END_REF]. L'extension de cette caractérisation aux systèmes LPV est immédiate, en considérant la fonction de commutation comme une fonction à valeurs dans un ensemble indéterminé au lieu d'un ensemble fini qui est appelé modes. Cette caractérisation est basée sur la notion de degré relatif d'un système dynamique [START_REF] Parriaux | Nilpotent semigroups for the characterization of flat outputs of switched linear and lpv discrete-time systems[END_REF] que l'on rappelle ci-après: Définition 2 Le degré relatif d'un système dynamique est le nombre minimal r d'itérations à partir duquel la sortie y k+r à l'instant k + r est influencée par l'entrée u k .

Dans le cas d'un système LPV [START_REF]FIPS publication 197 -advanced encryption standard[END_REF], on montre que si le système admet un degré relatif r alors, pour toute réalisation ρ, la sortie s'exprime par:

y k+r = C ρ(k+r) k l=k+r-1 A ρ(l) x k + T r,0 ρ(k) u k ( 3
)
où T r,0 ρ(k) est une quantité définie suivant les valeurs de r par:

1. si r = 0 : T 0,0 ρ(k) = 0 pour tout entier relatif k 2. sinon si r < ∞, alors r est le plus petit entier s tel que:

T i,j ρ(k) = 0 pour i = 0, . . . , s -1 et j = 0, . . . , i, T s,0 ρ(k) = 0 (4) pour tout entier relatif k ≥ 0 et pour toute réalisation ρ.

On a donc le théorème suivant qui permet de caractériser la sortie plate d'un système LPV [START_REF]FIPS publication 197 -advanced encryption standard[END_REF]. A ρ(l) [START_REF] Bara | Parameter-dependent state observer design for affine LPV systems[END_REF] La preuve de ce théorème est constructive et permet en outres de montrer que l'état interne x k ainsi que l'entrée u k du système LPV (1) s'expriment en fonction des itérés de la sortie y k par: [START_REF] Bellare | A concrete security treatment of symmetric encryption[END_REF] et

Théorème 1 ([34])

x k = K-1 i=0 i j=1 P ρ(k-j:k-j+r) (T r,0 ρ(k-1-i) ) -1 B ρ(k-1-i) y k-1-i+r
u k = (T r,0 ρ(k) ) -1 y k+r -(T r,0 ρ(k) ) -1 C ρ(k+r) k l=k+r-1 A ρ(l) • K-1 i=0 i-1 j=0 P ρ(k-j-1:k-j-1+r) (T r,0 ρ(k-1-i) ) -1 B ρ(k-1-i) y k-1-i+r (8)
L'intérêt du Théorème 1 est qu'il offre une expression explicite des fonctions F ρ et G ρ lorsque y k est une sortie plate. Cependant vérifier que y k est une sortie plate exigerait de vérifier le produit 5 pour un nombre infini de réalisations ρ; ce qui ne peut être réalisé dans la pratique. Pour cela, il sera proposé une approche basée sur les graphes orientés que l'on décrira un peu plus bas.

Problème de la mortalité: il est à noter que l'égalité de l'Equation ( 5) n'est pas nécessairement vérifiée pour tout produit de matrice P ρ(k:k+r) mais seulement pour un nombre de séquences admissibles de telles matrices. Cette égalité est connue de façon plus générale sous le nom de problème de mortalité qui est un problème indécidable ( [START_REF] Blondel | When is a pair of matrices mortal?[END_REF][START_REF] Bournez | The mortality problem for matrices of low dimensions[END_REF][START_REF] Paterson | Unsolvability in 3 × 3 matrices[END_REF]). Il a cependant été proposé dans [START_REF] Parriaux | Nilpotent semigroups for the characterization of flat outputs of switched linear and lpv discrete-time systems[END_REF] une approche basée sur les semi-groupes nilpotents de matrices vérifiant l'égalité (5).

Définition 3 (Semi-groupe nilpotent) Un semi-groupe S est un ensemble avec une loi multiplicative associative interne. On dit qu'un semi-groupe S qui admet une élément absorbant 0 est nilpotent s'il existe un entier t ∈ N * tel que tout produit de t éléments appartenant à S est nul. Le plus petit entier t est appelé dans ce cas la classe de nilpotence de S.

Résumé détaillé de la thèse

Cette notion de semi-groupe nilpotent est intrinsèquement liée à la notion de triangularisation simultanée. En effet le Théorème de Levitzky [START_REF] Radjavi | Simultaneous Triangularization[END_REF] dit qu'un ensemble de matrices forme un semi-groupe nilpotent si et seulement si cet ensemble est simultanément triangularisable autrement dit si et seulement si cet ensemble admet une base commune de triangularisation.

On a donc le théorème suivant qui caractérise une sortie plate d'un système LPV.

Théorème 2 ([89]

) Si la matrice P ρ(k:k+r) est triangularisable indépendemment de ρ, alors y k est une sortie plate du système [START_REF]FIPS publication 197 -advanced encryption standard[END_REF].

Cette dernière approche offre une complexité polynômiale, lorsque l'ensemble de matrices est donné, pour vérifier si une sortie du système est plate ou non. L'inconvénient est qu'elle n'est pas appropriée pour répondre à notre problématique à savoir la construction de matrices qui doivent vérifier le Théorème 2.

Pour toutes les raisons énumérées ci-dessus, il sera proposé une approche complémentaire basée sur les graphes orientés qui fournit des conditions nécessaires et suffisantes afin de caractériser les sorties plates d'un système LPV et plus encore qui fournit un moyen de construction systématique de systèmes LPV qui admettent une sortie plate.

Approche basée sur les graphes orientés: Cette approche considère le système linéaire structuré associé au système LPV (1) et qui est décrit par le système d'équations:

Σ Λ : x k+1 = I A x k + I B u k (9)
Ce système structuré exprime une forme simplifiée du système LPV. Ceci permet de traduire les variables de ce dernier en termes de sommets d'un graphe orienté noté par G(Σ Λ ). Les arcs de ce graphe décrivant la dynamique du système LPV. Ainsi aux matrices A ρ(k) et B ρ(k) du système LPV [START_REF]FIPS publication 197 -advanced encryption standard[END_REF], on associe les matrices I A et I B du système structuré [START_REF] Berbain | Sosemanuk, a fast softwareoriented stream cipher[END_REF] dont les coefficients sont des 0 et des 1 ; les variables non nulles des matrices du système LPV étant remplacées par des coefficients 1 dans les matrices du système structuré.

Si on considère l'exemple suivant de matrices d'un système LPV

A ρ(k) = 1 ρ 1 (k) 0 ρ 2 (k) , B ρ(k) = 0 ρ 3 (k) C ρ(k) = 1 0 D ρ(k) = 0. ( 10
)
alors les matrices du système structuré sont donnés par

I A = 1 1 0 1 , I B = 0 1
Le graphe orienté associé au système est donné par la Figure 1.

v

R ÉSUM É D ÉTAILL É DE LA TH ÈSE u v 2 v 1
Figure 1: Graphe orienté du système linéaire structuré associé au système LPV [START_REF] Thierry | Extended generalized Feistel networks using matrix representation[END_REF].

On note par v F et u les sommets du graphe orienté G(Σ Λ ) qui sont associés respectivement à la sortie (supposée plate) et l'entrée du système LPV [START_REF]FIPS publication 197 -advanced encryption standard[END_REF]; et par X l'ensemble des sommets de G(Σ Λ ) associés aux composantes de l'état interne x du système LPV. A partir de ce graphe orienté associé au système LPV [START_REF]FIPS publication 197 -advanced encryption standard[END_REF], on établit trois conditions nécessaires et suffisantes données par le théorème suivant: Théorème 3 [START_REF] Boukhobza | Graphical characterization of the set of all flat outputs for structured linear discrete-time systems[END_REF] Considérons le système linéaire structuré Σ Λ décrit par [START_REF] Berbain | Sosemanuk, a fast softwareoriented stream cipher[END_REF]. La sortie y F associée aux sommets v F ∈ X ∪ {u} est génériquement une sortie plate si et seulement si les trois conditions suivantes sont vérifiées dans le graphe G(Σ Λ ) associé: C0. v F est un successeur de u autrement dit, il existe un chemin dans le graphe G(Σ Λ ) qui relie l'entrée à la sortie; C1. tous les chemins simples 1 {u}-{v F } reliant les deux sommets, associés à l'entrée et à la sortie, sont de même longueur (u, v F ); C2. tous les cycles du graphe couvrent au moins un élément de l'ensemble des sommets essentiels 2 V ess ({u}, {v F }).

Ainsi l'approche graphe-orienté, à travers ces trois conditions, permet de caractériser de façon plus aisée avec une complexité polynômiale les sorties plates du système LVP [START_REF]FIPS publication 197 -advanced encryption standard[END_REF]. Et en se basant sur ces conditions, on peut aisément construire des schémas ou structures de graphe qui donnent des systèmes LPV plats. Ce que ne permettait pas l'approche algébrique (Théorème 1). De plus l'approche graphe-orienté fournit explicitement les valeurs du degré relatif (Définition 2) et de l'entier K du Théorème 1. Ces valeurs sont données par les deux propositions suivantes: Proposition 1 ( [START_REF] Dravie | A mixed algebraic/graph-oriented approach for flatness of SISO LPV discrete-time systems[END_REF]) Le degré relatif r du système [START_REF]FIPS publication 197 -advanced encryption standard[END_REF] est égal à (u, v F ) dans le graphe orienté G(Σ Λ ).

Proposition 2 ([34]) Si y F

k est une sortie plate, alors l'entier K du Théorème 1 est génériquement égal à la longueur maximale de tous les chemins simples {u}-X du graphe orienté G(Σ Λ ).

En combinant donc les deux approches algébrique et graphe-orienté, on obtient une caractérisation complète des sorties plates du système LPV (1) avec des expressions explicites des variables x k et u k comme données par les Equations [START_REF] Bellare | A concrete security treatment of symmetric encryption[END_REF] et [START_REF] Bellare | Introduction to modern cryptography[END_REF].

Résumé détaillé de la thèse

Nous sommes donc en mesure, grâce aux idées qui ont été développées jusqu'ici, d'établir le lien entre les SSSCs et les systèmes dynamiques LPV plats tout en proposant une construction systématique des SSSCs. C'est ce qui fera l'objet du Chapitre 2 de la thèse.

Rappelons avant tout que les SSSCs sont utilisés en cryptographie symétrique comme chiffreurs à flot. De tels chiffreurs sont utilisés dans la transmission de données de façon sécurisée à un débit trés élevé et via des appareils électroniques qui sont limités en ressources matérielles. On distingue deux classes principales de chiffreurs à flots: les chiffreurs dit synchrones (Synchronous Stream Ciphers ou SSC en anglais) et les chiffreurs auto-synchronisants (SSSC) qui font donc l'objet d'étude de cette thèse.

L'avantage majeur de ces derniers par rapport aux premiers est qu'ils ne nécessitent aucun protocole supplémentaire de resynchronisation entre les entités qui échangent des données sécurisées. L'utilisation des SSSCs est donc d'un intérêt crucial pour l'échange de communication sécurisée en groupe et permet par exemple à toute entité autorisée de s'insérer dans une communication en cours sans qu'elle n'ait nullement besoin d'initialiser son dispositif de communication avec les autres membres du groupe.

Les SSSCs sont décrits d'une façon générale à travers une forme dite canonique illustrée par la Figure 2. Les équations de chiffrement et de déchiffrement sont données par les Equations [START_REF] Biham | Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials[END_REF] et [START_REF] Blondel | When is a pair of matrices mortal?[END_REF] suivantes:

   z k = σ ss θ (c k-l-M +1 , . . . , c k-l ) c k = e(z k , m k ) (11)    z k = σ ss θ (c k-l-M +1 , . . . , c k-l ) m k = e(z k , c k ) (12)
où θ désigne un paramètre secret partagé par l'émetteur et le récepteur des messages chiffrés échangés, σ ss θ est appelée fonction de filtrage et génère la suite chiffrante notée z k côté chiffreur et z k côté déchiffreur. Ces suites chiffrantes dépendent des M précédents chiffrés c k . On voit donc qu'il suffit au déchiffreur de recevoir les M symboles chiffrés précédant c k et transmis sans erreur par le chiffreur pour pouvoir déchiffrer correctement c k .

Les études sur les SSSCs ont été initiées au début des années 90 par les travaux de Maurer dans [START_REF] Ueli | New approaches to the design of self-synchronizing stream ciphers[END_REF]. Dans la forme canonique des SSSCs, toute la complexité du schéma réside dans la vii R ÉSUM É D ÉTAILL É DE LA TH ÈSE fonction de filtrage σ ss θ ce qui est n'est pas évident à concevoir. Pour remédier à cela, Maurer a proposé une construction de SSSCs basée sur des automates à mémoire finie (illustrée d'une façon généralisée par la Figure 3), qui de façon récursive produira la même séquence de suite chiffrante que la forme canonique. L'automate à mémoire finie est caractérisé par le système d'équations suivant:

m k c k m k e e -1 z k z k g θ g θ h θ h θ q k q k
q k+1 = g θ (q k , c k+b ) z k+b = h θ (q k ) (13)
où g θ correspond à la fonction de transition d'état de l'automate, q k désigne l'état interne et z k la suite chiffrante générée par la fonction de filtrage h θ . Suite aux travaux de Maurer, quelques constructions ont été proposées [START_REF] Daemen | The self-synchronizing stream cipher mosquito: estream documentation, version 2[END_REF][START_REF] Daemen | The self-synchronizing stream cipher moustique[END_REF][START_REF] Hawkes | Primitive specification for sss[END_REF][START_REF] Sarkar | Hiji-bij-bij: A new stream cipher with a self-synchronizing mode of operation[END_REF] mais ont été toutes cassées par des travaux de cryptanalyse dans [START_REF] Daemen | Chosen ciphertext attack on SSS. eS-TREAM, ECRYPT Stream Cipher Project[END_REF][START_REF] Joux | Chosen-ciphertext attack against mosquito[END_REF][START_REF] Joux | Loosening the KNOT[END_REF][START_REF] Joux | Two attacks against the HBB stream cipher[END_REF][START_REF] Klíma | Cryptanalysis of hiji-bij-bij (HBB)[END_REF]. Il y a cependant un point commun à toutes ces constructions, c'est que la fonction de transition g θ dans [START_REF] Bogdanov | Zero-correlation linear cryptanalysis of block ciphers[END_REF] est une fonction dite triangulaire ou T-function [START_REF] Klimov | New cryptographic primitives based on multiword t-functions[END_REF] en anglais.

Un des objectifs de la thèse est donc de proposer une classe plus générale de fonctions de transition et qui ne sont pas nécessairement triangulaires. Les résultats sur la platitude des systèmes LPV, notamment à travers les Equations [START_REF] Bellare | A concrete security treatment of symmetric encryption[END_REF] et [START_REF] Bellare | Introduction to modern cryptography[END_REF] nous permettent d'ores et déjà d'établir le lien entre les SSSCs et les systèmes LPV plats. On montre qu'on peut utiliser le système LPV direct (1) comme chiffreur d'un SSSC et le système inverse du système LPV comme déchiffreur. Ceci est traduit par la proposition suivante:

Proposition 3 ([36]) Si le système LPV (1) admet un degré relatif r et est plat, alors l'automate à mémoire finie donnée par les systèmes d'équations suivants défini un SSSC:

     q k+1 = P ρ(k:k+r) q k + B ρ(k) (T r,0 ρ(k) ) -1 y k+r z k+r = C ρ(k+r) k l=k+r-1 A ρ(l) q k      q k+1 = P ρ(k:k+r) q k + B ρ(k) (T r,0 ρ(k) ) -1 y k+r z k+r = C ρ(k+r) k l=k+r-1 A ρ(l) q k
En conclusion pour construire notre automate à mémoire finie qui peut être utilisé comme un SSSC, on génère un graphe-orienté à partir des Conditions C0-C2 du Théorème 1. Ensuite viii Résumé détaillé de la thèse on extrait de ce graphe un système LPV plat et son système inverse. Ces systèmes correpondent à l'automate donné par la Proposition 3.

Dans la seconde partie de cette thèse, on s'intéresse à la sécurité d'algorithme autosynchronisant proposé dans la thèse. Dans un premier temps on étudie dans le Chapitre 3, la sécurité physique de l'algorithme en réalisant une attaque par canaux cachés plus précisément une analyse par consommation de courant sur un dispositif qui contient l'algorithme. Cette analyse porte le nom de Correlation Power Analysis ou CPA en anglais et fut proposée dans [START_REF] Brier | Correlation power analysis with a leakage model[END_REF]. L'originalité des travaux de ce Chapitre 3, c'est qu'on propose ici une approche spectrale pour réaliser une attaque CPA, approche qui est basée sur la transformée de Fourier. En effet l'objectif d'une attaque CPA est de retrouver des paramètres secrets de l'algorithme en établissant une corrélation entre d'une part la consommation réelle de courant du dispositif cryptographique attaqué et d'autre part une consommation hypothétique obtenue à partir d'un modèle d'attaque. Et plus la corrélation est élevée, plus les valeurs de paramètres secrets retrouvés sont fiables.

Les fonctions décrivant la consommation de courant sont ici des fonctions définies sur un ensemble de mots binaires à valeurs réelles et notée par ϕ: ϕ : {0, 1} n → R Définition 4 (Transformée de Fourier) La transformée de Fourier de la fonction ϕ la fonction définie sur {0, 1} n par:

u → ϕ(u) = ϕ, χ u = 1 √ 2 n x∈{0,1} n ϕ(x)(-1) u•x .
On montre donc que cette transformée de Fourier conserve la norme de la fonction ϕ notée ϕ . Autrement dit ϕ = ϕ . Cette remarque sur la conservation de la norme est très utile et constitue l'idée centrale qui permet de proposer une approche spectrale de la CPA en appliquant la transformée de Fourier à la consommation réelle de courant ϕ et à la consommation hypothétique que l'on va notée par g.

On montre ensuite qu'en adoptant cette approche spectrale, on peut retrouver les paramètres secrets utilisés dans un algorithme cryptographique, notamment les sous clés qui sont utilisées comme entrée de fonctions non linéaires représentées par des boîtes S ou Subtitution Box (S-Box) en anglais. Ainsi on peut retrouver la valeur d'une sous clé utilisée comme entrée d'une boîte S pendant l'exécution d'un algorithme cryptographique en calculant la valeur qui maximise la fonction F suivante:

F (k) = u∈{0,1} n ϕ(u) g(u)(-1) u•k . ( 14
)
Dans un deuxième temps, on traite de la sécurité théorique des SSSCs. En effet une question naturelle qui émerge, suite aux cryptanalyses réalisées sur les SSSCs qui ont été construits, c'est de savoir si l'on peut toutefois concevoir des SSSCs qui atteignent un certain niveau de sécurité souhaité. Le Chapitre 4 apporte une réponse à cette question en considérant la forme canonique des SSSCs. On traite plus précisément des notions d'indistingabilité introduites dans [START_REF] Goldwasser | Probabilistic encryption and how to play mental poker keeping secret all partial information[END_REF][START_REF] Goldwasser | Probabilistic encryption[END_REF]. Il s'agit donc d'étudier d'une part la résistance du schéma contre des attaques à clairs choisis ou indistinguishability against Chosen Plaintext Attack (IND-CPA) en anglais et d'autre part la résistance contre des attaques à chiffrés choisis ou indistinguishability against Chosen Cipher Attack (IND-CCA) en anglais.

Pour étudier les résistances contre de telles attaques, on établit des jeux de sécurité [START_REF] Bellare | Introduction to modern cryptography[END_REF]. Ces jeux de sécurité font intervenir un adversaire ou un challenger noté A qui défi un oracle noté O qui a accès à l'algorithme cryptographique et qui peut chiffrer ou déchiffrer des symboles clairs ou symboles chiffrés que lui soumet l'adversaire A. Le but de ce dernier est de savoir lequel de deux symboles clairs (respectivement chiffrés) soumis à l'oracle O a été chiffré (respectivement déchiffré) dans le cas d'une attaque IND-CPA (respectivement IND-CCA). Si l'adversaire parvient à deviner le bon symbole chiffré ou déchiffré par l'oracle alors il gagne le jeux, sinon il perd.

On montre donc à travers ces jeux de sécurité, que dans le cas des attaques IND-CCA le schéma n'est pas résistant à cause de sa malléabilité [START_REF] Dravie | Security proof of the canonical form of self-synchronizing stream ciphers[END_REF].

Par contre le schéma est résistant contre les attaques IND-CPA [START_REF] Dravie | Security proof of the canonical form of self-synchronizing stream ciphers[END_REF]. Pour montrer ce dernier résultat on se base sur les notions de fonction pseudo aléatoires ou Pseudo Random Function (PRF) en anglais (voir [START_REF] Goldreich | How to construct random functions[END_REF][START_REF] Bellare | Introduction to modern cryptography[END_REF].) On montre que si la fonction de filtrage σ ss θ de la forme canonique est une PRF alors le schéma est résistant conre les attaque IND-CCA. On va plus long en relaxant cette condition et en introduisant une notion plus faible que celle des PRF: il s'agit de la notion Weak Pseudo Random Function (WPRF) en anglais, qui permet de mieux caractériser la propriété d'auto-synchronisation et qui donne cette fois-ci une condition nécessaire et suffisante sur la fonction de filtrage pour que le schéma soit résistant contre les attaques IND-CPA.

Le dernier chapitre, Chapitre 5 de la thèse, porte sur la représentation matricielle de foncx Résumé détaillé de la thèse tions vectorielles Booléennes [START_REF] Carlet | Boolean functions for cryptography and error-correcting codes[END_REF] qui sont utilisées comme fonctions de transition d'un SSSC. Ces représentations matricielles décrivent en fait une même fonction mais dans différentes bases. Les matrices représentatives sont ici les matrices de corrélation, de Walsh, d'adjacence qui sont de façon usuelle utilisées en cryptographie pour analyser les propriétés des fonctions vectorielles Booléennes. On introduit une représentation matricielle supplémementaire qui est la matrice polynômiale. Un des résulats fort de ce chapitre établit des relations entre les valeurs propres, les espaces propres ainsi qu'une structure de graphe associée des matrices. Pour arriver à ces résultats on utilise les notions de fonctions booléennes: la forme algébrique normale ou Algebraic Normal Form (ANF) en anglais [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF]) et la forme numérique normale ou Numerical Normal Form (NNF) en anglais (voir [START_REF] Carlet | A new representation of Boolean functions[END_REF]).

L'application de ces représentations matricielles aux SSSCs, notamment la matrice de corrélation, permet de dire si la fonction de transition d'un SSSC est une fonction triangulaire ou non. Ce résultat a été déjà établi dans la thèse de Parriaux [START_REF] Parriaux | Control, synchronization and encryption[END_REF]. On donne dans ce chapitre un exemple qui confirme le résultat pour les SSSCs basés sur les systèmes LPV plat.

xi Un grand merci également à mes amis qui ont été présents et m'ont apporté leur soutien pendant la thèse en particulier, Eric, Ginette, Amen, Rico, Têtê, Hervé.

Finalement j'adresse mes profonds remerciements à ma famille qui a fait preuve d'un soutien sans faille durant ces années de thèse. Un sincère remerciement à ma mère et à mon père qui m'ont beaucoup encouragé et aidé.

Contents

Contents xv

List of Figures xix

Acronyms xxi

Notations xxiii

General Introduction 1

List of Figures

G digraph. G(Σ Λ ) digraph associated to Σ Λ . G(Σ ρ ) digraph associated to Σ ρ . V set of state vertices in a digraph. E set of edges in a digraph. v i the vertex number i of a digraph.
n M maximal number of edges of a digraph.

General Introduction

Synchronization has been an important topic in automatic control for years. Roughly speaking, by synchronization, it is meant correlated (according to given criteria) behaviors of at least two or more interconnected entities in virtual or physical networks. Throughout the past centuries, scientists have attempted to explain the emergence of order through the concept of synchronization. C. Huygens in 1665 can be considered as a pioneer. There is an outstanding number of examples of synchronized phenomena (see [START_REF] Strogatz | SYNC: The Emerging Science of Spontaneous Order[END_REF]) borrowed from nature, biology, neuroscience, physiology and more recently social networks. Synchronization can be a very efficient way of tackling engineering issues as well. For example, there is a growing interest in cooperative control problems. Such problems involve several autonomous entities (also called agents) which try to collectively reach a global objective by a suitable connectivity or couplings. The related applications are mobile robots, unmanned and autonomous vehicles, satellites, air traffic control. Synchronization is also central in communication: video, broadcasting, Phase Lock Loop-based equipments. When synchronization must occur in a peer-to-peer communication setup without any external control, it is called self-synchronization. It turns out that self-synchronization is central in cryptography, more specifically, in symmetric cryptography involving the so-called Self-Synchronizing Stream Ciphers (SSSC) (see [START_REF] Menezes | Handbook of Applied Cryptography[END_REF]). Such ciphers are based on generators which can take the form of dynamical systems operating on finite fields and must deliver complex sequences. Those sequences are used to scramble the information to be safely transmitted. For proper decryption, those sequences must be self-synchronized.

In this thesis, we aim at addressing SSSC-based cryptography in terms of control theoretical concepts. The main result is that the concept of flatness together with graph-theory allows to provide a convenient and systematic way to construct general classes of SSSC, the ciphers being viewed as dynamical systems. The flatness (differential or difference) on one hand and the SSSC on the other hand are detailed a little bit more below.

Differential flatness is a property of some continuous-time controlled dynamical systems introduced in [START_REF] Fliess | Flatness and defect of non-linear systems: introductory theory and examples[END_REF]. The counterpart for discrete-time systems is called difference flatness. For a flat discrete-time system, the state variables as well as the input are written as a function of the flat output (including forward and backward shifts in the output). Difference flatness has been

GENERAL INTRODUCTION

first reported in [START_REF] Fliess | Toward a module theoretic approach to discrete-time linear predictive control[END_REF][START_REF] Sira-Ramirez | Differentially Flat Systems[END_REF] although we should mention that a closely related notion, namely the dynamic feedback linearization, was addressed earlier in [START_REF] Aranda-Bricaire | Linearization of discrete-time systems[END_REF]. Flatness-based control has been involved in many applications and has an outstanding interest in, for instance, trajectory planning as reported in [START_REF] Meurer | Flatness-based trajectory planning for diffusion-reaction systems in a parallelepipedon -a spectral approach[END_REF][START_REF] Chamseddine | Flatnessbased trajectory planning/replanning for a quadrator unmanned aerial vehicle[END_REF], predictive control and constraint handling as detailed in [START_REF] De Donà | A flatness-based iterative method for reference trajectory generation in constrained NMPC[END_REF][START_REF] Kandler | A differential flatness based model predictive control approach[END_REF]. The reader can also refer to the book [START_REF] Sira-Ramirez | Differentially Flat Systems[END_REF] for further applications. Since in this thesis, only discrete-time finite state dynamical systems are considered, the word flatness will be often used for short without confusion. Chapter 1 will be devoted to characterization of flat output of LPV systems. It will show how graph approach can be used to achieve such a characterization.

Self-Synchronizing Stream Ciphers were patented in 1946. This self-synchronization property has many advantages and is especially relevant to group communications. Since 1960, specific SSSC have been designed and are still used to provide bulk encryption (for Hertzian line, RNIS link, . . . ) in military applications or governmental radio mobile networks. In the early 90 s, studies have been performed in [START_REF] Ueli | New approaches to the design of self-synchronizing stream ciphers[END_REF][START_REF] Daemen | On the design of high speed selfsynchronizing stream ciphers[END_REF] to propose secure designs of SSSC. These works have been followed by effective constructions ( [START_REF] Daemen | On the design of high speed selfsynchronizing stream ciphers[END_REF][START_REF] Sarkar | Hiji-bij-bij: A new stream cipher with a self-synchronizing mode of operation[END_REF][START_REF] Daemen | The self-synchronizing stream cipher moustique[END_REF]), but till now, all of these SSSC have been broken ([57, 58, 56, 61, 62]) which motivates the search for new constructions of SSSC.

It turns out that, all the constructions of SSSC that have been proposed in the literature are based on T-function (for Triangular function, see [START_REF] Klimov | New cryptographic primitives based on multiword t-functions[END_REF]). In [START_REF] Millérioux | Self-synchronizing stream ciphers and dynamical systems: state of the art and open issues[END_REF], it has been shown that a new architecture of SSSC not restricted to T-functions can be designed using concepts and results borrowed from Control Theory. In Chapter 2, it is shown that the consideration of the special class of flat Linear Parameter Varying (LPV) systems, with the help of graph theory, allows for a convenient and systematic design of SSSC admitting not exclusively T-functions.

The second part of the work is devoted to security. Regarding security, SSSC have intrinsic interesting properties due to the specific architecture. For example, as each plaintext symbol influences potentially all subsequent ciphertexts, they naturally have good diffusion properties and are efficient against attacks based on plaintext redundancy. Furthermore, they can prevent from traffic analysis as the information which is conveyed through the channel is encrypted whether there is traffic or not. In the middle of the 90 s, a new kind of attack on cryptosystems, called side-channel attack, has been developed with a pioneering work of P. Kocher [START_REF] Paul | Timing attacks on implementations of diffie-hellman, rsa, dss, and other systems[END_REF]. Sidechannel attacks are attacks that exploit leakages of devices running a cryptographic algorithm. These leakages can result from physical emanations such as power consumption, electromagnetic radiations, temperature or execution time when running the algorithm. This is due to Substitution Box (S-Box) used as nonlinear functions within a cryptographic algorithm and that are also implemented in SSSC algorithms. Indeed, S-Box are highly sensitive to power consumption and electromagnetic leakages. Although a cryptographic algorithm can be proved secure theoretically, it is not ensured that the algorithm does not reveal secret information when it is implemented in a device. Common side channel attacks are Simple Power Analysis (SPA) and Differential Power Analysis (DPA). The aim of Chapter 3 is to propose a new and simple approach to perform a Correlation Power Analysis (CPA) which is an advanced form of

General Introduction

DPA. The approach is based on spectral theory, especially on Fourier transform of real valued function over the set of binary words. We use hereafter this approach to perform a CPA attack on the S-Box used within the designed LPV-based SSSC.

Considering theoretical security, we show in Chapter 4 that the canonical form of the Self-Synchronizing Stream Cipher is not resistant against chosen ciphertext attack (IND-CCA security) but can reach the resistance against chosen plaintext attack (IND-CPA security) provided that the filtering function is pseudo random. We introduced a new family of functions in order to characterize the security of the canonical SSSC from its filtering function. Those functions are called Weak Pseudo Random Functions (WPRF) and provide a weaker property than pseudo-randomness. A connection with the left-or-right indistinguishability (LOR-IND) is made. This property provides a necessary and sufficient condition to characterize the indistinguishablity of SSSC. The technical developments used to establish the security proof follow similar lines than those used when dealing with symmetric encryption schemes based on block ciphers.

Finally, the approach used in this thesis to design Self-Synchronizing Stream Cipher is a mixed algebraic and graph theory approach. However, it is interesting to note that we can make a general characterization of functions that can be used in the design of Self-Synchronizing Stream Ciphers. The work of the paper [START_REF] Parriaux | A spectral approach for characterizing the self-synchronization of stream ciphers[END_REF] tackled this problem by giving a characterization that is based on Walsh transform and matrix representation of vectorial boolean functions. The aim of Chapter 5 is then devoted to results that are useful to establish such characterizations. It gives a general and unified overview on matrix representations of vectorial boolean functions. These results are not only useful to characterize self-synchronizing property of next-state function from spectral approach but are also really interesting in application of boolean function to cryptography.

Chapter 1 LPV Systems and

Characterization of Flatness

The aim of this chapter is to provide concepts from control theory that will be useful in the design of Self-Synchronizing Stream Ciphers. It illustrates the potential interest of LPV flat dynamical systems for cryptographic issues. The special class of LPV dynamical systems is presented. Then the definition of difference flatness is introduced and is particularized for LPV systems. First, necessary and sufficient conditions for an output to be difference flat are established. They are expressed in terms of algebraic conditions that must be verified by the state space matrices realization of the LPV system. It is shown how the combination of both the algebraic conditions and additional graph-based conditions allows to define a complete and tractable framework not only to find the flat outputs but also to explicit the functions of the state and the input with respect to the flat output. The results in this chapter are published in [START_REF] Dravie | A mixed algebraic/graph-oriented approach for flatness of SISO LPV discrete-time systems[END_REF]. [START_REF] Sato | Filter design for LPV systems using quadratically parameter-dependent lyapunov functions[END_REF]. The interest of LPV models is that they provide a systematic procedure to design gain-scheduled controllers like in the area of aerospace control [START_REF] Rugh | Research on gain scheduling[END_REF] or vehicle control [START_REF] Sename | Robust Control and Linear Parameter Varying Approaches, Application to Vehicle Dynamics[END_REF]. Besides, LPV models can represent nonlinear systems under appropriate conditions. Such a purpose has been investigated in the works reported in [START_REF] Bruzelius | Linear Parameter-Varying Systems: an approach to gain scheduling[END_REF] or in [START_REF] Millerioux | Considering the attractor structure of chaotic maps for observer-based synchronization problems[END_REF].

Contents

A Single Input Single Output (SISO) Linear Parameter-Varying (LPV) system denoted by Σ ρ , defined over a field F, is described by the following state space representation:

Σ ρ : x k+1 = A ρ(k) x k + B ρ(k) u k y k = C ρ(k) x k + D ρ(k) u k (1.1)
where k ∈ N stands for the discrete time,

x k ∈ F n is the state vector, u k ∈ F is the input, y k ∈ F is the output. The matrices A ∈ F n×n , B ∈ F n×1 , C ∈ F 1×n and D ∈ F 1×1
are respectively the dynamical matrix, the input matrix, the output matrix and the direct transfer matrix. Such a system is called Linear Parameter-Varying because it is written with a linear dependency with respect to the state vector. The set of all the varying parameters of A, B, C and D are collected on a vector denoted by ρ(k) = ρ 1 (k), ρ 2 (k), ..., ρ Lρ (k) ∈ F Lρ where L ρ is the total number of non zero (possibly varying) entries. The matrices A, B, C and D do not necessarily depend on all the parameters ρ i (k). Such systems can exhibit nonlinear dynamics. Indeed, the nonlinearity is obtained by defining the varying parameters ρ i (k) as nonlinear functions ϕ i of the output y k (or a finite number of shifts)

ρ i (k) = ϕ i (y k , y k-1 , • • • ).
Let us notice that the notation ρ i (k) (usual in the literature for LPV systems) is somehow abusive because it does not reflect an explicit dependency with respect to the time k but on quantities indexed with k.

In the next section, we focus on the property of flatness for LPV systems.

Difference Flatness for LPV Systems

For a non negative integer k 0 , a sequence {ρ(k 0 ), ρ(k 0 + 1), . . .} will be called a realization and denoted with ρ. The definition of a flat LPV system is given below in a generic sense, that is for almost every realization ρ.

Definition 1.2. [START_REF]FIPS publication 197 -advanced encryption standard[END_REF] The system (1.1) is said to be generically flat if, for almost every realization ρ, there exists a variable y k , called a flat output, such that all system variables can be expressed as a function of the flat outputs and a finite number of its backward and forward shifts. In other

Difference Flatness for LPV Systems

words, there exist two functions F ρ and G ρ parametrized by ρ such that

x k = F ρ y k+k F , . . . , y k+k F u k = G ρ y k+k G , . . . , y k+k G (1.2)
where k

F , k F , k G and k G are Z-valued integers.
Flatness is an important concept insofar as the applications of flatness (differential or difference) has a clear interest for trajectory planning [START_REF] Meurer | Flatness-based trajectory planning for diffusion-reaction systems in a parallelepipedon -a spectral approach[END_REF][START_REF] Chamseddine | Flatnessbased trajectory planning/replanning for a quadrator unmanned aerial vehicle[END_REF], predictive control or constraints handling [START_REF] Fliess | Toward a module theoretic approach to discrete-time linear predictive control[END_REF][START_REF] De Donà | A flatness-based iterative method for reference trajectory generation in constrained NMPC[END_REF][START_REF] Kandler | A differential flatness based model predictive control approach[END_REF] for example. Difference flatness has been recently addressed in [START_REF] Kaldmae | On flatness of discrete-time nonlinear systems[END_REF][97] [START_REF] Millérioux | Flatness of switched linear discrete-time systems[END_REF] for nonlinear discrete-time systems. However, those works suffer from either poorly tractable conditions or only sufficient conditions. Although flatness is closely related to controllability, only proving controllability of a system may not be satisfactory in practice. Indeed, beyond merely checking whether a system is flat or not, we should be not only interested in more constructive issues like finding the flat outputs and finding the functions that explicit the dependence of the state variables as well as the input with respect to the flat output. Those functions are central since they provide a convenient way to reconstruct the state of a system or to provide a feedforward control.

For LPV systems, several approaches can be used to characterize a flat output. They are recalled below and their shortcomings are pointed out to motivate the graph-oriented approach as a relevant complementary method. The discussion is illustrated through Example 1.2.1. It corresponds to the particular state space matrices setting of (1.1) given below.

Example 1.2.1

A ρ(k) = 1 ρ 1 (k) 0 ρ 2 (k) , B ρ(k) = 0 ρ 3 (k) , C ρ(k) = 1 0 , D ρ(k) = 0.
(1.

3)

The state component x 1 k is considered as the measured output, that is

y k = x 1 k .

Direct approach

This approach consists in trying to directly agree with the definition, that is attempting to express the input and the state vector as a function involving exclusively shifts of the output.

LPV SYSTEMS AND CHARACTERIZATION OF FLATNESS

For this example, y k is a flat output. Indeed, Definition 1.2.1 is satisfied with (1.2) which reads

           x 1 k = y k x 2 k = (ρ 1 (k)) -1 (y k+1 -y k ) u k = (ρ 3 (k)) -1 (ρ 1 (k + 1)) -1 y k+2 -(ρ 1 (k + 1)) -1 ρ 2 (k + 1)ρ 2 (k)(ρ 1 (k)) -1 (y k+1 -y k )
The problem of such an approach lies in that even for a small system, the task is not trivial and becomes prohibitive when the dimension grows up. However, let us mention that efficient algorithms involving elimination theory and symbolic computation can be used ( [START_REF] Buchberger | Gröbner bases: an algorithmic method in polynomial ideal theory[END_REF]).

The next subsection is devoted to the conditions which must be fulfilled by (1.1) to guarantee that a given output y k is flat.

Inverse system approach

First, it must be pointed out that for a given dynamics (first equation of (1.1)), y k is not necessarily a flat output. It depends on the matrices C and D. Besides, for some specific matrices A and B, it may happen that none of the matrices C and D yield to a flat output. As a result, the conditions which guarantee that an output of (1.1) is flat must be expressed in terms of properties verified by the 4-uple of state matrices A, B, C and D.

A flat output characterization based on the inverse system has been proposed in [START_REF] Millérioux | Flatness of switched linear discrete-time systems[END_REF] for switched linear systems. However, the extension to LPV systems is straightforward by considering the switching function as a function that takes values in a continuum rather than a finite set (the modes). Before giving the theorem, we must recall the definition and the characterization of the relative degree of (1.1) (see [START_REF] Parriaux | Nilpotent semigroups for the characterization of flat outputs of switched linear and lpv discrete-time systems[END_REF]).

Definition 1.2.2

The relative degree of a discrete-time dynamical system is the minimal number r of iterations such that its output y k+r at time k + r is sensitive to its input u k . Now, let us particularize this general definition to the system defined by equation (1.1). To this end, let us denote, for k 2 ≥ k 1 , by k1 l=k2 A ρ(l) the product of the matrices A ρ(l) , from k 2 down to k 1 , and

k1 l=k2 A ρ(l) = 1 n if k 2 < k 1 ,
and introduce the quantity T i,j ρ(k) defined for j ≤ i as

T i,j ρ(k) = C ρ(k+i) k+j+1 l=k+i-1 A ρ(l) B ρ(k+j) if j ≤ i -1 and T i,i ρ(k) = D ρ(k+i) (1.4)
From (1.1), it holds that , it follows that

y k+1 = C ρ(k+1) A ρ(k) x k + T 1,0 ρ(k) u k + T 0,0 ρ(k+1) u k+1 . Then,
y k+i = C ρ(k+i) k l=k+i-1 A ρ(l) x k + i j=0 T i,j ρ(k) u k+j (1.5)
Hence, if (1.1) admits a finite relative degree r, it follows from Definition 1.2.2 that:

1. r = 0 if T 0,0 ρ(k) = 0 for all k 2. r < ∞ is the least integer s such that for all k ≥ 0 and for all realization ρ.

T i,j ρ(k) = 0 for i = 0, . . . , s -1 and j = 0, . . . , i,

T s,0 ρ(k) = 0 (1.6)
Hence, it holds that

y k+r = C ρ(k+r) k l=k+r-1 A ρ(l) x k + T r,0 ρ(k) u k (1.7) Theorem
= A ρ(k) -B ρ(k) (T r,0 ρ(k) ) -1 C ρ(k+r) k l=k+r-1 A ρ(l) (1.9)
is equivalent to that y k is a flat output.

The result can be proved by using the inverse dynamical system of (1.1).

Proof. If the LPV system (1.1) has a finite relative degree r, the following dynamical system can always be defined since T r,0 ρ(k) is invertible.

       x k+r+1 = P ρ(k:k+r) x k+r + B ρ(k) (T r,0 ρ(k) ) -1 y k+r u k+r = (T r,0 ρ(k) ) -1 (C ρ(k+r) k l=k+r-1 A ρ(l) x k+r -y k+r ) (1.10)
Iterating K -1 times the first equation of (1.10) yields

x K+k+r = P ρ(K+k-1:K+k-1+r) • • • P ρ(k:k+r) x k+r + K-1 i=0 i j=1 P ρ(K+k-j:K+k-j+r) (T r,0 ρ(k-1-i+k) ) -1 B ρ(k-1-i+k) y k-1-i+k+r (1.11)

LPV SYSTEMS AND CHARACTERIZATION OF FLATNESS

Let us define ε k = x k+r -x k . Then ε k verifies

ε k+1 = x k+r+1 -x k+1 = P ρ(k:
+ K -1 + r)} ∈ Θ r+K x k = K-1 i=0 i j=1 P ρ(k-j:k-j+r) (T r,0 ρ(k-1-i) ) -1 B ρ(k-1-i) y k-1-i+r (1.12)
That is the LPV system (1.1) admits y k as flat output if and only if

P ρ(K+k-1:K+k-1+r) • • • P ρ(k:k+r) = 0.
Another way to prove Theorem 1.2.1 is to unfold (1.1).

Remark 1.2.1 From (1.1),

x k = A ρ(k-1) x k-1 + B ρ(k-1) u k-1 .
Then, if the system admits a finite relative degree r, one can infer from (1.7) that:

u k = (T r,0 ρ(k) ) -1 y k+r -(T r,0 ρ(k) ) -1 C ρ(k+r) k l=k+r-1 A ρ(l) x k (1.13)
Then, substituting (1.13) into the expression of x k above gives:

x k+1 = A ρ(k) x k + (T r,0 ρ(k) ) -1 B ρ(k) y k+r -(T r,0 ρ(k) ) -1 B ρ(k) C ρ(k+r) k l=k+r-1 A ρ(l) x k = P ρ(k:k+r) x k + (T r,0 ρ(k) ) -1 B ρ(k) y k+r (1.14)
Iterating (1.14) K -1 times and performing the change of variable k + K → k yields

x k =P ρ(k-1:k-1+r) • • • P ρ(k-K:k-K+r) x k-K + K-1 i=0 i-1 j=0 P ρ(k-j-1:k-j-1+r) (T r,0 ρ(k-1-i) ) -1 B ρ(k-1-i) y k-1-i+r (1.15)
The right hand side of (1.15) giving the expression of

x i k (i = 1, . . . ,
x k = K-1 i=0 i-1 j=0 P ρ(k-j-1:k-j-1+r) (T r,0 ρ(k-1-i) ) -1 B ρ(k-1-i) y k-1-i+r (1.16)
The explicit form of G ρ involved in (1.2) is obtained by substituting (1.12) into (1.13):

u k = (T r,0 ρ(k) ) -1 y k+r -(T r,0 ρ(k) ) -1 C ρ(k+r) k l=k+r-1 A ρ(l) • K-1 i=0 i-1 j=0 P ρ(k-j-1:k-j-1+r) (T r,0 ρ(k-1-i) ) -1 B ρ(k-1-i) y k-1-i+r (1.17)
The relevance of Theorem 1.2.1 is that it provides an explicit form for F ρ and G ρ , assuming that y k is a flat output. On the other hand, testing whether an output y k is flat or not requires the knowledge of r and K and the test to calculate r and K would need the computation of the product (1.8) for an infinite number of realizations ρ. Clearly, it is infeasible in practice. It will be shown in Section 1.3 that with additional conditions borrowed from structural analysis and expressed in terms of a digraph associated to the LPV system, a complete framework handling those problems can be defined.

Considering Example 1.2.1 with the setting (1.3), one has

D ρ(k) = 0, C ρ(k+1) B ρ(k) = 0 and C ρ(k+2) A ρ(k+1) B ρ(k) = ρ 1 (k + 1) • ρ 3 (k). If ρ 1 (k) and ρ 3 (k) never vanish, the relative degree is r = 2. Hence T 2,0 ρ(k) = ρ 1 (k + 1) • ρ 3 (k) for all k ≥ 0. The matrix P ρ(k:k+2) = A ρ(k) -B ρ(k) C ρ(k+1) A ρ(k+1) A ρ(k) reads P ρ(k:k+2) = 1 ρ 1 (k) -(ρ 1 (k + 1)) -1 -(ρ 1 (k + 1)) -1 ρ 1 (k) (1.18)
It turns out that P ρ(k+2:k+4) P ρ(k+1:k+3) = 0 for any realization ρ and thus, Equation (1.8) is fulfilled and K = 2. The explicit expressions of F and G are given by Equations (1.16) and (1.17) respectively:

LPV SYSTEMS AND CHARACTERIZATION OF FLATNESS

x k = 1 i=0 i-1 j=0 P ρ(k-j-1:k-j+1) (T 2,0 ρ(k-1-i) ) -1 B ρ(k-1-i) y k-i+1 = (T 2,0 ρ(k-1) ) -1 B ρ(k-1) y k+1 + P ρ(k-1:k+1) (T 2,0 ρ(k-2) ) -1 B ρ(k-2) y k = 1 ρ 1 (k)ρ 3 (k -1) 0 ρ 3 (k -1)y k+1 + 1 ρ 1 (k -1)ρ 3 (k -2)   1 ρ 1 (k -1) - 1 ρ 1 (k) - 1 ρ 1 (k) ρ 1 (k -1)   0 ρ 3 (k -2)y k x k =   y k 1 ρ 1 (k) (y k+1 -y k )   and u k = (T 2,0 ρ(k) ) -1 y k+2 -(T 2,0 ρ(k) ) -1 C ρ(k+r) k l=k+r-1 A ρ(l) • K-1 i=0 i-1 j=0 P ρ(k-j-1:k-j+1) (T 2,0 ρ(k-1-i) ) -1 B ρ(k-1-i) y k+1-i = 1 ρ 1 (k + 1)ρ 3 (k) y k+2 - 1 ρ 1 (k + 1)ρ 3 (k) A ρ(k+1) [2]A ρ(k) x k = 1 ρ 1 (k + 1)ρ 3 (k) y k+2 -0 ρ 2 (k + 1) 1 ρ 1 (k) 0 ρ 2 (k)   y k 1 ρ 1 (k) (y k+1 -y k )   u k = 1 ρ 1 (k + 1)ρ 3 (k) y k+2 - ρ 2 (k + 1)ρ 2 (k) ρ 1 (k) (y k+1 -y k )

Mortality problem

It is worth pointing out that P ρ(k:k+r) is not imposed to satisfy (1.8) for every K products but for admissible sequences of products checking (1.8). Such problem is closely related to the notion of mortality. Indeed, it is said that a set of matrices is mortal if the zero matrix can be expressed as the product of a finite number of matrices. And yet, from the papers [START_REF] Paterson | Unsolvability in 3 × 3 matrices[END_REF][START_REF] Blondel | When is a pair of matrices mortal?[END_REF][START_REF] Bournez | The mortality problem for matrices of low dimensions[END_REF], except from some very special cases, the problem of checking mortality of a set of matrices is unsolvable because it is an undecidable problem. This verification can be done in some special cases by resorting to nilpotent semigroup as proposed in [START_REF] Parriaux | Nilpotent semigroups for the characterization of flat outputs of switched linear and lpv discrete-time systems[END_REF]. From a computational point of view, the complexity of the nilpotent semigroup approach to generate matrices that fulfil (1.8) is polynomial. The definition of nilpotent semigroup is recalled below.

Definition 1.2.3 (Nilpotent semigroup)

A semigroup S is a set together with an associative internal law. A semigroup S with an absorbing element 0 is said to be nilpotent if there exists an integer t ∈ N * such that the internal law applied to any t elements of S is always equal to 0.

The smallest integer t is called the class of nilpotency of S.

Graph Approach to Characterize Flat Outputs

If S is a set of matrices, the associative internal law is the matrix multiplication. Hence, applying the internal law to any t elements of S amounts to performing the product of t matrices of S. The absorbing element is, in this case, the null matrix.

Nilpotent semigroup is also related to simultaneous triangularization. Indeed, from Levitsky's Theorem [START_REF] Radjavi | Simultaneous Triangularization[END_REF], a set of matrices generate a nilpotent semigroup if and only if they are simultaneously triangularizable (see Appendix B) and all of them admit exclusively zero as eigenvalues.

Thus, we have the following theorem recalled from [START_REF] Parriaux | Nilpotent semigroups for the characterization of flat outputs of switched linear and lpv discrete-time systems[END_REF].

: k + r) ∈ Θ r+1 } generates a nilpotent semigroup.
The problem of such an approach lies in that the structure of a semigroup assumes that the matrices involved in the product commute. Hence, Theorem 1.2.2 is more conservative than Theorem 1.2.1. This is precisely the issue regarding Example 1.2.1 with the setting (1.3). Indeed, the set of matrices (1.18) does not generate a nilpotent semigroup, although y k is actually a flat output.

S = {P ρ(k:k+1) = A ρ(k) -B ρ(k) C ρ(k+1) A ρ(k+1) A ρ(k) |ρ(k : k + 1) ∈ Θ 2 } defined in
As a conclusion, the existing methods that apply for LPV systems must consider any realization ρ. Symbolic computation can be a solution. However, the complexity of the algorithms for checking the conditions is either exponential or polynomial but in the latter case, the conditions are more conservative. The purpose of next Section 1.3 is to propose a complementary solution with a graph-oriented approach. Necessary and sufficient conditions will be derived to check whether a given output is flat or not. The corresponding algorithms to check the conditions have the polynomial complexity O(n 3 ).

Graph Approach to Characterize Flat Outputs

As a clue to tackle the problem, we consider the LPV system (1.1) as a particular realization of a linear structured system. A structured linear discrete-time system is a system that admits the form:

Σ Λ : x k+1 = I A x k + I B u k (1.19)
where x k ∈ R n is the state vector and u k ∈ R the input. The matrices I A ∈ R n×n and In particular, in our context, to the entries '1' of the linear structured system Σ Λ are assigned the non-zero (possibly time-varying parameters) of the LPV system (1.1). Thereby, generic flatness for the LPV system (1.1) is equivalent to flatness of the structured system (1.19). Thus, a graph-oriented approach, well dedicated to linear structured systems, can be used to define generic flatness for the LPV system (1.1). It is shown below how the combination of both the algebraic conditions of Theorem 1.2.1 and additional graph-based conditions allows to define a complete and tractable framework to find the flat outputs and to explicit the functions of the state and the input with respect to the flat output in a convenient way. Having in mind this line, the technical developments are now detailed.

I B ∈ R n×1 are

Necessary and sufficient conditions for flatness based on a digraph

A digraph denoted by G(Σ Λ ), associated to the state equations (1.19) of the system Σ Λ describes the dependence relation between the state components and the input. It involves a vertex set V and an edge set E. The vertices represent the state and the input components of Σ Λ whereas the edges model the static or the dynamic relations between these variables. More precisely, V = X ∪ U where X is the set of state vertices defined as X = x 1 , . . . , x n and U is the set of input vertices. In the case under consideration here, that is SISO system, U is a singleton, that is U = {u}. The edge set is

E = E A ∪ E B , with E A = (x j , x i ) |I A (i, j) = 0 and E B = (u, x i ) |I B (i) = 0
where I A (i, j) and I B (i) denote respectively the (i, j)th element of the matrix I A and the ith element of the vector I B . The pair (v i , v j ) denotes a directed edge from the vertex v i ∈ V to the vertex v j ∈ V. The vertex v F will be associated to the flat output.

• A directed path P is a sequence of successive edges directed in the same direction which connect a sequence of vertices. It is said that the path P covers a vertex if this vertex is the begin or the end vertex of one of the edges of P ;

• In a directed path from a vertex v i to a vertex v j , it is said that v j is a successor of v i and conversely, v i is a predecessor of v j ;

• A directed path is simple when every vertex occurs only once in this path;

• The length of a directed path P is equal to the number of the edges involved in P . We denote by (v i , v j ) the minimal length of a path linking v i to v j ;

• V ess (v i , v j
) is the set of vertices, called essential vertices from v i to v j , which are common to all the paths linking v i to v j whenever at least one path exists;

• P red(v F ) (resp. Succ(u))
is the set of all the predecessors (resp. successors) of v F (resp. u).

Graph Approach to Characterize Flat Outputs

Let us recall the necessary and sufficient conditions which must be satisfied by a vertex [START_REF] Bruzelius | Linear Parameter-Varying Systems: an approach to gain scheduling[END_REF]. The extension to any linear combination of x i k and possibly u k is then discussed. Theorem 1.3.1 [START_REF] Boukhobza | Graphical characterization of the set of all flat outputs for structured linear discrete-time systems[END_REF] Consider the structured linear discrete-time system Σ Λ described by (1.19). The output denoted y F associated to a specific vertex v F ∈ X ∪ U is generically a flat output if and only if, in the associated digraph G(Σ Λ ), the following three conditions hold:

x i (i ∈ {1, . . . , n}) or u of the digraph G(Σ Λ ) to be associated to a flat output y F k = x i k (i ∈ {1, . . . , n}) or y F k = u k of (1.
C0. v F is a successor of u; C1.
The length of all the {u}-{v F } simple paths is equal to (u, v F ); C2. All the cycles cover at least an element of V ess ({u}, {v F }).

Proof.

The proof is based on the structural and graphical subdivision of the system Σ Λ into 5 subsets Σ i , i = 0, . . . , 4. The subsets are defined according to their position with regard to the flat output and the input as depicted in Figure 1.1 and defined as follows:

• Σ 0 merges the input vertex u, vertex v F and all the state vertices which are predecessors of v F and which are reachable from u without necessarily covering

v F i.e. the components of Σ 0 are U ∪ {v F } ∪ P red(v F ) ∩ Succ(u) ∩ {v i ∈ X, v F / ∈ V ess ({u}, v i )} ;
• Σ 1 merges all the state vertices which are predecessors of v F and which are reachable from u only by covering v F , i.e. the components of Σ

1 are P red(v F ) ∩ Succ(u) ∩ {v i ∈ X, v F ∈ V ess ({u}, v i )};
• Σ 2 merges all the state vertices which are predecessors of v F but not successors of u i.e. the components of Σ 2 are P red(v F ) \ Succ(u);

• Σ 3 merges all the state vertices which are successors of u but neither predecessors nor successors of v F , i.e. the components of Σ 3 are Succ(u) \ Succ(v F ) ∪ P red(v F ) ;

• Σ 4 merges all the state vertices which are not successors of u, not successors of v F and not predecessors of

v F i.e. the components of Σ 4 are X \ Succ(u) ∪ Succ(v F ) ∪ P red(v F ) .
These vertices can be linked to Σ 2 and Σ 3 .

LPV SYSTEMS AND CHARACTERIZATION OF FLATNESS

u v F X 0 X 1 X 2 X 3 X 4 Σ 0 Σ 1 Σ 2 Σ 3 Σ 4 Figure 1.1: Structural system subdivision of Σ Λ .
Note that this subdivision is unique and is motivated by the fact that it allows to characterize y F as a flat output using the controllability and observability characteristics of each subsystem. Indeed, we can make two important remarks on subsystems Σ 2 and Σ 4 :

Remark 1.3.1 Subsystems Σ 2 and Σ 4 are not forced by the input u. So, it is clear that they don't involve any cycle (equivalently to a memorization operator), their state components will go to zero after a finite transient time. Conversely, if they involve at least one cycle, some of their state components will depend, at time k, on its own past value and so on the initial state value. And yet, the initial state of these subsystems cannot be expressed only as a function of the component associated to v F i.e. y F . Indeed, y F is not sensitive to the state of Σ 4 and since u is an input for Σ 0 , there isn't any equation linking the present, past and future values of y F to the state components of Σ 2 only.

Remark 1.3.2 According to Definition 1.2.1, it is clear that y F associated to the vertex v F is a flat output if and only if:

• The input can be expressed as a function of the past, present, future values of y F by considering simultaneously subsystems Σ 0 and Σ 2 since y F is an output of only these two subsystems;

• There exists an integer k 0 such that for all k ≥ k 0 , all the state components of all the subsystems are either equal to zero or can be expressed as a function of the past, present, future values of y F .

We are now in position of proving the sufficiency and the necessity.

Sufficiency: When Condition C2 is satisfied, there is no cycle in subsystems Σ 2 and Σ 4 . In

Graph Approach to Characterize Flat Outputs

this case and since these two subsystems are not forced by the inputs, after a finite time which is equal to the length of the longest path in these two subsystems, all the state components of these subsystems are equal to zero according to Remark 1.3.1.

Regarding subsystem Σ 0 , the generic dimension of the observability subspace of the structured system Σ Λ , considering that y F associated to v F is the output and that u is unknown, is equal to the length of the shortest {u}-{v F } path plus one i.e. (u, v F ) + 1 [START_REF] Boukhobza | Partial state and input observability recovering by additional sensor implementation: a graph-theoretic approach[END_REF]. Moreover, considering now that y F associated to v F is the output and that u is known, the generic dimension of the observability subspace of the structured system Σ Λ is equal to the longest {u}-{v F } path plus the length of all the disjoint cycles which are not covered by this path. Nevertheless, when Conditions C0, C1 and C2 are valid, the longest {u}-{v F } path is also the shortest {u}-{v F } and there are no cycles that are disjoint with these paths in Σ 0 . Therefore, if Conditions C0, C1 and C2 are satisfied, u can be expressed generically using the present and the past values of y F associated to v F . Furthermore, all the state components of Σ 0 belonging to V ess (U, {v F }) can also generically be expressed using the present and the past values of y F since they are generically observable considering that y F is the output [START_REF] Boukhobza | Partial state and input observability recovering by additional sensor implementation: a graph-theoretic approach[END_REF]. Therefore, substituting the input u and all the state vertices of all V ess (U, {v F }) by their expression in function of y F , there exists a positive constant ν such that the linear structured system Σ Λ can be written as:

Σ Λ : x k+1 = I Ãx k + φ(y F k , y F k-1 , . . . , y F k-ν ) (1.20)
where, as the cycles involve only elements of V ess (U, {v F }), the matrix I Ã is an adjacency matrix for a digraph of a structured system having no cycles. Thus, I Ã is nilpotent and verifies

I n à = 0.
As a result, every state can be expressed as a function of the past, present and future values of y F which is thereby a flat output according to Remark 1.3.2.

Necessity: If Condition C0 is not satisfied, then y F is not sensitive to u. As a result, the input cannot generically be expressed using the past, present and future values of y F and y F cannot be a flat output. Condition C0 is then necessary. Condition C1 is not applicable to subsystems Σ 1 , Σ 3 or Σ 4 . For subsystem Σ 0 , if Conditions C1 or C2 [i.e. if there exist cycles which cover the state components which are not in V ess (U, {v F })] are not satisfied, the generic dimension of the observability subspaces with and without the input knowledge are different. In this case, the input cannot generically be expressed using y F as output. Indeed, if there exist paths u-v F with different lengths 1 = 2 , then the expression of

y F at time k, that is y F k , will involve at least u k-1 and u k-2 .
It is the same when Σ 0 involves a cycle. Therefore, Conditions C1 and C2 are necessary for Σ 0 . Only Condition C2 is applicable to Σ 2 . If it is not satisfied i.e. when there is a cycle in Σ 2 involving a vertex x i , the expression of y F k will always contain at least a term x i k-3 in addition to the u k-. So, it is impossible to express the input using only the past, present and future values of y F , and thus y F is not a flat output. Therefore, Condition C2 is necessary for Σ 2 . Finally, assume that Condition C2 is not satisfied for Σ 1 , Σ 3 or Σ 4 . In such a case, the

LPV SYSTEMS AND CHARACTERIZATION OF FLATNESS

state components of Σ 1 , Σ 3 and Σ 4 respectively depend on their initial state X 1 0 , X 3 0 and X 4 0 . However, neither X 1 0 , X 3 0 nor X 4 0 are function of y F . Therefore, these state components cannot be expressed as a function of exclusively the past, present and future values of y F . As a result, y F cannot be a flat output.

Remark 1.3.3

The conditions of Theorem 1.3.1 are generic. This means that they hold for almost every realization ρ of the corresponding LPV system (1.1). However, for some specific realizations ρ, they do no longer hold. This situation happens for example (and mainly) for the realizations ρ which cancel the weight associated to an edge linking the input to the flat output.

Remark 1.3.4 Conditions C0-C2 of Theorem 1.3.1 can also be used as necessary and sufficient conditions to check if an output y in the form of linear combinations of some x i k

(i ∈ {1, . . . , n}) (and possibly u k ) is flat. Indeed, let us define X L ⊆ X be the set of variables involved in the linear combination under consideration. It suffices to add in the digraph G(Σ Λ ) a fictitious state v n+1 without outgoing edges and with ingoing edges from the vertices v i corresponding to the variables of X L (or X L ∪ U if u k is considered in the linear combination). considered in the linear combination (and y = u if u is considered in the linear combination) is a flat output.

Remark 1.3.5 The computational complexity of the algorithms for checking the conditions is of the same order as the algorithms used for finding successors and predecessors of vertex subsets or for computing maximal linkings and essential vertices in a digraph. Thus, the complexity is polynomial and is

O(n 3 ) [15].

Illustrative examples

Example 1.3.1 Consider the linear discrete-time system of the example discussed in Section 1.1 with the setting (1.3). Its corresponding digraph is depicted in Figure 1.2. The component x 2 is not a flat output. Indeed, Condition C2 is not fulfilled since there is a cycle on v 1 and v 1 does not belong to V ess ({u}, {v 2 }). On the other hand, x 1 is a flat output since all the Conditions C0, C1 and C2 are satisfied. That corroborates the result obtained from the direct approach detailed in Section 1.1.

• u • • v 1 = v F v 2

Graph Approach to Characterize Flat Outputs

path linking u to v 1 . There are two simple paths from u to v 1 of length respectively equal to 2 and 3. Therefore, x 1 cannot be a flat output since Condition C1 is not satisfied. The aim is to know if x 1 is a flat output. Condition C0 is satisfied since there exists a path linking u to v 1 . Moreover, Condition C1 is also satisfied because the two simple paths linking u to v 1 have the same length (u, v 1 ) = 2. On the other hand, Condition C2 is not satisfied because there exists a cycle including v 3 which does not belong to V ess ({u}, {v 1 }). Thus, x 1 is not a flat output. The aim is to know if x 1 is a flat output. Condition C0 is satisfied since there exists a path linking u to v 1 . Moreover, Condition C1 is also satisfied since there is only one simple path linking u to v 1 . Furthermore, Condition C2 is satisfied since the cycles involve v 1 , v 2 and v 3 which are all elements of V ess ({u}, {v 1 }). Thus, x 1 is a flat output.

• u • • • v 1 = v F v 2 v 3
• u • • • v 1 = v F v 2 v 3
• u • • • v 1 = v F v 2 v 3

Connection with the algebraic conditions

The aim of this section is to make the connection between the quantities r (relative degree) and K involved in Theorem 1.2.1 and graph properties of G(Σ Λ ). Regarding r, it will be shown that

LPV SYSTEMS AND CHARACTERIZATION OF FLATNESS

the connection is straightforward. On the other hand, regarding K, making the connection is not trivial. The proofs given below will be based on the same subdivision of the whole set of states into 5 subsets Σ i , i = 0, . . . , 4, as depicted in Figure 1.1.

Proposition 1.3.1 ([34])

The relative degree r of the system

(1.1) is equal to (u, v F ) of G(Σ Λ ).
Proof. From Definition 1.2.2, let us merely consider the subsystem Σ 0 of the subdivision of G(Σ Λ ) depicted in Figure 1.1. Indeed, subsystem Σ 0 directly connects the input u and the vertex v F assigned to the flat output. Then, the result holds as a straightforward consequence of Condition C1 of Theorem 1.3.1.

Proposition 1.3.2 ([34]) When y F

k is a flat output, the integer K involved in Theorem 1.2.1 is generically equal to the maximal path length over all the simple {u}-X paths of G(Σ Λ ).

Proof. First, let us notice that K is equal to the minimal integer such that, for some sufficiently large integer k, the state vector x k can be written as a function of y k-K+r , . . . , y k+r-1 only. Let us denote with d M the maximal path length over all the simple {u}-X paths of G(Σ Λ ). Since the elements of Σ 2 and Σ 4 are not submitted to the input u, they are equal to zero after a finite transient time and thus can always be expressed using y k-1+r , y k+r , y k+1+r ,. . . , y k+d M -1+r . Now, consider the subsystem Σ 0 . Since y F is a flat output, Condition C1 of Theorem 1.3.1 is fulfilled. Thus, the paths between u and v F have the same length which is equal to r, according to Proposition 1.3.1. Hence, u k can be written as a function of y k+1 ,. . . ,y k+r . Thus, every element of Σ 0 can be written as a function of y k ,. . . ,y k+r-1 . Regarding the subsystem Σ 3 , after a finite transient time, its elements can be considered as having only u as input because the state components of Σ 4 go to zero. There is no cycle in Σ 3 because the system being flat, the vertices are not essential. All its state vertices are linked to u through simple paths of lengths less than d M . Thus, the corresponding state components can be written as a function of u k-1 ,. . . ,u k-d M and so, after substituting the expressions of

u k-1 , . . . , u k-d M , as a function y k+1-d M ,. . . ,y k+r-1 .
Finally, let us consider Σ 1 . By the flatness assumption, it does not involve any cycle. Thus, the state components can be expressed as a function of

u k-1 , u k-2 ,. . . u k-d M and so as a function of y k+1-d M ,. . . , y k-1+r . Therefore, K ≤ d M .
On the other hand, since a vertex linked by a path of length d M to u depends on u k+d M -1 , then at least y k+d M -1+r is necessary to express it. Thus, K ≥ d M and finally

K = d M . Remark 1.3.6 If the system (1.1) is of dimension n, the number of vertices of G(Σ Λ ) equals n. It follows, from Proposition 1.3.2, that if y F k is a flat output of (1.1) then the integer K involved in Theorem 1.2.1 is bounded by n.

Graph Approach to Characterize Flat Outputs

Search procedure for flat outputs

Considering the system (1.1), we can sum up the steps to find its flat outputs until the expression of functions F and G of (1.2) as follow:

A ρ(k) = 1 ρ 1 (k) 0 ρ 2 (k) , B ρ(k) = 0 ρ 3 (k) C ρ(k) = 1 0 D ρ(k) = 0.

Search for the flat outputs with the graph-based condition

The graph of the linear structured system associated to the LPV system

(1.3) is given in Fig- ure 1.6. u v 2 v 1

Let us find (if any) the flat outputs of (1.3) by checking the Conditions C0-C2. It follows that :

• x 2 k is not a flat output. Indeed, when considering v 2 , Condition C2 is not satisfied because v 1 does not belong to V ess ({u}, {v 2 }) and there is a cycle that covers v 1 .

• x 1 k is a flat output because, when considering v 1 as output, Conditions C0-C2 are all satisfied.

Find the relative degree r and the quantity K for the flat output

From Proposition 1.3.1, x 1
k being a flat output, the relative degree r of the system (1.21) is given by (u, v 1 ) = 2. From Proposition 1.3.2, K is given by the maximal simple path length between the input and any component of the internal state. Hence, the quantity K equals 2 when considering the path that links u to v 1 .

Find the functions F ρ and G ρ Considering x 1

k as a flat output, it follows that C ρ(k) = 1 0 .

LPV SYSTEMS AND CHARACTERIZATION OF FLATNESS

From the values K = 2 and r = 2, one can compute P ρ(k:k+2) from (1.9). We have that

T 2,0 ρ(k) = C ρ(k+2) • A ρ(k+1) • B ρ(k) = ρ 1 (k + 1) • ρ 3 (k).
and thus

P ρ(k:k+2) = A ρ(k) -T 2,0 ρ(k) -1 B ρ(k) C ρ(k+2) A ρ(k+1) A ρ(k) P ρ(k:k+3) = 1 ρ 1 (k) -(ρ 1 (k + 1)) -1 -(ρ 1 (k + 1)) -1 ρ 1 (k)
Hence, by applying (1.16) one has:

x k =   y k 1 ρ 1 (k) (y k+1 -y k )  
and from (1.17) one has :

u k = 1 ρ 1 (k + 1)ρ 3 (k) y k+2 - ρ 2 (k + 1)ρ 2 (k) ρ 1 (k) (y k+1 -y k )
what gives the expressions of F ρ and G ρ . [START_REF] Kulcsár | Robust inversion based fault estimation for discrete-time LPV systems[END_REF].

Example 1.3.6 Let us consider the discrete-time dynamics of an unbalanced nonlinear dc motor studied in

   θ(k + 1) ω(k + 1) I(k + 1)    =    1 T s 0 p(k) • T s M gl/J 1 -T s b/J T s K/J 0 -T s K/L 1 -T s R/L       θ(k) ω(k) I(k)    +    0 0 T s /L    u k (1.21)
where T s , M, g, l, b, J, K are the parameters of the physical system and p(k) ∈ [0.1, 1] is a scheduling time-varying parameter. The system can be written as an LPV system like (1.1) with state variables

x 1 k , x 2 k and x 3 k respectively corresponding to θ(k), ω(k) and I(k). Letting ρ 0 (k) = 1, ρ 1 (k) = T s , ρ 2 (k) = p(k)T s M gl/J, ρ 3 (k) = 1 -T s b/J, ρ 4 (k) = T s K/J, ρ 5 (k) = -T s K/L, ρ 6 (k) = 1 -T s R/L and ρ 7 (k) = T s /L, one has A ρ(k) =    1 ρ 1 (k) 0 ρ 2 (k) ρ 3 (k) ρ 4 (k) 0 ρ 5 (k) ρ 6 (k)    , B ρ(k) =    0 0 ρ 7 (k)    .
Here, all the parameters ρ i (k) have constant values except ρ 2 (k). In the sequel, to avoid too

Graph Approach to Characterize Flat Outputs

heavy notation, since the first entry 1 of A does not correspond to a physical paramater, we will keep 1 instead of ρ 0 (k) in the subsequent equations.

In the following, we describe the successive steps which define the complete framework, to find the flat outputs and then to explicit the functions F ρ and G ρ characterizing those outputs. The characterization will hold for any parameters, in particular for any values of p(k). This will highlight the relevance of incorporating structural analysis in the complete framework.

v 0 v 3 v 2 v 1
Figure 1.7: Digraph of the linear structured system associated to the LPV system (1.21). The vertex v i , i = 1, 2, 3 is associated to the component x i k of the state x of (1.21) and v 0 is associated to the input u k .

Search for the flat outputs with the graph-based condition

The graph of the linear structured system associated to the LPV system (1.21) is given in Figure 1.7.

Let us find (if any) the flat outputs of (1.21) by checking the Conditions C0-C2. It follows that :

• x 2 k (resp. x 3 k
) is not a flat output. Indeed, when considering v 2 (resp. v 3 ), Condition C2 is not satisfied since v 1 does not belong to V ess ({v 0 }, {v 2 }) = {{v 0 }, {v 3 }, {v 2 }} (resp.

V ess ({v 0 }, {v 3 }) = {{v 0 }, {v 3 }}) whereas there is a cycle on v 1 .

• x 1

k is as flat output because, when considered v 1 as output, Conditions C0-C2 are satisfied.

Find the relative degree r and the quantity K for the flat output

From Proposition 1.3.1, x 1
k being a flat output, the relative degree r of the system (1.21) is given by (v 0 , v 1 ) = 3. From Proposition 1.3.2, K is given by the maximal simple path length between the input and any component of the internal state. Hence, the quantity K equals 3 by considering the path linking v 0 to v 1 .

Find the functions F ρ and G ρ Considering x 1

k as a flat output, it follows that C ρ(k) = 1 0 0 . From the values K = 3 and r = 3, one can compute P ρ(k:k+3) from (1.9). We have that

T r,0 ρ(k) = C ρ(k+3) • A ρ(k+2) ρ(k+1) • B ρ(k) = ρ 1 (k + 2)ρ 4 (k + 1)ρ 7 (k).

LPV SYSTEMS AND CHARACTERIZATION OF FLATNESS

and thus

P ρ(k:k+3) = A ρ(k) -T r,0 ρ(k) -1 B ρ(k) C ρ(k+3) A ρ(k+2) ρ(k) P ρ(k:k+3) =    1 ρ 1 (k) 0 ρ 2 (k) ρ 3 (k) ρ 4 (k) -P 1 (k) -P 2 (k) -P 3 (k)    with P 1 (k) = 1 + ρ 1 (k + 2)ρ 2 (k + 1) + ρ 1 (k + 1) + ρ 1 (k + 2)ρ 3 (k + 1) ρ 2 (k) P 2 (k) = 1 + ρ 1 (k + 2)ρ 2 (k + 1) ρ 1 (k) + (ρ 1 (k + 1) + ρ 1 (k + 2)ρ 3 (k + 1))ρ 7 (k) P 3 (k) = ρ 1 (k + 1) + ρ 1 (k + 2)ρ 3 (k + 1) ρ 4 (k)
Hence, by applying (1.16) one has:

x k = (T r,0 ρ(k-1) ) -1 B ρ(k-1) y k+2 + P ρ(k-1:k+2) (T r,0 ρ(k-2) ) -1 B ρ(k-2) y k+1 + P ρ(k-1:k+2) ρ(k-2:k+1) (T r,0 ρ(k-3) ) -1 B ρ(k-3) y k x k = 1 ρ 1 (k + 1)ρ 4 (k)    0 0 1   yk+2 + 1 ρ 1 (k)ρ 4 (k -1)    0 ρ 4 (k -1) -P 3 (k -1)   yk+1 + 1 ρ 1 (k -1)ρ 4 (k -2)    ρ 1 (k -1)ρ 4 (k -2) ρ 3 (k -1)ρ 4 (k -2) -ρ 4 (k -1)P 3 (k -2) -P 2 (k -1)ρ 4 (k -2) + P 3 (k -1)P 3 (k -2)    y k x k =                y k y k+1 ρ 1 (k) + ρ 3 (k -1)ρ 4 (k -2) -ρ 4 (k -1)P 3 (k -2) ρ 1 (k -1)ρ 4 (k -2) y k y k+2 ρ 1 (k + 1)ρ 4 (k) - P 3 (k -1) ρ 1 (k)ρ 4 (k -1) y k+1 + -P 2 (k -1)ρ 4 (k -2) + P 3 (k -1)P 3 (k -2) ρ 1 (k -1)ρ 4 (k -2) y k               

Conclusion

and from (1.17) one has :

u k = T r,0 ρ(k) -1 y k+3 -C ρ(k+3) A ρ(k+2) ρ(k) x k = 1 ρ 1 (k + 2)ρ 4 (k + 1)ρ 7 (k) y k+3 -    P 1 (k) P 2 (k) + ρ 1 (k + 2)ρ 4 (k + 1)ρ 5 (k) P 3 (k) + ρ 1 (k + 2)ρ 4 (k + 1)ρ 6 (k)    T x k
where 'T' stands for the transpose of the matrix. Finally,

x 1 k =y k x 2 k = y k+1 T s + 1 -T s b/J T s -(2 -T s b/J)T s (K/J) y k x 3 k = J T 2 s K y k+2 -2 T s b J y k+1 -1 + T 2 s p(k + 1)M gl/J + 2 -T s b/J T s /L + T 2 s 2 -T s b/J 2 K/J y k (1.22) (1.23) u k = JL T 3 s K y k+3 -P 1 (k) x 1 k -P 2 (k) + T 3 s K 2 LJ x 2 k + P 3 (k) + T 2 s K J 1-TsR L x 3 k (1.24)
what gives the expressions of F ρ and G ρ .

Conclusion

In this chapter, a mixed algebraic/graph-oriented approach has been proposed to characterize flatness for discrete-time LPV systems. We have derived necessary and sufficient conditions in terms of state space matrices realization of the LPV system. Those conditions allow to give explicitly the functions expressing the state and the input in terms of the flat output. On the other hand, we have considered LPV systems as linear structured systems. Resorting to additional graph-based conditions borrowed from structural analysis, by a (non trivial) combination of both conditions, a complete and tractable framework to find the flat outputs and characterize the flat outputs has been proposed. The use of the algebraic approach only would require an infinite number of numerical tests. Another interesting point of view of this mixed approach is that, it is not only useful to check if a given set of matrices satisfy (1.8), in other words for analysis, but can also be applied to generate matrices that fulfil (1.8), in other words for synthesis. This latter outcome will be central to the design of SSSC for cryptographic purposes as shown in Chapter 2.

Chapter 2

Flat LPV Systems and

Self-Synchronizing Stream

Ciphers

This chapter aims at showing the correspondence between flat LPV systems and Self-Synchronizing Stream Ciphers which belong to one of the class of stream ciphers. Then, we propose a new construction of Self-Synchronizing Stream Ciphers with a more general class than the ones involving T-functions. The construction is based on the mixed algebraic/graph approaches described in Chapter 1. The results in this chapter are published in [START_REF] Dravie | Design of self-synchronizing stream ciphers: a new control-theoretical paradigm[END_REF].

Contents

Introduction

Born from the imagination and intuition of historical strategists, cryptology -etymologically the science of secrecy -owes its longevity to all those who, over the centuries, have discovered new applications and revealed its potential. First reserved for military and diplomatic uses, cryptology has been an integral part of our everyday life since the advent of the Internet. Nowadays, this science of secrecy offers unrivaled opportunities to date. This science can be seen as a fusion of two fields: cryptography and cryptanalysis.

Cryptography is the study and the design of cryptographic algorithms to protect data. The original data to protect, called plaintext, are scrambled by a transmitter that uses cryptographic algorithms and send it through a public channel to a receiver. This latter, when receiving the scrambled data also called encrypted data, needs to recover the plaintext by resorting to reverse operations using also cryptographic algorithms. One says that the emitter encrypts the plaintext by using a cipher that is the encryption algorithm and conversely, one says that the receiver decrypts the encrypted data by using a decipher that is the decryption algorithm.

On the other hand, cryptanalysis is the study of weakness within algorithms that are designed by cryptographers. It involves attackers also called adversaries that try by using among others statistical or algebraic-based theory to break encryption schemes by revealing secret parameters that are used within these schemes.

These two fields can be seen as opposite and at the same time as complementary. Opposite because cryptanalysis breaks what cryptography designs and complementary because they allow each other to perform studies that are performed within these two fields.

Cryptography is used everywhere. People carry on them, without necessarily knowing, many cryptographic devices: mobile phone, smart cards (credit cards, biometric passport, social assurance card, pay-per-view cards), vehicle key start. Download applications on smartphones, software updates are marked with digital signature. Communications between people using Voice over IP or via social networks are encrypted with strong cryptographic algorithms.

Until the middle of the 70's, the only way that allows two entities to communicate securely, by using cryptography means, is to resort to symmetric cryptography. The transmitter uses a secret key that is shared with the receiver. This requires that the two entities need to communicate each other the secret key before initiating the exchange of encrypted data. In the middle of the 70's, Whitfield Diffie and Martin Hellman published a new concept that allows two entities, that never met before, to be able to communicate without sharing a same secret: it was the birth of asymmetric cryptography. Each entity owns a non-secret key called public key from which anybody can send him an encrypted data and a secret key called private key that allows him to decrypt encrypted data he received.

Generalities on Symmetric Cryptography

Any protection of information using cryptography requires either symmetric cryptography or asymmetric cryptography. And for a cryptographic system, it is a priority that one of the following four services should be provided: Confidentiality: guarantees that the content of the message is kept secret and protected against unauthorized release Authentication: guarantees the identity of the emitter of the message Integrity: guarantees that the content of the message to protect has not be altered during the transmission Non-Repudiation: guarantees that the emitter of the message cannot deny sending the message.

In this thesis, we tackle a problem that is related to symmetric cryptographic and that guarantees confidentiality of data: that is the design of so-called Self-Synchronizing Stream Ciphers, that will be developed in Section 2.3. The next section gives a general description on symmetric cryptography.

Generalities on Symmetric Cryptography

When using symmetric cryptography to encrypt or protect data, the quantity of the data, the device to process the cryptographic algorithms and the transmission speed of the encrypted data are a concern. The emergence of asymmetric cryptography in the the 70's with the public key concept may let believe to a regression of the use of symmetric cryptography. But this is certainly not the case. Indeed, architectures for symmetric key cryptographic algorithms are more suitable for hardware implementation, and are used more and more because of the number of devices needing lightweight cryptography increases. We recall the two families of ciphers used in symmetric cryptography.

Block ciphers

Block ciphers are widespread in symmetric cryptography. They operate on blocks of data i.e they can be seen as functions that map a n-bit data to a m-bit data. A block cipher encryption function can be used in a combination way called mode of operation to provide message authentication techniques, data integrity mechanisms, entity authentication protocols. As block cipher, we can mention FEAL [START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF], DES [START_REF]Fips publication 46-3 -Data Encryption Standard[END_REF], AES [START_REF]FIPS publication 197 -advanced encryption standard[END_REF]. We recall some example of mode of operation of block ciphers in Appendix A.1.

Stream ciphers

Stream ciphers are based on the so-called Vernam cipher where the plaintext (a binary string of some length) is bitwise added to a (binary) secret key of the same length, in order to produce

FLAT LPV SYSTEMS AND SELF-SYNCHRONIZING STREAM CIPHERS

the ciphertext. The Vernam cipher is also called the one-time-pad because a new random secret key must be used for every encryption.

For a stream cipher, it must be given an alphabet A, that is, a finite set of basic elements named symbols. Hereafter, the index k will stand for the discrete-time. On the transmitter side, a plaintext (also called information or message) m ∈ M (M is the message space) consisting of a string of symbols m k ∈ A is encrypted according to an encryption function e which depends on a so-called running key (also called keystream) z k which is invertible for any prescribed z k . Hence, the ciphering is performed with

c k+b = e(z k+b , m k ) (2.1)
where e is the ciphering function, m k is the plaintext symbol and c k ∈ B is the ciphertext symbol which belongs to an alphabet B usually (and assumed hereafter) identical to A. The integer b ≥ 0 stands for a potential delay between the plaintext m k and the corresponding ciphertext c k+b . This is explained by computational reasons, for instance pipelining (see [START_REF] Daemen | The self-synchronizing stream cipher mosquito: estream documentation, version 2[END_REF] for instance). Consequently, for stream ciphers, the way how to encrypt each plaintext symbol changes on each iteration. The resulting ciphertext c ∈ C (C is called the ciphertext space), a string of symbols c k , is conveyed through a public channel to the receiver. At the receiver side, the ciphertext c is decrypted according to a decryption function d which depends on the running key ẑk . The decryption function d obeys the following rule. For any two keystream symbols z k+b , z k+b , it holds that mk+b := d(c k+b , z k+b ) = m k whenever ẑk+b = z k+b .

(2.2)

From (2.
2), it is clear that, beyond the equality of the secret keys, the running keys z k and ẑk must be synchronized for a proper decryption. The distinct classes of stream ciphers differ from each other by the way on how the keystreams are generated and synchronized. The generators delivering the keystreams will be parametrized by a secret key denoted in the sequel by θ.

Synchronous Stream Ciphers

Synchronous Stream Ciphers admit the equations:

         q k = σ s (q k-1 ) z k = s(q k ) c k = e(z k , m k ) (2.3)
where σ s is the next-state transition function, s acts as a filter and generates the keystream z k . The value q k is the internal state of the cipher whose initial value is generated from a secret key. This nonce is generated by applying a key scheduling process or a Linear Feedback Shift

Generalities on Symmetric Cryptography

Register.

Among the huge variety of synchronous stream ciphers that exist, we can mention RC4, SOSEMANUK [START_REF] Berbain | Sosemanuk, a fast softwareoriented stream cipher[END_REF], GRAIN [START_REF] Hell | Grain: a stream cipher for constrained environments[END_REF], TRIVIUM [START_REF] De | Trivium: A stream cipher construction inspired by block cipher design principles[END_REF].

Self-Synchronizing Stream Ciphers

Self-Synchronizing Stream Ciphers admit the equations:

   z k = σ ss θ (c k-l-M +1 , . . . , c k-l ) c k = e(z k , m k ) (2.4)
where σ ss θ is the function that generates the keystream z k ; l is a non-zero positive integer standing for a possible delay. The keystream generator σ ss θ depends on past values of c k . The number of past values is most often bounded and equals M , the delay of memorization. Equation 2.4 is also known as the canonical form of the SSSC and is illustrated by Figure 2.1. To decrypt a ciphertext c k and recover the right plaintext, it is necessary to have the right past previous M ciphertexts. Hence, there is a synchronization delay that is exactly M . The decipher equation is then given by:

m k c k m k e e z k z k σ ss θ σ ss θ . . . . . . c k-1 c k-M c k-1 c k-M . . . . . .
   z k = σ ss θ (c k-l-M +1 , . . . , c k-l ) m k = e(z k , c k ) (2.5)
The transmission of encrypted data through free-error channel are the ideal solution when dealing with cryptographic protocols. However, it is difficult to have in reality such a channel, and transmissions of ciphertexts are subject to errors such as bit tampering, bit insertion or deletion. When faced to bit tampering, synchronous stream cipher can be used without need of additional synchronization protocol, since a 1-bit error in the ciphertext will result in 1-bit error in the recovered plaintext. However, this problem is catastrophic to block cipher that handle data which are sequence of bits. On the other hand, insertion or deletion of one bit of the ciphertext make a loss of synchronization both for block cipher and synchronous stream cipher. The use of SSSC when facing this situation allows automatic resynchronization after a

FLAT LPV SYSTEMS AND SELF-SYNCHRONIZING STREAM CIPHERS

transient time, without the use of any synchronization mechanism.

We can summarize advantages of SSSC as :

• if a ciphertext is deleted, inserted or flipped, the SSSC will automatically resume proper decryption after a short, finite and predictable transient time. Hence, SSSC does not require any additional synchronization flags or interactive protocols for recovering lost synchronization

• the self-synchronizing mechanism also enables the receiver to switch at any time into an ongoing enciphered transmission

• any modification of ciphertext symbols by an active eavesdropper causes incorrect decryption for a fixed number of next symbols. As a result, an SSSC prevents active eavesdroppers from undetectable tampering with the plaintext: message authenticity is guaranteed

• Finally, since each plaintext symbol influences a fixed number of following ciphertexts, the statistical properties of the plaintext are thereby diffused through the ciphertext. Hence, SSSC are very efficient against attacks based on plaintext redundancy and the property of diffusion is structurally fulfilled.

We detail in the next section the different architecture related to Self-Synchronizing Stream Ciphers.

Architectures of Self-Synchronizing Stream Ciphers

The defining property of self-synchronizing stream encryption is that a keystream bit depends on a limited number M (the memory) of past keystream bits, and hence it suffices to have received the last M + 1 ciphertext bits to correctly decrypt the current ciphertext bits. A first architecture calls for a block cipher (AES,DES) in a 1-bit CFB mode (see Figure A.3) as illustrated in Figure 2.2. As alternative to the SSSC architecture in CFB mode, U. Maurer proposed in [START_REF] Ueli | New approaches to the design of self-synchronizing stream ciphers[END_REF] several design approaches for SSSC based on automata. The design replaces the shift register in CFB mode based SSSC with serial and parallel combination of automata where each automaton consists on a function associated to a shift register of reduced size (see Figure 2.3). This architecture had led to the first one with finite state machine instead of simple shift register, that provides secure and high speed SSSC.

Architectures of Self-Synchronizing Stream Ciphers

+ c k m k z k Block Cipher (E k ) h . . . Shift register . . .

FLAT LPV SYSTEMS AND SELF-SYNCHRONIZING STREAM CIPHERS

Later, Daemen and al. in [START_REF] Daemen | On the design of high speed selfsynchronizing stream ciphers[END_REF] proposed another design based on the approach of Maurer where the use of serial and parallel automata had been lighten in structure involving boolean functions. In their design each component of the internal state is defined as a function of previous components; the first component being defined as the last ciphertext generated by the cipher. This gives rise to the so called Conditional Complementing Shift Register that was used to design the SSSC called KNOT. The architecture of KNOT [START_REF] Daemen | On the design of high speed selfsynchronizing stream ciphers[END_REF] is implemented in a pipelined block cipher construction as a number of relatively simple rounds, called stages. This architecture allows very high speed encryption for hardware. In [START_REF] Joux | Loosening the KNOT[END_REF], it had been shown that KNOT presented some weaknesses that have been eliminated by improving it in a new SSSC called ΥΓ. We can also mention other known SSSCs that admit a similar architecture: HBB [START_REF] Sarkar | Hiji-bij-bij: A new stream cipher with a self-synchronizing mode of operation[END_REF], SSS [START_REF] Hawkes | Primitive specification for sss[END_REF] and the family of MOUSTIQUE [START_REF] Daemen | The self-synchronizing stream cipher mosquito: estream documentation, version 2[END_REF][START_REF] Daemen | The self-synchronizing stream cipher moustique[END_REF]. They are described in Appendix A.2.

The resulting updating functions of all those constructions of SSSC were T-functions (see Subsection 2.3.2) or conditionally complementing shift registers (as in MOUSTIQUE).

The keystream bit is computed as a Boolean function of these statebits, possibly making use of pipelining (effectively adding bits to the internal state). This architecture guarantees that the keystream bit is completely determined by the previous M ciphertext bits. The situation of these architectures does not look very good as all concrete proposals have been broken and for the moment there is not a single unbroken dedicated self-synchronizing stream cipher. This motivates further investigations as proposed here.

Keystream generators for Self-Synchronizing Stream Ciphers

A well-admitted approach to generate the keystreams has been first suggest in [START_REF] Ueli | New approaches to the design of self-synchronizing stream ciphers[END_REF]. It is based on the use of state automata with finite input memory. This is typically the case in the cipher MOUSTIQUE [START_REF] Daemen | The self-synchronizing stream cipher moustique[END_REF]. At the ciphering side, the automaton delivering the keystream takes the form:

q k+1 = g θ (q k , c k+b ) z k+b = h θ (q k ) (2.6)
where q k is the internal state. As previously stressed, the delay b is due to the fact that the output (also called filtering) function h is pipelined with an a architecture involving b layers.

Architectures of Self-Synchronizing Stream Ciphers

m k c k m k e e -1 z k z k g θ g θ h θ h θ q k q k Figure 2.4: Automata architecture of SSSC.
If such an automaton has a finite input memory, it means that by iterating (2.6) a finite number of times, there exists a function l θ and a finite integer M such that

q k = l θ (c k+b-1 , . . . , c k+b-M ) (2.7)
and thus

z k+b = h θ (l θ (c k+b-1 , . . . , c k+b-M )) (2.8)
Actually, the fact that the keystream symbol can be written in the general form involving a function σ ss θ

z k+b = σ ss θ (c k-l , . . . , c k-l ) (2.9)
is a common feature of all the SSSC. The quantities l and l are integers in Z. Equation (2.9) is the canonical equation.

Remark 2.3.1

The outcome of implementing the recursive form (2.6) instead of directly implementing the canonical form (2.9) is that we can obtain complex nonlinear functions σ ss θ by implementing simpler nonlinear functions g θ . The complexity results from the successive iterations which act as composition operations.

At the deciphering side, the automaton takes the form:

q k+1 = g θ ( q k , c k+b ) z k+b = h θ ( q k ) (2.10)
where q k is the internal state. Following the same reasoning, since g θ corresponds to the state transition function of an automaton with finite input memory, it is clear that after a transient time of maximal length equal to M , it holds that, for k ≥ M ,

q k = q k and z k+b = z k+b (2.11)

FLAT LPV SYSTEMS AND SELF-SYNCHRONIZING STREAM CIPHERS

Hence, since the generators synchronize automatically after at most M iterations, the decryption is automatically and properly achieved after at most M iterations too. No specific synchronizing protocol between the cipher and decipher is needed. This explains the terminology Self-Synchronizing Stream Ciphers. The quantity M is called the synchronization delay.

To obtain a finite input memory feature, the solutions proposed in the open literature (see [START_REF] Daemen | Cipher and Hash function design, strategies based on linear and differential cryptanalysis[END_REF] for example), call for state transition functions g θ in the form of shifts or T -functions (T for Triangle), which are functions that propagate dependencies in one direction only. One of the aim of this thesis is to show that it is possible to construct automata with finite input memory and state transition functions that admit a more general form than T -functions and to provide a systematic methodology of construction. The construction is based on the property of flatness, a structural property borrowed from control theory. This property is considered for the class of Linear Parameter-Varying (LPV) systems as motivated in Section 2.3.3.

Strict T-function

Design of SSSC which next state function are not strict T-function [START_REF] Klimov | New cryptographic primitives based on multiword t-functions[END_REF] remains a challenge. In [START_REF] Millérioux | Self-synchronizing stream ciphers and dynamical systems: state of the art and open issues[END_REF], the authors established promising new ideas regarding the design of a new class of SSSC with a more general state resursive form (2.6). These ideas have been widely developed in Parriaux's Thesis [START_REF] Parriaux | Control, synchronization and encryption[END_REF] and led to a new design of SSSC. An effective construction of this class based on nilpotent semi-group approach had been proposed in [START_REF] Parriaux | Designing self-synchronizing switched linear systems: an application to communications[END_REF]. An interesting classification of SSSC has been also established, showing that the next state function of an SSSC belongs to three categories of function:

1. strict T-functions 2. conjugate of strict T-functions

functions not based on strict T-functions

For T-functions, each variable depends only on previous variables. Hence, the function in (2.6) and (2.10) g θ : F n+1 → F n is a strict T-function if the output of its coordinate function g j θ depends only on the j + 1 variables c k+b and q i k , i = 0, . . . , j -1:

g θ (q k , c k+b ) =          g 0 (c k+b ) g 1 (q 0 k , c k+b ) g 2 (q 0 k , q 1 k , c k+b ) . . . g n-1 (q 0 k , q 1 k , . . . , q n-2 k , c k+b )          (2.12)
T-functions are in general functions where the only Boolean operations are bit-oriented operations (additions, multiplications, subtractions, xor, or, and) and for which right shifts1 or rotate operations are excluded.

Architectures of Self-Synchronizing Stream Ciphers

The aim of the next section is to show that it is possible to design SSSC without T-functions when considering LPV systems as automata.

Particular case of LPV systems

The next proposition is essential to establish the correspondence between flat LPV systems and SSSC and is a central point to show that we can design a new architecture of SSSC.

Proposition 2.3.1 ([36]

) If the LPV system (1.1) has relative degree r and is flat, then the finite state automata given by

       q k+1 = P ρ(k:k+r) q k + B ρ(k) (T r,0 ρ(k) ) -1 y k+r z k+r = C ρ(k+r) k l=k+r-1 A ρ(l) q k (2.13)
along with

y k+r = z k+r + T r,0 ρ(k) u k (2.14) and        q k+1 = P ρ(k:k+r) q k + B ρ(k) (T r,0 ρ(k) ) -1 y k+r z k+r = C ρ(k+r) k l=k+r-1 A ρ(l) q k (2.15)
along with gives respectively the encryption and decryption functions.

u k+r = (T r,0 ρ(k) ) -1 (
The following correspondences hold:

• u k plays the role of m k (plaintext symbol) • y k plays the role of c k (ciphertext symbol) • z k+r = C ρ(k+r) k l=k+r-1
A ρ(l) q k is the keystream symbol of the cipher

• z k+r = C ρ(k+r) k l=k+r-1
A ρ(l) q k is the keystream symbol used for deciphering.

FLAT LPV SYSTEMS AND SELF-SYNCHRONIZING STREAM CIPHERS

• r plays the role of b (delay)

• the function (z k+r , u k ) → z k+r + T r,0 ρ(k) u k plays the role of e (encryption function)

• the function ( z k+r , y k+r ) → (T r,0 ρ(k) ) -1 (y k+r -z k+r ) plays the role of d (decryption function)

• K plays the role of M (synchronization delay).

The nonlinearity is obtained by defining the values of the varying parameters ρ i (k) as nonlinear functions of the output y k (or a finite number of shifts), implemented in the form of so-called S-Boxes The next state transition function g θ is not conjugated to a strict T-functions if the matrix P ρ(k:k+r) is not triangular. However, as stressed in Subsection 1.2.3, verifying and choosing non triangular matrices fulfilling (2.13) ( or also (1.8)) is an intricate problem which is closely related to the notion of mortality. Furthermore, the problem under consideration here is more intricate since the matrices P ρ(k:k+r) are not given but should be chosen. In other words, we are not concerned with analysis but with synthesis. The method proposed here, that is the design a flat LPV system (1.1) followed by deriving the automaton (2.13) (which will be, because of its flatness property, with finite input memory and so self-synchronizing) constitutes an efficient alternative to a very challenging direct design of the automaton (2.13). This approach is new in cryptography and provides a general framework. However, from a control theory point of view, the issue of designing a flat LPV system is a new paradigm. Indeed, in automatic control, we are usually given a system and we have to check whether a system is flat or not and to check for the flat outputs.

ϕ i : ρ i (k) = ϕ i (y k , y k-1 , • • • ) Remark 2.
The aim of the next section is to show that, using the graph approach, developed in Section 1.3 of Chapter 1, we can design SSSC based on flat LPV system. It is worth pointing out that those graphs are considered in the case where the relative degree of the LPV system is greater or equals 2. When r = 1 the only graphs that we can obtain correspond to systems whose next state functions are strict T-functions or conjugates of a strict T-function.

Construction of SSSC Based on Digraph

Construction of SSSC Based on Digraph

In this section, we tackle the problem of construction of SSSC by applying results that were developed in Chapter 1 and having in mind the correspondence between SSSC and LPV systems as shown in Subsection 2.3.3. More, we aim at designing a new class of SSSC where the state transition matrices P ρ are not conjugated to a T-function.

Construction of flat LPV systems

Conditions C0-C2 are instrumental for the construction of flat dynamical systems. Indeed, a systematic construction of digraphs fulfilling C0-C2 can be derived. It had been published in [START_REF] Dravie | Design of self-synchronizing stream ciphers: a new control-theoretical paradigm[END_REF] and is detailed below.

A digraph is parametrized by the triplet (n, r, n a ). The dimension n of the system (1.1) corresponds to the number of vertices of the graph minus one (the vertex assigned to the input). The relative degree r fulfilling (1.6) gives the number of edges in the main direct path. The integer n a defines the number of edges in the digraph G(Σ ρ ) and can be freely chosen provided it is less than the maximal number n M of edges. The expression of n M depends on the construction and thus, will be given later on. The proposed construction of the digraph involves the following steps.

Step 1: The digraph G(Σ ρ ) corresponding to the system Σ ρ of dimension n involves n + 1 vertices. The input is assigned to the vertex denoted by v 0 . The other n vertices are denoted by v 1 , . . . , v n . We want v r to be the vertex that corresponds to the flat output.

Step 2: Add the edges (v i , v i+1 ) with i = 0, . . . , r -1. The relative degree being r, there must have r edges which link v 0 to v r . The resulting path will be called main direct path. After Step 2, Conditions C0-C2 are fulfilled for v F = v r and the resulting digraph is depicted in Figure 2.5. However, the corresponding dynamical system is quite trivial. The following steps provide a way of adding edges (v i , v j ) while guaranteeing that Conditions C0-C2 are still fulfilled.

v 0 v 1 v 2 v r-1 v r v i v n
Step 3: Add the edges (v i , v i+1 ) for i = r, . . . , n -1 to avoid the situation with a vertex v j , j = r + 1, . . . , n without predecessor. Indeed, if so, the dynamics of the corresponding vertex v j would reduce to x j k+1 = 0 and clearly would be useless.

Step 4: Add the edges that link the vertex v r to any of the vertices of the graph (except the vertex related to the input), that is the edges (v r , v i ), i = 1, . . . , n.

FLAT LPV SYSTEMS AND SELF-SYNCHRONIZING STREAM CIPHERS

Step 5: Consider the vertices v i i = 1, . . . , r -1, as starting vertices. For every vertex v i , i = 1, . . . , r -1, add the directed edge (v i , v j ) with j = 1, . . . , i. Note that those edges introduce cycles, including cycles of order 1, but those cycles satisfy Condition C2 since v i , i = 0, . . . , r -1 belong to V ess (u, v r ).

The graph obtained after Steps 1-5 is depicted in Figure 2.6. Step 6: Consider the vertices v i , i = r + 1, . . . , n. For every vertex v i , i = r + 1, . . . , n, add the directed edge (v i , v j ) with j = 1, . . . , r and j = i + 2, . . . , n. Let us notice that this step generates cycles but Conditions C2 is still satisfied.

v 0 v 1 v 2 v r-1 v r v r+1 v i v n
The resulting digraph after completion of Steps 1-6 is depicted in Figure 2.7. A simple counting leads to the maximal number of edges n M that can be added by following the construction at Steps 1-6. One has:

v 0 v 1 v 2 v r-1 v r v r+1 v i v n
n M = n • (n + 1) 2 + r.
(2.17)

The number of edges n a of the triplet (n, r, n a ) must satisfy n a ≤ n M .

Step 7: Remove n M -n a edges. Insofar as Steps 1-6 guarantee that Conditions C0-C2 are fulfilled regardless whether the edges are actually added or not, Conditions C0-C2 are still preserved after arbitrarily removing edges of the graph.

Completion of the design

Let G(Σ ρ ) be a digraph characterized by the triplet (n, r, n a ). We can derive the matrices I A and I B of the structured linear system G(Σ Λ ), from the adjacency matrix. The adjacency matrix, denoted with I, of the digraph G(Σ ρ ), is the (n + 1) × (n + 1) matrix whose each entry (a) ij is defined as follows for 1 ≤ i, j ≤ n (a) ij = 1 if there exists an edge from v j to v i 0 otherwise (2.18)

Hence, the adjacency matrix associated to G(Σ ρ ) is given by:

I =       0 I T B 0 I T A . . . 0       (2.19)
where I T A and I T B stand respectively for the transpose of I A and I B . The varying parameter ρ 4 (k) is in practice implemented in the form of a so-called S-Box whose entry is the flat output y k and possibly a finite number of backwards iterates. By construction, any nonlinearity would lead to a flat LPV system and so to an SSSC. The approach proposed here gives thereby a family of SSSC. The design of a specific SSSC is completed by deriving the equations of Proposition 2.3.1. Actually, it can be shown (see next subsection) that even for this simple example, the state transition matrix P ρ(k:k+2) is non triangular, which corroborates that this method allows to provide a novel class of SSSC. Furthermore those SSSC are really simple to build owing to the graph approach associated to LPV system.

Basic construction of a flat LPV-based SSSC

We now show that an SSSC involving state transition functions more general than T -functions can be obtained even in a very simple case. Let us consider the graph depicted in Figure 2.8 which results from the construction given in the Subsection 2.4.1 for n = 2 and n a = n M = 5 (maximal number of edges) and r = 2. The relative degree r being equal to 2, it means that the component x 2 of the state vector of the corresponding LPV system (1.1) will be the flat output y k , that is the ciphertext. Hence, C ρ(k) = C = [0 1] and D ρ(k) = 0. The adjacency matrix I of this graph and the structured matrices I A and I B are

FLAT LPV SYSTEMS AND SELF-SYNCHRONIZING STREAM

CIPHERS v 0 v 1 v 2
I =    0 1 0 0 1 1 0 1 1    , I A = 1 1 1 1 , I B = 1 0 (2.20)
Each of the entries of I A and I B can be potentially replaced by a realization ρ i (k) to construct the matrices A ρ(k) and B ρ(k) of (1.1). Let us choose the functions ρ i i = 1, 2, 3 of the first three entries of A equal to 1. This finally leads to the following matrices A ρ(k) and B ρ(k) :

A ρ(k) = 1 1 1 ρ 4 (k) and B ρ(k) = B = 1 0
As stressed in Section 1.1, the varying parameter ρ 4 (k) is the output of an S-Box whose entry is the flat output y k and possibly a finite number of backwards iterates.

To complete the design of the decipher (see (2.13) of Proposition 2.3.1), let us calculate the matrix P ρ(k) (1.9) governing the state transition function of the automaton (2.13). One has

P ρ(k:k+2) = A ρ(k) -B • C • A ρ(k+1) • A ρ(k) . One obtains P ρ(k:k+2) = -ρ 4 (k + 1) -ρ 4 (k) • ρ 4 (k + 1) 1 ρ 4 (k)
Let us point out that (1.8) holds for K = 2. Indeed, it's a simple matter to see that P ρ(k+1:k+3) P ρ(k:k+2) = 0. It corroborates that y k is a flat output (but it is, by construction of the digraph).

It remains to show that the matrix P ρ(k:k+2) is not conjugate to a shift or to a T -function.

To this end, it must be shown that the matrices P ρ(k:k+2) , for almost every realization ρ, cannot be simultaneously triangularizable. The characteristic polynomial of P ρ(k:k+2) is given by N (X) = X X + (ρ 4 (k + 1) -ρ 4 (k)) . Hence, the eigenvalues of P ρ(k:k+2) are 0 and ρ 4 (k) -ρ 4 (k + 1). It follows that the related eigenspace to the eigenvalues of P ρ(k:k+2) is spanned by:

V 1 = -ρ 4 (k) 1 and V 2 = -ρ 4 (k + 1) 1
And yet, a necessary condition for simultaneous triangularization (see Theorem B.1.2) is that the matrices P ρ(k:k+2) share a common eigenvector for any realization ρ. As a result, if the

Construction of SSSC Based on Digraph

parameter ρ 4 (k) varies, the matrices P ρ(k:k+2) do not fulfill such a requirement. Clearly, even in this very trivial example, we have shown that an SSSC with state transition function different from a T -function can be obtained. Let us notice that the graph approach that is proposed here provides T-function-based next-state transition function when the relative degree r of the LPV system equals 1.

The next-state function g θ of a LPV-based SSSC is a T-function if and only if the inverse transition matrix P ρ(k:k+r) is triangular. One has:

q i k+1 = g i θ (q k , c k ) = P ρ(k:k+r) [i] • q k + δ i r c k
where δ i r equals 1 if r = i and 0 if r = i. P ρ(k:k+r) [i] denotes the i th row of the matrix P ρ(k:k+r) . It follows that the output of each g i θ (c k , q k ), i = 1, . . . , n depends only on q 0 k , . . . , q i-1 k if and only if P ρ(k:k+r) is a triangular matrix. Proof. From (1.9), if r = 1, it follows that:

P ρ(k:k+1) = A ρ(k) -(T 1,0 ρ(k) ) -1 B ρ(k) C ρ(k+1) A ρ(k) .
As a consequence, the rows of P ρ(k:k+1) are the same as the ones of A ρ(k) except the first row which coefficients are zero:

P ρ(k:k+1)) =          0 0 • • • 0 a 21 a 2,2 • • • a 2,n a 31 a 3,2 • • • a 3,n . . . a n1 a n,2 • • • a n,n          with A ρ(k) = (a i,j ) 1≤i,j≤n .
Each vertex v i is associated to the component x i . Since r = 1, according to the graph construction of Subsection 2.4.1, the only possible edges in the graph G(Σ ρ ) are the ones that start from v 1 or end at v 1 , and those that starting from each vertex towards its following vertices. Thus, G(Σ ρ ) has the form:

FLAT LPV SYSTEMS AND SELF-SYNCHRONIZING STREAM CIPHERS

u v 1 v 2 v 3 v n Figure 2
.9: Graph construction related to a flat LPV system of relative degree r = 1.

It follows then that the reduced (n -1) × (n -1) matrix obtained by removing the first row of A ρ(k) is strictly lower triangular: that is P ρ(k:k+1) is strictly lower triangular.

We give in the next section, a more general example of matrix P ρ that is not conjugated to a T-function. To show that, we use Algorithm 1 known as Simultaneous Triangularization Algorithm (STA) provided in [START_REF] Dubi | An algorithmic approach to simultaneous triangularization[END_REF].

Examples of construction of LPV-based SSSC without T-functions 2.5.1 Example 1

Let us consider the graph of Figure 2.8, we give an example of matrix A ρ(k) with non-constant coefficients in a finite field F = GF [START_REF] Boukhobza | Graphical characterization of the set of all flat outputs for structured linear discrete-time systems[END_REF]. The state matrix A ρ(k) related to this graph is a matrix of dimension 2 given by

A ρ(k) = ρ 1 (k) ρ 2 (k) 1 ρ 3 (k)
where

ρ i (k) : GF(16) s -→ GF(16) c k-1 , . . . , c k-s → y k
is assumed to be a surjective non-linear function. The inverse transition matrix P ρ(k:k+2) (1.9) that characterizes the decryption and then the self-synchronization property, is given by

P ρ(k:k+2) = A ρ(k) + B • C • A ρ(k+1) • A ρ(k)
Then, the rows of the matrix P ρ(k) are inferred as

P ρ(k:k+2) [1] = A ρ(k) [1] + A ρ(k+1) • A ρ(k) [2] P ρ(k:k+2) [2] = A ρ(k) [2]
Hence,

Examples of construction of LPV-based SSSC without T-functions

P ρ(k:k+2) = ρ 3 (k + 1) ρ 3 (k) • ρ 3 (k + 1) 1 ρ 3 (k)
Since, ρ 3 (k) is surjective, we can assume that, after a long transient time, P ρ(k:k+2) takes all the value in GF [START_REF] Boukhobza | Graphical characterization of the set of all flat outputs for structured linear discrete-time systems[END_REF]. Thus we need to find two instances of P ρ(k:k+2) that are not simultaneous triangularizable to prove that P ρ(k:k+2) is not simultaneous triangularizable regardless to ρ(k).

Let

A 1 = α 3 + 1 α + 1 1 α 2 + α A 2 = α 2 + α + 1 α 3 + α 2 + 1 1 α 3
We use a primitive element of GF( 16) given by α with α 4 = α + 1. The matrix A 1 is obtained by considering ρ 3 (k) = α 2 + α, ρ 3 (k + 1) = α 3 + 1 and the matrix A 2 is obtained for ρ 3 (k) = α 3 , ρ 3 (k + 1) = α 2 + α + 1. We show that A 1 and A 2 are not simultaneous triangularizable. Note that we need to iterate the STA (see Algorithm 1 of Appendix B) until we find no common eigenvectors for A 1 and A 2 . The example is minimalist due to the considered graph. For i = 1, 2, we denote by P Ai (X) the characteristic polynomial, Sp(A i ) the spectrum and V(A i ) the eigenvectors of A i .

• Compute the eigenvectors of A

1 : P A1 (X) = X(X + α 3 + α 2 + α + 1). Then Sp(A 1 ) = {0, α 3 + α 2 + α + 1} and V(A 1 ) = λ 1 α 2 + α 1 , λ 2 α 3 + 1 1 λ 1 , λ 2 ∈ GF(16)
• Compute the eigenvectors of A 2 : P A2 (X) = X(X + α 3 + α 2 + α + 1). Then Sp(A 1 ) = {0, α 3 + α 2 + α + 1} and

V(A 2 ) = λ 3 α 3 1 , λ 4 α 2 + α + 1 1 λ 3 , λ 4 ∈ GF(16)
It follows that A 1 and A 2 do not admit any common eigenvector. As a conclusion the transition function related to the LPV-based SSSC is not conjugate to a T-function.

Example 2

The following example is to show how we can apply the STA algorithm 1 on a set of matrices P ρ(k:k+r) , obtained from a graph that generates a flat system, to show that the set is not simultaneous triangularizable. For that, we show that there exist two instances of P ρ(k:k+r) , that do not have a common eigenvector. The LPV system is of dimension n = 6, relative degree r = 3. The matrix P ρ(k:k+3) is obtained from the graph on Figure 2.10. For each k ∈ N, the entries of P ρ(k:k+3) are given by polynomials ϕ j i : F s -→ F, with F = GF [START_REF] Boukhobza | Graphical characterization of the set of all flat outputs for structured linear discrete-time systems[END_REF]. The expression of P ρ(k:k+3) is given by: As ϕ j i take its values in F, it suffices to produce two instances of P (ρ:k+6) and show that these two instances do not share a common vector. For example, consider the following two instances of P (ρ:k+6) :

FLAT LPV SYSTEMS AND SELF-SYNCHRONIZING STREAM CIPHERS

P ρ(k:k+6) =            ϕ 1 1 ϕ 2 1 ϕ 3 1 ϕ 4 1 ϕ 5 1 ϕ 6 1 1 ϕ 2 2 ϕ 3 2 0 ϕ 5 2 ϕ 6 2 0 1 0 ϕ 4 3 ϕ 5 3 ϕ 6 3 0 0 ϕ 3 4 ϕ 4 4 0 0 0 0 0 ϕ 4 5 0 0 0 0 0 ϕ 4 6 ϕ 5 6 0            v 0 v 1 v 2 v 4 v 5 v 6 v 3
P ρ(k1) =    α 3 +1 0 α 3 +α 2 +α+1 α+1 α 2 α 3 +α 2 +α 1 α 3 +1 1 0 α 3 +α 2 +α 0 0 1 0 α 2 +α α 3 +α 2 α 3 +α 2 +1 0 0 α 0 0 0 0 0 0 α 3 +α 2 +1 0 0 0 0 0 0 α+1 0    and P ρ(k2) =     α 3 +α 2 +α+1 α 3 α 3 +α 2 +α+1 α 3 +α+1 1 α 2 1 α 2 +α+1 α 3 +α 2 +1 0 α 3 +α 2 +α 0 0 1 0 α 3 +α 2 +α+1 α 2 +α α 3 +α 2 +1 0 0 α 2 0 0 0 0 0 0 α+1 0 0 0 0 0 α 2 α 2 +α+1 0    
it can be checked that the only eigenvalue of P ρ(k1) is zero which eigenspace is spanned by the vector v = (1, α, 0, 0, 0, α 3 ). But v is not an eigenvector of P ρ(k2) . Indeed, P ρ(k2) × v = (α 3 + α, α 3 + α 2 + α + 1, 0, 0, 0, 0). The characteristic polynomial of the matrix P ρ(k2) is not split on F and its eigenvalues belong to an extension of F.

Test platform and specifications

The graph approach used to derive a flat LPV system provides a convenient way to design an SSSC with arbitrary size of the internal state. Let us recall that the size of the SSSC internal state is the dimension n of the LPV system. From a practical point of view, a large dimension must be chosen to allow a sufficiently complex architecture for the sake of security. The proposed graph-based approach is well suited to deal with high dimensions. The dimension n = 40, which is compatible with security issues has been tested with success on an arduino MEGA 2560 card (see Figure 2.12). Indeed, as the internal state components are 4-bit size, a dimension 40 would provide a security level of 80 bits against time-memory trade-off attack. The relative degree is given by r = 3. The choice of the value of the relative degree r is such that, the powers of the matrix P ρ(k:k+r) offer a good diffusion delay. By definition the least value s 0 such that the matrix P s0 ρ(k:k+r) does not have any zero coefficient is called diffusion delay 2.6 Test platform and specifications [4,[START_REF] Thierry | Extended generalized Feistel networks using matrix representation[END_REF], where P s0 ρ(k:k+r) stands for the power of P ρ(k:k+r) to s 0 . Another crucial point concerning the relative degree is the increase in the algebraic degree of the polynomial coefficients of the powers of the matrix P ρ(k:k+r) . The higher the value of r and the faster the increase of the algebraic degree. However, according to (1.9), a higher value of r would make the computation of the coefficients of P ρ(k:k+r) prohibitive for hardware implementation, since this computation involves products of S-Box. A value r = 3 provides a better compromise diffusion delay and coefficients complexity of the matrix P ρ(k:k+r) .

The number of edges is given by n a = 782, that is the number of non-zero coefficients in the matrix A ρ(k) minus 1. Hence, we set 80 coefficients of the matrix A ρ(k) as variable coefficients (or polynomial coefficients) that correspond to the same S-Box parametrized by 4-bit secret keys. Then, the subkeys size is 320 bits. The remaining 701 non-zero coefficients of the matrix are set to 1. The S-Box is defined as the inverse function on the Galois field GF (16) plus α 2 that is x -→ 1 x + α 2 where α is a primitive element of GF (16). Figure 2.11 illustrates the required number n a of edges (that is the number non-zero coefficients) to avoid coefficients equal zero in the matrix P ρ(k:k+r) after n iterations. We do not provide the complete specification here. The test platform is made of three wired arduino MEGA 2560 card. The supervisor depicted in Figure 2.13 describes the interconnection between the cards. Card 1 and card 3 are wired to temperature sensors that collect the plaintext data. Those cards can encrypt the data and send them to the card 2 that decrypts them. The platform also allows to perform desynchronization between the cards by setting randomly the internal state of the card that plays the role of cipher. It is also possible to alter the ciphertext that is sent to the decipher: this also produces a desynchrozination. However there is a maximum delay of 40 iterations to reach a resynchronization between the cards.

FLAT LPV SYSTEMS AND SELF-SYNCHRONIZING STREAM CIPHERS

Conclusion

A systematic and general construction of Self Synchronizing Stream Ciphers based on flat Linear Parameter Varying (LPV) dynamical systems has been proposed. It is based on algebraic conditions guaranteeing flatness of the LPV system and so the self-synchronizing property, those conditions being interpreted in terms of the structure of the graph associated to the LPV dynamical system. It has been shown that such an approach allows to enlarge the existing classes of SSSC, more precisely, to obtain non triangular SSSC. Two control-theoretical issues have been treated to this end: as a new paradigm, the construction of flat dynamical systems and the notion of mortality.

Conclusion

Spectral Approach for Correlation Power Analysis

This chapter provides a new approach to perform Correlation Power Analysis (CPA) attack. Power analysis attacks are side channel attacks based on power consumption measures on a device running a cryptographic algorithm with a CMOS-technology-based circuitry. Unlike most of CPA attacks that are based on statistical attacks, we propose a new approach based on spectral analysis. The interest lies in the reduction of the attack complexity. The complexity is quasi linear in the size of the table of values of the S-Box whereas it is quadratic with statistical attacks. It is shown that it can be easily extended to a so-called multidimensional attack. The results in this chapter are published in [START_REF] Guillot | Spectral approach for correlation power analysis[END_REF].

SPECTRAL APPROACH FOR CORRELATION POWER ANALYSIS

Introduction

The Correlation Power Analysis (CPA) is a method that allows to recover the secret information (usually the secret key) embedded in the silicon of an electronic component [START_REF] Brier | Correlation power analysis with a leakage model[END_REF]. It consists in measuring the power consumption while running operations that involve the secret information. This method has been introduced in 2004 by researchers of Gemplus Company (Eric Brier, Christophe Clavier and Francis Olivier) in [START_REF] Brier | Correlation power analysis with a leakage model[END_REF]. The attack follows the work of Paul Kocher proposed in 1999 [START_REF] Paul | Differential power analysis[END_REF]. The electric circuits that perform the computation in the processor are designed from a technology known as CMOS (Complementary Metal Oxide Semiconductor) [5].

A general description of this technology is provided in [START_REF] Mangard | Power analysis attacks -revealing the secrets of smart cards[END_REF]. The outcome of CMOS architectures (see Figure 3.1) lies in fast transitions but, on the other hand, they are sensitive to power consumption or electromagnetic leakage. Power analysis attacks are based on the general principle that the instantaneous power consumption of a cryptographic device, based on CMOS technology, depends on the data it processes and on the operation it performs [START_REF] Messerges | Examining smart-card security under the threat of power analysis attacks[END_REF]. During a symmetric encryption, those operations are in general processed by a nonlinear function called S-Box parametrized by a secret parameter [START_REF]Fips publication 46-3 -Data Encryption Standard[END_REF][START_REF]FIPS publication 197 -advanced encryption standard[END_REF]. Usually, CPA attacks computes a Pearson correlation coefficient for each subkey hypothesis that leads to a quadratic overall complexity [START_REF] Schimmel | Correlation power analysis in frequency domain[END_REF][START_REF] Prouff | Constructive Side-Channel Analysis and Secure Design -4th International Workshop[END_REF]. The attack can be applied to any encryption algorithm involving S-Boxes. This is usually the case of Self-Synchronizing Stream Cipher whose next-state transition function involves an S-Box and that guarantees confusion properties. To show the feasibility of the attack, we experiment it on the AES S-Box and the LPV-based SSSC that we have designed.

Preliminaries on Spectral Analysis

Having in mind a CPA attack based on spectral considerations, preliminaries on Fourier analysis must be recalled. It is worth pointing out that the suggested attack is based on a power consumption measurement on a component that processes binary data as input. Hence, the measurement can be modeled as a real-valued function over the set of binary words. This section is devoted to prerequisites on Fourier analysis of this class of functions.

Let Φ be the set of real valued functions over the set of n-dimensional binary words:

Φ = ϕ : {0, 1} n → R
For any two functions ϕ and ψ in Φ, let us define the scalar product of ϕ and ψ as:

ϕ, ψ = x∈{0,1} n ϕ(x)ψ(x).

Preliminaries on Spectral Analysis

This scalar product is a symmetric bilinear form that confers to this set the structure of a 2 n -dimensional Euclidean vector space over R.

The norm associated to this scalar product is:

ϕ = ϕ, ϕ = x∈{0,1} n ϕ(x) 2
The norm of a function ϕ in Φ is called the energy of ϕ.

The well-known Cauchy-Schwarz inequality holds:

∀ϕ, ψ ∈ Φ, ϕ, ψ ≤ ϕ × ψ (3.1)
where • stands for the absolute value.

The canonical basis of the space Φ is the family of characteristic functions of singletons which are by definition, for all vectors u ∈ {0, 1} n , the functions denoted by δ u and defined by:

δ u : x → 1 if x = u 0 otherwise (3.2)
This basis is clearly orthonormal according to the above scalar product. Each function ϕ ∈ Φ can be expressed in this basis as:

ϕ = u∈{0,1} n ϕ(u)δ u .
Another basis of the space Φ is the basis of the so-called Walsh functions.

Definition 3.2.1 (Walsh functions [49])

The Walsh functions are the functions of Φ defined for any u ∈ {0, 1} n by :

χ u : x → 1 √ 2 n (-1) u•x where x • u = u 1 x 1 + u 2 x 2 + • • • + u n
x n is the dot product over the space F n 2 of n-dimensional binary words over the two elements field F 2 .

The Walsh functions are pairwise orthogonal. They are presented here with a normalization coefficient equal to 1/ √ 2 n such that they provide an orthonormal basis as stated in the following proposition.

Proposition 3.2.1

The family (χ u ) u∈{0,1} n of Walsh functions is an orthonormal basis of Φ.

Proof. Let u and v be two n-dimensional binary vectors. One has:

χ u , χ v = 1 2 n x∈{0,1} n (-1) x•(u+v) .

SPECTRAL APPROACH FOR CORRELATION POWER ANALYSIS

If u = v then u + v = 0. The above sum has 2 n terms, all equal to 1. Then χ u , χ u = 1.

If u + v = 0, it has a non-zero component. Let u i + v i be this component. Then, the sum over all the vectors x for which x i = 0 is the opposite of the sum over all the vectors x for which

x i = 1. It results that if u = v then χ u , χ v = 0.
This family allows to express any function ϕ ∈ Φ in the basis of Walsh functions

ϕ = u∈{0,1} n ϕ, χ u χ u .

Definition 3.2.2 (Fourier Transform)

The Fourier spectrum of ϕ ∈ Φ is the family of coefficients ϕ, χ u u∈{0,1} n , of the expression of ϕ in the basis of Walsh functions, and the Fourier transform of ϕ is the function in Φ defined on {0, 1} n as:

u → ϕ(u) = ϕ, χ u = 1 √ 2 n x∈{0,1} n ϕ(x)(-1) u•x .
The Fourier transform expresses a change of basis. Thus, the transformation is linear. Moreover, it is isometric as stated in the following proposition. Proposition 3.2.2 For any functions ϕ and ψ in Φ, one has:

ϕ, ψ = ϕ, ψ . Proof. ϕ, ψ = x∈{0,1} n 1 √ 2 n u∈{0,1} n ϕ(u)(-1) u•x 1 √ 2 n v∈{0,1} n ψ(v)(-1) v•x
By inverting the summation order, it follows that

ϕ, ψ = 1 2 n u∈{0,1} n v∈{0,1} n ϕ(u)ψ(v) x∈{0,1} n (-1) (u+v)•x .
As this latter sum equals 2 n if u = v and equals 0 elsewhere, the result holds. As a direct consequence of this proposition, it follows that for all functions ϕ in Φ, the so-called Parseval equality holds (see [START_REF] Carlet | Boolean functions for cryptography and error-correcting codes[END_REF])) and expresses the energy conservation law:

ϕ = ϕ (3.3) Proposition 3.2.

(Effect of a translation [50])

For any vector a in {0, 1} n , let τ a : t -→ t + a be the translation of vector a. Let ϕ be a function in Φ, then for all vectors u ∈ {0, 1} n , one has:

ϕ • τ a (u) = (-1) u•a ϕ(u).

Modelling the Attack

Proof.

ϕ • τ a = 1 √ 2 n x∈{0,1} n ϕ(x + a)(-1) u•x = 1 √ 2 n y∈{0,1} n ϕ(y)(-1) u•(y+a) = (-1) u•a ϕ(u) (3.
k = k √ 2 n δ 0 .
Proof. By definition,

k(u) = 1 √ 2 n x∈{0,1} n k(-1) u•x = k √ 2 n x∈{0,1} n (-1) u•x .
The latter sum equals 2 n if u = 0 and 0 elsewhere, and the result holds.

Modelling the Attack

Physical principles

Nowadays, digital circuits are often designed with CMOS (Complementary Metal Oxide Semiconductor) technology. The main characteristic lies in the output stage of the logical gates that involves a pair of Field Effect Transistors (FET) with opposite polarity. The transistors are combined symmetrically (push-pull architecture) such that they switch between two states: on and off. The outcome of such architecture is that in a steady state mode, the current consumption is almost null. On the other hand, when the output state of a gate changes, a parasitic capacitor discharges in the complementary parasitic capacitor. This leads to power consumption while a transition occurs. As a consequence, the following assumption, which is the core idea of CPA is well-admitted:

Assumption 1 The power consumption of CMOS circuit is proportional to the number of logic gates that switch [5].

From this assumption, two models of consumption can be considered: the Hamming weight model and the Hamming distance model [START_REF] Brier | Correlation power analysis with a leakage model[END_REF]. For a given calculus, the first model assumes that the gates switch from the state 0 to the result of the calculus. It turns out that the model is well suited for software implementations. The second model assumes that the gates switch from an initial state that corresponds to the former calculus result to the state corresponding

SPECTRAL APPROACH FOR CORRELATION POWER ANALYSIS

Target of the Attack

Many symmetric ciphering algorithms such as DES [START_REF]Fips publication 46-3 -Data Encryption Standard[END_REF] or AES [START_REF]FIPS publication 197 -advanced encryption standard[END_REF] for instance are based on alternate stages of linear and nonlinear calculations. The nonlinear stage is most often implemented in the form of S-Boxes, each of one corresponding to a nonlinear function f from {0, 1} n to {0, 1} m , whose input is the exclusive or (XOR) of a data d ∈ {0, 1} n and of an unknown secret subkey k ∈ {0, 1} n , and returns a quantity y ∈ {0, 1} m , that is

y = f (d + k ).
Many strategies exist and allow to recover the secret key k . A well know approach provided in [START_REF] Mangard | Power analysis attacks -revealing the secrets of smart cards[END_REF] is based on statistical means and uses Pearson correlation coefficients.

General CPA approach

The strategy used in the CPA attack consists of performing the attack in 5 steps [START_REF] Mangard | Power analysis attacks -revealing the secrets of smart cards[END_REF] as illustrated in Figure 3.2.:

Step 1: choose intermediate result of the executed algorithm and hypothetical keys

Step 2: measure the power consumption and record the traces Step 5: correlate the hypothetical power consumption values with the power traces.

Modelling the Attack

d 1 d 2 . . . d D plaintext or ciphertext k 1 k 2 • • • k K Key hypotheses cryptographic algorithm y 11 y 12 • • • y 1K y 21 y 22 • • • y 2K . . . y D1 y D2 • • • y DK

Hypothetical intermediate values

y ij = f (d i + k j )
power model

h 11 h 12 • • • h 1K h 21 h 22 • • • h 2K . . . h D1 h D2 • • • h DK h i,j = H (y i,j )
Hypothetical power consumption (Hamming-weight or Hamming-distance model) In Step 1, the adversary chooses D random values (d 1 , d 2 , . . . , d D ) (plaintext or ciphertext) that will be used as input of the executed algorithm. He also chooses hypothetical values of keys k 1 , . . . , k K that will be correlated to the right key k .

t 11 t 12 • • • t 1N t 21 t 22 • • • t 2N Measured power traces . . . t D1 t D2 • • • t DN statistical analysis r 11 r 12 • • • r 1N r 21 r 22 • • • r 2N . . . r K1 r K2 • • • r KN Pearson correlation Result
In Step 2, the adversary records, using an oscilloscope, the power consumptions or traces related to each random value d i . Each trace is made of N samples and is denoted by t i,j , i = 1, . . . , D, j = 1, . . . , N . This provides a matrix T = (t i,j ).

In Step 3, for each random value d i and hypothetical key k j , the adversary computes hypothetical values y i,j = f (d i + k j ).

In Step 4, the adversary computes hypothetical power consumption values h i,j using either the Hamming weight or Hamming distance model, with h i,j = HW(f (d i + k j )) in the case of

SPECTRAL APPROACH FOR CORRELATION POWER ANALYSIS

Hamming weight model or h i,j = HD(f (d i + k j )) in the case of Hamming distance model. This provides a matrix H = (h i,j ).

Finally in Step 5, the adversary correlates column by column the entries of the matrices H and T above by applying Pearson correlation (3.5) formula.

We recall that for two random variables X = (X 1 , . . . , X D ), Y = (Y 1 , . . . , Y D ) the Pearson correlation formula is given by:

ρ(X, Y ) = D i=1 (X i -X) • (Y i -Ȳ ) D i=1 (X i -X) 2 • D i=1 (Y i -Ȳ ) 2 (3.5)
where X corresponds to the mean of the random variable X. In Step 5 the adversary computes then the correlation coefficients related to each hypothetical key value: r i,j = ρ(H .,i , T .,j ), i = 1, . . . , K, j = 1, . . . , N , where H .,i and T .,j are respectively the column i of H and the column j of T . The secret key k is recovered from the values of r i,j . For example, if k i0 is a right hypothesis key for an index i 0 , then the values r i0,j , j = 1, . . . , N or their mean are higher (i.e exceed a threshold value) than the other correlation coefficients

r i,j , i = i 0 .
In this chapter, the spectral approach based on Fourier transform allows to recover the secret key k without computing Pearson coefficient, but only to estimate the relevance of the secret key that had been found. For that, we try to minimize the value of the error related to the measurement of the power consumption or to the accuracy of the leakage model. In the sequel we will consider the Hamming-Weight model for the leakage, as we are concerned with software implementation. Indeed the implementation is realized on smart card based on an AVR processor.

Spectral Approach

Like in the general case, the attack consists in performing ciphering operations with various random inputs d 1 , d 2 , . . . , d D , chosen by the adversary, then, measuring the power consumption during the calculation and finally, trying to infer the values of the secret subkey k . In the sequel we will denote the known data by d. Having in mind a smart card software implementation, according to the discussion in Section 3.3.1, the first model of leakage will be hereafter considered and Assumption 1 applies. Let us notice that this is not restrictive because it is easy to adapt the proposed attack to the second model. Thus, for a given calculus of an S-Box with input d and secret subkey k , the power consumption is proportional to the quantity ϕ(d)

Modelling the Attack

which admits the following expression:

ϕ(d) = m i=1 f i (d + k ) + ε(d) + C, ( 3.6)
where:

• the first term is the model leakage, i.e. the Hamming weight of f (d + k ), with f i the i-th Boolean component of the function f

• the second term is a random noise denoted ε(d). This noise is due to errors in measurement and also on the accuracy of the model

• the third term is a constant C that corresponds to the power consumption of the device which does not depend on d.

Let g be the function d

→ m i=1 f i (d). Equation (3.6
) is rewritten as:

ϕ(d) = g(d + k ) + ε(d) + C.
However, the subkey k assumed by the adversary may not be equal to the right secret key k and the leakage model may not be the right one. Hence, we must introduce an error depending in particular on k. It is denoted by ε k (d) and is defined as:

ε k (d) = ϕ(d) -g(d + k) -C. (3.7)
In an ideal situation, that is no noise, no mismatch, and in particular when k = k , it should be zero for any d ∈ {0, 1} n . Hence, we can define the objective of the attack as finding the value of k which minimizes the quadratic error

E(k) 2 = ε k 2 = d∈{0,1} n ε k (d) 2 .
Based on Parseval's Equality (3.3), the problem is equivalent to find k which is solution to:

arg min k E(k) 2 = u∈{0,1} n ε k (u) 2 (3.8)
In the following, it is shown that a spectral approach to solve Equation (3.8) will be relevant in terms of complexity of the underlying attack.

By applying the Fourier transform to Equation (3.7), it comes, for all vectors u ∈ {0, 1} n :

ε k (u) = ϕ(u) -(-1) u•k g(u) -C √ 2 n δ 0 (u).
(3.9)

SPECTRAL APPROACH FOR CORRELATION POWER ANALYSIS

The interest of considering the Fourier transform is that discarding the value at the zero vector eliminates the last term which corresponds to the consumption that does not depend on the value of d. Hence, we define the functions ϕ and g by zeroing the value at the zero vector, that is:

ϕ (u) =    ϕ(u) if u = 0 0 otherwise and g (u) =    g(u) if u = 0 0 otherwise (3.10) then finding a solution k of Equation (3.8) is equivalent to finding a solution k of arg min k E(k) 2 = u∈{0,1} n ε k (u) 2 (3.11) with ε k (u) = ϕ (u) -(-1) u•k g (u).
Expanding the terms in E(k) 2 yields

E(k) 2 = u∈{0,1} n ϕ (u) 2 + u∈{0,1} n g (u) 2 -2 u∈{0,1} n ϕ (u) g (u)(-1) u•k (3.12)
On the right-hand side, only the last term depends on k. Hence and finally, the problem is to find a solution k to arg max

k F (k) (3.13)
with

F (k) = u∈{0,1} n ϕ (u) g (u)(-1)
u → ϕ (u) g (u)

Assessing the estimation reliability

From the above section, we assume that the attacker can choose any d ∈ {0, 1} n and knows the exact instant when the operation f (d + k) is performed. To circumvent such a difficulty which arises in practice, an enhancement of the attack should be proposed. We must memorize the consumption ϕ(d) during a sufficient large time window ∆ t (see Figure 3.5) to guarantee that the computation of f (d + k ) will be actually performed. The resulting signal is called a trace (see Figure 3.6). A trace has to be measured for all 2 n values of d. Let us denote by ϕ t (d) the consumption at time t for the input value d. For a finite number of sample times t in the time window ∆ t , an estimation k of the secret subkey k is computed from (3.13). However, if k is not involved in the operation performed at this time or if k is

Modelling the Attack

actually involved but k is not equal to k , the estimation of the right subkey k , that is the result of (3.13) will not be reliable. Thus, it is required to find a way of assessing this reliability.

To this end, similarly as in Subsection 3.3.2, let us introduce the quantity defined as:

F t (k) = u∈{0,1} n ϕ t (u) g (u)(-1) u•k . (3.15)
where

ϕ t (u) =    ϕ t (u) if u = 0 0 otherwise (3.
g k (u) =    g k (u) if u = 0 0 otherwise (3.17)
which allows to disregard the zero vector. According to Proposition 3.2.3, for all n-dimensional binary vectors u, we have that g k (u) = (-1) u•k g (u). Hence, Equation (3.15) can be rewritten as

F t (k) = ϕ t , g k (3.18)
Hence, for every sample time t in ∆ t , it is aimed at finding k, that is finding the solution of arg max

k F t (k) (3.19)
Any time t leads to a possible estimation k of k . It is then necessary to find at which time, this value k is relevant, in other terms, the time where there is a highly matching of k with k .

The scalar product F t (k) being computed for all sample times t in ∆ t , we must detect peaks. The more the matching between the measure and the model, including the key k and the higher the peaks. Hence, the orthogonality is a way of assessing the matching. However, since the detection of the peaks requires a comparison of F t (k) for all sample times t in ∆ t , a normalization must be done. To this end, we introduce the following quantity which will be called reliability coefficient.

r t (k) = F t (k) ϕ t • g k = ϕ t , g k ϕ t • g k
Noticing that g k = g , the reliability coefficient turns into

r t (k) = F t (k) ϕ t • g , (3.20)

SPECTRAL APPROACH FOR CORRELATION POWER ANALYSIS

with a normalization which is independent from k. According to Cauchy-Schwarz inequality (3.1) it follows that r t (k) ∈ [0, 1]

Finally, the attack consists in the following steps: Steps 1 : for every sample time t in ∆ t , find the solution k of (3.19); Steps 2 : for every solution k associated to a given sample time t in ∆ t , compute r t (k) (see Equation (3.20)) and detect the peaks among all the r t (k) with t ∈ ∆ t . Those peaks correspond to the times where the key k match with the solution k of Steps 1.

Remark 3.3.2 If the time where f (d + k ) is computed is exactly known, there is no need to perform Steps 2.

Let us comment on the complexity of the attack. The Fourier Transform of the function u → g (u) can be computed off-line once and for all from the S-Box table of the leakage model. The Fourier transform ϕ t must be computed from experimental data for every time t in ∆ t . For every time t in ∆ t , according to Remark 3.3.1, F t (k) is computed with the Fourier transforms of the functions u → ϕ t (u) g (u) and looking for the value of k that maximizes the function F t . Finally, the peaks are detected by computing r t (k) (see Equation (3.20)). The Fourier transform calculation can be carried out by using a fast algorithm. A simple divide-and-conquer butterfly algorithm exists for that purpose and is called the Fast Fourier Transform (FFT) (see for example [START_REF] Carlet | Boolean functions for cryptography and error-correcting codes[END_REF]). The complexity of this algorithm equals n 2 n , which is quasi linear in the size of the table of values of the involved function. As a result, the overall complexity of the attack is quasi linear in the size of the S-Box table. (3.20) is related to the usual Pearson correlation coefficient (3.5). This coefficient is widely used to evaluate relationship between data. Hence, it is a popular choice for statistical analysis when it comes to perform CPA attacks. The Pearson correlation coefficient of the functions ϕ and ψ in Φ is then given by:

Remark 3.3.3 It is worth pointing out that the quantity in Equation

c(ϕ, ψ) = x∈{0,1} n ϕ(x) -m ϕ × ψ(x) -m ψ x∈{0,1} n ϕ(x) -m ϕ 2 × x∈{0,1} n ψ(x) -m ψ 2 , (3.21)
where m ϕ and m ψ are the means of functions ϕ and ψ,given by:

m ϕ = 1 2 n x∈{0,1} n ϕ(x) and m ψ = 1 2 n x∈{0,1} n ψ(x)
In other words, Pearson coefficient c(ϕ, ψ) can be expressed as:

c(ϕ, ψ) = ϕ -m ϕ , ψ -m ψ ϕ -m ϕ • ψ -m ψ

Modelling the Attack

As it can be noticed that ϕ -m ϕ = ϕ , and as the Fourier transform is isometric, it follows that the coefficient given by Equation (3.20) is nothing but the Pearson correlation coefficient of the functions ϕ t and g k . Thus, it results that the value of k given by maximizing F (k) in Equation (3.14) is the same value that maximizes the Pearson correlation coefficient of ϕ and

g k .
The interest of the spectral analysis lies in low complexity calculation but also in the fact that it can be easily extended to a so-called multidimensional attack as explained in the next subsection.

Multidimensional attack

When computing the value of f (d + k ) in a software device, the processor computes sequentially: first d + k and later the value of f (d + k ). Thus, the unknown k is involved at least twice within a sufficient time window ∆ t . We call multidimensional attacks, the attacks that take into account the consumption at several instants. It can be expected that more reliable results can be obtained.

The two-dimensional attack is presented thereafter because it is the one which will be used in the experiments presented in Section 3.4 but it is straightforward to generalize it to any higher finite dimension.

Let us consider two instants t 1 and t 2 . Let us denote by f 1 (d + k ) and f 2 (d + k ) the values computed respectively at times t 1 and t 2 . In our case, the function f 1 is the identity since the computation d + k is considered and the function f 2 is the S-Box implementing f (d + k ). Let ϕ 1 (resp. ϕ 2 ) be the chip consumption at time t 1 (resp. at time t 2 ). We consider the two dimensional vector of functions -

→ ϕ = (ϕ 1 , ϕ 2 ) in a set Φ 2 of functions {0, 1} n → R 2 . Let E 1
the error value given by Equation (3.12) at time t 1 and E 2 be the error value at time t 2 . The most likely value of k is the one minimizing the Euclidean norm of the two-dimensional vector

- → E = (E 1 , E 2 ).
A direct computation shows that the value that minimizes this norm is the one maximizing the value of

F (k) = u =0 ϕ 1 (u) g 1 (u) + ϕ 2 (u) g 2 (u) (-1) u•k ,
where g 1 and g 2 are the sum of the components of f 1 and f 2 . The leakage model at time t 1 is

g 1 k (d) = g 1 (d + k) and at time t 2 is g 2 k (d) = g 2 (d + k).
The scalar product to consider in Φ 2 is the following: In all subsequent figures, the upper signal is the I/O signal corresponding to the data exchanges and the lower signal is the chip consumption. It is crucial to synchronize properly the 256 consumption traces. For this purpose, the consumption traces are synchronised with the instant given by the first falling edge of the I/O signal that follows the calculation.

∀ - → ϕ = (ϕ 1 , ϕ 2 ), - → ψ = (ψ 1 , ψ 2 ) ∈ Φ 2 , - → ϕ , - → ψ = ϕ 1 , ψ 1 + ϕ 2 , ψ 2 .

Experimental Results

For every sample t, t ∈ {1, . . . , 40 000} of each 256 traces, the values ϕ t (d), d ∈ {0, . . . , 255} are extracted. Then, for every t, t ∈ {1, . . . , 40 000}, the Fourier transform of ϕ t is computed. 3.9 show the reliability coefficient r t (k) given by equation (3.20) with respect to the time t, for the three respective situations. The attack is successful. Indeed, the correlation peaks correspond to the instants when the operations are actually performed and with the right secret key k i . Let us notice that in Figure 3.7 and Figure 3.9, there are ghost peaks. However, they can be easily disregarded since they correspond to k = 0. One possible explanation is that the value of d is loaded in a register previously containing the zero value.

SPECTRAL APPROACH FOR CORRELATION POWER ANALYSIS

Experimental Results

SPECTRAL APPROACH FOR CORRELATION POWER ANALYSIS

Application of the attack to the algorithm THE CASCADE

We consider the following cipher equation for a LPV-based SSSC that has be designed. The plaintext at the discrete time k is denoted by m k and the ciphertext at discrete time k by d k = x k [START_REF] Apkarian | A convex characterization of gainscheduled H ∞ Controllers[END_REF]. We denote the S-Box by S and the subkeys by SK i , i = 0, . . . , 21.

x k+1 [0] = S(d k + SK0) • x k [0] + S(d k + SK1) • x k [1] + S(d k + SK2) • x k [2] + S(d k + SK3) • x k [3] +S(d k + SK4) • x k [4] + S(d k + SK5) • x k [5] + S(d k + SK6) • x k [6] + m k x k+1 [1] = x k [0] + x k [1] + S(d k + SK7) • x k [2] + x k [6] x k+1 [2] = x k [1] + x k [2] x k+1 [3] = S(d k + SK8) • x k [1] + S(d k + SK9) • x k [2] x k+1 [4] = S(d k + SK10) • x k [1] + S(d k + SK11) • x k [2] + S(d k + SK12) • x k [3] x k+1 [5] = S(d k + SK13) • x k [1] + S(d k + SK14) • x k [2] + S(d k + SK15) • x k [3] +S(d k + SK16) • x k [4] x k+1 [6] = S(d k + SK17) • x k [1] + S(d k + SK18) • x k [2] + S(d k + SK19) • x k [3] +S(d k + SK20) • x k [4] + S(d k + SK21) • x k [5] (3.22)
Let us recall that, during the first and second iterations of the encryption, the ciphertext

x [START_REF] Apkarian | A convex characterization of gainscheduled H ∞ Controllers[END_REF] depends only on the initial internal state x 0 . The plaintext m k influences x[0] at the first iteration, x [START_REF]FIPS publication 197 -advanced encryption standard[END_REF] at the second iteration and x [START_REF] Apkarian | A convex characterization of gainscheduled H ∞ Controllers[END_REF] at the third iteration. Then the corresponding ciphertext of m k is x k+3 [START_REF] Apkarian | A convex characterization of gainscheduled H ∞ Controllers[END_REF].

Considering the encryption algorithm THE CASCADE, each ciphertext and plaintext are nibble (4 bits). Then we need 16 traces of power consumption. The measurements are performed for traces with 100 000 samples in order to cover the whole encryption operations (3.22). Note that unlike an attack on a simple S-Box, the inputs d i , i = 1, . . . , D of the attack are plaintext and the inputs of the S-Box which is targeted within the cipher function are ciphertext that are produced by the encryption function.

To perform the measurement, we then generate several random plaintexts by applying the coupon collector's context solution [START_REF] Ferrante | A note on the coupon -collector's problem with multiple arrivals and the random sampling[END_REF]. Then in order to get 16 different values of ciphertexts, we need to generate about 16 log(16) 37 random plaintexts. Then we encrypt these plaintexts by measuring the power consumption during the encryption operations.

The correlation peaks obtained from the attack are illustrated in Figure 3.11. Let us comment on the result. The correlation peaks show that there is high correlation even for times t where no calculation of S-Box is performed. And the attack returns wrong secret keys for several times t. These wrong secret keys result from intermediate multiplication operations that are performed during the encryption. Indeed, the operations can be also seen as nonlinear operations f (d + k) where k is an unknown value. Note that the multiplication operations are implemented in constant time operations. This makes it possible to synchronize properly the different traces. Otherwise, the synchronization of the traces would be impossible to achieve.

Conclusion

A solution to find the right secret keys, would be to synchronize the traces by considering the power consumption within an interval of time ∆ t that matches exactly with calculation of the output of the S-Box. Which is actually difficult to achieve.

Note also that we have implemented the multiplication operations as constant time operation to make the attack easy, but in the case where these operations are not implemented in constant time, it would be very complicated to perform the attack by any means since it will be very difficult to distinguish times when multiplication operations and S-Box computation are performed.

Conclusion

A new approach of CPA attack has been proposed. Unlike usual approaches based on statistical analysis, a spectral approach has been provided. It is based on a correlation quantity derived from the Fourier transform of the power consumption signals. The attack can be applied to any algorithms that involve S-Boxes whose input is the exclusive or of data with a secret subkey. A Hamming weight leakage model has been used. The interest is the complexity of the attack is quasi linear in the size of the S-Box table. Furthermore, it has been shown that it can be easily extended to a so-called multidimensional attack. The attack has been successfully applied to

Introduction

In this chapter, we derive a result on the security of the canonical form of the Self-Synchronizing Stream Ciphers. Let us recall that the canonical form of the Self-Synchronizing Stream Cipher (SSSC) is constituted by the combination of a shift register (Figure 4.1), which acts as a state register with the ciphertext as input, together with a filtering function that provides the running key stream. It had been shown in [START_REF] Dravie | Security proof of the canonical form of self-synchronizing stream ciphers[END_REF] that the canonical form of the Self-Synchronizing Stream Cipher is not resistant against chosen ciphertext attack (IND-CCA security) but can reach the resistance against chosen plaintext attack (IND-CPA security) provided that the filtering function is pseudo random. We introduced a new family of functions in order to characterize the security of the canonical SSSC from its filtering function. Those functions are called Weak Pseudo Random Functions (WPRF) and provide a weaker property than pseudo-randomness. A connection with the left-or-right indistinguishability (LOR-IND) is made. This property provides a necessary and sufficient condition to characterize the indistinguishablity of SSSC. The technical developments used to establish the security proof follow similar lines than those used when dealing with block cipher symmetric encryption schemes.

Canonical Form of the Self-Synchronizing Stream Cipher 4.2.1 Generalities on SSSC

A conventional way for designing an SSSC is to resort to a shift-register-like architecture, giving the so-called canonical representation of the SSSC [START_REF] Menezes | Handbook of Applied Cryptography[END_REF]. It has also been studied in [START_REF] Parriaux | Control, synchronization and encryption[END_REF]. We recall the canonical representation as depicted in Figure 4.1 and the equations that characterize the cipher and decipher respectively (see also 2.2.2.2 of Chapter 2): cipher:

   z k = σ ss θ (c k-1 , . . . , c k-n ) c k = z k ⊕ m k decipher:    z k = σ ss θ (c k-1 , . . . , c k-n ) m k = z k ⊕ c k (4.1)
where n is the dimension of the shift register, σ ss θ : {0, 1} n → {0, 1} denotes the filtering function parametrized by the secret key θ and for every instant t, m k ∈ {0, 1} is the plaintext symbol, c k ∈ {0, 1} is the ciphertext symbol, z k ∈ {0, 1} is the key stream symbol. The quantity

Canonical Form of the Self-Synchronizing Stream Cipher

z k ∈ {0, 1} is the key stream symbol on the deciphering side and m k ∈ {0, 1} is the recovered plaintext symbol.

It is worth pointing out that all the results are established here in the Boolean case but still hold when considering any other finite alphabet. The secret key θ corresponds to some suitable parameters that select the function σ ss among a family of filtering functions. The dimension of the shift register is given by the integer n.

c k-1 c k-n . . . c k-1 c k-n . . . c k . . . . . . σ ss θ σ ss θ m k m k z k z k
The key stream symbol z k is the output of the filtering function. It only depends on the secret key θ shared by the emitter (encryption side) and the receiver (decryption side) and on n past values of the ciphertext. The ciphertext c k is worked out from an exclusive or of the plaintext symbol m k and of the key stream symbol z k , and is conveyed through the public channel. Since the generator function σ ss shares, at the transmitter and receiver sides, the same values, namely the n past ciphertexts, then the receiver recovers the plaintext when it properly received the last n ciphertext symbols. Indeed m k = m k whenever z k = z k . Finally, the vector q k = (c k-1 , . . . , c k-n ) stands for the internal state. Then, it is clear that the generators synchronize automatically after a finite transient time of length n. As a result, the dimension n of the shift register defines the synchronization delay of the decipher.

The SSSC model defined by Equations (4.1) and depicted on Figure 4.1 remains a conceptual model that can be implemented by different architectures resulting from different design approaches. The state transition function is described by the shift register. It is very simple and is secret key independent. Therefore, the security relies entirely on the security of the filtering function. Maurer's approach is suggested in [START_REF] Ueli | New approaches to the design of self-synchronizing stream ciphers[END_REF] as an alternative.

Encryption/decryption mechanisms of SSSC

In order to assess the security level reached by the canonical SSSC, it is necessary to formally define the encryption and the decryption mechanisms.

Setup.

A random secret key θ is randomly chosen from the key space for both the encryption and the decryption algorithms.

SECURITY PROOF OF THE CANONICAL FORM OF SELF-SYNCHRONIZING STREAM CIPHERS

Encryption.

For encrypting a message m consisting of binary symbols, the steps are the following:

1. Randomly choose an n-dimensional binary vector as an initial state q 0 of the shift register.

2. Randomly choose n binary symbols to build the synchronization sequence and concatenate it with the message to be encrypted yielding a binary sequence m 0 , . . . , m n+ -1 . The first n symbols are those of the synchronization sequence, and the other ones are those of the message to be encrypted.

3.

For each symbol at instant k, (a) Compute the keystream symbol as

z k = σ ss θ (q k ). (b) Compute the ciphertext symbol as c k = m k ⊕ z k .
(c) Update the shift register state by shifting its components and feeding it by the computed ciphertext symbol c k to obtain the next state q k+1 .

Decryption.

For decrypting the cryptogram consisting of n + binary symbols, the steps are the following:

1. Initialize the shift register state to any arbitrary value, for example the n-dimensional zero vector q 0 = 0. (c) Update the shift register state by shifting its components and feeding it with the computed ciphertext symbol c k to obtain the next state qk+1 .

3. The first n decrypted symbols from the synchronization sequence are ignored. The decrypted message consists of the last decrypted symbols.

It is easy to check from (4.1) that the decryption procedure recovers the message m when encrypted with the same secret key θ.

Security Criteria on the Filtering Function

In this section, we first recall what a Pseudo Random Function is, and then we define a new security criterion on the filtering function that characterizes the security of the SSSC.

SECURITY PROOF OF THE CANONICAL FORM OF SELF-SYNCHRONIZING STREAM CIPHERS

an element of the family. So, the key size must be greater than the logarithm of any power of n. In practice, an n-bit long key is admissible.

Weak Pseudo Random Functions

In this section, we define a new family of functions with a weaker property than the pseudo random functions defined in the previous section and that is more suitable to assess the security of Self Synchronizing Stream Ciphers.

A Weak Pseudo Random Function, WPRF for short, is an element of a family of weak pseudo random functions. Such a family is computationally indistinguishable from the family of all functions. The WPRF property is defined by the so-called WPRF-game defined further.

Given a WPRF-family, the WPRF-game challenger is challenged to guess whether a given function presented to her is either an element of the family or a random function. In order to answer the challenge, the challenger can ask for help from an oracle. The difference with PRF-game lies in the form of the requests to the oracle.

The WPRF-game.

For the parameter n let us consider a family of functions f θ : {0, 1} n → {0, 1}, θ ∈ {0, 1} n . The steps of the game are the following.

1. The oracle chooses a random bit b ∈ {rf, wprf}. If b = rf, then it randomly chooses a function in the set of all 2 2 n functions {0, 1} n → {0, 1}. Otherwise, if b = wprf, then it chooses a random parameter θ that defines a random element f = f θ of the WPRF-family. The oracle keeps secret the chosen bit and the goal of the challenger is to guess it.

2. The challenger asks the oracle for responses to requests. The input of the request is a polynomial length string of bits m 1 • • • m k . The response of the oracle is the sequence of couples q i , f (q i ) i∈{0,...k} , where: q 0 is chosen at random by the oracle

for i = 1 to k, q i = (q i-1 < < 1) + m i ⊕ f (q i ) ,
x < < 1 denotes the left shift of the binary vector x by one and the symbol + stands for concatenation.

3. After a polynomial number η of queries, the challenger answers a binary value b ∈ {rf, wprf} which means that the function f chosen by the oracle is either random or weak pseudo random.

c i = m i ⊕ f (q i ).

SECURITY PROOF OF THE CANONICAL FORM OF SELF-SYNCHRONIZING STREAM CIPHERS

based on security concepts introduced by Goldwasser and Micali [START_REF] Goldwasser | Probabilistic encryption and how to play mental poker keeping secret all partial information[END_REF][START_REF] Goldwasser | Probabilistic encryption[END_REF]. The first concept is the semantic security, which is a computational analogue to the Shannon perfect secrecy. It means that an adversary cannot recover any bit of information of the plaintext from the ciphertext. However, the semantic security does not allow to fluently deal with security proof. This leads the authors in [START_REF] Goldwasser | Probabilistic encryption and how to play mental poker keeping secret all partial information[END_REF][START_REF] Goldwasser | Probabilistic encryption[END_REF] to define another concept known as indistinguishability which better facilitates proving the security of practical ciphers.

In order to characterize the security of the SSSC, we need a variant of the indistinguishability property known as the left-or-right indistinguishability which implies the indistinguishability property against an adaptive chosen plaintext attack.

Indistinguishability and IND-game

A cryptographic scheme is said to be secure, in the sense of indistinguishability, if a polynomial complexity algorithm has a negligible advantage in distinguishing from which of two messages (m 0 and m 1 it has provided) is the cryptogram presented to it. This is formalized by the so-called IND-game.

This game involves two players: an algorithm A called adversary or challenger, and an oracle. The game consists of the following steps:

1. The challenger chooses two messages m 0 and m 1 and provides the oracle with them. Before giving her answer, the challenger can be supported by the oracle to decrypt ciphertexts the challenger chooses (Chosen Ciphertext Attack, CCA) or to encrypt plaintexts the challenger chooses (Chosen Plaintext Attack, CPA). Of course, in a CCA attack, the challenger is not allowed to request the decryption of the challenge it has received.

For As m 0 and m 1 are randomly chosen with the same probability 1/2, it holds that

Adv(A) = 2Pr(b = b) -1 ,
where Pr(b = b) denotes the probability that A wins.

Indistinguishability and Security Games

If the challenger answers at random, then her advantage is null. If it always wins, or always looses, then her advantage equals 1.

A cryptographic scheme is defined by a security parameter, which is for example the key size. Such a scheme is said to be IND-secure if the advantage of any polynomial challenger is negligible. A cryptographic algorithm is said to be IND-CCA if it is IND-secure during a CCA attack. It is said to be IND-CPA if it is IND-secure during a CPA attack.

For the canonical SSSC, the security parameters are the size of the shift register which equals the number of inputs of the filtering function and the size of the secret key.

Left-or-right indistinguishability and LOR-IND-game

Likewise the IND-game, the LOR-IND-game, namely left-or-right indistinguishability is described in [START_REF] Bellare | A concrete security treatment of symmetric encryption[END_REF]. It involves two algorithms: the challenger A and an oracle. The game consists of the following steps:

1. First, the oracle randomly chooses a bit b ∈ {0, 1}. The following proposition states that the left-or-right indistinguishability introduced above is a stronger property that the indistinguishability against a chosen plaintext attack. Proof. We first prove that if the filtering function of a canonical SSSC is WPRF-family, then the SSSC reaches the LOR-IND security. In order to prove this property, we prove that if a polynomial adversary A exists against the SSSC, then we can deduce a challenger B against the WPRF property of the filtering function. Let B be defined as follows:

1. B chooses a random bit b ∈ {0, 1}.

2. For each received couple of messages (m i 0 , m i 1 ), the algorithm B asks for the WPRF oracle the sequence of bits m i b and receives from the oracle the sequence x i k , f (x i k ) . From this sequence, B computes a cryptogram c that it sends to A. It must be shown that if the advantage of A is non negligible, then the advantage of B is non negligible too. From the definition of B, its advantage is:

After a polynomial times of queries, the adversary

Adv(B) = Pr wprf (b = b) -Pr rf (b = b) .
In the WPRF world, the challenger B acts for A as a true ciphering oracle. Thus, the advantage of A is:

Adv(A) = 2Pr wprf (b = b) -1 ≤ 2Pr wprf (b = b) -2Pr rf (b = b) + 2Pr rf (b = b) -1 (4.2)
The first term of the right hand side of the inequality (4.2) is twice the advantage of B. Moreover, as in the random world, the answers of the WPRF oracle are random, the answers of B to A are random too. As a consequence, the answer of B is random and the second term in the second member of inequality (4.2) is null. It follows that:

Adv(A) ≤ 2Adv(B),
which proves the expected result. It remains to prove the reciprocal: if the canonical SSSC reaches the LOR-IND-CPA security, then the filtering function achieves the WPRF property. By contraposition, it is equivalent to prove that if a WPRF challenger exists against the filtering function, then a LOR-IND adversary can be constructed against the canonical SSSC.

Given a WPRF challenger B, then a LOR-IND adversary is constructed as follows:

1. On each query m i from the challenger B, the adversary A generates a random binary sequence a i and sends to the LOR-IND oracle the couple (m i , a i ).

SECURITY PROOF OF THE CANONICAL FORM OF SELF-SYNCHRONIZING STREAM CIPHERS

2. The oracle encrypts either m i or a i according to the value of a random bit b ∈ {0, 1} chosen once and for all. The oracle returns to A the corresponding cryptogram c i .

3. From the received cryptogram c i , the adversary A computes the values of the filtering functions used by the oracle, assuming that the oracle has encrypted the message m i , and transmits the sequence of couples We can summarize all the security notions developed in this chapter by the following implications:

x i k , f (x i k ) to B.
prf

⇒ wprf ⇔ LOR-IND-CPA ⇒ IND-CPA

Conclusion

The cryptological complexity of the canonical form of the Self-Synchronizing Stream Cipher lies in the filtering function. The maximum security is achieved when this function is a pure random function. It has been shown that, even in this ideal case, this kind of cipher cannot reach the IND-CCA security. This result consolidates the CCA attacks that have been performed on existing SSSC [START_REF] Joux | Chosen-ciphertext attack against mosquito[END_REF][START_REF] Daemen | Chosen ciphertext attack on SSS. eS-TREAM, ECRYPT Stream Cipher Project[END_REF][START_REF] Joux | Loosening the KNOT[END_REF]. This is due to the fact that the ciphertexts are malleable. Thus, the maximum expected security is IND-CPA. In realistic implementation, the filtering is a pseudo random function. We have proved that for such practical ciphers, the IND-CPA security can be reached. The interest of the result lies in that it guarantees the existence of SSSC that can be IND-CPA secure. Finally, a weaker property than pseudo-randomness has been proposed. It had been called WPRF. It allows to assess a stronger security level than indistinguishability, namely left-or-right indistinguishability, against chosen plaintext attacks.

Chapter 5

Matrix Representations of Vectorial Boolean Functions and Eigenanalysis

This chapter aims at giving a unified overview on the various representations of vectorial Boolean functions, namely the Walsh matrix, the correlation matrix and the adjacency matrix. A new representation called polynomial matrix is introduced. It is shown that those different representations are similar. For a vectorial Boolean function with the same number of inputs and outputs, an eigenanalysis of those representations is performed. It is shown how eigenvalues and eigenvectors are related to the structure of the graph associated to this function. Also, we give an example of LPV-based SSSC and, by considering the correlation matrix associated to its state transition function, we show that it is not based on a T-function. To simplify the reading of this chapter, the proof of the results are removed but can be found by the reader in [START_REF] Dravie | Matrix representations of vectorial Boolean functions and eigenanalysis[END_REF].

Introduction

Vectorial Boolean functions [START_REF] Carlet | Boolean functions for cryptography and error-correcting codes[END_REF] play an important role in cryptography as non-linear components of symmetric algorithms [START_REF] Meier | Nonlinearity criteria for cryptographic functions[END_REF]. They are also used in control theory to model discrete dynamical systems [START_REF] Bollman | A control theory for Boolean monomial dynamical systems[END_REF]. Usual existing representations are presented such as the Walsh matrix, the correlation matrix and the adjacency matrix (related to graph representations) [START_REF] Daemen | Correlation matrices[END_REF] often used in the analysis of cryptographic properties. Besides, we introduce a new representation based on algebraic properties. We call this representation polynomial matrix.

It is shown that the representations describe the same function in different bases and the bases are given explicitly. Then, the relations between these representations are proved. For square matrices representing the vectorial Boolean functions, we perform the eigenanalysis. Deep connections are established between the eigenvalues of those matrices, their related eigenspaces and the structure of the graphs associated to the vectorial Boolean functions.

This chapter provides further results to the work of Parriaux's Thesis [START_REF] Parriaux | Control, synchronization and encryption[END_REF]. They are useful to classify different categories of state transition function of SSSC when considering the correlation matrix of these functions. The results are also general and could be useful for people concerned with theoretical aspects regarding vectorial Boolean functions and with practical applications too. They are interesting in particular for cryptographic purposes.

Boolean functions representations

This section provides necessary prerequisites. The reader may refer to [START_REF] Carlet | Boolean functions for cryptography and error-correcting codes[END_REF] for details. New results are also presented here as important complements. A Boolean function is a function from the vector space F n 2 to the set {0, 1}. Depending on the context, the set {0, 1} is considered either as the two element field F 2 (1 + 1 = 0) or as a subset of the field C of complex number 1 + 1 = 2. We call such a function a (n)-function. The various usual representations are the truthtable, the Fourier and the Walsh transform and the polynomial representation. These are recalled below. It is clear that the convenience of a specific representation depends on the properties it is expected to characterize.

Boolean functions representations

Fourier/Walsh transform

Let f be any complex-valued function on F n 2 . We recall from Definition 3.2.1 of Chapter 3 the Fourier transform of f denoted by f , which is by definition the complex-valued mapping

F n 2 -→ C defined for u ∈ F n 2 by: f (u) = 1 √ 2 n x∈F n 2 f (x)(-1) x•u , ( 5.1)
where

x • u = x 0 u 0 + • • • + x n-1 u n-1
is the dot product of the two vectors x and u. This transform is invertible and the inverse is given by:

f = f (5.2)
And the Fourier transform is an expression of f in the orthogonal basis of the so-called Walsh functions (see Definition 3.2.1), defined for all u ∈ F n 2 by: χ u :

F n 2 -→ C x -→ 1 √ 2 n (-1) u•x . ( 5.3)
The expression of f in this basis is:

f = u∈F n 2 f (u)χ u .
When f is represented by the vector corresponding to its truthtable, the Fourier transform (5.1) also admits a matrix expression: f = Hf, (5.4) where H is the so-called Hadamard matrix whose coefficient at row u ∈ F n 2 and column v ∈ F n 2 is:

H u,v = 1 √ 2 n (-1) u•v .
(5.5)

The Hadamard matrix H is invertible and its inverse is given by:

H -1 = H. (5.6)
As a result, it holds that

f = H f
When dealing with Boolean functions, it is better to use the Walsh transform that has nicer properties than the Fourier transform in most cases. The Walsh transform of a Boolean

MATRIX REPRESENTATIONS OF VECTORIAL BOOLEAN FUNCTIONS AND EIGENANALYSIS

function f is the Fourier transform of its sign function f χ where f χ = (-1) f = 1 -2f . The Walsh transform of f is then the function f χ defined by:

f χ : F n 2 -→ R u -→ 1 √ 2 n x∈F n 2 (-1) f (x)+x•u (5.7)
By applying the Parseval's equality (3.3) to the sign function of Boolean functions, one has:

u∈F n 2 f χ (u) 2 =   u∈F n 2 f χ (u)   2 = 2 n (5.8)

Polynomial representations

This section is devoted to polynomial representations of (n)-functions. Two representations are presented: Algebraic Normal Form (ANF) (see [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF]) and Numerical Normal Form (NNF) (see [START_REF] Carlet | A new representation of Boolean functions[END_REF]). Due to the equality, ∀a ∈ {0, 1} , a = a 2 , distinct polynomials may represent the same Boolean function. In order to obtain the uniqueness of the representation, we only consider the polynomials in the ring of multivariate polynomials whose exponents for each indeterminate are at most one.

Let a and b be two elements of F 2 , it holds that a b = 1 if b ≤ a and a b = 0 elsewhere. Polynomial representations are expressions of the function in the so-called basis of monomials defined, for u ∈ F n 2 , by:

F n 2 -→ {0, 1} x -→ x u
(5.9)

where

x u = x u1 1 • • • x un n (5.10)
is called a monomial.

For any vector u in F n 2 , the support of u is defined by: supp(u) = i ∈ {1, . . . , n} | u i = 0 . Definition 5.2.1 When x and u are two n-dimensional binary vectors, the notation x u means that the support of x is included in the support of u. The following equivalences holds:

x u ⇐⇒ u x = 1 ⇐⇒ ∀i ∈ {1, . . . , n} , x i ≤ u i .

(5.11)

Boolean functions representations

Algebraic Normal Form (ANF)

Let us recall a multivariate polynomial representation of Boolean functions called Algebraic Normal Form (ANF for short).

The ANF coefficients of a function f are, by definition, for u ∈ F n 2 ,

a u = x∈F n 2 f (x)u x , (5.12)
where the sum is performed in the two-element field F 2 . They express the function f in the basis of monomials as:

∀x ∈ F n 2 , f (x) = u∈F n 2 a u x u .
(5.13)

Numerical Normal Form (NNF)

Let us recall another multivariate polynomial representation of Boolean functions called Numerical Normal Form (NNF for short). Unlike the ANF, the coefficients of the polynomial do not lie in the two element field F 2 but in the field C of complex numbers. Notice that such a polynomial may not correspond to a {0, 1} valued function.

The NNF coefficients of a complex valued function f are the complex coefficients of f expressed in the basis of monomial functions. They are defined by:

f (u) = x∈F n 2 (-1) HW(x)-HW(u) f (x)u x = x∈F n 2 |x u (-1) HW(x)-HW(u) f (x), u ∈ F n 2
where HW denotes the Hamming weight function and the sum is performed in the field of complex numbers. The expression of f in the basis of monomials is:

∀x ∈ F n 2 , f (x) = u∈F n 2 f (u)x u = u∈F n 2 |u x f (u) (5.14)
Likewise for the Fourier transform, a matrix relation exists between a function f described by its truthtable and its NNF:

f = Zf, (5.15)
where Z is a 2 n -dimensional square matrix whose coefficient at row u ∈ F n 2 and column v ∈ F n 2 is given by: Z u,v = (-1) HW(v)-HW(u) u v .

MATRIX REPRESENTATIONS OF VECTORIAL BOOLEAN FUNCTIONS AND EIGENANALYSIS

x 000 001 010 011 100 101 110 111 f e (x) 010 100 001 101 010 101 010 110 The matrix Z is invertible and the inverse is the so-called monomial matrix defined by:

Z -1 = M (5.16)
where the coefficient at row x ∈ F n 2 and column u ∈ F n 2 of M is given by M x,u = x u . As a result, one has f = M f .

Vectorial Boolean functions representations

A vectorial Boolean function is, by definition, a function from F n 2 to F m 2 . It can be considered as a vector of m (n)-functions. We call such a function an (n, m)-function. Vectorial Boolean functions have been extensively discussed in [START_REF] Carlet | Vectorial Boolean functions for cryptography[END_REF]. For any vectorial Boolean function f , it is possible to define different matrix representations denoted by A f , C f , W f , and P f . They are respectively named adjacency, correlation, Walsh and polynomial matrices. For brevity, the superscript of the matrices is omitted when the corresponding function is clear. Let f e be the function defined by the table of values of Table 5.1. This function is used throughout the rest of the paper to illustrate the results.

Adjacency matrix

The adjacency matrix of f is denoted by A. It is the expression of f in the basis of the characteristic functions (δ u ) u∈F n 2 , defined by Equation (3.2).

Definition 5.3.1 (Adjacency matrix) Let f be an (n, m)-function. Its adjacency matrix

A is a 2 n × 2 m dimensional matrix for which each row indexed by x ∈ F n 2 is null except the coefficient at the column y = f (x), which equals 1.

For example, the adjacency matrix of f e is:

A fe =                
0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0

               

Vectorial Boolean functions representations

The name adjacency matrix is inspired from graph theory [START_REF] Godsil | Algebraic Graph Theory[END_REF]. When the number of inputs equals the number of outputs, the function can also be represented by a labeled directed graph G. Hereafter, we only consider directed graphs. Thus, for brevity but without any ambiguity, we merely call them graphs. A graph is naturally associated to a (n, n)-function, where an arc relates an input of the function to its image as defined below. Now, let us recall some graph-theoretic terminology that is necessary in the further development. Some notions of this terminology have also been defined in Chapter 1. For each definition, the corresponding structure is illustrated for the function f e in Figure 5.1.

Definition 5.3.3 (Graph-related terminology (see [45]))

• An edge is an unordered pair of distinct vertices of the graph,

• An arc is a directed edge, i.e an ordered pair of distinct vertices. An arrow shows the direction of the edge,

• A vertex x is said to be incident to a vertex y (or to be a preimage of a vertex y) if there is an arc from x to y. The vertex 111 is incident to 110,

• The in-degree of a vertex is the number of vertices incident to that vertex. The in-degree of vertex 000 is 0. The in-degree of vertex 010 is 3,

• The out-degree of a vertex is the number of vertices for which this vertex is incident to. The out-degree of each vertex is 1, including vertex 101,

• A path is a sequence of vertices (x 0 , . . . , x k ) such that, for each vertex, there is an arc from x i to x i+1 . The length of the path is the number of arcs involved in the sequence. The sequence (110, 010, 001) is a path of length 2,

• A cycle is a path such that the starting vertex and the ending vertex are the same. The sequence (010, 001, 100, 010) is a cycle of length 3,

• A junction is a vertex such that the in-degree is at least two. The multiplicity of the junction is equal to the in-degree minus one. The vertex 101 is a junction of multiplicity one. The vertex 010 is a junction of multiplicity two,

• The preimage set of a vertex is the set of vertices incident to that vertex. The preimage set of the junction 010 is {000, 110, 100} and the preimage set of the junction 101 is {011, 101},

MATRIX REPRESENTATIONS OF VECTORIAL BOOLEAN FUNCTIONS AND EIGENANALYSIS

• A sink is a vertex with at least one incident vertex and such that it is not incident to any other vertex but itself. Any sink defines a cycle of length one. The vertex 101 is a sink,

• A leaf is a vertex with no incident vertex. The vertices 000, 011 and 111 are the leaves of the graph,

• A connected component is a set of vertices such that there is always a path (not necessarily directed) that relates any two vertices of that set. The set of vertices {111, 110, 000, 010, 100, 001} corresponds to one connected component and the set of vertices {011, 101} corresponds to another connected component. • the graph associated to an (n, n)-function is such that there is one and only one arrow starting from any of its vertices,

• the graph associated to a permutation contains neither leaf nor junctions,

• if a graph contains no leaf then it is the graph associated to a permutation and thus, it contains no junction,

• if a graph contains no junction then it is the graph associated to a permutation and thus, it contains no leaf.

Vectorial Boolean functions representations

Walsh/correlation matrix

Correlation matrices have been defined in [START_REF] Daemen | Correlation matrices[END_REF]. They are related to Walsh matrices by a mere normalization coefficient.

Definition 5.3.4 (see [START_REF] Carlet | Vectorial Boolean functions for cryptography[END_REF]) The Walsh matrix of an (n, m)-function is the 2 m × 2 n dimensional matrix W whose coefficients are defined at indexes u ∈ F m 2 and v ∈ F n 2 by:

W u,v = x∈F n 2 (-1) u•f (x)+v•x .
(5.17)

For all u ∈ F m 2 and all v ∈ F n 2 , the coefficient W u,v is the number of times the Boolean function x -→ u • f (x) equals the linear Boolean function x -→ v • x, minus the number of times they differ.

For example, the Walsh matrix of the function f e is:

W fe =                 8 0 0 0 0 0 0 0 2 2 2 2 -2 -2 6 -2 0 -4 0 -4 4 0 -4 0 -6 -2 2 -2 2 -2 2 -2 0 8 0 0 0 0 0 0 2 2 2 2 -2 -2 -2 6
-4 0 -4 0 0 4 0 -4 -2 -6 -2 2 -2 2 -2 2                
The row u ∈ F m 2 of the matrix W is the Walsh transform (up to a coefficient

√ 2 n ) of the linear combinations of the coordinates of f defined by x -→ u • f (x), x ∈ F n 2 .
The list of the coefficients of the Walsh matrix of a function is called the spectrum of the function. Definition 5.3.5 (see [START_REF] Daemen | Correlation matrices[END_REF]) The correlation matrix of a (n, m)-function f is:

C f = 2 -n W f .
(5.18)

Let us recall important results used further and which have been published in [START_REF] Parriaux | Towards a spectral approach for the design of self-synchronizing stream ciphers[END_REF]. We are given an (n, m)-function g and a random variable X ∈ F n 2 whose value is described by the probability law p : F n 2 -→ R that expresses the probability p(x) that X = x. We are concerned with inferring the probability law q : F m 2 -→ R that describes the random variable Y ∈ F m 2 defined by Y = g(X), q being defined by q(y) = Pr[g(X) = y]. Without any ambiguity, the notation p (respectively q) refers either to the function or to the 2 n (respectively 2 m ) column vectors whose coordinate index x ∈ F n 2 (respectively y ∈ F m 2 ) has the value p(x) (respectively q(y)).

MATRIX REPRESENTATIONS OF VECTORIAL BOOLEAN FUNCTIONS AND EIGENANALYSIS

Proposition 5.3.1 (see [START_REF] Parriaux | Towards a spectral approach for the design of self-synchronizing stream ciphers[END_REF]) Let g be an (n, m)-function and X be a random variable described by the probability law p. Then the probability law q of the random variable Y = g(X) is given by: q = H -1 C g Hp.

(5.19) Remark 5.3.4 Let p and q be the respective Fourier transform of p and q as defined in Proposition 5.3.1. It is also shown in [START_REF] Parriaux | Towards a spectral approach for the design of self-synchronizing stream ciphers[END_REF] that q = C g p (5.20)

Reduced Walsh/correlation matrix

The reduced Walsh matrix is defined as follows.

Definition 5.3.6 (Reduced Walsh matrix) For a Walsh matrix W of dimension 2 m × 2 n , its reduced matrix W of dimension (2 m -1) × (2 n -1) is the matrix deduced from W , where the first row and the first column have been removed.

W =     W 1,1 • • • W 1,2 n -1 . . . . . . W 2 m -1,1 • • • W 2 m -1,2 n -1     .

Remark 5.3.5 The same definition holds for the correlation matrix C.

It is interesting because it yields more homogeneous results. The purpose of the sequel is to show that no information on f is lost with the reduced matrix, except for constant functions.

First, let us note that the first row of the correlation matrix always equals the 2 n -dimensional vector (2 n , 0, . . . , 0). In the sequel, considerations on the first column are given. Lemma 5.3.1 Let f be an (n)-function. Then, the quantity

u∈F n 2 |u =0 f χ (u) is null if and only if f is a constant function.
Lemma 5.3.2 An (n)-function f can be uniquely recovered from its last 2 n -1 Walsh coefficients provided that it is not a constant function.

Finally, we have the following result.

Proposition 5.3.2 ([37]

) An (n, m)-function can be uniquely recovered from its reduced Walsh matrix provided that it is not a constant function.

Polynomial matrices

The extension of the NNF to an (n, m)-function gives rise to a 2 m × 2 n dimensional matrix denoted with P . We call it the polynomial matrix of f , and the entry at row indexed by u ∈ F m 2 and column indexed by v ∈ F n 2 is defined by:

P u,v = x∈F n 2 (-1) HW(x)-HW(v) f (x) u v x .
Note that the rows indexed by u ∈ F n 2 correspond to the NNF of the function f u and in particular the rows for which HW(u) = 1 correspond to the NNF of the coordinate functions of f . The matrix P expresses f in the basis of the polynomials, x -→ (-1) HW(x)-HW(v) v x , v ∈ F n 2 . For example, the polynomial matrix of f e is

P fe =                 1 0 0 0 0 0 0 0 0 0 1 0 0 1 -1 -1 1 -1 -1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 -2 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0                
In the same way as the ANF can be obtained by performing a modulo two reduction of the NNF, we can define a modulo two reduction of the polynomial matrix P .

Reduced Polynomial matrix

Likewise for correlation matrix, we define the reduced form P * of a polynomial matrix P associated to an (n, m)-function f . Assuming that f is not constant, we will prove that f can be recovered given the coefficients of P . Definition 5.3.7 (Reduced polynomial matrix) For any polynomial matrix P of dimension 2 m × 2 n , its reduced matrix P of dimension (2 m -1) × (2 n -1) is the matrix deduced from P , where the first row and column have been removed.

P =     P 1,1 • • • P 1,2 n -1 . . . . . . P 2 m -1,1 • • • P 2 m -1,2 n -1    
The following lemma is similar to Parseval's identity, and is based on the fact that for any {0, 1} valued function f , one has

x∈F n 2 f (x) = x∈F n 2 f 2 (x).

MATRIX REPRESENTATIONS OF VECTORIAL BOOLEAN FUNCTIONS AND EIGENANALYSIS

Lemma 5.3.3 (see [START_REF] Guillot | Fonctions courbes binaires et transformation de Möbius[END_REF])

If f is a Boolean (n)-function then, x∈F n 2 f (x) = x∈F n 2 u∈F n 2 v∈F n 2 f (u) f (v)x u x v .
(5.21)

The next lemma expresses orthogonality between monomial functions.

Lemma 5.3.4 (see [START_REF] Guillot | Fonctions courbes binaires et transformation de Möbius[END_REF]) Let s, u ∈ F n 2 then,

x∈F n 2 (-1) HW(x) x s u x = x∈F n 2 |s x u (-1) HW(x) =    (-1) HW(u) if s = u 0 else
In particular, for s = 0,

x∈F n 2 (-1) HW(x) u x =    1 if u = 0 0 else.
As a straightforward consequence of Lemma We are now able to prove that the reduced matrix P is sufficient to get the whole polynomial matrix P . Proposition 5.3.5 An (n, m)-function can be recovered from its reduced polynomial matrix coefficients, provided that it is not a constant function.

MATRIX REPRESENTATIONS OF VECTORIAL BOOLEAN FUNCTIONS AND EIGENANALYSIS

matrix C and polynomial matrix P , are given by:

A f •g = A g A f (5.24) C f •g = C f C g (5.25) P f •g = P f P g . ( 5.26)
The following relations between matrix product and function composition also hold for reduced correlation and polynomial matrices.

C f •g = C f C g (5.27) P f •g = P f P g , ( 5.28)
where C f (resp. P f ) denotes the reduced correlation (resp. the reduced polynomial) matrix of f .

Eigenanalysis of the matrix representation

Let f be an (n, n)-function, the adjacency matrix A, the polynomial matrix P and the correlation matrix C are square matrices. This section is devoted to the eigenanalysis of these matrices. Due to the similarity relations, the eigenvalue analysis can be done on any of them.

The study of the eigenvectors depends on the matrix under consideration. However, as the adjacency matrix has exactly one nonzero component equal to 1 per row, the study is easier on this matrix. As explained in Section 5.3.1, it is possible to associate a graph G to the function f . This section establishes connections between the eigenanalysis of the matrix representations of a vectorial Boolean function and its graph representation. We show that the eigenvalues of the representation matrices are directly related to the number of cycles, to their length and to the number of leaves in the graph G. It has been mentioned in Section 5.3.6 that, the adjacency matrix A can be considered either as a Cvalued matrix or an F 2 -valued matrix. The eigenanalysis below is performed in the field C of complex number, and thus, the eigenvectors are 2 n -dimensional complex vectors. Hence, each eigenvector can be indexed by the vertices of the graph G associated to the function f , since those vertices are elements of F n 2 . Section 5.4.1 is devoted to eigenvalues. In section 5.4.2, we show how to determine the corresponding eigenvectors of the adjacency matrix from the graph G of the function f .

Eigenvalues

Proposition 5.4.1 ([37]) The eigenvalues of the matrices A, P and C are either zero or roots of unity.

Eigenanalysis of the matrix representation

The following proposition makes a connection between the eigenvalue zero and the leaves of the graph G. Proposition 5.4.2 ([37]) Let f be an (n, n)-function. Zero is an eigenvalue of the adjacency matrix A of f if and only if there exists a leaf in the graph G of f . Remark 5.4.1 The proof of Proposition 5.4.2 gives a construction of eigenvectors related to the zero eigenvalue. There exists a simpler proof. Assuming that x ∈ {0, 1} n is a leaf, the column x of the adjacency matrix A is null, which implies that the determinant of A is null too. Since this determinant equals the product of the eigenvalues, this means that 0 is an eigenvalue of A. Conversely, if 0 is an eigenvalue of A, the kernel of the endomorphism associated to A is not reduced to zero. Thus, this endomorphism is not surjective, which indicates that the graph of f has a leaf. Remark 5.4.2 If f is an (n, n)-function, let E 0 be the eigenspace of the eigenvectors associated to the eigenvalue zero of the adjacency matrix A of f . Then, the dimension of E 0 equals the number of leaves in the graph G of f . If v is an eigenvector of the eigenvalue 0 for the adjacency matrix A then, Av = 0, and this is equivalent to v f (x) = 0 for all x ∈ F n 2 . Hence, it follows that the support of v is included in the set of the leaves of the graph and then E 0 is spanned by the vectors e y as defined in the proof of Proposition 5.4.2 where y is a leaf of the graph. Remark 5.4. [START_REF] Aranda-Bricaire | Linearization of discrete-time systems[END_REF] The eigenvectors defined in the proof of Proposition 5.4.2 shows that eigenvectors can be interpreted as functions. Indeed, let f be an (n, n)-function and g an (n)-function. If g • f = 0 then the truthtable of g is an eigenvector for the eigenvalue 0 of A f . Conversely, assume that g is an eigenvector of A f associated to the eigenvalue 0 such that all its components are either zero or one then, g • f = 0. Note that whenever the eigenvectors of the adjacency matrix of f associated to 0 are obtained as explained in the proof of Proposition 5.4.2, we can determine all the Boolean functions g for which Remark 5.4.3 applies. They belong to the set of all linear combinations with {0, 1} coefficients of the eigenvectors associated to 0. There is not any other one. Hence, if there are leaves in the graph G, there are exactly 2 (n)-functions g such that g • f = 0.

We are now interested in nonzero eigenvalues. From Proposition 5.4.1, those eigenvalues are roots of unity.

Proposition 5.4.3 ([37])

Let f be an (n, n)-function, α be a nonzero eigenvalue of the adjacency matrix of f and let v be an eigenvector for the eigenvalue α. Let be the order of α and x ∈ {0, 1} n be a n-dimensional binary vector. If the component v x of vector v is nonzero, then the length of the ultimate cycle of the connected component of the graph G that contains x is multiple of .

MATRIX REPRESENTATIONS OF VECTORIAL BOOLEAN FUNCTIONS AND EIGENANALYSIS

x 1

x 2 x 3 x x f (x) f 2 (x) f i (x) = f
, f (x), f 2 (x), . . . , f i (x) = x 1
Now, let us deal with the dimension of the eigenspaces. Let us denote by E α the eigenspace associated to the eigenvalue α of the adjacency matrix of the (n, n)-function f . As stated at the beginning of Section 5.4, each eigenvector v associated to α can be indexed by the vertices of the graph G. Thus, the support of v is defined as: According to Remark 5.3.2, there always exists a cycle in the graph and thus 1 is always an eigenvalue of the adjacency matrix.

supp(v) = {x ∈ F n 2 | v x = 0} Proposition

Eigenvectors

In this section, we are interested in identifying the eigenvectors associated to the eigenvalues for the adjacency matrix A, the polynomial matrix P and the correlation matrix C. Unlike eigenvalues, eigenvectors are basis-dependent. Due to Proposition 5.3.7, eigenvectors of P and

Eigenanalysis of the matrix representation

C are easily deduced from eigenvectors of the adjacency matrix A. For each matrix, there is a natural way to derive a basis of the eigenspaces from the graph of the function.

Eigenvectors of the adjacency matrix A

The following proposition shows that the eigenvectors of the adjacency matrix A corresponding to the zero eigenvalue are deduced from the junctions of the graph G of the function f . Proposition 5.4.6 ([37]) Assume that the vertex y is a junction of the (n, n)-function f and let x 1 and x 2 be two incident vertices of this junction. Let e x1 (respectively e x2 ) be the 2 ndimensional vector such that all its components are null except the one at coordinate x 1 (respectively x 2 ) which equals 1. Then, the vector e = e x1 -e x2 is an eigenvector of the matrix A T for the eigenvalue 0. Remark 5.4.5 Conversely, if v is an eigenvector of A T for the eigenvalue 0, then the support of v is included in the set of preimages of junctions in the graph G of f . Proposition 5.4.7 Let L = (x 0 , . . . , x -1 ) be a cycle of length of the graph G associated to an (n, n)-function, and α be a th root of unity. Then, for i in {0, . . . , -1}, the complex number α i is an eigenvalue of the adjacency matrix A. For every i ∈ {0, 1, . . . , -1}, an eigenvector v of α i associated to the transpose matrix A T of A is given by: The result of Proposition 5.4.8 can be proved by noticing that for x ∈ F n 2 , the coefficient A x,x belonging to the main diagonal of the adjacency matrix A equals 1 if and only if the vector f (x) = x. Then the result holds, as the trace of a matrix is the sum of the main diagonal coefficients.

v xj =    α i( -j) if x j ∈ L 0 elsewhere. ( 5
As an example, we show how to derive the eigenstructures of A fe based on the graph of Figure 5.1. According to Proposition 5.4.6, the four eigenvectors associated to 0 are related to:

Eigenanalysis of the matrix representation

According to Proposition 5.4.7, the following eigenvectors exist and are respectively associated to the eigenvalues  and  2 , where  =

MATRIX REPRESENTATIONS OF VECTORIAL BOOLEAN FUNCTIONS AND EIGENANALYSIS

Therefore:

∀y ∈ F n 2 , v y = x∈F n 2
(-1) HW(x)-HW(y) y x v x .

In the case when v is an eigenvector of A associated to the eigenvalue 0, the support of v is included in the set of the leaves of the graph G.

Application to Self-Synchronizing Stream Cipher

In Parriaux's thesis [START_REF] Parriaux | Control, synchronization and encryption[END_REF], it had been shown that the correlation matrix C g θ of the state transition function g θ in (2.6) determines whether g θ is based on a T-function or not. This provides a more general approach to characterize the category of state transition function. The approach provided in Section 2.5 of Chapter 2 is straightforward but works only for LPV systems, since in this case the expression of the inverse transition matrix P ρ(k:k+r) characterizes entirely the triangular structure of g θ . Note that g θ can be expressed as a (n, m)-function when the base field is F 2 . For a sake for simplicity we will denote in the sequel g θ by g.

Let us consider the partial function g c : F n 2 × F n 2 with g c (q k ) = g(q k , c), and c ∈ F ns 2 . We recall the following Proposition from [START_REF] Parriaux | A constructive approach for the design of selfsynchronizing dynamical systems: an application to communications[END_REF]. We show in the following example that the LPV-based SSSC designed from the graph approach in Chapter 2 provides a state transition function g that is not based on a T-function.

Example 5.5.1 Let us consider the system of dimension n = 2 in Example 2.5.1, where the parameters are elements of the finite field F 2 . The input matrix A ρ(k) is given by:

A ρ(k) = ρ 1 (k) ρ 2 (k) 1 ρ 3 (k) with ρ i (k) : F 2 -→ F 2 c k → f (c k )
We consider all the functions ρ i , i = 1, 2, 3 as the identity function. From Equation (1.9), we have n s = 3 and the inverse transition matrix P ρ(k:k+2) is given by:

P ρ(k:k+2) = c k+1 c k • c k+1 1 c k

Application to Self-Synchronizing Stream Cipher

Hence, from (2.13), the partial state transition function reads:

g c : F 2 2 → F 2 2 (q 1 k , q 2 k ) -→ c k • q 1 k + c k • c k+1 • q 2 k + c k+2 , q 1 k + c k • q 2 k
The expressions of the eight partial functions g c , c ∈ F 3 2 are provided in Table 5.2.

c q k (0,0) (0,1) (1,0) (1,1) 000 (0,0) (0,0) (0,1) (0,1) 001 (1,0) (1,0) (1,1) (1,1) 010 (0,0) (0,0) (0,1) (0,1) 011 (0,1) (0,1) (1,1) (1,1) 100 (0,0) (0,1) (1,1) (1,0) 101 (1,0) (1,1) (0,1) (0,0) 110 (1,0) (1,1) (0,1) (0,0) 111 (0,0) (0,1) (1,1) (1,0) Table 5.2: Table of the partial functions g c , with c = c k c k+1 c k+2 and q k = (q 1 k , q 2 k ).
The reduced correlation matrices are given by: shows that these matrices are not simultaneously triangularizable. As

C g000    0 4 0 0 0 0 0 4 0    C g001    0 4 0 0 0 0 0 -4 0    C g010    0 4 0 0 0 0 0 4 0    C g011    0 0 0 0 4 0 0 -4 0    C g100    0 0 4 0 4 0 4 0 0    C g101    0 0 4 0 -4 0 -4 0 0    C g110    0 0 4 0 -4 0 -4 0 0    C g111    0 0 4 0 4 0 4 0 0   

MATRIX REPRESENTATIONS OF VECTORIAL BOOLEAN FUNCTIONS AND EIGENANALYSIS

conclusion the state transition function g is not based on a T-function according to Proposition 5.5.1.

Conclusion

In this chapter, a unified overview on the various representations of vectorial Boolean functions, namely the Walsh matrix, the correlation matrix and the adjacency matrix, has been given. A new representation called polynomial matrix has been introduced with an interest when dealing with algebraic properties. It has been shown that those different representations are similar.

Then, an eigenanalysis of those representations has been performed. It has been shown that, for all the representations, the eigenvalues are either zero or roots of unity. For a given vectorial Boolean function with the same number of inputs and outputs, a link has been made between the eigenvalues of its matrix representations and the structure of the graph assigned to this function. The distinction between zero and nonzero eigenvalues plays an important role for that purpose. Finally, the eigenspace associated to the eigenvalues of the matrix representations has been studied. For nonzero eigenvalues, the corresponding eigenvectors can be determined from the cycles of the graph. On the other hand, the eigenvector corresponding to the zero and unique eigenvalue can be determined by the junctions of the graph.

General Conclusions and Perspectives

The aim of this thesis was to propose a new architecture of Self-Synchronizing Stream Ciphers whose next-state function is not based on T-functions and by using LPV systems with flat outputs.

In Chapter 1, an algebraic property has been proposed to characterize LPV systems with flat outputs. A complementary approach based on digraph has been proposed and provides a systematic way to design such LPV systems with flat outputs.

Chapter 2 focuses on SSSC and their representation as automata is provided. Thus a complete framework has been proposed and it is shown how to design LPV-based SSSC and how to replace the parameters within the obtained LPV system with cryptographic primitives such as S-Boxes using secret keys.

Chapter 3 tackles physical security issues of the designed LPV-based SSSC. In particular a spectral approach based on Fourier Transform is proposed in order to perform a side-channel attack. This attack works on the S-Box used within the LPV-based SSSC and can be applied on any other encryption algorithm that involves S-Boxes. Also a multidimensional attack has been proposed from the Fourier transform approach and allows to perform the attack at different times of the encryption process.

Chapter 4 focuses on theoretical security aspects of SSSC by considering their canonical form. It gives a necessary and sufficient condition of the filtering function of the canonical form of SSSC in order to achieve IND-CPA security. Besides it has been show that SSSC cannot achieve IND-CCA security.

Finally Chapter 5 gives results on matrix representations of vectorial boolean functions. The representations that are given are similar. Especially one of the representations that is the correlation matrix characterizes the type of state transition function of a SSSC: that is whether this function is based on a T-function or not. Furthermore, we show that the LPV-based SSSC designed in this thesis admits a state transition function that is not based on a T-function. This provides interesting perspectives to check the class of the state transition function from other approaches that can provide SSSC, other than the graph approach.

The subjects on which we focused in this thesis still leave several questions open:

GENERAL CONCLUSIONS AND PERSPECTIVES

Statistical SSSC. Statistical SSSC had not been tackled in this thesis. However it remains an open topic in the literature [START_REF] Geraldy | Optimized selfsynchronizing mode of operation[END_REF][START_REF] Howard | An analysis of the statistical self-synchronization of stream ciphers[END_REF]. A statistical SSSC is such that the synchronization delay is not bounded by any value and is a random variable. It then may depend on a pattern of ciphertexts or/and the initial state of the scheme. In Chapter 1, the graph-oriented approach provides sufficient and necessary structural conditions and a systematic way to construct LPV systems with flat output that can be used as SSSC. One can break this flatness property by altering one of these conditions. Besides, the algebraic characterization of the flatness property ensures that a combination of flat LPV system and non-flat LPV system can be also used as an SSSC. Hence the combination of these two systems can be used to provide statistical SSSC. For example one can switch between the two systems by checking whether previous ciphertexts match with a pattern of given ciphertexts.

• Matrix diffusion. The synchronization property of the LPV-based SSSC is mainly characterized by the inverse transition matrix. And this matrix is central in the study of the security of the scheme. The non-zero coefficients of this matrix can be replaced by S-Boxes as shown in Chapter 2, to increase the confusion of the scheme and make it resistant against well-known attacks such as linear, differential or distinguishers attacks [START_REF] Biham | Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials[END_REF][START_REF] Knudsen | Deal -a 128-bit block cipher[END_REF][START_REF] Bogdanov | Zero-correlation linear cryptanalysis of block ciphers[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF]. Hence the settings of the S-Boxes to achieve such resistances should be studied in more details compared to the work of Section 2.6. The diffusion of the entries of the inverse transition matrix P ρ(k:k+r) should be as complex as possible when considering its successive powers.

• Hardware implementation. Specifications have been provided to the industrial partner (Airbus Defence and Space) and have been implemented successfully on FPGA cards. However it could be interesting to make the architecture more compact by improving the circuitry for hardware, and also to reduce the cost of implementation by optimizing the use of cryptographic primitives or subkeys generation in the hardware.

• Correlation Power Analysis. The CPA attack proposed in Chapter 3 requires the calculation of the Fourier Transform of the leakage model g and then a number of traces equals to 2 n where n is the size of the input word of g. It would be interesting to see whether the number of traces could be reduced. It means that the attack could be achieved with an approximate value of the Fourier transform. In this case, the multidimensional attack would have a further interest as it can combine reduced Fourier transform for several leakage models. Furthermore, it remains to check how these improvements behave with countermeasures that have been proposed to resist such attack [START_REF] Itoh | DPA countermeasures by improving the window method[END_REF], [START_REF] Mamiya | Efficient countermeasures against RPA, DPA, and SPA[END_REF], [START_REF] Moradi | Lightweight cryptography and DPA countermeasures: A survey[END_REF], [START_REF] Tillich | Attacking state-of-the-art software countermeasures-a case study for AES[END_REF].

Block ciphers are used for symmetric encryption. This is an extension of simple substitution. The data to encrypt is subdivided in blocks of the same length, for example 64 or 128 binary symbols. A keyed reversible transformation is then performed on each block, involving an encryption algorithm denoted E k , to get the corresponding ciphertext block. The inverse transformation is performed in order to decrypt the ciphertext blocks. Block cipher is suitable to perform securely encryption or decryption on a single block of data. But encrypting a long plaintext for example requires to run repeatedly the block cipher within a mode of operation. We describe many mode of operations that use block ciphers. Some of the modes of operation act like SSSC. The Electronic CodeBook mode (ECB) performs a simple substitution. The message to encrypt is subdivided in block of the same length and all the blocks are encrypted the same way. This mode of operation is not semantically secure [START_REF] Bellare | Introduction to modern cryptography[END_REF].

m 1 m 2 m • • • E k E k E k c 1 c 2 c • • •

A. BASICS ON BLOCK CIPHERS AND SELF-SYNCHRONIZING STREAM CIPHERS

The Cipher Block Chaining (CBC) mode is another way to perform a block encryption. Here, the output block of the encryption algorithm E k is XORed to the next block of the plaintext. Then the resulting block is encrypted to produce the next output (the ciphertext). Note that to decrypt a block m i of the plaintext, we only need the ciphertexts c i and c i-1 :

m i = c i-1 ⊕ E -1
k (c i ). It turns out that this mode of operation can be used as SSSC on block of data.

m 1 m 2 m • • • + + + E k E k E k c 1 c 2 c c 0 • • • • • • • • • IV Figure A.2:
Chaining mode or Cipher Block Chaining (CBC) mode. The ciphertext block is XORed to the next plaintext block such that every ciphertext block depends on the previous blocks. This mode requires an Initial Vector (IV) block to start the chaining. This IV should be generated randomly and shared through a secure channel between the emitter and the receiver.

In Cipher FeedBack (CFB) mode, the last ciphertext is used as input of the encryption algorithm E k to produce an output that is XORed to the next plaintext to get the next ciphertext. This mode of operation is suitable to be used as SSSC to encrypt plaintext whose size is lower than the block size (see also Section 2.3 of Chapter 2). A shift register is used in this case to gather previous ciphertexts that are used as input of the encryption algorithm E k . x + 3

IV E k E k • • • E k + + + • • • c 1 c 2 • • • c m 1 m 2 m
E k E k E k + + + c 1 c 2 c 3 m 1 m 2 m 3
Figure A.4: CTR mode or counter mode. The mask is obtained as the encryption of a counter value that is initialized at given value x. The value of the counter is incremented, for each block, and used to produce another mask that is XORed to the plaintext block to get the ciphertext block.

A.2 Existing Self-Synchronizing Stream Cipher schemes A.2.1 The Self-Synchronizing Stream Cipher HBB

HHB is a stream cipher designed by Palash Sarkar in [START_REF] Sarkar | Hiji-bij-bij: A new stream cipher with a self-synchronizing mode of operation[END_REF]. The cipher operates in two modes: a basic mode as a synchronous stream cipher and a self-synchronizing mode. It operates on 128-bit data block and its internal state is partitioned into a linear core of 512 bits denoted LC and a non-linear core of 128 bits denoted NLC. The cores are updated by XORing a register that contains previous ciphertexts with an expansion of the secret key. Unlike others designed SSSC, HHB general structure is similar to a block cipher structure (internal state update in many rounds, input and output are blocks). The following algorithm describes the self-synchronizing mode of HBB: For a message M = M 0 • • • M n-1 to be encrypted with a key K of 128-bits, the corresponding ciphertext is given by the algorithm described below: HBB(M ,K) The keystream z k corresponds to K i and the keystream generator σ ss θ is a combination of the functions Round, Fold and Exp: [START_REF]FIPS publication 197 -advanced encryption standard[END_REF].

   z i = σ ss θ (C i , C i-1 , C i-2 , C i-3 ) C i = K i ⊕ M i with σ ss θ (C i , C i-1 , C i-2 , C i-3 ) = Round Exp(K) ⊕ (C i C i-1 C i-2 C i-3 ), Fold(K, 128) ⊕ C i ⊕ C i-1 ⊕ C i-2⊕Ci-3
Two cryptanalysis of HBB have been proposed: a known-plaintext attack in [START_REF] Klíma | Cryptanalysis of hiji-bij-bij (HBB)[END_REF] that recovers the whole key K in 2 66 HBB operations and a differential attack using chosen ciphertexts in [START_REF] Joux | Two attacks against the HBB stream cipher[END_REF] that also recovers the whole key.

+ M i C i K i

A.2.2 The Self-Synchronizing Stream Cipher SSS

SSS is a self-synchronizing that belongs to SOBER stream ciphers family proposed in [START_REF] Hawkes | Primitive specification for sss[END_REF]. The scheme allows self-synchronization, message authentication code and integrity. It is based on 16-bit operations and 16-bit blocks. Additions and multiplications related to the operations are performed in the finite field GF(2 16 ). The internal state of the scheme is made of 17 blocks of 16 bits called a vector of words. Update of the blocks relies on rotation operations, right shifting, addition on GF(2 16 ) and XOR as illustrated in Figure A.6. The scheme uses a nonlinear keyed function f . Despite the fact that the nonlinear function used in the scheme admits good properties as a high nonlinearity, balanced and pairwise uncorellated, a very efficient attack has been proposed against SSS in [START_REF] Daemen | Chosen ciphertext attack on SSS. eS-TREAM, ECRYPT Stream Cipher Project[END_REF]. The way the function f is used and also the T-function-like structure of the internal state defaults the scheme. The attack that has been performed is a chosen ciphertext attack that can compute the output of the function f without knowing the A.2 Existing Self-Synchronizing Stream Cipher schemes key and hence recovers the entire secret key.

A.2.3 Family of the Self-Synchronizing Stream Cipher MOUSTIQUE.

The SSSC MOUSTIQUE [START_REF] Daemen | The self-synchronizing stream cipher moustique[END_REF] belongs to a family of SSSC that are KNOT, ΥΓ, MOUSQUITO and that had been designed by Daemen et al. They had been upgraded subsequently after a weakness was find in their design.

The SSSCs belonging to MOUSTIQUE SSSC family, admit all an architecture that relies on the one proposed by Maurer [START_REF] Ueli | New approaches to the design of self-synchronizing stream ciphers[END_REF]. Daemen and al. pointed out that is was not very efficient to recompute the whole function g θ based on serial and parallel automata as proposed by Maurer. And their schemes have been designed to be efficient in one hand relatively to security with regard to more general attacks than the ones considered by Maurer; and in the other hand relatively to speed and easy implementation for hardware.

In the new architecture that they propose, the update function g θ in Equation (2.10) is implementing in a shift-register-like architecture called Complementing Shift Register (CCSR (see Figure (A.7))). It makes the computation of the internal state more complex. The architecture is pipelined providing a very fast gate delay. There is no key used in the filtering function, because the inputs of the filtering function are unknown values that depend on the key and have been calculated by the CCSR. Like the other designed SSSCs, the architecture is also based on a T-function. One can observe that the propagation goes always in the direction of increasing indexes. This guarantees that the influence of old ciphertext bits eventually vanishes, which makes the resynchronization possible.

KNOT had been tweaked in ΥΓ after the authors discovered later a statistical imbalance in the output function. Besides this security issue, another weakness has been discovered by Joux and Muller in [START_REF] Joux | Loosening the KNOT[END_REF]. They proposed an attack based on differential cryptanalysis that detects v

A. BASICS ON BLOCK CIPHERS AND SELF-SYNCHRONIZING STREAM CIPHERS

collisions in the internal state register of the scheme. MOSQUITO [START_REF] Daemen | The self-synchronizing stream cipher mosquito: estream documentation, version 2[END_REF] was an upgraded version of ΥΓ. Despite the efficiency of its structure, considering speed and the complexity of the update function, it has been broken in [START_REF] Joux | Chosen-ciphertext attack against mosquito[END_REF]. The weakness disclosed in MOSQUITO has been removed and the scheme has been upgraded to MOUSTIQUE.

The improvement to MOUSTIQUE offers resistance against attacks that make previous SSSC weak. However, in [START_REF] Käsper | Correlated keystreams in moustique[END_REF], the authors apply successfully a correlation keystream-based attack by exploiting a weakness in the output of some boolean function used in the design of MOUSTIQUE.

Résumé

Nous présentons dans le cadre de cette thèse une construction effective de chiffreurs par flot auto-synchronisants centrée autour de la classe particulière des systèmes dynamiques Linear Parameter Varying (LPV). Il s'agit de systèmes dont la représentation d'état admet une écriture affine par rapport à l'état et l'entrée mais dont les matrices de la représentation dépendent de paramètres variants dans le temps. Cette dépendance peut se traduire par des fonctions non linéaires de la variable de sortie. La dynamique résultante est donc non linéaire. Nous montrons que la propriété d'auto-synchronisation est liée à une propriété structurelle du système dynamique à savoir la platitude. La platitude est une propriété algébrique qui permet d'exprimer lorsque cela est possible les paramètres d'entrée et sortie d'un système dynamique en fonction de sa sortie qui est appelée dans ce cas une sortie plate. Une caractérisation de la platitude est exprimée en termes des matrices d'état du système dynamique. Une caractérisation complémentaire est proposée en termes de propriétés d'un graphe d'adjacence associé. L'utilisation conjointe de la caractérisation algébrique et graphique donne lieu à une construction systématique d'une nouvelle classe de chiffreurs auto-synchonisants.

Dans la deuxième partie de la thèse, nous nous intéressons à la sécurité de chiffreurs auto-synchronisants. Nous proposons dans un premier temps une approche spectrale pour réaliser une attaque par canaux cachés. Cette approche offre une complexité réduite par rapport aux approches classiques utilisées pour les attaques par canaux cachés. Nous donnons ensuite une preuve de sécurité de la forme canonique d'un chiffreur auto-synchronisant basée sur la notion d'indistinguabilité. Une condition nécessaire et suffisante pour caractériser l'indistinguabilité des chiffreurs auto-synchronisants est proposée. Finalement, nous avons établi des résultats sur les propriétés de fonctions vectorielles booléennes qui permettent de caractériser d'une façon générale les chiffreurs auto-synchronisants.

Mots clés: Systèmes LPV, platitude, chiffreur par flot auto-synchronisant, preuve de sécurité, attaque par canaux cachés

Abstract

In this thesis, we present an effective construction of self-synchronizing stream ciphers based on the class of Linear Parameter-Varying (LPV) dynamical systems. For such systems, the state-space representation admits an affine expression regarding the input and the state but the state matrices depend on time varying parameters. This dependence can be expressed using nonlinear functions of the output variable. Hence, the resulting dynamics of the system are nonlinear. We show that the self-synchronization property is related to a structural property of the dynamical system known as flatness. Flatness is an algebraic property that allows, when possible, the expression of the input and state parameters of a dynamical system as functions of its outputs which is then called flat output. A characterization of the flatness is expressed in terms of state matrices of the dynamical matrix. A complementary characterization is given in terms of properties of the related adjacency graph. The combination of the algebraic and graph theory characterization gives a systematic construction of a new class of self-synchronizing stream ciphers.

In the second part of the thesis, we tackle security aspects of self-synchronizing stream ciphers. We propose a spectral approach to performing side channel attacks. This approach offers reduced complexity when compared with standard approaches used for side channel attacks. We also give a security proof, based on the notion of indistinguishability, for the canonical form of self-synchronizing stream ciphers. A neccessary and sufficient condition is proposed in order to characterize the indistinguishability. Finally, we establish some results on vectorial boolean functions and properties they can be achieved when trying to design Self-Synchronizing Stream Ciphers. Keywords: LPV systems, flatness, self-synchronizing stream cipher, proof of security, side channel attack xxi

  Si le système LPV (1) admet un degré relatif r, alors y k est une sortie plate si et seulement si il existe un entier positif K tel que pour tout entier relatif iii R ÉSUM É D ÉTAILL É DE LA TH ÈSE k ≥ 0 et pour toute séquence {ρ(k), . . . , ρ(k + K -1 + r)} ∈ Θ r+K , la condition suivante est vérifiée: P ρ(k+K-1:k+K-1+r) P ρ(k+K-2:k+K-2+r) • • • P ρ(k:k+r) = 0 (5) avec P ρ(k:k+r) = A ρ(k) -B ρ(k) (T r,0 ρ(k) ) -1 C ρ(k+r) k l=k+r-1

Figure 2 :

 2 Figure 2: Forme canonique d'un SSSC pour l = 1.

Figure 3 :

 3 Figure 3: Architecture d'un SSSC basée sur un automate à mémoire finie.

Figure 1 . 2 : 1 . 1 . 3 . 2

 121132 Figure 1.2: Digraph associated to Example 1.3.1.

Figure 1 . 3 : 2 Example 1 . 3 . 3

 132133 Figure 1.3: Digraph associated to Example 1.3.2

Figure 1 . 4 : 3 Example 1 . 3 . 4

 143134 Figure 1.4: Digraph associated to Example 1.3.3

Figure 1 . 5 :

 15 Figure 1.5: Digraph associated to Example 1.3.4

1 .Example 1 . 3 . 5

 1135 search flat outputs by considering the related digraph of (1.1) and by checking Conditions C0-C2 of Theorem 1.3.1 2. find the relative degree r and the quantity K for the flat output by applying Propositions 1.3.1 and 1.3.2 3. finally find F and G by applying Equations (1.16) and (1.17). Let us consider the system of Example 1.2.1.

Figure 1 . 6 :

 16 Figure 1.6: Digraph of the linear structured system associated to the LPV system (1.3). .

Figure 2 . 1 :

 21 Figure 2.1: Canonical form of SSSC for l = 1.

Figure 2 . 2 :

 22 Figure 2.2: SSSC in CFB mode. A shift register is used to gather the previous ciphertexts. The output of the encryption algorithm E k is filtered with a function h to produce a 1-bit keystream z k that is XORed to the plaintext m k .

Figure 2 . 3 :

 23 Figure 2.3: Serial and parallel automata in the architecture proposed by Maurer.

Figure 2 . 5 :

 25 Figure 2.5: Digraph obtained after completion of Steps 1-2. The vertex v r corresponds to the flat output.

Figure 2 . 6 :

 26 Figure 2.6: Graph obtained after Steps 1-5.

Figure 2 . 7 :

 27 Figure 2.7: Graph obtained after completion of Steps 1-6.

Remark 2 . 4 . 1 2 . 4

 24124 By considering the flat LPV system related to the graph of Figure 2.7, it follows from Remark 1.3.6 that the integer K involved in Theorem 1.2.1 is bounded by the dimension n Construction of SSSC Based on Digraph of this flat LPV system. Hence the synchronization delay M of the flat LPV system is bounded by n.

Figure 2 . 8 :

 28 Figure 2.8: Digraph obtained for n = 2, r = 2, n a = n M = 5. The flat output is y F = x 2 and corresponds to the vertex v 2 .

Theorem 2 . 4 . 1

 241 Let Σ be a flat LPV system (1.1) of relative degree r = 1. Then the next-state function f of an LPV-based SSSC (1.1) is conjugated to a T-function.

Figure 2 . 10 :

 210 Figure 2.10: Graph structure related to the matrix P (ρ:k+6)

Figure 2 .

 2 Figure 2.11: Non-zero diffusion delay probability with respect to the number n a of non-zero coefficients in the inverse transition matrix P ρ(k:k+3) .

Figure 2 . 12 :

 212 Figure 2.12: Arduino mega 2560 card

Figure 2 .

 2 Figure 2.13: Supervisor

Contents 3 . 1 52 3. 2 52 3. 3 55 3. 3 . 1 55 3. 3 . 2 56 3. 3 . 3 56 3. 3 . 4 58 3. 4 64 3. 4 . 1 64 3. 4 . 2 68 3. 5

 31522523553155325633563458464416442685 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Preliminaries on Spectral Analysis . . . . . . . . . . . . . . . . . . Modelling the Attack . . . . . . . . . . . . . . . . . . . . . . . . . . Physical principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . Target of the Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . General CPA approach . . . . . . . . . . . . . . . . . . . . . . . . . . Spectral Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . Application of the attack on a simple S-Box . . . . . . . . . . . . . . Application of the attack to the algorithm THE CASCADE . . . . . Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

4 ) 3 . 2 . 4 (

 4324 Proposition Fourier Transform of a constant[START_REF] Guillot | Spectral approach for correlation power analysis[END_REF]) Let k ∈ {0, 1} n . The Fourier transform of the constant function x -→ k is:

Figure 3 .

 3 Figure 3.1: CMOS technology

Step 3 :

 3 calculate hypothetical values from the intermediate values Step 4: mapping the hypothetical values to power consumption values

Figure 3 . 2 :

 32 Figure 3.2: Block diagram of the different Steps of a general CPA attack.

Figure 3 . 3 :+Figure 3 . 4 :

 3334 Figure 3.3: Test bench.

Figure 3 .

 3 Figure 3.5 is an example of consumption trace and the corresponding consumption signal. The time window ∆ t during the computation of the four successive operations f (d + k i ) (i = 1, . . . , 4) is the range of time when the 256 traces of consumption are memorized in the oscilloscope. The 256 trace records are each composed of 40 000 samples.Figure 3.6 is a magnified part of the time window ∆ t .

Figure 3 . 5 :

 35 Figure 3.5: Whole data exchanges (up) and the corresponding consumption signal (down).

Figure 3 . 6 :Figure 3 . 7 ,

 3637 Figure 3.6: Zoom on the time range ∆ t highlighting the first falling edge of the card response used for the synchronization of the traces.

Figure 3 . 7 :

 37 Figure 3.7: Correlation peaks that correspond to scenario i).

Figure 3 . 8 :

 38 Figure 3.8: Correlation peaks that correspond to scenario ii).

Figure 3 . 9 :

 39 Figure 3.9: Correlation peaks that correspond to scenario iii). The two-dimensional attack considers the times instants t and t + 4.2µs.

Figure 3 . 10 :

 310 Figure 3.10: Correlation peaks when no key is found.

Figure 3 . 11 :

 311 Figure 3.11: Correlation peaks when performing CPA attack on the encryption algorithm THE CASCADE.

Figure 4 . 1 :

 41 Figure 4.1: Canonical form of a SSSC. Left: the encryption. Right: the decryption.

2 .

 2 For each symbol at instant k, (a) Compute the keystream symbol as z k = σ ss θ ( q k ). (b) Compute the plaintext symbol as m k = c k ⊕ z k .

Remark 4 . 3 . 2

 432 The sequence of couples transmitted by the oracle at Step 2 corresponds exactly to the parameters and the values of the canonical SSSC filtering function during the encryption process of the message m. Given this sequence, the cryptogram is deduced by:

2 . 3 .

 23 The oracle randomly chooses a binary digit b ∈ {0, 1}, encrypts the message m b and returns the cryptogram to the challenger. The challenger is challenged to guess the value of b, that is which of the two messages has been encrypted. The answer of the challenger is a binary value b. The challenger wins if b = b.

  any b and b in the set {0, 1}, let Pr m b (A = b) be the probability that the challenger A answers b given the ciphertext which corresponds to the encryption of the message m b . The advantage of A in this IND-game is by definition: Adv(A) = Pr m0 (A = 0) -Pr m1 (A = 0) .

2 . 3 .

 23 The challenger sends to the oracle a polynomial number of queries in the form of couples of messages (m i 0 , m i 1 ). The oracle encrypts either the message m i 0 or the message m i 1 depending on the bit b chosen during Step 1. It returns to the challenger the cryptogram c i of the message m i b . After a polynomial number of queries, the challenger is challenged to guess the value of the bit b chosen by the oracle. The response of the challenger is a binary value b ∈ {0, 1}. The challenger wins if b = b. Likewise the IND-game, the advantage of a challenger A in the LOR-IND-game is defined by: Adv(A) = Pr b=0 (A = 0) -Pr b=1 (A = 0) = 2 Pr(b = b) -1 A ciphering scheme is said to have the LOR-IND property if any polynomial adversary has a negligible advantage in the LOR-IND-game.

Proposition 4 . 4 . 1 ( 4 . 5

 44145 [38]) If a ciphering scheme reaches the LOR-IND-CPA property, then it reaches the IND-CPA property. Proof. By contraposition, assume that a challenger A against the IND-CPA property exists. A challenger B against the LOR-IND property is constructed from A: Security proof of the canonical SSSC Proposition 4.5.2 ([38]) A canonical SSSC reaches the LOR-IND security if and only if the filtering function is WPRF-family.

  A answers a bit b ∈ {0, 1}. If b = b then B answers wprf, and if b = b then she answers rf.

4 .Corollary 4 . 5 . 1 ([ 38 ])

 445138 After a polynomial number of queries, the challenger B returns an answer: rf or wprf. If B answers wprf, then A returns b = 0 and if B answers rf, then A returns b = 1. If the LOR-IND oracle chooses b = 0, then its answers to B correspond to the encryption of the binary sequences provided by A, and B acts as an oracle for A in the WPRF world. Conversely, if the LOR-IND oracle chooses b = 1, and as the sequences a i are random, B acts as an oracle for A in the rf world. As a consequence, the advantage of B in the LOR-IND game equals exactly the advantage of A in the WPRF game and that achieves the proof. From the above propositions, the following result holds: If the filtering function of a canonical SSSC is PRF, then it achieves the IND-CPA security. Proof. Assume that the filtering function of a canonical SSSC is PRF. From Proposition 4.3.1, it is WPRF. From Proposition 4.5.2, the canonical SSSC also achieves the LOR-IND security, and finally, from Proposition 4.4.1, it achieves the IND-CPA security too.

Contents 5 . 1 84 5. 2 84 5. 2 . 1 85 5. 2 . 2 86 5. 3 88 5. 3 . 1 91 5. 3 . 3

 518428421852286388319133 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Boolean functions representations . . . . . . . . . . . . . . . . . . Fourier/Walsh transform . . . . . . . . . . . . . . . . . . . . . . . . Polynomial representations . . . . . . . . . . . . . . . . . . . . . . . Vectorial Boolean functions representations . . . . . . . . . . . . Adjacency matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.3.2 Walsh/correlation matrix . . . . . . . . . . . . . . . . . . . . . . . . Reduced Walsh/correlation matrix . . . . . . . . . . . . . . . . . . . 92 5.3.4 Polynomial matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 5.3.5 Reduced Polynomial matrix . . . . . . . . . . . . . . . . . . . . . . . 93

Definition 5 . 3 . 2 (

 532 Graph associated to a function (see[START_REF] Franc | Discrete iterations : a metric study[END_REF])) Let f be an (n, n)function. The graph associated to f is defined by the set of vertices V = F n 2 and the set of arcs E that are the ordered pairs (x, y) ∈ F n 2 × F n 2 such that y = f (x).

Figure 5 . 1 :

 51 Figure 5.1: Graph associated to the function f e .

Remark 5 . 3 . 2 Remark 5 . 3 . 3

 532533 As the set of vertices of the graph of a (n, n)-function is finite, the graph contains at least one cycle. If there is no leaf, then the graph is a union of cycles and it contains no junction. Besides, each new leaf, either adds a new junction or increases the multiplicity of an existing junction by one. As a consequence, the number of leaves equals the sum of the multiplicities of the junctions.

Corollary 5 . 3 . 1

 531 If f is an (n, m)-function and g is a (p, n)-function then:

Figure 5 . 2 :

 52 Figure 5.2: Cycle of vertices. The vertex x of the connected component is connected to its ultimate cycle by a path of length i whose elements are the iteration of the (n, n)-function f on the vertex x. This path is x, f (x), f 2 (x), . . . , f i (x) = x 1

5 . 4 . 4 ( 1 .

 5441 [START_REF] Dravie | Matrix representations of vectorial Boolean functions and eigenanalysis[END_REF]) Let α be a nonzero eigenvalue of the adjacency matrix of the (n, n)function f and C be a connected component of the graph G whose ultimate cycle length is multiple of the order of α. Then, the subspace of E α of the vectors whose support is included in C is of dimensionThe following proposition gives the dimension of the eigenspace E α .Proposition 5.4.5 ([37])Let α be a nonzero eigenvalue of the adjacency matrix of an (n, n)function. The dimension of the vectorspace E α equals the number of cycles in the graph G whose length are multiple of the order of α.

Corollary 5 . 4 . 1

 541 Let f be an (n, n)-function. The function f is an involution if and only if the eigenvalues of its adjacency matrix are either -1 or 1.

Remark 5 . 4 . 4

 544 According to Remark 5.3.3, from each junction of multiplicity k in G, it is possible to get k independent eigenvectors of A T for the eigenvalue 0.

. 29 ) 5 . 4 . 8 (Remark 5 . 4 . 6

 29548546 Proposition[START_REF] Dravie | Matrix representations of vectorial Boolean functions and eigenanalysis[END_REF]) The trace of the adjacency matrix of f is the number of cycles of length one. As the trace is invariant under similarities, Proposition 5.4.8 also holds for polynomial and correlation matrices. Remark 5.4.7

Proposition 5 . 5 . 1

 551 Assume that the system (2.6)-(2.10) is finite-time self-synchronizing. And let us consider its state transition function g and the related partial functions g c , c ∈ F ns 2 . Then g is not based on a T-function if all the reduced correlation matrices C gc, are not simultaneously triangularizable.

Figure A. 1 :

 1 Figure A.1: Electronic CodeBook mode (ECB). The ciphertext is subdivided in blocks and every block is encrypted independently.

Figure A. 3 :

 3 Figure A.3: Cipher FeedBack mode (CFB). The mask is obtained as the encryption of the previous ciphertext block. An IV is then used to compute the first mask. The cipheretxt block is the result of the mask XORed to the plaintext block.

1 .

 1 LC = EXP(K); F = Fold(K,64); NLC = F F 2. for i = 0 to 15 do (T imod4 , LC,NLC) = Round(LC,NLC);3. LC-1 = LC ⊕ (T3 T2 T1 T0), NLC-1 = NLC; C-3 = T3; C-2 = T2; C-1 = T1; 4. for i = 0 to n -(K) ⊕ (Ci Ci-1 Ci-2 Ci-3); 8. NLCi = Fold(K, 128) ⊕ Ci ⊕ Ci-1 ⊕ Ci-2⊕C i-3 ; 9. output C0 • • • Cn-1;the function Fold(S,i) computes the sum on i-bit blocks of S, that is Fold(S,i) = k j=1 S j with |S j | = i. And the function Exp(K) is an expansion of the key K that concatenates it with its opposite: Exp(K) = K K. The lines 8 and 9 show that the internal state is a shift of the previous ciphertexts. The function Round is a non-linear transformation that performs iii A. BASICS ON BLOCK CIPHERS AND SELF-SYNCHRONIZING STREAM CIPHERS successive operations of permutation and transposition on the linear core and the non-linear core to produce the keystream. Hence, the round function can be identified to a filtering function. The corresponding figure is given in Figure A.5.

Figure A. 5 :

 5 Figure A.5: The Self-Synchronizing Stream Cipher HHB. One round of HBB.

Figure A. 6 :

 6 Figure A.6: The Self Synchronizing Stream Cipher SSS. The symbol >>> stands for rotation of the bits to the right, + stands for the addition on GF(16) and + stands for XOR.

Figure A. 7 :

 7 Figure A.7: MOUSTIQUE SSSC. Architecture of SSSC of the family of MOUSTIQUE. The CCSR is described on right.

1 LPV Systems and Characterization of Flatness 5

  Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

1.1 Linear Parameter Varying Systems . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Difference Flatness for LPV Systems . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.1 Direct approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.2 Inverse system approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.3 Mortality problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Graph Approach to Characterize Flat Outputs . . . . . . . . . . . . . . . . . . . 13 1.3.1 Necessary and sufficient conditions for flatness based on a digraph . . . . 14 1.3.2 Illustrative examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3.3 Connection with the algebraic conditions . . . . . . . . . . . . . . . . . . 19 1.3.4 Search procedure for flat outputs . . . . . . . . . . . . . . . . . . . . . . . 21 1.4

2 Flat LPV Systems and Self-Synchronizing Stream Ciphers 27

  2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2 Generalities on Symmetric Cryptography . . . . . . . . . . . . . . . . . . . . . . 29 2.2.1 Block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2.2 Stream ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2.2.1 Synchronous Stream Ciphers . . . . . . . . . . . . . . . . . . . . 30 2.2.2.2 Self-Synchronizing Stream Ciphers . . . . . . . . . . . . . . . . . 31 2.3 Architectures of Self-Synchronizing Stream Ciphers . . . . . . . . . . . . . . . . . 32

  Zoom on the the target power consumption signal . . . . . . . . . . . . . . . . . 3.7 Correlation peaks scenario i) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Correlation peaks scenario ii) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 Correlation peaks scenario iii) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.10 Correlation peaks when no key is found. . . . . . . . . . . . . . . . . . . . . . . . 3.11 Correlation peaks when performing CPA attack on the encryption algorithm THE CASCADE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Canonical form of a SSSC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cipher Block Chaining mode (CBC) . . . . . . . . . . . . . . . . . . . . . . . . . ii A.3 Cipher FeedBack mode (CFB) . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii A.4 CTR mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii A.5 The Self-Synchronizing Stream Cipher HHB . . . . . . . . . . . . . . . . . . . . iv A.6 The Self Synchronizing Stream Cipher SSS . . . . . . . . . . . . . . . . . . . . . v A.7 MOUSTIQUE SSSC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi

	NOTATION
		z k		keystream of a cipher.
		m k		recovered plaintext (output) of a decipher.
		q k		internal state of a decipher.
		z k		keystream of a decipher.
		g θ		next state transition function.
	Acronyms h θ Notations M	filter function of the internal state. synchronization delay.
		Adv prf (B)		advantage of an adversary B in a PRF-game.
		Adv wprf (B)		advantage of an adversary B in a WPRF-game.
		Pr prf (B = prf)	probability that B answers prf in a pseudo-random world.
	F	LPV Pr rf (B = prf) Linear Parameter Varying finite field. probability that B answers prf in a random world.
	n	Adv(A)	dimension of the system. advantage of an adversary A in a IND-game.
	x	SISO Σ Λ	Single Input Single Output state-space vector of a dynamical system. structured linear discrete-time system.
	x k		state vector at time k
	x i	SSC	Synchronous Stream Cipher
		SSSC	Self-Synchronizing Stream Cipher
		PRF	Pseudo Random Function
	u k		output of the left inverse dynamical system.
	WPRF ρ(k) ρ i (k)	time varying parameter vector. Weak Pseudo Random Function time varying parameter component number i.
		LOR-IND	left-or-right indistinguishability
	Σ ρ	IND-CPA	Indistinguishability against Chosen Plaintext Attack LPV discrete-time system.
	r		relative degree of a system.
	A ρ	IND-CCA	Indistinguishability against Chosen Ciphertext Attack dynamical matrix of Σ ρ .
	B ρ		input matrix of Σ ρ .
	C ρ	DES	Data Encryption Standard output matrix of Σ ρ .
	D ρ		direct transfer matrix of Σ ρ .
	P ρ	AES	Advanced Encryption Standard inverse transition matrix of Σ ρ .
	σ ss θ	CMOS	Complementary Metal Oxide Semiconductor keystream generator of an automaton
	e		encryption function.
	d	FET	Field Effect Transistors decryption function.
	M		message space.
	C	CPA	Correlation Power Analysis ciphertext space.
	m k		plaintext (input) of a cipher.
	c k		ciphertext (output) of a cipher.
	q k		internal state of a cipher.
				xxi xxiii

1

Graphe orienté du système linéaire structuré associé au système LPV

[START_REF] Thierry | Extended generalized Feistel networks using matrix representation[END_REF]

. . . . vi 2 Forme canonique d'un SSSC pour l = 1. . . . . . . . . . . . . . . . . . . . . . . . vii 3 Architecture d'un SSSC basée sur un automate à mémoire finie. . . . . . . . . . . viii 1.1 Structural system subdivision of Σ Λ . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Digraph associated to Example 1.3.1 . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Digraph associated to Example 1.3.2 . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Digraph associated to Example 1.3.3 . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Digraph associated to Example 1.3.4 . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 Digraph of the linear structured system . . . . . . . . . . . . . . . . . . . . . . . 1.7 Digraph of the linear structured system . . . . . . . . . . . . . . . . . . . . . . . 2.1 Canonical form of SSSC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 SSSC in CFB mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Maurer's architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Recursive architecture of SSSC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Digraph of Steps 1-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Digraph of Steps 1-5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Digraph of Steps 1-6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 Minimal example digraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9 Graph construction related to a flat LPV system of relative degree r = 1 . . . . . 2.10 Graph structure related to the matrix P (ρ:k+6) . . . . . . . . . . . . . . . . . . . 2.11 Non-zero delay diffusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.12 Arduino mega 2560 card . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.13 Supervisor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 CMOS technology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Block diagram of the different Steps of a general CPA attack. . . . . . . . . . . . 3.3 Test bench for correlation power analysis . . . . . . . . . . . . . . . . . . . . . . . 3.4 Schematic of the power consumption measurement . . . . . . . . . . . . . . . . . 3.5 I/O and consumption signal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xix LIST OF FIGURES 3.6 5.1 Graph associated to the function f e . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Cycle of vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.1 Electronic CodeBook mode (ECB) . . . . . . . . . . . . . . . . . . . . . . . . . . i A.2 k state vector component number i at time k u k input of a dynamical system.

y k output of a dynamical system.

x state-space vector of the left inverse dynamical system.

x k state vector at time k of the left inverse dynamical system. ρ realization (ρ(k), ρ(k + 1), . . . ) in a finite or infinite time window of ρ(k).

ε k error x k -x k .

1.1 Linear Parameter Varying Systems . . . . . . . . . . . . . . . . . . 6 1.2 Difference Flatness for LPV Systems . . . . . . . . . . . . . . . . 6

	1.2.1 Direct approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	7
	1.2.2 Inverse system approach . . . . . . . . . . . . . . . . . . . . . . . . .	8
	1.2.3 Mortality problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
	1

.3 Graph Approach to Characterize Flat Outputs . . . . . . . . . . 13

  Search procedure for flat outputs . . . . . . . . . . . . . . . . . . . .

	1.3.1 Necessary and sufficient conditions for flatness based on a digraph . 14
	1.3.2 Illustrative examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
	1.3.3 Connection with the algebraic conditions . . . . . . . . . . . . . . . 19
	1.3.4

21 1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1. LPV SYSTEMS AND CHARACTERIZATION OF FLATNESS 1.1 Linear Parameter Varying Systems

	Linear Parameter Varying (LPV) systems are linear models whose state representation depends
	on a parameter vector which may vary in time. Since several years, more and more attention
	has been paid to these systems both in control [2] [83] [70] [99] [69] [40] and in observation
	or filtering [6] [52] [106]

by iterating 1.2 Difference Flatness for LPV Systems

	the output y k for i ≥ 1 and noticing that T i,j ρ(k+1) = T i+1,j+1 ρ(k)

1.2.1 ([34]) If

	the LPV system (1.1) has a finite relative degree r, the follow-
	ing condition that must hold for a positive integer K, for all k ≥ 0 and for all sequences
	{ρ(k), . . . , ρ(k + K -1 + r)} ∈ Θ r+K
	P ρ(k+K-1:k+K-1+r) P ρ(k+K-2:k+K-2+r) • • • P ρ(k:k+r) = 0	(1.8)
	with
	P ρ(k:k+r)

.2 Difference Flatness for LPV Systems

	1only if, for all sequences {ρ(k -K), . . . , ρ(k -1 + r)} ∈ Θ K+r and for all k ≥ 0, (1.8) is
	fulfilled. In this case, the explicit form of F ρ reads
	n) is a multivariate
	polynomial with indeterminates x i k-K and y k-1-i+r . It follows that (1.2) holds for x k if and

If the 1. LPV SYSTEMS AND CHARACTERIZATION OF FLATNESS entries

  respectively the dynamical and the input matrices. By structured system, it is meant a system where the entries of the matrices I A and I B are '0' or '1'. If the entries a ij of I A (resp. b i of I B ) are '0', it means that there are no relation between the state x i k+1 at time k + 1 and the state x j k at time k (resp. the state x i k+1 at time k + 1 and the input u k ). are '1', it means that there exists a relation. Hence I A and I B act as incident matrices.

. . 28 2.2 Generalities on Symmetric Cryptography . . . . . . . . . . . . . . 29 2

	. .	39
	2.4.1 Construction of flat LPV systems . . . . . . . . . . . . . . . . . . . . 39
	2.4.2 Completion of the design . . . . . . . . . . . . . . . . . . . . . . . . 41
	2.4.3 Basic construction of a flat LPV-based SSSC . . . . . . . . . . . . . 41
	2.5

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.1 Block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2.2 Stream ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.3 Architectures of Self-Synchronizing Stream Ciphers . . . . . . . 32 2.3.1 Keystream generators for Self-Synchronizing Stream Ciphers . . . . 34 2.3.2 Strict T-function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.3.3 Particular case of LPV systems . . . . . . . . . . . . . . . . . . . . . 37 2.4 Construction of SSSC Based on Digraph . . . . . . . . . . . .

Examples of construction of LPV-based SSSC without T-functions 44

2.5.1 Example 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.5.2 Example 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

  It is recalled that this function stands for the leakage model. Let us denote by g k the Fourier transform of g k and with the same motivation as in Subsection 3.3.2, let us introduce g k as the Fourier transform of g k defined as

[START_REF] Boukhobza | Graphical characterization of the set of all flat outputs for structured linear discrete-time systems[END_REF]

For brevity, let us denote by g k the function d → g(d + k).

Table 5 .

 5 1: Truthtable of function f e

  5.3.4 and relation (5.14), the following remark holds.

	Remark 5.3.6 A Boolean function f is constant if and only if, for all nonzero vector
	u ∈ F n 2 , f (u) = 0.
	Remark 5.3.7 From Lemma 5.3.2, it can be inferred whether a Boolean function is a constant
	2 |u =0 function or not, given its 2 u∈F n f (u)2 -HW(u) is non null.

n -1 Walsh coefficients at the nonzero vectors.

The following result acts as a counterpart of Lemma 5.3.1 for NNF. They have been published in

[START_REF] Dravie | Matrix representations of vectorial Boolean functions and eigenanalysis[END_REF]

.

Proposition 5.3.3 The Boolean function f is non constant if and only if the quantity

Proposition 5.3.4 Let f be a non constant Boolean (n)-function such that all the NNF coefficients are known except f (0). Then f can be entirely recovered.

Table 5 .

 5 3: Reduced correlation matrices of the partial functions g c associated to the transition function g.

	And applying Algorithm 1 of Simultaneous Triangularization (see Appendix B) on the set
	of matrices C gc , c ∈ F 3 2

un chemin simple est un chemin qui passe une et une seule fois par les sommets qu'il couvre.

un sommet essentiel de l'entrée et de la sortie est un chemin qui appartient à l'intersection de tous les chemins reliant l'entrée à la sortie.

2.6 Test platform and specifications . . . . . . . . . . . . . . . . . . . .

2.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Note that left shifts are allowed since there are multiplication by

Remerciements

Publications

The publications related to this work are listed below:

SPECTRAL APPROACH FOR CORRELATION POWER ANALYSIS

The norm associated to this scalar product is:

Clearly, the multidimensional attack can be combined with the estimation approach described above. Let -→ ϕ t be the two-dimensional power consumption vector at time t. Then -→ ϕ t = (ϕ 1 t , ϕ 2 t ), where ϕ 1 t is the consumption at time t and ϕ 2 t is the consumption at time t + t 2 -t 1 . The reliability coefficient between the power consumption (ϕ 1 t , ϕ 2 t ) and the model (g 1 k , g 2 k ) is required to assess the quality of the estimation. This reliability coefficient for the estimated value k at time t is computed as :

,

where, for i ∈ {1, 2}, ϕ i t and g i k are obtained by discarding the value at the zero vector, as in (3.10).

By using fast Fourier transform algorithm, the multidimensional attack complexity still remains quasi linear in the size of the S-Box.

Experimental Results

The Challenge An ATMega 163 smart card, involving an 8-bit AVR type processor, has been programmed to process a cipher operation that involves f (d i + k i ), where f is the AES S-Box, the k i 's are 8-bit secret key elements previously introduced in the card, the d i 's are 8-bit parameters introduced in the card by the adversary. The operation + denotes the bitwise xor of bytes. The challenge of the adversary is to retrieve the secret values k i by measuring the smart card consumption during calculations. For this purpose, the adversary uses a test bench.

The test bench

The test bench (see Figure 3.3) involves the smart card, a smart card reader and an oscilloscope. The oscilloscope is a picoscope 5444b with a 200 MHz bandwidth and a sample rate of 1GS per second. The pins of the smart card are connected to the oscilloscope via an adapter. The chip consumption is measured through the potential drop at a resistor connected between the Vss of the card and the ground (see Figure 3.4). All these devices are driven by a computer that implements the attack algorithm.

Application of the attack on a simple S-Box

Experimental protocol The attack consists in recovering four secret keys k 1 , k 2 , k 3 and k 4 during a time window when the card processes sequentially f

SPECTRAL APPROACH FOR CORRELATION POWER ANALYSIS

the AES S-Box, but was less effective on the SSSC THE CASCADE owing to intermediate operations in the update function of the encryption.

Chapter 4

Security Proof of the Canonical Form of Self-Synchronizing

Stream Ciphers

The exiting SSSC mentioned in Chapter 2 have an issue related to security: they had been either totally broken (KNOT, ΥΓ, MOSQUITO, HBB, SSS) or partially broken (MOUSTIQUE). Furthermore the attacks were performed by applying Chosen Ciphertext Attacks (CCA). From this, a natural question is raised: can we expect the design of secure SSSC ? and if yes which security level can we expect for this design ?

In this chapter, we tackle the problem of security of SSSC by considering their canonical form. And we introduce a weaker property to characterize and study the indistinguishablity security of SSSC. The results in this chapter are published in [START_REF] Dravie | Security proof of the canonical form of self-synchronizing stream ciphers[END_REF].

Contents

Security Criteria on the Filtering Function

Pseudo Random Functions

A family of functions is said to be Pseudo Random Function (PRF), [START_REF] Goldreich | How to construct random functions[END_REF][START_REF] Bellare | Introduction to modern cryptography[END_REF], if it is computationally indistinguishable from the set of all the functions. This means that for polynomial complexity adversaries, a Pseudo Random Function behaves as if it was a true randomly chosen function.

The Pseudo Random property is assessed by the so-called PRF-game that involves an adversary B, challenged to guess whether a given function is either a true random function, randomly chosen from the set of all the functions, or is an element of the family. The entries of the algorithm B are an integer n together with an oracle that, on request for an n-dimensional vector, returns the value of the function.

The PRF-game.

For the parameter n, let us consider a family of functions 2. The challenger asks the oracle for the values of f (q i ) for inputs q 1 , . . . , x η . The number η of queries the challenger is allowed to perform is bounded by a polynomial in n. The adversary B does not know in which world she plays: pseudo random or random world? Let Pr prf (B = prf) be the probability that B answers prf given that it plays in the pseudo random world and let Pr rf (B = prf) be the probability that B answers prf given that it plays in the random world. In the first case, the answer of B is correct, and in the second case, it is wrong. The advantage of B in the PRF-game is by definition:

A family of Boolean functions is said to be pseudo random if the maximum advantage of any polynomial adversary is negligible. And a function of the real number x is said to be negligible if it decreases faster that the inverse of any polynomial in x as x grows to infinity. Remark 4.3.1 For a family of functions to be PRF, it is necessary that the number of its elements increases faster than any polynomial in the security parameter n. If not, the exhaustive search algorithm has polynomial complexity. In a cryptographic context, the secret key selects

Indistinguishability and Security Games

Conversely, knowing the cryptogram of a given message, it is possible to infer the sequence transmitted by the oracle. The parameter q i consists of the vector whose components are the latter cryptogram symbols and the value is given by:

Remark 4.3.3

As the initial value is randomly chosen by the oracle, the challenger cannot predict which parameters q i will be returned by the oracle.

The advantage of a challenger B in a WPRF game is defined in the same manner as in the PRF game:

Adv wprf (B) = Pr wprf (B = wprf) -Pr rf (B = wprf) . Proof. Given a family of functions F, one has to prove that if a challenger against the weak pseudo random property of F exists, then a challenger against the pseudo random property can be derived.

Pseudo random functions are weak pseudo random functions

Let B a challenger against the weak pseudo random function family. We construct a challenger A against the pseudo random function family, that will act for B as a weak pseudo random oracle. The precise definition of A is:

1. On request of a length k sequence m 1 • • • m k from B, the challenger A chooses a random value q 0 ∈ {0, 1} n , computes q 1 , . . . , q k as q i = (q i-1 < < 1) + m i , asks the oracle for the values f (q i ) and transmits them to B.

2. After a polynomial number q of such queries, the challenger B answers. If B answers rf, then A answers rf, and if B answers wprf, then A answers prf.

We now prove that the challenger A so constructed has the same advantage as the challenger B. This follows from the fact that the challenger A gives the same answer as B.

Indistinguishability and Security Games

The framework used here to assess the security of SSSC is the one defined in [START_REF] Bellare | Introduction to modern cryptography[END_REF] for symmetric encryption schemes. The notions of security games is used within this framework. They are

SECURITY PROOF OF THE CANONICAL FORM OF SELF-SYNCHRONIZING STREAM CIPHERS

1. The challenger A chooses a first couple of messages (m 0 0 , m 0 1 ) that she sends to B, and B sends directly theses messages to the LOR-IND oracle.

2. When A asks B for the cryptograms of a chosen plaintext message m i , the algorithm B sends to the LOR-IND-oracle the couple with twice the same message : (m i , m i ). The cryptogram returned by the oracle thus corresponds to m i whatever the random bit b chosen by the oracle. This cryptogram is returned to A.

3. After a polynomial number of queries, the challenger A returns a guess b for b, and B returns the same value.

The algorithm B so defined simulates for A an IND-CPA-oracle, and the advantage of B equals the advantage of A. Thus, if an adversary against the IND-CPA property exists, then an adversary against the LOR-IND property exists too. By contraposition, if the ciphering scheme is LOR-IND-CPA secure, then it is IND-CPA secure.

Security proof of the canonical SSSC

IND-CCA security of the canonical SSSC

The ideal case for a canonical SSSC is when the filtering function is randomly chosen among all the 2 2 n Boolean functions. This ideal case is not realistic as it would imply an exponential key size. However, even in this situation, the following property holds:

Proposition 4.5.1 ([38]) The canonical SSSC cannot reach the IND-CCA security

Proof. Actually, this is due to the fact that the cryptograms produced by an SSSC are malleable. Indeed, they can be modified at their end without effect on the beginning of the plaintext.

Consider the special situation when the challenger provides m 0 = 0 • • • 0, the message that only involves symbols 0, and m 1 = 1 • • • 1, the message that only involves symbols 1. It receives a cryptogram c. It modifies only the last symbol of the cryptogram and asks the oracle to decrypt. If the answer of the oracle starts with a sequence of 0, then c is the encryption of m 0 and if it starts with a sequence of 1, then c is the encryption of m 1 . Following this strategy, the challenger always wins. That completes the proof.

On the other hand, it is shown in next session that the canonical SSSC can reach the IND-CPA security.

IND-CPA security of the canonical SSSC

The main result of this section is to prove that the WPRF property of the filtering function characterizes the IND-CPA security of the canonical SSSC.

Vectorial Boolean functions representations

Similarity relations between the matrix representations

We prove in this subsection, for m = n, similarity relations that relate the polynomial matrix P , the correlation matrix C = 2 -n W and the adjacency matrix A (with complex coefficients). We also show that, when the coefficients of the adjacency matrix A and of the polynomial matrix P are considered in F 2 , there exists a similarity transform that relates them. This relation allows to simplify the analysis of the eigenstructures of these matrices. This is typically the case for the issue addressed in Section 5.4.

The result below allows to relate the correlation matrix (or the Walsh matrix) of a function to the adjacency matrix of its graph.

Proposition 5.3.6 ([37])

Let f be an (n, n)-function, then its adjacency matrix A and its correlation matrix C are related by:

where the matrix C T is the transpose of C and H is the Hadamard matrix (see (5.5)).

The result below allows to relate the polynomial matrix of a function to the adjacency matrix of its graph.

Proposition 5.3.7 ([37])

Let f be an (n, n)-function, then, its polynomial matrix P and its adjacency matrix A are related by :

(5.23

where M is the monomial matrix defined by (5.16).

Remark 5.3.8 When they are reduced modulo 2, the entries of the matrices M and P can also be considered as elements on F 2 , and then Proposition 5.3.7 still holds.

Considering Propositions 5.3.6 and 5.3.7 and taking into account the fact that a matrix and its transpose are similar, we conclude that A, A T , P and C are similar matrices.

Matrix representation and composition

It has been noted in [START_REF] Daemen | Correlation matrices[END_REF] that the correlation matrix of the composition of two functions is the product of the correlation matrices of these functions. From Propositions 5.3.6 and 5.3.7, it is clear that this property holds for the adjacency matrix and for the polynomial matrix. As a result, the following proposition holds.

Proposition 5.3.8 ([37])

If f is a Boolean (n, m)-function and g is a (p, n)-function then, the matrix representations of the composition f • g, for the adjacency matrix A, correlation to the vectors a 0 , a 1 , a 2 , a 3 , a 4 , a 5 , a 6 . It is shown in the sequel that, from the eigenvectors of the adjacency matrix A, the change of basis of Proposition 5.3.6 and of Proposition 5.3.7 can be used to determine respectively the eigenspaces of the correlation matrix C and the polynomial matrix P .

Eigenvectors of the correlation matrix C

From (5.22), the eigenvectors of C can be deduced from those of A T . If v is an eigenvector for A T , then, due to (5.4), the Fourier transform of v, denoted by v = Hv is an eigenvector of the Walsh matrix W and so of the correlation matrix C. Therefore:

If v is an eigenvector of A T associated to the eigenvalue 0, then from Remark 5.4.5, the support of v is included in the set of preimages of the junctions in the graph G.

Due to Equation (5.18), the eigenvalues of the Walsh matrix W are merely the eigenvalues of the ones of the correlation matrix C times 2 n . Thus, the eigenvectors are the same.

Eigenvectors of the polynomial matrix P

The eigenvectors of the polynomial matrix P can also be deduced from those of the adjacency matrix A by applying (5.23). If v is an eigenvector of A then v = Zv is an eigenvector of P .

Appendix A

Basics on Block Ciphers and Self-Synchronizing Stream Ciphers

A.1 Block ciphers Appendix B

Simultaneous Triangularization

In [START_REF] Dubi | An algorithmic approach to simultaneous triangularization[END_REF], the author gave an algorithm that computes for a set of matrices A, provided that A is simultaneous triangularizable, a matrix basis that triangularizes A. Furthermore, this algorithm aborts if such basis does not exist. A sufficient condition of non-existence of such a basis is that the matrices of A do not have a common eigenvector. Before getting in details of the algorithm itself, we present some important definitions and useful results.

Let E an n-dimensional vector space. Let B, B , two bases of E, f a linear application on E, A (resp. B) the matrix representation of f with respect to the basis B (resp. B ). If P is the change of coordinate matrix from B to B then B = P -1 AP .

B.1 Definition and property

The set A is simultaneous triangularizable if there exists a basis S that triangularizes A, that is

where T j is a triangular matrix. The matrix S is called a T-basis.

A set of matrices A is simultaneous triangularizable if and only if there exists nested subsets

In this case the T-basis S is given by S = (v 1 , . . . , v n ) with v i ∈ V i and where (v i ) are linearly independent. The notation S = (v 1 , . . . , v n ) denotes the change of coordinate matrix from a basis B (for instance the canonical basis) to the basis (v i ). Hence T j is the matrix representation of the multiplication by b j with respect to the basis (v i ).

B. SIMULTANEOUS TRIANGULARIZATION Theorem B.1.1 ([39]

) Let A be a set of matrices that is V -invariant, where V is a kdimensional linear subset spanned by {v 1 , . . . , v k }. Let B be a basis of E containing (v i ) and the matrix S = (v 1 , . . . , v n ). Then for each

And the set A is simultaneously triangularizable if and only if both the set A 1 = {A 11 , . . . , A 1n } and the set A 3 = {A 31 , . . . , A 3n } are simultaneously triangularizable.

Theorem B.1.2 ([39]) If

A is simultaneously triangularizable then, the matrices A j admit a common eigenvector.

B.2 Simultaneous Triangularization Algorithm (STA)

The algorithm takes as input the set of matrices for which we want to check whether they admit a basis S that triangularizes them together. The algorithm achieves the verification in at most n iterations where during iteration k < n, a search for common eigenvector is performed on a set of matrices of dimension n -k (Theorem B.1.2). If a common eigenvector is found, another vector is computed from it and added to a family B of linearly independent vectors. Actually, Theorem B.1.1 is applied by computing A 3 and checking whether it admits a common eigenvector. Here, one should mention that there is no need to check whether A 1 is simultaneous triangularizable since the process of the algorithm allows to have at each iteration the matrix A 1 as triangular matrix. If no common eigenvector is found at iteration k < n then the algorithm aborts. Otherwise the algorithm is processed until iteration n where a T-basis is inferred from B.

The algorithm requires a set of matrices on which the verification is performed and returns, in case it exists, a basis B that triangularizes this set. Otherwise the algorithm aborts. Remark B.2.1 For a given set of matrices, it suffices to find one of the smallest subsets of matrices that are not simultaneously triangularizable in order to guarantee that the set is not simultaneously triangularizable.

Algorithm 1 Simulatneous Triangularization Algorithm