Updated on 2022/07/02

写真a

 
KOSHIBA, Takeshi
 
Affiliation
Faculty of Education and Integrated Arts and Sciences, School of Education
Job title
Professor
Profile

My research interest includes Theoretical Computer Science. Especially,

  • Quantum Computation, Cryptography and Information
  • Theory of Cryptography
  • Pseudo-random Generation and Randomness Extraction

 

Concurrent Post

  • Faculty of Education and Integrated Arts and Sciences   Graduate School of Education

Research Institute

  • 2021
    -
    2022

    データ科学センター   兼任センター員

Education

  • 1998.04
    -
    2001.03

    Tokyo Institute of Technology   Graduate School of Information Science and Engineering  

  • 1990.04
    -
    1992.03

    Tokyo Institute of Technology   Graduate School of Science and Engineering  

  • 1986.04
    -
    1990.03

    Tokyo Institute of Technology   School of Engineering   Department of Computer Science  

Degree

  • 2001.03   Tokyo Institute of Technology   Doctor of Science

Research Experience

  • 2017.04
    -
    Now

    Waseda University   Faculty of Education and Integrated Arts and Sciences

  • 2015.04
    -
    2017.03

    Saitama University   Graduate School of Science and Engineering   Professor

  • 2005.04
    -
    2015.03

    Saitama University   Graduate School of Science and Engineering   Associate Professor

  • 2010.11
    -
    2011.02

    Université de Paris 7 Dederot   Laboratoire d'Informatique Algorithmique: Fondements et Applications (LIAFA)

  • 2010.03
    -
    2010.11

    Université de Paris-Sud   Laboratoire de Recherche en Informatique (LRI)

  • 2006.04
    -
    2009.03

    The Institute of Statistical Mathematics

  • 1992.04
    -
    2005.03

    株式会社富士通研究所   研究員

  • 2002.11
    -
    2004.09

    Japan Science and Technology Agency

  • 1999.01
    -
    2000.03

    Telecommunications Advancement Organization of Japan

▼display all

Professional Memberships

  • 2022.02
    -
     

    日本数学会

  •  
     
     

    IPSJ

  •  
     
     

    IEICE

  •  
     
     

    IEEE

  •  
     
     

    ACM

  •  
     
     

    IACR

▼display all

 

Research Areas

  • Theory of informatics

Research Interests

  • Information Security

  • Theoretical Computer Science

  • privacy-preserving

  • Secure Computation

  • Quantum Information

  • Quantum Computation

  • Theory of Cryptography

▼display all

Papers

  • The Dichotomy of Neural Networks and Cryptography: War and Peace

    Behrouz Zolfaghari, Takeshi Koshiba

    Applied System Innovation   5 ( 4 ) Article 61 - (28 pages)  2022.06  [Refereed]  [International journal]  [International coauthorship]

    Authorship:Last author

     View Summary

    In recent years, neural networks and cryptographic schemes have come together in war and peace; a cross-impact that forms a dichotomy deserving a comprehensive review study. Neural networks can be used against cryptosystems; they can play roles in cryptanalysis and attacks against encryption algorithms and encrypted data. This side of the dichotomy can be interpreted as a war declared by neural networks. On the other hand, neural networks and cryptographic algorithms can mutually support each other. Neural networks can help improve the performance and the security of cryptosystems, and encryption techniques can support the confidentiality of neural networks. The latter side of the dichotomy can be referred to as the peace. There are, to the best of our knowledge, no current surveys that take a comprehensive look at the many ways neural networks are currently interacting with cryptography. This survey aims to fill that niche by providing an overview on the state of the cross-impact between neural networks and cryptography systems. To this end, this paper will highlight the current areas where progress is being made as well as the aspects where there is room for future research to be conducted.

    DOI

  • Chaotic Image Encryption: State-of-the-Art, Ecosystem, and Future Roadmap

    Behrouz Zolfaghari, Takeshi Koshiba

    Applied System Innovation   5 ( 3 ) Article 57 - (38 pages)  2022.06  [Refereed]  [International journal]  [International coauthorship]

    Authorship:Last author

     View Summary

    Recently, many researchers have been interested in the application of chaos in cryptography. Specifically, numerous research works have been focusing on chaotic image encryption. A comprehensive survey can highlight existing trends and shed light on less-studied topics in the area of chaotic image encryption. In addition to such a survey, this paper studies the main challenges in this field, establishes an ecosystem for chaotic image encryption, and develops a future roadmap for further research in this area.

    DOI

  • Guesswork of a quantum ensemble

    Michele Dall'Arno, Francesco Buscemi, Takeshi Koshiba

    IEEE Transactions on Information Theory   68 ( 5 ) 3139 - 3143  2022.05  [Refereed]

    Authorship:Last author

    DOI

  • CARAN: A Context-Aware Recency Based Attention Network for Point-of-interest Recommendation

    Md. Billal Hossain, Mohammad Shamsul Arefin, Iqbal H. Sarker, Md. Kowsher, Pranab Kumar Dhar, Takeshi Koshiba

    IEEE Access   10   36299 - 36310  2022.04  [Refereed]  [International journal]  [International coauthorship]

    Authorship:Last author

    DOI

  • An Enhanced Neural Word Embedding Model for Transfer Learning

    Md. Kowsher, Md. Shohanur Islam Sobuj, Md. Fahim Shahriar, Nusrat Jahan Prottasha, Mohammad Shamsul Arefin, Pranab Kumar Dhar, Takeshi Koshiba

    Applied Sciences   12 ( 6 ) Article 2848 - (16 pages)  2022.03  [Refereed]  [International journal]  [International coauthorship]

    Authorship:Last author

     View Summary

    Due to the expansion of data generation, more and more natural language processing (NLP) tasks are needing to be solved. For this, word representation plays a vital role. Computation-based word embedding in various high languages is very useful. However, until now, low-resource languages such as Bangla have had very limited resources available in terms of models, toolkits, and datasets. Considering this fact, in this paper, an enhanced BanglaFastText word embedding model is developed using Python and two large pre-trained Bangla models of FastText (Skip-gram and cbow). These pre-trained models were trained on a collected large Bangla corpus (around 20 million points of text data, in which every paragraph of text is considered as a data point). BanglaFastText outperformed Facebook’s FastText by a significant margin. To evaluate and analyze the performance of these pre-trained models, the proposed work accomplished text classification based on three popular textual Bangla datasets, and developed models using various machine learning classical approaches, as well as a deep neural network. The evaluations showed a superior performance over existing word embedding techniques and the Facebook Bangla FastText pre-trained model for Bangla NLP. In addition, the performance in the original work concerning these textual datasets provides excellent results. A Python toolkit is proposed, which is convenient for accessing the models and using the models for word embedding, obtaining semantic relationships word-by-word or sentence-by-sentence; sentence embedding for classical machine learning approaches; and also the unsupervised finetuning of any Bangla linguistic dataset.

    DOI

  • The Odyssey of Entropy: Cryptography

    Behrouz Zolfaghari, Khodakhast Bibak, Takeshi Koshiba

    Entropy   24 ( 2 ) Article 266 - (27 pages)  2022.02  [Refereed]  [International journal]  [International coauthorship]

    Authorship:Last author

    DOI

  • Cryptography in Hierarchical Coded Caching: System Model and Cost Analysis

    Behrouz Zolfaghari, Vikrant Singh, Brijesh Kumar Rai, Khodakhast Bibak, Takeshi Koshiba

    Entropy   23 ( 11 ) Article 1459 - (22 pages)  2021.11  [Refereed]  [International journal]  [International coauthorship]

    Authorship:Last author

    DOI

  • Frequent contiguous pattern mining over biological sequences of protein misfolded diseases

    Mohammad Shahedul Islam, Md. Abul Kashem Mia, Mohammad Shamsur Rahman, Mohammad Shamsul Arefin, Pranab Kumar Dhar, Takeshi Koshiba

    BMC Bioinformatics   22 ( 1 ) Article 435 - (28 pages)  2021.09  [Refereed]  [International journal]  [International coauthorship]

    Authorship:Last author

     View Summary

    <title>Abstract</title><sec>
    <title>Background</title>
    Proteins are integral part of all living beings, which are building blocks of many amino acids. To be functionally active, amino acids chain folds up in a complex way to give each protein a unique 3D shape, where a minor error may cause misfolded structure. Genetic disorder diseases i.e. <italic>Alzheimer, Parkinson,</italic> etc. arise due to misfolding in protein sequences. Thus, identifying patterns of amino acids is important for inferring protein associated genetic diseases. Recent studies in predicting amino acids patterns focused on only simple protein misfolded disease i.e. <italic>Chromaffin Tumor</italic>, by association rule mining. However, more complex diseases are yet to be attempted. Moreover, association rules obtained by these studies were not verified by usefulness measuring tools.



    </sec><sec>
    <title>Results</title>
    In this work, we analyzed protein sequences associated with complex protein misfolded diseases (i.e. <italic>Sickle Cell Anemia, Breast Cancer, Cystic Fibrosis, Nephrogenic Diabetes Insipidus,</italic> and <italic>Retinitis Pigmentosa 4</italic>) by association rule mining technique and objective interestingness measuring tools. Experimental results show the effectiveness of our method.


    </sec><sec>
    <title>Conclusion</title>
    Adopting quantitative experimental methods, this work can form more reliable, useful and strong association rules i. e. dominating patterns of amino acid of complex protein misfolded diseases. Thus, in addition to usual applications, the identified patterns can be more useful in discovering medicines for protein misfolded diseases and thereby may open up new opportunities in medical science to handle genetic disorder diseases.


    </sec>

    DOI

  • CricShotClassify: An Approach to Classifying Batting Shots from Cricket Videos Using a Convolutional Neural Network and Gated Recurrent Unit

    Anik Sen, Kaushik Deb, Pranab Kumar Dhar, Takeshi Koshiba

    Sensors   21 ( 8 ) Article 2846 - (19 pages)  2021.04  [Refereed]  [International journal]  [International coauthorship]

    Authorship:Last author

    DOI

  • A Deep Learning Approach to Predict Autism Spectrum Disorder Using Multisite Resting-State fMRI

    Faria Zarin Subah, Kaushik Deb, Pranab Kumar Dhar, Takeshi Koshiba

    Applied Sciences   11 ( 8 ) Article 3636 - (16 pages)  2021.04  [Refereed]  [International journal]  [International coauthorship]

    Authorship:Last author

    DOI

  • Plant Leaf Disease Recognition using Depthwise Separable Convolution Based Models

    Syed Mohammad, Minhaz Hossain, Kaushik Deb, Pranab Kumar Dhar, Takeshi Koshiba

    Symmetry   13 ( 3 ) Article 511 - (29 pages)  2021.03  [Refereed]  [International journal]  [International coauthorship]

    Authorship:Last author

    DOI

  • Classification of indoor human fall events using deep learning

    Arifa Sultana, Kaushik Deb, Pranab Kumar Dhar, Takeshi Koshiba

    Entropy   23 ( 3 ) Article 328 - (20 pages)  2021.03  [Refereed]  [International coauthorship]

    Authorship:Last author

    DOI

  • Fourier-based verifiable function secret sharing

    Takeshi Koshiba

    Proceedings of 2020 International Symposium on Information Theory and Its Applications (ISITA 2020)     442 - 446  2021.03  [Refereed]

    Authorship:Lead author, Corresponding author

    DOI

  • Traditional Bangladeshi Sports Video Classification Using Deep Learning Method

    Moumita Sen Sarma, Kaushik Deb, Pranab Kumar Dhar, Takeshi Koshiba

    Applied Sciences   11 ( 5 ) Article 2149 - (20 pages)  2021.02  [Refereed]  [International journal]  [International coauthorship]

    Authorship:Last author

    DOI

  • Image Defogging Framework Using Segmentation and the Dark Channel Prior

    Sabiha Anan, Mohammad Ibrahim Khan, Mir Md Saki Kowsar, Kaushik Deb, Pranab Kumar Dhar, Takeshi Koshiba

    Entropy   23 ( 3 ) Article 285 - (21 pages)  2021.02  [Refereed]

    Authorship:Last author

     View Summary

    Foggy images suffer from low contrast and poor visibility problem along with little color information of the scene. It is imperative to remove fog from images as a pre-processing step in computer vision. The Dark Channel Prior (DCP) technique is a very promising defogging technique due to excellent restoring results for images containing no homogeneous region. However, having a large homogeneous region such as sky region, the restored images suffer from color distortion and block effects. Thus, to overcome the limitation of DCP method, we introduce a framework which is based on sky and non-sky region segmentation and restoring sky and non-sky parts separately. Here, isolation of the sky and non-sky part is done by using a binary mask formulated by floodfill algorithm. The foggy sky part is restored by using Contrast Limited Adaptive Histogram Equalization (CLAHE) and non-sky part by modified DCP. The restored parts are blended together for the resultant image. The proposed method is evaluated using both synthetic and real world foggy images against state of the art techniques. The experimental result shows that our proposed method provides better entropy value than other stated techniques along with have better natural visual effects while consuming much lower processing time.

    DOI

  • A guests managing system with lattice-based verifier-local revocation group signature scheme with time-bound keys

    Maharage Nisansala Sevwandi Perera, Takeshi Koshiba

    Advances in Intelligent Systems and Computing (ICMC2019)   1170   81 - 96  2021.02  [Refereed]

    Authorship:Last author

    DOI

  • Efficient Private Conjunctive Query Protocol Over Encrypted Data

    Tushar Kanti Saha, Takeshi Koshiba

    Cryptography   5 ( 1 ) Article 2 - (28 pages)  2021.01  [Refereed]  [International journal]  [International coauthorship]

    Authorship:Last author

    DOI

  • Enhanced Secure Comparison Schemes Using Homomorphic Encryption

    Lihua Wang, Tushar Kanti Saha, Yoshinori Aono, Takeshi Koshiba, Shiho Moriai

    Advances in Intelligent Systems and Computing   1264   211 - 224  2021  [Refereed]  [International coauthorship]

    DOI

  • Efficient protocols for private wildcards pattern matching

    Tushar Kanti Saha, Deevashwer Rathee, Takeshi Koshiba

    Journal of Information Security and Applications   55   Article 102609 - (18 pages)  2020.12  [Refereed]  [International journal]  [International coauthorship]

    Authorship:Last author

    DOI

  • Almost fully secured lattice-based group signatures with verifier-local revocation

    Maharage Nisansala Sevwandi Perera, Takeshi Koshiba

    Cryptography   4 ( 4 ) Article 33 - (28 pages)  2020.11  [Refereed]  [International journal]

    Authorship:Last author

    DOI

  • MCIC: Automated Identification of Cellulases from Metagenomic data and Characterization Based on Temperature and pH Dependence

    Mehdi Foroozandeh Shahraki, Shohreh Ariaeenejad, Fereshteh Fallah Atanaki, Behrouz Zolfaghari, Takeshi Koshiba, Kaveh Kavousi, Ghasem Hosseini Salekdeh

    Frontiers in Microbiology   11   Article 567863 - (10 pages)  2020.10  [Refereed]  [International journal]  [International coauthorship]

    DOI

  • Combined interactive protocol for lattice-based group signature schemes with verifier-local revocation

    Maharage Nisansala Sevwandi Perera, Takeshi Koshiba

    International Journal of Grid and Utility Computing   11 ( 5 ) 662 - 673  2020.09  [Refereed]  [International journal]

    Authorship:Last author

    DOI

  • Content delivery networks: State of the art, trends and future roadmap

    Behrouz Zolfaghari, Gautam Srivastava, Swapnoneel Roy, Hamid R. Nemati, Fatemeh Afghah, Takeshi Koshiba, Abolfazl Razi, Khodakhast Bibak, Pinaki Mitra, Brijesh Kumar Rai

    ACM Computing Surveys   53 ( 2 ) Article 34 - (34 pages)  2020.04  [Refereed]  [International journal]  [International coauthorship]

    DOI

  • Blind audio watermarking based on parametric-slant Hadamard transform and Hessenberg decomposition

    Pranab Kumar Dhar, Azizul Hakim Chowdhury, Takeshi Koshiba

    Symmetry   12 ( 3 ) Article 333 - (16 pages)  2020.03  [Refereed]  [International journal]  [International coauthorship]

    Authorship:Last author

    DOI

  • Blind image watermarking in canonical and cepstrum domains based on 4-connected t-o'clock scrambling

    Farhana Shirin Chowdhury, Pranab Kumar Dhar, Kaushik Deb, Takeshi Koshiba

    Symmetry   12 ( 2 ) Article 266 - (20 pages)  2020.02  [Refereed]  [International journal]  [International coauthorship]

    Authorship:Last author

    DOI

  • Generalized Mm,r-network: A case for fixed message dimensions

    Vikrant Singh, Behrouz Zolfaghari, Chunduri Venkata, Dheeraj Kumar, Brijesh Kumar Rai, Khodakhast Bibak, Gautam Srivastava, Swapnoneel Roy, Takeshi Koshiba

    IEEE Communications Letters   24 ( 1 ) 38 - 42  2020.01  [Refereed]  [International journal]  [International coauthorship]

    Authorship:Last author

    DOI

  • Arbitrable blind quantum computation

    Go Sato, Takeshi Koshiba, Tomoyuki Morimae

    Quantum Information Processing   18 ( 12 ) Article 370 - (8 pages)  2019.12  [Refereed]  [International journal]

    Authorship:Corresponding author

    DOI

  • Efficient private database queries using ring-LWE somewhat homomorphic encryption

    Tushar Kanti Saha, Mayank Rathee, Takeshi Koshiba

    Journal of Information Security and Applications   49   Article 102406 - (15 pages)  2019.12  [Refereed]  [International journal]  [International coauthorship]

    Authorship:Last author

    DOI

  • Perfectly secure message transmission against independent rational adversaries

    Kenji Yasunaga, Takeshi Koshiba

    Lecture Notes in Computer Science (GameSec 2019)   11836   563 - 582  2019.10  [Refereed]

    Authorship:Last author

     View Summary

    © 2019, Springer Nature Switzerland AG. Secure Message Transmission (SMT) is a two-party protocol by which the sender can privately transmit a message to the receiver through multiple channels. An adversary can corrupt a subset of channels and makes eavesdropping and tampering over the corrupted channels. Fujita et al. (GameSec 2018) introduced a game-theoretic security notion of SMT, and showed protocols that are secure even if an adversary corrupts all but one of the channels, which is impossible in the standard cryptographic setting. In this work, we study a game-theoretic setting in which all the channels are corrupted by two or more independent adversaries. Specifically, we assume that there are several adversaries who exclusively corrupt subsets of the channels, and prefer to violate the security of SMT with being undetected. Additionally, we assume that each adversary prefers other adversaries’ tampering to be detected. We show that secure SMT protocols can be constructed even if all the channels are corrupted by such rational adversaries. We also study the situation in which both malicious and rational adversaries exist.

    DOI

  • Impossibility of perfectly-secure one-round delegated quantum computing for classical client

    Tomoyuki Morimae, Takeshi Koshiba

    Quantum Information & Computation   19 ( 3&4 ) 214 - 221  2019.03  [Refereed]  [International journal]

    Authorship:Last author

  • New assumptions on isogenous pairing groups with applications to attribute-based encryption

    Takeshi Koshiba, Katsuyuki Takashima

    Lecture Notes in Computer Science (ICISC 2018)   11396   3 - 19  2019.01  [Invited]

    DOI

  • Outsourcing private equality tests to the cloud

    Tushar Kanti Saha, Takeshi Koshiba

    Journal of Information Security and Applications   43   83 - 98  2018.12  [Refereed]  [International journal]  [International coauthorship]

    Authorship:Last author

    DOI

  • Achieving strong security and member registration for lattice-based group signature scheme with verifier-local revocation

    Maharage Nisansala Sevwandi Perera, Takeshi Koshiba

    Journal of Internet Services and Information Security   8 ( 4 ) 1 - 15  2018.11  [Refereed]  [International journal]

    Authorship:Last author

    DOI

  • Achieving strong security and verifier-local revocation for dynamic group signatures from lattice assumptions

    Maharage Nisansala Sevwandi Perera, Takeshi Koshiba

    Lecture Notes in Computer Science (STM 2018)   11091   3 - 19  2018.10  [Refereed]

    DOI

  • Almost-fully secured fully dynamic group signatures with efficient verifier-local revocation and time-bound keys

    Maharage Nisansala Sevwandi Perera, Takeshi Koshiba

    Lecture Notes in Computer Science (IDCS 2018)   11226   134 - 147  2018.10  [Refereed]

    DOI

  • Achieving full security for lattice-based group signatures with verifier-local revocation

    Maharage Nisansala Sevwandi Perera, Takeshi Koshiba

    Lecture Notes in Computer Science (ICICS 2018)   11149   287 - 302  2018.10  [Refereed]

    DOI

  • Perfectly secure message transmission against rational timid adversaries

    Maiki Fujita, Kenji Yasunaga, Takeshi Koshiba

    Lecture Notes in Computer Science (GameSec 2018)   11199   127 - 144  2018.10  [Refereed]

     View Summary

    © 2018, Springer Nature Switzerland AG. Secure Message Transmission (SMT) is a two-party cryptographic protocol by which the sender can securely and reliably transmit messages to the receiver using multiple channels. It is assumed that an adversary corrupts a subset of the channels, and makes eavesdropping and tampering over the corrupted channels. In this work, we consider a game-theoretic security model for SMT. Specifically, we introduce a rational adversary who has the preference for the outcome of the protocol execution. We show that, under some reasonable assumption on the adversary’s preference, even if the adversary corrupts all but one of the channels, it is possible to construct SMT protocols with perfect security against rational adversaries. More specifically, we consider “timid” adversaries who prefer to violate the security requirement of SMT, but do not prefer the tampering actions to be detected. In the traditional cryptographic setting, perfect SMT can be constructed only when the adversary corrupt a minority of the channels. Our results demonstrate a way of circumventing the impossibility results of cryptographic protocols based on a game-theoretic approach.

    DOI

  • Fully dynamic group signature scheme with member registration and verifier-local revocation

    Maharage Nisansala Sevwandi Perera, Takeshi Koshiba

    Springer Proceedings in Mathematics & Statistics (Mathematics and Computing, ICMC 2018)   253   399 - 415  2018.09  [Refereed]

    DOI

  • Fourier-based function secret sharing with general access structure

    Takeshi Koshiba

    Springer Proceedings in Mathematics & Statistics (Mathematics and Computing, ICMC 2018)   253   417 - 428  2018.09  [Refereed]

    DOI

  • Zero-knowledge proof for lattice-based group signature schemes with verifier-local revocation

    Maharage Nisansala Sevwandi Perera, Takeshi Koshiba

    Lecture Notes on Data Engineering and Communications Technologies (TwCSec@NBiS 2018)   22   772 - 782  2018.09  [Refereed]

    DOI

  • Achieving almost-full security for lattice-based fully dynamic group signatures with verifier-local revocation

    Maharage Nisansala Sevwandi Perera, Takeshi Koshiba

    Lecture Notes in Computer Science (ISPEC 2018)   11125   229 - 247  2018.09  [Refereed]

    DOI

  • Private comparison protocol and its application to range queries

    Tushar Kanti Saha, Mayank, Deevashwer, Takeshi Koshiba

    Lecture Notes in Computer Science (IDCS 2017)   10794   128 - 141  2018.07  [Refereed]

    DOI

  • Universal construction of cheater-identifiable secret sharing against rushing cheaters based on message authentication

    Masahito Hayashi, Takeshi Koshiba

    Proceedings of 2018 IEEE International Symposium on Information Theory (ISIT 2018)     2614 - 2618  2018.06  [Refereed]

    DOI

  • Non-transferable proxy re-encryption for multiple groups

    Ei Mon Cho, Lwin San, Takeshi Koshiba

    International Journal of Space-Based and Situated Computing   8 ( 1 ) 20 - 29  2018.04  [Refereed]

    DOI

  • Privacy-preserving equality test towards big data

    Tushar Kanti Saha, Takeshi Koshiba

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   10723   95 - 110  2018  [Refereed]

     View Summary

    In this paper, we review the problem of private batch equality test (PriBET) that was proposed by Saha and Koshiba (3rd APWConCSE 2016). They described this problem to find the equality of an integer within a set of integers between two parties who do not want to reveal their information if they do not equal. For this purpose, they proposed the PriBET protocol along with a packing method using the binary encoding of data. Their protocol was secured by using ring-LWE based somewhat homomorphic encryption (SwHE) in the semi-honest model. But this protocol is not fast enough to address the big data problem in some practical applications. To solve this problem, we propose a base-N fixed length encoding based PriBET protocol using SwHE in the same semi-honest model. Here we did our experiments for finding the equalities of 8–64-bit integers. Furthermore, our experiments show that our protocol is able to evaluate more than one million (resp. 862 thousand) of equality comparisons per minute for 8-bit (resp. 16-bit) integers with an encoding size of base 256 (resp. 65536). Besides, our protocol works more than 8–20 in magnitude than that of Saha and Koshiba.

    DOI

  • Secure non-transferable proxy re-encryption for group membership and non-membership

    Ei Mon Cho, Lwin San, Takeshi Koshiba

    Lecture Notes on Data Engineering and Communications Technologies (TwCSec@NBiS 2017)   7   876 - 887  2017.08  [Refereed]

    DOI

  • Function secret sharing using Fourier basis

    Takuya Ohsawa, Naruhiro Kurokawa, Takeshi Koshiba

    Lecture Notes on Data Engineering and Communications Technologies (TwCSec@NBiS 2017)   7   865 - 875  2017.08  [Refereed]

    DOI

  • An efficient privacy-preserving comparison protocol

    Tushar Kanti Saha, Takeshi Koshiba

    Lecture Notes on Data Engineering and Communications Technologies (NBiS 2017)   7   553 - 565  2017.08  [Refereed]

    DOI

  • Physical implementation of oblivious transfer using optical correlated randomness

    Tomohiro Ito, Hayato Koizumi, Nobumitsu Suzuki, Izumi Kakesu, Kento Iwakawa, Atsushi Uchida, Takeshi Koshiba, Jun Muramatsu, Kazuyuki Yoshimura, Masanobu Inubushi, Peter Davis

    SCIENTIFIC REPORTS   7   Article 8444 - (12 pages)  2017.08  [Refereed]

     View Summary

    We demonstrate physical implementation of information-theoretic secure oblivious transfer based on bounded observability using optical correlated randomness in semiconductor lasers driven by common random light broadcast over optical fibers. We demonstrate that the scheme can achieve one-out-of-two oblivious transfer with effective key generation rate of 110 kb/s. The results show that this scheme is a promising approach to achieve information-theoretic secure oblivious transfer over long distances for future applications of secure computation such as privacy-preserving database mining, auctions and electronic-voting.

    DOI

  • Secure SMS transmission based on verifiable hash convergent group signcryption

    Ei Mon Cho, Takeshi Koshiba

    Proceedings - 18th IEEE International Conference on Mobile Data Management, MDM 2017     332 - 335  2017.06  [Refereed]

     View Summary

    Short Message Service (SMS) is one of the most popular services in the Global System for Mobile (GSM) and many challenges for security arise from the development of message transmission among the broadband network. Recently, an interesting technique called signcryption has been proposed, in which both the properties of signature (ownership) and encryption are simultaneously implemented, with better performance than the traditional signature-then-encryption approach. For the secure mobile computing, we propose a new method for two groups of users that send encrypted signed data by using SMS. We propose a new primitive called verifiable hash convergent group signcryption (VHCGS) by adding the properties of group signcryption and the verification facilities for the third party called the service provider. This research targets toward the type of applications in mobile computing and communication device concerning about SMS.

    DOI

  • Private Equality Test Using Ring-LWE Somewhat Homomorphic Encryption

    Tushar Kanti Saha, Takeshi Koshiba

    Proceedings - Asia-Pacific World Congress on Computer Science and Engineering 2016 and Asia-Pacific World Congress on Engineering 2016, APWC on CSE/APWCE 2016     1 - 5  2017.06  [Refereed]

     View Summary

    We propose two secure protocols namely private equality test (PET) for single comparison and private batch equality test (PriBET) for batch comparisons of l-bit integers. We ensure the security of these secure protocols using somewhat homomorphic encryption (SwHE) based on ring learning with errors (ring-LWE) problem in the semi-honest model. In the PET protocol, we take two private integers input and produce the output denoting their equality or non-equality. Here the PriBET protocol is an extension of the PET protocol. So in the PriBET protocol, we take single private integer and another set of private integers as inputs and produce the output denoting whether single integer equals at least one integer in the set of integers or not. To serve this purpose, we also propose a new packing method for doing the batch equality test using few homomorphic multiplications of depth one. Here we have done our experiments at the 140-bit security level. For the lattice dimension 2048, our experiments show that the PET protocol is capable of doing any equality test of 8-bit to 2048-bit that require at most 107 milliseconds. Moreover, the PriBET protocol is capable of doing about 600 (resp., 300) equality comparisons per second for 32-bit (resp., 64-bit) integers. In addition, our experiments also show that the PriBET protocol can do more computations within the same time if the data size is smaller like 8-bit or 16-bit.

    DOI

  • Fully Secure Lattice-based Group Signatures with Verifier-local Revocation

    M. Nisansala, S. Perera, Takeshi Koshiba

    2017 IEEE 31ST INTERNATIONAL CONFERENCE ON ADVANCED INFORMATION NETWORKING AND APPLICATIONS (AINA)     795 - 802  2017  [Refereed]

     View Summary

    In PKC 2014, Langlois et al. proposed the first lattice-based group signature scheme with the verifier-local revocability. The security of their scheme is selfless anonymity, which is weaker than the security model defined by Bellare, Micciancio and Warinschi (EUROCRYPT 2003). By using the technique in the group signature scheme proposed by Ling et al. ( PKC 2015), we propose a group signature scheme with the verifier-local revocability. For the security discussion of our scheme, we adapt the BMW03 model to cope with revocation queries, since the BMW03 model is for static groups. Then, we show that our scheme achieves the full anonymity in the adapted BMW03 model.

    DOI

  • An Enhancement of Privacy-Preserving Wildcards Pattern Matching

    Tushar Kanti Saha, Takeshi Koshiba

    FOUNDATIONS AND PRACTICE OF SECURITY, FPS 2016   10128   145 - 160  2017  [Refereed]

     View Summary

    We consider secure pattern matching for some alphabet set, where gaps are represented by the character '*'. Generally, we know that a wildcard character '*' in the pattern is used to replace zero or more letters in the text. Yasuda et al. (ACISP 2014) proposed a new packing method for somewhat homomorphic encryption for handling wildcards pattern where the wildcards replace one letter in the text. We extend the secure pattern matching so that the wildcards are replaced with any sequences. We propose a method for privacy-preserving wildcards pattern matching using somewhat homomorphic encryption in the semi-honest model. At the same time, we also propose another packing method for executing homomorphic operations between plaintext and encrypted wildcards pattern in three homomorphic multiplications rather than 3k multiplications required by Yasuda et al. method to handle k sub-patterns. Moreover, we have been able to improve the communication complexity of Yasuda et al. method by a factor k denoting the total number of sub-patterns appearing in the pattern. In addition, our practical implementation shows that our method is about k-times faster than that of Yasuda et al. Here, we show some applications of our packing method to computing secure Hamming and Euclidean distances.

    DOI

  • Analysis of decreasing squared-sum of Gram-Schmidt lengths for short lattice vectors.

    Masaya Yasuda, Kazuhiro Yokoyama, Takeshi Shimoyama, Jun Kogure, Takeshi Koshiba

    J. Mathematical Cryptology   11 ( 1 ) 1 - 24  2017  [Refereed]  [International journal]

    Authorship:Last author

    DOI

  • Secure Deduplication in a Multiple Group Signature Setting

    Ei Mon Cho, Takeshi Koshiba

    2017 IEEE 31ST INTERNATIONAL CONFERENCE ON ADVANCED INFORMATION NETWORKING AND APPLICATIONS (AINA)     811 - 818  2017  [Refereed]

     View Summary

    Multiple group setting schemes have recently become important for enabling deduplication for cloud servers. We consider a new primitive, cross-group deduplication, allowing the multiple groups by the group signature features. We propose a new framework DDUP-MUG (deduplication for the multiple-group signature scheme) that allows one or more groups to access a file such that the cloud storage server can avoid duplicates according to the ownership of the file. The main goal of the primitive is allowing to multiple groups with individual management and several clients from different groups who attempt to store an identical message on the server. In this paper, the group managers mainly manage the new entities and produce revocation lists for clients and the server respectively. We use Message Lock Encryption (MLE) as an ingredient for deduplication and we provide new three protocols, namely UPL-Dup (for uploading a new message), EDT-Dup (for editing the existing message) and DEL-Dup (for eliminating the existing message) in the DDUP-MUG framework.

    DOI

  • Private conjunctive query over encrypted data

    Tushar Kanti Saha, Takeshi Koshiba

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   10239   149 - 164  2017  [Refereed]

     View Summary

    In this paper, we propose an efficient protocol to process a private conjunctive query over encrypted data in the cloud using the somewhat homomorphic encryption (SwHE) scheme with a batch technique. In 2016, Cheon, Kim, and Kim (CKK) [IEEE Trans. Inf. Forensics Security] showed conjunctive query processing over encrypted data using search-and-compute circuits and an SwHE scheme and mentioned that their scheme should be improved in performance. To improve the performance of processing a private conjunctive query, we also propose a new packing method to support an efficient batch computation for our protocol using a few multiplications. Our implementation shows that our protocol works more than 50 times as fast as the CKK protocol for conjunctive query processing. In addition, the security level of our protocol is better than the security level of the CKK protocol.

    DOI

  • Big Data Cloud Deduplication based on Verifiable Hash Convergent Group Signcryption

    Ei Mon Cho, Takeshi Koshiba

    2017 THIRD IEEE INTERNATIONAL CONFERENCE ON BIG DATA COMPUTING SERVICE AND APPLICATIONS (IEEE BIGDATASERVICE 2017)     265 - 270  2017  [Refereed]

     View Summary

    As Big Data cloud storage servers are becoming popular the shortage of disk space in the cloud becomes a problem. Data deduplication is a method to control the explosion growth of data on the cloud and most of the storage providers are finding more secure and efficient methods for their sensitive data. Recently, an interesting technique called signcryption has been proposed, in which both the properties of signature (ownership) and encryption are simultaneously implemented, with better performance than the traditional signature-then-encryption approach. According to the deduplication, we introduce a new method for a group of users that can eliminate redundant encrypted data owned by different users. Furthermore, we generate the tag which will be the key component of big data management. We propose a new primitive group signcryption for deduplication called verifiable hash convergent group signcryption (VHCGS) by adding the properties of group signcryption and the verification facilities for the storage server (third party).

    DOI

  • Efficient protocols for private database queries

    Tushar Kanti Saha, Mayank, Takeshi Koshiba

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   10359   337 - 348  2017  [Refereed]

     View Summary

    We consider the problem of processing private database queries over encrypted data in the cloud. To do this, we propose a protocol for conjunctive query and another for disjunctive query processing using somewhat homomorphic encryption in the semi-honest model. In 2016, Kim et al. [IEEE Trans. on Dependable and Secure Comput.] showed an FHE-based query processing with equality conditions over encrypted data. We improve the performance of processing private conjunctive and disjunctive queries with the low-depth equality circuits than Kim et al.’s circuits. To get the low-depth circuits, we modify the packing methods of Saha and Koshiba [APWConCSE 2016] to support an efficient batch computation for our protocols with a few multiplications. Our implementation shows that our protocols work faster than Kim et al.’s protocols for both conjunctive and disjunctive query processing along with a better security level. We are also able to provide security to both attributes and values appeared in the predicate of the conjunctive and disjunctive queries whereas Kim et al. provided the security to the values only.

    DOI

  • Privacy-Preserving Fuzzy Commitment for Biometrics via Layered Error-Correcting Codes

    Masaya Yasuda, Takeshi Shimoyama, Narishige Abe, Shigefumi Yamada, Takashi Shinzaki, Takeshi Koshiba

    FOUNDATIONS AND PRACTICE OF SECURITY (FPS 2015)   9482   117 - 133  2016  [Refereed]

     View Summary

    With the widespread development of biometrics, concerns about security and privacy are increasing. In biometrics, template protection technology aims to protect the confidentiality of biometric templates (i.e., enrolled biometric data) by certain conversion. The fuzzy commitment scheme gives a practical way to protect biometric templates using a conventional error-correcting code. The scheme has both concealing and binding of templates, but it has some privacy problems. Specifically, in case of successful matching, stored biometric templates can be revealed. To address such problems, we improve the scheme. Our improvement is to coat with two error-correcting codes. In particular, our scheme can conceal stored biometric templates even in successful matching. Our improved scheme requires just conventional error-correcting codes as in the original scheme, and hence it gives a practical solution for both template security and privacy of biometric templates.

    DOI

  • Secure Data Devolution: Practical Re-encryption with Auxiliary Data in LWE-based Somewhat Homomorphic Encryption.

    Masaya Yasuda, Takeshi Koshiba, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama

    Proceedings of the 3rd ACM International Workshop on Security in Cloud Computing, SCC 2015     53 - 61  2015  [Refereed]

    DOI

  • New packing method in somewhat homomorphic encryption and its applications.

    Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba

    Security and Communication Networks   8 ( 13 ) 2194 - 2213  2015  [Refereed]  [International journal]

    Authorship:Last author

    DOI

  • Secure Statistical Analysis Using RLWE-Based Homomorphic Encryption.

    Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba

    Lecture Notes in Computer Science (ACISP 2015)   9144   471 - 487  2015  [Refereed]

    DOI

  • Practical Packing Method in Somewhat Homomorphic Encryption

    Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba

    DATA PRIVACY MANAGEMENT AND AUTONOMOUS SPONTANEOUS SECURITY, DPM 2013   8247   34 - 50  2014  [Refereed]

     View Summary

    Somewhat homomorphic encryption is public key encryption supporting a limited number of both additions and multiplications on encrypted data, which is useful for performing fundamental computations with protecting the data confidentiality. In this paper, we focus on the scheme proposed by Lauter, Naehrig and Vaikuntanathan (ACM CCSW 2011), and present two types of packed ciphertexts based on their packing technique. Combinations of two types of our packing method give practical size and performance for wider computations such as statistical analysis and distances. To demonstrate its efficiency, we implemented the scheme with our packing method for secure Hamming distance, which is often used in privacy-preserving biometrics. For secure Hamming distance between two binary vekoshiba@mail.saitama-u.ac.jpctors of 2048-bit, it takes 5.31ms on an Intel Xeon X3480 at 3.07 GHz. This gives the best performance in the state-of-the-art work using homomorphic encryption.

    DOI

  • Privacy-Preserving Wildcards Pattern Matching Using Symmetric Somewhat Homomorphic Encryption

    Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba

    INFORMATION SECURITY AND PRIVACY, ACISP 2014   8544   338 - 353  2014  [Refereed]

     View Summary

    The basic pattern matching problem is to find the locations where a pattern occurs in a text. We give several computations enabling a client to obtain matching results from a database so that the database can not learn any information about client's queried pattern. For such computations, we apply the symmetric-key variant scheme of somewhat homomorphic encryption proposed by Brakerski and Vaikuntanathan (CRYPTO 2011), which can support a limited number of both polynomial additions and multiplications on encrypted data. We also utilize the packing method introduced by Yasuda et al. (CCSW 2013) for efficiency. While they deal with only basic problems for binary vectors, we address more complex problems such as the approximate and wildcards pattern matching for non-binary vectors. To demonstrate the efficiency of our method, we implemented the encryption scheme for secure wildcards pattern matching of DNA sequences. Our implementation shows that a client can privately search real-world genomes of length 16,500 in under one second on a general-purpose PC.

    DOI

  • On the exact decryption range for Gentry-Halevi's implementation of fully homomorphic encryption.

    Masaya Yasuda, Kazuhiro Yokoyama, Takeshi Shimoyama, Jun Kogure, Takeshi Koshiba

    J. Mathematical Cryptology   8 ( 3 ) 305 - 329  2014  [Refereed]  [International journal]

    Authorship:Last author

    DOI

  • Ancilla-driven universal blind quantum computation

    Takahiro Sueki, Takeshi Koshiba, Tomoyuki Morimae

    PHYSICAL REVIEW A   87 ( 6 ) Article 060301(R) - (5 pages)  2013.06  [Refereed]  [International journal]

     View Summary

    Blind quantum computation is a new quantum secure protocol, which enables Alice who does not have enough quantum technology to delegate her computation to Bob who has a fully fledged quantum power without revealing her input, output, and algorithm. So far, blind quantum computation has been considered only for the circuit model and the measurement-based model. Here we consider the possibility and the limitation of blind quantum computation in the ancilla-driven model, which is a hybrid of the circuit and the measurement-based models.

    DOI

  • Secure pattern matching using somewhat homomorphic encryption.

    Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba

    Proceedings of the ACM Conference on Computer and Communications Security (2013 ACM Cloud Computing Security Workshop, CCSW 2013)     65 - 76  2013  [Refereed]

    DOI

  • Packed Homomorphic Encryption Based on Ideal Lattices and Its Application to Biometrics.

    Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba

    Lecture Notes in Computer Science (MoCrySEn 2013)   8128   55 - 74  2013  [Refereed]

    DOI

  • Computational Indistinguishability Between Quantum States and Its Cryptographic Application

    Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura, Tomoyuki Yamakami

    JOURNAL OF CRYPTOLOGY   25 ( 3 ) 528 - 555  2012.07  [Refereed]  [International journal]

     View Summary

    We introduce a computational problem of distinguishing between two specific quantum states as a new cryptographic problem to design a quantum cryptographic scheme that is "secure" against any polynomial-time quantum adversary. Our problem, QSCD(ff), is to distinguish between two types of random coset states with a hidden permutation over the symmetric group of finite degree. This naturally generalizes the commonly-used distinction problem between two probability distributions in computational cryptography. As our major contribution, we show that QSCD(ff) has three properties of cryptographic interest: (i) QSCD(ff) has a trapdoor; (ii) the average-case hardness of QSCD(ff) coincides with its worst-case hardness; and (iii) QSCD(ff) is computationally at least as hard as the graph automorphism problem in the worst case. These cryptographic properties enable us to construct a quantum public-key cryptosystem which is likely to withstand any chosen plaintext attack of a polynomial-time quantum adversary. We further discuss a generalization of QSCD(ff), called QSCD(cyc), and introduce a multi-bit encryption scheme that relies on similar cryptographic properties of QSCD(cyc).

    DOI

  • Public Discussion Must Be Back and Forth in Secure Message Transmission

    Takeshi Koshiba, Shinya Sawada

    INFORMATION SECURITY AND CRYPTOLOGY - ICISC 2010   6829   325 - 337  2011  [Refereed]

     View Summary

    Secure message transmission (SMT) is a two-party protocol between a sender and a receiver over a network in which the sender and the receiver are connected by 71 disjoint channels and t out of n channels can be controlled by an adaptive adversary with unlimited computational resources. If a public discussion channel is available to the sender and the receiver to communicate with each other then a secure and reliable communication is possible even when n &gt;= t + 1. The round complexity is one of the important measures for the efficiency for SMT. In this paper, we revisit the optimality and the impossibility for SMT with public discussion and discuss the limitation of SMT with the "unidirectional" public channel, where either the sender or the receiver can invoke the public channel, and show that the "bidirectional" public channel is necessary for SMT.

    DOI

  • Statistically-Hiding Quantum Bit Commitment from Approximable-Preimage-Size Quantum One-Way Function

    Takeshi Koshiba, Takanori Odaira

    THEORY OF QUANTUM COMPUTATION, COMMUNICATION, AND CRYPTOGRAPHY   5905   33 - 46  2009  [Refereed]

     View Summary

    We provide a quantum bit commitment scheme which has statistically-hiding and computationally-binding properties from any approximable-preimage-size quantum one-way function, which is a generalization of perfectly-hiding quantum bit commitment scheme based on quantum one-way permutation due to Dumais, Mayers and Salvail. in the classical case, statistically-hiding bit commitment scheme is constructible from any one-way function. However, it is known that the round complexity of the classical statistically-hiding bit commitment scheme is Omega(n/ log n) for the security parameter n. Our quantum scheme as well as the Dumais-Mayers-Salvail scheme is non-interactive, which is advantageous over the classical schemes.

    DOI

  • Strengthening the Security of Distributed Oblivious Transfer

    K. Y. Cheong, Takeshi Koshiba, Shohei Nishiyama

    INFORMATION SECURITY AND PRIVACY, PROCEEDINGS   5594   377 - 388  2009  [Refereed]

     View Summary

    We study the distributed oblivious transfer first proposed by Naor and Pinkas in ASIACRYPT 2000, and generalized by Blundo et al. originally in SAC 2002 and Nikov et al. in INDOCRYPT 2002. One major objective of distributed oblivious transfer is to achieve information theoretic security under specified conditions through the distribution of the functions of traditional oblivious transfer to a set of neutral parties. In this paper we revise the definition of distributed oblivious transfer in order to deal with stronger adversaries and clarify possible ambiguities. Under the new definition, we observe some impossibility results and derive the tipper bounds for the system parameters (with respect to the size of coalition). The weak points of previously proposed schemes based on threshold secret sharing schemes using polynomial interpolation are reviewed and resolved. We generalize the results and prove that, by adjusting some technical details, a previous scheme proposed by Nikov et al. is unconditionally secure. This protocol is efficient and achieves the parameter bounds at the same time.

    DOI

  • Reducing Complexity Assumptions for Oblivious Transfer

    K. Y. Cheong, Takeshi Koshiba

    ADVANCES IN INFORMATION AND COMPUTER SECURITY, PROCEEDINGS   5824   110 - 124  2009  [Refereed]

     View Summary

    Reducing the minimum assumptions needed to construct various cryptographic primitives is an important and interesting task in theoretical cryptography Oblivious transfer, one of the most basic cryptographic building blocks, could be also studied under this scenario. Reducing the minimum assumptions for oblivious transfer seems not an easy task, as there are a few impossibility results under black-box reductions
    Until recently, it is widely believed that oblivious transfer Can he constructed with trapdoor permutations Goldrech pointed out some flaw in the folklore and introduced some enhancement to cope with the flaw Haitner then revised the enhancement more properly. As a consequence they showed that some additional properties for trapdoor permutations are necessary to construct oblivious transfers In this paper, we discuss possibilities of basing not on trapdoor permutations but on trapdoor functions in general We generalize previous results and give an oblivious transfer protocol based on a collection of trapdoor functions with some extra properties with respect to the length-expansion and the pre- image size. We discuss that our reduced assumption is almost minimal and show the necessity for the extra properties.

    DOI

  • A combinatorial approach to deriving lower bounds for perfectly secure oblivious transfer reductions

    Kaoru Kurosawa, Wataru Kishimoto, Takeshi Koshiba

    IEEE Transactions on Information Theory   54 ( 6 ) 2566 - 2571  2008.06  [Refereed]  [International journal]

    Authorship:Last author

     View Summary

    Consider the scenario where we are given an ideal functionality of oblivious transfer (OT), and we wish to construct a larger OT by invoking the above functionality as a black box. How many invocations of an ideal OT functionality are necessary? In tackling this problem, some lower bounds were derived using entropy previously. In this paper, we manage to achieve tighter lower bounds by employing a combinatorial approach. This new approach yields lower bounds which are two times larger than the existing bounds. © 2008 IEEE.

    DOI

  • Simple direct reduction of string (1,2)-OT to Rabin's OT without privacy, amplification

    Kaoru Kurosawa, Takeshi Koshiba

    INFORMATION THEORETIC SECURITY, PROCEEDINGS   5155   199 - +  2008  [Refereed]

     View Summary

    It is known that string (1, 2)-OT and Rabin's OT are equivalent. Actually, there have been many reductions between them. Many of them use the privacy amplification technique as a basic tool. The privacy amplification technique essentially involves some post-processing of sending random objects (e.g., random indices of pairwise independent hash functions) per each invocation of Rabin's OT is necessary. In this paper, we show a simple direct reduction of string (1, 2)-OT to Rabin's OT by using a deterministic randomness extractor for bit-fixing sources. Our reduction can be realized without privacy amplification and thus our protocol is simpler and more efficient with respect to the communication complexity than the previous reductions.

    DOI

  • More on security of public-key cryptosystems based on Chebyshev polynomials

    Kai Y. Cheong, Takeshi Koshiba

    IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS   54 ( 9 ) 795 - 799  2007.09  [Refereed]  [International journal]

    Authorship:Last author

     View Summary

    Recently, a public-key cryptosystem based on Cheby-shev polynomials has been proposed, but it has been later analyzed and shown insecure. This paper addresses some unanswered questions about the cryptosystem. We deal with the issue of computational precision. This is important for two reasons. Firstly, the cryptosystem is defined on. real numbers, but any practical data communication channel can only transmit a limited number of digits. Any real number can only be specified to some precision level, and we study the effect of that. Secondly, we show that the precision issue is related to its security. In particular, the algorithm previously proposed to break the cryptosystem may not work in some situations. Moreover, we introduce another method to break the cryptosystem with general precision settings. We extend the method to show that a certain class of cryptosystems is insecure. Our method is based on the known techniques on the shortest vector problem in lattice and linear congruences.

    DOI

  • Low-density attack revisited

    Tetsuya Izu, Jun Kogure, Takeshi Koshiba, Takeshi Shimoyama

    DESIGNS CODES AND CRYPTOGRAPHY   43 ( 1 ) 47 - 59  2007.04  [Refereed]  [International journal]

     View Summary

    The low-density attack proposed by Lagarias and Odlyzko is a powerful algorithm against the subset sum problem. The improvement algorithm due to Coster et al. would solve almost all the problems of density < 0.9408... in the asymptotical sense. On the other hand, the subset sum problem itself is known as an NP-hard problem, and a lot of efforts have been paid to establish public-key cryptosystems based on the problem. In these cryptosystems, densities of the subset sum problems should be higher than 0.9408... in order to avoid the low-density attack. For example, the Chor-Rivest cryptosystem adopted subset sum problems with relatively high densities. In this paper, we further improve the low-density attack by incorporating an idea that integral lattice points can be covered with polynomially many spheres of shorter radius and of lower dimension. As a result, the success probability of our attack can be higher than that of Coster et al.'s attack for fixed dimensions. The density bound is also improved for fixed dimensions. Moreover, we numerically show that our improved low-density attack makes the success probability higher in case of low Hamming weight solution, such as the Chor-Rivest cryptosystem, if we assume SVP oracle calls.

    DOI

  • Progress in quantum computational cryptography

    Akinori Kawachi, Takeshi Koshiba

    JOURNAL OF UNIVERSAL COMPUTER SCIENCE   12 ( 6 ) 691 - 709  2006  [Refereed]  [Invited]

     View Summary

    Shor's algorithms for the integer factorization and the discrete logarithm problems can be regarded as a negative effect of the quantum mechanism on public-key cryptography. From the computational point of view, his algorithms illustrate that quantum computation could be more powerful. It is natural to consider that the power of quantum computation could be exploited to withstand even quantum adversaries. Over the last decade, quantum cryptography has been discussed and developed even from the computational complexity-theoretic point of view. In this paper, we will survey what has been studied in quantum computational cryptography.

  • Universal test for quantum one-way permutations

    A Kawachi, H Kobayashi, T Koshiba, RH Putra

    THEORETICAL COMPUTER SCIENCE   345 ( 2-3 ) 370 - 385  2005.11  [Refereed]

     View Summary

    The next bit test was introduced by Blum and Micali and proved by Yao to be a universal test for cryptographic pseudorandom generators. On the other hand, no universal test for the cryptographic one-wayness of functions (or permutations) is known, although the existence of cryptographic pseudorandom generators is equivalent to that of cryptographic one-way functions. In the quantum computation model, Kashefi, Nishimura and Vedral gave a sufficient condition of (cryptographic) quantum one-way permutations and conjectured that the condition would be necessary. In this paper, we affirmatively settle their conjecture and complete a necessary and sufficient condition for quantum one-way permutations. The necessary and sufficient condition can be regarded as a universal test for quantum one-way permutations, since the condition is described as a collection of stepwise tests similar to the next bit test for pseudorandom generators. (c) 2005 Published by Elsevier B.V.

    DOI

  • Computational indistinguishability between quantum states and its cryptographic application

    A Kawachi, T Koshiba, H Nishimura, T Yamakami

    ADVANCES IN CRYPTOLOGY - EUROCRYPT 2005,PROCEEDINGS   3494   268 - 284  2005  [Refereed]

     View Summary

    We introduce a problem of distinguishing between two quantum states as a new underlying problem to build a computational cryptographic scheme that is "secure" against quantum adversary. Our problem is a natural generalization of the distinguishability problem between two probability distributions, which are commonly used in computational cryptography. More precisely, our problem QSCD(ff) is the computational distinguishability problem between two types of random coset states with a hidden permutation over the symmetric group. We show that (i) QSCD(ff) has the trapdoor property; (ii) the average-case hardness of QSCD(ff) coincides with its worst-case hardness; and (iii) QSCD(ff) is at least as hard in the worst case as the graph automorphism problem. Moreover, we show that QSCD(ff) cannot be efficiently solved by any quantum algorithm that naturally extends Shor's factorization algorithm. These cryptographic properties of QSCD(ff) enable us to construct a public-key cryptosystem, which is likely to withstand any attack of a polynomial-time quantum adversary.

    DOI

  • Theoretical analysis of (2)(X) attack on RC6

    M Takenaka, T Shimoyama, T Koshiba

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES   E87A ( 1 ) 28 - 36  2004.01  [Refereed]

     View Summary

    In this paper, we give a theoretical analysis of chi(2) attack proposed by Knudsen and Meier on the RC6 block cipher. To this end, we propose a method of security evaluation against chi(2) attack precisely including key dependency by introducing a method "Transition Matrix Computing." Previously, no theoretical security evaluation against chi(2) attack was known, it has been done by computer experiments. We should note that it is the first result concerning the way of security evaluation against chi(2) attack is shown theoretically.

  • Universal test for quantum one-way permutations

    A Kawachi, H Kobayashi, T Koshiba, RH Putra

    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2004, PROCEEDINGS   3153   839 - 850  2004  [Refereed]

     View Summary

    The next bit test was introduced by Blum and Micali and proved by Yao to be a universal test for cryptographic pseudorandom generators. On the other hand, no universal test for the cryptographic one-wayness of functions (or permutations) is known, though the existence of cryptographic pseudorandom generators is equivalent to that of cryptographic one-way functions. In the quantum computation model, Kashefi, Nishimura and Vedral gave a sufficient condition of (cryptographic) quantum one-way permutations and conjectured that the condition would be necessary. In this paper, we relax their sufficient condition and give a new condition that is necessary and sufficient for quantum one-way permutations. Our condition can be regarded as a universal test for quantum one-way permutations, since our condition is described as a collection of stepwise tests similar to the next bit test for pseudorandom generators.

    DOI

  • Short exponent Diffie-Hellman problems

    T Koshiba, K Kurosawa

    PUBLIC KEY CRYPTOGRAPHY - PKC 2004, PROCEEDINGS   2947   173 - 186  2004  [Refereed]

     View Summary

    In this paper, we study short exponent Diffie-Hellman problems, where significantly many lower bits are zeros in the exponent. We first prove that the decisional version of this problem is as hard as two well known hard problems, the standard decisional Diffie-Hellman problem (DDH) and the short exponent discrete logarithm problem. It implies that we can improve the efficiency of ElGamal scheme and Cramer-Shoup scheme under the two widely accepted assumptions. We next derive a similar result for the computational version of this problem.

    DOI

  • Theoretical analysis of x(2) attack on RC6

    M Takenaka, T Shimoyama, T Koshiba

    INFORMATION SECURITY AND PRIVACY, PROCEEDINGS   2727   142 - 153  2003  [Refereed]

     View Summary

    In this paper, we give a theoretical analysis Of chi(2) attack proposed by Knudsen and Meier on the RC6 block cipher. To this end, we propose the method of security evaluation against chi(2) attack precisely including key dependency by introducing a method "Transition Matrix Computing." Previously, no theoretical security evaluation against chi(2) attack was known, it has been done by computer experiments. We should note that this is the first results that a theoretical evaluation against chi(2) attack is shown.

    DOI

  • Multiple linear cryptanalysis of a reduced round RC6

    T Shimoyama, M Takenaka, T Koshiba

    FAST SOFTWARE ENCRYPTION (REVISED PAPERS)   2365   76 - 88  2002  [Refereed]

     View Summary

    In this paper, we apply multiple linear cryptanalysis to a reduced round RC6 block cipher. We show that 18-round RC6 with weak key is breakable by using the multiple linear attack.

    DOI

  • On sufficient randomness for secure public-key cryptosystems

    Takeshi Koshiba

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   2274   34 - 47  2002  [Refereed]

     View Summary

    In this paper, we consider what condition is sufficient for random inputs to secure probabilistic public-key encryption schemes. Although a framework given in [16] enables us to discuss uniformly and comprehensively security notions of public-key encryption schemes even for the case where cryptographically weak pseudorandom generator is used as random nonce generator to encrypt single plaintext messages, the results are rather theoretical. Here we naturally generalize the framework in order to handle security for the situation where we want to encrypt many messages with the same key. We extend some results w.r.t. single message security in [16] – separation results between security notions and a non-trivial sufficient condition for the equivalence between security notions – to multiple messages security. Besides the generalization, we show another separation between security notions for k-tuple messages and for (k+1)-tuple messages. The natural generalization, obtained here, rather improves to understand the security of public-key encryption schemes and eases the discussion of the security of practical public-key encryption schemes. In other words, the framework contributes to elucidating the role of randomness in public-key encryption scheme. As application of results in the generalized framework, we consider compatibility between the ElGamal encryption scheme and some sequence generators. Especially, we consider the applicability of the linear congruential generator (LCG) to the ElGamal encryption scheme.

    DOI

  • The Decision Diffie-Hellman assumption and the Quadratic Residuosity assumption

    T Saito, T Koshiba, A Yamamura

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES   E84A ( 1 ) 165 - 171  2001.01  [Refereed]

     View Summary

    This paper examines similarities between the Decision Diffie-Hellman (DDH) assumption and the Quadratic Residuosity (QR) assumption. In addition, we show that many cryptographic protocols based on the QR assumption can be reconstructed using the DDH assumption.

  • A new aspect for security notions: Secure randomness in public-key encryption schemes

    T Koshiba

    PUBLIC KEY CRYPTOGRAPHY, PROCEEDINGS   1992   87 - 103  2001  [Refereed]

     View Summary

    In this paper, we introduce a framework in which we can uniformly and comprehensively discuss security notions of public-key encryption schemes even for the case where some weak generator producing seemingly random sequences is used to encrypt plaintext messages. First, we prove that indistinguishability and semantic security are not equivalent in general. On the other hand, we derive some sufficient condition for the equivalence and show that polynomial-time pseudo-randomness is not always necessary for the equivalence.

    DOI

  • Polynomial-time algorithms for the equivalence for one-way quantum finite automata

    T Koshiba

    ALGORITHMS AND COMPUTATION, PROCEEDINGS   2223   268 - 278  2001  [Refereed]

     View Summary

    Two quantum finite automata are equivalent if for any string x the two automata accept x with equal probability. This paper gives a polynomial-time algorithm for determining whether two measure-once one-way quantum finite automata are equivalent. The paper also gives a polynomial-time algorithm for determining whether two measure-many one-way quantum finite automata are equivalent.

    DOI

  • A theory of randomness for public key cryptosystems: The ElGamal cryptosystem case

    T Koshiba

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES   E83A ( 4 ) 614 - 619  2000.04  [Refereed]

     View Summary

    There are many public key cryptosystems that require random inputs to encrypt messages and their security is always discussed assuming that random objects are ideally generated. Since cryptosystems run on computers, it is quite natural that these random objects are computationally generated. One theoretical solution is the use of pseudorandom generators in the Yao's sense [16]. Informally saying, the pseudorandom generators are polynomial-time algorithms whose outputs are computationally indistinguishable from the uniform distribution. Since if we use the Yao's generators then it takes much more time to generate pseudorandom objects than to encrypt messages in public key cryptosystems, we relax the conditions of pseudorandom generators to fit public key cryptosystems and give a minimal requirement for pseudorandom generators within public key cryptosystems. As an example, we discuss the security of the El-Gamal cryptosystem [7] with some well-known generators (e.g., the linear congruential generator). We also propose a new pseudorandom number generator, for random inputs to the ElGamal cryptosystem, that satisfies the minimal requirement. The newly proposed generator is based on the linear congruential generator. We show some evidence that the ElGamal cryptosystem with the proposed generator is secure.

  • A technique for boosting the security of cryptographic systems with one-way hash functions

    T Koshiba

    INFORMATION SECURITY AND CRYPTOLOGY - ICISC'99   1787   76 - 81  2000  [Refereed]

     View Summary

    In this paper, we show a practical solution to the problems where one-wayness of hash functions does not guarantee cryptographic systems to be secure enough. We strengthen the notion of one-wayness of hash functions and construct strongly one-way hash functions from any one-way hash function or any one-way function.

    DOI

  • Inferring pure context-free languages from positive data

    Takeshi Koshiba, Erkki Mäkinen, Yuji Takada

    Acta Cybernetica   14 ( 3 ) 469 - 477  2000  [Refereed]  [International journal]  [International coauthorship]

    Authorship:Lead author, Corresponding author

  • Enhancing D-ABDUCTOR towards a diagrammatic user interface platform

    K Misue, K Nitta, K Sugiyama, T Koshiba, R Inder

    1998 SECOND INTERNATIONAL CONFERENCE ON KNOWLEDGE-BASED INTELLIGENT ELECTRONIC SYSTEMS, KES'98 PROCEEDINGS, VOL 1     359 - 368  1998  [Refereed]

     View Summary

    The D-ABDUCTOR system was originally developed as a diagram-based idea organizer with facilities for visualization and manipulation of a large class of graphs. It has since been enhanced to improve its extensibility, and now function exchange-ability, functional independence, and configurability without programming have become important features. The enhanced system and its features are illustrated with several examples of its application.

    DOI

  • Learning deterministic even linear languages from positive examples

    T Koshiba, E Makinen, Y Takada

    THEORETICAL COMPUTER SCIENCE   185 ( 1 ) 63 - 79  1997.10  [Refereed]  [International journal]  [International coauthorship]

    Authorship:Lead author, Corresponding author

     View Summary

    We consider the problem of learning deterministic even linear languages from positive examples, We show that, for any nonnegative integer k, the class of LR(k) even linear languages is not learnable from positive examples while there is a subclass called LRS(k), which is a natural subclass of LR(k) in the strong sense, learnable from positive examples. Our learning algorithm identifies this subclass in the limit with almost linear time in updating conjectures. As a corollary, in terms of even linear grammars, we have a learning algorithm for k-reversible languages that is more efficient than the one proposed by Angluin.

    DOI

  • On a hierarchy of slender languages based on control sets

    Takeshi Koshiba

    Fundamenta Informaticae   31 ( 1 ) 41 - 47  1997  [Refereed]  [International journal]

    Authorship:Lead author, Corresponding author

    DOI

  • Computational learning theoretic cryptanalysis of language theoretic cryptosystems

    Takeshi Koshiba

    Lecture Notes in Computer Science (ICICS 1997)   1334   28 - 38  1997  [Refereed]

    DOI

  • A machine learning approach to knowledge acquisitions from text databases

    Y Sakakibara, K Misue, T Koshiba

    INTERNATIONAL JOURNAL OF HUMAN-COMPUTER INTERACTION   8 ( 3 ) 309 - 324  1996.07  [Refereed]  [International journal]

     View Summary

    The rapid growth of data in large databases, such as text databases and scientific databases, requires efficient computer methods for automating analyses of the data with the goal of acquiring knowledges or making discoveries. Because the analyses of data are generally so expensive, most parts in databases remains as raw, unanalyzed primary data. Technology from machine learning (ML) will offer efficient tools for the intelligent analyses of the data using generalization ability. Generalization is an important ability specific to inductive learning that will predict unseen data with high accuracy based on learned concepts from training examples.
    In this article, we apply ML to text-database analyses and knowledge acquisitions from text databases. We propose a completely new approach to the problem of text classification and extracting keywords by using ML techniques. We introduce a class of representations for classifying text data based on decision trees; (i.e., decision trees over attributes on strings) and present an algorithm for learning them inductively. Our algorithm has the following features: It does not need any natural language processing technique and it is robust for noisy data. We show that our learning algorithm can be used for automatic extraction of keywords for text retrieval and automatic text categorization. We also demonstrate some experimental results using our algorithm on the problem of classifying bibliographic data and extracting keywords in order to show the effectiveness of our approach.

    DOI

  • Decision tree learning system with switching evaluator

    Takesih Koshiba

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   1081   349 - 361  1996  [Refereed]

     View Summary

    In this paper, we introduce the notion of the local strategy of constructing decision trees that includes the information theoretic entropy algorithm in ID3 (or C4.5) and any other local algorithms. Simply put, given a sample, a local algorithm constructs a decision tree in the top-down manner using an evaluation function. We propose a new local algorithm that is very different from the entropy algorithm. We analyze behaviors of the two algorithms on a simple model. Based on these analyses, we propose a learning system of decision trees which can change an evaluation function while constructing decision trees, and verify the effect of the system by experiments with real databases. The system not only achieves a high accuracy, but also produces well-balanced decision trees, which have the advantage of fast classification.

    DOI

  • Typed pattern languages and their learnability

    Takeshi Koshiba

    Lecture Notes in Computer Science (EUROCOLT 1995)   904   367 - 379  1995  [Refereed]

    DOI

  • TEXT CLASSIFICATION AND KEYWORD EXTRACTION BY LEARNING DECISION TREES

    Y SAKAKIBARA, K MISUE, T KOSHIBA

    NINTH CONFERENCE ON ARTIFICIAL INTELLIGENCE FOR APPLICATIONS : PROCEEDINGS     466 - 466  1993  [Refereed]

▼display all

Books and Other Publications

  • Statistical Trend Analysis of Physically Unclonable Functions: An Approach via Text Mining

    Behrouz Zolfaghari, Khodakhast Bibak, Takeshi Koshiba, Hamid R. Nemati, Pinaki Mitra( Part: Joint author)

    CRC Press  2021.02 ISBN: 036775455X

  • 観測に基づく量子計算

    小柴健史, 藤井啓祐, 森前智行

    コロナ社  2017.02 ISBN: 9784339028706

  • 乱数生成と計算量理論

    小柴健史

    岩波書店  2014.11 ISBN: 9784000069755

  • 確率と計算 ―乱択アルゴリズムと確率的解析―

    Michael Mitzenmacher, Eli Upfal, 小柴健史, 河内亮周( Part: Joint translator)

    共立出版  2009.04 ISBN: 4320122291

     View Summary

    高度な理論が必要な確率的検査証明の概念からパソコンのイーサネットカードの実設計まで,ランダム性と確率的手法は現代の計算機科学において主要な役割を果たしている。特にここ20年,確率論を計算機科学に導入する事例が急増している。そして計算機科学を広範かつより複雑な応用に適用できるように,より高度でより洗練された確率的技法が開発されてきている。そのような状況において,ネットワークアルゴリズム理論分野の第一級の研究者であるMichael Mitzenmacher とEli Upfal によって“Probability and Computing”が書き上げられた。本書はその邦訳版である。本書は,計算機科学に関連するランダム性の基本的手法である乱択アルゴリズムやアルゴリズムの確率的解析について詳しく解説している。

    ASIN

  • 量子暗号理論の展開

    小芦雅斗, 小柴健史

    サイエンス社  2008.11

     View Summary

    臨時別冊・数理科学 SGCライブラリ67
    第1章 量子鍵配送の基本プロトコル
    第2章 量子鍵配送の安全性とエンタングルメント
    第3章 量子鍵配送の安全性と相補性
    第4章 量子公開鍵暗号
    第5章 量子公開鍵暗号の安全性
    第6章 量子デジタル署名

Misc

  • 物理乱数生成の理論的側面

    小柴健史

    電子情報通信学会誌     1072 - 1076  2011.12  [Invited]

    Article, review, commentary, editorial, etc. (other)  

  • 暗号論的擬似乱数

    小柴健史

    数理科学   519   21 - 25  2006.09

  • Quantum Computational Cryptography

    Akinori Kawachi, Takeshi Koshiba

    H. Imai, M. Hayashi, eds., Quantum Computation and Information From Theory to Experiment (Topics in Applied Physics 102)     167 - 184  2006.07

    Article, review, commentary, editorial, etc. (other)  

    DOI

  • 量子コンピュータは公開鍵暗号にとって脅威なのか?

    小柴健史

    情報処理   47 ( 2 ) 159 - 168  2006.02

     View Summary

    量子コンピュータが実現すると素因数分解等を効率的に解くことができ, RSA暗号等の公開鍵暗号の解読が可能となってしまうことが知られている.量子暗号として有名な量子鍵配送プロトコルはその性質から, 公開鍵暗号にとって変わるものではない.では, 量子コンピュータが実現してしまった場合, 現在のセキュリティ基盤を支える公開鍵暗号系の技術は崩壊してしまうのであろうか?本稿では, 敵対者として量子コンピュータが存在したとしても安全性が保たれるような公開鍵暗号系の技術の最新動向について紹介する.

    CiNii

  • 現代暗号への量子アルゴリズムによる攻撃

    小柴健史

    数理科学   492   31 - 36  2004.06

Works

  • ARMADA

    小柴健史  Software 

    1987
    -
    Now

     View Summary

    NEC PC-8001mkII用ゲーム

Awards

  • Award for Outstanding Research Achievement

    2018.12   Asia Pacific Society for Computing and Information Technology  

  • Outstanding paper award

    2018.10   GameSec 2018 (Conference on the Decision and Game Theory for Security)  

  • 基礎・境界ソサイエティ編集活動感謝状

    2011.09   電子情報通信学会  

Research Projects

  • Construction of Quantum Computaional Infrastracture towards Quantum Information Society

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A)

    Project Year :

    2021.04
    -
    2026.03
     

  • Establishment of Fourier-based secure function secret sharing

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research Grant-in-Aid for Challenging Research (Exploratory)

    Project Year :

    2019.06
    -
    2022.03
     

  • Constructions for Cryptographic Primitives with Incentives

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)

    Project Year :

    2017.04
    -
    2021.03
     

  • Interpolative Expansion of Quantum Protocol Theory

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A)

    Project Year :

    2016.04
    -
    2021.03
     

  • Communication Complexity based on Blind Quantum Computation

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research Grant-in-Aid for Challenging Exploratory Research

    Project Year :

    2014.04
    -
    2017.03
     

    KOSHIBA Takeshi

     View Summary

    In order to discuss the quantum communication complexity of several problems, we propose efficient protocols for secure database search based on homomorphic encryption for comparison. In addition, we have computational experiments to verify the effectiveness of our proposals. We have a new result with respect to quantum blind computation. We devise an information-theoretic mechanism where a third-party can arbitrate between a client and a server if one party is cheating and incorporate the mechanism into quantum blind computation.

  • Exploring the Limits of Computation from the Statistical Physics

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)

    Project Year :

    2012.06
    -
    2017.03
     

    Watanabe Osamu, KABASHIMA Yoshiyuki, HUKUSHIMA Koji, Krzakala Florent, Zdeborova Lenka, Zhou Haijun

     View Summary

    We investigated computational problems studied in the statistical physics for developing a new approach in computational complexity theory. We examined a framework proposed in the statistical physics for understanding the computational hardness transition phenomena, and we discovered and mathematically proved a new type of hardness transition, which lead us to propose a new and robust framework for investigating the computational hardness transitions. This framework can be used as a new basis of discussing the security of cryptographic primitives. We also studied the structure of solutions and the number of solutions of various computational problems that have been discussed in the statistical physics, and found several fundamental properties for developing efficient algorithms for solving these problems.

  • Deepening Theory of Quantum Protocols

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A)

    Project Year :

    2012.04
    -
    2016.03
     

    KOSHIBA Takeshi

     View Summary

    We propose a generalized model of quantum interactive proof systems and show the existence of complete problems and a quantum version of Babai's collapse theorem. We construct efficient quantum algorithms for matrix multiplication of semi-rings and for finding triangles in graphs and develop their analysis to obtain their quantum distribution protocols. In ancilla-driven model where computation systems and measurement systems are separable, we show that quantum blind computation is achievable. We characterize a classical computational complexity class AWPP, which corresponds to a quantum computational complexity class BQP, by using the notion of post-selection. We give a natural reason why AWPP is the tightest upper bound of BQP and develop a quantum complexity theoretic approach to the study of AWPP.

  • Multi-user quantum network

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A)

    Project Year :

    2011.04
    -
    2016.03
     

    HAYASHI Masahito

     View Summary

    We have studied quantum communication technology on a multi-user network. Especially, we have studied the information theoretic security based on quantum communication technology because its realization is not easy for existing communication technology. The information theoretic security is usually realized by privacy amplification based on a code. We have clarified the effect by the finiteness of the length of the code while it had not been studied sufficiently. Further, we have investigated the blind computation based on quantum communication, which enables the client to ask the server the difficult computation without informing the server the knowledge of the request, whose security can be guaranteed information theoretically. We have derived the formula for guaranteeing the correctness of the computation result with a given significance level.

  • Interchangeable techniques between classical and quantum cryptography

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research Grant-in-Aid for Challenging Exploratory Research

    Project Year :

    2011
    -
    2013
     

    KOSHIBA Takeshi

     View Summary

    Quantum blind computation can be discussed in the measurement-based quantum computation model. As a special case, ancilla-driven quantum computation is defined as computation where measurements are made only on the measurement system and computation is carried on the computational system and those two system are separated. In the ancilla-driven computation model, we derive sufficient conditions for the blindness and show a bind protocol. In cryptography, the universal composability guarantees that a prococol can be used as a part of larger cryptosystems. We show that Fujii-Morimae blind computation, where only the client makes measurements, is universally composable.

  • Advances in crossover between quantum information theory and quantum computational complexity theory

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)

    Project Year :

    2009
    -
    2011
     

    KOSHIBA Takeshi, MATSUMOTO Keiji, KOBAYASHI Hirotada, TANAKA Keisuke, KAWACHI Akinori

     View Summary

    We developed useful techniques in quantum information theory and quantum computational complexity theory and applied them to interactive proof systems, cryptography, network theory and so on. With respect to quantum interactive proof systems, we investigated effects of quantum entanglements among multiple provers. Moreover, we considered the possibility of quantum communication in network coding and proposed efficient protocols. We proved the hard-core property of a function by the quantum computational complexity theory, while it had not been proved from the classical theory. Furthermore, we proposed several classical cryptographic protocols, which bring some ideas to quantum cryptography.

  • 脱量子化手法の確立と暗号理論応用

    日本学術振興会  科学研究費助成事業 挑戦的萌芽研究

    Project Year :

    2008
    -
    2010
     

    小柴 健史

     View Summary

    本研究課題では,アルゴリズム構築の新しいパラダイムとして「脱量子化手法」を確立することが目的であるが,前年度に着目した古典計算暗号技術でよく用いられているインタラクティブハッシングと呼ばれる技術とBB84量子鍵配送プロトコルで用いられているBB84量子状態との関係について,本年度はその応用研究を行った.両者の関係は量子化・脱量子化の関係にあり,まず,古典暗号理論における重要な定理の一つであるインタラクティブハッシュ定理の量子版として,非対話量子ハッシュ定理を導いた.これを応用し,量子一方向性関数に基づいて非対話形式の統計的秘匿性を持つ非対話の量子ビット委託プロトコルを構成することに成功した.古典暗号理論においては,ビット委託と紛失通信は大きく異なるプロトコルとして認識されているが,量子暗号においてはその親和性を示す状況証拠が得られていた.特に,F-束縛と呼ばれる特殊な束縛性を持つ文字列委託の存在を仮定した場合,量子紛失通信が得られることが知られており,F-束縛な文字列委託プロトコルをどのように構成すればよいのかは未解決問題のまま残されていた.量子一方向性関数に基づく非対話形式統計的秘匿ビット委託プロトコルを並列化することにより,F-束縛な文字列委託プロトコルを構成出来ることを示し,結果として,量子一方向性関数から量子紛失通信プロトコルを構成することに成功した.量子紛失通信は量子マルチパーティ計算につながると予想されるため,量子暗号理論においては量子一方向性関数の存在という妥当な仮定から高度な暗号プロトコルが構成できることを示唆するものとなっている.

  • Crossover between Quantum Information Theory and Quantum Computational Complexity Theory

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)

    Project Year :

    2006
    -
    2008
     

    KOSHIBA Takeshi, MATSUMOTO Keiji, KOBAYASHI Hirotada, KAWACHI Akinori

     View Summary

    We investigated the potential abilities of quantum information processing from the viewpoints of interactive proofs, theory of cryptography and algorithms. We showed that quantum entanglement is effective in multi-prover systems, proposed a non-interactive bit commitment scheme, and derived a limitation of quantum algorithms for the hidden subgroup problem.

▼display all

Presentations

  • Guesswork of a quantum ensemble

    Michele Dall'Arno, Francesco Buscemi, Takeshi Koshiba

    25th Annual Conference on Quantum Information Processing (QIP 2022) 

    Event date:
    2022.03
     
     
  • Non-Interactive Statistically-Hiding Quantum Bit Commitment from any Quantum One-way Function

    Takeshi Koshiba  [Invited]

    The 2nd Kyoto Workshop on Quantum Information, Computation and Foundation, QICF 2021  (Online)  the Quantum Information Unit and the Yukawa Institute for Theoretical Physics, Kyoto University

    Presentation date: 2021.09

    Event date:
    2021.09
     
     
  • Guesswork of a quantum ensemble

    Michele Dall'Arno, Francesco Buscemi, Takeshi Koshiba

    The 21st Asian Quantum Information Science Conference, AQIS 2021  (Online) 

    Presentation date: 2021.09

    Event date:
    2021.09
     
     
  • On Public Verifiability for Secure Delegated Quantum Computation

    Takeshi Koshiba  [Invited]

    The 1st Kyoto Workshop on Quantum Information, Computation, and Foundation, QICF 2020  (Online)  the Quantum Information Unit and Yukawa Institute for Theoretical Physics, Kyoto University

    Presentation date: 2020.09

    Event date:
    2020.09
     
     
  • Recent Progress in Quantum Computational Cryptography

    Takeshi Koshiba  [Invited]

    The 6th IEEE Conference on Computer Science and Data Engineering  (Melbourne) 

    Presentation date: 2019.12

  • On Public Verifiability for Secure Delegated Quantum Computation

    Takeshi Koshiba  [Invited]

    Quantum computation, post-quantum cryptography and quantum codes  (Fukuoka, Japan)  Institute for Mathematics for Industry, Kyushu University

    Presentation date: 2019.11

  • Homomorphic Encrypion and Its Applications

    Takeshi Koshiba  [Invited]

    The 2018 International Conference for Top and Emerging Computer Scientists (IC-TECS 2018)  (Taipei)  Asia Pacific Society for Computing and Information Technology

    Presentation date: 2018.12

  • 安全な代理量子計算

    小柴健史  [Invited]

    情報理論研究会「若手研究者のための講演会」@第41回情報理論とその応用シンポジウム(SITA 2018)  (スパリゾートハワイアンズ, いわき市)  電子情報通信学会 情報理論とその応用サブソサイエティ

    Presentation date: 2018.12

  • 観測に基づく量子計算と量子優位性

    小柴健史  [Invited]

    CREST暗号数理 平成30年度第2回全体会議 チュートリアルワークショップ  (九州大学マスフォアインダストリ研究所, 福岡市) 

    Presentation date: 2018.12

  • Pseudorandom Generation in Post Quantum Era

    Takeshi Koshiba  [Invited]

    Small-workshop on Communications between Academia and Industry for Security (SCAIS 2018)  (Niigata, Japan)  Osaka Univ. & AIST

    Presentation date: 2018.01

  • Secure Message Transmission : Possibilities and Limitations

    Takeshi Koshiba  [Invited]

    Presentation date: 2017.09

  • Secure Message Transmission against Rational Adversaries

    Takeshi Koshiba  [Invited]

    Cryptographic Technologies for Securing Network Storage and Their Mathematical Modeling  Institute of Mathematics for Industry, Kyushu University

    Presentation date: 2017.06

  • Composable Security of Blind Computation

    Takeshi Koshiba  [Invited]

    Quantum Science Symposium Asia 2013 (QSS-ASIA 2013)  (Tokyo Univ.) 

    Presentation date: 2013.11

  • Quantum Oblivious Transfer and Quantum One-Way Functions

    Takeshi Koshiba  [Invited]

    Japan-Singapore Workshop on Multi-User Quantum Network  (National University of Singapore) 

    Presentation date: 2012.09

  • Interactive Hashing and BB84 States

    Takeshi Koshiba  [Invited]

    Quatum Information in Paris  (Telecom Paris Tech) 

    Presentation date: 2010.05

  • On the Computational Power of BB84 States

    Takeshi Koshiba  [Invited]

    2010 International Workshop on Quantum Information Science  (Tokyo Univ.) 

    Presentation date: 2010.03

  • Quantum Bit Commitment from Quantum One-Way Function

    Takeshi Koshiba  [Invited]

    International Conference on Quantum Information and Technology  (Tokyo Univ.) 

    Presentation date: 2009.12

  • 一方向性関数からの擬似乱数生成器の構成法について

    小柴健史  [Invited]

    第3回公開鍵暗号の安全な構成とその応用ワークショップ  (秋葉原)  産業技術総合研究所・情報セキュリティーセンター

    Presentation date: 2009.09

  • An Unusual Short Introduction to Quantum Computing

    Takeshi Koshiba  [Invited]

    (Selangor)  Universiti Putra Malaysia

    Presentation date: 2009.06

  • Quantum Computational Bit Commitments

    Takeshi Koshiba  [Invited]

    (Kuala Lumper)  International Islamic University Malaysia

    Presentation date: 2009.06

  • An Old and New Direction to Quantum Cryptography

    Takeshi Koshiba  [Invited]

    (Kuala Lumper)  MIMOS Berhad

    Presentation date: 2009.06

  • On Quantum Oblivious Transfer

    Takeshi Koshiba  [Invited]

    JST-CNRS Joint Workshop on Quantum Computation: Theory and Feasibility  (Institut Henri Poincare (IHP), Paris) 

    Presentation date: 2008.09

  • 量子計算入門

    小柴健史  [Invited]

    非線形問題勉強会  (東京理科大学)  東京理科大学

    Presentation date: 2007.12

  • 擬似乱数のつくりかた

    小柴健史  [Invited]

    第312回情報科学セミナー  東京電機大学

    Presentation date: 2007.06

  • 計算量理論的な量子暗号の進展

    小柴健史  [Invited]

    第16回量子情報技術研究会 (QIT 16)  (NTT厚木) 

    Presentation date: 2007.05

  • 暗号理論における一方向性関数とその周辺の進展

    小柴健史  [Invited]

    科学研究費特定領域研究「新世代の計算限界-その解明と打破-」Complexity研究集会  (東京工業大学) 

    Presentation date: 2006.12

  • Quantum Public Key Cryptosystem

    Takeshi Koshiba  [Invited]

    Theory of Quantum Computation, Communication and Cryptography (TQC 2006) 

    Presentation date: 2006.02

  • 量子メカニズムと暗号通信

    小柴健史  [Invited]

    第3回情報科学技術フォーラム (FIT2004)  (同志社大学) 

    Presentation date: 2004.09

▼display all

Specific Research

  • 量子情報理論的学習理論の数理基盤構築

    2021  

     View Summary

    The guesswork of a quantum ensemble quantifies the minimum number of guesses needed in average to correctly guess the state of the ensemble, when only one state can be queried at a time. Here, we derive analytical solutions of the guesswork problem subject to a finite set of conditions, including the analytical solution for any qubit ensemble with uniform probability distribution. As explicit examples, we compute the guesswork for any qubit regular polygonal and polyhedral ensemble.

  • ゲーム理論的合理性にもとづくセキュアメッセージ転送

    2019   安永憲司

     View Summary

    セキュアメッセージ転送は2者間の暗号プロトコルであり,複数の通信チャネルが利用でき,そのうちの幾つかの通信チャネルが敵対者に支配されたとしても,プライバシーを保ちつつメッセージを確実に伝達する方式である。経済的合理性を考慮したゲーム理論の観点から複数の独立した敵対者がある種の合理性をもって行動をしたとき,全チャネルが複数の敵対者に支配されたとしてもセキュアメッセージ転送が可能であることを示すことができた。これは,通常の暗号理論における敵対者の設定や経済的合理性の敵対者でも単一の敵対者の場合は不可能なことであり,この成果をセキュリティに関するゲーム理論的研究に関するトップ国際会議のGameSec2019で発表した。<!-- /* Font Definitions */ @font-face {font-family:"MS 明朝"; panose-1:2 2 6 9 4 2 5 8 3 4; mso-font-alt:"MS Mincho"; mso-font-charset:128; mso-generic-font-family:modern; mso-font-pitch:fixed; mso-font-signature:-536870145 1791491579 134217746 0 131231 0;}@font-face {font-family:Century; panose-1:2 4 6 4 5 5 5 2 3 4; mso-font-charset:0; mso-generic-font-family:roman; mso-font-pitch:variable; mso-font-signature:647 0 0 0 159 0;}@font-face {font-family:"Cambria Math"; panose-1:2 4 5 3 5 4 6 3 2 4; mso-font-charset:0; mso-generic-font-family:roman; mso-font-pitch:variable; mso-font-signature:-536870145 1107305727 0 0 415 0;}@font-face {font-family:"\@MS 明朝"; panose-1:2 2 6 9 4 2 5 8 3 4; mso-font-charset:128; mso-generic-font-family:modern; mso-font-pitch:fixed; mso-font-signature:-536870145 1791491579 134217746 0 131231 0;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-unhide:no; mso-style-qformat:yes; mso-style-parent:""; margin:0mm; margin-bottom:.0001pt; text-align:justify; text-justify:inter-ideograph; mso-pagination:none; font-size:10.5pt; mso-bidi-font-size:11.0pt; font-family:"Century",serif; mso-fareast-font-family:"MS 明朝"; mso-bidi-font-family:"Times New Roman"; mso-font-kerning:1.0pt;}.MsoChpDefault {mso-style-type:export-only; mso-default-props:yes; font-size:10.0pt; mso-ansi-font-size:10.0pt; mso-bidi-font-size:10.0pt; font-family:"Century",serif; mso-ascii-font-family:Century; mso-fareast-font-family:"MS 明朝"; mso-hansi-font-family:Century; mso-font-kerning:0pt;}size:612.0pt 792.0pt; margin:99.25pt 30.0mm 30.0mm 30.0mm; mso-header-margin:36.0pt; mso-footer-margin:36.0pt; mso-paper-source:0;}div.WordSection1 {page:WordSection1;}<!-- /* Font Definitions */ @font-face {font-family:"MS 明朝"; panose-1:2 2 6 9 4 2 5 8 3 4; mso-font-alt:"MS Mincho"; mso-font-charset:128; mso-generic-font-family:modern; mso-font-pitch:fixed; mso-font-signature:-536870145 1791491579 134217746 0 131231 0;}@font-face {font-family:Century; panose-1:2 4 6 4 5 5 5 2 3 4; mso-font-charset:0; mso-generic-font-family:roman; mso-font-pitch:variable; mso-font-signature:647 0 0 0 159 0;}@font-face {font-family:"Cambria Math"; panose-1:2 4 5 3 5 4 6 3 2 4; mso-font-charset:0; mso-generic-font-family:roman; mso-font-pitch:variable; mso-font-signature:-536870145 1107305727 0 0 415 0;}@font-face {font-family:"\@MS 明朝"; panose-1:2 2 6 9 4 2 5 8 3 4; mso-font-charset:128; mso-generic-font-family:modern; mso-font-pitch:fixed; mso-font-signature:-536870145 1791491579 134217746 0 131231 0;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-unhide:no; mso-style-qformat:yes; mso-style-parent:""; margin:0mm; margin-bottom:.0001pt; text-align:justify; text-justify:inter-ideograph; mso-pagination:none; font-size:10.5pt; mso-bidi-font-size:11.0pt; font-family:"Century",serif; mso-fareast-font-family:"MS 明朝"; mso-bidi-font-family:"Times New Roman"; mso-font-kerning:1.0pt;}.MsoChpDefault {mso-style-type:export-only; mso-default-props:yes; font-size:10.0pt; mso-ansi-font-size:10.0pt; mso-bidi-font-size:10.0pt; font-family:"Century",serif; mso-ascii-font-family:Century; mso-fareast-font-family:"MS 明朝"; mso-hansi-font-family:Century; mso-font-kerning:0pt;}size:612.0pt 792.0pt; margin:99.25pt 30.0mm 30.0mm 30.0mm; mso-header-margin:36.0pt; mso-footer-margin:36.0pt; mso-paper-source:0;}div.WordSection1 {page:WordSection1;}

  • セキュアメッセージ転送の限界突破のためのモデル条件緩和

    2018   安永憲司

     View Summary

    セキュアメッセージ転送は2者間の暗号プロトコルで,2者間の間に利用できるチャネルが複数存在し,複数存在するチャネル数の内何本かを敵に支配され,改ざん・盗聴を許す設定である。セキュアメッセージ転送が要求する性質は秘匿性と信頼性であり,両性質が完全な意味で達成される条件は2者間のチャネル数 Nと敵が支配するチャネル数Tの間にN≧2T+1を満たすことが必要であることが示されている。敵対者モデルとして経済的合理性に従い,かつ,妥当なモデルを構築し,そのモデルにおいては,N≧T+1の場合でも完全なセキュアメッセージ転送が構築できることを示すことに成功した。本成果はGameSec2018で研究発表し,Outstanding Paper Awardを受賞した。

  • 秘匿計算における鍵伝播機構の計算理論構築

    2018   森前智行

     View Summary

    量子計算の枠組みで秘匿代理計算を行う暗号プロトコルとしてBroadbent, Fitzsimons, Kashefiの方法(BFK09法)やその発展版であるHayashi&amp;Morimaeの方法(HM12法)がある。BFK09方法では量子情報を量子ワンタイムパッド法で完全秘匿を達成するのにパウリ行列X及びZをどう適用するのかという鍵情報を保持する。秘匿された量子情報に演算を施すことは鍵情報をどう変遷させるかに対応する。古典計算での実現可能性を究明するために鍵伝播メカニズムを解明することを考えた。両方法を解析した副産物として,古典クライアントではある種のブラインド量子計算は実現不可能であることを示した。

  • 秘匿計算における鍵伝播メカニズムの解明

    2017   Go Sato, Tomoyuki Morimae

     View Summary

    量子計算の枠組みで秘匿代理計算を行う暗号プロトコルとしてBroadbent, Fitzsimons, Kashefiの方法(BFK09法)がある。BFK09法では量子情報を量子ワンタイムパッド法で完全秘匿を達成するのにパウリ行列X及びZをどう適用するのかという鍵情報を保持する。秘匿された量子情報に演算を施すことは鍵情報をどう変遷させるかに対応する。古典計算での実現可能性を究明するためにBFK09法の鍵伝播メカニズムを解明することを考えた。その検討過程としてBFK09法の発展版のHayashi-Morimaeプロトコルを解析し,副産物として公開検証可能はブラインド量子計算プロトコルを考案した。

  • プライバシー保護可能な構造化クエリを許容する暗号化データベース

    2017   Saha Tushar Kanti, Mayank

     View Summary

    Ring LWE (Learning With Error)問題に基づく準同型暗号に対してデータ符号化法を工夫することで,ベクトルを暗号化したままの状態で内積計算の高速計算を実現する方法(報告者の既存研究成果)がある。この技術を応用し,暗号化データベース内の複数データエントリに対して,論理和や論理積を用いて構造的な条件を満たすデータを高速に抽出できるような方法を開発し,従来手法と計算機比較実験をすることで新手法の実効性を実証した。

▼display all

 

Syllabus

▼display all

Teaching Experience

  • Information Mathematics 3&4 [Algorithms and Data Structures]

    Waseda University  

    2021.04
    -
    Now
     

  • Applied Mathematics 6 [Computability Theory]

    Waseda University  

    2021.04
    -
    Now
     

  • Applied Mathematics 5 [Formal Language Theory]

    Waseda University  

    2021.04
    -
    Now
     

  • Advances in Information Mathematics I-2 [Foundations of Cryptography || Analysis of Boolean Functions]

    Waseda University  

    2017.04
    -
    Now
     

  • Advances in Information Mathematics I-1 [Quantum Computation]

    Waseda University  

    2017.04
    -
    Now
     

  • Computer Mathematics 2 [Approximation Algorithms]

    Waseda University  

    2017.04
    -
    Now
     

  • Computer Mathematics 1 [Computational Complexity Theory]

    Waseda University  

    2017.04
    -
    Now
     

  • Information Mathematics 6

    Waseda University  

    2017.04
    -
    2021.03
     

  • Information Mathematics 5

    Waseda University  

    2017.04
    -
    2021.03
     

  • Applied Mathematics 3&4 [Discrete Mathematics]

    Waseda University  

    2017.04
    -
    2021.03
     

▼display all

 

Social Activities

  • 量子コンピューター時代の情報セキュリティ

    会津大学  夢の科学技術を子供たちの手に−シンポジウム2006  (会津大学) 

    2006.11
    -
     

Media Coverage

  • 未来の情報化社会を守る

    Newspaper, magazine

    Author: Other  

    埼玉新聞  

    サイ・テクこらむ  

    2014.04

  • [Future Story] 絶対に破れない量子暗号

    Promotional material

    Author: Other  

    三機工業株式会社広報部   Harmony  

    No.44, pp.12-13  

    2009.03