Imai Laboratory Introduction Quantum Computation and Information Introduction Current Our Research Fields Our Motivation Quantum Computation By utilizing Quantum Power, We want to design efficient algorithms and secure protocols which have not been accomplished in today’s computational and cryptographic model. Quantum Cryptography Quantum Walk Algorithms Quantum Key Distribution Algorithms for Hidden Subgroup Problem (HSP) Quantum Digital Signature Quantum Cryptography Quantum Computation Achievements Shor’s Integer factorization algorithm BB84 Protocol classical algorithm BB84 protocol Is unconditional secure key distribution protocol!! (Even though the adversary having unlimited computational resources) The best known algorithm takes sub exponential time. Sub exponential gap!! quantum algorithm Shor’s algorithm can solve it in polynomial time. secure Alice Adversary Bob Future Works Designing new cryptographic application Designing Algorithms for Non-Abelian HSP Shortest Vector There are no polynomial time quantum algorithms for Graph Isomorphism and Shortest Vector Problems in which are included Non-Abelian HSP. HSP Graph Isomorphism Non-Abelian HSP We want to design new cryptographic Applications by using quantum one-way functions which are related to Graph Isomorphism and Shortest Vector problems. References [1] P. W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings, 35th Annual Symposium on Foundation of Computer Science, IEEE Press, Los Alamitos, CA, 1994. [2] C. H. Bennett and G. Brassard. Quantum cryptography: Public key distribution and coin tossing. In proceedings of IEEE International Conference on Computers, Systems and Signal Processing, pages 175-179, IEEE, New York, 1984. Bangalore, India, December 1984. [3] C. Moore, A. Russel, and U. Vazirani. A classical one-way function to confound quantum adversaries. Preprint, quant-ph/07115v2,2007.