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 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