英語 日本語
研究概要

ポスト量子暗号

最も有名な公開鍵暗号としてRSA 暗号と楕円曲線暗号があり,SSL/TLS による暗号通信や電子政府でのディジタル署名などで広く普及している.
一方で,これらの暗号は量子計算機による多項式時間の解読法が知られており危殆化するため,量子計算機に耐性のある数学問題を利用したポスト量子暗号(Post-Quantum Cryptography) の研究が注目を集めている.実際,2015年8月にアメリカ国家安全性保障局NSAはポスト量子暗号への移行を表明し,2016年2月には米国標準技術研究所NISTがポスト量子暗号の標準化計画を発表している.

本研究室では,代表的なポスト量子暗号となる格子暗号や多変数多項式暗号に対して,安全性の評価と効率的な実装方法に関して研究を進めている.格子暗号の安全性は,実n次元空間の1次独立な基底Bに対して,Bで生成される格子に含まれる最短な非零ベクトルを求める問題(Shortest Vector Problem: SVP)の困難性に支えられている.本研究室では,格子縮約アルゴリズムを用いることによりSVPの困難性の厳密評価を研究している.また,多変数多項式暗号の安全性は,多変数多項式(Multivariate Quadratic polynomials)の求解問題(MQ 問題)の困難性を基にしている.本研究室のグループでは,MQ問題の困難性評価を目的として2015年4月1日から暗号解読コンテストMQ Challengeを実施している.

発表論文

  • Tsuyoshi Takagi, "Recent Developments in Post-Quantum Cryptography", IEICE Transaction, Vol.E101-A, No.1, pp.3-11, 2018.
  • Yasuhiko Ikematsu, Dung Hoang Duong, Albrecht Petzoldt, Tsuyoshi Takagi, "An Efficient Key Generation of ZHFE Public Key Cryptosystem", IEICE Transaction, Vol.E101-A, No.1, pp.29-38, 2018.
  • Koichiro Akiyama, Yasuhiro Goto, Shinya Okumura, Tsuyoshi Takagi, Koji Nuida and Goichiro Hanaoka, "A Public-key Encryption Scheme based on Non-linear Indeterminate Equations", The 24th Annual Conference on Selected Areas in Cryptography, SAC 2017, LNCS 10719, pp.215-234, 2018.
  • 高木剛, "ポスト量子暗号の構成法とその安全性評価", 電子情報通信学会, 基礎・境界ソサイエティ, Fundamentals Review, Vol.11, No.1, p.17-27, 2017.
  • Dung Hoang Duong, Albrecht Petzoldt, Tsuyoshi Takagi, "CyclicSRP - A Multivariate Encryption Scheme with a Partially Cyclic Public Key", IEICE Transaction, Vol.E100-A, No.12, pp.2691-2698, 2017.
  • Hyungrok Jo, Christophe Petit, and Tsuyoshi Takagi, "Full Cryptanalysis of Hash Functions Based on Cubic Ramanujan Graphs", IEICE Transaction, Vol.E100-A, No.9, pp.1891-1899, 2017.
  • Dung Hoang Duong, Masaya Yasuda, Tsuyoshi Takagi, "Choosing Parameters for the Subfield Lattice Attack Against Overstretched NTRU", The 20th International Conference on Information Security, ISC 2017, LNCS 10599, pp.79-91, 2017.
  • Rui Xu, Yeo Sze Ling, Kazuhide Fukushima, Tsuyoshi Takagi, Seo Hwajung, Shinsaku Kiyomoto, Henricksen Matt, "An Experimental Study of the BDD Approach for the Search LWE Problem", The 15th International Conference on Applied Cryptography and Network Security, ACNS 2017, LNCS 10355, pp.253-272, 2017.
  • Saed Alsayigh, Jintai Ding, Tsuyoshi Takagi, Yuntao Wang, "The Beauty and the Beasts — The Hard Cases in LLL Reduction", 12th International Workshop on Security, IWSEC 2017, LNCS 10418, pp.19–35, 2017.
  • Ye Yuan, Kazuhide Fukushima, Shinsaku Kiyomoto, Tsuyoshi Takagi, "Memory-constrained implementation of lattice-based encryption scheme on standard Java Card", IEEE International Symposium on Hardware Oriented Security and Trust, HOST 2017, pp.47-50, 2017.
  • Hikari Tachibana, Katsuyuki Takashima, Tsuyoshi Takagi, "Constructing an Efficient Hash Function from 3-Isogenies ", JSIAM Letters, Vol.9, p.29-32, 2017.
  • Yasuhiko Ikematsu, Dung Hoang Duong, Albrecht Petzoldt, Tsuyoshi Takagi, "Revisiting the Efficient Key Generation of ZHFE", The 2nd International Conference on Codes, Cryptology and Information Security, C2SI 2017, LNCS 10194, pp.195-212, 2017.
  • Chi Cheng, Rongxing Lu, Albrecht Petzoldt, Tsuyoshi Takagi, "Securing Internet of Things in a Quantum World", IEEE Communications Magazine, Vol.55, No.2, pp.116-120, 2017.
  • Dung Hoang Duong, Albrecht Petzoldt, Yacheng Wang, Tsuyoshi Takagi, "Revisiting the Cubic UOV Signature Scheme", The 19th Annual International Conference on Information Security and Cryptology, ICISC 2016, LNCS 10157, pp.223-238, 2017.
  • Duong Hoang Dung, Albrecht Petzoldt, Tsuyoshi Takagi, "Reducing the Key Size of the SRP Encryption Scheme", 21st Australasian Conference on Information Security and Privacy, ACISP 2016, LNCS 9723, pp.427-434, 2016.
  • Yoshinori Aono, Yuntao Wang, Takuya Hayashi, Tsuyoshi Takagi, "Improved Progressive BKZ Algorithms and their Precise Cost Estimation by Sharp Simulator", The 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2016, LNCS 9665, pp.789-819, 2016.
  • Ye Yuan, Chen-Mou Cheng, Shinsaku Kiyomoto, Yutaka Miyake, Tsuyoshi Takagi,"Portable Implementation of Lattice-based Cryptography using JavaScript", The Third International Symposium on Computing and Networking, CANDAR'15, pp.58-67, 2015.
  • 鷲見拓哉, 石黒司, 清本晋作, 三宅優, 小林透, 高木剛, "Web Workersを用いた多変数公開鍵暗号Rainbowの並列実装", 情報処理学会論文誌, Vol.55, No.9, pp.2061-2071, 2014.
  • Chen-Mou Cheng, Yasufumi Hashimoto, Hiroyuki Miura, Tsuyoshi Takagi, "A Polynomial-Time Algorithm for Solving a Class of Underdetermined Multivariate Quadratic Equations over Fields of Odd Characteristics", 6th International Workshop on Post-Quantum Cryptography, PQCrypto 2014, LNCS 8772, pp.40-58, 2014.
  • Hiroyuki Miura, Yasufumi Hashimoto, Tsuyoshi Takagi, "Extended Algorithm for Solving Underdefined Multivariate Quadratic Equations", Fifth International Conference on Post-Quantum Cryptography, PQCrypto 2013, LNCS 7932, pp.118-135, 2013.
  • Takanori Yasuda, Tsuyoshi Takagi, Kouichi Sakurai, "Multivariate Signature Scheme Using Quadratic Forms", Fifth International Conference on Post-Quantum Cryptography, PQCrypto 2013, LNCS 7932, pp.243-258, 2013.

PAGE TOP