Top > Search of International Patents > PAIRING COMPUTATION DEVICE, PAIRING COMPUTATION METHOD, AND RECORDING MEDIUM WHERE PAIRING COMPUTATION PROGRAM IS RECORDED

PAIRING COMPUTATION DEVICE, PAIRING COMPUTATION METHOD, AND RECORDING MEDIUM WHERE PAIRING COMPUTATION PROGRAM IS RECORDED meetings

Foreign code F110002665
File No. S2008-0053-C0
Posted date Apr 6, 2011
Country WIPO
International application number 2008JP069683
International publication number WO 2009/057656
Date of international filing Oct 29, 2008
Date of international publication May 7, 2009
Priority data
  • P2007-282487 (Oct 30, 2007) JP
Title PAIRING COMPUTATION DEVICE, PAIRING COMPUTATION METHOD, AND RECORDING MEDIUM WHERE PAIRING COMPUTATION PROGRAM IS RECORDED meetings
Abstract A paring computation device, a pairing computation method, and a recording medium where a pairing computation program is recorded all enabling a pairing computation at high speed. An Ate pairing e(Q, P) is defined as formula (I). If k is an integral multiple of 3, 4, or 6, the computation of a rational function necessary to derive a Miller function fs,Q(P) is conducted in a true subfield specified by a twist curve using a quadratic or third-power non-residue v which takes on one when exponentiation of fs,Q(P) to (qk-1)/r-th power is carried out.
Scope of claims (In Japanese)
【請求項1】 曲線の式がy2=x3+ax+b,a∈Fq,b∈Fq(q:3より大きい素数のべき乗)で与えられ、埋込み次数が2h次(h:自然数)で、Fq 2hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をE、素数位数rの有理点の集合をE[r]とし、φqをフロベニウス自己準同型写像として、
  G1=E[r]∩Ker(φq-[1])
  G2=E[r]∩Ker(φq-[q])
により、
  e:G2×G1→F* q 2h/(F* q 2h)r
である非退化な双線形写像として定義されるAteペアリングeによって、P∈G1、Q∈G2とし、フロベニウス自己準同型写像φqのトレースtを用いてs=t-1とし、ミラー関数fs,Q(・)を用いて、
【数式1】
としてAteペアリングe(Q,P)を演算するペアリング演算装置において、
 fs,Q(P)の導出に必要となる有理関数の演算を、このfs,Q(P)の(q2h-1)/r乗のべき乗算の演算によって1となる平方非剰余なv∈Fq hを用いて、E(Fq h)のツイスト曲線E'(Fq h):y2=x3+av-2x+bv-3による真部分体上で行うべく、
 前記s=t-1、P∈E(Fq)であるP、Q'∈E'(Fq h)であるQ'の入力を受け付ける入力手段と、
 有理点Pの座標(xP,yP)に対して、n←xPv-1、m←yPv-3/2の代入演算を行うとともに、f←1、T'←Q'の代入演算を行う代入手段と、
 有理点Tを通る接線lT,T(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,T(xP,yP)を演算する代わりに、lT,T(xP,yP)v-3/2をlT',T'(n,m)で演算して、f←f2・lT',T'(n,m)の代入演算を行う第1演算手段と、
 T'←2T'の代入演算を行う第2演算手段と、
 前記sを2進数表示とした場合の所定のビットの値が1である場合に、有理点TとQを通る直線lT,Q(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,Q(xP,yP)を演算する代わりに、lT,Q(xP,yP)v-3/2をlT',Q'(n,m)で演算して、f←f・lT',Q'(n,m)の代入演算を行う第3演算手段と、
 前記sを2進数表示とした場合の所定のビットの値が1である場合に、T'←T'+Q'の代入演算を行う第4演算手段と、
 (q2h-1)/r乗のべき乗算を演算する第5演算手段と
を備えたことを特徴とするペアリング演算装置。

【請求項2】 曲線の式がy2=x3+a,a∈Fq(q:3より大きい素数のべき乗)で与えられ、埋込み次数が3h次(h:自然数)で、Fq 3hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をE、素数位数rの有理点の集合をE[r]とし、φqをフロベニウス自己準同型写像として、
  G1=E[r]∩Ker(φq-[1])
  G2=E[r]∩Ker(φq-[q])
により、
  e:G2×G1→F* q 3h/(F* q 3h)r
である非退化な双線形写像として定義されるAteペアリングeによって、P∈G1、Q∈G2とし、フロベニウス自己準同型写像φqのトレースtを用いてs=t-1とし、ミラー関数fs,Q(・)を用いて、
【数式2】
としてAteペアリングe(Q,P)を演算するペアリング演算装置において、
 fs,Q(P)の導出に必要となる有理関数の演算を、このfs,Q(P)の(q3h-1)/r乗のべき乗算の演算によって1となる平方剰余かつ3乗非剰余なv∈Fq hを用いて、E(Fq h)のツイスト曲線E'(Fq h):y2=x3+av-1による真部分体上で行うべく、
 前記s=t-1、P∈E(Fq)であるP、Q'∈E'(Fq h)であるQ'の入力を受け付ける入力手段と、
 有理点Pの座標(xP,yP)に対して、n←xPv-1/3、m←yPv-1/2の代入演算を行うとともに、f←1、T'←Q'の代入演算を行う代入手段と、
 有理点Tを通る接線lT,T(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,T(xP,yP)を演算する代わりに、lT,T(xP,yP)v-1/2をlT',T'(n,m)で演算して、f←f2・lT',T'(n,m)の代入演算を行う第1演算手段と、
 T'←2T'の代入演算を行う第2演算手段と、
 前記sを2進数表示とした場合の所定のビットの値が1である場合に、有理点TとQを通る直線lT,Q(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,Q(xP,yP)を演算する代わりに、lT,Q(xP,yP)v-1/2をlT',Q'(n,m)で演算して、f←f・lT',Q'(n,m)の代入演算を行う第3演算手段と、
 前記sを2進数表示とした場合の所定のビットの値が1である場合に、T'←T'+Q'の代入演算を行う第4演算手段と、
 (q3h-1)/r乗のべき乗算を演算する第5演算手段と
を備えたことを特徴とするペアリング演算装置。

【請求項3】 曲線の式がy2=x3+ax,a∈Fq(q:3より大きい素数のべき乗)で与えられ、埋込み次数が4h次(h:自然数)で、4がqh-1を割り切るものとし、Fq 4hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をE、素数位数rの有理点の集合をE[r]とし、φqをフロベニウス自己準同型写像として、
  G1=E[r]∩Ker(φq-[1])
  G2=E[r]∩Ker(φq-[q])
により、
  e:G2×G1→F* q 4h/(F* q 4h)r
である非退化な双線形写像として定義されるAteペアリングeによって、P∈G1、Q∈G2とし、フロベニウス自己準同型写像φqのトレースtを用いてs=t-1とし、ミラー関数fs,Q(・)を用いて、
【数式3】
としてAteペアリングe(Q,P)を演算するペアリング演算装置において、
 fs,Q(P)の導出に必要となる有理関数の演算を、このfs,Q(P)の(q4h-1)/r乗のべき乗算の演算によって1となる平方非剰余なv∈Fq hを用いて、E(Fq h)のツイスト曲線E'(Fq h):y2=x3+av-1xによる真部分体上で行うべく、
 前記s=t-1、P∈E(Fq)であるP、Q'∈E'(Fq h)であるQ'の入力を受け付ける入力手段と、
 有理点Pの座標(xP,yP)に対して、n←xPv-1/2、m←yPv-3/4の代入演算を行うとともに、f←1、T'←Q'の代入演算を行う代入手段と、
 有理点Tを通る接線lT,T(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,T(xP,yP)を演算する代わりに、lT,T(xP,yP)v-3/4をlT',T'(n,m)で演算して、f←f2・lT',T'(n,m)の代入演算を行う第1演算手段と、
 T'←2T'の代入演算を行う第2演算手段と、
 前記sを2進数表示とした場合の所定のビットの値が1である場合に、有理点TとQを通る直線lT,Q(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,Q(xP,yP)を演算する代わりに、lT,Q(xP,yP)v-3/4をlT',Q'(n,m)で演算して、f←f・lT',Q'(n,m)の代入演算を行う第3演算手段と、
 前記sを2進数表示とした場合の所定のビットの値が1である場合に、T'←T'+Q'の代入演算を行う第4演算手段と、
 (q4h-1)/r乗のべき乗算を演算する第5演算手段と
を備えたことを特徴とするペアリング演算装置。

【請求項4】 曲線の式がy2=x3+a,a∈Fq(q:3より大きい素数のべき乗)で与えられ、埋込み次数が6h次(h:自然数)で、Fq 6hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をE、素数位数rの有理点の集合をE[r]とし、φqをフロベニウス自己準同型写像として、
  G1=E[r]∩Ker(φq-[1])
  G2=E[r]∩Ker(φq-[q])
により、
  e:G2×G1→F* q 6h/(F* q 6h)r
である非退化な双線形写像として定義されるAteペアリングeによって、P∈G1、Q∈G2とし、フロベニウス自己準同型写像φqのトレースtを用いてs=t-1とし、ミラー関数fs,Q(・)を用いて、
【数式4】
としてAteペアリングe(Q,P)を演算するペアリング演算装置において、
 fs,Q(P)の導出に必要となる有理関数の演算を、このfs,Q(P)の(q6h-1)/r乗のべき乗算の演算によって1となる平方非剰余かつ3乗非剰余なv∈Fq hを用いて、E(Fq h)のツイスト曲線E'(Fq h):y2=x3+av-1による真部分体上で行うべく、
 前記s=t-1、P∈E(Fq)であるP、Q'∈E'(Fq h)であるQ'の入力を受け付ける入力手段と、
 有理点Pの座標(xP,yP)に対して、n←xPv-1/3、m←yPv-1/2の代入演算を行うとともに、f←1、T'←Q'の代入演算を行う代入手段と、
 有理点Tを通る接線lT,T(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,T(xP,yP)を演算する代わりに、lT,T(xP,yP)v-1/2をlT',T'(n,m)で演算して、f←f2・lT',T'(n,m)の代入演算を行う第1演算手段と、
 T'←2T'の代入演算を行う第2演算手段と、
 前記sを2進数表示とした場合の所定のビットの値が1である場合に、有理点TとQを通る直線lT,Q(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,Q(xP,yP)を演算する代わりに、lT,Q(xP,yP)v-1/2をlT',Q'(n,m)で演算して、f←f・lT',Q'(n,m)の代入演算を行う第3演算手段と、
 前記sを2進数表示とした場合の所定のビットの値が1である場合に、T'←T'+Q'の代入演算を行う第4演算手段と、
 (q6h-1)/r乗のべき乗算を演算する第5演算手段と
を備えたことを特徴とするペアリング演算装置。

【請求項5】 曲線の式がy2=x3+ax+b,a∈Fq,b∈Fq(q:3より大きい素数のべき乗)で与えられ、埋込み次数が2h次(h:自然数)で、Fq 2hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をE、素数位数rの有理点の集合をE[r]とし、φqをフロベニウス自己準同型写像として、
  G1=E[r]∩Ker(φq-[1])
  G2=E[r]∩Ker(φq-[q])
により、
  e:G2×G1→F* q 2h/(F* q 2h)r
である非退化な双線形写像として定義されるAteペアリングeによって、P∈G1、Q∈G2とし、フロベニウス自己準同型写像φqのトレースtを用いてs=t-1とし、ミラー関数fs,Q(・)を用いて、
【数式5】
としてAteペアリングe(Q,P)を電子計算機で演算するペアリング演算方法において、
 fs,Q(P)の(q2h-1)/r乗のべき乗算の演算によって1となる平方非剰余なv∈Fq h、E(Fq h)のツイスト曲線E'(Fq h):y2=x3+av-2x+bv-3を用いて、
 前記電子計算機を入力手段として機能させて、前記s=t-1、P∈E(Fq)であるP、Q'∈E'(Fq h)であるQ'の入力を受け付けるステップと、
 前記電子計算機を代入手段として機能させて、有理点Pの座標(xP,yP)に対して、n←xPv-1、m←yPv-3/2の代入演算を行うステップと、
 前記電子計算機を代入手段として機能させて、f←1、T'←Q'の代入演算を行うステップと、
 前記電子計算機を第1演算手段として機能させて、有理点Tを通る接線lT,T(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,T(xP,yP)を演算する代わりに、lT,T(xP,yP)v-3/2をlT',T'(n,m)で演算して、f←f2・lT',T'(n,m)の代入演算を行うステップと、
 前記電子計算機を第2演算手段として機能させて、T'←2T'の代入演算を行うステップと、
 前記電子計算機を第3演算手段として機能させて、前記sを2進数表示とした場合の所定のビットの値が1である場合に、有理点TとQを通る直線lT,Q(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,Q(xP,yP)を演算する代わりに、lT,Q(xP,yP)v-3/2をlT',Q'(n,m)で演算して、f←f・lT',Q'(n,m)の代入演算を行うステップと、
 前記電子計算機を第4演算手段として機能させて、前記sを2進数表示とした場合の所定のビットの値が1である場合に、T'←T'+Q'の代入演算を行うステップと、
 前記電子計算機を第5演算手段として機能させて、(q2h-1)/r乗のべき乗算の演算を行うステップと
を有することを特徴とするペアリング演算方法。

【請求項6】 曲線の式がy2=x3+a,a∈Fq(q:3より大きい素数のべき乗)で与えられ、埋込み次数が3h次(h:自然数)で、Fq 3hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をE、素数位数rの有理点の集合をE[r]とし、φqをフロベニウス自己準同型写像として、
  G1=E[r]∩Ker(φq-[1])
  G2=E[r]∩Ker(φq-[q])
により、
  e:G2×G1→F* q 3h/(F* q 3h)r
である非退化な双線形写像として定義されるAteペアリングeによって、P∈G1、Q∈G2とし、フロベニウス自己準同型写像φqのトレースtを用いてs=t-1とし、ミラー関数fs,Q(・)を用いて、
【数式6】
としてAteペアリングe(Q,P)を電子計算機で演算するペアリング演算方法において、
 fs,Q(P)の(q3h-1)/r乗のべき乗算の演算によって1となる平方剰余かつ3乗非剰余なv∈Fq h、E(Fq h)のツイスト曲線E'(Fq h):y2=x3+av-1を用いて、
 前記電子計算機を入力手段として機能させて、前記s=t-1、P∈E(Fq)であるP、Q'∈E'(Fq h)であるQ'の入力を受け付けるステップと、
 前記電子計算機を代入手段として機能させて、有理点Pの座標(xP,yP)に対して、n←xPv-1/3、m←yPv-1/2の代入演算を行うステップと、
 前記電子計算機を代入手段として機能させて、f←1、T'←Q'の代入演算を行うステップと、
 前記電子計算機を第1演算手段として機能させて、有理点Tを通る接線lT,T(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,T(xP,yP)を演算する代わりに、lT,T(xP,yP)v-1/2をlT',T'(n,m)で演算して、f←f2・lT',T'(n,m)の代入演算を行うステップと、
 前記電子計算機を第2演算手段として機能させて、T'←2T'の代入演算を行うステップと、
 前記電子計算機を第3演算手段として機能させて、前記sを2進数表示とした場合の所定のビットの値が1である場合に、有理点TとQを通る直線lT,Q(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,Q(xP,yP)を演算する代わりに、lT,Q(xP,yP)v-1/2をlT',Q'(n,m)で演算して、f←f・lT',Q'(n,m)の代入演算を行うステップと、
 前記電子計算機を第4演算手段として機能させて、前記sを2進数表示とした場合の所定のビットの値が1である場合に、T'←T'+Q'の代入演算を行うステップと、
 前記電子計算機を第5演算手段として機能させて、(q3h-1)/r乗のべき乗算の演算を行うステップと
を有することを特徴とするペアリング演算方法。

【請求項7】 曲線の式がy2=x3+ax,a∈Fq(q:3より大きい素数のべき乗)で与えられ、埋込み次数が4h次(h:自然数)で、4がqh-1を割り切るものとし、Fq 4hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をE、素数位数rの有理点の集合をE[r]とし、φqをフロベニウス自己準同型写像として、
  G1=E[r]∩Ker(φq-[1])
  G2=E[r]∩Ker(φq-[q])
により、
  e:G2×G1→F* q 4h/(F* q 4h)r
である非退化な双線形写像として定義されるAteペアリングeによって、P∈G1、Q∈G2とし、フロベニウス自己準同型写像φqのトレースtを用いてs=t-1とし、ミラー関数fs,Q(・)を用いて、
【数式7】
としてAteペアリングe(Q,P)を電子計算機で演算するペアリング演算方法において、
 fs,Q(P)の(q4h-1)/r乗のべき乗算の演算によって1となる平方非剰余なv∈Fq h、E(Fq h)のツイスト曲線E'(Fq h):y2=x3+av-1xを用いて、
 前記電子計算機を入力手段として機能させて、前記s=t-1、P∈E(Fq)であるP、Q'∈E'(Fq h)であるQ'の入力を受け付けるステップと、
 前記電子計算機を代入手段として機能させて、有理点Pの座標(xP,yP)に対して、n←xPv-1/2、m←yPv-3/4の代入演算を行うステップと、
 前記電子計算機を代入手段として機能させて、f←1、T'←Q'の代入演算を行うステップと、
 前記電子計算機を第1演算手段として機能させて、有理点Tを通る接線lT,T(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,T(xP,yP)を演算する代わりに、lT,T(xP,yP)v-3/4をlT',T'(n,m)で演算して、f←f2・lT',T'(n,m)の代入演算を行うステップと、
 前記電子計算機を第2演算手段として機能させて、T'←2T'の代入演算を行うステップと、
 前記電子計算機を第3演算手段として機能させて、前記sを2進数表示とした場合の所定のビットの値が1である場合に、有理点TとQを通る直線lT,Q(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,Q(xP,yP)を演算する代わりに、lT,Q(xP,yP)v-3/4をlT',Q'(n,m)で演算して、f←f・lT',Q'(n,m)の代入演算を行うステップと、
 前記電子計算機を第4演算手段として機能させて、前記sを2進数表示とした場合の所定のビットの値が1である場合に、T'←T'+Q'の代入演算を行うステップと、
 前記電子計算機を第5演算手段として機能させて、(q4h-1)/r乗のべき乗算の演算を行うステップと
を有することを特徴とするペアリング演算方法。

【請求項8】 曲線の式がy2=x3+a,a∈Fq(q:3より大きい素数のべき乗)で与えられ、埋込み次数が6h次(h:自然数)で、Fq 6hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をE、素数位数rの有理点の集合をE[r]とし、φqをフロベニウス自己準同型写像として、
  G1=E[r]∩Ker(φq-[1])
  G2=E[r]∩Ker(φq-[q])
により、
  e:G2×G1→F* q 6h/(F* q 6h)r
である非退化な双線形写像として定義されるAteペアリングeによって、P∈G1、Q∈G2とし、フロベニウス自己準同型写像φqのトレースtを用いてs=t-1とし、ミラー関数fs,Q(・)を用いて、
【数式8】
としてAteペアリングe(Q,P)を電子計算機で演算するペアリング演算方法において、
 fs,Q(P)の(q6h-1)/r乗のべき乗算の演算によって1となる平方非剰余かつ3乗非剰余なv∈Fq h、E(Fq h)のツイスト曲線E'(Fq h):y2=x3+av-1を用いて、
 前記電子計算機を入力手段として機能させて、前記s=t-1、P∈E(Fq)であるP、Q'∈E'(Fq h)であるQ'の入力を受け付けるステップと、
 前記電子計算機を代入手段として機能させて、有理点Pの座標(xP,yP)に対して、n←xPv-1/3、m←yPv-1/2の代入演算を行うステップと、
 前記電子計算機を代入手段として機能させて、f←1、T'←Q'の代入演算を行うステップと、
 前記電子計算機を第1演算手段として機能させて、有理点Tを通る接線lT,T(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,T(xP,yP)を演算する代わりに、lT,T(xP,yP)v-1/2をlT',T'(n,m)で演算して、f←f2・lT',T'(n,m)の代入演算を行うステップと、
 前記電子計算機を第2演算手段として機能させて、T'←2T'の代入演算を行うステップと、
 前記電子計算機を第3演算手段として機能させて、前記sを2進数表示とした場合の所定のビットの値が1である場合に、有理点TとQを通る直線lT,Q(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,Q(xP,yP)を演算する代わりに、lT,Q(xP,yP)v-1/2をlT',Q'(n,m)で演算して、f←f・lT',Q'(n,m)の代入演算を行うステップと、
 前記電子計算機を第4演算手段として機能させて、前記sを2進数表示とした場合の所定のビットの値が1である場合に、T'←T'+Q'の代入演算を行うステップと、
 前記電子計算機を第5演算手段として機能させて、(q6h-1)/r乗のべき乗算の演算を行うステップと
を有することを特徴とするペアリング演算方法。

【請求項9】 曲線の式がy2=x3+ax+b,a∈Fq,b∈Fq(q:3より大きい素数のべき乗)で与えられ、埋込み次数が2h次(h:自然数)で、Fq 2hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をE、素数位数rの有理点の集合をE[r]とし、φqをフロベニウス自己準同型写像として、
  G1=E[r]∩Ker(φq-[1])
  G2=E[r]∩Ker(φq-[q])
により、
  e:G2×G1→F* q 2h/(F* q 2h)r
である非退化な双線形写像として定義されるAteペアリングeによって、P∈G1、Q∈G2とし、フロベニウス自己準同型写像φqのトレースtを用いてs=t-1とし、ミラー関数fs,Q(・)を用いて、
【数式9】
としてAteペアリングe(Q,P)を電子計算機に演算させるペアリング演算プログラムにおいて、
 fs,Q(P)の(q2h-1)/r乗のべき乗算の演算によって1となる平方非剰余なv∈Fq h、E(Fq h)のツイスト曲線E'(Fq h):y2=x3+av-2x+bv-3を用いて、
 前記電子計算機を入力手段として機能させて、前記s=t-1、P∈E(Fq)であるP、Q'∈E'(Fq h)であるQ'の入力を受け付けさせるステップと、
 前記電子計算機を代入手段として機能させて、有理点Pの座標(xP,yP)に対して、n←xPv-1、m←yPv-3/2の代入演算を行わせるステップと、
 前記電子計算機を代入手段として機能させて、f←1、T'←Q'の代入演算を行わせるステップと、
 前記電子計算機を第1演算手段として機能させて、有理点Tを通る接線lT,T(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,T(xP,yP)を演算する代わりに、lT,T(xP,yP)v-3/2をlT',T'(n,m)で演算して、f←f2・lT',T'(n,m)の代入演算を行わせるステップと、
 前記電子計算機を第2演算手段として機能させて、T'←2T'の代入演算を行わせるステップと、
 前記電子計算機を第3演算手段として機能させて、前記sを2進数表示とした場合の所定のビットの値が1である場合に、有理点TとQを通る直線lT,Q(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,Q(xP,yP)を演算する代わりに、lT,Q(xP,yP)v-3/2をlT',Q'(n,m)で演算して、f←f・lT',Q'(n,m)の代入演算を行わせるステップと、
 前記電子計算機を第4演算手段として機能させて、前記sを2進数表示とした場合の所定のビットの値が1である場合に、T'←T'+Q'の代入演算を行わせるステップと、
 前記電子計算機を第5演算手段として機能させて、(q2h-1)/r乗のべき乗算の演算を行わせるステップと
を前記電子計算機に実行させることを特徴とするペアリング演算プログラムを記録した記録媒体。

【請求項10】 曲線の式がy2=x3+a,a∈Fq(q:3より大きい素数のべき乗)で与えられ、埋込み次数が3h次(h:自然数)で、Fq 3hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をE、素数位数rの有理点の集合をE[r]とし、φqをフロベニウス自己準同型写像として、
  G1=E[r]∩Ker(φq-[1])
  G2=E[r]∩Ker(φq-[q])
により、
  e:G2×G1→F* q 3h/(F* q 3h)r
である非退化な双線形写像として定義されるAteペアリングeによって、P∈G1、Q∈G2とし、フロベニウス自己準同型写像φqのトレースtを用いてs=t-1とし、ミラー関数fs,Q(・)を用いて、
【数式10】
としてAteペアリングe(Q,P)を電子計算機に演算させるペアリング演算プログラムにおいて、
 fs,Q(P)の(q3h-1)/r乗のべき乗算の演算によって1となる平方剰余かつ3乗非剰余なv∈Fq h、E(Fq h)のツイスト曲線E'(Fq h):y2=x3+av-1を用いて、
 前記電子計算機を入力手段として機能させて、前記s=t-1、P∈E(Fq)であるP、Q'∈E'(Fq h)であるQ'の入力を受け付けさせるステップと、
 前記電子計算機を代入手段として機能させて、有理点Pの座標(xP,yP)に対して、n←xPv-1/3、m←yPv-1/2の代入演算を行わせるステップと、
 前記電子計算機を代入手段として機能させて、f←1、T'←Q'の代入演算を行わせるステップと、
 前記電子計算機を第1演算手段として機能させて、有理点Tを通る接線lT,T(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,T(xP,yP)を演算する代わりに、lT,T(xP,yP)v-1/2をlT',T'(n,m)で演算して、f←f2・lT',T'(n,m)の代入演算を行わせるステップと、
 前記電子計算機を第2演算手段として機能させて、T'←2T'の代入演算を行わせるステップと、
 前記電子計算機を第3演算手段として機能させて、前記sを2進数表示とした場合の所定のビットの値が1である場合に、有理点TとQを通る直線lT,Q(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,Q(xP,yP)を演算する代わりに、lT,Q(xP,yP)v-1/2をlT',Q'(n,m)で演算して、f←f・lT',Q'(n,m)の代入演算を行わせるステップと、
 前記電子計算機を第4演算手段として機能させて、前記sを2進数表示とした場合の所定のビットの値が1である場合に、T'←T'+Q'の代入演算を行わせるステップと、
 前記電子計算機を第5演算手段として機能させて、(q3h-1)/r乗のべき乗算の演算を行わせるステップと
を前記電子計算機に実行させることを特徴とするペアリング演算プログラムを記録した記録媒体。

【請求項11】 曲線の式がy2=x3+ax,a∈Fq(q:3より大きい素数のべき乗)で与えられ、埋込み次数が4h次(h:自然数)で、4がqh-1を割り切るものとし、Fq 4hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をE、素数位数rの有理点の集合をE[r]とし、φqをフロベニウス自己準同型写像として、
  G1=E[r]∩Ker(φq-[1])
  G2=E[r]∩Ker(φq-[q])
により、
  e:G2×G1→F* q 4h/(F* q 4h)r
である非退化な双線形写像として定義されるAteペアリングeによって、P∈G1、Q∈G2とし、フロベニウス自己準同型写像φqのトレースtを用いてs=t-1とし、ミラー関数fs,Q(・)を用いて、
【数式11】
としてAteペアリングe(Q,P)を電子計算機に演算させるペアリング演算プログラムにおいて、
 fs,Q(P)の(q4h-1)/r乗のべき乗算の演算によって1となる平方非剰余なv∈Fq h、E(Fq h)のツイスト曲線E'(Fq h):y2=x3+av-1xを用いて、
 前記電子計算機を入力手段として機能させて、前記s=t-1、P∈E(Fq)であるP、Q'∈E'(Fq h)であるQ'の入力を受け付けさせるステップと、
 前記電子計算機を代入手段として機能させて、有理点Pの座標(xP,yP)に対して、n←xPv-1/2、m←yPv-3/4の代入演算を行わせるステップと、
 前記電子計算機を代入手段として機能させて、f←1、T'←Q'の代入演算を行わせるステップと、
 前記電子計算機を第1演算手段として機能させて、有理点Tを通る接線lT,T(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,T(xP,yP)を演算する代わりに、lT,T(xP,yP)v-3/4をlT',T'(n,m)で演算して、f←f2・lT',T'(n,m)の代入演算を行わせるステップと、
 前記電子計算機を第2演算手段として機能させて、T'←2T'の代入演算を行わせるステップと、
 前記電子計算機を第3演算手段として機能させて、前記sを2進数表示とした場合の所定のビットの値が1である場合に、有理点TとQを通る直線lT,Q(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,Q(xP,yP)を演算する代わりに、lT,Q(xP,yP)v-3/4をlT',Q'(n,m)で演算して、f←f・lT',Q'(n,m)の代入演算を行わせるステップと、
 前記電子計算機を第4演算手段として機能させて、前記sを2進数表示とした場合の所定のビットの値が1である場合に、T'←T'+Q'の代入演算を行わせるステップと、
 前記電子計算機を第5演算手段として機能させて、(q4h-1)/r乗のべき乗算の演算を行わせるステップと
を前記電子計算機に実行させることを特徴とするペアリング演算プログラムを記録した記録媒体。

【請求項12】 曲線の式がy2=x3+a,a∈Fq(q:3より大きい素数のべき乗)で与えられ、埋込み次数が6h次(h:自然数)で、Fq 6hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をE、素数位数rの有理点の集合をE[r]とし、φqをフロベニウス自己準同型写像として、
  G1=E[r]∩Ker(φq-[1])
  G2=E[r]∩Ker(φq-[q])
により、
  e:G2×G1→F* q 6h/(F* q 6h)r
である非退化な双線形写像として定義されるAteペアリングeによって、P∈G1、Q∈G2とし、フロベニウス自己準同型写像φqのトレースtを用いてs=t-1とし、ミラー関数fs,Q(・)を用いて、
【数式12】
としてAteペアリングe(Q,P)を電子計算機に演算させるペアリング演算プログラムにおいて、
 fs,Q(P)の(q6h-1)/r乗のべき乗算の演算によって1となる平方非剰余かつ3乗非剰余なv∈Fq h、E(Fq h)のツイスト曲線E'(Fq h):y2=x3+av-1を用いて、
 前記電子計算機を入力手段として機能させて、前記s=t-1、P∈E(Fq)であるP、Q'∈E'(Fq h)であるQ'の入力を受け付けさせるステップと、
 前記電子計算機を代入手段として機能させて、有理点Pの座標(xP,yP)に対して、n←xPv-1/3、m←yPv-1/2の代入演算を行わせるステップと、
 前記電子計算機を代入手段として機能させて、f←1、T'←Q'の代入演算を行わせるステップと、
 前記電子計算機を第1演算手段として機能させて、有理点Tを通る接線lT,T(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,T(xP,yP)を演算する代わりに、lT,T(xP,yP)v-1/2をlT',T'(n,m)で演算して、f←f2・lT',T'(n,m)の代入演算を行わせるステップと、
 前記電子計算機を第2演算手段として機能させて、T'←2T'の代入演算を行わせるステップと、
 前記電子計算機を第3演算手段として機能させて、前記sを2進数表示とした場合の所定のビットの値が1である場合に、有理点TとQを通る直線lT,Q(x,y)=0の左辺に有理点Pの座標(xP,yP)を代入した値lT,Q(xP,yP)を演算する代わりに、lT,Q(xP,yP)v-1/2をlT',Q'(n,m)で演算して、f←f・lT',Q'(n,m)の代入演算を行わせるステップと、
 前記電子計算機を第4演算手段として機能させて、前記sを2進数表示とした場合の所定のビットの値が1である場合に、T'←T'+Q'の代入演算を行わせるステップと、
 前記電子計算機を第5演算手段として機能させて、(q6h-1)/r乗のべき乗算の演算を行わせるステップと
を前記電子計算機に実行させることを特徴とするペアリング演算プログラムを記録した記録媒体。
  • Applicant
  • ※All designated countries except for US in the data before July 2012
  • NATIONAL UNIVERSITY CORPORATION OKAYAMA UNIVERSITY
  • Inventor
  • AKANE, Masataka
  • NOGAMI, Yasuyuki
  • MORIKAWA, Yoshitaka
IPC(International Patent Classification)
Specified countries AE(UTILITY MODEL),AG,AL(UTILITY MODEL),AM(PROVISIONAL PATENT)(UTILITY MODEL),AO(UTILITY MODEL),AT(UTILITY MODEL),AU,AZ(UTILITY MODEL),BA,BB,BG(UTILITY MODEL),BH(UTILITY MODEL),BR(UTILITY MODEL),BW(UTILITY MODEL),BY(UTILITY MODEL),BZ(UTILITY MODEL),CA,CH,CN(UTILITY MODEL),CO(UTILITY MODEL),CR(UTILITY MODEL),CU(INVENTOR'S CERTIFICATE),CZ(UTILITY MODEL),DE(UTILITY MODEL),DK(UTILITY MODEL),DM(UTILITY MODEL),DO(UTILITY MODEL),DZ,EC(UTILITY MODEL),EE(UTILITY MODEL),EG(UTILITY MODEL),ES(UTILITY MODEL),FI(UTILITY MODEL),GB,GD,GE(UTILITY MODEL),GH(UTILITY CERTIFICATE),GM,GT(UTILITY MODEL),HN,HR(CONSENSUAL PATENT),HU(UTILITY MODEL),ID,IL,IN,IS,KE(UTILITY MODEL),KG(UTILITY MODEL),KM,KN,KP(INVENTOR'S CERTIFICATE)(UTILITY MODEL),KR(UTILITY MODEL),KZ(PROVISIONAL PATENT)(UTILITY MODEL),LA,LC,LK,LR,LS(UTILITY MODEL),LT,LU,LY,MA,MD(UTILITY MODEL),ME(PETTY PATENT),MG,MK,MN,MW,MX(UTILITY MODEL),MY(UTILITY-INNOVATION),MZ(UTILITY MODEL),NA,NG,NI(UTILITY MODEL),NO,NZ,OM(UTILITY MODEL),PG,PH(UTILITY MODEL),PL(UTILITY MODEL),PT(UTILITY MODEL),RO,RS(PETTY PATENT),RU(UTILITY MODEL),SC,SD,SE,SG,SK(UTILITY MODEL),SL(UTILITY MODEL),SM,ST,SV(UTILITY MODEL),SY,TJ(UTILITY MODEL),TM(PROVISIONAL PATENT),TN,TR(UTILITY MODEL),TT(UTILITY CERTIFICATE),TZ,UA(UTILITY MODEL),UG(UTILITY CERTIFICATE),US,UZ(UTILITY MODEL),VC(UTILITY CERTIFICATE),VN(PATENT FOR UTILITY SOLUTION),ZA,ZM,ZW,EP(AT,BE,BG,CH,CY,CZ,DE,DK,EE,ES,FI,FR,GB,GR,HR,HU,IE,IS,IT,LT,LU,LV,MC,MT,NL,NO,PL,PT,RO,SE,SI,SK,TR),OA(BF(UTILITY MODEL),BJ(UTILITY MODEL),CF(UTILITY MODEL),CG(UTILITY MODEL),CI(UTILITY MODEL),CM(UTILITY MODEL),GA(UTILITY MODEL),GN(UTILITY MODEL),GQ(UTILITY MODEL),GW(UTILITY MODEL),ML(UTILITY MODEL),MR(UTILITY MODEL),NE(UTILITY MODEL),SN(UTILITY MODEL),TD(UTILITY MODEL),TG(UTILITY MODEL)),AP(BW(UTILITY MODEL),GH(UTILITY MODEL),GM(UTILITY MODEL),KE(UTILITY MODEL),LS(UTILITY MODEL),MW(UTILITY MODEL),MZ(UTILITY MODEL),NA(UTILITY MODEL),SD(UTILITY MODEL),SL(UTILITY MODEL),SZ(UTILITY MODEL),TZ(UTILITY MODEL),UG(UTILITY MODEL),ZM(UTILITY MODEL),ZW(UTILITY MODEL)),EA(AM,AZ,BY,KG,KZ,MD,RU,TJ,TM)

PAGE TOP

close
close
close
close
close
close