Efficient Zero Knowledge Proof Protocols and Their Applications to Decision Tree Predictions and Accuracy

演讲人: Jiaheng Zhan UC Berkeley
时间: 2021-09-17 10:30-2021-09-17 11:30
地点:FIT 1-202

We present two efficient zero-knowledge proofs protocols with optimal prover computation, Libra and Virgo. Libra has linear prover time, logarithmic verification time, and proof size. It needs a universal trusted setup. Virgo removes the trusted setup of Libra and remains roughly the same complexity. The prover time is O(C+ n log n) and the proof size is O(D log C + log^2 n) for a D-depth circuit with n inputs and C gates. The verification time is also succinct, O(D log C+ log^2 n), if the circuit is structured. Underlying Virgo is a new transparent zero-knowledge verifiable polynomial delegation scheme with logarithmic proof size and verification time. In addition, we initiate the study of zero-knowledge machine learning and propose protocols for zero-knowledge decision tree predictions and accuracy tests (ZKDT). The protocols allow the owner of a decision tree model to convince others that the model computes a prediction on a data sample, or achieves a certain accuracy on a public dataset, without leaking any information about the model itself.



Jiaheng is a fourth-year Ph.D. student in Computer Science at UC Berkeley, where he is very fortunate to be advised by Prof. Dawn Song. He also works closely with Prof. Yupeng Zhang. And he is a member of RISE Lab, Initiative for Cryptocurrencies & Contracts Lab (IC3) and Berkeley AI Research (BAIR). His research interests lie in computer security and cryptography, especially zero-knowledge proofs and their applications on blockchains and machine learning models. Prior to coming to Berkeley, he received his Bachelor's degree in ACM Honors Class of Shanghai Jiao Tong University, where he worked under the supervision of Prof. Xiaotie Deng. During his undergraduate, he was also a research intern at Cornell, advised by Prof. Elaine Shi. He has published several papers on top conferences including CRYPTO, S&P, CCS, and USENIX Security. He received the Facebook Fellowship in Security and Privacy this year.