A matrix and key generation device in which N is an integer which is 1 or larger, n is an integer which is between 0 and N-1 inclusive, K n is an integer which is 1 or larger, i and j are integers, T n is a matrix having K n rows, k n is a vector which includes K n pieces of elements, T n [j] is a row on a j-th order of the matrix T n , k n [j] is an element on a j-th order of the vector k n , m n is an upper limit number in which the elements of the vector k n are duplicated, M n is a set composed of m n pieces of elements which are different from each other, M n [i] is an element on an i-th order of the set M n , the element on the j-th order of the vector k n is an element corresponding to a row on the j-th order of the matrix T n , and the matrices T 0 , ..., T N-1 and the vectors k 0 , ..., k N-1 are inputs, the matrix and key generation device comprising: a vector generation unit operable to generate a vector x n , of which a number of pieces of elements is K n and each of the elements is an element of the set Mn, with respect to each of n=0, ..., N-1 so that x n [i]≠x n [j] if k n [i]=k n [j] at i≠j; a set generation unit operable to generate a set B n,j with respect to each of n=0, ..., N-1 and each of j=1, ..., K n so that individual elements correspond to combinations of N-1 pieces of elements, the N-1 pieces of elements being individually selected from sets M 0 , ..., M N-1 other than the set M n , and x n [j], and the elements for all of the combinations are included; a matrix generation unit operable to generate a matrix T n ' with respect to each of n=0, ..., N-1 so that rows identical to T n [j] are included in a number equal to a number of elements of the set B n,j for all of j=1, ..., K n ; and a key generation unit operable to generate a vector k n ' with respect to each of n=0, ..., N-1 so that an element of the matrix T n ', the element corresponding to a row identical to T n [j], corresponds to a combination of k n [j] and an element of the set B n,j and further, the elements of the set B n,j are different from each other when there are a plurality of rows identical to T n [j]. a vector generation unit operable to generate a vector x n , of which a number of pieces of elements is K n and each of the elements is an element of the set Mn, with respect to each of n=0, ..., N-1 so that x n [i]≠x n [j] if k n [i]=k n [j] at i≠j; a set generation unit operable to generate a set B n,j with respect to each of n=0, ..., N-1 and each of j=1, ..., K n so that individual elements correspond to combinations of N-1 pieces of elements, the N-1 pieces of elements being individually selected from sets M 0 , ..., M N-1 other than the set M n , and x n [j], and the elements for all of the combinations are included; a matrix generation unit operable to generate a matrix T n ' with respect to each of n=0, ..., N-1 so that rows identical to T n [j] are included in a number equal to a number of elements of the set B n,j for all of j=1, ..., K n ; and a key generation unit operable to generate a vector k n ' with respect to each of n=0, ..., N-1 so that an element of the matrix T n ', the element corresponding to a row identical to T n [j], corresponds to a combination of k n [j] and an element of the set B n,j and further, the elements of the set B n,j are different from each other when there are a plurality of rows identical to T n [j]. <EOS>