Dubhe: Succinct Zero-Knowledge Proofs for Standard AES and related Applications

We explore a new approach to construct zero-knowledge proofs by combining ideas from the succinct proof system GKR, the Fully Linear PCP (FLPCP), and MPC-in-the-Head ZKPoK. Our discovery contributes to the state-of-the-art of ZKP in two aspects: (1) Methodology: We demonstrate a way to build transparent ZK proofs from simplified variant of FLPCP and KKW. The resulting proofs are practically efficient (O(|C|)-time prover, O(log(|C|)-time verifier, O(log(|C|))-bandwidth where |C| is the number of polynomial gates), and work readily for circuits defined with polynomial gates over any finite field. (2) Applications: We present efficient (interactive) identification schemes, ring identification schemes, (noninteractive) digital signatures and ring signatures, all based on the standard AES ciphersuite. We also show the first practically efficient verifiable symmetric-key encryption scheme, based on counter-mode AES.