Computer and Mathematical Sciences

Information Security A16

  • Prof. Hiroki Shizuya    
  • Assoc. Prof. Masao Sakai    
  • Assoc. Prof. Shuji Isobe  
  • Assis. Prof. Eisuke Koizumi    
  • Assis. Prof. Shingo Hasegawa    
Keywordscomputational complexity theory, reduction, public-key cryptosystem, cryptographic assumption, blockchain

Mathematical theory of information security

The main research subjects of the laboratory are on the theory of information security, which also involves related mathematics: combinatorics, computational complexity theory, algebra, geometry and so on. We are currently interested in the following subjects.

(1) Computational Complexity Theory

In the computational complexity theory, we classify various computational problems according to the difficulty of solving them and analyze reduction relationships among the problems. We study the complexity of various computational problems from a standpoint of the cryptologic research.

(2) Security of Cryptographic Systems

The security of public-key cryptosystems depends on some computational problems that are presumably hard to solve. We are interested in the complexity of such primitive problems.

Any cryptographic scheme depending on some primitive problem would no longer be secure if the underlying problem were proven to be easy. This happens when efficient algorithms are found or quantum computers work in a practical sense. We are interested in new primitives that are assured to be sufficiently hard even in such circumstances. We also attempt to find a generic methodology for reinforcing the hardness of the primitives.


Recently, we are also working on practical issues such as the development and evaluation of secure blockchain applications.

  • Reductions among Cryptographic Primitives

  • Inclusion Diagram on Some Complexity Classes