(57)【特許請求の範囲】
【請求項１】
ｎが２以上の整数であり、ｊ＝０，・・・，ｎ−１であり、Ｆ２が位数２の有限体であり、代数的構造Ｇでの演算の依存関係を表す依存関係グラフのノードＮ（ｊ）に代数的構造Ｇ１を割り当てる場合にｑ（ｊ）＝０∈Ｆ２とし、前記ノードＮ（ｊ）に代数的構造Ｇ２を割り当てる場合にｑ（ｊ）＝１∈Ｆ２とし、Ｇ１≠Ｇ２であり、ｍが１以上の整数であり、ｉ＝０，・・・，ｍ−１であり、Ｓ（ｉ）が１以上の整数であり、｛ｓ（ｉ，φ（０）），・・・，ｓ（ｉ，φ（Ｓ（ｉ）−１））｝⊆｛０，・・・，ｎ−１｝であり、
線形制約ｑ（ｓ（ｉ，φ（０）））＋・・・＋ｑ（ｓ（ｉ，φ（Ｓ（ｉ）−１）））＝ｙ（ｉ，ｎ）∈Ｆ２に対し、｛０，・・・，ｎ−１｝における｛ｓ（ｉ，φ（０）），・・・，ｓ（ｉ，φ（Ｓ（ｉ）−１））｝の補集合の要素ｒについてｙ（ｉ，ｒ）＝０とし、｛ｓ（ｉ，φ（０）），・・・，ｓ（ｉ，φ（Ｓ（ｉ）−１））｝の要素ｋについてｙ（ｉ，ｋ）＝１としたｙ（ｉ，０），・・・，ｙ（ｉ，ｎ−１），ｙ（ｉ，ｎ）をｉ行目の要素とする行列を表す情報を得る行列生成部と、
ｙ（ｉ，０），・・・，ｙ（ｉ，ｎ−１），ｙ（ｉ，ｎ）をｉ行目の要素とする前記行列から、ｚ（ｉ，０），・・・，ｚ（ｉ，ｎ−１），ｚ（ｉ，ｎ）をｉ行目の要素とする階段行列を表す情報を得る行列変形部と、
前記階段行列を表す情報に基づいて前記ノードＮ（ｊ）が独立ノードであるか否かを判定して、前記ノードＮ（ｊ）に前記代数的構造Ｇ１または前記代数的構造Ｇ２を割り当てる構造割当部と、
を有する構造変換装置。
【請求項２】
請求項１の構造変換装置であって、
（１）前記階段行列がｚ（０，０）＝１である行およびｚ（１，１）＝０である行を含む場合に前記ノードＮ（１）が独立ノードであると判定し、（２）前記階段行列が１以上ｎ−２以下の整数ｔ（ω）についてｚ（ω，０）＝・・・＝ｚ（ω，ｔ（ω）−１）＝０かつｚ（ω，ｔ（ω））＝１である行およびｚ（ω＋１，ｔ（ω）＋１）＝０である行を含む場合に前記ノードＮ（ｔ（ω）＋１）が独立ノードであると判定し、（３）前記階段行列がｚ（ｍ−１，０）＝・・・＝ｚ（ｍ−１，ｔ（ｍ−１）−１）＝０かつｚ（ｍ−１，ｔ（ｍ−１））＝１である行を含む場合に前記ノードＮ（ｔ（ｍ−１）＋１），・・・，Ｎ（ｎ−１）が独立ノードであると判定する第１判定部を有する構造変換装置。
【請求項３】
請求項２の構造変換装置であって、
前記構造割当部は、独立ノードであると判定された前記ノードＮ（ν）（ただし、ν∈｛０，・・・，ｎ−１｝）に前記代数的構造Ｇ１および前記代数的構造Ｇ２の何れを割り当てるかを決定した後、他の前記ノード（η）（ただし、η∈｛０，・・・，ｎ−１｝かつη≠ν）に前記代数的構造Ｇ１または前記代数的構造Ｇ２を割り当てる、構造変換装置。
【請求項４】
請求項１から３の何れかの構造変換装置であって、
前記階段行列がｚ（ι，０）＝・・・＝ｚ（ι，ｎ−１）＝０かつｚ（ι，ｎ）＝１となる要素を含む場合、前記線形制約での割り当てが不可能であると判定する第２判定部を有する構造変換装置。
【請求項５】
請求項１から４の何れかの構造変換装置であって、
前記依存関係グラフは、対称型双線形写像の入力値を得るアルゴリズムに含まれる群演算の依存関係を表し、
前記代数的構造Ｇは群であり、前記対称型双線形写像の定義域Ｇ×Ｇをなし、
前記代数的構造Ｇ１および前記代数的構造Ｇ２は互いに異なる群であり、非対称型双線形写像の定義域Ｇ１×Ｇ２をなし、
Ｓ（ｉ）＝２であり、
同一の前記対称型双線形写像の入力値の対に対応する前記ノードＮ（ｊ１）およびＮ（ｊ２）に対応する前記線形制約がｑ（ｊ１）＋ｑ（ｊ２）＝１∈Ｆ２であり、
前記ノードＮ（ｊ３）と前記ノードＮ（ｊ３）の祖先ノードである前記ノードＮ（ｊ４）とに対応する前記線形制約がｑ（ｊ３）＋ｑ（ｊ４）＝０∈Ｆ２である、構造変換装置。
【請求項６】
ｎが２以上の整数であり、ｊ＝０，・・・，ｎ−１であり、代数的構造Ｇでの演算の依存関係を表す依存関係グラフのノードＮ（ｊ）に代数的構造Ｇ１を割り当てる場合にｑ１，ｊ＝１かつｑ２，ｊ＝０とし、前記ノードＮ（ｊ）に代数的構造Ｇ２を割り当てる場合にｑ１，ｊ＝０かつｑ２，ｊ＝１とし、Ｇ１≠Ｇ２であり、前記ノードＮ（ｊ）に前記代数的構造Ｇ１を割り当てる場合にｄ（ｊ）＝０とし、前記ノードＮ（ｊ）に前記代数的構造Ｇ２を割り当てる場合にｄ（ｊ）＝１とし、前記ノードＮ（ｊ）の子孫ノードがＤＮ（ρ（ｊ，０）），・・・，ＤＮ（ρ（ｊ，＃Ｄ（ｊ）−１））であり、Ｄ（ｊ）が集合｛ρ（ｊ，０），・・・，ρ（ｊ，＃Ｄ（ｊ）−１）｝であり、＃Ｄ（ｊ）が前記集合Ｄ（ｊ）の要素数であり、
前記依存関係グラフに基づいて、ｑ１，ｊ＋Σρ（χ）∈Ｄ（ｊ）ｄ（ρ（χ））≦＃Ｄ（ｊ）であり、∀ρ（χ）∈Ｄ（ｊ）についてｑ１，ｊ＋ｄ（ρ（χ））≧１であり、ｑ２，ｊ−Σρ（χ）∈Ｄ（ｊ）ｄ（ρ（χ））≦０であり、∀ρ（χ）∈Ｄ（ｊ）についてｑ２，ｊ−ｄ（ρ（χ））≧０である旨を含む線形制約を設定する線形制約設定部と、
前記線形制約のもと、線形の評価関数ｆ（ｑ１，０，・・・，ｑ１，ｎ−１，ｑ２，０，・・・，ｑ２，ｎ−１）の出力値が所定の条件を満たすｑ１，０，・・・，ｑ１，ｎ−１，ｑ２，０，・・・，ｑ２，ｎ−１を決定する評価探索部と、
を有する構造変換装置。
【請求項７】
請求項６の構造変換装置であって、
｜Ｇσ｜がσ∈｛１，２｝について前記代数的構造Ｇσの元を表現するために必要な情報量であり、ｗｊが前記ノードＮ（ｊ）について予め定められた重み係数であり、ｗｊ，σ＝ｗｊ・｜Ｇσ｜であり、前記評価関数はｆ（ｑ１，０，・・・，ｑ１，ｎ−１，ｑ２，０，・・・，ｑ２，ｎ−１）＝Σｊ∈｛０，・・・，ｎ−１｝（ｗｊ，１・ｑ１，ｊ＋ｗｊ，２・ｑ２，ｊ）であり、前記所定の条件は前記評価関数の出力値が最小となることである、構造変換装置。
【請求項８】
請求項６または７の構造変換装置であって、
前記依存関係グラフは、対称型双線形写像の入力値を得るアルゴリズムに含まれる群演算の依存関係を表し、
前記代数的構造Ｇは群であり、前記対称型双線形写像の定義域Ｇ×Ｇをなし、
前記代数的構造Ｇ１および前記代数的構造Ｇ２は互いに異なる群であり、非対称型双線形写像の定義域Ｇ１×Ｇ２をなし、
前記線形制約は、同一の前記対称型双線形写像の入力値の対に対応する前記ノードＮ（ｊ１）およびＮ（ｊ２）についてｄ（ｊ１）＋ｄ（ｊ２）＝１であり、前記ノードＮ（ｊ３）と前記ノードＮ（ｊ３）の祖先ノードである前記ノードＮ（ｊ４）とについてｄ（ｊ３）＋ｄ（ｊ４）＝０である旨をさらに含む、構造変換装置。
【請求項９】
請求項１から８の何れかの構造変換装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アルゴリズムの代数的構造を変換する技術に関する。
【背景技術】
【０００２】
アルゴリズムの代数的構造を変換する技術が知られている。例えば、非特許文献１，２には、群Ｇ，ＧＴ上のペアリングｅ：Ｇ×Ｇ→ＧＴを用いたアルゴリズムを、群Ｇ１，Ｇ２，ＧＴ上のペアリングｅ：Ｇ１×Ｇ２→ＧＴ（ただしＧ１≠Ｇ２）を用いたアルゴリズムに変換する技術が開示されている。この技術では、群Ｇ上の群演算の依存関係グラフのノードに群Ｇ１またはＧ２を割り当て、その割り当て状況を評価関数で評価し、最も評価の良い割り当てを選択する。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】T. Tango, M. Abe, and T. Okamoto, “Implementation of Automated Translation for Schemes on Symmetric Bilinear Groups,” In Proc. of SCIS 2014, 2014.
【非特許文献２】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.」参照）。
Ｔｙｐｅ１：Ｇ１＝Ｇ２
Ｔｙｐｅ２：Ｇ１≠Ｇ２，Φ：Ｇ２→Ｇ１なる多項式時間同型写像が存在する。
Ｔｙｐｅ３：Ｇ１≠Ｇ２，Ｇ１，Ｇ２の間に多項式時間同型写像が存在しない。
Ｔｙｐｅ１は構造的に簡単な為、多くの暗号プロトコルがＴｙｐｅ１を前提に設計されている。しかし計算量や空間計算量（公開鍵や暗号文等のサイズなど）などの効率の観点から現在ではＴｙｐｅ３のペアリングを使用することが望ましいと考えられるようになった。
【００１８】
本形態では、Ｔｙｐｅ１のペアリング（対称型双線形写像）が定義されたペアリング群上で動作する方式Ａ１のアルゴリズムを、Ｔｙｐｅ３のペアリング（非対称型双線形写像）が定義されたペアリング群で動作する方式Ａ３のアルゴリズムに変換する。以下ではＴｙｐｅ１の群をＧと表記する。Ｇ＝Ｇ１であってもよいし、Ｇ≠Ｇ１であってもよい。Ｇ＝Ｇ２であってもよいし、Ｇ≠Ｇ２であってもよい。方式Ａ１のアルゴリズムは、方式Ａ１を実行するプロトコルの構成要素の各アルゴリズムからなり、特にＴｙｐｅ１のペアリングの入力値を得るためアルゴリズムを含む。さらに方式Ａ１の安全性は「帰着」と呼ばれるアルゴリズム（帰着アルゴリズム）の集合が存在することによって示される。方式Ａ１のアルゴリズムは、さらにこの帰着アルゴリズムも含む。
【００１９】
方式Ａ１のアルゴリズムは、それに含まれる群演算の依存関係を表す依存関係グラフ（有向グラフ）によって表現できる（例えば、非特許文献２参照）。方式Ａ１のアルゴリズムの記述において、入力、出力、途中結果として現れる各群要素には固有のラベルが与えられる。依存関係グラフでは、アルゴリズムが扱うすべての各群要素のラベルに「ノード（変数）」が割り当てられる。依存関係グラフは、ノードからその群要素を用いて得られる次の群要素のノードに向かう「エッジ」を持つ。図３に方式Ａ１のアルゴリズムに含まれる群演算の依存関係を表す依存関係グラフを例示する。図３の依存関係グラフはノードＸ１−Ｘ１０およびｐ１［０］，ｐ１［１］，ｐ２［０］，ｐ２［１］を含む。各ノードは群Ｇの群要素に対応し、ノードから他のノードに向かうエッジを持つ。例えば、ノードＸ１は群Ｇの生成元ｇに対応し、ノードＸ２は生成元ｇを用いた群演算で得られる群要素ｇυ２∈Ｇを表す。例えば、ノードＸ４，Ｘ７はそれぞれ群要素ｇυ４，ｇυ７∈Ｇに対応し、ノードＸ９は群要素ｇυ４，ｇυ７を用いた群演算（例えば、ｇυ４・ｇυ７∈Ｇ）で得られる群要素ｇυ９∈Ｇを表す。
【００２０】
ノードＸからエッジ方向にたどってたどり着くことのできるノードをＸの「子孫ノード」と呼ぶ。逆に、ノードＸからエッジの逆方向にたどってたどり着くことのできるノードをＸの「祖先ノード」と呼ぶ。図３の例の場合、ノードＸ９はノードＸ２の子孫ノードであり、逆にノードＸ２はノードＸ９の祖先ノードである。
【００２１】
ペアリングの入力値に対応するノードを「ペアリングノード」と呼ぶ。ペアリングの入力値は２個の群要素の対であり、それらに対応するペアリングノードも対となる。図３の例の場合、ｐ１［０］，ｐ１［１］，ｐ２［０］，ｐ２［１］がペアリングノードである。対（ｐ１［０］，ｐ１［１］）に対応する群要素の対がペアリングｅ１への入力となり、対（ｐ２［０］，ｐ２［１］）に対応する群要素の対がペアリングｅ２への入力となる。
【００２２】
他のノードへのエッジが存在しないノード、および、他のノードへのエッジは存在するがそのエッジをたどった先が再び元のノードに戻るループを構成するノードを「ボトムノード」と呼ぶ。図３の例では、ノードＸ８がボトムノードである。
【００２３】
群Ｇの元ｘに対する群演算Ｈ（ｘ）＝ｇα１∈Ｇを仮定する。ただし、α１は任意の正の整数である。このとき、群Ｇ１の生成元κ１∈Ｇ１および群Ｇ２の生成元κ２∈Ｇ２、ならびに元ｘに対応する群要素ｘ１∈Ｇ１およびｘ２∈Ｇ２について、α１を知ることなく、Ｈ１（ｘ１）＝κ１α１およびＨ２（ｘ２）＝κ２α１を満たす演算Ｈ１およびＨ２を設定することが困難な群演算Ｈが存在する。群演算Ｈの例はハッシュ関数である。このような群演算Ｈの演算値に対応するノードに群Ｇ１およびＧ２の両方を割り当てることはできない。このようなノードを「２重化禁止ノード」と呼ぶ。図３の例では、ノードＸ６が２重化禁止ノードである。
【００２４】
ペアリングノード、ボトムノード、および２重化禁止ノードをまとめて「クリティカルノード」と呼ぶ。クリティカルノードではないノードを「ノーマルノード」と呼ぶ。クリティカルノードには、群Ｇ１またはＧ２の何れか一方しか割り当てることができない。一方、ノーマルノードには、群Ｇ１またはＧ２の何れか一方のみを割り当ててもよいし、群Ｇ１およびＧ２の両方を割り当ててもよい。図３の例では、ノードＸ６，Ｘ８，ｐ１［０］，ｐ１［１］，ｐ２［０］，ｐ２［１］がクリティカルノードであり、ノードＸ１−Ｘ５，Ｘ７，Ｘ９，Ｘ１０がノーマルノードである。
【００２５】
図４は、図３の依存関係グラフのノードのうち、群Ｇ１が割り当てられたノードによって再構築された依存関係グラフを例示する。図５は、図３の依存関係グラフのノードのうち、群Ｇ２が割り当てられたノードから再構築された依存関係グラフを例示する。これらの依存関係グラフが方式Ａ３のアルゴリズムを表す。これらの例に示すように、クリティカルノードには群Ｇ１またはＧ２の何れか一方のみしか割り当てることはできないが、ノーマルノードには群Ｇ１およびＧ２の両方を二重に割り当ててもよいし、それらの一方のみを割り当ててもよい。
【００２６】
＜構成＞
図１に例示するように、本形態の構造変換装置１は、入力部１１、記憶部１２、制御部１３、グラフ構築部１４１、線形制約設定部１４２、行列生成部１４３、行列変形部１４４、判定部１４５、および構造割当部１４７を有する。構造割当部１４７は、探索部１４７ａ、割当部１４７ｂ、および判定部１４７ｃを有する。構造変換装置１は、制御部１３の制御のもとで各処理を実行する。入力されたデータおよび各部で得られたデータは記憶部１２に格納され、必要に応じて読み出されて各処理に用いられる。構造変換装置１は、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）およびＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。また、１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。
【００２７】
＜処理＞
図２を用い、方式Ａ１のアルゴリズムを方式Ａ３のアルゴリズムに変換する処理を説明する。まず、方式Ａ１のアルゴリズムが入力部１１に入力され、記憶部１２に格納される。グラフ構築部１４１は、記憶部１２から方式Ａ１のアルゴリズムを読み込み、それに含まれる群演算の依存関係を表す依存関係グラフgraph（Ａ１）を構築して記憶部１２に格納する（ステップＳ１４１）。
【００２８】
線形制約設定部１４２は記憶部１２から依存関係グラフgraph（Ａ１）を抽出し、それに含まれるクリティカルノードに対する線形制約を設定して出力する。クリティカルノードには、群Ｇ１およびＧ２の両方を二重に割り当てることができないという制約の他、以下の制約がある。
（制約１）対をなすペアリングノードの一方に群Ｇ１を割り当てた場合、その他方には群Ｇ２が割り当てられなければならない。
（制約２）あるクリティカルノードの祖先ノードのクリティカルノードが存在する場合、それらのクリティカルノードに割り当てられる群は等しい。
ここで、依存関係グラフgraph（Ａ１）のクリティカルノードをＮ（ｊ）と表記し、Ｎ（ｊ）に群Ｇ１を割り当てる場合にｑ（ｊ）＝０∈Ｆ２とし、Ｎ（ｊ）に群Ｇ２を割り当てる場合にｑ（ｊ）＝１∈Ｆ２とする。ただし、ｎが２以上の整数であり、ｊ＝０，・・・，ｎ−１である。すると、対をなすペアリングノード（同一の対称型双線形写像の入力値の対に対応するノード）Ｎ（ｊ１）およびＮ（ｊ２）に対応する制約１は、関係式ｑ（ｊ１）＋ｑ（ｊ２）＝１∈Ｆ２で表現できる。また、Ｎ（ｊ３）とその祖先ノードであるＮ（ｊ４）とに対応する制約２は、関係式ｑ（ｊ３）＋ｑ（ｊ４）＝０∈Ｆ２で表現できる。このような関係式を一般化すると、ｑ（ｓ（ｉ，φ（０）））＋・・・＋ｑ（ｓ（ｉ，φ（Ｓ（ｉ）−１）））＝ｙ（ｉ，ｎ）∈Ｆ２となる。ただし、ｍが１以上の整数であり、ｉ＝０，・・・，ｍ−１である。Ｓ（ｉ）は２以上の整数（例えば、Ｓ（ｉ）＝２）であり、｛ｓ（ｉ，φ（０）），・・・，ｓ（ｉ，φ（Ｓ（ｉ）−１））｝⊆｛０，・・・，ｎ−１｝である。線形制約設定部１４２は、このような関係式を線形制約として出力する（ステップＳ１４２）。
【００２９】
線形制約ｑ（ｓ（ｉ，φ（０）））＋・・・＋ｑ（ｓ（ｉ，φ（Ｓ（ｉ）−１）））＝ｙ（ｉ，ｎ）は、行列生成部１４３に入力される。行列生成部１４３は、｛０，・・・，ｎ−１｝における｛ｓ（ｉ，φ（０）），・・・，ｓ（ｉ，φ（Ｓ（ｉ）−１））｝の補集合の要素ｒについてｙ（ｉ，ｒ）＝０とし、｛ｓ（ｉ，φ（０）），・・・，ｓ（ｉ，φ（Ｓ（ｉ）−１））｝の要素ｋについてｙ（ｉ，ｋ）＝１としたｙ（ｉ，０），・・・，ｙ（ｉ，ｎ−１），ｙ（ｉ，ｎ）をｉ行目の要素とする行列matrix（Ａ１）を表す情報を得て出力する。すなわち、ｑ（ｓ（ｉ，φ（０）））＋・・・＋ｑ（ｓ（ｉ，φ（Ｓ（ｉ）−１）））＝ｙ（ｉ，ｎ）を、ｙ（ｉ，ｊ）∈Ｆ２を用いてｙ（ｉ，０）・ｑ（０）＋・・・＋ｙ（ｉ，ｎ−１）・ｑ（ｎ−１）＝ｙ（ｉ，ｎ）と表記した際のｙ（ｉ，０），・・・，ｙ（ｉ，ｎ−１），ｙ（ｉ，ｎ）をｉ行目の要素とするｍ×ｎ行列をmatrix（Ａ１）とする。ｙ（ｉ，０），・・・，ｙ（ｉ，ｎ−１）およびｙ（ｉ，ｎ）は、多項式ｙ（ｉ，０）・ｑ（０）＋・・・＋ｙ（ｉ，ｎ−１）・ｑ（ｎ−１）＝ｙ（ｉ，ｎ）の係数および定数項に相当する。図３の例において、Ｘ６，Ｘ８，ｐ１［０］，ｐ１［１］，ｐ２［０］，ｐ２［１］をそれぞれＮ（０），Ｎ（１），Ｎ（２），Ｎ（３），Ｎ（４），Ｎ（５）とすると、matrix（Ａ１）は、以下のようになる（ステップＳ１４３）。
0011001
0000111            式（１）
1001000
1100000
【００３０】
行列matrix（Ａ１）を表す情報は行列変形部１４４に入力される。行列変形部１４４は、この情報を用い、行列matrix（Ａ１）を階段行列e-matrix（Ａ１）に変形する。階段行列e-matrix（Ａ１）は、ｚ（ｉ，０），・・・，ｚ（ｉ，ｎ−１），ｚ（ｉ，ｎ）∈Ｆ２をｉ行目の要素とするｍ×ｎ行列である。行列matrix（Ａ１）から階段行列e-matrix（Ａ１）への変形は、ガウスの消去法（掃き出し法）等の周知の方法を用いて行うことができる。例えば、式（１）に例示した行列matrix（Ａ１）の階段行列e-matrix（Ａ１）は以下のようになる（ステップＳ１４４）。
1001000
0101000            式（２）
0011001
0000111
【００３１】
階段行列e-matrix（Ａ１）は判定部１４５に入力される。判定部１４５は、e-matrix（Ａ１）がｚ（ι，０）＝・・・＝ｚ（ι，ｎ−１）＝０かつｚ（ι，ｎ）＝１となる要素を含む場合（ただし、ι∈｛０，・・・，ｍ−１｝）、ステップＳ１４２で設定された線形制約での割り当てが不可能であると判定し（ステップＳ１４５）、処理を終了する。そうでない場合、判定部１４５は割り当てが可能であると判定し（ステップＳ１４５）、処理をステップＳ１４７に進める。式（２）の例の場合、非零の最後の行は0000111であり、ｚ（ι，０）＝・・・＝ｚ（ι，ｎ−１）＝０かつｚ（ι，ｎ）＝１となる要素は存在しない。そのため、判定部１４５は割り当てが可能であると判定し、処理をステップＳ１４７に進める。
【００３２】
ステップＳ１４７では、まず階段行列e-matrix（Ａ１）が判定部１４７ｃに入力される。判定部１４７ｃは以下の判定を行う。
（１）階段行列e-matrix（Ａ１）がｚ（０，０）＝１である行およびｚ（１，１）＝０である行を含む場合にＮ（１）が独立ノードであると判定する。
（２）階段行列e-matrix（Ａ１）が１以上ｎ−２以下の整数ｔ（ω）についてｚ（ω，０）＝・・・＝ｚ（ω，ｔ（ω）−１）＝０かつｚ（ω，ｔ（ω））＝１である行およびｚ（ω＋１，ｔ（ω）＋１）＝０である行を含む場合にＮ（ｔ（ω）＋１）が独立ノードであると判定する。
（３）階段行列e-matrix（Ａ１）がｚ（ｍ−１，０）＝・・・＝ｚ（ｍ−１，ｔ（ｍ−１）−１）＝０かつｚ（ｍ−１，ｔ（ｍ−１））＝１である行を含む場合にノードＮ（ｔ（ｍ−１）＋１），・・・，Ｎ（ｎ−１）が独立ノードであると判定する。
（４）それ以外のＮ（ｊ）を従属ノードであると判定する。
【００３３】
Ｎ（ｊ）が独立ノードである場合、他のクリティカルノードへの群の割り当てと独立にＮ（ｊ）に群Ｇ１またはＧ２を割り当てることができる。Ｎ（ｊ）が従属ノードである場合、他のクリティカルノードへの群の割り当てに応じて群Ｇ１またはＧ２の割り当てが決まる。例えば、式（２）の例では階段行列e-matrix（Ａ１）の３行目が0011001であり、４行目が0000111である。そのため、ω＝２，ｔ（２）＝２について、ｚ（２，０）＝ｚ（２，１）＝０かつｚ（２，２）＝１であり、かつ、ｚ（３，３）＝０である。そのため、判定部１４７ｃはＮ（３）が独立ノードであると判定する。また、ｍ＝４，ｔ（３）＝４，ｎ＝６について、ｚ（３，０）＝・・・＝ｚ（３，３）＝０かつｚ（３，４）＝１である。そのため、判定部１４７ｃは、Ｎ（５）が独立ノードであると判定する。この例のＮ（３）はｐ１［１］、Ｎ（５）はｐ２［１］であり、これらは確かに独立ノードである（図３）。一方、Ｘ６はｐ１［１］の祖先ノードであり、Ｘ８の祖先ノードでもある。また、ｐ１［０］にはｐ１［１］とは異なる群が割り当てられる。そのため、Ｘ６，Ｘ８，ｐ１［０］はｐ１［１］の従属ノードである。また、ｐ２［０］にはｐ２［１］とは異なる群が割り当てられる。そのため、ｐ２［０］はｐ２［１］の従属ノードである（ステップＳ１４７ｃ）。
【００３４】
Ｎ（ｊ）およびＮ（ｊ）が独立ノードであるか否かの情報は探索部１４７ａに入力される。探索部１４７ａは、所定の評価関数を用い、独立ノードであると判定されたクリティカルノードＮ（ν）（ただし、ν∈｛０，・・・，ｎ−１｝）に群Ｇ１および群Ｇ２の何れを割り当てる。評価関数としては、独立ノードであるクリティカルノードＮ（ν）に対応する群要素のビット長の合計値を表す関数、すべてのクリティカルノードＮ（ｊ）に対応する群要素のビット長の合計値を表す関数、すべてのノードの群要素のビット長の合計値を表す関数などを例示できる。探索にはモンテカルロ法等の周知の手段を用いればよい。ただし、探索空間は独立ノードであると判定されたクリティカルノードＮ（ν）だけであるため、その探索に必要な演算量を抑えることができる。探索部１４７ａは、Ｎ（ν）への群の割り当て結果を出力する（ステップＳ１４７ａ）。
【００３５】
割当部１４７ｂは、Ｎ（ν）への群の割り当て結果およびＮ（ｊ）を入力とし、従属ノードであると判定されたクリティカルノードへ群Ｇ１および群Ｇ２の何れを割り当てる。この割り当ては、Ｎ（ν）への群の割り当て結果から一義的に定まる。例えば、割当部１４７ｂは、階段行列e-matrix（Ａ１）のｉが大きい行から順番に、ｚ（ｉ，ｊ）＝１となる従属ノードＮ（ｊ）に割り当てる群を決定していく。例えば、式（２）の例の場合、独立ノードＮ（３），Ｎ（５）には既に群Ｇ１またはＧ２が割り当てられている。まず、割当部１４７ｂは、Ｎ（５）に割り当てられている群と異なる群をＮ（４）に割り当てる。次に割当部１４７ｂは、Ｎ（３）に割り当てられている群と異なる群をＮ（２）に割り当てる。次に割当部１４７ｂは、Ｎ（３）に割り当てられている群と同じ群をＮ（１）に割り当てる。最後に割当部１４７ｂは、Ｎ（３）に割り当てられている群と同じ群をＮ（０）に割り当てる。これにより、すべてのクリティカルノードＮ（０），・・・，Ｎ（ｎ−１）に群Ｇ１またはＧ２がそれぞれ割り当てられた。その後、割当部１４７ｂは、依存関係グラフgraph（Ａ１）のノーマルノードに群Ｇ１およびＧ２の少なくとも一方を割り当てる。ノーマルノードへの群の割り当ては任意の方法を用いればよい。ただし、クリティカルノードの祖先ノードには、少なくともそのクリティカルノードに割り当てられた群が割り当てられるか、群Ｇ１およびＧ２の両方が二重に割り当てられる。割当部１４７ｂは、このように得た群Ｇ１が割り当てられたノードからなる依存関係グラフ、および群Ｇ２が割り当てられたノードからなる依存関係グラフからなる集合を、依存関係グラフgraph（Ａ３）（例えば、図４，図５）として出力する（ステップＳ１４７ｂ）。
【００３６】
＜具体例１＞
図６に、Bonehらの検証者ローカル失効付きグループ署名の依存関係グラフgraph（Ａ１）を示す（例えば、参考文献２「D. Boneh and H. Shacham, “Group signatures with verifier-local revocation,” In V. Atluri,B. Pfitzmann, 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.」等参照）。図６の例では、（ｐ１［０］，ｐ１［１］），・・・，（ｐ８［０］，ｐ８［１］）がそれぞれペアリングノードの対である。また、他のノードへのエッジが存在しないＲ１，Ｒ２，（ｇ１＊）１／γ＋ｘがボトムノードである。また、ｕ，ｖが２重化禁止ノードにあたる。したがって、このグラフにはｕ，ｖ，Ｒ１，Ｒ２，（ｇ１＊）１／γ＋ｘ，ｐ１［０］，ｐ１［１］，・・・，ｐ８［０］，ｐ８［１］の２１個のクリティカルノードＮ（０），・・・，Ｎ（２０）が存在する。
【００３７】
この場合、ステップＳ１４３では以下の２１×２２の行列matrix（Ａ１）が生成される。
0000011000000000000001
0000000110000000000001
0000000001100000000001
0000000000011000000001
0000000000000110000001
0000000000000001100001
0000000000000000011001
0000000000000000000111
1010000000000000000000
1001000000000000000000
0100100000000000000000
0100000100000000000000
0100000001000000000000
0100000000010000000000
0100000000000100000000
0100000000000001000000
1000000000000000100000
0100000000000000010000
1000000000000000001000
1000000000000000000100
0100000000000000000010
【００３８】
この場合、ステップＳ１４４で生成される階段行列e-matrix（Ａ１）は以下のようになる。
1010000000000000000000
0100100000000000000000
0011000000000000000000
0001000000000000100000
0000100100000000000000
0000011000000000000001
0000000110000000000001
0000000011000000000001
0000000001100000000001
0000000000110000000001
0000000000010100000000
0000000000001100000001
0000000000000101000000
0000000000000011000001
0000000000000001100001
0000000000000000110001
0000000000000000011001
0000000000000000001100
0000000000000000000111
0000000000000000000000
0000000000000000000000
【００３９】
この階段行列e-matrix（Ａ１）の非零の最後の行は0000000000000000000111である。そのため、ステップＳ１４５では割り当てが可能であると判定される。ステップＳ１４７のステップＳ１４７ｃでは、Ｎ（６）＝ｐ１［１］およびＮ（２０）＝ｐ８［１］が独立ノードであると判定され、その他のクリティカルノードが従属ノードであると判定される。ステップＳ１４７ａでは、ｐ１［１］およびｐ８［１］を探索空間としてこれらに群Ｇ１またはＧ２を割り当て、ステップＳ１４７ｂでは、ｐ１［１］およびｐ８［１］への割り当てに応じてその他のノードへの割り当てを行い、依存関係グラフgraph（Ａ３）を得て出力する。
【００４０】
＜具体例２＞
図７に、WatersのＩＤベース暗号の依存関係グラフgraph（Ａ１）を示す（例えば、参考文献３「B. Waters, “Efficient identity-based encryption without random oracles,” In R. Cramer, editor, Advances in Cryptology - EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings, volume 3494 of Lecture Notes in Computer Science, pages 114-127. Springer, 2005.」等参照）。図７の怜では、（ｐ１［０］，ｐ１［１］），・・・，（ｐ４［０］，ｐ４［１］）がそれぞれペアリングノードの対である。ボトムノードおよび２重化禁止ノードは特に設定していない。したがって、このグラフにはｐ１［０］，ｐ１［１］，・・・，ｐ４［０］，ｐ４［１］の８個のクリティカルノードＮ（０），・・・，Ｎ（７）が存在する。
【００４１】
この場合、ステップＳ１４３では４×９の行列matrix（Ａ１）が生成される。
110000001
001100001
000011001
000000111
【００４２】
この場合、ステップＳ１４４で生成される階段行列e-matrix（Ａ１）はmatrix（Ａ１）と同一となる。
【００４３】
この階段行列e-matrix（Ａ１）の非零の最後の行は000000111である。そのため、ステップＳ１４５では割り当てが可能であると判定される。ステップＳ１４７のステップＳ１４７ｃでは、Ｎ（１）＝ｐ１［１］，Ｎ（３）＝ｐ２［１］，Ｎ（５）＝ｐ３［１］，Ｎ（７）＝ｐ４［１］が独立ノードであると判定され、その他のクリティカルノードが従属ノードであると判定される。ステップＳ１４７ａでは、ｐ１［１］，ｐ２［１］，ｐ３［１］，ｐ４［１］を探索空間としてこれらに群Ｇ１またはＧ２を割り当て、ステップＳ１４７ｂでは、それらの割り当てに応じてその他のノードへの割り当てを行い、依存関係グラフgraph（Ａ３）を得て出力する。
【００４４】
［第２実施形態］
上述した具体例１（図６）では２個の独立ノードｐ１［１］およびｐ８［１］が存在し、それ以外のクリティカルノードが従属ノードであった。そのため、２２通りの割り当てが可能であった。また、具体例１（図６）では４個の独立ノードｐ１［１］，ｐ２［１］，ｐ３［１］，ｐ４［１］が存在し、それ以外のクリティカルノードが従属ノードであった。そのため、２４通りの割り当てが可能であった。一般に独立変数がΘ個あるとすると、値の割り当て方法は２Θ通り存在する。本形態では、こうした割り当て（分割）のうち、何らかの評価基準を満たした最適な割り当てを効率的に見つける方法を説明する。
【００４５】
例えば、図７の依存関係グラフgraph（Ａ１）を持つＩＤベース暗号の場合、ｇ，ｇ１，ｇ２，ｕ’，ｕεを公開鍵に持つ。ただし、ｕεは複数個（Ｌ個）の元を表現している。したがって、公開鍵のサイズが最も小さい割り当てを見つけたいなら、ｇ，ｇ１，ｇ２，ｕ’およびＬ個の元からなるｕεの合計サイズが最も小さい依存関係グラフgraph（Ａ３）を見つければよい。
【００４６】
ここで、依存関係グラフgraph（Ａ１）の各ノードＮ（ｊ）に重み係数ｗｊを定める。例えば、図７の依存関係グラフgraph（Ａ１）の例の場合、ｇ，ｇ１，ｇ２，ｕ’に対応するノードの重み係数を１とし、Ｌ個の元からなるｕεに対応するノードの重み係数をＬとし、その他のノード（ノーマルノード）の重み係数を０と設定する。あるノードＮ（ｊ）に群Ｇσ（ただし、σ∈｛１，２｝）が割り当てられ、ノードＮ（ｊ）が依存関係グラフgraph（Ａ３）の群Ｇσ側のグラフに含まれているという述語をＮ（ｊ）∈Ｇσと記述し、その否定の述語¬（Ｎ（ｊ）∈Ｇσ）を
【数１】
0006348082.tif 000002
と記述する。それらの述語が真であるときの値を１と表現し、述語が偽であるときその値を０とする。すなわち、（Ｎ（ｊ）∈Ｇσ）∈｛０，１｝である。
【００４７】
あるノードＮ（ｊ）がクリティカルノードであるなら、述語Ｎ（ｊ）∈Ｇ１と述語Ｎ（ｊ）∈Ｇ２とは排他的である。すなわち、
【数２】
0006348082.tif 000003
であり、（Ｎ（ｊ）∈Ｇ１）∧（Ｎ（ｊ）∈Ｇ２）＝０が成立する。
【００４８】
一方、ノードＮ（ｊ）がノーマルノードであるなら、（Ｎ（ｊ）∈Ｇ１）∧（Ｎ（ｊ）∈Ｇ２）＝０は必ずしも成立しない。また、｜Ｇσ｜（ただし、σ∈｛１，２｝）をＧσの元を表現するために必要なビット数と定義し、ｗｊ，σ＝ｗｊ・｜Ｇσ｜と定義する。依存関係グラフgraph（Ａ１）に含まれるノードＮ（ｊ）の集合をＶｇとする。これらの記法を用いて、各述語の値をそのまま整数と見なすと、上記の公開鍵のサイズを最小化したい問題等は、以下の評価関数の値を最小化する問題であるととらえることができる。
【数３】
0006348082.tif 000004
【００４９】
ノードＮ（ｊ）の子孫ノードであるクリティカルノードＤＮ（ρ（ｊ，０）），・・・，ＤＮ（ρ（ｊ，＃Ｄ（ｊ）−１））の集合をｓｅｔ（ｊ）＝｛ＤＮ（ρ（ｊ，０）），・・・，ＤＮ（ρ（ｊ，＃Ｄ（ｊ）−１））｝と定義し、集合Ｄ（ｊ）＝｛ρ（ｊ，０），・・・，ρ（ｊ，＃Ｄ（ｊ）−１）｝と定義する。ただし、＃Ｄ（ｊ）は集合Ｄ（ｊ）の要素数を表す正の整数である。ノードＮ（ｊ）に割り当てられる群Ｇσとその子孫ノードであるクリティカルノードＤＮ（ρ（ｊ，０）），・・・，ＤＮ（ρ（ｊ，＃Ｄ（ｊ）−１））に割り当てられる群Ｇσとは一致する。そのため、以下の関係が成り立つ。
【数４】
0006348082.tif 000005
【００５０】
クリティカルノードであるノードＮ（ｊ）に群Ｇ１を割り当てる場合にｄ（ｊ）＝０とし、クリティカルノードであるノードＮ（ｊ）に群Ｇ２を割り当てる場合にｄ（ｊ）＝１とする。すなわち、クリティカルノードであるノードＮ（ｊ）について以下のように定義する。
【数５】
0006348082.tif 000006
すると、式（４）は以下のように書くことができる。
【数６】
0006348082.tif 000007
ただし、¬ｄ（ρ（χ））はｄ（ρ（χ））の否定を表す。
【００５１】
ところで、｛０，１｝上の変数ｘ’，ｙ’について、述語ｘ’∧ｙ’や¬ｘ’を通常の四則演算を用いて以下のように記述できる。
ｘ’∧ｙ’＝ｘ’×ｙ’
¬ｘ’＝１−ｘ’
連言と否定が四則演算で定義出来るのでどのような命題変数の論理式も命題変数の多項式で定義出来る。また、｛０，１｝上の変数ｘ’および１以上の自然数ξについてｘ’ξ＝ｘ’であるから、上記の多項式はどの変数に関しても注目している変数以外の変数を定数と見なすと高々１次の多項式とすることができる。ここで、｛０，１｝上の変数ｘ１’，・・・，ｘΓ’（ただし、Γは正の整数）について、それらの積をｙ’＝ｘ１’・・・ｘΓ’とすると以下が成り立つ。
【数７】
0006348082.tif 000008
そのため、どのような命題変数の論理式も命題変数の線型不等式の組で記述できる。
【００５２】
ここで、ｑ１，ｊ∈｛０，１｝をｑ１，ｊ＝（Ｎ（ｊ）∈Ｇ１）と定義する。すなわち、ノードＮ（ｊ）に群Ｇ１を割り当てる場合にｑ１，ｊ＝１とし、ノードＮ（ｊ）に群Ｇ１を割り当てない場合にｑ１，ｊ＝０とする。すると、式（５）（６）より、ｑ１，ｊは以下の線形不当式の組で記述できる。
【数８】
0006348082.tif 000009
【００５３】
式（７）よりｙ”＝１−ｑ１，ｊであるから、以下が成り立つ。
【数９】
0006348082.tif 000010
【００５４】
同様に、ｑ２，ｊ∈｛０，１｝をｑ２，ｊ＝（Ｎ（ｊ）∈Ｇ２）と定義する。すなわち、ノードＮ（ｊ）に群Ｇ２を割り当てる場合にｑ２，ｊ＝１とし、ノードＮ（ｊ）に群Ｇ２を割り当てない場合にｑ２，ｊ＝０とする。すると、式（５）（６）より、ｑ２，ｊは以下の線形不当式の組で記述できる。
【数１０】
0006348082.tif 000011
【００５５】
式（９）よりｚ”＝１−ｑ２，ｊであり、Σρ（χ）∈ｄ（ｊ）１＝＃Ｄ（ｊ）であるため、以下が成り立つ。
【数１１】
0006348082.tif 000012
【００５６】
式（８）（１０）より、式（３）の値を最小化する問題は∀Ｎ（ｊ）∈Ｖｇに関して
（線形制約１）ｑ１，ｊ＋Σρ（χ）∈Ｄ（ｊ）ｄ（ρ（χ））≦＃Ｄ（ｊ），
（線形制約２）∀ρ（χ）∈Ｄ（ｊ）についてｑ１，ｊ＋ｄ（ρ（χ））≧１，
（線形制約３）ｑ２，ｊ−Σρ（χ）∈Ｄ（ｊ）ｄ（ρ（χ））≦０，
（線形制約４）∀ρ（χ）∈Ｄ（ｊ）についてｑ２，ｊ−ｄ（ρ（χ））≧０
なる線形制約の下、
【数１２】
0006348082.tif 000013
なる評価関数（すなわち、Σｊ∈｛０，・・・，ｎ−１｝（ｗｊ，１・ｑ１，ｊ＋ｗｊ，２・ｑ２，ｊ））を最小化する問題に帰着できる。
【００５７】
また、ペアリングの入力値の対に対応するクリティカルノードＮ（ｊ１）およびＮ（ｊ２）についてｄ（ｊ１）＋ｄ（ｊ２）＝１∈Ｆ２を満たし、クリティカルノードＮ（ｊ３）とその祖先ノードであるクリティカルノードＮ（ｊ４）とについてｄ（ｊ３）＋ｄ（ｊ４）＝０∈Ｆ２を満たす。線形制約が、ペアリングの入力値の対に対応するクリティカルノードＮ（ｊ１）およびＮ（ｊ２）についてｄ（ｊ１）＋ｄ（ｊ２）＝１∈Ｆ２であり（線形制約５）、クリティカルノードＮ（ｊ３）とその祖先ノードであるクリティカルノードＮ（ｊ４）とについてｄ（ｊ３）＋ｄ（ｊ４）＝０∈Ｆ２である（線形制約６）旨をさらに含んでもよい。
【００５８】
以上の評価関数（式１１）および線形制約を任意の０−１整数計画法アルゴリズムに入力することにより、ｑ１，０，・・・，ｑ１，ｎ−１，ｑ２，０，・・・，ｑ２，ｎ−１の厳密解または近似解を得る。
【００５９】
次に第１実施形態の方式に上述の探索方式を適用した例を説明する。なお、以下ではこれまでに説明した事項との相違点を中心に説明し、既に説明した事項については同じ参照番号を用いて説明を簡略化する。
【００６０】
＜構成＞
図１に例示するように、本形態の構造変換装置２は、入力部１１、記憶部１２、制御部１３、グラフ構築部１４１、線形制約設定部１４２、行列生成部１４３、行列変形部１４４、判定部１４５、および構造割当部２４７を有する。構造割当部２４７は、線形制約設定部２４７ａ、評価関数設定部２４７ｂ、探索部２４７ｃ、および割当部２４７ｄを有する。構造変換装置２は、例えば、前述のコンピュータに所定のプログラムが読み込まれることで構成される。
【００６１】
＜処理＞
図９を用いて、本形態の処理を説明する。まず、構造変換装置１に代えて構造変換装置２が前述のステップＳ１４１−Ｓ１４５の処理を実行する。ステップＳ１４５で割り当て可能であると判定された場合、以下のステップＳ２４７の処理が実行される。
【００６２】
ステップＳ２４７では、まず、線形制約設定部２４７ａに依存関係グラフgraph（Ａ１）が入力される。線形制約設定部２４７ａは、依存関係グラフgraph（Ａ１）を用い、前述の（線形制約１）−（線形制約６）を含む線形制約を設定して出力する（ステップＳ２４７ａ）。
【００６３】
評価関数設定部２４７ｂには、依存関係グラフgraph（Ａ１）が入力される。評価関数設定部２４７ｂは、依存関係グラフgraph（Ａ１）を用い、式（１１）の評価関数を設定して出力する（ステップＳ２４７ｂ）。
【００６４】
探索演算部２４７ａｃには、ステップＳ２４７ａで得られた線形制約、およびステップＳ２４７ｂで得られた評価関数が入力される。探索演算部２４７ａｃは、これらの線形制約および評価関数を任意の０−１整数計画法アルゴリズムに入力することにより、ｑ１，０，・・・，ｑ１，ｎ−１，ｑ２，０，・・・，ｑ２，ｎ−１の厳密解または近似解を得て出力する（ステップＳ２４７ｃ）。
【００６５】
割当部２４７ｄには、ｑ１，０，・・・，ｑ１，ｎ−１，ｑ２，０，・・・，ｑ２，ｎ−１の解が入力される。割当部２４７ｄは、これらに従って、依存関係グラフgraph（Ａ１）のすべてのノードＮ（ｊ）（ただし、ｊ＝０，・・・，ｎ−１）に群Ｇ１およびＧ２の少なくとも一方を割り当てる。割当部２４７ｄは、例えば、ｑ１，ｊ＝１またはｑ２，ｊ＝０の場合にノードＮ（ｊ）に群Ｇ１を割り当て、ｑ１，ｊ＝０またはｑ２，ｊ＝１の場合にノードＮ（ｊ）に群Ｇ２を割り当てる。割当部２４７ｄは、このように得た群Ｇ１が割り当てられたノードからなる依存関係グラフ、および群Ｇ２が割り当てられたノードからなる依存関係グラフからなる集合を、依存関係グラフgraph（Ａ３）として出力する（ステップＳ２４７ｄ）。
【００６６】
［その他の変形例］
本発明は上述の実施の形態に限定されるものではない。例えば、ステップＳ１４１の処理を実行した後、ステップＳ１４２−Ｓ１４５を実行することなく、ステップＳ２４７ａ−Ｓ２４７ｄの処理が実行されてもよい。また、本発明は、ペアリング型変換だけではなく、代数構造Ｇの演算からなる処理を代数的構造Ｇ１の演算からなる処理と代数的構造Ｇ２の演算からなる処理とに分解する方法一般に適用できる。例えば、第１実施形態で例示した線形制約ｑ（ｓ（ｉ，φ（０）））＋・・・＋ｑ（ｓ（ｉ，φ（Ｓ（ｉ）−１）））＝ｙ（ｉ，ｎ）に限定はなく、目的に応じ、どのようなＳ（ｉ）（例えば、Ｓ（ｉ）≧３）、｛ｓ（ｉ，φ（０）），・・・，ｓ（ｉ，φ（Ｓ（ｉ）−１））｝、ｙ（ｉ，ｎ）が設定されてもよい。また、第２実施形態で例示した評価関数はΣｊ∈｛０，・・・，ｎ−１｝（ｗｊ，１・ｑ１，ｊ＋ｗｊ，２・ｑ２，ｊ）に限定されず、目的に応じ、ｑ１，ｊおよびｑ２，ｊを含むその他の多項式を評価関数としてもよい。
【００６７】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００６８】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００６９】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７０】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００７１】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００７２】
１，２  構造変換装置
【図１】
0006348082.tif 000014
【図２】
0006348082.tif 000015
【図３】
0006348082.tif 000016
【図４】
0006348082.tif 000017
【図５】
0006348082.tif 000018
【図６】
0006348082.tif 000019
【図７】
0006348082.tif 000020
【図８】
0006348082.tif 000021
【図９】
0006348082.tif 000022