Paper 2025/2151

Hardness of Problems with Hints in Code-Based Cryptography and Applications to Traitor Tracing

Abstract

Code-based cryptography has reached maturity for standard primitives such as encryption and digital signatures. However, when it comes to advanced encryption functionalities, particularly in multi-user settings involving collusions among users holding different secret keys, there is still no foundational framework for code-based schemes. In this work, we address this gap by introducing a multi-receiver encryption scheme with tracing capability based on coding assumptions. This primitive often serves as a foundation for more advanced constructions such as attribute-based or functional encryption. To achieve this goal, we propose a kernel sampling technique that enables the sampling of secret keys under a common public key, thereby realizing multi-receiver encryption. The resulting construction is as efficient as the underlying public-key encryption scheme, namely Alekhnovich's scheme from FOCS'03. We also introduce new hardness assumptions on problems with hints. These assumptions extend classical code-based problems to handle collusion among dishonest users in the multi-user setting. In particular, we define the $\ell$-Decoding Problem ($\ell$-DP), the code-based analogue of the $k$-LWE problem in lattices, and provide a reduction from the standard Decoding Problem (DP) to $\ell$-DP. We further introduce structural variants relying on Moderate Density Parity Check (MDPC) codes that we call $\ell$-MDPC-DP. Based on $\ell$-MDPC-DP, we design the first code-based traitor-tracing encryption scheme. Interestingly, the security of our scheme relies on $\ell$-MDPC-DP and a slight variation called $(\ell,\ell')$-OM-MDPC-DP, the latter of which we prove to be as hard as $\ell$-DP via a polynomial reduction, therefore reducing the security of our scheme to only $\ell$-MDPC-DP. Although no formal reduction from $\ell$-DP to $\ell$-MDPC-DP is given, the definition of $\ell$-MDPC-DP is a natural variant of $\ell$-DP adapted to the multi-user code-based setting. Furthermore, we also provide evidence of $\ell$-MDPC-DP hardness by presenting detailed cryptanalytic arguments.