情報処理装置、コード生成方法、コード検証方法およびプログラム
【課題】分散情報の改ざんを高確率および効率的に検知可能とし、かつ、パラメータ設定の自由度を大きくした情報処理装置を提供する。
【解決手段】入力される秘密情報sを、素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s＿1,...,s＿N｝で表し、s＿1*...*s＿N mod pをチェック用データvとして求めるチェック用データ生成部と、秘密情報sとチェック用データvに対して線形秘密分散法を用いてそれぞれの分散符号化した値を生成するコード分散部と、復元対象の情報から秘密情報s'およびチェック用データv’を復元するコード復元部と、秘密情報s'がチェック用データ生成部に入力されたときの出力であるチェック用データv''とv'とが等しいか否かを判定し、チェック用データv'とv''が等しい場合にはデータが改ざんされていないと判定し、チェック用データv'とv''が等しくない場合にはデータが改ざんされていると判定する同一性判定部と、を有する。
【解決手段】入力される秘密情報sを、素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s＿1,...,s＿N｝で表し、s＿1*...*s＿N mod pをチェック用データvとして求めるチェック用データ生成部と、秘密情報sとチェック用データvに対して線形秘密分散法を用いてそれぞれの分散符号化した値を生成するコード分散部と、復元対象の情報から秘密情報s'およびチェック用データv’を復元するコード復元部と、秘密情報s'がチェック用データ生成部に入力されたときの出力であるチェック用データv''とv'とが等しいか否かを判定し、チェック用データv'とv''が等しい場合にはデータが改ざんされていないと判定し、チェック用データv'とv''が等しくない場合にはデータが改ざんされていると判定する同一性判定部と、を有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データの改ざんを検知するための、情報処理装置、コード生成方法、コード検証方法、およびその方法をコンピュータに実行させるためのプログラムに関する。
【背景技術】
【０００２】
秘密にしておきたい情報（以下、秘密情報と称する）を保管する場合、秘密情報の紛失だけでなく、破壊の脅威、盗難の脅威がある。前者の脅威に対しては秘密情報のコピーを作成することが有効であるが、後者の盗難に対する脅威が増してしまう。
【０００３】
このような問題を解決する手段の１つとして、秘密分散法が知られている。秘密分散法の１つである(k,n)閾値法について簡単に説明する。秘密情報をn個の分散情報に符号化する。n個の分散情報のうち任意のk個以上の分散情報を集めれば、秘密情報を完全に復元できるが、k-1個以下の分散情報を集めても、元の秘密情報に関する情報をまったく得られない。したがって、k-1個までの分散情報が盗難にあったとしても秘密情報が他人に漏れることがなく、n-k個までの分散情報が破壊されても、秘密情報を復元できる。
【０００４】
(k, n)閾値法の一例が、非特許文献１に開示されている。この非特許文献１に開示された、shamirの提案する方式が効率的であるため、この方式が広く用いられている。
【０００５】
非特許文献１の方式は、素数または素数のべき乗pに対する有限体GF(p)を秘密情報のデータ集合として用い、秘密情報sを定数項に持つGF(p)上のランダムな(k-1)次多項式f(x)上の点、(x＿1,f(x＿1)),...,(x＿n,f(x＿n))を分散情報とする方式である。k個の分散情報からk-1次の多項式は一意に復元でき、f(0)である秘密情報sを復元することができる。また、k-1個以下の分散情報からはf(0)を定めることはできず、秘密情報sに関する情報は一切漏れない。秘密情報を埋め込む箇所はf(0)以外の任意の箇所でもよい。また、多項式の係数などでもよい。
【０００６】
また、xi(i=1,...,n)は互いに異なる値であればよい。
【０００７】
このような(k, n)閾値法を用いることで対処できる脅威もあるが、以下に示すような脅威も存在する。
【０００８】
(k, n)閾値法において分散情報の作成、配付が正しく行われ、その後、秘密情報を復元するために分散情報を複数集める状況を考える。
【０００９】
このとき、分散情報を要求された側が配付された値を改竄することなく渡すとは限らない。また、単純な(k, n)閾値法を用いる場合、改竄された分散情報を用いて復元された値は、秘密情報と異なる値になってしまう可能性を持っている。
【００１０】
現実の状況を例示すると、遺言状を分散したデータを作成して複数の子孫に渡しておいたところ、データが改ざんされ、一部の子孫にとって都合のよい内容に書き換えられてしまうということが挙げられる。
【００１１】
このような攻撃が非特許文献１の方式に行われた場合、秘密情報をsとし、有限体上の加算を+と書くと、改ざん者は、s+s'が復元されるような改ざんを行うことができることが知られている。そのため、先の遺言状の例のような改ざんが行われた場合には、その事実を検知できるような方式が望ましい。
【００１２】
このような機能を、非特許文献１に開示されている(k,n)閾値法に付与する方法は様々知られている。演算処理が効率的な方法としては、以下の方法が知られている。この方法について、秘密情報を分散する分散フェーズと、秘密情報を復元する復元フェーズに分けて概要を記述する。
【００１３】
［分散フェーズ］
１．秘密情報になんらかの処理を適用する。なお、処理を適用した後の値をコードと呼ぶ。
２．コードを既存の(k,n)閾値法で分散する。
【００１４】
［復元フェーズ］
１．コードを復元する。
２．コードの正当性を調べる。ここで正当でないものであると判明した場合、改ざんがあったものとする。
【００１５】
このような構成を採用し、秘密情報を入力としてコードを出力する装置をGenCode()とし、生成されたコードを入力としてそのコードが正当性なものであるかどうかを出力する関数をVerCode()とし、ある秘密情報sについてのコードをcとする。このとき、VerCode(c+c')が正当なものであるという出力を行うようなc'を、改ざん者が生成することができる確率は十分に低い。それだけでなく、コードが正当なときには、必ずコードに対応する秘密情報を出力するものを用いることで、上述の(k,n)閾値法に対する不正が高い確率で検知可能となる。
【００１６】
この方法を実行する情報処理装置について説明する。
【００１７】
図８Ａは関連する分散情報生成装置の一構成例を示すブロック図である。図８Ｂは関連する復元装置の一構成例を示すブロック図である。
【００１８】
図８Ａおよび図８Ｂに示すように、分散情報生成装置700および復元装置800のそれぞれには、分散情報を格納するための複数の保管装置900が接続されている。
【００１９】
はじめに、図８Ａを参照して、分散情報生成装置700の構成を説明する。
【００２０】
分散情報生成装置700は、コード生成部701およびコード分散部702を有する。分散情報生成装置700は、秘密情報用データ集合Sの元と、閾値ｋと、分散情報数nと、保管先装置指定データとが入力されると、保管先装置指定データの指定するn個の保管装置900のそれぞれに対し、分散コードデータ集合BSの元である分散コード情報を格納する。
【００２１】
コード生成部701は、秘密情報用データ集合Sの元sが入力されると、コード情報用データ集合Ｃの元cを出力する。
【００２２】
コード分散部702は、集合Cの元と、閾値ｋと、分散情報数nと、保管先装置指定データとが入力されると、保管先装置指定データの指定するn個の保管装置900のそれぞれに対して分散コードデータ集合BSの元を格納する。
【００２３】
次に、図８Ｂを参照して、復元装置800の構成を説明する。
【００２４】
復元装置800は、コード復元部801およびコード正当性検証部802を有する。復元装置800は、集合Cの元と、閾値ｋと、分散情報数nと、保管先装置指定データとが入力されると、複数の保管装置900から、それぞれが記憶するBSの元を読み出し、秘密情報用データ集合Sの元のデータ、または、不正の検出を表す記号を出力する。
【００２５】
コード復元部801は、集合Cの元と、閾値ｋと、保管先装置指定データとが入力されると、複数の保管装置900から、それぞれの記憶部901が記憶するBSの元を読み出し、Cの元を出力する。
【００２６】
コード正当性検証部802は、Ｃの元が入力されると、Ｓの元のデータ、またはコードが不正であったことを表すデータを出力する。なお、保管装置900は、分散コード用データ集合BCの元を記憶する記憶部901を有する。
【００２７】
次に、分散情報生成装置700の動作手順を、図９のフローチャートを参照して説明する。
【００２８】
閾値kと、分散情報数nと、保管先装置指定データと、秘密情報用データ集合Ｓの元sが分散情報生成装置700に入力される(ステップA1)。
【００２９】
コード生成部701は、入力されたsに対応するコード情報用データ集合Ｃの元であるcを出力する(ステップA2)。
【００３０】
コード分散部702は、閾値kと、分散情報数nと、保管先装置指定データと、コード生成部701の出力であるcとが入力されると、cを(k,n)閾値法で分散符号化し、分散符号化されたcを、保管先装置指定データの指定する保管装置900の記憶部901に格納する(ステップA3)。
【００３１】
次に、復元装置800の動作手順を、図１０のフローチャートを参照して説明する。
【００３２】
閾値kと分散情報数nが復元装置800に入力される(ステップB1)。コード復元部801は、ｋ機以上の複数の保管装置900の記憶部901からデータを読み出す(ステップB2)。続いて、コード復元部801は、読み出したデータと閾値kとから、コード分散部702の分散符号化方法に対応する復元方法を用いて復元処理を行った結果であるＣの元c'を出力する(ステップB3)。
【００３３】
コード正当性検証部802は、コード復元部801からc'を受け取ると、c'の正当性を検証する処理を行い、正当なコードであった場合には、c'に対応するSの元s'を出力し、それ以外の場合には、不正の検出を表す記号を出力する（ステップB4）。
【００３４】
なお、GenCodeの入力には、秘密情報以外の情報を入力する場合もある。また、cは有限体の要素がひとつであるとは限らず、複数の異なる有限体の要素からなる場合もある。例えば、３つの要素からなる場合を考えるとc=(c1,c2,c3)となる場合もある。このとき、c=(c1,c2,c3)とc'=(c1',c2',c3')に対し、+をc1,c2,c3の各要素に対応する有限体上で定義されている加算であるとすると、c+c'は(c1+c1',c2+c2',c3+c3')を表しているものとする。
【００３５】
また、コードの集合が小さければ小さいほど分散情報のサイズが小さく、秘密情報を分散して保管する場合に必要とする記憶容量が少なくて済み、好ましい。
【００３６】
また、これまで述べた技術を、先に説明したShamirの閾値法以外にも適用可能である。例えば、線形秘密分散法と呼ばれる秘密分散法に対してもこれまでに述べた技術を適用できることが知られている。
【００３７】
線形秘密分散法とは，次のような性質を持った秘密分散法である。なお、秘密を復元可能な分散情報の集合を要素とする集合をアクセス構造と呼ぶことにする。秘密情報は有限体Fの元であるとする。
1. 分散情報(v＿1,...,v＿n) が(v＿1, v＿2, ... ,v＿n)= (s, r＿1, ... ,r＿｛t-1｝)M のようにF 上の固定のt*n行列Mとランダムに選ばれたF の要素r＿i によって生成される。
2. アクセス構造に含まれる分散情報の集合V＿i = ｛v＿｛i＿1｝,v＿｛i＿2｝,...,v＿｛i＿j｝｝から秘密情報を、
s =c＿｛i＿1｝*v＿｛i＿1｝ + c＿｛i＿2｝*v＿｛i＿2｝ + ... + c＿｛i＿j｝*v＿｛i＿j｝のように計算できる。ただし、c＿｛i＿1｝,c＿｛i＿2｝,..,c＿｛i＿j｝はV＿iによって一意に決定される定数である。
【００３８】
先に説明したShamirの閾値法も線形秘密分散法であることが知られている。先に説明した技術を線形秘密分散法に用いる際、閾値ｋと分散情報数nの情報の代わりにアクセス構造に相当する情報を用いればよい。
【００３９】
一方、提案されている方式には、非特許文献１よりも演算処理が効率的な方式として、非特許文献２、非特許文献３および非特許文献４に開示されているものがある。そして、これら３つの文献に開示された方式を２種類に分類すると、非特許文献２および非特許文献３に開示された方式と、非特許文献４に開示された方式とに分けられる。以下にそれぞれの説明を行う。
【００４０】
非特許文献２および非特許文献３に開示されている処理装置は、秘密情報と、乱数と、秘密情報およびこれらの乱数をある関数に入力したときの出力とをコードとして生成する処理を行うコード生成装置と、コードを入力としてその正当性を検証するコード正当性検証装置とからなる。
【００４１】
これらの方式は、秘密情報そのものの乱数性とは関係なく、乱数Ｒはそれ自体が選ばれる元の集合から一様にランダムに選ばれることを条件として、秘密情報が選ばれる集合と乱数が選ばれる集合とコードの集合上の加算を+と表し、ある関数をM()と表すと、秘密情報s1と乱数r1について、s1とc1 = M(s1,r1)を取得した改ざん者がM(s1+s1', r1+r1')= M(s1,r1)+c1'を満たすs1',r1',c1'を生成するという改ざんを高い確率で検知可能となっている。
【００４２】
このような、秘密情報と一様な乱数の改ざんを検知するためのコード生成装置とコード検証装置の構成の一例を説明する。なお、この方式のコード生成装置を「改ざん検知コード生成装置」と称し、コード検証装置を「改ざん検知コード検証装置」と称する。
【００４３】
図１１Ａは非特許文献２または非特許文献３に開示されたコード生成装置の一構成例を示すブロック図である。図１１Ｂは非特許文献２または非特許文献３に開示されたコード検証装置の一構成例を示すブロック図である。
【００４４】
図１１Ａに示すように、改ざん検知コード生成装置100は、チェック用データ生成部101を有する。改ざん検知コード生成装置100は、秘密情報用データ集合Ｓの元である秘密情報sと、乱数情報用データ集合Ｒの元である乱数rとが入力されると、sとrを出力するとともに、sとrをチェック用データ生成部101に入力し、その結果としてチェック用データ集合Ｃの元であるcをチェック用データとして出力する。
【００４５】
また、図１１Ｂに示すように、改ざん検知コード検証装置200は、チェック用データ生成部101および同一性判定部201を有する。
【００４６】
改ざん検知コード検証装置200は、秘密情報用データ集合Ｓの元である秘密情報sと、乱数情報用データ集合Ｒの元である乱数rと、チェック用データ集合Ｃの元であるチェック用データcとが入力されると、sとrをチェック用データ生成部101に入力する。チェック用データ生成部101は、sとrが入力されると、c'を生成して出力する。同一判定部201は、チェック用データcと、チェック用データ生成部101の出力であるc'とが入力されると、判定処理を行う。同一判定部201は、判定処理の結果、c'=cである場合にはコードの整合性がとれていたことを表す記号を出力し、それ以外の場合はコードの整合性がとれていないことを表す記号を出力する。また、改ざん検知コード検証装置200は、秘密情報sを出力する。
【００４７】
非特許文献２の方式は、改ざんを検知できる確率を(1-ε)とすると、秘密情報が要素数sの集合から選ばれるとき、乱数が要素数1/εの集合の要素、関数の出力が要素数1/εの集合の要素となる。つまりコードはおよそ要素数がs*1/(ε^2)であるような集合の要素となる。この方式はsと1/εがほぼ等しい場合にのみ動作するというパラメータ上の条件がある。これは、εは1/2^80程度で十分であってもsが2^1000であればεも1/2^1000とする必要があることを表す。コードの長さに影響し、これらのパラメータは自由に設定できる方が好ましい。
【００４８】
具体的には、以下に説明する通りである。
【００４９】
非特許文献２に開示された方式は、pを素数とし、Z/pZを秘密情報の集合Sとしたとき、Sの要素であるsのコードとして、sと、Z/pZから一様ランダムに選択した要素rと、*をZ/pZ上の乗算として、s*r mod pをチェック用データとする方式である。
【００５０】
Z/pZの代わりにqを素数のべき乗としたとき、それぞれの集合をガロア体GF(q)の要素として乗算をガロア体上の乗算としてもよい。
【００５１】
非特許文献３の方式は、改ざんを検知できる確率を(1-ε)とすると、秘密情報が要素数sの集合から選ばれるとき、乱数が要素数1/εの集合の要素、関数の出力が要素数1/εの集合の要素となる。よって、コードはおよそ要素数がs*1/(ε^2)であるような集合の要素となる。つまり効率は非特許文献２の方式と同程度だが、sと1/εをほぼ独立に設定することができるという特徴がある。そのため、非特許文献２にあった問題が解決された方式であるといえる。
【００５２】
具体的には、以下に説明する通りである。
【００５３】
非特許文献３に開示された方式は、pを素数とし、Nを正の整数として、(Z/pZ)^Nを秘密情報の集合とする方式である。(Z/pZ)^Nの元をsまたは、(s＿1,s＿2,...,s＿N)と記す。また、(Z/pZ)^Nの代わりにガロア体GF(p^N)を用いてもよい。
【００５４】
このとき、(s＿1,s＿2,...,s＿N)のコードとして、sと、Z/pZから一様ランダムに選択した要素rと、*をZ/pZ上の乗算として、s＿1*r + s＿2*r^2 + ... + s＿｛N-1｝*r^｛N-1｝ + s＿｛N｝*r^｛N+1｝ mod p をチェック用データとする方式である。
【００５５】
Z/pZの代わりにqを素数のべき乗としたとき、それぞれの集合をガロア体GF(q)の要素として乗算をガロア体上の乗算としてもよい。
【００５６】
一方、非特許文献４に開示されている方式では、秘密情報の集合の要素を入力して秘密情報よりも大きな集合の部分集合の要素を出力する関数であって、異なる値が入力されたときは必ず異なる値が出力される関数を用いる方法である。このような関数をN()と表すとき、コードの生成装置は秘密情報sが入力されると、N(s)をコードとして出力する。コードの検証装置は、コードが入力されると、そのコードに対応する秘密情報の要素があるかどうかを調べ、秘密情報の要素がある場合にはその秘密情報に改ざんがなかったことを表す記号を出力し、それ以外の場合は秘密情報に改ざんがあったことを表す記号を出力する。この方式では、秘密情報が選ばれる集合から一様にランダムに選ばれることを条件としてコードの改ざんを高い確率で検知可能である。
【００５７】
具体的には、以下の通りである。
【００５８】
秘密情報の集合Sとして要素数がpである集合を用いる場合、N= (p(p-1) +1)としたときの｛0,...p(p-1)｝の要素数がpである部分集合Bであって、その部分集合の任意の異なる２つの要素s1とs2についてs1-s2 mod Nがすべて異なるという性質をもった部分集合を用いる方式である。
【００５９】
より具体的には、SのコードとしてＳの要素をBの要素に写像する関数を用いる方式である。この方式の検証方法はSからBに写像を行った際の逆を計算する関数を用いる。このとき、コードに対応するSの元がない場合には改ざんがあるものとみなす方式である。
【００６０】
また、非特許文献４に開示された方式は、改ざんを検知できる確率を(1-ε)とすると、秘密情報が要素数sの集合から選ばれるとき、関数の出力は要素数s*(1/ε)の集合の要素となる。また、sと1/εがほぼ等しい場合にのみ動作するというパラメータ上の条件がある。つまり、非特許文献２の方式と同様の課題を持つ方式であるといえる。ただし、非特許文献２や非特許文献３の方式を用いた場合に比べてコードの要素数の集合は1/εだけ少ないため演算処理の効率のよい方式となっていることがわかる。
【００６１】
このような、一様な秘密情報の改ざんを検知するためのコード生成装置とコード検証装置の構成の一例を説明する。なお、この方式のコード生成装置を「改ざん検知コード生成装置」と称し、コード検証装置を「改ざん検知コード検証装置」と称する。
【００６２】
図１２Ａは非特許文献４に開示されたコード生成装置の一構成例を示すブロック図である。図１２Ｂは非特許文献４に開示されたコード検証装置の一構成例を示すブロック図である。
【００６３】
図１２Ａに示すように、改ざん検知コード生成装置300は、秘密情報符号化部301を有する。改ざん検知コード生成装置300は、秘密情報用データ集合Ｓの元である秘密情報sが入力されると、sを秘密情報符号化部301に入力し、その出力のコード用データ集合Cの元であるcをコードとして出力する。
【００６４】
図１２Ｂに示すように、改ざん検知コード検証装置400は、秘密情報符号化部301に対応する秘密情報復号化部401と、復号結果判定部402とを有する。
【００６５】
改ざん検知コード検証装置400は、コード用データ集合Cの元であるcが入力されると、cを秘密情報復号化部401に入力し、秘密情報復号化部401の出力を復号結果判定部402に入力する。復号結果判定部402は、秘密情報復号化部401から受信した値が秘密情報用データ集合の要素である場合、その値をそのまま出力し、それ以外の場合、改ざんがあったことを表す記号を出力する。
【先行技術文献】
【非特許文献】
【００６６】
【非特許文献１】Adi Shamir. How to share a secret. Comm.ACM,22(11) 612-613(1979).
【非特許文献２】Sergio Cabello, Carles Padro', Germa'n Sa'ez: Secret Sharing Schemes with Detection of Cheaters for a General Access Structure. Des. Codes Cryptography 25(2): 175-188 (2002)
【非特許文献３】Toshinori Araki, Satoshi Obana: Flaws in Some Secret Sharing Schemes Against Cheating. ACISP 2007: 122-132
【非特許文献４】Wakaha Ogata. Kaoru Kurosawa. Douglas R Stinson:Optimum Secret Sharing Scheme Secure Against Cheating SIAM J.Discrete Math.,vol.20,no1,pages 79-95,2006
【発明の概要】
【発明が解決しようとする課題】
【００６７】
(k,n)閾値法を含む線形秘密分散法を用いて分散情報を生成する際、分散情報の改ざんを高確率で検知可能なコードを生成する方法として、検知性について非特許文献４の方式と同程度の効率であって、パラメータを自由に設定できるものがなかった。
【００６８】
本発明の目的は、分散情報の改ざんを高確率および効率的に検知可能とし、かつ、パラメータ設定の自由度を大きくした情報処理装置、コード生成方法、コード検証方法、およびその方法をコンピュータに実行させるためのプログラムを提供することである。
【課題を解決するための手段】
【００６９】
上記目的を達成するための本発明の情報処理装置は、
秘密情報sが入力されると、素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s＿1,...,s＿N｝で該秘密情報sを表し、s＿1*...*s＿N mod pをチェック用データvとして求めるチェック用データ生成部と、
前記秘密情報sと前記チェック用データvに対して線形秘密分散法を用いてそれぞれの分散符号化した値を生成するコード分散部と、
線形秘密分散法のアクセス構造に対応する秘密情報とチェック用データの符合語を含む復元対象の情報から秘密情報s'およびチェック用データv’を復元するコード復元部と、
前記秘密情報s'が前記チェック用データ生成部に入力されたときの出力であるチェック用データv''と前記チェック用データv'とが等しいか否かを判定し、該チェック用データv'とv''が等しい場合にはデータが改ざんされていないと判定し、該チェック用データv'とv''が等しくない場合にはデータが改ざんされていると判定する同一性判定部と、
を有する構成である。
【００７０】
また、本発明のコード生成方法は、線形秘密分散法により生成される情報の改ざんを検知するためのコード生成方法であって、
秘密情報sが入力されると、素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s＿1,...,s＿N｝で該秘密情報sを表し、s＿1*...*s＿N mod pをチェック用データvとして求め、
前記秘密情報sと前記チェック用データvに対して線形秘密分散法を用いてそれぞれの分散符号化した値を生成するものである。
【００７１】
また、本発明のコード検証方法は、線形秘密分散法により生成される情報の改ざんを検知するためのコード検証方法であって、
線形秘密分散法のアクセス構造に対応する秘密情報とチェック用データの符合語を含む復元対象の情報から秘密情報s'およびチェック用データv’を復元し、
素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s'＿1,...,s'＿N｝で前記秘密情報s'を表し、s'＿1*...*s'＿N mod pをチェック用データv''として求め、
前記チェック用データv''と前記チェック用データv'とが等しいか否かを判定し、該チェック用データv'とv''が等しい場合にはデータが改ざんされていないと判定し、該チェック用データv'とv''が等しくない場合にはデータが改ざんされていると判定するものである。
【００７２】
また、本発明のプログラムは、線形秘密分散法により生成される情報の改ざんを検知するためのコードを生成するコンピュータに実行させるためのプログラムであって、
秘密情報sが入力されると、素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s＿1,...,s＿N｝で該秘密情報sを表し、s＿1*...*s＿N mod pをチェック用データvとして求め、
前記秘密情報sと前記チェック用データvに対して線形秘密分散法を用いてそれぞれの分散符号化した値を生成する処理を前記コンピュータに実行させるものである。
【００７３】
さらに、本発明のプログラムは、線形秘密分散法により生成される情報の改ざんを検知するためのコードを検証するコンピュータに実行させるためのプログラムであって、
線形秘密分散法のアクセス構造に対応する秘密情報とチェック用データの符合語を含む復元対象の情報から秘密情報s'およびチェック用データv’を復元し、
素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s'＿1,...,s'＿N｝で前記秘密情報s'を表し、s'＿1*...*s'＿N mod pをチェック用データv''として求め、
前記チェック用データv''と前記チェック用データv'とが等しいか否かを判定し、該チェック用データv'とv''が等しい場合にはデータが改ざんされていないと判定し、該チェック用データv'とv''が等しくない場合にはデータが改ざんされていると判定する処理を前記コンピュータに実行させるものである。
【発明の効果】
【００７４】
本発明によれば、線形秘密分散法を用いた分散情報の改ざんを高確率および効率的に検知可能とし、かつ、パラメータ設定の自由度を大きくすることができる。
【図面の簡単な説明】
【００７５】
【図１】本実施形態の情報処理装置の一構成例を示すブロック図である。
【図２】図１に示した情報処理装置の具体的構成例を示すブロック図である。
【図３Ａ】本実施形態の情報処理装置に含まれるコード生成装置の一構成例を示すブロック図である。
【図３Ｂ】本実施形態の情報処理装置に含まれるコード検証装置の一構成例を示すブロック図である。
【図４】図３Ａに示したコード生成装置の動作手順を示すフローチャートである。
【図５】図３Ｂに示したコード検証装置の動作手順を示すフローチャートである。
【図６】本実施形態による、分散情報を生成する手順を示すフローチャートである。
【図７】本実施形態による、分散情報を復元する手順を示すフローチャートである。
【図８Ａ】関連する分散情報生成装置の一構成例を示すブロック図である。
【図８Ｂ】関連する復元装置の一構成例を示すブロック図である。
【図９】図８Ａに示した分散情報生成装置の動作手順を示すフローチャートである。
【図１０】図８Ｂに示した復元装置の動作手順を示すフローチャートである。
【図１１Ａ】非特許文献２または非特許文献３に開示されたコード生成装置の一構成例を示すブロック図である。
【図１１Ｂ】非特許文献２または非特許文献３に開示されたコード検証装置の一構成例を示すブロック図である。
【図１２Ａ】非特許文献４に開示されたコード生成装置の一構成例を示すブロック図である。
【図１２Ｂ】非特許文献４に開示されたコード検証装置の一構成例を示すブロック図である。
【発明を実施するための形態】
【００７６】
本実施形態について図面を参照して詳細に説明する。図１は本実施形態の情報処理装置の一構成例を示すブロック図である。
【００７７】
図１に示すように、本実施形態の情報処理装置10は、記憶部35と、制御部25とを有する。制御部25は、コード分散部702と、コード復元部801と、後述する秘密情報剰余算出部501および同一性判定部601とを有する。
【００７８】
図２は図１に示した情報処理装置の具体的構成例を示すブロック図である。
【００７９】
図２に示すように、プログラムにしたがって処理を実行するＣＰＵ（Central Processing Unit）11と、ＣＰＵ11に供給するプログラムおよび演算処理過程の情報を一時的に保存するためのＲＡＭ（Random Access Memory）13と、プログラムが予め格納された主記憶部12と、秘密情報、閾値および分散情報数などの演算処理に必要な情報が格納されたデータ蓄積部14と、記憶部35の各記憶領域間のデータ転送を制御するメモリ制御インタフェイス部15と、情報を入力するための入力部20と、演算結果を出力するための出力部30と、入力部20および出力部30の入出力制御を行うI/Oインタフェイス部16とを有する。これらの構成は、バス18を介して接続されている。
【００８０】
プログラムには、コード分散部702、同一性判定部601、コード復元部801、および秘密情報剰余算出部501の機能をＣＰＵ11に実行させるための処理手順が書き込まれている。ＣＰＵ11がプログラムを実行することで、コード分散部702、同一性判定部601、コード復元部801、および秘密情報剰余算出部501が情報処理装置10に仮想的に構成される。
【００８１】
なお、プログラムに、秘密情報符号化部301、秘密情報復号化部401および復号結果判定部402の機能をＣＰＵ11に実行させるための処理手順がさらに書き込まれていてもよい。
【００８２】
なお、データ蓄積部14は、情報処理装置10内に設けていなくてもよく、情報処理装置10とは別に設けていてもよい。また、データ蓄積部14は、記憶部901を有する保管装置900としてもよい。
【００８３】
また、演算処理に必要なプログラムやデータを格納した記憶媒体を入力部20に装着し、それらの情報を入力部20を介して情報処理装置10に入力するようにしてもよい。記憶部媒体には、例えば、磁気ディスク、半導体メモリ、光ディスクなどがあるが、その他の記録媒体であってもよい。
【００８４】
次に、チェック用データに相当するコードの生成と検証に注目して、図１に示した情報処理装置10が実行する情報改ざん検知方法を説明する。本実施形態で処理対象となる秘密情報は、例えば、文書の暗号化のための秘密鍵となる素数である。この場合、秘密情報の元の集合は素数の集合となる。また、ここでは、情報処理装置10を、コードの生成処理を行うコード生成装置とコードの検証処理を行うコード検証装置の２つの装置に分けて説明する。
【００８５】
秘密情報ｓは、pを素数としたとき、２以上の整数Nの要素数で｛1, ... ,p-1｝の要素の列に符号化されて秘密情報剰余算出部501に入力されるものとする。また、チェック用データの集合として｛1, ... ,p-1｝を用いる。
【００８６】
また、素数pはデータ蓄積部14に予め記録されていてもよく、秘密情報剰余算出部501に設けられたメモリ（不図示）に予め記録されていてもよく、秘密情報剰余算出部501に外部から入力されてもよい。秘密情報剰余算出部501への入力は、コード生成装置500への入力で実行される。以下では、説明を省略するが、素数pが秘密情報剰余部501のメモリ（不図示）に記録されているものとする。
【００８７】
また、秘密情報の符号化処理はコード生成装置500への入力前に行われてもよく、符号化処理の機能をコード生成装置500に予め備え、コード生成装置500が入力される秘密情報の符号化処理を実行してもよい。以下では、符号化された秘密情報がコード生成装置500に入力される場合で説明する。
【００８８】
また、本実施形態では、秘密分散法として非特許文献４に記載されている(k,n)閾値法を適用するが、秘密分散法は線形秘密分散法であれば適用可能である。
【００８９】
図３Ａは本実施形態の情報処理装置に含まれるコード生成装置の一構成例を示すブロック図である。図３Ｂは本実施形態の情報処理装置に含まれるコード検証装置の一構成例を示すブロック図である。本実施形態の情報処理装置10は、コード生成装置500およびコード検証装置600を含む構成である。
【００９０】
図３Ａに示すように、コード生成装置500は、秘密情報剰余算出部501を有する構成である。秘密情報剰余算出部501はチェック用データ生成部に相当する。コード生成装置500は、秘密情報用データ集合Ｓの元である秘密情報s=(s＿1,...,s＿N)が入力されると、入力されたsと、秘密情報剰余部501の出力であるチェック用データ集合Ｃの元を出力する。
【００９１】
秘密情報剰余算出部501は、s=(s＿1,...,s＿N)が入力されると、c = s＿1* s＿2* ... *s＿N mod pを計算し、cを出力する。
【００９２】
ここでは、秘密情報s=(s＿1,...,s＿N)が秘密情報剰余部501に入力される場合としているが、秘密情報sが入力されると、秘密情報剰余部501が、プログラムにしたがって、素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列(s＿1,...,s＿N)で表す処理を実行してもよい。
【００９３】
次に、コード検証装置600について説明する。
【００９４】
図３Ｂに示すように、コード検証装置600は、上述した秘密情報剰余算出部501と、同一性判定部601とを有する。コード検証装置600は、秘密情報用データ集合Ｓの元である秘密情報s'=(s'＿1,...,s'＿N)とチェック用データ集合Ｃの元c'が入力されると、同一性判定装置601の出力である検証結果とs'を出力する。
【００９５】
秘密情報剰余算出部501は、s' = (s'＿1,...,s'＿N)が入力されると、上述したように、c'' = s'＿1*s'＿2*...*s'＿N mod pを計算する処理を行い、c''を同一性判定部601に渡す。
【００９６】
同一性判定部601は、秘密情報剰余算出部501の出力であるc''を秘密情報剰余算出部501から受け取り、コード検証装置600に入力されたc'を受け取ると、c' ＝ c''が満たされるか否かをチェックする。その結果、c' ＝ c''である場合、同一性判定部601は、データが改ざんされていないと判定し、改ざんが検出されなかったことを表す記号を出力する。その反対に、c' ≠ c''である場合、同一性判定部601は、データが改ざんされていると判定し、改ざんの検出を表す記号を出力する。
【００９７】
次に、コード生成装置500の動作手順を、図４のフローチャートを参照して説明する。
【００９８】
秘密情報用データ集合Ｓの元s=(s＿1,...,s＿N)がコード生成装置500に入力される(ステップC1)。秘密情報剰余算出部501は、s=(s＿1,...,s＿N)が入力されると、c = s＿1* s＿2* ... *s＿N mod pを算出する（ステップC2）。続いて、コード生成装置500は、秘密情報剰余算出部501の算出結果であるcとコード生成装置500への入力であるsを出力する（ステップC3）。
【００９９】
その後、秘密情報sおよびチェック用データcの情報が分散情報に埋め込まれる際には、図１に示したコード分散部702が、秘密情報sとチェック用データcに対して線形秘密分散法を用いてそれぞれの分散符号化した値を生成するが、ここでは、その詳細な説明を省略する。
【０１００】
次に、コード検証装置600の動作手順を、図５のフローチャートを参照して説明する。
【０１０１】
秘密情報用データ集合Ｓの元s'=(s'＿1,...,s'＿N)と、チェック用データ集合Ｃの元であるc'がコード検証装置600に入力される(ステップD1)。秘密情報剰余算出部501は、s'=(s'＿1,...,s'＿N)が入力されると、c''=s'＿1*s'＿2*...*s'＿N mod pを算出する(ステップD2）。
【０１０２】
ステップD1でコード検証装置600に入力されたc'とステップD2で算出されたc''とが同一性判定部601に入力される（ステップD3）。同一性判定部601はc' = c''が満たされるか否かをチェックする（ステップD4）。その結果、c' ＝ c''である場合、同一性判定部601は、データが改ざんされていないと判定し、改ざんが検出されなかったことを表す記号を出力する（ステップD5）。ステップD4でc' ≠ c''である場合、同一性判定部601は、データが改ざんされていると判定し、改ざんの検出を表す記号を出力する（ステップD6）。
【０１０３】
なお、ステップD1の前に、図１に示したコード復元部801が線形秘密分散法のアクセス構造に対応する秘密情報とチェック用データの符合語を含む復元対象の情報から秘密情報s'およびチェック用データv’を復元し、これらの情報がステップD1でコード検証装置600に入力されるが、ここでは、その詳細な説明を省略している。
【０１０４】
ここまで、チェック用データのコードに注目して説明したが、図１に示した情報処理装置10による、チェック用データを分散情報に埋め込む場合の処理方法について説明する。
【０１０５】
ここでは、コード分散部702は分散符号語生成部（不図示）を含み、コード復元部801は符号語復元部（不図示）を含むものとする。これらの構成もＣＰＵ11がプログラムを実行することで仮想的に構成されるものである。
【０１０６】
はじめに、秘密情報に対して分散符号化処理を行って、分散情報を生成する手順を説明する。図６は、本実施形態による、分散情報を生成する手順を示すフローチャートである。
【０１０７】
図６に示すように、秘密情報剰余算出部501は、秘密情報sが入力されると、秘密情報sをある素数pを用いてsを1からp-1の値の列｛s＿1,...,s＿N｝と表し、s＿1*...*s＿N mod pをチェック用データvとして求める（ステップE1）。
【０１０８】
その後、分散符号語生成部（不図示）は、秘密情報sとチェック用データvが埋め込まれた（k-1）次多項式Fを生成し、互いに異なるn個の値x1乃至xnを多項式Fに入力したときの、入力と出力との組である(x1, F(x1))乃至(xn, F(xn))を分散符号語情報として生成し、分散符号語情報を出力する（ステップE2）。
【０１０９】
次に、情報処理装置10に復元対象となる情報が入力されたとき、その情報が改ざんされているか否かを判定する手順を説明する。図７は、本実施形態による、分散情報を復元する手順を示すフローチャートである。
【０１１０】
符号語復元部（不図示）は、k組分の分散符号語情報として(x1', F＿1')乃至(xk', F＿k')が入力されると、これらの点を通る(k-1)次多項式F'を生成し、多項式F'に埋め込まれた秘密情報s'=｛s'＿1,...,s'＿N｝とチェック用データv'を読み出して出力する（ステップF1）。秘密情報剰余算出部501は、s'が入力されると、s'＿1*...*s'＿N mod pをチェック用データv''として求める（ステップF2）。
【０１１１】
同一性判定部601は、チェック用データv'とv''が等しいかどうかを判定する（ステップF3）。その結果、v'とv''が等しい場合、同一性判定部601はデータが改ざんされていない旨の検証結果を出力し（ステップF4）、v'とv''が等しくない場合、同一性判定部601はデータが改ざんされている旨の検証結果を出力する（ステップF5）。
【実施例１】
【０１１２】
本実施例のコード生成装置500は、入力される秘密情報を用いて、分散情報の改ざん検知コードを生成して出力する。本実施例のコード検証装置600は、入力されるコードの正当性を検証する。
【０１１３】
本実施例では、秘密情報sを複数の要素の組s= (s＿｛0,1｝,...,s＿｛0,N｝)によって表す。Nは２以上の数であって、各要素s＿｛0,i｝(i = 1,...,N)はpを素数として、1,...,p-1とする。
【０１１４】
本実施例のコード生成装置500は、秘密情報sが入力されると、実施形態で説明したように演算を行い、秘密情報sを出力するとともに、c= s＿｛0,1｝*s＿｛0,2｝*...+s＿｛0,N｝ mod pをコードとして出力する。生成されたコードは分散情報に埋め込まれる。
【０１１５】
一方、コード検証装置600は、収集された分散情報から読み出された秘密情報s'= (s'＿｛0,1｝,...,s'＿｛0,N｝)とコードc'が入力されると、c''= s'＿｛0,1｝*s'＿｛0,2｝*...+s'＿｛0,N｝ mod pを求める。そして、コード検証装置600は、コードc'とc''が等しいか否かを判定し、c'= c''である場合にはデータが改ざんされていないと判定し、c'≠ c''である場合にはデータが改ざんされていると判定し、検証結果を出力する。
【０１１６】
ここで改ざん者が秘密情報s'をs＿｛1,1｝,...,s＿｛1,N｝だけ、コードcをc'''だけ改ざんする場合を考える。
このとき、(s＿｛0,1｝+s＿｛1,1｝)*(s＿｛0,2｝+s＿｛1,2｝)*...*(s＿｛0,N｝+s＿｛1,N｝) = s＿｛0,1｝*s＿｛0,2｝*...*s＿｛0,N｝ + s＿｛0,1｝*s＿｛0,2｝*...*s＿｛1,N｝ + ... + s＿｛1,1｝*s＿｛1,2｝*...*s＿｛1,N｝となっている。
【０１１７】
つまり、どのように改ざんを行っても、s＿｛0,1｝*s＿｛0,2｝*...*s＿｛1,N｝のように未知の秘密情報を含む項が存在する。
【０１１８】
そのため、改ざん者は、改ざんの結果がコードc'''に対してどのような影響を及ぼすかは秘密情報の確率分布に従って推測するよりなく、例えば秘密情報が一様な分布に従ってランダムに選ばれる場合には、改ざんした結果が予想した値と等しくなる確率は1/(p-1)となる。
【０１１９】
この場合、秘密情報の集合の要素数は(p-1)*Nとなり、改ざんの確率は1/p程度となる。
コードの集合の要素数はおよそp*(N+1)であり、検知性について非特許文献４の方式と同程度である。これに加え、素数pのサイズとNをほぼ独立に設定することが可能であるので、パラメータが自由に設定可能である。
【０１２０】
よって、本実施形態では、(k,n)閾値法を含む線形秘密分散法による分散情報の改ざんを高確率および効率的に検知可能とし、かつ、パラメータ設定の自由度を大きくすることができる。
【産業上の利用可能性】
【０１２１】
本発明を秘密鍵などの機密情報の分散管理に利用できる。
【符号の説明】
【０１２２】
１０ 情報処理装置
１１ ＣＰＵ
１２ 主記憶部
１３ ＲＡＭ
１４ データ蓄積部
１５ メモリ制御インタフェイス部
１６ I/Oインタフェイス部
２０ 入力部
２５ 制御部
３０ 出力部
３５ 記憶部
５０１ 秘密情報剰余算出部
６０１ 同一性判定部
７０２ コード分散部
８０１ コード復元部
【技術分野】
【０００１】
本発明は、データの改ざんを検知するための、情報処理装置、コード生成方法、コード検証方法、およびその方法をコンピュータに実行させるためのプログラムに関する。
【背景技術】
【０００２】
秘密にしておきたい情報（以下、秘密情報と称する）を保管する場合、秘密情報の紛失だけでなく、破壊の脅威、盗難の脅威がある。前者の脅威に対しては秘密情報のコピーを作成することが有効であるが、後者の盗難に対する脅威が増してしまう。
【０００３】
このような問題を解決する手段の１つとして、秘密分散法が知られている。秘密分散法の１つである(k,n)閾値法について簡単に説明する。秘密情報をn個の分散情報に符号化する。n個の分散情報のうち任意のk個以上の分散情報を集めれば、秘密情報を完全に復元できるが、k-1個以下の分散情報を集めても、元の秘密情報に関する情報をまったく得られない。したがって、k-1個までの分散情報が盗難にあったとしても秘密情報が他人に漏れることがなく、n-k個までの分散情報が破壊されても、秘密情報を復元できる。
【０００４】
(k, n)閾値法の一例が、非特許文献１に開示されている。この非特許文献１に開示された、shamirの提案する方式が効率的であるため、この方式が広く用いられている。
【０００５】
非特許文献１の方式は、素数または素数のべき乗pに対する有限体GF(p)を秘密情報のデータ集合として用い、秘密情報sを定数項に持つGF(p)上のランダムな(k-1)次多項式f(x)上の点、(x＿1,f(x＿1)),...,(x＿n,f(x＿n))を分散情報とする方式である。k個の分散情報からk-1次の多項式は一意に復元でき、f(0)である秘密情報sを復元することができる。また、k-1個以下の分散情報からはf(0)を定めることはできず、秘密情報sに関する情報は一切漏れない。秘密情報を埋め込む箇所はf(0)以外の任意の箇所でもよい。また、多項式の係数などでもよい。
【０００６】
また、xi(i=1,...,n)は互いに異なる値であればよい。
【０００７】
このような(k, n)閾値法を用いることで対処できる脅威もあるが、以下に示すような脅威も存在する。
【０００８】
(k, n)閾値法において分散情報の作成、配付が正しく行われ、その後、秘密情報を復元するために分散情報を複数集める状況を考える。
【０００９】
このとき、分散情報を要求された側が配付された値を改竄することなく渡すとは限らない。また、単純な(k, n)閾値法を用いる場合、改竄された分散情報を用いて復元された値は、秘密情報と異なる値になってしまう可能性を持っている。
【００１０】
現実の状況を例示すると、遺言状を分散したデータを作成して複数の子孫に渡しておいたところ、データが改ざんされ、一部の子孫にとって都合のよい内容に書き換えられてしまうということが挙げられる。
【００１１】
このような攻撃が非特許文献１の方式に行われた場合、秘密情報をsとし、有限体上の加算を+と書くと、改ざん者は、s+s'が復元されるような改ざんを行うことができることが知られている。そのため、先の遺言状の例のような改ざんが行われた場合には、その事実を検知できるような方式が望ましい。
【００１２】
このような機能を、非特許文献１に開示されている(k,n)閾値法に付与する方法は様々知られている。演算処理が効率的な方法としては、以下の方法が知られている。この方法について、秘密情報を分散する分散フェーズと、秘密情報を復元する復元フェーズに分けて概要を記述する。
【００１３】
［分散フェーズ］
１．秘密情報になんらかの処理を適用する。なお、処理を適用した後の値をコードと呼ぶ。
２．コードを既存の(k,n)閾値法で分散する。
【００１４】
［復元フェーズ］
１．コードを復元する。
２．コードの正当性を調べる。ここで正当でないものであると判明した場合、改ざんがあったものとする。
【００１５】
このような構成を採用し、秘密情報を入力としてコードを出力する装置をGenCode()とし、生成されたコードを入力としてそのコードが正当性なものであるかどうかを出力する関数をVerCode()とし、ある秘密情報sについてのコードをcとする。このとき、VerCode(c+c')が正当なものであるという出力を行うようなc'を、改ざん者が生成することができる確率は十分に低い。それだけでなく、コードが正当なときには、必ずコードに対応する秘密情報を出力するものを用いることで、上述の(k,n)閾値法に対する不正が高い確率で検知可能となる。
【００１６】
この方法を実行する情報処理装置について説明する。
【００１７】
図８Ａは関連する分散情報生成装置の一構成例を示すブロック図である。図８Ｂは関連する復元装置の一構成例を示すブロック図である。
【００１８】
図８Ａおよび図８Ｂに示すように、分散情報生成装置700および復元装置800のそれぞれには、分散情報を格納するための複数の保管装置900が接続されている。
【００１９】
はじめに、図８Ａを参照して、分散情報生成装置700の構成を説明する。
【００２０】
分散情報生成装置700は、コード生成部701およびコード分散部702を有する。分散情報生成装置700は、秘密情報用データ集合Sの元と、閾値ｋと、分散情報数nと、保管先装置指定データとが入力されると、保管先装置指定データの指定するn個の保管装置900のそれぞれに対し、分散コードデータ集合BSの元である分散コード情報を格納する。
【００２１】
コード生成部701は、秘密情報用データ集合Sの元sが入力されると、コード情報用データ集合Ｃの元cを出力する。
【００２２】
コード分散部702は、集合Cの元と、閾値ｋと、分散情報数nと、保管先装置指定データとが入力されると、保管先装置指定データの指定するn個の保管装置900のそれぞれに対して分散コードデータ集合BSの元を格納する。
【００２３】
次に、図８Ｂを参照して、復元装置800の構成を説明する。
【００２４】
復元装置800は、コード復元部801およびコード正当性検証部802を有する。復元装置800は、集合Cの元と、閾値ｋと、分散情報数nと、保管先装置指定データとが入力されると、複数の保管装置900から、それぞれが記憶するBSの元を読み出し、秘密情報用データ集合Sの元のデータ、または、不正の検出を表す記号を出力する。
【００２５】
コード復元部801は、集合Cの元と、閾値ｋと、保管先装置指定データとが入力されると、複数の保管装置900から、それぞれの記憶部901が記憶するBSの元を読み出し、Cの元を出力する。
【００２６】
コード正当性検証部802は、Ｃの元が入力されると、Ｓの元のデータ、またはコードが不正であったことを表すデータを出力する。なお、保管装置900は、分散コード用データ集合BCの元を記憶する記憶部901を有する。
【００２７】
次に、分散情報生成装置700の動作手順を、図９のフローチャートを参照して説明する。
【００２８】
閾値kと、分散情報数nと、保管先装置指定データと、秘密情報用データ集合Ｓの元sが分散情報生成装置700に入力される(ステップA1)。
【００２９】
コード生成部701は、入力されたsに対応するコード情報用データ集合Ｃの元であるcを出力する(ステップA2)。
【００３０】
コード分散部702は、閾値kと、分散情報数nと、保管先装置指定データと、コード生成部701の出力であるcとが入力されると、cを(k,n)閾値法で分散符号化し、分散符号化されたcを、保管先装置指定データの指定する保管装置900の記憶部901に格納する(ステップA3)。
【００３１】
次に、復元装置800の動作手順を、図１０のフローチャートを参照して説明する。
【００３２】
閾値kと分散情報数nが復元装置800に入力される(ステップB1)。コード復元部801は、ｋ機以上の複数の保管装置900の記憶部901からデータを読み出す(ステップB2)。続いて、コード復元部801は、読み出したデータと閾値kとから、コード分散部702の分散符号化方法に対応する復元方法を用いて復元処理を行った結果であるＣの元c'を出力する(ステップB3)。
【００３３】
コード正当性検証部802は、コード復元部801からc'を受け取ると、c'の正当性を検証する処理を行い、正当なコードであった場合には、c'に対応するSの元s'を出力し、それ以外の場合には、不正の検出を表す記号を出力する（ステップB4）。
【００３４】
なお、GenCodeの入力には、秘密情報以外の情報を入力する場合もある。また、cは有限体の要素がひとつであるとは限らず、複数の異なる有限体の要素からなる場合もある。例えば、３つの要素からなる場合を考えるとc=(c1,c2,c3)となる場合もある。このとき、c=(c1,c2,c3)とc'=(c1',c2',c3')に対し、+をc1,c2,c3の各要素に対応する有限体上で定義されている加算であるとすると、c+c'は(c1+c1',c2+c2',c3+c3')を表しているものとする。
【００３５】
また、コードの集合が小さければ小さいほど分散情報のサイズが小さく、秘密情報を分散して保管する場合に必要とする記憶容量が少なくて済み、好ましい。
【００３６】
また、これまで述べた技術を、先に説明したShamirの閾値法以外にも適用可能である。例えば、線形秘密分散法と呼ばれる秘密分散法に対してもこれまでに述べた技術を適用できることが知られている。
【００３７】
線形秘密分散法とは，次のような性質を持った秘密分散法である。なお、秘密を復元可能な分散情報の集合を要素とする集合をアクセス構造と呼ぶことにする。秘密情報は有限体Fの元であるとする。
1. 分散情報(v＿1,...,v＿n) が(v＿1, v＿2, ... ,v＿n)= (s, r＿1, ... ,r＿｛t-1｝)M のようにF 上の固定のt*n行列Mとランダムに選ばれたF の要素r＿i によって生成される。
2. アクセス構造に含まれる分散情報の集合V＿i = ｛v＿｛i＿1｝,v＿｛i＿2｝,...,v＿｛i＿j｝｝から秘密情報を、
s =c＿｛i＿1｝*v＿｛i＿1｝ + c＿｛i＿2｝*v＿｛i＿2｝ + ... + c＿｛i＿j｝*v＿｛i＿j｝のように計算できる。ただし、c＿｛i＿1｝,c＿｛i＿2｝,..,c＿｛i＿j｝はV＿iによって一意に決定される定数である。
【００３８】
先に説明したShamirの閾値法も線形秘密分散法であることが知られている。先に説明した技術を線形秘密分散法に用いる際、閾値ｋと分散情報数nの情報の代わりにアクセス構造に相当する情報を用いればよい。
【００３９】
一方、提案されている方式には、非特許文献１よりも演算処理が効率的な方式として、非特許文献２、非特許文献３および非特許文献４に開示されているものがある。そして、これら３つの文献に開示された方式を２種類に分類すると、非特許文献２および非特許文献３に開示された方式と、非特許文献４に開示された方式とに分けられる。以下にそれぞれの説明を行う。
【００４０】
非特許文献２および非特許文献３に開示されている処理装置は、秘密情報と、乱数と、秘密情報およびこれらの乱数をある関数に入力したときの出力とをコードとして生成する処理を行うコード生成装置と、コードを入力としてその正当性を検証するコード正当性検証装置とからなる。
【００４１】
これらの方式は、秘密情報そのものの乱数性とは関係なく、乱数Ｒはそれ自体が選ばれる元の集合から一様にランダムに選ばれることを条件として、秘密情報が選ばれる集合と乱数が選ばれる集合とコードの集合上の加算を+と表し、ある関数をM()と表すと、秘密情報s1と乱数r1について、s1とc1 = M(s1,r1)を取得した改ざん者がM(s1+s1', r1+r1')= M(s1,r1)+c1'を満たすs1',r1',c1'を生成するという改ざんを高い確率で検知可能となっている。
【００４２】
このような、秘密情報と一様な乱数の改ざんを検知するためのコード生成装置とコード検証装置の構成の一例を説明する。なお、この方式のコード生成装置を「改ざん検知コード生成装置」と称し、コード検証装置を「改ざん検知コード検証装置」と称する。
【００４３】
図１１Ａは非特許文献２または非特許文献３に開示されたコード生成装置の一構成例を示すブロック図である。図１１Ｂは非特許文献２または非特許文献３に開示されたコード検証装置の一構成例を示すブロック図である。
【００４４】
図１１Ａに示すように、改ざん検知コード生成装置100は、チェック用データ生成部101を有する。改ざん検知コード生成装置100は、秘密情報用データ集合Ｓの元である秘密情報sと、乱数情報用データ集合Ｒの元である乱数rとが入力されると、sとrを出力するとともに、sとrをチェック用データ生成部101に入力し、その結果としてチェック用データ集合Ｃの元であるcをチェック用データとして出力する。
【００４５】
また、図１１Ｂに示すように、改ざん検知コード検証装置200は、チェック用データ生成部101および同一性判定部201を有する。
【００４６】
改ざん検知コード検証装置200は、秘密情報用データ集合Ｓの元である秘密情報sと、乱数情報用データ集合Ｒの元である乱数rと、チェック用データ集合Ｃの元であるチェック用データcとが入力されると、sとrをチェック用データ生成部101に入力する。チェック用データ生成部101は、sとrが入力されると、c'を生成して出力する。同一判定部201は、チェック用データcと、チェック用データ生成部101の出力であるc'とが入力されると、判定処理を行う。同一判定部201は、判定処理の結果、c'=cである場合にはコードの整合性がとれていたことを表す記号を出力し、それ以外の場合はコードの整合性がとれていないことを表す記号を出力する。また、改ざん検知コード検証装置200は、秘密情報sを出力する。
【００４７】
非特許文献２の方式は、改ざんを検知できる確率を(1-ε)とすると、秘密情報が要素数sの集合から選ばれるとき、乱数が要素数1/εの集合の要素、関数の出力が要素数1/εの集合の要素となる。つまりコードはおよそ要素数がs*1/(ε^2)であるような集合の要素となる。この方式はsと1/εがほぼ等しい場合にのみ動作するというパラメータ上の条件がある。これは、εは1/2^80程度で十分であってもsが2^1000であればεも1/2^1000とする必要があることを表す。コードの長さに影響し、これらのパラメータは自由に設定できる方が好ましい。
【００４８】
具体的には、以下に説明する通りである。
【００４９】
非特許文献２に開示された方式は、pを素数とし、Z/pZを秘密情報の集合Sとしたとき、Sの要素であるsのコードとして、sと、Z/pZから一様ランダムに選択した要素rと、*をZ/pZ上の乗算として、s*r mod pをチェック用データとする方式である。
【００５０】
Z/pZの代わりにqを素数のべき乗としたとき、それぞれの集合をガロア体GF(q)の要素として乗算をガロア体上の乗算としてもよい。
【００５１】
非特許文献３の方式は、改ざんを検知できる確率を(1-ε)とすると、秘密情報が要素数sの集合から選ばれるとき、乱数が要素数1/εの集合の要素、関数の出力が要素数1/εの集合の要素となる。よって、コードはおよそ要素数がs*1/(ε^2)であるような集合の要素となる。つまり効率は非特許文献２の方式と同程度だが、sと1/εをほぼ独立に設定することができるという特徴がある。そのため、非特許文献２にあった問題が解決された方式であるといえる。
【００５２】
具体的には、以下に説明する通りである。
【００５３】
非特許文献３に開示された方式は、pを素数とし、Nを正の整数として、(Z/pZ)^Nを秘密情報の集合とする方式である。(Z/pZ)^Nの元をsまたは、(s＿1,s＿2,...,s＿N)と記す。また、(Z/pZ)^Nの代わりにガロア体GF(p^N)を用いてもよい。
【００５４】
このとき、(s＿1,s＿2,...,s＿N)のコードとして、sと、Z/pZから一様ランダムに選択した要素rと、*をZ/pZ上の乗算として、s＿1*r + s＿2*r^2 + ... + s＿｛N-1｝*r^｛N-1｝ + s＿｛N｝*r^｛N+1｝ mod p をチェック用データとする方式である。
【００５５】
Z/pZの代わりにqを素数のべき乗としたとき、それぞれの集合をガロア体GF(q)の要素として乗算をガロア体上の乗算としてもよい。
【００５６】
一方、非特許文献４に開示されている方式では、秘密情報の集合の要素を入力して秘密情報よりも大きな集合の部分集合の要素を出力する関数であって、異なる値が入力されたときは必ず異なる値が出力される関数を用いる方法である。このような関数をN()と表すとき、コードの生成装置は秘密情報sが入力されると、N(s)をコードとして出力する。コードの検証装置は、コードが入力されると、そのコードに対応する秘密情報の要素があるかどうかを調べ、秘密情報の要素がある場合にはその秘密情報に改ざんがなかったことを表す記号を出力し、それ以外の場合は秘密情報に改ざんがあったことを表す記号を出力する。この方式では、秘密情報が選ばれる集合から一様にランダムに選ばれることを条件としてコードの改ざんを高い確率で検知可能である。
【００５７】
具体的には、以下の通りである。
【００５８】
秘密情報の集合Sとして要素数がpである集合を用いる場合、N= (p(p-1) +1)としたときの｛0,...p(p-1)｝の要素数がpである部分集合Bであって、その部分集合の任意の異なる２つの要素s1とs2についてs1-s2 mod Nがすべて異なるという性質をもった部分集合を用いる方式である。
【００５９】
より具体的には、SのコードとしてＳの要素をBの要素に写像する関数を用いる方式である。この方式の検証方法はSからBに写像を行った際の逆を計算する関数を用いる。このとき、コードに対応するSの元がない場合には改ざんがあるものとみなす方式である。
【００６０】
また、非特許文献４に開示された方式は、改ざんを検知できる確率を(1-ε)とすると、秘密情報が要素数sの集合から選ばれるとき、関数の出力は要素数s*(1/ε)の集合の要素となる。また、sと1/εがほぼ等しい場合にのみ動作するというパラメータ上の条件がある。つまり、非特許文献２の方式と同様の課題を持つ方式であるといえる。ただし、非特許文献２や非特許文献３の方式を用いた場合に比べてコードの要素数の集合は1/εだけ少ないため演算処理の効率のよい方式となっていることがわかる。
【００６１】
このような、一様な秘密情報の改ざんを検知するためのコード生成装置とコード検証装置の構成の一例を説明する。なお、この方式のコード生成装置を「改ざん検知コード生成装置」と称し、コード検証装置を「改ざん検知コード検証装置」と称する。
【００６２】
図１２Ａは非特許文献４に開示されたコード生成装置の一構成例を示すブロック図である。図１２Ｂは非特許文献４に開示されたコード検証装置の一構成例を示すブロック図である。
【００６３】
図１２Ａに示すように、改ざん検知コード生成装置300は、秘密情報符号化部301を有する。改ざん検知コード生成装置300は、秘密情報用データ集合Ｓの元である秘密情報sが入力されると、sを秘密情報符号化部301に入力し、その出力のコード用データ集合Cの元であるcをコードとして出力する。
【００６４】
図１２Ｂに示すように、改ざん検知コード検証装置400は、秘密情報符号化部301に対応する秘密情報復号化部401と、復号結果判定部402とを有する。
【００６５】
改ざん検知コード検証装置400は、コード用データ集合Cの元であるcが入力されると、cを秘密情報復号化部401に入力し、秘密情報復号化部401の出力を復号結果判定部402に入力する。復号結果判定部402は、秘密情報復号化部401から受信した値が秘密情報用データ集合の要素である場合、その値をそのまま出力し、それ以外の場合、改ざんがあったことを表す記号を出力する。
【先行技術文献】
【非特許文献】
【００６６】
【非特許文献１】Adi Shamir. How to share a secret. Comm.ACM,22(11) 612-613(1979).
【非特許文献２】Sergio Cabello, Carles Padro', Germa'n Sa'ez: Secret Sharing Schemes with Detection of Cheaters for a General Access Structure. Des. Codes Cryptography 25(2): 175-188 (2002)
【非特許文献３】Toshinori Araki, Satoshi Obana: Flaws in Some Secret Sharing Schemes Against Cheating. ACISP 2007: 122-132
【非特許文献４】Wakaha Ogata. Kaoru Kurosawa. Douglas R Stinson:Optimum Secret Sharing Scheme Secure Against Cheating SIAM J.Discrete Math.,vol.20,no1,pages 79-95,2006
【発明の概要】
【発明が解決しようとする課題】
【００６７】
(k,n)閾値法を含む線形秘密分散法を用いて分散情報を生成する際、分散情報の改ざんを高確率で検知可能なコードを生成する方法として、検知性について非特許文献４の方式と同程度の効率であって、パラメータを自由に設定できるものがなかった。
【００６８】
本発明の目的は、分散情報の改ざんを高確率および効率的に検知可能とし、かつ、パラメータ設定の自由度を大きくした情報処理装置、コード生成方法、コード検証方法、およびその方法をコンピュータに実行させるためのプログラムを提供することである。
【課題を解決するための手段】
【００６９】
上記目的を達成するための本発明の情報処理装置は、
秘密情報sが入力されると、素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s＿1,...,s＿N｝で該秘密情報sを表し、s＿1*...*s＿N mod pをチェック用データvとして求めるチェック用データ生成部と、
前記秘密情報sと前記チェック用データvに対して線形秘密分散法を用いてそれぞれの分散符号化した値を生成するコード分散部と、
線形秘密分散法のアクセス構造に対応する秘密情報とチェック用データの符合語を含む復元対象の情報から秘密情報s'およびチェック用データv’を復元するコード復元部と、
前記秘密情報s'が前記チェック用データ生成部に入力されたときの出力であるチェック用データv''と前記チェック用データv'とが等しいか否かを判定し、該チェック用データv'とv''が等しい場合にはデータが改ざんされていないと判定し、該チェック用データv'とv''が等しくない場合にはデータが改ざんされていると判定する同一性判定部と、
を有する構成である。
【００７０】
また、本発明のコード生成方法は、線形秘密分散法により生成される情報の改ざんを検知するためのコード生成方法であって、
秘密情報sが入力されると、素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s＿1,...,s＿N｝で該秘密情報sを表し、s＿1*...*s＿N mod pをチェック用データvとして求め、
前記秘密情報sと前記チェック用データvに対して線形秘密分散法を用いてそれぞれの分散符号化した値を生成するものである。
【００７１】
また、本発明のコード検証方法は、線形秘密分散法により生成される情報の改ざんを検知するためのコード検証方法であって、
線形秘密分散法のアクセス構造に対応する秘密情報とチェック用データの符合語を含む復元対象の情報から秘密情報s'およびチェック用データv’を復元し、
素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s'＿1,...,s'＿N｝で前記秘密情報s'を表し、s'＿1*...*s'＿N mod pをチェック用データv''として求め、
前記チェック用データv''と前記チェック用データv'とが等しいか否かを判定し、該チェック用データv'とv''が等しい場合にはデータが改ざんされていないと判定し、該チェック用データv'とv''が等しくない場合にはデータが改ざんされていると判定するものである。
【００７２】
また、本発明のプログラムは、線形秘密分散法により生成される情報の改ざんを検知するためのコードを生成するコンピュータに実行させるためのプログラムであって、
秘密情報sが入力されると、素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s＿1,...,s＿N｝で該秘密情報sを表し、s＿1*...*s＿N mod pをチェック用データvとして求め、
前記秘密情報sと前記チェック用データvに対して線形秘密分散法を用いてそれぞれの分散符号化した値を生成する処理を前記コンピュータに実行させるものである。
【００７３】
さらに、本発明のプログラムは、線形秘密分散法により生成される情報の改ざんを検知するためのコードを検証するコンピュータに実行させるためのプログラムであって、
線形秘密分散法のアクセス構造に対応する秘密情報とチェック用データの符合語を含む復元対象の情報から秘密情報s'およびチェック用データv’を復元し、
素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s'＿1,...,s'＿N｝で前記秘密情報s'を表し、s'＿1*...*s'＿N mod pをチェック用データv''として求め、
前記チェック用データv''と前記チェック用データv'とが等しいか否かを判定し、該チェック用データv'とv''が等しい場合にはデータが改ざんされていないと判定し、該チェック用データv'とv''が等しくない場合にはデータが改ざんされていると判定する処理を前記コンピュータに実行させるものである。
【発明の効果】
【００７４】
本発明によれば、線形秘密分散法を用いた分散情報の改ざんを高確率および効率的に検知可能とし、かつ、パラメータ設定の自由度を大きくすることができる。
【図面の簡単な説明】
【００７５】
【図１】本実施形態の情報処理装置の一構成例を示すブロック図である。
【図２】図１に示した情報処理装置の具体的構成例を示すブロック図である。
【図３Ａ】本実施形態の情報処理装置に含まれるコード生成装置の一構成例を示すブロック図である。
【図３Ｂ】本実施形態の情報処理装置に含まれるコード検証装置の一構成例を示すブロック図である。
【図４】図３Ａに示したコード生成装置の動作手順を示すフローチャートである。
【図５】図３Ｂに示したコード検証装置の動作手順を示すフローチャートである。
【図６】本実施形態による、分散情報を生成する手順を示すフローチャートである。
【図７】本実施形態による、分散情報を復元する手順を示すフローチャートである。
【図８Ａ】関連する分散情報生成装置の一構成例を示すブロック図である。
【図８Ｂ】関連する復元装置の一構成例を示すブロック図である。
【図９】図８Ａに示した分散情報生成装置の動作手順を示すフローチャートである。
【図１０】図８Ｂに示した復元装置の動作手順を示すフローチャートである。
【図１１Ａ】非特許文献２または非特許文献３に開示されたコード生成装置の一構成例を示すブロック図である。
【図１１Ｂ】非特許文献２または非特許文献３に開示されたコード検証装置の一構成例を示すブロック図である。
【図１２Ａ】非特許文献４に開示されたコード生成装置の一構成例を示すブロック図である。
【図１２Ｂ】非特許文献４に開示されたコード検証装置の一構成例を示すブロック図である。
【発明を実施するための形態】
【００７６】
本実施形態について図面を参照して詳細に説明する。図１は本実施形態の情報処理装置の一構成例を示すブロック図である。
【００７７】
図１に示すように、本実施形態の情報処理装置10は、記憶部35と、制御部25とを有する。制御部25は、コード分散部702と、コード復元部801と、後述する秘密情報剰余算出部501および同一性判定部601とを有する。
【００７８】
図２は図１に示した情報処理装置の具体的構成例を示すブロック図である。
【００７９】
図２に示すように、プログラムにしたがって処理を実行するＣＰＵ（Central Processing Unit）11と、ＣＰＵ11に供給するプログラムおよび演算処理過程の情報を一時的に保存するためのＲＡＭ（Random Access Memory）13と、プログラムが予め格納された主記憶部12と、秘密情報、閾値および分散情報数などの演算処理に必要な情報が格納されたデータ蓄積部14と、記憶部35の各記憶領域間のデータ転送を制御するメモリ制御インタフェイス部15と、情報を入力するための入力部20と、演算結果を出力するための出力部30と、入力部20および出力部30の入出力制御を行うI/Oインタフェイス部16とを有する。これらの構成は、バス18を介して接続されている。
【００８０】
プログラムには、コード分散部702、同一性判定部601、コード復元部801、および秘密情報剰余算出部501の機能をＣＰＵ11に実行させるための処理手順が書き込まれている。ＣＰＵ11がプログラムを実行することで、コード分散部702、同一性判定部601、コード復元部801、および秘密情報剰余算出部501が情報処理装置10に仮想的に構成される。
【００８１】
なお、プログラムに、秘密情報符号化部301、秘密情報復号化部401および復号結果判定部402の機能をＣＰＵ11に実行させるための処理手順がさらに書き込まれていてもよい。
【００８２】
なお、データ蓄積部14は、情報処理装置10内に設けていなくてもよく、情報処理装置10とは別に設けていてもよい。また、データ蓄積部14は、記憶部901を有する保管装置900としてもよい。
【００８３】
また、演算処理に必要なプログラムやデータを格納した記憶媒体を入力部20に装着し、それらの情報を入力部20を介して情報処理装置10に入力するようにしてもよい。記憶部媒体には、例えば、磁気ディスク、半導体メモリ、光ディスクなどがあるが、その他の記録媒体であってもよい。
【００８４】
次に、チェック用データに相当するコードの生成と検証に注目して、図１に示した情報処理装置10が実行する情報改ざん検知方法を説明する。本実施形態で処理対象となる秘密情報は、例えば、文書の暗号化のための秘密鍵となる素数である。この場合、秘密情報の元の集合は素数の集合となる。また、ここでは、情報処理装置10を、コードの生成処理を行うコード生成装置とコードの検証処理を行うコード検証装置の２つの装置に分けて説明する。
【００８５】
秘密情報ｓは、pを素数としたとき、２以上の整数Nの要素数で｛1, ... ,p-1｝の要素の列に符号化されて秘密情報剰余算出部501に入力されるものとする。また、チェック用データの集合として｛1, ... ,p-1｝を用いる。
【００８６】
また、素数pはデータ蓄積部14に予め記録されていてもよく、秘密情報剰余算出部501に設けられたメモリ（不図示）に予め記録されていてもよく、秘密情報剰余算出部501に外部から入力されてもよい。秘密情報剰余算出部501への入力は、コード生成装置500への入力で実行される。以下では、説明を省略するが、素数pが秘密情報剰余部501のメモリ（不図示）に記録されているものとする。
【００８７】
また、秘密情報の符号化処理はコード生成装置500への入力前に行われてもよく、符号化処理の機能をコード生成装置500に予め備え、コード生成装置500が入力される秘密情報の符号化処理を実行してもよい。以下では、符号化された秘密情報がコード生成装置500に入力される場合で説明する。
【００８８】
また、本実施形態では、秘密分散法として非特許文献４に記載されている(k,n)閾値法を適用するが、秘密分散法は線形秘密分散法であれば適用可能である。
【００８９】
図３Ａは本実施形態の情報処理装置に含まれるコード生成装置の一構成例を示すブロック図である。図３Ｂは本実施形態の情報処理装置に含まれるコード検証装置の一構成例を示すブロック図である。本実施形態の情報処理装置10は、コード生成装置500およびコード検証装置600を含む構成である。
【００９０】
図３Ａに示すように、コード生成装置500は、秘密情報剰余算出部501を有する構成である。秘密情報剰余算出部501はチェック用データ生成部に相当する。コード生成装置500は、秘密情報用データ集合Ｓの元である秘密情報s=(s＿1,...,s＿N)が入力されると、入力されたsと、秘密情報剰余部501の出力であるチェック用データ集合Ｃの元を出力する。
【００９１】
秘密情報剰余算出部501は、s=(s＿1,...,s＿N)が入力されると、c = s＿1* s＿2* ... *s＿N mod pを計算し、cを出力する。
【００９２】
ここでは、秘密情報s=(s＿1,...,s＿N)が秘密情報剰余部501に入力される場合としているが、秘密情報sが入力されると、秘密情報剰余部501が、プログラムにしたがって、素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列(s＿1,...,s＿N)で表す処理を実行してもよい。
【００９３】
次に、コード検証装置600について説明する。
【００９４】
図３Ｂに示すように、コード検証装置600は、上述した秘密情報剰余算出部501と、同一性判定部601とを有する。コード検証装置600は、秘密情報用データ集合Ｓの元である秘密情報s'=(s'＿1,...,s'＿N)とチェック用データ集合Ｃの元c'が入力されると、同一性判定装置601の出力である検証結果とs'を出力する。
【００９５】
秘密情報剰余算出部501は、s' = (s'＿1,...,s'＿N)が入力されると、上述したように、c'' = s'＿1*s'＿2*...*s'＿N mod pを計算する処理を行い、c''を同一性判定部601に渡す。
【００９６】
同一性判定部601は、秘密情報剰余算出部501の出力であるc''を秘密情報剰余算出部501から受け取り、コード検証装置600に入力されたc'を受け取ると、c' ＝ c''が満たされるか否かをチェックする。その結果、c' ＝ c''である場合、同一性判定部601は、データが改ざんされていないと判定し、改ざんが検出されなかったことを表す記号を出力する。その反対に、c' ≠ c''である場合、同一性判定部601は、データが改ざんされていると判定し、改ざんの検出を表す記号を出力する。
【００９７】
次に、コード生成装置500の動作手順を、図４のフローチャートを参照して説明する。
【００９８】
秘密情報用データ集合Ｓの元s=(s＿1,...,s＿N)がコード生成装置500に入力される(ステップC1)。秘密情報剰余算出部501は、s=(s＿1,...,s＿N)が入力されると、c = s＿1* s＿2* ... *s＿N mod pを算出する（ステップC2）。続いて、コード生成装置500は、秘密情報剰余算出部501の算出結果であるcとコード生成装置500への入力であるsを出力する（ステップC3）。
【００９９】
その後、秘密情報sおよびチェック用データcの情報が分散情報に埋め込まれる際には、図１に示したコード分散部702が、秘密情報sとチェック用データcに対して線形秘密分散法を用いてそれぞれの分散符号化した値を生成するが、ここでは、その詳細な説明を省略する。
【０１００】
次に、コード検証装置600の動作手順を、図５のフローチャートを参照して説明する。
【０１０１】
秘密情報用データ集合Ｓの元s'=(s'＿1,...,s'＿N)と、チェック用データ集合Ｃの元であるc'がコード検証装置600に入力される(ステップD1)。秘密情報剰余算出部501は、s'=(s'＿1,...,s'＿N)が入力されると、c''=s'＿1*s'＿2*...*s'＿N mod pを算出する(ステップD2）。
【０１０２】
ステップD1でコード検証装置600に入力されたc'とステップD2で算出されたc''とが同一性判定部601に入力される（ステップD3）。同一性判定部601はc' = c''が満たされるか否かをチェックする（ステップD4）。その結果、c' ＝ c''である場合、同一性判定部601は、データが改ざんされていないと判定し、改ざんが検出されなかったことを表す記号を出力する（ステップD5）。ステップD4でc' ≠ c''である場合、同一性判定部601は、データが改ざんされていると判定し、改ざんの検出を表す記号を出力する（ステップD6）。
【０１０３】
なお、ステップD1の前に、図１に示したコード復元部801が線形秘密分散法のアクセス構造に対応する秘密情報とチェック用データの符合語を含む復元対象の情報から秘密情報s'およびチェック用データv’を復元し、これらの情報がステップD1でコード検証装置600に入力されるが、ここでは、その詳細な説明を省略している。
【０１０４】
ここまで、チェック用データのコードに注目して説明したが、図１に示した情報処理装置10による、チェック用データを分散情報に埋め込む場合の処理方法について説明する。
【０１０５】
ここでは、コード分散部702は分散符号語生成部（不図示）を含み、コード復元部801は符号語復元部（不図示）を含むものとする。これらの構成もＣＰＵ11がプログラムを実行することで仮想的に構成されるものである。
【０１０６】
はじめに、秘密情報に対して分散符号化処理を行って、分散情報を生成する手順を説明する。図６は、本実施形態による、分散情報を生成する手順を示すフローチャートである。
【０１０７】
図６に示すように、秘密情報剰余算出部501は、秘密情報sが入力されると、秘密情報sをある素数pを用いてsを1からp-1の値の列｛s＿1,...,s＿N｝と表し、s＿1*...*s＿N mod pをチェック用データvとして求める（ステップE1）。
【０１０８】
その後、分散符号語生成部（不図示）は、秘密情報sとチェック用データvが埋め込まれた（k-1）次多項式Fを生成し、互いに異なるn個の値x1乃至xnを多項式Fに入力したときの、入力と出力との組である(x1, F(x1))乃至(xn, F(xn))を分散符号語情報として生成し、分散符号語情報を出力する（ステップE2）。
【０１０９】
次に、情報処理装置10に復元対象となる情報が入力されたとき、その情報が改ざんされているか否かを判定する手順を説明する。図７は、本実施形態による、分散情報を復元する手順を示すフローチャートである。
【０１１０】
符号語復元部（不図示）は、k組分の分散符号語情報として(x1', F＿1')乃至(xk', F＿k')が入力されると、これらの点を通る(k-1)次多項式F'を生成し、多項式F'に埋め込まれた秘密情報s'=｛s'＿1,...,s'＿N｝とチェック用データv'を読み出して出力する（ステップF1）。秘密情報剰余算出部501は、s'が入力されると、s'＿1*...*s'＿N mod pをチェック用データv''として求める（ステップF2）。
【０１１１】
同一性判定部601は、チェック用データv'とv''が等しいかどうかを判定する（ステップF3）。その結果、v'とv''が等しい場合、同一性判定部601はデータが改ざんされていない旨の検証結果を出力し（ステップF4）、v'とv''が等しくない場合、同一性判定部601はデータが改ざんされている旨の検証結果を出力する（ステップF5）。
【実施例１】
【０１１２】
本実施例のコード生成装置500は、入力される秘密情報を用いて、分散情報の改ざん検知コードを生成して出力する。本実施例のコード検証装置600は、入力されるコードの正当性を検証する。
【０１１３】
本実施例では、秘密情報sを複数の要素の組s= (s＿｛0,1｝,...,s＿｛0,N｝)によって表す。Nは２以上の数であって、各要素s＿｛0,i｝(i = 1,...,N)はpを素数として、1,...,p-1とする。
【０１１４】
本実施例のコード生成装置500は、秘密情報sが入力されると、実施形態で説明したように演算を行い、秘密情報sを出力するとともに、c= s＿｛0,1｝*s＿｛0,2｝*...+s＿｛0,N｝ mod pをコードとして出力する。生成されたコードは分散情報に埋め込まれる。
【０１１５】
一方、コード検証装置600は、収集された分散情報から読み出された秘密情報s'= (s'＿｛0,1｝,...,s'＿｛0,N｝)とコードc'が入力されると、c''= s'＿｛0,1｝*s'＿｛0,2｝*...+s'＿｛0,N｝ mod pを求める。そして、コード検証装置600は、コードc'とc''が等しいか否かを判定し、c'= c''である場合にはデータが改ざんされていないと判定し、c'≠ c''である場合にはデータが改ざんされていると判定し、検証結果を出力する。
【０１１６】
ここで改ざん者が秘密情報s'をs＿｛1,1｝,...,s＿｛1,N｝だけ、コードcをc'''だけ改ざんする場合を考える。
このとき、(s＿｛0,1｝+s＿｛1,1｝)*(s＿｛0,2｝+s＿｛1,2｝)*...*(s＿｛0,N｝+s＿｛1,N｝) = s＿｛0,1｝*s＿｛0,2｝*...*s＿｛0,N｝ + s＿｛0,1｝*s＿｛0,2｝*...*s＿｛1,N｝ + ... + s＿｛1,1｝*s＿｛1,2｝*...*s＿｛1,N｝となっている。
【０１１７】
つまり、どのように改ざんを行っても、s＿｛0,1｝*s＿｛0,2｝*...*s＿｛1,N｝のように未知の秘密情報を含む項が存在する。
【０１１８】
そのため、改ざん者は、改ざんの結果がコードc'''に対してどのような影響を及ぼすかは秘密情報の確率分布に従って推測するよりなく、例えば秘密情報が一様な分布に従ってランダムに選ばれる場合には、改ざんした結果が予想した値と等しくなる確率は1/(p-1)となる。
【０１１９】
この場合、秘密情報の集合の要素数は(p-1)*Nとなり、改ざんの確率は1/p程度となる。
コードの集合の要素数はおよそp*(N+1)であり、検知性について非特許文献４の方式と同程度である。これに加え、素数pのサイズとNをほぼ独立に設定することが可能であるので、パラメータが自由に設定可能である。
【０１２０】
よって、本実施形態では、(k,n)閾値法を含む線形秘密分散法による分散情報の改ざんを高確率および効率的に検知可能とし、かつ、パラメータ設定の自由度を大きくすることができる。
【産業上の利用可能性】
【０１２１】
本発明を秘密鍵などの機密情報の分散管理に利用できる。
【符号の説明】
【０１２２】
１０ 情報処理装置
１１ ＣＰＵ
１２ 主記憶部
１３ ＲＡＭ
１４ データ蓄積部
１５ メモリ制御インタフェイス部
１６ I/Oインタフェイス部
２０ 入力部
２５ 制御部
３０ 出力部
３５ 記憶部
５０１ 秘密情報剰余算出部
６０１ 同一性判定部
７０２ コード分散部
８０１ コード復元部
【特許請求の範囲】
【請求項１】
秘密情報sが入力されると、素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s＿1,...,s＿N｝で該秘密情報sを表し、s＿1*...*s＿N mod pをチェック用データvとして求めるチェック用データ生成部と、
前記秘密情報sと前記チェック用データvに対して線形秘密分散法を用いてそれぞれの分散符号化した値を生成するコード分散部と、
線形秘密分散法のアクセス構造に対応する秘密情報とチェック用データの符合語を含む復元対象の情報から秘密情報s'およびチェック用データv’を復元するコード復元部と、
前記秘密情報s'が前記チェック用データ生成部に入力されたときの出力であるチェック用データv''と前記チェック用データv'とが等しいか否かを判定し、該チェック用データv'とv''が等しい場合にはデータが改ざんされていないと判定し、該チェック用データv'とv''が等しくない場合にはデータが改ざんされていると判定する同一性判定部と、
を有する情報処理装置。
【請求項２】
前記コード分散部は、
前記チェック用データ生成部で前記チェック用データvが生成されると、前記秘密情報sと該チェック用データvが埋め込まれた（k-1）次多項式Fを生成し、互いに異なるn個の値であるx1乃至xnを前記F（k-1）次多項式に入力したときの、入力と出力との組である(x1, F(x1))乃至(xn, F(xn))を分散符号語情報として生成し、
前記コード復元部は、
復元対象の情報として、k組分の分散符号語情報として(x1', F＿1')乃至(xk', F＿k')が入力されると、該(x1', F＿1')から該(xk', F＿k')の点を通る(k-1)次多項式F'を生成し、該(k-1)次多項式F'に埋め込まれた前記秘密情報s'および前記チェック用データv'を復元する、請求項１記載の情報処理装置。
【請求項３】
線形秘密分散法により生成される情報の改ざんを検知するためのコード生成方法であって、
秘密情報sが入力されると、素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s＿1,...,s＿N｝で該秘密情報sを表し、s＿1*...*s＿N mod pをチェック用データvとして求め、
前記秘密情報sと前記チェック用データvに対して線形秘密分散法を用いてそれぞれの分散符号化した値を生成する、コード生成方法。
【請求項４】
前記チェック用データ生成部で前記チェック用データvを求めた後、前記秘密情報sと該チェック用データvが埋め込まれた（k-1）次多項式Fを生成し、
互いに異なるn個の値であるx1乃至xnを前記F（k-1）次多項式に入力したときの、入力と出力との組である(x1, F(x1))乃至(xn, F(xn))を分散符号語情報として生成する、請求項３記載のコード生成方法。
【請求項５】
線形秘密分散法により生成される情報の改ざんを検知するためのコード検証方法であって、
線形秘密分散法のアクセス構造に対応する秘密情報とチェック用データの符合語を含む復元対象の情報から秘密情報s'およびチェック用データv’を復元し、
素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s'＿1,...,s'＿N｝で前記秘密情報s'を表し、s'＿1*...*s'＿N mod pをチェック用データv''として求め、
前記チェック用データv''と前記チェック用データv'とが等しいか否かを判定し、該チェック用データv'とv''が等しい場合にはデータが改ざんされていないと判定し、該チェック用データv'とv''が等しくない場合にはデータが改ざんされていると判定する、コード検証方法。
【請求項６】
復元対象の情報として、k組分の分散符号語情報として(x1', F＿1')乃至(xk', F＿k')が入力されると、該(x1', F＿1')から該(xk', F＿k')の点を通る(k-1)次多項式F'を生成し、
前記(k-1)次多項式F'に埋め込まれた前記秘密情報s'および前記チェック用データv'を復元する、請求項５記載のコード検証方法。
【請求項７】
線形秘密分散法により生成される情報の改ざんを検知するためのコードを生成するコンピュータに実行させるためのプログラムであって、
秘密情報sが入力されると、素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s＿1,...,s＿N｝で該秘密情報sを表し、s＿1*...*s＿N mod pをチェック用データvとして求め、
前記秘密情報sと前記チェック用データvに対して線形秘密分散法を用いてそれぞれの分散符号化した値を生成する処理を前記コンピュータに実行させるためのプログラム。
【請求項８】
前記チェック用データ生成部で前記チェック用データvを求めた後、前記秘密情報sと該チェック用データvが埋め込まれた（k-1）次多項式Fを生成し、
互いに異なるn個の値であるx1乃至xnを前記F（k-1）次多項式に入力したときの、入力と出力との組である(x1, F(x1))乃至(xn, F(xn))を分散符号語情報として生成する処理をさらに有する請求項７記載のプログラム。
【請求項９】
線形秘密分散法により生成される情報の改ざんを検知するためのコードを検証するコンピュータに実行させるためのプログラムであって、
線形秘密分散法のアクセス構造に対応する秘密情報とチェック用データの符合語を含む復元対象の情報から秘密情報s'およびチェック用データv’を復元し、
素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s'＿1,...,s'＿N｝で前記秘密情報s'を表し、s'＿1*...*s'＿N mod pをチェック用データv''として求め、
前記チェック用データv''と前記チェック用データv'とが等しいか否かを判定し、該チェック用データv'とv''が等しい場合にはデータが改ざんされていないと判定し、該チェック用データv'とv''が等しくない場合にはデータが改ざんされていると判定する処理を前記コンピュータに実行させるためのプログラム。
【請求項１０】
復元対象の情報として、k組分の分散符号語情報として(x1', F＿1')乃至(xk', F＿k')が入力されると、該(x1', F＿1')から該(xk', F＿k')の点を通る(k-1)次多項式F'を生成し、
前記(k-1)次多項式F'に埋め込まれた前記秘密情報s'および前記チェック用データv'を復元する処理をさらに有する請求項９記載のプログラム。
【請求項１】
秘密情報sが入力されると、素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s＿1,...,s＿N｝で該秘密情報sを表し、s＿1*...*s＿N mod pをチェック用データvとして求めるチェック用データ生成部と、
前記秘密情報sと前記チェック用データvに対して線形秘密分散法を用いてそれぞれの分散符号化した値を生成するコード分散部と、
線形秘密分散法のアクセス構造に対応する秘密情報とチェック用データの符合語を含む復元対象の情報から秘密情報s'およびチェック用データv’を復元するコード復元部と、
前記秘密情報s'が前記チェック用データ生成部に入力されたときの出力であるチェック用データv''と前記チェック用データv'とが等しいか否かを判定し、該チェック用データv'とv''が等しい場合にはデータが改ざんされていないと判定し、該チェック用データv'とv''が等しくない場合にはデータが改ざんされていると判定する同一性判定部と、
を有する情報処理装置。
【請求項２】
前記コード分散部は、
前記チェック用データ生成部で前記チェック用データvが生成されると、前記秘密情報sと該チェック用データvが埋め込まれた（k-1）次多項式Fを生成し、互いに異なるn個の値であるx1乃至xnを前記F（k-1）次多項式に入力したときの、入力と出力との組である(x1, F(x1))乃至(xn, F(xn))を分散符号語情報として生成し、
前記コード復元部は、
復元対象の情報として、k組分の分散符号語情報として(x1', F＿1')乃至(xk', F＿k')が入力されると、該(x1', F＿1')から該(xk', F＿k')の点を通る(k-1)次多項式F'を生成し、該(k-1)次多項式F'に埋め込まれた前記秘密情報s'および前記チェック用データv'を復元する、請求項１記載の情報処理装置。
【請求項３】
線形秘密分散法により生成される情報の改ざんを検知するためのコード生成方法であって、
秘密情報sが入力されると、素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s＿1,...,s＿N｝で該秘密情報sを表し、s＿1*...*s＿N mod pをチェック用データvとして求め、
前記秘密情報sと前記チェック用データvに対して線形秘密分散法を用いてそれぞれの分散符号化した値を生成する、コード生成方法。
【請求項４】
前記チェック用データ生成部で前記チェック用データvを求めた後、前記秘密情報sと該チェック用データvが埋め込まれた（k-1）次多項式Fを生成し、
互いに異なるn個の値であるx1乃至xnを前記F（k-1）次多項式に入力したときの、入力と出力との組である(x1, F(x1))乃至(xn, F(xn))を分散符号語情報として生成する、請求項３記載のコード生成方法。
【請求項５】
線形秘密分散法により生成される情報の改ざんを検知するためのコード検証方法であって、
線形秘密分散法のアクセス構造に対応する秘密情報とチェック用データの符合語を含む復元対象の情報から秘密情報s'およびチェック用データv’を復元し、
素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s'＿1,...,s'＿N｝で前記秘密情報s'を表し、s'＿1*...*s'＿N mod pをチェック用データv''として求め、
前記チェック用データv''と前記チェック用データv'とが等しいか否かを判定し、該チェック用データv'とv''が等しい場合にはデータが改ざんされていないと判定し、該チェック用データv'とv''が等しくない場合にはデータが改ざんされていると判定する、コード検証方法。
【請求項６】
復元対象の情報として、k組分の分散符号語情報として(x1', F＿1')乃至(xk', F＿k')が入力されると、該(x1', F＿1')から該(xk', F＿k')の点を通る(k-1)次多項式F'を生成し、
前記(k-1)次多項式F'に埋め込まれた前記秘密情報s'および前記チェック用データv'を復元する、請求項５記載のコード検証方法。
【請求項７】
線形秘密分散法により生成される情報の改ざんを検知するためのコードを生成するコンピュータに実行させるためのプログラムであって、
秘密情報sが入力されると、素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s＿1,...,s＿N｝で該秘密情報sを表し、s＿1*...*s＿N mod pをチェック用データvとして求め、
前記秘密情報sと前記チェック用データvに対して線形秘密分散法を用いてそれぞれの分散符号化した値を生成する処理を前記コンピュータに実行させるためのプログラム。
【請求項８】
前記チェック用データ生成部で前記チェック用データvを求めた後、前記秘密情報sと該チェック用データvが埋め込まれた（k-1）次多項式Fを生成し、
互いに異なるn個の値であるx1乃至xnを前記F（k-1）次多項式に入力したときの、入力と出力との組である(x1, F(x1))乃至(xn, F(xn))を分散符号語情報として生成する処理をさらに有する請求項７記載のプログラム。
【請求項９】
線形秘密分散法により生成される情報の改ざんを検知するためのコードを検証するコンピュータに実行させるためのプログラムであって、
線形秘密分散法のアクセス構造に対応する秘密情報とチェック用データの符合語を含む復元対象の情報から秘密情報s'およびチェック用データv’を復元し、
素数pと２以上の整数Nを用いて、1からp-1の値を要素とする列｛s'＿1,...,s'＿N｝で前記秘密情報s'を表し、s'＿1*...*s'＿N mod pをチェック用データv''として求め、
前記チェック用データv''と前記チェック用データv'とが等しいか否かを判定し、該チェック用データv'とv''が等しい場合にはデータが改ざんされていないと判定し、該チェック用データv'とv''が等しくない場合にはデータが改ざんされていると判定する処理を前記コンピュータに実行させるためのプログラム。
【請求項１０】
復元対象の情報として、k組分の分散符号語情報として(x1', F＿1')乃至(xk', F＿k')が入力されると、該(x1', F＿1')から該(xk', F＿k')の点を通る(k-1)次多項式F'を生成し、
前記(k-1)次多項式F'に埋め込まれた前記秘密情報s'および前記チェック用データv'を復元する処理をさらに有する請求項９記載のプログラム。
【図１】
【図２】
【図３Ａ】
【図３Ｂ】
【図４】
【図５】
【図６】
【図７】
【図８Ａ】
【図８Ｂ】
【図９】
【図１０】
【図１１Ａ】
【図１１Ｂ】
【図１２Ａ】
【図１２Ｂ】
【図２】
【図３Ａ】
【図３Ｂ】
【図４】
【図５】
【図６】
【図７】
【図８Ａ】
【図８Ｂ】
【図９】
【図１０】
【図１１Ａ】
【図１１Ｂ】
【図１２Ａ】
【図１２Ｂ】
【公開番号】特開２０１１−３５８０９（Ｐ２０１１−３５８０９Ａ）
【公開日】平成２３年２月１７日（２０１１．２．１７）
【国際特許分類】
【出願番号】特願２００９−１８２３０３（Ｐ２００９−１８２３０３）
【出願日】平成２１年８月５日（２００９．８．５）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２３年２月１７日（２０１１．２．１７）
【国際特許分類】
【出願日】平成２１年８月５日（２００９．８．５）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]