Quantum Reductions for Cryptographic Proofs

Date/Time: Mon.2nd July 2012 / 15:00 - - ()

Speaker: Dr. A. Kawachi (Tokyo Institute of Technology)

In modern cryptography, reductions are a fundamental proof technique for security of cryptographic protocols against computationally bounded adversaries. In the technique of reductions for security, we "reduce" security of a protocol to hardness of some problems which are believed to be computationally hard against any efficient algorithm. From a contrapositive viewpoint, our goal is to construct an efficient (classical or quantum) algorithm, called a reduction, to solve the hard problem by using an adversary breaking the protocol. In several (even classical) cryptographic protocols, it has been demonstrated that the notion of quantum computing is significantly useful for the reduction. In this talk, we survey several recent results in which quantum reductions work essentially.