(57)【要約】【課題】秘匿計算に効率よく適用でき、改ざん成功確率をより低く設定できる。【解決手段】改ざん検知装置１は、M個の乱数r0,…,rM-1を選択する選択部１２と、N個の値a0,…,aN-1と、乱数r0,…,rM-1と、値a0,…,aN-1のインデックスi（0≦i≦N-1）と乱数r0,…,rM-1のインデックスj（0≦j≦M-1）とに基づいて定まる次数d(i,j)とを用いて、チェックサムcを生成する生成部１３と、値a0,…,aN-1と乱数r0,…,rm-1と次数d(i,j)とを用いて計算した検証値とチェックサムcとを比較することで値a0,…,aN-1のいずれかが改ざんされたか否かを検証する検証部１４とを含む。ただし、M,Nを2以上の整数とし、M<Nとする。【選択図】図１
2014137474.tif 000002
【特許請求の範囲】
【請求項１】
M,Nを2以上の整数とし、M<Nとし、
M個の乱数r0,…,rM-1を選択する選択部と、
N個の値a0,…,aN-1と、前記乱数r0,…,rM-1と、前記値a0,…,aN-1のインデックスi（0≦i≦N-1）と前記乱数r0,…,rM-1のインデックスj（0≦j≦M-1）とに基づいて定まる次数d(i,j)とを用いて、チェックサムcを生成する生成部と、
前記値a0,…,aN-1と前記乱数r0,…,rm-1と前記次数d(i,j)とを用いて計算した検証値と前記チェックサムcとを比較することで前記値a0,…,aN-1のいずれかが改ざんされたか否かを検証する検証部と、
を含む改ざん検知装置。
【請求項２】
請求項１に記載の改ざん検知装置であって、
前記次数d(i,j)は、i,i’を正の整数とし、i≠i’とし、j<Mとし、いずれかのjでd(i,j)≠d(i’,j)であり、
前記生成部は、以下の式を計算することで前記チェックサムcを生成し、
【数６】
2014137474.tif 000008
前記検証部は、以下の式が真であれば前記値a0,…,aN-1のいずれも改ざんされていないと判断し、以下の式が偽であれば前記値a0,…,aN-1の少なくとも１個が改ざんされていると判断する
【数７】
2014137474.tif 000009
ことを特徴とする改ざん検知装置。
【請求項３】
M,Nを2以上の整数とし、M<Nとし、
選択部が、M個の乱数r0,…,rM-1を選択する選択ステップと、
生成部が、N個の値a0,…,aN-1と、前記乱数r0,…,rM-1と、前記値a0,…,aN-1のインデックスi（0≦i≦N-1）と前記乱数r0,…,rM-1のインデックスj（0≦j≦M-1）とに基づいて定まる次数d(i,j)とを用いて、チェックサムcを生成する生成ステップと、
検証部が、前記値a0,…,aN-1と前記乱数r0,…,rm-1と前記次数d(i,j)とを用いて計算した検証値と前記チェックサムcとを比較することで前記値a0,…,aN-1のいずれかが改ざんされたか否かを検証する検証ステップと、
を含む改ざん検知方法。
【請求項４】
請求項１または２に記載の改ざん検知装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、データを秘匿しつつデータ処理を行う秘匿計算においてデータ改ざんを検知するための改ざん検知技術に関する。
【背景技術】
【０００２】
従来の改ざん検知に使用するチェックサムとして非特許文献１に記載の技術がある。非特許文献１に記載のチェックサムは加算と乗算から構成されており秘匿計算に効率よく適用できる。
【０００３】
非特許文献１に記載のチェックサムは、Fを体として、値a0,…,aN-1∈Fのチェックサムcを、乱数r∈Fを用いて、以下の式(1)により生成する。
【０００４】
【数１】
2014137474.tif 000003
【０００５】
非特許文献１では、以下の式(2)によりチェックサムcを検証する。
【０００６】
【数２】
2014137474.tif 000004
【０００７】
式(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に比例してしまうため、チェックサムを生成する対象データが大きいほど改ざん成功確率が大きくなってしまう。
【００１０】
この発明の目的は、秘匿計算に効率よく適用でき、改ざん成功確率をより低く設定できる改ざん検知技術を提供することである。
【課題を解決するための手段】
【００１１】
上記の課題を解決するために、この発明の改ざん検知装置は、M,Nを2以上の整数とし、M<Nとし、M個の乱数r0,…,rM-1を選択する選択部と、N個の値a0,…,aN-1と、M個の乱数r0,…,rM-1と、値a0,…,aN-1のインデックスi（0≦i≦N-1）と乱数r0,…,rM-1のインデックスj（0≦j≦M-1）とに基づいて定まる次数d(i,j)とを用いて、チェックサムcを生成する生成部と、N個の値a0,…,aN-1とM個の乱数r0,…,rm-1と次数d(i,j)とを用いて計算した検証値とチェックサムcとを比較することで値a0,…,aN-1のいずれかが改ざんされたか否かを検証する検証部とを有する。
【発明の効果】
【００１２】
この発明の改ざん検知技術によれば、秘匿計算に効率よく適用でき、改ざん成功確率をより低く設定できる。
【図面の簡単な説明】
【００１３】
【図１】改ざん検知装置の機能構成を例示する図である。
【図２】チェックサム生成の処理フローを例示する図である。
【図３】チェックサム検証の処理フローを例示する図である。
【発明を実施するための形態】
【００１４】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１５】
［実施形態］
＜構成＞
図１を参照して、この実施形態の改ざん検知装置１の構成例を説明する。改ざん検知装置１は、制御部１０１、メモリ１０２、入力部１１、選択部１２、生成部１３、検証部１４、出力部１５を備える。改ざん検知装置１は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。改ざん検知装置１は制御部１０１の制御のもとで各処理を実行する。改ざん検知装置１に入力されたデータや各処理で得られたデータはメモリ１０２に格納され、メモリ１０２に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００１６】
＜チェックサム生成処理＞
図２を参照して、この実施形態の改ざん検知装置１が実行するチェックサム生成処理の動作例について手続きの順に従って詳細に説明する。以降の説明では、M,Nを2以上の整数とし、M<Nとし、Rを環とする。
【００１７】
改ざん検知装置１の備える入力部１１へN個の値a0,…,aN-1∈Rが入力される（ステップＳ１１ａ）。入力された値a0,…,aN-1は生成部１３へ入力される。値a0,…,aN-1はどのような情報であってもよいが、例えば準同型暗号の暗号文もしくは秘密分散の分散値などとすることができる。準同型暗号とは準同型性を有するような暗号方式であり、暗号文から暗号化されたままで元の平文の和または積を計算できる暗号方式である。準同型暗号の一例はElGamal暗号である。ElGamal暗号は群上の暗号だが、例えば当該群がZ/pZならば暗号文は環要素ともみなすことができる。群が体上の楕円曲線上の有理点群などであっても同様に暗号文は体（すなわち環）要素でもある。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.」などに記載されている。
【００１８】
選択部１２はM個の乱数r0,…,rM-1∈Rを選択する（ステップＳ１２）。選択した乱数r0,…,rM-1は生成部１３へ入力される。選択部１２は、逐一ランダムにM個の乱数r0,…,rM-1を選択してもよいし、事前に生成されメモリ１０２に格納されている複数個の値から所定の規則に従ってM個の乱数r0,…,rM-1を選択してもよい。
【００１９】
生成部１３は値a0,…,aN-1と乱数r0,…,rM-1を用いてチェックサムcを生成する（ステップＳ１３）。生成したチェックサムcと乱数r0,…,rM-1は出力部１５へ入力される。具体的には生成部１３は、以下の式(3)によりチェックサムcを計算する。
【００２０】
【数３】
2014137474.tif 000005
【００２１】
式(3)において、関数d(i,j)はi番目の値aiに対するj番目の乱数rjの次数を決定する関数である。ただし、i,i’を正の整数とし、i≠i’として、いずれかのj(ただしj<M)でd(i,j)≠d(i’,j)を満たすものとする。すなわち、乱数r0,…,rM-1の次数の組み合わせがai毎に重複しない組み合わせとなっていなければならない。
【００２２】
例えば、N=3,M=2とした場合であれば、c=a0r0+a1r1+a2r0r1のように計算すればよい。また、N=4,M=2とした場合であれば、c=a0r0+a1r1+a2r0r1+a3r02r1のように計算してもよいし、c=a0r02r1+a1r0r1+a2r1+a3r0のように計算してもよい。
【００２３】
Mは2以上N未満であればどのような値であってもよいが、log2Nを超える最少の整数とすれば、乱数r0,…,rM-1に対するすべての次数を1以下にすることができるため、最も効率がよい。例えば、N=7,M=3とした場合であれば、c=a0r0+a1r1+a2r0r1+a3r2+a4r0r2+a5r1r2+a6r0r1r2のようにすることができ、すべての乱数の次数を1以下とすることができる。
出力部１５はチェックサムcと乱数r0,…,rM-1を出力する（ステップＳ１５ａ）。
【００２４】
＜チェックサム検証処理＞
図３を参照して、この実施形態の改ざん検知装置１が実行するチェックサム検証処理の動作例について手続きの順に従って詳細に説明する。
【００２５】
改ざん検知装置１の備える入力部１１へN個の値a0,…,aN-1∈RとM個の乱数r0,…,rM-1∈Rとチェックサムcが入力される（ステップＳ１１ｂ）。入力された値a0,…,aN-1と乱数r0,…,rM-1とチェックサムcは検証部１４へ入力される。
【００２６】
検証部１４は値a0,…,aN-1と乱数r0,…,rM-1とチェックサムcとを用いて、値a0,…,aNのいずれかが改ざんされたか否かを示す検証結果を生成する（ステップＳ１４）。検証結果は出力部１５へ入力される。
【００２７】
具体的には検証部１４は以下の式(4)を評価する。式(4)が真であれば値a0,…,aN-1のいずれも改ざんされていないと判断する。式(4)が偽であれば値a0,…,aN-1の少なくとも１個が改ざんされていると判断する。
【００２８】
【数４】
2014137474.tif 000006
【００２９】
式(5)において、関数d(i,j)は式(1)の関数d(i,j)と同じ関数である。
出力部１５は検証結果を出力する（ステップＳ１５ｂ）。
【００３０】
＜効果＞
非特許文献１に記載のチェックサムは、チェックサム生成対象のデータ数がN、環Rの要素数がpとして、改ざん成功確率が高々N/pである。改ざん成功確率がNに比例するため、データ数が多いと改ざん成功確率が大きくなる。
この実施形態のチェックサムは、改ざん成功確率が以下の式(5)となる。
【００３１】
【数５】
2014137474.tif 000007
【００３２】
このように、乱数の数をMとして、改ざん成功確率はNのM乗根に比例する。例えば、M=2とすれば、改ざん成功確率は√N程度とすることができる。したがって、特にチェックサムを生成する対象データが大きいほど、従来の改ざん検知技術と比較して改ざん成功確率の上昇を抑えることができる。
【００３３】
したがってこの発明の改ざん検知技術によれば、秘匿計算に効率よく適用でき、改ざん成功確率をより低く設定できる。
【００３４】
［応用例］
この発明の改ざん検知技術は様々な利用方法が考えられる。例えば、準同型暗号による暗号文や秘密分散による分散データを第三者の管理するサーバに預託する場合が考えられる。このような場合には、サーバに対して悪意ある攻撃者が侵入しデータを改ざんする場合、サーバ自体が悪意を持って預託されたデータを改ざんする場合、サーバがマルウェアに感染してデータを改ざんする場合などのリスクが考えられる。預託するデータに対して、この発明によるチェックサムを生成して付与しておくことで、サーバは秘匿されたデータに対して秘匿されたままデータ処理を行うことができ、さらに、データ改ざんも防止することができる。
【００３５】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００３６】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００３７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００３８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００３９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００４０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００４１】
１  改ざん検知装置
１１  入力部
１２  選択部
１３  生成部
１４  検証部
１５  出力部
１０１  制御部
１０２  メモリ
【図１】
2014137474.tif 000010
【図２】
2014137474.tif 000011
【図３】
2014137474.tif 000012