(2026-02) Proving Knowledge of Syndrome Decoding Problems with Soundness
2026-02-18
This paper introduces a novel set of code-based protocols to demonstrate algebraic relationships in zero knowledge. Specifically, we present a comprehensive collection of secure arguments of knowledge for verifying additive and multiplicative relationships between syndrome-committed secrets, including matrix products, which enable us to construct a generic arithmetic circuit framework. We leverage these primitives to formulate a rich variety of privacy-oriented primitives, such as a post-quantum range proof, lookup argument, and verifiable shuffle protocols. These contributions provide the necessary ingredients to transition advanced confidential designs, such as cryptocurrencies, into the post-quantum code-based setting.