Skip to Main content
Number of documents

27

Bruno Martin


Je travaille principalement sur les automates cellulaires (AC) introduits dans les années 1950 par von Neumann et Ulam. Il s’agit d’un ensemble d’automates finis (les cellules) qui communiquent entre eux selon une topologie régulière (ligne, grille essentiellement). L’évolution se fait en parallèle en appliquant de manière synchrone une règle locale. Cette règle prend en compte les plus proches voisins de chaque cellule.

Complexité des modèles du parallélisme

Je me suis intéressé à la calculabilité des AC en construisant un AC universel qui simule le fonctionnement de n’importe quel AC pourvu que sa fonction de transition soit totalistique. Ce résultat permet de considérer les AC comme un modèle de calcul parallèle.

Ensuite, j’ai considéré la simulation des AC par différents modèles du calcul parallèle. D’abord par différents types de PRAM (CREW-PRAM et XPRAM), puis par différents types de machines spatiales (modèle introduit par Y. Feldman et E. Shapiro).

Automates cellulaires sur des graphes de Cayley

Je considère des AC sur des graphes de Cayley finis en prolongeant des résultats de Zs. Róka. J’ai construit deux simulations d’un tore d’automates par un anneau d’automates. L’une d’entre elles permet de restreindre au minimum possible le nombre de copies des voisins. De plus, pour des valeurs particulières de largeur et de longueur du tore, nous montrons également que notre simulation fonctionne en temps optimal. En combinant ces résultats avec ceux obtenus par Zs. Róka, on peut aussi simuler un réseau hexagonal d’automates par un anneau d’automates.

Génération de suites pseudo-aléatoires

Je m’intéresse aux interactions entre la cryptologie et les AC. J’ai montré qu’il n’existe pas de règle non-linéaire d’AC élémentaire qui soit résliente. Ce résultat limite fortement l’usage d’AC élémentaires pour la construction de suites pseudo-aléatoires utilisables en cryptographie. J’étudie actuellement d’autres pistes pour construires des générateurs pseudo-aléatoires.

Enfin, Je m’intéresse à l’utilisation de la cryptographie pour sécuriser les réseaux. J’ai conçu puis encadré un projet étudiant pour réaliser un protocole d’horodatage authentique. J’ai montré dans un article de vulgarisation comment utiliser des outils provenant du monde des logiciels libres pour construire à la volée de faux certificats pour réaliser une attaque du passeur de seau contre le protocole sécurisé SSL.


Journal articles5 documents

  • Bruno Martin. On Goles’ universal machines: A computational point of view. Theoretical Computer Science, Elsevier, 2013, Discrete Mathematical Structures: From Dynamics to Complexity, 504, pp.83-88. ⟨10.1016/j.tcs.2013.04.024⟩. ⟨hal-01217199⟩
  • Eric Goles, Bruno Martin, Enrico Formenti. Computational Complexity of Avalanches in the Kadanoff Sandpile Model. Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2012, 115 (1), pp.107-124. ⟨10.3233/FI-2012-643⟩. ⟨hal-01217125⟩
  • Bruno Martin. A walsh exploration of elementary CA rules. Journal of Cellular Automata, Old City Publishing, 2008, 3 (2), pp.145-156. ⟨hal-00300231⟩
  • Bruno Martin, Claudine Peyrat. A single-copy minimal-time simulation of a torus of automata by a ring of automata. Discrete Applied Mathematics, Elsevier, 2007, pp.2130-2139. ⟨10.1014/j.dam.2007.05.019⟩. ⟨hal-00296744⟩
  • Bruno Martin. Universal Simulations by Spatial Machines. Journal of Cellular Automata, Old City Publishing, 2007, 2 (3), pp.203-217. ⟨hal-00298560⟩

Conference papers17 documents

  • Piotr Krasnowski, Jerome Lebrun, Bruno Martin. Introducing a Verified Authenticated Key Exchange Protocol over Voice Channels for Secure Voice Communication. 6th International Conference on Information Systems Security and Privacy, Feb 2020, Valletta, France. pp.683-690, ⟨10.5220/0009156506830690⟩. ⟨hal-02863193⟩
  • Bruno Martin. Randomness with Cellular Automata. Discrete Models of Complex Systems, Mar 2018, Orléans, France. ⟨hal-01741411⟩
  • Bruno Martin. Pseudo-random sequence generation with cellular automata. 6th International Workshop on Applications and Fundamentals of Cellular Automata, Nov 2018, Hida, Takayama, Japan. ⟨hal-01980216⟩
  • Simon Martiel, Bruno Martin. An Intrinsically Universal Family of Causal Graph Dynamics. Machines, Computations, and Universality, Sep 2015, Famagusta, Cyprus. pp.129-148, ⟨10.1007/978-3-319-23111-2_9⟩. ⟨hal-01218448⟩
  • Bruno Martin, Simon Martiel. Intrinsic Universality of Causal Graph Dynamics. Machines, Computations and Universality, Sep 2013, Zürich, Switzerland. pp.137-149, ⟨10.4204/EPTCS.128.19⟩. ⟨hal-01218359⟩
  • Sheikh Ziauddin, Bruno Martin. Formal Analysis of ISO/IEC 9798-2 Authentication Standard using AVISPA. Asia Joint Conference on Information Security, Jul 2013, Séoul, South Korea. pp.108-114, ⟨10.1109/ASIAJCIS.2013.25⟩. ⟨hal-01218351⟩
  • Bruno Martin, R. Saito, Katsunobu Imai. On radius 1 nontrivial reversible and number-conserving cellular automata. Reversible Computation, Jul 2012, Copenhagen, Denmark. ⟨hal-00826548⟩
  • Thao Nguyen, Luigi Liquori, Bruno Martin, Karl Hanks. Towards a Trust and Reputation Framework for Social Web Platforms. Confederated International Workshops: OTM Academy, Industry Case Studies Program, EI2N, INBAST, META4eS, OnToContent, ORM, SeDeS, SINCOM, and SOMOCO 2012, Rome, Italy, September 10-14, 2012. Proceedings, Sep 2012, Rome, Italy. pp.13-22, ⟨10.1007/978-3-642-33618-8_3⟩. ⟨hal-00908805⟩
  • Eric Goles, Bruno Martin. Computational Complexity of Avalanches in the Kadanoff Two-dimensional Sandpile Model. Journées Automates Cellulaires 2010, Dec 2010, Turku, Finland. pp.121-132. ⟨hal-00542340⟩
  • Bruno Martin, Christophe Papazian. Neighborhood transformations on graph automata. JAC 2008, Apr 2008, Uzès, France. pp.90-101. ⟨hal-00273947⟩
  • Katsunobu Imai, Bruno Martin. Simulations between triangular and hexagonal number-conserving cellular automata. International Workshop on Natural Computing, Sep 2008, Yokohama, Japan. ⟨hal-00315932⟩
  • Patrick Lacharme, Bruno Martin, Patrick Solé. Pseudo-random sequences, boolean functions and cellular automata. Boolean Functions: Cryptography & Applications, May 2008, Copenhague, Denmark. pp.80-95. ⟨hal-00305493⟩
  • Bruno Martin, Patrick Solé. Pseudo-random Sequences Generated by Cellular Automata. International Conference on Relations, Orders and Graphs: Interactions with Computer Science, May 2008, Mahdia, Tunisia. pp.401-410. ⟨hal-00305407⟩
  • Bruno Martin. Analyse des suites aléatoires engendrées par des automates cellulaires et applications à la cryptographie. Journée de cryptanalyse et de sécurité de l'information, Mar 2007, Casablanca, Maroc. ⟨hal-00296811⟩
  • Bruno Martin. Mixing Compression and CA Encryption. SAR-SSI, Jun 2007, Annecy, France. pp.255-266. ⟨hal-00304320⟩
  • Bruno Martin. Another Co*cryption Method. International Conference on Science and Technology (JICT), Mar 2007, Malaga, Spain. pp.CD-ROM. ⟨hal-00301817⟩
  • Bruno Martin. A Walsh exploration of elementary CA rules. International Workshop on Cellular Automata, Sep 2006, Hiroshima, Japan. pp.25-30. ⟨hal-00305489⟩

Poster communications2 documents

  • Piotr Krasnowski, Bruno Martin, Jerome Lebrun. Enciphered data/voice over real-time voice channels. European School of Information Theory (ESIT 2019), Apr 2019, Sophia-Antipolis, France. ⟨hal-02337668⟩
  • Piotr Krasnowski, Bruno Martin, Jerome Lebrun. Joint source-cryptographic-channel coding real-time secured voice communications on voice channels. Summer School on real-world crypto and privacy, Jun 2019, Sibenik, Croatia. ⟨hal-02337657⟩

Book sections2 documents

  • Bruno Martin, Katsunobu Imai, Ryohei Saito. On Radius 1 Nontrivial Reversible and Number-Conserving Cellular Automata. Reversibility and Universality, 2018. ⟨hal-01741396⟩
  • Enrico Formenti, Katsunobu Imai, Bruno Martin, Jean-Baptiste Yunès. Advances on Random Sequence Generation by Uniform Cellular Automata. Computing with New Resources, 8808, Springer Verlag, pp.56-70, 2014, Lecture Notes in Computer Science, 978-3-319-13349-2. ⟨10.1007/978-3-319-13350-8_5⟩. ⟨hal-01218459⟩

Habilitation à diriger des recherches1 document

  • Bruno Martin. Simulations d'automates cellulaires. Mathématiques [math]. Université Nice Sophia Antipolis, 2005. ⟨tel-00212057⟩