(57)【特許請求の範囲】
【請求項１】
xは拡大体GF(xq)を生成する既約多項式f[X]の元Xであり、n, kは2以上の整数であり、n≧2k-1であり、mは1以上の整数であり、m=n-kであり、aはa0, …, ak-1∈GF(xq)を要素とするk次ベクトルであり、Aは次式で定義されるn行k列の行列であり、
【数２７】
0005918884.tif 000029
bはb0, …, bn-1∈GF(xq)を要素とし上記ベクトルaと上記行列Aを乗じて得たn次ベクトルであり、φは1以上m以下の整数であり、d0, …, dk-φ-1は0以上k未満の相異なる整数であり、e0, …, eφ-1は0以上k未満かつd0, …, dk-φ-1と重複しない相異なる整数であり、p0, …, pφ-1はk以上n未満の相異なる整数であり、
上記ベクトルbのφ個の要素bp0, …, bpφ-1を用いて、次式によりφ次のベクトルb'を生成するベクトル変換部と、
【数２８】
0005918884.tif 000030
次式によりφ行φ列の逆行列A'-1を生成する逆行列生成部と、
【数２９】
0005918884.tif 000031
上記ベクトルb'と上記逆行列A'-1とを乗ずることで上記ベクトルaの要素ae0, …, aeφ-1を計算する平文計算部と、
を含む復号装置。
【請求項２】
請求項１に記載の復号装置であって、
φは2以上4以下の整数であり、
上記ベクトル変換部は、上記ベクトルb'を用いて、次式によりφ-1次のベクトルb"を生成するものであり、
【数３０】
0005918884.tif 000032
上記逆行列生成部は、次式によりφ-1行φ-1列の逆行列A"-1を生成するものであり、
【数３１】
0005918884.tif 000033
上記平文計算部は、上記ベクトルb"と上記逆行列A"-1とを乗ずることで上記ベクトルaの要素ae1, …, aeφ-1を計算し、次式により上記ベクトルaの要素ae0を計算するものである、
【数３２】
0005918884.tif 000034
復号装置。
【請求項３】
請求項２に記載の復号装置であって、
上記平文計算部は、φ-2i<3を満たすiについて、上記逆行列A"-1の左上部φ-2i次正方行列の後ろから2行と上記ベクトルb"の0番目からφ-2i-1番目までの要素とを並列に乗算することを繰り返して上記ベクトルaの要素ae2, …, aeφ-1を計算し、次式により上記ベクトルaの要素ae1を計算し、
【数３３】
0005918884.tif 000035
次式により上記ベクトルaの要素ae0を計算するものである、
【数３４】
0005918884.tif 000036
復号装置。
【請求項４】
請求項１から３のいずれかに記載の復号装置であって、
x=2であり、
上記ベクトル変換部、上記逆行列生成部、および上記平文計算部は、加算を排他的論理和演算とし、多項式乗算をビットシフト演算として計算するものである、
復号装置。
【請求項５】
xは拡大体GF(xq)を生成する既約多項式f[X]の元Xであり、n, kは2以上の整数であり、n≧2k-1であり、mは1以上の整数であり、m=n-kであり、aはa0, …, ak-1∈GF(xq)を要素とするk次ベクトルであり、Aは次式で定義されるn行k列の行列であり、
【数３５】
0005918884.tif 000037
bはb0, …, bn-1∈GF(xq)を要素とし上記ベクトルaと上記行列Aを乗じて得たn次ベクトルであり、φは1以上m以下の整数であり、d0, …, dk-φ-1は0以上k未満の相異なる整数であり、e0, …, eφ-1は0以上k未満かつd0, …, dk-φ-1と重複しない相異なる整数であり、p0, …, pφ-1はk以上n未満の相異なる整数であり、
ベクトル変換部が、上記ベクトルbのφ個の要素bp0, …, bpφ-1を用いて、次式によりφ次のベクトルb'を生成するベクトル変換ステップと、
【数３６】
0005918884.tif 000038
逆行列生成部が、次式によりφ行φ列の逆行列A'-1を生成する逆行列生成ステップと、
【数３７】
0005918884.tif 000039
平文計算部が、上記ベクトルb'と上記逆行列A'-1とを乗ずることで上記ベクトルaの要素ae0, …, aeφ-1を計算する平文計算ステップと、
を含む復号方法。
【請求項６】
請求項１から４のいずれかに記載の復号装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、符号化技術に関し、特に、復号処理を効率的に行う技術に関する。
【背景技術】
【０００２】
従来の誤り訂正符号技術にリード・ソロモン符号（Reed-Solomon Codes）がある。リード・ソロモン符号については、例えば非特許文献１に記載されている。
【０００３】
誤り訂正符号の符号化処理は、平文の入力ベクトル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以上の整数である。
【０００７】
【数１】
0005918884.tif 000002
【０００８】
出力ベクトルbは式（５）で表されるn次のベクトルとする。ただし、nは2以上の整数であり、n≧2k-1である。
【０００９】
【数２】
0005918884.tif 000003
【００１０】
行列Aは、式（６）で表されるk行k列の単位行列とm行k列のファンデルモンデ行列（Vandermonde matrix）を縦に連結した行列である。ただし、m=n-kである。ファンデルモンデ行列とは、行または列の行列要素に等比数列の各項が順番にならんでいる特別な構成の行列である。
【００１１】
【数３】
0005918884.tif 000004
【００１２】
つまり、行列Aは式（７）のようなn行k列の行列である。
【００１３】
【数４】
0005918884.tif 000005
【００１４】
行列Aは、k行目までは単位行列であるため、出力ベクトルbのk番目までの要素b0, …, bk-1は入力ベクトルaの要素a0, …, ak-1と一致する。出力ベクトルbにおいて入力ベクトルaの要素と一致する要素をデータシェアと呼び、それ以外の要素をパリティシェアと呼ぶ。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】バァナード・スカラー著、「ディジタル通信 基本と応用」、ピアソン・エデュケーション、2006年
【発明の概要】
【発明が解決しようとする課題】
【００１６】
従来の誤り訂正符号技術では処理量が大きいという課題がある。特に、復号処理において行われる体乗算の処理量が大きい。
【００１７】
この発明の目的は、このような点を鑑みて、符号化技術における体乗算の処理量を低減することができる復号技術を提供することである。
【課題を解決するための手段】
【００１８】
上記の課題を解決するために、この発明の復号装置は、xは拡大体GF(xq)を生成する既約多項式f[X]の元Xであり、n, kは2以上の整数であり、n≧2k-1であり、mは1以上の整数であり、m=n-kであり、aはa0, …, ak-1∈GF(xq)を要素とするk次ベクトルであり、Aは次式で定義されるn行k列の行列であり、
【００１９】
【数５】
0005918884.tif 000006
【００２０】
bはb0, …, bn-1∈GF(xq)を要素としベクトルaと行列Aを乗じて得たn次ベクトルであり、φは1以上m以下の整数であり、d0, …, dk-φ-1は0以上k未満の相異なる整数であり、e0, …, eφ-1は0以上k未満かつd0, …, dk-φ-1と重複しない相異なる整数であり、p0, …, pφ-1はk以上n未満の相異なる整数であり、ベクトルbのφ個の要素bp0, …, bpφ-1を用いて、次式によりφ次のベクトルb'を生成するベクトル変換部と、
【００２１】
【数６】
0005918884.tif 000007
【００２２】
次式によりφ行φ列の逆行列A'-1を生成する逆行列生成部と、
【００２３】
【数７】
0005918884.tif 000008
【００２４】
ベクトルb'と逆行列A'-1とを乗ずることでベクトルaの要素ae0, …, aeφ-1を計算する平文計算部と、を含む。
【発明の効果】
【００２５】
この発明によれば、符号化技術における体乗算の処理量を低減することができる。
【図面の簡単な説明】
【００２６】
【図１】図１は復号装置の機能構成を例示する図である。
【図２】図２は復号方法の処理フローを例示する図である。
【発明を実施するための形態】
【００２７】
実施形態の説明に先立ち、この発明の原理について説明する。
【００２８】
前提として、以下の説明では、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と表現できる。
【００３０】
a, b∈GF(264)の乗算は、2つの63次多項式a, b（式（８））を掛けてから64次多項式fで割る操作である（式（９））。このとき、λ次の項の係数は式（10）となる。
【００３１】
【数８】
0005918884.tif 000009
【００３２】
式（９）において、126次多項式をmod fして63次多項式にする処理をリダクションと呼ぶ。リダクションは、式（11）の同値関係を用いて処理する。
f=x64+x4+x3+x+1=0 mod f        …（11）
【００３３】
式（11）を変形すると、式（12）に示すように64次項を4次式に落とす関係となる。
x64=x4+x3+x+1 mod f        …（12）
【００３４】
式（13）に示すように、64次以上の項もすべて60次次数を下げられる。
x64+n=xn(x4+x3+x+1) mod f        …（13）
【００３５】
126次多項式を、63次多項式gと62次多項式hを用いて、式（14）のように表すことができる。
g+x64h=g+(x4+x3+x+1)h mod f        …（14）
【００３６】
ある任意の要素aとx+1との乗算(x+1)aは、式（15）で表すことができる。
【００３７】
【数９】
0005918884.tif 000010
【００３８】
また、xnaはaの各項がn次高い項となるので、整数表現における2n倍、もしくはnビット左シフトと等価である。したがって、式（16）のように表すことができる。
【００３９】
【数１０】
0005918884.tif 000011
【００４０】
hは62次多項式であるため、式（16）の
【００４１】
【数１１】
0005918884.tif 000012
【００４２】
は64次以上の多項式となり、再度次数を下げる必要がある。64次以上の部分は式（17）のようになる。
【００４３】
【数１２】
0005918884.tif 000013
【００４４】
64ビット整数内では64ビットを超えたビットは切り捨てられることを考慮すると、式（18）を計算すればよい。
【００４５】
【数１３】
0005918884.tif 000014
【００４６】
乗算の際、片方が61ビット以内のとき（より正確には両方のビット数を足して125以下のとき）、式（19）が成り立つため、リダクションを効率化できる。
【００４７】
【数１４】
0005918884.tif 000015
【００４８】
したがって、リダクションまで含めて考えると、61ビット数で1ビットだけが立っている数、つまり0≦i≦60の範囲での2iとの乗算は高速である。
【００４９】
上述のとおり、誤り訂正符号の復号処理では、復号に利用するベクトルbの要素を抜き出したベクトルb'と、符号化処理に用いた行列Aのうちベクトルb'の要素に対応する行を抜き出した行列A'の逆行列とを乗算することで平文のベクトルaを復号する。データシェアb0, …, bk-1がすべて利用可能な場合、データシェアは入力ベクトルの各要素そのものであるため、入力をそのまま出力すればよい。一方、利用不能なデータシェアが1つでもある場合、利用可能なデータシェアとパリティシェアとから平文を復元する必要がある。
【００５０】
平文の復元は以下のように行う。利用不能なデータシェアがφ個存在するとする。ただし、φ≦mである。概念的には、逆行列のうちφ行を抜き出して利用可能なシェアと掛ければよい。しかし、逆行列の要素は一般的に、xの60までのべきとはならないため、逆行列のうちφ行と掛けた場合の処理量は、式（20）で示す通りである。なお、MULはキャリー無し乗算の回数であり、REDはリダクションの回数である。キャリー無し乗算はIntel（登録商標）社Sandy-bridge以降、AMD（登録商標）社のBulldozer以降のCPUであればPCLMUL命令1回で処理できる。
φ(kMUL+RED)        …（20）
【００５１】
逆行列をそのまま掛けるかわりに、データシェアが1つの入力ベクトルの要素しか持たないことを利用して、最初にパリティシェアからデータシェアに対応する入力ベクトルの要素を除去する。例えば、式（21）のようにして、データシェアb0を用いて、パリティシェアbp（ただし、pはいずれかのパリティシェアに対応する番号）から0番目の平文の要素を除去することができる。
b0=(1 0 0 … 0)a,
bp=(1 xp-k x(p-k)2 … x(p-k)(k-1))a より、
bp-b0=(0 xp-k x(p-k)2 … x(p-k)(k-1))a        …（21）
【００５２】
このような変形を使うと、復元すべきベクトルaの要素ae0, …, aeφ-1をk次よりも低次のφ次平方行列を用いて表現することができる。
【００５３】
【数１５】
0005918884.tif 000016
【００５４】
ただし、d0, …, dk-φ-1は利用可能なデータシェアの番号、e0, …, eφ-1は利用不能なデータシェアの番号、p0, …, pφ-1は復元に用いるパリティシェアの番号である。すなわち、d0, …, dk-φ-1は0以上k未満の相異なる整数、e0, …, eφ-1は0以上k未満かつd0, …, dk-φ-1と重複しない相異なる整数、p0, …, pφ-1はk以上n未満の相異なる整数である。
【００５５】
式（22）の左辺をベクトルb'として、式（23）のように、φ次平方行列の逆行列を掛ければ平文が復元できる。
【００５６】
【数１６】
0005918884.tif 000017
【００５７】
ベクトルb'を生成するために必要な処理量は、式（24）となる。なお、BMULは一方が単項式である乗算の回数、BREDは最高次項の次数の合計が2q-d-1以下である乗算におけるリダクションの回数である。
(k-φ)φBMUL+φBRED        …（24）
【００５８】
ベクトルb'とφ次の逆行列との乗算に必要な処理量は、式（25）となる。
φ2MUL+φRED        …（25）
【００５９】
したがって、全体の処理量は、式（24）と式（25）を合計した式（26）となる。
φ((k-φ)BMUL+φMUL+BRED+RED)        …（26）
【００６０】
利用不能なデータシェアが1個の場合、すなわちφ=1の場合、式（23）は式（27）のようになる。したがって、xp0e0の逆元をあらかじめ計算しておき、b'0に掛ければよい。
【００６１】
【数１７】
0005918884.tif 000018
【００６２】
利用不能なデータシェアが2個以上4個以下の場合、すなわち2≦φ≦4の場合、さらに1つ次数を削減することができる。φ≧2のとき式（22）のφ次正方行列は要素がすべてxのべきであるため、p0 < p1< … <pφ-1と並べ替えておけば、式（28）のようにBMUL, BREDでもう1つ次数を下げることができる。
【００６３】
【数１８】
0005918884.tif 000019
【００６４】
残るae0は、式（28）で求めたae1, …, aeφ-1を用いて、式（29）により計算する。
【００６５】
【数１９】
0005918884.tif 000020
【００６６】
この場合の処理量は、式（30）となる。
(k-φ)φBMUL+φBRED+(φ-1)BMUL+(φ-1)BRED
+(φ-1)2MUL+(φ-1)RED+(φ-1)BMUL+BRED+MUL+RED
=φ((k-φ+2)BMUL+(φ-2)MUL+2BRED+RED)+2(-BMUL+MUL)        …（30）
【００６７】
式（30）で処理量が減少していることを説明する。まず、BMULとMULの合計数は式（20）（26）（30）ですべて等しくkφ回となっている。次に、MULの回数が減っていることを確かめる。式（20）ではkφ回、式（26）では2φ回、式（30）ではφ2-2φ+2であり、φ≧2のとき、式（30）<式（26）<式（20）である。REDの数は式（30）=式（26）<式（20）である。BREDの数は式（20）で0、式（26）でφ、式（30）で2φと増加しているが、φ≧2では増分はMULの減少分以下である。そのため、BRED+BMUL<MULが成り立つ場合、全体では処理量は低下している。なお、φ≧5では、各iでb'iとb'i-x(pi-p0)e0b'0の両方を保持することができずロード／ストアのオーバーヘッドとなるため、この次数削減は行わない。
【００６８】
利用不能なデータシェアが2個の場合、φ-1=1であるため、式（28）はφ=1の場合と同様、式（31）のように簡単な式となる。したがって、xp1e1-xp0e1+(p1-p0)e0の逆元をあらかじめ計算しておき、b'1に掛ければよい。あとは、式（29）を用いてae0を復元する。
【００６９】
【数２０】
0005918884.tif 000021
【００７０】
利用不能なデータシェアが3個以上の場合、逆行列を掛けたときの処理量は、式（32）となる。
φ2MUL+φRED        …（32）
【００７１】
ここで、ae0, …, aeφ-1のうち、1個（例えばae0）だけ復元してみる。すると必要な処理量は式（33）となる。
φMUL+RED        …（33）
【００７２】
するとデータシェア成分を除去したときと同じ方法により、式（34）の処理量で次数を1次削減できる。
(φ-1)(BMUL+BRED)        …（34）
【００７３】
この次数削減を繰り返した場合、処理量は式（35）となる。
φ(φ+1)/2MUL+φ(φ-1)/2BMUL+φRED+φ(φ-1)/2BRED        …（35）
【００７４】
式（26）と比較してMULとBMULの総数は等しく、MULの比率が約半分に軽減している。BREDだけが増加しているが、増分がMULの減少分と等しいため、BUL+BRED<MULならば全体として処理量は低下する。
【００７５】
絶対的な計算量は式（35）が最小となるが、1個ずつデータシェアを復元して、他のパリティシェアからその成分を除去することを繰り返す方法ではMULとREDの並列性が低下する問題がある。並列性の高い逆行列との乗算と比較して、順番にしか実行できない処理が増えてしまうため、CPUのMUL, REDの並列実行可能数によっては性能が低下してしまう。そのため、最終的に、CPUのMUL, REDの並列実行可能数分ずつ逆行列によって復元し、パリティシェアからその復元した成分を除去することを繰り返す方法が最速となる。なお、MULの並列実行可能数は、Intel社のIvy-Bridgeでは1、Haswellでは2であり、REDの並列実行可能数は、Ivy-Bridge, Haswellとも2である。
【００７６】
上述した誤り訂正符号の復号処理を実装したアルゴリズムの例を次表に示す。
【００７７】
【表１】
0005918884.tif 000022
【００７８】
補助入力である係数行列Ciおよび係数c0, c1はφの値に応じて以下のように設定される。
【００７９】
φ=1の場合、係数は次式のc0のみである。c0はxのべきの逆元であるためテーブル参照のみで計算できる。
【００８０】
【数２１】
0005918884.tif 000023
【００８１】
φ=2の場合、上記のc0に加えて、次式のc1である。
【００８２】
【数２２】
0005918884.tif 000024
【００８３】
φ=3の場合、上記のc0, c1に加えて、式（28）左辺のφ-1次正方行列の逆行列である。
【００８４】
φ=4の場合、上記のc0, c1と、式（28）左辺のφ-1次正方行列の逆行列のうち1行目（番号は0スタート）と2行目である。逆行列の1つの行は1つの平文シェアを復元するための係数列に等しい。上述したCPUのMUL, REDの並列実行可能数を考慮して、平文シェアを後方から2つずつ復元すると効率がよいため、後ろから2行だけが必要になる。
【００８５】
φ=5の場合、φ=4の場合と同様に、後方から2つずつ復元していくため、φ次正方行列の逆行列の後ろから2行がまず必要になる。次に、残りのφ-2次正方行列の逆行列の後ろから2行が必要になる。このように、φ次正方行列のうち、φ-2i<3を満たす各iに対して左上部φ-2i次正方行列の逆行列の後ろから2行ずつが必要となる。逆行列をφ/2回求める必要はなく、一度の三角化でよい。三角化、後退代入とも、左上部分はより右下の部分に影響されないため、右2列下2行を除いた行列の三角行列は全体の三角行列から右2列下2行を除いたものと同じだからである。
【００８６】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００８７】
実施形態の復号装置１は、図１に例示するように、ベクトル入力部１０、ベクトル変換部１１、逆行列生成部１２、平文計算部１３、およびベクトル出力部１４を含む。この復号装置１が、図２に例示する各ステップの処理を行うことにより実施形態の復号方法が実現される。
【００８８】
復号装置１は、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。復号装置１は、例えば、中央演算処理装置の制御のもとで各処理を実行する。復号装置１に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。復号装置１の各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
【００８９】
図２を参照して、実施形態の復号方法の処理手続きを説明する。
【００９０】
ステップＳ１０において、ベクトル入力部１０へ、n次ベクトルbが入力される。n次ベクトルbのパリティシェアのうち利用可能なφ個の要素bp0, …, bpφ-1∈GF(xq)はベクトル変換部１１へ送られる。また、ベクトルbのデータシェアのうち利用可能なk-φ個の要素bd0, …, bdk-φ-1はベクトル出力部１４へ送られる。ベクトルbは、式（36）で定義されるk次ベクトルaと、式（37）で定義されるn行k列の行列Aとを乗じて得たn次ベクトルである。
【００９１】
【数２３】
0005918884.tif 000025
【００９２】
ステップＳ１１において、ベクトル変換部１１は、bp0, …, bpφ-1を用いて、式（38）によりφ次のベクトルb'を生成する。ベクトルb'は平文計算部１３へ送られる。
【００９３】
【数２４】
0005918884.tif 000026
【００９４】
ステップＳ１２において、逆行列生成部１２は、式（39）によりφ行φ列の逆行列A'-1を生成する。逆行列A'-1は平文計算部１３へ送られる。逆行列A'-1はk個のパリティシェアのうちどのφ個を用いて復元するかが定まれば生成可能であるため、すべてのφ個の組み合わせについてあらかじめ逆行列A'-1を計算しておいてもよい。その場合、逆行列生成部１２は、あらかじめ生成した逆行列から適切なものを選択するだけでよい。
【００９５】
【数２５】
0005918884.tif 000027
【００９６】
ステップＳ１３において、平文計算部１３は、式（40）に示すように、ベクトルb'と逆行列A'-1とを乗ずることでベクトルaの要素ae0, …, aeφ-1を計算する。要素ae0, …, aeφ-1はベクトル出力部１４へ送られる。
【００９７】
【数２６】
0005918884.tif 000028
【００９８】
ステップＳ１４において、ベクトル出力部１４は、ベクトル入力部１０から受け取ったk-φ個の要素bd0, …, bdk-φ-1と、平文計算部１３により計算されたφ個の要素ae0, …, aeφ-1とを要素としてk次ベクトルaを復元し、そのベクトルaを出力する。
【００９９】
上記のように構成することにより、実施形態の復号装置によれば、k次正方行列である行列A'をφ次正方行列に次数削減してから逆行列A'-1を作用させて復号を行う。これにより、φk個の多項式乗算のうち、φ(k-φ)個分が項の移動のみで済む軽量な多項式乗算となるため、効率的である。一般の多項式乗算は拡大次数qに対してq2の計算量となる。これに対して、項の移動による計算量は、実際に移動した場合はqの計算量、移動量のフラグを持つだけとした場合は計算量が1となる。
【０１００】
この発明の復号技術は、計算量的秘密分散に適用することが可能である。計算量型秘密分散は、計算量的安全性に基づき一定個数未満の分散値からは元のデータを一切復元できなくする秘密分散方式である。計算量型秘密分散は、例えば、下記参考文献１に記載されたものがある。
〔参考文献１〕H.Krawczyk, “Secret sharing made short.”, CRYPTO 1993, pp. 136-146, 1993.
【０１０１】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１０２】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１０３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１０４】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM、USBメモリ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１０５】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１０６】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１０７】
１  復号装置
１０  ベクトル入力部
１１  ベクトル変換部
１２  逆行列生成部
１３  平文計算部
１４  ベクトル出力部
【要約】
【課題】体乗算の処理量を低減する。
【解決手段】aはa0, …, ak-1∈GF(xq)を要素とするk次ベクトルである。Aは単位行列とファンデルモンデ行列を縦に連結したn行k列の行列である。bはb0, …, bn-1∈GF(xq)を要素としベクトルaと行列Aを乗じて得たn次ベクトルである。ベクトル変換部１１は、ベクトルbのφ個の要素bp0, …, bpφ-1を用いてφ次のベクトルb'を生成する。逆行列生成部１２は、φ行φ列の逆行列A'-1を生成する。平文計算部１３は、ベクトルb'と逆行列A'-1とを乗ずることでベクトルaの要素ae0, …, aeφ-1を計算する。
【選択図】図２【図１】
0005918884.tif 000040
【図２】
0005918884.tif 000041