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 (eprint.iacr.or...)
Part of CMU Workshop on Cryptography 2024 (sites.google.c...)
18 сен 2024
