Making
Classical Zero Knowledge Protocols Secure Against
Quantum Attacks (Part II)
By

Dr. Pranab Sen
Reader,
School of Technology and Computer Science
Tata
Institute of Fundamental Research



Date:
April 28, 2008 (Monday) 
Time:
4:00pm  5:00pm 
Venue:
Rm. 1009 William MW Mong Engineering Building,
CUHK 
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 zeroknowledge protocol also has,
under a reasonable condition, another classical zeroknowledge
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 ParisSud,
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.
