Greedy algorithmを改良したDBNS利用による効率的な楕円曲線暗号のスカラー倍算

摘要

楕円曲線暗号の暗号化処理は主にスカラー倍算(kP)により構成される.その高速化に向けた有力な手法として，バイナリ表現に比べ，Non-Zero digitの数を大きく削減可能なDBNS(Doubl&Base Number System)表現を利用する手法がある.しかしながら，DBNSを利用した既存手法では，DBNS表現の導出にGreedy Algorithmを用いており，スカラー倍算の高速化において最適なDBNS表現の導出が困難である.本研究では，既存研究に対し，よりスカラー倍算の高速化に適したDBNS表現の導出方法について提案する.%The dominant operation of the Elliptic Curve Cryptgraphy is to compute the scalar multiplication(kP).The Double-Base Number System(DBNS) gives fewer non-zero digits than binary representation or NAF. This is why it is a very efficient method to compute the scalar multiplication. But existing research uses the Greedy algorithm to generate DBNS representation from scalar k， and it has a problem not to be able to generate best representation for efficient scalar multiplication, We propose an improved Greedy algorithm, which generates a suitable DBNS representation for efficient scalar multiplication.