Login | Register

Zero-Knowledge Multi-Prover Interactive Proofs


Zero-Knowledge Multi-Prover Interactive Proofs

Yang, Nan (2013) Zero-Knowledge Multi-Prover Interactive Proofs. Masters thesis, Concordia University.

[thumbnail of Nan-Yang_MCompSc_S2013.pdf]
Text (application/pdf)
Nan-Yang_MCompSc_S2013.pdf - Accepted Version


Single-prover interactive proofs can recognize PSPACE; if certain complexity assumptions are made, they can do so in zero-knowledge. Generalizing to multiple non-communicating provers extends this class to NEXP, and at the same time removes the complexity assumption needed for zero-knowledge.

However, it was recently discovered that the non-communication condition might be insufficient to guarantee soundness. The provers can form joint randomness through non-local computation without communicating. This could break protocols that rely on the statistical independence of the provers.

In this work, we analyze multi-prover interactive proofs under the constraint of statistical isolation which prohibits non-local computation. We show that there exists perfect zero-knowledge proofs for NEXP under statistical isolation.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Yang, Nan
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science
Date:April 2013
Thesis Supervisor(s):Crepeau, Claude and Ford, David
ID Code:977228
Deposited By: NAN YANG
Deposited On:19 Jun 2013 16:38
Last Modified:18 Jan 2018 17:44
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top