Kissing Number of Codes: A Survey

Abstract

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 code performance. 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-based masking protections are applied, their performance in terms of the 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 code 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.