A decoding apparatus for decoding an (n,k) systematic code with φ, 2≤φ≤4, unavailable data shares, wherein x is an element of an irreducible polynomial f[X] that generates an extension field GF(x q ), n and k are integers equal to or greater than 2, n ≥ 2k-1, m denotes an integer equal to or greater than 1, m = n-k, a 0 , ..., a k-1 are elements of the extension field GF(x q ), a denotes a k-th order vector having elements a 0 , ..., a k-1 , A denotes a n-by-k matrix defined by the following formula: A ij = { 1 if i = j 0 if i ≠ j and i < k x i − k j if i ≥ k where i ∈ {0,..., n -1}, j ∈ {0,..., k - 1}. b 0 , ..., b n-1 are elements of the extension field GF(x q ), b denotes an n-th order vector having the elements b 0 , ..., b n-1 obtained by multiplying the vector a by the matrix A, the first to k-th elements b 0, b 1 , ..., b k-1 of the vector b are referred to as data shares and the other elements of the vector b are referred to as parity shares, φ ≤ m, d 0 , ..., d k-φ-1 denote different integers equal to or greater than 0 and smaller than k which are identification numbers of available data shares, e 0 , ..., e φ-1 denote different integers equal to or greater than 0 and smaller than k that are different from d 0 , ..., d k-φ-1 which are identification numbers of the unavailable data shares, and p 0 , ..., P φ-1 denote different integers equal to or greater than k and smaller than n which are identification numbers of the parity shares used for reconstruction of the unavailable data shares, and the decoding apparatus comprises: a vector conversion part that generates a φ-th order vector b' using φ elements b p0 , ..., b pφ-1 of the vector b according to the following formula: b ′ = b 0 ′ b 1 ′ ⋮ b φ − 1 ′ = b p 0 − ∑ i < k − φ x p 0 d i b d i b p 1 − ∑ i < k − φ x p 1 d i b d i ⋮ b p φ − 1 − ∑ i < k − φ x p φ − 1 d i b d i , generates a φ-1-th order vector b" using the vector b' according to the following formula: b " = b 0 " b 1 " ⋮ b φ − 2 " = b 1 ′ − x p 1 − p 0 e 0 b 0 ′ b 2 ′ − x p 2 − p 0 e 0 b 0 ′ ⋮ b φ − 1 ′ − x p φ − 1 − p 0 e 0 b 0 ′ . an inverse matrix generation part that generates a (φ-1)-by-(φ-1) inverse matrix A" -1 according to the following formula: A " − 1 = x p 1 e 1 − x p 0 e 1 + p 1 − p 0 e 0 ⋯ x p 1 e φ − 1 − x p 1 − p 0 e 0 x p 2 e 1 − x p 0 e 1 + p 2 − p 0 e 0 ⋯ x p 2 e φ − 1 − x p 2 − p 0 e 0 ⋮ ⋱ ⋮ x p φ − 1 e 1 − x p 0 e 1 + p φ − 1 − p 0 e 0 ⋯ x p φ − 1 e φ − 1 − x p φ − 1 − p 0 e 0 − 1 ; and a plaintext computation part that computes the elements a e1 , ..., a eφ-1 of the vector a by multiplying the vector b" and the inverse matrix A" -1 and computes the element a e0 of the vector a according to the following formula: a e 0 = x − p 0 e 0 b 0 ′ − ∑ 1 ≤ i < φ x p 0 e i a e i a vector conversion part that generates a φ-th order vector b' using φ elements b p0 , ..., b pφ-1 of the vector b according to the following formula: b ′ = b 0 ′ b 1 ′ ⋮ b φ − 1 ′ = b p 0 − ∑ i < k − φ x p 0 d i b d i b p 1 − ∑ i < k − φ x p 1 d i b d i ⋮ b p φ − 1 − ∑ i < k − φ x p φ − 1 d i b d i , generates a φ-1-th order vector b" using the vector b' according to the following formula: b " = b 0 " b 1 " ⋮ b φ − 2 " = b 1 ′ − x p 1 − p 0 e 0 b 0 ′ b 2 ′ − x p 2 − p 0 e 0 b 0 ′ ⋮ b φ − 1 ′ − x p φ − 1 − p 0 e 0 b 0 ′ . an inverse matrix generation part that generates a (φ-1)-by-(φ-1) inverse matrix A" -1 according to the following formula: A " − 1 = x p 1 e 1 − x p 0 e 1 + p 1 − p 0 e 0 ⋯ x p 1 e φ − 1 − x p 1 − p 0 e 0 x p 2 e 1 − x p 0 e 1 + p 2 − p 0 e 0 ⋯ x p 2 e φ − 1 − x p 2 − p 0 e 0 ⋮ ⋱ ⋮ x p φ − 1 e 1 − x p 0 e 1 + p φ − 1 − p 0 e 0 ⋯ x p φ − 1 e φ − 1 − x p φ − 1 − p 0 e 0 − 1 ; and a plaintext computation part that computes the elements a e1 , ..., a eφ-1 of the vector a by multiplying the vector b" and the inverse matrix A" -1 and computes the element a e0 of the vector a according to the following formula: a e 0 = x − p 0 e 0 b 0 ′ − ∑ 1 ≤ i < φ x p 0 e i a e i <EOS>