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

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

• 批准号: 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 = 12和16的椭圆曲线，称为嵌入式顺序，但是近年来，新推荐的椭圆曲线（例如k = 10、11、13和14）。但是，对于新推荐的椭圆曲线，尚未提出对配对的某些计算步骤（称为最终实用程序）的有效计算算法。因此，这项研究得出了可以应用于这些曲线的一种有效的最终功率计算算法。与现有的计算算法相比，发现对于K = 10的椭圆曲线，对于k = 11,13,14的椭圆形曲线，计算成本可能会降低约16％，约为83％。除了新推荐的椭圆曲线外，具有Prime K的椭圆曲线的重要性也增加了。在这项研究中，我们首先得出了一种用于计算小质量k曲线的最终功率的算法。根据结果​​，我们得出了最终功率计算的算法，该算法适用于满足k = 1 mod 6的任何素数k。现有计算算法的计算复杂性顺序为o（k^2），但在拟议的算法中，它是O（k）。因此，使用所提出的算法清楚地减少了计算量。上述所有结果均在国际会议上介绍了第9-1届计算和网络国际研讨会（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

FK12曲線上のペアリングにおける最終べきアルゴリズムの改良

改进了 FK12 曲线上配对的最终功率算法

• 发表时间: 2022
• 作者: 池坂和真;南條由紀;小寺雄太;日下卓也;野上保之
• 通讯作者: 野上保之