On Kissing Number of Codes


Venue/Location: C101, VIASM

Speaker: Olivier Rioul, Télécom Paris, Institut Polytechnique de Paris, France


The kissing number of a code is the average number of pairs of codewords at minimum distance from each other. It has fundamental applications in determining codes performances. Besides, a recent interest has arisen from the field of side-channel analysis of algorithms handling sensitive information (e.g., cryptographic keys). Namely, when code-base masking protections are applied, their performance in terms of attacker’s signal-to-noise ratio or mutual information is proportional to the kissing number of the masking code. Therefore the kissing number is also a security metric for a given minimum distance in side-channel protected implementation, as it is in codes performance evaluation. It is known exactly for some classical families of codes. To estimate it in general, two types of bounds are given. Linear programming, either numerically or by the polynomial method is the most versatile and the more precise. Spectral graph theory provides bounds on the multiplicity of the subdominant eigenvalue that are easier to state.

Bio:  Olivier Rioul is full Professor at the Department of Communication and Electronics at Télécom Paris, Institut Polytechnique de Paris, France. He graduated from École Polytechnique, Paris, France in 1987 and from École Nationale Supérieure des Télécommunications, Paris, France in 1989. He obtained his PhD degree from École Nationale Supérieure des Télécommunications, Paris, France in 1993. His research interests are in applied mathematics and include various, sometimes unconventional, applications of information theory such as inequalities in statistics, hardware security, and experimental psychology. He has been teaching information theory at various universities for twenty years and has published a textbook which has become a classical French reference in the field.