特許

J-GLOBAL ID：200903042477072356

ペアリング演算装置、ペアリング演算方法、およびペアリング演算プログラム

発明者： 小林 鉄太郎 ,  青木 和麻呂
出願人/特許権者： 日本電信電話株式会社
代理人 (1件)： 草野 卓
公報種別：公開公報
出願番号（国際出願番号）：特願2005-146556
公開番号（公開出願番号）：特開2006-323160
出願日： 2005年05月19日
公開日（公表日）： 2006年11月30日
要約：

【課題】ペアリングの演算に必要な演算量は通常の楕円演算にくらべると非常に大きいため、その演算速度が遅い。【解決手段】本発明では、有限体の性質を用いて高速化を行う。rを有限体GF(pk/2)上の元、fをMillerのアルゴリズムで求められる有限体GF(pk)上の元とすると、f’=rfを満足する有限体GF(pk)上の元f’へ写像するMillerアルゴリズムよりも計算量が少ないアルゴリズム用いて計算する。逆元を求める代わりに、乗算する元のpk乗を擬似逆元として求める。擬似逆元を用いることで、演算量の多いGF(pk)の元どうしの乗算を多項式展開できる。多項式展開によって演算量の多い項を繰り返し計算の共通の項としてあらかじめ求めておくことで高速化を行う。【選択図】図7

請求項（抜粋）：

pは素数または素数のべき乗、kは偶数であって、有限体GF(p)上の楕円曲線上の点Pと有限体GF(pk)上の楕円曲線上の点Qを入力とし、入力された点から有限体GF(pk)上の元f’を求める擬似Miller演算部と、求めた有限体上の元を有限体GF(pk)上の元e(P,Q)に写像し、出力するべき乗演算部とを備えるペアリング演算装置において、 XとYをGF(pk)上の元、X^をXの共役元、c、d、e、g、hをGF(p)上の元とする場合に、 PとQから有限体GF(pk)上の元fを求めるMillerアルゴリズムを、Millerアルゴリズム内で用いる有限体GF(pk)上の元Lの逆元の代わりに

IPC (1件)：

G09C 1/00

FI (1件)：

G09C1/00 650A

Fターム (4件)：

5J104AA18 ,  5J104AA25 ,  5J104NA16 ,  5J104PA07

引用特許：

出願人引用 (2件)

• ペアリング暗号装置、ペアリング暗号演算プログラム
  公報種別：公開公報   出願番号：特願2002-343942   出願人：富士通株式会社, 高木剛
• 楕円曲線ペアリング演算装置
  公報種別：公開公報   出願番号：特願2004-135867   出願人：株式会社日立製作所

引用文献：

出願人引用 (3件)

• “ペアリング高速実装”
• “Compressed Jacobian Coordinates for OEF”
• “ペアリングに関する最近の研究動向”