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


Changchang Ding and Yan Huang, Indiana University Bloomington


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 poly- nomial 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, (non-interactive) 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.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {291054,
author = {Changchang Ding and Yan Huang},
title = {Dubhe: Succinct {Zero-Knowledge} Proofs for Standard {AES} and related Applications},
booktitle = {32nd USENIX Security Symposium (USENIX Security 23)},
year = {2023},
isbn = {978-1-939133-37-3},
address = {Anaheim, CA},
pages = {4373--4390},
url = {https://www.usenix.org/conference/usenixsecurity23/presentation/ding-changchang},
publisher = {USENIX Association},
month = aug

Presentation Video