パステーブルを用いた楕円スカラー倍算における高階差分演算に関する考察

摘要

楕円曲線暗号における主な処理は，楕円曲線上の有理点Pのスカラー倍点kPの計算であるため．スカラー倍点の効率的な計算法の開発が重要な課題となっている．本研究では，あらかじめ作成されたパステーブルに従って，スカラー倍点kPを小さい計算量（コスト）で求める方法（これをパステーブル法と呼ぶ）について検討する．パステーブル法では，ROMなどで構成されるパステーブルに，各整数たに対してkPを最小コストで計算するパスが記憶されている.このパスはあらかじめ探索されたものであり，P＋Q,2Pだけでなく，比較的小さい整数λとμに対するλP±μQがパスを構成する基本演算として使われている．この論文では，パステーブルで与えられる最大の整数k_(max)に対してk_(max)≪Kなるようなスカラー倍点KPを求めるアルゴリズムの一つとして，高階差分の考え方を利用する方法を提案する．高階差分を用いた場合の計算量を評価し,差分を用いない場合や,通常のバイナリ法などの演算コストと比較する．%Efficient elliptic curve arithmetic is crucial for cryptosystems based on elliptic curves. Such cryptosys tems often require computing a scalar multiple kP of a base point P. Recently, some papers have proposed efficient algorithms to compute λP ± μQ directly for small integers λ and μ from given points P and Q. The authors have already developed some programs to find the path with the minimum cost for each scalar multiplication kP under the condition that several operations of λP±μQ can be used. We have also developed the minimum-cost path-table of scalar multiples kP for 1 ≦ k ≦ k_(max). In this paper, we present an algorithm to compute KP where k_(max) ≪ K. The algorithm adopts the higher order difference operation for the coefficients in b-ary representation of KP where b is the radix. We evaluate the costs due to our proposed algorithm in comparison with some conventional algorithms.