Ph. D. Project
Title:
Design of New Finite State Dynamical Systems Admitting a Matrix Rep-
resentation: Application to Cryptography
Dates:
2019/10/01 - 2022/09/30
Supervisor(s):
Other supervisor(s):
MINIER Marine (marine.minier@univ-lorraine.fr)
Description:
1. Context
The considerable development of new technologies of communication, within
the timely context of digital revolution and Internet of Things, leads nowadays
to an increasing need for security of the exchanges of information. From smart
objects (embedded or mobile units) to smart cities or smart grids (large scale
systems) to mention a few, the issue of security is ubiquitous. It is expected that 200 billion smart
objects will be in use in 2020, a one-hundred fold increase over 2006. This un-
precedented transformation has also a substantial impact in industrial control
equipements. Digital controllers and communication networks in many con-
trol applications have given birth to networked control systems (NCS). Those
information technology (IT) infrastructures, involving digital controllers, sen-
sors, and actuators at a low-level layer and supervisory systems at a high-level
layer, are named supervisory control and data acquisition (SCADA) systems.
Industrial control systems must face several threats, in particular emanating
from malicious adversaries. Among numerous solutions to tackle the problem
of cyber-security, cryptography plays a major role.
2. Main objective of the work
The main objective of this PhD work is to propose new Finite State Machines
admitting a matrix representation for cryptographic perspectives.
Finite State Machines are particular primitives widely used in symmetric
cryptography, in particular stream ciphers. Those automata take the form of
dynamical systems. Those mathematical objects are commonly used in auto-
matic control as well since they can describe the behavior of physical systems - in
that case they operate on the Field of real numbers - of discrete-events systems.
In the last case, they operate, similarly to cryptography, on Finite Fields. This
connection is at the core of the proposal. For cryptographic purposes, the de-
sign of Finite State Machines must be guided by the challenging trade-off good
properties with respect to security consideration versus ease and efficiency of
implementation. It enters the cost effective design paradigm. It turns out that,
quite recently and independently, Finite State Machines admitting a matrix
representation have been proposed for the sake of cryptography. On one hand,
Finite State Machines admitting new matrix representations, called Rational Linear Finite
State Machines and Feedback with Carry Shift Registers, have
been proposed in [1,2]. It is a generalization of Linear Feedback Shifts Registers
by extending the set of possible coefficients for the transition matrix to ratio-
nal fractions. This new approach is an interesting tool for constructing more
complex circuits from smaller LFSMs with nice properties. On the other hand,
since the early 90 s and the pioneering work of [3], several architectures based on
dynamical systems have been proposed. But till now, all of these SSSC schemes
have been broken (see [4, 5] as examples). Pursuing this goal, Linear Parameter
Varying (LPV) systems, a usual class of dynamical systems encountered in con-
trol, have been proposed in [6] to design new self-synchronizing architectures.
LPV dynamical systems are described by state transitions matrices where some
of the entries are replaced by time varying parameters. They are appealing for
their inherent nonlinearties while the matrix representation allows to tackle in
an efficient way synchronization issues.
As matrix representation is a common feature of RLFSM, FCSR and LPV sys-
tems, it makes sense and it sounds interesting to propose new Finite State
Machines within the unified framework of dynamical systems admitting a ma-
trix representation.
3. Expected work
Two symmetric ciphering mechanisms will be considered: synchronous and self-
synchronous. Regardless of the context, one of the main challenge will be to
obtain high nonlinear dynamics, that are dynamics generating sequences with
good statistical properties and yielding good resistance to attacks. The ways
how nonlinearties will be incorporated, while preserving the overall matrix rep-
resentation will be studied. For non autonomous Finite State Machines involved
in self-synchronous ciphers, the efficiency of the synchronization issue between
the cipher and the decipher will deserve a special attention. Taking benefit from
the framework of LPV systems, control theoretical concepts such as structural
analysis, stability, will be a complementary tool for tackling the problems.
At least one, preferably several ones of the following skills are expected:
Control Theory, Mathematics, Cryptography
References
[1] F. Arnault, T. Berger, C. Lauradoux, M. Minier, and B. Pousse. A new
approach for FCSRs. In Selected Areas in Cryptography (SAC'2010) , pages
433-448, 2010.
[2] François Arnault, Thierry P. Berger, Marine Minier, and Benjamin Pousse.
Revisiting lfsrs for cryptographic applications. IEEE Transactions on Infor-
mation Theory , 57(12):8095-8113, 2011.
[3] U. M. Maurer. New approaches to the design of self-synchronizing stream
cipher. Advance in Cryptography, In Proc. Eurocrypt '91, Lecture Notes in
Computer Science , pages 548-471, 1991.
[4] A. Joux and F. Muller. Chosen-ciphertext attack against mosquito.
Lecture Note in Computer Science, 2006.
[5] Emilia Käsper, Vincent Rijmen, Tor E. Bjørstad, Christian Rechberger,
Matthew J. B. Robshaw, and Gautham Sekar. Correlated keystreams in
moustique. In Progress in Cryptology - AFRICACRYPT 2008, First In-
ternational Conference on Cryptology in Africa, Casablanca, Morocco, June
11-14, 2008. Proceedings, pages 246-257, 2008.
[6] B. Dravie, P. Guillot, and G. Millérioux. Flatness and structural analysis as
a constructive framework for private communication. Nonlinear Analysis:
Hybrid Systems , 30:92-105, 2018.
The considerable development of new technologies of communication, within
the timely context of digital revolution and Internet of Things, leads nowadays
to an increasing need for security of the exchanges of information. From smart
objects (embedded or mobile units) to smart cities or smart grids (large scale
systems) to mention a few, the issue of security is ubiquitous. It is expected that 200 billion smart
objects will be in use in 2020, a one-hundred fold increase over 2006. This un-
precedented transformation has also a substantial impact in industrial control
equipements. Digital controllers and communication networks in many con-
trol applications have given birth to networked control systems (NCS). Those
information technology (IT) infrastructures, involving digital controllers, sen-
sors, and actuators at a low-level layer and supervisory systems at a high-level
layer, are named supervisory control and data acquisition (SCADA) systems.
Industrial control systems must face several threats, in particular emanating
from malicious adversaries. Among numerous solutions to tackle the problem
of cyber-security, cryptography plays a major role.
2. Main objective of the work
The main objective of this PhD work is to propose new Finite State Machines
admitting a matrix representation for cryptographic perspectives.
Finite State Machines are particular primitives widely used in symmetric
cryptography, in particular stream ciphers. Those automata take the form of
dynamical systems. Those mathematical objects are commonly used in auto-
matic control as well since they can describe the behavior of physical systems - in
that case they operate on the Field of real numbers - of discrete-events systems.
In the last case, they operate, similarly to cryptography, on Finite Fields. This
connection is at the core of the proposal. For cryptographic purposes, the de-
sign of Finite State Machines must be guided by the challenging trade-off good
properties with respect to security consideration versus ease and efficiency of
implementation. It enters the cost effective design paradigm. It turns out that,
quite recently and independently, Finite State Machines admitting a matrix
representation have been proposed for the sake of cryptography. On one hand,
Finite State Machines admitting new matrix representations, called Rational Linear Finite
State Machines and Feedback with Carry Shift Registers, have
been proposed in [1,2]. It is a generalization of Linear Feedback Shifts Registers
by extending the set of possible coefficients for the transition matrix to ratio-
nal fractions. This new approach is an interesting tool for constructing more
complex circuits from smaller LFSMs with nice properties. On the other hand,
since the early 90 s and the pioneering work of [3], several architectures based on
dynamical systems have been proposed. But till now, all of these SSSC schemes
have been broken (see [4, 5] as examples). Pursuing this goal, Linear Parameter
Varying (LPV) systems, a usual class of dynamical systems encountered in con-
trol, have been proposed in [6] to design new self-synchronizing architectures.
LPV dynamical systems are described by state transitions matrices where some
of the entries are replaced by time varying parameters. They are appealing for
their inherent nonlinearties while the matrix representation allows to tackle in
an efficient way synchronization issues.
As matrix representation is a common feature of RLFSM, FCSR and LPV sys-
tems, it makes sense and it sounds interesting to propose new Finite State
Machines within the unified framework of dynamical systems admitting a ma-
trix representation.
3. Expected work
Two symmetric ciphering mechanisms will be considered: synchronous and self-
synchronous. Regardless of the context, one of the main challenge will be to
obtain high nonlinear dynamics, that are dynamics generating sequences with
good statistical properties and yielding good resistance to attacks. The ways
how nonlinearties will be incorporated, while preserving the overall matrix rep-
resentation will be studied. For non autonomous Finite State Machines involved
in self-synchronous ciphers, the efficiency of the synchronization issue between
the cipher and the decipher will deserve a special attention. Taking benefit from
the framework of LPV systems, control theoretical concepts such as structural
analysis, stability, will be a complementary tool for tackling the problems.
At least one, preferably several ones of the following skills are expected:
Control Theory, Mathematics, Cryptography
References
[1] F. Arnault, T. Berger, C. Lauradoux, M. Minier, and B. Pousse. A new
approach for FCSRs. In Selected Areas in Cryptography (SAC'2010) , pages
433-448, 2010.
[2] François Arnault, Thierry P. Berger, Marine Minier, and Benjamin Pousse.
Revisiting lfsrs for cryptographic applications. IEEE Transactions on Infor-
mation Theory , 57(12):8095-8113, 2011.
[3] U. M. Maurer. New approaches to the design of self-synchronizing stream
cipher. Advance in Cryptography, In Proc. Eurocrypt '91, Lecture Notes in
Computer Science , pages 548-471, 1991.
[4] A. Joux and F. Muller. Chosen-ciphertext attack against mosquito.
Lecture Note in Computer Science, 2006.
[5] Emilia Käsper, Vincent Rijmen, Tor E. Bjørstad, Christian Rechberger,
Matthew J. B. Robshaw, and Gautham Sekar. Correlated keystreams in
moustique. In Progress in Cryptology - AFRICACRYPT 2008, First In-
ternational Conference on Cryptology in Africa, Casablanca, Morocco, June
11-14, 2008. Proceedings, pages 246-257, 2008.
[6] B. Dravie, P. Guillot, and G. Millérioux. Flatness and structural analysis as
a constructive framework for private communication. Nonlinear Analysis:
Hybrid Systems , 30:92-105, 2018.
Keywords:
LPV systems, Finite State Machines, Symmetric ciphers, Synchronization
Department(s):
| Control Identification Diagnosis |
