Paper 2026/1901

Nothing Up My Matrix: Kleptographic Backdoors in ZK-friendly Hash Functions

Abstract

ZK-friendly hash functions are often built from algebraic SPN permutations. The matrix provides diffusion by mixing the state elements after the S-box layer. However, there is no uniform convention for selecting matrices for the linear layer across primitives. Matrix selection may follow a transparent nothing-up-my-sleeve procedure or prioritize implementation efficiency. Some specifications instead treat any MDS matrix as admissible. This parameter-selection freedom also persists in practice, as some deployed implementations replace the concrete matrix proposed in the original specification with an alternative instantiation. We show that adversarial use of this freedom can create a kleptographic attack surface. In this paper, we study kleptographic backdoors embedded in the matrices of ZK-friendly hash functions. Assuming that a malicious designer controls matrix selection, the designer can choose a matrix that maps a chosen input to a chosen output under appropriate round and parameter conditions. The resulting matrix is MDS and passes the additional matrix security checks required by the target primitive. Three case studies show that such a backdoor could have critical security consequences in real-world deployments. In Plonky3, it would allow a prover to control a Fiat--Shamir challenge and make the verifier accept an invalid claim. In Neptune Cash, it would permit creating a digest collision between the program that checks whether a transaction is valid and one that omits this check, enabling counterfeit currency. Finally, in Plonky2, it would enable a forged Merkle-tree membership proof for an attacker-chosen element. Our results show that satisfying the MDS condition and other security requirements is insufficient to establish that a matrix is trustworthy. Its generation process must also be transparent and verifiable.