Publications
Books
Masahito Hayashi, Satoshi Ishizuka, Akinori Kawachi, Gen Kimura, and Tomohisa Ogawa, "Introduction to Quantum Information Science," Springer, 2014.
Journal Papers
Akinori Kawachi, Kenichi Kawano, Francois Le Gall, and Suguru Tamaki, "Query Complexity of Unitary Operator Discrimination," IEICE transactions on Information and Systems, Vol.E102-D, No.3, pp.483-491, March 2019.
Akinori Kawachi, Mitsunori Ogihara, and Kei Uchizawa, "Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems on Directed Graphs," Theoretical Computer Science, 762(1): 25-40, March 2019.
Akinori Kawachi, "Circuit Lower Bounds from Learning-theoretic Approaches," Theoretical Computer Science, 733: 83-98, April 2018.
Akinori Kawachi, Yoshio Okamoto, Keisuke Tanaka, and Kenji Yasunaga, "General Constructions of Rational Secret Sharing with Expected Constant-Round Reconstruction," The Computer Journal 60 (5): 711-728, April 2017.
Akinori Kawachi, Benjamin Rossman, and Osamu Watanabe, "The Query Complexity of Witness Finding," Theory of Computing Systems, 61(2): 305-321, August 2017.
Eiichiro Fujisaki, Akinori Kawachi, Ryo Nishimaki, Keisuke Tanaka, and Kenji Yasunaga, "Post-Challenge Leakage Resilient Public-Key Cryptosystem in Split State Model," IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences Vol.E98-A, No.3, pp.853-862, March 2015.
Akinori Kawachi and Ikko Yamane, "A Fourier-Analytic Approach to List-Decoding for Sparse Random Linear Codes," IEICE Transactions on Information and Systems Vol.E98-D, No.3, pp.532-540, March 2015.
Akinori Kawachi, "Proving Circuit Lower Bounds in High Uniform Classes," Interdisciplinary Information Sciences 20(1): 1--26, March 2014.
Andrej Bogdanov, Akinori Kawachi, and Hidetoki Tanaka, "Hard Functions for Low-Degree Polynomials over Prime Fields," ACM Transactions on Computation Theory 5(2): 5, July 2013.
Akinori Kawachi, Hidetoki Tanaka, and Osamu Watanabe, "Estimating the Gowers Norm of Modulo Functions over Prime Fields," IEICE transactions on Information and Systems 95-D(3): 755--762, March 2012.
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, July 2012.
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, June 2011. Special issue dedicated to selected CCC'10 papers.
Akinori Kawachi and Tomoyuki Yamakami, "Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding," SIAM Journal on Computing, Volume 39, Issue 7, pp.2941--2969, May 2010.
Masahito Hayashi, Akinori Kawachi, and Hirotada Kobayashi, "Quantum Measurements for Hidden Subgroup Problems with Optimal Sample Complexity," Quantum Information and Computation Journal, Vol 8, No 3&4, pp.345--358, March 2008.
Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Rudy Raymond, and Shigeru Yamashita, "Improved Algorithms for Quantum Identification of Boolean Oracles," Theoretical Computer Science, Vol.378, Issue 1, pp.41--53, June 2007.
Akinori Kawachi, "Approaches to Lattice Problems in Quantum Computing" (in Japanese), IEICE Journal A, Volume J90-A No.5, pp.376--384, May 2007.
Akinori Kawachi and Koshiba Takeshi, "Progress in Quantum Computational Cryptography," Journal of Universal Computer Science, Vol.12, Issue 6, pp.691--709, June 2006.
Akinori Kawachi, Hirotada Kobayashi, Takeshi Koshiba, and Raymond H. Putra, "Universal Test for Quantum One-Way Permutations," Theoretical Computer Science, Vol.345 Issues 2-3 No.22, pp.370--385, November 2005.
Kazuo Iwama, Akinori Kawachi, and Shigeru Yamashita, "Quantum Biased Oracles," IPSJ Journal, Vol.46 No.10, 2400--2408, October 2005.
Kazuo Iwama, Akinori Kawachi, and Shigeru Yamashita, "Quantum Sampling for Balanced Allocations," IEICE transactions on Information and Systems, Vol.E88-D No.1, pp.47--52, January 2005.
Kazuo Iwama and Akinori Kawachi, "Compact Routing with Stretch Factor of Less Than Three," IEICE transactions on Information and Systems, Vol.E88-D No.1, pp.39--46, January 2005.
Kazuo Iwama and Akinori Kawachi, "A New Quantum Claw-Finding Algorithm for Three Functions," New Generation Computing, 21(4), pp.319--327, August 2003.
Conference Papers
Akinori Kawachi and Yuki Naito, “Quantum Query Lower Bounds for Key Recovery Attacks on the Even-Mansour Cipher,” Proceeding of The 29th International Computing and Combinatorics Conference (COCOON 2023), pp. 3-16, 2023.
Akinori Kawachi and Harumichi Nishimura, "Communication Complexity of Private Simultaneous Quantum Messages Protocols," Proceedings of Conference on Information-Theoretic Cryptography (ITC 2021), pp. 20:1-20:19, 2021.
Akinori Kawachi, "Hamming Weight of Product of Random Sparse Polynomials," Proceedings of 2020 International Symposium on Information Theory and Its Applications (ISITA 2020), pp. 368-371, 2020.
Hideaki Miyaji, Akinori Kawachi, and Atsuko Miyaji, “String commitment schemes with low output locality,” Proceedings of AsiaJCIS 2019, pp.32-39, 2019.
Akinori Kawachi, Mitsunori Ogihara, and Kei Uchizawa, "Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems," Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) , LIPIcs Vol. 83, 8:1-8:13.
Akinori Kawachi, Kenichi Kawano, Francois Le Gall, and Suguru Tamaki, "Quantum Query Complexity of Unitary Operator Discrimination," Proceedings of the 23rd International Computing and Combinatorics Conference (COCOON 2017), 309-320, August 2017.
Akinori Kawachi, Hirotoshi Takebe, and Keisuke Tanaka, "Lower Bounds for Key Length of k-wise Almost Independent Permutations and Certain Symmetric-Key Encryption Schemes," Proceedings of the 11th International Workshop on Security (IWSEC 2016), LNCS 9836, pp.195--211, September 2016.
Akinori Kawachi, Benjamin Rossman, and Osamu Watanabe, "The Query Complexity of Witness Finding," Proceedings of the 9th International Computer Science Symposium in Russia (CSR 2014), LNCS 8476, pp.218--231, June 2014. Best Paper Award.
Akinori Kawachi, Hirotoshi Takebe, and Keisuke Tanaka, "Symmetric-Key Encryption Scheme with Multi-Ciphertext Non-Malleability," Proceedings of the 7th International Workshop on Security (IWSEC 2012), LNCS 7631, pp.123--137, November 2012.
Andrej Bogdanov, Akinori Kawachi, and Hidetoki Tanaka, "Hard Functions for Low-Degree Polynomials over Prime Fields," Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS 2011), LNCS 6907, pp.120--131, August 2011.
Akinori Kawachi, Christopher Portmann, and Keisuke Tanaka, "Characterization of the Relations between Information-Theoretic Non-Malleability, Secrecy, and Authenticity," Proceedings of the 5th International Conference on Information Theoretic Security (ICITS 2011), LNCS 6673, pp.6--24, May 2011.
Dan Gutfreund and Akinori Kawachi, "Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds," Proceedings of the 25th IEEE Conference on Computational Complexity (CCC 2010), pp.38--49, June 2010.
Akinori Kawachi, Akira Numayama, Keisuke Tanaka and Keita Xagawa, "Security of Encryption Schemes in Weakened Random Oracles," Proceedings of the 13th International Conference on Theory and Practice of Public-Key Cryptography (PKC 2010), LNCS 6056, pp.403--419, May 2010.
Akinori Kawachi, Keisuke Tanaka and Keita Xagawa, "Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems," Proceedings of the 14th Annual International Conference on the Theory and Application of Cryptology & Information Security (Asiacrypt 2008), LNCS 5350, pp.372--389, November 2008.
Akinori Kawachi and Christopher Portmann, "On the Power of Quantum Encryption Keys," Proceedings of the 2nd International Workshop on Post-Quantum Cryptography (PQCrypto 2008), LNCS 5299, pp.165--180, October 2008.
Akinori Kawachi, Keisuke Tanaka and Keita Xagawa, "Multi-Bit Cryptosystems Based on Lattice Problems," Proceedings of the 10th International Conference on Theory and Practice of Public-Key Cryptography (PKC 2007), LNCS 4450, pp.315--329, March 2007.
Akinori Kawachi and Tomoyuki Yamakami, "Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding," Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006), LNCS 4052, pp.216--227, July 2006.
Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Rudy Raymond, and Shigeru Yamashita, "Improved Algorithms for Quantum Identification of Boolean Oracles," Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), LNCS 4059, pp.280--291, July 2006.
Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura, and Tomoyuki Yamakami, "Computational Indistinguishability between Quantum States and Its Cryptographic Application," Advances in Cryptography -- Eurocrypt 2005, LNCS 3494, pp.268--284, March 2005.
Kazuo Iwama and Akinori Kawachi, "Approximated Two Choices in Randomized Load Balancing," Proceedings of the 15th International Symposium on Algorithms and Computation (ISAAC 2004), LNCS 3341, pp.545--557, November 2004.
Akinori Kawachi, Hirotada Kobayashi, Takeshi Koshiba, and Raymond H. Putra, "Universal Test for Quantum One-Way Permutations," Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004), LNCS 3153, pp.839--850, August 2004.
Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda, Raymond H. Putra, and Shigeru Yamashita, "Quantum Identification of Boolean Oracles," Proceedings of the 21st Symposium on Theoretical Aspects of Computer Science (STACS 2004), Lecture Notes in Computer Science 2996, pp.105--116, March 2004.
Kazuo Iwama, Akinori Kawachi, and Shigeru Yamashita, "Quantum Sampling for Balanced Allocations," Proceedings of the 9th International Computing and Combinatorics Conference (COCOON 2003), Lecture Notes in Computer Science 2697, pp.304--318, July 2003.
Kazuo Iwama and Akinori Kawachi, "Brief Announcement: Compact Routing with Stretch Factor of Less Than Three," Proceedings of the 19th ACM Symposium on Principles of Distributed Computing (PODC 2000), p.337, July 2000.