Akinori Kawachi

Assistant Professor
Department of Mathematical and Computing Sciences,
Graduate School of Information Science and Engineering,
Tokyo Institute of Technology


2-12-1 Ookayama, Meguro-ku, Tokyo 152-8552, Japan


My current research area is in computational complexity theory and foundations of cryptography from viewpoints of classical and quantum computation. In particular, I am interested in cryptographic primitives secure against quantum adversaries and general theory of computational cryptography.

Besides the current research area, I am also interested in
Quantum Computation:
Quantum Query Complexity, and Quantum Cryptography
Probabilistic and Distributed Computations:
Load Balancing, and Compact Routing Algorithms.

Selected Papers

Publication List (PDF file)
Andrej Bogdanov, Akinori Kawachi, and Hidetoki Tanaka,
"On Hard Functions for Low-Degree Polynomials over Prime Fields,"
ACM Transactions on Computing Theory, to appear.
Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura, and Tomoyuki Yamakami
"Computational Indistinguishability between Quantum States and Its Cryptographic Application,"
Journal of Cryptology 25(3): 528-555, 2012. [quant-ph]
Baris Aydinlioglu, Dan Gutfreund, John Hitchcock, and Akinori Kawachi,
"Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds,"
Computational Complexity 20(2): 329-366, 2011 (invited from CCC'10). [ECCC]
Akinori Kawachi, Christopher Portmann, and Keisuke Tanaka,
"Characterization of the Relations between Information-Theoretic Non-Malleability, Secrecy, and Authenticity,"
Proc. ICITS 2011, p.6-24, 2011. [Cryptology ePrint Archive]
Akinori Kawachi and Tomoyuki Yamakami,
"Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding,"
SIAM Journal on Computing, Volume 39, Issue 7, p.2941-2969, 2010. [quant-ph]
Akinori Kawachi and Osamu Watanabe,
"Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems,"
Akinori Kawachi and Christopher Portmann,
"On the Power of Quantum Encryption Keys,"
Proc. PQCrypto 2008, p.165-180, 2008. [quant-ph]
Akinori Kawachi, Keisuke Tanaka, and Keita Xagawa,
"Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems,"
Proc. Asiacrypt 2008, p.372-389, 2008. [full version (PDF)]
Masahito Hayashi, Akinori Kawachi, and Hirotada Kobayashi,
"Quantum Measurements for Hidden Subgroup Problems with Optimal Sample Complexity,"
Quantum Information and Computation Journal, 8, p.345-358, 2008. [quant-ph]
Akinori Kawachi, Keisuke Tanaka, and Keita Xagawa,
"Multi-Bit Cryptosystems Based on Lattice Problems,"
Proc. PKC 2007, LNCS 4450, p.315-329, 2007. [full version (PDF)]
Akinori Kawachi, Hirotada Kobayashi, Takeshi Koshiba, and Raymond H. Putra,
"Universal Test for Quantum One-Way Permutations,"
Theoretical Computer Science, 345:2-3, p.370-385, 2005. [quant-ph]
Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda, Raymond H. Putra, and Shigeru Yamashita,
"Quantum Identification of Boolean Oracles,"
Proc. STACS 2004, LNCS 2996, p.105-116, 2004. [quant-ph]