Phecda: Post-Quantum Transparent zkSNARKs from Improved Polynomial Commitment and VOLE-in-the-Head with Application in Publicly Verifiable AES

We propose Phecda, a new framework to produce quantum-resistant transparent zkSNARKs in the Random Oracle Model. Phecda features a novel multi-linear polynomial commitment scheme and a novel VOLE-in-the-Head zero-knowledge argument, offering a versatile solution for verifying many real-world computations. In particular, we invent a novel AES verification circuit, which, combined with Phecda, allows to verify 1024 blocks of AES in the counter-mode in 10ms using a single-thread program running on a Linux PC.