Updated on 2021/06/22

写真b

 
YASUDA Masaya
 
*Items subject to periodic update by Rikkyo University (The rest are reprinted from information registered on researchmap.)
Affiliation*
College of Science Department of Mathematics
Graduate School of Science Field of Study: Mathematics
Graduate School of Science Field of Study: Mathematics
Title*
Associate Professor
Degree
博士(数理科学) ( 東京大学 )
Contact information
Mail Address
Research Theme*
  • 現代暗号の安全性を支える数学問題の求解アルゴリズムを研究テーマとしている。具体的には、楕円曲線暗号の安全性を支える楕円曲線離散対数問題や、格子暗号の安全性を支える最短ベクトル問題などの格子問題に対して、効率的な求解法を研究すると共に、実際の計算機上でどこまで解けるのか試みている。

  • Research Interests
  • 格子基底簡約

  • 暗号数理

  • 格子暗号

  • 楕円曲線暗号

  • 準同型暗号

  • Campus Career*
    • 4 2020 - Present 
      College of Science   Department of Mathematics   Associate Professor
    • 4 2020 - Present 
      Graduate School of Science   Field of Study: Mathematics   Associate Professor
    • 4 2020 - Present 
      Graduate School of Science   Field of Study: Mathematics   Associate Professor
    Profile
    数学に関係する数理暗号の解読法の探索や安全性解析について研究しています。具体的には、楕円曲線暗号の安全性を支える楕円曲線離散対数問題や、格子暗号の安全性を支える最短ベクトル問題などの格子問題の代数的なアプローチによる解読法について興味を持っています。また、暗号化したまま加算や乗算が可能な準同型暗号のプライバシー保護データ利活用分野への応用にも取り組んでいます。
     

    Research Areas

    • Natural Science / Algebra

    • Informatics / Information security  / 暗号解析

    Research History

    • 4 2020 - Present 
      Kyushu University   Institute of Mathematics for Industry   Guest Professor

      More details

    • 4 2020 - Present 
      RIKKYO UNIVERSITY   College of Science Department of Mathematics   Associate Professor

      More details

    • 4 2020 - Present 
      RIKKYO UNIVERSITY   Graduate School of Science Field of Study: Mathematics   Associate Professor

      More details

    • 4 2020 - Present 
      RIKKYO UNIVERSITY   Graduate School of Science Field of Study: Mathematics   Associate Professor

      More details

    • 4 2020 - Present 
      Rikkyo University

      More details

    • 4 2015 - 3 2020 
      Kyushu University

      More details

    • 9 2007 - 3 2015 
      株式会社富士通研究所   セキュアコンピューティング研究部   研究員

      More details

    • 4 2007 - 8 2007 
      東京大学大学院   数理科学研究科   研究生

      More details

    ▼display all

    Education

    • 4 2004 - 3 2007 
      東京大学大学院   数理科学研究科 博士課程

      More details

    • 4 2002 - 3 2004 
      東京大学大学院   数理科学研究科 修士課程

      More details

    • 4 1998 - 3 2002 
      Kyoto University   Faculty of Science

      More details

    Committee Memberships

    • 2017 - Present 
      電子情報通信学会   英文論文誌小特集号編集委員会 編集委員

      More details

      Committee type:Academic society

      researchmap

    • 2016 - Present 
      電子情報通信学会   情報セキュリティ研究会(ISEC)の専門委員

      More details

      Committee type:Academic society

      researchmap

    • 2013 - Present 
      CRYPTREC暗号技術調査WG(暗号解析評価)における委員

      More details

      Committee type:Academic society

      researchmap

    Awards

    • 2013  
      暗号と情報セキュリティシンポジウム(SCIS2012)イノベーション論文賞 
       
      安田雅哉

      More details

    Papers

    • Implementation report of the Kohel-Lauter-Petit-Tignol algorithm for the constructive Deuring correspondence Peer-reviewed

      Yuta Kambda, Yusuke Aikawa, Momonari Kudo, Katsuyuki Takashima, Masaya Yasuda, Kazuhiro Yokoyama

      presented at International Conference on Mathematics and Computing (ICMC 2021)   3 2021

      More details

      Authorship:Corresponding author   Language:English   Publishing type:Research paper (international conference proceedings)  

      researchmap

    • A survey of solving SVP algorithms and recent strategies for solving the SVP challenge Invited Peer-reviewed

      Masaya Yasuda

      Proceedings of MQC 2019 (International Symposium on Mathematics, Quantum Theory, and Cryptography)   189 - 207   2021

      More details

      Publishing type:Research paper (international conference proceedings)  

      researchmap

    • Symbolic Computation of Isogenies of Elliptic Curves by Vélu’s Formula Peer-reviewed

      Masayuki NORO, Masaya YASUDA, Kazuhiro YOKOYAMA

      COMMENTARII MATHEMATICI UNIVERSITATIS SANCTI PAULI (to appear)68   12 2020

      More details

      Publishing type:Research paper (bulletin of university, research institution)  

      researchmap

    • Massive Parallelization for Finding Shortest Lattice Vectors Based on Ubiquity Generator Framework Peer-reviewed

      Nariaki Tateiwa, Yuji Shinano, Satoshi Nakamura, Akihiro Yoshida, Shizuo Kaji, Masaya Yasuda, Katsuki Fujisawa

      accepted at The International Conference for High Performance Computing, Networking, Storage, and Analysis (SC20). November 15–20, 2020, Atlanta Convention Center.   11 2020

      More details

      Authorship:Corresponding author   Publishing type:Research paper (international conference proceedings)  

      researchmap

    • Fast secure matrix multiplications over ring-based homomorphic encryption (Published Online) Peer-reviewed

      Pradeep Kumar Mishra, Deevashwer Rathee, Dung Hoang Duong, Masaya Yasuda

      Information Security Journal: A Global Perspective   1 - 16   28 10 2020

      More details

      Authorship:Last author, Corresponding author   Publishing type:Research paper (scientific journal)   Publisher:Informa UK Limited  

      DOI: 10.1080/19393555.2020.1836288

      researchmap

    • Dynamic self-dual DeepBKZ lattice reduction with free dimensions Peer-reviewed

      the 6th International Conference on Mathematics and Computing (ICMC 2020) to be held from September 23--25, 2020 at the Sikkim University, Gangtok, Sikkim, India   9 2020

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)  

      researchmap

    • Solving the search-LWE problem by lattice reduction over projected bases Peer-reviewed

      Satoshi Nakamura, Nariaki Tateiwa, Koha Kinjo, Yasuhiko, Ikematsu, Masaya Yasuda, Katsuki Fujisawa

      the 6th International Conference on Mathematics and Computing (ICMC 2020) to be held from September 23--25, 2020 at the Sikkim University, Gangtok, Sikkim, India   9 2020

      More details

    • Algebraic approaches for solving isogeny problems of prime power degrees. Peer-reviewed International journal

      Yasushi Takahashi, Momonari Kudo, Ryoya Fukasaku, Yasuhiko Ikematsu, Masaya Yasuda, Kazuhiro Yokoyama

      J. Math. Cryptol.15 ( 1 ) 31 - 44   2020

      More details

      Language:English   Publishing type:Research paper (scientific journal)  

      DOI: 10.1515/jmc-2020-0072

      researchmap

    • Analysis of DeepBKZ reduction for finding short lattice vectors. Peer-reviewed

      Masaya Yasuda, Satoshi Nakamura, Junpei Yamaguchi

      Des. Codes Cryptogr.88 ( 10 ) 2077 - 2100   2020

      More details

      Authorship:Lead author, Corresponding author   Language:English   Publishing type:Research paper (scientific journal)   Publisher:Springer Science and Business Media LLC  

      DOI: 10.1007/s10623-020-00765-4

      researchmap

    • Complexity bounds on Semaev's naive index calculus method for ECDLP. Peer-reviewed

      Kazuhiro Yokoyama, Masaya Yasuda, Yasushi Takahashi, Jun Kogure

      J. Math. Cryptol.14 ( 1 ) 460 - 485   2020

      More details

      Publishing type:Research paper (scientific journal)  

      DOI: 10.1515/jmc-2019-0029

      researchmap

    • Hybrid Meet-in-the-Middle Attacks for the Isogeny Path-Finding Problem. Peer-reviewed

      Yasuhiko Ikematsu, Ryoya Fukasaku, Momonari Kudo, Masaya Yasuda, Katsuyuki Takashima, Kazuhiro Yokoyama

          36 - 44   2020

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)  

      DOI: 10.1145/3384940.3388956

      researchmap

      Other Link: https://dblp.uni-trier.de/db/conf/ccs/asiapkc2020.html#IkematsuFKYTY20

    • Impact of the modulus switching technique on some attacks against learning problems. Peer-reviewed

      Huy Quoc Le, Pradeep Kumar Mishra, Satoshi Nakamura, Koha Kinjo, Dung Hoang Duong, Masaya Yasuda

      IET Inf. Secur.14 ( 3 ) 286 - 303   2020

      More details

      Publishing type:Research paper (scientific journal)  

      DOI: 10.1049/iet-ifs.2019.0220

      researchmap

    • Self-dual DeepBKZ for finding short lattice vectors. Peer-reviewed

      Masaya Yasuda

      J. Math. Cryptol.14 ( 1 ) 84 - 94   2020

      More details

      Authorship:Lead author, Corresponding author   Publishing type:Research paper (scientific journal)   Publisher:Walter de Gruyter GmbH  

      <title>Abstract</title>In recent years, the block Korkine-Zolotarev (BKZ) and its variants such as BKZ 2.0 have been used as de facto algorithms to estimate the security of a lattice-based cryptosystem. In 2017, DeepBKZ was proposed as a mathematical improvement of BKZ, which calls LLL with deep insertions (DeepLLL) as a subroutine alternative to LLL. DeepBKZ can find a short lattice vector by smaller blocksizes than BKZ. In this paper, we develop a self-dual variant of DeepBKZ, as in the work of Micciancio and Walter for self-dual BKZ. Like DeepBKZ, our self-dual DeepBKZ calls both DeepLLL and its dual variant as main subroutines in order to accelerate to find a very short lattice vector. We also report experimental results of DeepBKZ and our self-dual DeepBKZ for random bases on the Darmstadt SVP challenge.

      DOI: 10.1515/jmc-2015-0053

      researchmap

    • A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram-Schmidt lengths. Peer-reviewed

      Masaya Yasuda, Junpei Yamaguchi

      Des. Codes Cryptogr.87 ( 11 ) 2489 - 2505   2019

      More details

      Publishing type:Research paper (scientific journal)  

      DOI: 10.1007/s10623-019-00634-9

      researchmap

    • Security analysis of cryptosystems using short generators over ideal lattices Peer-reviewed

      Shinya Okumura, Shingo Sugiyama, Masaya Yasuda, Tsuyoshi Takagi

      Japan Journal of Industrial and Applied Mathematics35 ( 2 ) 739 - 771   1 7 2018

      More details

      Language:English   Publishing type:Research paper (scientific journal)   Publisher:Springer Tokyo  

      In this paper, we analyze the security of cryptosystems using short generators over ideal lattices. Our approach is based on a recent work by Cramer et al. on analysis of the recovering short generators problem on q-th cyclotomic fields with prime powers q. In their analysis, implicit lower bounds of the special values of Dirichlet L-functions at 1 are essentially used for estimating some sizes of the dual bases of the log-unit lattices of the q-th cyclotomic fields. Our contribution is to improve Cramer et al.’s analysis by giving explicit lower and upper bounds of the special values of Dirichlet L-functions at 1. Our improvement allows one to analyze the RSG attack not only asymptotically but also explicitly for fixed practical parameters. Moreover, we give experimental evidence that recovering short generators over 2 k-th cyclotomic fields for k≥ 10 is succeeded with high probability.

      DOI: 10.1007/s13160-018-0306-z

      Scopus

      researchmap

    • Acceleration of Index Calculus for Solving ECDLP over Prime Fields and Its Limitation. Peer-reviewed

      Momonari Kudo, Yuki Yokota, Yasushi Takahashi, Masaya Yasuda

      Cryptology and Network Security - 17th International Conference, CANS 2018, Naples, Italy, September 30 - October 3, 2018, Proceedings   377 - 393   2018

      More details

      Publishing type:Research paper (international conference proceedings)   Publisher:Springer  

      DOI: 10.1007/978-3-030-00434-7_19

      researchmap

      Other Link: https://dblp.uni-trier.de/db/conf/cans/cans2018.html#KudoYTY18

    • Development of a Dual Version of DeepBKZ and Its Application to Solving the LWE Challenge. Peer-reviewed

      Masaya Yasuda, Junpei Yamaguchi, Michiko Ooka, Satoshi Nakamura

      Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)10831   162 - 182   2018

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer Verlag  

      Lattice basis reduction is a strong tool in cryptanalysis. In 2017, DeepBKZ was proposed as a new variant of BKZ, and it calls LLL with deep insertions (DeepLLL) as a subroutine alternative to LLL. In this paper, we develop a dual version of DeepBKZ (which we call “Dual-DeepBKZ”), to reduce the dual basis of an input basis. For Dual-DeepBKZ, we develop a dual version of DeepLLL, and then combine it with the dual enumeration by Micciancio and Walter. It never computes the dual basis of an input basis, and it is as efficient as the primal DeepBKZ. We also demonstrate that Dual-DeepBKZ solves several instances in the TU Darmstadt LWE challenge. We use Dual-DeepBKZ in the bounded distance decoding (BDD) approach for solving an LWE instance. Our experiments show that Dual-DeepBKZ reduces the cost of Liu-Nguyen’s BDD enumeration more effectively than BKZ. For the LWE instance of (n, α) = (40, 0.015) (resp., (n, α) = (60, 0.005)), our results are about 2.2 times (resp., 4.0 times) faster than Xu et al.’s results, for which they used BKZ in the fplll library and the BDD enumeration with extreme pruning while we used linear pruning in our experiments.

      DOI: 10.1007/978-3-319-89339-6_10

      Scopus

      researchmap

      Other Link: https://dblp.uni-trier.de/db/conf/africacrypt/africacrypt2018.html#YasudaYON18

    • Explicit formula for gram-schmidt vectors in LLL with deep insertions and its applications Peer-reviewed

      Junpei Yamaguchi, Masaya Yasuda

      Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)10737   142 - 160   2018

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer Verlag  

      Lattice basis reduction algorithms have been used as a strong tool for cryptanalysis. The most famous one is LLL, and its typical improvements are BKZ and LLL with deep insertions (DeepLLL). In LLL and DeepLLL, at every time to replace a lattice basis, we need to recompute the Gram-Schmidt orthogonalization (GSO) for the new basis. Compared with LLL, the form of the new GSO vectors is complicated in DeepLLL, and no formula has been known. In this paper, we give an explicit formula for GSO in DeepLLL, and also propose an efficient method to update GSO in DeepLLL. As another work, we embed DeepLLL into BKZ as a subroutine instead of LLL, which we call “DeepBKZ”, in order to find a more reduced basis. By using our DeepBKZ with blocksizes up to β = 50, we have found a number of new solutions for the Darmstadt SVP challenge in dimensions from 102 to 123.

      DOI: 10.1007/978-3-319-76620-1_9

      Scopus

      researchmap

    • Faster PCA and Linear Regression through Hypercubes in HElib. Peer-reviewed

      Deevashwer Rathee, Pradeep Kumar Mishra, Masaya Yasuda

      Proceedings of the 2018 Workshop on Privacy in the Electronic Society, WPES@CCS 2018, Toronto, ON, Canada, October 15-19, 2018   42 - 53   2018

      More details

      Publishing type:Research paper (international conference proceedings)   Publisher:ACM  

      DOI: 10.1145/3267323.3268952

      researchmap

      Other Link: https://dblp.uni-trier.de/db/conf/wpes/wpes2018.html#RatheeMY18

    • Solving LWR via BDD Strategy: Modulus Switching Approach. Peer-reviewed

      Huy Quoc Le, Pradeep Kumar Mishra, Dung Hoang Duong, Masaya Yasuda

      Cryptology and Network Security - 17th International Conference, CANS 2018, Naples, Italy, September 30 - October 3, 2018, Proceedings   357 - 376   2018

      More details

      Publishing type:Research paper (international conference proceedings)   Publisher:Springer  

      DOI: 10.1007/978-3-030-00434-7_18

      researchmap

      Other Link: https://dblp.uni-trier.de/db/conf/cans/cans2018.html#LeMDY18

    • Practical Limit of Index Calculus Algorithms for ECDLP over Prime Fields Peer-reviewed International journal

      Yuki Yokota, Momonari Kudo, Masaya Yasuda

      Proceedings of The Tenth International Workshop on Coding and Cryptography 2017, WCC 2017, Saint-Petersburg, Russia, September 18-22, 2017   9 2017

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)  

      researchmap

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

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

      J. Math. Cryptol.11 ( 1 ) 1 - 24   2017

      More details

      Publishing type:Research paper (scientific journal)  

      DOI: 10.1515/jmc-2016-0008

      researchmap

    • Application of mixed integer quadratic program to shortest vector problems. Peer-reviewed

      Keiji Kimura, Hayato Waki, Masaya Yasuda

      JSIAM Lett.9   65 - 68   2017

      More details

      Publishing type:Research paper (scientific journal)  

      DOI: 10.14495/jsiaml.9.65

      researchmap

    • Choosing Parameters for the Subfield Lattice Attack Against Overstretched NTRU. Peer-reviewed

      Dung Hoang Duong, Masaya Yasuda, Tsuyoshi Takagi

      Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)10599   79 - 91   2017

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer Verlag  

      Albrecht et al. [1] at Crypto 2016 and Cheon et al. [4] at ANTS 2016 independently presented a subfield attack on overstretched NTRU problem. Their idea is to map the public key down to the subfield (by norm and trace map respectively) and hence obtain a lattice of smaller dimension for which a lattice reduction algorithm is efficiently applicable. At Eurocrypt 2017, Kirchner and Fouque proposed another variant attack which exploits the presence of orthogonal bases within the cyclotomic number rings and instead of using the matrix of the public key in the subfield, they use the multiplication matrix by the public key in the full field and apply a lattice reduction algorithm to a suitable projected lattice of smaller dimension. They also showed a tight estimation of the parameters broken by lattice reduction and implementation results that their attack is better than the subfield attack. In this paper, we exploit technical results from Kirchner and Fouque [12] for the relative norm of field elements in the subfield and we use Hermite factor for estimating the output of a lattice basis reduction algorithm in order to analyze general choice of parameters for the subfield attack by Albrecht et al. [1]. As a result, we obtain the estimation for better choices of the subfields for which the attack works with smaller modulus. Our experiment results show that we can attack overstretched NTRU with modulus smaller than that of Albrecht et al. and of Kirchner and Fouque.

      DOI: 10.1007/978-3-319-69659-1_5

      Scopus

      researchmap

      Other Link: https://dblp.uni-trier.de/db/conf/isw/isc2017.html#DuongYT17

    • Enhancement for Secure Multiple Matrix Multiplications over Ring-LWE Homomorphic Encryption. Peer-reviewed

      Pradeep Kumar Mishra, Dung Hoang Duong, Masaya Yasuda

      Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)10701   320 - 330   2017

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer Verlag  

      Homomorphic encryption allows to perform various calculations on encrypted data without decryption. In this paper, we propose an efficient method for secure multiple matrix multiplications over the somewhat homomorphic encryption scheme proposed by Brakerski and Vaikuntanathan. Our method is a generalization of Duong et al.’s method, which computes only one multiplication between two matrices. In order to minimize both the ciphertext size and the computation cost, our method packs every matrix into a single ciphertext so that it enables efficient matrix multiplications over the packed ciphertexts. We also propose several modifications to obtain practical performance of secure multiplications among matrices with larger size and entries. We show implementation results of our packing method with modifications for secure multiplications among two and three matrices with 32 × 32 and 64 × 64 sizes and entries from 16-bit to 64-bit.

      DOI: 10.1007/978-3-319-72359-4_18

      Scopus

      researchmap

      Other Link: https://dblp.uni-trier.de/db/conf/ispec/ispec2017.html#MishraDY17

    • Recovering Attacks Against Linear Sketch in Fuzzy Signature Schemes of ACNS 2015 and 2016. Peer-reviewed

      Masaya Yasuda, Takeshi Shimoyama, Masahiko Takenaka, Narishige Abe, Shigefumi Yamada, Junpei Yamaguchi

      Information Security Practice and Experience - 13th International Conference, ISPEC 2017, Melbourne, VIC, Australia, December 13-15, 2017, Proceedings   409 - 421   2017

      More details

      Publishing type:Research paper (international conference proceedings)   Publisher:Springer  

      DOI: 10.1007/978-3-319-72359-4_24

      researchmap

      Other Link: https://dblp.uni-trier.de/db/conf/ispec/ispec2017.html#YasudaSTAYY17

    • Secure Hamming distance computation for biometrics using ideal-lattice and ring-LWE homomorphic encryption. Peer-reviewed

      Masaya Yasuda

      Inf. Secur. J. A Glob. Perspect.26 ( 2 ) 85 - 103   2017

      More details

      Language:English   Publishing type:Research paper (scientific journal)   Publisher:Taylor and Francis Inc.  

      With widespread development of biometrics, concerns about security and privacy are rapidly increasing. Homomorphic encryption enables us to operate on encrypted data without decryption, and it can be applied to construct a privacy-preserving biometric system. In this article, we apply two homomorphic encryption schemes based on ideal-lattice and ring-LWE (Learning with Errors), which both have homomorphic correctness over the ring of integers of a cyclotomic field. We compare the two schemes in applying them to privacy-preserving biometrics. In biometrics, the Hamming distance is used as a metric to compare two biometric feature vectors for authentication. We propose an efficient method for secure Hamming distance. Our method can pack a biometric feature vector into a single ciphertext, and it enables efficient computation of secure Hamming distance over our packed ciphertexts.

      DOI: 10.1080/19393555.2017.1293199

      Scopus

      researchmap

    • Secure and Efficient Pairing at 256-Bit Security Level. Peer-reviewed

      Yutaro Kiyomura, Akiko Inoue, Yuto Kawahara, Masaya Yasuda, Tsuyoshi Takagi, Tetsutaro Kobayashi

      Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)10355   59 - 79   2017

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer Verlag  

      At CRYPTO 2016, Kim and Barbulescu proposed an efficient number field sieve (NFS) algorithm for the discrete logarithm problem (DLP) in a finite field. The security of pairing-based cryptography (PBC) is based on the difficulty in solving the DLP. Hence, it has become necessary to revise the bitlength that the DLP is computationally infeasible against the efficient NFS algorithms. The timing of the main operations of PBC (i.e. pairing, scalar multiplication on the elliptic curves, and exponentiation on the finite field) generally becomes slower as the bitlength becomes longer, so it has become increasingly important to compute the main operations of PBC more efficiently. To choose a suitable pairing-friendly curve from among various pairing-friendly curves is one of the factors that affect the efficiency of computing the main operations of PBC. We should implement the main operations of PBC and compare the timing among some pairing-friendly curves in order to choose the suitable pairing-friendly curve precisely. In this paper, we focus on the five candidate pairing-friendly curves from the Barreto- Lynn-Scott (BLS) and Kachisa-Schaefer-Scott (KSS) families as the 256- bit secure pairing-friendly curves and show the following two results
      (1) the revised bitlength that the DLP is computationally infeasible against the efficient NFS algorithms for each candidate pairing-friendly curve, (2) the suitable pairing-friendly curve by comparing the timing of the main operations of PBC among the candidate pairing-friendly curves using the revised bitlength.

      DOI: 10.1007/978-3-319-61204-1_4

      Scopus

      researchmap

      Other Link: https://dblp.uni-trier.de/db/conf/acns/acns2017.html#KiyomuraIKYTK17

    • Computational hardness of IFP and ECDLP Peer-reviewed

      Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Tetsuya Izu

      APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING27 ( 6 ) 493 - 521   12 2016

      More details

      Language:English   Publishing type:Research paper (scientific journal)   Publisher:SPRINGER  

      The RSA cryptosystem and elliptic curve cryptography (ECC) have been used practically and widely in public key cryptography. The security of RSA and ECC respectively relies on the computational hardness of the integer factorization problem (IFP) and the elliptic curve discrete logarithm problem (ECDLP). In this paper, we give an estimate of computing power required to solve each problem by state-of-the-art of theory and experiments. By comparing computing power required to solve the IFP and the ECDLP, we also estimate bit sizes of the two problems that can provide the same security level.

      DOI: 10.1007/s00200-016-0291-x

      researchmap

    • Efficient Secure Matrix Multiplication over LWE-Based Homomorphic Encryption Peer-reviewed

      Dung Hoang Duong, Pradeep Kumar Mishra, Masaya Yasuda

      Tatra Mountains Mathematical Publications67 ( 1 ) 69 - 83   1 9 2016

      More details

      Language:English   Publishing type:Research paper (scientific journal)   Publisher:De Gruyter Open Ltd  

      Homomorphic encryption enables various calculations while preserving the data confidentiality. In this paper, we apply the somewhat homomorphic encryption scheme proposed by Brakerski and Vaikuntanathan (CRYPTO 2011) to secure matrix multiplication between two matrices. To reduce both the ciphertext size and the computation cost, we propose a new method to pack a matrix into a single ciphertexts so that it also enables efficient matrix multiplication over the packed ciphertexts. Our packing method generalizes Yasuda et al.'s methods (Security Comm. Networks 2015 and ACISP 2015), which are for secure inner product. We also implement our methods and give a comparison with previous packing methods.

      DOI: 10.1515/tmmp-2016-0031

      Scopus

      researchmap

    • Comprehensive and Improved Secure Biometric System Using Homomorphic Encryption Peer-reviewed

      Avradip Mandal, Arnab Roy, Masaya Yasuda

      DATA PRIVACY MANAGEMENT, AND SECURITY ASSURANCE9481   183 - 198   2016

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER INT PUBLISHING AG  

      With the widespread development of biometric systems, concerns about security and privacy are increasing. An active area of research is template protection technology, which aims to protect registered biometric data. We focus on a homomorphic encryption approach, which enables building a "cryptographically-secure" system. In DPM 2013, Yasuda et al. proposed an efficient template protection system, using the homomorphic encryption scheme proposed by Brakerski and Vaikuntanathan. In this work, we improve and fortify their system to withstand impersonation attacks such as replay and spoofing attacks. We introduce a challenge-response authentication mechanism in their system and design a practical distributed architecture where computation and authentication are segregated. Our comprehensive system would be useful to build a large-scale and secure biometric system such as secure remote authentication over public networks.

      DOI: 10.1007/978-3-319-29883-2_12

      researchmap

    • Comprehensive and Improved Secure Biometric System Using Homomorphic Encryption Peer-reviewed

      Avradip Mandal, Arnab Roy, Masaya Yasuda

      DATA PRIVACY MANAGEMENT, AND SECURITY ASSURANCE9481   183 - 198   2016

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER INT PUBLISHING AG  

      With the widespread development of biometric systems, concerns about security and privacy are increasing. An active area of research is template protection technology, which aims to protect registered biometric data. We focus on a homomorphic encryption approach, which enables building a "cryptographically-secure" system. In DPM 2013, Yasuda et al. proposed an efficient template protection system, using the homomorphic encryption scheme proposed by Brakerski and Vaikuntanathan. In this work, we improve and fortify their system to withstand impersonation attacks such as replay and spoofing attacks. We introduce a challenge-response authentication mechanism in their system and design a practical distributed architecture where computation and authentication are segregated. Our comprehensive system would be useful to build a large-scale and secure biometric system such as secure remote authentication over public networks.

      DOI: 10.1007/978-3-319-29883-2_12

      researchmap

    • Practical Analysis of Key Recovery Attack Against Search-LWE Problem Peer-reviewed

      Momonari Kudo, Junpei Yamaguchi, Yang Guo, Masaya Yasuda

      ADVANCES IN INFORMATION AND COMPUTER SECURITY, IWSEC 20169836   164 - 181   2016

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER INTERNATIONAL PUBLISHING AG  

      The security of a number of modern cryptographic schemes relies on the computational hardness of the learning with errors (LWE) problem. In 2015, Laine and Lauter analyzed a key recovery (or decoding) attack against the search variant of LWE. Their analysis is based on a generalization of the Boneh-Venkatesan method for the hidden number problem to LWE. They adopted the LLL algorithm and Babai's nearest plane method in the attack against LWE, and they also demonstrated a successful range of the attack by experiments for hundreds of LWE instances. In this paper, we give an alternative analysis of the key recovery attack. While Laine and Lauter's analysis gives explicit information about the effective approximation factor in the LLL algorithm and Babai's nearest plane method, our analysis is useful to estimate which LWE instances can be solved by the key recovery attack. Furthermore, our analysis enables one to determine a successful range of the attack with practical lattice reduction such as the BKZ algorithm.

      DOI: 10.1007/978-3-319-44524-3_10

      researchmap

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

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

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

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER INTERNATIONAL PUBLISHING AG  

      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: 10.1007/978-3-319-30303-1_8

      researchmap

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

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

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

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER INTERNATIONAL PUBLISHING AG  

      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: 10.1007/978-3-319-30303-1_8

      researchmap

    • Torsion points and reduction of elliptic curves Peer-reviewed

      Masaya Yasuda

      ACTA ARITHMETICA176 ( 1 ) 89 - 100   2016

      More details

      Language:English   Publishing type:Research paper (scientific journal)   Publisher:POLISH ACAD SCIENCES INST MATHEMATICS-IMPAN  

      DOI: 10.4064/aa8425-6-2016

      researchmap

    • Biometric key-binding using lattice masking Peer-reviewed

      Masaya Yasuda, Yuka Sugimura

      SECURITY AND COMMUNICATION NETWORKS8 ( 18 ) 3405 - 3414   12 2015

      More details

      Language:English   Publishing type:Research paper (scientific journal)   Publisher:WILEY-BLACKWELL  

      In biometrics, template protection technology aims to protect the confidentiality of a biometric template (i.e., enrolled biometric information) by certain conversion. Here, we focus on the key-binding approach for template protection. This approach generates a secure template from joint data of a user's specific key with a user's template, and the key can be correctly extracted from the secure template only when a queried biometric feature is close to the plain template. While almost all conventional schemes use the error correcting code technique, we present a new technique based on lattices to give a new key-binding scheme. Our proposed scheme can provide several requirements (e.g., diversity and revocability) for template protection, which cannot be provided by error correcting code based typical schemes such as the fuzzy commitment and the fuzzy vault. Copyright (C) 2015 John Wiley & Sons, Ltd.

      DOI: 10.1002/sec.1267

      researchmap

    • Ramification of the Kummer extension generated from torsion points of elliptic curves Peer-reviewed

      Masaya Yasuda

      INTERNATIONAL JOURNAL OF NUMBER THEORY11 ( 6 ) 1725 - 1734   9 2015

      More details

      Language:English   Publishing type:Research paper (scientific journal)   Publisher:WORLD SCIENTIFIC PUBL CO PTE LTD  

      For a prime p, let zeta(p) denote a fixed primitive pth root of unity. Let E be an elliptic curve over a number field k with a p-torsion point. Then the p-torsion subgroup of E gives a Kummer extension over k(zeta(p)). In this paper, for p = 5 and 7, we study the ramification of such Kummer extensions using explicit Kummer generators directly computed by Verdure in 2006.

      DOI: 10.1142/S1793042115500736

      researchmap

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

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

      Security and Communication Networks8 ( 13 ) 2194 - 2213   2015

      More details

      Publishing type:Research paper (scientific journal)  

      DOI: 10.1002/sec.1164

      researchmap

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

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

      Proceedings of the 3rd International Workshop on Security in Cloud Computing, SCC@ASIACCS '15, Singapore, Republic of Singapore, April 14, 2015   53 - 61   2015

      More details

      Publishing type:Research paper (international conference proceedings)   Publisher:ACM  

      DOI: 10.1145/2732516.2732521

      researchmap

    • Secure Statistical Analysis Using RLWE-Based Homomorphic Encryption. Peer-reviewed

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

      Information Security and Privacy - 20th Australasian Conference, ACISP 2015, Brisbane, QLD, Australia, June 29 - July 1, 2015, Proceedings9144   471 - 487   2015

      More details

      Publishing type:Research paper (international conference proceedings)   Publisher:Springer  

      DOI: 10.1007/978-3-319-19962-7_27

      researchmap

    • A Biometric Key-Binding Scheme Using Lattice Masking Peer-reviewed

      Yuka Sugimura, Masaya Yasuda, Shigefumi Yamada, Narishige Abe, Takashi Shinzaki

      2014 INTERNATIONAL CONFERENCE OF THE BIOMETRICS SPECIAL INTEREST GROUP (BIOSIG)   211 - 218   2014

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:IEEE  

      Template protection technology can protect the confidentiality of a biometric template by certain conversion. We focus on the key-binding approach for template protection. This approach generates a secure template (or a conversion template) from joint data of a user's specific key with a user's template, and the key can be correctly extracted from the secure template only when a queried biometric feature is sufficiently close to the original template. While almost all conventional schemes use the error correcting code (ECC) technique, we present a new technique based on lattices to give a new key-binding scheme. Our proposed scheme can provide several requirements (e.g., diversity and revocability) for template protection, which cannot be provided by ECC-based schemes such as the fuzzy commitment and the fuzzy vault.

      researchmap

      Other Link: http://dblp.uni-trier.de/db/conf/biosig/biosig2014.html#conf/biosig/SugimuraYYAS14

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

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

      J. Mathematical Cryptology8 ( 3 ) 305 - 329   2014

      More details

      Publishing type:Research paper (scientific journal)  

      DOI: 10.1515/jmc-2013-0024

      researchmap

    • Practical Packing Method in Somewhat Homomorphic Encryption Peer-reviewed

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

      DATA PRIVACY MANAGEMENT AND AUTONOMOUS SPONTANEOUS SECURITY, DPM 20138247   34 - 50   2014

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

      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: 10.1007/978-3-642-54568-9_3

      researchmap

    • Practical Packing Method in Somewhat Homomorphic Encryption Peer-reviewed

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

      DATA PRIVACY MANAGEMENT AND AUTONOMOUS SPONTANEOUS SECURITY, DPM 20138247   34 - 50   2014

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

      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: 10.1007/978-3-642-54568-9_3

      researchmap

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

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

      INFORMATION SECURITY AND PRIVACY, ACISP 20148544   338 - 353   2014

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

      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: 10.1007/978-3-319-08344-5_22

      researchmap

    • KUMMER GENERATORS AND TORSION POINTS OF ELLIPTIC CURVES WITH BAD REDUCTION AT SOME PRIMES Peer-reviewed

      Masaya Yasuda

      INTERNATIONAL JOURNAL OF NUMBER THEORY9 ( 7 ) 1743 - 1752   11 2013

      More details

      Language:English   Publishing type:Research paper (scientific journal)   Publisher:WORLD SCIENTIFIC PUBL CO PTE LTD  

      For a prime p, let zeta(p) denote a fixed primitive pth root of unity. Let E be an elliptic curve over a number field K with a p-torsion point. Then the p-torsion subgroup of E gives a Kummer extension over K(zeta(p)), and in this paper, we study the ramification of such Kummer extensions using the Kummer generators directly computed by Verdure in 2006. For quadratic fields K, we also give unramified Kummer extensions over K(zeta(p)) generated from elliptic curves over K having a p-torsion point with bad reduction at certain primes. Many of these unramified Kummer extensions have not appeared in the previous work using fundamental units of quadratic fields.

      DOI: 10.1142/S1793042113500541

      researchmap

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

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

      Security Engineering and Intelligence Informatics - CD-ARES 2013 Workshops: MoCrySEn and SeCIHD, Regensburg, Germany, September 2-6, 2013. Proceedings   55 - 74   2013

      More details

      Publishing type:Research paper (international conference proceedings)   Publisher:Springer  

      DOI: 10.1007/978-3-642-40588-4_5

      researchmap

    • Secure pattern matching using somewhat homomorphic encryption. Peer-reviewed

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

      CCSW'13, Proceedings of the 2013 ACM Cloud Computing Security Workshop, Co-located with CCS 2013, Berlin, Germany, November 4, 2013   65 - 76   2013

      More details

      Publishing type:Research paper (international conference proceedings)   Publisher:ACM  

      DOI: 10.1145/2517488.2517497

      researchmap

    • Torsion points of elliptic curves with bad reduction at some primes II Peer-reviewed

      Masaya Yasuda

      Bulletin of the Korean Mathematical Society50 ( 1 ) 83 - 96   2013

      More details

      Language:English   Publishing type:Research paper (scientific journal)  

      Let K be a number field and fix a prime number p. For any set S of primes of K, we here say that an elliptic curve E over K has S-reduction if E has bad reduction only at the primes of S. There exists the set BK,p of primes of K satisfying that any elliptic curve over K with BK,p-reduction has no p-torsion points under certain conditions. The first aim of this paper is to construct elliptic curves over K with BK,p reduction and a p-torsion point. The action of the absolute Galois group on the p-torsion subgroup of E gives its associated Galois representation PE,p modulo p. We also study the irreducibility and surjectivity of ρE,p for semistable elliptic curves with BK,p-reduction. © 2013 The Korean Mathematical Society.

      DOI: 10.4134/BKMS.2013.50.1.083

      Scopus

      researchmap

    • Analysis of Lattice Reduction Attack against the Somewhat Homomorphic Encryption Based on Ideal Lattices. Peer-reviewed

      Masaya Yasuda, Jun Yajima, Takeshi Shimoyama, Jun Kogure

      Public Key Infrastructures, Services and Applications - 9th European Workshop, EuroPKI 2012, Pisa, Italy, September 13-14, 2012, Revised Selected Papers   1 - 16   2012

      More details

      Publishing type:Research paper (international conference proceedings)   Publisher:Springer  

      DOI: 10.1007/978-3-642-40012-4_1

      researchmap

    • On elliptic curves whose 3-torsion subgroup splits as μ3 ⊕ ℤ/3ℤ Peer-reviewed

      Masaya Yasuda

      Communications of the Korean Mathematical Society27 ( 3 ) 497 - 503   2012

      More details

      Language:English   Publishing type:Research paper (scientific journal)  

      In this paper, we study elliptic curves E over ( such thatthe 3-torsion subgroup E[3] is split as μ3 ⊕ ℤ/3ℤ. For a non-zero integer m, let Cm denote the curve x3 + y3 = m. We consider the relation between the set of integral points of Cm and the elliptic curves E with E[3] ≃ μ3 ⊕ ℤ/3ℤ. © 2012 The Korean Mathematical Society.

      DOI: 10.4134/CKMS.2012.27.3.497

      Scopus

      researchmap

    • On the Strength Comparison of the ECDLP and the IFP. Peer-reviewed

      Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Tetsuya Izu

      Security and Cryptography for Networks - 8th International Conference, SCN 2012, Amalfi, Italy, September 5-7, 2012. Proceedings   302 - 325   2012

      More details

      Publishing type:Research paper (international conference proceedings)   Publisher:Springer  

      DOI: 10.1007/978-3-642-32928-9_17

      researchmap

    • Solving a DLP with auxiliary input with the ρ-algorithm Peer-reviewed

      Yumi Sakemi, Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda

      Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)7115   98 - 108   2012

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer  

      The discrete logarithm problem with auxiliary input (DLPwAI) is a problem to find a positive integer α from elements G, αG, α d G in an additive cyclic group generated by G of prime order r and a positive integer d dividing r -1. In 2011, Sakemi et al. implemented Cheon's algorithm for solving DLPwAI, and solved a DLPwAI in a group with 128-bit order r in about 131 hours with a single core on an elliptic curve defined over a prime finite field which is used in the TinyTate library for embedded cryptographic devices. However, since their implementation was based on Shanks' Baby-step Giant-step (BSGS) algorithm as a sub-algorithm, it required a large amount of memory (246 GByte) so that it was concluded that applying other DLPwAIs with larger parameter is infeasible. In this paper, we implemented Cheon's algorithm based on Pollard's ρ-algorithm in order to reduce the required memory. As a result, we have succeeded solving the same DLPwAI in about 136 hours by a single core with less memory (0.5 MByte). © 2012 Springer-Verlag Berlin Heidelberg.

      DOI: 10.1007/978-3-642-27890-7_8

      Scopus

      researchmap

    • Solving a Discrete Logarithm Problem with Auxiliary Input on a 160-Bit Elliptic Curve Peer-reviewed

      Yumi Sakemi, Goichiro Hanaoka, Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda

      PUBLIC KEY CRYPTOGRAPHY - PKC 20127293   595 - 608   2012

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

      A discrete logarithm problem with auxiliary input (DLPwAI) is a problem to find a from G, alpha G, alpha(d)G in an additive cyclic group generated by an element G of prime order r, and a positive integer d satisfying d|(r - 1). The infeasibility of this problem assures the security of some cryptographic schemes. In 2006, Cheon proposed a novel algorithm for solving DLPwAI (Cheon's algorithm). This paper reports our experimental results of Cheon's algorithm by implementing it with some speeding-up techniques. In fact, we have succeeded to solve DLPwAI on a pairing-friendly elliptic curve of 160-bit order in 1314 core days. Implications of our experiments on cryptographic schemes are also discussed.

      researchmap

    • ON THE CANONICAL BUNDLE FORMULA FOR ABELIAN FIBER SPACES IN POSITIVE CHARACTERISTIC Peer-reviewed

      Masaya Yasuda

      KODAI MATHEMATICAL JOURNAL34 ( 1 ) 55 - 70   3 2011

      More details

      Language:English   Publishing type:Research paper (scientific journal)   Publisher:KINOKUNIYA CO LTD  

      Let X be a non-singular projective (n + 1)-fold defined over an algebraically closed field k of characteristic p &gt;= 0, and B be a non-singular complete curve defined over k. A surjective morphism f : X -&gt; B is said to be an n-abelian fiber space if almost all fibers are n-dimensional abelian varieties. We examine the canonical bundle formula for n-abelian fiber spaces.

      DOI: 10.2996/kmj/1301576761

      researchmap

    • Experimantal Analysis of Cheon's Algorithm against Pairing-Friendly Curves Peer-reviewed

      Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda

      25TH IEEE INTERNATIONAL CONFERENCE ON ADVANCED INFORMATION NETWORKING AND APPLICATIONS (AINA 2011)   90 - 96   2011

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:IEEE COMPUTER SOC  

      The discrete logarithm problem (DLP) is one of the familiar problem on which some cryptographic schemes rely. In 2006, Cheon proposed an algorithm for solving DLP with auxiliary input which works better than conventional algorithms.
      In this paper, we show our experimental results of Cheon's algorithm on a pairing-friendly elliptic curve defined over GF (3(127)). It is shown that the algorithm combined with the kangaroo method has an advantage over that combined with the baby-step giant-step method in the sense that the required time and space are smaller.
      Then, for the algorithm combined with the kangaroo-method, speeding-up techniques are introduced. Based on our experimental results and the speeding-up techniques, we evaluate the required time and space for some pairing-friendly elliptic curves curves. As results, a portion of pairing-friendly elliptic curves can be analyzed by Cheon's algorithm at reasonable cost.

      DOI: 10.1109/AINA.2011.37

      researchmap

    • Experimental analysis of cheon’s algorithm against pairing-friendly curves Peer-reviewed

      Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda

      Journal of Information Processing19   441 - 450   2011

      More details

      Language:English   Publishing type:Research paper (scientific journal)   Publisher:Information Processing Society of Japan  

      Let G be an additive group generated by an element G of prime order r. The discrete logarithm problem with auxiliary input (DLPwAI) is a problem to find α on inputs G, αG, α&lt
      sup&gt
      d&lt
      /sup&gt
      G ∈ G for a positive integer d dividing r − 1. The infeasibility of DLPwAI ensures the security of some pairing-based cryptographic schemes. In 2006, Cheon proposed an algorithm for solving DLPwAI which works better than conventional algorithms. In this paper, we report our experimental results of Cheon’s algorithm on a pairing-friendly elliptic curve defined over GF(3&lt
      sup&gt
      127&lt
      /sup&gt
      ). Moreover, based on our experimental results, we estimate the required cost of Cheon’s algorithm to solve DLPwAI on some pairing-friendly elliptic curves over a finite field of characteristic 3. Our estimation implies that DLPwAI on a part of pairing-friendly curves can be solved at reasonable cost when the optimal parameter d is chosen.

      DOI: 10.2197/ipsjjip.19.441

      Scopus

      researchmap

    • Solving DLP with Auxiliary Input over an Elliptic Curve Used in TinyTate Library Peer-reviewed

      Yumi Sakemi, Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda

      INFORMATION SECURITY THEORY AND PRACTICE: SECURITY AND PRIVACY OF MOBILE DEVICES IN WIRELESS COMMUNICATION6633   116 - 127   2011

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

      The discrete logarithm problem with auxiliary input (DLPwAI) is a problem to find alpha from G, alpha G, alpha(d)G in an additive cyclic group generated by G of prime order r and a positive integer d dividing r - 1. The infeasibility of DLPwAI assures the security of some cryptographic schemes. In 2006, Cheon proposed a novel algorithm for solving DLPwAI. This paper shows our experimental results of Cheon's algorithm by implementing it with some speeding-up techniques. In fact, we succeeded to solve DLPwAI in a group with 128-bit order in 45 hours with a single PC on an elliptic curve defined over a prime finite field with 256-bit elements which is used in the TinyTate library.

      researchmap

    • Time estimation of Cheon's algorithm over elliptic curves on finite fields with characteristic 3 Peer-reviewed

      Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda

      Proceedings - 2011 5th International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing, IMIS 2011   594 - 596   2011

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:IEEE Computer Society  

      Cheon introduced a novel algorithm for solving the discrete logarithm problems with auxiliary input (DLPwAI). Since the infeasibility of DLPwAI assures the security of some cryptographic schemes, some implementational results have been reported. This paper estimates the required time for solving DLPwAI on elliptic curves over finite fields with characteristics 3 by extrapolating previous results. © 2011 IEEE.

      DOI: 10.1109/IMIS.2011.113

      Scopus

      researchmap

    • Experimental Results on Cheon's Algorithm Peer-reviewed

      Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda

      FIFTH INTERNATIONAL CONFERENCE ON AVAILABILITY, RELIABILITY, AND SECURITY: ARES 2010, PROCEEDINGS   625 - 628   2010

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:IEEE COMPUTER SOC  

      The discrete logarithm problem (DLP) is one of the familiar problem on which cryptographic schemes rely. In 2006, Cheon proposed an algorithm for solving DLP with auxiliary input which works better than conventional algorithms. This paper firstly reports experimental results on Cheon's algorithm for DLP on a supersingular elliptic curve defined over GF(3(127)), which is used for efficient pairing computation in practice. About 8 hours and 34 MByte database are required for the 1st step of Cheon's algorithm, and about 6 hours and 23 MByte data-base for the 2nd step. In total, about 14 hours are required for solving the problem. Our results imply that the security evaluation from a viewpoint of Cheon's algorithm is crucial.

      DOI: 10.1109/ARES.2010.55

      researchmap

    • The Elliptic Curve Discrete Logarithm Problems over the p-adic Field and Formal Groups Peer-reviewed

      Masaya Yasuda

      INFORMATION SECURITY PRACTICE AND EXPERIENCE, PROCEEDINGS6047   110 - 122   2010

      More details

      Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

      The hardness of the elliptic curve discrete logarithm problem (ECDLP) on a finite field is essential for the security of all elliptic curve cryptographic schemes. The ECDLP on a field K is as follows: given an elliptic curve E over K, a point S is an element of E(K), and a point T is an element of E(K) with T is an element of &lt; S &gt;, find the integer d such that T = dS. A number of ways of approaching the solution to the ECDLP on a finite field is known, for example, the MOV attack [5], and the anomalous attack [7,10]. In this paper, we propose an algorithm to solve the ECDLP on the p-adic field Q(p). Our method is to use the theory of formal groups associated to elliptic curves, which is used for the anomalous attack proposed by Smart [10], and Satoh and Araki [7].

      DOI: 10.1007/978-3-642-12827-1_9

      researchmap

    • TORSION POINTS OF ELLIPTIC CURVES WITH GOOD REDUCTION Peer-reviewed

      Masaya Yasuda

      KODAI MATHEMATICAL JOURNAL31 ( 3 ) 385 - 403   10 2008

      More details

      Language:English   Publishing type:Research paper (scientific journal)   Publisher:KINOKUNIYA CO LTD  

      We consider the torsion points of elliptc curves over certain number fields with good reduction everywhere.

      DOI: 10.2996/kmj/1225980443

      researchmap

    • The discrete logarithm problem on elliptic curves defined over Q (abstract only). Peer-reviewed

      Masaya Yasuda

      ACM Comm. Computer Algebra42 ( 1-2 ) 64 - 66   2008

    ▼display all

    Misc.

    • Introduction to algebraic approaches for solving isogeny path-finding problems Invited

      Masaya YASUDA, Kazuhiro YOKOYAMA

      RIMS Conference on Theory and Applications of Supersingular Curves and Supersingular Abelian Varieties   10 2020

      More details

      Authorship:Lead author  

      researchmap

    • Kohel-Lauter-Petit-Tignolアルゴリズムのsageにおける実装報告

      神戸祐太, 安田雅哉, 横山和弘

      日本応用数理学会2020年度年会(オンライン開催)   8 9 2020

      More details

    • 指数計算法による素体上のECDLP解読の高速化 (第26回日本数式処理学会大会報告)

      横田 祐貴, 工藤 桃成, 安田 雅哉

      数式処理 = Bulletin of the Japan Society for Symbolic and Algebraic Computation24 ( 2 ) 35 - 38   5 2018

      More details

      Language:Japanese   Publisher:日本数式処理学会  

      CiNii Article

      researchmap

    • Comparison of Babai's nearest plane and rounding algorithms in Laine-Lauter's key recovery attack for LWE

      Momonari Kudo, Yang Guo, Masaya Yasuda

      Proceedings of 2016 Symposium on Cryptography and Information Security (SCIS2016)2D4-1   1 2016

      More details

      Language:English  

      researchmap

    • Searchable Encryption : A Technology That Enables Searches on Encrypted Data

      KOGURE Jun, SHIMOYAMA Takeshi, YASUDA Masaya

      The Journal of the Institute of Electronics, Information, and Communication Engineers98 ( 3 ) 202 - 206   3 2015

      More details

      Language:Japanese   Publisher:The Institute of Electronics, Information and Communication Engineers  

      CiNii Article

      researchmap

    • Secret computation of purchase history data using somewhat homomorphic encryption

      Pacific journal of mathematics for industry : PJMI6   37 - 45   2014

      More details

      Language:English   Publisher:Institute of Mathematics for Industry, Kyushu University ; c2014-  

      CiNii Article

      researchmap

    • RL-003 A customer information analysis between enterprises using homomorphic encryption

      Yasuda Masaya, Shimoyama Takeshi, Yokoyama Kazuhiro, Kogure Jun

        12 ( 4 ) 15 - 22   20 8 2013

      More details

      Language:Japanese   Publisher:Forum on Information Technology  

      CiNii Article

      researchmap

    • On the attack against Gentry's somewhat homomorphic encryption using LLL algorithm (II)

      YAJIMA Jun, YASUDA Masaya, SHIMOYAMA Takeshi, KOGURE Jun

      IEICE technical report. Life intelligence and office information systems111 ( 286 ) 13 - 17   7 11 2011

      More details

      Language:Japanese   Publisher:The Institute of Electronics, Information and Communication Engineers  

      After Gentry proposed a concrete method for constructing a fully homomorphic encryption scheme, it becomes popular to research on applications with homomorphic encryption schemes. Gentry's construction starts from a somewhat homomorphic encryption (SHE) scheme, which supports limited evaluation over encrypted data. To analyze the relation between its evaluations and security, we attacked the lattice problem ensuring the security of Gentry's SHE scheme. In this paper, we mainly report our experimental results of attacking the lattice problem of 512 dimension using the LLL algorithm.

      CiNii Article

      researchmap

    • On the attack against Gentry's somewhat homomorphic encryption using LLL algorithm (II)

      YAJIMA Jun, YASUDA Masaya, SHIMOYAMA Takeshi, KOGURE Jun

      Technical report of IEICE. ISEC111 ( 285 ) 13 - 17   7 11 2011

      More details

      Language:Japanese   Publisher:The Institute of Electronics, Information and Communication Engineers  

      After Gentry proposed a concrete method for constructing a fully homomorphic encryption scheme, it becomes popular to research on applications with homomorphic encryption schemes. Gentry's construction starts from a somewhat homomorphic encryption (SHE) scheme, which supports limited evaluation over encrypted data. To analyze the relation between its evaluations and security, we attacked the lattice problem ensuring the security of Gentry's SHE scheme. In this paper, we mainly report our experimental results of attacking the lattice problem of 512 dimension using the LLL algorithm.

      CiNii Article

      researchmap

    • On the attack against Gentry's somewhat homomorphic encryption using LLL algorithm

        2011 ( 3 ) 576 - 581   12 10 2011

      More details

      Language:Japanese  

      CiNii Article

      researchmap

    • On the security of the fully-homomorphic encryption scheme based on ideal lattices

      YASUDA Masaya, YAJIMA Jun, SHIMOYAMA Takeshi, KOGURE Jun

      IEICE technical report111 ( 204 ) 43 - 50   2 9 2011

      More details

      Language:Japanese   Publisher:The Institute of Electronics, Information and Communication Engineers  

      A fully-homomorphic encryption is a public-key encryption that allows one to fully interact with encypted data without being able to decrypt, and it is expected to be applied for the area of cloud computing. In this paper, we consider the security of the fully-homomorphic encryption scheme based on ideal lattices. The security of this scheme relies on the infeasibility of the SSSP and the BDDP, which are computational mathematical problems. We here study on the relation between the parameters of this scheme and the infeasibility of the BDDP.

      CiNii Article

      researchmap

    • On random walks of Pollard's rho method for the ECDLP on Koblitz curves

      JMI : journal of math-for-industry3 ( 0 ) 107 - 112   2011

      More details

      Language:English   Publisher:Faculty of Mathematics, Kyushu University  

      Pollard's rho method is the asymptotically fastest known attack for the elliptic curve discrete logarithm problem (ECDLP) except special cases. It works by giving a pseudo-random sequence defined by an iteration function and then detecting a collision in the sequence. We note that the number of iterations before obtaining a collision is significant for the running time of the rho method and depends on the choice of an iteration function. For many iteration functions suitable for the ECDLP on elliptic curves except Koblitz curves, the number of iterations before obtaining a collision had been investigated. In this paper, we propose a new iteration function on Koblitz curves which is an extension of the iteration function proposed by Gallant et al. and analyze the performance on our iteration function experimentally.

      CiNii Article

      researchmap

      Other Link: http://hdl.handle.net/2324/20144

    • On the proportion of the curves constructed by Brezing-Weng in the pairing-friendly curves

        2010 ( 2 ) 7p   8 2010

      More details

      Language:Japanese  

      CiNii Article

      researchmap

    • On the proportion of the curves constructed by Brezing-Weng in the pairing-friendly curves

      YASUDA Takanori, YASUDA Masaya, SHIMOYAMA Takeshi, KOGURE Jun

      IEICE technical report110 ( 114 ) 181 - 187   24 6 2010

      More details

      Language:Japanese   Publisher:The Institute of Electronics, Information and Communication Engineers  

      The Brezing-Weng curves are a kind of pairing-friendly curves. In this paper, we investigate the proportion of the Brezing-Weng curves with a maximal cyclic subgroup of at most 160 bit prime order in the all pairing-friendly curves with the same condition. The number of the all pairing-friendly curves is given by the experiment and theoretical expectation.

      CiNii Article

      researchmap

    • On the proportion of the curves constructed by Brezing-Weng in the pairing-friendly curves

      YASUDA Takanori, YASUDA Masaya, SHIMOYAMA Takeshi, KOGURE Jun

      IEICE technical report110 ( 113 ) 181 - 187   24 6 2010

      More details

      Language:Japanese   Publisher:The Institute of Electronics, Information and Communication Engineers  

      The Brezing-Weng curves are a kind of pairing-friendly curves. In this paper, we investigate the proportion of the Brezing-Weng curves with a maximal cyclic subgroup of at most 160 bit prime order in the all pairing-friendly curves with the same condition. The number of the all pairing-friendly curves is given by the experiment and theoretical expectation.

      CiNii Article

      researchmap

    • On the proportion of the curves constructed by Brezing-Weng in the pairing-friendly curves

      YASUDA Takanori, YASUDA Masaya, SHIMOYAMA Takeshi, KOGURE Jun

      IEICE technical report110 ( 115 ) 181 - 187   24 6 2010

      More details

      Language:Japanese   Publisher:The Institute of Electronics, Information and Communication Engineers  

      The Brezing-Weng curves are a kind of pairing-friendly curves. In this paper, we investigate the proportion of the Brezing-Weng curves with a maximal cyclic subgroup of at most 160 bit prime order in the all pairing-friendly curves with the same condition. The number of the all pairing-friendly curves is given by the experiment and theoretical expectation.

      CiNii Article

      researchmap

    ▼display all

    Books and Other Publications

    • 格子暗号解読のための数学的基礎:格子基底簡約アルゴリズム入門

      青野良範, 安田雅哉( Role: Joint author)

      近代科学社  9 2019 

      More details

    Research Projects

    • 格子暗号の大規模解読実験と解読計算量評価

      日本学術振興会  科学研究費助成事業 基盤研究(B) 

      安田 雅哉, 鍛冶 静雄, 藤澤 克樹, 青野 良範

      More details

      4 2020 - 3 2024

      Grant number:20H04142

      Grant amount:\17550000 ( Direct Cost: \13500000 、 Indirect Cost:\4050000 )

      researchmap

    • 同種写像暗号に対する数理的技法による解読法の探求と計算量評価

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

      安田 雅哉

      More details

      6 2019 - 3 2022

      Grant number:19K22847

      Grant amount:\6500000 ( Direct Cost: \5000000 、 Indirect Cost:\1500000 )

      researchmap

    • Security Analysis of Post-Quantum Cryptography

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

      More details

      4 2017 - 3 2020

      Grant number:17K00185

      Grant amount:\4550000 ( Direct Cost: \3500000 、 Indirect Cost:\1050000 )

      researchmap

    • LWE問題の解読計算量評価と格子準同型暗号の安全パラメータ設定法の確立

      日本学術振興会  科学研究費助成事業 基盤研究(B) 

      安田 雅哉, 脇 隼人, 青野 良範

      More details

      4 2016 - 3 2020

      Grant number:16H02830

      Grant amount:\14040000 ( Direct Cost: \10800000 、 Indirect Cost:\3240000 )

      本研究の目的は、近年暗号分野で非常に注目されているLWE(Learning with Errors)問題ベースの格子暗号の解読計算量を解析すると共に、LWEベースの格子準同型暗号の安全パラメータの抽出を行い、暗号方式の性能評価を行うことである。2018年度の研究実績として、2017年度までに開発した格子基底簡約アルゴリズムを改良し、LWE問題の求解実験を行いその求解時間を元にLWE問題の計算困難性を解析した。また、LWEやその変種であるLWR(Learning with Rounding)問題を効率的に解くことができるModulus Switchingと呼ばれる技術を理論的に解析し、その技術が有効に働くLWEとLWRのパラメータ範囲を明らかにした。さらに、LWE問題を解くための代表的なアルゴリズムである格子点数え上げ(ENUM)アルゴリズムに対して、成功確率を固定したときの計算量の下限を理論的に示した。この理論により、暗号のパラメータ設定がこれまでの計算機実験による外挿を用いたもののみではなく、理論的な解読コストの下限から設定が可能となるため、長期的な安全性を確保することが可能となった。その継続研究として、量子ゲート型計算機上のENUMアルゴリズムおよびその計算量評価を与えた。上記成果と組み合わせることで、量子ENUMアルゴリズムの計算量の下限を計算することが可能となる。これにより、大規模な量子コンピュータが実用化された際にもLWE問題を安全性の根拠とした格子準同型暗号を安全に運用する基礎を与えることができる。一方で、LWEベースの準同型暗号ライブラリであるHElibを用いて、主成分分析や線形回帰などの代表的な統計処理を暗号化したまま効率的に計算する手法を開発し、プライバシー保護利活用技術としてLWE格子準同型暗号が利用可能か判定するための実装結果を与えた。

      researchmap