Amortization with Fewer Equations for Proving Knowledge of Small Secrets

Abstract

For a linear function f, a vector \(\mathbf{x}\) with small coefficients, and a vector \(y=f(\mathbf{x})\), we would like to be able to give a zero-knowledge proof for the knowledge of an \(\mathbf{x}'\) with small coefficients that satisfies \(f(\mathbf{x}')=y\). This is a common scenario in lattice-based cryptography, and there is currently no satisfactory solution for this problem. All known protocols are built via the repetition of a basic protocol that only has constant (1/2 or 2/3) soundness error. This implies that the communication complexity of the final protocol will be at least a factor of k larger than that of the basic one, where k is the security parameter.