Yuval Ishai: Dot-Product Proofs

Abstract: A dot-product proof is a simple probabilistic proof system in which the verifier decides whether to accept an input vector based on a single linear combination of the entries of the input and a proof vector. I will present constructions of linear-size dot-product proofs for circuit satisfiability and discuss two kinds of applications: exponential-time hardness of approximation of MAX-LIN from ETH, and minimizing verification complexity of succinct arguments.

Joint work with Nir Bitansky, Prahladh Harsha, Ron Rothblum, and David Wu (https://eprint.iacr.org/2024/1138)

Part of CMU Workshop on Cryptography 2024 (https://sites.google.com/andrew.cmu.e...)