JP6445474B2 - ペアリング型変換装置、ペアリング型変換方法、プログラム - Google Patents

Description

本発明は、アルゴリズムの代数的構造を変換するペアリング型変換装置、ペアリング型変換方法、プログラムに関する。

アルゴリズムの代数的構造を変換する技術が知られている。例えば、非特許文献１には、群G,G_T上のペアリングe:G×G→G_Tを用いたアルゴリズムを、群G₁,G₂,G_T上のペアリングe:G₁×G₂→G_T(ただしG₁≠G₂)を用いたアルゴリズムに変換する技術が開示されている。非特許文献１では、群G上の群演算の依存関係グラフのノードに群G₁または群G₂を割り当て、その割り当て状況を評価関数で評価し、最も評価の良い割り当てを選択する。

＜準備＞
暗号学においてペアリングとは概ね次のような代数的構造を持つ符号を生成する確率的多項式時間アルゴリズムPの事である。

ただし、λは安全変数、qはq>2^Θ(λ)なる整数、G₁,G₂,G_Tはそれぞれ同型の位数qの有限アーベル群(の符号)で、それぞれ多項式時間の標本演算および群演算を持つ。また、e:G₁×G₂→G_Tは多項式時間非退化双準同型である。G₁,G₂,G_T上のCDH(Computational Diffie-Hellman)問題は難しい。

G₁,G₂をソース群(source group)、G_Tをターゲット群(target group)と呼ぶ。とくに明示しない限り、単に群と呼んだり群要素などと呼ぶ時はソース群あるいはソース群の群要素を意味するとする。Galbraithらは、暗号方式に用いられるペアリングを大雑把に以下の３つの型に分類した（非特許文献２）。
Type1:G₁=G₂
Type2:G₁≠G₂,φ:G₂→G₁なる多項式時間同型写像が存在する。
Type3:G₁≠G₂,G₁,G₂の間に多項式時間同型写像が存在しない。

一般にType1を対称ペアリングと呼び、Type2、Type3を非対称ペアリングと呼ぶ。Type2はType3を利用して実装できるので、方式や安全性証明にφを積極的に利用する時以外はType2が登場する事はあまり無い。本明細書では非対称ペアリングとして特にType3を想定する。演算速度や群要素のサイズといった実装上の問題に関して、対称ペアリングよりもずっと効率的な非対称ペアリングの存在が知られている（非特許文献３参照）。
＜依存関係グラフ(非特許文献１)＞
方式に対して、その依存関係グラフ(dependency graph)とは方式を記述する群要素変数の間の依存関係を表現する有向グラフである。図１に簡易な例における依存関係グラフを示す。以下は、図１の依存関係グラフに対応するアルゴリズムである。

上記アルゴリズムは、群要素A,B,Dを入力とし、群演算を使ってC,Eを計算し、そのペアリングe(C,E)を出力するアルゴリズムの例である。図１に示す依存関係グラフの丸いシンボルで表した各ノードは群要素変数を表現しており、各エッジ（図中の矢印シンボル）は群演算による依存関係を表現している。ペアリングへの入力はペアリングノード９１、９２（図中の角丸四角形シンボル）への結線（矢印）により表現される。依存関係グラフには、群演算を介した群要素同士の関係のみが記述され、"if-then-else"命令のようなプログラムの構造やa∈Z/pZのような群要素以外の変数、あるいはターゲット群上の演算などは全て捨象される。以下、依存関係グラフの説明に用いる用語を定義する。

＜祖先グラフ＞
ある特定のノードに到達可能な全ての経路（エッジ）を含む依存関係グラフの部分グラフを、その特定のノードの祖先グラフという。

＜祖先ノード＞
ある特定のノードに到達可能なノードをその特定のノードの祖先ノードという。例えば図１の例において、ノードＡはノードＣの祖先ノードである。

＜子孫ノード＞
ある特定のノードから到達可能なノードをその特定のノードの子孫ノードという。例えば図１の例において、ノードＣはノードＡの子孫ノードである。

＜入力エッジ＞
祖先ノードに対する群演算による依存関係を表す。図１の例において、群要素Cは、群要素Aに対して入力エッジ８１で接続されている。

＜出力エッジ＞
子孫ノードに対する群演算による依存関係を表す。図１の例において、群要素Aは、群要素Cに対して出力エッジ８１で接続されている。

＜ペアリングノード＞
依存関係グラフにおいてペアリングへの入力を表現するノードをペアリングノードという。図１の例において、ペアリングノード９１、９２が例示されている。

＜レギュラーノード＞
ペアリングノードでないノードをレギュラーノードという。図１の例においてレギュラーノードは丸いシンボルで表されている。

＜ボトムノード＞
レギュラーノードのうち、出力エッジが全くないか、出力エッジがないループ全体を代表するノードをボトムノードという。

＜二重化ノード＞
二つのソース群の両方の割り当てが起こったノードを二重化ノードという。二重化ノードについては後述する。

＜二重化禁止ノード＞
何らかの理由により二重化ノードとなることを禁止されたノードを二重化禁止ノードという。

＜クリティカルノード＞
ペアリングノード、ボトムノード、二重化禁止ノードをまとめてクリティカルノードという。

＜ノーマルノード＞
クリティカルノードでないノードをノーマルノードという。

＜術語＞
あるノードxに対してxが分割後にG_i,i∈{1,2}側のグラフに含まれているという述語をx∈G_iと記述し,¬(x∈G_i)の事を

と記述する。そしてそれらの述語が真であるときその値を1、述語が偽であるときその値を0と定義する。即ち(x∈G_i)∈{0,1}である。あるノードxがクリティカルノードであるなら述語x∈G₁と述語x∈G₂は排他的である。即ち排他律x∈G₁∧x∈G₂=0が成立する。一方xがノーマルノードであるなら排他律は必ずしも成立しない。本明細書ではクリティカルノードxに関する述語x∈G₂を改めて論理変数xとして記述する。即ちクリティカルノードxに関して

である。

＜丹後らのアルゴリズム（非特許文献４、１）＞
対称ペアリングは代数的構造が簡単な為、多くの暗号方式が対称ペアリングを前提に設計されている。しかし時間計算量や領域計算量等の効率の観点から、現在では非対称ペアリングを使用することが望ましいと考えられるようになった。そこで、丹後らは対称ペアリングに基づく暗号方式を安全性を保ったまま非対称ペアリングに基づく暗号方式に自動変換するアルゴリズムを提案した（非特許文献４、１）。丹後らの変換は概ね以下のアルゴリズムによって構成される。
Step1:暗号方式を構成する各アルゴリズムおよび安全性証明で使用する帰着アルゴリズムにおける群演算の依存関係グラフ(有向グラフ)をそれぞれ構成し、それを一つに統合する。図２に、丹後らのアルゴリズムにおける依存関係グラフの統合を例示した。例えば、ノードＰ，Ｑ，Ｒなどを含む暗号化アルゴリズムを表す依存関係グラフ（図２左）と、ノードＰを含む復号アルゴリズムを表す依存関係グラフ（図２中央）は、一つの依存関係グラフ（図２右）に統合される。
Step2:ペアリングへの入力に相当するペアリングノードと群要素比較演算への入力に相当するボトムノードと呼ばれるノードをG₁またはG₂に割り当てる。図３に、丹後らのアルゴリズムにおけるソース群の割り当ておよびソース群ごとのグラフの分解を例示する。図３の依存関係グラフに含まれるボトムノード７１、７２には例えばG₁が割り当てられ、ボトムノード７３、７４には例えばG₂が割り当てられる（図３上段中央）。
Step3:各ペアリングノードおよびボトムノードにおいて、入力エッジの隣接ノードを次々と遡ったノード(祖先ノード)を元のペアリングノードあるいはボトムノードと同じ割り当てを行なう。この時G₁とG₂の両方の割り当てが起こった場合は両方割り当たっているノード(二重化ノード)と解釈する。図３の例では、ボトムノード７１、７２の祖先ノードには、G₁が割り当てられ、ボトムノード７３、７４の祖先ノードには、G₂が割り当てられ、双方のソース群が割り当てられたノード６１などは、二重化ノードと解釈される（図３上段右）。
Step4:グラフ中に現れるHashToPoint()演算等に相当する二重化禁止ノードが二重化ノードとなっている場合はその割り当ては無効とする。それ以外の場合はグラフの全体の割り当て状況を評価関数に入力して評価する。
Step5:Step2における全ての割り当てに関して、最も評価が良いグラフをG₁が割当たってるノードからなるグラフとG₂が割当たってるノードからなるグラフに分解して出力する（図３下段）。

丹後らの変換はStep2におけるソース群割り当てのバリエーション数に比例した回数Step3、Step4を実行しなくてはならない。これはペアリングノードのペアの数とボトムノードの数の和をnとすると、2ⁿ回の演算を必要としており、nが大きい時には計算量が大きくなりすぎて実行困難となる。

＜整数計画法を用いた分割アルゴリズム＞
非対称ペアリングにおいては、ペアリングへの入力は一方にG₁が割当たってるとするなら対になるノードにはG₂が割当たっている必要がある。従ってペアリングの対になっているノード対x,y∈{0,1}について
x+y=1…(1)
が成立する。また、あるクリティカルノードxの祖先ノードにクリティカルノード(二重化禁止ノード)yがある場合はそれらのノードの割り当ては等しい、即ち
x-y=0…(2)
が成立する。

＜例＞
図４にBonehらの検証者ローカル失効付きグループ署名アルゴリズム（非特許文献５）を表現する依存関係グラフを示す。g₁,g₂,ωがこの方式のグループ公開鍵に相当する。詳細は非特許文献５を参照のこと。(p₁[0],p₁[1]),…,(p₈[0],p₈[1])がそれぞれ対になるペアリングノードの対である。また出力ノードの無いR₁,R₃,

がボトムノードである。また、u,vが二重化禁止ノードにあたる（非特許文献４）。従ってこのグラフには、u,v,R₁,R₃,

,p₁[0],p₁[1],…,p₈[0],p₈[1]の合計21個のクリティカルノードが存在する。これらのクリティカルノード間のGF(2)上線型関係を考える。上記の変数順序に従い係数および定数項の値を順に並べて一つの線型関係を表現する。例えばp₁[0],p₁[1]はペアリングの対になっているクリティカルノードであるから、

が成立する。上記の変数順序において、6番目の変数p₁[0]および7番目の変数p₁[1]の係数が1で他の係数が0であり、定数項が1であるから、この式を係数および定数項の値だけで表現すると
0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
となる。","を省略すると
0000011000000000000001
と表現できる。図５に上記の過程を図示した。この方法で、図４のグラフの線型関係を全て書き下すと、図６に例示する線形関係行列となる。この行列をGF(2)上のGaussの消去法を用いて階段型(echelon form)に変換する事が出来る。図６の線形関係行列を階段型に変換した階段型行列を図７に例示する。
もし階段型行列の最下段非ゼロ行が
0000000000000000000001
となった場合は、全ての変数の係数が0であり、かつ定数項が1であるから、どのような変数の割り当てに対してもその式を充足する事は出来ない。即ちそのグラフは分割不可能となる。上記のグループ署名の例では最下段非ゼロ行が
0000000000000000000111
となっている（図７参照）ので、分割可能であることが分かる。本明細書では、階段型の何れかの行(に対応する関係式)において、先頭項(図７の実線下線を付した１に相当)となる変数を従属変数と呼ぶ。そして従属変数でない変数（図７の破線下線を付した列に相当）を独立変数と呼ぶ。従って上記の例ではp₁[1],p₈[1]は独立変数、それ以外は従属変数である。全ての独立変数の値の割り当てを適当に1つ決めると、階段行列の下の方の関係式から順次従属変数の値を一意に決定することが出来る。

一般に独立変数の個数がn個あるとすると、値の割り当て方法(実行可能解)は2ⁿ個存在する。こうした割り当ての内、何らかの評価基準を満たした最適な分割を見つけたいとする。例えば図４のグループ署名の場合、g₁,g₂,ωが公開鍵に相当する。従って公開鍵のサイズが最も小さい分割を見つけたいならg₁,g₂,ωの合計サイズが最も小さいグラフを見つければ良い。本明細書では、このような評価基準をノードNに対する重みw_Nを用いて表現する。例えば図４の場合、ノードg₁,g₂,ωは重み1、残りのノードについては重み0等と設定する。

|G_i|,i∈{1,2}をG_iの元を表現するのに必要なビット数と定義し、w_N,i=w_N・|G_i|と定義する。そしてグラフgに含まれる頂点の集合をVgとする。これらの記法を用いて、各述語の値をそのまま整数と見なすと上記の公開鍵のサイズを最小化したい問題等は、

なる数値を最小化する問題であると捉えることが出来る。ノードNが子孫にもつクリティカルノードの集合をD_Nと定義すると

とする事ができる。従って

と書くことが出来る。ところで{0,1}上の変数x,x₁,x₂,yについて、

である。即ち{0,1}変数の任意の連言と否定は線型制約の元で変数に置き換え可能であり、どのような命題変数の論理式もこの置き換えを繰り返す事によって{0,1}変数の線型制約付き線型式に変換出来る事が良く知られている。特にx₁,...,x_k,y∈{0,1}の時

である。従って、{0,1}上の値y_1,Nを

と定義すると、

であるから

と出来る。同様に

と定義すると、

である。従って

を最小化する問題は

に関して

なる線形制約の下、

なる線形の目的関数を最小化する問題に帰着できる。

また、ペアリングの対になっているクリティカルノードd₁,d₂に対してd₁,d₂を{0,1}上の変数と見なすとd₁+d₂=1が成立する。また先祖・子孫の関係を持つクリティカルノードd₁,d₂について同様にd₁-d₂=0が成立する。従って、これらの線型関係を全て書き下した上で上記の線型制約および上記の目的関数を任意の0-1整数計画法アルゴリズムに入力する事によって、厳密解あるいは近似解を得ることが出来る。

M. Abe, J. Groth, M. Ohkubo, and T. Tango. Converting cryptographic schemes from symmetric to asymmetric bilinear groups. In J. A. Garay and R. 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. S. D. Galbraith, K. G. Paterson, and N. P. Smart. Pairings for cryptographers. Discrete Applied Mathematics, 156(16):3113{3121, 2008. P. S. L. M. Barreto and M. Naehrig. Pairing-friendly elliptic curves of prime order. In B. Preneel and S. 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. T. Tango, M. Abe, and T. Okamoto. Implementation of Automated Translation for Schemes on Symmetric Bilinear Groups. In Proc. of SCIS 2014, 2014. D. Boneh and H. Shacham. Group signatures with verier-local revocation. In V. Atluri, B. Ptz-mann, and P. D. McDaniel, editors, Proceedings of the 11th ACM Conference on Computer and Communications Security, CCS 2004, Washington, DC, USA, October 25-29, 2004, pages 168{177. ACM, 2004. J. Groth and A. Sahai. Efficient noninteractive proof systems for bilinear groups. SIAM J. Comput., 41(5):1193{1232, 2012.

大規模な方式の設計を行なう場合ペアリングやべき乗といった概念よりも抽象度が高い概念を暗号プリミティブとして利用する事がある(例えばGroth-Sahai証明、非特許文献６)。こうした抽象度の高いプリミティブ(上位プリミティブ)をペアリングやべき乗といった具体的プリミティブで実装する時、その実装方法は必ずしも一意であるとは限らない。さらにその最適な実装は上位プリミティブそのものでは無くそれを用いて設計している方式に依存して変化し得る。そのような場合は厳密な意味での依存関係グラフは一意に定まらない。例えばGroth-Sahai証明において

なる等式の非対話ゼロ知識証明(NIZK, NonInteractive Zero-Knowledge proofs)が

なる等式の非対話証拠識別不能証明(NIWI, NonInteractive Witness-Indistinguishable proofs)を利用して構成される場合がある（非特許文献６）。但し[X]は群要素Xについてコミットされた群要素変数であるとする。この時、利用しているペアリングが対称ペアリングである場合e(B_i ^-1,[C_i])を用いる代わりにe(C_i ^-1,[B_i])を用いても構わない。即ち上記の上位プリミティブGroth-Sahai証明を対称ペアリングで実装する際には、定数ペアリングの数をnとするとN=2ⁿ個の自由度が存在し、その依存関係グラフは一意に定まらない。従ってそのような上位プリミティブが方式内にm個存在すると、全ての実装の中で最適な方式を得るにはN^m回の整数計画法を用いたアルゴリズムを呼び出す必要があり、mが大きくなると事実上計算不能であった。

そこで本発明では、整数計画法を用いたアルゴリズムの呼び出し回数を１回に短縮することができるペアリング型変換装置を提供することを目的とする。

本発明のペアリング型変換装置は、仮想依存関係グラフ生成部と、識別子割り当て部と、論理式組み入れ部と、評価関数線形化部を含む。

仮想依存関係グラフ生成部は、実装に際し、選択可能な上位プリミティブを複数含む暗号プロトコルについて、上位プリミティブを全て列挙して組み入れた仮想の依存関係グラフを生成する。識別子割り当て部は、上位プリミティブのそれぞれに、識別子を割り当てる。論理式組み入れ部は、識別子が適切な実装の値と一致する場合に限り、識別子に対応するノードが評価関数においてカウントされるように論理式を組み入れる。評価関数線形化部は、評価関数を線形化し、評価関数および探索空間を整数計画問題インスタンスに変換する。

本発明のペアリング型変換装置によれば、整数計画法を用いたアルゴリズムの呼び出し回数を１回に短縮することができる。

簡易な例における依存関係グラフを示す図。 丹後らのアルゴリズムにおける依存関係グラフの統合を例示する図。 丹後らのアルゴリズムにおけるソース群の割り当ておよびソース群ごとのグラフの分解を例示する図。 Bonehらの検証者ローカル失効付きグループ署名アルゴリズムを表現する依存関係グラフを示す図。 クリティカルノード間の線形関係を行列形式に変換する過程を例示する図。 線形関係行列を例示する図。 線形関係行列を階段型に変換した階段型行列を例示する図。 実施例１のペアリング型変換装置の構成を示すブロック図。 実施例１のペアリング型変換装置の動作を示すフローチャート。 上位プリミティブを列挙した仮想の依存関係グラフを例示する図。 仮想の依存関係グラフにおいて特定の識別子に対応する上位プリミティブのノードのみが評価関数においてカウントされる状態を例示する図。

以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。

以下、図８、図９、図１０、図１１を参照して実施例１のペアリング型変換装置の構成および動作について説明する。図８は、本実施例のペアリング型変換装置１の構成を示すブロック図である。図９は、本実施例のペアリング型変換装置１の動作を示すフローチャートである。図１０は、上位プリミティブを列挙した仮想の依存関係グラフを例示する図である。図１１は、仮想の依存関係グラフにおいて特定の識別子に対応する上位プリミティブのノードのみが評価関数においてカウントされる状態を例示する図である。

図８に示すように、本実施例のペアリング型変換装置１は、仮想依存関係グラフ生成部１１と、識別子割り当て部１２と、論理式組み入れ部１３と、評価関数線形化部１４を含む。

仮想依存関係グラフ生成部１１は、実装に際し、選択可能な上位プリミティブを複数含む暗号プロトコルについて、上位プリミティブを全て列挙（図１０に上位プリミティブ５１−１、５１−２、５１−３、…として例示）して組み入れた仮想の依存関係グラフ（図１０に仮想依存関係グラフ４として例示）を生成する（Ｓ１１）。識別子割り当て部１２は、上位プリミティブのそれぞれに、識別子（図１０に識別子v=1,2,3…として例示）を割り当てる（Ｓ１２）。論理式組み入れ部１３は、識別子が適切な実装の値と一致する場合（図１１に識別子v=2が適切な実装の値と一致する場合を例示）に限り、識別子に対応するノードが評価関数においてカウントされるように論理式を組み入れる（Ｓ１３）。評価関数線形化部１４は、評価関数を線形化し、評価関数および探索空間を整数計画問題インスタンスに変換する（Ｓ１４）。

以下に、本実施例のペアリング型変換装置１の動作の詳細を説明する。方式の規模を表すパラメタをsとすると実装の自由度Nがsに対して多項式(即ちn=O(log(s)))であるような上位プリミティブが方式内に多項式個(m=O(s^c))ぐらい存在するような状況を考える。ただしOはビッグオー記法である。このような状況下では依存関係グラフが一意に定まらない場合でも、下記のように仮想的な依存関係グラフを考える事によって単一の整数計画問題インスタンスを構成出来る。
Step.1:各上位プリミティブに対して１つずつ整数変数（識別子）を定義する。
Step.2:上位プリミティブのあり得る実装を全て仮想的に実装し（上記ステップＳ１１）、各仮想的実装に上記整数変数（識別子）の値を１つずつ割り当てる（上記ステップＳ１２）。この時、仮想依存関係グラフ生成部１１は、元の方式に陽には含まれない群要素変数で、複数の仮想的実装から参照されるものはまとめて一つだけ（仮想的に）実装する。
Step.3:値が割り当てられた仮想的実装に含まれる群要素変数を評価関数に組み入れる際は、上記整数変数（識別子）がその値と一致する時だけ評価されるよう、係数に上記整数変数の術語（等式）を設定する。複数の仮想的実装から参照される仮想的な群要素変数については上記の術語を∨で繋いだものを係数に設定する（上記ステップＳ１３）。
Step.4: 評価関数線形化部１４は、必要な場合は、整数変数（識別子）をバイナリ変数に変換する。この時、整数変数（識別子）の術語（等式）はバイナリ変数の術語（等式）を∧で繋いだ式に変換される。さらにバイナリ変数の術語（等式）はリテラル（バイナリ変数それ自身か、またはその否定）に変換される。最終的に式(3)等を使って評価関数を線形化する（上記ステップＳ１４）。

例えば、以下のようなNIZK(NonInteractive Zero-Knowledge proofs)のシーケンスを考える。

ここで、crs,[X],[B],proof等は各右辺の関数内部で具体的な群演算によって生成される有限個の群要素変数のリストとする。以下、それらのリストのビット長を|[X]|等と記述する。一般にはNIZK.Proveと対応するNIZK.Verifyは方式を構成する異なるアルゴリズム中で使用されるが、最終的に依存関係グラフは一つに統合されるのでここでは一つのシーケンスとして記述する。コミット[B]は・・・の部分で参照されているとする。上記Step.1に従って上記のシーケンス中の上位プリミティブNIZKに対し変数v∈{0,1}を準備する。そしてStep.2に従い実装を以下のように列挙し、変数の値を割り当てる（下記のコメント部参照）。

ここで、元の方式には陽に含まれていないコミット[C]はv=0の仮想的実装からのみ参照される。仮にコミット[C]が他の仮想的実装から参照されるとしても１つだけ実装する。Groth-Sahai証明においてNIWI(NonInteractive Witness-Indistinguishable proofs)を使ってNIZK(NonInteractive Zero-Knowledge proofs)を構成する為には、実際には追加のNIWIが幾らか必要になるが、上記では、・・・と記述して省略している。Step.3に従い目的関数が例えばコミットのサイズを最小化する関数であったとするなら

等と定義する。コミット[X],[B]は元々の方式で定義されているので無条件に目的関数に組み入れられている。一方コミット[C]は上位プリミティブの展開によって新たに発生するコミットなので条件付きの項となる。Step.4に従い、|[X]|,|[B]|,|[C]|は、前述の方法に従ってクリティカルノードの論理式に展開される。

そして最終的に式(1)、(2)および、

なる線形制約の下、

なる目的関数を最小化する１つの0-1整数線形計画問題インスタンスに帰着される。

＜補記＞
本発明の装置は、例えば単一のハードウェアエンティティとして、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（CentralProcessingUnit、キャッシュメモリやレジスタなどを備えていてもよい）、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けることとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。

ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくこととしてもよい）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。

ハードウェアエンティティでは、外部記憶装置（あるいはＲＯＭなど）に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（上記、…部、…手段などと表した各構成要件）を実現する。

本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。

既述のように、上記実施形態において説明したハードウェアエンティティ（本発明の装置）における処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。

この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（DigitalVersatileDisc）、ＤＶＤ−ＲＡＭ（RandomAccessMemory）、ＣＤ−ＲＯＭ（CompactDiscReadOnlyMemory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Opticaldisc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（ElectronicallyErasableandProgrammable-ReadOnlyMemory）等を用いることができる。

また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。

このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（ApplicationServiceProvider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。

また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。

Claims (7)

1. 実装に際し、選択可能な上位プリミティブを複数含む暗号プロトコルについて、前記上位プリミティブを全て列挙して組み入れた仮想の依存関係グラフを生成する仮想依存関係グラフ生成部と、
   前記上位プリミティブのそれぞれに、識別子を割り当てる識別子割り当て部と、
   前記識別子が適切な実装の値と一致する場合に限り、前記識別子に対応するノードが評価関数においてカウントされるように論理式を組み入れる論理式組み入れ部と、
   前記評価関数を線形化し、前記評価関数および探索空間を整数計画問題インスタンスに変換する評価関数線形化部と、
   を含むペアリング型変換装置。
2. 請求項１に記載のペアリング型変換装置であって、
   前記仮想依存関係グラフ生成部は、
   複数の仮想的実装から参照される群要素変数を、前記仮想の依存関係グラフに一つだけ組み入れる
   ペアリング型変換装置。
3. 請求項１または２に記載のペアリング型変換装置であって、
   前記評価関数線形化部は、
   前記識別子をバイナリ変数に変換する
   ペアリング型変換装置。
4. ペアリング型変換装置の仮想依存関係グラフ生成部は、実装に際し、選択可能な上位プリミティブを複数含む暗号プロトコルについて、前記上位プリミティブを全て列挙して組み入れた仮想の依存関係グラフを生成するステップを実行し、
   ペアリング型変換装置の識別子割り当て部は、前記上位プリミティブのそれぞれに、識別子を割り当てるステップを実行し、
   ペアリング型変換装置の論理式組み入れ部は、前記識別子が適切な実装の値と一致する場合に限り、前記識別子に対応するノードが評価関数においてカウントされるように論理式を組み入れるステップを実行し、
   ペアリング型変換装置の評価関数線形化部は、前記評価関数を線形化し、前記評価関数および探索空間を整数計画問題インスタンスに変換するステップを実行する
   ペアリング型変換方法。
5. 請求項４に記載のペアリング型変換方法であって、
   前記仮想依存関係グラフ生成部は、
   複数の仮想的実装から参照される群要素変数を、前記仮想の依存関係グラフに一つだけ組み入れる
   ペアリング型変換方法。
6. 請求項４または５に記載のペアリング型変換方法であって、
   前記評価関数線形化部は、
   前記識別子をバイナリ変数に変換する
   ペアリング型変換方法。
7. コンピュータを請求項１から３の何れかに記載のペアリング型変換装置として機能させるためのプログラム。

Images