楕円曲線暗号の安全性解析

椭圆曲线密码技术的安全性分析

• 批准号: 19J10400
• 负责人: 小寺 健太
• 金额: $ 1.09万
• 依托单位: Osaka University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-25 至 2021-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19J10400/
• 关键词: 楕円曲線暗号; 安全性解析; 耐量子暗号; 同種写像暗号; 高速化; 同種写像計算; 同種写像

量子計算機の発展により楕円曲線暗号などの暗号は十分な安全性を保証できない恐れがある。そこで耐量子暗号と呼ばれる、量子計算機を用いた攻撃に耐えうる暗号の研究が重要となる。楕円曲線を用いた耐量子暗号の候補に同種写像暗号がある。同種写像暗号は他と比較して公開鍵長が短いという特長がある一方で、実行時間に課題がある。本年度は、引き続き同種写像暗号CSIDHの主要な計算である同種写像の計算手法を改良し、高速化に貢献した。既存の同種写像計算では、核の点のうち半数の座標を加法公式により計算し利用していた。本研究では楕円曲線の加法が持つ性質から、より少数の点を用いて同種写像を計算する手法を提案した。特に写像の次数が19から373であるとき、既存手法の中で最も効率が良いことを示した。この成果は国際会議WISA2020に採択され「Best Paper Gold」を受賞した。さらに提案手法の改良に取り組んだ。同種写像計算の高速化にはMeyerらの手法とBernsteinらの手法がある。本研究ではBernsteinらのアイデアを元に、核の点のうち同種写像計算に利用する半数の点の選び方を工夫し、さらに計算する点の数を削減した。体上の演算量について解析し、提案手法の原型であるMeyerらの手法と比べて、約12%の演算量を削減できることを示した。さらに提案手法をC言語で実装し、各種の同種写像計算の手法をCSIDHに適用した場合の性能を評価した。提案手法は512bitの体上のCSIDHを最も高速に実行できることを示した。本成果は国内会議で口頭発表を行った。一方で1024bitの体上のCSIDHにおいては、提案手法はMeyerらの手法を用いた場合よりも高速であるものの、Bernsteinらの手法を用いた場合には劣ることが明らかとなった。以上の全ての成果をまとめたものを論文誌に投稿し、本年3月に採択が決定した。

由于量子计算机的开发，诸如椭圆曲线加密等密码可能无法保证足够的安全性。因此，对使用量子计算机（称为量子密码学）来承受攻击的密码学的研究变得很重要。使用椭圆曲线的候选量子耐受性加密是同源映射密码学。虽然均匀的映射密码具有比其他型号短的优势，但它们在执行时间方面也有问题。今年，我们继续改善均匀映射的计算方法，这是均质映射加密CSIDH的主要计算，以促进加速。在现有的同源映射计算中，计算核中的一半点并由添加剂公式​​使用。在这项研究中，我们提出了一种使用较小的点来计算均匀图的方法，这是由于添加椭圆曲线的特性。这表明这是现有方法中最有效的，尤其是当地图订单在19至373之间。这项成就是在WISA 2020国际会议上选择的，并获得了“最佳纸质黄金”。此外，我们致力于改进所提出的方法。 Meyer等人的方法。和Bernstein等人，用于加快均匀的映射计算。在这项研究中，基于Bernstein等人的思想，我们设计了选择用于均匀映射计算的核点点的一半的方法，并进一步减少了要计算的点数。分析了该场上的计算量，并表明与Meyer等人的方法相比，计算量可以减少约12％，这是该方法的原型。此外，提出的方法是用C语言实施的，并在应用CSIDH时评估了各种均匀映射计算方法的性能。提出的方法表明，在512位主体上的CSIDH可以以最快的速度执行。结果是在国内会议上口服的。另一方面，对于1024位字段上的CSIDH，所提出的方法比使用Meyer等人的方法快，但已证明它不如Bernstein等人。上述所有结果的摘要已提交给期刊，并决定于今年3月通过。

项目成果

Efficient Algorithm to Compute Odd-Degree Isogenies Between Montgomery Curves for CSIDH

计算 CSIDH 蒙哥马利曲线之间奇数同源性的有效算法

• DOI: 10.1587/transfun.2020dmp0024
• 发表时间: 2021
• 期刊: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
• 作者: KODERA Kenta;CHENG Chen-Mou;MIYAJI Atsuko
• 通讯作者: MIYAJI Atsuko

2-ADD-Skip methodを用いた高速な同種写像計算アルゴリズムの改良

基于2-ADD-Skip方法的高速齐次映射计算算法的改进

• 发表时间: 2020
• 作者: Kenta Kodera;Chen-Mou Cheng;Atsuko Miyaji
• 通讯作者: Atsuko Miyaji

Montgomery曲線における同種写像計算の高速化について

关于加快蒙哥马利曲线上的齐次映射计算

• 发表时间: 2020
• 作者: Kenta Kodera;Chen-mou Cheng;Atsuko Miyaji
• 通讯作者: Atsuko Miyaji

Efficient Algorithm for Computing Odd-Degree Isogenies on Montgomery Curves

计算蒙哥马利曲线奇数同基因的高效算法

• DOI: 10.1007/978-3-030-65299-9_20
• 发表时间: 2020
• 期刊: Lecture Notes in Computer Science
• 作者: Kodera Kenta;Cheng Chen-Mou;Miyaji Atsuko
• 通讯作者: Miyaji Atsuko

Differences among Summation Polynomials over Various Forms of Elliptic Curves

各种形式的椭圆曲线上求和多项式的差异

• DOI: 10.1587/transfun.e102.a.1061
• 发表时间: 2019
• 期刊: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
• 作者: CHENG Chen-Mou;KODERA Kenta;MIYAJI Atsuko
• 通讯作者: MIYAJI Atsuko