### DIMACS Theoretical Computer Science Seminar

Title: Increasing the power of Honest Verifier Quantum Statistical Zero Knowledge proof systems

Speaker: **Iordanis Kerenidis**, CNRS- Univ Paris

Date: Wednesday, March 12, 2008 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

In quantum Zero Knowledge, the assumption was made that the Verifier
is only using unitary operations. Under this restriction, many nice
properties have been shown about quantum Zero Knowledge, including
the
fact that Honest-Verifier Quantum Statistical Zero Knowledge (HVQSZK)
is equal to Cheating-Verifier Quantum Statistical Zero Knowledge
(QSZK).

In this talk we investigate what happens when we raise the
restriction
of unitarity in quantum Zero Knowledge, i.e. we allow the Verifier to
apply any general quantum operation during the protocol. First, in
the
honest verifier case we show a striking result: any classical
Interactive Proof has an Honest-Verifier Quantum Statistical Zero
Knowledge proof. Note that in the classical case, honest verifier SZK
is no more powerful than SZK and hence it is not believed to contain
even NP. Second, if we allow a cheating verifier, then Quantum
Statistical Zero Knowledge with non-unitaries is equal to Quantum
Zero-Knowledge with unitaries.

One can think of our results in two complementary ways.
If we would like to use the honest verifier model as a means to study
the general model by taking advantage of their equivalence, then
it is
imperative to use the unitary definition, since with the general one
this equivalence is most probably not true.
On the other hand, if we would like to use quantum Zero Knowledge
protocols in a cryptographic scenario where the honest-but-curious
model is sufficient, then adding the unitary constraint severely
decreases the power of quantum Zero Knowledge protocols. We remark
that in order for the general definition to be meaningful, we also
have to strengthen our definition of simulation.