Converting Fixed-Length Binary Strings Into Constant Weight Words: Application on Post-Quantum Cryptography

This paper presents a new algorithm for encoding binary strings of fixed-length into a word of constant Hamming weight and constant length. The primary difference compared to previous publications is that the proposed algorithm can be directly applied to binary strings of fixed-length, without including a variable number of random bits needed to ensure the success of the encoding. The algorithm is useful for many post-quantum encryption schemes, in which a constant weight word is required. Additionally, a constant-time version of the algorithm is proposed, in order to mitigate information leakage vulnerabilities that could be exploited in potential timing attacks. An application based on a post-quantum Classic McEliece cryptosystem, using different security levels, is presented. Experimental results demonstrate the feasibility and correctness of our approach along with its advantages when compared with other solutions proposed in the past.