Compiling Any MIP* into a (Succinct) Classical Interactive Argument

We present a generic compiler that converts any MIP* protocol into a succinct interactive argument where the communication and the verifier are classical, and where post-quantum soundness relies on the post-quantum sub-exponential hardness of the Learning with Errors (LWE) problem. Prior to this work, such a compiler for MIP* was given by Kalai, Lombardi, Vaikuntanathan and Yang (STOC 2022), but the post-quantum soundness of this compiler is still under investigation.

More generally, our compiler can be applied to any QIP protocol which is sound only against semi-malicious provers which follow the prescribed protocol, but with possibly malicious initial state. Our compiler consists of two steps. We first show that if a language L has a QIP with semi-malicious soundness, where the prover runs in time T, then L is in QMATIME(T). We then construct a succinct classical argument for any such language, where the communication complexity grows only poly-logarithmically with T, under the post-quantum sub-exponential hardness of LWE.

The result is joint work with Yael Kalai.