Currently, the following three projects are running.

  • Theory of Cryptography
  • Pseudorandom Generators and Randomness Extractors
  • Cloud Computing Security
  • Quantum Cryptography
  • Computational Complexity via Cryptography

Theory of Cryptography

The notion of one-way functions plays essential role in cryptography. In many cases, the security of cryptographic protocols relies on the computational hardness of the inversion of one-way functions. Some cryptographic protocols are built on stronger assumptions. Thus, reducing assumptions of cryptographic protocols, or showing the unconditional security of cryptographic protocols are important. Moreover, giving efficient constructions of cryptographic protocols is important.

We are interested in theoretical aspects of the following protocols.

  • Public Key Encryption
  • Digintal Signature
  • Commitment
  • Oblivious Transfer
  • Zero Knowledge
  • Secure Function Evaluation

Some of the results concerned:

  • Kai Yuen Cheong, Takeshi Koshiba:
    Reducing Complexity Assumptions for Oblivious Transfer,
    The 4th International Workshop on Security, IWSEC 2009 (Toyama, Japan, 2009.10),
    Lecture Notes in Computer Science 5824, pp.110-124, Springer (2009).
  • Kai Yuen Cheong, Takeshi Koshiba, Shohei Nishiyama:
    Strengthening the Security of Distributed Oblivious Transfer,
    The 14th Australasian Conference on Information Security and Privacy, ACISP 2009 (Brisbane, Australia, 2009.7),
    Lecture Notes in Computer Science 5594, pp.377-388, Springer (2009).
  • Kaoru Kurosawa, Takeshi Koshiba:
    Simple Direct Reduction of String (1,2)-OT to Rabin's OT without Privacy Amplification,
    The 3rd International Conference on Information Theoretic Security, ICITS 2008 (Calgary, Canada, 2008.8),
    Lecture Notes in Computer Science 5155, pp.199-209, Springer (2008).
  • Kaoru Kurosawa, Wataru Kishimoto, Takeshi Koshiba:
    A Combinatorial Approach to Deriving Lower Bounds for Perfectly Secure Oblivious Transfer Reductions,
    IEEE Transactions on Information Theory, 54(6):2566-2571 (2008).

Pseudorandom Generators and Randomness Extractors

The equivalence between the existence of one-way functions and that of pseudorandom generators is one of the monumental results in cryptology. Hastad, Impagliazzo, Luby and Levin erected the work and the reduction was not so efficient. After that Holenstein and Harnik, Haitner and Reingold independently improved the efficiency. The reduction is still inefficient compared with any other cryptographic reductions.

Randomnes extractors are algorithms to extract the randomness from the imperfect sources. For specific sources, some deterministic randomness extractors are constructed. In general, supplemental randomness is necessary as catalyst and almost optimal randomness extractors for general sources are known.

Some relations between pseudorandom generators and randomness extractors are pointed out. Also, randomness extraction is useful in cryptographic construnctions.

Cloud Computing Security

Cloud computing provides network-based services, which appear to be provided by real server hardware. Such virtual servers do not physically exist and can therefore be moved around and scaled up (or down) on the fly without affecting the end users. Security issues are important in cloud computing. For example, fully homomorphic encryption or secure function evaluation can be fundamental ingredients in cloud computing security.

Some of the results concerned:

  • Masaya Yasuda, Takeshi Shiomyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba:
    Secure Pattern Matching using Somewhat Homomorphic Encryption,
    2013 ACM Workshop on Cloud Computing Security, CCSW 2013, pp.65-76, ACM (2013).
  • Masaya Yasuda, Takeshi Shiomyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba:
    Practical Packing Method in Somewhat Homomorphic Encryption,
    The 8th DPM International Workshop on Data Privacy Management, DPM 2013,
    Lecture Notes in Computer Science 8247.

Quantum Cryptography

Since Shor devised efficient algorithms on quantum computers for the integer factorization problem and the discrete logarithm problem, algorithmic aspects on quantum computers have been extensively investigated. On the other hand, besides quantum key distribution which was initiated by Bennett and Brassard, there are a few research results from the cryptographic point of view.

One-way function is one of the most fundamental notions in computational cryptography. Some candidates are practically used in the current Internet protocols. When considered quantum adversaries, there are few candidates for quantum one-way functions. For bit commitment schemes and zero-knowledge proof systems, which are cryptographic primitives, it is quite difficult to give even natural definitions.

I believe that the fundamental research for quantum computational cryptography is trailbrazing!

Some of the results concerned:

  • Sueki Takahiro, Takeshi Koshiba, Tomoyuki Morimae:
    Ancilla-Driven Universal Blind Quantum Computation,
    Physical Review A, 87, 060301 (R), 2013.
  • Takeshi Koshiba, Takanori Odaira:
    Statistically-Hiding Quantum Bit Commitment from Approximable-Preimage-Size Quantum One-Way Function,
    The 4th Workshop on Theory of Quantum Computation, Communication, and Cryptography, TQC 2009 (Waterloo, Canada, 2009.5),
    Lecture Notes in Computer Science 5906, pp.33-46, Springer (2009).
  • Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura, Tomoyuki Yamakami:
    Computational Indistinguishability between Quantum States and Its Cryptographic Application,
    EUROCRYPT 2005 (Aarhus, Demark, 2005.5),
    Lecture Notes in Computer Science 3494, pp.268-284, Springer (2005).
  • Akinori Kawachi, Hirotada Kobayashi, Takeshi Koshiba, Raymond H. Putra:
    Universal Test for Quantum One-Way Permutations,
    Theoretical Computer Science, 345(2-3):370-385 (2005).

Computational Complexity via Cryptography

P vs NP problem is related to the existence of one-way functions. Recently, Goldreich proposed a one-way function candidate, based on the random graphs and local functions. The 3-SAT is a well known NP-complete problem. The average case complexity of 3-SAT can be discussed in terms of Goldreich's one-way function.