Paper 2026/2512

SLEEK: Sparse Quasi-Cyclic Codes with Closed-Form DFR Key Encapsulation

Abstract

Performance in terms of bandwidth and execution time, as well as decoding failures remain important challenges for code-based KEMs. This paper introduces SLEEK: Sparse quasi-cycLic codEs with closEd-form DFR Key encapsulation, a Key Encapsulation Mechanism (KEM) based on Quasi-Cyclic Moderate-Density Parity-Check (QC-MDPC) codes. The scheme employs a parallel bit-flipping decoder with three iterations and a closed-form estimate of the decoding-failure rate (DFR). The latter allows parameter selection with analytically bounded failure probability and supports the use of standard IND-CCA transformations. We designed two variants of SLEEK. The first, SLEEK-LT, targets IND-CCA security for long-term keys, and supports QC-MDPC codes with different rates, allowing a tradeoff between public-key and ciphertext size. The second, SLEEK-E, targets IND-CPA security for ephemeral keys in settings requiring forward secrecy. While SLEEK-LT makes conservative choices and aims at security against active attackers, SLEEK-E relies on a novel QC key structure, for which we establish security equivalent to that of the original QC-MDPC construction under the same assumptions, while reducing key-generation cost. We explore a broad design space and provide parameter sets targeting $128$-, $192$-, and $256$-bit security, together with an $80$-bit configuration for constrained embedded platforms. We also optimize polynomial inversion and parallel bit-flipping decoding, the two dominant components of the implementation. We provide quantitative benchmarks of our optimized AVX2 implementation of SLEEK. For SLEEK-LT, ciphertexts are $4.9\times$ smaller than those of the NIST standard choice, HQC, at the cost of a $47$% increase in the runtime, and is $1.3\times$ to $2.7\times$ faster than BIKE. For SLEEK-E, execution time improves by $1.6\times$ over HQC with a bandwidth usage reduced by $2.1\times$. Compared with Lean-BIKE, SLEEK-E is $5.3\times$ faster and substantially reduces the impact of decoding failures on system reliability.