# Computing Theory Research Group

Computing theory research aims at establishing a theoretical foundation to handle information properly on computers and networks. Secure communication protocols on the internet and efficient computing algorithms on quantum computers etc. are being pursued with information and computer science approaches. The goal is to support a safe, secure, convenient, and pleasant next-generation network society.

Group Leaderă€€Seiichiro Tani

# Research Index

## Quantum Information Science

By putting information on photons, atoms, etc, and controlling them precisely and individually, various information processing schemes that are currently impossible will become possible. Quantum information science is expected to be an important field in information processing in the near future. Our mission is to find innovative theoretical principles of quantum information science that make the impossible possible...read more

## Security Verification using Formal Methods

If we are to use electronic voting or electronic commerce systems with confidence, we must ensure their safety.
We must find a way to verify that the protocols used in the network systems satisfy various desired security requirements including non-leakage of important information and protection against spoofing attacks. However, the verifications of complicated protocols utilizing high-level cryptographic techniques are often error-prone.
We are conducting research on...read more

## Dynamical Information Processing

The use of strong fluctuations in devices poses new possibilities of communication technology. We are exploring the possibilities by applying new methods from the fields of nonlinear dynamics and information theory to problems of signal transmission and generation in strongly fluctuating devices. In particular, we are developing a secure key sharing scheme and a fast and compact physical random number generator, based on strongly fluctuating phenomena in optical devices...read more

# Publications

- 2016
- 2015
- 2014
- 2013
- 2012

## 2016

### Journal Papers

- Takahashi, Y., Tani, S., Yamazaki, T., and Tanaka, K.: Commuting quantum circuits with few outputs are unlikely to be classically simulatable. Quantum Information and Computation, Vol.16, No.3&4, pp.251-270 (2016).
- Le Gall, F., Nishimura, H., and Tani, S.: Quantum algorithms for finding constant-sized sub- hypergraphs. Theoretical Computer Science, Vol.609, Part 3, pp. 569-582 (2016).
- Kubota, T., Kakutani, Y., Kato, G., Kawano, Y., and Sakurada, H. Semi-Automated Verification of Security Proofs of Quantum Cryptographic Protocols. Journal of Symbolic Computation, Vol. 71, March-April, pp. 192-220 (2016).
- Kawano, Y., and Sekigawa, H.: Quantum Fourier transform over symmetric groups --- improved result, Journal of Symbolic Computation, Vol. 75, pp. 219-243 (2016).

## 2015

### Journal Papers

- Inubushi, M., Yoshimura, K., Daivs, P.: Noise robustness of unpredictability in a chaotic laser system: Toward reliable physical random bit generation. Physical Review E, 91, 022918 (2015).
- Inubushi, M., Yoshimura, K., Arai, K., Davis, P.: Physical random bit generators and their reliability: focusing on chaotic laser systems. Nonlinear Theory and Its Applications (NOLTA), IEICE, 6, 2 (2015).
- Owari, M., Maruyama, K., Takui, T., and Kato, Go.: Probing an untouchable environment as a resource for quantum computing. Physical Review A, 91, 012343 (2015).

### Conference Papers

- Inubushi, M., Takehiro, S., Yamada, M.: Covariant Lyapunov analysis and its application to Navier-Stokes flows. Prog. and Abstract Book of The 9th International Conference on Computational Physics (ICCP9), p.121 (2015).
- Inubushi, M., Yoshimura, K., Arai, K., Davis, P.: Noise-robustness of physical random bit generation. The 35th Dynamics Days Europe 2015 (2015).
- Inubushi, M. and Yoshimura, K.: Memory capacity and time scales in delay dynamical systems for reservoir computing. The 35th Dynamics Days Europe 2015 (2015).
- Owari, M., Maruyama, K., and Kato, G.: Probing an untouchable environment as a resource for quantum computing. Quantum Information Processing (QIP 2015) (2015).
- Akibue, S., Owari, M., Kato, G., and Murao, M.: Globalness of separable maps in terms of classical indefinite causal correlations. Quantum Information Processing (QIP 2015) (2015).
- Takahashi, Y., Tani, S., Yamazaki, T., and Tanaka, K.: Commuting quantum circuits with few outputs are unlikely to be classically simulatable. Proc. of the 21st International Computing and Combinatorics Conference (COCOON 2015), LNCS, Vol.9198, pp.223-234 (2015).
- Takahashi, Y.: On the computational power of constant-depth exact quantum circuits. Computability Theory and Foundations of Mathematics (CTFM 2015) (2015).
- Tani, S.: Improved hardness results for classically simulating quantum computation models. Workshop on Quantum Computational Complexity (ICALP 2015 Satellite Workshop, Invited talk), (2015).
- Miyauchi, M: Track layouts of Graph Subdivisions. 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG2 2015) (2015).

## 2014

### Journal Papers

- Tamaki, K., Curty, M., Kato, G., Lo, H.-K., Azuma, K.: Loss-tolerant quantum cryptography with imperfect sources. Physical Review A, 90, 052314 (2014)
- Kawano, Y. and Sekigawa, H.: Quantum Fourier Transform over Symmetric Groups --- Improved Result. ACM Communications in Computer Algebra, Vol.48, No.3, Issue 189, pp.127-129 (2014).
- Tanjo, T. and Minami, K. and Mano, K. and Maruyama, H.: Evaluating data utility of privacy-preserving pseudonymized location datasets. Journal of Wireless Mobile Networks Ubiquitous Computing, and Dependable Applications, Vol.5, No.3, pp.63-78 (2014).
- Owari, M. and Hayashi, M.: Asymptotic local hypothesis testing between a pure bipartite state and the completely mixed state. Physical Review A, Vol.90, 032327 (2014).
- Takahashi, Y., Yamazaki, T., and Tanaka, K.: Hardness of classically simulating quantum circuits with unbounded Toffoli and fan-out gates. Quantum Information and Computation, Vol.14, No.13&14, pp.1149-1164 (2014).
- Kobayashi, H., Matsumoto, K., and Tani, S.: Simpler exact leader election via quantum reduction. Chicago Journal of Theoretical Computer Science, Vol.2014, No.10 (2014).
- Shinohara, S., Fukushima, T., Sunada, S., Harayama, T., Arai, K., and Yoshimura, K.: Anticorrelated bidirectional output from quasistadium-based semiconductor microlasers. Optical Review, Vol.21, No.2, pp.113-116 (2014).
- Sunada, S., Arai, K., Yoshimura, K., and Adachi, M.: Optical phase synchronization by injection of common broadband low-coherent light. Physical Review Letters, Vol.112, No.20, 204101 (2014).
- Takahashi, R., Akizawa, Y., Uchida, A., Harayama, T., Tsuzuki, K., Sunada, S., Arai, K., Yoshimura, K., and Davis, P.: Fast physical random bit generation with photonic integrated circuits with different external cavity lengths for chaos generation. Optics Express, Vol.22, No.10, pp.11727-11740 (2014).
- Shinohara, S., Sunada, S., Fukushima, T., Harayama, T., Arai, K., and Yoshimura, K.: Efficient optical path folding by using multiple total internal reflections in a microcavity. Applied Physics Letters, Vol.105, No.15, 151111 (2014).

### Conference Papers

- Inubushi, M., Yoshimura, K., Daivs, P.: Noise-robustness of Random Bit Generations by Chaotic Semiconductor Lasers. Proc. of the 2014 International Symposium on Nonlinear Theory and Its Applications (NOLTA 2014), pp.561-564 (2014).
- Akibue, S., Owari,M., Kato, G., and Murao, M.: Globalness of separable maps in terms of classical indefinite causal correlations. 14th Asian Quantum Information Science Conference (AQIS 2014) (2014).
- Kawano, Y. and Sekigawa, H.: Quantum Fourier Transform over Symmetric Groups --- Improved Result. Proc. of the International Symposium on Symbolic and Algebraic Computation (ISSAC 2014), pp.31-33 (2014).
- Kawano, Y. and Sekigawa, H: Quantum Fourier Transform over Symmetric Groups --- Improved Result. XVIII Conference on Quantum Information Processing (QIP 2014) (2014).
- Tanjo, T., Minami, K., Mano, K., and Maruyama, H.: On Safety of Pseudonym-based Location Data in the Context of Constraint Satisfation Problems. Proc. of the 2014 Asian Conference on Availability, Reliability and Security (AsiaARES 2014), pp.511-520 (2014).
- Mano, K. and Minami, K. and Maruyama, H.: Pseudonym Exchange for Privacy-Preserving Publishing of Trajectory Data Set. Proc. of 2014 IEEE 3rd Global Conference on Consumer Electronics (GCCE 2014), pp.691-695 (2014).
- Miyauchi, M.: Track layouts of Graph Subdivisions. Proc. of the 17th Japan-Korea Joint Workshop on Algorithms and Computation (WAAC 2014), pp.145--149 (2014).
- Sakurada, H.: Computational Soundness of Symbolic Blind Signatures under Active Attacker. Foundations and Practice of Security (6th International symposium, FPS 2013, La Rochelle, France, October 21-22, 2013, Revised Selected Papers), LNCS, Vol.8352, pp.247-263 (2014).
- Le Gall, F., Nishimura, H., and Tani, S.: Quantum algorithms for finding constant-sized sub-hypergraph. Proc. of the 20th International Computing and Combinatorics Conference (COCOON 2014), LNCS, Vol.8591, pp.429-440 (2014).
- Doi, Y. and Yoshimura, K.: Constructing a lattice model supporting highly mobile discrete breathers. Proc. of the 2014 International Symposium on Nonlinear Theory and Its Applications (NOLTA 2014), pp.401-403 (2014).
- Kakesu, I., Suzuki, N., Uchida, A., Yoshimura, K., Arai, K., and Davis, P.: Frequency dependence of common-signal-induced synchronization in semiconductor lasers with constant-amplitude and random-phase light. Proc. of the 2014 International Symposium on Nonlinear Theory and Its Applications (NOLTA 2014), pp.466-469 (2014).
- Sunada, S., Arai, K., Yoshimura, K., and Adachi, M.: Common noise-induced optical phase synchronization in lasers. Proc. of the 2014 International Symposium on Nonlinear Theory and Its Applications (NOLTA 2014), pp.470-473 (2014).
- Arai, K., Yoshimura, K., Sunada, S., and Uchida, A.: Synchronization induced by common ASE noise in semiconductor lasers. Proc. of the 2014 International Symposium on Nonlinear Theory and Its Applications (NOLTA 2014), pp.474-477 (2014).
- Yoshimura, K., Uchida, A., Muramatsu, J., and Davis, P.: Spectral characteristics of consistency of a single-mode semiconductor laser injected with broadband random light. Proc. of the 2014 International Symposium on Nonlinear Theory and Its Applications (NOLTA 2014), pp.545-548 (2014).

### Book Chapter, Tutorial Papers

- Yoshimura, K., Doi, Y. and Kimura, M.: Localized modes in nonlinear discrete systems. in M. Ohtsu and T. Yatsui (ed.), Progress in Nanophotonics 3, Chap. 4 (Springer-Verlag, Berlin Heidelberg, 2014).

## 2013

- Takahashi, Y., Yamazaki, T., and Tanaka, K.: Hardness of classically simulating quantum circuits with unbounded Toffoli and fan-out gates. Proc. of the 38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013), Lecture Notes in Computer Science 8087, pp.801-812 (2013).
- Takahashi, Y., and Tani, S.: Collapse of the hierarchy of constant-depth exact quantum circuits. Proc. of the 28th IEEE Conference on Computational Complexity (CCC 2013), pp.168-178 (2013).
- Owari M., Maruyama K., and Kato G.: Probing an untouchable environment as a resource for quantum. Workshop on Quantum Metrology, Interaction, and Causal Structure (2013).
- Kato G.: Analytical Optimization of Local Quantum Operation and Classical Communication. Math-for-Industry (2013).
- Owari M., Maruyama K., Takui T., and Kato G.: Probing an untouchable environment as a resource for quantum computing. NIC@QS (2013).
- Kato G., Tamaki K., Azuma K., and Owari M.: Security of CV-QKD with transmitted local oscillator. QCrypt (2013).
- Kubota, T., Kakutani, Y., Kato, G., Kawano, Y., and Sakurada, H.: Automated Verification of Equivalence on Quantum Cryptographic Protocols. Proc. of SCSS 2013 Symbolic Computation in Software Science 5th International Symposium, pp.64-69 (2013).
- Kawano, Y. and Sekigawa, H.: Quantum Fourier Transform over Symmetric Groups. Proc. of the International Symposium on Symbolic and Algebraic Computation (ISSAC 2013), pp. 227-234 (2013).
- Kubota, T., Kakutani, Y., Kato, G., Kawano, Y., and Sakurada, H.: Automated Verification of Equivalence on Quantum Cryptographic Protocols. Proc. of SCSS 2013 Symbolic Computation in Software Science 5th International Symposium, pp.64-69 (2013).
- Mano, K., Minami, K., and Maruyama, H.: Privacy-preserving publishing of pseudonym-based trajectory location data set. The 2nd International Workshop on Security of Mobile Applications (IWSMA 2013) , (2013).
- Mano, K., Minami, K., and Maruyama, H.: Protecting Location Privacy with K-Confusing Paths Based on Dynamic Pseudonyms. 5th IEEE International Workshop on Security and Social Networking (SESOC 2013), pp. 285-290 (2013).
- Tsukada, Y., Sakurada, H., Mano, K., and Manabe, Y.: An Epistemic Approach to Compositional Reasoning about Anonymity and Privacy. Proc. of 14th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2013), pp.239-248 (2013).
- Mitsunaga, T., Manabe, Y., and Okamoto, T.: Efficient Secure Auction Protocols Based on the Boneh-Goh-Nissim Encryption. IEICE Transactions on Fundamentals of electronics, communications and computer sciences, Vol.E96-A, No.1, pp.68-75 (2013).
- Kubota, T., Kakutani, Y., Kato, G., Kawano, Y., and Sakurada, H.: Automated Verification of Equivalence on Quantum Cryptographic Protocols. Proc. of SCSS 2013 Symbolic Computation in Software Science 5th International Symposium, pp.64-69 (2013).
- Mano, K., Minami, K., and Maruyama, H.: Privacy-preserving publishing of pseudonym-based trajectory location data set. The 2nd International Workshop on Security of Mobile Applications (IWSMA 2013) , (2013).
- Mano, K., Minami, K., and Maruyama, H.: Protecting Location Privacy with K-Confusing Paths Based on Dynamic Pseudonyms. 5th IEEE International Workshop on Security and Social Networking (SESOC 2013), pp. 285-290 (2013).
- Tsukada, Y., Sakurada, H., Mano, K., and Manabe, Y.: An Epistemic Approach to Compositional Reasoning about Anonymity and Privacy. Proc. of 14th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2013), pp.239-248 (2013).
- Mitsunaga, T., Manabe, Y., and Okamoto, T.: Efficient Secure Auction Protocols Based on the Boneh-Goh-Nissim Encryption. IEICE Transactions on Fundamentals of electronics, communications and computer sciences, Vol.E96-A, No.1, pp.68-75 (2013).

## 2012

- Cleve, R., Iwama, K., Le Gall, F., Nishimura, H., Tani, S., Teruyama, J., and Yamashita, S.: Reconstructing strings from substrings with quantum queries. Proc. of Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2013), Lecture Notes in Computer Science 7357, pp. 388-397 (2012).
- Kubota, T., Kakutani, T., Kato G., Kawano, Y., and Sakurada, H.: Application of a Process Calculus to Security Proofs of Quantum Protocols, The 2012 International Conference on Foundations of Computer Science, in press (2012).
- Tani, S. and Kobayashi, H., and Matsumoto, K.: Exact quantum algorithms for the leader election problem. ACM Transactions on Computation Theory, Vol.4, No.1, Article 1 (2012).
- Tani, S.: Compression of View on Anonymous Networks -- Folded View --. IEEE Transactions on Parallel and Distributed Systems, Vol.23, No.2, pp.255-262 (2012).
- Owari, M., Hayashi, M.: Asymptotic local hypothesis testing between a pure bipartite state and the completely mixed state, The 2nd Institute of Mathematical Statistics, Asia Pacific Rim Meeting (2012).
- Kato, G., Maruyama, K., Owari, M.: The Environment Tomography, The 2nd Institute of Mathematical Statistics, Asia Pacific Rim Meeting (2012).
- Azuma, A., Kato, G.: Optimal entanglement manipulation via coherent-state transmission, Physical Review A (PRA) 85, 060303(R) (2012).
- Fujita, K. and Tsukada, Y.: An approach to the formal analysis of license interoperability, Elsevier, Computers and Electrical Engineering, Vol. 38, No. 6, pp. 1670-1686 (2012).
- Bana, G, Adão, Sakurada, H.: Computationally Complete Symbolic Attacker in Action. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012), pp.546-560 (2012).
- Adão, P., Bana, G., and Sakurada, H.: Computationally Sound Verification of the NSL Protocol via Computationally Complete Symbolic Attacker (Abstract). Eighth Workshop on Formal and Computational Cryptography (FCC 2012) (2012).
- Manabe, Y. and Okamoto, T.: Meta-envy-free Cake-cutting and Pie-cutting Protocols. Journal of Information Processing, Vol.20, No.3, pp.686-693 (2012).
- Kiyoshima, S., Manabe, Y., and Okamoto, T.: Efficient Concurrent Oblivious Transfer in Super-Polynomial-Simulation Security. Proc. of 7th International Workshop on Security (IWSEC2012), LNCS Vol.7631, pp.216-232 (2012).
- Manabe, Y. and Okamoto, T.: Meta-envy-free Cake-cutting and Pie-cutting Protocols. Journal of Information Processing, Vol.20, No.3, in press (2012).
- Comon-Lundh, H., Hagiya, M., Kawamoto, Y., Sakurada, H.: Computational Soundness of Indistinguishability Properties without Computable Parsing. The 8th International Conference on Information Security Practice and Experience (ISPEC 2012), Lecture Notes in Computer Science, Vol.7232, pp.63-79 (2012).
- Bana, G. and Comon-Lundh, H.: Towards Unconditional Soundness: Computationally Complete Symbolic Attacker. Proc. of the First International Conference on Principles of Security and Trust (POST 2012), Springer LNCS, Vol.7215, pp.189-208 (2012).
- Manabe, Y. and Okamoto, T.: A Cryptographic Moving-knife Cake-Cutting Protocol. Proc. of International Workshop on Interactions, Games and Protocols (iWIGP2012), EPTCS Vol.78, pp.15-23 (2012).
- Hermanto, Manabe, Y., and Okamoto, T.: A Simplified Private Stable Matching Algorithm. Financial Cryptography and Data Security (FC 2012) (2012).

# Members

**Seiseki Akibue**

## Alumni

**Akinori Abe**

Chiba University

**Tadashi Araragi**

**Kunihiko Fujita**

Bunkyo Gakuin University

**Gergei Bana**

INRIA Saclay-Ile-de-France

**Yumi Nakajima**

Intellectual Property Center

**Hiroki Nakayama**

NEC

**Masaki Owari**

Shizuoka University

**Yoshinao Shiraki**

Toho University

**Junnosuke Yamada**

Cyber Solutions Laboratories