Speaker
Description
Arithmetic circuits provide a versatile framework for demonstrating generic algebraic statements, expressible as a system of polynomials, in a zero-knowledge manner. While this primitive can be used to prove knowledge of solutions to NP-complete problems (graph 3-coloring, Sudoku, etc), existing implementations generally rely on discrete logarithm problem assumptions. In this talk, we introduce a novel code-based arithmetic circuit framework. Our construction permits a prover to demonstrate that committed Hamming-ball vectors satisfy certain arithmetic relationships, solely by acting on their syndromes. By translating generic circuit satisfiability to this code-based setting, our framework provides a critical stepping stone for the development of a secure code-based cryptocurrency.