Toward finding best linear codes for side-channel protections (extended version)

Side-channel attacks aim at extracting secret keys from cryptographic devices. Randomly masking the implementation is a provable way to protect the secrets against this threat. Recently, various masking schemes have converged to the “code-based masking” philosophy. In code-based masking, different codes allow for different levels of side-channel security. In practice, for a given leakage function, it is important to select the code which enables the best resistance, i.e., which forces the attacker to capture and analyze the largest number of side-channel traces. This paper is a first attempt to address the constructive selection of the optimal codes in the context of side-channel countermeasures, in particular for code-based masking when the device leaks information in the Hamming weight leakage model. We show that the problem is related to the weight enumeration of the extended dual of the masking code. We first present mathematical tools to study those weight enumeration polynomials, and then provide an efficient method to search for good codes, based on a lexicographic sorting of the weight enumeration polynomial from the lowest to highest degrees.