Decoding apparatus, decoding method and program

Abstract

To reduce the processing amount of a field multiplication. a denotes a k-th order vector whose elements are a.sub.0, . . . , a.sub.k1 (a.sub.0, . . . , a.sub.k1GF(x.sup.q)). A denotes an n-by-k matrix formed by vertically connecting a identity matrix and a Vandermonde matrix. b denotes an n-th order vector obtained by multiplying the vector a and the matrix A whose elements are b.sub.0, . . . , b.sub.n1 (b.sub.0, . . . , b.sub.n1GF(x.sup.q)). A vector conversion part 11 generates a -th order vector b using elements b.sub.p0, . . . , b.sub.p1 of the vector b. An inverse matrix generation part 12 generates a -by- inverse matrix A.sup.1. A plaintext computation part 13 computes elements a.sub.e0, . . . , a.sub.e1 of the vector a by multiplying the vector b and the inverse matrix A.sup.1.

Claims

1. A decoding apparatus, wherein x is an element of an irreducible polynomial f[X] that generates an extension field GF(x.sup.q), n and k are integers equal to or greater than 2, n2k1, m denotes an integer equal to or greater than 1, m=nk, vector a denotes a k-th order vector having elements a.sub.0, . . . , a.sub.k1 (a.sub.0, . . . , a.sub.k1GF(x.sup.q)), A denotes a n-by-k matrix defined by the following formula: $A_{\mathrm{ij}}=\{\begin{array}{cc}1& \mathrm{if}i=j\\ 0& \mathrm{if}ij\mathrm{and}i<k\\ x^{\left(i-k\right)j}& \mathrm{if}ik\end{array}\mathrm{where}i\left\{0,\mathrm{.Math.},n-1\right\},j\left\{0,\mathrm{.Math.},k-1\right\},$ vector b denotes an n-th order vector having elements b.sub.0, . . . , b.sub.n1 (b.sub.0, . . . , b.sub.n1GF(x.sup.q)) obtained by multiplying the vector a by the matrix A, denotes an integer equal to or greater than 1 and equal to or smaller than m, d.sub.0, . . . , d.sub.k--1 denote different integers equal to or greater than 0 and smaller than k, e.sub.0, . . . , e.sub.1 denote different integers equal to or greater than 0 and smaller than k that are different from d.sub.0, . . . , d.sub.k--1, p.sub.0, . . . , p.sub.1 denote different integers equal to or greater than k and smaller than n, and the decoding apparatus comprises: circuitry configured to: receive the vector b as an input from an encoding apparatus over a communications channel; generate a -th order vector b using elements b.sub.p0, . . . , b.sub.p1 of the vector b, for n=p.sub. according to the following formula: $b^{}=\left(\begin{array}{c}{b}_0^{}\\ b_1^{}\\ \mathrm{.Math.}\\ b_{-1}^{}\end{array}\right)=\left(\begin{array}{c}{b}_{p_0}-\underset{i<k-}{.Math.}{x}^{p_0{d}_i}{b}_{d_i}\\ b_{p_1}-\underset{i<k-}{.Math.}{x}^{p_1{d}_i}{b}_{d_i}\\ \mathrm{.Math.}\\ b_{p_{-1}}-\underset{i<k-}{.Math.}{x}^{p_{-1}{d}_i}{b}_{d_i}\end{array}\right)$ generate a -by- inverse matrix A.sup.1 according to the following formula: $A^{-1}={\left(\begin{array}{cccc}{x}^{p_0{e}_0}& x^{p_0{e}_1}& \mathrm{.Math.}& x^{p_0{e}_{-1}}\\ x^{p_1{e}_0}& x^{p_1{e}_1}& \mathrm{.Math.}& x^{p_1{e}_{-1}}\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ x^{p_{-1}{e}_0}& x^{p_{-1}{e}_1}& \mathrm{.Math.}& x^{p_{-1}{e}_{-1}}\end{array}\right)}^{-1};$ and compute the elements a.sub.e0, . . . , a.sub.e1 of the vector a, as an output, by multiplying the vector b and the inverse matrix A.sup.1, the vector a corresponding to a plaintext input to the encoding apparatus.

2. The decoding apparatus according to claim 1, wherein denotes an integer within a range equal to or greater than 2 and equal to or smaller than 4, the circuitry configured to generate a -1-th order vector b using the vector baccording to the following formula: $b^{}=\left(\begin{array}{c}{b}_0^{}\\ b_1^{}\\ \mathrm{.Math.}\\ b_{-2}^{}\end{array}\right)=\left(\begin{array}{c}{b}_1^{}-x^{\left(p_1-p_0\right)e_0}{b}_0^{}\\ b_2^{}-x^{\left(p_2-p_0\right)e_0}{b}_0^{}\\ \mathrm{.Math.}\\ b_{{}_{-1}}^{}-x^{\left(p_{-1}-p_0\right)e_0}{b}_0^{}\end{array}\right),$ generate a -1-by--1 inverse matrix A.sup.1 according to the following formula: $A^{-1}={\left(\begin{array}{ccc}{x}^{p_1{e}_1}-x^{p_0{e}_1+\left(p_1-p_0\right)e_0}& \mathrm{.Math.}& x^{p_1{e}_{-1}}-x^{\left(p_1-p_0\right)e_0}\\ x^{p_2{e}_1}-x^{p_0{e}_1+\left(p_2-p_0\right)e_0}& \mathrm{.Math.}& x^{p_2{e}_{-1}}-x^{\left(p_2-p_0\right)e_0}\\ \mathrm{.Math.}& & \mathrm{.Math.}\\ x^{p_{-1}{e}_1}-x^{p_0{e}_1+\left(p_{-1}-p_0\right)e_0}& \mathrm{.Math.}& x^{p_{-1}{e}_{-1}}-x^{\left(p_{-1}-p_0\right)e_0}\end{array}\right)}^{-1},$ and compute the elements a.sub.e1, . . . , a.sub.e1 of the vector a by multiplying the vector b and the inverse matrix A.sup.1 and computes the element a.sub.e0 of the vector a according to the following formula: $a_{e_0}=x^{-p_0{e}_0}\left(b_0^{}-\underset{ii<}{.Math.}{x}^{p_0{e}_i}{a}_{e_i}\right).$

3. The decoding apparatus according to claim 2, wherein the circuitry is configured to compute the elements a.sub.e2, . . . , a.sub.e1 of the vector a by repeating parallel multiplications of the last two rows of a -2i-th order square matrix in an upper left part of the inverse matrix A.sup.1 by the 0-th to -2i1-th elements of the vector b for i that satisfies a relation 2i<3, compute the element a.sub.e1 of the vector a according to the following formula:
a.sub.e1=c.sub.1b.sub.1
where
c.sub.1=(x.sup.p.sup.1.sup.e.sup.1x.sup.p.sup.0.sup.e.sup.1.sup.+(p.sup.1.sup.p.sup.0.sup.)e.sup.0).sup.1, and compute the element a.sub.e0 of the vector a according to the following formula:
a.sub.e.sub.0=c.sub.0b.sub.0;
where
b.sub.0=x.sup.p.sup.0.sup.e.sup.1a.sub.e.sub.1,c.sub.0=(x.sup.p.sup.0.sup.e.sup.0).sup.1.

4. The decoding apparatus according to claim 1, wherein x=2, and the circuitry is configured to perform an exclusive-OR operation as an addition and perform a bit shift operation as a polynomial multiplication.

5. A decoding method, wherein x is an element of an irreducible polynomial f[X] that generates an extension field GF(x.sup.q), n and k are integers equal to or greater than 2, n2k1, m denotes an integer equal to or greater than 1, m=nk, vector a denotes a k-th order vector having elements a.sub.0, . . . , a.sub.k1 (a.sub.0, . . . , a.sub.k1GF(x.sup.q)), A denotes a n-by-k matrix defined by the following formula: $A_{\mathrm{ij}}=\{\begin{array}{cc}1& \mathrm{if}i=j\\ 0& \mathrm{if}ij\mathrm{and}i<k\\ x^{\left(i-k\right)j}& \mathrm{if}ik\end{array}\mathrm{where}i\left\{0,\mathrm{.Math.},n-1\right\},j\left\{0,\mathrm{.Math.},k-1\right\},$ vector b denotes an n-th order vector having elements b.sub.0, . . . , b.sub.n1 (b.sub.0, . . . , b.sub.n1GF(x.sup.q)) obtained by multiplying the vector a by the matrix A, denotes an integer equal to or greater than 1 and equal to or smaller than m, d.sub.0, . . . , d.sub.k--1 denote different integers equal to or greater than 0 and smaller than k, e.sub.0, . . . , e.sub.1 denote different integers equal to or greater than 0 and smaller than k that are different from d.sub.0, . . . , d.sub.k--1, p.sub.0, . . . , p.sub.1 denote different integers equal to or greater than k and smaller than n, and the decoding method, which is implemented by a decoding apparatus, comprises: receiving the vector b as an input from an encoding apparatus over a communications channel; generating, by circuitry of a decoding apparatus, a -th order vector b using elements b.sub.p0, . . . , b.sub.p1 of the vector b, for n=p.sub., according to the following formula: $b^{}=\left(\begin{array}{c}{b}_0^{}\\ b_1^{}\\ \mathrm{.Math.}\\ b_{-1}^{}\end{array}\right)=\left(\begin{array}{c}{b}_{p_0}-\underset{i<k-}{.Math.}{x}^{p_0{d}_i}{b}_{d_i}\\ b_{p_1}-\underset{i<k-}{.Math.}{x}^{p_1{d}_i}{b}_{d_i}\\ \mathrm{.Math.}\\ b_{p_{-1}}-\underset{i<k-}{.Math.}{x}^{p_{-1}{d}_i}{b}_{d_i}\end{array}\right)$ generating, by circuitry of the decoding apparatus, a -by- inverse matrix A.sup.1 according to the following formula: $A^{-1}={\left(\begin{array}{cccc}{x}^{p_0{e}_0}& x^{p_0{e}_1}& \mathrm{.Math.}& x^{p_0{e}_{-1}}\\ x^{p_1{e}_0}& x^{p_1{e}_1}& \mathrm{.Math.}& x^{p_1{e}_{-1}}\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ x^{p_{-1}{e}_0}& x^{p_{-1}{e}_1}& \mathrm{.Math.}& x^{p_{-1}{e}_{-1}}\end{array}\right)}^{-1};$ and computing, by circuitry of the decoding apparatus, the elements a.sub.c0, . . . , a.sub.c-1 of the vector a, as an output, by multiplying the vector b and the inverse matrix A.sup.1, the vector a corresponding to a plaintext input to the encoding apparatus.

6. A non-transitory computer readable medium including computer executable instructions that make a decoding apparatus, wherein x is an element of an irreducible polynomial f[X] that generates an extension field GF(x.sup.q), n and k are integers equal to or greater than 2, n2k1, m denotes an integer equal to or greater than 1, m=nk, vector a denotes a k-th order vector having elements a.sub.0, . . . , a.sub.k1 (a.sub.0, . . . , a.sub.k1GF(x.sup.q)), A denotes a n-by-k matrix defined by the following formula: $A_{\mathrm{ij}}=\{\begin{array}{cc}1& \mathrm{if}i=j\\ 0& \mathrm{if}ij\mathrm{and}i<k\\ x^{\left(i-k\right)j}& \mathrm{if}ik\end{array}\mathrm{where}i\left\{0,\mathrm{.Math.},n-1\right\},j\left\{0,\mathrm{.Math.},k-1\right\},$ vector b denotes an n-th order vector having elements b.sub.0, . . . , b.sub.n1 (b.sub.0, . . . , b.sub.n1GF(x.sup.q)) obtained by multiplying the vector a by the matrix A, denotes an integer equal to or greater than 1 and equal to or smaller than m, d.sub.0, . . . , d.sub.k--1 denote different integers equal to or greater than 0 and smaller than k, e.sub.0, . . . , e.sub.1 denote different integers equal to or greater than 0 and smaller than k that are different from d.sub.0, . . . , d.sub.k--1, p.sub.0, . . . , p.sub.1 denote different integers equal to or greater than k and smaller than n, perform a method comprising: receiving the vector b as an input from an encoding anDaratus over a communications channel; generating a -th order vector b using elements b.sub.p0, . . . , b.sub.p1 of the vector b, for n=p.sub. according to the following formula: $b^{}=\left(\begin{array}{c}{b}_0^{}\\ b_1^{}\\ \mathrm{.Math.}\\ b_{-1}^{}\end{array}\right)=\left(\begin{array}{c}{b}_{p_0}-\underset{i<k-}{.Math.}{x}^{p_0{d}_i}{b}_{d_i}\\ b_{p_1}-\underset{i<k-}{.Math.}{x}^{p_1{d}_i}{b}_{d_i}\\ \mathrm{.Math.}\\ b_{p_{-1}}-\underset{i<k-}{.Math.}{x}^{p_{-1}{d}_i}{b}_{d_i}\end{array}\right)$ generating a -by-inverse matrix A.sup.1 according to the following formula: and $A^{-1}={\left(\begin{array}{cccc}{x}^{p_0{e}_0}& x^{p_0{e}_1}& \mathrm{.Math.}& x^{p_0{e}_{-1}}\\ x^{p_1{e}_0}& x^{p_1{e}_1}& \mathrm{.Math.}& x^{p_1{e}_{-1}}\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ x^{p_{-1}{e}_0}& x^{p_{-1}{e}_1}& \mathrm{.Math.}& x^{p_{-1}{e}_{-1}}\end{array}\right)}^{-1};$ computing the elements a.sub.e0, . . . , a.sub.e1 of the vector a, as an output, by multiplying the vector b and the inverse matrix A.sup.1, the vector a corresponding to a plaintext input to the encoding apparatus.

7. The decoding apparatus according to claim 2, wherein x=2, and the circuitry is configured to perform an exclusive-OR operation as an addition and perform a bit shift operation as a polynomial multiplication.

8. The decoding apparatus according to claim 3, wherein x=2, and the circuitry is configured to perform an exclusive-OR operation as an addition and perform a bit shift operation as a polynomial multiplication.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a diagram illustrating a functional configuration of a decoding apparatus;

(2) FIG. 2 is a diagram illustrating a process flow of a decoding method.

DETAILED DESCRIPTION OF THE EMBODIMENTS

(3) Before describing an embodiment, a principle of the present invention will be described.

(4) The following description will be made on the assumption that x represents an element X of an extension field GF(2.sup.64) expressed by an irreducible polynomial f[X]=X.sup.64+X.sup.4+X.sup.3+X.sup.2+X+1. x is 2 in an integer expression.

(5) GF(2.sup.64) is a set of remainders of a division of a polynomial by a 64-th order polynomial f[X] whose coefficients are integers modulo 2 (division as polynomials). GF(2.sup.64) is a field on which the four arithmetic operations are possible. GF(2.sup.64) may also be regarded as a 64-th order vector of bits with a special arithmetic. GF(2.sup.64) can be expressed by a 64-bit integer, a term x.sup.i of which is expressed as 2.sup.i. For example, 1+x+x.sup.3 is expressed as 2.sup.0+2.sup.1+2.sup.3=11.

(6) Multiplication of a and b (a, bGF(2.sup.64)) is an operation of multiplying two 63-th order polynomials a and b (see the formula (8)) by each other and then dividing the product by the 64-th order polynomial f (see the formula (9)). A coefficient of a -th order term is expressed by the formula (10).

(7) $\begin{array}{cc}a=\underset{1<64}{.Math.}{a}_i{x}^i,b=\underset{1<64}{.Math.}{b}_i{x}^i& \left(8\right)\\ \underset{i<64}{.Math.}\underset{j<64}{.Math.}{a}_i{b}_j{x}^{i+j}\mathrm{mod}f& \left(9\right)\\ {}_{i+j=}{a}_i{b}_j& \left(10\right)\end{array}$

(8) In the formula (9), a process of taking a modulus f of the 126-th order polynomial to provide a 63-th order polynomial is referred to as reduction. The reduction is achieved by using the equivalence relation expressed by the formula (11).
F=x.sup.64+X.sup.4+x.sup.3+x+1=0 mod f(11)

(9) The formula (11) can be transformed into the formula (12), which represents a relation that reduces the 64-th order term to a fourth-order formula.
x.sup.64=x.sup.4+x.sup.3+x+1 mod f(12)

(10) As shown by the formula (13), the order of any 64-th or higher order term can be reduced by 60.
x.sup.64+n=x.sup.n(x.sup.4+x.sup.3+x+1)mod f(13)

(11) The 126-th order polynomial can be expressed by a 63-th order polynomial g and a 62-th order polynomial h according to the formula (14).
g+x.sup.64h=g+(x.sup.4+x.sup.3+x+1)h mod f(14)

(12) A multiplication (x+1)a of an arbitrary element a and x+1 can be expressed by the formula (15).
xa+a=xaa(15)

(13) In addition, since the order of each term of x.sup.na is n higher than the order of the corresponding term of a, each term of x.sup.na is equivalent to 2.sup.n times the term in the integer expression or the term left-shifted by n bits. Thus, x.sup.na can be expressed by the formula (16).
(x.sup.4+x.sup.3+x+1)h=(h<<4)(h<<3)(h<<1)h(16)

(14) Since h is a 62-th order polynomial, the term
(h<<4)(h<<3)

(15) in the formula (16) is a 64-th or higher order polynomial, and the order needs to be further reduced. The part of 64-th or higher order is expressed by the formula (17).
x.sup.4(h.sub.62x.sup.62+h.sub.61x.sup.61+h.sub.60x.sup.60)+x.sup.3(h.sub.62x.sup.62+h.sub.61x.sup.61)=x.sup.64((h>>60)(h>>61))(17)

(16) Considering that in the case of the 64-bit integer, any number is truncated to 64 bits, computation can be performed according to the formula (18).

(17) $\begin{array}{cc}{X}^{64}\left(h\left(h>>60\right)\left(h>>61\right)\right)=\left(x^4+x^3+x+1\right)\left(h\left(h>>60\right)\left(h>>61\right)\right)=\left(x^3+1\right)\left(x+1\right)\left(h\left(h>>60\right)\left(h>>61\right)\right)& \left(18\right)\end{array}$

(18) In multiplication, if one of the multiplier is a number with 61 bits or a smaller number of bits (more strictly, if the total number of bits of the multipliers is equal to or less than 125), the formula (19) holds, so that the reduction can be made more efficient.
(h>>60)(h>>61)=0(19)

(19) Thus, considering the processing amount including the reduction, the multiplication by a 61-bit number with only one bit being 1 (in other words, 2.sup.i where 0i60) is quick.

(20) As described above, in the decoding process for an error correcting code, the vector a in the form of a plaintext is decoded by multiplying the vector b formed by extracting elements of the vector b used for decoding by the inverse matrix of the matrix A formed by extracting rows corresponding to the elements of the vector b of the matrix A used for encoding. If all the data shares b.sub.0, . . . , b.sub.k1 are available, the data shares are the elements of the input vector themselves, so that the input can be used as it is. On the other hand, if any data share is unavailable, the plaintext needs to be reconstructed from the available data shares and a parity share.

(21) Reconstruction of the plaintext is performed as described below. It is assumed that there is unavailable data shares, where m. Conceptually, it is enough to extract rows of the inverse matrix and multiply the available data shares by extracted rows. In general, however, the elements of the inverse matrix are not x to the power of up to 60, so that the processing amount in the case of the multiplication by rows is expressed by the formula (20). In the formula, MUL represents the processing amount of one carry-less multiplication, and RED represents the processing amount of one reduction. The carry-less multiplication can be achieved by one PCLMUL instruction with a Sandy-bridge or later CPU available from Intel Corporation or a Bulldozer or later CPU available from AMD Inc.
(kMUL+RED)(20)

(22) Instead of multiplication by the inverse matrix itself, taking advantage of the fact that the data share has only one element of the input vector, elements of the input vector that correspond to the data shares are first removed from the parity shares. For example, as shown by the formula (21), the 0-th element of the plaintext can be removed from the parity share b.sub.p (where p denotes an identification number of any parity share) by using the data share b.sub.0.

(23) Since b.sub.0=(1 0 0 . . . 0)a, and
b.sub.p=(1x.sup.pk x.sup.(pk)2 . . . x.sup.(pk)(k1))a,
b.sub.pb.sub.0=(0x.sup.pkx.sup.(pk)2 . . . x.sup.(pk)(k1))a(21)

(24) By using such a transformation, elements a.sub.e0, . . . , a.sub.e1 of the vector a to be reconstructed can be expressed by a -th order square matrix whose order is lower than k.

(25) 0$\begin{array}{cc}\left(\begin{array}{c}{b}_{p_0}-\underset{i<k-}{.Math.}{x}^{p_0{d}_i}{b}_{d_i}\\ b_{p_1}-\underset{i<k-}{.Math.}{x}^{p_1{d}_i}{b}_{d_i}\\ \mathrm{.Math.}\\ b_{p_{-1}}-\underset{i<k-}{.Math.}{x}^{p_{-1}{d}_i}{b}_{d_i}\end{array}\right)=\underset{\underset{\mathrm{columns}}{}}{\left(\begin{array}{cccc}{x}^{p_0{e}_0}& x^{p_0{e}_1}& \mathrm{.Math.}& x^{p_0{e}_{-1}}\\ x^{p_1{e}_0}& x^{p_1{e}_1}& \mathrm{.Math.}& x^{p_1{e}_{-1}}\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ x^{p_{-1}{e}_0}& x^{p_{-1}{e}_1}& \mathrm{.Math.}& x^{p_{-1}{e}_{-1}}\end{array}\right)}\left(\begin{array}{c}{a}_{e_0}\\ a_{e_1}\\ \mathrm{.Math.}\\ a_{e_{-1}}\end{array}\right)\}\mathrm{rows}& \left(22\right)\end{array}$

(26) In the formula, d.sub.0, . . . , d.sub.k1 are identification numbers of the available data shares, e.sub.0, . . . , e.sub.1 are identification numbers of the unavailable data shares, and p.sub.0, . . . , p.sub.1 are identification numbers of the parity shares used for the reconstruction. That is, d.sub.0, . . . , d.sub.k1 denote different integers equal to or greater than 0 and smaller than k, e.sub.0, . . . , e.sub.1 denote different integers equal to or greater than 0 and smaller than k that are different from d.sub.0, . . . , d.sub.k1, and p.sub.0, . . . , p.sub.1 denote different integers equal to or greater than k and smaller than n.

(27) The left-hand side of the formula (22) is designated as the vector b, and the plaintext can be reconstructed by multiplying the vector b by an inverse matrix of the -th order square matrix.

(28) $\begin{array}{cc}{\left(\begin{array}{cccc}{x}^{p_0{e}_0}& x^{p_0{e}_1}& \mathrm{.Math.}& x^{p_0{e}_{-1}}\\ x^{p_1{e}_0}& x^{p_1{e}_1}& \mathrm{.Math.}& x^{p_1{e}_{-1}}\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ x^{p_{-1}{e}_0}& x^{p_{-1}{e}_1}& \mathrm{.Math.}& x^{p_{-1}{e}_{-1}}\end{array}\right)}^{-1}\left(\begin{array}{c}{b}_0^{}\\ b_1^{}\\ \mathrm{.Math.}\\ b_{-1}^{}\end{array}\right)=\left(\begin{array}{c}{a}_{e_0}\\ a_{e_1}\\ \mathrm{.Math.}\\ a_{e_{-1}}\end{array}\right)\mathrm{where}{b}^{}=\left(\begin{array}{c}{b}_0^{}\\ b_1^{}\\ \mathrm{.Math.}\\ b_{-1}^{}\end{array}\right)=\left(\begin{array}{c}{b}_{p_0}-\underset{i<k-}{.Math.}{x}^{p_0{d}_i}{b}_{d_i}\\ b_{p_1}-\underset{i<k-}{.Math.}{x}^{p_1{d}_i}{b}_{d_i}\\ \mathrm{.Math.}\\ b_{p_{-1}}-\underset{i<k-}{.Math.}{x}^{p_{-1}{d}_i}{b}_{d_i}\end{array}\right)& \left(23\right)\end{array}$

(29) The processing amount required to generate the vector b is expressed by the formula (24). In the formula, BMUL represents the processing amount of one multiplication one of whose multiplier is a monomial, and BRED represents the processing amount of one reduction involved in a multiplication the total of the orders of the highest-order terms of whose multipliers is equal to or smaller than 2qd1.
(k)BMUL+BRED(24)

(30) The processing amount required for the multiplication of the vector b by the -th order inverse matrix is expressed by the formula (25).
.sup.2MUL+RED(25)

(31) Thus, the total processing amount is expressed by the formula (26), which is the sum of the formulas (24) and (25).
((k)BMUL+MUL+BRED+RED)(26)

(32) If there is one unavailable data share, that is, if =1, the formula (23) can be rewritten as the formula (27). Thus, an inverse element of x.sup.p0e0 can be calculated in advance, and b.sub.0 can be multiplied by the inverse element.
(x.sup.p.sup.0.sup.e.sup.0).sup.1(b.sub.0)=(a.sub.e.sub.0)(27)

(33) If there are two to four unavailable data shares, that is, if 24, the order can be further reduced by one. If 2, all the elements of the -th order square matrix expressed by the formula (22) are powers of x. Thus, if the parity shares are arranged according to p.sub.0<p.sub.1< . . . <p.sub.1, the order can be further reduced by one in BMUL and BRED as shown by the formula (28).

(34) $\begin{array}{cc}\underset{\underset{-1\mathrm{rows}-1\mathrm{columns}}{}}{{\left(\begin{array}{ccc}{x}^{p_1{e}_1}-x^{p_0{e}_1+\left(p_1-p_0\right)e_0}& \mathrm{.Math.}& x^{p_1{e}_{-1}}-x^{\left(p_1-p_0\right)e_0}\\ x^{p_2{e}_1}-x^{p_0{e}_1+\left(p_2-p_0\right)e_0}& \mathrm{.Math.}& x^{p_2{e}_{-1}}-x^{\left(p_2-p_0\right)e_0}\\ \mathrm{.Math.}& & \mathrm{.Math.}\\ x^{p_{-1}{e}_1}-x^{p_0{e}_1+\left(p_{-1}-p_0\right)e_0}& \mathrm{.Math.}& x^{p_{-1}{e}_{-1}}-x^{\left(p_{-1}-p_0\right)e_0}\end{array}\right)}^{-1}}\left(\begin{array}{c}{b}_1^{}-x^{\left(p_1-p_0\right)e_0}{b}_0^{}\\ b_2^{}-x^{\left(p_2-p_0\right)e_0}{b}_0^{}\\ \mathrm{.Math.}\\ b_{-1}^{}-x^{\left(p_{-1}-p_0\right)e_0}{b}_0^{}\end{array}\right)=\left(\begin{array}{c}{a}_{e_1}\\ a_{e_2}\\ \mathrm{.Math.}\\ a_{e_{-1}}\end{array}\right)& \left(28\right)\end{array}$

(35) The remaining a.sub.e0 is calculated using a.sub.e1, . . . , a.sub.e1 determined from the formula (28) according to the formula (29).

(36) $\begin{array}{cc}{a}_{e_0}=x^{-p_0{e}_0}\left(b_0^{}-\underset{1i<}{.Math.}{x}^{p_0{e}_i}{a}_{e_i}\right)& \left(29\right)\end{array}$

(37) In this case, the processing amount is expressed by the formula (30).
(k)BMUL+BRED+(1)BMUL+(1)BRED+(1).sup.2MUL+(1)RED+(1)BMUL+BRED+MUL+RED=((k+2)BMUL+(2)MUL+2BRED+RED)+2(BMUL+MUL)(30)

(38) It will be now described that the formula (30) shows a reduced processing amount. First, the total of BMUL and MUL is k) in all of the formulas (20), (26) and (30). Next, it will be confirmed that MUL has been reduced. MUL is k in the formula (20), 2 in the formula (26) and .sup.22+2 in the formula (30). If 2, a relation holds: formula (30)<formula (26)<formula (20). In terms of RED, a relation holds: formula (30)=formula (26)<formula (20). BRED increases with formula: BRED is 0 in the formula (20), in the formula (26) and 2 in the formula (30). However, if 2, the increment is equal to or smaller than the reduction in MUL. Thus, if a relation BRED+BMUL<MUL holds, the total processing amount is reduced. If 5, both of b.sub.i and b.sub.ix.sup.(pip0)e0b.sub.0 cannot be held for each i, and an overhead of loading/storing occurs, so that this order reduction is not performed.

(39) If there are two unavailable data shares, 1=1. Thus, as in the case where =1, the formula (28) can be rewritten as the formula (31). Thus, an inverse element of x.sup.p1e1x.sup.p0e1+(p1p0)e0 can be calculated in advance, and b.sub.1 can be multiplied by the inverse element. Then, a.sub.e0 is reconstructed according to the formula (29).
(x.sup.p.sup.1.sup.e.sup.1x.sup.p.sup.0.sup.e.sup.1.sup.+(p.sup.1.sup.p.sup.0.sup.)e.sup.0)(b.sub.1)=(a.sub.e.sub.0)(31)

(40) If there are three or more unavailable data shares, the processing amount when the multiplication by the inverse matrix is performed is expressed by the formula (32).
.sup.2MUL+RED(32)

(41) If one (a.sub.e0, for example) of a.sub.e0, . . . , a.sub.e1 is reconstructed, the required processing amount is expressed by the formula (33).
MUL+RED(33)

(42) Then, in the same manner as in the case of the reduction of data-share components, the processing amount can be reduced by one order as expressed by the formula (34).
(1)(BMUL+BRED)(34)

(43) After such an order reduction is repeated, and the processing amount is expressed by the formula (35).
(+1)/2MUL+(1)/2BMUL+RED+(1)/2BRED(35)

(44) Comparing with the formula (26), the sum of MUL and BMUL is the same, and the ratio of MUL is reduced by approximately half, although only BRED has increased. However, the increment is equal to the reduction in MUL, so that if BUL+BRED<MUL, the total processing amount has decreased.

(45) The formula (35) shows the minimum absolute computation amount. However, the method of reconstructing the data shares one by one and repeating removal of the data-share component from the parity shares has a problem that the parallelism of MUL and RED decreases. Comparing the multiplication by the inverse matrix that has a high level of parallelism, the number of processings that can only sequentially be performed increases, so that the performance of the CPU may decrease depending on the number of MULs or REDs that can be executed in parallel by the CPU. Thus, it can be concluded that a method of using the inverse matrix to reconstruct a number of data shares equal to the number of MULs or REDs that can be executed in parallel by the CPU and removing the reconstructed components from the parity shares each time the data shares are reconstructed is the quickest. The number of MULs that can be executed in parallel is 1 and 2 for Ivy-Bridge and Haswell available from Intel Corporation, respectively, and the number of REDs that can be executed in parallel is 2 for both Ivy-Bridge and Haswell.

(46) An example of an algorithm that implements the decoding process for the error correcting code described above is expressed by the following formula. In the formula, f denotes the number of unavailable data shares, d.sub.0, . . . , d.sub.kf1 are identification number of kf available data shares, p.sub.0, . . . , p.sub.f1 are identification numbers of f available parity shares, e.sub.0, . . . , e.sub.f1 are identification numbers of plaintexts to be reconstructed, kf data shares b.sub.d0, . . . , b.sub.dkf1 and f parity shares b.sub.p0, . . . , b.sub.pf1 are inputs, a row C.sub.0, . . . of a coefficient matrix and coefficients c.sub.0 and c.sub.1 are auxiliary inputs, and plaintexts a.sub.e0, . . . , a.sub.ef1 are outputs.

(47) TABLE-US-00001 1: $b^{}:=\left(\begin{array}{c}\begin{array}{c}{b}_0^{}\\ b_1^{}\end{array}\\ \mathrm{.Math.}\\ b_{f-1}^{}\end{array}\right)=\left(\begin{array}{c}{b}_{p_0}-\underset{i<f}{.Math.}{x}^{p_0{d}_i}{b}_{d_i}\\ b_{p_1}-\underset{i<f}{.Math.}{x}^{p_1{d}_i}{b}_{d_i}\\ \mathrm{.Math.}\\ b_{p_{f-1}}-\underset{i<f}{.Math.}{x}^{p_{f-1}{d}_i}{b}_{d_i}\end{array}\right)$ 2: if f {3,4} then 3: $b^{}:=\left(\begin{array}{c}\begin{array}{c}{b}_0^{}\\ b_1^{}\end{array}\\ \mathrm{.Math.}\\ b_{f-2}^{}\end{array}\right)=\left(\begin{array}{c}{b}_1^{}-x^{\left(p_1-p_0\right)e_0}{b}_0^{}\\ b_2^{}-x^{\left(p_2-p_0\right)e_0}{b}_0^{}\\ \mathrm{.Math.}\\ b_{f-1}^{}-x^{\left(p_{f-1}-p_0\right)e_0}{b}_0^{}\end{array}\right)$ 4: f := f 1 5: else 6: b := b(just regarded as being so and not copied or otherwise used.) 7: f := f 8: i := 0 9: while f > 2 do 10: $\left(\begin{array}{c}{a}_{e_{f^{}-1}}\\ a_{e_{f^{}-2}}\end{array}\right)=\left(\begin{array}{cccc}{\left(C_i\right)}_{00}& {\left(C_i\right)}_{01}& \mathrm{.Math.}& {\left(C_1\right)}_{0\left(f^{}-1\right)}\\ {\left(C_i\right)}_{10}& {\left(C_i\right)}_{11}& \mathrm{.Math.}& {\left(C_1\right)}_{1\left(f^{}-1\right)}\end{array}\right)\left(\begin{array}{c}\begin{array}{c}{b}_0^{}\\ b_1^{}\end{array}\\ \mathrm{.Math.}\\ b_{f^{}-1}^{}\end{array}\right)$ 11: $b^{}:=\left(\begin{array}{c}\begin{array}{c}{b}_0^{}\\ b_1^{}\end{array}\\ \mathrm{.Math.}\\ b_{f^{}-3}^{}\end{array}\right)=\left(\begin{array}{c}{b}_0^{}-\underset{f^{}-2i<f^{}}{.Math.}{x}^{p_0{e}_i}{a}_{e_i}\\ b_1^{}-\underset{f^{}-2i<f^{}}{.Math.}{x}^{p_1{e}_i}{a}_{e_i}\\ \mathrm{.Math.}\\ b_{f^{}-3}^{}-\underset{f^{}-2i<f^{}}{.Math.}{x}^{p_{f^{}-3}{e}_i}{a}_{e_i}\end{array}\right)\left(\mathrm{update}\right)$ 12: f := f 2 13: if f = 2 then 14: a.sub.e.sub.1 := c.sub.1b.sub.1, where c.sub.1 = (x.sup.p.sub.1.sup.e.sub.1 x.sup.p.sub.0.sup.e.sub.1 .sup.+ .sup.(p.sub.1.sup.p.sub.0.sup.)e.sub.0).sup.1 15: b.sub.0' := x.sup.p.sub.0.sup.e.sub.1a.sub.e.sub.1 (update) 16: a.sub.e.sub.0 := c.sub.0b.sub.0.sup. , where c.sub.0 = (x.sup.p.sub.0.sup.e.sub.0).sup.1

(48) The coefficient matrix C.sub.i and the coefficients c.sub.0 and c.sub.1, which are auxiliary inputs, are set as follows depending on the value of .

(49) If =1, c.sub.0 in the following formula is the only coefficient. Since c.sub.0 is an inverse element of a power of x, c.sub.0 can be calculated only by referring to a table.
c.sub.0=(x.sup.p.sup.0.sup.e.sup.0).sup.1

(50) If =2, c.sub.1 in the following formula is also used in addition to c.sub.0 described above.
c.sub.1=(x.sup.p.sup.1.sup.e.sup.1x.sup.p.sup.0.sup.e.sup.1.sup.+(p.sup.1.sup.p.sup.0.sup.)e.sup.0).sup.1

(51) If =3, in addition to c.sub.0 and c.sub.1 described above, an inverse matrix of the 1-th order square matrix of the left-hand side of the formula (28) is used.

(52) If =4, c.sub.0 and c.sub.1 described above and the first (numbered 0) and second rows of the inverse matrix of the 1-th order square matrix of the left-hand side of the formula (28) are used. Each of the rows of the inverse matrix is equal to a sequence of coefficients used to reconstruct one plaintext share. Considering the number of MULs or REDs that can be executed in parallel by the CPU described above, the plaintext shares can be efficiently reconstructed on a two-by-two basis from the end to the beginning, so that only the last two rows are needed.

(53) If =5, as in the case where =4, the plaintext shares are reconstructed on a two-by-two basis from the end to the beginning, so that the last two rows of an inverse matrix of the -th order square matrix are first needed. The last two rows of an inverse matrix of the remaining 2-th square matrix are then needed. In this way, for each i that satisfies a relation 2i<3, the last two rows of an inverse matrix of the 2i-th square matrix in the upper left part of the -th square matrix are needed. There is no need to determine /2 inverse matrices, and only one triangulation is needed. This is because, in both triangulation and backward substitution, the upper left part of the matrix is not affected by the lower right part, and a triangular matrix of a matrix minus the rightmost two columns and the bottom two rows is the same as a triangular matrix of the whole of the matrix minus the rightmost two columns and the bottom two rows.

(54) In the following, an embodiment of the present invention will be described in detail. In the drawings, components having the same function are denoted by the same reference numerals, and redundant descriptions thereof will be omitted.

(55) As illustrated in FIG. 1, a decoding apparatus 1 according to the embodiment comprises a vector input part 10, a vector conversion part 11, an inverse matrix generation part 12, a plaintext computation part 13, and a vector output part 14. A decoding method according to the embodiment is achieved by the decoding apparatus 1 performing processings in steps illustrated in FIG. 2.

(56) The decoding apparatus 1 is a special apparatus formed by a well-known or dedicated computer in which a special program is loaded, the computer having a central processing unit (CPU: Central Processing Unit), a main memory (RAM: Random Access Memory), and other components. The decoding apparatus 1 performs the processings under the control of the central processing unit. Data input to the decoding apparatus 1 and data resulting from the processings are stored in the main memory, and the data stored in the main memory is loaded to the central processing unit and used for other processings. At least part of the processing parts of the decoding apparatus 1 may be formed by hardware, such as an integrated circuit.

(57) With reference to FIG. 2, a procedure of the decoding method according to the embodiment will be described.

(58) In step S10, an n-th order vector b is input to the vector input part 10. available elements b.sub.p0, . . . , b.sub.p1 (b.sub.p0, . . . , b.sub.p1GF(x.sup.q)) of the parity shares of the n-th order vector b are fed to the vector conversion part 11. In addition, k available elements b.sub.d0, . . . , b.sub.dk1 of the data shares of the vector b are fed to the vector output part 14. The vector b is an n-th order vector obtained by multiplying a k-th order vector a defined by the formula (36) by an n-by-k matrix A defined by the formula (37).

(59) $\begin{array}{cc}a=\left(\begin{array}{c}{a}_0\\ \mathrm{.Math.}\\ a_{k-1}\end{array}\right)& \left(36\right)\\ \begin{array}{c}{A}_{\mathrm{ij}}=\{\begin{array}{cc}1& \mathrm{if}i=j\\ 0& \mathrm{if}ij\mathrm{and}i<k\\ x^{\left(i-k\right)j}& \mathrm{if}ik\end{array}\\ \mathrm{where}i\left\{0,\mathrm{.Math.},n-1\right\},j\left\{0,\mathrm{.Math.},k-1\right\}\end{array}& \left(37\right)\end{array}$

(60) In step S11, the vector conversion part 11 generates a -th order vector b using b.sub.p0, . . . , b.sub.p1 according to the formula (38). The vector b is fed to the plaintext computation part 13.

(61) $\begin{array}{cc}{b}^{}=\left(\begin{array}{c}{b}_0^{}\\ b_1^{}\\ \mathrm{.Math.}\\ b_{-1}^{}\end{array}\right)=\left(\begin{array}{c}{b}_{p_0}-\underset{i<k-}{.Math.}{x}^{p_0{d}_i}{b}_{d_i}\\ b_{p_1}-\underset{i<k-}{.Math.}{x}^{p_1{d}_i}{b}_{d_i}\\ \mathrm{.Math.}\\ b_{p_{-1}}-\underset{i<k-}{.Math.}{x}^{p_{-1}{d}_i}{b}_{d_i}\end{array}\right)& \left(38\right)\end{array}$

(62) In step S12, the inverse matrix generation part 12 generates a -by- inverse matrix A.sup.1 according to the formula (39). The inverse matrix A.sup.1 is fed to the plaintext computation part 13. Since if the of the k parity shares used for reconstruction are determined, the inverse matrix A.sup.1 can be generated, the inverse matrix A.sup.1 may be computed in advance for all of the combinations. In that case, the inverse matrix generation part 12 has only to select an appropriate one of the inverse matrices generated in advance.

(63) 0$\begin{array}{cc}{A}^{-1}={\left(\begin{array}{cccc}{x}^{p_0{e}_0}& x^{p_0{e}_1}& \mathrm{.Math.}& x^{p_0{e}_{-1}}\\ x^{p_1{e}_0}& x^{p_1{e}_1}& \mathrm{.Math.}& x^{p_1{e}_{-1}}\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ x^{p_{-1}{e}_0}& x^{p_{-1}{e}_1}& \mathrm{.Math.}& x^{p_{-1}{e}_{-1}}\end{array}\right)}^{-1}& \left(39\right)\end{array}$

(64) In step S13, the plaintext computation part 13 computes elements a.sub.e0, . . . , a.sub.e1 of the vector a by multiplying the vector b by the inverse matrix A.sup.1 according to the formula (40). The elements a.sub.e0, . . . , a.sub.e1 are fed to the vector output part 14.

(65) $\begin{array}{cc}{\left(\begin{array}{cccc}{x}^{p_0{e}_0}& x^{p_0{e}_1}& \mathrm{.Math.}& x^{p_0{e}_{-1}}\\ x^{p_1{e}_0}& x^{p_1{e}_1}& \mathrm{.Math.}& x^{p_1{e}_{-1}}\\ \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ x^{p_{-1}{e}_0}& x^{p_{-1}{e}_1}& \mathrm{.Math.}& x^{p_{-1}{e}_{-1}}\end{array}\right)}^{-1}\left(\begin{array}{c}{b}_0^{}\\ b_1^{}\\ \mathrm{.Math.}\\ b_{-1}^{}\end{array}\right)=\left(\begin{array}{c}{a}_{e_0}\\ a_{e_1}\\ \mathrm{.Math.}\\ a_{e_{-1}}\end{array}\right)& \left(40\right)\end{array}$

(66) In step S14, the vector output part 14 reconstructs the k-th order vector a by using as elements thereof the k elements b.sub.d0, . . . , b.sub.dk1 received from the vector input part 10 and the 4 elements a.sub.e0, . . . , a.sub.e1 computed by the plaintext computation part 13, and outputs the vector a.

(67) The decoding apparatus according to the embodiment configured as described above performs decoding by reducing the order of the matrix A from the k-th order square matrix to the -th order square matrix and then applying the inverse matrix A.sup.1. Thus, (k) polynomial multiplications of k polynomial multiplications are less computationally intensive polynomial multiplications that involve only transposition of terms, so that the decoding process is efficient. The computation amount of an ordinary polynomial multiplication is q.sup.2 for an extension degree q. On the other hand, the computation amount of the multiplication involving only transposition of terms is q if the transportation actually occurs and 1 if a flag of the transposition amount is set.

(68) The decoding technique according to the present invention can be applied to the computational secret sharing. The computational secret sharing is a secret sharing scheme that inhibits reconstruction of original data from a number of variances smaller than a predetermined number based on the computational security. The computational secret sharing is described in the reference literature 1 listed below, for example. [Reference Literature 1] H. Krawczyk, Secret sharing made short., CRYPTO 1993, pp. 136-146, 1993

(69) The present invention is not limited to the embodiment described above, and modifications can be made as required without departing from the spirit of the present invention. The various processings described above with regard to the embodiment are not necessarily sequentially performed in the order described above but also can be performed in parallel with or independently of each other depending on the processing capacity of the apparatus that performs the processings or as required.

(70) [Program and Storage Medium]

(71) When a computer carries out the various processing functions of the apparatus according to the embodiment described above, the specific processings of the functions that the apparatus needs to have are described in a program. The various processing functions of the apparatus described above are implemented on the computer by the computer executing the program.

(72) The program that describes the specific processings can be recorded in a computer readable recording medium. Any computer readable recording medium can be used, such as a magnetic recording device, an optical disk, a magneto-optical recording medium, or a semiconductor memory.

(73) The program can be distributed by selling, transferring or lending a portable recording medium, such as a DVD, a CD-ROM, or an USB memory, on which the program is recorded, for example. Furthermore, the program may be distributed by storing the program in a memory of a server computer and transferring the program from the server computer to another computer.

(74) The computer that executes the program first temporarily stores, in a memory thereof, the program recorded on a portable recording medium or transferred from a server computer, for example. When performing the processings, the computer reads the program from the memory of the computer and performs the processings according to the read program. In an alternative implementation, the computer may read the program directly from the portable recording medium and perform the processings according to the program, or the computer may perform the processings according to the program each time the computer receives the program transferred from the server computer. As a further alternative, the processings described above may be performed on an application service provider (ASP) basis, in which the server computer does not transfer the program to the computer, and the processings are implemented only through execution instruction and result acquisition. The program according to the embodiment of the present invention include a quasi-program, which is information to be processed by a computer (such as data that is not a direct instruction to a computer but has a property that defines the processings performed by the computer).

(75) Although the apparatus according to the embodiment of the present invention have been described as being implemented by a computer executing a predetermined program, at least part of the specific processings may be implemented by hardware.