(57)【特許請求の範囲】
【請求項１】
N,qを2以上の整数とし、ρをN/q以上の最小の整数とし、
環Rから環Rqへ一様に対応させるためのパラメタαi,j,k（i=0,…,q-1; j=0,…,q-1; k=0,…,q-1）を記憶するパラメタ記憶部と、
N個の値a0,…,aN-1を先頭からq個ずつに分割して値ベクトルA0,…,Aρ-1を生成する分割部と、
前記値ベクトルA0,…,Aρ-1を用いて、ベクトルの乗算を下記の式で定義される関数fとして、加算と乗算からなるチェックサムcを生成する生成部と、
【数９】
0005957095.tif 000010
ベクトルの乗算を上記関数fとして、前記値ベクトルA0,…,Aρ-1を用いて生成した検証値と前記チェックサムcとを比較することで前記値a0,…,aN-1のいずれかが改ざんされたか否かを検証する検証部と、
を含む改ざん検知装置。
【請求項２】
請求項１に記載の改ざん検知装置であって、
乱数rを選択する選択部を含み、
前記生成部は、以下の式を計算することで前記チェックサムcを生成し、
【数１０】
0005957095.tif 000011
前記検証部は、以下の式が0であれば前記値a0,…,aN-1のいずれも改ざんされていないと判断し、以下の式が0以外であれば前記値a0,…,aN-1の少なくとも１個が改ざんされていると判断する
【数１１】
0005957095.tif 000012
ことを特徴とする改ざん検知装置。
【請求項３】
請求項１に記載の改ざん検知装置であって、
Mを2以上の整数とし、M<Nとし、i,i’を自然数とし、i≠i’とし、j<Mとし、いずれかのjでd(i,j)をd(i,j)≠d(i’,j)である関数とし、
M個の乱数r0,…,rM-1を選択する選択部を含み、
前記生成部は、以下の式を計算することで前記チェックサムcを生成し、
【数１２】
0005957095.tif 000013
前記検証部は、以下の式が真であれば前記値a0,…,aN-1のいずれも改ざんされていないと判断し、以下の式が偽であれば前記値a0,…,aN-1の少なくとも１個が改ざんされていると判断する
【数１３】
0005957095.tif 000014
ことを特徴とする改ざん検知装置。
【請求項４】
N,qを2以上の整数とし、ρをN/q以上の最小の整数とし、αi,j,k（i=0,…,q-1; j=0,…,q-1; k=0,…,q-1）を環Rから環Rqへ一様に対応させるためのパラメタとし、
分割部が、N個の値a0,…,aN-1を先頭からq個ずつに分割して値ベクトルA0,…,Aρ-1を生成する分割ステップと、
生成部が、前記値ベクトルA0,…,Aρ-1を用いて、ベクトルの乗算を下記の式で定義される関数fとして、加算と乗算からなるチェックサムcを生成する生成ステップと、
【数１４】
0005957095.tif 000015
検証部が、ベクトルの乗算を上記関数fとして、前記値ベクトルA0,…,Aρ-1を用いて生成した検証値と前記チェックサムcとを比較することで前記値a0,…,aN-1のいずれかが改ざんされたか否かを検証する検証ステップと、
を含む改ざん検知方法。
【請求項５】
請求項１から３のいずれかに記載の改ざん検知装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、データを秘匿しつつデータ処理を行う秘匿計算においてデータ改ざんを検知するための改ざん検知技術に関する。
【背景技術】
【０００２】
従来の改ざん検知に使用するチェックサムとして非特許文献１に記載の技術がある。非特許文献１に記載のチェックサムは加算と乗算から構成されており秘匿計算に効率よく適用できる。【０００３】
非特許文献１に記載のチェックサムは、Fを体として、値a0,…,aN-1∈Fのチェックサムcを、乱数r∈Fを用いて、以下の式(1)により生成する。【０００４】
【数１】
0005957095.tif 000002
【０００５】
非特許文献１では、以下の式(2)によりチェックサムcを検証する。【０００６】
【数２】
0005957095.tif 000003
【０００７】
式(2)が0であれば、値a0,…,aN-1はいずれも改ざんされていないと判断する。式(2)が0以外であれば、値a0,…,aN-1は少なくとも1個が改ざんされていると判断する。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】S. Obana and T. Araki, “Almost optimum secret sharing schemes secure against cheating for arbitrary secret distribution”, ASIACRYPT, Vol. 4284 of Lecture Notes in Computer Science, pp. 364-379, 2006.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
非特許文献１に記載の改ざん検知技術では、体Fが予め決定されている際の改ざん成功確率はN/|F|である。ここで、Nはチェックサム生成の対象データ数を表し、|・|は・の要素数を表す。このように、改ざん成功確率がデータ数Nに比例してしまうため、チェックサムを生成する対象データが大きいほど改ざん成功確率が大きくなってしまう。【００１０】
この発明の目的は、秘匿計算に効率よく適用でき、改ざん成功確率をより低く設定できる改ざん検知技術を提供することである。
【課題を解決するための手段】
【００１１】
上記の課題を解決するために、この発明の改ざん検知装置は、N,qを2以上の整数とし、ρをN/q以上の最小の整数とし、環Rから環Rqへ一様に対応させるためのパラメタαi,j,k（i=0,…,q-1; j=0,…,q-1; k=0,…,q-1）を記憶するパラメタ記憶部と、N個の値a0,…,aN-1を先頭からq個ずつに分割して値ベクトルA0,…,Aρ-1を生成する分割部と、値ベクトルA0,…,Aρ-1を用いて、ベクトルの乗算を下記の式で定義される関数fとして、加算と乗算からなるチェックサムcを生成する生成部と、ベクトルの乗算を関数fとして、値ベクトルA0,…,Aρ-1を用いて生成した検証値とチェックサムcとを比較することで値a0,…,aN-1のいずれかが改ざんされたか否かを検証する検証部とを含む。【００１２】
【数３】
0005957095.tif 000004
【発明の効果】
【００１３】
この発明の改ざん検知技術によれば、秘匿計算に効率よく適用でき、改ざん成功確率をより低く設定できる。
【図面の簡単な説明】
【００１４】
【図１】改ざん検知装置の機能構成を例示する図である。
【図２】チェックサム生成の処理フローを例示する図である。
【図３】チェックサム検証の処理フローを例示する図である。
【発明を実施するための形態】
【００１５】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１６】
［第一実施形態］
この発明の第一実施形態は、非特許文献１に記載の加算と乗算からなるチェックサムに適用した実施形態である。
【００１７】
＜構成＞
図１を参照して、この実施形態の改ざん検知装置１の構成例を説明する。改ざん検知装置１は、制御部１０１、メモリ１０２、入力部１１、分割部１２、選択部１３、生成部１４、検証部１５、出力部１６、パラメタ記憶部１９を備える。改ざん検知装置１は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。改ざん検知装置１は制御部１０１の制御のもとで各処理を実行する。改ざん検知装置１に入力されたデータや各処理で得られたデータはメモリ１０２に格納され、メモリ１０２に格納されたデータは必要に応じて読み出されて他の処理に利用される。パラメタ記憶部１９は、例えば、ＲＡＭ（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリなどの半導体メモリ素子により構成される補助記憶装置、リレーショナルデータベースやキーバリューストアなどのミドルウェア、などにより構成することができる。
【００１８】
＜チェックサム生成処理＞
図２を参照して、この実施形態の改ざん検知装置１が実行するチェックサム生成処理の動作例について手続きの順に従って詳細に説明する。以降の説明では、N,qを2以上の整数とし、ρをN/q以上の最小の整数とし、Rを環とする。
【００１９】
パラメタ記憶部１９には、予め環Rから環Rqへ一様に対応させるためのパラメタαi,j,k（i=0,…,q-1; j=0,…,q-1; k=0,…,q-1）が記憶されている。パラメタαi,j,kは環Rと次数qを決定することで求めることができる。パラメタαi,j,kは複数の種類があり得るが、計算の容易さなどを考慮して、パラメタαi,j,kに含まれるq3個の値に0が最も多く含まれるものをパラメタαi,j,kとして選択することが望ましい。例えば、Rが体であり、Rqが体Rの拡大体となるようにパラメタαi,j,kを決定すれば、効率的に改ざん検知が可能となる。
【００２０】
改ざん検知装置１の備える入力部１１へN個の値a0,…,aN-1∈Rが入力される（ステップＳ１１ａ）。入力された値a0,…,aN-1は分割部１２へ入力される。値a0,…,aN-1はどのような情報であってもよいが、例えば準同型暗号の暗号文もしくは秘密分散の分散値などとすることができる。準同型暗号とは準同型性を有するような暗号方式であり、暗号文から暗号化されたままで元の平文の和または積を計算できる暗号方式である。準同型暗号の一例はElGamal暗号である。ElGamal暗号についての詳細は「T. ElGamal, “A public key cryptosystem and a signature scheme based on discrete logarithms”, IEEE Transactions on Information Theory, vol.31, no.4, pp.469-472, 1985.」などに記載されている。秘密分散とは秘匿したいデータを複数の分散値に変換し、一定個数以上の分散値を用いれば元のデータを復元でき、一定個数未満の分散値からは元のデータを一切復元できなくする技術である。秘密分散の一例はShamir秘密分散である。Shamir秘密分散についての詳細は「A. Shamir, “How to share a secret”, Communications of the ACM, vol.22, issue 11, pp. 612-613, 1979.」などに記載されている。
【００２１】
分割部１２は、N個の値a0,…,aN-1を先頭からq個ずつに分割してρ個の値ベクトルA0,…,Aρ-1を生成する（ステップＳ１２ａ）。生成した値ベクトルA0,…,Aρ-1は生成部１４へ入力される。分割した際に最後の値ベクトルAρ-1の要素数がqとならない場合には、要素数がqとなるように任意の値でパディングする。例えば、0でパディングするものとして、N=11,q=2とした場合には、a0,…,a10をA0:=(a0,a1), A1:=(a2,a3), A2:=(a4,a5),…, A5:=(a10,0)のように分割すればよい。
【００２２】
選択部１３は乱数r∈Rを選択する（ステップＳ１３）。選択した乱数rは生成部１４へ入力される。選択部１３は、逐一ランダムに乱数rを選択してもよいし、事前に生成されメモリ１０２に格納されている複数個の値から所定の規則に従って乱数rを選択してもよい。また、乱数rは真の乱数ではなく任意の暗号方式やハッシュ関数などから生成される疑似乱数であってもよい。
【００２３】
生成部１４は値ベクトルA0,…,Aρ-1と乱数rを用いてチェックサムcを生成する（ステップＳ１４）。生成したチェックサムcと乱数rは出力部１６へ入力される。具体的には生成部１４は、以下の式(3)によりチェックサムcを計算する。
【００２４】
【数４】
0005957095.tif 000005
【００２５】
この際、ベクトルの乗算は、式(4)(5)で定義される関数fを用いて計算する。
【００２６】
【数５】
0005957095.tif 000006
【００２７】
出力部１６はチェックサムcと乱数rを出力する（ステップＳ１６ａ）。
＜チェックサム検証処理＞
図３を参照して、この実施形態の改ざん検知装置１が実行するチェックサム検証処理の動作例について手続きの順に従って詳細に説明する。
【００２８】
改ざん検知装置１の備える入力部１１へN個の値a0,…,aN-1∈Rと乱数r∈Rとチェックサムcが入力される（ステップＳ１１ｂ）。入力された値a0,…,aN-1は分割部１２へ入力される。入力された乱数rとチェックサムcは検証部１５へ入力される。
【００２９】
分割部１２は、値a0,…,aN-1を先頭からq個ずつに分割して値ベクトルA0,…,Aρ-1を生成する（ステップＳ１２ｂ）。分割の方法はチェックサム生成処理における分割部１２の処理と同様である。また、チェックサム生成処理において生成した値ベクトルA0,…,Aρ-1を記憶しておくように構成することで、ステップＳ１２ｂの処理は省略することができる。
【００３０】
検証部１５は値ベクトルA0,…,Aρ-1と乱数rとチェックサムcとを用いて、値a0,…,aN-1のいずれかが改ざんされたか否かを示す検証結果を生成する（ステップＳ１５）。検証結果は出力部１６へ入力される。
【００３１】
具体的には検証部１５は以下の式(6)を評価する。式(6)が0であれば値a0,…,aN-1のいずれも改ざんされていないと判断する。式(6)が0以外であれば値a0,…,aN-1の少なくとも１個が改ざんされていると判断する。
【００３２】
【数６】
0005957095.tif 000007
【００３３】
この際、ベクトルの乗算は、チェックサム生成処理と同様に、式(4)(5)で定義される関数fを用いて計算する。
【００３４】
出力部１６は検証結果を出力する（ステップＳ１６ｂ）。
＜効果＞
非特許文献１に記載のチェックサムは、チェックサム生成対象のデータ数がN、環Rの要素数がpとして、改ざん成功確率が高々N/pである。環Rが固定であり、例えばp=2とすると、改ざん検知はほとんど無力と言ってよい。
【００３５】
第一実施形態のチェックサムは、値ベクトルA0,…,Aρ-1∈Rqを単位に計算することで、改ざん成功確率を低く抑えることができる。例えば、Zを整数環、pを素数、qを2以上の整数として、環Rを素体すなわちZ/pZとしたとき、改ざん成功確率はN/pq程度とすることができる。したがって、任意に設定できる拡大次数qにより、任意の低い改ざん成功確率を得ることができる。
【００３６】
［第二実施形態］
この発明の第二実施形態は、非特許文献１に記載のチェックサムよりも改ざん成功確率を低く抑えることができるチェックサムに適用した実施形態である。
【００３７】
＜構成＞
図１を参照して、この実施形態の改ざん検知装置２の構成例を説明する。第二実施形態の改ざん検知装置２の構成は、第一実施形態の改ざん検知装置１と同様であるが、選択部と生成部と検証部の処理が異なる。改ざん検知装置２は、制御部１０１、メモリ１０２、入力部１１、分割部１２、選択部２３、生成部２４、検証部２５、出力部１６、パラメタ記憶部１９を備える。改ざん検知装置２は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。改ざん検知装置２は制御部１０１の制御のもとで各処理を実行する。改ざん検知装置２に入力されたデータや各処理で得られたデータはメモリ１０２に格納され、メモリ１０２に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００３８】
＜チェックサム生成処理＞
図２を参照して、この実施形態の改ざん検知装置２が実行するチェックサム生成処理の動作例について手続きの順に従って詳細に説明する。以降の説明では、M,N,qを2以上の整数とし、M<Nとし、ρをN/q以上の最小の整数とし、Rを環とする。
【００３９】
ステップＳ１１ａからステップＳ１２ａまでの処理は第一実施形態と同様であるので、ここでは説明を省略する。
【００４０】
この実施形態の選択部２３はM個の乱数r0,…,rM-1∈Rを選択する（ステップＳ２３）。選択した乱数r0,…,rM-1は生成部２４へ入力される。選択部２３は、逐一ランダムにM個の乱数r0,…,rM-1を選択してもよいし、事前に生成されメモリ１０２に格納されている複数個の値から所定の規則に従ってM個の乱数r0,…,rM-1を選択してもよい。
【００４１】
この実施形態の生成部２４は値ベクトルA0,…,Aρ-1と乱数r0,…,rM-1を用いてチェックサムcを生成する（ステップＳ２４）。生成したチェックサムcと乱数r0,…,rM-1は出力部１６へ入力される。具体的には生成部２４は、以下の式(7)によりチェックサムcを計算する。
【００４２】
【数７】
0005957095.tif 000008
【００４３】
この際、ベクトルの乗算は、第一実施形態と同様に、式(4)(5)で定義される関数fを用いて計算する。
【００４４】
式(7)において、関数d(i,j)はi番目の値aiに対するj番目の乱数rjの次数を決定する関数である。ただし、i,i’を自然数とし、i≠i’として、いずれかのj(ただしj<M)でd(i,j)≠d(i’,j)を満たすものとする。すなわち、乱数r0,…,rM-1の次数の組み合わせがAi毎に重複しない組み合わせとなっていなければならない。
【００４５】
例えば、ρ=3,M=2とした場合であれば、c=A0r0+A1r1+A2r0r1のように計算すればよい。また、ρ=4,M=2とした場合であれば、c=A0r0+A1r1+A2r0r1+A3r02r1のように計算してもよいし、c=A0r02r1+A1r0r1+A2r1+A3r0のように計算してもよい。
【００４６】
Mは2以上ρ未満であればどのような値であってもよいが、log2ρを超える最少の整数とすれば、乱数r0,…,rM-1に対するすべての次数を1以下にすることができるため、最も効率がよい。例えば、ρ=7,M=3とした場合であれば、c=A0r0+A1r1+A2r0r1+A3r2+A4r0r2+A5r1r2+A6r0r1r2のようにすることができ、すべての乱数の次数を1以下とすることができる。
【００４７】
出力部１６はチェックサムcと乱数r0,…,rM-1を出力する（ステップＳ１６ａ）。
＜チェックサム検証処理＞
図３を参照して、この実施形態の改ざん検知装置２が実行するチェックサム検証処理の動作例について手続きの順に従って詳細に説明する。
【００４８】
ステップＳ１１ｂからステップＳ１２ｂまでの処理は第一実施形態と同様であるので、ここでは説明を省略する。
【００４９】
検証部２５は値ベクトルA0,…,Aρ-1と乱数r0,…,rM-1とチェックサムcとを用いて、値a0,…,aN-1のいずれかが改ざんされたか否かを示す検証結果を生成する（ステップＳ２５）。検証結果は出力部１６へ入力される。
【００５０】
具体的には検証部２５は以下の式(8)を評価する。式(8)が真であれば値a0,…,aN-1のいずれも改ざんされていないと判断する。式(8)が偽であれば値a0,…,aN-1の少なくとも１個が改ざんされていると判断する。
【００５１】
【数８】
0005957095.tif 000009
【００５２】
この際、ベクトルの乗算は、チェックサム生成処理と同様に、式(4)(5)で定義される関数fを用いて計算する。
【００５３】
式(8)において、関数d(i,j)は式(7)の関数d(i,j)と同じ関数である。
【００５４】
出力部１６は検証結果を出力する（ステップＳ１６ｂ）。
＜効果＞
第二実施形態のチェックサムは、値a0,…,aN-1∈Rを単位に計算した場合には、チェックサム生成対象のデータ数がN、環Rの要素数がpとして、改ざん成功確率が高々logN/pである。非特許文献１に記載のチェックサムよりも低いながら、それでも環Rが固定であり、例えばp=2とすると改ざん検知はほとんど無力と言ってよい。
【００５５】
第二実施形態のチェックサムは、値ベクトルA0,…,Aρ-1∈Rqを単位に計算することで、改ざん成功確率を低く抑えることができる。例えば、Zを整数環、pを素数、qを2以上の整数として、環Rを素体すなわちZ/pZとしたとき、改ざん成功確率はlogN/pq程度とすることができる。したがって、任意に設定できる拡大次数qにより、任意の低い改ざん成功確率を得ることができる。
【００５６】
［応用例］
この発明の改ざん検知技術は様々な利用方法が考えられる。例えば、準同型暗号による暗号文や秘密分散による分散データを第三者の管理するサーバに預託する場合が考えられる。このような場合には、サーバに対して悪意ある攻撃者が侵入しデータを改ざんする場合、サーバ自体が悪意を持って預託されたデータを改ざんする場合、サーバがマルウェアに感染してデータを改ざんする場合などのリスクが考えられる。預託するデータに対して、この発明によるチェックサムを生成して付与しておくことで、サーバは秘匿されたデータに対して秘匿されたままデータ処理を行うことができ、さらに、データ改ざんも防止することができる。
【００５７】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００５８】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００５９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００６０】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
0005957095.tif 000016
【図２】
0005957095.tif 000017
【図３】
0005957095.tif 000018