(57)【特許請求の範囲】
【請求項１】
xは拡大体GF(xq)を生成する既約多項式f[X]の元Xであり、n, kは2以上の整数であり、n≧2k-1であり、p0, …, pk-1は0以上n未満の相異なる整数であり、Aは次式で定義されるn行k列の行列であり、
【数２３】
0005957120.tif 000024
分散装置が、乱数r0, …, rk-2∈GF(xq)を生成する乱数生成ステップと、
上記分散装置が、上記乱数r0, …, rk-2と平文s∈GF(xq)を要素とするベクトルa=(r0, …, rk-2, s)と上記行列Aとの乗算を計算することでシェアb0, …, bn-1を生成するシェア生成ステップと、
復元装置が、上記シェアb0, …, bn-1から選択したk個のシェアbp0, …, bpk-1を要素とするベクトルb'=(bp0, …, bpk-1)を生成するシェア選択ステップと、
上記復元装置が、上記行列Aのp0, …, pk-1行目からなるk次正方行列の逆行列A'-1を生成する逆行列生成ステップと、
上記復元装置が、上記逆行列A'-1のk行目とベクトルb'を乗算して上記平文sを復元する平文計算ステップと、
を含む秘密分散方法。
【請求項２】
請求項１に記載の秘密分散方法であって、
qは拡大体GF(xq)の拡大次数であり、dは既約多項式f[X]から最高次項を除いた多項式f'の最高次項の次数であり、m=n-kであり、(m-1)(k-1)≦q-dであり、
上記シェア生成ステップは、i∈{0, …, m-1}について次式により値ciを計算し、上記値ciのq次以上の部分をXqで割った多項式hiと、上記値ciのq次未満の部分である多項式giとを用いて、gi-hif'を計算して上記値ciを更新し、上記値c0, …, cm-1を上記シェアb0, …, bn-1とするものである、
【数２４】
0005957120.tif 000025
秘密分散方法。
【請求項３】
請求項１に記載の秘密分散方法であって、
qは拡大体GF(xq)の拡大次数であり、dは既約多項式f[X]から最高次項を除いた多項式f'の最高次項の次数であり、m=n-kであり、
上記シェア生成ステップは、j∈{0, …, k-1}についてa'j=aj, dj=0とし、i∈{0, …, m-1}について次式により値ciを計算し、上記値ciのq次以上の部分をXqで割った多項式hiと、上記値ciのq次未満の部分である多項式giとを用いて、gi-hif'を計算して上記値ciを更新し、i∈{0, …, m-1}, j∈{0, …, k-1}について、i≠m-1、かつ、(i+1)j-d≧q-dであれば、a'j:=a'jxα, dj:=dj+αと更新し、上記値c0, …, cm-1を上記シェアb0, …, bn-1とするものである、
【数２５】
0005957120.tif 000026
秘密分散方法。
【請求項４】
分散装置と復元装置とを含む秘密分散システムであって、
xは拡大体GF(xq)を生成する既約多項式f[X]の元Xであり、n, kは2以上の整数であり、n≧2k-1であり、p0, …, pk-1は0以上n未満の相異なる整数であり、Aは次式で定義されるn行k列の行列であり、
【数２６】
0005957120.tif 000027
上記分散装置は、
乱数r0, …, rk-2∈GF(xq)を生成する乱数生成部と、
上記乱数r0, …, rk-2と平文s∈GF(xq)を要素とするベクトルa=(r0, …, rk-2, s)と上記行列Aとの乗算を計算することでシェアb0, …, bn-1を生成するシェア生成部と、
を含み、
上記復元装置は、
上記シェアb0, …, bn-1から選択したk個のシェアbp0, …, bpk-1を要素とするベクトルb'=(bp0, …, bpk-1)を生成するシェア選択部と、
上記行列Aのp0, …, pk-1行目からなるk次正方行列の逆行列A'-1を生成する逆行列生成部と、
上記逆行列A'-1のk行目とベクトルb'を乗算して上記平文sを復元する平文計算部と、
を含む秘密分散システム。
【請求項５】
xは拡大体GF(xq)を生成する既約多項式f[X]の元Xであり、n, kは2以上の整数であり、n≧2k-1であり、p0, …, pk-1は0以上n未満の相異なる整数であり、Aは次式で定義されるn行k列の行列であり、
【数２７】
0005957120.tif 000028
乱数r0, …, rk-2∈GF(xq)を生成する乱数生成部と、
上記乱数r0, …, rk-2と平文s∈GF(xq)を要素とするベクトルa=(r0, …, rk-2, s)と上記行列Aとの乗算を計算することでシェアb0, …, bn-1を生成するシェア生成部と、
を含む分散装置。
【請求項６】
請求項５に記載の分散装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、秘密分散技術に関し、特に、情報理論型秘密分散の計算量を低減する技術に関する。
【背景技術】
【０００２】
従来の情報理論型秘密分散には、例えば、非特許文献１に記載されたShamirの秘密分散や、非特許文献２に記載されたXORベースの秘密分散がある。
【０００３】
Shamirの秘密分散およびXORベースの秘密分散は(k,n)-秘密分散の一つである。(k,n)-秘密分散は、入力された平文をn個に分割した分散値をn個のパーティに分散して保持しておき、任意のk個のシェアが揃えば平文を復元でき、k個未満のシェアからは平文に関する一切の情報を得られないような秘密分散である。このとき、n, kは2以上の整数であり、n≧2k-1である。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】A. Shamir, “How to share a secret”, Communications of the ACM, vol. 22(11), pp. 612-613, 1979.
【非特許文献２】J. Kurihara, S. Kiyomoto, K. Fukushima, and T. Tanaka, “On a Fast (k,n)-Threshold Secret Sharing Scheme”, IEICE Transactions, vol. 91-A(9), pp. 2365-2378, 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１に記載されたShamirの秘密分散では計算量が大きいという課題がある。具体的には、Shamirの秘密分散では(k-1)n回の体乗算を要する。非特許文献２に記載されたXORベースの秘密分散では対応できるk, nの値が限定されており、パラメータの柔軟性が欠ける。k, nの値はセキュリティ強度とデータ容量に直結するため、柔軟に対応できることが望ましい。
【０００６】
この発明の目的は、このような点に鑑みて、任意のk, nに対応し、従来よりも計算量を低減することができる秘密分散技術を提供することである。
【課題を解決するための手段】
【０００７】
上記の課題を解決するために、この発明の秘密分散方法は、xは拡大体GF(xq)を生成する既約多項式f[X]の元Xであり、n, kは2以上の整数であり、n≧2k-1であり、p0, …, pk-1は0以上n未満の相異なる整数であり、Aは次式で定義されるn行k列の行列であり、
【０００８】
【数１】
0005957120.tif 000002
【０００９】
分散装置が、乱数r0, …, rk-2∈GF(xq)を生成する乱数生成ステップと、分散装置が、乱数r0, …, rk-2と平文s∈GF(xq)を要素とするベクトルa=(r0, …, rk-2, s)と行列Aとの乗算を計算することでシェアb0, …, bn-1を生成するシェア生成ステップと、復元装置が、シェアb0, …, bn-1から選択したk個のシェアbp0, …, bpk-1を要素とするベクトルb'=(bp0, …, bpk-1)を生成するシェア選択ステップと、復元装置が、行列Aのp0, …, pk-1行目からなるk次正方行列の逆行列A'-1を生成する逆行列生成ステップと、復元装置が、逆行列A'-1のk行目とベクトルb'を乗算して平文sを復元する平文計算ステップと、を含む。
【発明の効果】
【００１０】
この発明の秘密分散技術は、任意のk, nに対応し、従来よりも計算量が低い。
【図面の簡単な説明】
【００１１】
【図１】図１は、秘密分散システムの機能構成を例示する図である。
【図２】図２は、秘密分散装置の機能構成を例示する図である。
【図３】図３は、秘密分散方法の処理フローを例示する図である。
【発明を実施するための形態】
【００１２】
実施形態の説明に先立ち、この発明の原理について説明する。
【００１３】
前提として、以下の説明では、xは既約多項式をf[X]=X64+X4+X3+X2+X+1とする拡大体GF(264)の元Xである。xを整数表現すると2である。
【００１４】
GF(264)は多項式を、mod 2整数を係数とする64次多項式f(x)で割った（多項式としての割り算）余りの集合である。体であり四則演算を行うことができる。特殊な演算をもつビットの64次ベクトルと考えてもよい。GF(264)は64ビット整数で表現でき、項xiを2iで表現する。例えば、1+x+x3は、20+21+23=11と表現できる。
【００１５】
この発明の秘密分散は、誤り訂正符号のリード・ソロモン符号（Reed-Solomon Codes）を応用して構成されたものである。リード・ソロモン符号については、例えば下記参考文献１に記載されている。
〔参考文献１〕バァナード・スカラー著、「ディジタル通信 基本と応用」、ピアソン・エデュケーション、2006年
【００１６】
誤り訂正符号の符号化処理は、平文の入力ベクトルaに線形変換（つまり行列）Aを乗じて出力ベクトルbを得る処理として、式（１）により表現できる。すなわち、行列Aのi番目の行は、出力ベクトルbのi番目の要素biを生成するために入力ベクトルaの各要素に乗じる係数を表す。
b = Aa        …（１）
【００１７】
誤り訂正符号の復号処理も線形変換と見ることができる。A', b'をA, bのうち利用するk個の要素に対応する行だけを抜き出した行列もしくはベクトルとして、式（２）により表現できる。
b' = A'a        …（２）
【００１８】
したがって、行列Aに逆行列が存在すれば、式（３）により復号できる。
a = A'-1b'        …（３）
【００１９】
誤り訂正符号の符号化では、入力ベクトルaは式（４）で表されるk次のベクトルとする。ただし、kは2以上の整数である。
【００２０】
【数２】
0005957120.tif 000003
【００２１】
出力ベクトルbは式（５）で表されるn次のベクトルとする。ただし、nは2以上の整数であり、n≧2k-1である。
【００２２】
【数３】
0005957120.tif 000004
【００２３】
行列Aは、式（６）で表されるk行k列の単位行列とm行k列のファンデルモンデ行列（Vandermonde matrix）を縦に連結した行列である。ただし、m=n-kである。ファンデルモンデ行列とは、行または列の行列要素に等比数列の各項が順番にならんでいる特別な構成の行列である。
【００２４】
【数４】
0005957120.tif 000005
【００２５】
つまり、行列Aは式（７）のようなn行k列の行列である。
【００２６】
【数５】
0005957120.tif 000006
【００２７】
行列Aは、k行目までは単位行列であるため、出力ベクトルbのk行目までの要素b0, …, bk-1は入力ベクトルaの要素a0, …, ak-1と一致する。出力ベクトルbにおいて入力ベクトルaの要素と一致する要素をデータシェアと呼び、それ以外の要素をパリティシェアと呼ぶ。
【００２８】
この発明の秘密分散技術は、上述した誤り訂正符号を応用して情報理論型秘密分散を構成したものである。具体的には以下のようにして情報理論型秘密分散を構成することができる。まず、情報理論型秘密分散を、誤り訂正符号と同様に、行列Aを用いた線形変換と捉える。この発明の情報理論型秘密分散の分散処理では、入力ベクトルaは、r0,…,rk-2を乱数とし、sを平文として、式（８）で表されるk次のベクトルとする。すなわち、入力ベクトルaは、k-1行目までの要素が乱数であり、k行目の要素が平文のベクトルである。
【００２９】
【数６】
0005957120.tif 000007
【００３０】
出力ベクトルbは、誤り訂正符号の符号化と同様であり、式（９）で表されるn次のベクトルとする。
【００３１】
【数７】
0005957120.tif 000008
【００３２】
誤り訂正符号の行列Aはk行目までが単位行列であるため、情報理論型秘密分散の入力ベクトルaを乗ずると、出力ベクトルbのk行目の要素がbk-1=sとなる。秘密分散では秘匿性のために平文をそのままシェアとすることは禁じられる。そのため、情報理論型秘密分散の行列Aは、式（10）で表されるように、誤り訂正符号と異なり、k-1行目までが単位行列であり、k行目からファンデルモンデ行列となる。
【００３３】
【数８】
0005957120.tif 000009
【００３４】
つまり、行列Aは式（11）のようなn行k列の行列である。
【００３５】
【数９】
0005957120.tif 000010
【００３６】
この発明の情報理論型秘密分散の復元処理では、入力ベクトルaの各要素のうちk行目の要素に設定された平文sのみを復元できればよいので、1回のk次元線形結合で復元できる。復元に利用するk個のシェアb'0, …, b'k-1に対応する行を抜き出した行列A'を生成し、その行列A'の逆行列A'-1のk行目と、k個のシェアb'0, …, b'k-1からなるベクトルとの内積により平文sを求めることができる。
【００３７】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００３８】
［第一実施形態］
第一実施形態の秘密分散システムは、図１に例示するように、n（≧3）台の秘密分散装置１0,…,１n-1を含む。この実施形態では、秘密分散装置１0,…,１n-1はそれぞれ通信網２へ接続される。通信網２は、接続される各装置が相互に通信可能なように構成された回線交換方式もしくはパケット交換方式の通信網であり、例えばインターネットやLAN（Local Area Network）、WAN（Wide Area Network）などを用いることができる。なお、各装置は必ずしも通信網２を介してオンラインで通信可能である必要はない。例えば、秘密分散装置１i（i∈{0,…,n-1}）へ入力する情報を磁気テープやUSBメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体からオフラインで入力するように構成してもよい。
【００３９】
秘密分散装置１は、図２に例示するように、シェア記憶部１０、入力部１１、乱数生成部１２、行列生成部１３、シェア生成部１４、シェア選択部１５、逆行列生成部１６、および平文計算部１７を含む。この秘密分散装置１が、図３に例示する各ステップの処理を行うことにより第一実施形態の秘密分散方法が実現される。
【００４０】
秘密分散装置１は、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。秘密分散装置１は、例えば、中央演算処理装置の制御のもとで各処理を実行する。秘密分散装置１に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。秘密分散装置１の各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
【００４１】
秘密分散装置１の備えるシェア記憶部１０は、例えば、RAM（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【００４２】
図３を参照して、第一実施形態の秘密分散方法の処理手続きを説明する。
【００４３】
秘密分散方法は分散処理と復元処理とに分かれる。分散処理および復元処理は、n台の秘密分散装置１0, …, １n-1から任意に選択された1台の秘密分散装置１i（i∈{0,…,n-1}）のみが実行する。分散処理を実行する秘密分散装置と復元処理を実行する秘密分散装置は同一の装置であってもよいし、異なる装置であってもよい。以降の説明では、分散処理を行う秘密分散装置を分散装置と呼び、復元処理を行う秘密分散装置を復元装置と呼ぶ。
【００４４】
ステップＳ１１において、分散装置の入力部１１へ平文s∈GF(xq)が入力される。平文sはシェア生成部１４へ送られる。
【００４５】
ステップＳ１２において、分散装置の乱数生成部１２は、k-1個の乱数r0, …, rk-2∈GF(xq)を生成する。乱数r0, …, rk-2はシェア生成部１４へ送られる。乱数生成部１１は、逐一ランダムに乱数生成器を用いてk-1個の乱数r0, …, rk-2を生成してもよいし、事前に生成されメモリに格納されている複数個の値から所定の規則に従ってk-1個の値を選択して乱数r0, …, rk-2を生成してもよい。
【００４６】
ステップＳ１３において、分散装置の行列生成部１３は、式（12）で定義されるn行k列の行列Aを生成する。行列Aはシェア生成部１４へ送られる。行列Aはn, kが定まれば計算できるため、あらかじめ生成しておいてもよい。その場合、行列生成部１３は、あらかじめ生成し記憶しておいた行列Aを読み込むだけでよい。
【００４７】
【数１０】
0005957120.tif 000011
【００４８】
ステップＳ１４において、分散装置のシェア生成部１４は、k次ベクトルa=(r0, …, rk-2, s)を生成し、ベクトルaと行列Aとの乗算を計算することでn次ベクトルb=(b0, …, bn-1)を求める。ベクトルbの0番目からk-2番目の要素b0, …, bk-2には、乱数r0, …, rk-2がそのまま設定される。ベクトルbの残りの要素bk-1, …, bn-1には、m=n-kとし、i=0, …, m-1について式（13）を計算して得られる値c0, …, cm-1がそれぞれ設定される。
【００４９】
【数１１】
0005957120.tif 000012
【００５０】
シェア生成部１４は、ベクトルbの各要素をn個のシェアb0, …, bn-1として生成し、n台の秘密分散装置１0,…,１n-1へそれぞれ分散して送信する。シェアbiを受信した秘密分散装置１iは、シェアbiをシェア記憶部１０へ記憶する。
【００５１】
以上で分散処理は完了となる。続いて復元処理を説明する。
【００５２】
ステップＳ１５において、復元装置のシェア選択部１５は、利用可能な任意のk個のシェアbp0,…,bpk-1を取得し、k次ベクトルb'=(bp0,…,bpk-1)を生成する。ただし、p0,…,pk-1は復元に用いるシェアの番号であり、0以上n未満の整数から選択したk個の相異なる整数である。ベクトルb'は平文計算部１７へ送られる。p0,…,pk-1は逆行列生成部１６へ送られる。
【００５３】
ステップＳ１６において、復元装置の逆行列生成部１６は、行列Aのp0,…,pk-1行目を抜き出したk次正方行列を生成し、その逆行列A'-1を計算する。逆行列A'-1は平文計算部１７へ送られる。
【００５４】
ステップＳ１７において、復元装置の平文計算部１７は、逆行列A'-1のk行目とベクトルb'=(bp0,…,bpk-1)を乗算して、平文sを復元する。
【００５５】
Shamirの秘密分散では分散処理における乗算数が(k-1)nである。本形態の秘密分散システムでは分散処理における乗算数が(k-1)(n-k+1)である。したがって、本形態の秘密分散システムによれば秘密分散の計算量を低減することができる。
【００５６】
［第二実施形態］
a, b∈GF(264)の乗算は、2つの63次多項式a, b（式（14））を掛けてから64次多項式fで割る操作である（式（15））。このとき、λ次の項の係数は式（16）となる。
【００５７】
【数１２】
0005957120.tif 000013
【００５８】
式（15）において、126次多項式をmod fして63次多項式にする処理をリダクションと呼ぶ。リダクションは、式（17）の同値関係を用いて処理する。
f=x64+x4+x3+x+1=0 mod f        …（17）
【００５９】
式（17）を変形すると、式（18）に示すように64次項を4次式に落とす関係となる。
x64=x4+x3+x+1 mod f        …（18）
【００６０】
式（19）に示すように、64次以上の項もすべて60次次数を下げられる。
x64+n=xn(x4+x3+x+1) mod f        …（19）
【００６１】
126次多項式を、63次多項式gと62次多項式hを用いて、式（20）のように表すことができる。
g+x64h=g+(x4+x3+x+1)h mod f        …（20）
【００６２】
ある任意の要素aとx+1との乗算(x+1)aは、式（21）で表すことができる。
【００６３】
【数１３】
0005957120.tif 000014
【００６４】
また、xnaはaの各項がn次高い項となるので、整数表現における2n倍、もしくはnビット左シフトと等価である。したがって、式（22）のように表すことができる。
【００６５】
【数１４】
0005957120.tif 000015
【００６６】
hは62次多項式であるため、式（22）の
【００６７】
【数１５】
0005957120.tif 000016
【００６８】
は64次以上の多項式となり、再度次数を下げる必要がある。64次以上の部分は式（23）のようになる。
【００６９】
【数１６】
0005957120.tif 000017
【００７０】
64ビット整数内では64ビットを超えたビットは切り捨てられることを考慮すると、式（24）を計算すればよい。
【００７１】
【数１７】
0005957120.tif 000018
【００７２】
乗算の際、片方が61ビット以内のとき（より正確には両方のビット数を足して125以下のとき）、式（25）が成り立つため、リダクションを効率化できる。
【００７３】
【数１８】
0005957120.tif 000019
【００７４】
したがって、リダクションまで含めて考えると、61ビット数で1ビットだけが立っている数、つまり0≦i≦60の範囲での2iとの乗算は高速である。
【００７５】
この発明の秘密分散ではファンデルモンデ行列を用いてパリティシェアを生成する。ベクトルaをa=(a0, …, ak-1∈GF(xq))と表すと、パリティシェアは式（26）により計算される。ただし、GF(xq)は既約多項式f[X]により生成され、拡大次数をqとする拡大体である。xは既約多項式f[X]の元であり、f[X]=Xである。
【００７６】
【数１９】
0005957120.tif 000020
【００７７】
このとき、体がサイズの大きな拡大体のときには効率化ができる。既約多項式fのうち、最高次項を除いた多項式をf'とする。多項式f'の最高次項の次数をdとする。すると、(m-1)(k-1)≦q-dを満たすとき、乗算が以下のように通常よりも簡単になる。
【００７８】
iがq未満のとき、xi=Xiである。入力aを式（27）とすると、多項式乗算の結果は、式（28）となる。
【００７９】
【数２０】
0005957120.tif 000021
【００８０】
ここで次数がq次以上となるので、f≡0⇔Xq≡-f'を用いて、fによる剰余をとる。つまり、aXiのうちq次未満の部分をg、q次以上の部分をXqで割った多項式hとおくと、aXi≡g-hf'と表される。拡大体乗算では通常、このような次数削減をg-hf'がq-1次となるまで繰り返す。このときiがq-d以下だと、aXiの次数はたかだかq-1+q-d≡2q-d-1であり、hの次数はたかだかq-d-1となる。f'がd次多項式なので、hf'の次数はたかだかq-1となり、次数削減が1回で済む。
【００８１】
ステップＳ１４において、以下のように構成することで、より効率的に計算することが可能となる。なお、(m-1)(k-1)≦q-dが成り立つものとする。
【００８２】
ステップＳ１４において、分散装置のシェア生成部１４は、i∈{0, …, m-1}について、式（29）により値ciを計算する。
【００８３】
【数２１】
0005957120.tif 000022
【００８４】
値ciのq次以上の部分をXqで割った多項式hiと、値ciのq次未満の部分である多項式giとを生成する。この多項式hiと多項式giとを用いて、gi-hif'を計算し、値ciを更新する。こうして求めた値c0, …, cm-1をベクトルbの要素bk-1, …, bn-1とする。
【００８５】
第二実施形態の分散方法では、(m-1)(k-1)≦q-dが成り立つため、すべての体乗算においてリダクションが1回で済むようになっている。そのため、リダクションを含めた乗算の処理量が低減する。
【００８６】
［第三実施形態］
第二実施形態では、(m-1)(k-1)≦q-dが成り立つ必要があった。第三実施形態では、(m-1)(k-1)≦q-dを満たさない場合でも体乗算の処理量を低減するように拡張する。
【００８７】
ステップＳ１４において、分散装置のシェア生成部１４は、j∈{0, …, k-1}について、a'j=ajとする。また、dj=0とする。その後、i∈{0, …, m-1}について、式（30）により値ciを計算する。
【００８８】
【数２２】
0005957120.tif 000023
【００８９】
値ciのq次以上の部分をXqで割った多項式hiと、値ciのq次未満の部分である多項式giとを生成する。この多項式hiと多項式giとを用いて、gi-hif'を計算し、値ciを更新する。そして、i∈{0, …, m-1}, j∈{0, …, k-1}について、i≠m-1、かつ、(i+1)j-d≧q-dであれば、a'j:=a'jxα, dj:=dj+αと更新する。ここで、αはq-d以下の正の整数である。こうして求めた値c0, …, cm-1をベクトルbの要素bk-1, …, bn-1とする。
【００９０】
第三実施形態では、第二実施形態ほどには処理量の削減はできないが、適切なαを設定すれば、十分高速化に有効である。
【００９１】
誤り訂正符号では入力をそのままシェアとすることができるが、秘密分散では入力をそのままシェアとすることができない。逆に、秘密分散であっても乱数をそのままシェアとしてもよい。この発明のポイントは、これらの点を考慮して、安全性を担保しながら演算を省いたことにある。
【００９２】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００９３】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００９４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００９５】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００９６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００９７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００９８】
１  秘密計算装置
１０  シェア記憶部
１１  入力部
１２  乱数生成部
１３  行列生成部
１４  シェア生成部
１５  シェア選択部
１６  逆行列生成部
１７  平文計算部
【要約】      （修正有）【課題】任意のk,nに対応し、計算量を低減する秘密分散方法を提供する。【解決手段】乱数生成部１２が、乱数r0,…,rk-2∈GF(xq)を生成する。シェア生成部１４が、乱数r0,…,rk-2と平文s∈GF(xq)を要素とするベクトルa=(r0,…,rk-2,s)と行列Aとの乗算を計算することでシェアb0,…,bn-1を生成する。シェア選択部１５が、シェアb0,…,bn-1から選択したk個のシェアbp0,…,bpk-1を要素とするベクトルb'=(bp0,…,bpk-1)を生成する。逆行列生成部１６が、行列Aのp0,…,pk-1行目からなるk次正方行列の逆行列A'-1を生成する。平文計算部１７が、逆行列A'-1のk行目とベクトルb'を乗算して平文sを復元する。【選択図】図２【図１】
0005957120.tif 000029
【図２】
0005957120.tif 000030
【図３】
0005957120.tif 000031