ペアリング暗号の効率化とその実装

提高配对密码学的效率及其实现

• 批准号: 19J21086
• 负责人: 南條 由紀
• 金额: $ 1.6万
• 依托单位: Okayama University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-25 至 2022-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19J21086/
• 关键词: 公開鍵暗号; ペアリング暗号; 楕円曲線; 高速化

楕円曲線上で定義されるペアリングと呼ばれる写像を利用することで、様々な機能をもつ暗号が実現できる。しかしながら、ペアリングの計算にかかる計算量が大きいことが課題となっている。このため、本研究では計算量を減らすことを目的としている。本年度は主に下記の研究を行なった。ペアリング暗号の安全性と効率性を両立させるためには楕円曲線の選択が重要である。これまでは埋込み次数と呼ばれるパラメータkがk=12,16の楕円曲線が主に活用されてきたが、近年では新たにk=10,11,13,14などの楕円曲線が推奨されている。しかしながら、新たに推奨された楕円曲線については、最終べきと呼ばれる、ペアリングの一部の計算ステップの効率的な計算アルゴリズムが提案されていない。このため、本研究ではこれらの曲線に適用可能な一つの効率的な最終べきの計算アルゴリズムを導出した。既存の計算アルゴリズムと比較すると、k=10の楕円曲線についてはおよそ16%、k=11,13,14の楕円曲線についてはおよそ83%計算コストが削減できることが分かった。また、新たに推奨された楕円曲線だけでなく、kが素数の楕円曲線の重要度も上がっている。本研究では、まず小さな素数kをもつ曲線について最終べきの計算アルゴリズムを導出した。その結果に基づき、k=1 mod 6を満たす任意の素数kに対して適用可能な最終べきの計算アルゴリズムを導出した。既存の計算アルゴリズムの計算量オーダーはO(k^2)であるが、提案アルゴリズムの場合はO(k)である。このため、提案アルゴリズムを用いることにより明らかに計算量を削減できる。上記の成果はいずれも国際会議 The 9-th International Symposium on Computing and Networking (CANDAR’21)にて発表した。

通过使用在椭圆曲线上定义的称为配对的映射，可以实现具有各种功能的密码学。但问题是配对计算所需的计算量较大。因此，本研究旨在减少计算量。今年，我们主要开展了以下研究。为了实现配对密码学的安全性和效率，椭圆曲线的选择非常重要。到目前为止，主要使用参数 k 称为嵌入阶数 k = 12、16 的椭圆曲线，但近年来推荐了 k = 10、11、13、14 等的新椭圆曲线。然而，对于新推荐的椭圆曲线，尚未提出一种针对称为最终幂的配对计算步骤的一部分的有效计算算法。因此，在本研究中，我们推导了一种可应用于这些曲线的有效的最终功率计算算法。与现有计算算法相比，对于k=10的椭圆曲线，计算成本可降低约16%；对于k=11、13、14的椭圆曲线，计算成本可降低约83%。除了新推荐的椭圆曲线外，k为素数的椭圆曲线的重要性也在增加。在本研究中，我们首先推导了一种计算具有小素数 k 的曲线的最终幂的算法。根据结果​​，我们推导了一种计算最终幂的算法，该算法可应用于满足 k=1 mod 6 的任何素数 k。现有计算算法的复杂度为O(k^2)，而本文算法的复杂度为O(k)。因此，使用所提出的算法可以明显减少计算量。上述所有结果均在第九届国际计算与网络研讨会（CANDAR’21）上公布。

项目成果

任意のBLS曲線の最終べきのhard partについて

关于任何 BLS 曲线的最终幂的困难部分

• 发表时间: 2020
• 作者: 白勢政明;南條由紀
• 通讯作者: 南條由紀

A Construction Method of an Isomorphic Map between Quadratic Extension Fields Applicable for SIDH

适用于SIDH的二次可拓域同构映射的构造方法

• DOI: 10.1587/transfun.2020tal0002
• 发表时间: 2020
• 期刊: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
• 作者: NANJO Yuki;SHIRASE Masaaki;KUSAKA Takuya;NOGAMI Yasuyuki
• 通讯作者: NOGAMI Yasuyuki

An Optimal Curve Parameters for BLS12 Elliptic Curve Pairing and Its Efficiency Evaluation

BLS12椭圆曲线配对的最优曲线参数及其效率评估

• 发表时间: 2021
• 期刊: ,”Proceedings of International Conference on Consumer Electronics-Taiwan 2021 (ICCETW)
• 作者: [1]D. Hattori;Y. Takahashi;T. Tatara;Y. Nanjo;T. Kusaka and Y. Nogami
• 通讯作者: T. Kusaka and Y. Nogami

A Performance Analysis and Evaluation of SIDH Applied Several Implementation-Friendly Quadratic Extension Fields

SIDH应用几种易于实现的二次扩展域的性能分析与评估

• DOI: 10.15803/ijnc.10.2_227
• 发表时间: 2020
• 期刊: International Journal of Networking and Computing
• 作者: Nanjo Yuki;Shirase Masaaki;Kusaka Takuya;Nogami Yasuyuki
• 通讯作者: Nogami Yasuyuki

An Implementation and Evaluation of Pairing Library ELiPS for BLS Curve with Several Techniques

BLS曲线配对库ELiPS多种技术的实现与评估

• 发表时间: 2019
• 作者: Yuto Takahashi;Yuki Nanjo;Takuya Kusaka;Yasuyuki Nogami;Tadaki Kanenari;Tomoya Tatara
• 通讯作者: Tomoya Tatara