(57)【要約】  G,Hを巡回群、Mを2以上の整数、i=1,…,M、fを群Hの元xiを群Gへ写す準同型関数、Ri及びR0を群Gに値を持つ確率変数、riを確率変数Riの実現値、r0を確率変数R0の実現値、aiを0以上の整数の乱数として、乱数生成部１１が、乱数a1,a2,…,aMを生成する。標本器２１が、f(x1)r1,f(x2)r2,…,f(xM)rMを計算可能であり、それらの計算結果をそれぞれz1,z2,…,zMとする。べき乗計算部１２が、(z1)a1,(z2)a2,…,(zM)aMを計算する。拡張乱数化可能標本器２２が、f(x1a1×x2a2×…×xMaM)r0を計算可能であり、その計算結果をz0とする。判定部１６が、(z1)a1×(z2)a2×…×(zM)aM=z0であるか判定する。
2012121152.tif 000002
【特許請求の範囲】
【請求項１】
G,Hを巡回群、Mを2以上の整数、i=1,…,M、fを群Hの元xiを群Gへ写す準同型関数、Ri及びR0を群Gに値を持つ確率変数、riを確率変数Riの実現値、r0を確率変数R0の実現値、aiを0以上の整数の乱数として、
乱数a1,a2,…,aMを生成する乱数生成部と、
f(x1)r1,f(x2)r2,…,f(xM)rMを計算可能であり、それらの計算結果をそれぞれz1,z2,…,zMとする標本器と、
(z1)a1,(z2)a2,…,(zM)aMを計算するべき乗計算部と、
f(x1a1×x2a2×…×xMaM)r0を計算可能であり、その計算結果をz0とする拡張乱数化可能標本器と、
(z1)a1×(z2)a2×…×(zM)aM=z0であるか判定する判定部と、
を含む代理計算システム。
【請求項２】
請求項１の代理計算システムにおいて、
所定の確率以上の確率で関数fと同じ値を出力する確率的関数をFとし、群Hの生成元をhとし、0以上の整数の乱数をsとして、
上記拡張乱数化可能標本器は、F(x1a1×x2a2×…×xMaMhs)f(h)-sの値を計算して、その計算結果をz0とする、
代理計算システム。
【請求項３】
G,Hを巡回群、Mを2以上の整数、i=1,…,M、fを群Hの元xiを群Gへ写す準同型関数、Ri及びR0を群Gに値を持つ確率変数、riを確率変数Riの実現値、r0を確率変数R0の実現値、aiを0以上の整数の乱数として、
乱数生成部が、乱数a1,a2,…,aMを生成する乱数生成ステップと、
標本器が、f(x1)r1,f(x2)r2,…,f(xM)rMを計算可能であり、それらの計算結果をそれぞれz1,z2,…,zMとする標本抽出ステップと、
べき乗計算部が、(z1)a1,(z2)a2,…,(zM)aMを計算するべき乗計算ステップと、
拡張乱数化可能標本器が、f(x1a1×x2a2×…×xMaM)r0を計算可能であり、その計算結果をz0とする拡張乱数化可能標本抽出ステップと、
判定部が、(z1)a1×(z2)a2×…×(zM)aM=z0であるか判定する判定ステップと、
を含む代理計算方法。
【請求項４】
請求項３の代理計算方法において、
所定の確率以上の確率で関数fと同じ値を出力する確率的関数をFとし、群Hの生成元をhとし、0以上の整数の乱数をsとして、
上記拡張乱数化可能標本ステップは、F(x1a1×x2a2×…×xMaMhs)f(h)-sの値を計算して、その計算結果をz0とする、
代理計算方法。
【請求項５】
G,Hを巡回群、Mを2以上の整数、i=1,…,M、fを群Hの元xiを群Gへ写す準同型関数、Ri及びR0を群Gに値を持つ確率変数、riを確率変数Riの実現値、r0を確率変数R0の実現値、aiを0以上の整数の乱数として、
乱数a1,a2,…,aMを生成する乱数生成部と、
f(x1)r1,f(x2)r2,…,f(xM)rMを計算可能な標本器による計算結果z1,z2,…,zMを用いて、(z1)a1,(z2)a2,…,(zM)aMを計算するべき乗計算部と、
上記べき乗計算部の計算結果、及び、f(x1a1×x2a2×…×xMaM)r0を計算可能な拡張乱数化可能標本器による計算結果z0を用いて、(z1)a1×(z2)a2×…×(zM)aM=z0であるか判定する判定部と、
を含む依頼装置。
【請求項６】
請求項５の依頼装置において、
所定の確率以上の確率で関数ｆと同じ値を出力する確率的関数をFとし、群Hの生成元をhとし、0以上の整数の乱数をsとして、
上記拡張乱数化可能標本器は、F(x1a1×x2a2×…×xMaMhs)f(h)-sの値を計算して、その計算結果をz0とする、
依頼装置。
【請求項７】
請求項５又は６の依頼装置の各部としてコンピュータを機能させるためのプログラム。
【請求項８】
請求項５又は６の依頼装置の各部としてコンピュータを機能させるためのプログラムを格納したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、コンピュータによる計算技術に関する。特に、他の計算機に行わせた計算結果を用いて計算を行う技術に関する。
【背景技術】
【０００２】
以下に説明する乱数化可能標本器及び標本器を用いて、ある入力ｘに対するf(x)を計算する技術が発明者により提案されている（例えば、非特許文献１参照。）。【０００３】
Rを群Gに値を持つ確率変数とする。w∈Gについて、0以上の整数aが与えられるたびに確率変数Rに従った標本r’に対応するwar’を返すものを、wについて誤差Rを持つ乱数化可能標本器(randomizable sampler)と呼ぶ。なお、乱数化可能標本器において、確率変数Rの分布と整数aとは無関係である。【０００４】
また、w∈Gについて、要求を受けるたびに確率変数Rに従った標本r’に対応するwr’を返すものを、wについて誤差Rを持つ標本器(sampler)と呼ぶ。【０００５】
乱数化可能標本器及び標本器は、ブラックボックスと呼ばれる関数を用いて、それぞれwar’及びwr’を計算する。【０００６】
r1及びr2を確率変数Rの実現値として、f(x)について誤差Rを持つ乱数化可能標本器の出力f(x)ar1と、f(x)について誤差Rを持つ標本器の出力f(x)r2のa乗(f(x)r2)aとが等しい場合には、高い確率でr1及びr2が群Gの単位元egである。したがって、この場合、f(x)r2=f(x)eg=f(x)であるため、標本器の出力f(x)r2が求めようとしていたf(x)となる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Go Yamamoto, Tetsutaro Kobayashi, ”Self-Correctors for Cryptographic Modules”, The 2011 Symposium on Cryptography and Information Security, 2F1-1, 2001.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
背景技術に記載した技術では、あるxに対するf(x)の値を計算するためには、乱数化可能標本器及び標本器にブラックボックス関数を用いて少なくとも2回計算させる必要がある。このため、Mを2以上の整数として、M個の入力x1,x2,…,xMに対するf(x1),f(x2),…,f(xM)をそれぞれ計算するためには、乱数化可能標本器及び標本器にブラックボックスを用いて少なくとも2M回計算させる必要がある。M個の入力x1,x2,…,xMのそれぞれに対して乱数化可能標本器及び標本器にブラックボックスを用いて少なくとも2回計算させる必要があるためである。【０００９】
この発明は、ブラックボックスを用いて計算する回数を2M回よりも少なくしつつ、M個の入力x1,x2,…,xMに対するf(x1),f(x2),…,f(xM)をそれぞれ計算する技術を提供することを目的とする。
【課題を解決するための手段】
【００１０】
この発明の一態様によれば、G,Hを巡回群、Mを2以上の整数、i=1,…,M、fを群Hの元xiを群Gへ写す準同型関数、Ri及びR0を群Gに値を持つ確率変数、riを確率変数Riの実現値、r0を確率変数R0の実現値、aiを0以上の整数の乱数として、乱数a1,a2,…,aMを生成する。f(x1)r1,f(x2)r2,…,f(xM)rMを計算可能であり、それらの計算結果をそれぞれz1,z2,…,zMとする。(z1)a1,(z2)a2,…,(zM)aMを計算する。f(x1a1×x2a2×…×xMaM)r0を計算可能であり、その計算結果をz0とする。(z1)a1×(z2)a2×…×(zM)aM=z0であるか判定する。
【発明の効果】
【００１１】
ブラックボックスを用いて計算する回数を最小でM+1回にすることができる。
【図面の簡単な説明】
【００１２】
【図１】実施形態の代理計算システムの構成を説明するためのブロック図。
【図２】実施形態の依頼装置及び計算装置の構成を説明するためのブロック図。
【図３】実施形態の代理計算システムの処理を説明するためのフローチャート。
【発明を実施するための形態】
【００１３】
以下、図面を参照してこの発明の一実施形態を説明する。
【００１４】
G,Hを巡回群、Mを2以上の整数、i=1,…,M、として、fを群Hの元xiを群Gへ写す準同型関数、Ri及びR0を群Gに値を持つ確率変数、riを確率変数Riの実現値、r0を確率変数R0の実現値、aiを0以上の整数の乱数とする。
【００１５】
依頼装置１の乱数生成部１１は、0以上の整数の乱数a1,a2,…,aMを生成する（ステップＳ１）。生成された乱数a1,a2,…,aMについての情報は、べき乗計算部１２及び計算装置２に送られる。
【００１６】
制御部１３は、tに1を代入する（ステップＳ２）。
【００１７】
依頼装置１の第一依頼部１４は、f(x1)r1,f(x2)r2,…,f(xM)rMの計算の依頼をする旨の依頼情報を計算装置２に送信する（ステップＳ３）。例えば、依頼情報は、群Hの元であるx1,x2,…,xMを含む。 計算装置２がf(x1)r1,f(x2)r2,…,f(xM)rMを計算可能であれば、必ずしもx1,x2,…,xMが依頼情報に含まれなくてもよい。
【００１８】
計算装置２の標本器２１は、f(x1)r1,f(x2)r2,…,f(xM)rMを計算可能であり、それらの計算結果をそれぞれz1,z2,…,zMとする（ステップＳ４）。計算結果z1,z2,…,zMは、依頼装置１に送信される。すなわち、f(x1)r1についての計算結果がz1となり、f(x2)r2についての計算結果がz2となり、…、f(xM)rMについての計算結果がzMとなる。
【００１９】
この出願において、計算可能とは、無視することができない確率以上の確率で計算することができることを意味する。無視することができない確率とは、セキュリティパラメータkについての広義単調増加関数である多項式を多項式Φ(k)として、1/Φ(k)以上の確率である。
【００２０】
ここで、f(x)rを計算するとは、f(x)rと定義される式の値を計算することである。式f(x)rの値を最終的に計算することができれば、途中の計算方法は問わない。これは、この出願で登場する他の式の計算についても同様である。
【００２１】
依頼装置１のべき乗計算部１２は、計算結果z1,z2,…,zMをそれぞれa1,a2,…,aM乗する（ステップＳ５）。すなわち、(z1)a1,(z2)a2,…,(zM)aMを計算する。(z1)a1,(z2)a2,…,(zM)aMは、第一記憶部１７に記憶される。
【００２２】
ここで、i=1,2,…,Mとして、(zi)の右肩のaiは、aiのことである。このように、この出願において、αを第一の文字、βを第二の文字、γを数字として、αβγと表記した場合には、そのβγはβγ、すなわちβの下付きγを意味する。
【００２３】
依頼装置１の第二依頼部１５は、f(x1a1×x2a2×…×xMaM)r0の計算の依頼をする旨の依頼情報を計算装置２に送信する（ステップＳ６）。例えば、依頼情報は、群Hの元であるx1,x2,…,xMを含む。依頼情報は、計算装置２がｆ(x1)r1,f(x2)r2,…,f(xM)rMを計算可能であれば、必ずしもx1,x2,…,xMを含まなくてもよい。
【００２４】
計算装置２の拡張乱数化可能標本器２２は、f(x1a1×x2a2×…×xMaM)r0を計算可能であり、その計算結果をz0とする（ステップＳ７）。計算結果z0は、依頼装置１に送信され、依頼装置１の第二記憶部１８に記憶される。
【００２５】
拡張乱数化可能標本器２２は、乱数a1,a2,…,aMを用いて、f(x1×x2×…×xM)を乱数化しつつ、乱数a1,a2,…,aMに依存しない分布を有する確率変数R0に基づいて誤差を与えるものである。
【００２６】
拡張乱数化可能標本器２２は、例えば、x1a1×x2a2×…×xMaMhsを引数とするブラックボックスである確率的関数Fを用いてf(x1a1×x2a2×…×xMaM)r0の値を計算する。すなわち、拡張乱数化可能標本器２２は、例えばF(x1a1×x2a2×…×xMaMhs)f(h)-sの値を計算して、z0とする。ここで、hは群Hの生成元であり、sは0以上の整数の乱数である。ここで、確率的関数Fは所定の確率以上の確率で関数fと同じ値を出力する確率的関数である。すなわち、任意の入力xc∈Hに対して所定の確率以上の確率でF(xc)=f(xc)となる。
【００２７】
Uを群Hの一様分布として、確率変数R0=F(U)f(U)-1とすると、F(x1a1×x2a2×…×xMaMhs)f(h)-sの分布は、f(x1a1×x2a2×…×xMaM)R0の分布と等しくなる。F(x1a1×x2a2×…×xMaMhs)f(h)-s=f(x1a1×x2a2×…×xMaMhs)R0f(h)-s=f(x1a1×x2a2×…×xMaM)f(h)sR0f(h)-s=f(x1a1×x2a2×…×xMaM)R0であるからである。上記式展開において、fの準同型関数であるという性質、及び、R0=F(U)f(U)-1=F(x1a1×x2a2×…×xMaMhs)f(x1a1×x2a2×…×xMaMhs)-1のため、F(x1a1×x2a2×…×xMaMhs)=f(x1a1×x2a2×…×xMaMhs)R0という性質を用いている。
【００２８】
依頼装置１の判定部１６は、第一記憶部１７から読み込んだ(z1)a1,(z2)a2,…,(zM)aM及び第二記憶部１８から読み込んだz0を用いて、(z1)a1×(z2)a2×…×(zM)aM=z0であるか判定する（ステップＳ８）。
【００２９】
(z1)a1×(z2)a2×…×(zM)aM=z0である場合には、後述するように、その場合のz1,z2,…,zMがそれぞれf(x1),f(x2),…,f(xM)となる。このため、出力部１９は、その場合のz1,z2,…,zMをそれぞれf(x1),f(x2),…,f(xM)として出力する（ステップＳ９）。
【００３０】
(z1)a1×(z2)a2×…×(zM)aM=z0である場合には、(f(x1)r1)a1×(f(x2)r2)a2×…×(f(xM)rM)aM=f(x1a1×x2a2×…×xMaM)r0であり、関数fが準同型関数であることを考慮すると、r1a1×r2a2×…×rMaM=r0である。この場合、r1,r2,…,rMが群Gの単位元egである可能性が非常に高いことを発明者は見出した。
【００３１】
なぜなら、第一に、非特許文献１に示された代理計算の原理によって、(z1)a1×(z2)a2×…×(zM)aM=z0であることを判定することで、z0=f(x1a1×x2a2×…×xMaM)であることを非常に高い確率で判定することができる。第二に、f(x1a1×x2a2×…×xMaM)=f(x1)a1×f(x2)a2×…×f(xM)aMであるから、z0=f(x1a1×x2a2×…×xMaM)が成立するということは、z0=f(x1)a1×f(x2)a2×…×f(xM)aMが成立する。第三に、aiを0以上の整数の乱数としてz0=f(x1a1×x2a2×…×xMaM)を計算する任意の方法について、それを繰り返し実行すれば、参考文献１及び参考文献２で示された方法を用いて、z0=f(x1)a1×f(x2)a2×…×f(xM)aMから各iについてf(xi)を導出することができる。第四に、第三で用いた方法と全く同じ方法で、第三で用いた整数aiと全く同じ値を用いることで、(z1)a1×(z2)a2×…×(zM)aMから各iについてziを導出することもできる。以上によって、(z1)a1×(z2)a2×…×(zM)aM=z0=f(x1a1×x2a2×…×xMaM)=f(x1)a1×f(x2)a2×…×f(xM)aMであるならば、各iについてzi=f(xi)である可能性が非常に高い。したがって、(z1)a1×(z2)a2×…×(zM)aM=z0であるならば、r1,r2,…,rMが群Gの単位元egである可能性が非常に高い。
【００３２】
〔参考文献１〕M. Bellare, J. Garay, and T. Rabin, “Fast Batch Verification for Modular Exponentiation and Digital Signatures,” Advances in Cryptology-EUROCRYPT '98, LNCS 1403, pp. 236-250, Springer-Verlag, 1998.
〔参考文献２〕K. Chida and G. Yamamoto, “Batch Processing of Interactive Proofs,” Topics in Cryptology-CT-RSA2007, LNCS 4377, pp. 196-207, Springer, 2007.
【００３３】
このため、(z1)a1×(z2)a2×…×(zM)aM=z0である場合、z1=f(x1)r1=f(x1)eg=f(x1),z2=f(x2)r2=f(x2)eg=f(x2),…,zM=f(xM)rM=f(x1)eg=f(xM)となるのである。
【００３４】
制御部１３は、t=Tであるか判定する（ステップＳ１０）。Tは予め定められた1以上の整数である。t=Tであれば、出力部１９は、計算をすることができなかった旨の情報、例えば記号「⊥」を出力して（ステップＳ１１）、処理を終える。t=Tでない場合には、制御部１３は、tを1だけインクリメント、すなわちtにt+1を代入して（ステップＳ１２）、ステップＳ３に戻る。
【００３５】
計算をすることができなかった旨の情報（この例では記号「⊥」）は、計算装置２が正しく計算を行う信頼性がTで定められる基準を下回るということを意味する。言い換えれば、T回の繰り返しで正しい演算を行うことができなかったということを意味する。
【００３６】
ステップＳ１２の後に、上記と同様にして、依頼装置１は計算装置２に、z1,z2,…,zMの全部又は一部の計算をさせる（ステップＳ３、ステップＳ４）。べき乗計算部１２は、計算された全部又は一部のz1,z2,…,zMのそれぞれついて、対応する乱数a1,a2,…,aMを用いてべき乗を行う（ステップＳ５）。べき乗された(z1)a1,(z2)a2,…,(zM)aMは、第一記憶部１７に記憶される。
【００３７】
ステップＳ８の処理において、第一記憶部１７及び第二記憶部１８にz0,(z1)a1,(z2)a2,…,(zM)aMの少なくとも１つが複数記憶されている場合には、第一記憶部１７及び第二記憶部１８に記憶されたｚ0,(z1)a1,(z2)a2,…,(zM)aMのそれぞれから1つずつ選択することにより構成されるz0,(z1)a1,(z2)a2,…,(zM)aMの全ての組(z0,(z1)a1,(z2)a2,…,(zM)aM)のそれぞれについて、判定部１６は(z1)a1×(z2)a2×…×(zM)aM=z0の関係を満たすか判定する（ステップＳ８）。
【００３８】
例えば、k0,k1,…,kMを１以上の整数として、第一記憶部１７及び第二記憶部１８にｚ0がk0個、z1がk1個、…、zMがkM個記憶されているとする。この場合、第一記憶部１７及び第二記憶部１８に記憶されたz0,(z1)a1,(z2)a2,…,(zM)aMのそれぞれから1つずつ選択することにより構成されるz0,(z1)a1,(z2)a2,…,(zM)aMの組(z0,(z1)a1,(z2)a2,…,(zM)aM)は、k0×k1×k2×…×kM個存在する。したがって、判定部１６は、k0×k1×k2×…×kM個の組(z0,(z1)a1,(z2)a2,…,(zM)aM)のそれぞれについて、(z1)a1×(z2)a2×…×(zM)aM=z0の関係を満たすか判定する。
【００３９】
第一回目のステップＳ８の処理で(z1)a1×(z2)a2×…×(zM)aM=z0の関係を満たす場合には、標本器２１はブラックボックスをM回用いてz1,z2,…,zMの計算を行い、拡張乱数化可能標本器２２はブラックボックスFを1回用いてz0の計算を行っており、ブラックボックスを参照する回数は合計でM+1回である。このように、ブラックボックスを用いて計算する回数を最小でM+1回にすることができる。
【００４０】
［変形例等］
確率変数R0,R1,…,RMは、同じでも異なっていてもよい。
【００４１】
乱数生成部１１は、一様乱数を生成することにより、代理計算システムの安全性が最も高くなる。しかし、求める安全性のレベルがそれほど高くない場合には、乱数生成部１１は、一様乱数ではない乱数を生成してもよい。
【００４２】
また、依頼装置１が複数の依頼情報を計算装置２にまとめて提供し、対応するz0,z1,z2,…,zMを複数個まとめて取得してもよい。これにより、依頼装置１と計算装置２との間のやり取り回数を減らすことができる。
【００４３】
依頼装置１及び計算装置２の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。
【００４４】
その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００４５】
例えば、第一記憶部１７及び第二記憶部１８にz0,(z1)a1,(z2)a2,…,(zM)aMの少なくとも１つが複数記憶されている場合には、図３に破線で示すように、判定部１６はステップＳ５とステップＳ６の間にステップＳ８の処理を行ってもよい。
【００４６】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００４７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４８】
その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【図１】
2012121152.tif 000003
【図２】
2012121152.tif 000004
【図３】
2012121152.tif 000005
【国際調査報告】
2012121152.tif 000006
2012121152.tif 000007
2012121152.tif 000008
2012121152.tif 000009