東京大学 大学院情報理工学系研究科 数理情報学専攻 高木・高安研究室 暗号数理情報学研究室（数理情報第1研究室）

ポスト量子暗号

最も有名な公開鍵暗号として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を実施している．

発表論文

  • Hiroki Furue, Yasuhiko Ikematsu, Yutaro Kiyomura, Tsuyoshi Takagi, "A New Variant of Unbalanced Oil and Vinegar Using Quotient Ring: QR-UOV", the 27th Annual International Conference on the Theory and Application of Cryptology and Information Security, Asiacrypt 2021, LNCS 13093, pp.187-217, 2021.
  • Shuhei Nakamura, Yasuhiko Ikematsu, Yacheng Wang, Jintai Ding, Tsuyoshi Takagi, "New complexity estimation on the Rainbow-Band-Separation attack", Theoretical Computer Science, Vol.896, pp.1-18, 2021.
  • Shusaku Uemura, Kazuhide Fukushima, Shinsaku Kiyomoto, Momonari Kudo, Tsuyoshi Takagi, "Shortest Vectors in Lattices of Bai-Galbraith's Embedding Attack on the LWR Problem", 16th International Workshop on Security, IWSEC 2021, LNCS 12835, pp.23-41, 2021.
  • Hiroki Furue, Shuhei Nakamura, Tsuyoshi Takagi, "Improving Thomae-Wolf Algorithm for Solving Underdetermined Multivariate Quadratic Polynomial Problem". 12th International Workshop on Post-Quantum Cryptography, PQCrypto 2021, LNCS 12841, pp.65-78, 2021.
  • Tomoki Moriya; Hiroshi Onuki; Tsuyoshi Takagi, "SiGamal: A supersingular isogeny-based PKE and its application to a PRF", the 26th Annual International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020, LNCS 12492, pp.551–580, 2020.
  • Hiroki Furue, Koha Kinjo, Yasuhiko Ikematsu, Yacheng Wang, Tsuyoshi Takagi, "A Structural Attack on Block-Anti-Circulant UOV at SAC 2019", The Eleventh International Conference on Post-Quantum Cryptography, PQCrypto 2020, LNCS 12100, pp.323-339, 2020.
  • Takanori Yasuda, Yacheng Wang, Tsuyoshi Takagi, "Multivariate Encryption Schemes Based on Polynomial Equations over Real Numbers", The Eleventh International Conference on Post-Quantum Cryptography, PQCrypto 2020, LNCS 12100, pp.402-421, 2020.
  • Tomoki Moriya, Hiroshi Onuki, Tsuyoshi Takagi, "How to Construct CSIDH on Edwards Curves", RSA Conference 2020 Cryptographer's Track, CT-RSA 2020, LNCS 12006, pp.512-537, 2020.
  • Yasufumi Hashimoto, Yasuhiko Ikematsu, Tsuyoshi Takagi, "Chosen Message Attack on Multivariate Signature ELSA at Asiacrypt 2017", Journal of Information Processing, Vol.27, pp.517–524, 2019.
  • Yacheng Wang, Yasuhiko Ikematsu, Dung Hong Dung, Tsuyoshi Takagi, "The Secure Parameters and Efficient Decryption Algorithm for Multivariate Public Key Cryptosystem EFC", IEICE Transactions, Vol.E102-A, No.9, pp.1028-1036, 2019.
  • Jintai Ding, Xinwei Gao, Tsuyoshi Takagi, Yuntao Wang, "One Sample Ring-LWE with Rounding and its Application to Key Exchange", 17th International Conference on Applied Cryptography and Network Security, ACNS 2019, LNCS 11464, pp.323-343, 2019.
  • Jintai Ding, Momonari Kudo, Shinya Okumura, Tsuyoshi Takagi, Chengdong Tao, "Cryptanalysis of a public key cryptosystem based on Diophantine equations via weighted LLL reduction", Japan Journal of Industrial and Applied Mathematics, Volume 35, Issue 3, pp.1123–1152, 2018.
  • Shinya Okumura, Shingo Sugiyama, Masaya Yasuda, Tsuyoshi Takagi, "Security analysis of cryptosystems using short generators over ideal lattices", Japan Journal of Industrial and Applied Mathematics, Volume 35, Issue 2, pp.739–771, 2018.
  • Weiyao Wang, Yuntao Wang, Atsushi Takayasu, Tsuyoshi Takagi, "Estimated Cost for Solving Generalized Learning with Errors Problem via Embedding Techniques", 13th International Workshop on Security, IWSEC 2018, LNCS 11049, pp.87-103, 2018.
  • Yasuhiko Ikematsu, Ray Perlner, Daniel Smith-Tone, Tsuyoshi Takagi, Jeremy Vates, "HFERP - A New Multivariate Encryption Scheme", PQCrypto 2018, LNCS 10786, pp.396-416, 2018.
  • Tsuyoshi Takagi, "Recent Developments in Post-Quantum Cryptography", IEICE Transaction, Vol.E101-A, No.1, pp.3-11, 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 鷲見拓哉, 石黒司, 清本晋作, 三宅優, 小林透, 高木剛, "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.
  • Yasufumi Hashimoto, Tsuyoshi Takagi, Kouichi Sakurai, "General Fault Attacks on Multivariate Public Key Cryptosystems", PQCrypto 2011, LNCS 7071, pp.1-18, 2011.