The role of help in Classical and Quantum Zero-Knowledge

Details The role of help in Classical and Quantum Zero-Knowledge The role of help in Classical and Quantum Zero-Knowledge

2007-11-27

arxiv.org/abs/0711.4251v2

Physics

Quantum Physics

22 pages, 0 figures, This paper will be be superseded by joint work with Dragos Florin Ciocan and Salil Vadhan and will be pre

Scientific paper

We study the role of help in Non-Interactive Zero-Knowledge protocols and its relation to the standard interactive model. In the classical case, we show that help and interaction are equivalent, answering an open question of Ben-Or and Gutfreund. This implies a new complete problem for the class SZK, the Image Intersection Density. For this problem, we also prove a polarization lemma which is stronger than the previously known one. In the quantum setting, we define the notion of quantum help and show in a more direct way that help and interaction are again equivalent. Moreover, we define quantum Non-Interactive Zero-Knowledge with classical help and prove that it is equal to the class of languages that have classical honest-Verifier Zero Knowledge protocols secure against quantum Verifiers. Last, we provide new complete problems for all these quantum classes. Similar results were independently discovered by Dragos Florin Ciocan and Salil Vadhan.

Affiliated with

Also associated with

No associations

Rating

The role of help in Classical and Quantum Zero-Knowledge does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The role of help in Classical and Quantum Zero-Knowledge, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The role of help in Classical and Quantum Zero-Knowledge will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-686554