(57)【要約】【課題】従来よりも最適化実行時間の高速化が期待できるペアリング型変換装置等を提供する。【解決手段】ペアリング型変換装置は、あらかじめ定めた分割のための4つの線形制約を設定する線型制約設定部と、目的関数を全ての割り当て変数に関する線型関数として設定し、目的関数が割り当て変数の非線形関数であるなら目的関数を線形制約付き線形目的関数に変換し設定する目的関数設定部と、線形制約と線型関数または線形制約付き線形目的関数とを0-1整数計画アルゴリズムに入力し厳密解又は近似解を求める整数計画部とを備える。線形制約は、(1)xが重複不可頂点の場合は、(x∈G0)+(x∈G1)=1、(2)Lyに含まれる任意のxについて、(y∈Gb)≧(x∈Gb)、(3)xとyとがペアリングへの入力対となる頂点である場合は、x+y=1、(4)xとyが1つの路上の2つの重複不可頂点ならば、x-y=0である。【選択図】図６
2018116194.tif 000002
【特許請求の範囲】
【請求項１】
対称ペアリングに基づく暗号方式を非対称ペアリングに基づく暗号方式に変換するためのペアリング型変換装置であって、
前記対称ペアリングに基づく暗号方式の構成、構文、帰着、仮定を含むアルゴリズムを入力情報、前記非対称ペアリングに基づく暗号方式の構成、構文、帰着、仮定を含むアルゴリズムを出力情報とし、
G0とG1は分割後の部分グラフ、xとyは分割前のグラフの頂点、b∈{0,1}、(x∈Gb)及び(y∈Gb)は()内の記述が真ならば1偽ならば0を示す割り当て変数、Lyはyの子孫のうち葉であるものの集合とし、
あらかじめ定めた分割のための4つの線形制約を設定する線型制約設定部と、
目的関数を全ての割り当て変数に関する線型関数として設定し、目的関数が割り当て変数の非線形関数であるなら目的関数を線形制約付き線形目的関数に変換し設定する目的関数設定部と、
前記線形制約と前記線型関数または前記線形制約付き線形目的関数とを0-1整数計画アルゴリズムに入力し厳密解又は近似解を求める整数計画部と、
厳密解又は近似解の割り当て変数の値に従って、前記対称ペアリングに基づく暗号方式の構成、構文、帰着、仮定を含むアルゴリズムを表現する1つの依存関係グラフを2つの部分グラフに分割する分割構成部と、
を備え、
前記線形制約は、
(1)xが重複不可頂点の場合は、(x∈G0)+(x∈G1)=1
(2)Lyに含まれる任意のxについて、(y∈Gb)≧(x∈Gb)
(3)xとyとがペアリングへの入力対となる頂点である場合は、x+y=1
(4)xとyが1つの路上の2つの重複不可頂点ならば、x-y=0
である、
ペアリング型変換装置。
【請求項２】
ペアリング型変換装置が、対称ペアリングに基づく暗号方式を非対称ペアリングに基づく暗号方式に変換するためのペアリング型変換方法であって、
前記対称ペアリングに基づく暗号方式の構成、構文、帰着、仮定を含むアルゴリズムを入力情報、前記非対称ペアリングに基づく暗号方式の構成、構文、帰着、仮定を含むアルゴリズムを出力情報とし、
G0とG1は分割後の部分グラフ、xとyは分割前のグラフの頂点、b∈{0,1}、(x∈Gb)及び(y∈Gb)は()内の記述が真ならば1偽ならば0を示す割り当て変数、Lyはyの子孫のうち葉であるものの集合とし、
あらかじめ定めた分割のための4つの線形制約を設定する線型制約設定ステップと、
目的関数を全ての割り当て変数に関する線型関数として設定し、目的関数が割り当て変数の非線形関数であるなら目的関数を線形制約付き線形目的関数に変換し設定する目的関数設定ステップと、
前記線形制約と前記線型関数または前記線形制約付き線形目的関数とを0-1整数計画アルゴリズムに入力し厳密解又は近似解を求める整数計画ステップと、
厳密解又は近似解の割り当て変数の値に従って、前記対称ペアリングに基づく暗号方式の構成、構文、帰着、仮定を含むアルゴリズムを表現する1つの依存関係グラフを2つの部分グラフに分割する分割構成ステップと、
を備え、
前記線形制約は、
(1)xが重複不可頂点の場合は、(x∈G0)+(x∈G1)=1
(2)Lyに含まれる任意のxについて、(y∈Gb)≧(x∈Gb)
(3)xとyとがペアリングへの入力対となる頂点である場合は、x+y=1
(4)xとyが1つの路上の2つの重複不可頂点ならば、x-y=0
である、
ペアリング型変換方法。
【請求項３】
請求項１のペアリング型変換装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アルゴリズムの代数的構造を変換する技術に関する。
【背景技術】
【０００２】
アルゴリズムの代数的構造を変換する従来技術として非特許文献１が知られている。非特許文献１には、群G、GT上のペアリングe:G×G→GTを用いたアルゴリズムを、群G0、G1、GT上のペアリングe:G0×G1→GT(ただしG0≠G1)を用いたアルゴリズムに変換する技術が開示されている。この技術では、群G上の群演算の依存関係グラフのノードに群G0またはG1を割り当て、その割り当て状況を評価関数で評価し、最も評価の良い割り当てを選択する。また非特許文献２には、上記割り当ての選択を整数計画法を用いて高速化する技術が記述されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Masayuki Abe, Jens Groth, Miyako Ohkubo, and Takeya Tango, "Converting cryptographic schemes from symmetric to asymmetric bilinear groups", In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I, volume 8616 of Lecture Notes in Computer Science, pages 241-260. Springer, 2014.
【非特許文献２】Masayuki Abe, Fumitaka Hoshino, and Miyako Ohkubo, "Design in Type-I, Run in Type-III: Fast and Scalable Bilinear-Type Conversion Using Integer Programming", In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part III, volume 9816 of Lecture Notes in Computer Science, pages 387{415. Springer, 2016.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来技術において用いられる0-1整数計画問題は一般にNP困難と呼ばれる問題クラスに属しており、必ずしも実行可能な時間で厳密に最適な解が得られる事は保証されない。しかしながら、入力される問題を特殊な形式に限定すると最適化問題の求解時間が大幅に削減される事がある。
【０００５】
本発明は、ペアリング型変換で必要となる制約を上手く制御し0-1整数計画問題に入力される問題を特殊な形式に限定することにより、従来よりも最適化実行時間の高速化が期待できるペアリング型変換装置、ペアリング型変換方法、プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記の課題を解決するために、本発明の一態様によれば、対称ペアリングに基づく暗号方式を非対称ペアリングに基づく暗号方式に変換するためのペアリング型変換装置は、対称ペアリングに基づく暗号方式の構成、構文、帰着、仮定を含むアルゴリズムを入力情報、非対称ペアリングに基づく暗号方式の構成、構文、帰着、仮定を含むアルゴリズムを出力情報とし、G0とG1は分割後の部分グラフ、xとyは分割前のグラフの頂点、b∈{0,1}、(x∈Gb)及び(y∈Gb)は()内の記述が真ならば1偽ならば0を示す割り当て変数、Lyはyの子孫のうち葉であるものの集合とし、あらかじめ定めた分割のための4つの線形制約を設定する線型制約設定部と、目的関数を全ての割り当て変数に関する線型関数として設定し、目的関数が割り当て変数の非線形関数であるなら目的関数を線形制約付き線形目的関数に変換し設定する目的関数設定部と、線形制約と線型関数または線形制約付き線形目的関数とを0-1整数計画アルゴリズムに入力し厳密解又は近似解を求める整数計画部と、厳密解又は近似解の割り当て変数の値に従って、対称ペアリングに基づく暗号方式の構成、構文、帰着、仮定を含むアルゴリズムを表現する1つの依存関係グラフを2つの部分グラフに分割する分割構成部と、を備える。線形制約は、(1)xが重複不可頂点の場合は、(x∈G0)+(x∈G1)=1、(2)Lyに含まれる任意のxについて、(y∈Gb)≧(x∈Gb)、(3)xとyとがペアリングへの入力対となる頂点である場合は、x+y=1、(4)xとyが1つの路上の2つの重複不可頂点ならば、x-y=0である。
【０００７】
上記の課題を解決するために、本発明の他の態様によれば、ペアリング型変換装置が、対称ペアリングに基づく暗号方式を非対称ペアリングに基づく暗号方式に変換するためのペアリング型変換方法は、対称ペアリングに基づく暗号方式の構成、構文、帰着、仮定を含むアルゴリズムを入力情報、非対称ペアリングに基づく暗号方式の構成、構文、帰着、仮定を含むアルゴリズムを出力情報とし、G0とG1は分割後の部分グラフ、xとyは分割前のグラフの頂点、b∈{0,1}、(x∈Gb)及び(y∈Gb)は()内の記述が真ならば1偽ならば0を示す割り当て変数、Lyはyの子孫のうち葉であるものの集合とし、あらかじめ定めた分割のための4つの線形制約を設定する線型制約設定ステップと、目的関数を全ての割り当て変数に関する線型関数として設定し、目的関数が割り当て変数の非線形関数であるなら目的関数を線形制約付き線形目的関数に変換し設定する目的関数設定ステップと、線形制約と線型関数または線形制約付き線形目的関数とを0-1整数計画アルゴリズムに入力し厳密解又は近似解を求める整数計画ステップと、厳密解又は近似解の割り当て変数の値に従って、対称ペアリングに基づく暗号方式の構成、構文、帰着、仮定を含むアルゴリズムを表現する1つの依存関係グラフを2つの部分グラフに分割する分割構成ステップと、を備える。線形制約は、(1)xが重複不可頂点の場合は、(x∈G0)+(x∈G1)=1、(2)Lyに含まれる任意のxについて、(y∈Gb)≧(x∈Gb)、(3)xとyとがペアリングへの入力対となる頂点である場合は、x+y=1、(4)xとyが1つの路上の2つの重複不可頂点ならば、x-y=0である。
【発明の効果】
【０００８】
本発明によれば、従来よりも最適化実行時間の高速化が期待できるという効果を奏する。
【図面の簡単な説明】
【０００９】
【図１】ペアリングを出力するアルゴリズムの例を示す図。
【図２】ペアリングを出力するアルゴリズムの依存関係グラフを示す図。
【図３】ペアリングを出力するアルゴリズムの分割による変換の例を示す図。
【図４】ペアリングを出力するアルゴリズムの分割による変換の依存関係グラフを示す図。
【図５】分割のための制約2を説明するための図。
【図６】第一実施形態に係るペアリング型変換装置の機能ブロック図。
【図７】第一実施形態に係るペアリング型変換装置の処理フローの例を示す図。
【図８】第一実施形態に係るペアリング型変換装置を用いて変換した非対称ペアリングに基づく暗号方式をIDベース暗号を説明するための図。
【発明を実施するための形態】
【００１０】
以下、本発明の実施形態について、説明する。なお、以下の説明に用いる図面では、同じ機能を持つ構成部や同じ処理を行うステップには同一の符号を記し、重複説明を省略する。以下の説明において、ベクトルや行列の各要素単位で行われる処理は、特に断りが無い限り、そのベクトルやその行列の全ての要素に対して適用されるものとする。
【００１１】
＜前提＞
まず、第一実施形態の前提について説明する。
＜準備＞
＜ペアリング＞
暗号学においてペアリングとは概ね次のような代数的構造を持つ符号を生成する確率的多項式時間アルゴリズムPの事である。
【００１２】
【数１】
2018116194.tif 000003
【００１３】
1.L,G0,G1,GTはそれぞれ#Q>2Θ(λ)なる同じ有限可換環Qの符号。
2.次の確率的多項式時間アルゴリズムが利用可能。
-L,G0,G1,GT上の標本。
-L,G0,G1,GT上の加法。
-L上の乗法。
-非退化双準同型^:Gx×L→Gx,∀x∈{0,1,T}
-非退化双準同型e:G0×G1→GT
【００１４】
3.G0,G1,GT上のCDH(Computational Diffie-Hellman)問題(乗法)はそれぞれ計算困難。
λは安全変数と呼ばれ、系に対する何らかの攻撃計算量がλに関して指数オーダー(あるいは準指数等)となる事が期待される。G0,G1,GTはそれぞれ群と呼ばれ、Lは離散対数などと呼ばれる。G0,G1,GTが群と呼ばれる為、G0,G1,GT上の(環の符号としての)加法は乗法とも呼ばれA,B∈Gx,∀x∈{0,1,T}に対してA×B、A・B、AB等と記述される。多項式時間非退化双準同型^は冪乗などと呼ばれg∈Gx,a∈Lに対して^(g,a)はgaと記述される。冪乗およびG0、G1、GT上の加法を群演算と呼ぶ。多項式時間非退化双準同型eはペアリングと呼ばれる。また符号の組(L,G0,G1,GT)をペアリングと呼ぶ事もある。歴史的経緯と習慣によりペアリングと言った時それがeを指すのか、(L,G0,G1,GT)を指すのか、Pを指すのか、あるいは特にそれらを区別していないのかは文脈によって判断する必要がある。G0,G1を入力群(source group)、GTを標的群(target group)と呼ぶ。本願明細書では特に明示しない限り、単に群および群要素などと呼ぶ時は、それぞれ入力群および入力群要素を意味するとする。Galbraithらは、暗号方式に用いられるペアリングを大雑把に以下の
３つの型に分類した(参考文献１参照)。
(参考文献１) Steven D. Galbraith, Kenneth G. Paterson, and Nigel P. Smart, "Pairings for cryptographers", Discrete Applied Mathematics, 156(16):3113-3121, 2008.
【００１５】
Type1:G0,G1間で双方向に多項式時間同型が存在する。
Type2:G1→G0なる一方向同型が存在する。
Type3:G0,G1間で双方向に多項式時間同型が存在しない。
【００１６】
一般にType1を対称ペアリングと呼び、Type2、Type3を非対称ペアリングと呼ぶ。対称ペアリングにおいてはG0とG1はいつでも双方向に多項式時間で行き来出来る為、両者を特に区別する必要はなく、それらは単にGと記述される。Type2はType3を利用して実装できるので、特殊な機能や安全性証明を考える時以外はType2が登場する事はあまり無い。本願明細書では非対称ペアリングとして特にType3を想定する。
【００１７】
このときG0とG1は明確に区別される。演算速度や群要素のサイズといった実装上の問題に関して、対称ペアリングよりもずっと効率的な非対称ペアリングの存在が知られている(参考文献２参照)。
(参考文献２) Paulo S. L. M. Barreto and Michael Naehrig, "Pairing-friendly elliptic curves of prime order", In Bart Preneel and Stafford E. Tavares, editors, Selected Areas in Cryptography, 12th International Workshop, SAC 2005, Kingston, ON, Canada, August 11-12, 2005, Revised Selected Papers, volume 3897 of Lecture Notes in Computer Science, pages 319-331. Springer, 2005.
【００１８】
＜依存関係グラフ(非特許文献１及び参考文献３参照)＞
(参考文献３) Takeya Tango, Masayuki Abe, and Tatsuaki Okamoto, "Implementation of Automated Translation for Schemes on Symmetric Bilinear Groups", In Proc. of SCIS 2014 The 31st Symposium on Cryptography and Information Security kagoshima, Japan, Jan. 21 - 24, 2014. IEICE, 2014.
【００１９】
方式に対して、その依存関係グラフ(dependency graph)とは方式の構成(construction)、構文(syntax)、帰着(reduction)、仮定(assumption)等で使用される群要素変数の情報の流れ(data flow)を抽象した有向グラフである。各頂点はプログラム中で使用される群要素変数を、各辺はその依存関係(終点は始点に依存する)を表現する。図１は群要素A,B,Dを入力とし群演算を使ってC,Eを計算しそのペアリングe(C,E)を出力するアルゴリズムの例であり、図２はその依存関係グラフである。
【００２０】
依存関係グラフには群演算を介した群要素同士の関係のみが記述され、"if-then-else"命令のようなプログラムの構造やa∈Z/pZのような群要素以外の変数あるいは標的群上の演算等は全て捨象される。
【００２１】
ペアリングは入力群要素2つ(図２の例では、群要素９１及び群要素９２)を入力として標的群要素1つを出力する関数なので、依存関係グラフ中では出力辺を持たない対となる2つの頂点として表現される。ペアリングへの入力に相当する方式中の群要素変数は暗黙に宣言および定義されるとする。例えば図１のアルゴリズム中にはA,B,C,D,Eの5つの群要素変数が宣言および定義されているが、ペアリングへの入力に相当する2つの群要素変数は宣言も定義もされていない。この暗黙の群要素変数は図２ではp1[0]、p1[1]と表現されている。ペアリングが複数ある場合はi番目のペアリングはpi[0]、pi[1]なる暗黙の群要素変数を持つとする。また、一般にプログラム中の群演算や群要素比較で構成される表現からも、依存関係の文脈で必要なら適当に暗黙の群要素変数が宣言および定義されるとする。
【００２２】
阿部らは対称ペアリングに基づく暗号方式を安全性を維持したまま非対称ペアリングに基づく暗号方式に変換する為のフレームワークを提案した(非特許文献１及び参考文献３参照)。阿部らのフレームワークでは、対称ペアリング上定義された方式の構成、構文、帰着、仮定等をまとめた1つの依存関係グラフから、ある制約に従う二つの部分グラフを導く。この部分グラフ達を導出する事を分割と呼ぶ。各部分グラフは変換後の方式を抽象しており、それぞれG0およびG1の群要素に関する依存関係グラフとなる。そして二つの部分グラフおよび元の方式より非対称ペアリング上定義された方式の構成、構文、帰着、仮定等が再構築される。図１のアルゴリズムの分割による変換の例を図３に、その依存関係グラフを図４に示す。分割による変換を考察するため、概ね非特許文献１、２、参考文献３、４に従っていくつか用語や記法を定義する。
(参考文献４) Fumitaka Hoshino, Masayuki Abe, and Miyako Ohkubo, "Optimal Conversion from Symmetric Pairing-based Scheme to Asymmetric One", In Proc. of SCIS 2016 2016 Symposium on Cryptography and Information Security Kumamoto, Japan, Jan. 19 - 22, 2016. IEICE, 2016.
【００２３】
定義1（G,G0,G1）  上述の＜ペアリング＞でType1におけるペアリングの入力群をGと定義したが、以下Gを依存関係グラフまたはその頂点集合と再定義する。また、上述の＜ペアリング＞で一般の設定におけるペアリングの入力群をG0およびG1と定義したが、以下G0およびG1を依存関係グラフGの部分グラフまたはその頂点集合と再定義する。
【００２４】
以下依存関係グラフGから分割によって2つの部分グラフGb、b∈{0,1}が生成されるとする。
定義2（祖先）  頂点x∈Gに対してxに到達可能な頂点y∈G(但しxを含まない)をxの祖先と呼ぶ。このとき頂点xは頂点yを祖先に持つと言う。
定義3（子孫）  頂点x∈Gに対してxから到達可能な頂点y∈G(但しxを含まない)をxの子孫と呼ぶ。このとき頂点xは頂点yを子孫に持つと言う。
【００２５】
一般に有効な変数定義の連鎖によって構成された単一アルゴリズムのデータフローは有向非巡回グラフを構成するので閉路(cycle)を持たない。しかし方式の構成、構文、帰着、仮定等の複数のアルゴリズムが統合される場合、依存関係グラフは閉路を持ち得る。依存関係グラフが閉路を持つ場合、ある頂点yがある頂点xの祖先でありかつ子孫であるという事がありうる。閉路を構成する頂点同士はどれも互いに祖先でありかつ子孫であるから、依存関係の文脈では閉路自体を単一の頂点と同一視してよい。この性質を考慮し、有向グラフにおける葉の概念を多少拡張し、次のように定める。
【００２６】
定義4（葉）  出力が無い頂点、または(他の葉に到達可能な)出力が無い閉路を代表する頂点を葉と呼ぶ。定義によりペアリングへの入力は必ず葉となる。
【００２７】
本願明細書では整数の集合{0,1}を論理値の集合と同一視し、0を偽、1を真とみなす。論理式は全て古典論理(ブール代数)に従い演繹できるとする。概ね慣例に従い次の記法を用いる。
【００２８】
定義5（∧,∨,xor,⇒,⇔,¬,-）  二つの論理式x、yに対してその論理積、論理和、排他的論理和、含意、同値をそれぞれx∧y、x∨y、x xor y、x⇒y、x⇔yと記述する。論理式xに対してその否定を¬xまたは-xと記述する。また、排他的論理和を
【数２】
2018116194.tif 000004
とも記述する。
【００２９】
論理的な言明と代数的な関係式の間の往来を容易にする為、次の定義を行なう。
定義6（割り当て変数(x∈Gb)）(x∈Gb)なる表現をその真理値に従う論理変項、即ち{0,1}上の変数とする。(x∈Gb)を割り当て変数と呼ぶ。即ち、
【数３】
2018116194.tif 000005
である。割り当て変数(x∈Gb)に関して、写像{(x∈Gb)}→{0,1}を割り当て変数(x∈Gb)への割り当てあるいは代入と呼ぶ。全ての割り当て変数の集合をVGとする。即ち
VG={(x∈Gb)|x∈G,b∈{0,1}}
である。写像VG→{0,1}を依存関係グラフGへの割り当て、あるいは単に割り当てと呼ぶ。割り当てを決定すれば分割を決定する事が出来る。
【００３０】
依存関係グラフG中にn個の頂点が存在する時、2n個の割り当て変数が存在する。従って、依存関係グラフGへの割り当て、即ち写像VG→{0,1}は22n個存在する。それらの割り当ての中には方式を変換する上で有効でないものも存在する。どのような割り当てが有効となるかは後に議論する。
【００３１】
定義7（重複頂点）  ある頂点xが
x∈G0 ∧ x∈G1
を満たすならxを重複頂点(duplicated node)と呼ぶ。
【００３２】
定義8（重複不可頂点）  何らかの理由により分割後に重複頂点となる可能性が無い頂点を重複不可頂点(non-duplicatable node)と呼ぶ。重複不可頂点はアルゴルズム中でハッシュ関数の出力が群要素となるような演算の出力を表現したり、データサイズを節約する為に方式の設計者により設定される事がある。また後述する理由により本願明細書で扱う変換では葉は全て重複不可頂点となる。
【００３３】
＜阿部らのフレームワーク(非特許文献１、参考文献３参照)＞
対称ペアリングは代数的構造が簡単な為、多くの暗号方式が対称ペアリングをを前提に設計されている。しかし、時間計算量や領域計算量等の効率の観点から、現在では非対称ペアリングを使用することが望ましいと考えられるようになった。そこで、阿部らは対称ペアリングに基づく暗号方式を安全性を保ったまま非対称ペアリングに基づく暗号方式に自動変換する以下のフレームワークを提案した(非特許文献１、参考文献３参照)。
【００３４】
Step1:Type1のペアリング上の暗号方式の構成、構文、帰着、仮定等の各アルゴリズムが入力される。
Step2:各アルゴリズム中の群要素変数の依存関係グラフ(有向グラフ)をそれぞれ構成し、それを一つに統合する。
Step3:後述の制約条件の下で依存関係グラフを2つの部分グラフに分割する。なお、分割が存在しない場合は本フレームワークでは変換不可能とする。
Step4:分割に基づきType3ペアリング上の暗号方式の構成、構文、帰着、仮定等の各アルゴリズムが出力される。
【００３５】
阿部らは上記の分割に関して次の定理を証明した。
定理1（非特許文献１参照）  上記の分割が下記の4つの制約を満たすとき、導出される方式は元の方式の機能と安全性をType3上で実現する。
制約1  分割された2つの部分グラフの合併は元のグラフと一致する。
制約2  もし部分グラフが頂点xを含むなら、その部分グラフは頂点xへの全ての路(path)を含む。
制約3  一つのペアリングに含まれる二つの頂点は互いに異なる部分グラフに含まれる。
制約4  もし一方の部分グラフが重複不可頂点を含むなら他方の部分グラフはその頂点を含まない。
【００３６】
これら4つの制約条件を満たす分割を有効分割(valid split)と呼び、その割り当てを有効割り当て(valid assignment)と呼ぶ。非特許文献１、参考文献３ではStep3の分割は、方式に関する時間計算量や領域計算量といった何らかの評価関数を、総当たり探索により評価する事によって決定されるとしている。
【００３７】
＜有効分割と最適性の仮定＞
以下、有効分割に関して考察する。
制約1  分割された2つの部分グラフの合併は元のグラフと一致する。
制約1は明らかに
G=G0∪G1
を意味する。これは頂点xがx∈Gであるなら
x∈G0∨x∈G1         (1)
である事を意味しており、従って
【数４】
2018116194.tif 000006
は成立しない。式(1)の選言は
(x∈G0)+(x∈G1)≧1        (2)
と同義である。xが重複不可頂点である場合は
(x∈G0)+(x∈G1)=1        (3)
が成立する。
【数５】
2018116194.tif 000007
としても良い。記述を簡素化するため、本発明では重複不可頂点xに関しては、論理変数(x∈G1)を改めて論理変数xと略記する事があるとする。即ち重複不可頂点x∈Gおよびb∈{0,1}に関して
【数６】
2018116194.tif 000008
である。
【００３８】
本願明細書では評価関数に関して次の仮定を設ける。
仮定1（最適性の仮定）  Gに関する二つの有効分割が存在しその違いが、"ある頂点xが重複頂点であるか否か"のみであったとする。この時xが重複頂点となる分割の評価値は必ずもう一方の分割の評価値と等しいかより悪い。
【００３９】
この仮定は重複頂点が少なければ少ないほど方式に要する領域計算量や時間計算量が小さくなり、方式が効率的になるという観察に基づいている。評価関数がそうした評価基準とは異なる価値観(例えば出来るだけ沢山の重複頂点を持ちたい等)を持つ場合には本方式は適用できない。本方式ではこの仮定を最適性の仮定と呼ぶ。この仮定により、冗長な重複頂点を含む分割を考察の対象から除外出来る。以下、この仮定の下で有効分割に関して考察する。
【００４０】
制約2  もし部分グラフが頂点xを含むなら、その部分グラフは頂点xへの全ての路(path)を含む。yをxの祖先とする。
制約2は明らかに
(x∈Gb)⇒(y∈Gb)
を意味する。図５の通り、真理値表の通り含意は不等号と同義である。従って、次式により表される。
(x∈Gb)≦(y∈Gb)        (5)
【００４１】
yを頂点、Dyをyの子孫の全体とする。割り当て(y∈Gb)∈{0,1}は下記を満足する必要がある。
(y∈Gb)≧(x∈Gb),  ∀x∈Dy        (6)
即ち
【数７】
2018116194.tif 000009
最適性の仮定により等号のみを考えれば良い。
【数８】
2018116194.tif 000010
【００４２】
今、仮にyが子孫を持たないと仮定すると、x∈Dyなるxが存在しないので、式(7)を考慮せずに(y∈Gb)の値を決定出来る。この時最適性の仮定によりyが重複頂点となる事は除外できる。即ち、もしyが葉なら、yは重複不可として良い。
【００４３】
次に、全ての葉の割り当てが決定したと仮定する。葉から繰り返し上流に遡り、上流側の頂点yの割り当てを式(7)により決定したい。最適性の仮定により全ての頂点の割り当てはその頂点から到達可能な全ての葉の割り当てによって決定されるとして良い。即ち値(y∈Gb)∈{0,1}は葉の値のみに依存する。LyをDyに含まれる葉の全体とする。式(7)より
【数９】
2018116194.tif 000011
【００４４】
制約3  一つのペアリングに含まれる二つの頂点は互いに異なる部分グラフに含まれる。
x,yをペアリングへの入力対となる頂点とする。x,yは葉なので重複不可として良い。従ってx,yを{0,1}変数として良い。明らかに制約3は
【数１０】
2018116194.tif 000012
を意味する。x,yが{0,1}変数なので
x+y=1        (9)
として良い。
【００４５】
制約4  もし一方の部分グラフが重複不可頂点を含むなら他方の部分グラフはその頂点を含まない。
【００４６】
x,yを重複不可頂点とし、xをyの子孫とする。式(4)より
【数１１】
2018116194.tif 000013
式(5)より
【数１２】
2018116194.tif 000014
が成立する。(x∈Gb)≠(y∈Gb)を仮定すると、直ちに(x∈Gb)=0および(y∈Gb)=1が成立する。なぜなら
0≦(x∈Gb)<(y∈Gb)≦1
であるから、式(10)により
【数１３】
2018116194.tif 000015
が成立する。従って式(5)即ち
【数１４】
2018116194.tif 000016
が成立しない。従って(x∈Gb)≠(y∈Gb)なる仮定は成立しない。よって(x∈Gb)=(y∈Gb)即ちx=yである。即ち、もしx,yが一つの路上の二つの重複不可頂点であるなら
x-y=0        (11)
が成立する。
【数１５】
2018116194.tif 000017
としても良い。
【００４７】
＜阿部らのアルゴリズム(非特許文献２及び参考文献４)＞
非特許文献１及び参考文献３では、Step3の分割は、方式に関する時間計算量や領域計算量といった何らかの関数を、総当たり探索により評価する事によって決定されるとしていた。ペアリングの数とペアリングへの入力でない葉の数の総和をnとすると、上記の総当たり探索には2n回の演算が必要であり、nが大きい時には計算量が大きくなりすぎて実行困難となる。阿部らはこの問題を有効分割の求解問題と最適化問題とに分離し、多項式時間求解アルゴリズムと次の最適化アルゴリズムを提案した(非特許文献２及び参考文献４)。
【００４８】
Step1:制約(3),(8),(9),(11)をすべて書き下す。
Step2:(8)を下記の良く知られた方法で線形制約に変換する。
Step3:割り当て変数を使って線形目的関数を書き下す。
Step4:全ての線形制約および線形目的関数を任意の0-1整数計画アルゴリズムに入力し厳密解あるいは近似解を得る。
Step5:割り当て変数の値に従って分割を構成する。
【００４９】
線形制約への変換:(d∈G1)をdと略記すると(8)は
【数１６】
2018116194.tif 000018
と記述できる。ところで{0,1}上の変数y0,y1,zについて、
【数１７】
2018116194.tif 000019
である。即ち{0,1}変数の任意の連言と否定は線型制約の元で変数に置き換え可能で、従ってどのような命題変数の論理式もこの置き換えを繰り返す事によって{0,1}変数の線型制約付き線型式に変換出来る事が良く知られている。特にy1,…,yk,z∈{0,1}の時
【数１８】
2018116194.tif 000020
【００５０】
である。従って制約(12)は線型制約
【数１９】
2018116194.tif 000021
と同値である。
【００５１】
＜第一実施形態のポイント＞
本実施形態に係るペアリング型変換装置では、ペアリング型変換で必要となる制約をうまく制御し0-1整数計画問題に入力される問題を特殊な形式に限定することにより最適化実行時間を高速化する。
【００５２】
整数行列A、整数ベクトルb,f、ベクトル変数xで定義される整数計画問題
max{f・x|Ax≧b, 0≦x≦1, x∈Zn}
の線型緩和
max{f・x|Ax≧b, 0≦x≦1, x∈Rn}
を考える。行列Aは、その如何なる小行列式も0、1、-1のいずれかであるとき完全単模(完全ユニモジュラー、totally unimodular)と呼ばれる。行列Aが完全単模である時、整数計画問題の解はその線型緩和の解と一致する事が知られている。一般に線型計画問題はPと呼ばれる問題クラスに属しており、従って行列Aが完全単模であるなら整数計画問題を線型計画問題ととらえ直す事によって多項式時間で解く事が出来る。
【００５３】
ペアリング型変換で必要となる線型制約Aは必ずしも完全単模ではないので、直接この方法を適用する事は出来ないが行列Aの小行列式のうちなるべく多くのものが0,1,-1となるようAを構成出来れば、整数計画法を高速化出来る事が期待できる。
【００５４】
ところで、以下の四つの条件を満たす行列Aは完全単模となる事が知られている。
条件1:Aのすべての成分は0、1、-1のいずれかである。
条件2:Aのすべての行には、ゼロでない成分が高々二つしか存在しない。
条件3:Aのある行の二つのゼロでない成分の符号が同一であるなら、その一つの列はある添え字集合Bに属し、もう一つの列はBに属さない添え字の集合Cに属する。
条件4:Aのある行の二つのゼロでない成分の符号が異なるなら、それら両方の列はBあるいはCのどちらか一方に属する。
【００５５】
一般に条件1と条件2を満足するAが条件3や条件4を満足しない場合、条件3や条件4に矛盾を生じるような行をAから適当に除去した行列A'を完全単模とする事ができる。
【００５６】
阿部らの方法で生成されるAは条件1を満たすが式(14)の第1式と第3式の為に、大抵の場合、条件2を満足しない。従って、部分行列A'が完全単模となる為に条件3や条件4に矛盾を生じるような行以外に大抵は条件2を満足しない行を全て取り除く必要がある。
【００５７】
阿部らのアルゴリズム(非特許文献２、参考文献４)では式(7)から得た式(8)を式(13)を使って無理やり線形制約に置き換えた。本実施形態ではこの置き換えを辞めて式(6)から最適性の仮定を使って直接以下を得る。
【００５８】
yを頂点、Lyをyの子孫のうち葉であるものの全体とする。割り当て(y∈Gb)∈{0,1}は下記を満足する必要がある。
(y∈Gb)≧(x∈Gb),  ∀x∈Ly       (15)
阿部らの方法で問題となった制約(14)の第1式と第3式は出現しない。
【００５９】
本実施形態では、以下のStepを実行する。
Step1:制約(3)、(15)、(9)、(11)をすべて書き下し線型制約を設定する。
Step2:割り当て変数を使って線形目的関数を書き下す。
Step3:全ての線形制約および線形目的関数を任意の0-1整数計画アルゴリズムに入力し厳密解あるいは近似解を得る。
Step4:割り当て変数の値に従って分割を構成する。
【００６０】
以上を実現するペアリング型変換装置について説明する。
＜第一実施形態＞
図６は第一実施形態に係るペアリング型変換装置１００の機能ブロック図を、図７はその処理フローを示す。
【００６１】
ペアリング型変換装置１００は、CPUと、RAMと、以下の処理を実行するためのプログラムを記録したROMを備えたコンピュータで構成され、機能的には次に示すように構成されている。
【００６２】
ペアリング型変換装置１００は、線型制約設定部１１０と、目的関数設定部１２０と、整数計画部１３０と、分割構成部１４０とを含む。
【００６３】
ペアリング型変換装置１００は、対称ペアリングに基づく暗号方式を非対称ペアリングに基づく暗号方式に変換する。例えば、ペアリング型変換装置１００は、対称ペアリングに基づく暗号方式の構成、構文、帰着、仮定を含むアルゴリズムを入力情報とし、非対称ペアリングに基づく暗号方式の構成、構文、帰着、仮定を含むアルゴリズムに変換し、出力情報として出力する。
【００６４】
＜線型制約設定部１１０＞
線型制約設定部１１０は、あらかじめ定めた分割のための4つの線形制約を設定する（Ｓ１１０）。なお、4つの線形制約とは、
(1)xが重複不可頂点の場合は、(x∈G0)+(x∈G1)=1
(2)Lyに含まれる任意のxについて、(y∈Gb)≧(x∈Gb)
(3)xとyとがペアリングへの入力対となる頂点である場合は、x+y=1
(4)xとyが1つの路上の2つの重複不可頂点ならば、x-y=0
であり、それぞれ以下の分割のための4つの制約に対応する。
制約1  分割された2つの部分グラフの合併は元のグラフと一致する。
制約2  もし部分グラフが頂点xを含むなら、その部分グラフは頂点xへの全ての路(path)を含む。
制約3  一つのペアリングに含まれる二つの頂点は互いに異なる部分グラフに含まれる。
制約4  もし一方の部分グラフが重複不可頂点を含むなら他方の部分グラフはその頂点を含まない。
【００６５】
＜目的関数設定部１２０＞
目的関数設定部１２０は、目的関数を全ての割り当て変数に関する線型関数として設定する（Ｓ１２０）。もし目的関数が割り当て変数の非線形（論理）関数であるなら、次式に基づき、目的関数を線形制約付き線形目的関数に変換し設定する。
【数２０】
2018116194.tif 000022
【００６６】
＜整数計画部１３０＞
整数計画部１３０は、線形制約と線型関数または線形目的関数とを0-1整数計画アルゴリズムに入力し、依存関係グラフの最適分割の厳密解又は近似解を求める（Ｓ１３０）。
【００６７】
＜分割構成部１４０＞
分割構成部１４０は、厳密解又は近似解の割り当て変数の値に従って、対称ペアリング上定義された方式の構成、構文、帰着、仮定等をまとめた1つの依存関係グラフを2つの部分グラフに分割し（Ｓ１４０）、2つの部分グラフ及び元の方式より非対称ペアリング上に定義された方式の構成、構文、帰着、仮定等を再構築し、そのアルゴリズムを出力する。
【００６８】
＜効果＞
以上の構成により、従来よりも最適化実行時間の高速化が期待できる。式(15)が全て±1係数の2変数不等式であるので、条件1と条件2を満足するAを構成できる。そのため、整数計画部１３０における整数計画法の高速化が期待できる。
【産業上の利用可能性】
【００６９】
例えば、本実施形態のペアリング型変換装置によって、対称ペアリングに基づくIDベース暗号(参考文献５参照)を非対称ペアリングに基づくIDベース暗号に変換することができる。
(参考文献５)小林鉄太郎,山本剛,鈴木幸太郎,平田真一,「IDベース暗号の応用とキーワード検索」、NTT技術ジャーナル、2010.2, pp.17-20
【００７０】
ここで、変換されたIDベース暗号は以下のように産業上利用可能である。例えば、ある利用者Aが他の利用者Bに平文mを暗号化して送信する場合について考える(図８参照)。利用者Aの利用者端末１０Ａは、鍵発行センタ２０の公開情報と利用者BのIDから暗号化鍵PKBを計算し、計算した暗号鍵PKBを用いて平文mを暗号化し(このとき、ペアリング演算を行う、例えば、c=enc(PKB,m))、暗号文cを利用者Bの利用者端末１０Ｂに送信する。利用者端末１０Ｂは、鍵発行センタ２０に対して利用者B用の秘密鍵(復号鍵)を要求する。鍵発行センタ２０は要求に基づき利用者Bの暗号化鍵(公開鍵)PKBとIDからマスター秘密鍵SKを用いて利用者B用の秘密鍵SKBを生成し、利用者端末１０Ｂに送信する。利用者端末１０Ｂは利用者B用の秘密鍵をSKB受け取り、暗号文cを復号する(このとき、ペアリング演算を行う、例えば、m'=dec(SKB,c))。このようにして、利用者Aは利用者Bに平文mを暗号化して安全に送信することができる。
【００７１】
また、例えば、本実施形態のペアリング型変換装置によって、対称ペアリングに基づく電子署名(参考文献６参照)、属性ベース暗号、関数暗号を、それぞれ非対称ペアリングに基づく電子署名、属性ベース暗号、関数暗号に変換することができる。変換された電子署名、属性ベース暗号、関数暗号についても当然、産業上利用可能である。
(参考文献６)Dan Boneh, Ben Lynn, and Hovav Shacham, "Short signatures from the Weil pairing", 2004.
【００７２】
＜その他の変形例＞
本発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【００７３】
＜プログラム及び記録媒体＞
また、上記の実施形態及び変形例で説明した各装置における各種の処理機能をコンピュータによって実現してもよい。その場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００７４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させてもよい。
【００７６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶部に格納する。そして、処理の実行時、このコンピュータは、自己の記憶部に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実施形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよい。さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、プログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７７】
また、コンピュータ上で所定のプログラムを実行させることにより、各装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2018116194.tif 000023
【図２】
2018116194.tif 000024
【図３】
2018116194.tif 000025
【図４】
2018116194.tif 000026
【図５】
2018116194.tif 000027
【図６】
2018116194.tif 000028
【図７】
2018116194.tif 000029
【図８】
2018116194.tif 000030