Speaker: Shengyu Zhang California Institute of Technology
Time: 2007-03-27 14:00-2007-03-27 15:30
Venue: FIT Building, Tsinghua University

Abstract:

 

    One of the main impacts of quantum computation thus far has been its potential implications for cryptography. Understanding which cryptosystems are secure against quantum computers is one of the fundamental questions in the field. A central concept in cryptography is that of a zero-knowledge protocol. Recently Watrous [STOC'06] showed that two specific well-known classical interactive protocols continue to be zero-knowledge against quantum verifiers with quantum auxiliary input. We greatly extends this result by showing that any problem $L$ in Statistical Zero-Knowledge (SZK) has a fully classical protocol that is SZK against both classical and quantum (possibly cheating) verifiers. This answers an open question in [Watrous, STOC'06], and generalizes a classical result by Goldreich, Sahai and Vadhan who showed that HVSZK = SZK. As their result, ours does not depend on any computational assumption. 
     My talk will assume "zero knowledge" on quantum computing; the problem will soon reduce to a purely classical task. 
     Joint work with Sean Hallgren, Alexandra Kolla and Pranab Sen.

 

Short Bio:

 

Shengyu Zhang received the B.S. in mathematics at Fudan University in 1999, a M.S. in Computer Science at Tsinghua University in 2002, and the Ph.D. in Computer Science at Princeton University in 2006. He is currently a postdoc at California Institute of Technology. His main research interests include quantum computing and classical algorithms for various applied areas.