公開鍵暗号に対する格子理論に基づく安全性解析とその暗号設計への応用

基于格理论的公钥密码安全性分析及其在密码设计中的应用

• 批准号: 14J08237
• 负责人: 高安 敦
• 金额: $ 1.6万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2014
• 资助国家: 日本
• 起止时间: 2014-04-25 至 2017-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14J08237/
• 关键词: 格子; RSA暗号; 耐量子暗号; 最短ベクトル問題; 格子簡約アルゴリズム; 格子暗号; 安全性解析; 法付き方程式

今年度は、格子理論に基づいて公開鍵暗号の安全性解析を行うという、本研究課題における非常に先進的な成果をあげ、さらに、ここで得た格子理論の知見を暗号設計にも応用するという理想的な目標においても成果をあげることができ、飛躍的に研究が進んで年度であったと言える。本研究課題の主たる内容である公開鍵暗号の安全性解析の研究は、大きく二つのテーマを行った。一つ目は格子理論に基づくRSA暗号の安全性解析であり、二つ目は格子暗号の安全性解析である。まず、格子理論に基づくRSA暗号の安全性解析について記す。RSA暗号の理論的な安全性を保証するために、特殊な設定、もしくは、その秘密鍵の部分情報が漏洩した際の安全性の格子理論に基づいた解析は、長く続く暗号理論の代表的な研究テーマの一つである。このテーマにおいて、査読付き国際論文誌・査読付き国際会議予稿集に6件の論文が採録され、国際会議で5件の発表を行った。これらの成果は、国内の暗号・セキュリティ分野において権威のある辻井重男セキュリティ論文特別賞を受賞したものや、国際会議ACISPでBest Student Paper Awardを受賞した成果を含む。次に、格子暗号の安全性解析における成果を紹介する。上記のRSA暗号を含め、現在実用化されている公開鍵暗号方式は、量子計算機が完成すれば大幅に安全性が低下し、実用上利用できなくなることがわかっている。そのため、量子計算機にも耐性のある格子暗号の研究は、近年の暗号研究の主流なテーマとなっている。今年度は、このテーマに対して、理論的な成果ではあるが、最悪時の理論評価を厳密に行った。この成果は国内学会で発表しており、情報セキュリティ研究奨励賞を受賞している。また、類似な文脈において、格子暗号を攻撃するためのより高速なアルゴリズムを開発した成果を、国際会議で発表している。

This year, the lattice theory is based on the analysis of the security of the open key. This research topic is very advanced. The main content of this research topic is to analyze the security of public key codes. One is the security analysis of RSA secret code based on lattice theory, and the other is the security analysis of RSA secret code. The security analysis of RSA password based on lattice theory RSA theory security guarantee, special password setting, secret key information leakage, security lattice theory analysis, long password theory representative 6 papers were collected and 5 papers were submitted for international conferences. The results of the ACISP are included in the ACISP Best Student Paper Award Second, the lattice security analysis results are introduced. The above RSA password includes, and now uses, the public key password mode, and the quantum computer to complete, and the security is greatly reduced, and the application is not used. The research of lattice code in quantum computer is the mainstream of code research in recent years. This year, the theory of the results of the study, the most timely theory of the study The results of this research are presented to the Chinese Academy of Sciences, and are rewarded for their information and research. In addition, similar context, grid code, high-speed development, international conference, etc.

项目成果

近似GCD問題のパラメータ解析，

近似GCD问题的参数分析，

• 发表时间: 2015
• 作者: Sekitani Y;Hayashida N;Takahashi J;Kozlovsky AA;Rudnitskiy S;Petrova A;Gutevych OK;Chorniy SA;Yamashita S;Takamura N;高安敦，國廣昇
• 通讯作者: 高安敦，國廣昇

Better Lattice Constructions for Solving Multivariate Linear Equations Modulo Unknown Divisors

• DOI: 10.1007/978-3-642-39059-3_9
• 发表时间: 2013-07
• 作者: Atsushi Takayasu;N. Kunihiro

Partial Key Exposure Attacks on RSA with Multiple Exponent Pairs

• DOI: 10.1007/978-3-319-40367-0_15
• 发表时间: 2016-07
• 作者: Atsushi Takayasu;N. Kunihiro

改善された安全性証明を持つGGHLiteパラメータ

GGHLite参数具有改进的安全认证

• 发表时间: 2015
• 期刊: 暗号と情報セキュリティシンポジウム（SCIS2015）予稿集
• 作者: Takeo S;Kimura K;Shirasuna K;Kuwayama T;Iwata H.;高安敦，高島克幸
• 通讯作者: 高安敦，高島克幸

General Bounds for Small Inverse Problems and Its Applications to Multi-Prime RSA

• DOI: 10.1007/978-3-319-15943-0_1
• 发表时间: 2014-12
• 作者: Atsushi Takayasu;N. Kunihiro