2024/10/09 更新

写真b

ヤスダ マサヤ
安田 雅哉
YASUDA Masaya
*大学が定期的に情報更新している項目(その他は、researchmapの登録情報を転載)
所属*
理学部 数学科
理学研究科 数学専攻 博士課程後期課程
理学研究科 数学専攻 博士課程前期課程
職名*
教授
学位
博士(数理科学) ( 東京大学 )
連絡先
メールアドレス
研究テーマ*
  • 現代暗号の安全性を支える数学問題の求解アルゴリズムを研究テーマとしている。具体的には、楕円曲線暗号の安全性を支える楕円曲線離散対数問題や、格子暗号の安全性を支える最短ベクトル問題などの格子問題に対して、効率的な求解法を研究すると共に、実際の計算機上でどこまで解けるのか試みている。

  • 研究キーワード
  • 格子基底簡約

  • 準同型暗号

  • 楕円曲線暗号

  • 格子暗号

  • 暗号数理

  • 学内職務経歴*
    • 2022年4月 - 現在 
      理学部   数学科   教授
    • 2022年4月 - 現在 
      理学研究科   数学専攻 博士課程前期課程   教授
    • 2022年4月 - 現在 
      理学研究科   数学専攻 博士課程後期課程   教授
    • 2020年4月 - 2022年3月 
      理学部   数学科   准教授
    • 2020年4月 - 2022年3月 
      理学研究科   数学専攻 博士課程前期課程   准教授
    • 2020年4月 - 2022年3月 
      理学研究科   数学専攻 博士課程後期課程   准教授

    ▼全件表示

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

    研究分野

    • 情報通信 / 情報セキュリティ  / 暗号解析

    • 自然科学一般 / 代数学

    経歴

    • 2022年4月 - 現在 
      立教大学   理学部数学科   教授

      詳細を見る

    • 2020年4月 - 現在 
      九州大学   マス・フォア・インダストリ研究所   客員教員

      詳細を見る

    • 2020年4月 - 2022年3月 
      立教大学   理学部 数学科   准教授

      詳細を見る

    • 2020年4月 - 2022年3月 
      立教大学   理学研究科 数学専攻博士課程前期課程   准教授

      詳細を見る

    • 2015年4月 - 2020年3月 
      九州大学   マス・フォア・インダストリ研究所   准教授

      詳細を見る

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

      詳細を見る

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

      詳細を見る

    ▼全件表示

    学歴

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

      詳細を見る

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

      詳細を見る

    • 1998年4月 - 2002年3月 
      京都大学   理学部

      詳細を見る

    委員歴

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

      詳細を見る

      団体区分:学協会

      researchmap

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

      詳細を見る

      団体区分:学協会

      researchmap

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

      詳細を見る

      団体区分:学協会

      researchmap

    受賞

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

      詳細を見る

    論文

    • Computing endomorphism rings of supersingular elliptic curves by finding cycles in concatenated supersingular isogeny graphs 査読有り

      Yuta Kambe, Akira Katayama, Yusuke Aikawa, Yuki Ishihara, Masaya Yasuda, Kazuhiro Yokoyama

      Commentarii Mathematici Universitatis Sancti Pauli72 ( 1 ) 19 - 42   2024年10月

      詳細を見る

      記述言語:英語   掲載種別:研究論文(学術雑誌)  

      researchmap

    • Experimental Analysis of Integer Factorization Methods Using Lattices 査読有り

      Arata Sato, Aurélien Auzemery, Akira Katayama, Masaya Yasuda

      Lecture Notes in Computer Science14977   142 - 157   2024年9月13日

      詳細を見る

      担当区分:最終著者, 責任著者   記述言語:英語   掲載種別:論文集(書籍)内論文   出版者・発行元:Springer Nature Singapore  

      DOI: 10.1007/978-981-97-7737-2_8

      researchmap

    • Computing a Basis of the Set of Isogenies Between Two Supersingular Elliptic Curves 査読有り

      Akira Katayama, Masaya Yasuda

      Lecture Notes in Computer Science14938   178 - 192   2024年8月21日

      詳細を見る

      担当区分:最終著者   記述言語:英語   掲載種別:論文集(書籍)内論文   出版者・発行元:Springer Nature Switzerland  

      DOI: 10.1007/978-3-031-69070-9_11

      researchmap

    • Parallel DeepBKZ 2.0: Development of parallel DeepBKZ reduction with large blocksizes 査読有り

      Satoshi Nakamura, Nariaki Tateiwa, Masaya Yasuda, Katsuki Fujisawa

      accepted at CREST BOOK: Mathematical Foundations for Post- Quantum Cryptography   2024年

      詳細を見る

      担当区分:責任著者   記述言語:英語   掲載種別:研究論文(その他学術会議資料等)  

      researchmap

    • Expanded lattices for solving ring-based LWE and NTRU problems 査読有り

      Satoshi Nakamura, Masaya Yasuda

      accepted at CREST BOOK: Mathematical Foundations for Post- Quantum Cryptography   2024年

      詳細を見る

      担当区分:最終著者   記述言語:英語   掲載種別:研究論文(その他学術会議資料等)  

      researchmap

    • On the feasibility of computing constructive Deuring correspondence 査読有り

      Yuta Kambe, Yasushi Takahashi, Masaya Yasuda, Kazuhiro Yokoyama

      Banach Center Publications: Post-proceedings of Number-Theoretic Methods in Cryptology (NuTMiC 2021)126   105 - 121   2023年12月

      詳細を見る

      担当区分:責任著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)  

      DOI: 10.4064/bc126-7

      researchmap

    • Development and analysis of massive parallelization of a lattice basis reduction algorithm 査読有り

      Nariaki Tateiwa, Yuji Shinano, Masaya Yasuda, Shizuo Kaji, Keiichiro Yamamura, Katsuki Fujisawa

      Japan Journal of Industrial and Applied Mathematics41 ( 1 ) 13 - 56   2023年4月3日

      詳細を見る

      記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Springer Science and Business Media LLC  

      DOI: 10.1007/s13160-023-00580-z

      researchmap

      その他リンク: https://link.springer.com/article/10.1007/s13160-023-00580-z/fulltext.html

    • Computing the Brauer group of the product of two elliptic curves over a finite field 査読有り

      Akira Katayama, Masaya Yasuda

      Japan Journal of Industrial and Applied Mathematics (JJIAM), Online First   2023年

      詳細を見る

      担当区分:最終著者   記述言語:英語   掲載種別:研究論文(学術雑誌)  

      researchmap

    • Solving the search-LWE problem over projected lattices 査読有り

      Satoshi Nakamura, Nariaki Tateiwa, Masaya Yasuda, Katsuki Fujisawa

      Discrete Applied Mathematics318   69 - 81   2022年9月

      詳細を見る

      担当区分:責任著者   記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Elsevier BV  

      DOI: 10.1016/j.dam.2022.04.018

      researchmap

    • Introduction to algebraic approaches for solving isogeny path-finding problems 査読有り

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

      RIMS Kˆokyˆuroku BessatsuB90   169 - 184   2022年6月

      詳細を見る

      担当区分:責任著者   記述言語:英語   掲載種別:研究論文(学術雑誌)  

      researchmap

    • CMAP-LAP: Configurable Massively Parallel Solver for Lattice Problems 査読有り

      Nariaki Tateiwa, Yuji Shinano, Keiichiro Yamamura, Akihiro Yoshida, Shizuo Kaji, Masaya Yasuda, Katsuki Fujisawa

      2021 IEEE 28th International Conference on High Performance Computing, Data, and Analytics (HiPC)   42 - 52   2021年12月

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:IEEE  

      Lattice problems are a class of optimization problems that are notably hard. There are no classical or quantum algorithms known to solve these problems efficiently. Their hardness has made lattices a major cryptographic primitive for post-quantum cryptography. Several different approaches have been used for lattice problems with different computational profiles; some suffer from super-exponential time, and others require exponential space. This motivated us 10 develop a novel lattice problem solver, CMAP-LAP, based on the clever coordination of different algorithms that run massively in parallel. With our flexible framework, heterogeneous modules run asynchronously in parallel on a large-scale distributed system while exchanging information, which drastically boosts the overall performance. We also implement full checkpoint-and-restart functionality, which is vital to high-dimensional lattice problems. CMAP-LAP facilitates the implementation of large-scale parallel strategies for lattice problems since all the functions are designed to he customizable and abstract. Through numerical experiments with up to 103,680 cores, we evaluated the performance and stability of our system and demonstrated its high capability for future massive-scale experiments.

      DOI: 10.1109/hipc53243.2021.00018

      researchmap

    • Dynamic self-dual DeepBKZ lattice reduction with free dimensions and its implementation 査読有り

      Satoshi Nakamura, Masaya Yasuda

      Discrete Applied Mathematics304   220 - 229   2021年12月

      詳細を見る

      担当区分:責任著者   記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Elsevier BV  

      DOI: 10.1016/j.dam.2021.07.035

      researchmap

    • A Trace Map Attack Against Special Ring-LWE Samples 査読有り

      Yasuhiko Ikematsu, Satoshi Nakamura, Masaya Yasuda

      Advances in Information and Computer Security   3 - 22   2021年9月

      詳細を見る

      担当区分:最終著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer International Publishing  

      DOI: 10.1007/978-3-030-85987-9_1

      researchmap

    • Solving the constructive Deuring correspondence via the Kohel-Lauter-Petit-Tignol algorithm 査読有り

      Yuta Kambe, Masaya Yasuda, Masayuki Noro, Kazuhiro Yokoyama, Yusuke Aikawa, Katsuyuki Takashima, Momonari Kudo

      Mathematical Cryptology (Special Issue of MathCrypt 2021)1 ( 2 ) 10 - 24   2021年8月

      詳細を見る

      担当区分:責任著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)  

      researchmap

    • Implementation report of the Kohel-Lauter-Petit-Tignol algorithm for the constructive Deuring correspondence 査読有り

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

      International Conference on Mathematics and Computing (ICMC 2021)   2021年3月

      詳細を見る

      担当区分:責任著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)  

      researchmap

    • An Extension of Kannan’s Embedding for Solving Ring-Based LWE Problems 査読有り

      Satoshi Nakamura, Masaya Yasuda

      Cryptography and Coding   201 - 219   2021年

      詳細を見る

      担当区分:責任著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer International Publishing  

      DOI: 10.1007/978-3-030-92641-0_10

      researchmap

    • A survey of solving SVP algorithms and recent strategies for solving the SVP challenge 招待有り 査読有り

      Masaya Yasuda

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

      詳細を見る

      掲載種別:研究論文(国際会議プロシーディングス)  

      researchmap

    • Symbolic Computation of Isogenies of Elliptic Curves by Vélu’s Formula 査読有り

      Masayuki NORO, Masaya YASUDA, Kazuhiro YOKOYAMA

      COMMENTARII MATHEMATICI UNIVERSITATIS SANCTI PAULI68   93 - 127   2020年12月

      詳細を見る

      記述言語:英語   掲載種別:研究論文(大学,研究機関等紀要)  

      researchmap

    • Massive Parallelization for Finding Shortest Lattice Vectors Based on Ubiquity Generator Framework 査読有り

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

      SC20: International Conference for High Performance Computing, Networking, Storage and Analysis2020-November   1 - 15   2020年11月

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:IEEE  

      Lattice-based cryptography has received attention as a next-generation encryption technique, because it is believed to be secure against attacks by classical and quantum computers. Its essential security depends on the hardness of solving the shortest vector problem (SVP). In the cryptography, to determine security levels, it is becoming significantly more important to estimate the hardness of the SVP by high-performance computing. In this study, we develop the world's first distributed and asynchronous parallel SVP solver, the MAssively Parallel solver for SVP (MAP-SVP). It can parallelize algorithms for solving the SVP by applying the Ubiquity Generator framework, which is a generic framework for branch-and-bound algorithms. The MAP-SVP is suitable for massive-scale parallelization, owing to its small memory footprint, low communication overhead, and rapid checkpoint and restart mechanisms. We demonstrate its performance and scalability of the MAP-SVP by using up to 100,032 cores to solve instances of the Darmstadt SVP Challenge.

      DOI: 10.1109/sc41405.2020.00064

      Scopus

      researchmap

    • Fast secure matrix multiplications over ring-based homomorphic encryption 査読有り

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

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

      詳細を見る

      担当区分:最終著者, 責任著者   掲載種別:研究論文(学術雑誌)   出版者・発行元:Informa UK Limited  

      DOI: 10.1080/19393555.2020.1836288

      researchmap

    • Dynamic self-dual DeepBKZ lattice reduction with free dimensions 査読有り

      Satoshi Nakamura, Yasuhiko Ikematsu, Masaya Yasuda

      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   2020年9月

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)  

      researchmap

    • Solving the search-LWE problem by lattice reduction over projected bases 査読有り

      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   29 - 42   2020年9月

      詳細を見る

      掲載種別:研究論文(国際会議プロシーディングス)  

      DOI: 10.1007/978-981-15-8061-1_3

      researchmap

      その他リンク: https://dblp.uni-trier.de/db/conf/icmc2/icmc2020.html#NakamuraTKIYF20

    • Analysis of DeepBKZ reduction for finding short lattice vectors. 査読有り

      Masaya Yasuda, Satoshi Nakamura, Junpei Yamaguchi

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

      詳細を見る

      担当区分:筆頭著者, 責任著者   記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Springer Science and Business Media LLC  

      DOI: 10.1007/s10623-020-00765-4

      researchmap

    • Impact of the modulus switching technique on some attacks against learning problems. 査読有り

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

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

      詳細を見る

      掲載種別:研究論文(学術雑誌)  

      DOI: 10.1049/iet-ifs.2019.0220

      researchmap

    • Hybrid Meet-in-the-Middle Attacks for the Isogeny Path-Finding Problem. 査読有り

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

      Proceedings of the 7th on ASIA Public-Key Cryptography Workshop(APKC@AsiaCCS)   36 - 44   2020年

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:ACM  

      DOI: 10.1145/3384940.3388956

      researchmap

      その他リンク: https://dblp.uni-trier.de/db/conf/ccs/asiapkc2020.html#IkematsuFKYTY20

    • Algebraic approaches for solving isogeny problems of prime power degrees. 査読有り 国際誌

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

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

      詳細を見る

      記述言語:英語   掲載種別:研究論文(学術雑誌)  

      DOI: 10.1515/jmc-2020-0072

      researchmap

    • Complexity bounds on Semaev's naive index calculus method for ECDLP. 査読有り

      Kazuhiro Yokoyama, Masaya Yasuda, Yasushi Takahashi, Jun Kogure

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

      詳細を見る

      掲載種別:研究論文(学術雑誌)  

      DOI: 10.1515/jmc-2019-0029

      researchmap

    • Self-dual DeepBKZ for finding short lattice vectors. 査読有り

      Masaya Yasuda

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

      詳細を見る

      担当区分:筆頭著者, 責任著者   掲載種別:研究論文(学術雑誌)   出版者・発行元: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. 査読有り

      Masaya Yasuda, Junpei Yamaguchi

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

      詳細を見る

      掲載種別:研究論文(学術雑誌)  

      DOI: 10.1007/s10623-019-00634-9

      researchmap

    • Security analysis of cryptosystems using short generators over ideal lattices 査読有り

      Shinya Okumura, Shingo Sugiyama, Masaya Yasuda, Tsuyoshi Takagi

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

      詳細を見る

      記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元: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

    • Explicit formula for gram-schmidt vectors in LLL with deep insertions and its applications 査読有り

      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年

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元: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. 査読有り

      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年

      詳細を見る

      掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:ACM  

      DOI: 10.1145/3267323.3268952

      researchmap

      その他リンク: https://dblp.uni-trier.de/db/conf/wpes/wpes2018.html#RatheeMY18

    • Acceleration of Index Calculus for Solving ECDLP over Prime Fields and Its Limitation. 査読有り

      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年

      詳細を見る

      掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

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

      researchmap

      その他リンク: https://dblp.uni-trier.de/db/conf/cans/cans2018.html#KudoYTY18

    • Solving LWR via BDD Strategy: Modulus Switching Approach. 査読有り

      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年

      詳細を見る

      掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

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

      researchmap

      その他リンク: https://dblp.uni-trier.de/db/conf/cans/cans2018.html#LeMDY18

    • Development of a Dual Version of DeepBKZ and Its Application to Solving the LWE Challenge. 査読有り

      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年

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元: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

      その他リンク: https://dblp.uni-trier.de/db/conf/africacrypt/africacrypt2018.html#YasudaYON18

    • Practical Limit of Index Calculus Algorithms for ECDLP over Prime Fields 査読有り 国際誌

      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   2017年9月

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)  

      researchmap

    • Application of mixed integer quadratic program to shortest vector problems. 査読有り

      Keiji Kimura, Hayato Waki, Masaya Yasuda

      JSIAM Lett.9   65 - 68   2017年

      詳細を見る

      掲載種別:研究論文(学術雑誌)  

      DOI: 10.14495/jsiaml.9.65

      researchmap

    • Choosing Parameters for the Subfield Lattice Attack Against Overstretched NTRU. 査読有り

      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年

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元: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

      その他リンク: https://dblp.uni-trier.de/db/conf/isw/isc2017.html#DuongYT17

    • Recovering Attacks Against Linear Sketch in Fuzzy Signature Schemes of ACNS 2015 and 2016. 査読有り

      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年

      詳細を見る

      掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

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

      researchmap

      その他リンク: https://dblp.uni-trier.de/db/conf/ispec/ispec2017.html#YasudaSTAYY17

    • Enhancement for Secure Multiple Matrix Multiplications over Ring-LWE Homomorphic Encryption. 査読有り

      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年

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元: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

      その他リンク: https://dblp.uni-trier.de/db/conf/ispec/ispec2017.html#MishraDY17

    • Secure and Efficient Pairing at 256-Bit Security Level. 査読有り

      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年

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元: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

      その他リンク: https://dblp.uni-trier.de/db/conf/acns/acns2017.html#KiyomuraIKYTK17

    • Analysis of decreasing squared-sum of Gram-Schmidt lengths for short lattice vectors. 査読有り

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

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

      詳細を見る

      掲載種別:研究論文(学術雑誌)  

      DOI: 10.1515/jmc-2016-0008

      researchmap

    • Secure Hamming distance computation for biometrics using ideal-lattice and ring-LWE homomorphic encryption. 査読有り

      Masaya Yasuda

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

      詳細を見る

      記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元: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

    • Computational hardness of IFP and ECDLP 査読有り

      Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Tetsuya Izu

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

      詳細を見る

      記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元: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 査読有り

      Dung Hoang Duong, Pradeep Kumar Mishra, Masaya Yasuda

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

      詳細を見る

      記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元: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

    • 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年

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元: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

    • Comprehensive and Improved Secure Biometric System Using Homomorphic Encryption 査読有り

      Avradip Mandal, Arnab Roy, Masaya Yasuda

      DATA PRIVACY MANAGEMENT, AND SECURITY ASSURANCE9481   183 - 198   2016年

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元: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

    • Torsion points and reduction of elliptic curves 査読有り

      Masaya Yasuda

      ACTA ARITHMETICA176 ( 1 ) 89 - 100   2016年

      詳細を見る

      記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:POLISH ACAD SCIENCES INST MATHEMATICS-IMPAN  

      DOI: 10.4064/aa8425-6-2016

      researchmap

    • Practical Analysis of Key Recovery Attack Against Search-LWE Problem 査読有り

      Momonari Kudo, Junpei Yamaguchi, Yang Guo, Masaya Yasuda

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

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元: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

    • Biometric key-binding using lattice masking†. 査読有り

      Masaya Yasuda, Yuka Sugimura

      Security and Communication Networks8 ( 18 ) 3405 - 3414   2015年12月

      詳細を見る

      記述言語:英語   掲載種別:研究論文(学術雑誌)  

      DOI: 10.1002/sec.1267

      researchmap

    • Ramification of the Kummer extension generated from torsion points of elliptic curves 査読有り

      Masaya Yasuda

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

      詳細を見る

      記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元: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

    • 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 International Workshop on Security in Cloud Computing, SCC@ASIACCS '15, Singapore, Republic of Singapore, April 14, 2015   53 - 61   2015年

      詳細を見る

      掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:ACM  

      DOI: 10.1145/2732516.2732521

      researchmap

    • Secure Statistical Analysis Using RLWE-Based Homomorphic Encryption. 査読有り

      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年

      詳細を見る

      掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

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

      researchmap

    • New packing method in somewhat homomorphic encryption and its applications. 査読有り

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

      Security and Communication Networks8 ( 13 ) 2194 - 2213   2015年

      詳細を見る

      掲載種別:研究論文(学術雑誌)  

      DOI: 10.1002/sec.1164

      researchmap

    • 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 20138247   34 - 50   2014年

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元: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

    • 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 Cryptology8 ( 3 ) 305 - 329   2014年

      詳細を見る

      掲載種別:研究論文(学術雑誌)  

      DOI: 10.1515/jmc-2013-0024

      researchmap

    • 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 20148544   338 - 353   2014年

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元: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

    • A Biometric Key-Binding Scheme Using Lattice Masking 査読有り

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

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

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元: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

      その他リンク: http://dblp.uni-trier.de/db/conf/biosig/biosig2014.html#conf/biosig/SugimuraYYAS14

    • KUMMER GENERATORS AND TORSION POINTS OF ELLIPTIC CURVES WITH BAD REDUCTION AT SOME PRIMES 査読有り

      Masaya Yasuda

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

      詳細を見る

      記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元: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

    • Secure pattern matching using somewhat homomorphic encryption. 査読有り

      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年

      詳細を見る

      掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:ACM  

      DOI: 10.1145/2517488.2517497

      researchmap

    • Packed Homomorphic Encryption Based on Ideal Lattices and Its Application to Biometrics. 査読有り

      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年

      詳細を見る

      掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

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

      researchmap

    • Torsion points of elliptic curves with bad reduction at some primes II 査読有り

      Masaya Yasuda

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

      詳細を見る

      記述言語:英語   掲載種別:研究論文(学術雑誌)  

      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

    • On the number of the pairing-friendly curves

      Takanori Yasuda, Masaya Yasuda, Takeshi Shimoyama, Jun Kogure

      International Journal of Pure and Applied Mathematics77 ( 1 ) 11 - 15   2012年

      詳細を見る

      記述言語:英語   掲載種別:研究論文(学術雑誌)  

      In pairing-based cryptography, it is necessary to choose an elliptic curve with a small embedding degree and a large prime-order subgroup, which is called a pairing-friendly curve. In this paper, we study the number of the pairing-friendly curves with a given large prime-order subgroup. © 2012 Academic Publications, Ltd.

      Scopus

      researchmap

    • On elliptic curves whose 3-torsion subgroup splits as μ3 ⊕ ℤ/3ℤ 査読有り

      Masaya Yasuda

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

      詳細を見る

      記述言語:英語   掲載種別:研究論文(学術雑誌)  

      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

    • Solving a DLP with Auxiliary Input with the ρ-Algorithm. 査読有り

      Yumi Sakemi, Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda

      Information Security Applications - 12th International Workshop, WISA 2011, Jeju Island, Korea, August 22-24, 2011. Revised Selected Papers7115   98 - 108   2012年

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

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

      Scopus

      researchmap

    • On the Strength Comparison of the ECDLP and the IFP. 査読有り

      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年

      詳細を見る

      掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

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

      researchmap

    • Analysis of Lattice Reduction Attack against the Somewhat Homomorphic Encryption Based on Ideal Lattices. 査読有り

      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年

      詳細を見る

      掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

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

      researchmap

    • Solving a Discrete Logarithm Problem with Auxiliary Input on a 160-Bit Elliptic Curve 査読有り

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

      PUBLIC KEY CRYPTOGRAPHY - PKC 20127293   595 - 608   2012年

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元: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 査読有り

      Masaya Yasuda

      KODAI MATHEMATICAL JOURNAL34 ( 1 ) 55 - 70   2011年3月

      詳細を見る

      記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元: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

    • Experimental Analysis of Cheon's Algorithm against Pairing-friendly Curves

      Izu Tetsuya, Takenaka Masahiko, Yasuda Masaya

      Information and Media Technologies6 ( 4 ) 1175 - 1184   2011年

      詳細を見る

      記述言語:英語   出版者・発行元:Information and Media Technologies 編集運営会議  

      Let G be an additive group generated by an element <i>G</i> of prime order <i>r</i>. The discrete logarithm problem with auxiliary input (DLPwAI) is a problem to find &alpha; on inputs <i>G</i>, &alpha;<i>G</i>, &alpha;<i><sup>d</sup>G</i> &isin; G for a positive integer <i>d</i> dividing <i>r</i>-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<sup>127</sup>). 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 <i>d</i> is chosen.

      DOI: 10.11185/imt.6.1175

      CiNii Article

      researchmap

    • Time estimation of Cheon's algorithm over elliptic curves on finite fields with characteristic 3 査読有り

      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年

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元: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 analysis of cheon’s algorithm against pairing-friendly curves 査読有り

      Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda

      Journal of Information Processing19   441 - 450   2011年

      詳細を見る

      記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元: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

    • Experimantal Analysis of Cheon's Algorithm against Pairing-Friendly Curves 査読有り

      Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda

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

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元: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

    • Solving DLP with Auxiliary Input over an Elliptic Curve Used in TinyTate Library 査読有り

      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年

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元: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

    • Experimental Results on Cheon's Algorithm 査読有り

      Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda

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

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元: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 査読有り

      Masaya Yasuda

      INFORMATION SECURITY PRACTICE AND EXPERIENCE, PROCEEDINGS6047   110 - 122   2010年

      詳細を見る

      記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元: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 査読有り

      Masaya Yasuda

      KODAI MATHEMATICAL JOURNAL31 ( 3 ) 385 - 403   2008年10月

      詳細を見る

      記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元: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). 査読有り

      Masaya Yasuda

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

      詳細を見る

    ▼全件表示

    MISC

    • 同種写像グラフ上のサイクル探索による同種写像求解法の高効率化

      神戸祐太, 片山瑛, 相川勇輔, 石原侑樹, 安田雅哉, 横山和弘

      2024年暗号と情報セキュリティシンポジウム(SCIS2024)   2024年1月

      詳細を見る

      記述言語:日本語  

      researchmap

    • 近似最近ベクトル探索と埋め込み法を用いた格子による素因数分解法の実装報告

      佐藤新, Auzemery Aurelien, 片山瑛, 安田雅哉

      2024年暗号と情報セキュリティシンポジウム(SCIS2024)   2024年1月

      詳細を見る

      記述言語:日本語  

      researchmap

    • FALCON におけるマスキング実装の提案

      片山瑛, 中邑聡史, 上野真奈, 安田雅哉

      2024年暗号と情報セキュリティシンポジウム(SCIS2024)   2024年1月

      詳細を見る

      記述言語:日本語  

      researchmap

    • ハイブリッドStreaming法によるCRYSTALS-Dilithiumのリソース最適化

      高橋康, 西田直央, 海上勇二, 豊永三朗, 池松泰彦, 縫田光司, 安田雅哉

      2024年暗号と情報セキュリティシンポジウム(SCIS2024)   2024年1月

      詳細を見る

      記述言語:日本語  

      researchmap

    • CSIDHにおける同値な秘密鍵の探索と秘密鍵空間の解析

      高橋康, 安田雅哉

      2023年コンピュータセキュリティシンポジウム(CSS 2023)   2023年11月

      詳細を見る

      担当区分:最終著者   記述言語:日本語   掲載種別:機関テクニカルレポート,技術報告書,プレプリント等  

      researchmap

    • Solving the supersingular isogeny problem over Fp via the Deuring correspondence 査読有り

      Yuta Kambe, Akira Katayama, Yusuke Aikawa, Yuki Ishihara, Masaya Yasuda, Kazuhiro Yokoyama

      5-th International Workshop on Mathematical Cryptology (MathCrypt 2023)   2023年8月

      詳細を見る

      担当区分:責任著者   記述言語:英語   掲載種別:会議報告等  

      researchmap

    • 有限体上の通常楕円曲線の自己準同型環の生成元計算

      片山瑛, 安田雅哉

      日本応用数理学会第19回研究部会連合発表会 「数論アルゴリズムとその応用」   2023年3月

      詳細を見る

      担当区分:最終著者   記述言語:日本語   掲載種別:研究発表ペーパー・要旨(全国大会,その他学術会議)  

      researchmap

    • 超特異楕円曲線の自己準同型環計算の実装報告

      神戸祐太, 片山瑛, 相川勇輔, 石原侑樹, 安田雅哉, 横山和弘

      2023年暗号と情報セキュリティシンポジウム(SCIS2023)   2023年1月

      詳細を見る

      記述言語:日本語   掲載種別:会議報告等  

      researchmap

    • 探索Module-LWE問題に対する格子攻撃の実験報告

      中邑聡史, 片山瑛, 安田雅哉

      2023年暗号と情報セキュリティシンポジウム(SCIS2023)   2023年1月

      詳細を見る

      担当区分:最終著者   記述言語:日本語   掲載種別:会議報告等  

      researchmap

    • 構成的Deuring対応の計算可能性について

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

      日本応用数理学会2022年度年会「数論アルゴリズムとその応用」(JANT)セッション   2022年9月

      詳細を見る

      記述言語:日本語   掲載種別:研究発表ペーパー・要旨(全国大会,その他学術会議)  

      researchmap

    • ρ法による超特異同種写像グラフにおけるサイクル探索

      神戸祐太, 片山瑛, 相川勇輔, 安田雅哉, 横山和弘

      日本応用数理学会2022年度年会「数論アルゴリズムとその応用」(JANT)セッション   2022年9月

      詳細を見る

      記述言語:日本語   掲載種別:研究発表ペーパー・要旨(全国大会,その他学術会議)  

      researchmap

    • 有限体上の楕円曲線の積によるアーベル曲面のブラウアー群の位数計算

      片山瑛, 安田雅哉

      日本応用数理学会2022年度年会「数論アルゴリズムとその応用」(JANT)セッション   2022年9月

      詳細を見る

      担当区分:最終著者   記述言語:日本語   掲載種別:研究発表ペーパー・要旨(全国大会,その他学術会議)  

      researchmap

    • NTRU格子の拡張と格子攻撃

      中邑聡史, 安田雅哉

      2022年暗号と情報セキュリティシンポジウム(SCIS2022)   2022年1月

      詳細を見る

      掲載種別:会議報告等  

      researchmap

    • 適切な素数選択によるKLPTアルゴリズムを利用した同種写像構成計算

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

      2022年暗号と情報セキュリティシンポジウム(SCIS2022)   2022年1月

      詳細を見る

      掲載種別:会議報告等  

      researchmap

    • SIKEに対するvOW法の内部関数の新計算手法

      神戸祐太, 高橋康, 相川勇輔, 工藤桃成, 安田雅哉, 高島克幸, 横山和弘

      2022年暗号と情報セキュリティシンポジウム(SCIS2022)   2022年1月

      詳細を見る

      担当区分:責任著者   掲載種別:会議報告等  

      researchmap

    • Selection of primes in the KLPT algorithm for construction of fast isogeny (poster)

      Yasushi Takahashi, Yuta Kambe, Masaya Yasuda, Kazuhiro Yokoyama

      poster session in IWSEC 2021   2021年9月

      詳細を見る

      記述言語:英語   掲載種別:研究発表ペーパー・要旨(国際会議)  

      researchmap

    • 探索Ring-LWE問題に対するKannan の埋め込み法の拡張

      中邑聡史, 安田雅哉

      日本応用数理学会2021年度年会「数論アルゴリズムとその応用」(JANT)セッション(オンライン開催)   2021年9月

      詳細を見る

      記述言語:日本語  

      researchmap

    • Kohel-Lauter-Petit-Tignolアルゴリズムの構成的Deuring対応への適用

      神戸祐太, 相川勇輔, 工藤桃成, 安田雅哉, 高島克幸, 横山和弘

      2021年暗号と情報セキュリティシンポジウム(SCIS2021)   2021年1月

      詳細を見る

      記述言語:日本語   掲載種別:研究発表ペーパー・要旨(全国大会,その他学術会議)  

      researchmap

    • 代数構造を持つ格子上の最短ベクトル探索アルゴリズムの開発

      中邑聡史, 安田雅哉

      2021年暗号と情報セキュリティシンポジウム(SCIS2021)   2021年1月

      詳細を見る

      記述言語:日本語   掲載種別:研究発表ペーパー・要旨(全国大会,その他学術会議)  

      researchmap

    • Introduction to algebraic approaches for solving isogeny path-finding problems 招待有り

      Masaya YASUDA, Kazuhiro YOKOYAMA

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

      詳細を見る

      担当区分:筆頭著者  

      researchmap

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

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

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

      詳細を見る

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

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

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

      詳細を見る

      記述言語:日本語   出版者・発行元:日本数式処理学会  

      CiNii Article

      researchmap

    • Relation between torsion points and reduction of elliptic curves over number fields (計算代数システムによる新しい数学の開拓と進展)

      Yasuda Masaya

      数理解析研究所講究録 ( 2012 ) 41 - 65   2016年12月

      詳細を見る

      記述言語:英語   出版者・発行元:京都大学数理解析研究所  

      CiNii Article

      researchmap

    • 完全準同形暗号の応用 (小特集 完全準同形暗号の研究動向)

      安田 雅哉

      電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers99 ( 12 ) 1167 - 1175   2016年12月

      詳細を見る

      記述言語:日本語   出版者・発行元:電子情報通信学会  

      CiNii Article

      researchmap

    • 円分体に対するイデアル格子上の短い生成元の復元可能性について (情報セキュリティ)

      奥村 伸也, 安田 雅哉, 高木 剛

      電子情報通信学会技術研究報告 = IEICE technical report : 信学技報116 ( 35 ) 25 - 32   2016年5月19日

      詳細を見る

      記述言語:日本語   出版者・発行元:電子情報通信学会  

      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   2016年1月

      詳細を見る

      記述言語:英語  

      researchmap

    • 暗号化したまま検索が可能な秘匿検索技術 (小特集 個人データの活用とプライバシー保護)

      小暮 淳, 下山 武司, 安田 雅哉

      電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers98 ( 3 ) 202 - 206   2015年3月

      詳細を見る

      記述言語:日本語   出版者・発行元:一般社団法人電子情報通信学会  

      クラウドコンピューティングの普及やビッグデータ分析技術の発展に伴い,大量のデータを分析することにより新たな知見を得て,新しいサービスを提供することが広まっている.一方で,大量のデータに含まれるプライバシー情報を保護することが求められている.データの利活用とプライバシー保護を両立させるため,データを秘匿したまま分析・検索する技術が,現在盛んに研究されている.本稿では,データを秘匿したまま検索が可能な秘匿検索技術の概要を紹介する.

      CiNii Article

      researchmap

    • AI-1-2 (完全)準同型暗号の応用(AI-1.最新暗号ツールの研究動向:完全準同型暗号、多線形写像、難読化,依頼シンポジウム,ソサイエティ企画)

      安田 雅哉

      電子情報通信学会総合大会講演論文集2015   "SS - 71"   2015年2月24日

      詳細を見る

      記述言語:日本語   出版者・発行元:一般社団法人電子情報通信学会  

      CiNii Article

      researchmap

    • 準同型暗号を用いた秘匿生体認証に対する安全性について(その2) (技術と社会・倫理)

      酒見 由美, 武仲 正彦, 鳥居 直哉, 安田 雅哉

      電子情報通信学会技術研究報告 = IEICE technical report : 信学技報114 ( 116 ) 293 - 300   2014年7月3日

      詳細を見る

      記述言語:日本語   出版者・発行元:一般社団法人電子情報通信学会  

      ID/パスワードの使い回し問題により,生体情報を使った認証への注目が集まっている.生体情報は個人を特定できるセンシティブな情報であることから,準同型暗号により生体情報を暗号化したまま認証処理を行う秘匿生体認証方式が提案されている.著者等はこれまでに,Hattori et al.が提案した準同型暗号を用いたキャンセラブル生体認証方式に対し,二値符号が利用される場合に,なりすまし攻撃,テンプレート復元攻撃が可能であることを報告し,それらに対する対策を検討した.さらに,著者らは,Yasuda et al.が提案した準同型暗号を用いた秘匿生体認証方式に対するなりすまし攻撃,テンプレート復元攻撃が可能であることを報告した.本稿では,Yasuda et al.の準同型暗号を用いた秘匿生体認証方式に対し,Hattori et al.方式への攻撃に対する対策として検討した,特徴ベクトルが二値符号であることを確認する対策の適用可能性について検討する.その結果,二値符号であることを確認する対策については,Yasuda et al.の方式へ単純に適用できないということが分かった.そこで,新たにユーザ乱数をXorマスクする対策,乗算マスクする対策,加算マスクする対策を提案し,その効果について検討を行う.

      CiNii Article

      researchmap

    • 準同型暗号を用いた秘匿生体認証に対する安全性について(その1) (技術と社会・倫理)

      酒見 由美, 武仲 正彦, 鳥居 直哉, 安田 雅哉

      電子情報通信学会技術研究報告 = IEICE technical report : 信学技報114 ( 116 ) 287 - 292   2014年7月3日

      詳細を見る

      記述言語:日本語   出版者・発行元:一般社団法人電子情報通信学会  

      ID/パスワードの使い回し問題により,生体情報を使った認証への注目が集まっている.生体情報は個人を特定できるセンシティブな情報であることから,準同型暗号により生体情報を暗号化したまま認証処理を行う秘匿生体認証方式が提案されている.著者らはこれまでに,Hattori et al.が提案した準同型暗号によるキャンセラブル生体認証方式に対し,任意のユーザに対してなりすましが可能であることを示した.また,それを利用してテンプレートを復元可能であることを示した.これらの攻撃は,テンプレートと照合データのユークリッド二乗距離を求める処理の問題を利用したものである.そのため,認証にユークリッド二乗距離を使用しない方式に対しては,本攻撃を適用することはできなかった.本稿は,Yasuda et al.が提案したハミング距離による認証を行う準同型を用いた秘匿生体認証方式において,二値符号が利用される場合に,攻撃者が高い確率で任意のユーザになりすます攻撃が可能であることを示す.さらに,提案なりすまし攻撃を拡張し,攻撃者は判定サーバを認証結果を返すオラクルとして利用することで,任意のユーザのオリジナルの生体情報を入手できる攻撃が可能であることを示す.

      CiNii Article

      researchmap

    • 準同型暗号を用いた秘匿生体認証に対する安全性について(その2)

      酒見 由美, 武仲 正彦, 鳥居 直哉, 安田 雅哉

      研究報告コンピュータセキュリティ(CSEC)2014 ( 45 ) 1 - 8   2014年6月26日

      詳細を見る

      記述言語:日本語   出版者・発行元:一般社団法人情報処理学会  

      ID/パスワードの使い回し問題により,生体情報を使った認証への注目が集まっている.生体情報は個人を特定できるセンシティブな情報であることから,準同型暗号により生体情報を暗号化したまま認証処理を行う秘匿生体認証方式が提案されている.著者等はこれまでに,Hattori et al. が提案した準同型暗号を用いたキャンセラブル生体認証方式に対し,二値符号が利用される場合に,なりすまし攻撃,テンプレート復元攻撃が可能であることを報告し,それらに対する対策を検討した.さらに,著者らは,Yasuda et al. が提案した準同型暗号を用いた秘匿生体認証方式に対するなりすまし攻撃,テンプレート復元攻撃が可能であることを報告した.本稿では,Yasuda et al. の準同型暗号を用いた秘匿生体認証方式に対し,Hattori et al. 方式への攻撃に対する対策として検討した,特徴ベクトルが二値符号であることを確認する対策の適用可能性について検討する.その結果,二値符号であることを確認する対策については,Yasuda et al. の方式へ単純に適用できないということが分かった.そこで,新たにユーザ乱数を Xor マスクする対策,乗算マスクする対策,加算マスクする対策を提案し,その効果について検討を行う.Biometric authentication attracts much attention because of the reuse problem of IDs and passwords. Recently, privacy-preserving biometric authentication schemes in which authentication process is exectuted on encrypted biometric information by homomorphic-encryption have been proposed. In our previous work, we have shown a spoofing attack to arbitrary user and a recovery attack for template against a cancelable biometric authentication scheme based on homomorphic encryption proposed by Hattori et al. when a binary coding is used. In addition, we have also proposed a countermeasure to our attack. Furthermore, a spoofing attack to arbitrary user and a recovery attack for template against a cancelable biometric authentication scheme based on homomorphic encryption by Yasuda et al. have been proposed. In this paper, we consider about applicability of the proposed countermeasure which verifies whether a feature vector is a binary code or not to our attack against Hattori et al. scheme to Yasuda et al. scheme. As a result, it is difficult to apply the countermeasure to Yasuda et al. scheme. Then, we consider about new countermeasure that uses Xor masking, multiplicative masking and additive masking, respectively.

      CiNii Article

      researchmap

    • 準同型暗号を用いた秘匿生体認証に対する安全性について(その1)

      酒見 由美, 武仲 正彦, 鳥居 直哉, 安田 雅哉

      研究報告コンピュータセキュリティ(CSEC)2014 ( 44 ) 1 - 6   2014年6月26日

      詳細を見る

      記述言語:日本語   出版者・発行元:一般社団法人情報処理学会  

      ID/パスワードの使い回し問題により,生体情報を使った認証への注目が集まっている.生体情報は個人を特定できるセンシティブな情報であることから,準同型暗号により生体情報を暗号化したまま認証処理を行う秘匿生体認証方式が提案されている.著者らはこれまでに,Hattori et al. が提案した準同型暗号によるキャンセラブル生体認証方式に対し、 任意のユーザに対してなりすましが可能であることを示した.また,それを利用してテンプレートを復元可能であることを示した.これらの攻撃は,テンプレートと照合データのユークリッド二乗距離を求める処理の問題を利用したものである.そのため,認証にユークリッド二乗距離を使用しない方式に対しては,本攻撃を適用することはできなかった.本稿は,Yasuda et al. が提案したハミング距離による認証を行う準同型を用いた秘匿生体認証方式において,二値符号が利用される場合に,攻撃者が高い確率で任意のユーザになりすます攻撃が可能であることを示す.さらに,提案なりすまし攻撃を拡張し,攻撃者は判定サーバを認証結果を返すオラクルとして利用することで,任意のユーザのオリジナルの生体情報を入手できる攻撃が可能であることを示す.Vulnerability in a Privacy-preserving Biometric Authentication by using Homomorphic Encryption

      CiNii Article

      researchmap

    • Secret computation of purchase history data using somewhat homomorphic encryption

      Yasuda Masaya, Shimoyama Takeshi, Kogure Jun

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

      詳細を見る

      記述言語:英語   出版者・発行元:Institute of Mathematics for Industry, Kyushu University ; c2014-  

      CiNii Article

      researchmap

    • RL-003 準同型暗号を用いた複数企業間の顧客情報分析(L分野:ネットワーク・セキュリティ,査読付き論文)

      安田 雅哉, 下山 武司, 横山 和弘, 小暮 淳

      情報科学技術フォーラム講演論文集12 ( 4 ) 15 - 22   2013年8月20日

      詳細を見る

      記述言語:日本語   出版者・発行元:FIT(電子情報通信学会・情報処理学会)運営委員会  

      CiNii Article

      researchmap

    • 格子マスキングを利用したKey Binding技術の提案 (マルチメディア情報ハイディング・エンリッチメント)

      杉村 由花, 安田 雅哉, 山田 茂史, 安部 登樹, 新崎 卓

      電子情報通信学会技術研究報告 = IEICE technical report : 信学技報113 ( 138 ) 297 - 304   2013年7月18日

      詳細を見る

      記述言語:日本語   出版者・発行元:一般社団法人電子情報通信学会  

      生体認証において,テンプレートと呼ばれる登録生体データを何らかの変換により保護しつつ,照合処理を行うテンプレート保護型生体認証技術が近年盛んに研究されている.特に,テンプレート保護型生体認証技術の一つであるkey bindingは,生体データとユーザ固有の鍵の結合データから補助情報を生成し,登録時と照合時の生体データが十分に近い場合のみユーザ固有の鍵が抽出できる特殊な技術である.Key bindingで利用するユーザ固有の鍵として,電子署名や文書などの情報を扱うことで,電子署名や文書暗号化/復号などに応用でき,認証判定だけでなく様々な利用形態の実現が期待されている技術でもある.本論文では,fuzzy commitmentやfuzzy vaultといった誤り訂正符号を利用した従来key binding実現方式とは異なる,新しい実現方式を提案する.我々の実現方式では,通常の乱数付加アプローチに加え,生体認証特有のデータの揺らぎ吸収のために,格子と呼ばれる数学的概念を利用した格子マスキングを新しく導入する.本論文では,格子マスキングによるkey binding技術の特長を述べると共に,具体的なシステムへの適用例を紹介する.

      CiNii Article

      researchmap

    • 格子マスキングを利用したKey Binding技術の提案

      杉村 由花, 安田 雅哉, 山田 茂史, 安部 登樹, 新崎 卓

      研究報告コンピュータセキュリティ(CSEC)2013 ( 44 ) 1 - 8   2013年7月11日

      詳細を見る

      記述言語:日本語  

      生体認証において,テンプレートと呼ばれる登録生体データを何らかの変換により保護しつつ,照合処理を行うテンプレート保護型生体認証技術が近年盛んに研究されている.特に,テンプレート保護型生体認証技術の一つである key binding は,生体データとユーザ固有の鍵の結合データから補助情報を生成し,登録時と照合時の生体データが十分に近い場合のみユーザ固有の鍵が抽出できる特殊な技術である.Key binding で利用するユーザ固有の鍵として,電子署名や文書などの情報を扱うことで,電子署名や文書暗号化/復号などに応用でき,認証判定だけでなく様々な利用形態の実現が期待されている技術でもある.本論文では,fuzzy commitment や fuzzy vault といった誤り訂正符号を利用した従来 key binding 実現方式とは異なる,新しい実現方式を提案する.我々の実現方式では,通常の乱数付加アプローチに加え,生体認証特有のデータの揺らぎ吸収のために,格子と呼ばれる数学的概念を利用した格子マスキングを新しく導入する.本論文では,格子マスキングによる key binding 技術の特長を述べると共に,具体的なシステムへの適用例を紹介する.Recently, the biometric template protection technology has been actively researched in biometrics. In this technology, the enrollment biometric data called a template are protected by some conversion. Among many approaches for the template protection technology, we here focus on the key binding approach. In the key binding approach, helper data is generated from joint data of a user's specific key with user's biometric data, and the user's specific key can be extracted only when the enrolled biometric data and a query data are sufficiently similar. By handling digital signature or document information as a user's specific key, the key binding approach can be applied to the digital signature, and document encryption/decryption. Hence the key binding approach is expected to be applied not only to authentication but also to various application scenarios. While conventional schemes like fuzzy commitment and fuzzy vault schemes use the error correcting code technique to achieve the key binding approach, we present a new scheme using so called the lattice masking. The notion of the lattice masking is derived from a combination of the random masking technique and the lattice theory. In this paper, we describe the feature of our scheme and also introduce a concrete application example.

      CiNii Article

      researchmap

    • 格子マスキングを利用したKey Binding技術の提案

      杉村 由花, 安田 雅哉, 山田 茂史, 安部 登樹, 新崎 卓

      研究報告セキュリティ心理学とトラスト(SPT)2013 ( 44 ) 1 - 8   2013年7月11日

      詳細を見る

      記述言語:日本語  

      CiNii Article

      researchmap

    • 楕円曲線暗号の攻撃とその安全性 (Computer Algebra : Design of Algorithms, Implementations and Applications)

      安田 雅哉

      数理解析研究所講究録1814   74 - 84   2012年10月

      詳細を見る

      記述言語:日本語   出版者・発行元:京都大学  

      CiNii Article

      researchmap

    • Torsion Points of Elliptic Curves with Bad Reduction at Some Primes

      Yasuda Masaya

      Commentarii mathematici Universitatis Sancti Pauli = Rikkyo Daigaku sugaku zasshi61 ( 1 ) 1 - 7   2012年7月

      詳細を見る

      記述言語:英語   出版者・発行元:立教大学  

      CiNii Article

      researchmap

    • 国際会議SHARCS 2012報告

      安田 雅哉, 伊豆 哲也, 下山 武司, 小暮 淳

      電子情報通信学会技術研究報告. ISEC, 情報セキュリティ112 ( 39 ) 33 - 38   2012年5月11日

      詳細を見る

      記述言語:日本語   出版者・発行元:一般社団法人電子情報通信学会  

      2012年3月17日から18日の2日間の日程で、米国ワシントンDCで開催された2012年の暗号攻撃専用ハードウェアに関する国際会議SHARCS 2012について報告する。

      CiNii Article

      researchmap

    • Gentry 準同型暗号に対するLLL攻撃実験(II)

      矢嶋 純, 安田 雅哉, 下山 武司, 小暮 淳

      電子情報通信学会技術研究報告. ISEC, 情報セキュリティ111 ( 285 ) 13 - 17   2011年11月7日

      詳細を見る

      記述言語:日本語   出版者・発行元:一般社団法人電子情報通信学会  

      暗号分野で長年難問とされていた完全準同型暗号の具体的な構成法をGentryが示して以来、完全準同型暗号を主体とした準同型暗号のクラウド・コンピューティング分野への応用に関する研究が盛んになりつつある。Gentryによる完全準同型暗号は、暗号文に関する加算・乗算操作の演算回数が制限されたSHEスキーム(=somewhat homomorphic encryption scheme)から構成される。Gentry's SHEスキームの暗号操作可能回数と安全性の関係を検証するために、Gentry's SHEスキームの安全性を支える格子問題に対し、格子縮約アルゴリズムを利用した攻撃実験を行った。本論文では、512次元Gentry's SHEスキームに対するLLL攻撃実験結果を主に報告する。

      CiNii Article

      researchmap

    • Gentry 準同型暗号に対するLLL攻撃実験(II)

      矢嶋 純, 安田 雅哉, 下山 武司, 小暮 淳

      電子情報通信学会技術研究報告. LOIS, ライフインテリジェンスとオフィス情報システム = IEICE technical report. LOIS, Life intelligence and office information systems111 ( 286 ) 13 - 17   2011年11月7日

      詳細を見る

      記述言語:日本語   出版者・発行元:一般社団法人電子情報通信学会  

      暗号分野で長年難問とされていた完全準同型暗号の具体的な構成法をGentryが示して以来、完全準同型暗号を主体とした準同型暗号のクラウド・コンピューティング分野への応用に関する研究が盛んになりつつある。Gentryによる完全準同型暗号は、暗号文に関する加算・乗算操作の演算回数が制限されたSHEスキーム(=somewhat homomorphic encryption scheme)から構成される。Gentry's SHEスキームの暗号操作可能回数と安全性の関係を検証するために、Gentry's SHEスキームの安全性を支える格子問題に対し、格子縮約アルゴリズムを利用した攻撃実験を行った。本論文では、512次元Gentry's SHEスキームに対するLLL攻撃実験結果を主に報告する。

      CiNii Article

      researchmap

    • Gentry 準同型暗号に対するLLL攻撃実験について

      矢嶋 純, 安田 雅哉, 下山 武司, 小暮 淳

      コンピュータセキュリティシンポジウム2011 論文集2011 ( 3 ) 576 - 581   2011年10月12日

      詳細を見る

      記述言語:日本語  

      CiNii Article

      researchmap

    • Experimental Analysis of Cheon's Algorithm against Pairing-friendly Curves (特集 人と共存するコンピュータセキュリティ技術)

      Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda

      情報処理学会論文誌52 ( 9 ) 2652 - 2661   2011年9月15日

      詳細を見る

      記述言語:英語   出版者・発行元:情報処理学会  

      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, αdG ∈ 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 127). 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.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, αdG ∈ 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 127). 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.

      CiNii Article

      researchmap

      その他リンク: http://id.nii.ac.jp/1001/00077497/

    • 格子版完全準同型暗号の安全性について

      安田 雅哉, 矢嶋 純, 下山 武司, 小暮 淳

      電子情報通信学会技術研究報告. ISEC, 情報セキュリティ111 ( 204 ) 43 - 50   2011年9月2日

      詳細を見る

      記述言語:日本語   出版者・発行元:一般社団法人電子情報通信学会  

      完全準同型暗号は、暗号化されたデータを復号せずに機密性を保つたままあらゆる処理が可能な公開鍵暗号で、クラウト・コンピューティング分野への応用が期待されている技術である。本論文では、格子版完全準同型暗号の安全性について述べる。格子版完全準同型暗号の安全性は、SSSPとBDDPと呼ばれる2つの数学的問題の解読困難性に基づいている。ここでは、格子版完全準同型暗号のパラメータとBDDPの解読困難性の関係について考察する。

      CiNii Article

      researchmap

    • TinyTate ライブラリが使用する楕円曲線における補助入力付き離散対数問題の解読報告(その2)

      酒見 由美, 伊豆 哲也, 武仲 正彦, 安田 雅哉

      研究報告情報セキュリティ心理学とトラスト(SPT)2011 ( 24 ) 1 - 8   2011年7月5日

      詳細を見る

      記述言語:日本語  

      CiNii Article

      researchmap

    • TinyTate ライブラリが使用する楕円曲線における補助入力付き離散対数問題の解読報告(その2)

      酒見 由美, 伊豆 哲也, 武仲 正彦, 安田 雅哉

      研究報告コンピュータセキュリティ(CSEC)2011 ( 24 ) 1 - 8   2011年7月5日

      詳細を見る

      記述言語:日本語  

      補助入力付き離散対数問題 (Discrete Logarithm Problem with Auxiliary Input,DLPwAI) とは,素数位数 r の元 G が生成する加法群において,3 つの元 G,αG,αdG と d|(r − 1) を満たす正整数 d とから,解となる正整数 α を求める問題である.2010 年に酒見等は,Cheon が提案した補助入力付き離散対数問題の解法アルゴリズム (Cheon アルゴリズム) を実装し,組込み機器向けのペアリング暗号ライブラリである TinyTate ライブラリで使用されている楕円曲線 (位数 r は 128 ビット) において,補助入力付き離散対数問題が (1 コアに換算して) 約 131 時間で解読できることを報告した.しかし Cheon アルゴリズムのサブアルゴリズムとして Shanks の BSGS 法 (Baby-step Giant-step 法) を使用していたことから,膨大な記憶容量 (約 246 GByte) が必要であった.このため,より大きなサイズの補助入力付き離散対数問題への適用は難しいと結論付けられていた.そこで本稿は,記憶容量を抑制する目的で,サブアルゴリズムとして Pollard の ρ 法を使用した Cheon アルゴリズムを実装し,同じ補助入力付き離散対数問題を (1 コアに換算して) 約 136 時間で解いた結果について報告する.使用した記憶容量は約 0.5 MByte 程度であった.The discrete logarithm problem with auxiliary input (DLPwAI) is a problem to find a positive integer α from elements G, αG, αdG in an additive cyclic group generated by G of prime order r and a positive integer d dividing r − 1. In 2010, 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 article, 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).

      CiNii Article

      researchmap

    • TinyTate ライブラリが使用する楕円曲線における補助入力付き離散対数問題の解読報告(その2)

      酒見 由美, 伊豆 哲也, 武仲 正彦, 安田 雅哉

      電子情報通信学会技術研究報告. ICSS, 情報通信システムセキュリティ : IEICE technical report111 ( 125 ) 151 - 158   2011年7月5日

      詳細を見る

      記述言語:英語   出版者・発行元:一般社団法人電子情報通信学会  

      補助入力付き離散対数問題(Discrete Logarithm Problem with Auxiliary Input,DLPwAI)とは,素数位数rの元Gが生成する加法群において, 3つの元G,αG,α^dGとd|(r-1)を満たす正整数dとから,解となる正整数αを求める問題である.2010年に酒見等は,Cheonが提案した補助入力付き離散対数問題の解法アルゴリズム(Cheonアルゴリズム)を実装し,組込み機器向けのペアリング暗号ライブラリであるTinyTateライブラリで使用されている楕円曲線(位数rは128ビット)において,補助入力付き離散対数問題が(1コアに換算して)約131時間で解読できることを報告した.しかしCheonアルゴリズムのサブアルゴリズムとしてShanksのBSGS法(Baby-step Giant-step法)を使用していたことから,膨大な記憶容量(約246GByte)が必要であった.このため,より大きなサイズの補助入力付き離散対数問題への適用は難しいと結論付けられていた.そこで本稿は,記憶容量を抑制する目的で,サブアルゴリズムとしてPollardのρ法を使用したCheonアルゴリズムを実装し,同じ補助入力付き離散対数問題を(1コアに換算して)約136時間で解いた結果について報告する.使用した記憶容量は約0.5MByte程度であった.

      CiNii Article

      researchmap

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

      Yasuda Masaya, Izu Tetsuya, Shimoyama Takeshi

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

      詳細を見る

      記述言語:英語   出版者・発行元: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

      その他リンク: http://hdl.handle.net/2324/20144

    • Cheonアルゴリズムの高速化検討 (コンピュータセキュリティ(CSEC) Vol.2010-CSEC-50)

      安田 雅哉, 伊豆 哲也, 武仲 正彦

      情報処理学会研究報告2010 ( 2 ) 8p   2010年8月

      詳細を見る

      記述言語:日本語   出版者・発行元:情報処理学会  

      CiNii Article

      researchmap

    • ペアリングフレンドリ曲線全体におけるBW法で構成される曲線の割合について (コンピュータセキュリティ(CSEC) Vol.2010-CSEC-50)

      安田 貴徳, 安田 雅哉, 下山 武司

      情報処理学会研究報告2010 ( 2 ) 7p   2010年8月

      詳細を見る

      記述言語:日本語   出版者・発行元:情報処理学会  

      CiNii Article

      researchmap

    • 補助入力つき離散対数問題と暗号プロトコルの安全性について

      伊豆 哲也, 武仲 正彦, 花岡 悟一郎, 安田 雅哉

      電子情報通信学会技術研究報告. SITE, 技術と社会・倫理 : IEICE technical report110 ( 114 ) 189 - 194   2010年6月24日

      詳細を見る

      記述言語:日本語   出版者・発行元:一般社団法人電子情報通信学会  

      公開鍵暗号プロトコルの安全性は,根拠となる数学的問題の困難性に帰着される.さまざまな暗号プロトコルが考案されるにつれ,新しい数学的問題が提案されてきているが,特に2001年以降に注目を集めている双線形写像を用いた暗号プロトコルでは,Diffie-Hellman問題に関連したさまざまな問題(Diffie-Hellman関連問題)が提案・使用されている.しかしこれら新しい数学的問題の困難性は,素因数分解問題や離散対数問題などの古典的な数学的問題に比べ,評価はまだ十分でない.2006年にCheonが提案したアルゴリズム(Cheonアルゴリズム)は補助入力付き散対数問題(DLPwAI)に対する解法アルゴリズムであるが,Diffie-Hellman関連問題の解法にもなっており,暗号プロトコルの安全性に与える影響は大きい.本稿では,いくつかの暗号プロトコルの安全性とDiffi-Hellman関連問題にCheonアルゴリズムを適用した場合の問題の困難性について考察する.

      CiNii Article

      researchmap

    • Cheon アルゴリズムの高速化検討

      安田 雅哉, 伊豆 哲也, 武仲 正彦

      電子情報通信学会技術研究報告. SITE, 技術と社会・倫理 : IEICE technical report110 ( 114 ) 173 - 180   2010年6月24日

      詳細を見る

      記述言語:日本語   出版者・発行元:一般社団法人電子情報通信学会  

      多くの暗号システムの安全性は、離散対数問題の計算困難性に基づいている。2006年に、Cheonは補助入力つき離散対数問題を効率的に解くアルゴリズムを提案した。近年、我々はペアリング暗号で利用される楕円曲線上の補助入力つき離散対数問題(補助入力つき楕円曲線離散対数問題)に対して、Cheonアルゴリズムの実装報告をした。今回、過去の実装では用いなかったCheonアルゴリズムに関するいくつかの高速化手法を説明する。また、高速化手法を用いたCheonアルゴリズムの高速化効果を述べる。

      CiNii Article

      researchmap

    • 補助入力つき離散対数問題と暗号プロトコルの安全性について

      伊豆 哲也, 武仲 正彦, 花岡 悟一郎, 安田 雅哉

      電子情報通信学会技術研究報告. ISEC, 情報セキュリティ110 ( 113 ) 189 - 194   2010年6月24日

      詳細を見る

      記述言語:日本語   出版者・発行元:一般社団法人電子情報通信学会  

      公開鍵暗号プロトコルの安全性は,根拠となる数学的問題の困難性に帰着される.さまざまな暗号プロトコルが考案されるにつれ,新しい数学的問題が提案されてきているが,特に2001年以降に注目を集めている双線形写像を用いた暗号プロトコルでは,Diffie-Hellman問題に関連したさまざまな問題(Diffie-Hellman関連問題)が提案・使用されている.しかしこれら新しい数学的問題の困難性は,素因数分解問題や離散対数問題などの古典的な数学的問題に比べ,評価はまだ十分でない.2006年にCheonが提案したアルゴリズム(Cheonアルゴリズム)は補助入力付き散対数問題(DLPwAI)に対する解法アルゴリズムであるが,Diffie-Hellman関連問題の解法にもなっており,暗号プロトコルの安全性に与える影響は大きい.本稿では,いくつかの暗号プロトコルの安全性とDiffi-Hellman関連問題にCheonアルゴリズムを適用した場合の問題の困難性について考察する.

      CiNii Article

      researchmap

    • Cheon アルゴリズムの高速化検討

      安田 雅哉, 伊豆 哲也, 武仲 正彦

      電子情報通信学会技術研究報告. ISEC, 情報セキュリティ110 ( 113 ) 173 - 180   2010年6月24日

      詳細を見る

      記述言語:日本語   出版者・発行元:一般社団法人電子情報通信学会  

      多くの暗号システムの安全性は、離散対数問題の計算困難性に基づいている。2006年に、Cheonは補助入力つき離散対数問題を効率的に解くアルゴリズムを提案した。近年、我々はペアリング暗号で利用される楕円曲線上の補助入力つき離散対数問題(補助入力つき楕円曲線離散対数問題)に対して、Cheonアルゴリズムの実装報告をした。今回、過去の実装では用いなかったCheonアルゴリズムに関するいくつかの高速化手法を説明する。また、高速化手法を用いたCheonアルゴリズムの高速化効果を述べる。

      CiNii Article

      researchmap

    • ペアリングフレンドリ曲線全体におけるBW法で構成される曲線の割合について

      安田 貴徳, 安田 雅哉, 下山 武司, 小暮 淳

      電子情報通信学会技術研究報告. ISEC, 情報セキュリティ110 ( 113 ) 181 - 187   2010年6月24日

      詳細を見る

      記述言語:日本語   出版者・発行元:一般社団法人電子情報通信学会  

      近年、楕円曲線上のペアリングと呼ばれる写像を利用したペアリング暗号技術が注目されている。ペアリング暗号では、ペアリングフレンドリ曲線と呼ばれる特別な楕円曲線を選ぶ必要があり、その曲線の構成法がいくつか提案されている。従来提案されている方法によって得られる曲線はペアリング暗号を利用する上で最適なものなのかは明らかではない。今回、ペアリングフレンドリ曲線全体の中で、代表的な構成法であるBrezing-Weng法(BW法)によって得られる曲線がどれぐらい有効であるか、実験と理論の両面から検討した結果について述べる。

      CiNii Article

      researchmap

    • ペアリングフレンドリ曲線全体におけるBW法で構成される曲線の割合について

      安田, 安田 雅哉, 下山 武司, 小暮 淳

      電子情報通信学会技術研究報告. SITE, 技術と社会・倫理 : IEICE technical report110 ( 114 ) 181 - 187   2010年6月24日

      詳細を見る

      記述言語:日本語   出版者・発行元:一般社団法人電子情報通信学会  

      近年、楕円曲線上のペアリングと呼ばれる写像を利用したペアリング暗号技術が注目されている。ペアリング暗号では、ペアリングフレンドリ曲線と呼ばれる特別な楕円曲線を選ぶ必要があり、その曲線の構成法がいくつか提案されている。従来提案されている方法によって得られる曲線はペアリング暗号を利用する上で最適なものなのかは明らかではない。今回、ペアリングフレンドリ曲線全体の中で、代表的な構成法であるBrezing-Weng法(BW法)によって得られる曲線がどれぐらい有効であるか、実験と理論の両面から検討した結果について述べる。

      CiNii Article

      researchmap

    • ペアリングフレンドリ曲線全体におけるBW法で構成される曲線の割合について

      安田, 安田 雅哉, 下山 武司, 小暮 淳

      電子情報通信学会技術研究報告. ICSS, 情報通信システムセキュリティ : IEICE technical report110 ( 115 ) 181 - 187   2010年6月24日

      詳細を見る

      記述言語:日本語   出版者・発行元:一般社団法人電子情報通信学会  

      近年、楕円曲線上のペアリングと呼ばれる写像を利用したペアリング暗号技術が注目されている。ペアリング暗号では、ペアリングフレンドリ曲線と呼ばれる特別な楕円曲線を選ぶ必要があり、その曲線の構成法がいくつか提案されている。従来提案されている方法によって得られる曲線はペアリング暗号を利用する上で最適なものなのかは明らかではない。今回、ペアリングフレンドリ曲線全体の中で、代表的な構成法であるBrezing-Weng法(BW法)によって得られる曲線がどれぐらい有効であるか、実験と理論の両面から検討した結果について述べる。

      CiNii Article

      researchmap

    • 楕円曲線暗号の攻撃評価

      安田 雅哉, 伊豆 哲也, 下山 武司, 小暮 淳

      全国大会講演論文集72   569 - 570   2010年3月8日

      詳細を見る

      記述言語:日本語  

      CiNii Article

      researchmap

    ▼全件表示

    書籍等出版物

    • 暗号の理論と技術~量子時代のセキュリティ理解のために~

      國廣昇, 安田雅哉, 水木敬明, 高安敦, 高島克幸, 米山一樹, 大原一真, 江村恵太( 担当: 共著 ,  範囲: 第2章「現代の暗号技術を支える数学」)

      講談社  2024年5月 

      詳細を見る

    • NIST標準化の格子暗号方式の紹介

      安田雅哉( 担当: 単著 ,  範囲: 会誌11月号(特集「耐量子計算機暗号の最新動向」における記事))

      電子情報通信学会  2023年11月 

      詳細を見る

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

      青野良範, 安田雅哉( 担当: 共著)

      近代科学社  2019年9月 

      詳細を見る

    講演・口頭発表等

    • 超特異楕円曲線の自己準同型環計算と同種写像問題の求解 招待有り

      安田雅哉

      名城大学理工学部数学科・談話会  2024年5月24日 

      詳細を見る

      記述言語:日本語   会議種別:口頭発表(一般)  

      researchmap

    • 格子ベース準同型暗号の応用と格子基底簡約

      安田雅哉

      研究集会「暗号と量子計算」(東京工業大学)  2023年12月21日 

      詳細を見る

      開催年月日: 2023年12月21日 - 2023年12月21日

      記述言語:日本語   会議種別:口頭発表(一般)  

      researchmap

    • 格子問題の求解アルゴリズムとその応用

      安田雅哉

      2023年度東大数理・情報数学セミナー  2023年11月 

      詳細を見る

      記述言語:日本語   会議種別:公開講演,セミナー,チュートリアル,講習,講義等  

      researchmap

    • 数理暗号の紹介:格子暗号と同種写像暗号 招待有り

      安田雅哉

      日本数学会・秋季総合分科会・代数学(特別講演)  2023年9月20日 

      詳細を見る

      記述言語:日本語   会議種別:口頭発表(招待・特別)  

      researchmap

    • Lattice Basis Reduction and Its Application to Cryptanalysis

      Masaya Yasuda

      Mathematics for Industry in the Asia Pacific Area at SIAM Conference on Computational Science and Engineering (CSE23))  2023年3月2日 

      詳細を見る

      記述言語:英語   会議種別:シンポジウム・ワークショップ パネル(指名)  

      researchmap

    • 格子基底簡約とLWE/NTRU問題に対する格子攻撃 招待有り

      安田雅哉

      九大IMI共同利用「耐量子計算機暗号と量子情報の数理」  2022年8月3日 

      詳細を見る

      開催年月日: 2022年8月1日 - 2022年8月4日

      記述言語:日本語   会議種別:口頭発表(招待・特別)  

      researchmap

    • 最短ベクトル問題を解くための格子基底簡約とその大規模並列化 招待有り

      安田雅哉

      研究集会「量子暗号理論と耐量子暗号」(早稲田大学・Zoomによるオンライン開催)  2022年3月18日 

      詳細を見る

      開催年月日: 2022年3月18日 - 2022年3月18日

      記述言語:日本語   会議種別:口頭発表(招待・特別)  

      researchmap

    • 現代の暗号技術を支える数学

      安田 雅哉

      KISTEC教育講座「情報セキュリティ理解のための先端暗号技術入門」  2021年11月25日 

      詳細を見る

      開催年月日: 2021年11月25日 - 2021年11月30日

      記述言語:日本語   会議種別:公開講演,セミナー,チュートリアル,講習,講義等  

      researchmap

    • 格子基底簡約とその大規模並列化の紹介 招待有り

      安田 雅哉

      九大IMI共同利用研究集会「新世代暗号の設計・評価」  2021年11月16日 

      詳細を見る

      開催年月日: 2021年11月16日 - 2021年11月17日

      記述言語:日本語   会議種別:口頭発表(招待・特別)  

      researchmap

    • 最短ベクトル問題求解に向けた格子基底簡約入門

      安田 雅哉

      RIMS共同研究「準周期的秩序の数理とその周辺」  2021年11月8日 

      詳細を見る

      開催年月日: 2021年11月8日 - 2021年11月10日

      記述言語:英語   会議種別:口頭発表(一般)  

      researchmap

    ▼全件表示

    共同研究・競争的資金等の研究

    • 補助情報付き同種写像問題に対する数理的解読法の探求と開拓

      日本学術振興会  科学研究費助成事業 

      安田 雅哉, 相川 勇輔

      詳細を見る

      2023年6月 - 2026年3月

      課題番号:23K18469

      配分額:6500000円 ( 直接経費:5000000円 、 間接経費:1500000円 )

      researchmap

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

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

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

      詳細を見る

      2020年4月 - 2024年3月

      課題番号:20H04142

      配分額:17550000円 ( 直接経費:13500000円 、 間接経費:4050000円 )

      量子計算機による暗号解読にも耐性のある耐量子計算機暗号(Post-Quantum Cryptography)の有力候補である格子暗号の安全性は、格子上の最短ベクトル問題(SVP, Shortest Vector Problem)や最近ベクトル問題(CVP, Closest Vector Problem)などの格子問題の計算困難性に基づく。本年度(2021年度)は、格子問題に対する解読アルゴリズムの大規模並列化フレームワークの設計・開発・求解実験に成功した。具体的には、昨年度開発した並列化システムをベースに、格子問題に対する効率的な求解法である格子基底簡約・列挙法・篩法の異なる3つの格子アルゴリズムを大規模計算機システム上で同時に動作可能とする並列化フレームワークCMAP-LAP(Configurable Massively Parallel Solver for Lattice Problems)の開発に成功した。また、今回開発したCMAP-LAPフレームワークにおける格子基底簡約としてDeepBKZアルゴリズムを採用し、最大100,032並列プロセスを持つ大規模計算機上で、130次元程度のSVPを約100時間以内で求解可能であることを実験的に示した。本研究成果は、高性能計算分野のトップ国際会議の1つであるHigh Performance Computing(HiPC2021)に採択された。また、格子暗号方式の安全性に直接関係するLWEやNTRU問題に対して、新しい攻撃手法を提案すると共に、求解実験によりその有効性を示した。LWEやNTRU問題に対する解析結果は、暗号分野における多数の査読付き国際会議・国際雑誌に採択された。

      researchmap

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

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

      安田 雅哉

      詳細を見る

      2019年6月 - 2022年3月

      課題番号:19K22847

      配分額:6500000円 ( 直接経費:5000000円 、 間接経費:1500000円 )

      近年、超特異楕円曲線間の同種写像の列を利用した同種写像暗号は、量子計算機による暗号解読でも耐性のある耐量子計算機暗号技術(Post-Quantum Cryptography)の1つとして期待されている。具体的には、米国標準技術研究所NISTが2016年以降進めている耐量子計算機暗号の標準化プロセスにおいて、超特異楕円曲線上の鍵交換アルゴリズムSIKE(Supersingular Isogeny Key Encapsulation)は2020年7月にThird Roundに進むことが許可された15方式の内の1つに選出された。同種写像暗号の安全性は、2つの同種な楕円曲線を結ぶ同種写像の列を具体的に計算する同種写像問題の計算量困難性に依存する。一方、楕円曲線論において、有限体上の超特異楕円曲線全体と四元数環におけるmaximal order全体が1対1に対応するDeuring対応が知られている。本年度(2021年度)は、超特異楕円曲線のDeuring対応下における四元数環上の同種写像問題を効率的に解くKohel-Lauter-Petit-Tignol(KLPT)アルゴリズムの高速実装に成功した。また、実装開発したKLPTアルゴリズムに加えて、超特異楕円曲線のねじれ点の高速探索法を提案し、与えられたイデアルにDeuring対応する超特異楕円曲線を求める構成的Deuring対応問題を実用的な処理時間で求解可能であることを示した。(近年、構成的Deuring対応計算は超特異楕円曲線の同種写像列を利用した署名方式などで非常に注目されている。)これらの研究成果は、多数の国内会議で発表すると共に、査読付きの国際会議・国際雑誌にも採択された。

      researchmap

    • ポスト量子暗号の標準化に向けた安全な暗号パラメータの導出

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

      高木 剛, 安田 雅哉

      詳細を見る

      2017年4月 - 2020年3月

      課題番号:17K00185

      配分額:4550000円 ( 直接経費:3500000円 、 間接経費:1050000円 )

      本研究課題では、ポスト量子暗号の標準化に向けた安全な暗号パラメータの導出に関する研究を行なっている。平成30年度は、格子の最短ベクトル問題SVPに対する高速な解法として、BKZアルゴリズムの改良を行なった。LLL簡約基底をノルムの大きさで並び替えることにより、BKZアルゴリズムで用いる基底列挙法の高速化を検討した。100次から120次元の格子に対して、NTLライブラリによりブロックサイズβが15から30のBKZ簡約基底を求めたところ、提案手法では40%から46%程度の確率で短い基底を求めることができた。また、格子を用いた完全準同型暗号の構成で利用されるGeneral Approximate Common Divisors(GACD)問題の困難性を評価した。2014年にDingとTaoにより提案されたアルゴリズムを改良して、必要されるサンプル数に関する新たな条件式を求めて、計算機実験により有効性を確認した。更に、格子暗号のIoTディバスなどの組込み機器での効率性能を評価するために、JavaScriptによる高速実装を行なった。格子暗号としては Lizard, Kyber, Frodo, および NewHopeを選択して、Web browsers, Tessel2, Androidの計算環境で高速実装による効率性のデータを得た。最後に、昨年度に国際会議で発表した、Learning With Errors(LWE)問題の困難性に関する論文をジャーナル論文化した。この論文では、LWE問題をKannan's embeddingにより格子のunique-SVPに帰着する方法に対して、埋め込み係数の大きさ、LWE問題のサンプル数の大きさ、BKZアルゴリズムのブロックサイズを考察した。

      researchmap

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

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

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

      詳細を見る

      2016年4月 - 2020年3月

      課題番号:16H02830

      配分額:14040000円 ( 直接経費:10800000円 、 間接経費: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

    お問い合わせ先
    外部の方
    学内の方