Abstract :

A zero knowledge protocol is an interactive proof whereby a prover can convince the verifier of the truth of a statement with revealing any additional information about the statement. The zero knowledge condition should hold even when the verifier cheats, that is, it deviates from the prescribed protocol. The possibility of making quantum computers begs the question as to what happens about the security of a zero knowledge protocol if the verifier cheats quantumly. Since problems like factoring and discrete logarithm which are at the heart of many classical cryptosystems and protocols become tractable in the presence of quantum computation, it is a priori conceivable that a cheating quantum computer can break the security of a classical zero knowledge protocol.

Nevertheless, in these talks, we shall see that any problem that has a classical zero-knowledge protocol also has, under a reasonable condition, another classical zero-knowledge protocol which is secure against all classical and quantum polynomial time verifiers, even cheating ones. This answers an open question of Watrous, and generalizes classical results on zero knowledge by Goldreich, Sahai and Vadhan, and Vadhan.

This is joint work with Sean Hallgren, Alexandra Kolla and Shengyu Zhang, and will appear at the ICALP 2008 conference.

Biography :

Pranab Sen completed his PhD in Computer Science at the Tata Institute of Fundamental Research, Mumbai, India in 2001, under the supervision of Prof. Jaikumar Radhakrishnan. His thesis was on algebraic methods in computational complexity. The greater part of his thesis was on lower bounds on quantum computational complexity of data structure problems. After his PhD, he did postdoctoral research in quantum computation at Laboratoire de Recherche en Informatique, Universite de Paris-Sud, France in the group of Miklos Santha, and at the Institute of Quantum Computation, University of Waterloo, Canada. After that, he worked as a Research Staff Member in the Quantum Information Technology group at NEC Laboratories, Princeton, USA. He returned to India in August 2006 to join his alma mater, Tata Institute of Fundamental Research, he is a Reader in the School of Technology and Computer Science. His research interests lie in quantum computation and computational complexity.