(57)【要約】【課題】効率的な計算方法による一括検証を実現することができるペアリング等式一括検証装置を提供する。【解決手段】kを検証式のインデックス、lを各検証式に存在するペアリングのインデックスとし、ペアリングの積である検証式の集合{Ek}を取得して、k番目の検証式におけるl番目のペアリングにおいて、一方の入力群要素に冪を集めるか他方の入力群要素に冪を集めるかの何れかを表す変数bklの論理式の線形和として、計算量を表す目的関数Bを生成する目的関数生成部と、目的関数Bを、線形制約付き線形目的関数に変換する線形目的関数変換部と、全ての線形制約および線形目的関数を任意の0-1整数計画アルゴリズムに入力して、厳密解と近似解の少なくとも何れか一方を取得する整数計画アルゴリズム実行部と、厳密解または近似解によって定まる変数bklの値に従って一括検証方式を構成する一括検証方式構成部を含む。【選択図】図１
2019041166.tif 000002
【特許請求の範囲】
【請求項１】
kを検証式のインデックス、lを各検証式に存在するペアリングのインデックスとし、ペアリングの積である検証式の集合{Ek}を取得して、k番目の検証式におけるl番目のペアリングにおいて、一方の入力群要素に冪を集めるか他方の入力群要素に冪を集めるかの何れかを表す変数bklの論理式の線形和として、計算量を表す目的関数Bを生成する目的関数生成部と、
前記目的関数Bを、線形制約付き線形目的関数に変換する線形目的関数変換部と、
全ての前記線形制約および前記線形目的関数を任意の0-1整数計画アルゴリズムに入力して、厳密解と近似解の少なくとも何れか一方を取得する整数計画アルゴリズム実行部と、
前記厳密解または前記近似解によって定まる前記変数bklの値に従って一括検証方式を構成する一括検証方式構成部と、
を含むペアリング等式一括検証装置。
【請求項２】
請求項１に記載のペアリング等式一括検証装置であって、
前記目的関数Bは、多重ペアリングに必要な演算コストに関する項と、多重冪乗に必要な演算コストに関する項を含む
ペアリング等式一括検証装置。
【請求項３】
ペアリング等式一括検証装置が実行するペアリング等式一括検証生成方法であって、
kを検証式のインデックス、lを各検証式に存在するペアリングのインデックスとし、ペアリングの積である検証式の集合{Ek}を取得して、k番目の検証式におけるl番目のペアリングにおいて、一方の入力群要素に冪を集めるか他方の入力群要素に冪を集めるかの何れかを表す変数bklの論理式の線形和として、計算量を表す目的関数Bを生成するステップと、
前記目的関数Bを、線形制約付き線形目的関数に変換するステップと、
全ての前記線形制約および前記線形目的関数を任意の0-1整数計画アルゴリズムに入力して、厳密解と近似解の少なくとも何れか一方を取得するステップと、
前記厳密解または前記近似解によって定まる前記変数bklの値に従って一括検証方式を構成するステップと、
を含むペアリング等式一括検証生成方法。
【請求項４】
請求項３に記載のペアリング等式一括検証生成方法であって、
前記目的関数Bは、多重ペアリングに必要な演算コストに関する項と、多重冪乗に必要な演算コストに関する項を含む
ペアリング等式一括検証生成方法。
【請求項５】
コンピュータを請求項１または２に記載のペアリング等式一括検証装置として機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は署名・認証・零知識証明あるいは一般の暗号認証技術の設計に関し、ペアリング等式一括検証装置、ペアリング等式一括検証生成方法、プログラムに関する。
【背景技術】
【０００２】
＜ペアリング＞
暗号認証技術の設計においてペアリングとは様々な方式に応用可能な暗号プリミティブ(暗号用原始関数)であって、形式的には概ね次の様な代数的構造を持つ符号を出力する確率的多項式時間アルゴリズムG（数式においてイタリック体で表現されるG、以下同様）であると定義される。
【０００３】
【数１】
2019041166.tif 000003
【０００４】
１）Lは、
【０００５】
【数２】
2019041166.tif 000004
【０００６】
なる有限可換環L（イタリック体）の符号。
【０００７】
G0,G1,GTはそれぞれ
【０００８】
【数３】
2019041166.tif 000005
【０００９】
なる同じL（イタリック体）-可群M（イタリック体）の符号。auxは補助出力。
【００１０】
２）次のλに関する確率的多項式時間アルゴリズムが利用可能。
−L,G0,G1,GT上の標本
−L上の環演算
−和：Gx×Gx→Gx,∀x∈{0,1,T}
−スカラー倍：L×Gx→Gx,∀x∈{0,1,T}
−非退化双準同型e:G0×G1→GT
【００１１】
一般に暗号認証技術の設計において安全性の証明を行う際には、暗号プリミティブに対して定義される何らかの暗号学的問題を考察する。λは安全変数と呼ばれ、暗号学的問題を解こうと試みる確率的多項式時間攻撃者A（イタリック体）に対して定義される利得が、如何なるA（イタリック体）に対してもλに関して無視可能となる事が暗号プリミティブが安全である事の差し当たっての定義である。暗号プリミティブの安全性を数学的に証明する事は多くの場合は困難であり、通常は経験的に成立すると予想される仮説が用いられる。そのような仮説を暗号学的仮定と呼ぶ。習慣によりLは離散対数などと呼ばれ、Gx,∀x∈{0,1,T}はそれぞれ群と呼ばれる。特にG0,G1を入力群(source group)、GTを標的群(target group)と呼ぶ。補助出力auxはG（イタリック体）の入力および乱数テープの適当な関数である。G（イタリック体）の具体的な出力(L,G0,G1,GT,aux)は広い意味で共通参照文字列あるいはパラメタなどと呼ばれるが、これをペアリングと呼ぶ事もある。Gxの加群としての和は、積あるいは乗算などと呼ばれg,h∈Gxに対してg×h,g・h,gh等と記述される。GxのL（イタリック体）-加群としてのスカラー倍は冪乗などと呼ばれa∈L,g∈Gxに対してgaと記述される。積と冪乗はまとめて群演算と呼ばれる。また非退化双準同型eもペアリングと呼ばれる。qをq>2Θ(λ)なる十分大きな素数から取り、LとしてZ/qZを、G0,G1としてそれぞれ適当な楕円曲線の有理点群の位数qの巡回部分群を、GTとして適当な有限体の乗法群の位数qの巡回部分群を取ると上記のようなG（イタリック体）を具体的に構成出来る事が知られている。ペアリングに関する暗号学的仮定はそのような構成のうち、幾つかのものが持つと予想される性質を抽象して定義され、そのような暗号学的仮定は少なくとも以下を含意する。
【００１２】
３）Lを離散対数とするG0,G1,GT上のCDH問題はそれぞれ計算困難。
従ってあるG（イタリック体）の具体的な構成について、有意な確率で条件３）を破る多項式時間アルゴリズムが見つかったならばG（イタリック体）は安全なペアリングではないという事が出来る。あるG（イタリック体）の具体的な構成が条件１）、２）を満たし暗号学的仮定が成立すると信じられるなら、そのようなG（イタリック体）を安全なペアリングの候補と呼ぶ。歴史的経緯と習慣により、安全なペアリングの候補の事を単にペアリングと呼ぶ事が多い。また、ペアリングと言った時それがeを指すのか、(L,G0,G1,GT,aux)を指すのか、G（イタリック体）を指すのか、あるいは特にそれらを区別していないのかは文脈によって判断する必要がある。Galbraithらは、暗号プロトコルに用いられるペアリングを大雑把に以下の３つの型に分類した（非特許文献１）。
Type1:G0,G1間で双方向に多項式時間同型が存在する。
Type2:G1→G0なる一方向同型が存在する。
Type3:G0,G1間で双方向に多項式時間同型が存在しない。
【００１３】
一般にType1を対称ペアリングと呼び、Type2,Type3を非対称ペアリングと呼ぶ。対称ペアリングにおいてはG0とG1は、いつでも双方向に多項式時間で行き来出来る為、暗号方式の設計においては両者は特に区別されず、単にGと記述される。
【００１４】
＜一括検証＞
ペアリングを用いた、署名やゼロ知識証明などの一般化された暗号認証方式が、方式を構成するアルゴリズム内に
【００１５】
【数４】
2019041166.tif 000006
【００１６】
の型の式の検証を含む時、一般にこれを
【００１７】
【数５】
2019041166.tif 000007
【００１８】
の検証と見做すことが出来る。
【００１９】
【数６】
2019041166.tif 000008
【００２０】
と定めれば上記検証式は
【００２１】
【数７】
2019041166.tif 000009
【００２２】
と記述出来る。従って以下ではこの型の検証式を考える。今、方式を構成するペアリングの入力群変数の集合が
【００２３】
【数８】
2019041166.tif 000010
【００２４】
であるとき、検証アルゴリズム内に
【００２５】
【数９】
2019041166.tif 000011
【００２６】
(但しαl≠0,βl≠0)の型の検証式が多数含まれる場合を考える。即ち整数k∈{1,...,kmax}について
【００２７】
【数１０】
2019041166.tif 000012
【００２８】
とし
【００２９】
【数１１】
2019041166.tif 000013
【００３０】
なる命題の検証が検証アルゴリズムに含まれるとする。この命題の真理値について
【００３１】
【数１２】
2019041166.tif 000014
【００３２】
であるが、逆は必ずしも成立しない。しかし暗号学的に安全なペアリングを用いる場合R（イタリック体）を離散対数Lの十分大きな部分集合とすれば高い確率で逆が成り立つとして良い。一般にEk=1なる命題をk∈{1,...,kmax}について一つずつ検証するよりも
【００３３】
【数１３】
2019041166.tif 000015
【００３４】
を一括で検証する方が効率が良い。これを一括検証と呼ぶ。
【先行技術文献】
【非特許文献】
【００３５】
【非特許文献１】Steven D. Galbraith, Kenneth G. Paterson, and Nigel P. Smart. Pairings for cryptographers. Discrete Applied Mathematics, 156(16):3113-3121, 2008.
【非特許文献２】Joseph A. Akinyele, Matthew Green, Susan Hohenberger, and Matthew W. Pagano. Machine-Generated Algorithms, Proofs and Software for the Batch Verication of Digital Signature Schemes.In CCS'12 Proceedings of the 2012 ACM conference on Computer and communications security, Pages474-487.
【非特許文献３】Der-San Chen, Robert G. Batson, and Yu Dang. Applied Integer Programming: Modeling and Solution. ISBN: 978-0-470-37306-4, pp.54-58, December 2009.
【非特許文献４】久保幹雄、田村明久、松井知己［編集］、「応用数理計画ハンドブック」、株式会社朝倉書店、2012年5月、p.243-244,2002.
【発明の概要】
【発明が解決しようとする課題】
【００３６】
一般にe(X,Y)r=e(Xr,Y)=e(X,Yr)であり、e(X,Y)rの計算方法は一通りではない。さらに
【００３７】
【数１４】
2019041166.tif 000016
【００３８】
あるいは
【００３９】
【数１５】
2019041166.tif 000017
【００４０】
であり、引数のどちらか一方が等しいペアリングはまとめる事が可能である。従って一括検証式
【００４１】
【数１６】
2019041166.tif 000018
【００４２】
には使用される乱数rkをどう配置し、ペアリングをどうまとめるかにより沢山の計算方法が存在し、一般にその数は少なくともペアリングの数に対して指数関数的に増大する。そして計算方法により、まとめる事が可能なペアリング数やペアリングへ入力される式の型が変化するので計算の効率が大きく変わる。指数的多数の計算方法の候補から最も良い、あるいはそれに匹敵するくらい良い計算方法を単純に探索する事は、一括検証の規模が大きくなると事実上実行不可能となる。
【００４３】
例えば、非特許文献２には、経験を基に様々な計算手法を探索的に適用することで一括検証を効率よく計算できる方法が開示されているが、最適、もしくはそれに匹敵するくらい良い計算方法を統一的な手法で求めることができないという課題がある。
【００４４】
従って、k∈{1,...,kmax}に関して予め決められたEkの型が与えられたとき、この指数的多数の計算方法の候補から最も良い、あるいはそれに匹敵するくらい良い計算方法を見つけ出す事が重要な課題となる。
【００４５】
そこで本発明では、効率的な計算方法による一括検証を実現することができるペアリング等式一括検証装置を提供することを目的とする。
【課題を解決するための手段】
【００４６】
本発明のペアリング等式一括検証装置は、目的関数生成部と、線形目的関数変換部と、整数計画アルゴリズム実行部と、一括検証方式構成部を含む構成である。
【００４７】
目的関数生成部は、kを検証式のインデックス、lを各検証式に存在するペアリングのインデックスとし、ペアリングの積である検証式の集合{Ek}を取得して、k番目の検証式におけるl番目のペアリングにおいて、一方の入力群要素に冪を集めるか他方の入力群要素に冪を集めるかの何れかを表す変数bklの論理式の線形和として、計算量を表す目的関数Bを生成する。
【００４８】
線形目的関数変換部は、目的関数Bを、線形制約付き線形目的関数に変換する。
【００４９】
整数計画アルゴリズム実行部は、全ての線形制約および線形目的関数を任意の0-1整数計画アルゴリズムに入力して、厳密解と近似解の少なくとも何れか一方を取得する。
【００５０】
一括検証方式構成部は、厳密解または近似解によって定まる変数bklの値に従って一括検証方式を構成する。
【発明の効果】
【００５１】
本発明のペアリング等式一括検証装置によれば、効率的な計算方法による一括検証を実現することができる。
【図面の簡単な説明】
【００５２】
【図１】実施形態のペアリング等式一括検証装置の構成を示すブロック図。
【図２】実施形態のペアリング等式一括検証装置の動作を示すフローチャート。
【発明を実施するための形態】
【００５３】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００５４】
≪準備：{0,1}変数bkl、目的関数B≫
今、ペアリングe(Xα,Yβ)rに対して、便宜的にb∈{0,1}なる変数を考え、b=0ならば冪を全てYに集め、b=1ならば冪を全てXに集めるとする。従ってε=αβ、
【００５５】
【数１７】
2019041166.tif 000019
【００５６】
とすれば、
【００５７】
【数１８】
2019041166.tif 000020
【００５８】
と展開出来る。今、非対称ペアリングの場合を想定して一括検証
【００５９】
【数１９】
2019041166.tif 000021
【００６０】
の全てのペアリングに上記の展開を適用すると、
【００６１】
【数２０】
2019041166.tif 000022
【００６２】
を得る。G0変数Xiの添え字i∈{1,...,imax}の関数Iを
【００６３】
【数２１】
2019041166.tif 000023
【００６４】
と定義すると、上記下線部について有限個のペアリングの積の演算順序を交換し、同じ基底Xiを持つペアリングをまとめる事により、
【００６５】
【数２２】
2019041166.tif 000024
【００６６】
として良い。命題Pの関数δを
【００６７】
【数２３】
2019041166.tif 000025
【００６８】
と定義すると、上記下線部について有限個の冪乗の積の演算順序を交換する事により、
【００６９】
【数２４】
2019041166.tif 000026
【００７０】
として良い。上記下線部について
【００７１】
【数２５】
2019041166.tif 000027
【００７２】
と定義すれば、
【００７３】
【数２６】
2019041166.tif 000028
【００７４】
と出来る。同様にG1変数Yjの添え字j∈{1,...,jmax}の関数Jを
【００７５】
【数２７】
2019041166.tif 000029
【００７６】
と定義し、
【００７７】
【数２８】
2019041166.tif 000030
【００７８】
と定義し、上記下線部を変形すると
【００７９】
【数２９】
2019041166.tif 000031
【００８０】
と出来る。大雑把に見積もると、この一括検証の計算コストは最大imax+jmax個のペアリングの積で構成される多重ペアリングのコストと各ペアリングの引数を構成する多重冪乗のコストの総和により決定される。このとき、
【００８１】
【数３０】
2019041166.tif 000032
【００８２】
あるいは
【００８３】
【数３１】
2019041166.tif 000033
【００８４】
なるペアリングは値が1となる事が予め分かっているので、一般には実際に多重ペアリングを構成する有効なペアリングの個数nはimax+jmaxよりも小さい。Lをペアリングを計算する際のMiller loopのコストFをペアリングを計算する際の最終冪のコストとすると、多重ペアリングに必要な演算コストは概ね
F+n・L
と見積もることが出来る。またG1多重冪乗
【００８５】
【数３２】
2019041166.tif 000034
【００８６】
に必要な演算コストは、s1,iを全指数の最大bit数、m1,iを全指数の合計bit数とし、S1をG1自乗のコストM1をG1乗算のコストとすると、ある定数
【００８７】
【数３３】
2019041166.tif 000035
【００８８】
が存在して、
s1,i・S1+c1・m1,i・M1
と見積もることが出来る。同様にG0多重冪乗
【００８９】
【数３４】
2019041166.tif 000036
【００９０】
に必要な演算コストはs0,jを全指数の最大bit数、m0,jを全指数の合計bit数とし、S0をG0自乗のコスト、M0をG0乗算のコストとすると、ある定数
【００９１】
【数３５】
2019041166.tif 000037
【００９２】
が存在して
s0,j・S0+c0・m0,j・M0
と見積もることが出来る。
【００９３】
【数３６】
2019041166.tif 000038
【００９４】
と定義すれば、一括検証の全コストBを
【００９５】
【数３７】
2019041166.tif 000039
【００９６】
とする事が出来る。対称ペアリングの場合も似たような評価が出来る(後述)。
【００９７】
≪準備：線形制約付き線形目的関数への変換（後述するＳ１２）≫
ところで{0,1}上の変数x,x1,x2,yについて、
【００９８】
【数３８】
2019041166.tif 000040
【００９９】
である。即ち{0,1}変数の任意の連言と否定はある線型制約の元で新しい{0,1}変数に置き換え可能で、従ってどのような命題変数の論理式もこの置き換えを繰り返す事によって{0,1}変数の線型制約付き線型式に変換出来る事が良く知られている（非特許文献３）。
【０１００】
従って、もしBを{0,1}変数bklの論理式の線形和で見積もる事が出来るなら、上記の変換を用いてBを{0,1}変数の線型制約付き線型式に変換出来、Bの最適値あるいは近似最適値を与えるbklの割り当ては任意の整数線形計画アルゴリズムを用いて求めることが出来る。整数線形計画問題を解くアルゴリズムは例えば、動的計画法、分岐限定法、切除平面法、分岐切除法などの厳密解法、ランダム丸め法、ランダム抽出法などの近似解法、貪欲解法、局所探索法、タブーサーチ、シミュレーテッドアニーリング、遺伝的アルゴリズムなどのヒューリスティック解法などが良く知られている（非特許文献４）。
【０１０１】
≪準備：目的関数Bの生成−非対称ペアリングの場合（後述するＳ１１）≫
rkを確率変数として実際に多重ペアリングを構成する有効なペアリングの個数nは
【０１０２】
【数３９】
2019041166.tif 000041
【０１０３】
である。G1多重冪乗
【０１０４】
【数４０】
2019041166.tif 000042
【０１０５】
の全指数の最大bit数s1,iは、
【０１０６】
【数４１】
2019041166.tif 000043
【０１０７】
と見積もることが出来る。但し
【０１０８】
【数４２】
2019041166.tif 000044
【０１０９】
とする。εklおよびrkがどのような集合から選択されるかは予め分かっているため、|εklrk|の値は概算する事が出来、従って整列する事が出来るとする。例えばL=Z/qZのとき、一般に|εkl|は非常に小さい場合(例えば|εkl|〜1の時)あるいは非常に大きい場合(例えば|εkl|〜|q|の時)を想定することが可能で、|rk|は|rk|〜|q|/2あるいは、特定のkについては|rk|〜1等と想定することが可能である。このとき、|εklrk|は表１のように見積もられる。
【０１１０】
【表１】
2019041166.tif 000045
【０１１１】
同様にG0多重冪乗
【０１１２】
【数４３】
2019041166.tif 000046
【０１１３】
の全指数の最大bit数s0,jは、
【０１１４】
【数４４】
2019041166.tif 000047
【０１１５】
と見積もることが出来る。但し
【０１１６】
【数４５】
2019041166.tif 000048
【０１１７】
とする。G1多重冪乗
【０１１８】
【数４６】
2019041166.tif 000049
【０１１９】
の全指数の合計bit数m1,iは、
【０１２０】
【数４７】
2019041166.tif 000050
【０１２１】
と見積もることが出来る。但し
【０１２２】
【数４８】
2019041166.tif 000051
【０１２３】
とする。同様にG0多重冪乗
【０１２４】
【数４９】
2019041166.tif 000052
【０１２５】
の全指数の合計bit数m0,jは、
【０１２６】
【数５０】
2019041166.tif 000053
【０１２７】
と見積もることが出来る。但し
【０１２８】
【数５１】
2019041166.tif 000054
【０１２９】
とする。従って、
【０１３０】
【数５２】
2019041166.tif 000055
【０１３１】
および一括検証の全コスト
【０１３２】
【数５３】
2019041166.tif 000056
【０１３３】
を考えると、Bを{0,1}変数bklの論理式の線形和で記述できた。
【０１３４】
≪準備：目的関数Bの生成−対称ペアリングの場合（後述するＳ１１）≫
対称ペアリングにおいてはG0=G1=Gと考えて良い。従って方式を構成するペアリングの入力群変数の集合
【０１３５】
【数５４】
2019041166.tif 000057
【０１３６】
および
【０１３７】
【数５５】
2019041166.tif 000058
【０１３８】
を同一視しimax=jmaxとし全てのi∈{1,...,imax}についてXi=Yiと定義し直す。またI(i)とJ(i)のdisjoint unionU(i)を
U(i)=I(i)└┘J(i)={(k,l,t)|(k,l)∈I(i)∧t=1∨(k,l)∈J(i)∧t=0}
と定義し、
【０１３９】
【数５６】
2019041166.tif 000059
【０１４０】
と定義し
【０１４１】
【数５７】
2019041166.tif 000060
【０１４２】
と定義する。
【０１４３】
【数５８】
2019041166.tif 000061
【０１４４】
である。但し、
【０１４５】
【数５９】
2019041166.tif 000062
【０１４６】
とする。このとき有効なペアリングの数nは
【０１４７】
【数６０】
2019041166.tif 000063
【０１４８】
G多重冪乗
【０１４９】
【数６１】
2019041166.tif 000064
【０１５０】
の全指数の最大bit数siは、
【０１５１】
【数６２】
2019041166.tif 000065
【０１５２】
と見積もる事ができる。但し
【０１５３】
【数６３】
2019041166.tif 000066
【０１５４】
とする。また、G多重冪乗
【０１５５】
【数６４】
2019041166.tif 000067
【０１５６】
の全指数の合計bit数miは、
【０１５７】
【数６５】
2019041166.tif 000068
【０１５８】
と見積もることが出来る。但し
【０１５９】
【数６６】
2019041166.tif 000069
【０１６０】
とする。SをG自乗のコスト、MをG乗算のコストとすると、ある定数
【０１６１】
【数６７】
2019041166.tif 000070
【０１６２】
が存在してG多重冪乗
【０１６３】
【数６８】
2019041166.tif 000071
【０１６４】
の演算コストを
si・S+c・mi・M
と見積もることが出来る。従って、
【０１６５】
【数６９】
2019041166.tif 000072
【０１６６】
とすると一括検証の全コスト
B=F+n・L+s・S+c・m・M
を考えると、Bを{0,1}変数bklの論理式の線形和で記述できた。
【０１６７】
＜ペアリング等式一括検証装置＞
以下、図１、図２を参照して実施形態に係るペアリング等式一括検証装置の構成、および動作について説明する。図１に示すように、本実施形態のペアリング等式一括検証装置１は、目的関数生成部１１と、目的関数記憶部１１ａと、線形目的関数変換部１２と、線形目的関数記憶部１２ａと、整数計画アルゴリズム実行部１３と、厳密解／近似解記憶部１３ａと、一括検証方式構成部１４を含む構成である。
【０１６８】
図２に示すように、目的関数生成部１１は、kを検証式のインデックス、lを各検証式に存在するペアリングのインデックスとし、ペアリングの積である検証式の集合{Ek}を取得して、k番目の検証式におけるl番目のペアリングにおいて、一方の入力群要素に冪を集めるか他方の入力群要素に冪を集めるかの何れかを表す{0,1}変数bklの論理式の線形和として、計算量を表す目的関数Bを生成する（Ｓ１１）。目的関数生成部１１は生成した目的関数Bを目的関数記憶部１１ａに記憶する。
【０１６９】
線形目的関数変換部１２は、目的関数Bを、線形制約付き線形目的関数に変換する（Ｓ１２）。線形目的関数変換部１２は、変換した線形制約付き線形目的関数を線形目的関数記憶部１２ａに記憶する。
【０１７０】
整数計画アルゴリズム実行部１３は、全ての線形制約および線形目的関数を任意の0-1整数計画アルゴリズムに入力して、厳密解と近似解の少なくとも何れか一方を取得する（Ｓ１３）。整数計画アルゴリズム実行部１３は、取得した厳密解、または近似解を厳密解／近似解記憶部１３ａに記憶する。
【０１７１】
一括検証方式構成部１４は、厳密解または近似解によって定まる変数bklの値に従って一括検証方式を構成する（Ｓ１４）。具体的には、bklの値に従って一括検証方式
【０１７２】
【数７０】
2019041166.tif 000073
【０１７３】
（非対称ペアリングの場合）、あるいは
【０１７４】
【数７１】
2019041166.tif 000074
【０１７５】
（対称ペアリングの場合）等を構成する。一括検証方式構成部１４は、構成した一括検証方式を出力する。
【０１７６】
従来は、ペアリング間で冪の集め方を異ならせるといった発想はあまり一般的でなかった。従来は、同じ種類のデータを扱うことが多かったため、例えばあるペアリングにおいてXに冪を集めることとした場合、他のペアリングにおいても同様にXに冪を集めるのが通常であったためである。このため、従来は各ペアリングにおける冪の集め方を記述した変数である{0,1}変数bklといった着想はなかった。また一括検証方式において任意の0-1整数計画アルゴリズムを利用するという発想が一般的でなかったため、計算量を表す目的関数Bを{0,1}変数bklの論理式の線形和として表したうえで、これを0-1整数計画アルゴリズムにおいて取扱い可能なように、線形制約付き線形目的関数に変換するという発想がなかった。本実施形態のペアリング等式一括検証装置１は、上述の新しい着想を採用したため、効率的な計算方法による一括検証を実現することができた。
【０１７７】
＜補記＞
本発明の装置は、例えば単一のハードウェアエンティティとして、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit、キャッシュメモリやレジスタなどを備えていてもよい）、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けることとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【０１７８】
ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくこととしてもよい）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。
【０１７９】
ハードウェアエンティティでは、外部記憶装置（あるいはＲＯＭなど）に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（上記、…部、…手段などと表した各構成要件）を実現する。
【０１８０】
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【０１８１】
既述のように、上記実施形態において説明したハードウェアエンティティ（本発明の装置）における処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【０１８２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【０１８３】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１８４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１８５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【０１８６】
なお、明細書、特許請求の範囲に記載された各ステップは各種の情報を生成する方法の各ステップに該当する。ここでいう各種の情報は特許法第二条第四項に規定するプログラム等（プログラム…その他電子計算機による処理の用に供する情報であってプログラムに準ずるもの）に該当するため、ここでいう各種の情報は、特許法第二条第三項第一号に規定する物に該当する。従って、明細書、特許請求の範囲に記載された各種の情報を生成する方法はすなわち、特許法第二条第三項第三号に規定する物を生産する方法に該当することはいうまでもない。
【図１】
2019041166.tif 000075
【図２】
2019041166.tif 000076