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

点击翻译按钮获取中文摘要

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