CWI Cryptology Group

Abstract: For a linear function f, an integer vector x with small coefficients, and an image y=f(x), we would like to be able to prove knowledge of a small preimage of y. This is a common scenario in lattice-based cryptography and there is currently no satisfactory solution, all known protocols have an overhead linear in the security parameter or prove knowledge of a weaker witness. A succession of works [CD09,DPSZ12,BDLN16,CDXY17,PL17] have tackled this issue in the context of amortized proofs of knowledge, in which one wants to prove knowledge for multiple images at once, resulting in proofs with constant overhead and linear slack, at the cost of needing to be amortized over a few thousand equations. In this talk we will present a new amortized proof of knowledge which we believe is conceptually much simpler than previous works as well as more efficient. We achieve better overhead (with a full proof size that grows linearly in the security parameter rather than the number of equations) and linear slack, while only requiring around 100 equations for amortization.