Dimension Padding as a Structural Countermeasure to Linear Inversion in Dual-Public-Key Code-Based Cryptosystems

Dual-public-key constructions in code-based cryptography expose both generator-based and parity-based public representations. While such designs simplify encryption and decryption, they may admit linear algebraic attacks when the public matrices jointly form a square and invertible system. In this case, the private parity structure can be recovered exactly by matrix inversion, independently of decoding hardness. We identify the structural root cause of this vulnerability and show how correctness requirements in the unpadded construction can force invertibility of the stacked public matrix, enabling full recovery of the private parity matrix. To address this issue, we propose a dimension padding countermeasure that enlarges the public ambient space. Although generalized inverses of the resulting non-square public matrix may exist, padding provably destroys uniqueness: the public equations admit an exponential-size equivalence class of parity matrices consistent with the public key, only one of which corresponds to the structured trapdoor. Consequently, the private parity structure becomes information-theoretically non-identifiable from public data while correctness and decoding behavior are preserved.