最近、楕円曲線上のペアリングを用いた暗号が大きな注目を集めている。 ペアリング暗号の実装に適したr進数の非連接形式(rNAF)と、rNAF を計 算するアルゴリズムを提案する。rNAFの平均零濃度は漸近的にr/(2r-1) と証明でき、GF(r^m)上のペアリング暗号で使われるス カラー倍算をより高速に計算できる。我々の実験による と、r=3の場合、標準的な2進数非連接形式(NAF)と比較 して約4倍の高速化が実現できた。提案アルゴリズムは、 Boneh-FranklinのID暗号の暗号化プロセス、Boneh等の Short Signatureの署名生成プロセスなどで使われる。 |