情報処理装置、コード生成方法、コード検証方法およびプログラム
【課題】分散情報の改ざんを高確率および効率的に検知可能とし、かつ、パラメータ設定の自由度を大きくした情報処理装置を提供する。
【解決手段】秘密情報sを一方が秘密情報sの元の集合から一様にランダムに選択された要素となるように秘密情報s＿1および秘密情報s＿2に分割する秘密情報分割部と、関数M()についてM(s＿1, s＿2)の値をチェック用データvとして算出するコード生成部と、秘密情報sとチェック用データvが埋め込まれた（k-1）次多項式Fを出力するコード分散部と、復元対象のk組分の分散符号語情報の点を通る(k-1)次多項式F'を生成し、F'に埋め込まれた秘密情報s'およびチェック用データv'を復元するコード復元部と、秘密情報s'から分割された秘密情報s'＿1および秘密情報s'＿2について関数M(s'＿1, s'＿2)の値とチェック用データv'が等しいかを否かを判定するコード検証部と、を有する。
【解決手段】秘密情報sを一方が秘密情報sの元の集合から一様にランダムに選択された要素となるように秘密情報s＿1および秘密情報s＿2に分割する秘密情報分割部と、関数M()についてM(s＿1, s＿2)の値をチェック用データvとして算出するコード生成部と、秘密情報sとチェック用データvが埋め込まれた（k-1）次多項式Fを出力するコード分散部と、復元対象のk組分の分散符号語情報の点を通る(k-1)次多項式F'を生成し、F'に埋め込まれた秘密情報s'およびチェック用データv'を復元するコード復元部と、秘密情報s'から分割された秘密情報s'＿1および秘密情報s'＿2について関数M(s'＿1, s'＿2)の値とチェック用データ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')を表しているものとする。
【００３５】
なお、コードの集合が小さければ小さいほど分散情報のサイズが小さく、秘密情報を分散して保管する場合に必要とする記憶容量が少なくて済み、好ましい。
【００３６】
提案されている方式には、非特許文献１よりも演算処理が効率的な方式として、非特許文献２、非特許文献３および非特許文献４に開示されているものがある。そして、これら３つの文献に開示された方式を２種類に分類すると、非特許文献２および非特許文献３に開示された方式と、非特許文献４に開示された方式とに分けられる。以下にそれぞれの説明を行う。
【００３７】
非特許文献２および非特許文献３に開示されている処理装置は、秘密情報と、乱数と、秘密情報およびこれらの乱数をある関数に入力したときの出力とをコードとして生成する処理を行うコード生成装置と、コードを入力としてその正当性を検証するコード正当性検証装置とからなる。
【００３８】
これらの方式は、秘密情報そのものの乱数性とは関係なく、乱数Ｒはそれ自体が選ばれる元の集合から一様にランダムに選ばれることを条件として、秘密情報が選ばれる集合と乱数が選ばれる集合とコードの集合上の加算を+と表し、ある関数を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)閾値法を用いて分散情報を生成する際、分散情報の改ざんを高確率で検知可能なコードを生成する方法として、非特許文献４の方式と同程度の演算効率であって、パラメータを自由に設定可能なものはなかった。
【００６５】
本発明の目的は、(k, n)閾値法による分散情報の改ざんを高確率および効率的に検知可能とし、かつ、パラメータ設定の自由度を大きくした情報処理装置、コード生成方法、コード検証方法、およびその方法をコンピュータに実行させるためのプログラムを提供することである。
【課題を解決するための手段】
【００６６】
上記目的を達成するための本発明の情報処理装置は、(k, n)閾値法により生成される情報の改ざんを検知する情報処理装置であって、
秘密情報sが入力されると、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が前記秘密情報sの元の集合から一様にランダムに選択された要素となるように、前記秘密情報sを前記秘密情報s＿1および秘密情報s＿2に分割する秘密情報分割部と、
２入力の関数M()について、前記秘密情報s＿1と前記秘密情報s＿2を入力とする関数M(s＿1, s＿2)の値をチェック用データvとして算出するコード生成部と、
前記秘密情報sと前記チェック用データvが埋め込まれた（k-1）次多項式Fを生成し、互いに異なるn個の値であるx1乃至xnを前記(k-1)次多項式Fに入力したときの、入力と出力との組である(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'が分割された秘密情報s'＿1および秘密情報s'＿2を該秘密情報分割部から受け取ると、関数M(s'＿1, s'＿2)の値と前記チェック用データv'が等しいかを否かを判定し、関数M(s'＿1, s'＿2)の値と該チェック用データv'が等しい場合、前記秘密情報s'は改ざんされていないと判定し、関数M(s'＿1, s'＿2)の値と該チェック用データv'が等しくない場合、前記秘密情報s'は改ざんされていると判定するコード検証部と、を有する。
【００６７】
また、本発明のコード生成方法は、(k, n)閾値法により生成される情報の改ざんを検知するためのコード生成方法であって、
符号化対象の秘密情報sを、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が前記秘密情報sの元の集合から一様にランダムに選択された要素となるように、前記秘密情報s＿1および秘密情報s＿2に分割し、
２入力の関数M()について、前記秘密情報s＿1と前記秘密情報s＿2を入力とする関数M(s＿1, s＿2)の値をチェック用データvとして算出し、
前記秘密情報sと前記チェック用データvが埋め込まれた（k-1）次多項式Fを生成し、互いに異なるn個の値であるx1乃至xnを前記(k-1)次多項式Fに入力したときの、入力と出力との組である(x1, F(x1))乃至(xn, F(xn))を分散符号語情報として出力するものである。
【００６８】
また、本発明のコード検証方法は、(k, n)閾値法により生成された情報の改ざんを検知するためのコード検証方法であって、
（k-1）次多項式Fとして、互いに異なるn個の値であるx1乃至xnを前記(k-1)次多項式Fに入力したときの、入力と出力との組である(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を、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が前記秘密情報sの元の集合から一様にランダムに選択された要素となるように、前記秘密情報s＿1および秘密情報s＿2に分割し、
２入力の関数M()について、関数M(s＿1, s＿2)の値と前記チェック用データvが等しいかを否かを判定し、関数M(s＿1, s＿2)の値と該チェック用データvが等しい場合、前記秘密情報sは改ざんされていないと判定し、関数M(s＿1, s＿2)の値と該チェック用データvが等しくない場合、前記秘密情報sは改ざんされていると判定するものである。
【００６９】
また、本発明のプログラムは、(k, n)閾値法により生成される情報の改ざんを検知するためのコードを生成するコンピュータに実行させるプログラムであって、
符号化対象の秘密情報sが入力されると、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が前記秘密情報sの元の集合から一様にランダムに選択された要素となるように、前記秘密情報sを前記秘密情報s＿1および秘密情報s＿2に分割し、
２入力の関数M()について、前記秘密情報s＿1と前記秘密情報s＿2を入力とする関数M(s＿1, s＿2)の値をチェック用データvとして算出し、
前記秘密情報sと前記チェック用データvが埋め込まれた（k-1）次多項式Fを生成し、互いに異なるn個の値であるx1乃至xnを前記(k-1)次多項式Fに入力したときの、入力と出力との組である(x1, F(x1))乃至(xn, F(xn))を分散符号語情報として出力する処理を前記コンピュータに実行させるものである。
【００７０】
さらに、本発明のプログラムは、(k, n)閾値法により生成された情報の改ざんを検知するためのコードを検証するコンピュータに実行させるプログラムであって、
（k-1）次多項式Fとして、互いに異なるn個の値であるx1乃至xnを前記(k-1)次多項式Fに入力したときの、入力と出力との組である(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を、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が前記秘密情報sの元の集合から一様にランダムに選択された要素となるように、前記秘密情報s＿1および秘密情報s＿2に分割し、
２入力の関数M()について、関数M(s＿1, s＿2)の値と前記チェック用データvが等しいかを否かを判定し、関数M(s＿1, s＿2)の値と該チェック用データvが等しい場合、前記秘密情報sは改ざんされていないと判定し、関数M(s＿1, s＿2)の値と該チェック用データvが等しくない場合、前記秘密情報sは改ざんされていると判定する処理を前記コンピュータに実行させるものである。
【発明の効果】
【００７１】
本発明によれば、（k, n)閾値法による分散情報の改ざんを高確率および効率的に検知可能とし、かつ、パラメータ設定の自由度を大きくすることができる。
【図面の簡単な説明】
【００７２】
【図１】本実施形態の情報処理装置の一構成例を示すブロック図である。
【図２】図１に示した情報処理装置の具体的構成例を示すブロック図である。
【図３Ａ】本実施形態の情報処理装置に含まれるコード生成装置の一構成例を示すブロック図である。
【図３Ｂ】本実施形態の情報処理装置に含まれるコード検証装置の一構成例を示すブロック図である。
【図４】図３Ａに示したコード生成装置の動作手順を示すフローチャートである。
【図５】図３Ｂに示したコード検証装置の動作手順を示すフローチャートである。
【図６】本実施形態による、分散情報を生成する手順を示すフローチャートである。
【図７】本実施形態による、分散情報を復元する手順を示すフローチャートである。
【図８Ａ】関連する分散情報生成装置の一構成例を示すブロック図である。
【図８Ｂ】関連する復元装置の一構成例を示すブロック図である。
【図９】図８Ａに示した分散情報生成装置の動作手順を示すフローチャートである。
【図１０】図８Ｂに示した復元装置の動作手順を示すフローチャートである。
【図１１Ａ】非特許文献２または非特許文献３に開示されたコード生成装置の一構成例を示すブロック図である。
【図１１Ｂ】非特許文献２または非特許文献３に開示されたコード検証装置の一構成例を示すブロック図である。
【図１２Ａ】非特許文献４に開示されたコード生成装置の一構成例を示すブロック図である。
【図１２Ｂ】非特許文献４に開示されたコード検証装置の一構成例を示すブロック図である。
【発明を実施するための形態】
【００７３】
本実施形態について図面を参照して詳細に説明する。図１は本実施形態の情報処理装置の一構成例を示すブロック図である。
【００７４】
図１に示すように、本実施形態の情報処理装置10は、記憶部35と、制御部25とを有する。制御部25は、コード分散部702と、改ざん検知コード生成部100と、改ざん検知コード検証部200と、コード復元部801と、後述する秘密情報分割部501とを有する。
【００７５】
図２は図１に示した情報処理装置の具体的構成例を示すブロック図である。
【００７６】
図２に示すように、プログラムにしたがって処理を実行するＣＰＵ（Central Processing Unit）11と、ＣＰＵ11に供給するプログラムおよび演算処理過程の情報を一時的に保存するためのＲＡＭ（Random Access Memory）13と、プログラムが予め格納された主記憶部12と、秘密情報、閾値および分散情報数などの演算処理に必要な情報が格納されたデータ蓄積部14と、記憶部35の各記憶領域間のデータ転送を制御するメモリ制御インタフェイス部15と、情報を入力するための入力部20と、演算結果を出力するための出力部30と、入力部20および出力部30の入出力制御を行うI/Oインタフェイス部16とを有する。これらの構成は、バス18を介して接続されている。
【００７７】
プログラムには、コード分散部702、改ざん検知コード生成部100、改ざん検知コード検証部200、コード復元部801、および秘密情報分割部501の機能をＣＰＵ11に実行させるための処理手順が書き込まれている。ＣＰＵ11がプログラムを実行することで、コード分散部702、改ざん検知コード生成部100、改ざん検知コード検証部200、コード復元部801、および秘密情報分割部501が情報処理装置10に仮想的に構成される。
【００７８】
なお、プログラムに、秘密情報符号化部301、秘密情報復号化部401および復号結果判定部402の機能をＣＰＵ11に実行させるための処理手順がさらに書き込まれていてもよい。
【００７９】
なお、データ蓄積部14は、情報処理装置10内に設けていなくてもよく、情報処理装置10とは別に設けていてもよい。また、データ蓄積部14は、記憶部901を有する保管装置900としてもよい。
【００８０】
また、演算処理に必要なプログラムやデータを格納した記憶媒体を入力部20に装着し、それらの情報を入力部20を介して情報処理装置10に入力するようにしてもよい。記憶部媒体には、例えば、磁気ディスク、半導体メモリ、光ディスクなどがあるが、その他の記録媒体であってもよい。
【００８１】
次に、チェック用データに相当するコードの生成と検証に注目して、図１に示した情報処理装置10が実行する情報改ざん検知方法を説明する。本実施形態で処理対象となる秘密情報は、例えば、文書の暗号化のための秘密鍵となる素数である。この場合、秘密情報の元の集合は素数の集合となる。また、ここでは、情報処理装置10を、コードの生成処理を行うコード生成装置とコードの検証処理を行うコード検証装置の２つの装置に分けて説明する。
【００８２】
図３Ａは本実施形態の情報処理装置に含まれるコード生成装置の一構成例を示すブロック図である。図３Ｂは本実施形態の情報処理装置に含まれるコード検証装置の一構成例を示すブロック図である。本実施形態の情報処理装置10は、コード生成装置500およびコード検証装置600を含む構成である。
【００８３】
図３Ａに示すように、コード生成装置500は、秘密情報分割部501および改ざん検知コード生成部100を有する。この改ざん検知コード生成部100は、上述の改ざん検知コード生成装置100と同様な機能を有しているため同じ符号が用いられている。改ざん検知コード生成部100は、改ざん検知コード生成装置100と同様な構成であるため、ここでは、その詳細な説明を省略する。
【００８４】
コード生成装置500は、秘密情報用データ集合Sの元である秘密情報sが入力されると、改ざん検知コード生成部の出力である、チェック用データ集合Ｃの元を出力し、また、入力されたｓを出力する。
【００８５】
秘密情報分割部501は、Sの元であるsが入力されると、秘密情報用データ集合Ｓ'の元である秘密情報s'と乱数用データ集合Rの元であるr'を改ざん検知コード生成部100へ出力する。改ざん検知コード生成部100は、秘密情報分割部501からs'とr'を受け取ると、s'とr'を用いてチェック用データ集合Ｃの要素であるcを生成し、生成したcを出力する。
【００８６】
次に、コード検証装置600について説明する。
【００８７】
図３Ｂに示すように、コード検証装置600は、上述した秘密情報分割部501と、改ざん検知コード検証部200とを有する。この改ざん検知コード検証部200は、上述の改ざん検知コード検証装置200と同様な機能を有しているため同じ符号が用いられている。改ざん検知コード検証部200は、改ざん検知コード検証装置200と同様な構成であるため、ここでは、その詳細な説明を省略する。
【００８８】
コード検証装置600は、復元対象の秘密情報sと、復元対象の秘密情報から取り出されたチェック用データ集合Ｃの元cとが入力されると、sと改ざん検知コード検証部200の出力である検証結果を出力し、また、入力されたsを出力する。
【００８９】
秘密情報分割部501は、その出力の秘密情報と一様乱数の改ざん検知コード生成部の出力である秘密情報と一様乱数の改ざん検知コード生成部の入力である秘密情報用データ集合Ｓ'の元である秘密情報s'とし、秘密情報と一様乱数の改ざん検知コード生成部の入力である乱数用データ集合Rの元であるr'とする。
【００９０】
改ざん検知コード検証部200は、s'とr'とcとが入力されると、これらの情報を用いて検証処理を行い、検証結果を出力する。
【００９１】
次に、コード生成装置500の動作手順を、図４のフローチャートを参照して説明する。
【００９２】
秘密情報用データ集合Sの元sがコード生成装置500に入力される（ステップC1）。秘密情報分割部501は、秘密情報sが入力されると、秘密情報用データ集合Ｓ'の元である秘密情報s'と、乱数用データ集合Rの元であるr'を生成し、s'およびr'を改ざん検知コード生成部100へ出力する（ステップC2）。
【００９３】
改ざん検知コード生成部100は、秘密情報用データ集合Ｓ'の元である秘密情報s'と、乱数用データ集合Rの元であるr'が入力されると、これらを用いてチェック用データ集合Cの元であるcを生成し、生成したcを出力する（ステップC3）。
【００９４】
ここでは、詳細な説明を省略するが、ステップC3で生成されたチェック用データcが分散情報に埋め込まれる。
【００９５】
次に、コード検証装置600の動作手順を、図５のフローチャートを参照して説明する。
【００９６】
復元対象の秘密情報用データ集合Ｓの元sと、秘密情報から取り出された、チェック用データ集合Cの元であるcとがコード検証装置600に入力される（ステップD1）。秘密情報分割部501は、sが入力されると、sを用いて、秘密情報用データ集合Ｓ'の元である秘密情報s'と、乱数用データ集合Rの元であるr'を生成し、s'およびr'を改ざん検知コード検証部200へ出力する（ステップD2）。
【００９７】
改ざん検知コード検証部200は、s'およびr'を秘密情報分割部501より受け取り、c'が入力されると、これらの情報を用いて検証処理を行い、検証結果を出力する（ステップD3）。改ざん検知コード検証部200は、s'およびr'を用いて算出される値とc'とが一致している場合、情報が改ざんされていないと判定し、それらの値が一致していない場合、情報が改ざんされていると判定する。
【００９８】
ここまで、チェック用データのコードに注目して説明したが、チェック用データを分散情報に埋め込む場合の処理方法について説明する。
【００９９】
ここでは、コード分散部702は分散符号語生成部（不図示）を含み、コード復元部801は符号語復元部（不図示）を含み、改ざん検知コード検証部200が符号語検証部（不図示）を含むものとする。これらの構成もＣＰＵ11がプログラムを実行することで仮想的に構成されるものである。
【０１００】
はじめに、秘密情報に対して分散符号化処理を行って、分散情報を生成する手順を説明する。図６は、本実施形態による、分散情報を生成する手順を示すフローチャートである。
【０１０１】
図６に示すように、秘密情報分割部501は、秘密情報sを秘密情報s＿1および秘密情報s＿2の２つに分割する処理を行う（ステップE1）。その際、秘密情報分割部501は、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が秘密情報sの元の集合から一様にランダムに選択された要素となるようにする。続いて、改ざん検知コード生成部100は、秘密情報s＿1と秘密情報s＿2を入力とする２入力の関数M()の出力としてチェック用データvを算出する（ステップE2）。
【０１０２】
その後、分散符号語生成部（不図示）は、秘密情報sとチェック用データvが埋め込まれた（k-1）次多項式Fを生成し、互いに異なるn個の値x1乃至xnを多項式Fに入力したときの、入力と出力との組である(x1, F(x1))乃至(xn, F(xn))を分散符号語情報として生成し、分散符号語情報を出力する（ステップE3）。
【０１０３】
次に、復元対象となる情報が入力されたとき、その情報が改ざんされているか否かを判定する手順を説明する。図７は、本実施形態による、分散情報を復元する手順を示すフローチャートである。
【０１０４】
符号語復元部（不図示）は、k組分の分散符号語情報として(x1', F＿1')乃至(xk', F＿k')が入力されると、これらの点を通る(k-1)次多項式F'を生成し、多項式F'に埋め込まれた秘密情報s'とチェック用データv'を読み出して出力する（ステップF1）。秘密情報分割部501は、s'が入力されると、s'をs'＿1とs'＿2に分割する（ステップF2）。
【０１０５】
符号語検証部（不図示）は、M(s'＿1,s'＿2)とv'が等しいか否かを判定する。その結果、符号語検証部（不図示）は、M(s'＿1,s'＿2)とv'が等しい場合、情報が改ざんされていない旨の検証結果を出力し、M(s'＿1,s'＿2)とv'が等しくない場合、情報が改ざんされている旨の検証結果を出力する（ステップF3）。
【０１０６】
本実施形態では、コード生成方法において、秘密情報sを２つの情報s2＿1とs2＿2に分割する際、乱数の元s2＿2は乱数Ｒが選ばれる集合から一様にランダムに選択された要素となるように分割し、s2＿1をsとし、s2＿2をrとして、ある関数M()にそれらを入力し、その出力をコードとしている。
【０１０７】
このような方法により、秘密情報が選ばれる集合と乱数が選ばれる集合とコードの集合上の加算を+と表すとき、秘密情報s1と乱数r1について、s1とc1 = M(s1,r1)を与えられた改ざん者がM(s1+s1' ,r1+r1')= M(s1, r1)+c1'を満たすs1'、r1'、c1'を生成するという改ざんを高い確率で検知可能となっている。
【０１０８】
そして、s2＿2の乱数性とM()の性質によって、s2＿1、s2＿2を与えられない改ざん者は、M(s2＿1+s2＿1',s2＿2+s2＿2')=M(s2＿1,s2＿2)+c'となるようなs2＿1'、s2＿2'、c'を生成することは困難となる。
【０１０９】
さらに、本実施形態では、秘密情報用データ集合Ｓの元である秘密情報sと乱数用データ集合Rの元であるrのサイズを独立に設定可能なため、パラメータを自由に設定可能となる。よって、(k,n)閾値法による分散情報の改ざんを高確率および効率的に検知可能とし、かつ、パラメータ設定の自由度を大きくすることができる。
【実施例１】
【０１１０】
本実施例は、上述した実施形態に、非特許文献３の方法を適用したものである。本実施例では、非特許文献３の方式を適用する場合を説明するが、上述した実施形態の情報改ざん検知方法の関数M()に他の方式を適用してもよい。
【０１１１】
非特許文献３の方法は、背景技術の欄で説明したように、以下の通りである。
【０１１２】
非特許文献３に開示された方法は、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)の要素として乗算をガロア体上の乗算としてもよい。
【０１１５】
次に、本実施例の動作手順を図３Ａおよび図３Ｂを参照して説明する。
【０１１６】
はじめにコード生成方法について説明する。コード生成装置500に、秘密情報sとして(Z/pZ)^｛N+1｝の要素である(s1,s2,...,s｛N+1｝)が入力された場合を例に説明する。
【０１１７】
コード生成装置500は、秘密情報分割部501に、s=(s1,s2,...,s｛N+1｝)を入力する。なお、各siは一様にランダム選ばれた値であるものとする。
【０１１８】
秘密情報分割部501は、sを、S'=(s1,s2,...,sN)とR'=s｛N+1｝と分割して出力する。ここでは、単純にs｛N+1｝をR'としたが、s1からsNのうちいずれの値でもよい。
【０１１９】
続いて、改ざん検知コード生成部100は、S'とR'が入力されると、s1*s｛N+1｝ + s2*s｛N+1｝^2 + ... + s｛N-1｝*s｛N+1｝^｛N-1｝ + s＿｛N｝*s｛N+1｝^｛N+1｝ mod p= Cとして計算する。コード生成装置500はsとcを出力する。
【０１２０】
次に、コード検証方法について説明する。
【０１２１】
コード検証装置600に、秘密情報sとして(Z/pZ)^｛N+1｝の要素であるs'= (s1', s2',...,s｛N+1｝')が入力され、チェック用データとしてc'が入力された場合を例に説明する。
【０１２２】
コード検証装置600は、秘密情報分割部501に、s'=(s1',s2',...,s｛N+1｝')を入力する。秘密情報分割装置501は、s'が入力されると、s'をS'=(s1',s2',...,sN')とR'=s｛N+1｝'とに分割して出力する。なお、ここでは単純にs｛N+1｝をR'としたが、s1からsNのうちいずれの値でもよい。
【０１２３】
続いて、コード検証装置600は、s'とr'とc'を改ざん検知コード検証部200に入力する。改ざん検知コード検証部200は、s'とr'とc'が入力されると、s1'*s｛N+1｝' + s2'*s｛N+1｝'^2 + ... + s｛N-1｝'*s｛N+1｝'^｛N-1｝ + s｛N｝'*s｛N+1｝'^｛N+1｝ mod pを計算し、計算結果をc'と比較する。改ざん検知コード検証部200は、比較の結果、これらの値が等しかった場合には改ざんが無かったことを表す記号を出力する。それ以外の場合は改ざんがあったことを表す記号を出力する。コード検証装置600は、入力のs'と改ざん検知コード検証装置200の出力結果を出力する。
【０１２４】
ここで、コード生成装置500の処理内容を詳細に見ると、s=(s1,s2,...,s｛N+1｝)とc= s1*s｛N+1｝ + s2*s｛N+1｝^2 + ... + s｛N-1｝*s｛N+1｝^｛N-1｝ + s＿｛N｝*s｛N+1｝^｛N+1｝ mod pのセットである(s1,s2,...,s｛N+1｝,c)がコードとなっている。
【０１２５】
このコードについて、(s1+d1,s2+d2,...,s｛N+1｝+d｛N+1｝,c+dc)の検証結果が正しくなるようなd1,d2,...,d｛N+1｝,dcを生成することは、非特許文献３の方式において、s= (s1, s2,...,s｛N｝)を秘密情報s｛N+1｝を乱数として生成されたチェック用データcについて、s=｛s1+d1,...,sN+dN｝を秘密情報とし、s｛N+1｝+d｛N+1｝を乱数とし、c+dcをチェック用データとしたときの検証結果が、改ざんがなかったとなるような(d1, d2,..., d｛N+1｝, dc)を生成することに他ならない。
【０１２６】
よって非特許文献３に開示された方式の持つ安全性により、改ざんの検知確率が高い値に保たれる。
【０１２７】
また、この方式においてはs｛N+1｝が選ばれる集合の大きさが非特許文献３における乱数の選ばれる集合の大きさになっている。この乱数の選ばれる集合の大きさのサイズが改ざん検知の成功確率にかかわっている。そのため、s｛N+1｝が選ばれる集合の大きさを調節することによってコードの長さと改ざんの成功確率を調整することが可能となっており、非特許文献４の方式に対してパラメータが柔軟にとれるようになっていることがわかる。
【０１２８】
そして、非特許文献４の方式では秘密情報の選ばれる集合のサイズを｜S｜とし、改ざん者による改ざんの成功確率をδとしたとき、コードの集合のサイズはおよそ｜S｜/δであった。
【０１２９】
一方、上述した方法では非特許文献３による方式の性質より、s｛N+1｝が選ばれる集合の大きさを｜s｛N+1｝｜とすると、ほぼ1/｜s｛N+1｝｜が改ざんの成功確率となる。｜s｛N+1｝｜はチェック用データのサイズとほぼ等しいため、この方式のコードの集合のサイズはおよそ｜S｜/δとなっていることがわかる。
【０１３０】
つまり、本実施例の方法では、秘密情報の集合の要素数はs*rとなり、改ざんの確率は1/r程度となる。このとき、コードの集合の要素数はおよそrとなり、非特許文献４の方式と同程度の演算効率となることがわかる。
【０１３１】
さらに、非特許文献４のsとrのサイズは非特許文献３の方式の性質によってほぼ独立に設定することが可能であるので、パラメータが自由に設定可能な方式となる。よって非特許文献４に記載されている方式と同程度の効率を持ちながら、M()として非特許文献３に開示された技術を用いることで、パラメータを自由に設定可能となる。
【産業上の利用可能性】
【０１３２】
本発明を秘密鍵などの機密情報の分散管理に利用できる。
【符号の説明】
【０１３３】
１０ 情報処理装置
１１ ＣＰＵ
１２ 主記憶部
１３ ＲＡＭ
１４ データ蓄積部
１５ メモリ制御インタフェイス部
１６ 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')を表しているものとする。
【００３５】
なお、コードの集合が小さければ小さいほど分散情報のサイズが小さく、秘密情報を分散して保管する場合に必要とする記憶容量が少なくて済み、好ましい。
【００３６】
提案されている方式には、非特許文献１よりも演算処理が効率的な方式として、非特許文献２、非特許文献３および非特許文献４に開示されているものがある。そして、これら３つの文献に開示された方式を２種類に分類すると、非特許文献２および非特許文献３に開示された方式と、非特許文献４に開示された方式とに分けられる。以下にそれぞれの説明を行う。
【００３７】
非特許文献２および非特許文献３に開示されている処理装置は、秘密情報と、乱数と、秘密情報およびこれらの乱数をある関数に入力したときの出力とをコードとして生成する処理を行うコード生成装置と、コードを入力としてその正当性を検証するコード正当性検証装置とからなる。
【００３８】
これらの方式は、秘密情報そのものの乱数性とは関係なく、乱数Ｒはそれ自体が選ばれる元の集合から一様にランダムに選ばれることを条件として、秘密情報が選ばれる集合と乱数が選ばれる集合とコードの集合上の加算を+と表し、ある関数を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)閾値法を用いて分散情報を生成する際、分散情報の改ざんを高確率で検知可能なコードを生成する方法として、非特許文献４の方式と同程度の演算効率であって、パラメータを自由に設定可能なものはなかった。
【００６５】
本発明の目的は、(k, n)閾値法による分散情報の改ざんを高確率および効率的に検知可能とし、かつ、パラメータ設定の自由度を大きくした情報処理装置、コード生成方法、コード検証方法、およびその方法をコンピュータに実行させるためのプログラムを提供することである。
【課題を解決するための手段】
【００６６】
上記目的を達成するための本発明の情報処理装置は、(k, n)閾値法により生成される情報の改ざんを検知する情報処理装置であって、
秘密情報sが入力されると、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が前記秘密情報sの元の集合から一様にランダムに選択された要素となるように、前記秘密情報sを前記秘密情報s＿1および秘密情報s＿2に分割する秘密情報分割部と、
２入力の関数M()について、前記秘密情報s＿1と前記秘密情報s＿2を入力とする関数M(s＿1, s＿2)の値をチェック用データvとして算出するコード生成部と、
前記秘密情報sと前記チェック用データvが埋め込まれた（k-1）次多項式Fを生成し、互いに異なるn個の値であるx1乃至xnを前記(k-1)次多項式Fに入力したときの、入力と出力との組である(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'が分割された秘密情報s'＿1および秘密情報s'＿2を該秘密情報分割部から受け取ると、関数M(s'＿1, s'＿2)の値と前記チェック用データv'が等しいかを否かを判定し、関数M(s'＿1, s'＿2)の値と該チェック用データv'が等しい場合、前記秘密情報s'は改ざんされていないと判定し、関数M(s'＿1, s'＿2)の値と該チェック用データv'が等しくない場合、前記秘密情報s'は改ざんされていると判定するコード検証部と、を有する。
【００６７】
また、本発明のコード生成方法は、(k, n)閾値法により生成される情報の改ざんを検知するためのコード生成方法であって、
符号化対象の秘密情報sを、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が前記秘密情報sの元の集合から一様にランダムに選択された要素となるように、前記秘密情報s＿1および秘密情報s＿2に分割し、
２入力の関数M()について、前記秘密情報s＿1と前記秘密情報s＿2を入力とする関数M(s＿1, s＿2)の値をチェック用データvとして算出し、
前記秘密情報sと前記チェック用データvが埋め込まれた（k-1）次多項式Fを生成し、互いに異なるn個の値であるx1乃至xnを前記(k-1)次多項式Fに入力したときの、入力と出力との組である(x1, F(x1))乃至(xn, F(xn))を分散符号語情報として出力するものである。
【００６８】
また、本発明のコード検証方法は、(k, n)閾値法により生成された情報の改ざんを検知するためのコード検証方法であって、
（k-1）次多項式Fとして、互いに異なるn個の値であるx1乃至xnを前記(k-1)次多項式Fに入力したときの、入力と出力との組である(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を、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が前記秘密情報sの元の集合から一様にランダムに選択された要素となるように、前記秘密情報s＿1および秘密情報s＿2に分割し、
２入力の関数M()について、関数M(s＿1, s＿2)の値と前記チェック用データvが等しいかを否かを判定し、関数M(s＿1, s＿2)の値と該チェック用データvが等しい場合、前記秘密情報sは改ざんされていないと判定し、関数M(s＿1, s＿2)の値と該チェック用データvが等しくない場合、前記秘密情報sは改ざんされていると判定するものである。
【００６９】
また、本発明のプログラムは、(k, n)閾値法により生成される情報の改ざんを検知するためのコードを生成するコンピュータに実行させるプログラムであって、
符号化対象の秘密情報sが入力されると、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が前記秘密情報sの元の集合から一様にランダムに選択された要素となるように、前記秘密情報sを前記秘密情報s＿1および秘密情報s＿2に分割し、
２入力の関数M()について、前記秘密情報s＿1と前記秘密情報s＿2を入力とする関数M(s＿1, s＿2)の値をチェック用データvとして算出し、
前記秘密情報sと前記チェック用データvが埋め込まれた（k-1）次多項式Fを生成し、互いに異なるn個の値であるx1乃至xnを前記(k-1)次多項式Fに入力したときの、入力と出力との組である(x1, F(x1))乃至(xn, F(xn))を分散符号語情報として出力する処理を前記コンピュータに実行させるものである。
【００７０】
さらに、本発明のプログラムは、(k, n)閾値法により生成された情報の改ざんを検知するためのコードを検証するコンピュータに実行させるプログラムであって、
（k-1）次多項式Fとして、互いに異なるn個の値であるx1乃至xnを前記(k-1)次多項式Fに入力したときの、入力と出力との組である(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を、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が前記秘密情報sの元の集合から一様にランダムに選択された要素となるように、前記秘密情報s＿1および秘密情報s＿2に分割し、
２入力の関数M()について、関数M(s＿1, s＿2)の値と前記チェック用データvが等しいかを否かを判定し、関数M(s＿1, s＿2)の値と該チェック用データvが等しい場合、前記秘密情報sは改ざんされていないと判定し、関数M(s＿1, s＿2)の値と該チェック用データvが等しくない場合、前記秘密情報sは改ざんされていると判定する処理を前記コンピュータに実行させるものである。
【発明の効果】
【００７１】
本発明によれば、（k, n)閾値法による分散情報の改ざんを高確率および効率的に検知可能とし、かつ、パラメータ設定の自由度を大きくすることができる。
【図面の簡単な説明】
【００７２】
【図１】本実施形態の情報処理装置の一構成例を示すブロック図である。
【図２】図１に示した情報処理装置の具体的構成例を示すブロック図である。
【図３Ａ】本実施形態の情報処理装置に含まれるコード生成装置の一構成例を示すブロック図である。
【図３Ｂ】本実施形態の情報処理装置に含まれるコード検証装置の一構成例を示すブロック図である。
【図４】図３Ａに示したコード生成装置の動作手順を示すフローチャートである。
【図５】図３Ｂに示したコード検証装置の動作手順を示すフローチャートである。
【図６】本実施形態による、分散情報を生成する手順を示すフローチャートである。
【図７】本実施形態による、分散情報を復元する手順を示すフローチャートである。
【図８Ａ】関連する分散情報生成装置の一構成例を示すブロック図である。
【図８Ｂ】関連する復元装置の一構成例を示すブロック図である。
【図９】図８Ａに示した分散情報生成装置の動作手順を示すフローチャートである。
【図１０】図８Ｂに示した復元装置の動作手順を示すフローチャートである。
【図１１Ａ】非特許文献２または非特許文献３に開示されたコード生成装置の一構成例を示すブロック図である。
【図１１Ｂ】非特許文献２または非特許文献３に開示されたコード検証装置の一構成例を示すブロック図である。
【図１２Ａ】非特許文献４に開示されたコード生成装置の一構成例を示すブロック図である。
【図１２Ｂ】非特許文献４に開示されたコード検証装置の一構成例を示すブロック図である。
【発明を実施するための形態】
【００７３】
本実施形態について図面を参照して詳細に説明する。図１は本実施形態の情報処理装置の一構成例を示すブロック図である。
【００７４】
図１に示すように、本実施形態の情報処理装置10は、記憶部35と、制御部25とを有する。制御部25は、コード分散部702と、改ざん検知コード生成部100と、改ざん検知コード検証部200と、コード復元部801と、後述する秘密情報分割部501とを有する。
【００７５】
図２は図１に示した情報処理装置の具体的構成例を示すブロック図である。
【００７６】
図２に示すように、プログラムにしたがって処理を実行するＣＰＵ（Central Processing Unit）11と、ＣＰＵ11に供給するプログラムおよび演算処理過程の情報を一時的に保存するためのＲＡＭ（Random Access Memory）13と、プログラムが予め格納された主記憶部12と、秘密情報、閾値および分散情報数などの演算処理に必要な情報が格納されたデータ蓄積部14と、記憶部35の各記憶領域間のデータ転送を制御するメモリ制御インタフェイス部15と、情報を入力するための入力部20と、演算結果を出力するための出力部30と、入力部20および出力部30の入出力制御を行うI/Oインタフェイス部16とを有する。これらの構成は、バス18を介して接続されている。
【００７７】
プログラムには、コード分散部702、改ざん検知コード生成部100、改ざん検知コード検証部200、コード復元部801、および秘密情報分割部501の機能をＣＰＵ11に実行させるための処理手順が書き込まれている。ＣＰＵ11がプログラムを実行することで、コード分散部702、改ざん検知コード生成部100、改ざん検知コード検証部200、コード復元部801、および秘密情報分割部501が情報処理装置10に仮想的に構成される。
【００７８】
なお、プログラムに、秘密情報符号化部301、秘密情報復号化部401および復号結果判定部402の機能をＣＰＵ11に実行させるための処理手順がさらに書き込まれていてもよい。
【００７９】
なお、データ蓄積部14は、情報処理装置10内に設けていなくてもよく、情報処理装置10とは別に設けていてもよい。また、データ蓄積部14は、記憶部901を有する保管装置900としてもよい。
【００８０】
また、演算処理に必要なプログラムやデータを格納した記憶媒体を入力部20に装着し、それらの情報を入力部20を介して情報処理装置10に入力するようにしてもよい。記憶部媒体には、例えば、磁気ディスク、半導体メモリ、光ディスクなどがあるが、その他の記録媒体であってもよい。
【００８１】
次に、チェック用データに相当するコードの生成と検証に注目して、図１に示した情報処理装置10が実行する情報改ざん検知方法を説明する。本実施形態で処理対象となる秘密情報は、例えば、文書の暗号化のための秘密鍵となる素数である。この場合、秘密情報の元の集合は素数の集合となる。また、ここでは、情報処理装置10を、コードの生成処理を行うコード生成装置とコードの検証処理を行うコード検証装置の２つの装置に分けて説明する。
【００８２】
図３Ａは本実施形態の情報処理装置に含まれるコード生成装置の一構成例を示すブロック図である。図３Ｂは本実施形態の情報処理装置に含まれるコード検証装置の一構成例を示すブロック図である。本実施形態の情報処理装置10は、コード生成装置500およびコード検証装置600を含む構成である。
【００８３】
図３Ａに示すように、コード生成装置500は、秘密情報分割部501および改ざん検知コード生成部100を有する。この改ざん検知コード生成部100は、上述の改ざん検知コード生成装置100と同様な機能を有しているため同じ符号が用いられている。改ざん検知コード生成部100は、改ざん検知コード生成装置100と同様な構成であるため、ここでは、その詳細な説明を省略する。
【００８４】
コード生成装置500は、秘密情報用データ集合Sの元である秘密情報sが入力されると、改ざん検知コード生成部の出力である、チェック用データ集合Ｃの元を出力し、また、入力されたｓを出力する。
【００８５】
秘密情報分割部501は、Sの元であるsが入力されると、秘密情報用データ集合Ｓ'の元である秘密情報s'と乱数用データ集合Rの元であるr'を改ざん検知コード生成部100へ出力する。改ざん検知コード生成部100は、秘密情報分割部501からs'とr'を受け取ると、s'とr'を用いてチェック用データ集合Ｃの要素であるcを生成し、生成したcを出力する。
【００８６】
次に、コード検証装置600について説明する。
【００８７】
図３Ｂに示すように、コード検証装置600は、上述した秘密情報分割部501と、改ざん検知コード検証部200とを有する。この改ざん検知コード検証部200は、上述の改ざん検知コード検証装置200と同様な機能を有しているため同じ符号が用いられている。改ざん検知コード検証部200は、改ざん検知コード検証装置200と同様な構成であるため、ここでは、その詳細な説明を省略する。
【００８８】
コード検証装置600は、復元対象の秘密情報sと、復元対象の秘密情報から取り出されたチェック用データ集合Ｃの元cとが入力されると、sと改ざん検知コード検証部200の出力である検証結果を出力し、また、入力されたsを出力する。
【００８９】
秘密情報分割部501は、その出力の秘密情報と一様乱数の改ざん検知コード生成部の出力である秘密情報と一様乱数の改ざん検知コード生成部の入力である秘密情報用データ集合Ｓ'の元である秘密情報s'とし、秘密情報と一様乱数の改ざん検知コード生成部の入力である乱数用データ集合Rの元であるr'とする。
【００９０】
改ざん検知コード検証部200は、s'とr'とcとが入力されると、これらの情報を用いて検証処理を行い、検証結果を出力する。
【００９１】
次に、コード生成装置500の動作手順を、図４のフローチャートを参照して説明する。
【００９２】
秘密情報用データ集合Sの元sがコード生成装置500に入力される（ステップC1）。秘密情報分割部501は、秘密情報sが入力されると、秘密情報用データ集合Ｓ'の元である秘密情報s'と、乱数用データ集合Rの元であるr'を生成し、s'およびr'を改ざん検知コード生成部100へ出力する（ステップC2）。
【００９３】
改ざん検知コード生成部100は、秘密情報用データ集合Ｓ'の元である秘密情報s'と、乱数用データ集合Rの元であるr'が入力されると、これらを用いてチェック用データ集合Cの元であるcを生成し、生成したcを出力する（ステップC3）。
【００９４】
ここでは、詳細な説明を省略するが、ステップC3で生成されたチェック用データcが分散情報に埋め込まれる。
【００９５】
次に、コード検証装置600の動作手順を、図５のフローチャートを参照して説明する。
【００９６】
復元対象の秘密情報用データ集合Ｓの元sと、秘密情報から取り出された、チェック用データ集合Cの元であるcとがコード検証装置600に入力される（ステップD1）。秘密情報分割部501は、sが入力されると、sを用いて、秘密情報用データ集合Ｓ'の元である秘密情報s'と、乱数用データ集合Rの元であるr'を生成し、s'およびr'を改ざん検知コード検証部200へ出力する（ステップD2）。
【００９７】
改ざん検知コード検証部200は、s'およびr'を秘密情報分割部501より受け取り、c'が入力されると、これらの情報を用いて検証処理を行い、検証結果を出力する（ステップD3）。改ざん検知コード検証部200は、s'およびr'を用いて算出される値とc'とが一致している場合、情報が改ざんされていないと判定し、それらの値が一致していない場合、情報が改ざんされていると判定する。
【００９８】
ここまで、チェック用データのコードに注目して説明したが、チェック用データを分散情報に埋め込む場合の処理方法について説明する。
【００９９】
ここでは、コード分散部702は分散符号語生成部（不図示）を含み、コード復元部801は符号語復元部（不図示）を含み、改ざん検知コード検証部200が符号語検証部（不図示）を含むものとする。これらの構成もＣＰＵ11がプログラムを実行することで仮想的に構成されるものである。
【０１００】
はじめに、秘密情報に対して分散符号化処理を行って、分散情報を生成する手順を説明する。図６は、本実施形態による、分散情報を生成する手順を示すフローチャートである。
【０１０１】
図６に示すように、秘密情報分割部501は、秘密情報sを秘密情報s＿1および秘密情報s＿2の２つに分割する処理を行う（ステップE1）。その際、秘密情報分割部501は、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が秘密情報sの元の集合から一様にランダムに選択された要素となるようにする。続いて、改ざん検知コード生成部100は、秘密情報s＿1と秘密情報s＿2を入力とする２入力の関数M()の出力としてチェック用データvを算出する（ステップE2）。
【０１０２】
その後、分散符号語生成部（不図示）は、秘密情報sとチェック用データvが埋め込まれた（k-1）次多項式Fを生成し、互いに異なるn個の値x1乃至xnを多項式Fに入力したときの、入力と出力との組である(x1, F(x1))乃至(xn, F(xn))を分散符号語情報として生成し、分散符号語情報を出力する（ステップE3）。
【０１０３】
次に、復元対象となる情報が入力されたとき、その情報が改ざんされているか否かを判定する手順を説明する。図７は、本実施形態による、分散情報を復元する手順を示すフローチャートである。
【０１０４】
符号語復元部（不図示）は、k組分の分散符号語情報として(x1', F＿1')乃至(xk', F＿k')が入力されると、これらの点を通る(k-1)次多項式F'を生成し、多項式F'に埋め込まれた秘密情報s'とチェック用データv'を読み出して出力する（ステップF1）。秘密情報分割部501は、s'が入力されると、s'をs'＿1とs'＿2に分割する（ステップF2）。
【０１０５】
符号語検証部（不図示）は、M(s'＿1,s'＿2)とv'が等しいか否かを判定する。その結果、符号語検証部（不図示）は、M(s'＿1,s'＿2)とv'が等しい場合、情報が改ざんされていない旨の検証結果を出力し、M(s'＿1,s'＿2)とv'が等しくない場合、情報が改ざんされている旨の検証結果を出力する（ステップF3）。
【０１０６】
本実施形態では、コード生成方法において、秘密情報sを２つの情報s2＿1とs2＿2に分割する際、乱数の元s2＿2は乱数Ｒが選ばれる集合から一様にランダムに選択された要素となるように分割し、s2＿1をsとし、s2＿2をrとして、ある関数M()にそれらを入力し、その出力をコードとしている。
【０１０７】
このような方法により、秘密情報が選ばれる集合と乱数が選ばれる集合とコードの集合上の加算を+と表すとき、秘密情報s1と乱数r1について、s1とc1 = M(s1,r1)を与えられた改ざん者がM(s1+s1' ,r1+r1')= M(s1, r1)+c1'を満たすs1'、r1'、c1'を生成するという改ざんを高い確率で検知可能となっている。
【０１０８】
そして、s2＿2の乱数性とM()の性質によって、s2＿1、s2＿2を与えられない改ざん者は、M(s2＿1+s2＿1',s2＿2+s2＿2')=M(s2＿1,s2＿2)+c'となるようなs2＿1'、s2＿2'、c'を生成することは困難となる。
【０１０９】
さらに、本実施形態では、秘密情報用データ集合Ｓの元である秘密情報sと乱数用データ集合Rの元であるrのサイズを独立に設定可能なため、パラメータを自由に設定可能となる。よって、(k,n)閾値法による分散情報の改ざんを高確率および効率的に検知可能とし、かつ、パラメータ設定の自由度を大きくすることができる。
【実施例１】
【０１１０】
本実施例は、上述した実施形態に、非特許文献３の方法を適用したものである。本実施例では、非特許文献３の方式を適用する場合を説明するが、上述した実施形態の情報改ざん検知方法の関数M()に他の方式を適用してもよい。
【０１１１】
非特許文献３の方法は、背景技術の欄で説明したように、以下の通りである。
【０１１２】
非特許文献３に開示された方法は、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)の要素として乗算をガロア体上の乗算としてもよい。
【０１１５】
次に、本実施例の動作手順を図３Ａおよび図３Ｂを参照して説明する。
【０１１６】
はじめにコード生成方法について説明する。コード生成装置500に、秘密情報sとして(Z/pZ)^｛N+1｝の要素である(s1,s2,...,s｛N+1｝)が入力された場合を例に説明する。
【０１１７】
コード生成装置500は、秘密情報分割部501に、s=(s1,s2,...,s｛N+1｝)を入力する。なお、各siは一様にランダム選ばれた値であるものとする。
【０１１８】
秘密情報分割部501は、sを、S'=(s1,s2,...,sN)とR'=s｛N+1｝と分割して出力する。ここでは、単純にs｛N+1｝をR'としたが、s1からsNのうちいずれの値でもよい。
【０１１９】
続いて、改ざん検知コード生成部100は、S'とR'が入力されると、s1*s｛N+1｝ + s2*s｛N+1｝^2 + ... + s｛N-1｝*s｛N+1｝^｛N-1｝ + s＿｛N｝*s｛N+1｝^｛N+1｝ mod p= Cとして計算する。コード生成装置500はsとcを出力する。
【０１２０】
次に、コード検証方法について説明する。
【０１２１】
コード検証装置600に、秘密情報sとして(Z/pZ)^｛N+1｝の要素であるs'= (s1', s2',...,s｛N+1｝')が入力され、チェック用データとしてc'が入力された場合を例に説明する。
【０１２２】
コード検証装置600は、秘密情報分割部501に、s'=(s1',s2',...,s｛N+1｝')を入力する。秘密情報分割装置501は、s'が入力されると、s'をS'=(s1',s2',...,sN')とR'=s｛N+1｝'とに分割して出力する。なお、ここでは単純にs｛N+1｝をR'としたが、s1からsNのうちいずれの値でもよい。
【０１２３】
続いて、コード検証装置600は、s'とr'とc'を改ざん検知コード検証部200に入力する。改ざん検知コード検証部200は、s'とr'とc'が入力されると、s1'*s｛N+1｝' + s2'*s｛N+1｝'^2 + ... + s｛N-1｝'*s｛N+1｝'^｛N-1｝ + s｛N｝'*s｛N+1｝'^｛N+1｝ mod pを計算し、計算結果をc'と比較する。改ざん検知コード検証部200は、比較の結果、これらの値が等しかった場合には改ざんが無かったことを表す記号を出力する。それ以外の場合は改ざんがあったことを表す記号を出力する。コード検証装置600は、入力のs'と改ざん検知コード検証装置200の出力結果を出力する。
【０１２４】
ここで、コード生成装置500の処理内容を詳細に見ると、s=(s1,s2,...,s｛N+1｝)とc= s1*s｛N+1｝ + s2*s｛N+1｝^2 + ... + s｛N-1｝*s｛N+1｝^｛N-1｝ + s＿｛N｝*s｛N+1｝^｛N+1｝ mod pのセットである(s1,s2,...,s｛N+1｝,c)がコードとなっている。
【０１２５】
このコードについて、(s1+d1,s2+d2,...,s｛N+1｝+d｛N+1｝,c+dc)の検証結果が正しくなるようなd1,d2,...,d｛N+1｝,dcを生成することは、非特許文献３の方式において、s= (s1, s2,...,s｛N｝)を秘密情報s｛N+1｝を乱数として生成されたチェック用データcについて、s=｛s1+d1,...,sN+dN｝を秘密情報とし、s｛N+1｝+d｛N+1｝を乱数とし、c+dcをチェック用データとしたときの検証結果が、改ざんがなかったとなるような(d1, d2,..., d｛N+1｝, dc)を生成することに他ならない。
【０１２６】
よって非特許文献３に開示された方式の持つ安全性により、改ざんの検知確率が高い値に保たれる。
【０１２７】
また、この方式においてはs｛N+1｝が選ばれる集合の大きさが非特許文献３における乱数の選ばれる集合の大きさになっている。この乱数の選ばれる集合の大きさのサイズが改ざん検知の成功確率にかかわっている。そのため、s｛N+1｝が選ばれる集合の大きさを調節することによってコードの長さと改ざんの成功確率を調整することが可能となっており、非特許文献４の方式に対してパラメータが柔軟にとれるようになっていることがわかる。
【０１２８】
そして、非特許文献４の方式では秘密情報の選ばれる集合のサイズを｜S｜とし、改ざん者による改ざんの成功確率をδとしたとき、コードの集合のサイズはおよそ｜S｜/δであった。
【０１２９】
一方、上述した方法では非特許文献３による方式の性質より、s｛N+1｝が選ばれる集合の大きさを｜s｛N+1｝｜とすると、ほぼ1/｜s｛N+1｝｜が改ざんの成功確率となる。｜s｛N+1｝｜はチェック用データのサイズとほぼ等しいため、この方式のコードの集合のサイズはおよそ｜S｜/δとなっていることがわかる。
【０１３０】
つまり、本実施例の方法では、秘密情報の集合の要素数はs*rとなり、改ざんの確率は1/r程度となる。このとき、コードの集合の要素数はおよそrとなり、非特許文献４の方式と同程度の演算効率となることがわかる。
【０１３１】
さらに、非特許文献４のsとrのサイズは非特許文献３の方式の性質によってほぼ独立に設定することが可能であるので、パラメータが自由に設定可能な方式となる。よって非特許文献４に記載されている方式と同程度の効率を持ちながら、M()として非特許文献３に開示された技術を用いることで、パラメータを自由に設定可能となる。
【産業上の利用可能性】
【０１３２】
本発明を秘密鍵などの機密情報の分散管理に利用できる。
【符号の説明】
【０１３３】
１０ 情報処理装置
１１ ＣＰＵ
１２ 主記憶部
１３ ＲＡＭ
１４ データ蓄積部
１５ メモリ制御インタフェイス部
１６ I/Oインタフェイス部
２０ 入力部
２５ 制御部
３０ 出力部
３５ 記憶部
１０１ チェック用データ生成部
２０１ 同一性判定部
５０１ 秘密情報分割部
７０１ コード生成部
７０２ コード分散部
８０１ コード復元部
８０２ コード正当性検証部
【特許請求の範囲】
【請求項１】
(k, n)閾値法により生成される情報の改ざんを検知する情報処理装置であって、
秘密情報sが入力されると、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が前記秘密情報sの元の集合から一様にランダムに選択された要素となるように、前記秘密情報sを前記秘密情報s＿1および秘密情報s＿2に分割する秘密情報分割部と、
２入力の関数M()について、前記秘密情報s＿1と前記秘密情報s＿2を入力とする関数M(s＿1, s＿2)の値をチェック用データvとして算出するコード生成部と、
前記秘密情報sと前記チェック用データvが埋め込まれた（k-1）次多項式Fを生成し、互いに異なるn個の値であるx1乃至xnを前記(k-1)次多項式Fに入力したときの、入力と出力との組である(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'が分割された秘密情報s'＿1および秘密情報s'＿2を該秘密情報分割部から受け取ると、関数M(s'＿1, s'＿2)の値と前記チェック用データv'が等しいかを否かを判定し、関数M(s'＿1, s'＿2)の値と該チェック用データv'が等しい場合、前記秘密情報s'は改ざんされていないと判定し、関数M(s'＿1, s'＿2)の値と該チェック用データv'が等しくない場合、前記秘密情報s'は改ざんされていると判定するコード検証部と、
を有する情報処理装置。
【請求項２】
pを素数とし、Nを正の整数とし、(Z/pZ)^｛N+1｝を秘密情報sの集合とし、(Z/pZ)^｛N+1｝の元を(x＿1,x＿2,...,x＿｛N+1｝)とし、さらに、*をZ/pZ上の乗算とすると、
前記秘密情報分割部は、
前記元x＿1, x＿2,..., x＿｛N+1｝のうちいずれか１つの値を選択してその値を秘密情報s＿2とし、選択した値以外を秘密情報s＿1 = (x'＿1, x'＿2,...,x'＿｛N｝)とすると、M(s＿1, s＿2)= x'＿1*s＿2 + x'＿2*s＿2^2 + ... + x'＿｛N-1｝*s＿2^｛N-1｝ + x'＿｛N｝*s＿2^｛N+1｝ mod pを計算し、計算結果を前記チェック用データvとする、請求項１に記載の情報処理装置。
【請求項３】
(k, n)閾値法により生成される情報の改ざんを検知するためのコード生成方法であって、
符号化対象の秘密情報sを、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が前記秘密情報sの元の集合から一様にランダムに選択された要素となるように、前記秘密情報s＿1および秘密情報s＿2に分割し、
２入力の関数M()について、前記秘密情報s＿1と前記秘密情報s＿2を入力とする関数M(s＿1, s＿2)の値をチェック用データvとして算出し、
前記秘密情報sと前記チェック用データvが埋め込まれた（k-1）次多項式Fを生成し、互いに異なるn個の値であるx1乃至xnを前記(k-1)次多項式Fに入力したときの、入力と出力との組である(x1, F(x1))乃至(xn, F(xn))を分散符号語情報として出力する、コード生成方法。
【請求項４】
pを素数とし、Nを正の整数とし、(Z/pZ)^｛N+1｝を秘密情報sの集合とし、(Z/pZ)^｛N+1｝の元を(x＿1,x＿2,...,x＿｛N+1｝)とし、さらに、*をZ/pZ上の乗算とすると、
前記元x＿1, x＿2,..., x＿｛N+1｝のうちいずれか１つの値を選択してその値を秘密情報s＿2とし、選択した値以外を秘密情報s＿1 = (x'＿1, x'＿2,...,x'＿｛N｝)とすると、M(s＿1, s＿2)= x'＿1*s＿2 + x'＿2*s＿2^2 + ... + x'＿｛N-1｝*s＿2^｛N-1｝ + x'＿｛N｝*s＿2^｛N+1｝ mod pを計算し、計算結果を前記チェック用データvとする、請求項３に記載のコード生成方法。
【請求項５】
(k, n)閾値法により生成された情報の改ざんを検知するためのコード検証方法であって、
（k-1）次多項式Fとして、互いに異なるn個の値であるx1乃至xnを前記(k-1)次多項式Fに入力したときの、入力と出力との組である(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を、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が前記秘密情報sの元の集合から一様にランダムに選択された要素となるように、前記秘密情報s＿1および秘密情報s＿2に分割し、
２入力の関数M()について、関数M(s＿1, s＿2)の値と前記チェック用データvが等しいかを否かを判定し、関数M(s＿1, s＿2)の値と該チェック用データvが等しい場合、前記秘密情報sは改ざんされていないと判定し、関数M(s＿1, s＿2)の値と該チェック用データvが等しくない場合、前記秘密情報sは改ざんされていると判定する、コード検証方法。
【請求項６】
pを素数とし、Nを正の整数とし、(Z/pZ)^｛N+1｝を秘密情報sの集合とし、(Z/pZ)^｛N+1｝の元を(x＿1,x＿2,...,x＿｛N+1｝)とし、さらに、*をZ/pZ上の乗算とすると、
前記元x＿1, x＿2,..., x＿｛N+1｝のうちいずれか１つの値を選択してその値を秘密情報s＿2とし、選択した値以外を秘密情報s＿1 = (x'＿1, x'＿2,...,x'＿｛N｝)とすると、M(s＿1, s＿2)= x'＿1*s＿2 + x'＿2*s＿2^2 + ... + x'＿｛N-1｝*s＿2^｛N-1｝ + x'＿｛N｝*s＿2^｛N+1｝ mod pを計算し、計算結果を前記チェック用データvとする、請求項５に記載のコード検証方法。
【請求項７】
(k, n)閾値法により生成される情報の改ざんを検知するためのコードを生成するコンピュータに実行させるプログラムであって、
符号化対象の秘密情報sが入力されると、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が前記秘密情報sの元の集合から一様にランダムに選択された要素となるように、前記秘密情報sを前記秘密情報s＿1および秘密情報s＿2に分割し、
２入力の関数M()について、前記秘密情報s＿1と前記秘密情報s＿2を入力とする関数M(s＿1, s＿2)の値をチェック用データvとして算出し、
前記秘密情報sと前記チェック用データvが埋め込まれた（k-1）次多項式Fを生成し、互いに異なるn個の値であるx1乃至xnを前記(k-1)次多項式Fに入力したときの、入力と出力との組である(x1, F(x1))乃至(xn, F(xn))を分散符号語情報として出力する処理を前記コンピュータに実行させるためのプログラム。
【請求項８】
(k, n)閾値法により生成された情報の改ざんを検知するためのコードを検証するコンピュータに実行させるプログラムであって、
（k-1）次多項式Fとして、互いに異なるn個の値であるx1乃至xnを前記(k-1)次多項式Fに入力したときの、入力と出力との組である(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を、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が前記秘密情報sの元の集合から一様にランダムに選択された要素となるように、前記秘密情報s＿1および秘密情報s＿2に分割し、
２入力の関数M()について、関数M(s＿1, s＿2)の値と前記チェック用データvが等しいかを否かを判定し、関数M(s＿1, s＿2)の値と該チェック用データvが等しい場合、前記秘密情報sは改ざんされていないと判定し、関数M(s＿1, s＿2)の値と該チェック用データvが等しくない場合、前記秘密情報sは改ざんされていると判定する処理を前記コンピュータに実行させるためのプログラム。
【請求項９】
pを素数とし、Nを正の整数とし、(Z/pZ)^｛N+1｝を秘密情報sの集合とし、(Z/pZ)^｛N+1｝の元を(x＿1,x＿2,...,x＿｛N+1｝)とし、さらに、*をZ/pZ上の乗算とすると、
前記元x＿1, x＿2,..., x＿｛N+1｝のうちいずれか１つの値を選択してその値を秘密情報s＿2とし、選択した値以外を秘密情報s＿1 = (x'＿1, x'＿2,...,x'＿｛N｝)とすると、M(s＿1, s＿2)= x'＿1*s＿2 + x'＿2*s＿2^2 + ... + x'＿｛N-1｝*s＿2^｛N-1｝ + x'＿｛N｝*s＿2^｛N+1｝ mod pを計算し、計算結果を前記チェック用データvとする、請求項７または８に記載のプログラム。
【請求項１】
(k, n)閾値法により生成される情報の改ざんを検知する情報処理装置であって、
秘密情報sが入力されると、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が前記秘密情報sの元の集合から一様にランダムに選択された要素となるように、前記秘密情報sを前記秘密情報s＿1および秘密情報s＿2に分割する秘密情報分割部と、
２入力の関数M()について、前記秘密情報s＿1と前記秘密情報s＿2を入力とする関数M(s＿1, s＿2)の値をチェック用データvとして算出するコード生成部と、
前記秘密情報sと前記チェック用データvが埋め込まれた（k-1）次多項式Fを生成し、互いに異なるn個の値であるx1乃至xnを前記(k-1)次多項式Fに入力したときの、入力と出力との組である(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'が分割された秘密情報s'＿1および秘密情報s'＿2を該秘密情報分割部から受け取ると、関数M(s'＿1, s'＿2)の値と前記チェック用データv'が等しいかを否かを判定し、関数M(s'＿1, s'＿2)の値と該チェック用データv'が等しい場合、前記秘密情報s'は改ざんされていないと判定し、関数M(s'＿1, s'＿2)の値と該チェック用データv'が等しくない場合、前記秘密情報s'は改ざんされていると判定するコード検証部と、
を有する情報処理装置。
【請求項２】
pを素数とし、Nを正の整数とし、(Z/pZ)^｛N+1｝を秘密情報sの集合とし、(Z/pZ)^｛N+1｝の元を(x＿1,x＿2,...,x＿｛N+1｝)とし、さらに、*をZ/pZ上の乗算とすると、
前記秘密情報分割部は、
前記元x＿1, x＿2,..., x＿｛N+1｝のうちいずれか１つの値を選択してその値を秘密情報s＿2とし、選択した値以外を秘密情報s＿1 = (x'＿1, x'＿2,...,x'＿｛N｝)とすると、M(s＿1, s＿2)= x'＿1*s＿2 + x'＿2*s＿2^2 + ... + x'＿｛N-1｝*s＿2^｛N-1｝ + x'＿｛N｝*s＿2^｛N+1｝ mod pを計算し、計算結果を前記チェック用データvとする、請求項１に記載の情報処理装置。
【請求項３】
(k, n)閾値法により生成される情報の改ざんを検知するためのコード生成方法であって、
符号化対象の秘密情報sを、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が前記秘密情報sの元の集合から一様にランダムに選択された要素となるように、前記秘密情報s＿1および秘密情報s＿2に分割し、
２入力の関数M()について、前記秘密情報s＿1と前記秘密情報s＿2を入力とする関数M(s＿1, s＿2)の値をチェック用データvとして算出し、
前記秘密情報sと前記チェック用データvが埋め込まれた（k-1）次多項式Fを生成し、互いに異なるn個の値であるx1乃至xnを前記(k-1)次多項式Fに入力したときの、入力と出力との組である(x1, F(x1))乃至(xn, F(xn))を分散符号語情報として出力する、コード生成方法。
【請求項４】
pを素数とし、Nを正の整数とし、(Z/pZ)^｛N+1｝を秘密情報sの集合とし、(Z/pZ)^｛N+1｝の元を(x＿1,x＿2,...,x＿｛N+1｝)とし、さらに、*をZ/pZ上の乗算とすると、
前記元x＿1, x＿2,..., x＿｛N+1｝のうちいずれか１つの値を選択してその値を秘密情報s＿2とし、選択した値以外を秘密情報s＿1 = (x'＿1, x'＿2,...,x'＿｛N｝)とすると、M(s＿1, s＿2)= x'＿1*s＿2 + x'＿2*s＿2^2 + ... + x'＿｛N-1｝*s＿2^｛N-1｝ + x'＿｛N｝*s＿2^｛N+1｝ mod pを計算し、計算結果を前記チェック用データvとする、請求項３に記載のコード生成方法。
【請求項５】
(k, n)閾値法により生成された情報の改ざんを検知するためのコード検証方法であって、
（k-1）次多項式Fとして、互いに異なるn個の値であるx1乃至xnを前記(k-1)次多項式Fに入力したときの、入力と出力との組である(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を、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が前記秘密情報sの元の集合から一様にランダムに選択された要素となるように、前記秘密情報s＿1および秘密情報s＿2に分割し、
２入力の関数M()について、関数M(s＿1, s＿2)の値と前記チェック用データvが等しいかを否かを判定し、関数M(s＿1, s＿2)の値と該チェック用データvが等しい場合、前記秘密情報sは改ざんされていないと判定し、関数M(s＿1, s＿2)の値と該チェック用データvが等しくない場合、前記秘密情報sは改ざんされていると判定する、コード検証方法。
【請求項６】
pを素数とし、Nを正の整数とし、(Z/pZ)^｛N+1｝を秘密情報sの集合とし、(Z/pZ)^｛N+1｝の元を(x＿1,x＿2,...,x＿｛N+1｝)とし、さらに、*をZ/pZ上の乗算とすると、
前記元x＿1, x＿2,..., x＿｛N+1｝のうちいずれか１つの値を選択してその値を秘密情報s＿2とし、選択した値以外を秘密情報s＿1 = (x'＿1, x'＿2,...,x'＿｛N｝)とすると、M(s＿1, s＿2)= x'＿1*s＿2 + x'＿2*s＿2^2 + ... + x'＿｛N-1｝*s＿2^｛N-1｝ + x'＿｛N｝*s＿2^｛N+1｝ mod pを計算し、計算結果を前記チェック用データvとする、請求項５に記載のコード検証方法。
【請求項７】
(k, n)閾値法により生成される情報の改ざんを検知するためのコードを生成するコンピュータに実行させるプログラムであって、
符号化対象の秘密情報sが入力されると、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が前記秘密情報sの元の集合から一様にランダムに選択された要素となるように、前記秘密情報sを前記秘密情報s＿1および秘密情報s＿2に分割し、
２入力の関数M()について、前記秘密情報s＿1と前記秘密情報s＿2を入力とする関数M(s＿1, s＿2)の値をチェック用データvとして算出し、
前記秘密情報sと前記チェック用データvが埋め込まれた（k-1）次多項式Fを生成し、互いに異なるn個の値であるx1乃至xnを前記(k-1)次多項式Fに入力したときの、入力と出力との組である(x1, F(x1))乃至(xn, F(xn))を分散符号語情報として出力する処理を前記コンピュータに実行させるためのプログラム。
【請求項８】
(k, n)閾値法により生成された情報の改ざんを検知するためのコードを検証するコンピュータに実行させるプログラムであって、
（k-1）次多項式Fとして、互いに異なるn個の値であるx1乃至xnを前記(k-1)次多項式Fに入力したときの、入力と出力との組である(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を、秘密情報s＿1および秘密情報s＿2からなる２つの分割情報のうち少なくとも一方が前記秘密情報sの元の集合から一様にランダムに選択された要素となるように、前記秘密情報s＿1および秘密情報s＿2に分割し、
２入力の関数M()について、関数M(s＿1, s＿2)の値と前記チェック用データvが等しいかを否かを判定し、関数M(s＿1, s＿2)の値と該チェック用データvが等しい場合、前記秘密情報sは改ざんされていないと判定し、関数M(s＿1, s＿2)の値と該チェック用データvが等しくない場合、前記秘密情報sは改ざんされていると判定する処理を前記コンピュータに実行させるためのプログラム。
【請求項９】
pを素数とし、Nを正の整数とし、(Z/pZ)^｛N+1｝を秘密情報sの集合とし、(Z/pZ)^｛N+1｝の元を(x＿1,x＿2,...,x＿｛N+1｝)とし、さらに、*をZ/pZ上の乗算とすると、
前記元x＿1, x＿2,..., x＿｛N+1｝のうちいずれか１つの値を選択してその値を秘密情報s＿2とし、選択した値以外を秘密情報s＿1 = (x'＿1, x'＿2,...,x'＿｛N｝)とすると、M(s＿1, s＿2)= x'＿1*s＿2 + x'＿2*s＿2^2 + ... + x'＿｛N-1｝*s＿2^｛N-1｝ + x'＿｛N｝*s＿2^｛N+1｝ mod pを計算し、計算結果を前記チェック用データvとする、請求項７または８に記載のプログラム。
【図１】
【図２】
【図３Ａ】
【図３Ｂ】
【図４】
【図５】
【図６】
【図７】
【図８Ａ】
【図８Ｂ】
【図９】
【図１０】
【図１１Ａ】
【図１１Ｂ】
【図１２Ａ】
【図１２Ｂ】
【図２】
【図３Ａ】
【図３Ｂ】
【図４】
【図５】
【図６】
【図７】
【図８Ａ】
【図８Ｂ】
【図９】
【図１０】
【図１１Ａ】
【図１１Ｂ】
【図１２Ａ】
【図１２Ｂ】
【公開番号】特開２０１１−１３４２８（Ｐ２０１１−１３４２８Ａ）
【公開日】平成２３年１月２０日（２０１１．１．２０）
【国際特許分類】
【出願番号】特願２００９−１５６９０４（Ｐ２００９−１５６９０４）
【出願日】平成２１年７月１日（２００９．７．１）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２３年１月２０日（２０１１．１．２０）
【国際特許分類】
【出願日】平成２１年７月１日（２００９．７．１）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]