Secret Sharing through Cellular Automata


A secret sharing scheme is a protocol enabling a dealer to share a secret S with a set of players, in such a way that only some subsets of players can recover S. For instance, in (k,n)-threshold schemes all subsets of at least k players can reconstruct the secret, while k-1 or less players gain no information on the secret by combining their shares. In this talk, we show how cellular automata can be used to define secret sharing schemes. We begin with a first construction based on the computation of preimages in bipermutive cellular automata, remarking that the resulting access structure requires at least k adjacent players to recover the secret. We then present an improved scheme which focuses on orthogonal Latin squares induced by cellular automata, showing that it implements a real (2,n)–threshold scheme without adjacency constraints.

Salle des Actes, Château de Valrose, University of Nice Sophia Antipolis, France