Skip to Main content Skip to Navigation
Conference papers

Linear Programming Bounds on the Kissing Number of q-ary Codes

Patrick Solé 1 Yi Liu 2, 3, 4 Wei Cheng 2, 3, 4 Sylvain Guilley 5, 3, 4, 6 Olivier Rioul 4, 3, 2 
Abstract : We use linear programming (LP) to derive upper and lower bounds on the "kissing number" A d of any q-ary code C with distance distribution frequencies Ai, in terms of the given parameters (n, M, d). In particular, a polynomial method gives explicit analytic bounds in a certain range of parameters, which are sharp for some low-rate codes like the first-order Reed-Muller codes. The general LP bounds are more suited to numerical estimates. Besides the classical estimation of the probability of decoding error and of undetected error, we outline recent applications in hardware protection against side-channel attacks using code-based masking countermeasures, where the protection is all the more efficient as the kissing number is low.
Complete list of metadata
Contributor : Olivier Rioul Connect in order to contact the contributor
Submitted on : Wednesday, September 15, 2021 - 9:50:15 AM
Last modification on : Saturday, July 9, 2022 - 7:53:10 AM
Long-term archiving on: : Thursday, December 16, 2021 - 6:16:46 PM


Files produced by the author(s)


  • HAL Id : hal-03323516, version 1


Patrick Solé, Yi Liu, Wei Cheng, Sylvain Guilley, Olivier Rioul. Linear Programming Bounds on the Kissing Number of q-ary Codes. 2021 IEEE Information Theory Workshop (ITW2021), Oct 2021, Kanazawa, Japan. ⟨hal-03323516⟩



Record views


Files downloads